Phân cụm nửa giám sát dựa trên đồ thị

Trong bài báo này, chúng tôi mở rộng một thuật toán phân cụm nửa giám sát sử dụng các seed bằng cách thêm vào một kĩ thuật học tích cực (active learning) để thu thập các ràng buộc từ người sử dụng. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Phân cụm nửa giám sát dựa trên đồ thị JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 60-69 This paper is available online at http://stdb.hnue.edu.vn PHÂN CỤM NỬA GIÁM SÁT DỰA TRÊN ĐỒ THỊ Vũ Việt Vũ1, Vũ Việt Thắng2, Nicolas Labroche3, Bernadette Bouchon Meunier3, Nguyễn Thị Thu Hiền4 1 Khoa Điện tử, Trường ĐH Kĩ thuật Công nghiệp, ĐH Thái Nguyên; 2 Khoa CNTT, Trường ĐH Công nghiệp Hà Nội; 3 LIP6, ĐH Pierre và Marie Curie 75005, Paris, Cộng hòa Pháp; 4 Khoa Toán, Trường ĐH Sư Phạm, ĐH Thái Nguyên 1 Email: vuvietvu@gmail.com Tóm tắt. Thuật toán phân cụm nửa giám sát sử dụng một số lượng ít các dữ liệu đã gán nhãn (seeds) hoặc một số ràng buộc (must-link hoặc can-not link) giữa các dữ liệu nhằm mục đích cải tiến chất lượng của bài toán phân cụm. Trong bài báo này, chúng tôi mở rộng một thuật toán phân cụm nửa giám sát sử dụng các seed bằng cách thêm vào một kĩ thuật học tích cực (active learning) để thu thập các ràng buộc từ người sử dụng. Theo chúng tôi biết đây là thuật toán đầu tiên trên thế giới sử dụng đồng thời cả hai loại seed và constraint vào trong cùng một quá trình phân cụm. Kết quả thực nghiệm cho thấy thuật toán của chúng tôi cải tiến đáng kể chất lượng của quá trình phân cụm trên các tập dự liệu thực. Từ khóa: Thuật toán, phân cụm nửa giám sát, đồ thị.1. Mở đầu Bài toán phân cụm (clustering) là một dạng của phương pháp học không giám sát(unsupervised learning) được phát biểu như sau: cho tập X gồm n đối tượng, hãy phân rãtập X ra thành k (k ≤ n) cụm (cluster) sao cho các đối tượng trong cùng một cụm thìtương tự nhau và các đối tượng ở các cụm khác nhau thì không tương tự nhau theo mộttiêu chuẩn nào đó. Mặc dù những thuật toán đầu tiên đưa ra giải quyết vấn đề này như K-Means,Hierarchical Clustering hay Graph-based Clustering đã xuất hiện vào những năm 60 củathế kỉ trước, tuy nhiên với sự bùng nổ thông tin như vũ bão, rất nhiều nguồn dữ liệu khổnglồ xuất hiện (tổng số dữ liệu được số hóa từ nhiều nguồn khác nhau trên thế giới năm 2011sẽ khoảng 2810 exabyte [9]) ở các lĩnh vực khác nhau đòi hỏi chúng ta phải có các thuậttoán phân cụm dữ liệu hiệu quả để đáp ứng được các yêu cầu đặt ra cả về tốc độ lẫn chấtlượng. Hiện nay bài toán phân cụm là một chủ đề quan trọng trong các hội thảo và cáctạp chí hàng đầu quốc tế như ICDM, ICML, KDD, ECAI, PAMI, Pattern Recognition,Machine learning,...60 Phân cụm nửa giám sát dựa trên đồ thị Một trong những hướng nghiên cứu quan trọng trong các năm gần đây là pháttriển các phương pháp phân cụm nửa giám sát (semi-supervised clustering). Các thuậttoán phân cụm nửa giám sát sẽ sử dụng các thông tin có được từ người sử dụng (sideinformation) nhằm mục đích trợ giúp trong quá trình phân cụm và vì vậy cải tiến đáng kểchất lượng của clustering. Trên thực tế, có hai loại side information thường được sử dụng là các dữ liệu đã đượcgán nhãn (labeled data hay còn gọi là seed) và các ràng buộc (constraint). Các constraintbao gồm hai loại: must-link(u,v) (u, v ∈ X) biểu thị u và v sẽ được phân vào cùng mộtcụm và cannot-link(u,v) biểu thị u và v sẽ được phân về hai cụm khác nhau. Mặc dù đãcó rất nhiều nghiên cứu quan trọng được đưa ra nhưng các thuật toán semi-supervisedclustering mới chỉ dừng lại ở việc tích hợp từng loại side information riêng lẻ, hơn nữachất lượng của các bài toán loại này còn phụ thuộc vào việc lựa chọn số lượng và chấtlượng của các side information. (a) Partially labelled (b) Partially constrained Hình 1. Các dạng side information là seed và constraint Trong bài báo này, chúng tôi sẽ tập trung vào giải quyết bài toán sau đây: Phát triển một phương pháp phân cụm nửa giám sát có khả năng tích hợp đồng thờicả hai loại side information là các seed và các constraint. Chúng tôi cũng phát triển mộtkĩ thuật cho phép tham khảo ý kiến người sử dụng về việc ra các quyết định trong quátrình phân cụm các đối tượng.2. Nội dung nghiên cứu2.1. Tổng quan tình hình nghiên cứu Các phương pháp semi-supervised clustering bắt đầu được nghiên cứu một cáchmạnh mẽ từ sau nghiên cứu của Wagstaff về Constrained K-Means Clustering tại hội 61 V.V.Vũ, V.V.Thắng, N.Labroche, B.B.Meunier, N.T.T.Hiềnnghị ICML năm 2001 [32]. Chúng tôi liệt kê ra đây một số thuật toán cơ bản bao gồm:Constrained Hierarchical Clustering [2,3,17], Constraint Spectral Clustering [7,8,25,29],Constraint DBSCAN [5], Constrained-Kmeans [26,27,28,31], Constraint Fuzzy C-Means[10,21], Constraint Leader Ant Clustering [16], Constrainted Graph Clustering [14, 24], Seed Fuzzy C-means[33], Seed K-Means [30], Seed DBSCAN [15, 20], Seed GraphClustering [4],... Các thuật toán semi-supervised clustering đã được nghiên cứu khẳngđịnh chất lượng phân cụm được tăng lên rõ rệt với sự sử dụng chỉ một lượng nhỏ các sideinformation. Hiện nay, các thuật toán semi-supervised clustering sử dụng constraint bằng haicách: các constraint sẽ được “nhúng” trực tiếp trong quá trình clustering hoặc sử dụng đểhuấn luyện (training) một hàm độ đo nhằm xây dựng một hàm khoảng cách mới trongkhông gian dữ liệu. Phương pháp sử dụng trực tiếp các constraint: Trong phương pháp này, có hai cáchđược sử dụng dụng là: các chiến thuật thỏa mãn tất cả các ràng buộc và các chiến thuật tìmthỏa mãn một cách tối đa các ràng buộc. Với các kĩ thuật thỏa mãn tất cả các ràng buộc,quá clustering sẽ được kiểm tra sự thỏa mãn của các constraint liên tục trong quá trìnhclustering như trong các nghiên cứu về COP-Kmeans [32], Constrained Leader Ant[1 ...