Tài liệu Rút gọn thuộc tính trong bảng quyết định động theo tiếp cận tập thô

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- VŨ VĂN ĐỊNH 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 LUẬN ÁN TIẾN SỸ TOÁN HỌC HÀ NỘI – 2016 2 VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ……..….***………… VŨ VĂN ĐỊNH 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 LUẬN ÁN TIẾN SỸ TOÁN HỌC Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62 46 01 10 Người hướng dẫn khoa học: 1. GS.TS Vũ Đức Thi 2. PGS.TS Ngô Quốc Tạo HÀ NỘI – 2016 1 LỜI CAM ĐOAN Tôi xin cam đoan bản luận án tiến sĩ này là công trình do chính tôi nghiên cứu và thực hiện. Các thông tin số liệu được sử dụng trong luận án hoàn toàn trung thực và chính xác. Tất cả sự giúp đỡ cho việc thực hiện luận án đã được xin phép và cảm ơn. Các thông tin trích dẫn trong luận án đã được ghi rõ nguồn gốc. Tác giả luận án Vũ Văn Định 2 LỜI CẢM ƠN Lời đầu tiên, tôi xin bày tỏ lòng biết ơn sâu sắc đến GS.TS Vũ Đức Thi, PGS.TS Ngô Quốc Tạo, TS. Nguyễn Long Giang, những người Thầy đã không ngại gian khó tận tình giúp đỡ và hướng dẫn tôi trong suốt quá trình nghiên cứu và hoàn thành luận án. Tôi xin chân thành cảm ơn đến Ban lãnh đạo Viện Công nghệ thông tin thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam, Học viện Khoa học và Công nghệ thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam, Phòng quản lý đào tạo, các phòng ban chức năng và tập thể các Nhà khoa học của Viện Công nghệ thông tin và Học viện Khoa học và Công nghệ đã giúp đỡ tôi trong suốt quá trình học tập và nghiên cứu. Tôi xin được bày tỏ lòng biết ơn đến Ban giám hiệu, lãnh đạo các đơn vị Trường Đại học Điện lực đã hỗ trợ, tạo điều kiện tốt nhất cho tôi trong suốt quá trình thực hiện luận án. Tôi xin chân thành cảm ơn tới lãnh đạo và các đồng nghiệp tại Khoa Công nghệ thông tin, Phòng Khảo thí và Đảm bảo chất lượng giáo dục trường Đại học Điện lực đã động viên giúp đỡ tôi trong thời gian tôi học tập và nghiên cứu. Cuối cùng tôi bày tỏ lòng biết ơn đến gia đình và người thân của tôi, những người luôn sát cánh bên tôi để động viên, giúp đỡ tôi vượt qua khó khăn để hoàn thành luận án. 3 MỤC LỤC LỜI CAM ĐOAN.............................................................................................................................1 LỜI CẢM ƠN....................................................................................................................................2 MỤC LỤC ..........................................................................................................................................3 DANH MỤC CÁC THUẬT NGỮ...............................................................................................6 BẢNG CÁC KÝ HIỆU, TỪ VIẾT TẮT.....................................................................................7 DANH MỤC HÌNH, BẢNG..........................................................................................................8 MỞ ĐẦU.............................................................................................................................................9 CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ.........................................................................18 1.1. Hệ thông tin và mô hình tập thô truyền thống ................................................18 1.1.1. Hệ thông tin....................................................................................18 1.1.2. Mô hình tập thô truyền thống.........................................................19 1.1.3. Bảng quyết định đầy đủ..................................................................21 1.1.4. Tập rút gọn và tập lõi ....................................................................22 1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai................................23 1.2.1. Hệ thông tin không đầy đủ .............................................................23 1.2.2. Mô hình tập thô dung sai ...............................................................24 1.2.3. Bảng quyết định không đầy đủ.......................................................27 1.3. Các khái niệm về tập rút gọn của bảng quyết định không đầy đủ.................29 1.3.1. Tập rút gọn dựa trên hàm quyết định suy rộng .............................29 1.3.2. Tập rút gọn dựa trên miền dương ..................................................30 1.3.3. Tập rút gọn dựa trên độ đo lượng thông tin ..................................30 1.3.4. Tập rút gọn dựa trên ma trận phân biệt ........................................30 1.3.5. Tập rút gọn dựa trên ma trận dung sai..........................................31 1.3.6. Tập rút gọn dựa trên hàm phân bố, hàm ấn định ..........................32 1.3.7. Tập rút gọn dựa trên metric...........................................................32 1.4. Kết luận chương 1 ............................................................................................33 4 CHƯƠNG 2. ĐỀ XUẤT PHÂN NHÓM VÀ ĐÁNH GIÁ CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ........34 2.1. Mở đầu ..............................................................................................................34 2.2. Đề xuất phân nhóm các phương pháp rút gọn thuộc tính ..............................35 2.2.1 Bảng ký hiệu các tập rút gọn của bảng quyết định không đầy đủ .36 2.2.2 Mối liên hệ giữa các khái niệm tập rút gọn RD , RI , RTM ...............37 2.2.3 Mối liên hệ giữa R và RP ..............................................................40 2.2.4 Mối liên hệ giữa RD và R .............................................................41 2.2.5 Mối liên hệ giữa R và R .............................................................44 2.2.6 Đề xuất phân nhóm các phương pháp rút gọn thuộc tính .............45 2.3. Đánh giá các phương pháp rút gọn thuộc tính................................................48 2.3.1. Luật quyết định và các độ đo đánh giá hiệu năng .........................48 2.3.2. Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định ....54 2.3.3. Nghiên cứu sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn ........................................................................................................57 2.3.4. Thử nghiệm sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn ........................................................................................................60 2.3.5. Lựa chọn, đánh giá các phương pháp rút gọn thuộc tính..............65 2.4. Kết luận chương 2 ............................................................................................67 CHƯƠNG 3. ĐỀ XUẤT CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ.............................................................................68 3.1. Mở đầu ..............................................................................................................68 3.2. Chọn tập đối tượng đại diện cho bài toán rút gọn thuộc tính.........................68 3.2.1. Chọn tập đối tượng đại diện cho hệ thông tin không đầy đủ.........69 3.2.2. Chọn tập đối tượng đại diện cho bảng quyết định không đầy đủ ..73 3.3. Phương pháp rút gọn thuộc tính sử dụng lượng thông tin mở rộng có điều kiện ...........................................................................................................................78 5 3.3.1. Độ đo lượng thông tin mở rộng .....................................................79 3.3.2. Xây dựng lượng thông tin mở rộng có điều kiện ...........................80 3.3.3. Rút gọn thuộc tính sử dụng lượng thông tin mở rộng có điều kiện82 3.3.4. Thử nghiệm và đánh giá kết quả....................................................87 3.4. Phương pháp rút gọn thuộc tính sử dụng hàm quan hệ..................................91 3.4.1. Ma trận quan hệ và hàm quan hệ ..................................................92 3.4.2. Rút gọn thuộc tính sử dụng hàm quan hệ ......................................95 3.4.3. Thử nghiệm và đánh giá kết quả....................................................98 3.5. Kết luận chương 3 ..........................................................................................100 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ.....................................................................104 6 DANH MỤC CÁC THUẬT NGỮ Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh Hệ thông tin không đầy đủ Incomplete Information System Bảng quyết định không đầy đủ Incomplete Decision Table Quan hệ không phân biệt được Indiscernibility Relation Quan hệ dung sai Tolerance Relation Tập thô dung sai Tolerance Rough Set Xấp xỉ dưới Lower Approximation Xấp xỉ trên Upper Approximation Rút gọn thuộc tính Attribute Reduction Tập rút gọn Reduct Tập lõi Core Ma trận phân biệt Indiscernibility Matrix Hàm phân biệt Indiscernibility Function Ma trận quan hệ Relational Matrix Hàm quan hệ Relations Function Lượng thông tin mở rộng Extended information quantity Luật quyết định Decision Rule 7 BẢNG CÁC KÝ HIỆU, TỪ VIẾT TẮT Ký hiệu, từ viết tắt Diễn giải IIS  U , A Hệ thông tin không đầy đủ IDS  U , A  d  Bảng quyết định không đầy đủ U Số đối tượng A Số thuộc tính điều kiện của bảng quyết định u a Giá trị của đối tượng u tại thuộc tính a SIM  A Quan hệ dung sai trên tập thuộc tính A SA u  Lớp dung sai của đối tượng u trên tập thuộc tính A U/A Phân hoạch của U sinh bởi tập thuộc tính A. U / SIM  A Phủ của U sinh bởi tập thuộc tính A. COVER U  Họ tất cả các phủ của U.  A (u ) Hàm quyết định suy rộng của đối tượng u đối với A. AX A  xấp xỉ dưới của X AX A  xấp xỉ trên của X BN P  X  B - miền biên của X POS A  D  A  miền dương của D I B /d  Lượng thông tin của tập thuộc tính B đối với thuộc tính quyết định d   CEI R d  Lượng thông tin mở rộng của tập thuộc tính R đối với thuộc tính quyết định d MC A Họ các khối đồng nhất cực đại trên tập A DIS R  Hàm quan hệ của IDS trên R 8 DANH MỤC HÌNH, BẢNG Hình 1.1. Mối quan hệ giữa các tập rút gọn .................................................46 Hình 2.1. Sự thay đổi độ hỗ trợ  trên các tập rút gọn..................................64 Hình 3.1. Sự thay đổi độ hỗ trợ  trên hai tập rút gọn của hai thuật toán EIQBAR và MBAR....................................................................................90 Bảng 1.1. Bảng quyết định về bệnh cúm.........................................................21 Bảng 1.2. Bảng thông tin về xe hơi.................................................................24 Bảng 1.3. Bảng quyết định về các xe hơi........................................................28 Bảng 2.1. Ký hiệu các tập rút gọn trong bảng quyết định không đầy đủ. ......36 Bảng 2.2. Bảng quyết định minh họa Ví dụ 2.1 ..............................................41 Bảng 2.3. Bảng quyết định minh họa Ví dụ 2.2 ..............................................43 Bảng 2.4. Bảng quyết định không đầy đủ về các tivi ......................................49 Bảng 2.5. Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 1 ..63 Bảng 2.6. Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 2 ..63 Bảng 3.1. Bảng thông tin về các xe hơi ..........................................................72 Bảng 3.2. Bảng quyết định không đầy đủ về các xe hơi .................................77 Bảng 3.3. Bảng quyết định không đầy đủ mô tả về các xe hơi .......................86 Bảng 3.5. Tập rút gọn của thuật toán MBAR và Thuật toán EIQBAR ...........89 Bảng 3.6. Kết quả tính toán độ chắc chắn, độ nhất quán và độ hỗ trợ trên các tập rút gọn ................................................................................................90 Bảng 3.7. Bảng quyết định không đầy đủ mô tả về các tivi ............................92 Bảng 3.8. Kết quả thực hiện thuật toán MBAR, Thuật toán EIQBAR và Thuật toán RBAR ................................................................................................99 Bảng 3.9. Tập rút gọn của thuật toán MBAR, Thuật toán EIQBAR và Thuật toán RBAR ................................................................................................99 9 MỞ ĐẦU Lý thuyết tập thô do Pawlak [31] đề xuất vào những năm đầu thập niên tám mươi của thế kỷ hai mươi được xem là công cụ hữu hiệu để giải quyết các bài toán phân lớp, phát hiện luật…chứa dữ liệu không đầy đủ, không chắc chắn. Từ khi xuất hiện, lý thuyết tập thô đã được sử dụng hiệu quả trong các bước của quá trình khai phá dữ liệu và khám phá tri thức, bao gồm tiền xử lý số liệu, khai phá dữ liệu và đánh giá kết quả thu được. Rút gọn thuộc tính và trích lọc luật quyết định (luật phân lớp) là hai ứng dụng chính của lý thuyết tập thô trong khai phá dữ liệu. Rút gọn thuộc tính thuộc giai đoạn tiền xử lý dữ liệu còn trích lọc luật thuộc giai đoạn khai phá dữ liệu. Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa nhằm tìm tập con nhỏ nhất của tập thuộc tính điều kiện (tập rút gọn) mà bảo toàn thông tin phân lớp của bảng quyết định. Dựa trên tập rút gọn thu được, việc sinh luật và phân lớp đạt hiệu quả cao nhất. Rút gọn thuộc tính trong bảng quyết định theo tiếp cận lý thuyết tập thô của Pawlak [31] là chủ đề nghiên cứu sôi động trong hai thập kỷ qua. Cho đến nay, có rất nhiều phương pháp rút gọn thuộc tính đã được đề xuất bởi các nhóm nghiên cứu theo các hướng tiếp cận khác nhau như: hướng tiếp cận dựa trên miền dương, hướng tiếp cận dựa trên ma trận, hướng tiếp cận dựa trên độ đo entropy, hướng tiếp cận tính toán hạt, hướng tiếp cận dựa trên độ đo khoảng cách... Phương pháp rút gọn thuộc tính dựa trên miền dương do Pawlak [48] đề xuất, phương pháp này đã xây dựng thuật toán tính miền dương POS C D  . Về sau, các công bố trong [31][49][11][25] đã tiếp tục cải tiến thuật toán này. Phương pháp rút gọn thuộc tính sử dụng các phép toán trong đại số quan hệ do Hu Xiaohua và các cộng sự [14] đưa ra, phương pháp này xây dựng thuật toán tìm tập lõi và tập rút gọn của bảng quyết định. Tuy nhiên khái niệm tập lõi có nhược điểm và đã được tác giả trong luận án [1] 10 khắc phục. Phương pháp rút gọn thuộc tính sử dụng ma trận phân biệt do Skowron [8] đề xuất được xây dựng trên khái niệm ma trận phân biệt, hàm phân biệt. Phương pháp này cũng đã được Ye Dong Yi và các cộng sự [51] khắc phục nhược điểm tìm tập rút gọn và tập lõi trong bảng quyết định không nhất quán. Phương pháp rút gọn thuộc tính sử dụng các độ đo trong tính toán hạt được Zadeh [53] giới thiệu về mô hình tính toán hạt và đã được các tác giả [21], [22], [54] đề xuất các thuật toán heuristic tìm tập rút gọn sử dụng độ đo phép kết hạt bởi thuộc tính làm tiêu chuẩn đánh giá độ quan trọng của thuộc tính. Phương pháp rút gọn thuộc tính sử dụng entropy thông tin do các tác giả Wang Guo Yin và các cộng sự [43], [45], [46], [47], [48] phát triển từ khái niệm Entropy thông tin Shannon giới thiệu vào năm 1948. Tuy nhiên, các tác giả trong [42], [43], đã phân tích nhược điểm của định nghĩa độ quan trọng của thuộc tính trong [47] và đề xuất định nghĩa độ quan trọng mới, từ đó xây dựng thuật toán heuristic tìm tập rút gọn sử dụng entropy Shannon có điều kiện. Phương pháp rút gọn thuộc tính sử dụng metric do tác giả trong luận án[2] đề xuất dựa trên cơ sở khái niệm metric do R.López de Mántaras [38] xây dựng. Song song với việc đề xuất các phương pháp rút gọn thuộc tính, các nhà nghiên cứu tập trung vào đề xuất các độ đo làm tiêu chuẩn định lượng để so sánh, đánh giá các phương pháp rút gọn thuộc tính. Trong luận án [2] tác giả đã tìm mối liên hệ giữa các tập rút gọn của các phương pháp rút gọn, dựa vào đó đã phân các phương pháp rút gọn làm 3 nhóm: Nhóm 1: Nhóm phương pháp tìm tập rút gọn Pawlak; Nhóm 2: Nhóm phương pháp tìm tập rút gọn Entropy Shannon (bao gồm phương pháp sử dụng entropy Shannon và phương pháp sử dụng các phép toán trong đại số quan hệ); Nhóm 3: Nhóm phương pháp tìm tập rút gọn Entropy Liang (Bao gồm phương pháp sử dụng entropy Liang, phương pháp sử dụng ma trận phân biệt và phương pháp sử dụng độ khác biệt của tri thức). Dựa vào ba độ đo độ chắc chắn, độ nhất quán và độ hỗ trợ của Yuhua Qian [36], tác giả trong luận án [2] cũng đã đề xuất độ 11 nhất quán mới, nhằm so sánh, đánh giá các nhóm phương pháp rút gọn thuộc tính. 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à các bảng quyết định không đầy đủ. Trên bảng quyết định không đầy đủ, Kryszkiewicz [18] đã 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à đề xuất mô hình tập thô dung sai nhằm giải quyết bài toán rút gọn thuộc tính và trích lọc luật trực tiếp không qua bước xử lý giá trị thiếu. Giống như các phương pháp rút gọn thuộc tính trong bảng quyết định đầy đủ theo tiếp cận lý thuyết tập thô truyền thống được trình bày trong luận án [2], 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 đã công bố là các phương pháp heuristic, đều thực hiện các bước sau đây: 1) Đưa ra khái niệm tập rút gọn dựa trên độ đo được xây dựng. 2) Đưa ra khái niệm độ quan trọng của thuộc tính, đặc trưng cho khả năng đóng góp của thuộc tính vào việc phân lớp tập đối tượng. Thuộc tính có độ quan trọng càng lớn thì khả năng đóng góp vào việc phân lớp đối tượng càng nhiều và ngược lại. 3) Xây dựng một thuật toán heuristic tìm một tập rút gọn tốt nhất theo tiêu chuẩn đánh giá là độ quan trọng của thuộc tính (khả năng phân lớp của thuộc tính) Trong mấy năm gần đây 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 đã được các nhà khoa học quan tâm nghiên cứu và đã thu được một số kết quả đáng kể. Các phương pháp điển hình có thể kể đến là: Kryszkiewicz [18] định nghĩa tập rút gọn dựa trên hàm quyết định suy rộng và đề xuất phương pháp rút gọn thuộc tính sử 12 dụng hàm quyết định suy rộng. Zuqiang Meng và các cộng sự [56] đưa ra khái niệm về tập rút gọn dựa trên miền dương và đề xuất phương pháp rút gọn thuộc tính dựa trên miền dương. Theo hướng tiếp cận tính toán hạt (granular computing), Huang B và các cộng sự [16] đưa ra khái niệm tập rút gọn dựa trên độ đo lượng thông tin (information quantity) và đề xuất phương pháp rút gọn thuộc tính dựa trên độ đo lượng thông tin. Theo hướng tiếp cận mở rộng khái niệm ma trận phân biệt trong lý thuyết tập thô truyền thống, Huasheng ZOU và cộng sự [17] đưa ra khái niệm tập rút gọn dựa trên ma trận phân biệt và đề xuất phương pháp rút gọn thuộc tính dựa trên ma trận phân biệt . Cũng theo hướng tiếp cận này, các tác giả trong [19] đưa ra khái niệm tập rút gọn dựa trên ma trận dung sai (tolerance matrix) và xây dựng phương pháp rút gọn thuộc tính dựa trên ma trận dung sai. Ngoài ra, có thể kể đến các phương pháp rút gọn thuộc tính trong các công trình [29], [31], các tác giả này đã đưa ra khái niệm tập rút gọn phân bố (distribution reduct), tập rút gọn ấn định (assignment reduct) và xây dựng phương pháp rút gọn thuộc tính dựa trên hàm phân bố, hàm ấn định. Theo hướng tiếp cận độ đo khoảng cách (metric), tác giả trong luận án [2] xây dựng độ đo metric và đề xuất phương pháp rút gọn thuộc tính trên bảng quyết định không đầy đủ dựa trên metric được xây dựng. Giống như cách tiếp cận trong lý thuyết tập thô truyền thống, để tiến hành so sánh, đánh giá các phương pháp rút gọn thuộc tính theo các hướng tiếp cận khác nhau nhằm tìm ra một phương pháp hiệu quả với một bài toán thực tế, các nhà nghiên cứu tập trung giải quyết hai vấn đề: vấn đề thứ nhất là tìm kiếm mối liên hệ giữa các khái niệm tập rút gọn của các phương pháp nhằm phân nhóm các phương pháp; vấn đề thứ hai là đề xuất các độ đo hiệu quả nhằm đánh giá các phương pháp về mặt định lượng. 13 Về vấn đề thứ nhất, cho đến nay đã có một số kết quả nghiên cứu về mối liên hệ giữa các khái niệm tập rút gọn. Trong bảng quyết định nhất quán, công bố [37], [56] đã chỉ ra tập rút gọn dựa trên miền dương [56], tập rút gọn dựa trên hàm quyết định suy rộng [18], tập rút gọn dựa trên hàm phân bố, tập rút gọn dựa trên hàm ấn định [37], [55] là có định nghĩa độ đo tương đương nhau. Trong bảng quyết định không nhất quán, Renpu Li và cộng sự [37] đã chứng minh tập rút gọn dựa trên miền dương, tập rút gọn dựa trên hàm ấn định là có định nghĩa độ đo tương đương nhau. Huasheng ZOU và cộng sự [17] đã chứng minh tập rút gọn dựa trên hàm quyết định suy rộng, tập rút gọn dựa trên ma trận phân biệt là có định nghĩa độ đo tương đương nhau. Tuy nhiên, theo tài liệu hiện có thì cho đến nay chưa có nghiên cứu tổng thể về mối liên hệ đầy đủ giữa các khái niệm tập rút gọn, từ đó có một bức tranh tổng thể về mối liên hệ giữa các khái niệm tập rút gọn, là cơ sở để phân nhóm các phương pháp rút gọn thuộc tính dựa vào tập rút gọn. Về vấn đề thứ hai, Yuhua Qian và các cộng sự [33] đã xây dựng các độ đo đánh giá hiệu năng của tập luật quyết định, tuy nhiên các độ đo này các tác giả đã xây dựng dựa trên khối đồng nhất cực đại, nhưng các phương pháp trên được định nghĩa dựa trên quan hệ dung sai, do đó không thể sử dụng các độ đo của Yuhua Qian và các cộng sự [33] để đánh giá các phương pháp rút gọn thuộc tính và đòi hỏi phải xây dựng các độ đo mới. Trên cơ sở tổng kết các nghiên cứu liên quan đến các phương pháp rút gọn thuộc tính và các độ đo đánh giá hiệu năng tập luật quyết định dựa trên các tập rút gọn theo tiếp cận tập thô dung sai như đã trình bày ở trên, luận án đặt ra các vấn đề cần nghiên cứu như sau: 1) Có thể nói rằng tập rút gọn chính là kết quả của một phương pháp rút gọn thuộc tính. Trong bảng quyết định nhất quán, công bố [37], [56] đã chỉ ra tập rút gọn của phương pháp dựa trên miền dương [56], tập 14 rút gọn của phương pháp sử dụng hàm quyết định suy rộng [18], tập rút gọn sử dụng hàm phân bố, phương pháp sử dụng hàm ấn định [37], [55] là có định nghĩa độ đo tương đương nhau. Tuy nhiên trên bảng quyết định không nhất quán, các tập rút gọn của các phương pháp là khác nhau và theo tài liệu hiện có mà tác giả biết thì chưa có nghiên cứu liên quan đến việc so sánh các tập rút gọn làm cơ sở để so sánh, đánh giá các phương pháp rút gọn thuộc tính. 2) Việc so sánh, đánh giá các phương pháp rút gọn thuộc tính thường dựa trên hai tiêu chuẩn: độ phức tạp thời gian của thuật toán heuristic tìm tập rút gọn và khả năng phân lớp của tập rút gọn [2]. Từ việc tổng kết các phương pháp rút gọn thuộc tính, tác giả thấy rằng nếu cùng sử dụng một đơn vị tính toán cơ sở trong tập thô dung sai (lực lượng các lớp dung sai) thì độ phức tạp thời gian các thuật toán heuristic của các phương pháp là gần như nhau (độ phức tạp thời gian đa thức). Do đó, việc so sánh, đánh giá các phương pháp đều sử dụng tiêu chuẩn khả năng phân lớp (độ hỗ trợ của tập luật) của tập rút gọn. Về mặt định tính, tập rút gọn bảo toàn khả năng phân lớp của bảng quyết định. Về mặt định lượng, tập rút gọn bảo toàn độ chắc chắn của tập luật quyết định [2]. Tập rút gọn của phương pháp nào có độ hỗ trợ của tập luật cao (luật quyết định phủ nhiều đối tượng) thì có khả năng phân lớp cao [2]. Do đó, khả năng phân lớp được tính bằng độ hỗ trợ của tập luật. Trong công trình [33], các tác giả đã đưa ra độ chắc chắn, độ nhất quán và độ hỗ trợ của tập luật quyết định trên bảng quyết định không đầy đủ. Tuy nhiên, các tác giả chưa nghiên cứu sự thay đổi của các độ đo này trên các tập rút gọn của các phương pháp rút gọn thuộc tính, do đó các độ đo này không đánh giá được khả năng phân lớp của tập rút gọn và đòi hỏi phải có 15 độ chắc chắn, độ hỗ trợ mới để đánh giá khả năng phân lớp của tập rút gọn, làm cơ sở để so sánh, đánh giá các phương pháp rút gọn thuộc tính. 3) Hướng nghiên cứu rút gọn thuộc tính đã đạt được một số kết quả nhất định. Tuy nhiên, việc nghiên cứu và tìm kiếm các phương pháp mới vẫn đòi hỏi nhiều nỗ lực nghiên cứu nhằm phong phú thêm các phương pháp rút gọn thuộc tính. Trên cơ sở đó, lựa chọn các phương pháp phù hợp để giải quyết các bài toán trong thực tiễn. Từ các vấn đề cần nghiên cứu đã trình bày ở trên, mục tiêu nghiên cứu của luận án là so sánh, đánh giá các phương pháp rút gọn thuộc tính đã công bố, trên cơ sở đó đề xuất các phương pháp mới. Với mục tiêu trên, nội dung nghiên cứu của luận án là: 1) Nghiên cứu mối liên hệ giữa các tập rút gọn nhằm: phân nhóm các phương pháp rút gọn thuộc tính đã công bố theo nguyên tắc: các tập rút gọn của các phương pháp có định nghĩa độ đo tương đương nhau được phân thành một nhóm; mối quan hệ giữa các tập rút gọn của các nhóm phương pháp. 2) Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định (độ chắc chắn, độ nhất quán, độ hỗ trợ) và nghiên cứu sự thay đổi các độ đo này trên các tập rút gọn của các nhóm phương pháp nhằm đánh giá các phương pháp theo tiêu chuẩn khả năng phân lớp của tập rút gọn. Tập rút gọn của phương pháp nào có khả năng phân lớp tốt nhất, kém nhất... 3) Đề xuất hai phương pháp mới rút gọn thuộc tính trong bảng quyết định không đầy đủ: phương pháp sử dụng hàm quan hệ và phương 16 pháp sử dụng lượng thông tin mở rộng. So sánh, đánh giá phương pháp đề xuất với các phương pháp đã công bố. Đối tượng nghiên cứu của luận án: các bảng quyết định không đầy đủ với kích thước trung bình và kích thước lớn. Phạm vi nghiên cứu của luận án: Tập trung vào bài toán toán rút gọn thuộc tính ở bước tiền xử lý số liệu trên bảng quyết định không đầy đủ. Phương pháp nghiên cứu: - Nghiên cứu lý thuyết: các mệnh đề được đưa ra đều được chứng minh chặt chẽ trên nền tảng kiến thức cơ bản kết hợp với các kết quả đã được công bố trên các tạp chí chuyên ngành uy tín. - Nghiên cứu thực nghiệm: Thực nghiệm các phương pháp đề xuất trên các bộ số liệu lấy từ kho dữ liệu UCI [40], kết quả thực nghiệm kiểm chứng kết quả lý thuyết để khẳng định tính đúng đắn của kết quả nghiên cứu. Bố cục của luận á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 tổng quan về các khái niệm cơ bản về mô hình tập thô truyền thống và mô hình tập thô dung sai dựa trên quan hệ dung sai trong hệ thông tin không đầy đủ, các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ đã có. Các đóng góp chính của luận án sẽ được trình bày trong chương 2 và chương 3. Chương 2 trình bày hai kết quả chính. Thứ nhất là kết quả phân nhóm các phương pháp rút gọn thuộc tính dựa vào kết quả nghiên cứu mối liên hệ giữa các tập rút gọn. Thứ hai là đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định (độ chắc chắn, độ nhất quán, độ hỗ trợ) và nghiên cứu sự thay đổi giá trị các độ đo này trên các tập rút gọn nhằm so sánh, đánh giá các nhóm 17 phương pháp rút gọn thuộc tính trên tiêu chuẩn khả năng phân lớp của tập rút gọn (độ hỗ trợ của tập luật). Chương 3 trình bày ba kết quả chính. Thứ nhất là chọn tập tối tượng đại diện cho bài toán rút gọn thuộc tính nhằm giảm thiểu số đối tượng (dữ liệu), tăng tính hiệu quả của các thuật toán rút gọn thuộc tính. Thứ hai là đề xuất phương pháp mới rút gọn thuộc tính sử dụng hàm quan hệ và so sánh, thử nghiệm phương pháp với các phương pháp đã có trên các bộ số liệu UCI. Thứ ba là đề xuất phương pháp mới rút gọn thuộc tính sử dụng lượng thông tin mở rộng và so sánh, thử nghiệm phương pháp với các phương pháp đã có trên các bộ số liệu UCI. Cuối cùng, phần kết luận nêu những đóng góp của luận án, hướng phát triển tiếp theo và các vấn đề khác mà tác giả quan tâm. 18 CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ Chương này trình bày một số khái niệm cơ bản về hệ thông tin và mô hình tập thô truyền thống của Pawlak[31], mô hình tập thô mở rộng dựa trên quan hệ dung sai do Kryszkiewicz [18] đề xuất, gọi là mô hình tập thô dung sai, trên các hệ thông tin không đầy đủ, bao gồm: hệ thông tin không đầy đủ, quan hệ dung sai, các tập xấp xỉ dựa trên quan hệ dung sai, bảng quyết định không đầy đủ. Chương này cũng trình bày một số khái niệm về tập rút gọn của các phương pháp rút gọn thuộc tính đã công bố làm cơ sở cho nghiên cứu về mối liên hệ giữa các khái niệm tập rút gọn ở Chương 2. 1.1. Hệ thông tin và mô hình tập thô truyền thống 1.1.1. Hệ thông tin 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 . Với mọi u  U , a  A , ta ký hiệu giá trị thuộc tính a tại đối tượng u là a  u  Nếu B  b1 , b2 ,..., bk   A là một tập con các thuộc tính thì ta ký hiệu bộ các giá trị bi  u  bởi B  u  . Như vậy, nếu u và v là hai đối tượng, thì ta viết B  u   B  v  nếu bi  u   bi  v  với mọi i  1,..., k . 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