MỞ ĐẦU Bài toán phân cum di liệu thuộc lĩnh vực học không giám sat, 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 đữ liệu là bài toán khám phá cau 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 đữ liệu với thời gian rất nhanh đối với các tập đữ 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 cach: “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 nao đó. Đ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 bat 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à đượ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 dé 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 dang bat 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 đữ liệu theo một ngưỡng nào đó. Với phương pháp này, khi xác định được một cum đữ 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 cau trúc lưới của dir 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 đữ 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 dé 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 dé có thé phan cum bang một mô hình không mờ. Thuật toán phân cum 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 dir 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 dé đánh giá số cụm, vì vậy một câu hỏi được đặt ra là làm thé nào dé phân cụm dif liệu với số cụm chưa biết trước ?. Làm thế nao dé tìm kiếm tối ưu số lượng cụm 2.
Đố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 đữ 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 phan 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. 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 bay như sau: Chương | 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 cum 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 dit 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 phat trién và tài liệu tham khảo. TONG QUAN VE PHAN CUM DU LIEU 1.
Giới thiệu Phân cum đữ 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 đữ 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 cu 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 bat kỳ trong cụm đó với một điểm bat 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é dang phát biểu không hình thức về một cụm, nhưng lại rất khó dé 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 cum di liệu thường được chia làm 4 loại : Phuong 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 mat độ (Density Based Data Clustering Method), phương pháp dựa trên lưới (Grid Based Data Clustering Method).
Cụ thể của đữ liệu Các phương pháp phân cụm này sẽ được trình bày chỉ tiết phần 4 của chương này. Các van đề liên quan tới bài toán phân cụm dir liệu là van đề 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é dé á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 dé thuật toán cho ra kết quả phân cụm tốt. Biểu diễn dữ liệu Điều kiện đầu tiên của tất cả các ứng dụng áp dụng thuật toán phân cụm dữ liệu là trích chọn các đặc trưng cần thiết của các đối tượng trong tập dữ liệu liệu thực, các đối tượng phải được biểu diễn dưới dạng dữ liệu, tức chúng ta phải xác định các kiểu đữ liệu cho các thuộc tinh của đối tượng.
Các thuật toán phân cụm được áp dụng cho từng kiểu dữ liệu.