Rút gọn thuộc tính trực tiếp trên bảng quyết định theo tiếp cận tập thô mờ

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

Thêm vào BST

Báo xấu

55
lượt xem 1
download

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

Trong bài báo này, đề xuất phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết định có miền giá trị thuộc tính số theo tiếp cận tập thô mờ. Phương pháp đề xuất sử dụng độ phụ thuộc mờ của thuộc tính nên hiệu quả hơn các phương pháp sử dụn

Chủ đề:

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

Lưu

Nội dung Text: Rút gọn thuộc tính trực tiếp trên bảng quyết định theo tiếp cận tập thô mờ

Công nghệ thông tin & Khoa học máy tính RÚT GỌN THUỘC TÍNH TRỰC TIẾP TRÊN BẢNG QUYẾT ĐỊNH THEO TIẾP CẬN TẬP THÔ MỜ Cao Chính Nghĩa1*, Vũ Đức Thi2, Nguyễn Long Giang3 Tóm tắt: Các phương pháp rút gọn thuộc tính theo tiếp cận lý thuyết tập thô thực hiện trên các bảng quyết định có miền giá trị thuộc tính rời rạc. Để thực hiện rút gọn thuộc tính trực tiếp trên các bảng quyết định có miền giá trị thuộc tính số, hướng tiếp cận tập thô mờ được xem là hiệu quả và được các nhà nghiên cứu quan tâm hiện nay. Trong bài báo này, chúng tôi đề xuất phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết định có miền giá trị thuộc tính số theo tiếp cận tập thô mờ. Phương pháp đề xuất sử dụng độ phụ thuộc mờ của thuộc tính nên hiệu quả hơn các phương pháp sử dụng độ đo entropy Shannon. Từ khóa: Tập thô, Tập thô mờ, Bảng quyết định, Quan hệ tương tự mờ, Rút gọn thuộc tính, Tập rút gọn. 1. MỞ ĐẦU Rút gọn thuộc tính là bài toán quan trọng trong bước tiền xử lý số liệu với mục tiêu là loại bỏ các thuộc tính dư thừa nhằm nâng cao tính hiệu quả của các thuật toán khai phá dữ liệu. Đối với các thuộc tính có miền giá trị số, liên tục cần được rời rạc hóa trước khi áp dụng các phương pháp rút gọn theo tiếp cận lý thuyết tập thô. Tuy nhiên, các phương pháp rời rạc hóa không bảo toàn được sự khác nhau ban đầu giữa các giá trị thuộc tính. Để giải quyết bài toán rút gọn thuộc tính trực tiếp trên các bảng quyết định có miền giá trị thuộc tính số không qua bước rời rạc hóa dữ liệu, trong mấy năm gần đây các nhà nghiên cứu quan tâm đến hướng tiếp cận mới sử dụng lý thuyết tập thô mờ. Lý thuyết tập thô mờ (Fuzzy Rough Set) [2,3] là sự kết hợp của lý thuyết tập thô và lý thuyết tập mờ nhằm xấp xỉ các tập mờ (fuzzy set) dựa trên quan hệ tương tự mờ (fuzzy similarity relation). Trong lý thuyết tập thô, hai đối tượng là tương đương trên tập thuộc tính R (độ tương tự là 1) nếu giá trị thuộc tính của chúng bằng nhau trên tất cả các thuộc tính thuộc R. Ngược lại, chúng là không tương đương (độ tương tự là 0). Trong lý thuyết tập thô mờ, quan hệ tương tự mờ thay thế quan hệ tương đương nhằm xác định độ tương tự của hai đối tượng. Độ tương tự là một giá trị nằm trong khoảng [0, 1] cho thấy tính gần nhau, hay tính tương tự, của hai đối tượng. Trong các công trình [1, 9], các tác giả xây dựng ma trận quan hệ mờ dựa trên một quan hệ tương tự mờ được định nghĩa trên miền giá trị thuộc tính. Từ đó, các tác giả xây dựng thuật toán tìm tất cả các tập rút gọn bằng cách mở rộng phương pháp rút gọn thuộc tính dựa trên ma trận phân biệt trong lý thuyết tập thô truyền thống. Trong công trình [5, 7], dựa trên ma trận quan hệ mờ được xây dựng, các tác giả tính toán lượng thông tin tăng thêm (information gain) của entropy Shanon mờ [5] và tính entropy Shannon có điều kiện mờ [7], trên cơ sở đó xây dựng thuật toán heuristic tìm một tập rút tối thiểu nhất dựa trên độ quan trọng của thuộc tính. Nhóm tác giả trong [5, 7] cũng minh chứng bằng thực nghiệm rằng, phương pháp của họ có độ chính xác phân lớp tốt hơn phương pháp rút gọn theo tiếp cận lý thuyết tập thô truyền thống trên một số bộ dữ liệu thử nghiệm. Trong bài báo này, chúng tôi đề xuất thuật toán heuristic tìm một tập rút gọn của bảng quyết định có miền giá trị thuộc tính số sử dụng độ phụ thuộc mờ của thuộc tính trong tập thô mờ. Thuật toán đề xuất tìm một tập rút gọn tối thiểu nhất nhất theo độ quan trọng của thuộc tính, do đó hiệu quả hơn các công bố trong [1, 9]. Kết quả thử nghiệm trên một số bộ dữ liệu cho thấy, thời gian thực hiện của phương pháp đề xuất hiệu quả hơn phương pháp sử dụng độ đo entropy Shannon trong [5]. 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ô và lý thuyết tập thô mờ. Phần 3 trình bày 110 C.C.Nghĩa, V.Đ.Thi, N.L.Giang, “Rút gọn thuộc tính trực tiếp… tiếp cận tập thô mờ.” Nghiên cứu khoa học công nghệ phương pháp rút gọn thuộc tính sử dụng độ phụ thuộc mờ của thuộc tính theo tiếp cận tập thô mờ. Phần 4 trình bày ví dụ minh họa của thuật toán. Phần 5 trình bày kết quả thử nghiệm. Cuối cùng là kết luận và hướng phát triển tiếp theo. 2. CÁC KHÁI NIỆM CƠ BẢN 2.1. Các khái niệm cơ bản trong lý thuyết tập thô Hệ thông tin là một cặp IS  U , A  trong đó U là tập khác rỗng, hữu hạn các đối tượng; A là tập khác rỗng, hữu hạn 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  A . Bảng quyết định là hệ thông tin DS  U , C  D  với C  D   , D được gọi là tập thuộc tính quyết định, C được gọi là tập thuộc tính điều kiện. Cho bảng quyết định DS  U , C  D  , mỗi tập thuộc tính P  C xác định một quan hệ tương đương: 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  . Với X  U , các tập     CX  u U uC  X và CX  u U uC  X   tương ứng gọi là C-xấp xỉ dưới, C- xấp xỉ trên của X. Ta gọi tập POSC ( D)    CX  X U / D 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 của U / D sử dụng tập thuộc tính C. Độ phụ thuộc của tập thuộc tính C vào tập thuộc tính D trong lý POSC  D thuyết tập thô truyền thống, ký hiệu là  C  D  , được định nghĩa: k   C  D  U với S là lực lượng của tập S. Nếu k =1 thì D phụ thuộc hoàn toàn vào C. Nếu 0  k  1 , D phụ thuộc bộ phận vào C. 2.2. Ma trận quan hệ và tập thô mờ Cho U  x1 ,..., xn  là tập hữu hạn, khác rỗng n đối tượng, R là một quan hệ trên U . Ma trận quan hệ của R trên U , ký hiệu là M ( R ) , được xác định như sau [7]  r11 r12 ... r1 n  r r22 ... r2 n  M ( R )   21  ... ... ... ...     rn 1 rn 2 ... rnn    với rij  R xi , x j là giá trị của quan hệ giữa đối tượng xi và x j , rij   0,1 . Một quan hệ R xác định trên U được gọi là quan hệ tương tự mờ (fuzzy similarity relation) nếu thỏa mãn các điều kiện sau đây [7] 1) Tính phản xạ: R  x, x   1, x  U 2) Tính đối xứng: R  x, y   R  y , x  , x, y  U Tạp chí Nghiên cứu KH&CN quân sự, Số 43, 06 - 2016 111 Công nghệ thông tin & Khoa học máy tính 3) Tính bắc cầu Max-min: R  x, z   min  R  x, y  , R  y, z  với mọi x, y , z  U . Quan hệ tương tự mờ R có các tính chất sau đây [7] 1) R1  R 2  R1  x , y   R 2  x , y  2) R  R 1  R 2  R  x , y   m a x R 1  x , y  , R 2  x , y  3) R  R 1  R 2  R  x , y   m in R 1  x , y  , R 2  x , y  4) R 1  R 2  R 1  x , y   R 2  x , y  Quan hệ tương tự mờ R xác định một phân hoạch mờ (fuzzy partition) trên U, ký hiệu n U / R   xi R  , với  xi R là một tập mờ, được gọi là lớp tương đương mờ.  xi R được i 1 biểu diễn dựa trên lý thuyết tập mờ như sau:  x i    ri 1  ri 2  ...  rin  và lực lượng của R  x1 x2 xn  n tập mờ  xi R được tính:  x i   r ij R j 1 Dễ thấy rằng, hàm thuộc của các đối tượng u j  U đối với lớp tương đương mờ ui R     là ui  u j  R ui , u j  rij . R Giả sử F là một tập mờ trên U và R là một quan hệ tương tự mờ, khi đó tập mờ xấp xỉ dưới R  F  và tập mờ xấp xỉ trên R  F  của F là các tập mờ và hàm thuộc của các đối tượng x  U được xác định như sau [2, 3]  R  F   x   inf max 1   R  x , y  ,  F  y   (1) yU  R  F   x   sup m in   R  x , y  ,  F  y   (2) y U Với  x   y   R  x, y  , khi đó tập mờ xấp xỉ dưới R  F  và tập mờ xấp xỉ trên R R  F  được viết lại như sau: y U   R  F   x   inf m ax 1    x  R  y  ,  F  y  (3)  RF   x   sup min     x R  y  ,  F  y  (4) y U   Cặp R  F  , R  F  được gọi là tập thô mờ [2, 3]. Dễ thấy rằng một tập hợp (tập rõ) bất kỳ X  U có thể xem là một tập mờ, hàm thuộc  X  y   1 với y  X và  X  y   0 với y  X . Mô hình tập thô mờ có thể xem là việc sử dụng quan hệ tương tự mờ để xấp xỉ tập mờ (hoặc tập rõ) bằng tập mờ xấp xỉ dưới và tập mờ xấp xỉ trên. Cho bảng quyết định có miền giá trị thuộc tính số DS  U , C  D  với U  u1 ,..., u n  , C  c1 ,..., cm  . Giả sử một quan hệ tương tự mờ R xác định trên miền giá   trị của thuộc tính C. Ta ký hiệu R ck  là quan hệ R xác định trên thuộc tính điều kiện ck  C , k  1..m và R  C  là quan hệ R xác định trên tập thuộc tính điều kiện C. Khi đó, khái niệm miền dương POSC  D  trong lý thuyết tập thô truyền thống được mở rộng thành khái niệm miền dương mờ của tập thuộc tính D đối với tập thuộc tính C dựa trên 112 C.C.Nghĩa, V.Đ.Thi, N.L.Giang, “Rút gọn thuộc tính trực tiếp… tiếp cận tập thô mờ.” Nghiên cứu khoa học công nghệ quan hệ R, ký hiệu là POS RC   D  . POS RC   D  là một tập mờ mà hàm thuộc của các đối tượng x  U được định nghĩa như sau [7]. POS  R C D  x  sup RC  X   x  (5) X U / D Dựa trên khái niệm miền dương mờ, độ phụ thuộc của tập thuộc tính điều kiện C vào tập thuộc tính quyết định D dựa trên quan hệ R được định nghĩa theo tiếp cận tập thô mờ như sau [7].  PO S D  x  xU  PO S D  x  R C   D   R C   R C  (6) U U Cho bảng quyết định có miền giá trị thuộc tính số DS  U , C  D  với P, Q  C và R  P  , R  Q  là quan hệ R trên tập thuộc tính P, Q tương ứng. Khi đó ta có R  P  Q   R  P   R Q  [7], nghĩa là với mọi x, y  U , R  P  Q  x, y   min R  P  x, y  , R Q  x, y  . Giả sử M  R  P     rijR P   và   n n M  R  Q     rijRQ   là ma trận quan hệ của R trên tập thuộc tính P và Q tương ứng, khi n n đó ma trận quan hệ của R trên tập thuộc tính P  Q là: M  R  P  Q     rijR PQ   n n  với rijR PQ   min rijR P  , rijRQ   (7) 3. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH MIỀN GIÁ TRỊ LIÊN TỤC SỬ DỤNG ĐỘ PHỤ THUỘC CỦA THUỘC TÍNH Trong phần này, chúng tôi trình bày phương pháp rút gọn thuộc tính của bảng quyết định có miền giá trị thuộc tính số sử dụng độ phụ thuộc mờ của thuộc tính trong tập thô mờ. Phương pháp đề xuất bao gồm các bước: định nghĩa tập rút gọn dựa trên độ phụ thuộc mờ của thuộc tính trong tập thô mờ, định nghĩa độ quan trọng của thuộc tính trong tập thô mờ và xây dựng thuật toán heuristic tìm tập rút gọn tối thiểu nhất dựa trên tiêu chuẩn độ quan trọng của thuộc tính. Định nghĩa 1. Cho bảng quyết định có miền giá trị thuộc tính số DS  U , C  D  , quan hệ tương tự mờ R và tập thuộc tính P  C . Nếu: 1)  R P  ( D )   RC  ( D ) 2) p  P,  R P  p ( D )   RC  ( D ) thì P là một tập rút gọn nhỏ nhất của C dựa trên độ phụ thuộc mờ của thuộc tính. Định nghĩa 2. Cho bảng quyết định có miền giá trị thuộc tính số DS  U , C  D  và quan hệ tương tự mờ R xác định trên miền giá trị thuộc tính. Với B  C , độ quan trọng của thuộc tính b  C  B đối với tập thuộc tính B dựa trên quan hệ R được định nghĩa: SIGR B   b    R Bb  D    R B   D  (8) Độ quan trọng của thuộc tính được sử dụng làm tiêu chuẩn lựa chọn thuộc tính cho thuật toán heuristic tìm tập rút gọn nhỏ nhất sau đây. Thuật toán F_RSAR (Fuzzy Rough Set based Attribute Reduction) Thuật toán heuristic tìm một tập rút gọn sử dụng độ phụ thuộc mờ của thuộc tính theo tiếp cận tập thô mờ. Tạp chí Nghiên cứu KH&CN quân sự, Số 43, 06 - 2016 113 Công nghệ thông tin & Khoa học máy tính Đầu vào: Bảng quyết định giá trị thuộc tính số DS  U , C  D  , quan hệ tương tự mờ R. Đầu ra: Một tập rút gọn nhỏ nhất P . 1. P   ;  R  D   0 ; 2. Tính ma trận quan hệ M(R(C)); 3. Tính  R C   D  ; // Thêm dần vào P các thuộc tính có độ quan trọng lớn nhất 4. While  R P   D    R C   D  do 5. Begin 6. For c  C  P tính SIG R  P   c    R  P c  D    R  P   D  ; 7. Chọn cm  C  P sao cho SIGR P   cm   Max SIGR P   c  ; cC  P   8. P  P  cm  ; 9. Tính  R P   D  ; 10. End; //Loại bỏ các thuộc tính dư thừa trong P nếu có 11. For each a  P 12. Begin 13. Tính  R  P a  D  ; 14. If  R  P a  D    R  C   D  then P  P  a ; 15. End; 16. Return P; Ví dụ 1. Xét bảng quyết định DS  U , C  d  cho ở Bảng 1 với U  u1 , u2 , u3 , u4 , u5 , u6  , C  c1 , c2 , c3 , c4 , c5 , c6  . Bảng 1. Bảng quyết định mô tả ví dụ 1. c1 c2 c3 c4 c5 c6 d u1 0.8 0.2 0.6 0.4 1 0 No u2 0.8 0.2 0 0.6 0.2 0.8 Yes u3 0.6 0.4 0.8 0.2 0.6 0.4 No u4 0 0.4 0.6 0.4 0 1 Yes u5 0 0.6 0.6 0.4 0 1 Yes u6 0 0.6 0 1 0 1 No   Định nghĩa quan hệ tương tự mờ R ck  ; k  1..6 trên ck  C như sau:  xi  x j xi  x j 1  4 * ,  0 .2 5 R c k  ( u i , u j )   m a x ( c k )  m in ( c k ) m a x ( c k )  m in ( c k ) (9)   0, o th e rw ise 114 C.C.Nghĩa, V.Đ.Thi, N.L.Giang, “Rút gọn thuộc tính trực tiếp… tiếp cận tập thô mờ.” Nghiên cứu khoa học công nghệ   M R C được tính thông qua các ma trận quan hệ tương tự mờ trên các thuộc tính    điều kiện M R ck  ; k  1..6 . Từ đó tính được  R C   d   .  1 0 0 0 0 0   0 1 0 0 0 0 0 0 1 0 0 0  xU  POS d  x  M ( R  C )   ,  R  C   d      RC 1 0 0 0 1 0 0 U 0 0 0 0 1 0  0 0 0 0 0  1   Áp dụng các bước của Thuật toán F_RSAR tìm được tập rút gọn nhỏ nhất P  c4 , c1 . Thuật toán F_RSAR tìm được một tập rút gọn nhỏ nhất dựa trên độ quan trọng của thuộc tính nên hiệu quả hơn các thuật toán tìm tất cả các tập rút gọn theo hướng tiếp cận ma trận phân biệt trong các công trình [1, 9]. Thuật toán F_RSAR sử dụng độ phụ thuộc của thuộc tính để tìm tập rút gọn, do đó có khối lượng tính toán nhỏ hơn các thuật toán theo hướng tiếp cận entropy Shannon trong [5, 7]. Dễ thấy rằng, tập rút gọn thu được của Thuật toán F_RSAR bảo toàn miền dương mờ. 4. THỬ NGHIỆM Chúng tôi chọn thuật toán GAIN_RATIO_AS_FRS (Gọi tắt là thuật toán GRAF) tìm tập rút gọn sử dụng lượng thông tin tăng thêm (gain ratio) theo tiếp cận tập thô mờ trong công trình [5] để so sánh với thuật toán đề xuất F_RSAR về thời gian thực hiện và kết quả thực hiện. Sở dĩ chọn thuật toán GRAF vì đây là thuật toán heuristic tìm một tập rút gọn tối thiểu nhất của bảng quyết định miền giá trị thuộc tính số sử dụng entropy Shannon theo tiếp cận thô mờ. Thuật toán GRAF được trình bày cụ thể trong công trình [5], tóm lược như sau: Thuật toán GRAF (GAIN_RATIO_AS_FRS) Tìm một tập rút gọn tốt nhất của bảng quyết định theo tiếp cận tập thô mờ. Đầu vào: Bảng quyết định giá trị thuộc tính số DS  U , C  D  , P, Q  C , quan hệ tương tự mờ R. Đầu ra: Một tập rút gọn nhỏ nhất P . 1. P  ;  2. For a  C  P , tính độ quan trọng của thuộc tính a, Gain _ Ratio(a, P, D );  3. Chọn thuộc tính a sao cho Gain _ Ratio(a, P, D) đạt giá trị lớn nhất;  4. If Gain _ Ratio(a, P, D)  0 , then P  P  {a} goto 2, else goto 5; 5. P là tập thuộc tính được chọn. Trong đó:  (a, B, D) Gain H (B {a})  H ((B {a})D)  H (B)  H (BD)  Gain _ Ratio(a, B, D)   H ({a}) H ({a}) (10) 1 n [x ] 1 n [ xi ]P  [ xi ]Q Với H ( R)    log i R ; H ( RP RQ )    log n i 1 n n i 1 n Tạp chí Nghiên cứu KH&CN quân sự, Số 43, 06 - 2016 115 Công nghệ thông tin & Khoa học máy tính Thuật toán GRAF[5] có độ phức tạp tính toán hàm đa thức do sử dụng ma trận quan hệ 2 trên các thuộc tính, độ phức tạp tính toán của các ma trận quan hệ là O ( C U ) với C là số lượng thuộc tính điều kiện, U là số lượng phần tử của bộ dữ liệu. Do vậy, độ phức tạp 3 2 tính toán của GRAF và F_RSAR đều là O ( C U ) . Thuật toán GRAF được xây dựng dựa trên việc tính lượng thông tin tăng thêm khi thêm dần các thuộc tính điều kiện vào tập rút gọn, khi nào lượng thông tin không tăng nữa thì kết thúc nên đảm bảo được các điều kiện của định nghĩa 1 để tìm ra một tập rút gọn tối thiểu nhất, loại bỏ được các thuộc tính dư thừa của tập rút gọn. Hơn nữa, theo hiểu biết của tác giả thì đây là công bố tốt nhất cho đến thời điểm năm 2015 về hướng nghiên cứu của bài báo. Để tiến hành thử nghiệm, chúng tôi thực hiện các công việc sau: 1) Cài đặt thuật toán GRAF trong [5] và Thuật toán F_RSAR bằng ngôn ngữ C#. Cả hai thuật toán đều sử dụng quan hệ tương tự mờ xác định bởi công thức (9). 2) Trên máy tính PC với cấu hình Pentium dual core 2.13 GHz CPU, 1GB bộ nhớ RAM, hệ điều hành Windows 7, chạy thử nghiệm hai thuật toán với 5 bộ số liệu lấy từ kho dữ liệu UCI [10]. Với mỗi bộ số liệu, giả sử U là số đối tượng, C là số thuộc tính điều kiện, R là số thuộc tính của tập rút gọn, t là thời gian thực hiện thuật toán (đơn vị là giây s), các thuộc tính điều kiện được đánh số là 1, 2,…, C . Kết quả thực hiện của hai thuật toán được mô tả ở bảng 2 và bảng 3: Bảng 2. Kết quả thực hiện Thuật toán F_RSAR và Thuật toán GRAF[5]. Thuật toán Thuật toán STT Bộ số liệu U C F_RSAR GRAF[5] R t R t 1 Ionosphere 351 34 12 1.02 12 1.04 2 Wpbc 198 33 15 0.67 17 0.68 3 Wine 178 13 6 0.26 6 0.26 4 Glass 214 9 7 0.46 8 0.48 5 Magic04 19020 10 9 6.09 9 6.28 Bảng 3. Tập rút gọn của Thuật toán F_RSAR và Thuật toán GRAF[5]. Tập rút gọn của Tập rút gọn của STT Tập dữ liệu Thuật toán F_RSAR Thuật toán GRAF[5] 1,2,4,5,8,9,10,24,26,27, 1,2,4,5,8,9,10,24,26,27,29 1 Ionosphere 29,33 ,33 1,3,4,5,7,12,13,15,18,2 1,3,4,5,7,12,13,15,17,18,2 2 Wpbc 4,25,26,28,32,33 0,24,25,26,28,32,33 3 Wine 1,3,4,8,9,12 1,3,4,8,9,12 4 Glass 1,2,4,5,6,8,9 1,2,4,5,6,7,8,9 5 Magic04 1,2,3,4,5,7,8,9,10 1,2,3,4,5,7,8,9,10 Kết quả thử nghiệm cho thấy: - Trên các bộ số liệu Ionosphere.data, Wine.data, Magic04.data, tập rút gọn thu được bởi Thuật toán F_RSAR và Thuật toán GRAF là như nhau. Tuy nhiên, với bộ số liệu 116 C.C.Nghĩa, V.Đ.Thi, N.L.Giang, “Rút gọn thuộc tính trực tiếp… tiếp cận tập thô mờ.” Nghiên cứu khoa học công nghệ Wpbc.data, Glass.data, tập rút gọn thu được bởi Thuật toán F_RSAR tối thiểu hơn tập rút gọn thu được bởi Thuật toán GRAF. - Thời gian thực hiện Thuật toán F_RSAR thường nhỏ hơn Thuật toán GRAF, đặc biệt là trên các bộ số liệu lớn thì độ chênh lệch càng nhiều. 5. KẾT LUẬN Mô hình tập thô mờ do D. Dubois và các cộng sự [2, 3] đề xuất là công cụ hiệu quả để giải quyết bài toán rút gọn thuộc tính trực tiếp trên các bảng quyết định có miền giá trị thuộc tính số. Trong bài báo này, chúng tôi đề xuất thuật toán heuristic tìm một tập rút gọn của bảng quyết định có miền giá trị thuộc tính số sử dụng độ phụ thuộc mờ của thuộc tính theo tiếp cận tập thô mờ. Độ phụ thuộc mờ của thuộc tính được xác định dựa trên ma trận quan hệ xác định bởi quan hệ tương tự mờ ở công thức (9). Thực nghiệm trên các bộ số liệu UCI cho thấy, tập rút gọn thu được bởi thuật toán đề xuất F_RSAR có số thuộc tính nhỏ hơn thuật toán GRAF trong [5] trên một số bộ dữ liệu. Do đó, độ hỗ trợ của tập luật trên tập rút gọn của thuật toán F_RSAR cao hơn so với thuật toán GRAF trong [5]. Hơn nữa, thời gian thực hiện thuật toán F_RSAR nhỏ hơn so với thuật toán GRAF trong [5] bởi thuật toán F_RSAR không sử dụng các công thức logarit, đặc biệt là trên một số bộ dữ liệu lớn. Định hướng nghiên cứu tiếp theo là tìm kiếm các độ đo hiệu quả để giải quyết bài toán rút gọn thuộc tính theo tiếp cận tập thô mờ. TÀI LIỆU THAM KHẢO [1]. Chen Degang, Lei Zhang, Suyun Zhao, Qinghua Hu, and Pengfei Zhu, “A Novel Algorithm for Finding Reducts With Fuzzy Rough Sets”, IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. 20, NO. 2, pp. 385 - 389 , 2012. [2]. D. Dubois and H. Prade, “Putting rough sets and fuzzy sets together”, Intelligent Decision Support, Kluwer Academic Publishers,Dordrecht, 1992. [3]. Dubois, D. and Prade, H., “Rough fuzzy sets and fuzzy rough sets”, International Journal of General Systems, 17, pp. 191-209, 1990. [4]. F.F. Xu, D.Q. Miao and L. Wei, “Fuzzy-rough attribute reduction via mutual information with an application to cancer classification”, Computers and Mathematics with Applications 57, pp. 1010 -1017, 2009. [5]. Jianhua Dai and Qing Xu, “Attribute selection based on information gain ratio in fuzzy rough set theory with application to tumor classification”, Applied Soft Computing 13, pp. 211–221, 2013. [6]. Qiang He, Congxin Wu, Degang Chen, Suyun Zhao, “Fuzzy rough set based attribute reduction for information systems with fuzzy decisions”, Knowledge-Based Systems 24 (2011), pp. 689–696, 2011. [7]. Qinghua Hu, Daren Yu, Zongxia Xie, “Information-preserving hybrid data reduction based on fuzzy-rough techniques”, Pattern Recognition Letters 27, 2006, pp. 414-423. [8]. R. Jensen and Q. Shen., “Fuzzy-Rough Sets for Descriptive Dimensionality Reduction”, Proceedings of the 2002 IEEE International Conference on Fuzzy Systems ,FUZZ-IEEE'02, pp. 29-34, 2002. [9]. Zhao Ming, Yan Zhengbo, Zhou Liukun, Wang Huijie and Xu Xiaogang, “The Extraction Method of the Energy Consumption Characteristics Based on Fuzzy Rough Set”, Proceedings of Conference on Computational Intelligence and Bioinformatics (AASRI), pp. 142 – 149, 2012. [10]. The UCI machine learning repository, http://archive.ics.uci.edu/ml/datasets.html Tạp chí Nghiên cứu KH&CN quân sự, Số 43, 06 - 2016 117 Công nghệ thông tin & Khoa học máy tính ABSTRACT FUZZY ROUGH SET BASED ON THE DIRECTLY ATTRIBUTE REDUCTION IN DECISION TABLES Attribute reduction methods based on the approach rough set perform on the decision table with discrete attribute value domain. To perform a attribute reduction directly on the decision table with the numerical attribute value, fuzzy rough set approach is considered effective and researchers are now interested. In this paper, we propose a method attribute reduction directly on the decision table with the numerical attribute value according to fuzzy rough set approach. The proposed method uses degree of dependence between attributes is more efficient than the method of using the Shannon entropy measure. Keywords: Rough set, Fuzzy rough set, Decision table, fuzzy similarity relation, Attribute redection, Reduct. Nhận bài ngày 25 tháng 3 năm 2016 Hoàn thiện ngày 25 tháng 4 năm 2016 Chấp nhận đăng ngày 09 tháng 6 năm 2016 1 Địa chỉ: Học viện Cảnh sát Nhân dân; 2 Đại học Sư phạm kỹ thuật Hưng Yên; 3 Viện Công nghệ thông tin, Viện Hàn lâm Khoa học & Công nghệ Việt Nam. *Email: ccnghia@gmail.com 118 C.C.Nghĩa, V.Đ.Thi, N.L.Giang, “Rút gọn thuộc tính trực tiếp… tiếp cận tập thô mờ.”