Về phương pháp rút gọn thuộc tính trong bảng quyết định với miền trị thuộc tính nhận giá trị số theo tiếp cận tập thô mờ

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

Thêm vào BST

Báo xấu

31
lượt xem 1
download

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

Bài viết trình bày các nội dung chính sau: Rút gọn thuộc tính trong bảng quyết định với miền trị thuộc tính nhận giá trị số, phương pháp rút gọn thuộc tính trong bảng quyết định với miền trị thuộc tính nhận giá trị số theo tiếp cận tập thô mờ.

Chủ đề:

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

Lưu

Nội dung Text: Về phương pháp rút gọn thuộc tính trong bảng quyết định với miền trị thuộc tính nhận giá trị số theo tiếp cận tập thô mờ

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 Về phƣơng pháp rút gọn thuộc tính trong bảng quyết định với miền trị thuộc tính nhận giá trị số theo tiếp cận tập thô mờ Fuzzy Rough Set based Attribute Reduction in Numeric Domain Decision Tables Nguyễn Văn Thiện, Nguyễn Long Giang, Nguyễn Nhƣ Sơn Abstract: Attributes reduction based on rough set tươ g ứ g 39.5 độ v 39.6 độ được rời rạ hó is interesting research area. However, the attributes th h một gi t ị “Nhiệt độ cao”. T ê ảng quyết định reduction algorithms based on rough set is done on mới, h i đối tượng x v y ó gi t ị bằ g h u t ê the discrete domain decision tables (that is applied thuộ t h "Nhiệt độ cơ thể” v khô g ả t được discretization methods). In recent years, some sự kh h u 0.1 độ t ê ảng quyết đị h đầu. researchs on fuzzy rough set based directly attribute D đó, phươ g ph p ời rạ hó dữ liệu khô g ảo reduction in numeric domain decision tables have t “ gữ ghĩ ” ủa dữ liệu gố v ó thể m giảm been studied. This paper proposes fuzzy rough set độ h h x phâ ớp t ê dữ liệu gố . Để giải quyết based directly attribute reduction method in numeric i t út gọn thuộ t h t ực tiếp t ê ảng domain decision tables. The experiment results quyết đị h ó miền trị thuộ t h hậ gi t ị số, iê showed that the fuzzy rough set method has better tục nhằm khắc phụ hượ điểm t ê , t g mấy ăm classification accuracy than rough set theory. gầ đây ô g t ì h ghiê ứu đề xuất hướng tiếp cận mới sử dụ g ý thuyết tập thô mờ Keywords: rough set, fuzzy rough set, decision table, fuzzy similarity relation, attribute reduction, Lý thuyết tập thô mờ (Fuzzy Rough Set) do D. reduct. Du is v ộng sự [4, 5] đề xuất mở ra một hướng ghiê ứu mới về út gọn thuộ t h t ê ảng I. GIỚI THIỆU quyết định mờ v ảng quyết đị h ó miền trị Rút gọn thuộ t h i t u t ọ g trong thuộ t h nhậ gi t ị số, iê tục. Lý thuyết tập thô ước tiền xử ý số liệu với mụ tiêu ại bỏ mờ sự kết hợp củ ý thuyết tập thô [13] v ý thuyết thuộ t h dư thừa nhằm â g t h hiệu quả của tập mờ [11] nhằm xấp xỉ tập mờ dự t ê một thuật t kh i ph dữ liệu. Lý thuyết tập thô [13] quan hệ tươ g tự (simi ity e ti ) đượ x định ô g ụ hiệu quả giải quyết i t út gọn thuộc t ê miề gi t ị thuộ t h. T g ý thuyết tập thô, t h t g ảng quyết đị h v được cộ g đồ g ghiê h i đối tượ g tươ g đươ g t ê tập thuộ t h R, cứu về tập thô thực hiệ âu y. Để thực hiệ h y độ tươ g tự 1, ếu gi t ị thuộ t h ủ hú g phươ g ph p út gọn thuộ t h the tiếp cận tập thô, bằ g h u t ê tất cả thuộ t h t g R. Ngược thuộ t h ó miền gi t ị số, iê tục cầ được rời lại, hú g khô g tươ g đươ g, h y độ tươ g tự 0. rạ hó . Tuy hiê , phươ g ph p ời rạ hó dữ T g ý thuyết tập thô mờ, quan hệ tươ g tự thay thế liệu khô g ả t được sự kh h u đầu giữa quan hệ tươ g đươ g hằm x đị h độ tươ g tự của gi t ị thuộ t h. V dụ, với thuộ t h “Nhiệt độ h i đối tượ g. Độ tươ g tự một gi t ị nằm trong cơ thể”, giả sử h i đối tượng x v y ó hiệt độ ơ thể khoảng [0, 1] cho thấy t h gầ h u, h y t h tươ g - 40 - Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 tự, củ h i đối tượ g. C ghiê ứu iê u đến T g i y, hú g tôi đề xuất thuật t út gọn thuộ t h the tiếp cận tập thô mờ tập trung heu isti út gọn thuộ t h t g ảng quyết đị h ó v h i hướ g h h: hướng thứ nhất sử dụng tập miền trị thuộ t h nhậ gi t ị số sử dụ g độ phụ thô mờ để giải quyết i t út gọn thuộ t h t ê thuộc mờ của thuộ t h t g tập thô mờ. Thuật t ảng quyết định mờ (bảng quyết định với gi t ị đề xuất tìm một tập út gọn tốt nhất the tiêu huẩn thuộ t h tập mờ) t ước khi thực hiệ thuật chất ượng phâ ớp (độ quan trọng của thuộ t h), d t t h ọc hệ luật mờ với ô g ố điể hì h đó hiệu quả hơ ô g ố trong [1, 2, 3, 21, 22, 23, [6, 7, 8, 15, 18, 19, 20, 24]; hướng thứ hai giải quyết 25]. Do sử dụ g độ phụ thuộc mờ củ thuộ t h i t út gọn thuộ t h t ực tiếp t ê ảng ê thuật t đề xuất ó khối ượ g t h t hỏ hơ quyết đị h ó miền trị thuộ t h nhậ gi t ị số, đây thuật t t g [8, 17] sử dụ g ô g thức entropy hướ g ghiê ứu củ i y. Shannon mờ. Kết quả thử nghiệm t ê một số bộ số The hướng tiếp cậ út gọn thuộ t h t ực tiếp liệu cho thấy, phươ g ph p đề xuất ó độ h h x tê ảng quyết đị h ó miền trị thuộ t h nhận phâ ớp tốt hơ s với phươ g ph p sử dụ g độ phụ gi t ị số, t ước hết một quan hệ tươ g tự đượ định thuộc của thuộ t h the tiếp cậ ý thuyết tập thô ghĩ t ê miề gi t ị thuộ t h. Tiếp the , m truyền thố g. Hơ ữ , phươ g ph p đề xuất ó độ trận quan hệ đượ xây dựng. Ma trận quan hệ cho h h x phâ ớp tốt hơ phươ g ph p dự t ê phép x định gi t ị h m thuộc củ đối tượ g đối entropy Shannon mờ trong [8, 17]. Cấu t ú i với mỗi lớp tươ g tự mờ. Từ đó, h m thuộc củ hư s u. Phầ 2 t ì h y một số kh i iệm ơ ản tập xấp xỉ dưới mờ, xấp xỉ t ê mờ, miề dươ g mờ t g ý thuyết tập thô mờ. Phầ 3 t ì h y phươ g đượ t h dự v t tử xấp xỉ t g ý thuyết ph p út gọn thuộ t h sử dụ g độ phụ thuộc mờ của tập thô mờ [4, 5]. T ê ơ sở đó, phươ g ph p út thuộ t h the tiếp cận tập thô mờ. Phần 4 t ì h y gọn thuộ t h đượ xây dựng dự t ê ền tảng mở kết quả thử nghiệm. Cuối ù g kết luậ v hướng rộng phươ g ph p út gọn thuộ t h the tiếp cận ph t t iển tiếp theo tập thô t uyền thố g. Đó g góp u t ọng về hướng II. CÁC KHÁI NIỆM CƠ BẢN ghiê ứu y phải kể đế ô g t ì h [1, 2, 3, 21, 22, 23, 25]. T g ô g t ì h y, t giả xây Phầ y t ì h y một số kh i iệm ơ ả t g dựng ma trận phâ iệt mờ dự t ê m t ận quan hệ ý thuyết tập thô t uyề thố g ủ P w k [13] v ý v đề xuất thuật t tìm tất cả tập út gọn bằng thuyết tập thô mờ d D. Du is v ộ g sự [4, 5] h mở rộ g phươ g ph p út gọn thuộ t h dự t ê đề xuất. ma trậ phâ iệt t g ý thuyết tập thô t uyền thống. Mô hì h tập thô t uyền thố g d P w k [13] đề Tuy hiê , t giả hư ô g ố thuật t xuất dự t ê u hệ tươ g đươ g để xấp xỉ tập hợp. heuristic tìm một tập út gọn tốt nhất dự t ê tiêu Xét ảng quyết định DS  U , C  D  , Mỗi tập thuộc chuẩn chất ượ g phâ ớp h y độ quan trọng của t h PC x định một quan hệ tươ g đươ g thuộ t h. T g ô g t ì h [8, 17], t giả xây dự g phươ g ph p út gọn thuộ t h dự t ê   IND  P    u, v  U U a  P, a u   a  v  . Nếu entropy Shannon. C t giả t g [8, 17] ũ g mi h u, v   IND  P  thì u v v khô g phâ iệt được nhau chứng bằng thực nghiệm rằ g, phươ g ph p út gọn bởi thuộ t h t g P. Ký hiệu lớp tươ g đươ g thuộ t h the tiếp cận tập thô mờ ó độ h h x chứ đối tượng u  u P , khi đó phâ ớp tốt hơ phươ g ph p út gọn theo tiếp cậ ý thuyết tập thô t uyền thống (sau khi rời rạ hó dữ u P  v U u, v   IND  P  . Với X  U , tập liệu) t ê một số bộ dữ liệu thử nghiệm.    CX  u U u C  X v CX  u U u C  X   tươ g  - 41 - Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 ứng gọi C-xấp xỉ dưới, C-xấp xỉ trên của X. Ta gọi với  x  y   R  x, y  , khi đó tập mờ xấp xỉ dưới R tập POSC ( D)   CX  C-miền dương của D. Dễ R  F  v tập mờ xấp xỉ t ê R  F  đượ viết ại hư X U / D thấy POSC ( D) tập đối tượng trong U đượ phâ sau: lớp đú g v ớp của U / D sử dụng tập thuộ t h C. Độ phụ thuộc của tập thuộ t h C v tập thuộ t h D yU  R F   x   inf max 1   x  y  , F  y  R  (3) t g ý thuyết tập thô t uyền thố g, ký hiệu  C  D , yU  R F   x   sup min  x  y  ,  F  y  R  (4) đượ đị h ghĩ hư s u: Cặp  R  F  , R  F   đượ gọi tập thô mờ. Dễ thấy POSC  D  k   C  D  ằ g một tập hợp (tập õ) ất kỳ X  U ó thể xem U một tập mờ, h m thuộ  X  y   1 với y  X v với S ự ượ g ủ tập S. Nếu k =1 thì D phụ thuộ  X  y   0 với y  X . Mô hì h tập thô mờ ó thể xem h t v C. Nếu 0  k  1 , D phụ thuộ ộ phậ việ sử dụ g u hệ tươ g tự để xấp xỉ tập mờ v C. Tiếp the , hú g tôi t ì h y kh i iệm t ê (h ặ tập õ) ằ g tập mờ xấp xỉ dưới v tập mờ xấp t g ý thuyết tập thô mờ t g [4, 5]. xỉ t ê . T g mô hì h tập thô mờ, một u hệ tươ g tự Ch ả g uyết đị h ó miề t ị thuộ t h hậ (similarity relation) đượ sử dụ g th y thế u hệ gi t ị số DS  U , C  D  với U  u1,..., un , tươ g đươ g để xấp xỉ tập mờ. Cho U tập đối tượ g, một u hệ R đượ đị h ghĩ t ê U đượ C  c1,..., cm  . Giả sử một u hệ tươ g tự R ất kỳ gọi u hệ tươ g tự ếu R thỏ mã t h hất: x đị h t ê miề gi t ị ủ thuộ t h điều kiệ t h phả xạ ( ef exive) R  x, x   1 , t h đối xứ g c  C . T ký hiệu ck u hệ R x đị h t ê thuộ (symetric) R  x, y   R  y, x  v t h ắ ầu sup-min t h điều kiệ ck  C, k  1..m . Khi đó, kh i iệm miề (sup-min transitive) R  x, z   min R  x, y  , R  y, z  ) với dươ g POSC  D  t g ý thuyết tập thô t uyề thố g mọi x, y, z U . Qu hệ tươ g tự R x đị h một phâ đượ mở ộ g th h kh i iệm miề dươ g mờ ủ h ạ h mờ t ê U, ký hiệu U / R   x R x U  , trong tập thuộ t h D đối với tập thuộ t h C dự t ê u hệ R, ký hiệu POSC  D  . POSC  D  một tập mờ đó  x R một ớp tươ g đươ g mờ tươ g ứ g với đối m h m thuộ ủ đối tượ g x U đượ đị h ghĩ tượ g x, h m thuộ đượ x đị h ởi ô g thứ như s u [18].  x  y   R  x, y   R  x, y  với mọi y U . POS  x  sup C  X   x  R  D (5) Giả sử F một tập mờ v R một u hệ tươ g C X U / D tự x đị h t ê U, khi đó tập mờ xấp xỉ dưới R  F  v Dự t ê kh i iệm miề dươ g mờ, độ phụ thuộ tập mờ xấp xỉ t ê R  F  ủ F tập mờ v h m ủ tập thuộ t h điều kiệ C v tập thuộ t h uyết đị h D dự t ê u hệ R đượ đị h ghĩ the tiếp thuộ ủ đối tượ g x U đượ x đị h hư s u: ậ tập thô mờ hư s u [18]. R F   x   inf max 1  R  x, y  , F  y   (1) yU POS  D  x   xU POS  D   x   C  D   R F   x   sup min  R  x, y  , F  y   C C (6) (2) U U yU The hướ g tiếp ậ út gọ thuộ t h t ự tiếp tê ả g uyết đị h thuộ t h số, m t ậ u - 42 - Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 hệ x đị h t ê thuộ t h ck m t ậ vuô g ấp n giả t g [8] ũ g xây dự g thuật t heu isti tìm đượ đị h ghĩ hư s u [21] một tập út gọ tốt hất dự t ê ượ g thô g ti tă g thêm mờ. T g ả h i ô g t ì h [8, 17], t giả   M ck  mijck    nn đều hứ g mi h ằ g thự ghiệm ằ g út gọ thuộ t h the tiếp ậ thô mờ ó độ h h x phâ ớp tốt với mijc  ck  ui , u j  , i  1..n, j  1..n . Ở đây, ck  ui , u j  k hơ út gọ thuộ t h the tiếp ậ ý thuyết tập thô gi t ị ủ u hệ giữ hai đối tượ g ui v u j . Khi t uyề thố g. Tuy hiê , hượ điểm ủ h i phươ g đó, m t ậ u hệ mờ x đị h t ê tập thuộ t h ph p y đều sử dụ g ô g thứ e t py Sh điều kiệ C đượ đị h ghĩ [21] để xây dự g đị h ghĩ tập út gọ , d đó thời gi thự hiệ kém hiệu uả d phải t h t iểu   M C  mijC    nn thứ g it. T g i y, hú g tôi sử dụ g độ phụ thuộ mờ ủ thuộ t h th y h độ đ e t py k 1.. m    với mijC  min mijc  min mijc , mijc ,..., mijc k 1 2 m  Sh để đị h ghĩ tập út gọ v xây dự g thuật t heu isti tìm một tập út gọ tốt hất. Vì độ phụ Dễ thấy ằ g, với phầ tử mijC ủ m tậ M C   thuộ mờ ủ thuộ t h khô g phải t h t iểu t ó mijC  C  ui , u j  , i  1..n, j  1..n , với thứ g it ê hiệu uả hơ phươ g ph p dự t ê e t py Sh t g [8, 17]. Chú g tôi ũ g C  ui , u j   C  ui , u j   ui   u j  . Từ m t ậ C M C  hứ g mi h ằ g thự ghiệm ằ g phươ g ph p đề h phép x đị h đượ ớp tươ g đươ g mờ xuất ó độ h h x phâ ớp hơ phươ g m C m C ph p dự t ê e t py Sh t g [8, 17]. ui C   ...  i1 i1 thuộ phâ h ạ h mờ u1 un Tươ g tự phươ g ph p út gọ thuộ t h t g ý U / C  ui C ui U  . Khi đó, h m thuộ ủ tập thuyết tập thô t uyề thố g, phươ g ph p đề xuất mờ xấp xỉ dưới, tập mờ xấp xỉ t ê , miề dươ g mờ ó gồm ướ : đị h ghĩ tập út gọ dự t ê độ phụ thể đượ t h dự v ô g thứ (3), (4), (5) tươ g thuộ mờ ủ thuộ t h, đị h ghĩ độ u t ọ g ủ ứ g v từ đó t h đượ độ phụ thuộ ủ tập thuộ t h thuộ t h đặ t ư g h hất ượ g phâ ớp ủ điều kiệ C v tập thuộ t h uyết đị h D the ô g thuộ t h v xây dự g thuật t heu isti tìm tập út thứ (6). gọ tốt hất dự t ê tiêu huẩ độ u t ọ g ủ thuộ t h. III. RÚT GỌN THUỘC TÍNH TRONG BẢNG Định nghĩa 1. Cho bảng quyết định DS  U ,C  D  ó QUYẾT ĐỊNH VỚI MIỀN TRỊ THUỘC TÍNH miề t ị thuộ t h hậ gi t ị số , một u hệ tươ g tự NHẬN GIÁ TRỊ SỐ R đượ x đị h t ê miề gi t ị ủ thuộ t h. Với Như đã t ì h y ở phầ I, t ê ớp i t út gọ P  C , nếu thuộ t h t ự tiếp t ê ả g uyết đị h với miề t ị 1)  P ( D)   C ( D) thuộ t h hậ gi t ị số the hướ g tiếp ậ heuristic sử dụ g tập thô mờ, t g ô g t ì h [17], t giả 2) p  P,  P p ( D)   C ( D)   đã đị h ghĩ tập út gọ dự t ê e t py Sh mờ v xây dự g thuật t heu isti tìm một tập út thì P một tập út gọ ủ C dự t ê độ phụ thuộ gọ tốt hất dự t ê e t py Sh mờ. T g mờ ủ thuộ t h. ô g t ì h [8], t giả đị h ghĩ tập út gọ dư Từ Đị h ghĩ 1, dễ thấy ằ g tập út gọ dự t ê t ê độ đ ượ g thô g ti tă g thêm mờ (fuzzy độ phụ thuộ mờ ủ thuộ t h tươ g đươ g với tập information gain). Lượ g thô g ti tă g thêm mờ út gọ dự t ê miề dươ g mờ, tập út gọ dự t ê đượ xây dự g dự t ê e t py Sh mờ. C t - 43 - Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 miề dươ g mờ mở ộ g tập út gọ dự t ê miề Ví dụ 1. Xét ả g uyết đị h ó miề gi t ị thuộ dươ g ủ P w k the tiếp ậ ý thuyết tập thô mờ. t h số DS  U , C  d  h ở Bả g 1 với Định nghĩa 2. Cho bảng quyết định DS  U , C  D  ó U  u1 , u2 , u3 , u4 , u5 , u6  , C  c1 , c2 , c3 , c4 , c5 , c6  . miề gi t ị thuộ t h số v u hệ tươ g tự R x đị h Bảng 1. Bảng quyết định mô tả Ví dụ 1 t ê miề gi t ị thuộ t h. Với B  C , độ u t ọ g mờ ủ thuộ t h b  C  B đối với tập thuộ t h B c1 c2 c3 c4 c5 c6 d đượ đị h ghĩ : u1 0.8 0.2 0.6 0.4 1 0 No SIGB  b    Bb  D    B  D  (7) 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 Độ u t ọ g ủ thuộ t h đặ t ư g h hất u4 0 0.4 0.6 0.4 0 1 Yes ượ g phâ ớp ủ thuộ t h điều kiệ v thuộ t h uyết đị h v đượ sử dụ g m tiêu huẩ ự họ u5 0 0.6 0.6 0.4 0 1 Yes thuộ t h h thuật t heu isti tìm tập út gọ s u u6 0 0.6 0 1 0 1 No đây. Giả sử t ê miề gi t ị ủ thuộ t h ck  C , quan Thuật toán F_RSAR (Fuzzy Rough Set based Attribute Reduction). Thuật t heu isti tìm một tập hệ tươ g tự ck đượ đị h ghĩ hư s u [8] út gọ sử dụ g độ phụ thuộ mờ ủ thuộ t h.  ck  ui   ck  u j  ck  ui   ck  u j  1  4 * ,  0.25 (8) Đầu vào: Bả g uyết đị h gi t ị thuộ t h số ck (ui , u j )   max(ck )  min(ck ) max(ck )  min(ck )  DS  U , C  D  , một u hệ tươ g tự R đượ x 0, otherwise đị h t ê miề gi t ị thuộ t h. Với max  ck  , min  ck  tươ g ứ g gi t ị ớ Đầu ra: Một tập út gọ tốt hất P . hất v gi t ị hỏ hất ủ miề gi t ị thuộ t h ck 1. P   ; Áp dụ g ướ ủ Thuật t F_RSAR tìm một 2.    D   0 ; tập út gọ ủ ả g uyết đị h. T ướ hết, t h thuộ t h điều kiệ M  c1  , 3. T h m t ậ u hệ M C ;   m t ậ u hệ t ê 4. T h  C  D  ;       M c2 , M c3 , M c4 , M c5 , M c6 . Từ đó, t h m     5. While  P  D    C  D  do tậ M C :   6. Begin 1 0 0 0 0 0 For c  C  P t h 0 0  7.  1 0 0 0 SIGP  c    Pc  D    P  D  ; 0 0 1 0 0 0 M (C )    8. Chọ cm  C  P sao cho 0 0 0 1 0 0 0 0 SIGP  cm   Max SIGP  c  ; 0 0 0 1 cC  P   0 0 0 0 0 1 9. P  P  cm  ; T ó U / d   u1 , u3 , u6  , u2 , u4 , u5  . Xét 10. T h  P  D ; X  u1 , u3 , u6  , xấp xỉ mờ dưới C  X  tập mờ với 11. End; 12. Return P; h m thuộ ủ x U t h ởi 1 3 6  Cu ,u ,u   x   inf max 1   x  y  , u ,u ,u   y  yU C 1 3 6  - 44 - Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 Từ m t ậ M C t   ó đó thuật t dừ g v P  c1, c4  một tập út gọ tốt hất ủ ả g uyết đị h DS. 1 0 0 0 0 0 u1 C       Thuật t F_RSAR tìm đượ một tập út gọ ủ u1 u2 u3 u4 u5 u6 ả g uyết đị h dự t ê độ u t ọ g ủ thuộ t h D đó C u ,u ,u   u1   inf 1,1,1,1,1,1  1 , tươ g (đặ t ư g h hất ượ g phâ ớp ủ thuộ t h)  1 3 6 ê hiệu uả hơ thuật t tìm tất ả tập út tự t ó Cu ,u ,u   u2   0 , Cu ,u ,u   u3   1 , 1 3 6 1 3 6 gọ the hướ g tiếp ậ m t ậ phâ iệt t g Cu ,u ,u   u4   0 , Cu ,u ,u   u5   0 , 1 3 6 ô g t ì h [1, 2, 3, 21, 22, 23, 25]. Thuật t 1 3 6 F_RSAR sử dụ g độ phụ thuộ ủ thuộ t h để tìm Cu ,u ,u   u6   1 , 1 3 6 Cu ,u ,u   u1   0 , 2 4 5 tập út gọ , d đó ó khối ượ g t h t hỏ hơ thuật t the hướ g tiếp ậ e t py Sh t g Cu ,u ,u   u2   1 , Cu ,u ,u   u3   0 , 2 4 5 2 4 5 [8, 17]. Dễ thấy ằ g, tập út gọ thu đượ ủ Thuật Cu ,u ,u   u4   1 Cu ,u ,u   u5   1 , t F_RSAR ả t miề dươ g mờ. Phầ tiếp the , hú g tôi tiế h h thử ghiệm phươ g ph p đề 2 4 5 2 4 5 Cu ,u ,u   u6   0 . 2 4 5 xuất t ê một số ộ dữ iệu thử ghiệm để m õ h i vấ đề s u: 1) T h hiệu uả ủ hướ g tiếp ậ tập Từ đó, h m thuộ ủ đối tượ g đối với miề thô mờ s với hướ g tiếp ậ tập thô t uyề thố g về dươ g mờ POSC d  : độ h h x phâ ớp s u khi út gọ thuộ t h; 2)  POS d   u1   sup Cu ,u ,u   u1  , Cu ,u ,u   u1   1 , C 1 3 6 2 4 5  T h hiệu uả ủ thuật t đề xuất với thuật t t g ô g t ì h [8] về độ h h x phâ ớp. POS d   u2   1 , POS d   u3   1 , POS d   u4   1 , C C C VI. KẾT QUẢ THỰC NGHIỆM POS d   u5   1 , POS d   u6   1 . Từ đó: Chú g tôi họ 8 ộ dữ iệu mẫu từ ấy từ kh dữ C C  C d   1 iệu UCI [26] ó miề t ị thuộ t h hậ gi t ị số h ở Bả g 2 để tiế h h thử ghiệm. Môi t ườ g thử Áp dụ g ướ ủ Thuật t F_RSAR t ó ghiệm m y t h PC với ấu hì h Pe tium du e c 1 d   0.167 ,  d   0 , c2 c 3 d   0.167 , 2.13 GHz CPU, 1GB ộ hớ RAM, sử dụ g hệ điều h h Wi d ws 7. c d   0.5 ,  d   0.467 , c5 c d   0.467 . 4 6 Bảng 2. Bộ số liệu thử nghiệm Chọ thuộ t h c4 ó độ u tọ g ớ hất v TT Bộ dữ liệu Số thuộc tính Số đối P  c4  . Thự hiệ vò g ặp Whi e. Xét thuộ điều kiện tƣợng 1 Ecoli 7 336 t h c1 t ó: 2 Ionosphere 34 351 3 Wdbc 30 569 SIGc  c1    c ,c d    c d   1  0.5  0.5 . Tươ g tự 4 Wpbc 33 198 4 4 1 4 5 Wine 13 178 SIGc  c2   0.5 , SIGc  c3   0 , SIGc  c5   0.5 , 6 Glass 9 214 4 4 4 SIGc c6   0.5 . Khô g mất t h tổ g u t, họ 7 Magic04 10 19020 4 8 Page-blocks 10 5473 thuộ t h c1 ó độ u tọ g ớ hất v T ướ hết, hú g tôi tiế h h thử ghiệm hằm P  c1, c4 . Khi đó t ó  c ,c 1 4 d   1   d  , do C đ h gi độ h h x phâ ớp t ê ộ số iệu - 45 - Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 mẫu s u khi thự hiệ thuật t F_RSAR v thuật Bảng 3. Kết quả thử nghiệm rút gọn thuộc tính theo tiếp t út gọ thuộ t h sử dụ g độ phụ thuộ ủ cận tập thô và tập thô mờ thuộ t h t g ý thuyết tập thô t uyề thố g (gọi tắt Rút gọn thuộc tính Rút gọn thuộc tính theo thuật t RSAR). Để tiế h h thử ghiệm, hú g theo tiếp cận tập thô tiếp cận tập thô mờ (RSAR) (F_RSAR) tôi thự hiệ ô g việ s u: S R Độ Độ R Độ Độ Bộ số U C - C i đặt thuật t ời ạ hó dữ iệu ằ g phươ g T chính chính chính chính liệu ph p e u -width [12], thuật t RSAR, thuật t T xác xác xác xác phân phân phân phân F_RSAR sử dụ g u hệ tươ g tự t g [8], thuật lớp lớp lớp lớp t phâ ớp SVM [9], C4.5 [10] ằ g ô g ụ J v . SVM C4.5 SVM C4.5 - Thự hiệ thuật t ời ạ hó equal-width v 1 Ecoli 336 7 50.851 0.819 7 0.865 0.855 thuật t RSAR để tìm tập út gọ the tiếp ậ tập 2 Ionos 351 3 10.814 0.802 15 0.937 0.915 phere 4 0 thô. 3 Wdbc 569 3 80.795 0.784 19 0.980 0.975 - Thự hiệ thuật t F_RSAR để tìm tập út gọ 0 t ự tiếp từ ả g uyết đị h đầu the tiếp ậ tập 4 Wpbc 198 3 70.718 0.704 19 0.825 0.818 3 thô mờ sử dụ g u hệ tươ g tự ở ô g thứ (8) 5 Wine 178 1 40.814 0.802 10 0.955 0.920 trong ô g t ì h [8] 3 - T ê ả g uyết đị h thu đượ ủ h i h tiếp 6 Glass 214 9 50.815 0.795 7 0.891 0.882 7 Magic 190 1 40.745 0.715 6 0.782 0.765 ậ , họ 2/3 đối tượ g đầu tiê để m tập huấ uyệ 04 20 0 (t i i g), 1/3 đối tượ g ò ại m tập kiểm t (test). 8 Page- 547 1 50.758 0.725 7 0.865 0.855 Thự hiệ thuật t SVM, C4.5 t ê tập huấ uyệ blocks 3 0 v đ h gi độ h h x phâ ớp t ê tập kiểm t . Từ đó, đ h gi độ h h x phâ ớp ủ h i h Từ Bả g 3 v Hì h 1 t thấy, tập út gọ ủ tiếp ậ . F_RSAR hiều thuộ t h hơ RSAR. Độ h h x Bả g 3 kết uả thử ghiệm t ê 8 ộ số iệu phâ ớp s u khi út gọ thuộ t h the tiếp ậ tập đượ họ với U số đối tượ g, C số thuộ t h thô mờ (F_RSAR) hơ độ h h x phâ ớp the tiếp ậ tập thô t uyề thố g (RSAR). điều kiệ , R số thuộ t h ủ tập út gọ . Tiếp the , hú g tôi tiế h h thử ghiệm để đ h gi thuật t đề xuất (F_RSAR) với thuật t tìm tập út gọ the tiếp ậ tập thô mờ sử dụ g ượ g thô g ti tă g thêm (i f m ti g i ) dự t ê e t py Sh , gọi thuật t GAIN_RATIO_AS_FRS [8]. Để tiế h h thử ghiệm, hú g tôi i đặt thuật t GAIN_RATIO_AS_FRS trong [8] v thuật t F_RSAR. Cả h i thuật t đều dù g u hệ tươ g tự ở ô g thức (8) trong ô g t ì h [8]. Chạy 02 thuật t t ê 8 ộ dữ iệu thử ghiệm. Kết uả thử ghiệm h ở Bả g 4. Hình 1. Độ chính xác phân lớp F_RSAR và RSAR - 46 - Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 Bảng 4. Kết quả thử nghiệm thuật toán V. KẾT LUẬN GAIN_RATIO_AS_FRS và thuật toán F_RSAR Mô hì h tập thô mờ do D. Du is v ộng sự Thuật toán Thuật toán F_RSAR [4, 5] đề xuất ô g ụ hiệu quả để giải quyết i GAIN_RATIO_AS_FR t út gọn thuộ t h t ực tiếp t ê ảng quyết S S R Độ Độ R Độ Độ đị h ó miền trị thuộ t h nhậ gi t ị số. T g i Bộ số C T U chính chính chính chính y, hú g tôi đề xuất thuật t heu isti tìm một liệu T xác xác xác xác tập út gọn của bảng quyết đị h ó miền trị thuộ t h phân phân phân phân nhậ gi t ị số sử dụ g độ phụ thuộc mờ của thuộc lớp lớp lớp lớp SVM C4.5 SVM C4.5 t h the tiếp cận tập thô mờ. 1 Ecoli 336 7 6 0.814 0.802 7 0.865 0.855 Độ phụ thuộc mờ của thuộ t h đượ x định dựa 2 Ionosp 351 34 13 0.916 0.904 15 0.937 0.915 t ê m t ận quan hệ sinh bởi một quan hệ tươ g tự here 3 Wdbc 569 30 17 0.925 0.917 19 0.980 0.975 x đị h t ê miề gi t ị thuộ t h. Thực nghiệm t ê 4 Wpbc 198 33 17 0.815 0.804 19 0.825 0.818 ộ số liệu UCI cho thấy, độ h h x phâ ớp 5 Wine 178 13 9 0.910 0.902 10 0.955 0.920 của tập dữ liệu sau khi thực hiệ phươ g ph p đề xuất 6 Glass 214 9 7 0.891 0.882 7 0.891 0.882 hơ độ h h x phâ ớp sau khi thực hiệ út Magic 1902 7 10 6 0.782 0.765 6 0.782 0.765 gọn thuộ t h the tiếp cận tập thô truyền thống. 04 0 Page- Hơ ữ , phươ g ph p đề xuất ó độ h h x 8 5473 10 6 0.852 0.848 7 0.865 0.855 blocks phâ ớp hơ phươ g ph p tiếp cận dự t ê e t py Sh t g ô g t ì h [8]. Mặt kh , phươ g ph p đề xuất khô g phải t h ô g thức logarit củ e t py Sh ê thời gian thực hiện hiệu quả hơ phươ g ph p t g [8]. Về đị h hướ g ghiê ứu tiếp theo, thứ nhất tìm kiếm độ đ hiệu quả để giải quyết i t út gọn thuộ t h the tiếp cận tập thô mờ nhằm â g độ h h x phâ ớp, thứ h i tìm kiếm u hệ tươ g tự kh hằm â g độ h h x phâ ớp s u khi út gọn thuộ t h. TÀI LIỆU THAM KHẢO Hình 2. Độ chính xác phân lớp của GAIN_RATIO_AS_FRS [1] CHEN, D.G., TSANG E.C.C. and ZHAO, S.Y, An và F_RSAR approach of attributes reduction based on fuzzy TL rough sets, IEEE International Conference on Từ Bả g 4 v Hì h 2 t thấy, t ê ù g một u Systems, Man and Cybernetics, pp. 486-491, 2007. hệ tươ g tự đượ sử dụ g, độ h h x phâ ớp s u [2] CHEN D.G, ZHAO S.Y., Local reduction of decision khi thự hiệ thuật t đề xuất F_RSAR hơ độ system with fuzzy rough sets, Fuzzy Sets and Systems h h x phâ ớp s u khi thự hiệ thuật t 161, pp. 1871-1883, 2010. GAIN_RATIO_AS_FRS t g [8]. Bả g 4 ũ g h [3] CHEN D.G, LEI Z, SUYUN Z, QINGHUA H, and thấy, tập út gọ ủ thuật t đề xuất F_RSAR ả PENGFEI Z, A Novel Algorithm for Finding Reducts With Fuzzy Rough Sets, IEEE Transaction on Fuzzy t miề dươ g mờ v hiều thuộ t h hơ s với Systems, Vol. 20, No. 2, pp. 385 - 389 , 2012. thuật t GAIN_RATIO_AS_FRS t g [8]. - 47 - Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 [4] DUBOIS D, PRADE H, Putting rough sets and fuzzy Knowledge-Based Systems 24 (2011), pp. 689–696, sets together, Intelligent Decision Support, Kluwer 2011. Academic Publishers,Dordrecht, 1992. [17] QINGHUA HU, DAREN YU, ZONGXIA XIE, [5] DUBOIS D, PRADE H, Rough fuzzy sets and fuzzy Information-preserving hybrid data reduction based rough sets, International Journal of General Systems, on fuzzy-rough techniques, Pattern Recognition Letters 17, pp. 191-209, 1990. 27, 2006, pp. 414-423. [6] F. F. XU, D. Q. MIAO and L. WEI, An Approach for [18] R. JENSEN, Q. SHEN, Fuzzy-Rough Sets for Fuzzy-Rough Sets Attributes Reduction via Mutual Descriptive Dimensionality Reduction, Proceedings of Information, Fourth International Conference the 2002 IEEE International Conference on Fuzzy on Fuzzy Systems and Knowledge Discovery, FSKD Systems ,FUZZ-IEEE'02, pp. 29-34, 2002. 2007, Volume 3, pp. 107 – 112, 2007. [19] R. JENSEN, Q. SHEN, Fuzzy–rough attribute [7] F.F. XU, D.Q. MIAO and L. WEI, Fuzzy-rough reduction with application to web categorization, attribute reduction via mutual information with an Fuzzy Sets and Systems, Volume 141, Issue 3, pp. application to cancer classification, Computers and 469-485,2004. Mathematics with Applications 57, pp. 1010 -1017, [20] RAJEN, B. BHATT, M. GOPAL., On fuzzy-rough sets 2009. approach to feature selection, Pattern Recognition [8] J. DAI, QING X, Attribute selection based on Letters 26, pp. 965–975, 2005. information gain ratio in fuzzy rough set theory with [21] TSANG G.C.Y., CHEN DEGANG., TSANG application to tumor classification, Applied Soft E.C.C, LEE J.W.T and DANIEL S. YEUNGA, On Computing 13, pp. 211–221, 2013. attributes reduction with fuzzy rough sets, [9] J. NEUMANN, C. SCHNORR, G. STEILD, Proceedings of 2005 IEEE International Conference Combined SVM-based feature selection and on Systems, Man and Cybernetics ,Volume 3, pp. classification, Mach. Learn. 61 (2005), pp. 129-150. 2775 - 2780, 2005. [10] J. QUINLAN, C4.5: Programs For Machine [22] TSANG E.C.C, DE GANG CHEN, The Fuzzy Rough Learning, Morgan kaufmann, 1993. Set Approaches of Fuzzy Reasoning, Proceedings of [11] L. A. ZADEH, Fuzzy sets, Information and Control, the Fifth International Conference on Machine 8:338-353, 1965. Learning and Cybernetics, Dalian, pp. 1642-1646, 2006. [12] M.R. CHMIELEWSKI, J.W. GRZYMALABUSSE, Global discretization of continuous attributes as [23] TSANG E.C.C, DEGANG CHEN. YEUNG D.S., XI preprocessing for machine learning, Int. J. Approx. ZHAO WANG and JOHN W. T. LEE, Attributes reasoning 15 (4), 1996, pp. 319–331. Reduction Using Fuzzy Rough Sets, IEEE Transactions on Fuzzy Systems, Volume16, Issue 5 , pp. 1130 - [13] PAWLAK Z., Rough sets, International Journal of 1141, 2008. Computer and Information Sciences, 11(5): 341-356, 1982. [24] YI CHENG, Forward approximation and backward approximation in fuzzy rough sets, Neurocomputing, [14] PAWLAK Z., Rough sets: Theoretical Aspects of Volume 148, pp. 340-353, 2015. Reasoning About Data, Kluwer Aca-demic Publishers, 1991. [25] ZHAO MING, YAN ZHENGBO, ZHOU LIUKUN, WANG HUIJIE and XU XIAOGANG, The Extraction [15] Q. SHEN, R. JENSEN, Selecting informative features Method of the Energy Consumption Characteristics with fuzzy-rough sets and its application for complex Based on Fuzzy Rough Set, Proceedings of Conference systems monitoring, Pattern Recognition, Volume 37, on Computational Intelligence and Bioinformatics Issue 7, pp. 1351–1363, 2004. (AASRI), pp. 142 – 149, 2012. [16] QIANG HE, CONGXIN WU, DEGANG CHEN, [26] The UCI machine learning repository, SUYUN ZHAO, Fuzzy rough set based attribute reduction for information systems with fuzzy decisions, Ngày nhận bài: 29/02/2016 - 48 - Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016 SƠ LƢỢC VỀ TÁC GIẢ NGUYỄN VĂN THIỆN NGUYỄN NHƢ SƠN Si h ăm 1970 tại Phú Thọ. Si h ăm 1974 tại Nghệ A . Tốt ghiệp ĐH B h kh H Nội Tốt ghiệp ĐH B h kh H ăm 1996. Tốt ghiệp Thạ sỹ tại Nội ăm 1995, thạ sĩ CNTT tại t ườ g ĐH Sư phạm H Nội ăm t ườ g ĐH B h kh H Nội 2000. ăm 2001. Nhậ ằ g tiế sỹ tại Hiệ đ g ô g t tại : T ườ g ĐH Queensland - Aust i ăm ĐH Cô g ghiệp H Nội. 2007, huyê g h Kh họ m y t h. Hướ g ghiê ứu: Hệ thố g thô g ti , Cơ sở dữ iệu, Kh i ph dữ iệu. Hiệ ô g t tại: Việ CNTT, Việ H âm KH&CN Việt N m. Điệ th ại: 0902416668. Hướ g ghiê ứu: Hệ thố g thô g ti , Cơ sở dữ iệu, Email: nvthien1970@gmail.com Kh i ph dữ iệu, T h t đ m mây. NGUYỄN LONG GIANG Điệ th ại: 0987039966. Email: nnson@ioit.ac.vn Sinh ăm 1975 tại H Nội. Tốt ghiệp ĐH B h kh H Nội