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

  • Số trang: 122 |
  • Loại file: PDF |
  • Lượt xem: 41 |
  • Lượt tải: 0
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 LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI –2019 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 LUẬN ÁN TIẾN SĨ TOÁN HỌC Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62.46.01.10 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS Ngô Thành Long HÀ NỘI –2019 1 LỜI CAM ĐOAN Tôi xin cam đoan các kết quả trình bày trong luận án là công trình nghiên cứu của tôi dưới sự giám sát của giảng viên hướng dẫn. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào luận án. Các kết quả trong luận án là trung thực và chưa từng được công bố trong bất kỳ công trình nào khác. Nghiên cứu sinh Đặng Trọng Hợp 2 LỜI CẢM ƠN Luận án được nghiên cứu sinh hoàn thành dưới sự hướng dẫn tận tình, nghiêm khắc của PGS. TS. Ngô Thành Long, lời đầu tiên tôi xin bày tỏ lòng kính trọng và sự biết ơn sâu sắc tới Thầy. Những định hướng, nhận xét và góp ý của Thầy trong suốt quá trình nghiên cứulà những bài học vô cùng quý giá đối với tôi không chỉ trong việc hoàn thành luận án mà trong cả các hoạt động chuyên môn sau này. Tôi xin chân thành cảm ơn GS. TSKH Phạm Thế Long, PGS. TS. Bùi Thu Lâm, TS. Tống Minh Đức, TS. Hoa Tất Thắng, TS. Nguyễn Văn Giang và các thầy cô trong Bộ môn Hệ thống thông tin, Khoa Công nghệ thông tin Học viện Kỹ thuật quân sự đã có những góp ý quý báu trong quá trình nghiên cứu và các hội thảo chuyên môn của Khoa, Bộ môn. Tác giả xin gửi lời cảm ơn chân thành đến Khoa Công nghệ thông tin, Phòng Sau đại học,Học Viện Kỹ Thuật Quân Sự đã tạo điều kiện thuận lợi trong quá trình học tập, nghiên cứu và hoàn thành luận án. Tôi xin cảm ơn Trung tâm Công nghệ thông tin, Phòng Đào tạo và Lãnh đạo Trường Đại học Công nghiệp, nơi tôi công tác đã tạo điều kiện cơ sở vật chất, thời gian, sắp xếp công việc cơ quan hợp lý và thường xuyên động viên, nhắc nhở tôi trong quá trình nghiên cứu. Cuối cùng, tôi xin cảm ơn gia đình, bạn bè và đồng nghiệp những người đã luôn bên cạnh động viên, chia sẻ và hỗ trợ tôi trong quá trình học tập, nghiên cứu. 3 MỤC LỤC DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT ..................................... 5 DANH MỤC CÁC BẢNG BIỂU ..................................................................... 7 DANH MỤC CÁC HÌNH VẼ .......................................................................... 8 DANH MỤC THUẬT TOÁN .......................................................................... 9 MỞ ĐẦU ......................................................................................................... 10 1. Tính cấp thiết của nội dung nghiên cứu. ..................................................... 10 2. Mục tiêu nghiên cứu của luận án ................................................................ 11 3. Đối tượng nghiên cứu.................................................................................. 11 4. Phạm vi nghiên cứu ..................................................................................... 12 5. Phương pháp nghiên cứu............................................................................. 12 6. Cấu trúc của luận án .................................................................................... 12 CHƯƠNG 1. TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU ............................. 14 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ở ................... 14 1.1.1 Phân cụm mờ.............................................................................. 14 1.1.2 Phân cụm mờ cộng tác ............................................................... 16 1.1.3 Tập mờ ....................................................................................... 19 1.1.4 Khoảng cách trong phân cụm .................................................... 23 1.1.5 Chỉ số đánh giá chất lượng phân cụm ........................................ 24 1.2 Tổng quan về phân cụm mờ cộng tác ....................................................... 28 1.2.1 Tổng quan về phân cụm mờ ....................................................... 29 1.2.2 Tổng quan về phân cụm mờ cộng tác ........................................ 31 1.2.3 Phân cụm dữ liệu lớn ................................................................. 33 1.2.4 Một số kỹ thuật kết hợp nâng cao chất lượng phân cụm ........... 38 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 ....... 43 1.4 Những đóng góp chính của luận án .......................................................... 45 1.5 Kết luận chương 1 ..................................................................................... 45 CHƯƠNG 2. PHÂN CỤM MỜ LOẠI 2 KHOẢNG CỘNG TÁC ................ 46 2.1 Phân cụm mờ loại 2 khoảng cộng tác ....................................................... 46 2.2 Phân cụm mờ loại 2 khoảng cộng tác khi số cụm khác nhau ................... 53 2.3 Thuật toán phân cụm mờ loại 2 khoảng cộng tác (CIVFCM) .................. 56 2.4 Thử nghiệm và đánh giá ............................................................................ 57 4 2.4.1 Thử nghiệm với dữ liệu sinh ngẫu nhiên ................................... 58 2.4.2 Thử nghiệm với dữ liệu S1, S4 ................................................... 60 2.4.3 Thử nghiệm với dữ liệu thời tiết Canada ................................... 62 2.4.4 Thử nghiệm với dữ liệu ảnh vệ tinh ........................................... 64 2.4.5 Một số đánh giá .......................................................................... 70 2.5 Kết luận chương 2 ..................................................................................... 71 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 ................................................................................... 73 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 ...... 74 3.1.1 Phân cụm mờ cộng tác đa nhân ................................................. 74 3.1.2 Tạo hạt siêu điểm ảnh (Super-pixel granulation) ...................... 77 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ố ............................................................................................ 78 3.1.4 Thuật toán phân mờ cụm cộng tác đa nhân. .............................. 84 3.1.5 Thử nghiệm và đánh giá ............................................................ 86 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 .................................................................................................... 96 3.2.1 Kỹ thuật giảm chiều dữ liệu theo định lý Johnson Lindenstrauss............................................................................................... 97 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 ....................................................................................... 99 3.2.3 Thử nghiệm và đánh giá .......................................................... 101 3.3 Kết luận chương 3 ................................................................................... 105 KẾT LUẬN ................................................................................................... 107 1. Kết luận chung .......................................................................................... 107 2. Những đóng góp mới của luận án ............................................................. 108 3. Kiến nghị về một số hướng nghiên cứu tiếp theo ..................................... 108 DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ .............................................. 109 TÀI LIỆU THAM KHẢO ............................................................................. 110 5 DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT Kí hiệu FL FS T2FL T2FS IT2FS IVFS FOU SCI SCIE WoS SoI FSoI SSE SSE PCI XBI DI SI CEI DBI CR CDI FMI JI MI RI FCM KFCM Thuật ngữ tiếng Anh Fuzzy Logic Fuzzy Sets Type-2 Fuzzy Logic Type-2 Fuzzy Sets Interval Type-2 Fuzzy Sets Interval-Valued Fuzzy Sets Footprint Of Uncertainty Science Citation Index Science Citation Index Expanded Web of Science Silhouette Criterion Index Fuzzy Silhouette Index Sum of Squared Error Fuzzy Sum of Squared Error Bezdek’s Partition Coefficient Index Xie and Beni Index Dunn’s Index Separation Index Classification Entropy Index Davies-Bouldin’s Index Classification Rate Czekanowski-Dice Index Folkes-Mallows Index Jaccard Index McNemar Index Rand Index Fuzzy C-Means Kernel FCM Thuật ngữ tiếng Việt Logic mờ Tập mờ Logic mờ loại 2 Tập mờ loại 2 Tập mờ loại 2 khoảng Tập mờ giá trị khoảng Vùng không rõ ràng, vùng mờ Danh mục trích dẫn khoa học Danh mục trích dẫn khoa học mở rộng Kho dữ liệu thông tin khoa học ISI Chỉ số đánh giá SoI Chỉ số đánh giá phân cụm mờ FSoI Trung bình bình phương lỗi Trung bình bình phương lỗi mờ Chỉ số đánh giá phân cụm PCI Chỉ số đánh giá phân cụm XBI Chỉ số đánh giá phân cụm DI Chỉ số đánh giá phân cụm SI Chỉ số đánh giá phân cụm CEI Chỉ số đánh giá phân cụm DBI Tỉ lệ phân loại đúng Chỉ số đánh giá phân cụm CDI Chỉ số đánh giá phân cụm FMI Chỉ số đánh giá phân cụm JI Chỉ số đánh giá phân cụm MI Chỉ số đánh giá phân cụm RI Thuật toán Phân cụm mờ Thuật toán phân cụm mờ nhân 6 Thuật toán phân cụm mờ đa nhân Thuật toán Phân cụm mờ cộng tác Thuật toán phân cụm mờ loại 2 CIVFCM khoảng cộng tác Thuật toán phân cụm mờ cộng tác đa MKCFCM nhân Thuật toán phân cụm mờ cộng tác đa SMKCFCM Superpixels MKFCM nhân sử dụng siêu điểm ảnh Clustering by Fast Search Phân cụm bằng cách tìm kiếm nhanh CFSFD and Find of Density Peaks và tìm các điểm mật độ cao RPFRRandom Projection Phân cụm mờ cộng tác kết hợp giảm CFCM Features Reduction CFCM chiều bằng phép chiếu ngẫu nhiên random sampling plus Thuật toán FCM mở rộng lẫu mẫu rseFCM extension Fuzzy c-Means nhẫu nhiên. spFCM Single Pass FCM Thuật toán FCM từng phần Random Sample and Thuật toán FCM sử dụng nhân và lẫy rsekFCM Extend Kernel FCM mẫu ngẫu nhiên OF Objective Function Hàm mục tiêu GrC Granular Computing Tính toán hạt IC Information Granules Hạt thông tin N Number of data objects Số đối tượng dữ liệu M Number of features of data Số thuộc tính của dữ liệu X={x1, x2,..., xN}RM là một tập dữ liệu M chiều, xiX là đối tượng X dữ liệu thứ i Department of National DNRS Cục Viễn thám Quốc gia Remote Sensing MKFCM CFCM Multi Kernel FCM Collaborative FCM Collaborative Interval valued FCM Multi KernelCollaborative FCM 7 DANH MỤC CÁC BẢNG BIỂU Bảng 1.1 Phân loại dữ liệu lớn ........................................................................ 34 Bảng 2.1. Kết quả phân cụm với thử nghiệm 2.1 ........................................... 58 Bảng 2.2. Chỉ số đánh giá với thử nghiệm 2.1................................................ 59 Bảng 2.3 Chỉ số đánh giá của các thuật toán với dữ liệu S1 ........................... 61 Bảng 2.4 Chỉ số đánh giá của các thuật toán với dữ liệu S4 ........................... 62 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 Canada ... 64 Bảng 2.6 Tỉ lệ % diện tích các vùng của Hà Nội ............................................ 67 Bảng 2.7 Tỉ lệ % diện tích các vùng của Bảo lộc ........................................... 67 Bảng 2.8 Chỉ số đánh giá chất lượng phân cụm các thuật toán ...................... 69 Bảng 2.9 Độ phức tạp tính toán của các thuật toán ........................................ 71 Bảng 3.1 Kết quả phân cụm từng vùng TP. Thanh Hóa ................................. 90 Bảng 3.2 Chỉ số đánh giá phân cụm cho TP. Thanh Hóa .............................. 91 Bảng 3.3 Kết quả phân cụm từng vùng TP. Thái Nguyên .............................. 92 Bảng 3.4 Chỉ số đánh giá phân cụm cho TP. Thái Nguyên ........................... 93 Bảng 3.5 Kết quả phân cụm từng vùng H. Quỳ Hợp ...................................... 94 Bảng 3.6 Chỉ số đánh giá phân cụm cho H. Quỳ Hợp ................................... 94 Bảng 3.7 Thời gian tính của các thuật toán..................................................... 96 Bảng 3.8 Chỉ số đánh giá và thời gian tính toán với dữ liệu NIPS ............... 102 Bảng 3.9 Chỉ số đánh giá và thời gian tính toán với dữ liệu EEG ................ 103 Bảng 3.10 Chỉ số đánh giá và thời gian tính toán với dữ liệu MNIST ......... 104 8 DANH MỤC CÁC HÌNH VẼ Hình 1.1 Kết quả phân cụm (a) trước cộng tác, (b) sau khi cộng tác. ............ 17 Hình 1.2 Mô hình phân cụm mờ cộng tác....................................................... 18 Hình 1.3 Hàm thuộc: (a) loại 1 và (b) loại 2 ................................................... 21 Hình 1.4 Mối liên hệ giữa các loại tập mờ ...................................................... 23 Hình 2.1 Kết quả thử nghiệm 2.2 với thuật toán CIVFCM2 .......................... 59 Hình 2.2 Kết quả phân cụm dữ liệu S1 ........................................................... 61 Hình 2.3 Kết quả phân cụm dữ liệu S4 ........................................................... 61 Hình 2.4 Biểu đồ hiển thị giá trị các chỉ số theo tham số mờ hóa m1, m2 ...... 64 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 ............. 66 Hình 2.6 Biểu đồ so sánh tỉ lệ % diện tích của Hà Nội................................... 67 Hình 2.7 Biểu đồ so sánh tỉ lệ % diện tích của Bảo lộc .................................. 68 Hình 2.8 Đồ thị kết quả các chỉ số với nhiều bộ tham số m1 và m2................ 69 Hình 3.1: Ảnh vệ tinh kênh 3 và 4 của TP. Thanh Hóa .................................. 87 Hình 3.2: Ảnh vệ tinh kênh 3 và 4 của TP. Thái Nguyên ............................... 87 Hình 3.3: Ảnh vệ tinh kênh 3 và 4 của H. Quỳ Hợp ....................................... 88 Hình 3.4 Sơ đồ tính toán thử nghiệm .............................................................. 89 Hình 3.5 Kết quả phân cụm TP. Thanh Hóa ................................................... 90 Hình 3.6 So sánh % diện tích các cụm TP. Thanh Hóa .................................. 91 Hình 3.7 Kết quả phân cụm TP. Thái Nguyên ................................................ 92 Hình 3.8 So sánh % diện tích các cụm TP. Thái Nguyên ............................... 93 Hình 3.9 Kết quả phân cụm H. Quỳ Hợp........................................................ 94 Hình 3.10 So sánh % diện tích các cụm H. Quỳ Hợp ..................................... 94 Hình 3.11 Mô hình phân cụm dữ liệu lớn. .................................................... 100 9 DANH MỤC THUẬT TOÁN Thuật toán 1.1. Phân cụm mờ FCM ................................................................ 15 Thuật toán 1.2. rseFCM .................................................................................. 35 Thuật toán 1.3 wFCM ..................................................................................... 36 Thuật toán 1.4 spFCM..................................................................................... 37 Thuật toán 1.5 rsekFCM ................................................................................. 37 Thuật toán 1.6. Tính siêu điểm ảnh SLIC ....................................................... 41 Thuật toán 2.1 Phân cụm mờ loại 2 khoảng cộng tác ..................................... 56 Thuật toán 3.1 SMKCFCM ............................................................................. 84 Thuật toán 3.2 Giảm chiều dữ liệu .................................................................. 99 Thuật toán 3.3 RPFR-CFCM ........................................................................ 100 10 MỞ ĐẦU 1. Tính cấp thiết của nội dung nghiên cứu. 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 thuộc các cụm khác nhau thì khác nhau. Đây là một kỹ thuật học không giám sát trong máy học. Phân cụm được ứng dụng rộng rãi trong lĩnh vực khác nhau như: khai phá dữ liệu, xử lý ảnh, y học, kỹ thuật, phân tích thị trường… Có nhiều nghiên cứu về các kỹ thuật và cách tiếp cận để giải quyết bài toán phân cụm nhưng chúng đều có mục tiêu là nâng cao chất lượng phân cụm và tốc độ thực hiện của thuật toán. Trong đó các thuật toán phân cụm dữ liệu bằng ứng dụng tập mờ đã nhận được sự quan tâm của nhiều nhà khoa học,đặc biệt là sự phát triển mạnh mẽ của tập mờ loại 2 đã đem lại hiệu quả, độ chính xác cao, khử độ không chắc chắn chắn trong ứng dụng thực tế. Khi chúng ta có nhiều tập dữ liệu có mối liên hệ với nhau thì việc phân cụm trong mỗi tập dữ liệu này sẽ có ảnh hưỏng, tác động đến việc phân cụm trên các tập dữ liệu khác.Tuy nhiên, vì nhiều lý do khác nhau như vấn đề tính riêng tư của dữ liệu, vấn đề bảo mật, vấn đế đường truyền mà các dữ liệu này không thể thực hiện phân cụm một cách tập trung.Khi đó, phương phápphân cụm cộng tác (Collaborative clustering) sẽ giải quyết được vấn đề trên bằng cách phân cụm tại từng tập dữ liệu con, sau đó thực hiện trao đổi thông tin về cấu trúc trên mỗi tập cho các tập dữ liệu còn lại và thực hiện bước phân cụm cộng tác để điều chỉnh kết quả phân cụm trên từng tập nhằm đạt được sự tương đồng về kết quả phân cụm của các tập dữ liệ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 là 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 11 nghiên cứu và giải pháp một cách triệt để. Đề tài “Phát triển một số mô hình phân cụm mờ cộng tác” nghiên cứu về mô hình phân cụm cộng tác và đề xuất một số cải tiến, mô hình mới giải quyết các yêu cầu trên. 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, cụ thể là:  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. Các kỹ thuật được nghiên cứu để giải quyết cho các vấn đề trên có thể gồm: ứng dụng của tập mờ loại 2, các kỹ thuật nhân và đa nhân, tính toán hạt và siêu điểm ảnh, kỹ thuật giảm chiều dữ liệu. Các giải pháp đề xuất cần được mô hình hóa, thuật toán hóa, có sự mô phỏng và thử nghiệm với các bộ dữ liệu thực tế để chứng minh tính hiệu quả. 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. 12 4. Phạm vi nghiên cứu  Nghiên cứu lý thuyết tập mờ loại 1, 2và các phương pháp giải mờ.  Nghiên cứu các thuật toán phân cụm dữ liệu và một số vấn đề 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  Tìm kiếm và phát triển một số ứng dụng mô hình phân cụm mờ cộng tác. 5. Phương pháp nghiên cứu Luận án sử dụng công cụ giải tích để thiết lập các phương trình tính toán, tìm kiếm lời giải tối ưu và xây dựng, chứng minh các định lý trong hệ mờ. Ngoài ra, luận án cũng sử dụng phương pháp lập trình cài đặt các thuật toán với các bộ dữ liệu máy học và chỉ số đánh giá và thực tế nhằm so sánh kết quả nghiên cứu của luận án với các kết quả nghiên cứu khác để khẳng định tính hiệu quả của các giải pháp được đề xuất. Thực hiện nghiên cứu một cách có khoa học từ định hướng của giảng viên hướng dẫn với các công trình nghiên cứu đã công bố cùng lĩnh vực, phát hiện ra các vấn đề cần giải quyết, đề ra giải pháp khắc phục, có chứng minh và thực nghiệm từ đó công bố kết quả trên các hội thảo và tạp chí có uy tín. 6. 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: trình bày các kiến thức và kết quả nghiên cứu đã được công bố liên quan tới phân cụm mờ cộng tác như bài toán phân cụm dữ liệu, phân cụm dữ liệu cộng tác; các loại thuật toán phân cụm và phân cụm mờ; thước đo khoảng cách; tính toán hat; siêu điểm ảnh; xác định số cụm và tâm cụm; chỉ số đánh giá kết quả phân cụm; kỹ thuật nhân; kỹ thuật giảm chiều dữ liệu… 13 Chương 2.Phân cụm mờ loại 2 khoảng cộng tác: trình bày mô hình và thuật toán phân cụm giá trị khoảng cộng tác và các thử nghiệm minh họa tính hiệu quả của thuật toán. Chương 3.Một số cải tiến thuật toán phân cụm mờ cộng tác: trình bày mô hình ứng dụng kỹ thuật đa nhân trong giải quyết vấn đề phức tạp dữ liệu và chia tách cụm không tuyến tính, kết hợp với tính soán hạt siêu điểm ảnh có trọng số, ứng dụng kỹ thuật giảm chiều cho dữ liệu lớn bằng phương pháp chiếu ngẫu nhiên từ đó thực hiện phân cụm mờ cộng tác và các thử nghiệm. Phần kết luận nêu tóm tắt các vấn đề nghiên cứu, các mô hình phân cụm mờ cộng tác được để xuất trong luận án cũng như các hướng nghiên cứu liên quan có thể mở rộng. 14 CHƯƠNG 1. TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU Phân tích dữ liệu đóng vai trò quan trọng trong nhiều ứng dụng thực tế hiện nay như y học, quảng cao, phân tích thị trường, trong xử lý ảnh, nhận dạng mẫu... Đặc biệt trong kỷ nguyên cách mạng công nghiệp 4.0 và vạn vật kết nối hiện nay, lượng dữ liệu được tạo ra ngày càng nhiều, loại dữ liệu đa dạng thì càng cần có các công cụ tự động phân tích dữ liệu. Phân cụm dữ liệu là một công cụ học không giám sát được ứng dụng rất phổ biến trong phân tích dữ liệu. Chương này luận án trình bày những khái niệm cơ bản và tình hình nghiên cứu các vấn đề liên quan tới phân cụm dữ liệu, trong đó phân cụm mờ cộng tác được tìm hiểu và trình bày chi tiết. 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ờ Thuật toán phân cụm sử dụng các lý thuyết tập mờ để phân hoạch các đối tượng vào các cụm được Dunn giới thiệu [2] và Bezdek tổng quát hóa thành thuật toán FCM [3]. Thuật toán phân hoạch n đối tượng 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } ∈ 𝑅𝑀 vào c cụm dựa trên tối thiểu hàm mục tiêu đo chất lượng phân hoạch và tâm cụm. Một phân hoạch mờ của n đối tượng X vào C cụm được biểu diễn bằng ma trận 𝑈 = [𝑢𝑖𝑘 ] với 𝑢𝑖𝑘 là độ thuộc của đối tượng thứ k vào cụm i. 𝑢11 ⋯ 𝑢1𝑛 ⋱ ⋮ ] 𝑈𝑐𝑛 = [ ⋮ 𝑢𝑐1 ⋯ 𝑢𝑐𝑛 Hàm mục tiêu mờ được Dunn định nghĩa như sau: Min 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 : Min Trong đó: 𝑚 2 𝐽𝑚 (𝑈, 𝑣) = ∑𝑛𝑘=1 ∑𝑐𝑖=1 𝑢𝑖𝑘 𝑑𝑖𝑘 15 m  1,   là trọng số mũ hay còn gọi là tham số mờ. v là vector tâm cụm với 𝑣𝑖 ∈ 𝑅𝑀 là trọng tâm của cụm thứ i dik là khoảng cách theo thước đo Euclide giữa mẫu dữ liệu xk với trọng tâm cụm thứ i là vi và được tính bằng công thức sau: 1/2 d  dik  d ( xk  vi )  xk  vi    ( xkj  vij ) 2   j 1  (1.5) uik   0,1 là bậc hay độ thuộc của dữ liễu mẫu xk vào cụm thứ i với ràng buộc ∑𝑐𝑖=1 𝑢𝑖𝑘 = 1∀1 ≤ 𝑘 ≤ 𝑛 và 0 ≤ ∑𝑛𝑘=1 𝑢𝑖𝑘 ≤ 𝑛∀1 ≤ 𝑖 ≤ 𝑐 Bezdek [3] đã chứng minh được hàm mục tiêu (1.1) đạt giá trị tối thiểu cục bộ khi: 1 𝑢𝑖𝑘 = 𝑑 ∑𝑐𝑗=1( 𝑖𝑘 ) 2 𝑚−1 (1.6) 𝑑𝑗𝑘 𝑣𝑖 = 𝑚 ∑𝑛 𝑘=1 𝑢𝑖𝑘 𝑥𝑘 𝑚 ∑𝑛 𝑘=1 𝑢𝑖𝑘 (1.7) 𝑉ớ𝑖 1 ≤ 𝑖 ≤ 𝑐, 1 ≤ 𝑘 ≤ 𝑛 Thuật toán phân cụm mờ FCM thực hiện việc lặp lại tính toán giá trị u và v và được mô tả như sau : Thuật toán 1.1. Phân cụm mờ FCM Đầu vào: Tập dữ liệu 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } ∈ 𝑅 𝑝 , số cụm c (1 - Xem thêm -