Tài liệu Khai phá dữ liệu dựa trên bảng quyết định nhờ lý thuyết tập thô

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG THỊ KIM OANH KHAI PHÁ DỮ LIỆU DỰA TRÊN BẢNG QUYẾT ĐỊNH NHỜ LÝ THUYẾT TẬP THÔ Ngành:Công nghệ thông tin Chuyên ngành:Hệ thống thông tin Mã số: 60480104 TÓM TẮT LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội - 2014 2 MỤC LỤC MỤC LỤC MỞ ĐẦU Chương 1. KHAI PHÁ DỮ LIỆU THEO TIẾP CẬN TẬP THÔ 1.1. Hệ thông tin 1.2. Bảng quyết định 1.3. Quan hệ không phân biệt được 1.4. Các tập xấp xỉ 1.5. Tập rút gọn và tập lõi Chương 2. PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT TRÊN BẢNG QUYẾT ĐỊNH 2.1. Phương pháp rút gọn thuộc tính trên bảng quyết định 2.2. Phương pháp rút gọn thuộc tính sử dụng entropy Shannon 2.2.1. Entropy Shannon trên bảng quyết định 2.2.2. Tập lõi của bảng quyết định dựa trên Entropy Shannon 2.2.3. Tập rút gọn của bảng quyết định dựa trên Entropy Shannon 2.2.5. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng Entropy Shannon 2.3. Sinh luật quyết định trên tập rút gọn của bảng quyết định 2.3.1. Luật quyết định 2.3.2. 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 2.3.3. Thuật toán sinh luật quyết định dựa trên tập rút gọn của bảng quyết định Chương 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ 3.1. Bài toán 3 3.2. Một số kết quả thử nghiệm 3.2.1. Kết quả thử nghiệm thuật toán rút gọn thuộc tính sử dụng entropy Shannon 3.2.2. Kết quả thử nghiệm thuật toán sinh luật quyết định dựa trên tập rút gọn 3.3. Ứng dụng thuật toán rút gọn thuộc tính vào thực tế 3.4. Một số giao diện chương trình 3.4.1. Thực hiện thuật toán rút gọn thuộc tính CEBARKCC 3.4.2. Thực hiện thuật toán sinh luật quyết định KẾT LUẬN TÀI LIỆU THAM KHẢO 4 MỞ ĐẦU Lý thuyết tập thô do nhà logic học Balan Zdzislak Pawlak [17] đề xuất vào đầu những năm 80 được xem như là một cách tiếp cận mới để phát hiện tri thức và tạo thành một cơ sở vững chắc cho các ứng dụng khai phá dữ liệu. Nó rất hữu ích trong việc giải quyết các bài toán phân lớp dữ liệu, phát hiện luật, … chứa dữ liệu mơ hồ không chắc chắn. Các mối quan hệ trong mô hình này được biểu diễn qua quan hệ không phân biệt được, còn các dữ liệu được biểu diễn thông qua tập xấp xỉ trên và xấp xỉ dưới của nó. 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. Với những lý do trên, tập thô đã chứng tỏ là một trong những lý thuyết rất hiệu quả trong lĩnh vực khai phá dữ liệu. Vì vậy tôi đã chọn đề tài “Khai phá dữ liệu dựa trên bảng quyết định nhờ lý thuyết tập thô”. Đối tượng nghiên cứu của luận văn là các bảng quyết định 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 văn tập trung vào bài toán rút gọn thuộc tính ở bước tiền xử lý số liệu trong quá trình khai phá dữ liệu. Phương pháp nghiên cứu của luận vă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 mệnh đề đượ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 vă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 5 Chương 1. KHAI PHÁ DỮ LIỆU THEO TIẾP CẬN TẬP THÔ Lý thuyết tập thô (Rough Set Theory) do Zdzisaw Pawlak (1926-2006) đề xuất vào năm 1982 đã được ứng dụng ngày càng rộng rãi trong lĩnh vực khoa học máy tính. Lý thuyết tập thô được phát triển trên một nền tảng toán học vững chắc, cung cấp các công cụ hữu ích để giải quyết các bài toán phân tích dữ liệu, phát hiện luật, nhận dạng… Đặc biệt lý thuyết này thích hợp với các bài toán phân tích trên khối lượng dữ liệu lớn, chứa đựng thông tin mơ hồ, không chắc chắn. 1.1. Hệ thông tin Trong hầu hết các hệ quản trị cơ sở dữ liệu thông thường, thông tin thường được biểu diễn dưới dạng các bảng dữ liệu, trong đó mỗi dòng biểu diễn thông tin ứng với một đối tượng, mỗi cột biểu diễn một thuộc tính có thể đo được của đối tượng. 1.2. Bảng quyết định Bảng quyết định là một dạng đặc biệt của hệ thông tin, trong đó tập các thuộc tính A bao gồm hai tập con tách biệt nhau: tập các thuộc tính điều kiện C và tập các thuộc tính quyết định D. Bảng quyết định, được ký hiệu là DS  U , C  D,V , f  với C  D   . 1.3. Quan hệ không phân biệt được Xét hệ thông tin IS  U , A,V , f  , P  A , quan hệ không phân biệt được trên U theo P, ký hiệu là IND  P  , được định nghĩa như sau:   IND  P    u, v  U U a  P, u  a   v  a  . Khi đó 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 6 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 . 1.4. Các tập xấp xỉ 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 . Trong lý thuyết tập thô truyền thống, để biểu diễn tập đối tượng 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 phân hoạch 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ần 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. 1.5. Tập rút gọn và tập lõi Trong bảng quyết định, các thuộc tính điều kiện được phân thành thuộc tính lõi và thuộc tính không cần thiết. Thuộc tính lõi là thuộc tính cốt yếu, không thể thiếu trong việc phân lớp chính xác tập dữ liệu. Thuộc tính không cần thiết là thuộc tính dư thừa mà việc loại bỏ thuộc tính này không ảnh hưởng đến việc phân lớp dữ liệu. Các thuộc tính không cần thiết được phân thành hai nhóm: Thuộc tính dư thừa thực sự và thuộc tính rút gọn. Thuộc tính dư thừa thực sự là những thuộc tính dư thừa mà việc loại bỏ tất cả các thuộc tính như vậy không ảnh hưởng đến việc phân lớp dữ liệu. Thuộc tính rút gọn, với một tổ hợp thuộc tính nào đó, nó là thuộc tính dư thừa và với một tổ hợp các thuộc tính khác nó có thể là thuộc tính lõi. 7 Chương 2. PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT TRÊN BẢNG QUYẾT ĐỊNH Chương này trình bày phương pháp rút gọn thuộc tính trên bảng quyết định sử dụng entropy Shannon trong mô hình tập thô truyền thống. Trên cơ sở đó, phần tiếp theo sẽ trình bày phương pháp sinh luật quyết định từ tập rút gọn tìm được trong mô hình tập thô truyền thống. 2.1. Phương pháp rút gọn thuộc tính trên bảng quyết định Rút gọn thuộc tính trên bảng quyết định là tìm tập con nhỏ nhất của tập thuộc tính điều kiện mà bảo toàn thông tin phân lớp của bảng quyết định để việc sinh luật và phân lớp đạt hiệu quả cao nhất. 2.2. Phương pháp rút gọn thuộc tính sử dụng entropy Shannon 2.2.1. Entropy Shannon trên bảng quyết định Định nghĩa 2.2. ([25]) Cho bảng quyết định DS  U , C  D,V , f  . Giả sử U / C  {C1, C2 ,...., Cm }, U / D  {D1 , D2 ,..., Dn } . Entropy Shannon có điều kiện của D khi đã biết C được định nghĩa bởi m H  D C    i 1 Ci U n  j 1 Ci  D j Ci log 2 Ci  D j Ci 2.2.2. Tập lõi của bảng quyết định dựa trên Entropy Shannon Định nghĩa 2.3. ([21]) Cho bảng quyết định DS  U ,C  D ,V , f  , thuộc tính a  C được gọi là không cần thiết (dư thừa) trong DS dựa trên     entropy Shannon có điều kiện nếu H D C  H D C  a  ; Ngược lại, a gọi là cần thiết. Tập tất cả các thuộc tính cần thiết trong DS được gọi là tập lõi dựa trên entropy Shannon có điều kiện và ký hiệu là HCORE  C  . 8 Ví dụ 2.1. Xét bảng quyết định DS  U , C  D,V , f  với U  u1 , u2 , u3 , u4 , u5 , u6  , C  a1 , a2 , a3  và D  d  cho ở Bảng 2.1. Bảng 2.1. Bảng quyết định minh họa Ví dụ 2.1 U a1 a2 a3 d u1 0 1 1 0 u2 0 1 1 1 u3 0 1 0 0 u4 0 1 0 1 u5 1 0 0 1 u6 1 0 1 1 Rõ ràng DS không nhất quán vì u1  C   u2  C  nhưng u1 d   u2 d  . Ta có U / C  u1 , u2  , u3 , u4  , u5  , u6  ,U / D  u1 , u3  , u2 , u4 , u5 , u6  U /  C  a3   U / a1 , a2   u1 , u2 , u3 , u4  , u5 , u6  1 1 1 1 1 4 2 H  D | C     2. log 2  2. log 2  *2   6 2 2 2 2 6 3 9 1 2 2 2 2 1 2 2 H D |  C  a3   H  D | a1 , a2     4* *log 2  4* log 2    2* *log 2  6 4 4 4 4 6 2 2 2  3 2 H D  C  a3   H D a1 , a2   H  D C   nên a3 là dư 3       thừa trong DS dựa trên entropy Shannon có điều kiện 2.2.3. Tập rút gọn của bảng quyết định dựa trên Entropy Shannon Định nghĩa 2.4. ([21]) Cho bảng quyết định DS  U , C  D, V , f  và tập thuộc tính R  C . Nếu    1) H D R  H D C    2) r  R, H ( D R  r )  H ( D C ) thì R là một tập rút gọn của C dựa trên entropy Shannon có điều kiện, gọi tắt là tập rút gọn Entropy Shannon. Ký hiệu HRED  C  là họ tất cả các tập rút gọn Entropy Shannon. Theo [21], HCORE  C   R. RHRED C  2.2.5. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng Entropy Shannon Thuật toán tìm tập lõi Thuật toán 2.1. Thuật toán tìm tập lõi sử dụng entropy Shannon Input: Bảng quyết định DS  U , C  D,V , f  . Output: Method: Tập lõi HCORE  C  . 10 HCORE  C    ; 1. 2. Tính H ( D | C ) ; 3. For each a  C 4. Begin   5. Tính H D | C  a ; 6. If H D | C  a  H  D | C  then   HCORE  C  : HCORE  C   a; 7. End; 8. Return HCORE  C  ; Phân tích độ phức tạp Thuật toán 2.1 Sử dụng thuật toán trong [14] để tính U / C , độ phức tạp là O  C U  . Do đó, độ phức tạp để tính H ( D | C ) là O  C U  . Vì vậy, độ phức tạp của vòng lặp For từ dòng lệnh thứ 3 đến dòng lệnh  2 thứ 7 là O C U   2  và độ phức tạp của Thuật toán 2.1 là O C U . Thuật toán 2.2. Tính phân hoạch U / R  a khi biết U / R Input: Phân hoạch U / R  R1, R2 ,..., Rk  . Output: Method: 1. TMP   ; Phân hoạch U / R  a 11 2. For each Ri U / R do 3. Begin 4. Tính phân hoạch Ri / a ; 5. TMP  TMP  Ri / a ; 6. End; 7. Return (TMP); Sử dụng thuật toán trong [14] để tính phân hoạch Ri / a với   độ phức tạp O Ri thì độ phức tạp của Thuật toán 2.2 là k O  R   O  U  . i 1 i Thuật toán heuristic tìm tập rút gọn tốt nhất Luận văn đã chọn thuật toán CEBARKCC [23] (Conditional Entropy Based Algorithm for Reduction of Knowledge with Computing Core) là thuật toán heuristic tìm tập rút gọn tốt nhất trong bảng quyết định sử dụng entropy Shannon có điều kiện có tính toán lõi để tìm hiểu, nghiên cứu. Ý tưởng của thuật toán là xuất phát từ tập lõi R  HCORE  C  , lần lượt bổ sung vào tập R các thuộc tính có độ quan trọng lớn nhất cho đến khi tìm được tập rút gọn. Thuật toán 2.3. CEBARKCC: Input: Bảng quyết định DS = (U, CD, R  C, a  C  R Output: 1. Một tập rút gọn R. Tìm tập lõi HCORE  C  theo Thuật toán 2.1; V, f), 12 2. R  HCORE  C  ; // Thêm dần vào R các thuộc tính có độ quan trọng lớn nhất 3.   4.  Begin For each a  C  R 5. 6. Begin  Tính H D | R  a 7. 8.  While H D R  H D C do  Tính SIGR  a   H  D R   H  D R  a ; 9. End 10. am  C  R Chọn sao cho SIGR  am   Max SIGR  a  ; aC  R 11. R  R  am  ; 12. Tính H D R  13.  End; R*  R  HCORE  C  ; 14. For each a  R * 15. 16. 17. Begin  Tính H D | R  a      If H D R  a  H D C then R  R  a ; 13 18. End 19. Return R ; Chứng minh tính đúng đắn của Thuật toán 2.3 Với bước thêm dần vào R các thuộc tính có độ quan trọng lớn nhất, tập thuộc tính R thu được từ câu lệnh từ 3 đến 13 thỏa mãn điều     kiện bảo toàn entropy Shannon H D R  H D C . Với bước loại bỏ các thuộc tính dư thừa, câu lệnh từ 14 đến 19 đảm bảo tập R là tối thiểu, nghĩa là r  R, H ( D  R  r)  H ( D C ) . Theo Định nghĩa 2.2, R là tập rút gọn dựa trên entropy Shannon. Độ phức tạp thời gian của Thuật toán 2.3 Xét vòng lặp While từ dòng lệnh số 3 đến dòng lệnh số 13, theo công thức (2.2) | Ri  a  D j | | Ri  a  D j |  1 n  | Ri  D j | | Ri  D j | log2  | Ri  a | log 2  | Ri |   | Ri | | Ri | | Ri  a | | Ri  a |  i 1 | U i | j 1  m SIGR  a    để tính SIGR  a  , ta chỉ cần tính phân hoạch U / R  a và phân hoạch U / R đã được tính ở bước trước. Từ Thuật toán 2.1, độ phức   tạp thời gian để tính U / R  a khi biết U / R là O U nên độ phức tạp thời gian để tính tất cả các SIGR  a  là  C   C 1  ...  1 * U   C *  C 1 / 2 * U  O  C 2 Độ phức tạp thời gian để chọn thuộc tính có độ quan trọng lớn nhất       . Vòng lặp For là C  C  1  ...  1  C * C  1 / 2  O C 2 tại dòng U  14 lệnh 17 thực hiện R* lần, mỗi lần ta phải tính H  D | R  với độ phức tạp   thời gian O R U . Do đó, độ phức tạp thời gian của dòng lệnh 17 là   O R* R U . Vì vậy, độ phức tạp thời gian của thuật toán là   2 O C U . Ví dụ 2.4. Xét bảng quyết định DS  U , C  D,V , f 2.2. Từ Ví dụ  2.2. cho ở Ví dụ ta U / C  u1 , u2  , u3 , u4 , u5  , u6  , u7  ,U / D  u1 , u3  , u2 , u4 , u5 , u6 , u7  có U /  C  a3   U / a1 , a2   u1 , u2 , u3 , u4 , u5  , u6  , u7  1 2 H  D | C     8. log 2 7 4 2 4  4 7 R  HCORE  C   a3  , U / a3  u1 , u2 , u7  , u3 , u4 , u5 , u6  1 1 2 3 2 H  D | a3     3log 2  2log 2  2  3log 2   3  log 2 3 7 3 3 4 7   Do đó H D | a3   H  D | C  thực hiện vòng lặp While. Xét thuộc tính a1  C  a3  . Theo tính toán ở Ví dụ 2.2: H  D | a1 , a3   H  D | C   4 7 SIGa3  a1   H  D | a3   H  D | a1 , a3   , 2 4 2 3  log2 3   1  log2 3 7 7 7 Xét thuộc tính a2  C  a3  . Tính toán tương tự ta được: SIGa3  a2   SIGa3  a1   2 1  log 2 3 . 7 15 Do a1 và a2 có độ quan trọng như nhau nên chọn bất kỳ a1 hoặc a2 , giả sử chọn a1 , khi đó và R  a1 , a3  và theo tính toán ở   Ví dụ 2.2: H D | a1 , a3   H  D | C  .Thực hiện vòng lặp For. Xét R*  R  HCORE (C )  a1 và R  a1  a3  Theo tính toán ở trên, H  D | a3   H  D | C  . Do đó thuật toán kết thúc và R  a1 , a3  là một tập rút gọn tốt nhất của C dựa trên entropy Shannon. 2.3. Sinh luật quyết định trên tập rút gọn của bảng quyết định 2.3.1. Luật quyết định Cho bảng quyết định DS  U ,C D  , giả sử U / C  {X1 , X 2 ,..., X m} và U / D  {Y1, Y2 ,..., Yn} là các phân hoạch được sinh bởi C, D. Với X i U / C , Y j U / D và X i  Yj   , ký hiệu des  X i  và des Y j  lần lượt là các mô tả của các lớp tương đương X i và Y j trong bảng quyết định DS.   Một luật quyết định đơn có dạng Zij : des  X i   des Y j . 2.3.2. 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 2.3.3. Thuật toán sinh luật quyết định dựa trên tập rút gọn của bảng quyết định Cho bảng quyết U / C  {X1 , X 2 ,..., X m} và định DS  U ,C D  , U / D  {Y1, Y2 ,..., Yn } . Với giả sử X i U / C , Y j U / D và X i  Yj   . Thuật toán RuleExtract hiển thị các luật 16   với độ s  Z   X Y quyết định dạng Zij : des  X i   des Y j   Zij   X i  Yj / X i và đỗ hỗ trợ ij i chắc chắn / U tương j ứng. Thuật toán RuleExtract Input: Bảng quyết định DS = (U, CD, V, f). Output: Hiển thị danh sách các luật với độ chắc chắn  và độ hỗ trợ s . 1. Tính phân hoạch U / C ; 2. For each X i U / C 3. Begin 4. Tính X i / D ; 5. For each Y j  X i / D 6. Begin   7. Sinh luật Zij : des  X i   des Y j 8. Tính  Zij  Y j / X i ; 9. Tính s Zij  Y j / U ; 10. Hiển thị luật Z ij , độ chắc chắn  Zij , độ hỗ         trợ s Zij ; 11. End; 12. End; 13. Return. 17 Chương 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ 3.1. Bài toán Cho trước các bảng quyết định với kích thước trung bình và kích thước lớn, nhiệm vụ của phần thử nghiệm và đánh giá đặt ra là: 1) Cài đặt và thử nghiệm, đánh giá thuật toán rút gọn thuộc tính sử dụng entropy Shannon 2) Cài đặt và thử nghiệm thuật toán sinh luật quyết định RuleExtract trên tập rút gọn tìm được của thuật toán sử dụng entropy Shannon. 3.2. Một số kết quả thử nghiệm 3.2.1. Kết quả thử nghiệm thuật toán rút gọn thuộc tính sử dụng entropy Shannon Bảng 3.1. Kết quả thực hiện Thuật toán CEBARKCC STT Bộ số liệu U C R t Tập rút gọn 1 Lungcancer.data 32 56 4 0.78 {3, 4, 9, 43} 2 Zoo.data 101 17 1 0.505 {1} 3 Liver-disorders (bupa.data) 345 6 3 0.677 {1, 2, 5} 4 Soybean Large.data 307 35 4 3.115 {1, 2, 8, 11} 5 Flag.data 194 29 1 0.682 {1} 6 Credit Approval 690 15 7 29.703 {1, 2, 3, 4, 5, 6, – 18 8} 7 Anneal.data 798 38 7 49.336 {3, 5, 8, 12, 33, 34, 35} 8 Abalone.data 4177 8 3 256.12 {2, 5, 6} 3.2.2. Kết quả thử nghiệm thuật toán sinh luật quyết định dựa trên tập rút gọn Thử nghiệm Thuật toán RuleExtract sinh luật quyết định (luật phân lớp) với bộ số liệu Soybean - small.data. Bảng 3.4. Các luật phân lớp trên bảng quyết định rút gọn Các luật trên bảng quyết định rút gọn  s 1 c4(1) and c22(1) ==> D1 1 0.12766 2 c4(1) and c22(0) ==> D1 1 0.08511 3 c4(2) and c22(3) ==> D2 1 0.12766 4 c4(1) and c22(3) ==> D2 1 0.08511 5 c4(0) and c22(1) ==> D3 1 0.21277 6 c4(1) and c22(2) ==> D4 1 0.21277 7 c4(0) and c22(2) ==> D4 1 0.14894 STT 3.3. Ứng dụng thuật toán rút gọn thuộc tính vào thực tế Trong bộ dữ liệu Lung-Cancer của bộ dữ liệu UCI thì số thuộc tính ban đầu khi chưa thực hiện thuật toán rút gọn là 56. Sau khi thực hiện thuật toán rút gọn đã trình bày thì số thuộc tính quyết định chỉ còn lại 4. Như vậy, thay bằng việc để dự đoán bệnh nhân nào có 19 khả năng mắc ung thư phổi cao, Bác sĩ sẽ phải xét tất cả 56 thuộc tính mà trong đó có tới 52 thuộc tính dư thừa, trong khi chỉ cần dựa vào 4 thuộc tính trong bảng quyết định, Bác sĩ vẫn có thể có kết luận như trên. Một ví dụ khác, khi áp dụng thuật toán tìm tập rút gọn với bộ dữ liệu viêm gan Hepatitis.data trong kho dữ liệu UCI để sinh luật quyết định phục vụ cho các bác sĩ chuyên ngành chuẩn đoán bệnh viêm gan cho bệnh nhân. Ban đầu, bộ dữ liệu Hepatitis.data gồm 19 thuộc tính điều kiện, tương ứng với 19 triệu chứng thu thập được từ bệnh nhân có biểu hiện viêm gan, bao gồm: Tuổi, Giới tính, STEROID, Dùng thuốc kháng Virus, Mệt mỏi, Khó ở, Chán ăn, Gan sưng to, Sơ gan, Viêm lá lách, Huyết thanh, Tĩnh mạch, Sắc tố da, ALK PHOSPHATE, SGOT, ALBUMIN, PROTIME, Tiền sử mắc bệnh hay chưa. Sau khi thực hiện thuật toán rút gọn thuộc tính thu được một tập rút gọn gồm 03 thuộc tính là: Giới tính, Sắc tố da, ALK PHOSPHATE. Điều đó có nghĩa là 16 thuộc tính còn lại là dư thừa. Thay vì sinh luật từ tập 19 thuộc tính ban đầu, chúng tôi chỉ thực hiện việc sinh luật trên tập rút gọn gồm 03 thuộc tính để chuẩn đoán bệnh viêm gan… 3.4. Một số giao diện chương trình 3.4.1. Thực hiện thuật toán rút gọn thuộc tính CEBARKCC 3.4.2. Thực hiện thuật toán sinh luật quyết định 20 KẾT LUẬN 1) Những kết quả chính của luận văn Luận văn tập trung vào hướng nghiên cứu lý thuyết với nội dung nghiên cứu bao gồm hai phần: phần nghiên cứu tổng hợp các kết quả đã công bố và phần chương trình mô phỏng thuật toán. Luận văn đạt được hai kết quả chính sau: (1) Trên cơ sở tổng kết các kết quả đã công bố mới nhất về hướng nghiên cứu rút gọn thuộc tính trong bảng quyết định, bao gồm nhóm các phương pháp rút gọn thuộc tính, luận văn nghiên cứu phương pháp rút gọn thuộc tính sử dụng entropy Shannon (2) Cài đặt và thử nghiệm phương pháp rút gọn thuộc tính sử dụng entropy Shannon và phương pháp sinh luật quyết định trên các bộ số liệu thử nghiệm từ kho dữ liệu UCI. Phương pháp sử dụng entropy Shannon không hiệu quả hơn phương pháp sử dụng khoảng cách entropy Liang ([13]), tuy nhiên ý nghĩa của phần này là làm phong phú thêm các phương pháp rút gọn thuộc tính sử dụng entropy. 2) Hướng phát triển tiếp theo Tác giả luận văn sẽ tiếp tục nghiên cứu các phương pháp rút gọn thuộc tính trên bảng quyết định không đầy đủ sử dụng các độ đo khoảng cách.