Luận án Nghiên cứu phát triển một số thuật toán phân cụm bán giám sát sử dụng mạng Nơ-ron min-max mờ và ứng dụng

if 25 End if 26 End if 27 For  /{ }k jB B B // kiểm tra chồng lấn giữa Bj và   kB B j k 28 For i =1 to n 29 If Có chồng lấn giữa Bj và Bk trên chiều thứ i then 30 Điều chỉnh chồng lấn giữa Bj và Bk theo (1.12)-(1.23) tƣơng ứng 31 End if 32 End for 33 End For 34 If h = m then 35 If s old = s new then tính lại β theo (2.5); 36 h  0; snew  sold; sold  0; m  |D| 37 End if 38 Until (D=). 39 Tính C theo (1.7) End. 40 Thuật toán 2.2 FindBmax Đầu vào Tập siêu hộp B, max, Ah Đầu ra vt FindBmax 1 : 0A  ; bmax  0; vt  0; 2 For Bj  B 3 : 0b  ;   0 4 For i =1 to n 5     1: , ,hi ji ji hib b f a w f v a      //f(x,y) tính theo (1.4) 6        : , ,ji i ji imax w a min v a 7 End for 8 b := b/n; A := /n 9 If (A  max) and (bmax  b) then 10 vt  j; bmax  b 11 End if 12 End for End. Thuật toán 2.3 FindEmax Đầu vào Tập siêu hộp B, ngƣỡng β, mẫu dữ liệu Ah Đầu ra vt FindEmax 1 Emax  0; vt  0 2 For Bj  B 3 E := 0; vt := 0; 4 For i =1 to n 5  : / 2ji ji jic v w  41 6   2 : ji hiE E c a   7 End for 8 1: /E E n  9 If (E  β ) and (E  Emax) then 10 vt  j 11 Emax  E 12 End if 13 End for End. Các kết quả thực nghiệm đƣợc trình bày ở phần 2.4 cho thấy chất lƣợng phân cụm khi áp dụng thuật toán phân cụm bán giám sát mờ SS-FMM cho kết quả tốt hơn so với một số mô hình phân cụm khác (GFMM, RFMN, ). Đặc biệt SS-FMM cho kết quả phân cụm tốt với số ít mẫu trong tập huấn luyện đƣợc gán nhãn. 2.1.3. Đánh giá độ phức tạp thuật toán SS-FMM Mệnh đề 2.1. Thuật toán học SS-FMM có độ phức tạp thời gian là O(M(M-1)/2 + NK). Trong đó M là tổng số mẫu trong tập dữ liệu huấn luyện, N là số thuộc tính của mẫu dữ liệu, K là tổng số siêu hộp tạo ra trong SS-FMM. Chứng minh. Dễ nhận thấy, thuật toán thực hiện 3 vòng lặp lồng nhau. Vòng lặp Repeat (dòng 2 - Thuật toán 2.1), gọi thực hiện chƣơng trình con FindBmax và FindEmax. - Xét vòng lặp Repeat gọi chƣơng trình con FindBmax thực hiện hai vòng For lồng nhau: + Xét vòng For thứ hai (dòng 4 - Thuật toán 2.2): duyệt qua N chiều dữ liệu, do vậy độ phức tạp là T1(N) = O(N) 42 + Xét vòng For nhứ nhất (dòng 2 - Thuật toán 2.2): duyệt qua tập các siêu hộp, gồm K siêu hộp. Do vậy độ phức tạp thời gian T2(K,N) = K.T1(N) = O(KN). + Xét vòng lặp Repeat (dòng 2 - Thuật toán 2.1): duyệt qua M mẫu, do vậy độ phức tạp là T3(M,K,N) = O(MKN) - Xét vòng lặp Repeat gọi chƣơng trình con FindEmax thực hiện hai vòng For lồng nhau. + Xét vòng For thứ hai (dòng 4 - Thuật toán 2.3): duyệt qua N chiều dữ liệu, do vậy độ phức tạp là T4(N) = O(N) + Xét vòng For nhứ nhất (dòng 2 - Thuật toán 2.3): duyệt qua tập các siêu hộp, gồm K siêu hộp. Do vậy độ phức tạp thời gian T5(K,N) = K.T4(N) = O(KN). + Xét vòng lặp Repeat (dòng 2 - Thuật toán 2.1): duyệt qua M mẫu, do vậy độ phức tạp là T6(M,T5(K,N)) = O(MKN) - Xét vòng lặp Repeat có cấu trúc If (dòng 19 đến dòng 24 - Thuật toán 2.1) bỏ qua mẫu không có nhãn trong trƣờng hợp không tạo đƣợc siêu hộp mới cho lần duyệt tiếp theo, do vậy số phép tính cần thực hiện trong trƣờng hợp tồi nhất là mỗi lần duyệt chỉ kết nạp đƣợc 1 mẫu là (M-1)+(M-2)++2+1 = M(M- 1)/2. Độ phức tạp thời gian là T7(M(M-1)/2) = O(M(M-1)/2). Độ phức tạp thời gian của thuật toán SS-FMM là : T(M,N,K) = T7(M(M-1)/2) + T6(M,T5(K,T4(N))) + T3(M,K,N) = O(M(M-1)/2 + MKN + MNK) = O(M((M-1)/2 + NK)).  T(M,N,K) = O(M((M-1)/2 + NK)) (2.6) 2.2. Thuật toán phân cụm bán giám sát mờ kết hợp SCFMN 2.2.1. Ý tưởng thuật toán Thuật toán học trong SS-FMM sinh ra các tập siêu hộp, với mỗi tập siêu hộp là một cụm. SS-FMM sử dụng nhiều siêu hộp với kích thƣớc nhỏ để phân 43 loại các mẫu ở vùng biên. Tuy nhiên, khi giảm tham số max thì số lƣợng siêu hộp trong mạng tăng, làm tăng độ phức tạp thuật toán. Không những vậy, SS- FMM cần có một tỷ lệ mẫu nhất định trong tập huấn luyện đƣợc gán nhãn. Để khắc phục nhƣợc điểm trên của mô hình SS-FMM, nghiên cứu sinh đề xuất một thuật toán kết hợp giữa mô hình SS-FMM và FMNN [64] gọi là SCFMN. SCFMN sử dụng hai giới hạn kích thƣớc max khác nhau trong hai giai đoạn để cải thiện kết quả phân cụm với số lƣợng siêu hộp ít hơn. Ở giai đoạn đầu, SCFMN tạo ra các siêu hộp và gán nhãn cho các mẫu có độ thuộc đầy đủ với các siêu hộp, với mỗi siêu hộp là một cụm. 1 max  xác định kích thƣớc tối đa của các siêu hộp lớn. 2 max  xác định kích thƣớc tối đa của các siêu hộp bé. Ở giai đoạn sau, SCFMN thực hiện quá trình lan truyền các nhãn từ các siêu hộp đƣợc tạo ra trƣớc đó tới các siêu hộp đƣợc tạo ra từ các mẫu không có nhãn. Các siêu hộp lớn và nhỏ có cùng một nhãn kết hợp với nhau hình thành nên các cụm đầy đủ. Hình 2.3 minh họa ý tƣởng sử dụng siêu hộp lớn ở khu vực tâm cụm kết hợp với các siêu hộp nhỏ nhơn ở khu vực biên đƣợc biểu diễn trong không gian 2-chiều khi phân cụm dữ tập dữ liệu gồm hai cụm. Hình 2.3. Cấu trúc SCFMN sử dụng các siêu hộp lớn và nhỏ Trong đó: - B là siêu hộp có kích thƣớc lớn; * Siêu hộp B Siêu hộp R Siêu hộp G * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + * * * * + + + + + 44 - G là siêu hộp có kích thƣớc nhỏ hình thành từ các mẫu có nhãn; - R là các siêu hộp có kích thƣớc nhỏ hình thành từ các mẫu không có nhãn. Hình 2.4 minh họa mô hình lai ghép kết hợp giữa FMNN với học không có giám sát với SS-FMM học bán giám sát để phân loại mẫu. Đầu vào là các tập dữ liệu không có nhãn đi kèm, ngƣời dùng xác định các tham số: số cụm k, tham số mờ , ngƣỡng β, hệ số giảm ngƣỡng . Từ tập dữ liệu đầu vào, sử dụng thuật toán học không giám sát trong FMNN với để phân cụm cho tập dữ liệu. Kết quả của quá trình phân cụm là các cụm với mỗi cụm tƣơng ứng với một siêu hộp. Khi này kết quả nhận đƣợc là các thông tin bổ trợ cho thuật toán SS-FMM với học bán giám sát mờ tiếp theo. Hình 2.4. Lƣợc đồ tổng quan thuật toán SCFMN Thuật toán học gồm 2 pha: - Pha 1: Cung cấp thông tin bổ trợ bằng cách ghi nhãn cho một phần dữ liệu. - Pha 2: Thực hiện phân cụm dữ liệu với các thông tin bổ trợ trong pha 1. Các bƣớc thực hiện của Pha 1 và Pha 2 đƣợc mô tả nhƣ sau: Tập dữ liệu vào Bắt đầu Sử dụng thông tin bổ trợ xác định nhãn và gán nhãn cho một phần dữ liệu trong tập dữ liệu huấn luyện. B ổ t rợ t h ô n g t in Dùng mô hình SS-FMM với thông tin bổ trợ là nhãn (chỉ số của các siêu hộp) đƣợc xác định ở giai đoạn 1. Dùng mô hình FMNN với học không giám sát để xác định thông tin bổ trợ. Kết thúc 45 Đầu tiên, Pha 1 của thuật toán học tạo ra tập gồm C siêu hộp, kích thƣớc tối đa đƣợc xác định bởi tham số 1 max  . Tập các siêu hộp này đƣợc ký hiệu là B    1,..., ,jB B j C C là tổng số các siêu hộp trong tập B tƣơng ứng với C cụm cần hình thành. Nhãn của siêu hộp Bj (ký hiệu l j B ) đƣợc xác định bằng chỉ số j. Để đạt đƣợc C cụm thì phƣơng pháp đƣợc sử dụng là “thử sai” (try error) với các giá trị 1 max  khác nhau. Sau khi hình thành tập các siêu hộp B, thực hiện gán nhãn cho các mẫu dữ liệu bằng nhãn của siêu hộp mà nó thuộc về. Nếu Ah có độ thuộc đầy đủ vào Bj bất kỳ thì nhãn của mẫu Ah đƣợc gán là j, ngƣợc lại thì nhãn của mẫu Ah đƣợc gán là 0. Nhƣ vậy, sau khi Pha 1 kết thúc sẽ có một số lƣợng nhất định các mẫu Ah trong tập dữ liệu huấn luyện đƣợc gán nhãn. Tập mẫu huấn luyện D trong Pha 1 hình thành nên hai tập D1 gồm các mẫu có nhãn và D2 gồm các mẫu không có nhãn. Đây là cơ sở để thực hiện quá trình học bán giám sát ở Pha 2. Pha 2 của thuật toán học tạo ra các tập siêu hộp nhỏ là G và R với kích thƣớc tối đa đƣợc xác định bởi tham số 2 max  . Các siêu hộp trong tập G có đƣợc là do quá trình huấn luyện từ các mẫu có nhãn ở giai đoạn 1, với các mẫu huấn luyện thuộc các siêu hộp B, tập dữ liệu huấn luyện là tập D1. Các siêu hộp trong tập R có đƣợc là do quá trình huấn luyện giai đoạn 2, với các mẫu huấn luyện thuộc tập dữ liệu D2. Các siêu hộp trong tập R đƣợc kết nối với siêu hộp Bj gần nhất với nó để hình thành các cụm đầy đủ. SCFMN kết hợp giữa CFMNN và SS-FMM. CFMNN hình thành các cụm ở giai đoạn đầu và SS-FMM hoàn thiện và tinh chỉnh cụm ở giai đoạn sau. SCFMN chia nhỏ các siêu hộp tại các vùng biên trong quá trình phân cụm để tăng khả năng tìm ranh giới cụm. Do vậy, SCFMN có khả năng phân cụm tốt hơn trên các tập dữ liệu có sự phân bố cụm và hình dạng cụm rõ ràng, dữ liệu của các cụm tập trung, ít bị xen lẫn và không có sự bao nhau giữa các cụm. Tuy nhiên với các tập dữ liệu khác, SCFMN vẫn cho kết quả tốt nếu ở giai đoạn đầu CFMNN có khả năng xác định đƣợc số ít mẫu gần tâm cụm. 46 2.2.2. Thuật toán học trong SCFMN Hình 2.5 là sơ đồ mô phỏng thuật toán học của SCFMN, thuật toán học gồm 2 pha. Pha 1 của thuật toán học gồm hai giai đoạn, giai đoạn 1 tạo ra tập các siêu hộp B, mỗi siêu hộp tƣơng ứng với một cụm, gán nhãn cho Bj  B bằng chỉ số j. Giai đoạn 2 gán nhãn cho các mẫu dữ liệu theo nhãn của Bj  B với các mẫu A thỏa mãn  , 1j jb A B  và tách tập dữ liệu đầu vào D thành D1 và D2. Hình 2.5. Thuật toán học SCFMN Giai đoạn 1 của pha 1 tƣơng tự nhƣ thuật toán học FMNN đƣợc trình bày trong phần 1.1.6. Giai đoạn 2 của pha 1 thực hiện gán nhãn cho các mẫu thuộc siêu hộp và tách tập mẫu D thành hai tập D1 và D2. đ Có chồng lấn siêu hộp? Co lại siêu hộp Dữ liệu vào {Ah ,dh}D s đ Pha 1: Xác định thông tin bổ trợ Tất cả dữ liệu đã có nhãn? s   , : 1,...,h sA Hmax E s q   Kết thúc Pha 2: Sử dụng SS-FMM để phân cụm dữ liệu Ah có thuộc vào BjB? dh = 0? đ l h sd H s s Tạo Hnew, lnew hH d R = R{Hnew} s l h jd B đ Có BjB chứa đƣợc Ah? Mở rộng Bj dh = 0 ? s dh ≠ 0? đ s đ đ s đ s Dữ liệu vào AhD Dữ liệu vào đã hết? Bắt đầu Có BjB chứa đƣợc Ah? Có chồng lấn siêu hộp? Co lại siêu hộp đ s đ Mở rộng hyperbox s Tạo Bj mới, ljB j đ Dữ liệu vào AhD Ah có thuộc vào BjB ? s đ l h jd B D1=D1{Ah,dh} Dữ liệu vào đã hết? s đ 0hd  D2=D2{Ah,dh} D = D1D2 Tạo Hnew, l new hH d G = G{Hnew} 47 Với mỗi mẫu vào hA D , tính độ thuộc ( , )j h jb A B vào các siêu hộp Bj  B. Xét các khả năng sau: - Nếu có bất kỳ một siêu hộp Bj có ( , ) 1j h jb A B  : + Gán nhãn cho Ah là nhãn của Bj  lh jd B . +   1 1 ,h hD D A d . - Nếu không: + Mặc định nhãn của Ah là 0   0hd . +   2 2 , .h hD D A d Quá trình huấn luyện trong pha 2 tƣơng tự nhƣ thuật toán học SS-FMM đƣợc trình bày trong phần 2.1 của luận án. Đầu tiên, các mẫu dữ liệu vào có nhãn 1hA D đƣợc huấn luyện để tạo ra tập các siêu hộp G. Sau đó các mẫu dữ liệu 2hA D đƣợc huấn luyện và học theo các mẫu có nhãn trong tập D1 tạo ra tập các siêu hộp R. Pha 2 của thuật toán học SCFMN gồm hai giai đoạn: - Giai đoạn 1 của pha 2 tạo ra tập các siêu hộp G     11,2,...,yG G y C . Nhãn của các siêu hộp đƣợc gán theo nhãn của các mẫu huấn luyện. - Giai đoạn 2 của pha 2 tạo ra tập các siêu hộp R     21,2,...,iR R i C và thực hiện lan truyền nhãn từ tập siêu hộp G sang tập siêu hộp R. Cơ chế lan truyền nhãn thực hiện bằng cách lan truyền nhãn từ các siêu hộp trong tập G sang các siêu hộp trong tập R. Thuật toán thực hiện một lần duyệt qua các mẫu trong tập dữ liệu D2, tạo ra các siêu hộp iR R . Thuật toán học gán nhãn cho các siêu hộp trong tập R theo nhãn của các siêu hộp trong tập G và các siêu hộp đã đƣợc gán nhãn trong tập R. Thuật toán học dừng khi tất cả các mẫu đƣợc gán nhãn. Tập các siêu hộp đƣợc huấn luyện bởi SCFMN ở đầu ra bao gồm tất cả các siêu hộp thuộc tập siêu hộp B và tập siêu hộp R  B R . 48 Khi đó, quá trình phân cụm dữ liệu của SCFMN đƣợc mô tả thông qua Thuật toán 2.4. Thuật toán 2.4 SCFMN Đầu vào Tập dữ liệu D, max,  , β, , số cụm C. Đầu ra Tập các siêu hộp SCFMN 1 FMNN 2 For Ah  D 3 If bj(Ah,Bj) = 1 then 4 : lh jd B ; D1  D1{Ah,dh} 5 Else 6 : 0hd  ; D2  D2{Ah,dh} 7 End if 8 End for 9 D  D1  D2 10 SS-FMM End. Thuật toán 2.5 FMNN Đầu vào Tập dữ liệu D, max,  , β, , số cụm C. Đầu ra Tập các siêu hộp SCFMN 1 1  1; 2 Repeat 3 j  0; 1  1 *  4 For Ah  D 5 FindBmax(Ah, B,max, vt, bmax) 6 If vt != 0 then 7 Tính new vjV theo (1.26); 49 tính new vjW theo (1.27) 8 Else 9 j  j+1; Tạo siêu hộp Bj mới 10 End if 11 For  /{ }k jB B B // kiểm tra chồng lấn giữa Bj và   kB B j k 12 For i =1 to n 13 If Có chồng lấn giữa Bj và Bk trên chiều thứ i then 14 Điều chỉnh chồng lấn giữa siêu hộp Bj và siêu hộp Bk theo (1.14)-(1.25) 15 End if 16 End for 17 End For 18 End for 19 Until j = C // dừng khi số siêu hộp bằng số cụm End. 2.2.3. Đánh giá độ phức tạp thuật toán SCFMN Mệnh đề 2.2. Thuật toán học SCFMN có độ phức tạp thời gian là O(KN(M(K+1)+1)+M(M-1)/2). Trong đó M là tổng số mẫu trong tập dữ liệu huấn luyện, N là số thuộc tính của mẫu dữ liệu, K là tổng số siêu hộp tạo ra trong SCFMN. Chứng minh. Dễ nhận thấy, thuật toán thực hiện 3 vòng lặp lồng nhau, xét các trƣờng hợp sau: - Dòng lệnh 1 gọi chƣơng trình con FMNN: + FMNN gọi chƣơng trình con FindBmax (dòng 5 – Thuật toán 2.5) có độ phức tạp là T5(M,K,N)= O(MKN). + Xét vòng For thứ 4 (dòng 12 - Thuật toán 2.5) duyệt qua tập thuộc tính của dữ liệu, do đó độ phức tạp thời gian đƣợc xác định là T4(N) = O(N). 50 + Xét vòng For thứ 3 (dòng 11 - Thuật toán 2.5) duyệt qua tập các siêu hộp, do đó độ phức tạp thời gian đƣợc xác định là T3(K). T4(N) = O(NK). + Xét vòng For thứ 2 (dòng 4 - Thuật toán 2.5) duyệt qua các mẫu trong tập huấn luyện, do đó độ phức tạp thời gian đƣợc xác định là T2(M).T3(K). T4(N) = O(MNK). + Xét vòng lặp Repeat (dòng 4 - Thuật toán 2.5) duyệt qua tập các siêu hộp hình thành nên K siêu hộp, độ phức tạp thời gian đƣợc xác định là: T1(K).(T2(M).T3(K). T4(N) + T5(M,K,N)) = O(KMNK + MKN) = O(MKN(K+1)). - Dòng lệnh 3 thực hiện tính độ thuộc của mẫu vào Ah so với các siêu hộp BjB : để tính độ thuộc, cần hai vòng lặp For lồng nhau, vòng lặp ngoài duyệt qua K siêu hộp. Vòng lặp trong duyệt qua N chiều dữ liệu, do vậy độ phức tạp là T6(K,N) = O(KN). - Dòng lệnh 10 gọi chƣơng trình SS-FMM, độ phức tạp thời gian: T7(M,K,N) = O(M((M-1)/2 + KN)) (theo 2.6) Vậy, độ phức tạp thời gian thuật toán SCFMN là: T(M,K,N) = T1 + T6 + T7 = O(MKN(K+1)) + O(KN) + O(M((M-1)/2 + KN)) = O(MKN(K+1)+KN+ M((M-1)/2 + KN)) = O(KN(M(K+1)+1)+M(M-1)/2).  T(M,K,N) = O(KN(M(K+1)+1)+M(M-1)/2). (2.7) 2.3. Thuật toán phân cụm mờ dựa trên tâm cụm dữ liệu CFMNN 2.3.1. Ý tưởng thuật toán Trong giai đoạn dự báo của FMNN [64], các mẫu đƣợc phân loại dựa trên các giá trị hàm thuộc và mẫu sẽ thuộc về siêu hộp có giá trị hàm thuộc cao nhất. Tuy nhiên giá trị hàm thuộc trong FMNN không giảm dần khi mẫu rời xa siêu hộp. Có nghĩa là độ thuộc không giảm dần khi khoảng cách giữa mẫu và siêu hộp tăng. Hình 2.6. là một ví dụ minh họa quá trình dự đoán không chính xác 51 của mô hình FMNN với siêu hộp Bj có điểm min Vj = (0.2,0.2), điểm max Wj=(0.4,0.3). Minh họa trên Hình 2.6 cho thấy, ngay cả đối với các mẫu nằm xa siêu hộp (mẫu A1), độ thuộc của mẫu vào siêu hộp vẫn đạt giá trị lớn hơn so với mẫu ở gần (mẫu A2). Độ thuộc giảm dần đều khi giá trị hàm thuộc lớn hơn 0.6, Ngƣợc lại, khi độ thuộc nhỏ hơn 0.6, giá trị hàm thuộc không còn giảm dần khi mẫu rời xa siêu hộp. Hình 2.6. Giá trị dự đoán sai của FMNN Không những vậy, FMNN bỏ sót các trƣờng hợp phát hiện chồng lấn giữa các siêu hộp (nhƣ đã trình bày ở mục 1.2.3). Các mẫu rơi vào vùng chồng lấn giữa siêu hộp sẽ có giá trị hàm thuộc đầy đủ nhƣ nhau, khi này FMNN thực hiện phân loại một cách ngẫu nhiên. Điều này làm giảm hiệu suất của FMNN. CFMNN (Centroid-based FMNN) là phƣơng pháp mới đƣợc đề xuất khắc phục các nhƣợc điểm trên: - Thứ nhất là sử dụng tập 10 luật mới để chỉ ra và hiệu chỉnh các siêu hộp bị chồng lấn trong quá trình huấn luyện. - Thứ hai là dựa trên khoảng cách tƣơng ứng giữa các mẫu vào và tâm của siêu hộp khi mẫu rời xa siêu hộp. Giá trị tâm hình học đƣợc tính đến khi mẫu rời xa siêu hộp và độ thuộc nhỏ hơn 0.6, khi mà giá trị hàm thuộc của FMNN không giảm dần. Mỗi siêu hộp tƣơng ứng có tâm của siêu hộp tính theo (2.8). 52 , 2 ji ji ji v w c   (2.8) với cji là tâm hình học của siêu hộp thứ j theo chiều thứ i, vji và wji là 2 điểm min, max của siêu hộp thứ j theo chiều thứ i. Với mỗi mẫu vào A thỏa mãn điều kiện gới hạn kích thƣớc (1.24) mà độ thuộc bj < 0.6, giá trị  , jA B E đƣợc tính toán và so sánh.  , jA B E đƣợc tính toán dựa trên tâm hình học của các siêu hộp. Mẫu vào Ah sẽ thuộc vào siêu hộp nào có  , jA B E đạt max. Điều này có nghĩa, việc điều chỉnh các điểm min, điểm max của siêu hộp thuật toán học trong CFMNN không những phụ thuộc vào hàm thuộc bj và còn phụ thuộc tâm hình học siêu hộp tùy theo điều kiện cụ thể. Tâm hình học của siêu hộp chỉ đƣợc tính toán khi có điều kiện phụ xảy ra. Giá trị  , jA B E đƣợc tính toán dựa trên khoảng cách Euclidean giữa mẫu vào A và tâm hình học của siêu hộp tƣơng ứng,  , jA B E đƣợc tính theo (2.9).     2 , 1 1 1 . j n ji iA B i E c a n     (2.9) Hình 2.7 mô phỏng trƣờng hợp so sánh khoảng cách giữa mẫu vào A với hai siêu hộp. C1 là tâm hình học của siêu hộp 1, C2 là tâm hình học của siêu hộp 2. c1, c2 là khoảng cách Euclidean giữa mẫu vào với tâm hình học của siêu hộp 1, 2 tƣơng ứng. Vì c1 > c2 dẫn tới  2,A BE đạt max, mẫu vào đƣợc đƣa vào siêu hộp 2 (mở rộng siêu hộp 2). Hình 2.7. So sánh khoảng cách mẫu vào với tâm của siêu hộp của CFMNN Mẫu vào V1 W1 V2 W2 C2 c1 c2 53 Ngoài ra, để tăng hiệu suất phân cụm, thay vì sử dụng 4 trƣờng hợp chồng lấn [63], thuật toán học của CFMNN sử dụng tập 10 luật mới để chỉ ra và hiệu chỉnh các siêu hộp bị chồng lấn trong quá trình huấn luyện. Các trƣờng hợp xảy ra chồng lấn: • Trƣờng hợp 1: ji ki ji kiv v w w   • Trƣờng hợp 2: ki ji ki jiv v w w   • Trƣờng hợp 3: ji ki ki jiv v w w   • Trƣờng hợp 4: ki ji ji kiv v w w   • Trƣờng hợp 5: ji ki ji kiv v w w   • Trƣờng hợp 6: ji ki ji kiv v w w   • Trƣờng hợp 7: ki ji ki jiv v w w   • Trƣờng hợp 8: ki ji ki jiv v w w   • Trƣờng hợp 9: ji ki ji kiv v w w   • Trƣờng hợp 10: ki ji ki jiv v w w   CFMNN sinh ra và tinh chỉnh các siêu hộp, với mỗi siêu hộp là một cụm. Do vậy, CFMNN có khả năng phân cụm tốt hơn trên các tập dữ liệu có sự phân bố cụm và hình dạng cụm rõ ràng, dữ liệu của các cụm tập trung, ít bị xen lẫn và không có sự bao nhau giữa các cụm. CFMNN sử dụng mỗi nút trong lớp thứ hai là một cụm, hay nói cách khác mỗi siêu hộp ở đầu ra là một cụm, do vậy khả năng tìm ranh giới cụm bị hạn chế. 2.3.2. Thuật toán học trong CFMNN Quá trình phân cụm dữ liệu của CFMNN đƣợc mô tả thông qua Thuật toán 2.6. 54 Thuật toán 2.6 CFMNN Đầu vào D, tham số mờ , giới hạn kích thƣớc max. Đầu ra Tập các siêu hộp CFMNN 1 For Ah  D 2 : 0A  ; bmax  0; vt  0; Emax  0; vte  0; 3 For Bj  B 4 : 0b  ;   0 ; 5 For i =1 to n 6     1: , ,hi ji ji hib b f a w f v a      ; //f(x,y) tính theo (1.4) 7         ,: ,ji i ji imax w a min v a ; 8    2 : / 2ji ji hiE E v w a    ; 9 End for 10 b  b/n; A  /n; 1: /E E n  ; 11 If (A  max) and (bmax  b) then 12 vt := j; bmax := b; 13 If (bmax  0.6) and (Emax < E) then 14 Emax  E; vte  j; 15 End if 16 End if 17 End for 18 If vt != 0 then 19 If bmax  0.6 then 20 Tính newvtV theo (1.26), tính new vtW theo (1.27) 21 Else 22 Tính e new vtV theo (1.26), tính e new vtW theo (1.27) 23 End 24 Else 55 25 Tạo siêu hộp Bnew 26 End if 27 For  /{ }k jB B B // kiểm tra chồng lấn giữa Bj và   kB B j k 28 For i =1 to n 29 If Có chồng lấn giữa Bj và Bk trên chiều thứ i then 30 Điều chỉnh chồng lấn giữa Bj và Bk 31 End if 32 End for 33 End For 34 End for End. 2.3.3. Đánh giá độ phức tạp thuật toán CFMNN Mệnh đề 2.1. Thuật toán học CFMNN có độ phức tạp thời gian là O(MKN). Trong đó M là tổng số mẫu trong tập dữ liệu huấn luyện, N là số thuộc tính của mẫu dữ liệu, K là tổng số siêu hộp tạo ra trong mạng CFMNN. Chứng minh: Dễ nhận thấy, thuật toán thực hiện 3 vòng lặp lồng nhau (dòng 1, 3, 5; dòng 1, 27, 28). - Xét vòng For thứ 3 (dòng 5): cần duyệt theo số chiều của mẫu dữ liệu, do đó độ phức tạp thời gian đƣợc xác định là T3(N) = O(N). Tƣơng tự với vòng For thứ 5 (dòng 28), ta có T5(N) = O(N). - Xét vòng For thứ 2 (dòng 3): cần duyệt theo số siêu hộp trong tập B, do đó độ phức tạp thời gian đƣợc xác định là T2(K) = K.T3(N) = O(KN). Tƣơng tự với vòng For thứ 4 (dòng 27), ta có T4(K) = K.T5(N) = O(KN) - Xét vòng For thứ 1 (dòng 1): dễ nhận thấy, cần phải duyệt qua tất cả các siêu hộp 2 lần, lần thứ nhất (dòng 3) và lần thứ 2 (dòng 27) để tính độ thuộc và kiểm tra chồng lấn giữa các siêu hộp. Do vậy, độ phức tạp T(M,K,N) = M(T2(K,N)+T4(K,N)) = O(M(KN+KN)) = O(MKN).  T(M,K,N) = O(MKN). (2.10) 56 2.4. Thực nghiệm và đánh giá 2.4.1. Phương pháp thực nghiệm 2.4.1.1. Tập dữ liệu thực nghiệm Để đánh giá hiệu năng của thuật toán đề xuất, nghiên cứu sinh tiến hành thực nghiệm với các tập dữ liệu chẩn (Benchmark) từ kho dữ liệu học máy UCI [77], CS [78]. Các tập dữ liệu từ CS bao gồm: Aggregation, Flame, Spiral, Jain, R15, Pathbased, Thyroidnew. Các tập dữ liệu từ UCI bao gồm: Iris, Wine, PID (Pima Indian Diabetes), Thyroid, Sonar. Thông tin về các tập dữ liệu đƣợc trình bày trên Bảng 2.1. Bảng 2.1. Thông tin các tập dữ liệu thực nghiệm Benchmark TT Tập dữ liệu Số mẫu Số thuộc tính Số nhóm 1 Aggregation 788 2 7 2 Flame 240 2 2 3 Iris 150 4 3 4 Jain 373 2 2 5 R15 600 2 15 6 Spiral 312 2 3 7 Sonar 208 60 2 8 Pathbased 317 2 3 9 PID 768 8 2 10 Thyroid 7200 21 3 11 Thyroidnew 215 5 3 12 Wine 178 13 3 Các tập dữ liệu thực nghiệm đƣợc chẩn hóa trƣớc khi tiến hành thực nghiệm. Với các tập dữ liệu bị thiếu thông tin (missing values) đƣợc xử lý tƣơng tự Batista [9]. Các thông tin bị thiếu đƣợc tính bằng giá trị trung bình trên thuộc tính tƣơng ứng theo công thức (2.11): 57 1 , m hj ij i A A m   (2.11) trong đó Ahj là đặc trƣng thứ j của mẫu vào thứ h, m là tổng số mẫu trong tập dữ liệu. 2.4.1.2. Mục tiêu và phương pháp thực nghiệm Mục tiêu thực nghiệm đánh giá khả năng cải thiện hiệu năng, số lƣợng và sự phân bố các siêu hộp khi điều chỉnh tham số max của các thuật toán SS-FMM, CFMNN, SCFMN và thay đổi tỉ lệ mẫu có nhãn (SoL) trong tập dữ liệu huấn luyện của SS-FMM. Đánh giá khả năng giảm thiểu siêu hộp của SCFMN so với SS-FMM và các đề xuất trƣớc đó. So sánh hiệu năng của SS-FMM, CFMNN, SCFMN so với một số phƣơng thức khác. Các tham số lựa chọn bao gồm: tham số mờ  = 10, ngƣỡng ban đầu của β = 0.99, hệ số giảm ngƣỡng  = 0.9. Thực nghiệm sử dụng phƣơng pháp kiểm tra chéo “k-fold cross- validation”, với k = 10 để đánh giá, cụ thể nhƣ sau: - Tập dữ liệu đƣợc chia ngẫu nhiên thành 10 tập con không giao nhau (k-fold) có kích thƣớc xấp xỉ nhau. - Tiến hành kiểm tra 10 lần, với mỗi lần thực nghiệm tập kiểm thử đƣợc thay đổi và 9 tập con còn lại đƣợc sử dụng để huấn luyện. - Kết quả thực nghiệm là trung bình cộng của 10 lần thực nghiệm. 2.4.1.3. Độ đo và tiêu chí đánh giá kết quả Thực nghiệm đƣợc tiến hành trên máy tính có bộ xử lý Intel CoreTM i3 3.40 GHz với RAM 4GB trên MATLAB R2014a 64bit. Thực nghiệm sử dụng phƣơng pháp đánh giá ngoài, kết quả phân cụm đƣợc đánh giá dựa tập dữ liệu Benchmark. 58 Các độ đo Accuracy và hệ số tƣơng quan CCC (Cophenetic Correlation Coefficient) đƣợc sử dụng để đánh giá hiệu năng của các thuật toán và so sánh với các thuật toán khác. Độ đo Accuracy đƣợc tính theo công thức (2.12) [74]. Giá trị của độ đo Accuracy càng lớn càng tốt. Giả sử xi là mẫu dữ liệu thuộc tập dữ liệu, yi là nhãn thực sự của xi, iy là các nhãn tƣơng ứng của xi theo kết quả gom cụm.      1 1 , n i i i Acc H y y n uracy (2.12) trong đó H(y) = 1 nếu i iy y , ngƣợc lại H(y) = 0 nếu i iy y , n là tổng số mẫu trong tập kiểm tra. Độ đo CCC đƣợc tính theo công thức (2.13) [58], giá trị CCC càng gần 1 càng tốt.       