MỞ ĐẦU Bài toán phân cụm dữ liệu thuộc lĩnh vực học không giám sát, nhằm phân tập dữ liệu thành các tập con, thỏa mãn điều kiện các đối tƣợng trong cũng một tập con có độ tƣơng đồng cao, và ngƣợc lại các đối tƣợng ở các tập con khác nhau thì có độ tƣơng đồng thấp. Hay nói cách khác, bài toán phân cụm dữ liệu là bài toán khám phá cấu trúc của tập dữ liệu. Tùy theo đặc điểm cấu trúc của tập dữ liệu và mục đích sử dụng, có các phƣơng pháp giải quyết khác nhau nhƣ: Phân cụm dựa vào phân hoạch, phân cụm theo phân cấp, phân cụm dựa vào mật độ và phân cụm dựa vào lƣới. Tƣ tƣởng của phƣơng pháp phân hoạch là tìm cách phân chia tập dữ liệu thành các tập không giao nhau, thỏa mãn điều kiện làm tối ƣu hàm đánh giá.
Trong mỗi tập con thƣờng có ít nhất một phần tử đại diện, phần tử đại diện có thể là tâm của tập con đó. Mỗi đối tƣợng trong tập dữ liệu đƣợc phân vào cụm có điểm đại diện gần với đối tƣợng đó nhất. Quá trình này lặp đi lặp lại cho tới khi hàm mục tiêu không thay đổi. Có nhiều thuật toán áp dụng phƣơng pháp này nhƣ: K-Means, K-Medoids, EM.
Các phƣơng pháp phân cụm theo phân hoạch có thể phân cụm dữ liệu với thời gian rất nhanh đối với các tập dữ liệu lớn tuy nhiên nó có thể phân cụm sai trong trƣờng hợp hình dạng các cụm không phải là hình cầu, hoặc dữ liệu chứa nhiễu và yêu cầu phải xác định trƣớc số lƣợng cụm. Phƣơng pháp phân cấp phân tách các tập đối tƣợng theo hai cách: “Bottom - Up” hoặc “Top - Down”. Tiếp cận “Bottom – Up” bắt đầu với mỗi đối tƣợng đƣợc xem nhƣ một nhóm, sau đó trộn các đối tƣợng hay các nhóm theo các hàm nhƣ hàm khoảng cách giữa các tâm của hai nhóm và điều này đƣợc thực hiện cho tới khi tất cả các nhóm đƣợc trộn vào làm một nhóm hoặc cho tới khi điều kiện kết thúc đƣợc thỏa mãn. Tiếp cận theo phƣơng pháp “Top-Down”, bắt đầu với tất cả các đối tƣợng nằm trong cùng một cụm.
Trong mỗi lần lặp, một cụm đƣợc tách ra thành các cụm nhỏ hơn theo một ƣớc lƣợng nào đó. Điều này đƣợc thực hiện cho tới khi mỗi đối tƣợng là một cụm, hoặc cho tới khi điều kiện kết thúc thỏa mãn. Các thuật toán áp dụng phƣơng pháp này là : BIRCH, CURE, CHAMELEON. Phần lớn các phƣơng pháp phân cụm các đối tƣợng dựa trên khoảng cách giữa các đối tƣợng (thƣờng sử dụng khoảng cách Euclidean).
Vì thế có thể chỉ tìm thấy các cụm có dạng hình cầu và sẽ khó khăn khi khám phá các cụm có hình dạng bất kỳ. Đối với các phƣơng pháp đƣợc phát triển dựa trên quan niệm về mật độ. Các cụm tiêu biểu đƣợc xét là các vùng có các đối tƣợng tập trung đậm đặc và 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com đƣợc phân chia bởi các vùng có mật độ thấp (đặc trƣng cho nhiễu). Các phƣơng pháp dựa trên mật độ có thể sử dụng để lọc ra các nhiễu (phần tử ngoại lai), và khám phá ra các cụm có hình dạng bất kỳ.
Các phƣơng pháp phân cụm dựa trên mật độ thƣờng sử dụng hai tham số là Eps và Minpts để xác định các cụm có thể đƣợc khám phá. 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 ngƣỡng nào đó. Với phƣơng pháp này, khi xác định đƣợc một cụm dữ liệu thì việc phát triển thêm các đối tƣợng mới thực hiện bằng cách kiểm tra xem số các đối tƣợng lân cận (Minpts) của đối tƣợng này phải lớn hơn ngƣỡng Eps cho trƣớc. Để nâng cao chất lƣợng của phân cụm, cách tiếp cận dựa trên lƣới sử dụng cấu trúc lƣới của dữ liệu.
Nó lƣợng tử hóa khoảng cách vào một số hữu hạn các ô là cấu trúc dạng lƣới để tất cả các phép toán phân cụm thực hiện đƣợc. Ƣu điểm chính của cách tiếp cận này là nó xử lý nhanh đặc biệt phụ thuộc vào số lƣợng của các đối tƣợng dữ liệu, chỉ phụ thuộc vào số lƣợng các ô ở mỗi chiều trong không gian lƣợng hóa. Để nắm bắt hình dạng tự nhiên của cụm và tránh sự ảnh hƣởng của các phần tử ngoại lai tốt hơn, các thuật toán phân cụm mờ đƣợc đề xuất và đã cung cấp một cách tiếp cận khác để tìm kiếm cấu trúc của tập dữ liệu. Một trong những đặc điểm chính của các thuật toán này là nắm bắt tính chất chƣa rõ ràng của dữ liệu thực.
Do đó, ngƣời sử dụng đƣợc cung cấp thêm thông tin về cấu trúc trong tập dữ liệu để có thể phân cụm bằng một mô hình không mờ. Thuật toán phân cụm dữ liệu mờ, cũng nhƣ các thuật toán dựa vào phân hoạch và phân cấp đòi hỏi ngƣời sử dụng phải cung cấp số lƣợng cụm của tập dữ liệu. Đối với một tập dữ liệu thông thƣờng thì chúng ta chƣa biết trƣớc số cụm, và ngƣời sử dụng thƣờng không phải là chuyên gia để đánh giá số cụm, vì vậy một câu hỏi đƣợc đặt ra là làm thế nào để phân cụm dữ liệu với số cụm chƣa biết trƣớc ?. Làm thế nào để tìm kiếm tối ƣu số lƣợng cụm ?.
Đối với các tập dữ liệu phức tạp thì sao? Do đó, để có thể giải quyết đƣợc các vấn đề nêu trên trong luận văn sẽ đề xuất một phƣơng pháp phân cụm dữ liệu mờ với số cụm không xác định. Thuật toán này đầu tiên sẽ loại bỏ phần tử ngoại lại ra khỏi tập dữ liệu, cải tiến khởi tạo tâm ban đầu cho thuật toán phân cụm mờ K-Means, với K là chạy trong một khoảng cho trƣớc. Để xác định giá trị K đúng với số lƣợng cụm thực của tập dữ liệu, tôi đề xuất hàm đánh giá chất lƣợng phân cụm cho các kết quả phân cụm của thuật toán phân cụm mờ K-Means tƣơng ứng với mỗi giá trị của K. 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Vì vậy, luận văn đƣợc trình bày thành 4 chƣơng.
Nội dung chính trong các chƣơng đƣợc trình bày nhƣ sau: Chƣơng 1 trình bày cách biểu diễn dữ liệu trong máy tính nhằm phục vụ cho quá trình phân cụm, giới thiệu độ tƣơng đồng giữa các đối tƣợng trong tập dữ liệu, các phƣơng pháp phân cụm dữ liệu. Với mỗi phƣơng pháp phân cụm sẽ trình bày một số thuật toán tƣơng ứng. Chƣơng 2 trình bày về thuật toán phân cụm dữ liệu mờ, phƣơng pháp phát hiện các phần từ ngoại lại dựa vào đặc trƣng ngoại lai cục bộ trong tập dữ liệu. Chƣơng 3 trình bày về đề xuất thuật toán phân cụm mờ với số cụm chƣa xác chƣa xác định.
Cụ thể, luận văn sẽ trình bày phƣơng pháp loại bỏ phần tử ngoại lại trƣớc khi phân cụm, cải tiến khởi tạo tâm ban đầu cho thuật toán phân cụm mờ K-Means, đề xuất hàm đánh giá chất lƣợng phân cụm của thuật toán phân cụm mờ với K chạy trong đoạn cho trƣớc. Cũng trong chƣơng này, luận văn sẽ trình bày kết quả thực nghiệm đối với hai tập dữ liệu, đồng thời so sánh chất lƣợng phân cụm đối với hai hàm đánh giá chất lƣợng cụm là Index Partition, và Entropy Partition. Cuối cùng là chƣơng kết luận, hƣớng phát triển và tài liệu tham khảo. 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG I.
TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1. Giới thiệu Phân cụm dữ liệu là một kỹ thuật quan trọng trong công nghệ tri thức đƣợc ứng dụng rộng rãi và đa dạng trong các ngành khoa học nhƣ sinh học, tâm lý học, y học, ngành marketing, thị giác máy tính, và điều kiển học v. Phân cụm dữ liệu tổ chức dữ liệu bằng cách nhóm các đối tƣợng có độ tƣơng đồng cao để khám phá cấu trúc của dữ liệu mà không yêu cầu các giả thiết cho trƣớc từ các phƣơng pháp thống kê. Mục tiêu của phƣơng pháp phân cụm dữ liệu chỉ đơn giản là tìm kiếm các nhóm đối tƣợng theo hình dạng tự nhiên.
Các thuật toán phân cụm hƣớng tới việc tìm kiếm cấu trúc trong dữ liệu. Phƣơng pháp này còn đƣợc gọi là “học không thầy” hay “học không có giám sát” (Unsupervised Learning) trong lĩnh vực nhận dạng mẫu (Pattern Recognition) nói riêng và trong trí tuệ nhân tạo nói chung [1]. Một cụm bao gồm một tập các đối tƣợng có độ tƣơng đồng cao. Định nghĩa về cụm đƣợc phát biểu một cách không hình thức nhƣ sau: Một cụm là một tập các thực thể (các đối tƣợng) tƣơng tự nhau, và các thực thể ở các cụm khác nhau thì không giống nhau.
Tùy vào từng ứng ứng dụng, đặc tính của dữ liệu và từng phƣơng pháp phân cụm cụ thể, chúng ta có thể xem xét các dữ liệu nhƣ là các điểm trong không gian thỏa mãn điều kiện khoảng cách giữa hai điểm bất kỳ trong một cụm bé hơn khoảng cách giữa một điểm bất kỳ trong cụm đó với một điểm bất kỳ không thuộc cụm hoặc các cụm có thể đƣợc mô tả nhƣ là các vùng chứa các đối tƣợng có mật độ cao trong không gian nhiều chiều, đƣợc tách với các vùng chứa các đối tƣợng có mật độ thấp hơn. Chúng ta có thể dễ dàng phát biểu không hình thức về một cụm, nhƣng lại rất khó để có thể đƣa ra một định nghĩa hình thức về cụm. Bởi vì thực tế thì các đối tƣợng đƣợc nhóm vào trong các cụm theo các mục đích khác nhau trong từng ứng dụng. Dữ liệu có thể cho thấy các cụm theo hình dạng và theo các kích thƣớc cụm.
Các phƣơng pháp phân cụm dữ liệu thƣờng đƣợc chia làm 4 loại : Phƣơng pháp dựa vào phân hoạch ( Partition Based Data Clustering Method), phƣơng pháp phân cấp (Hierarchical Based Data Clustering Method), phƣơng pháp dựa trên mật độ (Density Based Data Clustering Method), phƣơng pháp dựa trên lƣới (Grid Based Data Clustering Method). Cụ thể của dữ liệu Các phƣơng pháp phân cụm này sẽ đƣợc trình bày chi tiết phần 4 của chƣơng này. 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Các vấn đề liên quan tới bài toán phân cụm dữ liệu là vấn đề biểu diễn dữ liệu trong máy tính, xác định phƣơng pháp, từ đó đƣa ra thuật toán cụ thể để áp dụng, đồng thời xác định độ tƣơng đồng giữa các đối tƣợng. Đối với các thuật toán trong phƣơng pháp dựa vào phân hoạch thì chúng ta còn phải xây dựng hàm đánh giá phù hợp để thuật toán cho ra kết quả phân cụm tốt.