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

Chia sẻ: Phong Tỉ | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

17
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu của đề tài là 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Toán học: Phát triển một số mô hình phân cụm mờ cộng tác

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. Mục tiêu nghiên cứu của luận á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. Phạ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 cụ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: 𝐽𝑚 (𝑈, 𝑣) = ∑𝑛𝑘=1 ∑𝑐𝑖=1 𝑢𝑖𝑘 𝑑𝑖𝑘 2 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 : 𝐽𝑚 (𝑈, 𝑣) = ∑𝑛𝑘=1 ∑𝑐𝑖=1 𝑢𝑖𝑘 𝑚 2 𝑑𝑖𝑘 Bezdek chứng minh hàm mục tiêu đạt giá trị tối thiểu cục bộ khi: 1 𝑢𝑖𝑘 = 2 (1.4) ∑𝑛 𝑘=1 𝑐 𝑚 𝑢𝑖𝑘 𝑑𝑥𝑖𝑘𝑘 𝑚−1 𝑣𝑖 = ∑𝑗=1( 𝑚 ) ∑𝑛 𝑑𝑗𝑘 (1.5) 𝑘=1 𝑢𝑖𝑘 𝑉ớ𝑖 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
3 Tâm cụm V; τ=0. //Đếm số vòng lặp. REPEAT Tính toán giá trị tâm cụm v theo công thứ (1.5); Cập nhật giá trị ma trận hàm thộcuci theo công thức (1.4); τ=τ+1; UNTIL (( J (n)  J (n  1)   ) hoặc (≥max)) 1.1.2 Phân cụm mờ cộng tác Bài toán phân cụm mờ cộng tác có hàm mục tiêu cần tối ưu là: N [ ii ] c N [ ii ] P c Min Q[ ii] =  u k =1 i =1 m ik [ii ]d ik2     [ii | jj]u k =1 jj =1, jj  ii i =1 m ik [ii ]d ik2 [ jj] Sử dụng phương pháp Lagrange để tối ưu hàm mục tiêu trên sẽ được công thức tính ma trận phân hoạch và tâm cụm như sau:  P  P  c   u~ js [ii | jj]    u~rs [ii | jj] 1 1   jj=1, jjii   jj=1, jjii urs [ii ] = c      (1   ( P  1))  (1 ( P 1)) d rs2 /d 2js  j =1  j =1   N [ ii ] P N [ ii ] u k =1 2 rk [ii ]xkt     (u jj =1, jj  ii k =1 rk [ii ]  u~rk [ii | jj]) 2 xkt vrt [ii ] = N [ ii ] P N [ ii ] u k =1 2 rk [ii ]     (u jj =1, jj  ii k =1 rk [ii ]  u~rk [ii | jj]) 2 1.1.3 Tập mờ 1.1.3.1 Tập mờ loại 1 (Type 1 Fuzzy Sets - FS) 1.1.2.2 Tập mờ loại 2 (Type 2 Fuzzy Sets - T2FS) 1.1.2.3 Tập mờ loại 2 khoảng (Interval Type 2 Fuzzy Sets - IT2FS) 1.1.2.4 Tập mờ giá trị khoảng (Interval – valued Fuzzy Sets) 1.1.4 Khoảng cách trong phân cụm Có hai cách đo phổ biến là đo khoảng cách và do độ tương tự. 1.1.4.1 Độ đo khoảng cách
4 1.1.4.2 Độ tương tự 1.1.5 Chỉ số đánh giá chất lượng phân cụm Các chỉ số đánh giá được chia làm 2 nhóm: chỉ số đánh giá trong và chỉ số đánh giá ngoài. 1.1.5.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 cá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 hạn chế của các nghiên cứu hiện có và mụ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 cụm mờ loại 2 khoảng cộng tác Hàm mục tiêu như sau: N [ ii ] c N [ ii ] P c  u [ii ]d ik2     [ii | jj]u m1 m1 m1 Q[ii] = ik ik [ii ]d ik2 [ jj] k =1 i =1 k =1 jj =1, jj  ii i =1 N [ ii ] c N [ ii ] P c  u [ii ]d ik2     [ii | jj]u m2 m2 m2 Q[ ii] = ik ik [ii ]d ik2 [ jj] k =1 i =1 k =1 jj =1, jj  ii i =1 Giá trị ma trận phân hoạch và tâm cụm xác định như sau: m 1 u rs 1 [ii ] = 1/(m1 1)   P c c   1 (d rs2    [ii | jj]d ks2 [ jj])  j =1   P c  (d js    [ii | jj]d ks [ jj])  jj =1, jj ii k =1 2 2  jj=1, jj ii k =1  m 1 u rs 2 [ii ] = 1/(m2 1)   P c c   1 (d rs2    [ii | jj]d ks2 [ jj])  j =1   P c jj=1, jjii k =1  (d js  2    [ii | jj ]d 2 ks [ jj ])   jj=1, jjii k =1 
9 N [ ii ] N [ ii ] u [ii ]xkt    [ii | jj]u rk1 vrt [ jj] m1 m rk m1 k =1 k =1 vrt [ii ] = N [ ii ] N [ ii ] u [ii ]    [ii | jj]u rk1 [ii ] m1 m rk k =1 k =1 N [ ii ] N [ ii ] u [ii ]x kt    [ii | jj]u m2 m2 rk rk v rt [ jj] m2 k =1 k =1 v rt [ii ] = N [ ii ] N [ ii ] u [ii ]    [ii | jj]u m2 m2 rk rk [ii ] k =1 k =1 2.2 Phân cụm mờ loại 2 khoảng cộng tác khi số cụm khác nhau Hàm mục tiêu đề xuất như sau: N [ ii ]c[ ii ] N [ ii ]c[ ii ]  u [ii ]d ik2    uik1 [ii ](vi [ii ]  v~i [ii ]) 2 m1 m1 m Q[ii] = ik k =1 i =1 k =1 i =1 N [ ii ]c[ ii ] N [ ii ]c[ ii ]  u [ii ]d    uik 2 [ii ](vi [ii ]  v~i [ii ]) 2 m2 m2 2 m Q[ii] = ik ik k =1 i =1 k =1 i =1 U và V để tối thiểu hóa cho hàm mục theo công thức: m 1 u rs 1 [ii ] = 1/(m1 1) d  (d  c[ ii ] 1 2   (vr [ii ]  v~r [ii ]) 2 ~ [ii ]) 2 )     rs 2 j =1 js ( v j [ii ] v j  m2 1 u rs [ii ] = 1/(m2 1) d  (d  c[ ii ] 1 2   (vr [ii ]  v~r [ii ]) 2 ~ 2   js   (v j [ii ]  v j [ii ]) )  rs 2 j =1  N [ ii ] N [ ii ] u [ii ]xkt   u rk1 v~rt [ii ] m1 m rk m k =1 k =1 vrt 1 [ii ] = N [ ii ] (1   ) u rk1 [ii ] m k =1 N [ ii ] N [ ii ] u [ii ]x kt   u rk2 v~rt [ii ] m2 m rk m2 k =1 k =1 v rt [ii ] = N [ ii ] (1   ) u rk2 [ii ] m k =1 2.3 Thuật toán phân cụm mờ loại 2 khoảng cộng tá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 | < 𝜀1 𝑜𝑟 𝑡 > 𝑡𝑚𝑎𝑥 End 2.4 Thử nghiệm và đánh giá Để đá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 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 CIVFCM1 CIVFCM2 CFCM CFSFD (m1, m2) (m1, m2) 14.2741 12.7577 FS 12.309 NA (1.8,3) (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 tạ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 cụm mờ cộng tác đa nhân dựa trên tính toán hạ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 ] P c Q[ii ]    uik2 [ii]( (x k )  vi )2   Min   [ii | jj ] (uik  uik~ [ii | jj ])2 ( (x k )  vi )2 k 1 i 1 k 1 jj 1, jj ii 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  P    [ii | jj ]urs~ [ii | jj ] 1  c   [ii | jj ]u ~js [ii | jj ]  urs  jj 1, jj  ii  c 1   jj 1, jj  ii  P d rs2  P  (1    [ii | jj ])  2  j 1 (1    [ii | jj ])  jj 1, jj  ii j 1 d js  jj 1, jj  ii  M dik2    iktt2 t 1 1 M 1  N [ ii ] c N [ ii ] P c t 1  u k 1 i 1 2 ik [ii ] ikt    k 1 jj 1, jj  ii  [ii | jj ] (uik  uik~ [ii | jj ]) 2  ikt i 1 t  N [ ii ] c N [ ii ] P c  u k 1 i 1 2 ik [ii ] ikt   k 1 jj 1, jj  ii   [ii | jj ] (uik  uik~ [ii | jj ]) 2  ikt i 1 N [ ii ] N [ ii ] P u 2 ij [ii ]K t ( xk , x j )     [ii | jj ](uij  uij~ [ii | jj ]) 2 K t ( xk , x j )  ikt  K t ( xk , xk )  2 j 1 N [ ii ] j 1 jj 1, jj  ii N [ ii ] P uj 1 2 ik [ii ]    j 1 jj 1, jj  ii  [ii | jj ](uij  uij~ [ii | jj ]) 2 N [ ii ] N [ii ] N [ ii ] N [ii ] P  u j11 j 2 1 2 ij1 [ii ]uij2 2 [ii ]K t ( x j1 , x j 2 )  2    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 )  2  N [ ii ] 2 N [ ii ] P    uik [ii ]     [ii | jj ](uij  uij~ [ii | jj ]) 2   j11 j11 jj 1, jj  ii  P N [ ii ] N [ii]    jj 1, jj  ii j11 j 2 1 2 [ii | jj ](uij1  uij~1[ii | jj ]) 2 (uij 2  uij~2 [ii | jj ]) 2 K t ( x j1 , x j 2 )  2  N [ ii ] 2 N [ ii ] P    uik [ii ]     [ii | jj ](uij  uij~ [ii | jj ]) 2   j11 j11 jj 1, jj  ii 
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: N [ ii ] c N [ ii ] P c Q[ii ]    u k 1 i 1 2 k ik [ii ]( (x k )  vi ) 2    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: 𝑢𝑖𝑘 ∑𝑃 𝑖𝑖 𝑗𝑗 u~ ii jj 𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 𝛽[ | ] ik [ | ] 1−∑𝑐𝑖=1 (𝜑𝑘 +∑𝑃 𝑖𝑖 𝑗𝑗 𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 𝛽[ | ]) ∑𝑃𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 𝛽[𝑖𝑖|𝑗𝑗] u~ik [ii|jj] 𝑑𝑖𝑘 2 + 𝑐 1 ∑𝑖=1 (𝜑𝑘 +∑𝑃 𝑖𝑖 𝑗𝑗 2 𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 𝛽[ | ])𝑑𝑖𝑘 = (𝜑𝑘 + ∑𝑃𝑖𝑖=1,𝑗𝑗≠𝑖𝑖 𝛽[𝑖𝑖|𝑗𝑗])𝑑𝑖𝑘 2 M dik2    iktt2 t 1 1 M 1  N [ ii ] c N [ ii ] P c t 1   u k 1 i 1 2 k ik [ii ] ikt    k 1 jj 1, jj  ii  [ii | jj ] (uik  uik~ [ii | jj ]) 2  ikt i 1 t  N [ ii ] c N [ ii ] P c   u k 1 i 1 2 k ik [ii ] ikt    k 1 jj 1, jj  ii  [ii | jj ] (uik  uik~ [ii | jj ]) 2  ikt i 1
17 N [ ii ] N [ ii ] P   u [ii]K ( x , x )    j 1 2 j ij t k j j 1 jj 1, jj  ii  [ii | jj ](uij  uij~ [ii | jj ]) 2 K t ( xk , x j )  ikt  K t ( xk , xk )  2 N [ ii ] N [ ii ] P  u j 1 2 j ik [ii ]    j 1 jj 1, jj  ii  [ii | jj ](uij  uij~ [ii | jj ]) 2 N [ ii ] N [ii ] N [ ii ] N [ii ] P   j11 j 2 1 j1  j 2uij21[ii ]uij22 [ii ]K t ( x j1 , x j 2 )  2    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 )  2  N [ ii ] N [ ii ] P 2    j1uik [ii ]     [ii | jj ](uij  uij [ii | jj ])  2 ~  j11 j11 jj 1, jj  ii  P N [ ii ] N [ii]    jj 1, jj  ii j11 j 2 1  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  2  N [ ii ] N [ ii ] P 2    j1uik [ii ]     [ii | jj ](uij  uij [ii | jj ])  2 ~  j11 j11 jj 1, jj  ii  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 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