Tóm tắt Luận án Nghiên cứu một số thuật toán đồng phân cụm mờ cải tiến trong xử lý dữ liệu ảnh

u cầu đặt ra đối với các kỹ thuật phân cụm về thông tin đầu vào và đầu ra ngày càng cao hơn, phức tạp hơn. 1.2. Thuật toán phân cụm mờ Kết hợp giữa Tập mờ với các kỹ thuật phân cụm đã hình thành các kỹ thuật phân cụm mờ để nâng cao khả năng nhận biết các vấn đề không rõ ràng. Các kỹ thuật phân cụm mờ được phân loại như chỉ ra trong hình 1.3. Hình 1.3: Sơ đồ phân loại các thuật toán phân cụm mờ Nói chung, việc kết hợp Tập mờ, các thuật toán Phân cụm mờ đã đạt được chất lượng cụm tốt hơn so với một số thuật toán phân cụm rõ. Tuy nhiên, thuật toán phân cụm mờ còn tồn tại một số hạn chế khi tiến hành phân cụm trên các loại dữ liệu đa chiều, nhiều đặc trưng. Để khắc phục hạn chế này, gần đây thuật toán đồng phân cụm mờ đã được phát triển. 1.3. Những vấn đề nghiên cứu của luận án 1.3.1. Mô hình phân cụm dữ liệu Để xác định các vấn đề nghiên cứu cụ thể, luận án biểu diễn quy trình phân cụm dưới dạng mô hình phân cụm chi tiết, như chỉ ra trong hình 1.6. Các kỹ thuật phân cụm mờ Phân cụm mờ trọng số Phân cụm mờ bán giám sát Phân cụm mờ dựa trên nhân Thuật toán Phân cụm mờ Phân cụm mờ trực cảm Đồng phân cụm mờ trọng số Đồng phân cụm mờ giảm chiều Đồng phân cụm mờ bán giám sát Thuật toán Đồng phân cụm mờ Đồng phân cụm mờ loại 2 Phân cụm mờ loại 2 5 Hình 1.6: Mô hình phân cụm dữ liệu sử dụng thuật toán phân cụm mờ 1.3.2. Nghiên cứu nâng cao chất lượng đồng phân cụm mờ 1.3.3. Nghiên cứu xác định tâm cụm khởi tạo cho đồng phân cụm mờ 1.3.4. Nghiên cứu xác định số cụm tối ưu 1.3.5. Nghiên cứu các kỹ thuật giảm đặc trưng dữ liệu 1.3.6. Nghiên cứu để tăng tốc đồng phân cụm mờ 1.3.7. Nghiên cứu các phương pháp đánh giá trong phân cụm 1.4. Cơ sở toán học của luận án 1.4.1. Thuật toán Phân cụm mờ FCM là thuật toán phân cụm mờ phổ biến nhất đã được cải tiến và áp dụng trong nhiều ứng dụng khác nhau. Hàm mục tiêu của FCM được cho bởi công thức (1.4). 2 1 1 ( ; ; ) C N m FCM ci ci c i J U P X u d    (1.14) Dữ liệu Xác định tâm cụm khởi tạo Phân cụm dữ liệu Đánh giá chất lượng phân cụm và hợp nhất các cụm Hiển thị kết quả Cụm 1 Kết quả đánh giá cụm Kết quả hợp nhất các cụm Cụm 2 Cụm C Tiền xử lý dữ liệu Xác định số cụm Pha 1 Pha 2 Pha 3 6 1.4.2. Thuật toán đồng phân cụm mờ FCoC Thuật toán FCoC là một kỹ thuật mở rộng của FCM, được sử dụng để phân cụm dữ liệu đa chiều, nhiều đặc trưng. Hàm mục tiêu của thuật toán đồng phân cụm mờ JFCoC được biểu diễn bởi công thức sau: 1 1 1 1 1 1 1 ( , , ) log log C N D C N C D FCoC ci cj cij U ci ci V cj cj c i j c i c j J U V P u v d T u u T v v             (1.16) Các nghiên cứu FCoC gần đây mới chỉ nghiên cứu và ứng dụng trong phân loại dữ liệu văn bản và phân đoạn ảnh mầu. FCoC còn hạn chế như nhạy cảm với khởi tạo tâm cụm; độ phức tạp tính toán cao. 1.4.3. Thuật toán tối ưu bầy đàn trong mô hình đồng phân cụm mờ Thuật toán tối ưu bầy đàn PSO là một thuật toán sử dụng trí tuệ bầy đàn [49] để mô phỏng theo ý tưởng hành vi bầy đàn của các loài chim. Thuật toán này được coi là một thuật toán đa năng vì nó có thể được áp dụng trong nhiều mô hình ứng dụng khác nhau. Trong luận án này, thuật toán PSO được cải tiến và ứng dụng để khởi tạo tâm cụm thay thế phương pháp khởi tạo tâm cụm ngẫu nhiên. 1.5. Kết luận chương 1 Từ tổng quan về đồng phân cụm mờ cho thấy phân cụm nói chung và đồng phân cụm mờ nói riêng là một kỹ thuật quan trọng trong khai phá dữ liệu. Những nghiên cứu gần đây đã chứng tỏ tính hiệu quả của FCoC trong việc giải quyết các bài toán phân cụm dữ liệu đa chiều, nhiều đặc trưng và được ứng dụng trong QP&AN, y tế và sinh học, khai thác khoáng sản, Tuy nhiên, FCoC gần đây mới chỉ được ứng dụng để phân loại dữ liệu website, văn bản và ảnh mầu. FCoC chưa đề cập đến dữ liệu có số đặc trưng lớn hơn và phức tạp hơn như ảnh đa phổ và ảnh siêu phổ. Ngoài ra, FCoC còn nhạy cảm với khởi tạo tâm cụm, số cụm tối ưu và giảm đặc trưng dữ liệu. Nội dung tiếp theo của luận án sẽ tập trung xây dựng các thuật toán đồng phân cụm mờ cải tiến để nâng cao chất lượng và ổn định đồng phân cụm mờ. Đề xuất phương pháp đánh giá xu hướng cụm và kỹ thuật giảm đặc trưng mới để xác định số cụm tối ưu và phân tích dữ liệu ảnh siêu phổ. 7 Chương 2 MỘT SỐ TIẾP CẬN CẢI TIẾN NÂNG CAO CHẤT LƯỢNG VÀ TĂNG TỐC ĐỒNG PHÂN CỤM MỜ 2.1. Thuật toán đồng phân cụm mờ giá trị khoảng Trong khai phá dữ liệu, không phải lúc nào chúng ta cũng có thể trích xuất được tri thức thực sự trong một bộ dữ liệu. Do vậy, đã hình thành nên các bài toán nhận dạng mờ bằng cách mô hình hóa dữ liệu bởi các kỹ thuật mờ. IVFs [75] là một trường hợp đặc biệt của Tập mờ loại 2 khoảng. IVFs được xem như dễ cài đặt và có độ phức tạp tính toán thấp hơn Tập mờ loại 2 khoảng. Trong mục này, luận án đề xuất thuật toán đồng phân cụm mờ giá trị khoảng, ký hiệu là IVFCoC. Bằng cách tích hợp các kỹ thuật của IVFs để xây dựng hàm mục tiêu mới cho đồng phân cụm. 2.1.1. Cơ sở thuật toán IVFCoC Thuật toán IVFCoC được xây dựng bằng cách mở rộng hàm mục tiêu đồng phân cụm mờ tổng quát GFCoC: 1 1 1 1 1 1 1 ( , , ) log log C N D C N C D m m m m m m GFCoC ci cj cij U ci ci V cj cj c i j c i c j J U V P u v d T u u T v v             (2.2) Sử dụng hai tham số mờ m1, m2 để tạo thành vùng không rõ ràng (FOU), tương ứng với các giá trị cận trên và cận dưới của đồng phân cụm mờ giá trị khoảng để đưa ra các hàm mục tiêu khác nhau cần được tối thiểu như sau: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ( , , log log C N D C N C D m m m m m m m ci cj cij u ci ci v cj cj c i j c i c j J U V P u v d T u u T v v             (2.4) 2 2 2 2 2 2 2 1 1 1 1 1 1 1 ( , , ) log log C N D C N C D m m m m m m m ci cj cij u ci ci v cj cj c i j c i c j J U V P u v d T u u T v v             (2.5) Định lý và bổ đề sau được sử dụng để xác định các thành phần của (2.4) và (2.5). Định lý 2.1. 1m J công thức (2.4) và 2m J trong công thức (2.5) đạt được cực tiểu cục bộ khi 1 1( ) ( )ci x m m C N U u    , 2 2( ) ( ) ci x m m C N U u    , 1 1( ) ( ) cj x m m C D V v    , 2 2( ) ( ) cj x m m C D V v    , 1 1( ) ( ) cj x m m C D P p    và 2 2( ) ( ) cj x m m C D P p    thỏa mãn các công thức (2.6)- 8 (2.11). Trong đó c = 1, 2, , C, i=1, 2, , N, j = 1, 2, , D, C tương ứng là số cụm, N là số mẫu và D là số đặc trưng. Bổ đề 2.1. Cho ( ) ( ) ( )1 1 1( ) ( , )1 m m mU J U Vm  , ( ) ( ) ( )2 2 2( ) ( , )2 m m mU J U Vm  trong đó ( )( ) 11 ci mmU u CxN      và ( )( ) 22 ci mmU u CxN      thỏa mãn các điều kiện ràng buộc ( )1 1 1 C m uci c   và ( )2 1 1 C m uci c   (với i=1, 2,..., N), chúng ta có dcij>0, m2>m1>1 thì ( )1mU là tối ưu cục bộ của ( )1( )mU và ( )2mU là tối ưu của ( )2( )mU , nếu và chỉ nếu ( )1muci và ( )2muci (với c=1, 2,..., C và i=1, 2,..., N) tương ứng được tính toán bởi (2.6) và (2.7). Thuật toán IVFCoC bao gồm các bước lặp để cập nhật các thành phần của hàm mục tiêu, như sau: Thuật toán 2.1: Thuật toán đồng phân cụm mờ giá trị khoảng IVFCoC Đầu vào: Dữ liệu  , , =1..Di iX x x R i N  , số cụm C, các tham số mờ 1 2 1 2 ,(, ) , , 1u vT T m m m m    ε, số vòng lặp tối đa τmax. Đầu ra: C cụm kết quả. 1. Khởi tạo: Ma trận hàm thuộc U=[uci] thỏa mãn ràng buộc (2.3), ci ci ciu u u  , τ=1. 2. DO 3. Cập nhật ,L Rcj cjp p và pcj sử dụng (2.36), (2.37) và (2.38); 4. Tính toán dcij sử dụng (2.1); 5. Cập nhật ,cj cjv v và vcj sử dụng (2.33), (2.34) và (2.35); 6. Cập nhật ,ci ciu u và uci sử dụng (2.30), (2.31) và (2.32); 7. τ=τ+1; 8. UNTILL (( ( [ ] [ 1]) )|| (= ))ci ci MaxMax u u      . Độ phức tạp tính toán của IVFCoC là O(CD 2 Nτ). 2.1.2. Kết quả thực nghiệm Trong mục này, luận án tiến hành một số thực nghiệm trên ảnh mầu, dữ liệu nhiều đặc trưng và ảnh đa phổ để chứng tỏ hiệu quả của IVFCoC. Kết quả thực nghiệm có trong các hình 2.2-2.3 và các bảng 2.1-2.3. 9 Bảng 2.1: Kết quả phân cụm trên các ảnh mầu theo các chỉ số đánh giá Thuật toán PC PE MS E IQI DB-I XB-I  1 9 0 2 1 FCM 0,56 0,371 25,3 0,9 0,78 0,47 18 FCoC 0,96 0,014 26,7 0,79 0,77 0,42 15 IVFCoC 0,98 0,013 22,3 0,96 0,76 0,40 8 2 1 0 0 8 8 FCM 0,62 0,307 24,6 0,91 0,74 0,40 20 FCoC 0,97 0,012 25,3 0,93 0,73 0,46 17 IVFCoC 0,98 0,012 23,2 0,95 0,73 0,44 9 2 1 6 0 8 1 FCM 0,52 0,387 45,6 0,86 0,67 0,44 18 FCoC 0,86 0,003 42,6 0,8 0,56 0,32 14 IVFCoC 0,99 0,002 34,3 0,95 0,67 0,39 7 2 2 0 0 7 5 FCM 0,58 0,337 34,5 0,88 0,77 0,48 19 FCoC 0,94 0,010 35,9 0,81 0,78 0,49 14 IVFCoC 0,98 0,007 30,8 0,95 0,77 0,47 8 2 4 1 0 0 4 FCM 0,78 0,196 20,9 0,98 0,48 0,27 17 FCoC 0,83 0,003 36,3 0,92 0,49 0,25 12 IVFCoC 0,99 0,002 18,5 0,99 0,49 0,25 6 Hình 2.2: Kết quả phân cụm trên các ảnh mầu 10 Bảng 2.2: Kết quả phân cụm sử dụng sau bộ dữ liệu đa chiều Thuật toán PC PE MSE IQI DB-I XB-I Prec. Rec.  D im 2 5 6 FCM 0,80 0,095 19,1 0,75 0,97 0,62 0.79 0.82 27 FCoC 0,90 0,046 8,2 0,97 0,91 0,49 0.97 0.96 18 IVFCoC 0,98 0,008 0,7 0,99 0,88 0,44 0.98 0.99 15 D im 5 1 2 FCM 0,78 0,151 11,2 0,86 1,20 0,47 0.91 0.93 17 FCoC 0,93 0,037 6,4 0,98 0,93 0,43 0.93 0.95 13 IVFCoC 0,92 0,048 0,8 0,99 0,83 0,35 0.99 0.98 10 D im 1 0 2 4 FCM 0,75 0,169 21,1 0,72 0,95 0,59 0.85 0.82 19 FCoC 0,95 0,023 7,0 0,98 0,84 0,59 0.96 0.93 15 IVFCoC 0,95 0,022 3,9 0,99 0,78 0,52 0.98 0.99 12 Hình 2.3. Kết quả phân lớp ảnh về tinh đa phổ: a) NDVI; b) Thuật toán FCM; c) Thuật toán FCoC; d) Thuật toán IVFCoC. 11 Bảng 2.3: Kết quả phân lớp ảnh vệ tinh đa phổ sử dụng các thuật toán phân cụm FCM, FCoC và IVFCoC theo các chỉ số đánh giá Thuật toán PC PE MSE IQI DB-I XB-I  FCM 0,21 0,583 5,7 0,83 0,93 0,82 25 FCoC 0,97 0,014 5,6 0,85 0,89 0,80 17 IVFCoC 0,98 0,008 4,7 0,91 0,75 0,68 11 2.1.3. Phân tích và đánh giá thuật toán IVFCoC Theo kết quả thực nghiệm cho thấy, bằng sự kết hợp giữa IVFs với FCoC, thuật toán IVFCoC đã nâng cao khả năng nhận biết các vấn đề không rõ ràng trong dữ liệu nhiều đặc trưng để đạt được hiệu suất tốt hơn so với các thuật toán phân cụm mờ FCM và FCoC. 2.2. Thuật toán đồng phân cụm mờ lai ghép Để khắc phục hạn chế về nhạy cảm với khởi tạo tâm cụm. Trong mục này, thuật toán đồng phân cụm mờ lai ghép (MHFCoC) đã được đề xuất bằng cách lai ghép thuật toán PSO với thuật toán FCoC. Đồng thời, để tăng tốc phân cụm, thuật toán MHFCoC được cài đặt song song trên bộ xử lý đồ hoạ GPU. 2.2.1. Thuật toán tối ưu bầy đàn Trong mục này, thuật toán PSO được sử dụng để tìm tâm cụm khởi tạo cho thuật toán FCoC. Để nâng cao hiệu suất của thuật toán PSO, luận án đã đề xuất thay thế điều kiện dừng mới có độ phức tạp tính toán thấp hơn. Bằng cách sử dụng chỉ số đánh giá chất lượng cụm PC thay thế hàm mục tiêu JFCoC trong công thức hàm thích nghi như sau: 2 1 1 1 ( ) C N ci c i N f X PC u      (2.39) 2.2.2. Thuật toán đồng phân cụm mờ Nhằm nâng cao chất lượng và độ ổn định đồng phân cụm, mục này đề xuất sử dụng điều kiện dừng mới cho thuật toán FCoC. 2.2.3. Sơ đồ thuật toán MHFCoC Các bước của thuật toán MHFCoC được chỉ ra trong thuật toán 2.2. 12 Thuật toán 2.2. Thuật toánMHFCoC Đầu vào: Bộ dữ liệu  , , i=1,Di iX x x R N  , Phân bố PSO   ( ) ,1 ,2 ,K, ( , , ..., ) ; =1, t T i i i i i pP P P p p p i N  , Các tham số bầy đàn: c1= c2=2, =1, PSO, max-PSO; Các tham số đồng phân cụm mờ C, Tu, Tv, FCCI, max-FCCI. Đầu ra: Kết quả phân cụm. Thuật toán PSO: 1. Khởi tạo bầy đàn Np phần tử (P, Pbest và A), (0) Gbestf . 2. While ( ( ) 1 Gbest PSO f         ) do 3. For k=1 to Np do 4. Tính toán uci; và fi; 5. If ( i Pbest if f  ) then Pbest-i=Xi; fPbest-i=fi; 8. If ( ( )i Gbestf f  ) then ( )Gbest if f   ; PGbest= Pbest-i; 9. Tính vận tốc a={ a1, a2, , aC}, vị trí p={p1, p2, , pC}. 10. End For 11. End While FCCI Algorithm: 11. Khởi tạo C cụm từ C vị trí của PGbest và tính U={uci}. τ=1; 12. Do 13. Cập nhật pcj; 14. Cập nhật vcj; 15. Cập nhật uci; 16. Tính f () (P); 17. τ=τ+1; 18. While(  ( ) 1 ( or )FCCI FCCI f P      ) 2.2.4. Tăng tốc thuật toán MHFCoC Để tăng tốc mô hình đồng phân cụm mờ lai ghép khắc phục hạn chế về tốc độ tính toán do độ phức tạp của các thuật toán PSO và FCoC. Luận án đã áp dụng kỹ thuật cài đặt thuật toán PSO song song trên GPU. 2.2.5. Kết quả thực nghiệm Thực nghiệm được tiến hành trên một số bộ dữ liệu khác nhau. Kết quả thực nghiệm có trong các bảng 2.7-2.10 và các hình 2.8 và 2.9. 13 Bảng 2.7: Kết quả phân cụm trên các bộ dữ liệu đa chiều sử dụng các mô hình thuật toán FCM, FCoC, IVFCoC, HFCoC và MHFCoC Dữ liệu Thuật toán PC PE MSE IQI DB-I XB-I Prec. Rec.  S p am b as e FCM 0,61 0,271 12,02 0,73 1,59 1,11 0.95 0.93 19 FCoC 0,91 0,047 8,50 0,92 1,17 0,93 0.95 0.96 15 IVFCoC 0,93 0,014 5,12 0,94 0,84 0,83 0.98 0.97 13 HFCoC 0,92 0,016 7,48 0,91 0,92 0,96 0,98 0,97 10 MHFCoC 0,94 0,011 5,18 0,95 0,67 0,69 0.98 0.98 8 E co li FCM 0,93 0,013 9,63 0,94 1,96 0,63 0.87 0.89 13 FCoC 0,93 0,014 9,63 0,94 1,55 0,63 0.95 0.94 12 IVFCoC 0,98 0,002 9,60 0,98 1,83 0,57 0.97 0.97 10 HFCoC 0,96 0,005 9,60 0,97 1,54 0,93 0,98 0,97 9 MHFCoC 0,98 0,001 9,61 0,99 1,36 0,86 0.98 0.98 5 L an d sa t FCM 0,55 0,312 6,36 0,96 1,55 0,38 0.93 0.94 18 FCoC 0,88 0,069 7,47 0,89 1,79 0,54 0.95 0.96 15 IVFCoC 0,98 0,002 6,25 0,94 1,35 0,39 0.98 0.98 13 HFCoC 0,97 0,009 7,67 0,94 1,52 0,58 0,96 0,97 10 MHFCoC 0,99 0,001 6,18 0,96 1,21 0,68 0.98 0.98 8 Bảng 2.8: Kết quả sử dụng FCM, FCoC, IVFCoC, HFCoC và MHFCoC Thuật toán PC PE MSE IQI DB-I XB-I Prec. Rec.  D im 2 5 6 FCM 0,80 0,095 19,1 0,75 0,97 0,62 0.79 0.82 27 FCoC 0,90 0,046 8,2 0,97 0,91 0,49 0.97 0.96 18 IVFCoC 0,98 0,008 0,7 0,99 0,88 0,44 0.98 0.99 15 HFCoC 0,95 0,023 7,5 0,98 0,93 0,42 0,98 0,97 13 MHFCoC 0,98 0,008 5,3 0,99 0,52 0,47 0.99 0.99 12 D im 5 1 2 FCM 0,78 0,151 11,2 0,86 1,20 0,47 0.91 0.93 17 FCoC 0,93 0,037 6,4 0,98 0,93 0,43 0.93 0.95 13 IVFCoC 0,92 0,048 0,8 0,99 0,83 0,35 0.99 0.98 10 HFCoC 0,95 0,023 2,9 0,96 0,88 0,39 0,96 0,95 9 MHFCoC 0,95 0,023 1,0 0,99 0,78 0,40 0.99 0.99 11 D im 1 0 2 4 FCM 0,75 0,169 21,1 0,72 0,95 0,59 0.85 0.82 19 FCoC 0,95 0,023 7,0 0,98 0,84 0,59 0.96 0.93 15 IVFCoC 0,95 0,022 3,9 0,98 0,78 0,52 0.98 0.99 12 HFCoC 0,96 0,018 6,0 0,98 0,79 0,56 0,97 0,97 10 MHFCoC 0,98 0,009 4,0 0,98 0,70 0,59 0.99 0.99 11 14 Hình 2.8: Kết quả phân cụm a) NVDI, b) FCM, c) FCoC, d) IVFCoC, e) HFCoC và f) MHFCoC. Bảng 2.10: Các kết quả phân lớp ảnh về tinh đa phổ sử dụng các thuật toán FCM, FCoC, IVFCoC, HFCoC và MHFCoC Thuật toán PC PE MSE IQI DB-I XB-I  FCM 0,79 0,137 8 11,2 0,83 3,50 1,18 21 FCoC 0,95 0,027 9,2 0,94 1,26 0,98 18 IVFCoC 0,97 0,006 7,1 0,97 1,05 0,67 12 HFCoC 0,97 0,007 8,5 0,96 1,59 0,84 9 MHFCoC 0,98 0,002 6,5 0,96 0.93 0,56 5 2.2.6. Phân tích và đánh giá hiệu quả của thuật toán MHFCoC Theo kết quả phân cụm, thuật toán MHFCoC được xem là hội tụ nhanh hơn, hiệu suất phân cụm cao hơn so với FCM, FCoC, IVFCoC và HFCoC. Ngoài ra, để tăng tốc đồng phân cụm, luận án đã cài đặt các thuật toán phân cụm trên các mô hình lập trình song song khác nhau. Kết quả thực nghiệm trong bảng 2.11 cho thấy các thuật toán đồng phân cụm mờ 15 có thể tăng tốc bằng cách cài đặt trên các mô hình lập trình song song. Bảng 2.11: Thời gian xử lý trên các mô hình lập trình song song và các mô hình phân cụm khác nhau Dữ liệu Mô hình lập trình Mô hình phân cụm FCM FCoC IVFCoC HFCoC MHFCoC D im 2 5 6 Tuần tự 45,08 5,78 79,60 6,23 4,61 Đa vi xử lý 14,54 1,65 25,68 2,15 1,44 MPI 7,91 0,95 14,21 1,13 0,82 GPU 1,50 1,21 2,16 2,08 1,68 D im 5 1 2 Tuần tự 69,83 9,78 96,75 11,22 7,85 Đa vi xử lý 23,28 3,06 33,36 3,87 2,45 MPI 8,20 1,69 18,25 2,24 1,51 GPU 2,42 2,02 2,64 2,99 2,16 D im 1 0 2 4 Tuần tự 118,89 21,32 137,45 29,59 21,01 Đa vi xử lý 41,00 6,88 44,34 10,20 6,37 MPI 21,23 3,61 26,43 5,58 3,82 GPU 3,68 3,03 4,32 5,07 3,60 Ả n h đ a p h ổ Tuần tự 1.235,23 985,27 1.587,16 2.560,54 2.120,38 Đa vi xử lý 398,46 281,51 495,99 825,98 605,82 MPI 224,59 156,39 299,46 492,41 400,07 GPU 205,87 151,58 255,99 406,43 326,21 2.3. Kết luận chương 2 Chương II đã đề xuất hai thuật toán đồng phân cụm mờ cải tiến nâng cao chất lượng và ổn định phân cụm. Thứ nhất, thuật toán IVFCoC được đề xuất bằng cách kết hợp FCoC với IVFs [3], [4]. Thứ hai, thuật toán MHFCoC được đề xuất bằng cách lai ghép thuật toán PSO với thuật toán FCoC để khắc phục hạn chế về nhạy cảm với khởi tạo tâm cụm và độ phức tạp tính toán. Ngoài ra, thuật toán MHFCoC được cài đặt song song trên GPU để tăng tốc đồng phân cụm mờ. Thực nghiệm được tiến hành trên các bộ dữ liệu đa chiều, nhiều đặc trưng và ảnh đa phổ cho thấy các thuật toán IVFCoC và MHFCoC đạt hiệu quả tốt hơn so với một vài thuật toán đã được đề xuất trước đó. 16 Chương 3 ĐỒNG PHÂN CỤM MỜ GIẢM CHIỀU ẢNH SIÊU PHỔ 3.1. Thuật toán đánh giá xu hướng cụm Đánh giá xu hướng cụm là một phương pháp xác định xem một bộ dữ liệu có chứa các cụm có ý nghĩa hay không. Các câu hỏi thường được đặt ra là: Có bao nhiêu cụm? Dữ liệu được phân bố như thế nào? Trong mục này, luận án đề xuất một phương pháp đánh giá xu hướng cụm mới dựa vào chỉ số Silhouette được gọi là thuật toán SACT. 3.1.1. Phương pháp đánh giá xu hướng cụm bằng trực quan 3.1.2. Thuật toán đánh giá xu hướng cụm tự động SACT Ý tưởng của thuật toán SACT như sau: Xây dựng cây khung tối thiểu. Sau đó, từng bước băm cây khung tối thiểu theo lần lượt các cạnh lớn nhất. Mỗi lần băm hình thành một nhánh mới tương ứng với một cụm mới được tách ra, với một phương án cụm ứng viên. Sử dụng chỉ số đánh giá cụm Silhouette để định lượng chất lượng cụm cho từng phương án. Cuối cùng, xác định số cụm tương ứng với chỉ số Silhouette cao nhất. Thuật toán 3.2. Thuật toán đánh giá xu hướng cụm SACT Đầu vào: Bộ dữ liệu kích thước N để xây dựng ma trận tương quan R kích thước NxN, số cụm tối đa Cmax. Đầu ra: Số cụm phù hợp và các trung tâm cụm tương ứng. 1. Khởi tạo K={1, 2, , N}; Lựa chọn (i, j) arg max{dpq} với p, q K. Gán E={(i,j)}; I={i} và J=K-{i}. 2. Lặp đối với t=2, 3, , N Lựa chọn (i, j) arg max{dpq} với pI, qJ; Gán E=E{(i,j)}; thay thế II{j} và JJ-{j}. 3. Khởi tạo T={E}, S0=0. Lặp đối với c=2, , Cmax 3.1. Lựa chọn (k, i, ni) với T={T1, , Ti, Tc} và ekarg min{T}, ekTi. 3.2. Gán Tc+1=. Di chuyển ek+1, ek+2, , eniTi tới Tc+1. Băm ekTi; gán T=TTc+1. 3.3. Tính chỉ số Silhouette Sc. Nếu Sc>Sc-1 lưu số cụm co=c và trạng thái phân bố cụm T, ngược lại quay về bước 3.1. 4. Xây dựng biểu đồ chỉ số Silhouette với số cụm. 5. Xác định số cụm dựa vào biểu đồ chỉ số Silhouette với số cụm. 17 3.1.3. Thực nghiệm đánh giá xu hướng cụm Luận án đã tiến hành một số thực nghiệm đánh giá xu hướng cụm sử dụng thuật toán SACT trên một số bộ dữ liệu mẫu, dữ liệu được gán nhãn và ảnh mầu. Đồng thời, luận án đánh giá hiệu suất của các thuật toán phân cụm sử dụng tâm cụm thu được từ thuật toán SACT so sánh với tâm cụm khởi tạo ngẫu nhiên. Kết quả thực nghiệm được chỉ ra trong các bảng 3.2, 3.3, 3.4 và các hình 3.3 và 3.4 cho thấy thuật toán SACT đạt được hiệu quả tốt trong việc xác định số cụm dữ liệu và tâm cụm khởi tạo so với một vài phương pháp đã đề xuất trước đây. Hình 3.3: Kết quả thực nghiệm tìm số cụm trên các bộ dữ liệu Dim032- Dim1024 sử dụng thuật toán SACT và phương pháp trong [39]. 18 Bảng 3.4: Kết quả phân cụm sử dụng các thuật toán FCM, FCoC, IVFCoC và SACT với tâm cụm khởi tạo ngẫu nhiên và tâm cụm khởi tạo từ SACT Thuật toán FCM FCM- SACT FCoC FCoC- SACT IVFCoC IVFCoC- SACT D im 2 5 6 PC 0.80 0.89 0.90 0.95 0.98 0.99 MSE 19.10 12.20 8.22 6.43 0.66 0.62 IQI 0.75 0.85 0.97 0.98 0.99 0.99 D im 5 1 2 PC 0.78 0.90 0.93 0.95 0.91 0.98 MSE 11.23 9.45 6.42 4.32 0.84 0.53 IQI 0.86 0.92 0.98 0.99 0.99 0.99 D im 1 0 2 4 PC 0.75 0.91 0.95 0.97 0.97 0.99 MSE 21.12 15.13 7.02 5.17 3.9 1.89 IQI 0.72 0.89 0.98 0.98 0.99 0.99 3.1.4. Mô hình ảnh siêu phổ thưa 3.2. Thuật toán đồng phân cụm mờ giảm đặc trưng Trong các ứng dụng phân tích dữ liệu đa chiều, nhiều đặc trưng như ảnh siêu phổ, thường phát sinh các vấn đề như giảm chiều, giảm đặc trưng, lựa chọn kênh, để nâng cao hiệu quả về chất lượng cũng như tốc độ xử lý. Trong mục này, luận án đề xuất thuật toán đồng phân cụm mờ giảm đặc trưng, ký hiệu là FRFCoC. 3.2.1. Kỹ thuật giảm đặc trưng trong phân cụm mờ Hàm mục tiêu của thuật toán FRFCM được chỉ ra trong công thức (3.5). 2 ij w 1 1 1 1 ( , , W) w (x ) ( ) C N D D m ci j j cj j j j c i j j J U V u p T w log w          (3.5) 3.2.2. Thuật toán đồng phân cụm mờ giảm đặc trưng Luận án đã đề xuất thuật toán đồng phân cụm mờ giảm chiều FRFCoC. Hàm mục tiêu của thuật toán FRFCoC được đề xuất như sau, RFCoC 1 1 1 1 1 w 1 1 1 ( , , , W, ) w log log w log w C N D C N F ci cj j j cij u ci ci c i j c i C D D v cj cj j j j c j j J U V P u v d T u u T v v T                    (3.11) Thuật toán FRFCoC được chỉ ra như sau. 19 Thuật toán 3.4. Thuật toán đồng phân cụm mờ giảm chiều FRFCoC Đầu vào: Bộ dữ liệu  , , i=1..NDi iX x x R  , số cụm C, các tham số mờ w,, , u v TT T ε, số vòng lặp tối đa τmax. Đầu ra: Kết quả phân cụm. 1. τ=1. 2. Khởi tạo uci thỏa mãn (3.12); 3. DO 4. Tính toán j sử dụng (3.10); 5. Cập nhật pcj sử dụng (3.21); 6. Cập nhật vcj sử dụng (3.19); 7. Cập nhật uci sử dụng (3.18); 8. Cập nhật wj sử dụng (3.23); 9. Ước lượng Dr ; 10. Cập nhật D (new) = D − Dr; 11. τ=τ+1; D=D (new) 12. UNTIL ( ( ) ( 1)W Wt t   hoặc τ≥ τmax). Độ phức tạp tính toán của thuật toán FRFCoC là O(CD 2 Nτ). 3.2.3. Kết quả thực nghiệm Mục này trình bày các kết quả thực nghiệm trên các bộ dữ liệu tổ hợp số và ảnh siêu phổ sử dụng các mô hình thuật toán phân cụm FCM, FRFCM, FCoC, IVFCoC, MHFCoC và HFRFCoC. Để đánh giá chất lượng của các thuật toán phân cụm này, luận án sử dụng các chỉ số đánh giá PC, MSE, IQI, DI, DB-I, XB-I. Kết quả thực nghiệm được chỉ ra trong các bảng 3.5, 3.6, 3.8, 3.9 và hình 3.8. Bảng 3.5: Kết quả giảm đặc trưng sử dụng thuật toán FRFCM, FRFCoC Dữ liệu Số đặc trưng ban đầu FRFCM FRFCoC Dim256 256 49(19,14%) 53(20.7%) Dim512 512 87(16,99%) 92(17.9%) Dim1024 1024 105(10,25%) 112(10.9%) 20 Bảng 3.6: Kết quả phân cụm trên các bộ dữ liệu Dim032-Dim1024 sử dụng các thuật toán FCM, FRFCM, FCoC, IVFCoC và FRFCoC Thuật toán PC PE MSE IQI DB-I XB-I Prec. Rec.  D im 2 5 6 FCM 0,80 0,095 19,1 0,75 0,97 0,62 0.79 0.82 27 FRFCM 0,91 0,040 11,4 0,96 0,97 0,45 0.92 0.95 7 FCoC 0,90 0,046 8,2 0,97 0,91 0,49 0.97 0.96 18 IVFCoC 0,98 0,008 0,7 0,99 0,88 0,44 0.98 0.99 15 FRFCoC 0,98 0,009 1,6 0,98 0,41 0,07 0.98 0.99 4 D im 5 1 2 FCM 0,78 0,151 11,2 0,86 1,20 0,47 0.91 0.93 17 FRFCM 0,91 0,039 8,4 0,93 0,99 0,48 0.96 0.92 9 FCoC 0,93 0,037 6,4 0,98 0,93 0,43 0.93 0.95 13 IVFCoC 0,92 0,048 0,8 0,99 0,83 0,35 0.99 0.98 10 FRFCoC 0,96 0,020 2,2 0,99 0,53 0,15 0.98 0.99 3 D im 1 0 2 4 FCM 0,75 0,169 21,1 0,72 0,95 0,59 0.85 0.82 19 FRFCM 0,93 0,037 14,9 0,92 0,90 0,55 0.97 0.90 9 FCoC 0,95 0,023 7,0 0,98 0,84 0,59 0.96 0.93 15 IVFCoC 0,95 0,022 3,9 0,99 0,78 0,52 0.98 0.99 12 FRFCoC 0,98 0,011 4,3 0,99 0,56 0,17 0.99 0.99 3 Bảng 3.8: Kết quả phân cụm ảnh siêu phổ sử dụng các thuật toán FCM, FRFCM, FCoC, và FRFCoC Dữ liệu PC MSE IQI XB-I DB-I  G o M W s FCM 0,42 76,4 0,85 0,69 1,98 18 FRFCM 0,61 75,3 0,96 0,43 1,75 6 FCoC 0,92 76,8 0,94 1,15 2,15 14 FRFCoC 0,97 73,8 0,98 0,28 0,75 3 G s FCM 0,3 238,1 0,78 1,15 2,03 21 FRFCM 0,58 231,3 0,94 0,35 1,76 8 FCoC 0,91 240,1 0,85 1,1 1,94 19 FRFCoC 0,96 215,2 0,95 0,35 1,43 3 A & V s FCM 0,23 163,1 0,84 0,71 1,26 17 FRFCM 0,48 145,9 0,95 0,16 0,88 9 FCoC 0,87 159,2 0,91 0,93 0,96 9 FRFCoC 0,97 136,5 0,95 0,16 0,82 3 21 Bảng 3.9: Kết quả giảm đặc trưng dữ liệu ảnh siêu phổ sử dụng FRFCM và FRFCoC Dữ liệu Số đặc trưng ban đầu FRFCM FRFCoC GoMWs 360 37(10,28%) 41 (11.4%) Gs 357 29(8,12%) 32 (8,9%) A&Vs 360 30(8,33%) 31(8.6%) Hình 3.8: Kết quả phân cụm ảnh siêu phổ a) Tổ hợp mầu ENVI; b)FCM; c) FRFCM; d) FCoC; e) FRFCoC 22 3.2.4. Phân tích và đánh giá hiệu quả thuật toán FRFCoC Theo các kết quả phân cụm, thuật toán FRFCoC được đánh giá là hiệu quả hơn các thuật toán FCM, FRFCM, IVFCoC và FCoC, hiệu suất giảm đặc trưng