Luận văn Thạc Sỹ: Nghiên cứu các phương pháp phân cụm mờ (Fuzzy Clustering)

Luận văn về các phương pháp phân cụm mờ. Tìm hiểu sâu về thuật toán, ứng dụng phân cụm mờ trong thực tế, cùng các nghiên cứu liên quan.

• Người hướng dẫn: Pgs. Trần Đình Khang
• Trường học: Trường Đại học Bách Khoa Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Các phương pháp phân cụm mờ
• Loại tài liệu: Luận văn thạc sỹ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT
• MỞ ĐẦU
• 1. CHƯƠNG I: CƠ SỞ LÝ THUYẾT
• 1.1. Phân cụm dữ liệu
• 1.1. Giới thiệu về khai phá dữ liệu:
• 1.2. Bài toán phân cụm dữ liệu
• 1.3. Khái niệm phân cụm dữ liệu
• 1.4. Ứng dụng của phân cụm dữ liệu
• 1.5. Các phương pháp phân cụm dữ liệu
• 1.2. Phân cụm mở
• 1.2.1. Giới thiệu về phân cụm mở
• 1.2.2. Các phương pháp phân cụm mở
• 1.3. Thuật toán FCM và các mở rộng của FCM
• 1.4. Thuật toán Diffuzzy
• 1.5. Self -Organizing Map
• 1.6. Fuzzy ART
• II. CHƯƠNG II: PHƯƠNG PHÁP PHÂN CỤM MỞ CẢI TIẾN
• 2.1. Yêu cầu bài toán
• 2.2. Giới thiệu phương pháp phân cụm mở cải tiến:
• 2.3. Các bước của phương pháp
• 2.4. Phân cụm multi-protolype
• 2.5. Phát hiện cụm cứng và cụm mềm:
• 2.6. Gom các cụm cứng tương đồng
• 2.7. Gán độ thuộc cho mỗi điểm dữ liệu
• III. CHƯƠNG III: THỬ NGHIỆM VÀ ỨNG DỤNG PHƯƠNG PHÁP PHÂN CỤM MỞ CẢI TIẾN
• 3.1. Thử nghiệm với bộ dữ liệu nhân tạo:
• 3.3. Nhận xét
• 3.4. Ứng dụng:
• KẾT LUẬN
• DANH MỤC HÌNH VẼ

Tóm tắt

I. Tổng Quan Về Phân Cụm Mờ Khái Niệm và Ưu Điểm

Trong bối cảnh bùng nổ dữ liệu, việc trích xuất thông tin hữu ích từ khối lượng dữ liệu khổng lồ trở nên vô cùng quan trọng. Khai phá dữ liệu đóng vai trò then chốt trong quá trình này. Theo Han-Kamber, khai phá dữ liệu là một khâu quan trọng trong quá trình khám phá tri thức (Knowledge Discovery from Data hay còn gọi là KDD). Quá trình này gồm nhiều bước, từ làm sạch dữ liệu đến biểu diễn tri thức. Phân cụm dữ liệu, đặc biệt là phân cụm mờ, là một kỹ thuật quan trọng. Phân cụm mờ (Fuzzy Clustering) khác với phân cụm cứng (Hard Clustering) ở chỗ, một điểm dữ liệu có thể thuộc về nhiều cụm với mức độ thành viên khác nhau. Điều này phản ánh thực tế dữ liệu thường không có ranh giới rõ ràng. Phương pháp phân cụm mờ cho phép xử lý các tình huống mà một đối tượng có thể có đặc điểm của nhiều nhóm khác nhau. Ưu điểm của phân cụm mờ là khả năng mô hình hóa sự không chắc chắn và linh hoạt trong việc gán nhãn dữ liệu.

1.1. Giới Thiệu Tổng Quan về Khai Phá Dữ Liệu

