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

Chia sẻ: Thi Thi | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

60
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

Nghiên cứu khoa học công nghệ 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ạ: a : U  Va với Va 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: Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 53 Kỹ thuật điện tử & Khoa học máy tính   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à u P , khi đó u P  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 BX  u  U u B  X  và BX  u  U u B  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 POSC ( D)    CD  Di U / D i là C-miền dương của D. Dễ thấy POSC ( 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 POSC ( 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ạ d : U  U   0,   thỏa mãn các điều kiện sau với mọi x, y, z  U [3] P 1 d  x, y   0 , d  x, y   0 khi và chỉ khi x  y . P  2  d  x, y   d  y , x  . P  3  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 U / P  {P1 , P2 ,...., Pm }, U / Q  {Q1 , Q2 ,..., Qn } . Entropy Liang có điều kiện của Q khi đã biết P được định nghĩa bởi 54 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.” Nghiên cứu khoa học công nghệ c c n m Qi  Pj Qi  Pj E (Q P )   với Qic  U  Qi , Pjc  U  Pj . i 1 j 1 U U Mệnh đề 1. [2] Cho bảng quyết định DS  U , C  D  với P, Q  C . Giả sử K  P   U / P  {P1 , P2 ,..., Pm } và K  Q   U / Q  {Q1 , Q2 ,..., Qn } . 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 K  B  U / B  {X1, X2 ,...Xm} và K  D   U / D  {Y1 , Y2 ,..., Yn } . Khi đó: n m 1 d  K  B  , K  B  D   2  Y  X i j X j  Yi U i 1 j 1 Chứng minh. Với u  U ta có u B  D  u B  u D , do đó các phần tử của phân hoạch U / B  D sẽ là Yi  X j khác rỗng với i  1,..., n và j  1,..., m . Từ đó ta có: E BBD  m n  Xj Yi Xj  Yi Xj   Xj Yi Xj   m n Yi Xj Yi Xj  Yi Xj  j1 i1 U U  j1 i1 U U 0 n m Y  X   C i j j X j  Yi  X j  1 n m E  B  D B    2  Y  X i j X j  Yi . i 1 j 1 U U U i 1 j 1 n m 1  Do đó: d K  B  , K  B  D    2  Y  X i j X j  Yi . U i 1 j 1 Đị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 K  B   U / B  { X 1 , X 2 ,... X m } và K  D   U / D  {Y1 , Y2 ,..., Yn } . Khoảng cách giữa K  B  và K  B  D  là dU  K  B  , K  B  D   . Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 55 Kỹ thuật điện tử & Khoa học máy tính Mệnh đề 3. Giả sử đối tượng x được bổ sung vào U , khi đó ta có: 1) Nếu x  X j với mọi j  1..m và x  Yi với mọi i  1..n thì 2 U dU x  K  B  , K  B  D    2 dU  K  B  , K  B  D   U 1 2) Nếu x  X j với mọi j  1..m và x  Yq với q  n thì 2 U dU x  K  B  , K  B  D    2 dU  K  B  , K  B  D   U 1 3) Nếu x  X p với p  m và x  Yi với mọi i  1..n thì 1 dU x  K  B , K  B  D   U 1 U 2 2 dU  K  B , K  B  D   2 X p  4) Nếu x  X p với p  m và x  Yq với q  n thì 1 dUx  K  B , K  B  D   U 1 U 2 2 dU  K  B , K  B  D   2 X p Yq  Chứng minh n1 m1 1  1) Giả sử Xm1   x , Yn1  x . Ta có dU x K B , K BD   Y X 2 i j Xj Yi U1 i1 j1 1  n m m1 n   2   U  1  i 1 j 1 Yi  X j X j  Yi   Yn 1  X j X j  Yn 1   Yi  X m 1 X m 1  Yi  j 1 i 1  2 U  2 dU  K  B  , K  B  D   U 1 2) Giả sử X m 1   x và x  Yq với q  n . Ta có: 1  n m1 m1  dU x  K  B , K  B D   2  i Y  X j X j  Yi   Yq x  X j X j Yq x  U 1  i1,iq j1 j 1  1  n m m  2    i   Y  X j X j  Yi  Yq  X j X j  Yq  U  1  i1,i q j 1 j 1  2 1  n m  U 2 U   2   Yi  X j X j  Yi  d K  B  , K  B  D  U  1  i 1 j 1  U 1 3) Giả sử x  X p với p  m và Yn 1   x . Ta có: 1  n1 m n1  dUx  K  B , K  B D   2    Yi  X j X j Yi   Yi  X p  x   X p  x  Yi  U 1  i1 j1, j p i 1  1  n m n   2    Yi  X j X j  Yi   Yi   X p  x   X p  x   Yi  X p  x  U 1  i1 j1, j p i 1  56 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.” Nghiên cứu khoa học công nghệ 1 n m n  1  2  i U 1  i1 j1 Y X j X j Yi Yi Xp  x  Xp  x    i1  U 1 2 2 U dU  K B , K BD  2 Xp   4) Giả sử x  X p với p  m và x  Yq với q  n . Ta có: dU x K  B  , K  B  D     n m m 1 1  U 1 2   i 1,i  q j 1, j  p Yi  X j X j  Yi  U 1 2  Y x  X j 1, j  p q j X j  Yq  x n 1 1  2 Y x  X x  X x Y x  q p p q 2  Y  X x  X x Y i p p i U 1 U 1 i1,iq n m n 1 1 1  U 1 2  Y  X i 1 j 1 i j X j  Yi  U 1 2  x X p  Yq   U 1 2   Y  X x  i 1,i  q i p 1  U 1 2 U 2 deU  K  B  , K  B  D    X p  Yq  U  Yq   X p  1  U 1 2 U 2 dU  K  B  , K  B  D    2 X p  Yq . 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  x  X p với p  m và  x  Yq với q  n thì 2 U dU  x  K  B  , K  B  D    2 dU  K  B  , K  B  D   U 1 2) Nếu  x  X p với p  m và x  Yq với q  n thì 2 U dU  x  K  B  , K  B  D    2 dU  K  B  , K  B  D   U 1 3) Nếu x  X p với p  m và  x  Yq với q  n thì 1 dU x  K  B  , K  B  D    U 1 2 U 2 dU  K  B  , K  B  D    2 X p  2  4) Nếu x  X p với p  m và x  Yq với q  n thì 1 dU x  K  B , K  B  D   U 1 U 2 2 dU  K  B , K  B  D   X p Yq  X p  Yq  X p  Chứng minh 1) Giả sử X m   x và Yn   x . Ta có n 1 m 1 1 dU x  K  B  , K  B  D    2  Y  X i j X j  Yi U 1 i 1 j 1 Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 57 Kỹ thuật điện tử & Khoa học máy tính 1  n m m 1 n  2   i    Y  X j X j  Yi  Yn  X j X j  Yn  Yi  X m X m  Yi  U  1  i 1 j 1 j 1 i 1  2 U  2 dU  K  B  , K  B  D   U 1 2) Giả sử X m   x và x  Yq với q  n . Ta có:  n m1 1 m1  dUx  K  B , K  B  D   2  i U 1  i1,iq j1 Y  X j X j  Yi    Yq x  X j X j  Yq x  j1  1  n m m  1  n m  2   i  Y  X j X j  Yi   Yq  X j X j  Yq   2   i Y  X j X j  Yi  U 1  i1,iq j1 j1  U 1  i1 j1  2 U  2 dU  K  B  , K  B  D   U 1 3) Giả sử x  X p với p  m và Yn   x . Ta có:  n1 m 1 n1  dUx  K  B , K  B  D   2   i Y  X j X j  Yi   Yi  X p x  X p x Yi  U 1  i1 j1, jp i1  1  n m n n   2   Yi  X j X j  Yi   Yi  X p X p  Y i   Yi   X p  x  X p  x  Yi  U 1  i1 j1 i 1 i 1  n m n1 n1 1    2   i U 1  i1 j1 Y  X j X j Yi  Yi  Xp X p Yi  Yn  X p Xp Yn  Yi  Xp Xp Yi 1    i1 i1  1  n m  1  2   i U 1  i1 j1 Y  X j X j Yi  2 X p  2   U 1 2 2  U dU  K  B , K  B  D   2 X p  2  4) Giả sử x  X p với p  m và x  Yq với q  n . Ta có: dUx K  B , K  B  D    n m m 1 1  U 1 2   i 1,i  q j 1, j  p Yi  X j X j  Yi  U 1 2  Y  x  X j 1, j  p q j X j  Yq  x n 1 1  U 1 2 Yq x  Xp x  Xp x Yq x  U 1 2  Y  X x  X x Y i p p i i1,iq n m m 1 1  U 1 2   i 1,i  q j 1, j  p Yi  X j X j  Yi  U 1 2  j 1, j  p Yq  X j X j  Yq n 1 1  U 1 2  Yq  X p 1 X p Yq   U 1 2  Y X  X i 1,i q i p p  Yi 1  1  U 1 2 U 2 dU  K  B  , K  B  D    X p  Yq  X p  Yq  X p  58 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.” Nghiên cứu khoa học công nghệ 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 K  B   U / B  { X 1 , X 2 ,... X m } , K  C   U / C  {Y1 , Y2 ,..., Yn } .    1) Nếu x  X j với mọi j  1..m thì dUx K  B , K  B D  dUx K  C , K  C  D  2) Nếu x  X p với p  m và x  Yi với mọi i  1..n thì dU x  K  B  , K  B  D    dU x  K  C  , K  C  D   3) Nếu x  X p với p  m và x  Yq với q  n thì dU x  K  B  , K  B  D    dU x  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ó: 1 dUx  K B ,K BD   U1  U d  K B ,K BD 2 X D  với D U / D , xX ,xD 2 2 U p r r p r 1 dUx  K C , K CD   U1  U d  KC ,KCD 2Y D  với x  Y , x  D 2 2 U q r q r    Do B là tập rút gọn của DS nên dU K  B , K  B  D  dU K  C , K  C  D , theo định      nghĩa ta có E D B  E D C . Do B  C nên Yq  X p . Nếu Yq  X p thì rõ ràng ta có điều phải chứng minh. Nếu Yq  X p thì giả sử Yq  X p  X k . Từ E D B  E D C     theo [6] ta có X p  Dr , X k  Dr hay X p  Dr , Yq  Dr , do đó Xp Dr  và Yq  Dr . Từ đó kết luận dUx  K B , K BD   dUx  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 dU  K  B  , K  B  D   , dU  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 RU trên U và đối tượng mới x. Đầu ra: Tập rút gọn RU x trên U  x . 1. Đặt R  RU , tính U / R  { X 1 , X 2 ,... X m } ; 2. If x  X p , X p  U / R then 3. Begin 4. Tính U / C  {Y1 , Y2 ,..., Yn } ; Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 59 Kỹ thuật điện tử & Khoa học máy tính 5. If x  Yq , q  1..n then 6. Begin 7.    While dU x K  R  , K  R  D   dU x K  C  , K  C  D  do  8. Begin 9. For a  C  R tính SIGR  a ; 10. Chọn am  C  R sao cho SIGR  am   Max SIGR  a  ; aC  R   11. R  R  am  ; 12. End; 13. End; 14. End; 15. For a  R do 16. Begin 17.   Tính dU x K R  a , K    R  a  D   ; 18.    K Ra , K  Ra D d    K R , K RD  then R  R  a ; If dU x U x 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à     O C U  m C  U  X p Yq  O C U  X p Yq . Độ phức tạp của vòng lặp While từ dòng lệnh số 7 đến số 12 là O  C  C U  X Y   . Độ phức tạp của vòng lặp For p q từ dòng lệnh số 15 đến 19 là O  C  C U  X Y   . Do đó, độ phức tạp của Thuât toán 1 là p q  2  O C U  C X p Yq . Rõ ràng là X p Yq nhỏ hơn nhiều U 2 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ử K  B   U / B  { X 1 , X 2 ,... X m } , K  C   U / C  {Y1 , Y2 ,..., Yn } . 1) Nếu x  X j với mọi j  1..m thì dU x  K  B  , K  B  D    dU  x  K  C  , K  C  D   2) Nếu x  X p với p  m và x  Yi với mọi i  1..n thì dU x  K  B  , K  B  D    dU x  K  C  , K  C  D   3) Nếu x  X p với p  m và x  Yq với q  n thì 60 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.” Nghiên cứu khoa học công nghệ dU x  K  B  , K  B  D    dU  x  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. Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 61 Kỹ thuật điện tử & Khoa học máy tính 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: nlgiang@ioit.ac.vn. ** Đại học Tài nguyên môi trường Hà Nội. Email: huanvn.tnmt@gmail.com. 62 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.”