Tóm tắt Luận án 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ờ - Cao Chính Nghĩa

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:   ,PPX u U u X      PPX 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. 4 Xét hệ thông tin  ,IS U A với ,P Q A , ta gọi ( )PPOS 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,     ( )P QPPOS Q u U u u   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 quan hệ R xác định trên miền giá trị thuộc tính được gọi là quan hệ 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):   , 1R x x  ; 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):          , min , , ,R x z R x y R y z ; Cho bảng quyết định miền giá trị thực  ,DT U C D  với  1 2, , ..., nU x x x và PR là quan hệ tương đương mờ xác định trên tập thuộc tính P C . Quan hệ PR được biểu diễn bởi ma trận tương đương mờ   ijP n nM R p     với   ,Pij i jp R x x là giá trị của quan hệ giữa hai đối tượng ix và jx trên tập thuộc tính P ,  0,1ijp  , , , 1 ,i jx x U i j n   . 5 Quan hệ tương đương mờ PR xác định một phân hoạch mờ   / PP U R  là        11/ ,...,PP P n P P i nRR Ri R U R x x x             với  1 1 2 2/ / ... /Pi i i in nRx p x p x p x      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 ix . Hàm thuộc của các đối tượng xác định bởi:         , ,Pi RP Pj i j i j ijx Rx x x R x x p       với mọi jx U . Khi đó, lực lượng của lớp đương đương mờ Pi Rx   là  1 P n i ijR j x p      Cho X là một tập mờ trên U và PR là một quan hệ tương đương mờ trên tập thuộc tính P C . Khi đó, tập xấp xỉ dưới  PR X và tập xấp xỉ trên  PR 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            / sup , inf 1 , P P F F XR X y UF U R x min x max y y                     / sup ,sup , P P F F XR X y UF U R x min x min y y            Bộ  , PPR X R X là tập thô mờ. Với hai quan hệ tương đương mờ  ,P QR R xác định trên hai tập thuộc tính ,P Q C , miền dương mờ   P QRPOS R là một tập mờ, hàm thuộc của các đối tượng x U được xác định         / sup Q PRP Q R XPOS R X U R x x    6 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à các tập mờ (fuzzy set). Cho bảng quyết định mờ   ,DT U C D  , phân hoạch mờ sinh ra bởi tập thuộc tính  P C được xác định      / : /U P a P U a   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:              / sup , inf 1 ,F FP X Xy UF U P x min x max y y                       / sup ,sup ,F F XP X y UF U P x min x min y y            Khi đó, miền dương mờ là tập mờ với hàm thuộc là:         / sup P P XPOS Q X U Q x x    Lực lượng của miền dương mờ được tính theo công thức          P PPOS Q POS Qx Ux 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. 7 Tập thuộc tính ban đầu Định nghĩa tập rút gọn Định nghĩa độ quan trọng của thuộc tính Xây dựng thuật toán heuristic tìm một tập rút gọn Tập rút gọn 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. Các công trình nghiên cứu về rút 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 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:  Tạo lập tập con  Đánh giá tập con  Kiểm tra điều kiện dừng  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 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. 8 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  ,DT U C D  , quan hệ tương đương mờ R và tập thuộc tính P C . Nếu 1)          R RP CPOS D POS Dx x  2)          ( { }), R RP p CPOS D POS Dp P x 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  và quan hệ tương đương mờ R xác định trên miền giá trị thuộc tính. Với P C , độ quan trọng của thuộc tính b C P  đối với tập thuộc tính P dựa trên quan hệ R được định nghĩa:     ( {b})POS ( ) POS ( )( ) ( )P R RP PD DRSIG b x x   Thuật toán F_RSAR2: Thuật toán tìm một tập rút gọn không dư 9 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. POS ( ); | ( ) | 0R DP x   ; 2. Tính POS ( ) ( )RC D x ; 3. While  POS ( ) POS ( )( ) ( )R RP CD Dx x  Do 4. Begin 5. For c C P  Do    ( {c})POS ( ) POS ( )( ) ( )R RP PP D DSIG c x x   ; 6. Chọn mc C P  sao cho ( ) { ( )}P m Pc C PSIG c Max SIG c  ; 7. { }mP P c  ; 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  ( { }) ( ) ( ) R P a POS D x  ; 12. If  ( { })POS ( ) POS ( ) ( ) ( ) R RP a C D Dx x    then  P P a  ; 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 1c 2c 3c 4c 5c 6c D 1u 0.8 0.2 0.6 0.4 1 0 0 10 2u 0.8 0.2 0 0.6 0.2 0.8 1 3u 0.6 0.4 0.8 0.2 0.6 0.4 0 4u 0 0.4 0.6 0.4 0 1 1 5u 0 0.6 0.6 0.4 0 1 1 6u 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  ip x là giá trị của thuộc tính p tại đối tượng ix , max min,p p tương ứng là giá trị lớn nhất, nhỏ nhất của thuộc tính p.         max min max min 1 4 * 0.25 0, i j i j ij p x p x p x p x , ifp p p p p otherwise            Áp dụng F_RSAR2 tìm được tập rút gọn  4 1,P c c . Thuật toán F_RSAR2 có độ phức tạp tính toán ma trận tương đương mờ của một thuộc tính là 2( )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 ( )CM R là 2( )O C U . Độ phức tạp của F_RSAR2 là 3 2( )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 TT Bộ dữ liệu Số thuộc tính điều kiện Số đối tượng Số 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 11 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 TT Bộ số liệu C FA_RSAR2 FAR_VPFRS R t R 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 T T Bộ số liệu U C F_RSAR2 FAR-VPFRS R Độ chính xác phân lớp C4.5 (%) R Độ chính xác phân 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 12 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 ( , ) 1J A B D A B A B     Định lý 2.1. Cho   , ,A B C là ba tập mờ trên U . Khi đó      ( , ) 1FJ A B D A B 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ử hai quan hệ tương đương mờ CR và DR xác định trên hai tập thuộc tính C và D tương ứng. Gọi Cijr là các phần tử của ma trận tương đương mờ  CM R và Dijr là các phần tử của ma trận tương đương mờ  DM 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:     1 1 1 min , 1, 1 n C D ij ijU j FJ n Ci ij j r r d C C D U r          Đị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)    , ,FJ FJd P P D d C C D   2)     , ( , ) ( , )FJ FJp P d P p P p D d 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ờ. 13 Đị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         , ,P FJ FJSIG b d P P D d 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  4 1,P c c 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 T T Tập dữ liệu |U| |C| FJ_DBAR GRAF |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 14 Bảng 2.6. Độ chính xác phân lớp C4.5 của FJ_DBAR và GRAF T T Tập dữ liệu |U| |C| FJ_DBAR GRAF |R| Độ chính xác phân lớp (%) |R| Độ chính xác phân 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]. 15 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 đó       , 2NFd A B A B A B    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  1 2, , ..., nU x x x và  PR ,  QR là hai phân hoạch mờ sinh bởi hai quan hệ tương đương mờ PR , QR trên ,P Q C . Khi đó:          1 21, P Q P Q n i i i iR R R R P QNF i x x x x D R R n n                               là khoảng cách phân hoạch mờ giữa  PR và  QR . 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  ,DT U C D  với  PR ,  QR là hai phân hoạch mờ sinh ra bởi hai quan hệ tương đương mờ PR , QR 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à  ,NFd P Q , được định nghĩa là khoảng cách phân hoạch mờ giữa hai phân hoạch mờ  PR và  QR , nghĩa là       , ,P QNF NFd P Q D R R  . Mệnh đề 3.4. Cho bảng quyết định miền giá trị thực  ,DT U C D  với  1 2, , ..., nU x x x và R là quan hệ tương đương mờ xác định 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:      1 1C,C D C C n i i iR R D NF i x x x d n n                       16 Định nghĩa 3.2. Cho bảng quyết định miền giá trị thực  ,DT U C D  với B C và R là quan hệ tương đương mờ xác định trên miền giá trị tập thuộc tính điều kiện. Nếu: 1)    , ,NF NFd B B D d C C D   2)      , ( , )) ( , )NF NFb B d B b B b D d 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         , ,B NF NFSIG b d B B D d 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  4 1,P c c 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 T T Bộ số liệu C FA_ FSCE FA_FPR NF_DBAR 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 17 Bảng 3.3. Độ chính xác phân lớp C4.5 của FA_FSCE, FA_FPR, NF_DBAR T T Bộ số liệu U C FA_ FSCE FA_FPR NF_DBAR R Độ chính xác phân lớp C4.5 (%) R Độ chính xác phân lớp C4.5 (%) R Độ chính xác phân 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 18 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  P C . Nếu 1)    POS ( ) POS ( ) ( ) ( ) P CD D x x  2)      {p}POS ( ) POS ( ) , ( ) ( ) P C D Dp P x 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 4.2. 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 tập thuộc tính P được định nghĩa       {b}POS ( ) POS ( )( ) ( )P PDP DSIG b x x   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 TT  1C 2C 3C D  1c 2c 3c 4c 5c 6c 7c 8c 1d 2d 3d 1u 0.3 0.7 0 0.2 0.7 0.1 0.3 0.7 0.1 0.9 0 2u 1 0 0 1 0 0 0.7 0.3 0.8 0.2 0 3u 0 0.3 0.7 0 0.7 0.3 0.6 0.4 0 0.2 0.8 4u 0.8 0.2 0 0 0.7 0.3 0.2 0.8 0.6 0.3 0.1 5u 0.5 0.5 0 1 0 0 0 1 0.6 0.8 0 6u 0 0.2 0.8 0 1 0 0 1 0 0.7 0.3 19 7u 1 0 0 0.7 0.3 0 0.2 0.8 0.7 0.4 0 8u 0.1 0.8 0.1 0 0.9 0.1 0.7 0.3 0 0 1 9u 0.3 0.7 0 0.9 0.1 0 1 0 0 0 1 Áp dụng F_RSAR1 tìm được một tập rút gọn là   1 3{ , }P C C . 4.3. Phương pháp sinh luật quyế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 sinh luật quyết định từ bảng quyết định mờ đã rút gọn thuộc tính sử dụng khoảng cách Jaccard mờ tính trực tiếp giữa hai tập mờ. Kết quả của phần này được công bố trong công trình [CCN5]. Cho U là tập hữu hạn các đối tượng và các tập mờ  ,A B U . Theo chương 2, khoảng cách Jaccard mờ tính trực tiếp của hai tập mờ được xác định như sau:           min( ( ), ( )) ( , ) 1 1 max( ( ), ( )) A B u U FJ A B u U u uA B D A B u uA B               Cho bảng quyết định mờ   ,DT U C D  . Mỗi phần tử u U được phân vào một lớp  jd D theo một luật quyết định mờ có dạng IF ( iC is  1 1 iT AND AND (kC is  k k iT )) THEN ( D is jd ) Phương pháp sinh luật quyết định từ bảng quyết định mờ bao gồm các bước: - Phân nhóm các đối tượng của bảng quyết định mờ theo giá trị cao nhất của từng biến ngôn ngữ của thuộc tính quyết định. - Tính khoảng cách Jaccard mờ giữa các biến ngôn ngữ của thuộc tính quyết định với các biến ngôn ngữ của các thuộc tính điều kiện theo từng phân nhóm. 20 - Đưa ra các tham số ngưỡng [ , ] [0,1]   phù hợp để sinh ra các luật quyết định. Những luật cần dùng thêm tham số  được xác định như sau: Rule k: IF MF (Rule i) <  And MF (Rule j) <  Then D is kd với MF (Rule i) = MF (Condition Part of Rule i) là giá trị hàm thuộc phần điều kiện của luật i. Khả năng phân lớp dữ liệu của bảng quyết định theo các tập luật quyết định cho mỗi đối tượng là ( )iD d = MF(Rule i) Thuật toán FJ_RBAR: Thuật toán tìm một tập luật quyết định của bảng quyết định mờ đã rút gọn thuộc tính. Đầu vào: Tập rút gọn   1{ ,..., }pP C C của bảng quyết định mờ đã rút gọn thuộc tính và các tham số ngưỡng ,  Đầu ra: Tập luật quyết định Rules. 1. ;Rule  k=0;   1{ ,..., }sD d d ;   1( ) {T ,...,T }k k k k k iT C  ; 2. For each u U Do phân nhóm  jd D ; 3. For each  jd D Do 4. Begin 5. For each  ic C Do 6. Begin 7. Tính  ( , )FJ j iD d c ; 8. If    ( , ) min{ ( )}FJ j i i iD d c AND c T C  Then  W( ) {c }i ic  ; 9. End; // Sinh ra các luật quyết định mờ 10. For each  ( )i ic W c Do  i jRule j c d   ; 11. End; 12. For each Wk C  Do Tính Rule k ; 13. Return Rules; 21 Độ phức tạp tính toán của FJ_RBAR là ( )O C D U , với |C| là số biến ngôn ngữ của tất cả các thuộc tính điều kiện của bảng quyết định, |D| là số biến ngôn ngữ của thuộc tính quyết định, |U| là số đối tượng của bảng dữ liệu. Ví dụ 4.2. Cho bảng quyết định mờ, phân nhóm như ở Bảng 4.2, tìm một tập luật quyết định phân lớp được thực hiện như sau: Bảng 4.2. Bảng quyết định mờ chơi thể thao đã rút gọn thuộc tính TT  1C 3C D  1c 2c 3c 7c 8c 1d 2d 3d Phân nhóm 1 2u 1 0 0 0.7 0.3 0.8 0.2 0 7u 1 0 0 0.2 0.8 0.7 0.4 0 4u 0.8 0.2 0 0.2 0.8 0.6 0.3 0.1 Phân nhóm 2 1u 0.3 0.7 0 0.3 0.7 0.1 0.9 0 5u 0.5 0.5 0 0 1 0.6 0.8 0 6u 0 0.2 0.8 0 1 0 0.7 0.3 Phân nhóm 3 8u 0.1 0.8 0.1 0.7 0.3 0 0 1 9u 0.3 0.7 0 1 0 0 0 1 3u 0 0.3 0.7 0.6 0.4 0 0.2 0.8 - Trong mỗi phân nhóm, tính khoảng cách Jaccard mờ giữa các biến ngôn ngữ của các thuộc tính như ở Bảng 4.3. Bảng 4.3. Khoảng cách Jaccard mờ giữa các biến ngôn ngữ của Bảng 4.2 Quyết định  1C 3C  1c 2c 3c 7c 8c  1d 0.25 0.904762 1 0.47619 0.333333 