Theo Jiowei Han và Micheline Kamber, khai phá dữ liệu là quá trình trích xuất tri thức từ lượng lớn dữ liệu. Encyclopedia Britannica định nghĩa nó là quá trình khám phá các hình mẫu và mối quan hệ hữu ích. Hiểu một cách tổng quát, khai phá dữ liệu là khai thác thông tin trừu tượng, tổng quát từ dữ liệu thô. Dữ liệu thô cần được xử lý, phân tích để đưa ra thông tin hữu ích cho người dùng. Khai phá dữ liệu là công cụ để chuyển đổi dữ liệu thô thành tri thức có giá trị. Quá trình này bao gồm làm sạch dữ liệu, tích hợp dữ liệu, lựa chọn dữ liệu, biến đổi dữ liệu, khai phá dữ liệu, đánh giá mẫu và biểu diễn tri thức.

1.2. So Sánh Phân Cụm Mờ và Phân Cụm Cứng Truyền Thống

Phân cụm cứng gán mỗi điểm dữ liệu vào một cụm duy nhất. Ngược lại, phân cụm mờ cho phép một điểm dữ liệu thuộc về nhiều cụm với các mức độ thành viên khác nhau. Điều này thể hiện sự không chắc chắn và chồng chéo giữa các cụm. Ví dụ, một người có thể vừa là thành viên của nhóm 'người yêu thích thể thao' vừa là thành viên của nhóm 'người thích đọc sách' với các mức độ khác nhau. Phân cụm mờ phù hợp với các bài toán mà ranh giới giữa các cụm không rõ ràng, ví dụ như phân loại tài liệu, phân tích hình ảnh, hoặc phân khúc khách hàng.

1.3. Tại Sao Nên Sử Dụng Phân Cụm Mềm Trong Ứng Dụng Thực Tế

Phân cụm mềm hay phân cụm mờ mang lại nhiều lợi ích trong thực tế. Nó cho phép mô hình hóa sự không chắc chắn vốn có trong dữ liệu. Dữ liệu thực tế thường chứa nhiễu và sự mơ hồ, phân cụm mờ giúp xử lý tốt hơn các tình huống này. Ví dụ, trong bài toán phân tích ảnh y tế, một tế bào có thể có các đặc điểm của cả tế bào ung thư và tế bào khỏe mạnh. Phân cụm mờ sẽ phản ánh điều này tốt hơn phân cụm cứng.

II. Thách Thức và Hạn Chế Của Thuật Toán Phân Cụm Mờ

Mặc dù phân cụm mờ có nhiều ưu điểm, nó cũng tồn tại một số thách thức và hạn chế. Một trong những thách thức lớn nhất là lựa chọn tham số phù hợp, ví dụ như số lượng cụm và các tham số của hàm thành viên (membership function). Việc lựa chọn tham số không phù hợp có thể dẫn đến kết quả phân cụm kém chất lượng. Ngoài ra, thuật toán phân cụm mờ có thể tốn kém về mặt tính toán, đặc biệt đối với dữ liệu lớn. Một số thuật toán phân cụm mờ, như FCM (Fuzzy C-Means), có thể hội tụ vào các cực tiểu cục bộ, dẫn đến kết quả không tối ưu. Việc đánh giá chất lượng phân cụm mờ cũng là một thách thức, vì các chỉ số đánh giá cho phân cụm cứng không phù hợp.

2.1. Vấn Đề Lựa Chọn Tham Số Trong Phân Cụm Mờ

Việc lựa chọn số lượng cụm (C) là một vấn đề quan trọng. Không có quy tắc chung nào để xác định số lượng cụm tối ưu. Cần phải thử nghiệm với nhiều giá trị khác nhau và sử dụng các chỉ số đánh giá chất lượng phân cụm mờ để lựa chọn. Các tham số của hàm thành viên cũng ảnh hưởng đến kết quả. Ví dụ, trong FCM, tham số m (fuzzifier) kiểm soát mức độ mờ của phân cụm. Giá trị m càng lớn, các cụm càng mờ.

2.2. Độ Phức Tạp Tính Toán Của Thuật Toán FCM Fuzzy C Means

Thuật toán FCM có độ phức tạp tính toán O(nCd*I), trong đó n là số lượng điểm dữ liệu, C là số lượng cụm, d là số chiều của dữ liệu, và I là số vòng lặp. Điều này có nghĩa là thời gian chạy của FCM tăng tuyến tính với số lượng điểm dữ liệu, số lượng cụm và số chiều của dữ liệu. Đối với dữ liệu lớn, FCM có thể mất nhiều thời gian để hội tụ.

2.3. Làm Thế Nào Để Vượt Qua Cực Tiểu Cục Bộ Trong FCM

Để tránh hội tụ vào các cực tiểu cục bộ, có thể sử dụng nhiều cách. Một cách là khởi tạo các tâm cụm ngẫu nhiên nhiều lần và chọn kết quả tốt nhất. Một cách khác là sử dụng các thuật toán tối ưu hóa toàn cục, như giải thuật di truyền (giải thuật di truyền và phân cụm mờ) hoặc mô phỏng luyện kim, để tìm kiếm không gian giải pháp rộng hơn. Mạng nơ-ron cũng có thể được sử dụng để khởi tạo tâm cụm ban đầu một cách thông minh.

III. Thuật Toán Phân Cụm Mờ FCM Hướng Dẫn Chi Tiết Cải Tiến

FCM (Fuzzy C-Means) là một trong những thuật toán phân cụm mờ phổ biến nhất. Ý tưởng chính của FCM là tìm các tâm cụm sao cho tổng khoảng cách từ các điểm dữ liệu đến các tâm cụm, được trọng số bằng mức độ thành viên, là nhỏ nhất. FCM là một thuật toán lặp. Bắt đầu với các tâm cụm ngẫu nhiên, FCM lặp lại hai bước: cập nhật mức độ thành viên và cập nhật tâm cụm. Quá trình lặp dừng lại khi sự thay đổi trong mức độ thành viên hoặc tâm cụm là nhỏ hơn một ngưỡng cho trước. Có nhiều cách để cải tiến thuật toán FCM, ví dụ như sử dụng các hàm khoảng cách khác nhau, thêm các ràng buộc vào mức độ thành viên, hoặc kết hợp FCM với các thuật toán khác.

3.1. Giải Thích Cụ Thể về Hàm Thành Viên Trong FCM

Trong FCM, hàm thành viên xác định mức độ mà một điểm dữ liệu thuộc về một cụm. Hàm thành viên có giá trị từ 0 đến 1. Giá trị 1 có nghĩa là điểm dữ liệu hoàn toàn thuộc về cụm đó, giá trị 0 có nghĩa là điểm dữ liệu không thuộc về cụm đó. Hàm thành viên thường dựa trên khoảng cách giữa điểm dữ liệu và tâm cụm. Điểm dữ liệu càng gần tâm cụm, mức độ thành viên càng cao. Ma trận phân cụm mờ chứa các giá trị hàm thành viên cho tất cả các điểm dữ liệu và tất cả các cụm.

3.2. Các Bước Chi Tiết Của Thuật Toán FCM Fuzzy C Means

Thuật toán FCM hoạt động như sau: 1. Khởi tạo các tâm cụm ngẫu nhiên. 2. Tính toán ma trận phân cụm mờ dựa trên khoảng cách từ các điểm dữ liệu đến các tâm cụm. 3. Cập nhật các tâm cụm dựa trên ma trận phân cụm mờ. 4. Lặp lại bước 2 và 3 cho đến khi hội tụ.

3.3. Các Phương Pháp Cải Tiến Thuật Toán FCM Hiệu Quả

Có thể cải tiến thuật toán FCM bằng cách sử dụng các độ đo phân cụm mờ khác nhau. Ví dụ, có thể sử dụng khoảng cách Mahalanobis thay vì khoảng cách Euclidean để xử lý dữ liệu có tương quan giữa các thuộc tính. Ngoài ra, có thể thêm các ràng buộc vào hàm thành viên, ví dụ như yêu cầu tổng mức độ thành viên của một điểm dữ liệu phải bằng 1. Thuật toán phân cụm mờ cải tiến giúp nâng cao hiệu quả và độ chính xác.

IV. Ứng Dụng Thực Tế Của Phân Cụm Mờ Trong Nhiều Lĩnh Vực

