Luận án Phát triển một số 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 filter - Wrapper

3 Mệnh đề 3.7. Cho bảng quyết định không đầy đủ   ,IDS U C d  với  1 2, ,..., nU u u u . Giá sử tập thuộc tính điều kiện B được bổ sung vào C với B C  . Đặt ij( ) n nM B b     là ma trận dung sai trên B. Khi đó ta có: 1) Nếu ij 1b  với mọi i=1..n, j=1..n (hay  ( )K B K  ) thì      , ,D C B C B d D C C d     2) Nếu ij 0,b i j  với mọi i=1..n, j=1..n (hay  ( )K B K  ) thì   , 0D C B C B d    . 3) Trường hợp còn lại,     2 1 1 1 , . . . n n ij ij ij ij i j D C B C B d b c c d n        Chứng minh. Từ Mệnh đề 2.3 tính độ đo khoảng cách, ta có:            2 1 1 , . n C B i C B i id i D C B C B d S u S u S u n                      2 1 1 . n C i B i C i B i id i S u S u S u S u S u n          2 2 1 1 1 1 1 1 . . . . . . . n n n n ij ij ij ij ij ij ij ij ij i j i j c b c b d b c c d n n         Dễ thấy rằng, nếu ij 1b  với mọi i=1..n, j=1..n thì        2 1 1 1 , . . , n n ij ij ij i j D C B C B d c c d D C C d n          và nếu ij 0,b i j  với mọi i=1..n, j=1..n thì   , 0D C B C B d    . 3.2.2. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung tập thuộc tính Từ công thức gia tăng tính khoảng cách trong Mệnh đề 3.7 ta có Mệnh đề 3.8 sau đây: 94 Mệnh đề 3.8. Cho bảng quyết định không đầy đủ   ,IDS U C d  với  1 2, ,..., nU u u u và R C là tập rút gọn dựa trên khoảng cách. Giá sử tập thuộc tính điều kiện B được bổ sung vào C với B C  . Đặt ij( ) n nM B b     là ma trận dung sai trên B. Khi đó, nếu ij 1b  với mọi i=1..n, j=1..n thì R là tập rút gọn của   1 ,IDS U C B d   Chứng minh. Nếu ij 1b  với mọi i=1..n, j=1..n, từ Mệnh đề 3.7 ta có:      , ,D C B C B d D C C d     . Do R là tập rút gọn của IDS nên         , , ,D R R d D C C d D C B C B d       và           , , ,r R D R r R r d D C C d       Từ đó ta có: R là tập rút gọn của   1 ,IDS U C B d   . Ý tưởng của thuật toán gia tăng theo hướng tiếp cận kết hợp filter- wrapper bao gồm hai giai đoạn. Trong giai đoạn filter (giống như tiếp cận truyền thống), thuật toán tìm các ứng viên của tập rút gọn, là các tập thuộc tính khi lần lượt bổ sung vào các thuộc tính có độ quan trọng lớn nhất. Trong giai đoạn wrappper, ta sử dụng một bộ phân lớp để tính độ chính xác phân lớp trên từng ứng viên của tập rút gọn và lựa chọn ứng viên có độ chính xác phân lớp tốt nhất làm tập rút gọn. Như vậy, với cách tiếp cận này, ta phải trả giá về thời gian tính toán độ chính xác phân lớp trong giai đoạn wrapper. Tuy nhiên, tập rút gọn thu được có thể có số thuộc tính nhỏ hơn, do đó tập luật phân lớp trên tập rút gọn sẽ có hiệu quả cao hơn về thời gian thực hiện và độ chính xác. Trong bối cảnh tăng trưởng không ngừng của dữ liệu lớn (Big Data), các bảng quyết định ngày càng có số thuộc tính rất lớn và chúng luôn thay đổi, cập nhật. Việc tìm kiếm tập rút gọn có số thuộc tính nhỏ nhất đặc biệt quan trọng. Do đó, chi phí về mặt thời gian để có tập rút gọn giảm thiểu số lượng thuộc 95 tính nhằm thu được tập luật hiệu quả là chấp nhận được. Dựa trên Mệnh đề 3.8, thuật toán gia tăng filter-wrapper tìm tập rút gọn trong bảng quyết định không đầy đủ sử dụng khoảng cách khi bổ sung tập thuộc tính B như sau: Thuật toán IDS_IFW_AA: Thuật toán gia tăng filter- wrapper tìm tập rút gọn khi bổ sung tập thuộc tính. Đầu vào: 1) Bảng quyết định không đầy đủ   ,IDS U C d  với  1 2, ,..., nU u u u , tập rút gọn R C , các ma trận dung sai  ( ) , ( )ij U ijn n n nM C c M d d         , khoảng cách   ,D C C d ; 2) Tập thuộc tính bổ sung B với B C ; Đầu ra: Tập rút gọn 1R của   1 ,IDS U C B d   Bước 1: Khởi tạo 1. :T ; //Chứa các ứng viên tập rút gọn 2. Tính ma trận dung sai ( ) ij n n M B b      ; Bước 2: Kiểm tra tập thuộc tính bổ sung 3. If 1ijb  với mọi  , 1..i j n then Return R ; Bước 3: Thực hiện thuật toán tìm tập rút gọn // Giai đoạn filter, tìm các ứng viên cho tập rút gọn xuất phát từ tập R. 4. While      , ,D R R d D C B C B d     do 5. Begin 6. For each a B do 7. Begin 8. Tính       ,D R a R a d   bởi công thức cập nhật khoảng cách ở Mệnh đề 3.7; 9. Tính            , ,RSIG a D R R d D R a R a d      ; 10. End; 11. Chọn a B sao cho     R m R a B SIG a Max SIG a   ; 12.  : mR R a  ; 13. :T T R  ; 14. End; 96 // Giai đoạn Wrapper,tìm tập rút gọn có độ chính xác phân lớp cao nhất 15. Đặt :t T //t là số phần tử của T, T chứa các chuỗi thuộc tính được chọn, nghĩa là        1 1 2 1 2 , , ,..., , ,..., ti i i i i i T R a R a a R a a a    ; 16. Đặt       1 1 2 1 21 2 : ; : , ;...; : , ,..., ti i i t i i i T R a T R a a T R a a a      17. For j = 1 to t 18. Begin 19. Tính độ chính xác phân lớp trên jT bằng một bộ phân lớp sử dụng phương pháp 10-fold; 20. End 21. 1 : joR T với joT có độ chính xác phân lớp lớn nhất. 22. Return 1R ; Tiếp theo, ta đánh giá độ phức tạp của thuật toán IDS_IFW_AA. Ký hiệu , ,C U B tương ứng là số thuộc tính điều kiện, số đối tượng và số thuộc tính điều kiện bổ sung thêm. Ở câu lệnh 2, độ phức tạp tính ma trận dung sai ( )M B là  2O B U . Trong trường hợp tốt nhất, thuật toán kết thúc ở câu lệnh 3 (tập rút gọn không thay đổi). Khi đó, độ phức tạp thuật toán IDS_IFW_AA là  2O B U . Ngược lại xét vòng lặp While từ câu lệnh 4 đến 14, để tính  BSIG a ta phải tính       ,D R a R a d   vì   ,D R R d đã được tính ở bước trước. Độ phức tạp tính gia tăng       ,D R a R a d   ở câu lệnh số 8 là  2O U . Do đó, độ phức tạp của vòng lặp While là  2 2O B U và độ phức tạp của giai đoạn filter trong trường hợp xấu nhất là  2 2O B U . Độ phức tạp của giai đoạn wrapper phụ thuộc vào độ phức tạp của bộ phân lớp được sử dụng. Giả sử độ phức tạp của bộ phân lớp là  O T , khi đó độ phức tạp của giai đoạn wrapper là 97  *O B T . Vì vậy, độ phức tạp của thuật toán IDS_IFW_AA là    2 2 *O B U O B T . Nếu thực hiện thuật toán không gia tăng filter-wrapper trực tiếp trên bảng quyết định có số thuộc tính C B , độ phức tạp là      2 2* *O C B U O C B T   . Do đó, thuật toán gia tăng IDS_IFW_AA giảm thiểu đáng kể độ phức tạp thời gian thực hiện, đặc biệt trong trường hợp B nhỏ. Tiếp theo, sẽ trình bày thuật toán filter-wrapper tìm tập rút gọn sử dụng khoảng cách khi loại bỏ tập thuộc tính theo hướng tiếp cận tính toán gia tăng. Trước hết, ta xây dựng các công thức cập nhật khoảng cách khi loại bỏ tập thuộc tính. 3.2.3. Công thức cập nhật khoảng cách khi loại bỏ tập thuộc tính Cho bảng quyết định không đầy đủ   ,IDS U C d  với  1 2, ,..., nU u u u và   ij n nM C c     ,    ij n nM d d     tương ứng là ma trận dung sai trên C và d. Theo Mệnh đề 2.3 ở Chương 2, khoảng cách giữa hai tập thuộc tính C và  C d được xác định như sau:              2 2 1 1 1 1 1 , . n n n C i C i i ij ij ijd i i j D C C d S u S u S u c c d n n          Mệnh đề 3.9. Cho bảng quyết định không đầy đủ   ,IDS U C d  với  1 2, ,..., nU u u u . Giá sử tập thuộc tính điều kiện B loại bỏ khỏi C với B C và A C B  là tập thuộc tính còn lại. Đặt ij( ) n nM B b     và ij( ) n nM A a     tương ứng là ma trận dung sai trên B và A . Khi đó,     2 1 1 1 , . . n n ij ij ij i j D A A d a a d n      với các phần tử ija của ma trận ( )M A được tính như sau: 98 1) Nếu ij 1c  thì ij 1a  với i=1..n, j=1..n 2) Nếu ij 0c  và ij 1b  thì ij 0a  với i=1..n, j=1..n 3) Nếu ij 0c  và ij 0b  thì ij 1a  nếu  j A iu S u và ij 0a  nếu  j A iu S u với i=1..n, j=1..n. Chứng minh. Dễ thấy rằng: 1) Do A C nên    C i A iS u S u , từ ij 1c  ta có ij 1a  . 2) Do ij ij ij.c a b , nếu ij 0c  và ij 1b  thì ij 0a  3) Theo định nghĩa ma trận dung sai, nếu  j A iu S u thì ij 1a  , nếu  j A iu S u thì ij 1a  Mệnh đề 3.9 cho phép tính toán khoảng cách   ,D A A d dựa vào các ma trận dung sai đầu vào ij( ) n n M C c      , ij( ) n nM B b     . Trong trường hợp ma trận ij( ) n n M C c      chứa nhiều phần tử bằng 1 (Phủ sinh bởi C là thô) thì công thức tính   ,D A A d bởi Mệnh đề 3.9 là hiệu quả. 3.2.4. Thuật toán gia tăng filter-wrapper cập nhật tập rút gọn khi loại bỏ tập thuộc tính Dựa trên Mệnh đề 3.9, thuật toán gia tăng filter-wrapper tìm tập rút gọn trong bảng quyết định không đầy đủ sử dụng khoảng cách khi loại bỏ tập thuộc tính B như sau: Thuật toán IDS_IFW_DA: Thuật toán gia tăng filter- wrapper tìm tập rút gọn khi loại bỏ tập thuộc tính. Đầu vào: 1) Bảng quyết định không đầy đủ   ,IDS U C d  với  1 2, ,..., nU u u u , tập rút gọn R C , các ma trận dung sai  ( ) , ( )ij U ijn n n nM C c M d d         , khoảng cách   ,D C C d ; 2) Tập thuộc tính B loại bỏ khỏi C với B C ; 99 Đầu ra: Tập rút gọn 1R của     1 ,IDS U C B d   1) Trường hợp 1: Tập thuộc tính bị loại bỏ B không thuộc tập rút gọn (các thuộc tính dư thừa), tập rút gọn không thay đổi. Nếu B C R  thì Retturn (R); 2) Trường hợp 2: Tập thuộc tính bị loại bỏ B chứa tập rút gọn R, khi đó thực hiện lại thuật toán filter-wrapper IDS_FW_DAR ở Chương 2 tìm tập rút gọn. Nếu R B thì thực hiện thuật toán IDS_FW_DAR; 3) Trường hợp 3: Trường hợp còn lại B R , thực hiện các bước của thuật toán tìm tập rút gọn. Bước 1: Khởi tạo 1. Đặt : ;A C B  :T  ; // Chứa các ứng viên tập rút gọn 2. Tính ma trận dung sai ( ) ij n n M B b      , tính ma trận dung sai ij( ) n n M A a      bởi công thức trong Mệnh đề 3.9. 3. Đặt : ;R R B  //Xét các thuộc tính trong tập rút gọn Bước 2: Thực hiện thuật toán tìm tập rút gọn // Giai đoạn filter, tìm các ứng viên cho tập rút gọn xuất phát từ tập R. 4. While      , ,D R R d D A A d   do 5. Begin 6. For each a R do 7. Begin 8. Tính khoảng cách        ,D R a R a d   bởi công thức trong Mệnh đề 3.9; 9. Tính             , ,RSIG a D R a R a d D R R d      10. End; 11. Chọn ma R sao cho     R m R a R SIG a Min SIG a   ; 12.  : mR R a  ; 13. :T T R  ; 14. End; 100 // Giai đoạn Wrapper,tìm tập rút gọn có độ chính xác phân lớp cao nhất 15. Đặt :t T //t là số phần tử của T, T chứa các chuỗi thuộc tính được chọn, nghĩa là        1 1 2 1 , , ,..., ,..., ti i i i i T R a R a a R a a    ; 16. Đặt       1 1 2 11 2 , , ,..., ,..., ti i i t i i T R a T R a a T R a a      17. For j = 1 to t 18. Begin 19. Tính độ chính xác phân lớp trên jT bằng một bộ phân lớp sử dụng phương pháp 10-fold; 20. End 21. 1 : joR T với joT có độ chính xác phân lớp lớn nhất. 22. Return 1R ; Tiếp theo, ta đánh giá độ phức tạp của thuật toán IDS_IFW_DA. Ký hiệu , ,C U B tương ứng là số thuộc tính điều kiện, số đối tượng và số thuộc tính điều kiện xóa khỏi C. Trường hợp tốt nhất, thuật toán rơi vào Trường hợp 1, nghĩa là tập rút gọn không thay đổi. Trường hợp xấu nhất, thuật toán rơi vào Trường hợp 2, thực hiện lại thuật toán IDS_FW_DAR ở Chương 2 tìm tập rút gọn trên bảng quyết định sau khi xóa tập thuộc tính B với độ phức tạp là:    2 2* *O C B U O C B T   . Ta xét độ phức tạp trong trường hợp còn lại (Trường hợp 3). Xét vòng lặp While từ câu lệnh 4 đến 14, để tính  RSIG a ta phải tính        ,D R a R a d   vì   ,D R R d đã được tính ở bước trước. Độ phức tạp tính        ,D R a R a d   ở câu lệnh số 8 là   2 O U . Do đó, độ phức 101 tạp của vòng lặp While là  2 2*O R B U và độ phức tạp của giai đoạn filter là  2 2*O R B U . Độ phức tạp của giai đoạn wrapper phụ thuộc vào độ phức tạp của bộ phân lớp được sử dụng. Giả sử độ phức tạp của bộ phân lớp là  O T , khi đó độ phức tạp của giai đoạn wrapper là  *O R B T . Vì vậy, độ phức tạp của thuật toán IDS_IFW_DA là    2 2* *O R B U O R B T   . Nếu thực hiện thuật toán không gia tăng filter-wrapper trực tiếp trên bảng quyết định có số thuộc tính C B , độ phức tạp là    2 2* *O C B U O C B T   . Do đó, với Trường hợp 3 thì thuật toán IDS_IFW_DA hiệu quả. Nếu R càng nhỏ thì thuật toán IDS_IFW_DA càng hiệu quả. Nếu thuật toán rơi vào Trường hợp 2 (tính lại tập rút gọn) thì độ phức tạp thuật toán IDS_IFW_DA tương đương thuật toán IDS_FW_DAR ở chương 2. Còn nếu thuật toán rơi vào Trường hợp 1 thì thu được luôn tập rút gọn mà không phải tính toán gì cả. 3.2.5. Thực nghiệm và đánh giá các thuật toán Trong phần này trình bày kết quả thực nghiệm nhằm đánh giá tính hiệu quả của thuật toán gia tăng filter-wrapper IDS_IFW_AA đề xuất với thuật toán gia tăng filter UARA [83] về số lượng thuộc tính tập rút gọn và độ chính xác của mô hình phân lớp. UARA [83] là thuật toán gia tăng filter tìm tập rút gọn của bảng quyết định không đầy đủ trong trường hợp bổ sung tập thuộc tính sử dụng miền dương. Việc thực nghiệm được thực hiện trên 06 tập dữ liệu mẫu lấy từ kho dữ liệu UCI [118] được mô tả ở Bảng 3.10, đây là các tập dữ liệu thiếu giá trị (missing value) trên miền giá trị thuộc tính điều kiện. Mỗi tập thuộc tính điều kiện được chia ngẫu nhiên thành hai phần: tập thuộc tính ban đầu (cột 4 Bảng 3.10) ký hiệu là C0, và tập thuộc tính gia tăng (cột 5 Bảng 3.10). Tập thuộc tính gia tăng được chia ngẫu nhiên thành 5 phần bằng nhau, ký hiệu tương ứng là C1, C2, C3, C4, C5. 102 Bảng 3.10. Bộ dữ liệu thực nghiệm của thuật toán IDS_IFW_AA STT Tập dữ liệu Số đối tượng Số thuộc tính điều kiện Số thuộc tính ban đầu Số thuộc tính gia tăng Số lớp quyết định (1) (2) (3) (6) (4) (5) (7) 1 Audiology 226 69 34 35 24 2 Soybean -large 307 35 20 15 2 3 Cong. Voting Records 435 16 6 10 2 4 Arrhythmia 452 279 139 140 16 5 Anneal 798 38 18 20 6 6 Advers. 3279 1558 778 780 2 Để tiến hành thực nghiệm hai thuật toán IDS_IFW_AA và UARA, trước hết ta thực hiện hai thuật toán trên tập dữ liệu với tập thuộc tính ban đầu (coi tập thuộc tính ban đầu là tập gia tăng). Tiếp theo, thực hiện hai thuật toán khi lần lượt bổ sung từ phần thứ nhất đến phần thứ năm của tập thuộc tính gia tăng. Với các thuật toán filter-wrapper, việc lựa chọn bộ phân lớp trong giai đoạn wrapper sẽ ảnh hưởng đến kết quả thực hiện của thuật toán về thời gian thực hiện và độ chính xác phân lớp. Tuy nhiên, việc lựa chọn bộ phân lớp sẽ không ảnh hưởng đến kết quả so sánh, đánh giá giữa các thuật toán khác vì chúng đều thực hiện trên một bộ phân lớp cụ thể. Do đó, ta sử dụng bộ phân lớp C4.5 để tính độ chính xác phân lớp của hai thuật toán và phương pháp kiểm tra chéo 10-fold. Sở dĩ ta chọn bộ phân lớp C4.5 vì đây là bộ phân lớp thông dụng, được sử dụng phổ biến trong các nghiên cứu khác khi so sánh, đánh giá các phương pháp rút gọn thuộc tính. Công cụ thực hiện thử nghiệm là Matlab R2016a. Môi trường thử nghiệm là máy tính PC với cấu hình Intel(R) Core(TM) 2 i3-2120 CPU, 3.3 GHz và 4 GB bộ nhớ. 103 Bảng 3.11 trình bày kết quả so sánh về số lượng thuộc tính tập rút gọn (ký hiệu là R ) và độ chính xác phân lớp của hai thuật toán IDS_IFW_AA và UARA. Kết quả Bảng 3.11 cho thấy, với mỗi bước lặp khi bổ sung tập dữ liệu gia tăng và trên toàn bộ tập dữ liệu, độ chính xác phân lớp của IDS_IFW_AA cao hơn UARA một chút trên tất cả các tập dữ liệu. Hơn nữa, số thuộc tính tập rút gọn của IDS_IFW_AA nhỏ hơn khá nhiều UARA, đặc biệt trên tập rút gọn có số thuộc tính lớn như Arrhythmia, Advertisements. Do đó, thời gian thực hiện và tính khái quát hóa của tập luật phân lớp trên tập rút gọn của IDS_IFW_AA tốt hơn so với UARA. Bảng 3.11. Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của thuật toán IDS_IFW_AA và UARA STT Tập dữ liệu Tập thuộc tính Số thuộc tính Tổng số thuộc tính IDS_IFW_AA UARA R Độ chính xác R Độ chính xác 1 Audiology 0C 34 34 4 64.26 8 62.18 1C 7 41 5 68.19 9 65.17 2C 7 48 5 68.19 10 69.26 3C 7 55 6 72.36 12 72.35 4C 7 62 7 78.26 14 74.18 5C 7 69 7 78.26 15 78.02 2 Soybean – large 0C 20 20 4 82.34 8 81.16 1C 3 23 4 82.34 8 81.16 2C 3 26 5 86.92 9 82.08 3C 3 29 5 86.92 10 85.14 4C 3 32 7 90.27 11 90.26 5C 3 35 8 92.85 12 92.18 104 STT Tập dữ liệu Tập thuộc tính Số thuộc tính Tổng số thuộc tính IDS_IFW_AA UARA R Độ chính xác R Độ chính xác 3 Cong. Voting Records 0C 6 6 4 81.36 5 81.04 1C 2 8 5 86.24 7 85.52 2C 2 10 6 89.18 8 89.18 3C 2 12 6 89.18 9 89.18 4C 2 14 7 91.15 11 90.29 5C 2 16 8 94.06 12 93.68 4 Arrhythmia 0C 139 139 5 62.14 9 62.86 1C 28 167 6 69.27 14 68.15 2C 28 195 7 70.48 16 69.84 3C 28 223 7 70.48 17 69.84 4C 28 251 9 71.37 24 70.92 5C 28 279 10 76.24 25 75.68 5 Anneal 0C 18 18 3 68.24 5 68.24 1C 4 22 4 72.46 7 71.62 2C 4 26 4 72.46 7 71.62 3C 4 30 5 79.88 8 76.85 4C 4 34 6 86.13 9 85.19 5C 4 38 7 91.28 10 90.84 6 Advers. 0C 778 778 9 71.18 15 70.68 1C 156 934 12 76.64 22 72.85 2C 156 1090 15 79.14 29 78.94 3C 156 1246 19 86.18 35 83.17 4C 156 1402 20 89.24 38 86.26 5C 156 1558 21 92.85 44 91.46 Bảng 3.12 trình bày kết quả so sánh thời gian thực hiện hai thuật toán IDS_IFW_AA và UARA (tính bằng giây - s). Kết quả Bảng 3.12 cho thấy, 105 thời gian thực hiện của IDS_IFW_AA cao hơn UARA trên tất cả các tập dữ liệu, nguyên nhân là IDS_IFW_AA mất thêm chi phí thời gian thực hiện bộ phân lớp trong giai đoạn wrapper, đây cũng là nhược điểm chung của các thuật toán theo tiếp cận filter-wrapper. Bảng 3.12. Thời gian thực hiện của thuật toán IDS_IFW_AA và UARA (s) STT Tập dữ liệu Tập thuộc tính Số thuộc tính Tổng số thuộc tính IFWA_ IDS _AA UARA Thời gian Tổng thời gian Thời gian Tổng thời gian 1 Audiology 0C 34 34 5.36 5.36 4.28 4.28 1C 7 41 0.48 5.84 0.39 4.67 2C 7 48 0.45 6.29 0.41 5.08 3C 7 55 0.52 6.81 0.38 5.46 4C 7 62 0.44 7.25 0.39 5.85 5C 7 69 0.59 7.84 0.34 6.19 2 Soybean – large 0C 20 20 2.84 2.84 2.18 2.18 1C 3 23 0.14 2.98 0.36 2.54 2C 3 26 0.21 3.19 0.22 2.76 3C 3 29 0.16 3.35 0.15 2.91 4C 3 32 0.33 3.68 0.21 3.12 5C 3 35 0.28 3.96 0.16 3.28 3 Cong. Voting Records 0C 6 6 4.12 4.12 3.08 3.08 1C 2 8 0.54 4.66 0.54 3.62 2C 2 10 0.32 4.98 0.43 4.05 3C 2 12 0.63 5.61 0.54 4.59 4C 2 14 0.51 6.12 0.53 5.12 5C 2 16 0.72 6.84 0.56 5.68 4 Arrhythmia 0C 139 139 24.68 24.68 20.78 20.78 1C 28 167 3.04 27.72 2.06 22.84 2C 28 195 3.24 30.96 2.33 25.17 3C 28 223 3.69 34.65 2.89 28.06 4C 28 251 2.07 36.72 2.06 30.12 5C 28 279 2.12 38.84 1.16 31.28 106 STT Tập dữ liệu Tập thuộc tính Số thuộc tính Tổng số thuộc tính IFWA_ IDS _AA UARA Thời gian Tổng thời gian Thời gian Tổng thời gian 5 Anneal 0C 18 18 6.84 6.84 5.19 5.19 1C 4 22 0.48 7.32 0.55 5.74 2C 4 26 0.43 7.75 0.55 6.29 3C 4 30 0.44 8.19 0.53 6.82 4C 4 34 0.45 8.64 0.36 7.18 5C 4 38 0.42 9.06 0.24 7.42 6 Advers. 0C 778 778 77.24 77.24 68.35 68.35 1C 156 934 6.51 83.75 4.54 72.89 2C 156 1090 6.09 89.84 5.35 78.24 3C 156 1246 6.13 95.97 4.94 83.18 4C 156 1402 5.26 101.23 4.58 87.76 5C 156 1558 5.55 106.78 4.52 92.28 3.3. Kết luận chương 3 Trong Chương 3, luận án trình bày kết quả xây dựng các công thức gia tăng tính khoảng cách đề xuất ở Chương 2 trong trường hợp bổ sung, loại bỏ tập đối tượng và bổ sung, loại bỏ tập thuộc tính. Dựa vào các công thức gia tăng được xây dựng, luận án trình bày kết quả đề xuất bốn thuật toán gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ thay đổi theo tiếp cận filter- wrapper: 1) Thuật toán gia tăng filter-wrapper IDS_IFW_AO tìm tập rút gọn trong trường hợp bổ sung tập đối tượng. 2) Thuật toán filter-wrapper IDS_IFW_DO tìm tập rút gọn trong trường hợp loại bỏ tập đối tượng. 3) Thuật toán gia tăng filter-wrapper IDS_IFW_AA tìm tập rút gọn trong trường hợp bổ sung tập thuộc tính. 107 4) Thuật toán gia tăng filter-wrapper IDS_IFW_DA tìm tập rút gọn trong trường hợp loại bỏ tập thuộc tính. Luận án tiến hành thực nghiệm hai thuật toán đề xuất IDS_IFW_AO, IDS_IFW_AA trên các bộ dữ liệu mẫu từ kho dữ liệu UCI [118] để đánh giá tính hiệu quả của thuật toán gia tăng đã đề xuất. Trong trường hợp bổ sung tập đối tượng, thuật toán gia tăng filter- wrapper đề xuất IDS_IFW_AO hiệu quả hơn thuật toán không gia tăng filter- wrapper IDS_FW_DAR (được trình bày ở Chương 2) về thời gian thực hiện. Với hướng tiếp cận truyền thống filter, số lượng thuộc tính tập rút gọn của thuật toán IDS_IFW_AO nhỏ hơn đáng kể thuật toán filter IARM-I [86], hơn nữa độ chính xác phân lớp của thuật toán IDS_IFW_AO cao hơn so với IARM-I. Do đó, mô hình phân lớp trên tập rút gọn của thuật toán IDS_IFW_AO hiệu quả hơn so với các thuật toán filter khác. Tuy nhiên, thuật toán IDS_IFW_AO phải mất thêm chi phí về thời gian thực hiện do phải thực hiện các bộ phân lớp. Trong trường hợp bổ sung tập thuộc tính, số lượng thuộc tính tập rút gọn của thuật toán gia tăng filter-wrapper IDS_IFW_AA cũng nhỏ hơn đáng kể thuật toán gia tăng filter UARA [83]. Hơn nữa, độ chính xác phân lớp của thuật toán IDS_IFW_AA cũng cao hơn so với UARA. Với trường hợp này, mô hình phân lớp trên tập rút gọn của thuật toán IDS_IFW_AA cũng hiệu quả hơn so với các thuật toán filter khác. Tuy nhiên, thuật toán IDS_IFW_AA cũng phải trả giá về thời gian thực hiện do phải thực hiện các bộ phân lớp. 108 KẾT LUẬN A. Các kết quả đạt được của luận án Luận án nghiên cứ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 đủ 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 phân lớp. Kết quả chính của luận án bao gồm: 1. Xây dựng một độ đo khoảng cách mới và đề xuất thuật toán theo tiếp cận kết hợp filter-wrapper IDS_FW_DAR 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. 2. Xây dựng các công thức gia tăng tính khoảng cách mới và đề xuất 04 thuật toán gia tăng filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ trong trường hợp bảng quyết định bổ sung, loại bỏ tập đối tượng và tập thuộc tính (các thuật toán IDS_IFW_AO, IDS_IFW_DO, IDS_IFW_AA, IDS_IFW_DA) 3. Cài đặt, thử nghiệm, so sánh, đánh giá các thuật toán đề xuất với các thuật toán khác đã công bố trên các tập dữ liệu mẫu từ kho dữ liệu UCI [118]. Kết quả thử nghiệm trên các bộ số liệu mẫu từ kho dữ liệu UCI [118] cho thấy, các thuật toán đề xuất theo tiếp cận filter-wrapper IDS_FW_DAR đề xuất giảm thiểu đáng kể số lượng thuộc tính tập rút gọn so với các thuật toán filter khác. Hơn nữa, các thuật toán gia tăng filter-wrapper duy trì và nâng cao độ chính xác của mô hình phân lớp so với các thuật toán gia tăng filter. Do đó, các thuật toán filter-wrapper đề xuất giảm thiểu đáng kể độ phức tạp của mô hình phân lớp. Tuy nhiên, nhược điểm chung của các thuật toán filter-wrapper đề xuất là mất thêm chi phí về thời gian thực hiện các bộ phân lớp so với các thuật toán filter khác. Với mục tiêu nâng cao hiệu quả của mô hình phân lớp thì nhược điểm này có thể chấp nhận được vì rút gọn thuộc tính chỉ là bước tiền xử lý trong quá trình xây dựng các mô hình khai phá dữ liệu. 109 B. Những đóng góp mới của luận án 1. Xây dựng một độ đo khoảng cách mới và đề xuất thuật toán theo tiếp cận kết hợp filter-wrapper IDS_FW_DAR 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. 2. Xây dựng các công thức gia tăng tính khoảng cách mới và đề xuất 04 thuật toán gia tăng filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ trong trường hợp bảng quyết định bổ sung, loại bỏ tập đối tượng và tập thuộc tính (các thuật toán IDS_IFW_AO, IDS_IFW_DO, IDS_IFW_AA, IDS_IFW_DA). C. Hướng nghiên cứu tiếp theo 1. Triển khai các thuật toán đề xuất vào việc giải quyết các lớp bài toán trong thực tiễn, đặc biệt các bài toán có dữ liệu với số thuộc tính lớn (high dimention data) trong các lĩnh vực khác nhau như dữ liệu gen trong tin sinh học 2. Tiếp tục nghiên cứu, đề xuất các thuật toán gia tăng filter-wrapper hiệu quả nhằm giảm thiểu thời gian thực hiện dựa trên các mô hình tập thô mở rộng khác phù hợp với các lớp bài toán trong thực tiễn. 110 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ 1 Nguyen Ba Quang, Nguyen Long Giang, Dang Thi Oanh “A Distance based Incremental Filter-Wrapper Algorithm for Fingding Reduct in Incomplete Decision Tables”, Vietnam Journal of Science and Technology - Vietnam Academy of Science and Technology, Vol 57, No 4, 2019, pp. 499-512. 2 Nguyễn Bá Quảng, Nguyễn Long Giang, Trần Thanh Đại, Nguyễn Ngọc Cương, “Phương pháp Filter-Wrapper rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng khoảng cách”, Kỷ yếu Hội thảo quốc gia lần thứ XXII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Thái Bình, 28-29/06/2019, Tr. 246-252. 3 Nguyễn Bá Quảng, Nguyễn Long Giang, Nguyễn Thị Lan Hương, Nguyễn Ngọc Cương, “Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng khoảng cách”, Kỷ yếu Hội thảo quốc gia lần thứ XXII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Thái Bình, 28-29/06/2019, Tr. 253-259. 4 Phạm Minh Ngọc Hà, Nguyễn Long Giang, Nguyễn Văn Thiện, Nguyễn Bá Quảng, “Về một thuật toán gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ”, Chuyên san các công trình nghiên cứu phát triển CNTT&TT, Tạp chí Công nghệ thông tin và truyền thông - Bộ TT&TT, Tập 2019, Số 1, Tháng 9, Tr. 11-18. 5 Nguyễn Bá Quảng, Nguyễn Long Giang, “Về một thuật toán gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ trong trường hợp bổ sung tập thuộc tính”, Tạp chí Nghiên cứu KH&CN Quân sự, Số 63, 10-2019, Tr. 171-183. 111 TÀI LIỆU THAM KHẢO Tiếng Việt: [1] 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ọc viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, 2016. [2] Nguyễn Thị Lan Hương, “Rút gọn thuộc tính trong bảng quyết định động theo tiếp cận tập thô”, Luận án Tiến sĩ Toán học, Học viện Khoa học và Công nghệ-Viện Hàn lâm Khoa học và Công nghệ Việt Nam, 2016. [3] Nguyễn Văn Thiện, “Một số phương pháp lai ghép trong rút gọn thuộc tính theo tiếp cận tập thô mờ”, Luận án Tiến sĩ Máy tính, Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, 2018. [4] Nguyễn Văn Thiện, Nguyễn Long Giang, Nguyễn Như Sơn, “Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định sử dụng khoảng cách mờ”, Hội thảo Quốc gia lần thứ XXI - Một số vấn đề chọn lọc của CNTT và TT, Thanh Hóa, 27-28/07/2018, Tr. 296- 302. Tiếng Anh: [5] A.K. Das, S. Sengupta, S. Bhattacharyya, “A Group Incremental Feature Selection for Classification using Rough Set Theory based Genetic Algorithm”, Applied Soft Computing 65, pp. 400-411, 2018. [6] A.P. Zeng, T.R. Li, D. Liu, J.B. Zhang, H.M. Chen, “A fuzzy rough set approach for incremental feature selection on hybrid information systems”, Fuzzy Sets and Systems, Volume 258, pp. 39-60, 1 January 2015. [7] A.P. Zeng , T.R. Li, J. Hu, H.M. Chen, Chuan Luo, “Dynamical updating fuzzy rough approximations for hybrid data under the variation of attribute values”, Information Sciences 000, pp. 1-26, 2016. 112 [8] Cao Chinh Nghia, Demetrovics Janos, Nguyen Long Giang, Vu Duc Thi, “About a fuzzy distance between two fuzzy partitions and attribute reduction problem”, Cybernetics and Information Technologies, Vol 16, No 4, pp. 13-28, 2016. [9] C. C. Zhang, J. H. Dai, “An incremental attribute reduction approach based on knowledge granularity for incomplete decision systems”, Granular Computing, pp. 1-15, 2019. [10] C.J. Yang, H. Ge, L.S. Li, J. Ding, “A unified incremental reduction with the variations of the object for decision tables”, Soft Computing, Vol. 23, Iss. 15, pp. 64076427, 2019. [11] C. Luo, T. R. Li and H. M. Chen, “Dynamic maintenance of approximations in setvalued ordered decision systems under the attribute generalization”, Information Sciences 257, pp. 210 - 228, 2014. [12] C. Luo, T.R. Li, H.M. Chen, H. Fujita, Z. Yi, “Efficient updating of probabilistic approximations with incremental objects”, Knowledge-Based Systems 109, pp. 71-83, 2017. [13] C. Luo, T.R. Li, Y. Yao, “Dynamic probabilistic rough sets with incomplete data”, Information Sciences 417, pp. 39–54, 2017. [14] C. Luo, T.R. Li, Y.Y. Huang, H. Fujita, “Updating three-way decisions in incomplete multi-scale information systems”, Information Sciences 476, pp. 274-289, 2019. [15] C.X. Hu, S.X. Liu, G.X. Liu, “Matrix-based approaches for dynamic updating approximations in multigranulation rough sets”, Knowl Based Syst 122, pp. 51-63, 2017. [16] C.Z. Wang, Y. Qi, Q. He, Attribute reduction using distance-based fuzzy rough sets, 2015 International Conference on Machine Learning and Cybernetics , IEEE, 2015. [17] C.Z. Wang, Y.Huang, M.W. Shao, X.D.Fan, Fuzzy rough set-based attribute reduction using distance measures, Knowledge-Based Systems, Volume 164, 15 January 2019, pp. 205-212. 113 [18] D.D. Zhang, R.P. Li, X.T. Tang, Y.S. Zhao, “An incremental reduct algorithm based on generalized decision for incomplete decision tables”, IEEE 3rd International Conference on Intelligent System and Knowledge Engineering, pp. 340-344, 2008. [19] Demetrovics Janos, Nguyen Thi Lan Huong, Vu Duc Thi, Nguyen Long Giang, “Metric Based Attribute Reduction Method in Dynamic Decision Tables”, Cybernetics and Information Technologies, Vol.16, No.2, pp. 3- 15, 2016. [20] D.G. Chen, Y. Yang, Z. Dong, “An incremental algorithm for attribute reduction with variable precision rough sets”, Appl. Soft Comput., vol. 45, pp. 129-149, 2016. [21] D. Liu, T.R. Li, D. Ruan, W.L. Zou, “An incremental approach for inducing knowledge from dynamic information systems”, Fundam. Inform. 94, pp. 245-260, 2009. [22] D. Liu, T.R. Li, G.R. Liu, P. Hu, “An incremental approach for inducing interesting knowledge based on the change of attribute values”, in: Proceedings of the2009 IEEE International Conference on Granular Computing, Nanchang, China, pp.415–418, 2009. [23] D. Liu, T.R. Li, J.B. Zhang, “A rough set-based incremental approach for learning knowledge in dynamic incomplete information systems”, International Journal of Approximate Reasoning 55, pp. 1764-1786, 2014. [24] D. Liu, T.R. Li, J.B. Zhang, “Incremental updating approximations in probabilistic rough sets under the variation of attributes”, Knowledge- Based Systems 73, pp. 81-96, 2015. [25] D.X. Peng, X.D. Hong, “Research on Heuristic Knowledge Reduction Algorithm for Incomplete Decision Table”, IEEE International Conference on Internet Technology and Applications, 2010. [26] D. Yue, Z. Xu, C.D. Mei, W.Y. Mei, “Analysis of Attribute Reduction of Incomplete Decision Table Based on Information Entropy”, 8th International Conference on Intelligent Computation Technology and Automation (ICICTA), 2015. 114 [27] F. Hu, G. Wang, H. Huang, “Incremental attribute reduction based on elementary sets”, International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, Springer-Verlag, pp.185-193, 2005. [28] F.M. Ma, J.W. Chen, W. Han, “A Positive Region Based Incremental Attribute Reduction Algorithm for Incomplete System”, International Conference on Electronic Information Technology and Intellectualization (ICEITI 2016), pp. 153-158, 2016. [29] F.M. Ma, T.F. Zhang, “Generalized binary discernibility matrix for attribute reduction in incomplete information systems”, The Journal of China Universities of Posts and Telecommunications, Volume 24, Issue 4, pp. 57-75, 2017. [30] F.M. Ma, M.W. Ding , T.F. Zhang, J. Cao, “Compressed binary discernibility matrix based incremental attribute reduction algorithm for group dynamic data”, Neurocomputing, 2019. [31] F. Wang, J.Y. Liang, C.Y. Dang, “Attribute reduction for dynamic data sets”, Applied Soft Computing, 13(1), pp. 676-689, 2013. [32] F. Wang, J.Y. Liang, Y.H. Qian, “Attribute reduction: A dimension incremental strategy”, Knowledge-Based Systems, Volume 39, pp. 95- 108, 2013. [33] G. Hao, L.L. Shu, Y.C. jian, D. Jian, “Incremental reduction algorithm with acceleration strategy based on conflict region”, Artif Intell Rev, Springer, 2017. [34] G.M. Lang, D.Q. Miao, T. Yang, M.J. Cai, “Knowledge reduction of dynamic covering decision information systems when varying covering cardinalities”, Information Sciences 346-47, pp. 236-260, 2016. [35] G.M. Lang, Q. Li, M.J. Cai, T. Yang, Q.M. Xiao, Incremental approaches to knowledge reduction based on characteristic matrices, Int. J. Mach. Learn. Cybern. 8 (1) pp. 203-222, 2017. [36] G.M. Lang, D.Q. Miao , M.J. Cai, Z.F. Zhang, “ Incremental approaches for updating reducts in dynamic covering information systems, Knowledge Based Systems 134, pp. 85..104, 2017. 115 [37] G.M. Lang, M.J. Cai, H. Fujita, Q.M. Xiao, “Related families- based attribute reduction of dynamic covering decision information systems”, Knowledge-Based Systems, Volume 162, 15 December, pp. 161-173, 2018. [38] G. Q. Wang, “Valid Incremental Attribute Reduction Algorithm Based on Attribute Generalization for an Incomplete Information System”, Chinese Journal of Electronics, Vol.28, No.4, 2019. [39] Guyon, Isabelle; Elisseeff, André, “An Introduction to Variable and Feature Selection”, Journal of Machine Learning Research, pp. 1157- 1182, 2003. [40] H. Liu, L. Yu, “Toward integrating feature selection algorithms for classification and clustering”, IEEE Transactions on knowledge and data engineering, 17(4), pp. 491-502, 2005. [41] H.M. Chen, T.R. Li, S.J. Qiao, D. Ruan, “A rough set based dynamic maintenance approach for approximations in coarsening and refining attribute values”, Int. J. Intell. Syst. 25, pp. 1005-1026, 2010. [42] H.M. Chen, T.R. Li, R. Da, “Maintenance of approximations in incomplete ordered decision systems while attribute values coarsening or refining”, Knowl.-Based Syst. 31, pp. 140-161, 2012. [43] H.M. Chen, T.R. Li, R. Da, et al., “A rough-set-based incremental approach for updating approximations under dynamic maintenance environments”, IEEE Trans. Knowl. Data Eng. 25, pp. 274-284, 2013. [44] H. M. Chen, T. R. Li, D. Ruan, J. H. Lin and C. X. Hu, “A rough-set based incremental approach for updating approximations under dynamic maintenance environments”, IEEE Transactions on Knowledge and Data Engineering. 25 (2), 274 - 284, 2013. [45] H.S. Zou, C.S. Zhang, “Efficient Algorithm for Knowledge Reduction in Incomplete Information System”, Journal of Computational Information Systems 8: 6, pp. 2531–2538, 2012. [46] Huyen Tran, Thinh Cao, Koichi Yamada, Do Van Nguyen, “Incremental Updating Methods with Three-way Decision Models in Incomplete 116 Information Systems”, IEEE Joint 10th International Conference on Soft Computing and Intelligent Systems, pp. 27-32, 2018. [47] H.X. Li, X.H. Zhou, M.M. Zhu, “A Heuristic Reduction Algorithm in IIS Based on Binary Matrix”, RSKT, pp. 143-150, 2010. [48] H. Zhao, K.Y. Qin, “Mixed feature selection in incomplete decision table” Knowledge-Based Systems, Volume 57, pp. 181-190, 2014. [49] J.C. Xu, L. Sun, “Knowledge Entropy and Feature Selection in Incomplete Decision Systems,” Applied Mathematics & Information Sciences, vol. 7, no. 2, pp. 829-837, 2013. [50] J.H. Dai, W.T. Wang, H.W. Tian, L. Liu, “Attribute selection based on a new conditional entropy for incomplete decision systems”, Knowledge- Based Systems, Volume 39, pp. 207-213, 2013. [51] J. Hu, K. Wang, H. Yu, “Attribute Reduction on Distributed Incomplete Decision Information System”, IJCRS 2017, pp 289-305, 2017. [52] J. Qian, C.Y. Dang, X.D. Yue, N. Zhang, “Attribute reduction for sequential three-way decisions under dynamic granulation”, International Journal of Approximate Reasoning 85(2017) 196-216. [53] J. Xie, X.F. Shen, H.F. Liu, X.Y. Xu, “Research on an Incremental Attribute Reduction Based on Relative Positive Region”, Journal of Computational Information Systems 9:16, pp. 6621-6628, 2013. [54] J.Y. Liang, R. Li, Y. H. Qian, “Distance: A more comprehensible perspective for measures in rough set theory”, Knowledge-Based Systems, Volume 27, pp. 126-136, 2012. [55] J.Y. Liang, F. Wang, C.Y. Dang, Y.H. Qian, “A group incremental approach to feature selection applying rough set technique”, IEEE Transactions on Knowledge and Data Engineering, 26(2), pp. 294-308, 2014. [56] J. Yu, L. Sang, H. Dong, “Based on Attribute Order for Dynamic Attribute Reduction in the Incomplete Information System”, IEEE IMCEC 2018, pp. 2475-2478, 2018. 117 [57] J. Zhou, E. Xu, Y.H. Li, Z. Wang, Z.X. Liu, X.Y. Bai , “A New Attribute Reduction Algorithm Dealing With The Incomplete Information System”, 2009 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, 2009. [58] J. Zhang, T. Li, D. Ruan, “Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems”, Int. J. Approx. Reason, Vol.53, pp. 620-635, 2012. [59] L.H Guan, “An incremental updating algorithm of attribute reduction set in decision tables”, FSKD'09 Proceedings of the 6th international conference on Fuzzy systems and knowledge discovery, Vol 2, pp. 421- 425, 2009. [60] L.N. Wang , X. Yang , Y. Chen , L. Liu , S.Y. An , P. Zhuo , “Dynamic composite decision-theoretic rough set under the change of attributes”, Int. J. Comput. Intell.Syst. 11 (2018) 355–370 . [61] Long Giang Nguyen, “Metric Based Attribute Reduction in Decision Tables”, Federated Conference on Computer Science and Information System (FEDCSIS), Wroclaw, Poland, IEEE, pp. 311-316, 2012. [62] Long Giang Nguyen, Hung Son Nguyen, “Metric Based Attribute Reduction in Incomplete Decision Tables”, Proceedings of 14th International Conference, Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, RSFDGrC 2013, Halifax, NS, Canada, Lecture Notes in Computer Science, SpingerLink, Vol. 8170, pp. 99-110, 2013. [63] Long Giang Nguyen, Thien Nguyen, Nhu Son Nguyen , “Fuzzy Partition Distance based Attribute Reduction in Decision Tables”, IJCRS 2018: International Joint Conference on Rough Sets 2018, LNCS, Vol. 11103, Springer Link, 2018, pp. 614-627. [64] L. Sun, J.C. Xu, Y. Tian, “Feature selection using rough entropy-based uncertainty measures in incomplete decision systems”, Knowledge-Based Systems, Volume 36, pp. 206-216, 2012. [65] M.J. Cai, Q.G. Li, J.M. Ma, “Knowledge reduction of dynamic covering decision information systems caused by variations of attribute values”, 118 International Journal of Machine Learning and Cybernetics 8(4), pp. 1131-1144, 2017. [66] M.J. Cai, G.M. Lang, H. Fujita, Z.Y. Li, T. Yang, Incremental approaches to updating reducts under dynamic covering granularity, Knowledge-Based Systems, 2019. [67] M. Kryszkiewicz (1998), “Rough set approach to incomplete information systems”, Information Science, Vol. 112, pp. 39-49. [68] M.S. Raza,U. Qamar, “An incremental dependency calculation technique for feature selection using rough sets”, Information Sciences 343–344, pp. 41–65, 2016. [69] Nguyen Long Giang, Vu Van Dinh, Relationships Among the Concepts of Reduct in Incomplete Decision Tables, Frontiers in Artificial Intelligence and Applications (FAIA), Volume 252: Advanced Methods and Technologies for Agent and Multi-Agent Systems, IOS Press, 2013, pp. 417-426. [70] Nguyen Thi Lan Huong, Nguyen Long Giang, “Incremental algorithms based on metric for finding reduct in dynamic decision tables”, Journal on Research and Development on Information & Communications Technology, Vol.E-3, No.9 (13), pp. 26-39, 2016. [71] R.P. Li, D.D. Zhang, Y.S. Zhao, X.T. Tang, “Incremental Core Computing for Incomplete Decision Tables, International Symposium on Computational Intelligence and Design”, IEEE ISCID, pp. 270-273, 2008. [72] Sai Prasad P.S.V.S, Raghavendra Rao Chillarige, Novel Granular Framework for Attribute Reduction in Incomplete Decision Systems, Multi-disciplinary Trends in Artificial In Artificial Intelligence, 2012. [73] S. Li, T. Li, D. Liu, “Incremental updating approximations in dominance-based rough sets approach under the variation of the attribute set”, Knowledge-Based Systems, Vol.40, pp. 17-26, 2013. [74] S. Li, T. Li, “Incremental update of approximations in dominance-based rough sets approach under the variation of attribute values”, Inf. Sci. 294, pp.348-361, 2015. 119 [75] S. Wang , T. Li , C. Luo , H. Fujita , Efficient updating rough approximations with multi-dimensional variation of ordered data, Inf. Sci. 372, pp. 690-708, 2016. [76] T.R. Li, D. Ruan, W. Geert, J. Song, Y. Xu, A rough sets based characteristic relation approach for dynamic attribute generalization in data mining, Knowl.-Based Syst. 20, pp. 485-494, 2007. [77] Vu Van Dinh, Nguyen Long Giang, Duc Thi Vu, Generalized Discernibility Function based Attribute Reduction in Incomplete Decision Systems, Serdica Journal of Computing 7 (2013), Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, No 4, 2013, pp. 375-388. [78] Vu Van Dinh, Vu Duc Thi, Ngo Quoc Tao, Nguyen Long Giang, “Partition Distance Based Attribute Reduction in Incomplete Decision Tables”, Journal on Information Communications Technology, Research and Development on Information & Communications Technology, Vol. V-2, No. 14(34), pp. 23-32, 12-2015. [79] W.B. Qian, W.H. Shu, “Mutual information criterion for feature selection from incomplete data”, Neurocomputing, Volume 168, pp. 210- 220, 2015. [80] W.D. Tan, E. Xu, F. Shi, Y.C. Ren, L.J. Fan, “A Novel Method of Attribute Reduction for Incomplete Information System”, IEEE International Conference on Innovative Computing and Communication, pp. 352-354, 2010. [81] W.H. Shu, H. Shen, “Incremental Attribute Reduction in Incomplete Decision systems”, IEEE Fifth International Symposium on Parallel Architectures, Algorithms and Programming, pp. 250-254, 2012. [82] W.H. Shu, H. Shen, “A rough-set based incremental approach for updating attribute reduction under dynamic incomplete decision systems”, IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), pp. 1-7, 2013. 120 [83] W.H. Shu, H. Shen, “Updating attribute reduction in incomplete decision systems with the variation of attribute set”, International Journal of Approximate Reasoning, vol. 55, no.3, pp. 867-884, 2014. [84] W.H. Shu, H. Shen, “Incremental feature selection based on rough set in dynamic incomplete data”, Pattern Recognition 47, pp.3890-3906, 2014. [85] W.H. Shu, W.B. Qian, “A fast approach to attribute reduction from perspective of attribute measures in incomplete decision systems”, Knowledge-Based Systems, V.72, pp. 60-71, 2014. [86] W.H. Shu, W.B. Qian, “An incremental approach to attribute reduction from dynamic incomplete decision systems in rough set theory”, Data & Knowledge Engineering 100, pp. 116-132, 2015. [87] W.H. Shua, W.B. Qian, Y.H. Xie, “Incremental approaches for feature selection from dynamic data with the variation of multiple objects”, Knowledge-Based Systems, Volume 163, pp. 320-331, 2019. [88] W.J. Liu, “An incremental approach to obtaining attribute reduction for dynamic decision systems”, Open Math 2016, 14, pp. 875–888, 2016. [89] W. Wei, P. Song, J.Y. Liang, X.Y. Wu, “Accelerating incremental attribute reduction algorithm by compacting a decision table”, International Journal of Machine Learning and Cybernetics, Springer, 2018. [90] W. Wei, X.Y. Wu, J.Y. Liang, J.B. Cui, Y.J. Sun, “Discernibility matrix based incremental attribute reduction for dynamic data”, Knowledge- Based Systems, Volume 140, pp. 142-157, 15 January 2018. [91] X. Guo, Y.Z. Xiang, L. Shu, “An Information Quantity-Based Uncertainty Measure to Incomplete Numerical Systems”, International Conference on Fuzzy Information & Engineering, pp. 23-29, 2019. [92] X.J. Xie, X. L. Qin, “A novel incremental attribute reduction approach for dynamic incomplete decision systems”, International Journal of Approximate Reasoning 93, pp. 443-462, 2018. [93] X.P. Dai, D.H. Xiong, “Research on Heuristic Knowledge Reduction Algorithm for Incomplete Decision Table”, IEEE 121 2010 International Conference on Internet Technology and Applications, pp. 1-3, 2010. [94] Xu E, Y.Q. Yang, Y.C. Ren, “A New Method of Attribute Reduction Based On Information Quantity in An Incomplete System”, JOURNAL OF SOFTWARE, VOL. 7, NO. 8, pp. 1881-1888, 2012. [95] X. Yang, T.R. Li, D. Liu, H.M. Chen, C. Luo, “A unified framework of dynamic three-way probabilistic rough sets”, Information Sciences 420, pp. 126-147, 2017. [96] X. Yang, T.R. Li, H. Fujita, D. Liu, Y.Y. Yao, “A unified model of sequential three-way decisions and multilevel incremental processing”, Knowledge-Based Systems 134, pp. 172-188, 2017. [97] Y. Cheng, “The incremental method for fast computing the rough fuzzy approximations”, Data Knowl. Eng. 70, pp. 84-100, 2011. [98] Y.H. Qian, J.Y. Liang, D.Y. Li, F. Wang, N.N. Ma, “Approximation reduction in inconsistent incomplete decision tables”, Knowledge-Based Systems, Volume 23, Issue 5, pp. 427-433, 2010. [99] Y.H. Qian, J.Y. Liang, W. Pedrycz, C.Y. Dang, “An efficient accelerator for attribute reduction from incomplete data in rough set framework”, Pattern Recognition 44, pp. 1658-1670, 2011. [100] Y. Jing, T. Li, C. Luo, S.J. Horng, G. Wang, Z. Yu, “An incremental approach for attribute reduction based on knowledge granularity”, Knowledge-Based Systems, Vol.104, pp. 24-38, 2016. [101] Y. Jing, T. Li, J. Huang, et al., “An incremental attribute reduction approach based on knowledge granularity under the attribute generalization”, Int. J. Approx. Reason. 76, pp.80-95, 2016. [102] Y. Jing, T. Li, H. Fujita, Z. Yu, B. Wang, An incremental attribute reduction approach based on knowledge granularity with a multi- granulation view, Information Sciences 411, pp. 23-38, 2017. [103] Y. Jing, T. Li, J. Huang, H.M. Chen, S.J. Horng, “A Group Incremental Reduction Algorithm with Varying Data Values”, International Journal of Intelligent Systems 32(9), pp. 900-925, 2017. 122 [104] Y. Jing, T. Li, H. Fujita, B.L. Wang, N. Cheng, “An incremental attribute reduction method for dynamic data mining”, Information Sciences 465, pp. 202-218, 2018. [105] Y. Li, Y.F. Jin, X.D. Sun, “Incremental method of updating approximations in DRSA under variations of multiple objects”, Int. J. Mach. Learn. & Cyber, 2015. [106] Y.M. Liu, S.Y. Zhao, H. Chen, C.P. Li, Y.M. Lu, “Fuzzy Rough Incremental Attribute Reduction Applying Dependency Measures”, APWeb-WAIM 2017: Web and Big Data, pp 484-492, 2017. [107] Y. Tao, H.C. Zhao, “Entropy based attribute reduction approach for incomplete decision table”, 20th International Conference on Information Fusion (Fusion), pp. 1-8, 2017. [108] Y.Y. Huang, T.R. Li, C. Luo, H. Fujita, S.J. Horng, “Dynamic variable precision rough set approach for probabilistic set-valued information systems”, Knowledge-Based Systems 122, pp. 131-147,2017. [109] Y.Y. Huang , T.R. Li , C. Luo , H. Fujita , S.J. Horng , Matrix-based dynamic updating rough fuzzy approximations for data mining, Knowl. Based Syst. 119, pp. 273-283, 2017. [110] Y.Y. Yang, D.G. Chen, H. Wang, “Active Sample Selection Based Incremental Algorithm for Attribute Reduction With Rough Sets”, IEEE Transactions on Fuzzy Systems, 25(4), pp. 825–838, 2017. [111] Y.Y. Yang, D.G. Chen, H. Wang, Eric C.C.Tsang, D.L. Zhang, “Fuzzy rough set based incremental attribute reduction from dynamic data with sample arriving”, Fuzzy Sets and Systems, Volume 312, 1, Pages 66-86, April 2017. [112] Y.Y. Yang, D.G. Chen, H. Wang, X.H. Wang, “Incremental perspective for feature selection based on fuzzy rough sets”, IEEE TRANSACTIONS ON FUZZY SYSTEMS, TFS-2016-0916, 27 June 2017. [113] Z. Pawlak, Rough sets: Theoretical Aspects of Reasoning about Data, Kluwer Academic Publisher, London, 1991. 123 [114] Z.Q. Meng, Z.Z. Shi, “A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets”, Information Sciences, Vol. 179, pp. 2774-2793, 2009. [115] Z.Q. Meng, Z.Z. Shi, “Extended rough set-based attribute reduction in inconsistent incomplete decision systems”, Information Sciences, Volume 204, pp. 44-69, 2012. [116] Z.Y. Xu, B. Yang, W.H. Shu, "Efficient Algorithm for Attribute Reduction of Incomplete Information Systems Based on Assignment Matrix”, Fuzzy Information and Engineering, Volume 2, 2009. [117] Z.Y. Xu, J.H. Zhou, C.G. Zhang, “A Quick Attribute Reduction Algorithm Based on Incomplete Decision Table”, Information Computing and Applications, 2013. [118] The UCI machine learning repository.