Tài liệu Phát triển một số mô hình phân cụm mờ cộng tác (tt)

  • Số trang: 27 |
  • Loại file: PDF |
  • Lượt xem: 29 |
  • Lượt tải: 1
sharebook

Tham gia: 25/12/2015

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ ĐẶNG TRỌNG HỢP PHÁT TRIỂN MỘT SỐ MÔ HÌNH PHÂN CỤM MỜ CỘNG TÁC Chuyên ngành: Cơ sở toán học cho tin học Mã số: 9460110 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2019 Công trình được hoàn thành tại HỌC VIỆN KỸ THUẬT QUÂN SỰ Người hướng dẫn khoa học PGS. TS Ngô Thành Long Phản biện 1: PGS.TSKH NGUYỄN CÁT HỒ VIỆN CNTT - VIỆN HÀN LÂM KHCN VIỆT NAM Phản biện 2: PGS.TS TRẦN NGUYÊN NGỌC HỌC VIỆN KỸ THUẬT QUÂN SỰ Phản biện 3: PGS.TS LÊ TRỌNG VĨNH ĐH KHTN - ĐH QUỐC GIA HÀ NỘI Luận án được bảo vệ tại Hội đồng đánh giá luận án cấp Học viện theo quyết định số 2110/QĐ-HV, ngày 14 tháng 06 năm 2019 của Giám đốc Học viện Kỹ thuật Quân sự, họp tại Học viện Kỹ thuật Quân sự vào hồi giờ ngày tháng năm 2019. Có thể tìm hiểu luận án tại: - Thư viện Học viện Kỹ thuật Quân sự. - Thư viện Quốc gia. 1 MỞ ĐẦU 1. Tính cấp thiết của nội dung nghiên cứu. Trong thực tế, dữ liệu phân cụm thường có sự không chắc chắn và có nhiễu, nhiều dữ liệu có sự chia tách các cụm không tuyến tính, nhiều loại dữ liệu có số chiều và kích thước lớn. Hiện nay có nhiều nhà khoa học quan tâm đến bài toán phân cụm cộng tác, tuy nhiên những vấn đề trên vẫn chưa có các nghiên cứu và giải pháp một cách triệt để. 2. Mục tiêu nghiên cứu của luận án Nghiên cứu bài toán phân cụm mờ cộng tác, các vấn đề còn tồn tại của phân cụm mờ cộng tác khi ứng dụng trong các bài toán thực tế và đề ra các mô hình, giải pháp nâng cao hiệu quả phân cụm: - Giải pháp cho vấn đề không rõ ràng, không chắc chắn của dữ liệu thực tế cần phân cụm. - Giải pháp cho vấn đề dữ liệu phức tạp, hình dạng và sự chia tách các cụm không tuyến tính. - Giải pháp cho vấn đề dữ liệu nhiều chiều, kích thước lớn, độ phức tạp tính toán cao thường gặp trong thực tế hiện nay. 3. Đối tượng nghiên cứu Các thuật toán phân cụm mờ, tập mờ loại 1, loại 2 và loại 2 giá trị khoảng; Mô hình và thuật toán phân cụm cộng tác; Phương pháp nhân và các thuật toán phân cụm dựa trên phương pháp nhân và tính toán hạt siêu điểm ảnh; Phương pháp giảm chiều dựa trên phép chiếu ngẫu nhiên và ứng dụng trong bài toán phân cụm. 4. Phạm vi nghiên cứu - Nghiên cứu lý thuyết tập mờ loại 1, 2. - Nghiên cứu các thuật toán phân cụm dữ liệu và một số vấn đề 2 liên quan trong bài toán phân cụm dữ liệu. - Nghiên cứu mô hình và thuật toán phân cụm mờ cộng tác. - Nghiên cứu và phát triển các kỹ thuật phân cụm mờ cộng tác trên cơ sở ứng dụng tập loại 2 giá trị khoảng, phương pháp nhân, tính toán hạt siêu điểm ảnh và kỹ thuật giảm chiều dữ liệu 5. Cấu trúc của luận án Chương 1. Tổng quan về phân cụm mờ cộng tác Chương 2. Phân cụm mờ giá trị khoảng cộng tác Chương 3. Một số cải tiến thuật toán phân cụm mờ cộng tác Kết luận nêu tóm tắt vấn đề nghiên cứu, các mô hình phân cụm mờ cộng tác được để xuất cũng như các hướng nghiên cứu mở rộng. CHƯƠNG 1. TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1.1 Giới thiệu phân cụm mờ cộng tác và một số kiến thức cơ sở 1.1.1 Phân cụm mờ FCM (Fuzzy C – Means) Hàm mục tiêu mờ được Dunn định nghĩa như sau: 2 𝐽𝑚 (𝑈, 𝑣) = ∑𝑛𝑘=1 ∑𝑐𝑖=1 𝑢𝑖𝑘 𝑑𝑖𝑘 Bezdek khái quát hóa hàm mục tiêu mờ bằng cách đưa ra trọng số mũ m  1 , là số thực như sau : 𝑚 2 𝐽𝑚 (𝑈, 𝑣) = ∑𝑛𝑘=1 ∑𝑐𝑖=1 𝑢𝑖𝑘 𝑑𝑖𝑘 Bezdek chứng minh hàm mục tiêu đạt giá trị tối thiểu cục bộ khi: 𝑢𝑖𝑘 = 𝑣𝑖 = 1 2 𝑚 ∑𝑛 𝑢𝑖𝑘 𝑑𝑥 𝑘 𝑚−1 𝑘=1 𝑐 𝑖𝑘 ∑𝑗=1( 𝑚 ) 𝑑𝑗𝑘 ∑𝑛 𝑘=1 𝑢𝑖𝑘 (1.4) (1.5) 𝑉ớ𝑖 1 ≤ 𝑖 ≤ 𝑐, 1 ≤ 𝑘 ≤ 𝑛 Thuật toán phân cụm mờ FCM được mô tả như sau : Thuật toán 1.6. Phân cụm mờ FCM Đầu vào: Tập dữ liệu 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } ∈ 𝑅𝑝 , số cụm c (1 𝑡𝑚𝑎𝑥 . End for Until|𝑉 𝑡 − 𝑉 𝑡−1 | < 𝜀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 FS 11.554 NA 13.980 CIVFCM2 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 2.4.3 Thử nghiệm với dữ liệu thời tiết Canada 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. 1 https://cs.joensuu.fi/sipu/datasets/ 2 http://climate.weather.gc.ca/ 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 FS 12.309 NA FSSE DI DBI PCI CEI SI 490.37 0.2247 5.0594 2.7768 1.9078 0.4329 NA 0.2401 5.2677 NA NA 0.7669 CIVFCM1 (m1, m2) 14.2741 (1.8,3) 387(1.8,3) 0.2398 (2, 2.8) 4.09(1.4,2.8) 3.5506(1.8, 3) 0.9368(1.8, 3) 0.3812(1.8, 3) CIVFCM2 (m1, m2) 12.7577 (2,2.8) 469(2, 2.8) 0.2287(2, 2.6) 4.05(2,3) 2.8012(2, 2.4) 1.7078(2, 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] [Ảnh gốc Bảo lộc] [CIVFCM2] [CFSFD] [CFCM] [CIVFCM1] [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 FS 6.2762 NA 6.941 CIVFCM2 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 1 Thuật toán CFCM Độ phức tạp tính toán 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: N [ ii ] c N [ ii ] k 1 i 1 k 1 jj 1, jj ii Q[ii ]    uik2 [ii]( (x k )  vi )2   Min P c   [ii | jj ] (uik  uik~ [ii | jj ])2 ( (x k )  vi )2 i 1 Ma trận phân hoạch để hàm mục tiêu trên đạt giá trị tối thiểukhi: P urs   jj 1, jj  ii  [ii | jj ]urs~ [ii | jj ] P (1    [ii | jj ]) jj 1, jj  ii 1  c d rs2  2 d j 1 js   c 1    j 1    P  jj 1, jj  ii  [ii | jj ]u ~js [ii | jj ]  P  (1   [ii | jj ]) jj 1, jj  ii     M dik2    iktt2 t 1 1 M  t 1 t  1 N [ ii ] c  u k 1 i 1 N [ ii ] c  u k 1 i 1 N [ ii ] 2 ik 2 ik P [ii ] ikt   k 1 jj 1, jj  ii N [ ii ] P [ii ] ikt    k 1 jj 1, jj  ii N [ ii ]  ikt  K t ( xk , xk )  2 u j 1 2 ij   u j11 j 2 1 N [ ii ] u 2 ik i 1 c  [ii | jj ] (uik  uik~ [ii | jj ]) 2  ikt i 1 [ii ]  N [ ii ] P    [ii | jj ](uij  uij~ [ii | jj ]) 2 K t ( xk , x j )    [ii | jj ](uij  uij~ [ii | jj ]) 2 j 1 jj 1, jj  ii N [ ii ] P j 1 jj 1, jj  ii N [ ii ] N [ii ] [ii ]uij2 2 [ii ]K t ( x j1 , x j 2 )  2  P   j11 j 2 1 jj 1, jj  ii N [ ii ]  N [ ii ] 2   uik [ii ]   j11  j11 P  2 ij1  [ii | jj ] (uik  uik~ [ii | jj ]) 2  ikt [ii ]K t ( xk , x j )  j 1 N [ ii ] N [ii ] c  N [ ii ] N [ii]    jj 1, jj  ii j11 j 2 1 2 P  jj 1, jj  ii  [ii | jj ]uij21 (uij 2  uij~2 [ii | jj ]) 2 K t ( x j1 , x j 2 )  2  [ii | jj ](uij  uij~ [ii | jj ]) 2   [ii | jj ](uij1  uij~1[ii | jj ]) 2 (uij 2  uij~2 [ii | jj ]) 2 K t ( x j1 , x j 2 ) N [ ii ]  N [ ii ] 2   uik [ii ]   j11  j11 P  jj 1, jj  ii   [ii | jj ](uij  uij~ [ii | jj ]) 2   2 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: Q[ii ]  N [ ii ] c N [ ii ]   u k 1 i 1 2 k ik [ii ]( (x k )  vi ) 2   P  c k 1 jj 1, jj  ii  [ii | jj ] (uik  uik~ [ii | jj ]) 2 ( (x k )  vi ) 2 i 1 Ma trận phân hoạch để hàm mục tiêu trên đạt giá trị tối thiểukhi: 𝑢𝑖𝑘 2 ∑𝑃𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 𝛽[𝑖𝑖|𝑗𝑗] u~ik [ii|jj] 𝑑𝑖𝑘 + = 𝑖𝑖 𝑗𝑗 u~ ii jj 𝑖𝑖 𝑗𝑗 ∑𝑃 𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 𝛽[ | ] ik [ | ] 1−∑𝑐𝑖=1 (𝜑𝑘 +∑𝑃 𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 𝛽[ | ]) 1 𝑐 ∑𝑖=1 2 (𝜑𝑘 +∑𝑃 𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 𝛽[ | ])𝑑𝑖𝑘 𝑖𝑖 𝑗𝑗 2 (𝜑𝑘 + ∑𝑃𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 𝛽[𝑖𝑖|𝑗𝑗])𝑑𝑖𝑘 M dik2    iktt2 t 1 1 M  t 1 t  1 N [ ii ] c   u k 1 i 1 N [ ii ] c 2 k ik   u k 1 i 1 2 k ik N [ ii ] [ii ] ikt   P  c k 1 jj 1, jj  ii N [ ii ] P [ii ] ikt    k 1 jj 1, jj  ii  [ii | jj ] (uik  uik~ [ii | jj ]) 2  ikt i 1 c  [ii | jj ] (uik  uik~ [ii | jj ]) 2  ikt i 1 17 N [ ii ]  ikt  K t ( xk , xk )  2 N [ ii ] j 1 2 j ij t    j11 j 2 1  u 2 j ik j j 1 jj 1, jj  ii N [ ii ] P [ii ]    j 1 jj 1, jj  ii N [ ii ] N [ii ]  j 2uij21[ii ]uij22 [ii ]K t ( x j1 , x j 2 )  2   j1  [ii | jj ](uij  uij~ [ii | jj ]) 2 K t ( xk , x j )  [ii | jj ](uij  uij~ [ii | jj ]) 2 P  j11 j 2 1 jj 1, jj  ii  [ii | jj ]uij21 (uij 2  uij~2 [ii | jj ]) 2 K t ( x j1 , x j 2 ) N [ ii ] P  N [ ii ] 2 ~ 2    j1uik [ii ]     [ii | jj ](uij  uij [ii | jj ])  j11 jj 1, jj  ii  j11  P  k N [ ii ] j 1 N [ ii ] N [ii ] P   u [ii]K ( x , x )    N [ ii ] N [ii]    jj 1, jj  ii j11 j 2 1 2  j 2  2 [ii | jj ](uij1  uij~1[ii | jj ]) 2 (uij 2  uij~2 [ii | jj ]) 2 K t ( x j1 , x j 2 ) j1 N [ ii ] P  N [ ii ] 2 ~ 2    j1uik [ii ]     [ii | jj ](uij  uij [ii | jj ])  j11 jj 1, jj  ii  j11  2 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 | < 𝜀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 FS SSE DI DBI PCI CEI SI XBI CLI GCI FCM 2.3456 156.5873 0.1254 5.6712 0.4533 4.7829 0.9673 0.378424 0.865314 3.7287452 CFCM 3.7612 122.8734 0.3549 4.7643 0.6823 2.8961 0.7862 0.276494 0.897023 2.9826426 IIT2FCM 3.9871 98.8745 0.7875 1.3794 0.7862 0.9982 0.4672 0.138232 0.965734 2.676874 MKCFCM 4.6735 88.7621 0.7963 1.2623 0.8632 0.9985 0.3672 0.148723 0.9553116 2,8749717 SMKCFCM 4.7867 81.6784 0.8058 1.2837 0.8751 0.9985 0.2871 0.129408 0.978963 2.074824
- Xem thêm -