phần mở đầu, phần kết luận, phần mục lục, phần tài liệu tham khảo. Các nội dung cơ bản của luận văn đƣợc trình bày theo cấu trúc nhƣ sau: Chƣơng 1: Tổng quan về phân cụm Trong chƣơng này, luận văn sẽ trình bày tổng quan về tập mờ, bài toán phân cụm và phân cụm mờ và thuật toán cơ bản giải quyết vấn đề phân cụm trên tập mờ đó là thuật toán Fuzzy C – Means (FCM), KFCM. Từ thuật toán này đƣa ra thuật toán đa mô hình cho bài toán phân cụm ảnh viễn thám. Chƣơng 2: Phân cụm đa mô hình Trong chƣơng này, tổng quan về học đa mô hình và phân cụm đa mô hình.
Tiếp theo, giới thiệu về thuật toán đa mô hình SCPA, MCLA, HBGF và MG. Chƣơng 3:Ứng dụng phân đoạn ảnh viễn thám Trong chƣơng này, chúng tôi cài đặt và đánh giá hiệu năng các thuật toán đa mô hình: MG và SCPA từ đây thấy hiệu quả của các thuật toán phân cụm đa mô hình cho ảnh viễn thám đƣợc khẳng định. 9 TIEU LUAN MOI download : skknchat@gmail.com CHƢƠNG 1: TỔNG QUAN VỀ PHÂN CỤM 1. Khái quát phân cụm Phân cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp các phƣơng pháp học không giám sát trong học máy, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định.
Có rất nhiều định nghĩa khác nhau về kỹ thuật này, nhƣng về bản chất ta có thể hiểu phân cụm là các qui trình tìm cách nhóm các đối tƣợng đã cho vào các cụm, sao cho các đối tƣợng trong cùng một cụm tƣơng tự nhau và các đối tƣợng khác cụm thì không tƣơng tự nhau[1]. Mục đích của phân cụm là tìm ra bản chất bên trong các nhóm nội tại bên trong của bộ dữ liệu không có nhãn. Tuy nhiên, không có tiêu chí nào là đƣợc xem là tốt nhất để đánh giá hiệu quả của phân tích phân cụm, điều này phụ thuộc vào mục đích cuối cùng của phân cụm dữ liệu. Do đó, ngƣời sử dụng phải cung cấp tiêu chuẩn, theo cách nhƣ vậy mà kết quả của phân cụm sẽ phù hợp với nhu cầu của ngƣời sử dụng cần.1 Cho X là một tập dữ liệu gồm N vector: x 1 , x 2 ,.
Bài toán phân cụm là chia tập dữ liệu X , c cụm dữ liệu c. Thỏa mãn 3 điều kiện sau: zi , i 1, 2,., c c X i 1 zi zi z j với i j ; i, j 1, 2,., c Phân cụm đƣợc đóng vai trò quan trọng trong các nghành khoa học: Thƣơng mại: Phân cụm dữ liệu giúp các nhà cung cấp biết đƣợc nhóm khác hàng quan trọng có các đặc trƣng tƣơng đồng nhau và đặc tả họ từ các mẫu trong cơ sở dữ liệu khách hàng. 10 TIEU LUAN MOI download : skknchat@gmail.com - Sinh học: Phân cụm dữ liệu đƣợc sử dụng để xác định các loại sinh vật, phân loại các Gen với chức năng tƣơng đồng và thu đƣợc các cấu trúc trong các mẫu. - Phân tích dữ liệu không gian: Do sự đồ sộ của dữ liệu không gian nhƣ dữ liệu thu đƣợc từ các hình ảnh chụp từ vệ tinh, các thiết bị y học hoặc hệ thống thông tin địa lý (GIS), v.v, làm cho ngƣời dùng rất khó để kiểm tra các dữ liệu không gian một cách chi tiết.
Phân cụm dữ liệu có thể trợ giúp ngƣời dùng tự động phân tích và xử lý các dữ liêu không gian nhƣ nhận dạng và chiết xuất các đặc tính hoặc các mẫu dữ liệu quan tâm có thể tồn tại trong cơ sở dữ liệu không gian. - Lập quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lý, v.v, nhằm cung cấp thông tin cho quy hoạch đô thị. - Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm cung cấp thông tin cho nhận dạng các vùng nguy hiểm. - Địa lý: Phân lớp các động vật, thực vật và đƣa ra đặc trƣng của chúng.
- Khai phá Web: Phân cụm dữ liệu có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý nghĩa trong môi trƣờng Web. Các lớp tài liệu này trợ giúp cho việc khám phá tri thức từ dữ liệu Web, khám phá ra các mẫu truy cập của khách hàng đặc biệt hay khám phá ra cộng đồng Web, v. Tổng quan các thuật toán phân cụm tiêu biểu Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng trong thực tế, nó đều hƣớng tới hai mục tiêu chung đó là chất lƣợng của các cụm khám phá đƣợc và tốc độ thực hiện của thuật toán [1]. Hiện nay, các kỹ thuật phân cụm có thể phân loại theo các cách tiếp cận chính sau: 1.1 Phân cụm cụm phân hoạch Kỹ thuật này phân hoạch một tập hợp dữ liệu có n phần tử thành k nhóm cho đến khi xác định số các cụm đƣợc thiết lập.
Số các cụm đƣợc thiết lập là các đặc trƣng đƣợc lựa chọn trƣớc. Phƣơng pháp này là tốt cho việc tìm các cụm 11 TIEU LUAN MOI download : skknchat@gmail.com hình cầu trong không gian Euclidean. Ngoài ra, phƣơng pháp này cũng phụ thuộc vào khoảng cách cơ bản giữa các điểm, để lựa chọn các điểm dữ liệu nào có quan hệ là gần nhau với mỗi điểm khác và các điểm dữ liệu nào không có quan hệ hoặc có quan hệ là xa nhau so với mỗi điểm khác. Tuy nhiên, phƣơng pháp này không thể xử lý các cụm có hình dạng kỳ quặc hoặc các cụm có mật độ các điểm dầy đặc.
Các thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ƣu toàn cục cho vấn đề phân cụm dữ liệu, do nó phải tìm kiếm tất cả các phân hoạch có thể đƣợc. Chính vì vậy, trên thực tế thƣờng đi tìm giải pháp tối ƣu cục bộ cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lƣợng của cụm cũng nhƣ để hƣớng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Nhƣ vậy, ý tƣởng chính của thuật toán phân cụm phân hoạch tối ƣu cục bộ là sử dụng chiến lƣợc ăn tham để tìm kiếm nghiệm. Một số thuật toán phân cụm theo tiếp cận phân hoạch: Thuật toán K-Means, thuật toán K-Medoids Thuật toán K-Means: Cho k là số cụm sau khi phân hoạch.
(1≤ k ≤ n, với n là số điểmtrong không gian giữ liệu) Thuật toán k-means gồm 4 bƣớc: B1. Chọn ngẫu nhiên k điểm làm trọng tâm ban đầu của k cụm. Gán (hoặc gán lại) từng điểm vào cụm có trọng tâm gần điểm đang xét nhất. Nếu không có phép gán nào thì dừng.
Vì không có phép gán nào có nghĩa là các cụm đã ổn định và thuật toán không thể cải thiện làm giảm độ phân biệt hơn đƣợc nữa. Tính lại trọng tâm cho từng cụm. Quay lại bƣớc 2. Minh họa thuật toán với k=2 12 TIEU LUAN MOI download : skknchat@gmail.com Ƣu điểm của phƣơng pháp phân cụm k-means - Độ phức tạp của thuật toán là O(tkn) với t là số lần lặp (t khá nhỏ so với n), k là số cụm cần phân hoạch, n là số điểm trong không gian dữ liệu.
- K-means phù hợp với các cụm có dạng hình cầu. Nhƣợc điểm của phƣơng pháp k-mean - Không đảm bảo đạt đƣợc tối ƣu toàn cục và kết quả đầu ra phụ thuộc nhiều vào việc chọn k điểm khởi đầu. Do đó có thể phải chạy lại thuật toán với nhiều bộ khởi đầu khác nhau để có đƣợc kết quả đủ tốt. Trong thực tế có thể áp dụng thuật giải di truyền để phát sinh các bộ khởi đầu.
- Cần phải xác định trƣớc số cụm. - Khó xác định số cụm thực sự mà không gian dữ liệu có. Do đó có thể phải thử với các giá trị k khác nhau. - Khó phát hiện các loại cụm có hình dạng phức tạp và nhất là các dạng cụm không lồi.
- Không thể xử lý nhiễu và mẫu cá biệt. - Chỉ có thể áp dụng khi tính đƣợc trọng tâm. Thuật toán K-Medoids Thuật toán K-Medoids là cải tiến của thuật toán k-means, k-medoids khác k- means: - Chiến lƣợc cho k trọng tâm đầu tiên. - Phƣơng pháp tính độ phân biệt - Phƣơng pháp tính trọng tâm trong cụm Thuật toán K-Medoids đƣợc thực hiện qua các bƣớc sau: B1: Chọn ngẫu nhiên k điểm Oi (i 1,., k) làm trung tâm (medoids) ban đầu của k cụm.
13 TIEU LUAN MOI download : skknchat@gmail.com B2: Gán (hoặc gán lại) từng điểm vào cụm có trung tâm gần điểm đang xét nhất B3: Với mỗi điểm trung tâm Oi (i 1,. Lần lƣợt xét các điểm không là trung tâm x. Tính S là độ lợi khi hoán đổi Oi bởi x. S đƣợc xác định nhƣ sau: S Ex EOi (1.1) Với Eoi , Ex lần lƣợt là giá trị hàm mục tiêu trƣớc và sau khi thaybởi x.
Nếu S là âm thì thay thế Oi trong bộ k trung tâm bởi x ( chọn trung tâm mới tốt hơn). Nếu có ít nhất 1 sự thay đổi trong B3 thì tiếp tục quay lại B2. Ngƣợc lại thì kết thúc thuật toán. Ƣu điểm: Thuật toán K-medoids làm việc đƣợc với nhiễu và biệt lệ.
Nhƣợc điểm:Thuật toán K-medoids chỉ hiệu quả khi tập dữ liệu không quá lớn vì có độ phức tạp là O(k(n-k)2t). Trong đó: n là số điểm trong không gian dữ liệu, k là số cụm cần phân hoạch, t là số lần lặp.2 Phân cụm phân cấp Phƣơng pháp này xây dựng một phân cấp trên cơ sở các đối tƣợng dữ liệu đang xem xét. Nghĩa là sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng hình cây, cây phân cấp này đƣợc xây dựng theo kỹ thuật đệ quy. Có hai cách tiếp cận phổ biến của kỹ thuật này đó là: 14 TIEU LUAN MOI download : skknchat@gmail.com + Hoà nhập nhóm, thƣờng đƣợc gọi là tiếp cận Bottom-Up + Phân chia nhóm, thƣờng đƣợc gọi là tiếp cận Top-Down \ Hình 1.1 Các chiến lược phân cụm phân cấp 1.3 Phân cụm dựa trên mật độ Kỹ thuật này nhóm các đối tƣợng dữ liệu dựa trên hàm mật độ xác định, mật độ là số các đối tƣợng lân cận của một đối tƣợng dữ liệu theo một nghĩa nào đó.
Trong cách tiếp cận này, khi một dữ liệu đã xác định thì nó tiếp tục đƣợc phát triển thêm các đối tƣợng dữ liệu mới miễn là số các đối tƣợng lân cận này phải lớn hơn một ngƣỡng đã đƣợc xác định trƣớc.