Phân cụm mờ được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau. Trong nhận dạng mẫu, phân cụm mờ có thể được sử dụng để phân loại các đối tượng dựa trên các đặc trưng của chúng. Trong thị giác máy tính, phân cụm mờ có thể được sử dụng để phân đoạn ảnh và nhận diện đối tượng. Trong khai phá dữ liệu, phân cụm mờ có thể được sử dụng để tìm các nhóm dữ liệu tương đồng và phát hiện các mẫu ẩn. Ví dụ, phân cụm mờ trong nhận dạng mẫu giúp phân loại các loại hoa khác nhau dựa trên kích thước cánh hoa và đài hoa. Phân cụm mờ trong thị giác máy tính được sử dụng để phân đoạn ảnh y tế nhằm phát hiện các khối u. Ứng dụng phân cụm mờ đang ngày càng phổ biến.

4.1. Phân Cụm Mờ Trong Bài Toán Nhận Dạng Mẫu

Trong nhận dạng mẫu, phân cụm mờ có thể được sử dụng để phân loại các đối tượng dựa trên các đặc trưng của chúng. Ví dụ, có thể sử dụng phân cụm mờ để phân loại các loại trái cây khác nhau dựa trên màu sắc, kích thước và hình dạng của chúng. Phân cụm mờ cho phép một đối tượng thuộc về nhiều lớp khác nhau với các mức độ khác nhau, phản ánh sự không chắc chắn và chồng chéo giữa các lớp.

4.2. Ứng Dụng Phân Cụm Mờ Trong Thị Giác Máy Tính

Trong thị giác máy tính, phân cụm mờ có thể được sử dụng để phân đoạn ảnh và nhận diện đối tượng. Ví dụ, có thể sử dụng phân cụm mờ để phân đoạn ảnh y tế nhằm phát hiện các khối u. Phân cụm mờ cho phép mỗi pixel thuộc về nhiều vùng khác nhau với các mức độ khác nhau, phản ánh sự không chắc chắn và chồng chéo giữa các vùng.

4.3. Cách Phân Cụm Mờ Hỗ Trợ Quá Trình Khai Phá Dữ Liệu

Trong khai phá dữ liệu, phân cụm mờ có thể được sử dụng để tìm các nhóm dữ liệu tương đồng và phát hiện các mẫu ẩn. Ví dụ, có thể sử dụng phân cụm mờ để phân khúc khách hàng dựa trên hành vi mua hàng của họ. Phân cụm mờ cho phép một khách hàng thuộc về nhiều phân khúc khác nhau với các mức độ khác nhau, phản ánh sự đa dạng trong hành vi của khách hàng.

V. Đánh Giá So Sánh Phân Cụm Mờ với Các Phương Pháp Khác

Việc đánh giá phân cụm mờ là một bước quan trọng để xác định chất lượng của kết quả. Có nhiều chỉ số đánh giá chất lượng phân cụm mờ khác nhau, ví dụ như hệ số phân vùng (Partition Coefficient) và chỉ số Dunn mờ (Fuzzy Dunn Index). Việc so sánh phân cụm mờ và K-Means cho thấy phân cụm mờ phù hợp hơn với dữ liệu có cấu trúc phức tạp và ranh giới không rõ ràng. Phân cụm mờ linh hoạt hơn và có thể cung cấp thông tin chi tiết hơn về cấu trúc dữ liệu.

5.1. Các Chỉ Số Đánh Giá Chất Lượng Phân Cụm Mờ Quan Trọng

Các chỉ số đánh giá chất lượng phân cụm mờ giúp xác định mức độ tách biệt giữa các cụm và tính đồng nhất của các điểm dữ liệu trong mỗi cụm. Hệ số phân vùng (Partition Coefficient) đo mức độ rõ ràng của phân vùng. Chỉ số Dunn mờ (Fuzzy Dunn Index) đo tỷ lệ giữa khoảng cách nhỏ nhất giữa các cụm và khoảng cách lớn nhất trong mỗi cụm.

5.2. So Sánh Phân Cụm Mờ và Thuật Toán K Means Chi Tiết

