Phân cụm mờ với đại số gia tử và ứng dụng

- TÓM TẮT LUẬN VĂN THẠC SĨĐề tài: Phân cụm mờ với Đại số gia tử và ứng dụng.Tác giả luận văn: Đinh Khắc Đông – Khóa: 2009.Người hướng dẫn: PGS.
- Tuy vậy, các nghiên cứu sau đó chỉ ra những khó khăn gặp phải khiáp dụng thuật toán phân cụm mờ - Fuzzy C-Means trong các bài toán thực tế.
- 11iii Mục lục2 Phân cụm dữ liệu 132.1 Đặt vấn đề.
- 132.2 Bài toán phân cụm dữ liệu.
- 202.6 Các kỹ thuật phân cụm.
- 222.6.1 Các thuật toán phân cụm phân cấp.
- 222.6.2 Các thuật toán phân vùng.
- 252.6.3 Phân cụm mờ.
- 272.6.4 Phân cụm với mạng nơron nhân tạo.
- 292.6.5 Phân cụm với thuật toán tiến hóa.
- 302.7 So sánh các phương pháp phân cụm dữ liệu.
- 312.8 Các ứng dụng của phân cụm dữ liệu.
- 444 Phân cụm mờ với Đại số gia tử 464.1 Đặt vấn đề.
- 484.3 Thuật toán xác định trọng số.
- 514.4 Thuật toán phân cụm mờ với Đại số gia tử - HAFCM.
- 555 Các ứng dụng của Thuật toán phân cụm mờ với ĐSGT 575.1 Giải thuật di truyền.
- 60v Mục lục5.2 Ứng dụng trong bài toán phân cụm với dữ liệu nhân tạo.
- 615.3 Ứng dụng trong bài toán phân cụm với dữ liệu thực đa chiều.
- 395.1 Kết quả phân cụm của 3 thuật toán.
- 82.1 Ví dụ về phân cụm dữ liệu.
- 142.2 Một số bước trong bài toán phân cụm.
- 232.6 Biểu đồ có được khi sử dụng thuật toán với liên kết đơn.
- 232.7 Kết quả phân cụm phân cấp với thuật toán liên kết đơn.
- 242.8 Kết quả phân cụm phân cấp với thuật toán liên kết đầy đủ.
- 252.10 Thuật toán k-means nhạy cảm với những khởi tạo ban đầu.
- 272.11 Thuật toán phân cụm mờ.
- 434.1 Ví dụ về độ thuộc trong thuật toán FCM.
- 595.2 HCM, FCM, HAFCM cho kết quả phân cụm giống nhau khi không có nhiễu 615.3 Kết quả phân cụm của thuật toán HCM với dữ liệu nhiễu.
- 625.4 Kết quả phân cụm của thuật toán FCM với dữ liệu nhiễu.
- 625.5 Kết quả phân cụm của thuật toán HAFCM với dữ liệu nhiễu.
- Phân cụm dữ liệuHình 2.4: Ví dụ về độ tương tự khi xét đến yếu tố khái niệm.
- [28]2.6 Các kỹ thuật phân cụmTrong phần này, luận văn trình bày tóm tắt một số kỹ thuật phân cụm chính với nhiềuhướng tiếp cận khác nhau.2.6.1 Các thuật toán phân cụm phân cấpThuật toán phân cụm phân cấp được minh họa bởi ví dụ trong hình 2.5 với dữ liệu trongkhông gian hai chiều.
- Ta có thể cắt biểu đồ nàyở bất kỳ mức nào để có được các kết quả phân cụm tương ứng.Đa phần các thuật toán phân cụm phân cấp là sự biến đổi của các thuật toán liên kếtđơn, liên kết đầy đủ và sai khác tối thiểu.
- Phân cụm dữ liệuHình 2.5: Các dữ liệu thuộc về ba cụmHình 2.6: Biểu đồ có được khi sử dụng thuật toán với liên kết đơngiữa hai cụm là khoảng cách nhỏ nhất giữa hai giá trị bất kỳ lần lượt thuộc vào hai cụm(một điểm thuộc cụm này và một điểm thuộc cụm kia).
- Phân cụm dữ liệucó xu hướng sinh ra các cụm kéo dài và rời rạc.
- Ví dụ trong hình 2.7 và hình 2.8 minhhọa bài toán phân cụm với hai cụm cách nhau bởi các dữ liệu nhiễu.
- Phân cụm dữ liệunhiễu.
- Kết quả phân cụm cuối cùng làkết quả tốt nhất trong các lần chạy.Tiêu chuẩn dễ quan sát nhất và được áp dụng nhiều nhất trong các thuật toán phân vùng25 Chương 2.
- Phân cụm dữ liệulà tiêu chuẩn sai số bình phương.
- Phân cụm dữ liệuHình 2.10: Thuật toán k-means nhạy cảm với những khởi tạo ban đầu2.6.3 Phân cụm mờKết quả của phương pháp phân cụm truyền thống là một phân hoạch của tập dữ liệu đầuvào.
- Vì vậy, các cụm đầu ra củathuật toán phân cụm rõ là rời nhau.
- Thuật toán phân cụm mờ mở rộng khái niệm nàykhi cho phép mỗi dữ liệu thuộc vào tất cả các cụm với độ thuộc khác nhau.
- Đầu ra củathuật toán này không phải là một phân hoạch mà là ma trận các độ thuộc.Thuật toán phân cụm mờ• (1) Khởi tạo một phân vùng mờ của N đối tượng thành C cụm bằng cách chọn matrận độ thuộc U kích thước N × C.
- Hình 2.11 mô tả ý tưởng của thuật toán.
- Thuật toán phân cụm mờ có thể sinh ra hai cụmF1và F2được thể hiện bởi hình eclipse.
- Phân cụm dữ liệuKết quả phân cụm rõ có thể thu được từ kết quả của thuật toán phân cụm mờ nếu phânngưỡng dựa trên độ thuộc của các mẫu.
- Thuật toán phân cụm mờ được sử dụng nhiều nhấtlà Fuzzy C-means (FCM).
- Bước xác định các hàm thuộc là quan trọng nhất trong thuậttoán phân cụm mờ.
- Một số mạng nơron nhântạo được dùng trong các bài toán phân cụm như lượng tử hóa véctơ học của Kohonen(LVQ), bản đồ tự tổ chức (SOM) [21] và mô hình lý thuyết cộng hưởng thích nghi [8].29 Chương 2.
- Trong số 3 giải thuật này, GAđược dùng rộng rãi hơn cả trong các bài toán phân cụm.
- Phân cụm dữ liệuToán tử tái tổ hợp được dùng nhiều nhất trong GA là lai ghép.
- Toántử đột biến đảm bảo toàn bộ không gian đều được khai phá.2.7 So sánh các phương pháp phân cụm dữ liệuTrong chương này, luận văn đã trình bày các tiếp cận khác nhau với bài toán phân cụm.Phần lớn các thuật toán này dùng tiêu chuẩn sai số bình phương để tối ưu kết quả phâncụm.
- Phân cụm dữ liệuHình 2.13: Giải thuật di truyền đưa ra lời giải toàn cụcphân cấp khi các cụm kết quả đều có dạng cầu.
- Phân cụm dữ liệuthuật toán rất tốt để làm việc với tập dữ liệu có kích thước lớn.Về mặt lí thuyết, chúng được xếp vào lớp các thuật toán yếu bởi không sử dụng những trithức về dữ liệu.
- Nghiên cứu chỉ ra rằng những tri thức này có thể cải thiện đáng kể hiệunăng của các thuật toán phân cụm.
- Hình 2.14 là một ví dụ về ứng dụng của phân cụm trongphân vùng ảnh.
- Quá trình phânngưỡng này đóng vai trò “phân cụm” các điểm ảnh thành 2 phần dựa trên dữ liệumột chiều là mức xám.
- Phân cụm dữ liệuHình 2.14: (a) Ảnh đa mức xám gốc.
- Hình 4.1 mô tả các độ thuộc vào các cụm khác nhau phụ thuộc vào khoảng cáchtới các tâm cụm.Hình 4.1: Ví dụ về độ thuộc trong thuật toán FCMGiả sử có hai cụm trong dữ liệu là c1và c2.
- Các thuật toán dựa trên FCMphù hợp với dữ liệu chứa các cụm có hình dạng và mật độ như nhau.
- Phân cụm mờ với Đại số gia tửđóng góp của các dữ liệu vào quá trình cập nhật các tâm cụm.
- Phân cụm mờ với Đại số gia tửHình 4.3: Tâm cụm ngôn ngữ xây dựng dựa trên cấu trúc Đại số gia tử4.3 Thuật toán xác định trọng sốTrong thuật toán đề xuất cải tiến FCM, khoảng cách từ các mẫu đến các tâm cụm đượcgán thêm trọng số dựa vào tâm cụm ngôn ngữ tương ứng.
- Phân cụm mờ với Đại số gia tử• Đầu ra: Trọng số cho mỗi khoảng cách dijtừ mẫu xiđến tâm cụm cj.• 1.
- Phân cụm mờ với Đại số gia tửDo đó, tồn tại duy nhất giá trị ngôn ngữ mức k: ˆxithỏa mãn fm(ˆxi.
- Do đó trọng số tương ứng của xivới cjtrong trường hợpnày là wij= f m(P T ).Thuật toán này sẽ được sử dụng trong thuật toán Phân cụm mờ với Đại số gia tử đượctrình bày dưới đây.4.4 Thuật toán phân cụm mờ với Đại số gia tử -HAFCMĐầu tiên, để tăng độ tin cậy cho thuật toán, các tâm cụm được khởi tạo thông qua thuậttoán k-means.
- Phân cụm mờ với Đại số gia tửMặt khác, trong 4.3, các tâm cụm chỉ được cập nhật với những mẫu có độ thuộc lớn hơnmột ngưỡng w - phần tử trung hòa của ĐSGT.
- Tuynhiên, câu hỏi đặt ra là mối quan hệ giữa hai thuật toán này như thế nào? Mệnh đề sauđây có thể là câu trả lời thỏa đáng.Mệnh đề 2: Mệnh đề về tính tổng quát của Thuật toán phân cụm mờ với ĐSGT.Xét ĐSGT (AX, G, H.
- Phân cụm mờ với Đại số gia tử• Pha 2: Cập nhật các tâm cụmChú ý rằng công thức cập nhật tâm cụm trong Pha 2 của HAFCM và FCM là khôngkhác nhau.
- f m(hp) thì kết quả phân cụm của HAFCM và FCM là như nhau.
- Mệnh đề trên cho thấy, không gian tìm kiếm của HAFCM, tồn tại một bộ các tham sốđể thuật toán cho kết quả phân cụm giống hệt với thuật toán FCM.
- Do đó thuật toánHAFCM là tổng quát hơn FCM và khả năng cho kết quả phân cụm tốt hơn là rất rõ ràng.4.5 Tối ưu hóa các tham số của Đại số gia tửNhư đã trình bày ở trên, ý tưởng quan trọng nhất của thuật toán HAFCM là gắn đượccấu trúc ĐSGT vào thuật toán FCM truyền thống dưới dạng trọng số cho khoảng cáchgiữa dữ liệu và tâm cụm.
- Rõ ràng khi thay đổi các tham số của ĐSGT như độ đo tính mờcủa các gia tử hay phần tử trung hòa w hoặc mức k của các giá trị ngôn ngữ sẽ ảnh hưởngđến kết quả phân cụm.
- Phân cụm mờ với Đại số gia tử4.2 với bộ tham số {w, µ(Less), µ(P ossible), µ(M ore), µ(V ery.
- Khi đó kết quả phân cụm sẽ bị ảnh hưởng.
- Leonardo da Vinci .Sau khi xây dựng thuật toán Phân cụm mờ với Đại số gia tử, ta cần chứng minh khả năngứng dụng của thuật toán.
- HAFCM có thể làm việc với nhiều bài toán phân cụm khácnhau, từ dữ liệu có nhiễu, không có nhiễu hay dữ liệu đa chiều.
- Việc sử dụng độ đo tínhmờ của các giá trị ngôn ngữ làm trọng số cho khoảng cách giữa các mẫu và các tâm cụmđã tổng quát hóa thuật toán HAFCM so với FCM.
- Đồng thời, biến HAFCM thành thuậttoán phân cụm có giám sát với bộ tham số của ĐSGT.
- Các thuật toán học có thể đượcáp dụng để tìm ra bộ tham số cho kết quả phân cụm tốt.Trong chương này, luận văn trình bày hai ứng dụng minh họa cho khả năng của thuậttoán HAFCM trong bài toán phân cụm với dữ liệu nhân tạo, có nhiễu và bài toán phâncụm với dữ liệu thực đa chiều.
- Các ứng dụng của Thuật toán phân cụm mờ với ĐSGT5.1 Giải thuật di truyềnCác thành phần của giải thuật di truyền được áp dụng trong hai bài toán như sau:5.1.1 Mã hóaCác các thể được mã hóa bằng các véctơ nhị phân.
- Các ứng dụng của Thuật toán phân cụm mờ với ĐSGT5.1.4 Toán tử đột biếnVới các cá thể con vừa được lai ghép, ta tiến hành đột biến trước khi cho vào quần thểmới.
- Trong cả hai bài toán phân cụm, hàm thích nghi chính là sốlượng các mẫu bị phân cụm sai.
- Các ứng dụng của Thuật toán phân cụm mờ với ĐSGT5.2 Ứng dụng trong bài toán phân cụm với dữ liệunhân tạoBan đầu 50 bộ dữ liệu được sinh ngẫu nhiên theo thuật toán Gaussian trong không gianhai chiều.
- Các thuật toán HCM, FCM và HAFCM cho kết quả phân cụm giống hệt nhau(Hình 5.2).
- Các kết quả phân cụm tương ứng với các thuật toán HCM, FCMvà HAFCM được chỉ ra trong hình 5.3, hình 5.4 và hình 5.5.Các kết quả phân cụm cụ thể được chỉ ra trong bảng 5.1.61 Chương 5.
- Các ứng dụng của Thuật toán phân cụm mờ với ĐSGTHình 5.3: Kết quả phân cụm của thuật toán HCM với dữ liệu nhiễuHình 5.4: Kết quả phân cụm của thuật toán FCM với dữ liệu nhiễu62 Chương 5.
- Do kết quả phân cụm là63 Chương 5.
- Các ứng dụng của Thuật toán phân cụm mờ với ĐSGTbiết trước trong bộ dữ liệu nên ta có thể dễ dàng tính toán được tỉ lệ nhận dạng đúng khicó các kết quả phân cụm.
- Trong cả hai bài toán phân cụm, thuật toán HAFCMđều cho kết quả tốt hơn thuật toán FCM.
- Điều này khẳng định những phân tích vềmặt lý thuyết của thuật toán.• Trong bài toán phân cụm với dữ liệu được sinh ngẫu nhiên, dữ liệu ban đầu chỉ gồm50 mẫu.
- Các thuật toán HCM, FCM và HAFCM đều cho kết quả phân cụm nhưnhau.
- Kết quả này được ghi nhận như là cơ sở để tính toán tỉ lệ phân cụm sai sauđó.
- Khi áp dụng nhiễu lên tới 40%, thuật toán phân cụm rõ - HCM cho kết quảphân cụm với 9 mẫu sai.
- Trong khi đó, FCM phân cụm sai 4 mẫu (chiếm 5.71%)64 Chương 5.
- Các ứng dụng của Thuật toán phân cụm mờ với ĐSGTcòn HAFCM chỉ cho kết quả sai với 2 mẫu (2.86.
- Tỉ lệ phân cụm chính xác củaHAFCM là cao nhất với 97.14.
- Trong bài toán phân cụm với bộ dữ liệu IRIS, 75% dữ liệu được sử dụng trong quátrình học các tham số của ĐSGT.
- Kết luận• Với thuật toán FCM truyền thống, tất cả các mẫu đều tác động đến quá trình cậpnhật tâm cụm.
- Các tham số này được sử dụng làm tham số huấn luyện trong phươngpháp học có giám sát để thu được kết quả tốt hơn với thuật toán phân cụm mờ vớiĐSGT.6.2 Các vấn đề tồn tạiLuận văn đã xây dựng thuật toán Phân cụm mờ dựa trên Đại số gia tử cùng và hai ứngdụng minh họa với kết quả khá tốt.
- Kết luận6.3 Hướng phát triểnBài toán phân cụm mờ đã được nghiên cứu từ rất lâu với nhiều cải tiến theo nhiều hướngkhác nhau

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt