Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định thay đổi sử dụng khoảng cách - Nguyễn Long Giang

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 53 Ph­¬ng ph¸p gi¸ t¨ng rót gän thuéc tÝnh trong b¶ng quyÕt ®Þnh thay ®æi sö dông kho¶ng c¸ch NGUYỄN LONG GIANG*, VŨ VĂN HUÂN** Tóm tắt: Trong hai thập kỷ trở lại đây, chủ đề nghiên cứu về rút gọn thuộc tính đã thu hút đông đảo cộng đồng nghiên cứu về tập thô tham gia. Tuy nhiên, hầu hết các phương pháp rút gọn thuộc tính đều thực hiện trên các bảng quyết định cố định, không thay đổi. Sử dụng độ đo khoảng cách, trong bài báo này chúng tôi đề xuất các thuật toán tìm tập rút gọn của bảng quyết định khi bổ sung và loại bỏ đối tượng. Vì không phải thực hiện lại thuật toán trên toàn bộ tập đối tượng nên các thuật toán đề xuất giảm thiểu đáng kể độ phức tạp về thời gian thực hiện. Từ khóa: Tập thô, Bảng quyết định, Rút gọn thuộc tính, Tập rút gọn, Khoảng cách. 1. MỞ ĐẦU Trong lý thuyết tập thô, chủ đề nghiên cứu về rút gọn thuộc tính đã và đang thu hút sự quan tâm của đông đảo các nhà nghiên cứu [1]. Tuy nhiên, phần lớn các nghiên cứu về rút gọn thuộc tính đều được thực hiện trên các bảng quyết định với tập đối tượng và tập thuộc tính cố định, không thay đổi. Trong các bài toán thực tế, các bảng quyết định luôn bị cập nhật và thay đổi với các trường hợp: bổ sung hoặc loại bỏ tập đối tượng, bổ sung hoặc loại bỏ tập thuộc tính, cập nhật tập đối tượng đã tồn tại. Mỗi khi thay đổi như vậy, chúng ta lại phải thực hiện lại các thuật toán tìm tập rút gọn trên toàn bộ tập đối tượng, do đó chi phí về thời gian thực hiện thuật toán tìm tập rút gọn sẽ rất lớn. Trong mấy năm gần đây, một số công trình nghiên cứu đã xây dựng các phương pháp gia tăng rút gọn thuộc tính trên bảng quyết định thay đổi dựa trên các độ đo khác nhau [4,5,8,9]. Trong [4,5,9], các tác giả đã xây dựng phương pháp gia tăng tìm tập rút gọn dựa trên miền dương và ma trận phân biệt khi bổ sung tập đối tượng mới. Trong [8], các tác giả đã xây dựng các công thức tính các độ đo entropy (entropy Shannon, entropy Liang, entropy kết hợp) khi bổ sung, loại bỏ các thuộc tính. Tuy nhiên, các công thức tính toán entropy trong [8] còn phức tạp. Hơn nữa, các công trình trên chưa giải quyết đầy đủ các trường hợp đối với bảng quyết định thay đổi với các trường hợp nêu trên. Sử dụng độ đo khoảng cách trong công trình số [2], trong bài báo này chúng tôi đề xuất hai thuật toán gia tăng tìm tập rút gọn của bảng quyết định trong trường hợp bổ sung và loại bỏ đối tượng. Thuật toán đề xuất sử dụng độ đo khoảng cách nên giảm thiểu đáng kể thời gian thực hiện so với các thuật toán sử dụng entropy Shannon trong [8]. Cấu trúc bài báo như sau. Phần 2 trình bày một số khái niệm cơ bản trong lý thuyết tập thô. Phần 3 trình bày hai thuật toán tìm tập rút gọn sử dụng khoảng cách trong trường hợp bổ sung và loại bỏ đối tượng. Phần 4 là kết luận và định hướng nghiên cứu tiếp theo. 2. CÁC KHÁI NIỆM CƠ BẢN Phần này trình bày một số khái niệm cơ bản trong lý thuyết tập thô do Pawlak [7] đề xuất. Hệ thông tin là một cặp  ,IS U A trong đó U là tập hữu hạn, khác rỗng các đối tượng; A là tập hữu hạn, khác rỗng các thuộc tính. Mỗi thuộc tính a A xác định một ánh xạ: : aa U V với aV là tập giá trị của thuộc tính a. Cho hệ thông tin  ,IS U A , mỗi tập thuộc tính P A xác định một quan hệ tương đương: Kỹ thuật điện tử & Khoa học máy tính N. L. Giang, V. V. Huân, “Phương pháp gia tăng rút gọn sử dụng khoảng cách.” 54         , ,IND P u v U U a P a u a v      . Ký hiệu phân hoạch của U sinh bởi quan hệ  IND P là /U P và lớp tương đương chứa đối tượng u là   P u , khi đó       ,Pu v U u v IND P   . Cho hệ thông tin  ,IS U A . Với B A và X U , các tập   BBX u U u X   và   BBX u U u X     tương ứng gọi là B- xấp xỉ dưới, B-xấp xỉ trên của X. Bảng quyết định là một dạng đặc biệt của hệ thông tin, trong đó tập 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. Như vậy, bảng quyết định là một hệ thông tin  ,DS U C D  trong đó C D  . Với bảng quyết định  ,DS U C D  , ta gọi tập   / ( ) i C i D U D POS D CD    là C-miền dương của D. Dễ thấy ( )CPOS D là tập các đối tượng trong U được phân lớp đúng vào các lớp quyết định của D nếu sử dụng tập thuộc tính điều kiện C. Bảng quyết định DS được gọi là nhất quán khi và chỉ khi ( )CPOS D U , ngược lại DS là không nhất quán. Rút gọn thuộc tính là lựa chọn 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. Trong hai thập kỷ trở lại đây, nhiều phương pháp rút gọn thuộc tính được công bố [1]. Mỗi phương pháp đều đưa ra một khái niệm về tập rút gọn và xây dựng thuật toán heuristic tìm một tập rút gọn tốt nhất dựa trên tiêu chuẩn là chất lượng phân lớp của thuộc tính. Các phương pháp điển hình được trình bày trong [1] là: phương pháp miền dương, phương pháp sử dụng ma trận phân biệt, phương pháp sử dụng đại số quan hệ, phương pháp sử dụng entropy thông tin, phương pháp sử dụng tính toán hạt, phương pháp sử dụng khoảng cách (metric). Các nghiên cứu trong [1] cho thấy hầu hết các phương pháp rút gọn thuộc tính đều thực hiện trên bảng quyết định cố định, không thay đổi. Dựa vào ý tưởng tính toán gia tăng trong các công trình [4,5,9], phần tiếp theo chúng tôi trình bày phương pháp rút gọn trong bảng quyết định thay đổi sử dụng khoảng cách trong hai trường hợp: bổ sung đối tượng và loại bỏ đối tượng. 3. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH THAY ĐỔI SỬ DỤNG KHOẢNG CÁCH 3.1. Khoảng cách giữa hai phân hoạch Một khoảng cách trên tập hợp U là một ánh xạ  : 0,d U U   thỏa mãn các điều kiện sau với mọi , ,x y z U [3]  1P  , 0d x y  ,  , 0d x y  khi và chỉ khi x y .  2P    , ,d x y d y x .  3P      , , ,d x y d y z d x z  . Điều kiện P(3) được gọi là bất đẳng thức tam giác. Trong công trình số [2], tác giả đã xây dựng công thức tính khoảng cách giữa hai phân hoạch dựa trên độ đo entropy Liang [6]. Định nghĩa 1. [6] Cho bảng quyết định  ,DS U C D  với ,P Q C . Giả sử ta có hai phân hoạch 1 2/ {P , ,...., }, mU P P P 1 2/ { , ,..., }nU Q Q Q Q . Entropy Liang có điều kiện của Q khi đã biết P được định nghĩa bởi Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 55 1 1 ( ) c c n m i ji j i j Q PQ P E Q P U U     với ,c ci i j jQ U Q P U P    . Mệnh đề 1. [2] Cho bảng quyết định  ,DS U C D  với ,P Q C . Giả sử   1 2/ { , ,..., }mK P U P P P P  và   1 2/ { , ,..., }nK Q U Q Q Q Q  . Khi đó         ,d K P K Q E P Q E Q P  . là khoảng cách entropy giữa hai phân hoạch  K P và  K Q . Mệnh đề 1 cho thấy công thức tính khoảng cách     ,d K P K Q thỏa mãn điều kiện bất đẳng thức tam giá P(3). Từ mệnh đề 1, chúng tôi xây dựng công thức tính khoảng cách     ,d K B K B D như sau: Mệnh đề 2. Cho bảng quyết định  ,DS U C D  với B C . Giả sử ta có hai phân hoạch   1 2/ { , ,... }mK B U B X X X  và   1 2/ { , ,..., }nK D U D Y Y Y  . Khi đó:      2 1 1 1 , n m i j j i i j d K B K B D Y X X Y U       Chứng minh. Với u U ta có       B D B D u u u    , do đó các phần tử của phân hoạch /U B D sẽ là i jY X khác rỗng với 1,...,i n và 1,...,j m . Từ đó ta có:              1 1 1 1 0 m n m ni j j i jj i j i j i ji j j i j i Y X X Y XX Y X Y X Y XY X E BB D U U U U                       2 1 1 1 1 1n m n mi j j j i j i j j i i j i j Y X C X Y X E B D B Y X X Y U U U              . Do đó:      2 1 1 1 , n m i j j i i j d K B K B D Y X X Y U       . Định nghĩa 2. Cho bảng quyết định  ,DS U C D  và tập thuộc tính R C . Nếu 1)          , ,d K R K R D d K C K C D   2)          , ( , ) ( , )r R d K R r K R r D d K C K C D       thì R là một rút gọn của C dựa trên khoảng cách. Phần tiếp theo, chúng tôi xây dựng công thức tính khoảng cách khi bổ sung và loại bỏ đối tượng. 3.2. Công thức tính khoảng cách khi bổ sung một đối tượng mới Cho bảng quyết định  ,DS U C D  với B C . Giả sử ta có hai phân hoạch   1 2/ { , ,... }mK B U B X X X  và   1 2/ { , ,..., }nK D U D Y Y Y  . Khoảng cách giữa  K B và  K B D là     ,Ud K B K B D . Kỹ thuật điện tử & Khoa học máy tính N. L. Giang, V. V. Huân, “Phương pháp gia tăng rút gọn sử dụng khoảng cách.” 56 Mệnh đề 3. Giả sử đối tượng x được bổ sung vào U , khi đó ta có: 1) Nếu jx X với mọi 1..j m và ix Y với mọi 1..i n thì             2 2 , , 1 UU x U d K B K B D d K B K B D U      2) Nếu jx X với mọi 1..j m và qx Y với q n thì             2 2 , , 1 UU x U d K B K B D d K B K B D U      3) Nếu px X với p m và ix Y với mọi 1..i n thì             22 1 , , 2 1 U pU x d K B K B D U d K B K B D X U       4) Nếu px X với p m và qx Y với q n thì             22 1 , , 2 1 U p qU x d K B K B D U d K B K B D X Y U        Chứng minh 1) Giả sử  1mX x  ,  1nY x  . Ta có        1 1 2 1 1 1 , 1 n m i j j iU x i j d K B K B D Y X X Y U            1 1 1 1 12 1 1 1 1 1 1 n m m n i j j i n j j n i m m i i j j i Y X X Y Y X X Y Y X X Y U                                 2 2 , 1 U U d K B K B D U    2) Giả sử  1mX x  và qx Y với q n . Ta có:              1 1 2 1, 1 1 1 , 1 n m m i j j i q j j qU x i i q j j d K B K B D Y X X Y Y x X X Y x U                         2 1, 1 1 1 1 n m m i j j i q j j q i i q j j Y X X Y Y X X Y U                         2 2 2 1 1 1 , 1 1 n m i j j i U i j U Y X X Y d K B K B D U U              3) Giả sử px X với p m và  1nY x  . Ta có:              1 1 2 1 1, 1 1 , 1 n m n i j j i i p p iU x i j j p i d K B K B D Y X X Y Y X x X x Y U                                 2 1 1, 1 1 1 n m n i j j i i p p i p i j j p i Y X X Y Y X x X x Y X x U                       Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 57          22 2 1 1 1 1 1 , 2 1 1 n m n i j j i i p p U p i j i Y X X Y Y X x X x U d K B K B D X U U                    4) Giả sử px X với p m và qx Y với q n . Ta có:       ,U xd K B K B D        2 2 1, 1, 1, 1 1 1 1 n m m i j j i q j j q i i q j j p j j p Y X X Y Y x X X Y x U U                                    2 2 1, 1 1 1 1 n q p p q i p p i i i q Y x X x X x Y x Y X x X x Y U U                       2 2 2 1 1 1, 1 1 1 1 1 1 n m n i j j i p q i p i j i i q Y X X Y x X Y Y X x U U U                       221 , 1 U p q q pU de K B K B D X Y U Y X U              221 , 2 1 U p qU d K B K B D X Y U      . 3.3. Công thức tính khoảng cách khi loại bỏ một đối tượng Mệnh đề 4. Giả sử đối tượng x U bị loại khỏi U , khi đó ta có: 1) Nếu   px X với p m và   qx Y với q n thì             2 2 , , 1 UU x U d K B K B D d K B K B D U      2) Nếu   px X với p m và qx Y với q n thì             2 2 , , 1 UU x U d K B K B D d K B K B D U      3) Nếu px X với p m và   qx Y với q n thì             221, , 2 2 1 U pU x d K B K B D U d K B K B D X U        4) Nếu px X với p m và qx Y với q n thì             221, , 1 U p q p q pU x d K B K B D U d K B K B D X Y X Y X U           Chứng minh 1) Giả sử  mX x và  nY x . Ta có        1 1 2 1 1 1 , 1 n m i j j iU x i j d K B K B D Y X X Y U            Kỹ thuật điện tử & Khoa học máy tính N. L. Giang, V. V. Huân, “Phương pháp gia tăng rút gọn sử dụng khoảng cách.” 58 1 2 1 1 1 1 1 1 n m m n i j j i n j j n i m m i i j j i Y X X Y Y X X Y Y X X Y U                             2 2 , 1 U U d K B K B D U    2) Giả sử  mX x và qx Y với q n . Ta có:              1 1 2 1, 1 1 1 , 1 n m m i j j i q j j qU x i i q j j d K B K B D Y X X Y Y x X X Y x U                         2 2 1, 1 1 1 1 1 1 1 1 n m m n m i j j i q j j q i j j i i i q j j i j Y X X Y Y X X Y Y X X Y U U                                    2 2 , 1 U U d K B K B D U    3) Giả sử px X với p m và  nY x . Ta có:              1 1 2 1 1, 1 1 , 1 n m n i j j i i p p iU x i j j p i d K B K B D Y X X Y Y X x X x Y U                               2 1 1 1 1 1 1 n m n n i j j i i p p i i p p i i j i i Y X X Y Y X X Y Y X x X x Y U                           1 1 2 1 1 1 1 1 1 1 n m n n i j j i i p p i n p p n i p p i i j i i Y X X Y Y X X Y Y X X Y Y X X Y U                                  22 2 1 1 1 1 2 2 , 2 2 1 1 n m i j j i p U p i j Y X X Y X U d K B K B D X U U                  4) Giả sử px X với p m và qx Y với q n . Ta có:       ,U xd K B K B D        2 2 1, 1, 1, 1 1 1 1 n m m i j j i q j j q i i q j j p j j p Y X X Y Y x X X Y x U U                                    2 2 1, 1 1 1 1 n q p p q i p p i i i q Y x X x X x Y x Y X x X x Y U U                  2 2 1, 1, 1, 1 1 1 1 n m m i j j i q j j q i i q j j p j j p Y X X Y Y X X Y U U                    2 2 1, 1 1 1 1 1 1 n q p p q i p p i i i q Y X X Y Y X X Y U U                   221 , 1 U p q p q pU d K B K B D X Y X Y X U         Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 59 3.4 Thuật toán tìm tập rút gọn khi bổ sung, loại bỏ đối tượng Trước hết, chúng tôi xây dựng thuật toán gia tăng tìm tập rút gọn khi bổ sung một đối tượng mới. Mệnh đề 5 sau đây là cơ sở để xây dựng thuật toán. Mệnh đề 5. Cho bảng quyết định  ,DS U C D  với B C là một tập rút gọn của DS dựa trên khoảng cách và x là đối tượng mới được bổ sung vào U. Giả sử ta có hai phân hoạch   1 2/ { , ,... }mK B U B X X X  ,   1 2/ { , ,..., }nK C U C Y Y Y  . 1) Nếu jx X với mọi 1..j m thì              , ,U x U xd K B K B D d K C K C D    2) Nếu px X với p m và ix Y với mọi 1..i n thì              , ,U x U xd K B K B D d K C K C D    3) Nếu px X với p m và qx Y với q n thì              , ,U x U xd K B K B D d K C K C D    Chứng minh. Mục 1) và 2) được suy ra trực tiếp từ Mệnh đề 3 và Định nghĩa 2. Chúng tôi chứng minh mục 3). Theo Mệnh đề 3 ta có:             221, , 2 1 U p rU x d K B K B D U d K B K B D X D U        với /rD U D , ,p rx X x D              221, , 2 1 U q rU x d K C K C D U d K C K C D Y D U        với ,q rx Y x D  Do B là tập rút gọn của DS nên          , ,U Ud K B K B D d K C K C D   , theo định nghĩa ta có    E D B E D C . Do B C nên q pY X . Nếu q pY X thì rõ ràng ta có điều phải chứng minh. Nếu q pY X thì giả sử q p kY X X  . Từ    E D B E D C theo [6] ta có ,p r k rX D X D  hay ,p r q rX D Y D  , do đó p rX D  và q rY D . Từ đó kết luận              , ,U x U xd K B K B D d K C K C D    . Mệnh đề 5 cho thấy nếu x không thuộc một lớp tương đương nào trong /U B và /U C, hoặc x đồng thời thuộc một lớp tương tương trong /U B và /U C thì các khoảng cách     ,Ud K B K B D ,     ,Ud K C K C D được bảo toàn, nghĩa là không thay đổi tập rút gọn. Từ đó chúng tôi xây dựng thuật toán tính gia tăng tập rút gọn như sau: Thuật toán 1. Thuật toán gia tăng tìm tập rút gọn dựa trên khoảng cách Đầu vào: Bảng quyết định  ,DS U C D  , tập rút gọn UR trên U và đối tượng mới x. Đầu ra: Tập rút gọn  U xR  trên  U x . 1. Đặt UR R , tính 1 2/ { , ,... }mU R X X X ; 2. If , /p px X X U R  then 3. Begin 4. Tính 1 2/ { , ,..., }nU C Y Y Y ; Kỹ thuật điện tử & Khoa học máy tính N. L. Giang, V. V. Huân, “Phương pháp gia tăng rút gọn sử dụng khoảng cách.” 60 5. If qx Y , 1..q n  then 6. Begin 7. While              , ,U x U xd K R K R D d K C K C D    do 8. Begin 9. For a C R  tính  RSIG a ; 10. Chọn ma C R  sao cho     R m R a C R SIG a Max SIG a    ; 11.  mR R a  ; 12. End; 13. End; 14. End; 15. For a R do 16. Begin 17. Tính          ,U xd K R a K R a D    ; 18. If                 , ,U x U xd K R a K R a D d K R K R D      then  R R a  ; 19. End 20. Return R . Theo [9], độ phức tạp để tính phân hoạch /U C là  O C U , do đó độ phức tạp của công thức tính gia tăng khoảng cách trong Mệnh đề 3 là    p q p qO C U m C U X Y O C U X Y     . Độ phức tạp của vòng lặp While từ dòng lệnh số 7 đến số 12 là   p qO C C U X Y . Độ phức tạp của vòng lặp For từ dòng lệnh số 15 đến 19 là   p qO C C U X Y . Do đó, độ phức tạp của Thuât toán 1 là  2 p qO C U C X Y . Rõ ràng là p qX Y nhỏ hơn nhiều 2U nên độ phức tạp của Thuật toán 1 tính gia tăng tập rút gọn nhỏ hơn nhiều thuật toán tính tập rút gọn bằng phương pháp truyền thống [1]. Tương tự trường hợp bổ sung đối tượng mới, cơ sở xây dựng thuật toán tìm tập rút gọn khi xóa một đối tượng là Mệnh đề 6 sau đây. Mệnh đề 6. Cho bảng quyết định  ,DS U C D  với B C là một tập rút gọn của DS dựa trên khoảng cách và x U . Giả sử   1 2/ { , ,... }mK B U B X X X  ,   1 2/ { , ,..., }nK C U C Y Y Y  . 1) Nếu jx X với mọi 1..j m thì              , ,U x U xd K B K B D d K C K C D    2) Nếu px X với p m và ix Y với mọi 1..i n thì              , ,U x U xd K B K B D d K C K C D    3) Nếu px X với p m và qx Y với q n thì Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 61              , ,U x U xd K B K B D d K C K C D    Sử dụng công thức tính khoảng cách khi loại bỏ một đối tượng trong Mệnh đề 4, Mệnh đề 6 được chứng minh tương tự như Mệnh đề 5. Từ Mệnh đề 6, thuật toán tìm tập rút gọn khi xóa một đối tượng được xây dựng tương tự như Thuật toán 1. 5. KẾT LUẬN Trong bối cảnh các hệ cơ sở dữ liệu ngày càng lớn, thay đổi và cập nhật, việc đề xuất các phương pháp hiệu quả nhằm tối ưu thời gian thực hiện các thuật toán tìm tập rút gọn là mục tiêu của các nhà nghiên cứu. Dựa vào ý tưởng tính toán gia tăng, trong bài báo này chúng tôi sử dụng độ đo khoảng cách để xây dựng hai thuật toán tìm tập rút gọn tương ứng với hai trường hợp: bổ sung và loại bỏ đối tượng. Dựa vào hai thuật toán này, chúng tôi hoàn toàn có thể xây dựng được thuật toán mở rộng để giải quyết trường hợp bổ sung tập đối tượng hoặc loại bỏ tập đối tượng. Chúng tôi cũng chứng minh bằng lý thuyết độ phức tạp thời gian của hai thuật toản nhỏ hơn độ phức tạp của thuật toán thực hiện theo phương pháp truyền thống. Định hướng nghiên cứu tiếp theo của chúng tôi là sử dụng độ đo khoảng cách đề xây dựng thuật toán tìm tập rút gọn trong trường hợp cập nhật các đối tượng. TÀI LIỆU THAM KHẢO [1] 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ô”, Luận án Tiến sĩ Toán học, Viện Công nghệ thông tin (2012). [2] Nguyễn Thanh Tùng,“Về một metric trên họ các phân hoạch của một tập hợp hữu hạn”, Tạp chí Tin học và Điều khiển học, T.26, S.1 (2010), tr. 73-85. [3] Deza M. M. and Deza E., “Encyclopedia of Distances”, Springer (2009). [4] Guan L. H, “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 (2009), pp. 421-425. [5] Hu F., Wang G.Y., Huang H., Wu Y., “Incremental attribute reduction based on elementary sets”, Proceedings of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing, Regina, Canada (2005), pp. 185-193. [6] Liang J.Y, Chin K.S., Dang C.Y. and Richard C.M.YAM, “New method for measuring uncertainty and fuzziness in rough set theory”, International Journal of General Systems 31 (2002), pp. 331-342. [7] Pawlak Z., Rough sets: Theoretical Aspects of Reasoning About Data, Kluwer Aca-demic Publishers (1991). [8] Wang F., Liang J. Y, Qian Y. H., “Attribute reduction: A dimension incremental strategy”, Knowledge-Based Systems, Volume 39 (2013), pp. 95–108 [9] Zhang C. S, Jing Ruan J.,Tan Y. H., “An Improved Incremental Updating Algorithm for Core Based on Positive Region, Journal of Computational Information Systems“ 7: 9 (2011), pp. 3127-3133. Kỹ thuật điện tử & Khoa học máy tính N. L. Giang, V. V. Huân, “Phương pháp gia tăng rút gọn sử dụng khoảng cách.” 62 ABSTRACT INCREMENTAL METHODS FOR ATTRIBUTE REDUCTION IN DYNAMIC DECISION TABLES BASED ON DISTANCE. In the last two decades, many attribute reduction methods in decision tables have been developed. However, most of them can only be applicable to static decision tables. In this paper, by using distance measure we propose algorithms for attribute reduction in decision tables in two cases: adding objects, deleting objects. By this approach, we show that the reduct of the dynamically-increasing decision table do not recomputed, so this reduces significantly computational time and memory space. Keywords: Rough set, Decision table, Attribute reduction, Reduct, Distance. Nhận bài ngày 11 tháng 12 năm 2013 Hoàn thiện ngày 04 tháng 02 năm 2014 Chấp nhận đăng ngày 10 tháng 03 năm 2014 Địa chỉ: * Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt nam. Email: [email protected]. ** Đại học Tài nguyên môi trường Hà Nội. Email: [email protected].