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. | JOURNAL OF SCIENCE OF HNUE FIT. 2013 Vol. 58 pp. 60-69 This paper is available online at http 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@ 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ột tiê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ủa thế 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ổng lồ 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 2011 sẽ 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ật toán .
