Luận án Tiến sĩ: Rút Gọn Thuộc Tính Bảng Quyết Định Không Đầy Đủ Theo Tiếp Cận Tập Thô Dung Sai

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.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. MỘT SỐ KIẾN THỨC CƠ SỞ.

Hệ thông tin và mô hình tập thô truyền thống. Hệ thông tin. Mô hình tập thô truyền thống. Bảng quyết định đầy đủ.

Tập rút gọn và tập lõi. Hệ thông tin không đầy đủ và mô hình tập thô dung sai. Hệ thông tin không đầy đủ. Mô hình tập thô dung sai.

Bảng quyết định không đầy đủ. Các khái niệm về tập rút gọn của bảng quyết định không đầy đủ. 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 miền dương.

Tập rút gọn dựa trên độ đo lượng thông tin. Tập rút gọn dựa trên ma trận phân biệt. Tập rút gọn dựa trên ma trận dung sai. Tập rút gọn dựa trên hàm phân bố, hàm ấn định.

Tập rút gọn dựa trên metric. Kết luận chương 1. ĐỀ 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 ĐỦ. Đề xuất phân nhóm các phương pháp rút gọn thuộc tính .1 Bảng ký hiệu các tập rút gọn của bảng quyết định không đầy đủ .2 Mối liên hệ giữa các khái niệm tập rút gọn RD , RI , RTM .3 Mối liên hệ giữa R và RP .4 Mối liên hệ giữa RD và R .5 Mối liên hệ giữa R và R .6 Đề xuất phân nhóm các phương pháp rút gọn thuộc tính.

Đánh giá các phương pháp rút gọn thuộc tính. Luật quyết định và các độ đo đánh giá hiệu năng. Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định. Nghiên cứu sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn.

Thử nghiệm sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn. Lựa chọn, đánh giá các phương pháp rút gọn thuộc tính. Kết luận chương 2. ĐỀ 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 ĐỦ.

Chọn tập đối tượng đại diện cho bài toán rút gọn thuộc tính. Chọn tập đối tượng đại diện cho hệ thông tin không đầy đủ. Chọn tập đối tượng đại diện cho bảng quyết định không đầy đủ. 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.

Độ đo lượng thông tin mở rộng. Xây dựng lượng thông tin mở rộng có điều kiện. 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. Thử nghiệm và đánh giá kết quả.

Phương pháp rút gọn thuộc tính sử dụng hàm quan hệ. Ma trận quan hệ và hàm quan hệ. Rút gọn thuộc tính sử dụng hàm quan hệ. Thử nghiệm và đánh giá kết quả.

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. Mối quan hệ giữa các tập rút gọn. Sự thay đổi độ hỗ trợ  trên các tập rút gọn. Sự thay đổi độ hỗ trợ  trên hai tập rút gọn của hai thuật toán EIQBAR và MBAR.

Bảng quyết định về bệnh cúm. Bảng thông tin về xe hơi. Bảng quyết định về các xe hơi. Ký hiệu các tập rút gọn trong bảng quyết định không đầy đủ.

Bảng quyết định minh họa Ví dụ 2. Bảng quyết định minh họa Ví dụ 2. Bảng quyết định không đầy đủ về các tivi. Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 1.

Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 2. Bảng thông tin về các xe hơi. Bảng quyết định không đầy đủ về các xe hơi. Bảng quyết định không đầy đủ mô tả về các xe hơi.

Tập rút gọn của thuật toán MBAR và Thuật toán EIQBAR. 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. Bảng quyết định không đầy đủ mô tả về các tivi. Kết quả thực hiện thuật toán MBAR, Thuật toán EIQBAR và Thuật toán RBAR.

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.