K-Means là một thuật toán phân cụm cứng, trong khi phân cụm mờ là một thuật toán phân cụm mềm. K-Means gán mỗi điểm dữ liệu vào một cụm duy nhất, trong khi phân cụm mờ cho phép một điểm dữ liệu thuộc về nhiều cụm với các mức độ khác nhau. Phân cụm mờ phù hợp hơn với dữ liệu có cấu trúc phức tạp và ranh giới không rõ ràng, trong khi K-Means phù hợp hơn với dữ liệu có cấu trúc đơn giản và ranh giới rõ ràng.

5.3. Ưu Điểm Nổi Bật Của Phân Cụm Mờ So Với Các Phương Pháp Khác

Phân cụm mờ có khả năng xử lý dữ liệu có nhiễu và sự mơ hồ tốt hơn so với các phương pháp phân cụm khác. Phân cụm mờ cung cấp thông tin chi tiết hơn về cấu trúc dữ liệu, vì nó cho phép một điểm dữ liệu thuộc về nhiều cụm khác nhau. Điều này giúp người dùng hiểu rõ hơn về mối quan hệ giữa các điểm dữ liệu.

VI. Tương Lai Của Phân Cụm Mờ Hướng Nghiên Cứu Phát Triển

Phân cụm mờ tiếp tục là một lĩnh vực nghiên cứu tích cực. Các hướng nghiên cứu hiện tại bao gồm phát triển các thuật toán phân cụm mờ cải tiến cho dữ liệu lớn, kết hợp phân cụm mờ với các kỹ thuật học máy khác, và ứng dụng phân cụm mờ trong các lĩnh vực mới. Phân cụm mờ dựa trên mật độ và phân cụm mờ dựa trên khoảng cách là hai hướng phát triển đầy hứa hẹn. Việc tích hợp giải thuật di truyền và phân cụm mờ cũng mở ra nhiều cơ hội mới.

6.1. Phân Cụm Mờ Dựa Trên Mật Độ Tiềm Năng và Ứng Dụng

Phân cụm mờ dựa trên mật độ tìm các cụm dựa trên mật độ của các điểm dữ liệu. Các cụm được xác định là các vùng có mật độ điểm dữ liệu cao, được phân tách bởi các vùng có mật độ điểm dữ liệu thấp. Phương pháp này phù hợp với dữ liệu có hình dạng phức tạp và nhiều nhiễu.

6.2. Phân Cụm Mờ Dựa Trên Khoảng Cách Các Tiếp Cận Mới

Phân cụm mờ dựa trên khoảng cách sử dụng khoảng cách giữa các điểm dữ liệu để xác định các cụm. Các cụm được xác định là các nhóm điểm dữ liệu gần nhau. Việc sử dụng các hàm khoảng cách khác nhau có thể ảnh hưởng đến kết quả phân cụm.

6.3. Kết Hợp Giải Thuật Di Truyền và Phân Cụm Mờ Triển Vọng

Việc kết hợp giải thuật di truyền và phân cụm mờ giúp tìm kiếm không gian giải pháp rộng hơn và tránh hội tụ vào các cực tiểu cục bộ. Giải thuật di truyền có thể được sử dụng để tối ưu hóa các tham số của thuật toán phân cụm mờ, ví dụ như số lượng cụm và các tham số của hàm thành viên.

Trích đoạn nội dung tài liệu

CHƯƠNG 1I: PHƯƠNG PHÁP PHÂN CỰM MỞ CẢI TIỀN.1 Yên cầu bài loan - 30 2.2 Giới thiệu phương pháp phân cụm mở cải tiễn:.3 Cáo bước của phương pháp.2 Phan curn multi-protolype.3 Phat hign cum oing va cum mém:.4 Gom các cụm cứng tương đồng.5 Gan d@ thuộc dho mỗi điểm đữ liệu 60 CHƯƠNG III: THỨ NGHIỆM VẢ ỨNG DUNG PHUONG PHAP PHAN CUM M6 CAI TIEN.1 Thử nghiệm với bộ đữ liện nhân tạo: - - 63 3.3 Nhận X6t ce scssasisasinetentsauitasiatasienatiistsisineneeueeiansnenesnnasn OD 3.4 Ứng dung: - - 70 KẾT LUẬN. CHUONG I: CO SO LÝ THUYET 1.1 Phan cụm dữ liệu 1.1 Giới thiệu về khai nhá dữ liệu: Tạ có thể liệt kê một số các khái niệm về khai phá dữ liệu sau: “Khai phá đữ liệu là quả trình trích xuất boặc khai phá trì thúc từ một lượng lớn đất" liệu” Jiowei Han, Micheline Kamber, Data Mining:Concept and Technique 2 (2006). “Khai phá đữ liệu, trong khoa hoc máy tính, là quá trình khám phá các hình mẫu hữu ích và các mối quan hệ trong mội lượng lớn dữ liệu” Enoyclopedia Brilamioa. Thông, qua một số phát biểu trên, ta có thể hiểu khai phả dữ liệu dược coi là một quá trình nhằm khai thác các thông tin có mức trừu tượng cao hơn, tổng quát hem tử xmột lượng kin di liu.

