Tài liệu Nghiên cứu một số phương pháp khai phá dữ liệu theo tiếp cận lý thuyết tập thô

i BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN NGUYỄN LONG GIANG NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU THEO TIẾP CẬN LÝ THUYẾT TẬP THÔ Chuyên ngành: BẢO ĐẢM TOÁN HỌC CHO MÁY TÍNH VÀ HỆ THỐNG TÍNH TOÁN Mã số: 62.46.35.01 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1.GS.TS Vũ Đức Thi 2. PGS.TS Nguyễn Thanh Tùng HÀ NỘI - 2012 ii MỤC LỤC MỤC LỤC................................................................................................................... i Danh mục các thuật ngữ................................................................................................iv Bảng các ký hiệu, từ viết tắt.............................................................................................v Danh sách bảng...........................................................................................................vii Danh sách hình vẽ.......................................................................................................viii MỞ ĐẦU.................................................................................................................... 1 Chương 1. CÁC KHÁI NIỆM CƠ BẢN..........................................................................7 1.1. Hệ thông tin đầy đủ và mô hình tập thô truyền thống...........................................7 1.1.1. Hệ thông tin đầy đủ............................................................................................7 1.1.2. Mô hình tập thô truyền thống.............................................................................8 1.1.3. Bảng quyết định đầy đủ...................................................................................10 1.1.4. Tập rút gọn và tập lõi.......................................................................................10 1.1.5. Ma trận phân biệt và hàm phân biệt.................................................................12 1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai.....................................13 1.2.1. Hệ thông tin không đầy đủ...............................................................................13 1.2.2. Bảng quyết định không đầy đủ........................................................................15 1.2.3. Tập rút gọn của bảng quyết định không đầy đủ...............................................16 1.3. Cơ sở dữ liệu quan hệ.......................................................................................17 1.3.1. Một số khái niệm cơ bản..................................................................................17 1.3.2. Một số thuật toán cơ bản..................................................................................19 Chương 2. SO SÁNH, ĐÁNH GIÁ CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH ĐẦY ĐỦ.................................................................23 2.1. Mở đầu............................................................................................................23 2.2. Mối liên hệ giữa các loại tập rút gọn dựa trên các tiêu chuẩn khác nhau..............28 2.2.1. Các định nghĩa về tập rút gọn dựa trên entropy thông tin...............................28 2.2.2. Mối liên hệ giữa tập rút gọn Entropy Shannon với tập rút gọn Pawlak...................31 2.2.3. Mối liên hệ giữa tập rút gọn dựa trên entropy Shannon với ma trận phân biệt...33 2.2.4. Mối liên hệ giữa tập rút gọn dựa trên độ khác biệt của tri thức với tập rút gọn Entropy Liang...............................................................................................................37 2.2.5. Tổng kết mối liên hệ giữa các loại tập rút gọn và phân loại các phương pháp....39 iii 2.3. Sự thay đổi các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn.......40 2.3.1. Luật quyết định và các độ đo cổ điển..............................................................41 2.3.2. Các độ đo đánh giá hiệu năng tập luật quyết định...........................................42 2.3.3. Độ nhất quán mới của tập luật quyết định.......................................................43 2.3.4. Sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định..............47 2.4. Tiêu chuẩn đánh giá các phương pháp rút gọn thuộc tính........................................49 2.4.1. Lựa chọn nhóm phương pháp rút gọn thuộc tính.................................................49 2.4.2. Tiêu chuẩn đánh giá các phương pháp rút gọn thuộc tính....................................50 2.5. Kết luận chương 2............................................................................................51 Chương 3. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH ĐẦY ĐỦ SỬ DỤNG METRIC.......................................................................................................52 3.1. Mở đầu............................................................................................................52 3.2. Metric trên họ các tri thức và các tính chất.........................................................53 3.2.1. Khoảng cách Jaccard giữa hai tập hợp hữu hạn...............................................53 3.2.2. Metric trên họ các tri thức................................................................................55 3.2.3. Một số tính chất của metric trên bảng quyết định............................................56 3.3. Rút gọn thuộc tính trong bảng quyết định sử dụng metric...................................59 3.3.1. Tập lõi và tập rút gọn của bảng quyết định dựa trên metric............................59 3.3.2. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng metric.....................59 3.3.3. Mối liên hệ giữa tập rút gọn dựa trên metric và tập rút gọn Entropy Shannon66 3.3.4. Thuật toán tìm tập rút gọn theo tham số độ chắc chắn của tập luật.................66 3.4. Thực nghiệm các thuật toán tìm tập rút gọn.......................................................68 3.4.1. Thực nghiệm thuật toán tìm tập rút gọn tốt nhất sử dụng metric.....................68 3.4.2. Thực nghiệm thuật toán tìm tập rút gọn theo tham số độ chắc chắn...............70 3.5. Thực nghiệm các phương pháp phân lớp dựa trên tập rút gọn.............................72 3.5.1. Thực nghiệm phương pháp phân lớp sử dụng tập thô.....................................72 3.5.2. Thực nghiệm phương pháp phân lớp bằng cây quyết định..............................73 3.6. Kết luận chương 3............................................................................................76 Chương 4. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ SỬ DỤNG METRIC..................................................................................................77 4.1. Mở đầu............................................................................................................77 4.2. Entropy Liang mở rộng trong hệ thông tin không đầy đủ và các tính chất............78 iv 4.2.1. Entropy Liang mở rộng của tập thuộc tính......................................................78 4.2.2. Entropy Liang mở rộng có điều kiện...............................................................79 4.2.3. Một số tính chất của entropy Liang mở rộng...................................................80 4.3. Metric trên họ các phủ và các tính chất..............................................................84 4.3.1. Metric trên họ các phủ.....................................................................................84 4.3.2. Một số tính chất của metric..............................................................................87 4.4. Rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng metric..............90 4.4.1. Tập rút gọn của bảng quyết định không đầy đủ dựa trên metric.....................90 4.4.2. Thuật toán tìm tập rút gọn của bảng quyết định không đầy đủ........................90 4.4.3. Mối liên hệ giữa tập rút gọn dựa trên metric với tập rút gọn Kryszkiewicz....96 4.4.4. Mối liên hệ giữa tập rút gọn dựa trên metric với tập rút gọn dựa trên lượng thông tin.......................................................................................................................98 4.5. Thực nghiệm thuật toán....................................................................................99 4.6. Kết luận chương 4..........................................................................................101 Chương 5. MỘT SỐ THUẬT TOÁN TRÊN BẢNG QUYẾT ĐỊNH NHẤT QUÁN....102 5.1. Mở đầu..........................................................................................................102 5.2. Thuật toán tìm tập tất cả các thuộc tính rút gọn của bảng quyết định nhất quán..102 5.2.1. Đặt vấn đề......................................................................................................102 5.2.2. Thuật toán......................................................................................................103 5.2.3. Thực nghiệm thuật toán.................................................................................106 5.3. Thuật toán tìm họ tất cả các tập rút gọn của bảng quyết định nhất quán.........106 5.4. Thuật toán xây dựng các phụ thuộc hàm từ bảng quyết định nhất quán.............109 5.5. Thuật toán xây dựng bảng quyết định từ tập phụ thuộc hàm.............................110 5.6. Kết luận chương 5..........................................................................................114 KẾT LUẬN.............................................................................................................115 Danh mục các công trình của tác giả..............................................................................117 Tài liệu tham khảo......................................................................................................118 Phụ lục..................................................................................................................... 125 v Danh mục các thuật ngữ Thuật ngữ tiếng Việt Tập thô Hệ thông tin Information System Hệ thông tin đầy đủ Hệ thông tin không đầy đủ Hệ thông tin không nhất quán Bảng quyết định Bảng quyết định đầy đủ Bảng quyết định không đầy đủ Bảng quyết định không nhất quán Quan hệ không phân biệt được Quan hệ dung sai Xấp xỉ dưới Xấp xỉ trên Upper Approximation Rút gọn thuộc tính Tập rút gọn Tập lõi Ma trận phân biệt Hàm phân biệt Luật quyết định Quan hệ Sơ đồ quan hệ Phụ thuộc hàm Khóa, phản khóa Tập tối thiểu của thuộc tính a Họ các tập tối thiểu của thuộc tính a Hàm biểu diễn khoảng cách giữa hai tập hợp trong [17] Thuật ngữ tiếng Anh Rough Set Complete Information System Incomplete Information System Inconsistent Information System Decision Table Complete Decision Table Incomplete Decision Table Inconsistent Decision Table Indiscernibility Relation Tolerance Relation Lower Approximation Attribute Reduction Reduct Core Indiscernibility Matrix Indiscernibility Function Decision Rule Relation Relation Schema Functional Dependency Key, Antikey Minimal set of the attribute a Family of all minimal sets of attribute a Metric vi Bảng các ký hiệu, từ viết tắt Ký hiệu, từ viết tắt Diễn giải Hệ thông tin, hệ thông tin đầy đủ IIS   U , A,V , f Hệ thông tin không đầy đủ IS   U , A, V , f   DS   U , C �D,V , f  Bảng quyết định, bảng quyết định đầy đủ IDS   U , C �D,V , f  Bảng quyết định không đầy đủ U Số đối tượng C Số thuộc tính điều kiện trong bảng quyết định A Số thuộc tính trong hệ thông tin u  a Giá trị của đối tượng u tại thuộc tính a IND  B  Quan hệ B  không phân biệt SIM  B  Quan hệ dung sai trên tập thuộc tính B U /B U / SIM  B  Lớp dung sai của đối tượng u trên quan hệ SIM  B  Phân hoạch của U sinh bởi tập thuộc tính B . Phủ của U sinh bởi tập thuộc tính B .  u B SB  u  Lớp tương đương chứa u của quan hệ IND  B  COVER  U  Họ tất cả các phủ của U. �B (u ) Hàm quyết định suy rộng của đối tượng u đối với B . BX BX POS B  D  B - miền B  xấp xỉ dưới của X B  xấp xỉ trên của X B  miền dương của D biên của X BN B  X  PRED  C  Họ tất cả các tập rút gọn Pawlak HRED  C  Họ tất cả các tập rút gọn Entropy Shannon SRED  C  Họ tất cả các tập rút gọn dựa trên các phép toán trong đại số quan hệ Họ tất cả các tập rút gọn dựa trên ma trận phân biệt FRED  C  ERED  C  KRED  C  Họ tất cả các tập rút gọn dựa trên metric Họ tất cả các tập rút gọn Entropy Liang Họ tất cả các tập rút gọn dựa trên độ khác biệt của tri thức vii MRED  C  PCORE  C  Tập lõi dựa trên miền dương HCORE  C  Tập lõi dựa trên entropy Shannon có điều kiện SCORE  C  Tập lõi dựa trên ma trận phân biệt ECORE  C  Tập lõi dựa trên entropy Liang có điều kiện MCORE  C  Tập lõi dựa trên metric H  P Entropy Shannon của tập thuộc tính P H (Q | P ) E  P Entropy Shannon có điều kiện của Q khi đã biết P Entropy Liang của tập thuộc tính P Entropy Liang có điều kiện của Q khi đã biết P E (Q P ) IE (Q P ) Entropy Liang mở rộng của tập thuộc tính P trong hệ thông tin không đầy đủ IE  P  K  P Entropy Liang mở rộng có điều kiện của Q khi đã biết P trong hệ thông tin không đầy đủ. Trong hệ thông tin đầy đủ, ký hiệu K  P  là tri thức sinh bởi tập thuộc tính P. Trong hệ thông tin không đầy đủ, ký hiệu K  P  là phủ sinh bởi tập thuộc tính P. dJ  K  P , K  Q   Khoảng cách giữa K  P  và K  Q  trong hệ thông tin đầy đủ dựa trên khoảng cách Jaccard giữa hai tập hợp. dE  K  P  , K  Q   Khoảng cách giữa K  P  và K  Q  trong hệ thông tin không đầy đủ dựa trên entropy Liang mở rộng DQP  K  P  , K  Q   Độ khác biệt giữa K  P  và K  Q  SĐQH PTH Sơ đồ quan hệ Phụ thuộc hàm viii ix Danh sách bảng Bảng 1.1. Bảng thông tin về bệnh cúm.................................................................................9 Bảng 1.2. Bảng quyết định về bệnh cúm..............................................................................11 Bảng 1.3. Bảng thông tin về các xe hơi...............................................................................15 Bảng 1.4. Bảng quyết định về các xe hơi.............................................................................16 Bảng 2.1. Bảng quyết định minh họa Ví dụ 2.1.....................................................................32 Bảng 2.2. Bảng quyết định minh họa Ví dụ 2.3.....................................................................35 Bảng 2.3. Ma trận phân biệt của Ví dụ 2.3..........................................................................36 Bảng 3.1. Bảng quyết định về bệnh cảm cúm......................................................................59 Bảng 3.2. Bảng quyết định minh họa Ví dụ 3.2.....................................................................61 Bảng 3.3. Kết quả thực hiện Thuật toán 3.3 và Thuật toán CEBARKCC...........................70 Bảng 3.4. Tập rút gọn của Thuật toán 3.3 và Thuật toán CEBARKCC..............................70 Bảng 3.5. Kết quả thực hiện Thuật toán 3.3 trên các bộ số liệu lớn...................................71 Bảng 3.6. Sự thay đổi tập rút gọn theo ngưỡng độ chắc chắn  ......................................72 Bảng 3.7. Tập rút gọn tốt nhất của bộ số liệu Soybean-small............................................73 Bảng 3.8. Các luật phân lớp trên bảng quyết định rút gọn sử dụng tập thô.......................74 Bảng 3.9. Các luật phân lớp trên bảng quyết định ban đầu sử dụng cây quyết định..........75 Bảng 3.10. Các luật phân lớp trên bảng quyết định rút gọn sử dụng cây quyết định.........76 Bảng 4.1. Hệ thông tin không đầy đủ về các xe hơi...........................................................84 Bảng 4.2. Bảng quyết định không đầy đủ minh họa Ví dụ 4.3.............................................93 Bảng 4.3. Bảng quyết định không đầy đủ về các xe hơi......................................................95 Bảng 4.4. Kết quả thực hiện Thuật toán 4.2 và Thuật toán IQBARK................................101 Bảng 4.5. Tập rút gọn của Thuật toán 4.2 và Thuật toán IQBARK..................................101 Bảng 4.6. Kết quả thực hiện Thuật toán 4.2 trên các bộ số liệu lớn.................................102 Bảng 5.1. Bảng quyết định ở Ví dụ 5.1..............................................................................107 Bảng 5.2. Kết quả thử nghiệm Thuật toán 5.1...................................................................108 Bảng 5.3. Bảng quyết định ở Ví dụ 5.2..............................................................................110 Bảng 5.4. Bảng quyết định được xây dựng từ Thuật toán 5.4...........................................116 x Danh sách hình vẽ Hình 3.1. Sự thay đổi tập rút gọn theo ngưỡng độ chắc chắn  ........................................73 Hình 3.2. Cây quyết định tương ứng với bảng quyết định ban đầu....................................75 Hình 3.3. Cây quyết định tương ứng với bảng quyết định rút gọn....................................76 1 MỞ ĐẦU Lý thuyết tập thô - do Zdzislaw Pawlak [42] đề 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 mơ hồ 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, trích lọc các tri thức tiềm ẩn trong dữ liệu và đánh giá kết quả thu được. Trong lý thuyết tập thô, dữ liệu được biểu diễn thông qua một hệ thông tin IS   U , A  với U là tập các đối tượng và A là tập các thuộc tính. 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ệ không phân biệt được để đưa ra các tập xấp xỉ biểu diễn tập đối tượng cần quan sát. 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ó. Xấp xỉ dưới bao gồm các đối tượng chắc chắn thuộc tập đó, còn xấp xỉ trên chứa tất cả các đối tượng có khả năng thuộc về tập đó. Nếu tập xấp xỉ dưới bằng tập xấp xỉ trên thì tập đối tượng cần quan sát là tập rõ, ngược lại là tập thô. Các tập xấp xỉ là cơ sở để đưa ra các kết luận từ dữ liệu. Bảng quyết định là một hệ thông tin IS với tập thuộc tính A được chia thành hai tập con 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. Nói cách khác, DS   U , C �D  với C �D  �. Bảng quyết định là mô hình thường gặp trong thực tế, khi mà giá trị dữ liệu tại các thuộc tính điều kiện có thể cung cấp cho ta thông tin về giá trị của thuộc tính quyết định. Bảng quyết định là nhất quán khi phụ thuộc hàm C � D là đúng, trái lại là không nhất quán. Rút gọn thuộc tính là ứng dụng quan trọng nhất trong lý thuyết tập thô. 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 để tìm ra các thuộc tính cốt yếu và cần thiết trong cơ sở dữ liệu. Với bảng quyết định, rút gọn thuộc tính là tìm tập con nhỏ nhất của tập thuộc tính điều kiện bảo toàn thông tin phân lớp của bảng quyết định. Đối với một bảng quyết định có thể có nhiều tập rút gọn khác nhau 2 Tuy nhiên, trong thực hành thường không đòi hỏi tìm tất cả các tập rút gọn mà chỉ cần tìm được một tập rút gọn tốt nhất theo một tiêu chuẩn đánh giá nào đó là đủ. Vì vậy, mỗi phương pháp rút gọn thuộc tính đều đề xuất một thuật toán heuristic tìm tập rút gọn. Các thuật toán này giảm thiểu đáng kể khối lượng tính toán, nhờ đó có thể áp dụng đối với các bài toán có khối lượng dữ liệu lớn. Mười năm trở lại đây đã chứng kiến sự phát triển mạnh mẽ và sôi động của lĩnh vực nghiên cứu về rút gọn thuộc tính sử dụng lý thuyết tập thô. Trong xu thế đó, nhiều nhóm nhà khoa học trên thế giới quan tâm nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết định. Các phương pháp chính là: phương pháp dựa trên miền dương [18, 29, 41, 42, 67], phương pháp sử dụng các phép toán trong đại số quan hệ [20, 61], phương pháp sử dụng ma trận phân biệt [11, 19, 65, 69], phương pháp sử dụng entropy thông tin [39, 52, 55, 56, 57, 58, 59, 60, 63], phương pháp sử dụng các độ đo trong tính toán hạt [12, 24, 26, 27, 28, 70, 71]. Tại Việt Nam, luận án tiến sĩ của tác giả Hoàng Thị Lan Giao [1] đã đề xuất các thuật toán heuristic tìm tập rút gọn và tìm tập rút gọn xấp xỉ của bảng quyết định nhất quán, bao gồm thuật toán sử dụng các phép toán trong đại số quan hệ và thuật toán sử dụng ma trận phân biệt. Luận án tiến sĩ của tác giả Nguyễn Đức Thuần [2] đề xuất thuật toán heuristic tìm tập rút gọn của bảng quyết định đầy đủ nhất quán dựa vào phủ tập thô. Với mục tiêu tìm kiếm một phương pháp phù hợp, hiệu quả rút gọn thuộc tính trong bảng quyết định, vấn đề trước tiên là cần đưa ra tiêu chuẩn lựa chọn các phương pháp phù hợp với lớp bài toán cần giải quyết và tiêu chuẩn so sánh, đánh giá các phương pháp. Tiêu chuẩn lựa chọn các phương pháp phù hợp là tập rút gọn của phương pháp phải bảo toàn độ chắc chắn của bảng quyết định. Việc lựa chọn các phương pháp phù hợp được thực hiện bằng việc nghiên cứu sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn. Tiêu chuẩn so sánh, đánh giá các phương pháp là số lượng thuộc tính tập rút gọn của phương pháp và độ phức tạp của thuật toán tìm tập rút gọn. Việc so sánh số lượng thuộc tính tập rút gọn của phương pháp được thực hiện bằng việc nghiên cứu mối liên hệ 3 giữa các tập rút gọn. Tập rút gọn của phương pháp càng ít thuộc tính thì độ hỗ trợ của tập luật dựa trên tập rút gọn đó càng cao và phương pháp đó càng hiệu quả. Độ phức tạp thuật toán tìm tập rút gọn của phương pháp càng nhỏ thì phương pháp đó càng hiệu quả. Từ hai tiêu chuẩn này, ta có thể chứng minh được phương pháp cần tìm kiếm là phù hợp và hiệu quả hơn các phương pháp đã có hay không. Trên thế giới và tại Việt Nam, một số nhóm tác giả đã nghiên cứu mối liên hệ giữa các loại tập rút gọn của một số phương pháp rút gọn thuộc tính và nghiên cứu một số độ đo đánh giá hiệu năng tập luật quyết định [2, 6, 37, 48, 61, 64]. Tuy nhiên trên cả bảng quyết định nhất quán và không nhất quán, các tác giả trên chưa nghiên cứu đầy đủ mối liên hệ giữa các loại tập rút gọn và chưa nghiên cứu đầy đủ sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định dựa trên các loại tập rút gọn này. Trong các bài toán thực tế, các hệ thông tin thường thiếu giá trị trên các thuộc tính, gọi là các hệ thông tin không đầy đủ. Xuất phát từ mô hình tập thô mở rộng dựa trên quan hệ dung sai trong hệ thông tin không đầy đủ do Kryszkiewicz [23] đề xuất, nhiều nhóm nhà khoa học trên thế giới đã quan tâm nghiên cứu các độ đo không chắc chắn [31, 32, 44, 45] và sử dụng các độ đo này để giải quyết bài toán rút gọn thuộc tính [13, 21, 28, 34]. Trên lớp bài toán rút gọn thuộc tính trong bảng quyết định không đầy đủ, vấn đề các nhà nghiên cứu tiếp tục quan tâm là cải tiến các các phương pháp đã có hoặc xây dựng các phương pháp mới hiệu quả hơn theo các tiêu chuẩn đánh giá được chọn. Cho bảng quyết định nhất quán DS   U , C � d   , tập thuộc tính R �C được gọi là một tập rút gọn của tập thuộc tính điều kiện C nếu R là tập tối thiểu thỏa mãn phụ thuộc hàm R �  d  . Xét quan hệ r trên tập thuộc tính C � d  , tập thuộc tính R �C � d  được gọi là một tập tối thiểu của thuộc tính  d  nếu R là tập tối thiểu thỏa mãn phụ thuộc hàm R �  d  . Do đó, khái niệm tập rút gọn của bảng quyết định tương đương với khái niệm tập tối thiểu của thuộc tính {d} trên quan hệ, và một số bài toán trong bảng quyết định liên quan đến tập rút gọn có thể được 4 giải quyết bằng một số kết quả liên quan đến tập tối thiểu của một thuộc tính trong cơ sở dữ liệu quan hệ; bao gồm bài toán tìm tập tất cả các thuộc tính rút gọn, bài toán tìm họ tất cả các tập rút gọn, bài toán trích lọc các tri thức dưới dạng các phụ thuộc hàm từ bảng quyết định, bài toán xây dựng bảng quyết định từ tập phụ thuộc hàm cho trước. Cho đến nay, hướng tiếp cận này chưa được nhiều tác giả quan tâm nghiên cứu. Từ các nội dung đã trình bày ở trên, luận án đặt ra các vấn đề nghiên cứu sau: 1) Trên bảng quyết định đầy đủ, vấn đề đầu tiên là nghiên cứu đầy đủ mối liên hệ giữa các loại tập rút gọn của các phương pháp rút gọn thuộc tính và nghiên cứu đầy đủ sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định dựa trên các loại tập rút gọn này. Mục đích nghiên cứu trước tiên là lựa chọn các phương pháp phù hợp với lớp bài toán cần giải quyết, sau đó là so sánh, đánh giá các phương pháp theo các tiêu chuẩn khác nhau. Dựa trên các kết quả này, vấn đề nghiên cứu tiếp theo là tìm kiếm một phương pháp mới hiệu quả hơn các phương pháp đã có theo các tiêu chuẩn đánh giá được chọn. 2) Trên bảng quyết định không đầy đủ, vấn đề nghiên cứu đặt ra là tìm kiếm một phương pháp rút gọn thuộc tính hiệu quả hơn các phương pháp đã có theo các tiêu chuẩn đánh giá được chọn. 3) Trên bảng quyết định nhất quán, vấn đề nghiên cứu đặt ra là xây dựng các thuật toán có ý nghĩa liên quan đến tập rút gọn sử dụng một số kết quả liên quan đến tập tối thiểu của một thuộc tính trong cơ sở dữ liệu quan hệ. Mục tiêu của luận án tập trung nghiên cứu bốn vấn đề chính. Vấn đề thứ nhất là so sánh, đánh giá các phương pháp rút gọn thuộc tính trong bảng quyết định đầy đủ theo các tiêu chuẩn khác nhau. Vấn đề thứ hai là đề xuất phương pháp mới rút gọn thuộc tính trong bảng quyết định đầy đủ sử dụng metric và chứng minh phương pháp mới hiệu quả hơn các phương pháp đã có dựa trên kết quả nghiên cứu của vấn đề thức nhất. Vấn đề thứ ba là đề xuất phương pháp mới rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng metric và chứng minh phương pháp 5 mới hiệu quả hơn các phương pháp đã có theo các tiêu chuẩn đánh giá được chọn. Vấn đề thứ tư là đề xuất một số thuật toán trong bảng quyết định nhất quán sử dụng một số kết quả trong cơ sở dữ liệu quan hệ. Đối tượng nghiên cứu của luận án là các bảng quyết định đầy đủ và 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 rút gọn thuộc tính trong bước tiền xử lý số liệu. Ngoài ra, luận án nghiên cứu thêm phương pháp trích lọc tri thức từ bảng dữ liệu dưới dạng phụ thuộc hàm trong bước khai phá dữ liệu ở chương 5. Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết: các định lý, mệnh đề trong luận án được chứng minh chặt chẽ dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. Về nghiên cứu thực nghiệm: luận án thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho dữ liệu UCI, so sánh và đánh giá kết quả thực nghiệm so với kết quả nghiên cứu lý thuyết, từ đó kết luận 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à năm 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ề mô hình tập thô truyền thống, mô hình tập thô mở rộng dựa trên quan hệ dung sai và cơ sở dữ liệu quan hệ. Chương 1 cũng trình bày một số thuật toán cơ bản trong cơ sở dữ liệu quan hệ được sử dụng để xây dựng các thuật toán trên bảng quyết định nhất quán trong chương 5. Các đóng góp chính của luận án được trình bày trong chương 2, chương 3, chương 4 và chương 5. Chương 2 trình bày kết quả nghiên cứu về mối liên hệ giữa các loại tập rút gọn của các phương pháp rút gọn thuộc tính trong bảng quyết định đầy đủ và sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định dựa trên các loại tập rút gọn này. Trên cơ sở đó, chương 2 phân loại các phương pháp rút gọn thuộc tính trong 6 bảng quyết định không nhất quán thành 3 nhóm, lựa chọn nhóm phương pháp phù hợp với lớp bài toán cần giải quyết và đánh giá các phương pháp trong 3 nhóm dựa trên hai tiêu chuẩn: số lượng thuộc tính tập rút gọn của phương pháp và độ phức tạp thuật toán tìm tập rút gọn.. Chương 3 trình bày phương pháp xây dựng một metric trên họ các tri thức trong hệ thông tin đầy đủ dựa trên khoảng cách Jaccard giữa hai tập hợp hữu hạn. Sử dụng metric được xây dựng, chương 3 đề xuất một phương pháp mới rút gọn thuộc tính trong bảng quyết định đầy đủ. Dựa trên lý thuyết, thực nghiệm và dựa trên kết quả nghiên cứu của chương 2, chương 3 chứng minh phương pháp sử dụng metric hiệu quả hơn các phương pháp khác trên cả hai tiêu chuẩn đánh giá: số lượng thuộc tính tập rút gọn của phương pháp và độ phức tạp thuật toán tìm tập rút gọn. Chương 4 trình bày phương pháp xây dựng một metric trên họ các phủ trong hệ thông tin không đầy đủ dựa trên entropy Liang mở rộng. Sử dụng metric được xây dựng, chương 4 đề xuất phương pháp mới rút gọn thuộc tính trong bảng quyết định không đầy đủ. Bằng lý thuyết và thực nghiệm, chương 4 chứng minh phương pháp sử dụng metric hiệu quả hơn phương pháp sử dụng độ đo lượng thông tin và phương pháp sử dụng ma trận dung sai theo tiêu chuẩn đánh giá độ phức tạp thuật toán tìm tập rút gọn. Chương 5 đề xuất bốn thuật toán trên bảng quyết định nhất quán dựa trên một số kết quả trong cơ sở dữ liệu quan hệ. Thuật toán 5.1 tìm tập tất cả các thuộc tính rút gọn của bảng quyết định với độ phức tạp thời gian là đa thức. Đây là thuật toán thực sự có ý nghĩa trong tiền xử lý dữ liệu vì cho phép xác định và loại bỏ tất cả các thuộc tính dư thừa thực sự trong bảng dữ liệu trước khi thực hiện các nhiệm vụ khai phá dữ liệu tiếp theo. Thuật toán 5.2 tìm họ tất cả các tập rút gọn của bảng quyết định. Thuật toán 5.3 trích lọc tất cả các tri thức dưới dạng phụ thuộc hàm từ bảng quyết định cho trước. Thuật toán 5.4 xây dựng bảng quyết định từ tập các phụ thuộc hàm cho trước. Độ phức tạp thời gian của Thuật toán 5.2, Thuật toán 5.3 và Thuật toán 5.4 đều là hàm mũ. 7 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 và những vấn đề quan tâm của tác giả. 8 Chương 1. CÁC KHÁI NIỆM CƠ BẢN 1.1. Hệ thông tin đầy đủ và mô hình tập thô truyền thống 1.1.1. Hệ thông tin đầy đủ 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 p cột ứng với p thuộc tính và n hàng ứng với n đối tượng. Một cách hình thức, hệ thông tin được định nghĩa như sau. Định nghĩa 1.1. Hệ thông tin là một bộ tứ IS   U , A, V , f  trong đó U là tập hữu Va 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; V  � a�A với Va là tập giá trị của thuộc tính a �A ; f là hàm thông tin, với mọi a �A và u �U hàm f cho giá trị f  u , a  �Va . Với mọi u �U , a �A , ta ký hiệu giá trị của đối tượng u tại thuộc tính a là u  a  thay vì f  u , a  . 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ị u  bi  bởi u  B  . Như vậy, nếu u và v là hai đối tượng, thì ta viết u  B   v  B  nếu u  bi   v  bi  với mọi i  1,..., k . Nếu với mọi u �U và a �A , u  a  đều chứa giá trị khác rỗng thì hệ thông tin được gọi là hệ thông tin đầy đủ. Trong luận án này, hệ thông tin đầy đủ được gọi tắt là hệ thông tin và được ký hiệu là IS   U , A, V , f  . Xét hệ thông tin IS   U , A, V , f  . Với mỗi tập con các thuộc tính P �A , tồn tại 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, u  a   v a . IND  P  được gọi là quan hệ B - không phân biệt được. Dễ thấy rằng đây là một quan hệ tương đương trên U. Nếu  u , v  �IND  B  thì hai đối tượng u và v không phân biệt được bởi các thuộc tính trong B. Quan hệ tương đương IND  P  xác định một phân 9 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   . Định nghĩa 1.2. [43] Cho hệ thông tin IS   U , A, V , f  và P, Q �A . Ta nói: 1) Phân hoạch U / P và phân hoạch U / Q là như nhau (viết U / P  U / Q ), khi và chỉ khi u �U ,  u  P   u  Q . 2) Phân hoạch U / P mịn hơn phân hoạch U / Q (viết U / P p U / Q ) khi và chỉ khi u �U ,  u  P � u  Q . Tính chất 1.1 [43] Xét hệ thông tin IS   U , A,V , f  và P, Q �A . 1) Nếu P �Q thì U / Q p U / P , mỗi lớp của U / P là một lớp hoặc hợp của một số lớp thuộc U / Q . 2) Với mọi u �U ta có  u  P �Q   u  P � u  Q . 1.1.2. Mô hình tập thô truyền thống Cho hệ thông tin IS   U , A, V , f  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 có các lớp tương đương của phân hoạch U / B , thế thì một tập đối tượng X có thể biểu diễn thông qua các lớp tương đương này như thế nào? Trong lý thuyết tập thô truyền thống, để 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ó khả năng được phân loại vào X dựa vào 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. 10 Dễ thấy B-miền biên của X là tập chứa các đối tượng có thể thuộc X, còn Bmiề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  U Y �U / B Y �X  , BX �ǹ� U Y U / B Y . X Trong trường hợp BN B  X   �, X được gọi là tập rõ, ngược lại X được gọi là tập thô. 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 POS B ( D )  U  BX  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, POS B ( D)  u �U  u  B � u  D . Ví dụ 1.1. Xét hệ thông tin biểu diễn các triệu chứng cúm của bệnh nhân cho ở Bảng 1.1. Bảng 1.1. Bảng thông tin về bệnh cúm U u1 u2 u3 u4 u5 u6 u7 u8 Đau đầu Có Có Có Không Không Không Không Không Thân nhiệt Bình thường Cao Rất cao Bình thường Cao Rất cao Cao Rất cao Cảm cúm Không Có Có Không Không Có Có Không   u , u , u  , u , u , u , u , u   U / {Thân nhiệt} =   u , u  ,  u , u , u  ,  u , u , u   U / {Cảm cúm} =   u , u , u , u  ,  u , u , u , u   U / {Đau đầu, Cảm cúm} =   u  ,  u , u  ,  u , u , u  ,  u , u   Ta có: U / {Đau đầu} = 1 2 1 1 3 4 4 4 2 5 5 5 8 6 7 7 2 1 3 3 2 8 6 3 6 8 7 4 5 8 6 7 Như vậy, các bệnh nhân u2 , u3 không phân biệt được về đau đầu và cảm cúm, nhưng phân biệt được về thân nhiệt. Các lớp không phân biệt được bởi B = {Đau đầu, Thân nhiệt} là:  u1 ,  u2  ,  u3  ,  u4  ,  u5 , u7  ,  u6 , u8  . Đặt X  {u u (Cảm cúm) = Có} =  u2 , u3 , u6 , u7  . Khi đó: