Tóm tắt Luận án Phát triển một số mô hình phân cụm mờ cộng tác

Một số kỹ thuật kết hợp nâng cao chất lượng phân cụm

1.2.4.1 Kỹ thuật nhân trong phân cụm

Một trong những thách thức của bài toán phân cụm là sự phức tạp

của dữ liệu, sự phức tạp có thể ở nhiều khía cạnh khác nhau như:

kích thước dữ liệu, sự đa dạng các loại thuộc tính, tính đa dạng của

dữ liệu nói chung. Một trong các cách phổ biến để phân lớp tuyến

tính một dữ liệu phi tuyến trong không gian đầu vào là sử dụng một

hàm nhân Mercer để làm phép ánh xạ ẩn.6

1.2.4.2 Kỹ thuật siêu điểm ảnh trong phân cụm dữ liệu

Khái niệm về siêu điểm ảnh được Ren giới thiệu như là một tập

các điểm gần nhau có sự tương tự về màu hoặc mức xám. Bằng cách

chia ảnh cần phân đoạn thành các siêu điểm ảnh (super pixels) không

chồng nhau, thay vì thực hiện phân đoạn ảnh dựa trên các điểm ảnh

ta phân đoạn ảnh dựa trên các siêu điểm ảnh.

1.2.4.3 Tính toán hạt trong phân cụm

Tính toán hạt (Granular Computing – GrC) được đề xuất bởi

Zadeh, là một khái niệm bao gồm lý thuyết, phương pháp, kỹ thuật

và công cụ sử dụng hạt để giải quyết những vấn đề phức tạp trong xử

lý thông tin, thông tin cần xử lý trong tính toán hạt ta gọi là “hạt

thông tin” (Information Granules - IG), IG thường được tạo thành từ

các thực thể gồm các thông tin số tương tự nhau.

pdf27 trang | Chia sẻ: trungkhoi17 | Lượt xem: 323 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Tóm tắt Luận án Phát triển một số mô hình phân cụm mờ cộng tác, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
.1 Chỉ số đánh giá trong (Internal Quality Criteria) 1.1.5.2 Chỉ số đánh giá ngoài (External Quality Criteria) 1.2 Tổng quan các nghiên cứu liên quan 1.2.1 Tổng quan về phân cụmmờ Phân cụm là kỹ thuật nhóm các đối tượng vào các cụm dựa trên thông tin của các đối tượng và mối liên hệ của chúng sao cho các đối tượng trong cùng một cụm thì tương tự nhau còn các đối tượng khác thuộc các cụm khác nhau thì khác nhau. Phân cụm mờ là phương pháp phân cụm dữ liệu mà cho phép mỗi điểm dữ liệu thuộc về hai hoặc nhiều cụm thông qua hàm thành viên thể hiện độ thuộc. Trong thực tế dữ liệu đầu vào cho bài toán phân cụm thường có nhiễu và không chắc chắn, nhiều tác giả đã nghiên cứu phát triển các thuật toán phân cụm sử dụng tập mờ loại 2 để giải quyết vấn đề hoặc kết hợp tập mờ loại 2 với giải thuật di truyền và phương pháp nhân và các phương pháp lai khác. 1.2.2Tổng quan về phân cụm mờ cộng tác Phân cụm mờ cộng tác được Pedrycz giới thiệu như là công cụ tìm ra những cấu trúc và đặc điểm tương đồng giữa các dữ liệu nằm trên nhiều khu vực riêng biệt dựa trên cách mở rộng hàm mục tiêu và cách tiếp cận phân cụm mờ của thuật toán FCM. Có 2 đặc điểm của phân cụm mờ cộng tác, một là thông tin chi tiết trong các tập dữ liệu không thể trao đổi với nhau mà chỉ có thể trao đổi thông tin về cấu 5 trúc, hai là cần xem xét việc phân cụm mờ ở tập dữ liệu này có tác động tới việc phân cụm ở các tập dữ liệu khác, thông tin cấu trúc các cụm trong từng tập dữ liệu là có ích trong việc phân cụm tại các tập dữ liệu còn lại. 1.2.3 Phân cụm dữ liệu lớn 1.2.3.1 Dữ liệu lớn Có 2 cách tiếp cận để giải quyết bài toán phân cụm dữ liệu lớn: cách thứ nhất phân cụm trên toàn bộ dữ liệu, ví dụ một số thuật toán cải tiến từ thuật toán FCM như: LFCM/AO, thuật toán SPFCM hay OFCM các thuật toán này chia dữ liệu thành các tập nhỏ và phân từng tập dữ liệu con thành c cụm; một cách tiếp cận khác là lấy mẫu dữ liệu từ tập dữ liệu lớn để thực hiện phân cụm sau đó kết quả được mở rộng xấp xỉ cho phần dữ liệu còn lại, ví dụ thuật toán rseFCM hay thuật toán RSIO-FCM. 1.2.3.2 Một số thuật toán phân cụm dữ liệu lớn a. Thuật toán FCM lấy mẫu ngẫu nhiên mở rộng b. Thuật toán FCM có trọng số c. Thuật toán spFCM d. Thuật toán rseFCM sử dụng nhân 1.2.4 Một số kỹ thuật kết hợp nâng cao chất lượng phân cụm 1.2.4.1 Kỹ thuật nhân trong phân cụm Một trong những thách thức của bài toán phân cụm là sự phức tạp của dữ liệu, sự phức tạp có thể ở nhiều khía cạnh khác nhau như: kích thước dữ liệu, sự đa dạng các loại thuộc tính, tính đa dạng của dữ liệu nói chung. Một trong các cách phổ biến để phân lớp tuyến tính một dữ liệu phi tuyến trong không gian đầu vào là sử dụng một hàm nhân Mercer để làm phép ánh xạ ẩn. 6 1.2.4.2 Kỹ thuật siêu điểm ảnh trong phân cụm dữ liệu Khái niệm về siêu điểm ảnh được Ren giới thiệu như là một tập các điểm gần nhau có sự tương tự về màu hoặc mức xám. Bằng cách chia ảnh cần phân đoạn thành các siêu điểm ảnh (super pixels) không chồng nhau, thay vì thực hiện phân đoạn ảnh dựa trên các điểm ảnh ta phân đoạn ảnh dựa trên các siêu điểm ảnh. 1.2.4.3 Tính toán hạt trong phân cụm Tính toán hạt (Granular Computing – GrC) được đề xuất bởi Zadeh, là một khái niệm bao gồm lý thuyết, phương pháp, kỹ thuật và công cụ sử dụng hạt để giải quyết những vấn đề phức tạp trong xử lý thông tin, thông tin cần xử lý trong tính toán hạt ta gọi là “hạt thông tin” (Information Granules - IG), IG thường được tạo thành từ các thực thể gồm các thông tin số tương tự nhau. 1.3 Những hạn chế của các nghiên cứu hiện có và mục tiêu nghiên cứu Khi giải quyết các bài toán phân cụm trong thực tế, ta thường gặp những vấn đề như: vấn đề nhiễu, sự không chắc chắn của dữ liệu; sự phức tạp trong cấu trúc cụm, cụm không có dạng khối cầu, sự chia tách cụm không tuyến tính; dữ liệu lớn nhiều chiều và nhiều đối tượng cần phân cụm. Những vấn đề này trong phân cụm mờ cộng tác vẫn là một bài toán chưa có các nghiên cứu giải quyết, do đó mục tiêu của luận án là nghiên cứu và đề xuất mô hình ứng dụng các kỹ thuật này vào lớp bài toán phân cụm mờ cộng tác để giải quyết những vấn đề trên. Cụ thể là: - Nghiên cứu đề xuất mô hình ứng dụng tập mờ giá trị khoảng để nâng cao chất lượng phân cụm mờ cộng tác khi dữ liệu đầu vào không rõ ràng, không chắc chắn. 7 - Nghiên cứu đề xuất mô hình ứng dụng kỹ thuật đa nhân trong phân cụm mờ cộng tác để nâng cao chất lượng phân cụm dữ liệu có cấu trúc phức tạp và sự chia tách các cụm không tuyến tính. - Nghiên cứu kỹ thuật gom điểm ảnh thành các hạt siêu điểm ảnh và ứng dụng trong mô mình phân mờ cụm cộng tác đa nhân để giảm độ phức tạp tính toán. - Nghiên cứu đề xuất giải pháp giảm chiều dữ liệu bằng định lý Johnson- Lindenstrauss và phân cụm mờ cộng tác cho bài toán phân cụm dữ liệu nhiều chiều, kích thước lớn, độ phức tạp tính toán cao. 1.4 Những đóng góp chính của luận án Luận án đã đề xuất ra hai thuật toán phân cụm mờ giá trị khoảng cộng tác để nâng cao chất lượng phân cụm khi dữ liệu có nhiễu và không chắc chắn của dữ liệu. Luận án đề xuất được thuật toán phân cụm mờ cộng tác sử dụng kỹ thuật đa nhân và tính toán hạt siêu điểm ảnh có trọng số để giải quyết vấn đề nâng cao chất lượng phân cụm khi dữ liệu có sự phân tách cụm không tuyến tính và giảm độ phức tạp trong tính toán khi phân cụm ảnh bằng kỹ thuật tính toán hạt siêu điểm ảnh có trọng số. Luận án cũng đã đưa ra một Framework ứng dụng thuật toán phân cụm mờ cộng tác cho phân cụm dữ liệu lớn kết hợp giảm chiều bằng phép chiếu ngẫu nhiên. Các kết quả của luận án đã được công bố trong 5 công trình gồm 1 bài báo trong danh mục SCI Q1, một bài báo trong danh mục được hội đồng chức danh giáo sư nhà nước tính điểm, 3 bài hội thảo quốc gia và quốc tế (và 1 bài chờ duyệt tạp chí trong danh mục SCI Q1) 1.5 Kết luận chương 1 Chương này luận án tổng hợp lại các lý thuyết và kết quả nghiên 8 cứu về phân cụm dữ liệu gồm: phân cụm dữ liệu, phân cụm dữ liệu mờ loại 1, mờ loại 2 và phân cụm mờ cộng tác. Luận án đưa ra các câu hỏi cần nghiên cứu, các giải pháp cho các câu hỏi đó sẽ được nghiên cứu và trình bày trong luận án. Phần cuối chương trình bày tổng hợp các kiến thức cơ sở phục vụ cho luận án như: tập mờ, phân cụm mờ, phân cụm mờ cộng tác. Nhiều phương pháp xác định khoảng cách, độ đo tương tự và chỉ số đánh giá chất lượng phân cụm cũng được tổng hợp và trình bày. CHƯƠNG 2. PHÂN CỤM MỜ LOẠI 2 KHOẢNG CỘNG TÁC Dữ liệu phân cụm thường có nhiễu và không chắc chắn mà phân cụm mờ loại 1 thường không giải quyết tốt, chương này luận án đề xuất sử dụng tập mờ giá trị khoảng để giải quyết vấn đề trên. 2.1 Phân cụm mờ loại 2 khoảng cộng tác Hàm mục tiêu như sau: Giá trị ma trận phân hoạch và tâm cụm xác định như sau: )1 1 1/( 2 1=1,= 21= 2 1=1,= 2 1 ])[]|[( 1 ])[]|[( 1 =][                    m ks c k P iijjjj js c j ks c k P iijjjj rs m rs jjdjjiid jjdjjiid iiu   )1 2 1/( 2 1=1,= 21= 2 1=1,= 2 2 ])[]|[( 1 ])[]|[( 1 =][                    m ks c k P iijjjj js c j ks c k P iijjjj rs m rs jjdjjiid jjdjjiid iiu   ][][]|[][= 22 1=1,= ][ 1= 22 1= ][ 1= 2 ][ jjdiiujjiidiiuQ ik m ik c i P iijjjj iiN k ik m ik c i iiN k m ii    ][][]|[][= 21 1=1,= ][ 1= 21 1= ][ 1= 1 ][ jjdiiujjiidiiuQ ik m ik c i P iijjjj iiN k ik m ik c i iiN k m ii    9 ][]|[][ ][]|[][ =][ 1 ][ 1= 1 ][ 1= 1 ][ 1= 1 ][ 1=1 iiujjiiiiu jjvujjiixiiu iiv m rk iiN k m rk iiN k rt m rk iiN k kt m rk iiN km rt       ][]|[][ ][]|[][ =][ 2 ][ 1= 2 ][ 1= 2 ][ 1= 2 ][ 1=2 iiujjiiiiu jjvujjiixiiu iiv m rk iiN k m rk iiN k rt m rk iiN k kt m rk iiN km rt       2.2 Phân cụm mờ loại 2 khoảng cộng tác khi số cụm khác nhau Hàm mục tiêu đề xuất như sau: 21 ][ 1= ][ 1= 21 ][ 1= ][ 1= 1 ][ ])[ ~][(][][= iiviiviiudiiuQ ii m ik iic i iiN k ik m ik iic i iiN k m ii    22 ][ 1= ][ 1= 22 ][ 1= ][ 1= 2 ][ ])[ ~][(][][= iiviiviiudiiuQ ii m ik iic i iiN k ik m ik iic i iiN k m ii    U và V để tối thiểu hóa cho hàm mục theo công thức:   1) 1 1/( 22 ][ 1= 22 1 )])[~][(( 1 ])[~][( 1 =][             m jjjs iic j rrrs m rs iiviivd iiviivd iiu     1) 2 1/( 22 ][ 1= 22 2 )])[~][(( 1 ])[~][( 1 =][             m jjjs iic j rrrs m rs iiviivd iiviivd iiu   ][)(1 ][~][ =][ 1 ][ 1= 1 ][ 1= 1 ][ 1=1 iiu iivuxiiu iiv m rk iiN k rt m rk iiN k kt m rk iiN km rt       ][)(1 ][~][ =][ 2 ][ 1= 2 ][ 1= 2 ][ 1=2 iiu iivuxiiu iiv m rk iiN k rt m rk iiN k kt m rk iiN km rt       2.3 Thuật toán phân cụm mờ loại 2 khoảng cộng tác (CIVFCM) Thuật toán 2.1 Phân cụm mờ loại 2 khoảng cộng tác Đầu vào: số tập dữ liệu P, số phần tử trong tập dữ liệu thứ ii là N[ii], số cụm trong tập dữ liệu thứ ii là 10 c[ii], số thuộc tính của dữ liệu là M, dữ liệu trong tập dữ liệu thứ ii là X[ii], số lần lặp tối đa 𝑡𝑚𝑎𝑥, thay đổi ma trận phân hoạch sau 2 lần chạy tối thiểu 𝜀 và thay đổi ma trận tâm cụm sau 2 lần chạy tối thiểu 𝜀1 Đầu ra: Kết quả phân cụm Begin Pha 1: Phân cụm trong từng datasite (Locally Clustering) Chạy các thuật toán phân cụm mờ với từng tập dữ liệu Pha 2: Quá trình phân cụm cộng tác (Collaboration) Repeat Trao đổi tâm cụm tới tất cả các tập dữ liệu For each data site D[ii] Tính ma trận phân hoạch cộng tác u~ Tính ma trận hệ số cộng tác 𝛽 Repeat Tính ma trận phân hoạch u Tính ma trận tâm cụm v Until|𝑈𝓉 − 𝑈𝓉−1| 𝑡𝑚𝑎𝑥. End for Until|𝑉𝑡 − 𝑉𝑡−1| 𝑡𝑚𝑎𝑥 End 2.4 Thử nghiệm và đánh giá Để đánh giá kết quả hoạt động của thuật toán CIVFCM, thuật toán phân cụm mờ cộng tác CFCM, thuật toán phân cụm mờ dựa trên mật độ CFSFD được sử dụng để so sánh bằng các chỉ số đánh giá. 2.4.1 Thử nghiệm với dữ liệu sinh ngẫu nhiên Bảng 2.2. Chỉ số đánh giá với thử nghiệm 2.1 CFCM CFSFD CIVFCM1 CIVFCM2 FS 11.554 NA 13.980 10.598 FSSE 833801.43 NA 436733.43 843230.91 DI 0.5753 0.6035 0.6208 0.5916 DB 1.6214 1.5163 1.5021 1.5230 PCI 3.5209 NA 3.9127 3.5721 CEI 2.6817 NA 1.9604 2.5992 SI 1.0457 1.1368 1.0062 1.0586 11 2.4.2 Thử nghiệm với dữ liệu S1, S41 Các chỉ số đánh giá trình bày trong bảng 1 và 2 cho thấy thuật toán đề xuất có kết quả tốt hơn trong hầu hết các trường hợp. Bảng 2.3 Chỉ số đánh giá của các thuật toán với dữ liệu S1 CFCM CFSFD CIVFCM1 CIVFCM2 FS 4.5381 NA 4.7142 4.6645 FSSE 1,004,183,637,717 NA 681,006,714,269 722,143,727,431 DI 0.4843 0.7324 0.5576 0.5448 DBI 1.6917 1.5654 1.5526 1.6524 PCI 2.0568 NA 2.9172 2.8211 CEI 4.7755 NA 2.8774 3.3848 SI 2.9499 1.5024 2.3910 2.6351 Bảng 2.4 Chỉ số đánh giá của các thuật toán với dữ liệu S4 CFCM CFSFD CIVFCM1 CIVFCM2 FS 3.6464 NA 3.6813 3.6721 FSSE 660,571,313,435 NA 521,849,610,363 603,423,516,250 DI 0.2234 0.5629 0.2305 0.5448 DBI 3.1118 3.3503 2.0419 3.1207 PCI 1.4510 NA 2.1642 1.9572 CEI 6.5427 NA 4.7711 5.3481 SI 1.1544 1.7297 0.9699 1.0254 2.4.3 Thử nghiệm với dữ liệu thời tiết Canada2 Giá trị chỉ số đánh giá phân cụm tốt nhất của các thuật toán được thể hiện trong bảng 2.5 cho thấy các thuật toán đề xuất cho kết quả tốt hơn, tốt nhất là CIVFCM1. 1https://cs.joensuu.fi/sipu/datasets/ 2 12 Bảng 2.5 Chỉ số đánh giá của các thuật toán với dữ liệu thời thiết CFCM CFSFD CIVFCM1 (m1, m2) CIVFCM2 (m1, m2) FS 12.309 NA 14.2741 (1.8,3) 12.7577 (2,2.8) FSSE 490.37 NA 387(1.8,3) 469(2, 2.8) DI 0.2247 0.2401 0.2398 (2, 2.8) 0.2287(2, 2.6) DBI 5.0594 5.2677 4.09(1.4,2.8) 4.05(2,3) PCI 2.7768 NA 3.5506(1.8, 3) 2.8012(2, 2.4) CEI 1.9078 NA 0.9368(1.8, 3) 1.7078(2, 3) SI 0.4329 0.7669 0.3812(1.8, 3) 0.423(2,3) 2.4.4 Thử nghiệm với dữ liệu ảnh vệ tinh Dữ liệu ảnh vệ tinh khu vực Hà Nội và Bảo lộc. Sử dụng dữ liệu 2 ảnh này như tập dữ liệu cho thuật toán phân cụm cộng tác để chia làm 6 cụm tương ứng với 06 vùng bề mặt trái đất.Kết quả cho thấy tỷ lệ sai khác của thuật toán CFCM, CFSFD, CIVFCM1,2 với dữ liệu DNRS vùng Hà Nội lần lượt là 8,30%; 8,68%; 4.75% và 7,16%, tương tự với vùng Bảo lộc là 13.94%, 14.46%, 8.45% và 2.53%. Thuật toán CIVFCM1 là tốt nhất về chỉ số đánh giá và sự sai khác nhỏ nhất so với dữ liệu gốc. [Ảnh gốc Hà Nội] [CFCM] [CIVFCM1] 13 [CIVFCM2] [CFSFD] [Ảnh gốc Bảo lộc] [CFCM] [CIVFCM1] [CIVFCM2] [CFSFDP] Hình 2.5 Kết quả phân cụm Hà Nội và Bảo Lộc theo các thuật toán Bảng 2.8 Chỉ số đánh giá chất lượng phân cụm các thuật toán CFCM CFSFD CIVFCM1 CIVFCM2 FS 6.2762 NA 6.941 6.35 FSSE 1458 NA 1290 1429 DI 0.1073 0.1501 0.111 0.10 14 DBI 1.0875 1.1341 1.01 1.033 PCI 0.8879 NA 1.442 1.130 CEI 2.0958 NA 1.121 1.816 SI 0.5751 0.9157 0.1942 0.423 2.4.5 Một số đánh giá Các thử nghiệm cho thấy thuật toán đề xuất có kết quả tốt nhất trong hầu hết các chỉ số đánh giá. Thuật toán đề xuất phân cụm mờ loại 2 khoảng CIVFCM sẽ có hiệu quả tốt hơn nhiều khi dữ liệu có nhiễu, không chắc chắn trong thực tế được thu thập bởi các cảm biến như dữ liệu thời tiết hoặc ảnh vệ tinh thì thuật toán đề xuất cho kết quả tốt hơn hẳn. Thử nghiệm với dữ liệu ảnh vệ tinh cho ta một hướng ứng dụng hợp lý của phân cụm cộng tác. Độ phức tạp tính toán trình bày trong bảng 2.8 cho thấy các thuật toán sử dụng tập mờ loại 2 nói chung cũng như thuật toán đề xuất CIVFCM có độ phức tạp tính toán cao hơn các thuật toán sử dụng tập mờ loại 2. Tuy nhiên các thuật toán này sẽ cho chất lượng tốt hơn khi giải quyết dữ liệu có nhiễu và không chắc chắn. Bảng 2.9 Độ phức tạp tính toán của các thuật toán STT Thuật toán Độ phức tạp tính toán 1 CFCM NMC2P2 2 CFSFD NMC2P 3 CIVFCM NMC3P3 2.5 Kết luận chương 2 Trong chương này, luận án đã đề xuất ra thuật phân cụm mờ loại 2 khoảng cộng tác trong đó sử dụng tập mờ giá trị khoảng để tăng chất lượng phân cụm khi dữ liệu đầu vào có nhiễu, không chắc chắn. Thuật toán đề xuất đặc biệt tốt hơn hẳn trong với các dữ liệu thời tiết và dữ liệu ảnh vệ tinh, đây là các dữ liệu thực tế và chịu ảnh 15 hưởng bởi các yếu tốt khách quan khi thu thập bởi các cảm biến dẫn đễn nhiễu và không rõ ràng. Các đề xuất được công bố trong [III], [V]. CHƯƠNG 3. MỘT SỐ CẢI TIẾN VÀ ỨNG DỤNG THUẬT TOÁN PHÂN CỤM MỜ CỘNG TÁC 3.1 Phân cụm mờ cộng tác đa nhân dựa trên tính toán hạt siêu điểm ảnh 3.1.1 Phân cụm mờ cộng tác đa nhân Hàm mục tiêu cho thuật toán phân cụm mờ cộng tác đa nhân: [ ] [ ] 2 2 ~ 2 2 [ ] 1 1 1 1, 1 [ ]( (x ) ) [ | ] ( [ | ]) ( (x ) ) N ii N iic P c ii ik k i ik ik k i k i k jj jj ii i Q u ii v ii jj u u ii jj v                 Ma trận phân hoạch để hàm mục tiêu trên đạt giá trị tối thiểukhi: ~ ~ 1, 1, 2 1 2 1, 1,1 [ | ] [ | ] [ | ] [ | ] 1 1 (1 [ | ]) (1 [ | ]) P P rs jsc jj jj ii jj jj ii rs P Pc jrs jj jj ii jj jj iij js ii jj u ii jj ii jj u ii jj u d ii jj ii jj d                                  2 2 1 M ik ikt t t d     [ ] [ ] 2 ~ 21 1 1 1 1, 1 [ ] [ ] 2 ~ 2 1 1 1 1, 1 1 1 [ ] [ | ] ( [ | ]) [ ] [ | ] ( [ | ]) M N ii N iic P c t ik ikt ik ik ikt k i k jj jj ii i t N ii N iic P c ik ikt ik ik ikt k i k jj jj ii i u ii ii jj u u ii jj u ii ii jj u u ii jj                                   [ ] [ ] 2 ~ 2 1 1 1, [ ] [ ] 2 ~ 2 1 1 1, [ 2 2 1 2 1 2 2 1 [ ] ( , ) [ | ]( [ | ]) ( , ) ( , ) 2 [ ] [ | ]( [ | ]) [ ] [ ] ( , ) N ii N ii P ij t k j ij ij t k j j j jj jj ii ikt t k k N ii N ii P ik ij ij j j jj jj ii N ij ij t j j j u ii K x x ii jj u u ii jj K x x K x x u ii ii jj u u ii jj u ii u ii K x x                          [ ] ] [ ] [ ] 2 ~ 2 1 2 2 1 2 1 1 1 1 2 1 1, 2 [ ] [ ] 2 ~ 2 1 1 1 1 1, 2 ~ 2 1 1 2 [ | ] ( [ | ]) ( , ) [ ] [ | ]( [ | ]) [ | ]( [ | ]) ( N ii ii N ii N ii P ij ij ij t j j j j j jj jj ii N ii N ii P ik ij ij j j jj jj ii ij ij ij ii jj u u u ii jj K x x u ii ii jj u u ii jj ii jj u u ii jj u                              [ ] [ii] ~ 2 2 2 1 2 1, 1 1 2 1 2 [ ] [ ] 2 ~ 2 1 1 1 1 1, [ | ]) ( , ) [ ] [ | ]( [ | ]) N ii NP ij t j j jj jj ii j j N ii N ii P ik ij ij j j jj jj ii u ii jj K x x u ii ii jj u u ii jj                      M n 16 3.1.2 Tạo hạt siêu điểm ảnh (Super-pixel granulation) Luận án đề xuất sử dụng phương pháp tạo hạt thông tin bằng “Thuật toán 1.2. Tính siêu điểm ảnh SLIC”, các đối tượng dữ liệu cần phân cụm sẽ được nhóm lại thành các hạt như bước tiền xử lý và được sử dụng để phân cụm mờ cộng tác dựa trên đa nhân với giá trị hạt chính là giá trị tâm cụm đầu ra của thuật toán SLIC. 3.1.3 Phân cụm mờ cộng tác đa nhân dựa trên tính toán hạt siêu điểm ảnh có trọng số Sử dụng hạt siêu điểm ảnh làm đầu vào cho phân cụm mờ cộng tác, mỗi siêu điểm ảnh có trọng số 𝜑𝑘,hàm mục tiêu như sau: [ ] [ ] 2 2 ~ 2 2 [ ] 1 1 1 1, 1 [ ]( (x ) ) [ | ] ( [ | ]) ( (x ) ) N ii N iic P c ii k ik k i ik ik k i k i k jj jj ii i Q u ii v ii jj u u ii jj v                  Ma trận phân hoạch để hàm mục tiêu trên đạt giá trị tối thiểukhi: 𝑢𝑖𝑘 = ∑ 𝛽[𝑖𝑖|𝑗𝑗] iku ~ [ii|jj] 𝑑𝑖𝑘 2𝑃 𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 + 1−∑ ∑ 𝛽[𝑖𝑖|𝑗𝑗] iku ~ [ii|jj]𝑃𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 (𝜑𝑘+∑ 𝛽[𝑖𝑖|𝑗𝑗]𝑃𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 ) 𝑐 𝑖=1 ∑ 1 (𝜑𝑘+∑ 𝛽[𝑖𝑖|𝑗𝑗])𝑑𝑖𝑘2𝑃𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 𝑐 𝑖=1 (𝜑𝑘 + ∑ 𝛽[𝑖𝑖|𝑗𝑗])𝑑𝑖𝑘 2𝑃 𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 2 2 1 M ik ikt t t d     [ ] [ ] 2 ~ 21 1 1 1 1, 1 [ ] [ ] 2 ~ 2 1 1 1 1, 1 1 1 [ ] [ | ] ( [ | ]) [ ] [ | ] ( [ | ]) M N ii N iic P c t k ik ikt ik ik ikt k i k jj jj ii i t N ii N iic P c k ik ikt ik ik ikt k i k jj jj ii i u ii ii jj u u ii jj u ii ii jj u u ii jj                                     17 [ ] [ ] 2 ~ 2 1 1 1, [ ] [ ] 2 ~ 2 1 1 1, 2 2 1 2 1 2 1 [ ] ( , ) [ | ]( [ | ]) ( , ) ( , ) 2 [ ] [ | ]( [ | ]) [ ] [ ] ( , N ii N ii P j ij t k j ij ij t k j j j jj jj ii ikt t k k N ii N ii P j ik ij ij j j jj jj ii j j ij ij t j u ii K x x ii jj u u ii jj K x x K x x u ii ii jj u u ii jj u ii u ii K x                             [ ] [ ] [ ] [ ] 2 ~ 2 2 1 2 2 1 2 1 1 2 1 1 1 2 1 1, 2 [ ] [ ] 2 ~ 2 1 1 1 1 1 1, 2 1 2 1 ) 2 [ | ] ( [ | ]) ( , ) [ ] [ | ]( [ | ]) [ | ]( N ii N ii N ii N ii P j ij ij ij t j j j j j j jj jj ii N ii N ii P j ik ij ij j j jj jj ii j j ij x ii jj u u u ii jj K x x u ii ii jj u u ii jj ii jj u                                 [ ] [ii] ~ 2 ~ 2 1 2 2 1 2 1, 1 1 2 1 2 [ ] [ ] 2 ~ 2 1 1 1 1 1 1, [ | ]) ( [ | ]) ( , ) [ ] [ | ]( [ | ]) N ii NP ij ij ij t j j jj jj ii j j N ii N ii P j ik ij ij j j jj jj ii u ii jj u u ii jj K x x u ii ii jj u u ii jj                        3.1.4 Thuật toán phân mờ cụm cộng tác đa nhân. Thuật toán 3.1 MKCFCM/SMKCFCM Đầu vào: P tập dữ liệu D’[ii], số phần tử trong tập dữ liệu thứ ii là N’[ii], số cụm trong tập dữ liệu thứ ii là c[ii], số thuộc tính của dữ liệu là M, dữ liệu trong tập dữ liệu thứ ii là X’[ii], số lần lặp tối đa 𝑡𝑚𝑎𝑥 , thay đổi ma trận phân hoạch sau 2 lần chạy tối thiểu 𝜀 và thay đổi ma trận tâm cụm sau 2 lần chạy tối thiểu 𝜀1 Đầu ra: Ma trận phân hoạch kết quả phân cụm Begin Pha 1: Tính siêu điểm ảnh và phân cụm cục bộ 1.1 Tính toán hạt siêu điểm ảnh theo thuật toán SLIC được đầu ra là P tập dữ liệu D[ii] gồm N[ii] siêu điểm ảnh cho mỗi tập. 1.2 Phân cụm tại mỗi tập dữ liệu hạt siêu điểm ảnh bằng thuật toán IT2FCM Phase 2: Phân cụm cộng tác Repeat Trao đổi ma trận phân hoạch và tâm cụm giữa các tập dữ liệu D[ii] For each data site D[ii]. Tính ma trận phân hoạch cộng tác u~ Tính ma trận hệ số cộng tác 𝛽 Repeat Tính ma trận α Tính ma trận trọng số ω Tính ma trận phân hoạch u 18 Until|𝑈𝓉 − 𝑈𝓉−1| 𝑡𝑚𝑎𝑥. End for Until|𝑉𝑡 − 𝑉𝑡−1| 𝑡𝑚𝑎𝑥 End 3.1.5 Thử nghiệm và đánh giá Thử nghiệm so sánh hiệu quả của nó với các thuật toán IIT2FCM, thuật toán CFCM và thuật toán FCM. Dữ liệu thử nghiệm gồm ba tập là ảnh vệ tinh: TP. Thanh Hóa; TP. Thái Nguyên; H. Kỳ Hợp Nghệ An với kênh 3 và 4. Bảng 3.2 Chỉ số đánh giá phân cụm cho TP. Thanh Hóa FCM CFCM IIT2FCM MKCFCM SMKCFCM FS 2.3456 3.7612 3.9871 4.6735 4.7867 SSE 156.5873 122.8734 98.8745 88.7621 81.6784 DI 0.1254 0.3549 0.7875 0.7963 0.8058 DBI 5.6712 4.7643 1.3794 1.2623 1.2837 PCI 0.4533 0.6823 0.7862 0.8632 0.8751 CEI 4.7829 2.8961 0.9982 0.9985 0.9985 SI 0.9673 0.7862 0.4672 0.3672 0.2871 XBI 0.378424 0.276494 0.138232 0.148723 0.129408 CLI 0.865314 0.897023 0.965734 0.9553116 0.978963 GCI 3.7287452 2.9826426 2.676874 2,8749717 2.074824 19 DT 10.317% 6.739% 1.968% 0.596% 1.014% Bảng 3.4 Chỉ số đánh giá phân cụm cho TP. Thái Nguyên FCM CFCM IIT2FCM MKCFCM SMKCFCM FS 2.1983 3.2985 4.2761 4.3872 4.4893 SSE 123.8763 119.2763 106.2745 98.8736 91.8763 DI 0.2437 0.3894 0.7658 0.8162 0.8641 DBI 6.2872 4.6253 1.5621 1.3876 1.299 PCI 0.2872 0.7982 0.8742 0.9031 0.9082 CEI 3.7624 2.0983 0.7761 0.5712 0.4826 SI 0.9487 0.7183 0.3981 0.4128 0.3983 XBI 0.465274 0.382749 0.208592 0.187264 0.177628 CLI 0.838759 0.865848 0.959247 0.923948 0.950831 GCI 4.284826 4.194786 3.682747 3.194982 2.687764 DT 7.736% 5.664% 2.728% 1.520% 1.002% Bảng 3.6 Chỉ số đánh giá phân cụm cho H. Quỳ Hợp FCM CFCM IIT2FCM MKCFCM SMKCFCM FS 3.3872 3.8762 4.8723 4.8692 4.9071 SSE 206.7843 178.3985 158.7814 140.8757 129.9856 DI 0.1107 0.3215 0.6534 0.6873 0.7109 DBI 5.7823 4.2761 2.6715 1.2313 1.0871 PCI 0.3652 0.7652 0.8802 0.8891 0.8895 CEI 2.7632 1.0963 0.4516 0.2511 0.2501 SI 0.9762 0.7965 0.4978 0.3123 0.3082 XBI 0.309846 0.237452 0.168982 0.158749 0.108414 CLI 0.769829 0.828769 0.946924 0.960845 0.959482 GCI 2.857827 2.276144 1.826746 1.439173 1.138756 DT 10.214% 8.146% 3.056% 1.061% 0.834% Bảng 3.7 Thời gian tính của các thuật toán Thời gian (giây) FCM IIT2FCM CFCM MKCFCM SMKCFCM Thanh Hóa 63.8742 98.7263 326.7263 417.8723 206.7282 Thái Nguyên 128.8233 196.8772 Quỳ Hợp 93.8729 136.7824 Tổng thời gian tính 286.5704 432.3859 326.7263 417.8723 206.7282 3.2 Phân cụm dữ liệu lớn dựa trên thuật toán phân cụm mờ cộng tác và giảm chiều dữ liệu 20 3.2.1 Kỹ thuật giảm chiều dữ liệu theo định lý Johnson Lindenstrauss Thuật toán 3.2 Giảm chiều dữ liệu Đầu vào: Tập dữ liệu𝑋 = {𝑥1, 𝑥2, , 𝑥𝑛} ∈ 𝑅 𝑝, p là số chiều ban đầu,  , và độ phân mảnh s. Đầu ra: dữ liệu sau giảm chiều Y= {𝑥1, 𝑥2, , 𝑥𝑛} ∈ 𝑅 𝑚 Begin Tính giá gị m từ  theo công thức (4.4) Tính ma trận G(m,k) theo phân phối Gaussian Tính ma trận ngẫu nhiên A với giá trị 0 hoặc 1 Tính ma trận nhân Hadamard Φs = 𝐴𝑠𝑜𝐺 Tính ma trận ngẫu nhiên Ψs = √ 2 π s m Φs Tính ma trận đầu ra Y=XoΨs End 3.2.2 Phân cụm dữ liệu lớn dựa trên thuật toán phân cụm cộng tác và giảm chiều dữ liệu Mô hình và thuật toán đề xuất đã hướng đến giải quyết vấn đề kích thước dữ liệu bằng cách giảm cả số cột và số hàng của dữ liệu. 21 Hình 3.10 Mô hình phân cụm dữ liệu lớn. 3.2.3 Thử nghiệm và đánh giá Để đánh giá mô hình đề xuất, thử nghiệm được tiến hành trên 3 tập dữ liệu với 05 và thời gian chạy để so sánh thuật toán RPFR- CFCM với các thuật toán FCM, rseFCM, spFCM, rsekFCM 3.2.3.1 Tập dữ liệu văn bản Bảng 3.8 Chỉ số đánh giá và thời gian tính toán với dữ liệu NIPS DI SI DBI XBI PCI Thời gian (s) RPFR - CFCM 0.8257 0.4251 2.0473 3.1201 0.1308 106 FCM 0.8024 0.4915 3.1546 3.5434 0.0915 598 rseFCM1 0.6841 0.6841 6.2381 5.0143 0.0848 46 rseFCM5 0.7035 0.6438 5.8472 4.8647 0.0861 63 rseFCM10 0.7543 0.6005 5.5142 4.5116 0.0917 81 spFCM 0.7816 0.6249 4.0651 4.0130 0.0958 100 rsekFCM1 0.6438 0.7365 6.3147 4.6527 0.0894 64 rsekFCM5 0.6752 0.7152 5.8461 4.5239 0.0911 78 22 rsekFCM10 0.6915 0.7009 5.5208 4.1035 0.0936 86 3.2.3.2 Thử nghiệm với dữ liệu nhận dạng bệnh động kinh(EEG)3 Bảng 3.9 Chỉ số đánh giá và thời gian tính toán với dữ liệu EEG DI SI DBI XBI PCI Thời gian (s) RPFR - CFCM 0.6251 0.3652 3.2471 2.7614 0.5163 73 FCM 0.6197 0.3729 3.3621 3.9716 0.4327 235 rseFCM1 0.3145 0.5841 5

Các file đính kèm theo tài liệu này:

  • pdftom_tat_luan_an_phat_trien_mot_so_mo_hinh_phan_cum_mo_cong_t.pdf
Tài liệu liên quan