Vy tai sao phải khai phá dữ liệu ? Ngày nay, nhờ sự phát triển của công nghệ má lượng dữ liệu sinh ra từ các hoạt động kinh doanh, sắn xuất, nghiên cứu khoa học và các hoạt động giao tiếp của cơn người thông qua rnáy tính diện tử tăng lên nhanh chóng. Đặc biệt trong vải nấm trở lại đây, nhờ sự phát triển của các mạng xã hội và các thiết bị di động đã dẫn tới sự búng nỗ dữ liệu do người dùng cung cập. Người ta ưúc lính rằng nằm 2013 lông đữ liệu của mạng World Wide Web dã dạt khoảng 4 Zetabytes. Tuy nhiên các dữ liệu nảy mới chí ở dạng thô, cân phải có quá trình xử lý, phân tích và trích xuất mới có thê đưa ra các thông tăm hữu ích, để hiển cho người đùng, và đó chính là công việc của khmi phá dữ liệu 'Theo Han-Kamber, khai phá dữ liệu là một khâu quan trọng trong quá trình khám.

pha tri thie (Knowledge Discovery from Data hay còn gọi là KDD). Quá trình này gồm 7 bước 3> Lam sạch đữ liệu (Data cleaning): Loại bỏ đữ liệu nhiễu và không phủ hợp 3_ Tích hợp dữ liêu (Dala imtergraion): kết hợp đữ liều từ nhiều nguồn > Lựa chọn dữ liệu (Data Selection): đữ liệu liên quan dén tảe vụ phản tích được thu thập từ cơ sở dữ liệu. DANH MỤC HÌNH VẼ Hình 1: Khai phá dữ liệu là một bước trong quả trình khai phá trí thức [1]. 9 Hình 2: Cae curt duge xac dinh bai giải thuật K-mcans [1 ts Hình 3: Tich ty va phan cap trong phan cum phan cap [I .eesccccsecuseeseeseneseesenseneesel7 (inh 4: Céu tric cdy CH - 20 Hình 5: Các cụnn có hình đạng bắtkỳ được phát hiện bởi TTBSCAN.

- 22 Hình 6: Câu trúc phân cấp của phân cạm STING.” inh 7: Các cụm tìm được bởi EM. - 26 Hinh 8: Kohonen Feature Map với dâu vào 2 cliển và mạng nơ-ron hat chiều. - 4L Hinh 9: Các quốc gia trên lưới SOM dựa trên các chỉ số vẻ tinh trạng đói nghéo (thing ké của WorldBank 1992) nguồn-hifp:/wsww.eis hut fi/research/som-research/worldmap html Ai Hinh 10: Cac chu ky hoc cita ART. Hinh 11: Mang hoc canh tranh.

ri 46 Hình 12: Các cụm có kích thước khác nhau - - 34 Hình 13: Các cụm có mật độ khác nhau. 34 Lừnh 14: dữ liệu chứa nhiễu - - 35 [inh 15: cum có hình đạng bất kỳ. - 55 Hinh 16: Trước khi điều chỉnh.SỦ Hình 17: Sau khi điều chính bằng K-mean. 5Ó Tinh 18: Kết quả sau khi xác định các vùng đít liệu cứng và vùng đữ liện mở.

a SB Hình 19: Các cụm cửng được xác dịnh đựa trên tham sốr và mửnPt,. Hình 20: Sự gom cụm đựa trên khoảng cách giữa 2 cụm. seo Tình 21: Kết quả gom các cựm con với r=10%, mìnPIs=5. 0 Hinh 22: Kết quá phân cụm với + 2.

cà sineisrreeereoeorØ Hình 23: FCM với k 2. Linh 24 E-FCM với k=2 - - 64 Hình 25: DBSCAN với cps—109 và minPIs=5. - 64 Hinh 26: Phuong php cia tién vi r-12% va MINPtS—. sees Tĩnh 27: FCM với k=2 65 MO DAU Đới sự phát triền của xã ội thông tin, nhà cầu xử lý đữ: liệu đề lấy r các thông tìm hữu ích là rất cấp thiết, đặc biệt trong bối cảnh hiện nay, khi công nghệ thông tin dã và dang dược dp dung trong hấu khắp các ngành và lĩnh vực của dời sống.

Việc kết tình trí thức từ một lượng đữ liệu lớn là công việc của khai phá đt liệu, và ong cáo bước của tiến trình đỏ, phân cụm dữ liệu đồng mội vai trò quan trọng, Phân cụm dữ liệu giúp phốt hiện ra các nhóm dữ liệu tương đông, từ đó làm cơ sở cho nhiều hưởng xử lý dữ liệu khac nhan như nhận dạng mẫu, phát hiện mai quan hệ giữa các thuộc tính, dánh giá phân bó dữ liệu,.Đã có nhiều công trình nghiên cứu về phân cụm dữ liệu trong suốt một thời gian đài từ thập lợ' 30-40, đi theo các hưởng khác nhau nhằm giải quyết bài toán phân cụm. Mỗi phương pháp phân cụm dều có các ưu nhược diễm riêng, phù hợp với các lớp bài toán khác nhau. lrong đó, các phương pháp phân cum mở được nghiên cứu và phát triển nhằm giải quyết các bai todn phan cum mà trong đó ranh giới giữa các cụm là không rõ rằng, mỗi dữ liệu có thể thuộc về các cụm với bậc thành viên khác nhau căn cứ trên mốt quan hệ tương đồng của các dữ liệu. Khởi đầu từ các nghiên cứu của Bedek với phương pháp Fuasy C-Mean nổi tỗng, phân cụn mờ hiện nay đổ có rất nhiều phương pháp tiếp cận và cải tiền theo các hướng khác nhau.

Luận văn này nhằm mục dich fim hiểu và làm sáng lỗ một số phương pháp phân cụm mò điễn hình nhằm cung cấp mội cải nhìn bao quái về phân cụm mở, sau đỏ nghiên cửu và phát triên một phương pháp cái tiễn mới và áp dụng nó cho một bài toán cụ thể. Phương pháp nghiên cứu ở đâu là tìm hiểu và phân tích các phưong pháp phân cụm mờ hiện có ở các hưởng dị khác nhau, từ đó phát biện các diễm mạnh và diém yếu của từng phương pháp, qua đó đề xuất một giải pháp mang tỉnh tổng hợp để giải quyết vẫn dé phân cụm. Phương pháp cải tiến được đem thử nghiệm và áp dụng vào một số bài toán cụ thể nhằm mình chứng các đặc diễm của phương pháp. Bồ cục của luận văn được trình bày nÏúc sau: Hinh 28: Phương pháp mới véi minPis—$ va 12.

enenenienmetn sensed 1ũnh 29: FCM với k=2 - - - 66 Hình 30: Phương pháp mới véi minPts-20, r-2. acsesesesseeeuteenenseusissisiasienineninenaanensnenaess 9 Hình 34: r=5%, minPts=7. - - 69 Hình 35: Các thành phân của Hansense - - - A Hình 36: Các giá trị đo lúc 17h-19h (ngày 27/8/2013). - 73 Hình 37: Các giá trị đo lúc 9h-11h (ngày 27/8/2013).78 Linh 38: Cáo điểm dữ liệu trước khi gom cụm.

- - 7A Hình 39: Các điểm dư liệu sau khi gom cụm. 75 Tỉnh 41: Các cụm dữ liệu tao bởi các dit ign do tir 1/4 - 1/6/2013 vào lúc 9h-19h. 76 Hình 42: Độ ò nhiễm của các vùng được biếu thị bằng các ô lục giác mằu.77 Điển đối dữ liệu (Data transfarmation) : dữ liệu được biến đổi hoặc hợp nhất về các dạng thích hợp với các phương pháp khai phá. Khai pha dé ligu (Data mining) : là tiền trinh quan trọng nhất, wong do các phương pháp thông minh duoc ap đụng đề trích xuât các hình mẫu đữ liệu từ tập đữ liệu.

Dénh giá mẫu (Pattem IvaÌntion): nhận dạng các mẫu có giá trị biếu điển trí thúc đựa trên các phép dơ dộ giá trị. Biễn diễn tri thức (Knowlsdge presentation): các trí thức được hiển thị cho người dùng nhờ các phương pháp biểu điển và trực quan hóa ị Í| Mey và Ịi Evatute adh |1 rei A = fi i on Snag PURE —¬+ Le toe Hình 1: Khai phá dữ liệu là một bước trong quả ?rình khai phá trí thúc ƒ1J Điển đối dữ liệu (Data transfarmation) : dữ liệu được biến đổi hoặc hợp nhất về các dạng thích hợp với các phương pháp khai phá. Khai pha dé ligu (Data mining) : là tiền trinh quan trọng nhất, wong do các phương pháp thông minh duoc ap đụng đề trích xuât các hình mẫu đữ liệu từ tập đữ liệu. Dénh giá mẫu (Pattem IvaÌntion): nhận dạng các mẫu có giá trị biếu điển trí thúc đựa trên các phép dơ dộ giá trị.

Biễn diễn tri thức (Knowlsdge presentation): các trí thức được hiển thị cho người dùng nhờ các phương pháp biểu điển và trực quan hóa ị Í| Mey và Ịi Evatute adh |1 rei A = fi i on Snag PURE —¬+ Le toe Hình 1: Khai phá dữ liệu là một bước trong quả ?rình khai phá trí thúc ƒ1J Hinh 28: Phương pháp mới véi minPis—$ va 12. enenenienmetn sensed 1ũnh 29: FCM với k=2 - - - 66 Hình 30: Phương pháp mới véi minPts-20, r-2. acsesesesseeeuteenenseusissisiasienineninenaanensnenaess 9 Hình 34: r=5%, minPts=7. - - 69 Hình 35: Các thành phân của Hansense - - - A Hình 36: Các giá trị đo lúc 17h-19h (ngày 27/8/2013).

- 73 Hình 37: Các giá trị đo lúc 9h-11h (ngày 27/8/2013).78 Linh 38: Cáo điểm dữ liệu trước khi gom cụm. - - 7A Hình 39: Các điểm dư liệu sau khi gom cụm. 75 Tỉnh 41: Các cụm dữ liệu tao bởi các dit ign do tir 1/4 - 1/6/2013 vào lúc 9h-19h. 76 Hình 42: Độ ò nhiễm của các vùng được biếu thị bằng các ô lục giác mằu.77 Hinh 28: Phương pháp mới véi minPis—$ va 12.

enenenienmetn sensed 1ũnh 29: FCM với k=2 - - - 66 Hình 30: Phương pháp mới véi minPts-20, r-2. acsesesesseeeuteenenseusissisiasienineninenaanensnenaess 9 Hình 34: r=5%, minPts=7. - - 69 Hình 35: Các thành phân của Hansense - - - A Hình 36: Các giá trị đo lúc 17h-19h (ngày 27/8/2013). - 73 Hình 37: Các giá trị đo lúc 9h-11h (ngày 27/8/2013).78 Linh 38: Cáo điểm dữ liệu trước khi gom cụm.

- - 7A Hình 39: Các điểm dư liệu sau khi gom cụm. 75 Tỉnh 41: Các cụm dữ liệu tao bởi các dit ign do tir 1/4 - 1/6/2013 vào lúc 9h-19h. 76 Hình 42: Độ ò nhiễm của các vùng được biếu thị bằng các ô lục giác mằu.