Tóm tắt Luận án tiến sĩ Kỹ thuật: Nghiên cứu các phương pháp rút gọn thuộc tính và sinh luật quyết định theo tiếp cận tập thô mờ

Chia sẻ: Tỉ Thành | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

49
lượt xem 2
download

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

Luận án được nghiên cứu với mục tiêu nhằm nghiên cứu sinh nghiên cứu các phương pháp hiệu quả rút gọn thuộc tính và sinh luật quyết định trên bảng quyết định mờ. Tính hiệu quả dựa trên hai tiêu chí đánh giá là độ chính xác phân lớ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: Tóm tắt Luận án tiến sĩ Kỹ thuật: Nghiên cứu các phương pháp rút gọn thuộc tính và sinh luật quyết định theo tiếp cận tập thô mờ

BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG CAO CHÍNH NGHĨA NGHIÊN CỨU CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT QUYẾT ĐỊNH THEO TIẾP CẬN TẬP THÔ MỜ Chuyên ngành: Hệ thống thông tin Mã số: 62.48.01.04 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT Hà Nội - 2017
Công trình được hoàn thành tại: Học viện Công nghệ Bưu chính Viễn thông Người hướng dẫn khoa học: GS. TS. Vũ Đức Thi TS. Tân Hạnh Phản biện:..................................................................... ..................................................................................... Phản biện:..................................................................... ..................................................................................... Phản biện:..................................................................... ..................................................................................... Luận án sẽ được bảo vệ trước Hội đồng cấp Học viện Công nghệ Bưu chính Viễn thông chấm luận án tiến sĩ họp tại.. ..................................................................................... vào hồi giờ ngày tháng năm Có thể tìm hiểu luận án tại: - Thư viện Quốc gia Việt Nam - Thư viện Học viện Công nghệ Bưu chính Viễn thông
MỞ ĐẦU Tính cấp thiết của luận án Rút gọn thuộc tính và sinh luật quyết định là hai bài toán quan trọng trong quá trình khám phá tri thức từ dữ liệu. Rút gọn thuộc tính của bảng quyết định là quá trình lựa chọn tập con nhỏ nhất của tập thuộc tính điều kiện, loại bỏ các thuộc tính dư thừa mà bảo toàn thông tin phân lớp của bảng quyết định, gọi là tập rút gọn (reduct). Kết quả rút gọn thuộc tính ảnh hưởng trực tiếp đến hiệu quả thực hiện các nhiệm vụ khai phá: Gia tăng tốc độ, cải thiện chất lượng, tính dễ hiểu của các kết quả thu được. Sinh luật quyết định là bước tiếp theo của rút gọn thuộc tính trong khai phá dữ liệu nhằm đánh giá chất lượng phân lớp của dữ liệu thông qua độ hỗ trợ của tập luật quyết định. Lý thuyết tập thô mờ (Fuzzy rough set) do Dubois, D., và Prade, H., đề xuất 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ờ dựa trên một quan hệ tương đương mờ (fuzzy equivalent relation) được xác định trên miền giá trị thuộc tính. Theo lý thuyết tập thô mờ, độ tương đương mờ của hai đối tượng là một giá trị nằm trong đoạn [0,1] cho thấy tính gần nhau, hay khả năng phân biệt giữa hai đối tượng. Do đó, quan hệ tương đương mờ bảo toàn sự khác nhau giữa các đối tượng và các phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ có tiềm năng trong việc bảo toàn độ chính xác phân lớp sau khi thực hiện các phương pháp rút gọn thuộc tính. Chủ đề nghiên cứu về rút gọn thuộc tính và sinh luật quyết định theo tiếp cận tập thô mờ đã thu hút sự quan tâm của các nhà nghiên cứu trong mấy năm gần đây. Luận án tập trung nghiên cứu trọng tâm vào hai bài toán: 1
1) Bài toán thứ nhất là rút gọn thuộc tính của bảng quyết định miền giá trị thực trong bước tiền xử lý số liệu. 2) Bài toán thứ hai là rút gọn thuộc tính và sinh luật quyết định của bảng quyết định mờ. Đối tượng nghiên cứu của luận án là các bảng quyết định có miền giá trị thực và bảng quyết định mờ. Các kết quả đạt được của luận án 1) Đề xuất các phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết định miền giá trị thực theo tiếp cận tập thô mờ, bao gồm: - Phương pháp rút gọn thuộc tính sử dụng miền dương mờ nhằm nhằm khắc phục một số hạn chế của những công bố trước đây để tìm được một tập rút gọn không dư thừa thuộc tính và bảo toàn miền dương mờ. Kết quả này công bố trong công trình [CCN1], [CCN2]. - Phương pháp rút gọn thuộc tính sử dụng khoảng cách Jaccard mờ và khoảng cách phân hoạch mờ. Thực nghiệm trên một số bộ dữ liệu lấy từ kho dữ liệu UCI chứng minh hai phương pháp sử dụng khoảng cách mờ hiệu quả hơn các phương pháp đã công bố trên cả hai tiêu chí: Độ chính xác phân lớp và thời gian thực hiện trên một số bộ dữ liệu thực nghiệm. Các kết quả này công bố trong công trình [CCN3], [CCN4]. 2) Đề xuất phương pháp rút gọn thuộc tính và sinh luật trong bảng quyết định mờ theo tiếp cận tập thô mờ. Phương pháp rút gọn thuộc tính sử dụng miền dương mờ được công bố trong công trình [CCN2], phương pháp sinh hệ luật mờ trên bảng quyết định mờ sử dụng khoảng cách Jaccard mờ được công bố trong [CCN5]. Bằng lý thuyết và thực nghiệm chứng minh phương pháp đề xuất tương 2
đương với các phương pháp khác trên tiêu chí độ chính xác phân lớp dữ liệu. Bố cục của luận án gồm phần mở đầu và bốn chương nội dung, phần kết luận và danh mục các tài liệu tham khảo. Chương 1 trình bày một số khái niệm cơ bản về lý thuyết tập thô và tổng quan về bài toán rút gọn thuộc tính mà luận án tập trung nghiên cứu. Chương 2 trình bày các kết quả nghiên cứu về các phương pháp rút gọn thuộc tính trong bảng quyết định miền giá trị thực sử dụng miền dương mờ và khoảng cách Jaccard mờ. Chương 3 trình bày kết quả nghiên cứu về phương pháp rút gọn thuộc tính trong bảng quyết định miền giá trị thực sử dụng khoảng cách phân hoạch mờ. Chương 4 trình bày phương pháp rút gọn thuộc tính và sinh luật quyết định của bảng quyết định mờ. CHƯƠNG 1. CÁC KIẾN THỨC CƠ SỞ 1.1. Một số khái niệm về tập thô 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 gọi là tập vũ trụ; A là tập hữu hạn khác rỗng các thuộc tính. Cho hệ thông tin IS  U , A  và tập đối tượng X  U . Với một tập thuộc tính P  A cho trước, xác định được các lớp tương đương của phân hoạch U / P . Có hai cách xấp xỉ tập đối tượng X thông qua tập thuộc tính P, được gọi là P-xấp xỉ dưới và P-xấp xỉ trên của X, ký hiệu lần lượt là PX và PX , được xác định như sau:  P   P  PX  u  U  u   X , PX  u U u   X   Tập PX bao gồm tất cả các phần tử của U chắc chắn thuộc vào X, còn tập PX bao gồm các phần tử của U có khả năng thuộc vào X dựa vào tập thuộc tính P. 3
Xét hệ thông tin IS  U , A  với P, Q  A , ta gọi POS P (Q ) là P-miền dương của Q, 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 / Q sử dụng tập thuộc tính P. Nói một cách hình thức, POSP (Q)  u U uP  uQ Bảng quyết định DT  U , C  D  là một dạng đặc biệt của hệ thông tin, trong đó tập các 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 với C  D   . Nếu miền giá trị của mọi thuộc tính c  C là các giá trị số thực thì bảng quyết định DT được gọi là bảng quyết định miền giá trị thực. 1.2. Một số khái niệm về tập thô mờ xác định trên bảng quyết định miền giá trị thực Cho bảng quyết định miền giá trị thực DT  U , C  D  , một  xác định trên miền giá trị thuộc tính được gọi là quan hệ quan hệ R tương đương mờ nếu thỏa mãn các điều kiện sau với mọi x, y, z U 1) Tính phản xạ (reflexive):   x, x   1 ; R 2) Tính đối xứng (symetric): R  x , y   R  y , x  ; 3) Tính bắc cầu max-min (max-min transitive):   x, z   min  R R   x, y  , R   y, z  ; Cho bảng quyết định miền giá trị thực DT  U , C  D  với U   x1 , x2 ,..., xn   P là quan hệ tương đương mờ xác định trên và R  P được biểu diễn bởi ma trận tập thuộc tính P  C . Quan hệ R tương đương mờ P  p  M R   ij  nn với pij  R P  xi , x j  là giá trị của quan hệ giữa hai đối tượng xi và x j trên tập thuộc tính P, pij  0,1 , xi , x j  U , 1  i , j  n . 4
Quan hệ tương đương mờ R  P xác định một phân hoạch mờ  P là  R P  U / R P   x  n   x  ,...,  x  với   P  U / R    i  R P   1  R P  n  R P  i 1 xi R P  pi1 / x1  pi2 / x2  ...  pin / xn là một tập mờ đóng vai trò là một lớp tương đương mờ (fuzzy equivalent class) của đối tượng xi . Hàm thuộc của các đối tượng xác định bởi: xi   R P  x j    R  xi , x j   R P  xi , x j   pij P với mọi x j  U . Khi đó, lực lượng của lớp đương đương mờ xi R P là n  xi R P  p j 1 ij  P là một quan hệ tương Cho X là một tập mờ trên U và R đương mờ trên tập thuộc tính P  C . Khi đó, tập xấp xỉ dưới R P X và tập xấp xỉ trên R P X của X là các tập mờ và hàm thuộc của các đối tương x U được xác định    R  x  sup min   F  x  , inf max 1   F  y  ,  X  y   PX  F U / R P  y U      x  sup min   F  x  , sup min  F  y  ,  X  y   RP X P FU / R  yU   X,R Bộ R  P X là tập thô mờ. P Với hai quan hệ tương đương mờ R P , R Q xác định trên hai tập  Q là một tập mờ, thuộc tính P , Q  C , miền dương mờ POS R P R   hàm thuộc của các đối tượng x U được xác định  POS  RP  R Q   x   X sup   x Q RP X U /R 5
1.3. Một số khái niệm về tập thô mờ xác định trên bảng quyết định mờ Bảng quyết định mờ là bảng quyết định mà các thuộc tính là  D  , các tập mờ (fuzzy set). Cho bảng quyết định mờ DT  U , C   phân hoạch mờ sinh ra bởi tập thuộc tính P  C  được xác định    a  P  : U / a U/P    với A  B  X   Y :    X  A, Y  B ,  X  Y   .  Xấp xỉ dưới mờ và xấp xỉ trên mờ của tập  X là các tập mờ và hàm thuộc của các đối tượng được xác định như sau:    P X  x   sup min   F  x  , inf max 1   F  y  ,  X  y    F U / P  yU         x   sup min   F  x  ,sup min  F  y  ,  X  y   PX   FU / P  yU  Khi đó, miền dương mờ là tập mờ với hàm thuộc là:  POS  P Q   x   Xsup    x  PX U / Q Lực lượng của miền dương mờ được tính theo công thức POS  P Q   x    xU  POS P Q   x  1.4. Rút gọn thuộc tính trong bảng quyết định Các kỹ thuật rút gọn thuộc tính được phân thành hai loại: Lựa chọn thuộc tính (Attribute selection) và biến đổi thuộc tính (Attribute transformation). Lựa chọn thuộc tính là chọn một tập con tốt nhất (theo một nghĩa nào đó) từ tập dữ liệu ban đầu. 6
Biến đổi thuộc tính thực hiện việc biến đổi các thuộc tính ban đầu thành một tập các thuộc tính mới với số lượng ít hơn sao cho bảo tồn được thông tin nhiều nhất. Tập thuộc Các công trình nghiên cứu về rút tính ban đầu gọn thuộc tính thường tập trung vào nghiên cứu các kỹ thuật lựa chọn Định nghĩa tập rút gọn thuộc tính. Nhìn chung, một thuật toán lựa chọn thuộc tính thường bao gồm bốn khâu cơ bản: Định nghĩa độ quan trọng của thuộc tính  Tạo lập tập con  Đánh giá tập con  Kiểm tra điều kiện dừng Xây dựng thuật toán heuristic tìm một tập rút gọn  Kiểm chứng kết quả. Phương pháp rút gọn thuộc tính heuristic được mô hình hóa như hình Tập rút gọn vẽ. 1.5. Kết luận chương 1 Chương 1 trình bày một số khái niệm cơ bản trong lý thuyết tập thô; một số khái niệm cơ bản về tập thô mờ nhằm giải quyết bài toán rút gọn thuộc tính trên bảng quyết định miền giá trị thực; giải quyết bài toán rút gọn thuộc tính và sinh luật quyết định trên bảng quyết định mờ. Các khái niệm được trình bày ở Chương 1 là các kiến thức nền tảng được sử dụng trong các chương sau của luận án. 7
CHƯƠNG 2. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH MIỀN GIÁ TRỊ THỰC SỬ DỤNG MIỀN DƯƠNG MỜ VÀ KHOẢNG CÁCH JACCARD MỜ 2.1. Đặt vấn đề Các kết quả chính trong chương này được công bố trong các công trình [CCN1], [CCN2], [CCN3]. 2.2. Rút gọn thuộc tính sử dụng miền dương mờ Theo hướng tiếp cận này, Hu, Q., và các cộng sự đề xuất thuật toán FAR-VPFRS tìm một tập rút gọn sử dụng độ phụ thuộc của thuộc tính dựa trên miền dương mờ. Dựa trên phương pháp của Hu, Q., phần này đề xuất phương pháp rút gọn thuộc tính dựa trên miền dương mờ sử dụng quan hệ tương đương mờ, để tìm một tập rút gọn không dư thừa và bảo toàn miền dương mờ. 2.2.1. Phương pháp rút gọn thuộc tính sử dụng miền dương mờ Định nghĩa 2.1. Cho bảng quyết định có miền giá trị thực  và tập thuộc tính DT  U , C  D  , quan hệ tương đương mờ R P  C . Nếu 1)  POS  D   x    POS   D   x  RP RC 2) p  P,  POS  R( P { p })  D   x    POS R C  D   x  thì P là một tập rút gọn của C dựa trên miền dương mờ. Định nghĩa 2.2. Cho bảng quyết định có miền giá trị thực DT  U , C  D   xác định trên miền và quan hệ tương đương mờ R giá trị thuộc tính. Với P  C , độ quan trọng của thuộc tính b  C  P  được định nghĩa: đối với tập thuộc tính P dựa trên quan hệ R SIGR P  b    POS ( D ) ( x)   POS (D) ( x) R ( P {b}) RP Thuật toán F_RSAR2: Thuật toán tìm một tập rút gọn không dư 8
thừa dựa trên miền dương mờ sử dụng quan hệ tương đương mờ. Đầu vào: Bảng quyết định giá trị thực DT  U , C  D  , quan . hệ tương đương mờ R Đầu ra: Một tập rút gọn P . 1. P  ; | POSR ( D) ( x) | 0 ;  2. Tính  POS  RC (D) ( x) ; 3. While POS P R ( D) ( x)  POSR (D ) ( x) Do C 4. Begin 5. For c  C  P Do SIGP  c   POS R( P{c}) ( D ) ( x )  POSR ( D ) ( x) ; P 6. Chọn cm  C  P sao cho SIGP (cm )  Max{SIGP (c)} ; cC  P 7. P  P  {cm } ; 8. End; // Kiểm tra thuộc tính dư thừa trong P nếu có 9. For each a  P 10. Begin 11. Tính  POS  R( P { a }) (D) ( x) ; 12. If POS  ( P { a }) R (D) ( x )   POSR (D) ( x ) then P  P  a ; C 13. End; 14. Return P; Ví dụ 2.1. Cho bảng quyết định miền giá trị thực DT  U , C  D  như ở Bảng 2.1. Bảng 2.1. Bảng quyết định miền giá trị thực của Ví dụ 2.1 U c1 c2 c3 c4 c5 c6 D u1 0.8 0.2 0.6 0.4 1 0 0 9
u2 0.8 0.2 0 0.6 0.2 0.8 1 u3 0.6 0.4 0.8 0.2 0.6 0.4 0 u4 0 0.4 0.6 0.4 0 1 1 u5 0 0.6 0.6 0.4 0 1 1 u6 0 0.6 0 1 0 1 0 Một quan hệ tương đương mờ được định nghĩa trên miền giá trị của thuộc tính với p  xi  là giá trị của thuộc tính p tại đối tượng xi , pmax , pmin tương ứng là giá trị lớn nhất, nhỏ nhất của thuộc tính p.  1  4 *   p  xi   p x j   p  xi   p x j , if  0.25 pij   p max  p min p max  p min   0, otherwise Áp dụng F_RSAR2 tìm được tập rút gọn P  c 4 , c1  . Thuật toán F_RSAR2 có độ phức tạp tính toán ma trận tương 2 đương mờ của một thuộc tính là O( U ) với U là số lượng đối tượng, C là số lượng thuộc tính điều kiện; độ phức tạp tính toán của 2 3 2 C ) M (R là O( C U ) . Độ phức tạp của F_RSAR2 là O( C U ) . 2.2.2. Thử nghiệm và đánh giá kết quả Luận án chọn sáu bộ dữ liệu lấy từ kho dữ liệu UCI có miền giá trị số thực cho ở Bảng 2.2 để tiến hành thử nghiệm. Môi trường thử nghiệm là máy tính PC với cấu hình Pentium core i3 2.4 GHz CPU, 2 GB bộ nhớ RAM, hệ điều hành Windows 10. Bảng 2.2. Bộ dữ liệu thử nghiệm Số thuộc tính Số đối Số TT Bộ dữ liệu điều kiện tượng lớp 1 Fisher_Order 35 47 4 2 Iris 4 150 3 3 Glass 10 214 7 4 Sonar 60 208 2 5 Sensor_Readings_24 24 5456 4 10
6 EEG_Eye_State 14 14980 2 Cài đặt các thuật toán F_RSAR2, FAR-VPFRS bằng ngôn ngữ C#, các thuật toán sử dụng quan hệ tương đương mờ như ở Ví dụ 2.1. Sử dụng thuật toán C4.5 trong công cụ J48 của WEKA để đánh giá độ chính xác phân lớp của hai thuật toán bằng cách chọn 2/3 số đối tượng làm tập huấn luyện (training set), 1/3 số đối tượng còn lại làm tập kiểm tra (testing set). Bảng 2.3 và Bảng 2.4 là kết quả thử nghiệm trên sáu bộ số liệu được chọn với 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 với mỗi thuật toán, t là thời gian thực hiện (đơn vị là giây). Bảng 2.3. Kết quả thực nghiệm của F_RSAR2, FAR-VPFRS FA_RSAR2 FAR_VPFRS TT Bộ số liệu C R R t t 1 Fisher_Order 35 19 0.216 21 0.209 2 Iris 4 1 0.003 2 0.003 3 Glass 10 7 0.40 7 0.040 4 Sonar 60 12 2.975 12 2.889 5 Sensor_Readings_24 24 15 2.634 15 2.465 6 EEG_Eye_State 14 7 4.969 7 4.356 Bảng 2.4. Độ chính xác phân lớp C4.5 của F_RSAR2, FAR-VPFRS F_RSAR2 FAR-VPFRS T Độ chính Độ chính Bộ số liệu U C xác phân xác phân T R R lớp C4.5 lớp C4.5 (%) (%) 1 Fisher_Order 47 35 19 78.72 21 76.59 2 Iris 150 4 1 94.67 2 94.00 3 Glass 214 10 7 81.56 7 81.56 4 Sonar 208 60 12 70.60 12 70.60 5 Sensor_Readings_24 5456 24 15 95.12 15 95.12 6 EEG_Eye_State 14980 14 7 81.25 7 81.25 11
2.3. Rút gọn thuộc tính sử dụng khoảng cách Jaccard mờ 2.3.1. Khoảng cách Jaccard mờ và các tính chất Định nghĩa 2.3. Cho U là tập hữu hạn các đối tượng và A, B  U . Khoảng cách Jaccard giữa hai tập hợp hữu hạn, được định nghĩa A B DJ ( A, B)  1  A B Định lý 2.1. Cho A, B ,C  là ba tập mờ trên U . Khi đó   A B , B DFJ ( A )  1   A B là khoảng cách Jaccard mờ giữa hai tập mờ A, B . Định nghĩa 2.4. Cho bảng quyết định mờ DT  U , C  D  , giả sử  C và R hai quan hệ tương đương mờ R  D xác định trên hai tập thuộc C tính C và D tương ứng. Gọi rij là các phần tử của ma trận tương  C và r D là các phần tử của ma trận tương đương đương mờ M R   ij D mờ M R   với 1  i, j  n . Khoảng cách Jaccard mờ giữa hai tập thuộc tính C và C  D dựa trên ma trận quan hệ tương đương mờ xây dựng như sau: n 1 U  min r j 1 C D ij , rij  d FJ C, C  D   1  U  n C i 1 r j 1 ij Định nghĩa 2.5. Cho bảng quyết định có miền giá trị thực DT  U , C  D  và tập thuộc tính P  C . Nếu 1) d FJ  P , P  D   d FJ  C , C  D  2) p  P, dFJ (P   p ,  P   p   D)  d FJ (C, C  D) thì P là một tập rút gọn của C dựa trên khoảng cách Jaccard mờ. 12
Định nghĩa 2.6. Cho bảng quyết định DT  U , C  D  , P  C và b  C  P . Độ quan trọng của thuộc tính b đối với P được định nghĩa bởi SIGP  b   dFJ  P, P  D  dFJ  P b , P b  D 2.3.2. Phương pháp rút gọn thuộc tính sử dụng khoảng cách Jaccard mờ Thuật toán FJ_DBAR xây dựng theo phương pháp heuristic (phần 1.4) để tìm một tập rút gọn, cách thức xây dựng giống như thuật toán F_RSAR2 ở phần 2.2 với tập rút gọn xác định theo định nghĩa 2.5, độ quan trọng thuộc tính xác định theo định nghĩa 2.6. Áp dụng FJ_DBAR cho Ví dụ 2.1 thu được P  c 4 , c1  2.3.3. Thử nghiệm và đánh giá kết quả Luận án lựa chọn thuật toán heuristic tìm một tập rút gọn dựa trên lượng thông tin tăng thêm GAIN_RATIO_AS_FRS (gọi là GRAF, sử dụng entropy mờ) khi thêm một thuộc tính vào tập rút gọn để so sánh với thuật toán FJ_DBAR, kịch bản thử nghiệm như (phần 2.2.2). Kết quả thử nghiệm cho ở Bảng 2.5 và Bảng 2.6 Bảng 2.5. Kết quả thực nghiệm của FJ_DBAR và GRAF FJ_DBAR GRAF T Tập dữ liệu |U| |C| T |R| t |R| T 1 Fisher_Order 47 35 18 0.095 21 0.107 2 Iris 150 4 1 0.002 2 0.003 3 Glass 214 10 6 0.46 8 0.48 4 Sonar 208 60 26 2.053 23 1.980 5 Sensor_Readings_24 5456 24 14 2.095 12 1.986 6 EEG_Eye_State 14980 14 7 2.580 7 2.790 13
Bảng 2.6. Độ chính xác phân lớp C4.5 của FJ_DBAR và GRAF FJ_DBAR GRAF T Độ chính Độ chính Tập dữ liệu |U| |C| T |R| xác phân |R| xác phân lớp (%) lớp (%) 1 Fisher_Order 47 35 18 78.72 21 76.59 2 Iris 150 4 1 94.00 2 94.00 3 Glass 214 10 6 80.15 8 81.70 4 Sonar 208 60 26 71.63 23 70.67 5 Sensor_Readings_24 5456 24 14 94.84 12 91.25 6 EEG_Eye_State 14980 14 7 81.25 7 81.25 2.4. Kết luận chương 2 Chương 2 của luận án cải tiến phương pháp rút gọn thuộc tính của bảng quyết định miền giá trị thực trong công trình của Hu, Q., để tìm một tập rút gọn không dư thừa thuộc tính, bảo toàn miền dương mờ. Đóng góp chính của Chương 2 là đề xuất phương pháp rút gọn thuộc tính của bảng quyết định miền giá trị thực sử dụng khoảng cách Jaccard mờ. Thử nghiệm trên một số bộ dữ liệu mẫu từ kho dữ liệu UCI cho thấy độ chính xác phân lớp của phương pháp sử dụng khoảng cách Jaccard mờ tốt hơn phương pháp sử dụng entropy mờ trên một số bộ dữ liệu, thời gian thực hiện nhanh hơn trên đa số bộ dữ liệu thử nghiệm. CHƯƠNG 3. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH MIỀN GIÁ TRỊ THỰC SỬ DỤNG KHOẢNG CÁCH PHÂN HOẠCH MỜ 3.1. Đặt vấn đề Chương 3 của luận án đề xuất độ đo khoảng cách giữa hai phân hoạch mờ và ứng dụng rút gọn thuộc tính của bảng quyết định miền giá trị thực. Các kết quả chính trong chương này được công bố trong công trình [CCN4]. 14
3.2. Khoảng cách phân hoạch mờ và các tính chất Mệnh đề 3.1. Cho hai tập mờ A, B trên cùng tập đối tượng U. Khi đó , B   A B  2 A  B  d NF A   là một độ đo khoảng cách giữa A và B . Định lý 3.1. Xét bảng quyết định DT  U , C  D  với P ,  R  Q là hai phân hoạch mờ sinh bởi U   x1 , x2 ,..., xn  và  R    P , R hai quan hệ tương đương mờ R  Q trên P, Q  C . Khi đó:  x   x   2 x   x  n   P , R Q   i R P  i R Q 1  i R P  i R Q  DNF        R  i 1   n n      P và  R Q . là khoảng cách phân hoạch mờ giữa  R     3.3. Phương pháp rút gọn thuộc tính sử dụng khoảng cách phân hoạch mờ Định nghĩa 3.1. Cho bảng quyết định miền giá trị thực P ,  R  Q là hai phân hoạch mờ sinh ra DT  U , C  D  với  R     bởi hai quan hệ tương đương mờ R P , R  Q trên P, Q  C . Khi đó, khoảng cách phân hoạch mờ giữa hai tập thuộc tính P và Q , ký hiệu là d NF  P , Q  , được định nghĩa là khoảng cách phân hoạch mờ P Q , giữa hai phân hoạch mờ  R   và    R nghĩa là  P , R Q d NF  P, Q   DNF  R      . Mệnh đề 3.4. Cho bảng quyết định miền giá trị thực DT  U , C  D   là quan hệ tương đương mờ xác định với U   x1 , x2 ,..., xn  và R trên miền giá trị tập thuộc tính điều kiện, khi đó khoảng cách phân hoạch mờ giữa hai tập thuộc tính C và C  D dựa trên ma trận tương đương mờ được xác định như sau: n x    x    x   1   i R C  i R C  i D  d NF  C, C D   n   i 1  n    15
Định nghĩa 3.2. Cho bảng quyết định miền giá trị thực DT  U , C  D   là quan hệ tương đương mờ xác với B  C và R định trên miền giá trị tập thuộc tính điều kiện. Nếu: 1) d NF  B , B  D   d NF  C , C  D  2) b  B, d NF ( B  b , B  b  D))  d NF (C, C  D) thì B là một tập rút gọn của C theo khoảng cách phân hoạch mờ. Định nghĩa 3.3. Cho bảng quyết định miền giá trị thực DT  U , C  D  với B  C và b  C  B . Độ quan trọng của thuộc tính b đối với B được định nghĩa bởi SIGB  b  d NF  B, B  D   d NF  B  b , B  b  D Thuật toán NF_DBAR xây dựng theo phương pháp heuristic (phần 1.4) để tìm một tập rút gọn, cách thức xây dựng giống như thuật toán F_RSAR2 ở phần 2.2 với tập rút gọn xác định theo định nghĩa 3.2, độ quan trọng thuộc tính xác định theo định nghĩa 3.3. Áp dụng NF_DBAR cho Ví dụ 2.1 thu được P  c 4 , c1  3.4. Thử nghiệm và đánh giá kết quả Luận án chọn thuật toán FA_FPR (tìm tập rút gọn dựa trên miền dương mờ) và thuật toán FA_FSCE (tìm tập rút gọn dựa trên entropy mờ) để so sánh với NF_DBAR, kịch bản thử nghiệm như ở phần 2.2.2. Kết quả thử nghiệm cho ở Bảng 3.2 và Bảng 3.3. Bảng 3.2. Kết quả thực nghiệm của FA_FSCE, FA_FPR, NF_DBAR FA_ FSCE FA_FPR NF_DBAR T C Bộ số liệu T R t R t R t 1 Fisher_Order 35 22 0.198 21 0.193 18 0.079 2 Iris 4 2 0.002 2 0.003 1 0.002 3 Glass 10 6 0.029 7 0.036 7 0.024 4 Sonar 60 8 2.012 12 2.889 13 2.433 5 Sensor_Readings_24 24 12 1.963 15 2.465 14 2.005 6 EEG_Eye_State 14 7 3.659 7 4.069 7 3.046 16
Bảng 3.3. Độ chính xác phân lớp C4.5 của FA_FSCE, FA_FPR, NF_DBAR FA_ FSCE FA_FPR NF_DBAR T Bộ số liệu U C Độ chính Độ chính Độ chính R xác phân R xác phân R xác phân T lớp C4.5 lớp C4.5 lớp C4.5 (%) (%) (%) 1 Fisher_Order 47 35 22 79.87 21 76.59 18 78.72 2 Iris 150 4 2 94.00 2 94.00 1 94.67 3 Glass 214 10 6 80.15 7 81.56 7 81.56 4 Sonar 208 60 8 75.40 12 70.60 13 76.25 5 Sensor_Readings24 5456 24 12 91.25 15 95.12 14 94.84 6 EEG_Eye_State 14980 14 7 81.25 7 81.25 7 81.25 3.5. Kết luận chương 3 Chương 3 của luận án đề xuất một khoảng cách giữa hai phân hoạch mờ, ứng dụng xây dựng phương pháp rút gọn thuộc tính của bảng quyết định có miền giá trị thực. Thực nghiệm trên một số bộ dữ liệu lấy từ kho dữ liệu UCI cho thấy phương pháp đề xuất hiệu quả hơn các phương pháp sử dụng entropy thông tin mờ và miền dương mờ trên một số bộ dữ liệu thử nghiệm theo các tiêu chí đánh giá: Thời gian thực hiện và độ chính xác phân lớp dữ liệu. CHƯƠNG 4. RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT TRÊN BẢNG QUYẾT ĐỊNH MỜ 4.1. Đặt vấn đề Bài toán rút gọn thuộc tính trực tiếp trên bảng quyết định mờ được giới thiệu lần đầu trong công trình của Jensen, R., và Shen, Q., với thuật toán FUZZY-QUICKREDUCT. Sinh luật quyết định thường được thực hiện trên các tập rút gọn với mục tiêu rút ra tập luật đơn giản và nâng cao chất lượng phân lớp dữ liệu học theo các luật này. 4.2. Phương pháp rút gọn thuộc tính của bảng quyết định mờ Trong phần này, luận án trình bày phương pháp heuristic rút gọn thuộc tính trực tiếp của bảng quyết định mờ dựa trên miền dương mờ, sử dụng thuật toán F_RSAR1 được công bố trong công 17
trình [CCN2]. Thuật toán F_RSAR1 là cải tiến của thuật toán FUZZY-QUICKREDUCT để tìm được một tập rút gọn không dư thừa thuộc tính và bảo toàn miền dương mờ. Định nghĩa 4.1. Cho bảng quyết định DT (U , C  D  ) và tập thuộc tính  C P  . Nếu 1) POS  ) (D ( x )   POS  ( D ) ( x ) P C 2)  p  P ,   (D) POSP {p} ( x )  POS ( D ) ( x ) C  là một tập rút gọn của C thì P  dựa trên miền dương mờ. Định nghĩa 4.2. Cho bảng quyết định DT  (U,C  D  C ), P  và b  C P   . Độ quan trọng của thuộc tính b đối với tập thuộc tính P được định nghĩa SIGP b  POS   ( D ) ( x)  POS ( D ) ( x ) P{b} P Thuật toán F_RSAR1 xây dựng theo phương pháp heuristic (phần 1.4) để tìm một tập rút gọn, cách thức xây dựng giống như thuật toán F_RSAR2 ở phần 2.2 với tập rút gọn xác định theo định nghĩa 4.1, độ quan trọng thuộc tính xác định theo định nghĩa 4.2. Ví dụ 4.1. Cho bảng quyết định mờ D T  (U , C  D  ) như sau: Bảng 4.1. Bảng quyết định mờ chơi thể thao  C  C  C  TT 1 2 3 D c1 c 2 c3 c4  c 5 c6 c7 c8 d1 d2 d3 u1 0.3 0.7 0 0.2 0.7 0.1 0.3 0.7 0.1 0.9 0 u2 1 0 0 1 0 0 0.7 0.3 0.8 0.2 0 u3 0 0.3 0.7 0 0.7 0.3 0.6 0.4 0 0.2 0.8 u4 0.8 0.2 0 0 0.7 0.3 0.2 0.8 0.6 0.3 0.1 u5 0.5 0.5 0 1 0 0 0 1 0.6 0.8 0 u6 0 0.2 0.8 0 1 0 0 1 0 0.7 0.3 18