Tài liệu Luận văn thạc sĩ nghiên cứu thuật toán filter wrapper tìm tập rút gọn của bảng quyết định không đầy đủ và ứng dụng phát hiện tàu thuyền từ ảnh vệ tinh

BỘ GIÁO DỤC VIỆN HÀN LÂM VÀ ĐÀO TẠO KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PHẠM QUANG NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Phạm Quang Nam NGHIÊN CỨU THUẬT TOÁN FILTER-WRAPPER HỆ THỐNG THÔNG TIN TÌM TẬP RÚT GỌN CỦA BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ VÀ ỨNG DỤNG PHÁT HIỆN TÀU THUYỀN TỪ ẢNH VỆ TINH LUẬN VĂN THẠC SĨ NGÀNH MÁY TÍNH 2021 Hà Nội – 2021 BỘ GIÁO DỤC VIỆN HÀN LÂM VÀ ĐÀO TẠO KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Phạm Quang Nam NGHIÊN CỨU THUẬT TOÁN FILTER-WRAPPER TÌM TẬP RÚT GỌN CỦA BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ VÀ ỨNG DỤNG PHÁT HIỆN TÀU THUYỀN TỪ ẢNH VỆ TINH Chuyên ngành : Hệ thống thông tin Mã số: 8480104 LUẬN VĂN THẠC SĨ NGÀNH MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC : PGS.TS. NGUYỄN LONG GIANG Hà Nội – 2021 LỜI CAM ĐOAN Tôi là Phạm Quang Nam, học viên khóa 2019B, ngành Công nghệ thông tin, chuyên ngành Hệ Thống Thông Tin. Tôi xin cam đoan luận văn “Nghiên cứu thuật toán filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ và ứng dụng phát hiện tàu thuyền từ ảnh vệ tinh” là do tôi nghiên cứu, tìm hiểu và phát triển dưới sự hướng dẫn của PGS.TS. Nguyễn Long Giang, không phải sự sao chép từ các tài liệu, công trình nghiên cứu của người khác mà không ghi rõ trong tài liệu tham khảo. Tôi xin chịu trách nhiệm về lời cam đoan này. Hà Nội, ngày tháng năm 2021 Tác giả Phạm Quang Nam LỜI CẢM ƠN Lời cảm ơn trân trọng đầu tiên em muốn dành tới các thầy cô Học viện khoa học và công nghệ Việt Nam, Viện công nghệ thông tin, Viện Hàn lâm khoa học và công nghệ Việt Nam nói chung và các thầy cô trong bộ môn Hệ thống thông tin cũng như khoa Công nghệ thông tin nói riêng đã tận tình giảng dạy và truyền đạt những kiến thức quý báu trong suốt khoá cao học vừa qua, giúp em có những kiến thức chuyên môn nền tảng để làm cơ sở lý luận khoa học cho luận văn này. Đặc biệt em xin chân thành cảm ơn thầy PGS.TS. Nguyễn Long Giang đã dìu dắt và hướng dẫn em trong suốt quá trình làm luận văn, sự chỉ bảo và định hướng của thầy giúp em tự tin nghiên cứu những vấn đề mới và giải quyết bài toán một cách khoa học. Em xin trân trọng cảm ơn Ban giám hiệu Học viện khoa học công nghệ Việt Nam - Viện Hàn lâm khoa học và công nghệ Việt Nam đã tạo các điều kiện cho em được học tập và làm luận văn một cách thuận lợi. Mặc dù đã cố gắng rất nhiều, nhưng chắc chắn trong quá trình học tập cũng như luận văn không khỏi những thiết sót. Em rất mong được sự thông cảm và chỉ bảo tận tình của các thầy cô và các bạn. Hà Nội, ngày . tháng năm 2021 Tác giả Phạm Quang Nam MỤC LỤC DANH MỤC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT ...................................................... i DANH MỤC HÌNH VẼ VÀ ĐỒ THỊ ............................................................................ ii MỞ ĐẦU .........................................................................................................................1 1. Tính cấp thiết ..........................................................................................................1 2. Mục tiêu nghiên cứu ...............................................................................................2 3. Đối tượng và phạm vi nghiên cứu ..........................................................................3 4. Phương pháp nghiên cứu ........................................................................................3 5. Nội dung nghiên cứu ..............................................................................................3 6. Ý nghĩa khoa học và thực tiễn ................................................................................3 7. Bố cục của luận văn ................................................................................................4 CHƯƠNG 1. TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ DUNG SAI .............................................................................................................5 1.1. Hệ thông tin và mô hình tập thô truyền thống .................................................5 1.1.1. Hệ thông tin .................................................................................................5 1.1.2. Mô hình tập thô truyền thống ......................................................................6 1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai .................................6 1.2.1. Hệ thông tin không đầy đủ ..........................................................................7 1.2.2. Mô hình tập thô dung sai .............................................................................7 1.2.3. Bảng quyết định không đầy đủ ....................................................................8 1.2.4. Ma trận dung sai ........................................................................................10 1.3. Tổng quan về rút gọn thuộc tính theo tiếp cận tập thô dung sai ...................11 1.3.1. Tổng quan về rút gọn thuộc tính ...............................................................11 1.3.2. Tiếp cận filter, wrapper trong rút gọn thuộc tính ......................................12 1.3.3. Rút gọn thuộc tính theo tiếp cận tập thô dung sai .....................................14 1.4. Các nghiên cứu liên quan đến rút gọn thuộc tính theo tiếp cận tập dung sai 16 1.4.1. Rút gọn thuộc tính theo tiếp cận tập thô dung sai .....................................16 1.5. Kết luận..........................................................................................................18 CHƯƠNG 2. THUẬT TOÁN FILTER-WRAPPER TÌM TẬP RÚT GỌN CỦA BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ ..................................................................19 2.1. Mở đầu ...........................................................................................................19 2.2. Xây dựng độ đo khoảng cách trong bảng quyết định không đầy đủ .............20 2.2.1. Xây dựng độ đo khoảng cách giữa hai tập hợp .........................................20 2.2.2. Xây dựng độ đo khoảng cách giữa hai tập thuộc tính ...............................21 2.3. Rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng khoảng cách ……………………………………………………………………………...23 2.3.1. Xây dựng thuật toán filter tìm tập rút gọn của bảng quyết định không đầy đủ………………………………………………………………………………...24 2.3.2. Thuật toán filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ………………………………………………………………………………...26 2.3.3. Thực nghiệm và đánh giá kết quả ...............................................................28 2.4. Kết luận chương 2 .........................................................................................33 CHƯƠNG 3: THỬ NGHIỆM RÚT GỌN THUỘC TÍNH VỚI BÀI TOÁN PHÂN LỚP ĐỐI TƯỢNG TRONG ẢNH VIỄN THÁM ........................................................34 3.1. Bài toán ...............................................................................................................34 3.2. Xây dựng mô hình giải quyết bài toán ...............................................................34 Hình 3.3. Thực thi mô hình phân lớp gán nhãn cho ảnh viễn thám ..........................36 3.3. Môi trường chạy thử nghiệm ..............................................................................36 3.4. Thực hiện chương trình ......................................................................................37 3.4.1 Tiền xử lý dữ liệu .........................................................................................37 3.4.2 Huấn luyện mô hình .....................................................................................44 3.4.3 Thực thi mô hình ..........................................................................................50 CHƯƠNG 4: KẾT LUẬN .............................................................................................54 TÀI LIỆU THAM KHẢO .............................................................................................55 DANH MỤC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT Từ viết tắt Từ chuẩn Diễn giải AI Artificial Intelligence Trí tuệ nhân tạo CNN Convolution Neural Network Mạng nơ-ron tích chập ML Machine Learning Học máy, máy có khả năng học tập SVM Vector Support Machine Máy vector hỗ trợ DANH MỤC HÌNH VẼ VÀ ĐỒ THỊ Hình 1.1: Quy trình rút gọn thuộc tính ..........................................................................15 Hình 1.2: Cách tiếp cận filter và wrapper trong rút gọn thuộc tính...............................16 Hình 1.3: Mô hình phương pháp rút gọn thuộc tính theo hướng tiếp cận thô dung sai 17 Hình 2.1: Thời gian thực hiện ba thuật toán (tính bằng giây) .......................................35 Hình 2.2: Số lượng thuộc tính tập rút gọn của ba thuật toán .........................................37 Hình 2.3: Độ chính xác phân lớp của ba thuật toán.......................................................37 Hình 3.1: Xây dựng dữ liệu phân lớp từ tập dữ liệu huấn luyện ...................................40 Hình 3.2: Ví dụ minh hoạ cửa sổ trượt ..........................................................................41 Hình 3.3: Thực thi mô hình phân lớp gán nhãn cho ảnh viễn thám ..............................42 Hình 3.4: Giao diện màn hình chính..............................................................................43 Hình 3.5: Giao diện tác vụ Nạp dữ liệu .........................................................................44 Hình 3.6: Hiển thị hình ảnh dạng lưới ...........................................................................45 Hình 3.7: Giao diện tác vụ Gán nhãn dữ liệu ................................................................46 Hình 3.8: Gán nhãn cho từng ô lưới ..............................................................................47 Hình 3.9: Giao diện tác vụ Hiển thị thuộc tính ..............................................................48 Hình 3.10: Bảng thuộc tính của dữ liệu hình ảnh ..........................................................49 Hình 3.11: Các thành phần trong huấn luyện mô hình ..................................................50 Hình 3.12: Giao diện tác vụ Rút gọn thuộc tính ............................................................51 Hình 3.13: Giao diện tác vụ Huấn luyện mô hình .........................................................53 Hình 3.14: Huấn luyện mô hình phân lớp .....................................................................54 Hình 3.15: Giao diện tác vụ Kiểm thử mô hình ............................................................55 Hình 3.16: Giao diện Kiểm thử mô hình phân lớp ........................................................56 Hình 3.17: Các thành phần trong dự đoán tàu thuyền ...................................................57 Hình 3.18: Giao diện tác vụ Dự đoán tàu thuyền ..........................................................58 Hình 3.19: Dự đoán tàu thuyền......................................................................................60 1. Tính cấp thiết MỞ ĐẦU Trong bối cảnh ngày nay, sự tăng trưởng không ngừng của dung lượng dữ liệu và số lượng các thuộc tính đã gây khó khăn, thách thức cho việc thực thi các thuật toán khai phá dữ liệu, phát hiện tri thức. Rút gọn thuộc tính (còn gọi là rút gọn chiều, hay rút gọn đặc trưng) là bài toán quan trọng trong bước tiền xử lý dữ liệu với mục tiêu là loại bỏ các thuộc tính dư thừa, không cần thiết nhằm tăng tính hiệu quả của các thuật toán khai phá dữ liệu. Hiện nay có hai cách tiếp cận chính đối với bài toán rút gọn thuộc tính [1-2]: filter (lọc) và wrapper (đóng gói). Cách tiếp cận filter thực hiện việc rút gọn thuộc tính độc lập với thuật khai phá dữ liệu sử dụng sau này. Các thuộc tính được chọn chỉ dựa trên độ quan trọng của chúng trong việc phân lớp dữ liệu. Trong khi đó, cách tiếp cận wrapper tiến hành việc lựa chọn bằng cách áp dụng ngay thuật khai phá, độ chính xác của kết quả được lấy làm tiêu chuẩn để lựa chọn các tập con thuộc tính. Lý thuyết tập thô (Rough set) do Pawlak đề xuất [3] được xem là công cụ hiệu quả giải quyết bài toán rút gọn thuộc tính trong bảng quyết định đầy đủ, đã và đang được cộng đồng nghiên cứu về tập thô thực hiện lâu nay. Trong các bài toán thực tế, các bảng quyết định thường thiếu giá trị trên miền giá trị thuộc tính, gọi là bảng quyết định không đầy đủ. Ví dụ với bảng quyết định chẩn đoán bệnh viêm gan với các thuộc tính là các triệu chứng, các bác sĩ không thể thu thập đầy đủ các triệu chứng của tất cả các bệnh nhân để ra quyết định. Để giải quyết bài toán rút gọn thuộc tính trực tiếp trên bảng quyết định không đầy đủ mà không qua bước tiền xử lý giá trị thiếu, Kryszkiewicz [4] mở rộng quan hệ tương đương trong lý thuyết tập thô truyền thống thành quan hệ dung sai và xây dựng mô hình tập thô dung sai (tolerance rough set). Các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận mô hình tập thô dung sai là các nghiên cứu mở rộng của các phương pháp rút gọn thuộc tính theo tiếp cận tập thô truyền thống. Đây là các phương pháp heuristic bao gồm các bước: xây dựng độ đo, định nghĩa tập rút gọn và độ quan trọng của thuộc tính sử dụng độ đo được xây dựng, trên cơ sở đó xây dựng thuật toán heuristic tìm tập rút gọn theo tiêu chuẩn là độ quan trọng của thuộc tính. Các nghiên cứu liên quan đến rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai tập trung vào các phương pháp chính như: các phương pháp sử dụng miền dương mở rộng [5], [6], [7], [8], [9], các phương 1 pháp sử dụng ma trận phân biệt, hàm phân biệt mở rộng [10], [11], [12], [13], [14], [15], [16], các phương pháp sử dụng entropy thông tin mở rộng [17], [18-20], [21], [22], [23], các phương pháp sử dụng độ đo lượng thông tin [24], [25], [26], phương pháp sử dụng khoảng cách [27], [28] và một số phương pháp sử dụng các độ đo khác như quan hệ không phân biệt mở rộng [29], độ bao phủ của thuộc tính [30], độ đo không nhất quán [31]. Theo tiếp cận tập thô dung sai, luận văn tiến sĩ [32] đã đề xuất các phương pháp rút gọn thuộc tính sử dụng độ đo khoảng cách. Nhìn chung, các phương pháp rút gọn thuộc tính theo tiếp cận tập thô và tập thô dung sai đều hướng tới mục tiêu là tìm được tập rút gọn hiệu quả nhất để thực thi mô hình phân lớp dựa trên các tiêu chí: giảm thiểu số thuộc tính tập rút gọn để giảm thiểu độ phức tạp và nâng cao độ chính xác của mô hình. Các thuật toán đã đề xuất trong các phương pháp nêu trên đều là các thuật toán heuristic theo tiếp cận filter truyền thống, nghĩa là tập rút gọn thu được là tập thuộc tính tối thiểu bảo toàn độ đo được định nghĩa. Việc đánh giá độ chính xác của mô hình phân lớp được thực hiện sau khi tìm được tập rút gọn. Do đó, tập rút gọn của các thuật toán filter nêu trên chưa tối ưu về số lượng thuộc tính và độ chính xác phân lớp. Trong luận văn tiến sĩ [33] và công trình [34], [35], các tác giả đề xuất hướng tiếp cận kết hợp filterwrapper tìm tập rút gọn của bảng quyết định đầy đủ dựa trên lý thuyết tập thô mờ (fuzzy rough set). Trong đó, giai đoạn filter tìm các ứng viên cho tập rút gọn dựa vào độ đo (còn gọi là tập rút gọn xấp xỉ), giai đoạn wrapper tính toán độ chính xác phân lớp của các ứng viên và lựa chọn tập rút gọn xấp xỉ có độ chính xác phân lớp cao nhất. Kết quả thử nghiệm cho thấy, số lượng thuộc tính tập rút gọn giảm thiểu đáng kể so với các phương pháp filter, trong khi độ chính xác phân lớp vẫn được bảo toàn và cải thiện hơn. Tuy nhiên, các phương pháp trong [33], [34], [35] đều thực hiện trên bảng quyết định đầy đủ theo tiếp cận tập thô mờ (fuzzy rough set). Do đó, động lực nghiên cứu của luận văn là nghiên cứu, tìm hiểu hướng tiếp cận kết hợp filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai nhằm giảm thiểu số lượng thuộc tính tập rút gọn, trong khi cố gắng bảo toàn, cải thiện độ chính xác mô hình phân lớp. 2. Mục tiêu nghiên cứu Trên cơ sở phân tích các vấn đề còn tồn tại của các nghiên cứu liên quan và xác định động lực nghiên cứu, mục tiêu của luận văn là: 2 Tìm hiểu thuật toán filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai nhằm giảm thiểu số lượng thuộc tính tập rút gọn (từ đó giảm thiểu độ phức tạp của mô hình) và cải thiện độ chính xác của mô hình phân lớp. 3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của luận văn là bảng quyết định không đầy đủ, mô hình tập thô dung sai, các phương pháp rút gọn thuộc tính theo tiếp cận tập thô. Phạm vi nghiên cứu của luận văn là các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai. 4. Phương pháp nghiên cứu Phương pháp nghiên cứu của luận văn là nghiên cứu, tìm hiểu lý thuyết và nghiên cứu thực nghiệm. 1) Nghiên cứu lý thuyết: Nghiên cứu các thuật toán rút gọn thuộc tính theo tiếp cận tập thô dung sai đã công bố. Phân tích ưu điểm, nhược điểm và các vấn đề còn tồn tại của các thuật toán đã có. Trên cơ sở đó, tìm hiểu các độ đo cải tiến và thuật toán theo hướng tiếp cận kết hợp filter-wrapper. 2) Nghiên cứu thực nghiệm: Tiến hành cài đặt, chạy thử nghiệm, so sánh, đánh giá với các thuật toán khác trên các bộ số liệu mẫu từ kho dữ liệu UCI nhằm minh chứng về tính hiệu quả của thuật toán về mặt lý thuyết. 5. Nội dung nghiên cứu 1) Nghiên cứu, tìm hiểu phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ dựa trên mô hình tập thô dung sai theo tiếp cận kết hợp filter-wrapper. 2) Cài đặt, thử nghiệm, so sánh, đánh giá thuật toán đề xuất với các thuật toán khác đã công bố trên các bộ dữ liệu thử nghiệm từ kho dữ liệu UCI [36]. 6. Ý nghĩa khoa học và thực tiễn Ý nghĩa khoa học: Tìm hiểu thuật toán mới tìm tập rút gọn của bảng quyết định không đầy đủ theo tiếp cận kết hợp filter-wrapper trong trường hợp bảng quyết định cố định. Cụ thể luận văn có các kết quả chính như sau: 3 Tìm hiểu một độ đo khoảng cách mới và tìm hiểu thuật toán theo tiếp cận kết hợp filter-wrapper IDS_FW_DAR [19] tìm tập rút gọn của bảng quyết định không đầy đủ sử dụng độ đo khoảng cách. Kết quả thử nghiệm trên các bộ số liệu mẫu từ kho dữ liệu UCI [36] cho thấy, thuật thoán filter-wrapper IDS_FW_DAR giảm thiểu đáng kể số lượng thuộc tính tập rút gọn và cải thiện độ chính xác mô hình phân lớp so với các thuật toán filter khác. Ý nghĩa thực tiễn Thuật toán có thể áp dụng để giải quyết bài toán rút gọn thuộc tính trong các ứng dụng thực tiễn nhằm loại bỏ các thuộc tính dư thừa, nâng cao hiệu quả các mô hình khai phá dữ liệu và học máy, đặc biệt là các hệ thống cơ sở dữ liệu không đầy đủ, thiếu giá trị trong các lĩnh vực chẩn đoán y tế, tài chính ngân hàng. 7. Bố cục của luận văn Bố cục của luận văn gồm phần mở đầu và ba chương nội dung, phần kết luận và danh mục các tài liệu tham khảo. Chương 1 trình bày các khái niệm cơ bản về lý thuyết tập thô truyền thống, mô hình tập thô dung sai và tổng quan về tiếp cận filter-wrapper trong rút gọn thuộc tính. Chương 1 cũng trình bày các nghiên cứu liên quan đến rút gọn thuộc tính theo tiếp cận tập thô dung sai trong mấy năm gần đây. Nội dung chính của luận văn được trình bày trong chương 2. Chương 2 trình bày kết quả tìm hiểu về xây dựng độ đo khoảng cách mới và thuật toán filter-wrapper IDS_FW_DAR tìm tập rút gọn của bảng quyết định không đầy đủ. Chương 3 áp dụng thuật toán filter-wrapper IDS_FW_DAR vào bài toán phát hiện tàu thuyền từ ảnh vệ tinh. Cuối cùng, phần kết luận nêu những nội dung đã tìm hiểu của luận văn, hướng phát triển tiếp theo. 4 CHƯƠNG 1. TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ DUNG SAI 1.1. Hệ thông tin và mô hình tập thô truyền thống Lý thuyết tập thô truyền thống do Z.Pawlak [3] đề xuất là công cụ toán học hiệu quả để biểu diễn và xử lý các khái niệm không chắc chắn. Phương pháp tiếp cận chính của lý thuyết tập thô là dựa trên quan hệ tương đương (hay quan hệ không phân biệt được) để xấp xỉ tập hợp. Khi đó, mọi tập đối tượng đều được xấp xỉ bởi hai tập rõ là xấp xỉ dưới và xấp xỉ trên của nó. Mỗi tập xấp xỉ được hợp thành bởi một hoặc nhiều lớp tương đương, là cơ sở để xây dựng các thuật toán rút gọn thuộc tính và khai phá tri thức từ dữ liệu. Trong phần này, luận văn trình bày một số khái niệm cơ bản trong lý thuyết tập thô truyền thống của Z.Pawlak [3], là cơ sở nền tảng cho mô hình tập thô dung sai được trình bày ở phần 1.2. 1.1.1. Hệ thông tin Hệ thông tin là công cụ biểu diễn tri thức dưới dạng một bảng dữ liệu gồm n cột ứng với N thuộc tính và M hàng ứng với M đối tượng. Một cách hình thức, hệ thông tin là một cặp IS = (U , A) trong đó U là tập hữu hạn, khác rỗng các đối tượng; A là tập hữu hạn, khác rỗng các thuộc tính. Mỗi thuộc tính a  A xác định một ánh xạ: a : U → Va với Va là tập giá trị của thuộc tính a  A . Xét hệ thông tin IS = (U , A) . Mỗi tập con các thuộc tính P  A xác định một quan hệ hai ngôi trên U, ký hiệu là IND ( P ) , xác định bởi   IND ( P ) = ( u, v ) U U a  P, a (u ) = a ( v ) . IND ( P ) là quan hệ P-không phân biệt được. Dễ thấy rằng IND ( P ) là một quan hệ tương đương trên U. Nếu ( u, v )  IND ( P ) thì hai đối tượng u và v không phân biệt được bởi các thuộc tính trong P. Quan hệ tương đương IND ( P ) xác định một phân hoạch trên U, ký hiệu là U / IND ( P ) hay U / P . Ký hiệu lớp tương đương trong phân hoạch   U / P chứa đối tượng u là u P , khi đó u P = v U ( u, v )  IND ( P ) . 5 1.1.2. Mô hình tập thô truyền thống Cho hệ thông tin IS = (U , A) và tập đối tượng X  U . Với một tập thuộc tính B  A cho trước, chúng ta biểu diễn X thông qua các lớp tương đương của U / B (còn gọi là biểu diễn X bằng tri thức có sẵn B), người ta xấp xỉ X bởi hợp của một số hữu hạn các lớp tương đương của U / B . Có hai cách xấp xỉ tập đối tượng X thông qua tập thuộc tính B , được gọi là B-xấp xỉ dưới và B-xấp xỉ trên của X, ký hiệu là lượt là BX và BX , được xác định như sau:     BX = u U u B  X , BX = u U u B  X   . Tập BX bao gồm tất cả các phần tử của U chắc chắn thuộc vào X, còn tập BX bao gồm các phần tử của U có thể thuộc vào X dựa trên tập thuộc tính B. Từ hai tập xấp xỉ nêu trên, ta định nghĩa các tập BN B ( X ) = BX − BX : B-miền biên của X, U − BX : B-miền ngoài của X. B-miền biên của X là tập chứa các đối tượng có thể thuộc hoặc không thuộc X, còn B-miền ngoài của X chứa các đối tượng chắc chắn không thuộc X. Sử dụng các lớp của phân hoạch U/B, các xấp xỉ dưới và trên của X có thể viết lại BX = Y U / B Y  X  , BX = Y U / B Y  X  . Trong trường hợp BN B ( X ) =  thì X được gọi là tập chính xác (exact set), ngược lại X được gọi là tập thô (rough set). Xét hệ thông tin IS = (U , A) với B, D  A , ta gọi B-miền dương của D là tập được xác định như sau ( BX ) POS B ( D) = X U / D Rõ ràng POS B ( D) là tập tất cả các đối tượng u sao cho với mọi v U mà   u ( B ) = v ( B ) ta đều có u ( D ) = v ( D ) . Nói cách khác, POSB ( D) = u U u   u D . B 1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai Phần này trình bày một số khái niệm cơ bản về mô hình tập thô dung sai trên hệ thông tin không đầy đủ do Kryszkiewicz [4] đề xuất. 6 1.2.1. Hệ thông tin không đầy đủ Xét hệ thông tin IS = (U , A) , nếu tồn tại u U và a  A sao cho a ( u ) chứa giá trị thiếu (missing value) thì IS được gọi là hệ thông tin không đầy đủ, trái lại IS được gọi là hệ thông tin đầy đủ. Ta biểu diễn giá trị thiếu được ký hiệu là ‘*’ và hệ thông tin không đầy đủ là IIS = (U , A) . 1.2.2. Mô hình tập thô dung sai Xét hệ thông tin không đầy đủ IIS = (U , A) , với tập thuộc tính P, P  A ta định nghĩa một quan hệ nhị phân trên U như sau:   SIM ( P ) = ( u, v ) U U a  P, a (u ) = a ( v )  a (u ) = '*'  a ( v ) = '*' . Quan hệ SIM ( P ) không phải là quan hệ tương đương vì chúng có tính phản xạ, đối xứng nhưng không có tính bắc cầu. Do đó, SIM ( P ) là một quan hệ dung sai (tolerance relation), hay quan hệ tương tự (similarity relation) trên U. Dễ thấy rằng SIM ( P ) = aP SIM (a) . Gọi S P ( u ) là tập v U ( u, v )  SIM ( P ) . S P ( u ) là tập lớn nhất các đối tượng không có khả năng phân biệt được với u trên tập thuộc tính P dựa trên quan hệ dung sai, còn gọi là một lớp dung sai hay một hạt thông tin. Ký hiệu tập tất cả các lớp dung sai sinh bởi quan hệ SIM(P) trên U là U / SIM ( P ) , khi đó các lớp dung sai trong U / SIM ( P ) không phải là một phân hoạch của U mà hình thành một phủ của U vì chúng có thể giao nhau và uU SP (u ) = U . Cho tập đối tượng X , dựa trên quan hệ dung sai các tập P-xấp xỉ dưới và P-xấp xỉ trên của X trong hệ thông tin không đầy đủ, ký hiệu lần lượt là PX và PX , được xác định như sau    PX = u U SP ( u )  X = u  X SP (u )  X   S PX = u U SP ( u )  X   = 7 P  (u ) u U  Với các tập xấp xỉ nêu trên, ta gọi P-miền biên của X là tập BN P ( X ) = PX − PX , và P-miền ngoài của X là tập U − PX . Trong trường hợp BN P ( X ) =  thì X được gọi là tập chính xác (exact set), ngược lại X được gọi là tập thô dung sai (tolerance rough set). Với P, D  A , ta gọi P-miền dương của D là tập được xác định như sau POS P ( D ) = ( PX ) X U / D Rõ ràng POS P ( D ) là tập tất cả các đối tượng u sao cho với mọi v  S P ( u ) ta đều có u ( D ) = v ( D ) . Nói cách khác, POS P ( D ) = u  U S P ( u )  u D  . Như vậy, mô hình tập thô dung sai là mô hình tập thô mở rộng dựa trên quan hệ dung sai trên các hệ thông tin không đầy đủ với các tập xấp xỉ dưới, xấp xỉ trên được định nghĩa dựa trên quan hệ dung sai. 1.2.3. Bảng quyết định không đầy đủ Một lớp đặc biệt của các hệ thông tin có vai trò quan trọng trong nhiều ứng dụng là bảng quyết định. Bảng quyết định DS là một hệ thông tin với tập thuộc tính A được chia thành hai tập khác rỗng rời nhau C và D , lần lượt được gọi là tập thuộc tính điều kiện và tập thuộc tính quyết định. Tức là DS = (U , C  D ) với C  D =  . Xét bảng quyết định DS = (U , C  D ) , nếu tồn tại u U và c  C sao cho c ( u ) thiếu giá trị thì DS được gọi là bảng quyết định không đầy đủ, trái lại DS được gọi là bảng quyết định đầy đủ. Ta biểu diễn bảng quyết định không đầy đủ là IDS = (U , C  D ) với d  D, '*'  Vd . Không mất tính chất tổng quát, giả thiết D chỉ gồm một thuộc tính quyết định duy nhất d  . Cho bảng quyết định không đầy đủ IDS = (U , C  d ) . Với P  C , u U ,  P (u ) = d ( v ) v  S P (u ) gọi là hàm quyết định suy rộng của đối tượng u trên tập thuộc tính P. Nếu |  C (u ) |= 1 với mọi u U thì IDS là nhất quán, trái lại IDS là không nhất quán. 8 Với bảng quyết định không đầy đủ IDS, miền dương của C đối với d  là POSC (d ) = {CX | X U / {d }} , khi đó IDS là nhất quán khi và chỉ khi POSC (d ) = U Với P  C , quan hệ dung sai SIM ( P ) xác định một phủ (covering) trên U, ký hiệu là K ( P ) = U / SIM ( P ) = S P ( u ) u U  . Ký hiệu COVER (U ) = K ( P ) P  C  là tập tất cả các phủ của U sinh bởi các tập con thuộc tính P  C . Trên COVER (U ) , phần tử nhỏ nhất K ( ) = S A ( u ) S A ( u ) = u, u U  được gọi là phủ rời rạc, phần tử lớn nhất   K ( ) = S A ( u ) S A ( u ) = U , u U được gọi là phủ một khối. Một quan hệ thứ tự bộ phận được định nghĩa trên COVER (U ) như sau: K ( P ) K (Q )  S P ( u )  SQ ( u ) , u U . Dấu đẳng thức K ( P ) = K (Q )  S P ( u ) = SQ ( u ) , u U . K ( P ) K (Q )  K ( P ) K (Q ) và K ( P )  K (Q ) . Ví dụ 1.1. Xét bảng quyết định về các xe hơi cho ở Bảng 1.1. Bảng 1.1 là bảng quyết định không đầy đủ IDS = (U , C  d ) với U = {u1 , u2 , u3 , u4 , u5 , u6 } , C = {c1 , c2 , c3 , c4 } với c1 (Đơn giá), c2 (Km đã đi), c3 (Kích thước), c4 (Tốc độ) và d (Gia tốc) Bảng 1.1. Bảng quyết định không đầy đủ về các xe hơi Ô tô Đơn giá Km đã đi Kích thước Tốc độ Gia tốc u1 Cao Nhiều Trung bình Thấp Nhanh u2 Thấp * Trung bình Thấp Nhanh u3 * * Gọn nhẹ Cao Chậm u4 Cao * Trung bình Cao Nhanh u5 * * Trung bình Cao Rất nhanh u6 Thấp Nhiều Trung bình * Nhanh Các lớp dung sai của các đối tượng như sau: 9 SC ( u1 ) = u1 , SC ( u2 ) = u2 , u6  , SC ( u3 ) = u3 , S B ( u4 ) = u4 , u5  , S B ( u5 ) = u4 , u5 , u6  , S B ( u6 ) = u2 , u5 , u6  . Ta có U / d  = { X 1 , X 2 , X 3} với X 1 = {u1 , u2 , u4 , u6 }, X 2 = {u3}, X 3 = {u5} . Các tập xấp xỉ dưới đối với C là CX 1 = u1 , u2 , CX 2 = u3, CX 3 =  . Do đó, POSC (d ) = {u1 , u2 , u3} Hàm quyết định suy rộng của các đối tượng trên tập thuộc tính C là:  C (u1 ) = {Nhanh},  C (u2 ) = {Nhanh},  C (u3 ) = {Chậm},  C (u4 ) = {Nhanh, Rất nhanh},  C (u5 ) = {Nhanh, Rất nhanh},  C (u6 ) = {Nhanh, Rất nhanh}. Do đó, IDS là bảng quyết định không đầy đủ không nhất quán. 1.2.4. Ma trận dung sai Ma trận dung sai là công cụ biểu diễn giá trị quan hệ dung sai của các đối tượng trong bảng quyết định không đầy đủ và được định nghĩa như sau: Định nghĩa 1.1. Cho bảng quyết định không đầy đủ IDS = (U , C  d ) với U = u1 , u2 ,..., un  và P  C . Khi đó, ma trận dung sai của quan hệ dung sai SIM ( P ) , ký hiệu là M ( P ) =  pij nn , được định nghĩa như sau:  p11 p M ( P ) =  21  ...   pn1 p12 p22 ... pn 2 ... ... ... ... p1n  p2 n   ...   pnn  trong đó pij là giá trị của quan hệ dung sai giữa hai đối tượng ui và u j trên tập thuộc tính P, pij = 1 nếu u j  SP ( ui ) và pij = 0 nếu u j  SP ( ui ) với i, j = 1..n Với việc biểu diễn quan hệ dung sai SIM ( P ) bằng ma trận dung sai M ( P ) , ta có mọi u i U , SP ( ui ) = u j U pij = 1 và SP ( ui ) =  pij . Với P, Q  C, u U ta có n j =1 S P Q ( u ) = S P ( u )  SQ ( u ) . Giả sử M ( P ) =  pij  , M (Q ) =  qij  là hai ma trận nn nn dung sai của SIM ( P ) , SIM (Q ) , khi đó ma trận dung sai trên tập thuộc tính S = P  Q là 10 M ( S ) = M ( P  Q ) =  sij  nn với sij = pij . qij Xét bảng quyết định không đầy đủ IDS = (U , C  D ) với U = u1 , u2 ,..., un  , P  C , X  U . Giả sử tập đối tượng X được biểu diễn bằng véc tơ một chiều X = ( x1 , x2 ,..., xn ) với xi = 1 nếu ui  X và xi = 0 nếu ui  X . Khi đó,     PX = ui U pij  x j , j = 1..n và PX = ui U pij . x j   , j = 1..n . Ví dụ 1.2. Xét bảng quyết định ở Ví dụ 1.1, khi đó ma trận dung sai của quan hệ SIM ( C ) là 1 0  0 M ( P) =  0 0  0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 1  0  0 1  1 Khi đó ta có SC ( u1 ) = u1 , SC ( u2 ) = u2 , u6  , SC ( u3 ) = u3 , S B ( u4 ) = u4 , u5 , S B ( u5 ) = u4 , u5 , u6  , S B ( u6 ) = u2 , u5 , u6  . 1.3. Tổng quan về rút gọn thuộc tính theo tiếp cận tập thô dung sai 1.3.1. Tổng quan về rút gọn thuộc tính Trong bối cảnh ngày nay, các cơ sở dữ liệu ngày càng gia tăng về dung lượng dữ liệu cũng như số lượng thuộc tính, gây rất nhiều khó khăn cho việc thực thi các thuật toán khai phá dữ liệu. Vấn đề đặt ra là phải tìm cách rút gọn số lượng thuộc tính mà không làm mất mát những thông tin cần thiết phục vụ nhiệm vụ khai phá dữ liệu. Do đó, rút gọn thuộc tính (hay còn gọi là rút gọn chiều - dimension reduction, rút gọn đặc trưng - feature reduction) trở thành đề tài thu hút sự quan tâm của nhiều nhà nghiên cứu thuộc các lĩnh vực nhận dạng thống kê, học máy, khai phá dữ liệu. Rút gọn thuộc tính là bài toán quan trọng trong bước tiền xử lý dữ liệu với mục tiêu là loại bỏ các thuộc tính dư thừa, không liên quan nhằm tăng tính hiệu quả của các thuật toán khai phá dữ liệu: Gia tăng tốc độ, cải thiện chất lượng và tính dễ hiểu của các kết quả thu được. Các kỹ thuật rút gọn thuộc tính thường được phân thành hai loại: Lựa chọn thuộc tính (Attribute selection) và biến đổi thuộc tính (Attribute transformation). 11 Lựa chọn thuộc tính là chọn một tập con tối thiểu tốt nhất (theo một nghĩa nào đó) từ tập thuộc tính ban đầu của tập dữ liệu. Trong khi đó, biến đổi thuộc tính là thực hiện việc biến đổi các thuộc tính ban đầu thành thành một tập các thuộc tính mới với số lượng ít hơn sao cho bảo tồn được thông tin nhiều nhất. Trong luận văn này, tôi nghiên cứu, tìm hiểu hướng tiếp cận lựa chọn thuộc tính, gọi chung là rút gọn thuộc tính. 1.3.2. Tiếp cận filter, wrapper trong rút gọn thuộc tính Rút gọn thuộc tính là quá trình lựa chọn một tập con gồm P thuộc tính từ tập gồm M thuộc tính (P ≤ M) sao cho không gian thuộc tính được thu gọn lại một cách tối ưu theo một tiêu chuẩn nhất định. Việc tìm ra một tập con thuộc tính tốt nhất (làm mất đi ít nhất lượng thông tin cần thiết) thường khó thực hiện; nhiều bài toán liên quan đến vấn đề này là những bài toán NP - khó. Nhìn chung, một thuật toán lựa chọn thuộc tính thường bao gồm bốn bước cơ bản: (1) Tạo lập tập con, (2) Đánh giá tập con, (3) Kiểm tra điều kiện dừng, (4) Kiểm chứng kết quả. Tạo lập tập con thuộc tính là quá trình tìm kiếm liên tiếp nhằm tạo ra các tập con để đánh giá, lựa chọn. Giả sử có M thuộc tính trong tập dữ liệu ban đầu, khi đó số tất cả các tập con từ M thuộc tính sẽ là 2 M . Với số ứng viên này, việc tìm tập con tối ưu, ngay cả khi M không lớn lắm, cũng là một việc không thể. Vì vậy, phương pháp chung để tìm tập con thuộc tính tối ưu là lần lượt tạo ra các tập con để so sánh. Mỗi tập con sinh ra bởi một thủ tục sẽ được đánh giá theo một tiêu chuẩn nhất định và đem so sánh với tập con tốt nhất trước đó. Nếu tập con này tốt hơn, nó sẽ thay thế tập cũ. Quá trình tìm kiếm tập con thuộc tính tối ưu sẽ dừng khi một trong bốn điều kiện sau xảy ra: (a) đã thu được số thuộc tính quy định, (b) số bước lặp quy định cho quá trình lựa chọn đã hết, (c) việc thêm vào hay loại bớt một thuộc tính nào đó không cho một tập con tốt hơn, (d) đã thu được tập con tối ưu theo tiêu chuẩn đánh giá. Tập con tốt nhất cuối cùng phải được kiểm chứng thông qua việc tiến hành các phép kiểm định, so sánh các kết quả khai phá với tập thuộc tính “tốt nhất” này và tập thuộc tính ban đầu trên các tập dữ liệu thực hoặc nhân tạo khác nhau. 12