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 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 1Khoa Điện tử, Trường ĐH Kĩ thuật Công nghiệp, ĐH Thái Nguyên; 2Khoa CNTT, Trường ĐH Công nghiệp Hà Nội; 3LIP6, ĐH Pierre và Marie Curie 75005, Paris, Cộng hòa Pháp; 4Khoa Toán, Trường ĐH Sư Phạm, ĐH Thái Nguyên 1Email: 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ậpX 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 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ất lượ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ác tạ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át triển các phương pháp phân cụm nửa giám sát (semi-supervised clustering). Các thuật toá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 (side information) 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 đã được gán nhãn (labeled data hay còn gọi là seed) và các ràng buộc (constraint). Các constraint bao 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ột cụ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-supervised clustering 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ữa chấ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ất lượ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ời cả hai loại side information là các seed và các constraint. Chúng tôi cũng phát triển một kĩ 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ứu 2.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ách mạ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ền nghị 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 Graph Clustering [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 side information. Hiện nay, các thuật toán semi-supervised clustering sử dụng constraint bằng hai cá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 trong khô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ìm thỏ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ình clustering như trong các nghiên cứu về COP-Kmeans [32], Constrained Leader Ant[16] hoặc C-DBSCAN[5]. Với phương pháp thỏa mãn tối đa các constraint, các constraint sẽ được tích hợp vào trong hàm mục tiêu (object function) và áp dụng một số phương pháp tối ưu để giải quyết các hàm mục tiêu trong các thuật toán như Fuzzy C-Means[10, 21], K-Means [18, 23]. Phương pháp sử dụng các constraint để huấn luyện một hàm khoảng cách: Trong phương pháp này các constraint sẽ được dùng để huấn luyện (training) nhằm xây dựng một hàm khoảng cách sao cho trong không gian độ đo mới, các điểm dữ liệu thuộc cùng ràng buộc must-link sẽ “gần nhau” hơn và ngược lại các điểm thuộc về các cannot-link sẽ “xa nhau” ra. Một số hàm khoảng cách đã được các tác giả sử dụng trong các nghiên cứu như: string-edit [36], Jensen-Shannon [37], Euclidean [38] và Mahalanobis [31]. Với các thuật toán semi-suypervised clustering sử dụng các seed, chúng tôi có thể kể ra đây một số nghiên cứu quan trọng như Seed K-Means [30], Seed Fuzzy C-Means[33], Seed DBSCAN [5], Seed Graph Clustering [4],... Trong thuật toán Seed K-Means được trình bày bằng cách sử dụng một số seed nhằm vượt qua hạn chế của thuật toán K-Means trong vấn đề lựa chọn các trọng tâm của các lớp - thuật toán K-Means thường có các kết quả khác nhau sau mỗi lần thi hành vì chúng phụ thuộc vào vấn đề lựa chọn các trọng tâm ngẫu nhiên. Các seed sẽ được dùng vào việc trợ giúp quá trình khởi tạo cho các trọng tâm và vì vậy thuật toán sẽ cho ra kết quả xác định sau duy nhất một lần thực hiện. Trong Seed Fuzzy C-Means được giới thiệu bằng cách sử dụng các seed vào việc trợ giúp quá trình khởi tạo và điều khiển kích thước của các cluster. Trong Seed DBSCAN, các seed được sử dụng để đánh giá mật độ của dữ liệu giúp cho thuật toán có thể thực hiện phân cụm trong trường hợp dữ liệu đầu vào có mật độ dữ liệu là khác nhau. Với Seed Graph clustering, các tác giả đã sử dụng các seed 62 Phân cụm nửa giám sát dựa trên đồ thị trong việc trợ giúp quá trình phân rã các đồ thị để được các thành phần đồ thị con liên thông chỉ chứa duy nhất một loại seed trước khi xây dựng các cụm. Hiện nay các thuật toán semi-supervised clustering vẫn không ngừng được phát triển và cải tiến. Hạn chế cơ bản của các thuật loại này là chúng chỉ tích hợp được từng loại side information riêng rẽ - hoặc là các seed hoặc là các constraint mà chưa tích hợp được cả hai loại vào trong cùng một thuật toán, thách thức này cũng đã được chỉ ra trong [9]. 2.2. Thuật toán SSDBSCAN Thuật toán SSDBSCAN [15] (Semi-Supervised Density based Clustering) là một cải tiến của thuật toán DBSCAN [39]. Ý tưởng cơ bản của thuận toán DBSCAN là sử dụng khái niệm mật độ của các đối tượng để xây dựng các cluster. DBSCAN sử dụng hai tham số là MinPts và ε. Trong quá trình xây dựng các cluster, DBSCAN sẽ kết nối trực tiếp các “siêu cầu” có bán kính ε mà ở đó nó chứa ít nhất MinPts đối tượng; với tính chất này DBSCAN có khả năng phát hiện các nhiễu của dữ liệu. Tuy nhiên, trên thực tế dữ liệu đầu vào thường sẽ có mật độ khác nhau giữa các vùng, chính vì vậy thuật toán DBSCAN không thể xây dựng chính xác các cluster ở các vùng có mật độ khác nhau khi ε là cố định. Thuật toán SSDBSCAN ra đời bằng cách sử dụng các seed để trợ giúp trong việc tự động tính toán ε trong quá trình phân cụm, và vì vậy SSDBSCAN có thể xây dựng các cluster với các mật độ dữ liệu là khác nhau. Thuật toán SSDBSCAN sử dụng duy nhất một tham số là MinPts, ε sẽ được tính toán tự động dựa trên mật độ dữ liệu. Trong thuật toán SSDBSCAN, dữ liệu đầu vào sẽ được biểu diễn bởi một đồ thị vô hướng có trọng số trong đó mỗi đỉnh là một đối tượng dữ liệu, mỗi cạnh giữa hai đối tượng p và q sẽ được xác định bởi giá trị rDist() được định nghĩa ngay sau đây. rDist() biểu thị cho giá trị nhỏ nhất của ε sao cho với hai đối tượng p và q thì p và q sẽ có ít nhấtMinPts đối tượng nằm trong “siêu cầu” bán kính ε, hơn nữa và p và q có thể kết nối trực tiếp được với nhau - tức là p nằm trong “siêu cầu” bán kính ε của q và ngược lại. Vì vậy, rDist được định nghĩa như sau: ∀p, q ∈ X, rDist(p, q) = max(cDist(p), cDist(q), d(p, q)) (2.1) Trong đó d(p, q) là khoảng cách giữa p và q, cDist(o) là khoảng cách nhỏ nhất mà ở đó o vẫn chứa đủMinPts đối tượng trong nó. Quá trình xây dựng các cluster trong SSDBSCAN như sau: Sử dụng rDist(), chúng ta bắt đầu xây dựng cluster C bằng cách sử dụng một seed đầu tiên p, tiếp theo cluster C sẽ được thêm các điểm thỏa mãn rDist() vào C. Quá trình sẽ tiếp tục đến khi gặp một điểm q có nhãn khác với nhãn của p. Tiếp đó, thuật toán sẽ quay trở lại đến điểm o với giá trị rDist(o) là lớn nhất trên đường đi mở rộng cluster C. Chúng ta sẽ gọi đây là “nhát cắt” lớn nhất của các rDist(). Quá trình xây dựng cluster C hoàn thành, C sẽ bao gồm các điểm trong quá trình mở rộng đến o (không kể o), cho chúng ta một cluster C chứa seedp. Việc tìm kiếm các cluster tiếp theo sẽ được thực hiện theo quy trình tương tự. Quá trình tìm kiếm các cluster giống như quy trình đi xây dựng cây khung nhỏ nhất trên đồ thị, 63 V.V.Vũ, V.V.Thắng, N.Labroche, B.B.Meunier, N.T.T.Hiền vì vậy chúng ta có thể áp dụng các thuật toán Kruskal hoặc Prim trong lí thuyết đồ thị. 2.3. Thuật toán ASSDBSCAN Trong bài báo này chúng tôi cải tiến SSDBSCAN thành thuật toán ASSDBSCAN (Active learning for SSDBSCAN) theo hai khía cạnh: (1) Kết hợp các ràng buộc must-link và cannot-link vào trong quá trình phân cụm và (2) xây dựng một pha tương tác với người sử dụng (active learning) nhằm quyết định chính xác “nhát cắt” trong quá trình mở rộng cluster. Các thuật toán active learning được chỉ ra rất hiệu quả trong rất nhiều nghiên cứu về việc đi thu thập các side information từ người sử dụng [1,6, 11,12,13,22,34]. Trên thực tế chúng ta thấy rằng, dữ liệu thực là rất đa dạng (nhiễu, không đồng đều về mật độ phân bố, các cluster có thể rất gần nhau,...), vì vậy việc sử dụng “nhát cắt” lớn nhất cho việc xây dựng cluster không phải bao giờ cũng đúng. Chúng tôi sẽ xây dựng pha active learning nhằm mục đích tương tác với người sử dụng cho quá trình xác định “nhát cắt”. 64 Phân cụm nửa giám sát dựa trên đồ thị Quá trình active learning như sau: Xuất phát từ “nhát cắt” lớn nhất, thuật toán sẽ đưa ra câu hỏi cho người sử dụng để biết nhát cắt này có nối hai điểm nằm về hai cluster khác nhau hay không (cannot-link). Nếu câu trả lời là không thì pha “active learning” sẽ tiếp tục với rDist() lớn nhất chưa được chọn,... và quá trình sẽ kết thúc khi câu trả lời của người sử dụng là cannot-link. Và cluster C sẽ bao gồm các điểm trong quá trình mở rộng cluster đến khi gặp ràng buộc cannot-link. Thuật toán ASSDBSCAN được trình bày trong Algorithm 1 và Algorithm 2. 2.4. Kết quả thực nghiệm Để đánh giá chất lượng của thuật toán đưa ra chúng tôi tiến hành so sánh thuật toán ASDBSCAN và thuật toán SSDBSCAN. Chúng tôi sử dụng 6 tập dữ liệu được lấy từ UCI Machine Learning [35] (Bảng 1). Để đánh giá kết quả của clustering, chúng tôi sử dụng hàm Rand - một phương pháp phổ biến trong quá trình đánh giá kết quả của clustering [19]. Bảng 1. Các tập dữ liệu sử dụng Tập dữ liệu n m k 1 Ecoli 336 8 8 2 Glass 214 9 6 3 Iris 150 4 3 4 LetterIJL 227 16 3 5 Protein 116 6 6 6 Thyroid 101 16 7 (n: số phần tử cần clustering,m: số thuộc tính, k là số cluster) 65 V.V.Vũ, V.V.Thắng, N.Labroche, B.B.Meunier, N.T.T.Hiền Hình 2 trình bãy kết quả của quá trình clustering cho lần lượt 6 tập dữ liệu ở trên. Chúng ta có thể thấy rõ, thuật toán ASSDBSCAN cho kết quả tốt hơn hẳn thuật toán SSDBSCAN. Kết quả này khẳng định giả thiết của chúng tôi về việc xác định “nhát cắt” lớn nhất trong quá trình xây dựng cluster. Việc trợ giúp của người sử dụng trong pha “active learning” đã đem lại hiệu quả rất rõ trong quá trình clustering. Chúng tôi cũng lưu ý rằng, trong hình 2, thuật toán SSDBSCAN chỉ sử dụng các seed trong khi thuật toán ASSDBSCAN sử dụng cả seed và ràng buộc (số lượng ràng buộc chính là số lượng query trong quá trình active learning). Hình 2. Kết quả thực nghiệm 66 Phân cụm nửa giám sát dựa trên đồ thị 3. Kết luận Bài báo này trình bày một phương pháp mới cho bài toán semi-supervised clustering ASSDBSCAN. ASSDBSCAN là thuật toán đầu tiên trên thế giới có khả năng kết hợp cả hai loại side information là seed và constraint trong quá trình clustering. Kết quả thực nghiệm trên các tập dựu liệu thực từ UCI Machine Learning đã chứng minh tính hiệu quả của thuật toán ASSDBSCAN. Trong thời gian tới, chúng tôi tiếp tục mở rộng hướng nghiên cứu này cho các loại thuật toán clustering khác cũng như thử nghiệm đối với các tập dữu liệu thực tế của các lĩnh vực như Computer Vision hay các tập dữ liệu Biology. TÀI LIỆU THAM KHẢO [1] Viet-Vu Vu, Nicolas Labroche, and Bernadette Bouchon-Meunier, Improving Constrained Clustering with Active Query Selection, Pattern Recognition 45(4): 1749-1758 (2012), ISSN: 0031-3203. [2] Sean Gilpin, Ian Davidson: Incorporating SAT solvers into hierarchical clustering algorithms: an efficient and flexible approach. KDD 2011: 1136-1144 [3] Tengke Xiong, Shengrui Wang, André Mayers, Ernest Monga: Semi-supervised Parameter-Free Divisive Hierarchical Clustering of Categorical Data. PAKDD 2011: 265-276 [4] Viet-Vu Vu, Semi-supervised Clsutering and Active Learning, PhD Thesis, Paris 6 University, 2011 [5] Carlos Ruiz, Myra Spiliopoulou, Ernestina Menasalvas Ruiz: Density-based semi-supervised clustering. Data Min. Knowl. Discov. 21(3): 345-370 (2010) [6] Burr Settles: Active Learning Literature Survey, Computer Sciences Technical Report 1648, University of Wisconsin-Madison, 2010. [7] Xiang Wang, Ian Davidson: Active Spectral Clustering. ICDM 2010: 561-568 [8] Xiang Wang, Ian Davidson: Flexible constrained spectral clustering. KDD 2010: 563-572 [9] Anil K. Jain: Data clustering: 50 years beyond K-means. Pattern Recognition Letters (PRL) 31(8):651-666 (2010). [10] Violaine Antoine, Benjamin Quost, Marie-Hélène Masson, Thierry Denoeux: CECM: Adding pairwise constraints to evidential clustering. FUZZ-IEEE 2010: 1-8 [11] Viet-Vu Vu, Nicolas Labroche, and Bernadette Bouchon-Meunier. Active Learning for Semi-Supervised K-Means Clustering. In Proceedings of the 22nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI-2010), Arras, France, October, 2010. [12] Viet-Vu Vu, Nicolas Labroche, and Bernadette Bouchon-Meunier. Boosting Clustering by Active Constraint Selection. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI-2010), Lisbon, Portugal, August, 2010. 67 V.V.Vũ, V.V.Thắng, N.Labroche, B.B.Meunier, N.T.T.Hiền [13] Viet-Vu Vu, Nicolas Labroche, and Bernadette Bouchon-Meunier. An Efficient Active Constraint Selection Algorithm for Clustering. In Proceedings of the 20th IEEE International Conference on Pattern Recognition (ICPR-2010), Istanbul, Turkey, August, 2010. [14] Brian Kulis, Sugato Basu, Inderjit S. Dhillon, Raymond J.Mooney: Semi-supervised graph clustering: a kernel approach. Machine Learning 74(1): 1-22 (2009) [15] Levi Lelis, Jo¨rg Sander: Semi-supervised Density-Based Clustering. ICDM 2009: 842-847 [16] Viet-Vu Vu, Nicolas Labroche, and Bernadette Bouchon-Meunier. Leader Ant Clustering with Constraints. In Proceedings of the 7th IEEE International Conference on Computing and Communication Technologies (IEEE-RIVF-2009), Danang, Vietnam, July, 2009. [17] Ian Davidson, S. S. Ravi: Using instance-level constraints in agglomerative hierarchical clustering: theoretical and empirical results. Data Min. Knowl. Discov. (DATAMINE) 18(2):257-282 (2009) [18] Zijie Qi, Ian Davidson: A principled and flexible framework for finding alternative clusterings. KDD 2009: 717-726 [19] S. Basu, I. Davidson, and K. L. Wagstaff, Constrained Clustering: Advances in Algorithms, Theory, and Applications, Chapman and Hall/CRC Data Mining and Knowledge Discovery Series, 1st edn., 2008. [20] Christian Bo¨hm, Claudia Plant: HISSCLU: a hierarchical density-based method for semi-supervised clustering. EDBT 2008: 440-451 [21] Nizar Grira, Michel Crucianu, Nozha Boujemaa: Active semi-supervised fuzzy clustering. Pattern Recognition 41(5): 1834-1844 (2008) [22] Pavan Kumar Mallapragada, Rong Jin, Anil K. Jain: Active query selection for semi-supervised clustering. ICPR 2008: 1-4 [23] Ian Davidson, S. S. Ravi: The complexity of non-hierarchical clustering with instance and cluster level constraints. Data Min. Knowl. Discov. (DATAMINE) 14(1):25-61 (2007) [24] Brian Kulis, Sugato Basu, Inderjit S. Dhillon, Raymond J. Mooney: Semi-supervised graph clustering: a kernel approach. ICML 2005: 457-464 [25] Qianjun Xu, Marie desJardins, Kiri Wagstaff: Active Constrained Clustering by Examining Spectral Eigenvectors. Discovery Science 2005: 294-307 [26] Sugato Basu, Arindam Banerjee, Raymond J. Mooney: Active Semi-Supervision for Pairwise Constrained Clustering. SDM 2004 [27] Sugato Basu, Mikhail Bilenko, Raymond J. Mooney: A probabilistic framework for semi-supervised clustering. KDD 2004: 59-68 [28] Mikhail Bilenko, Sugato Basu, Raymond J. Mooney: Integrating constraints and metric learning in semi-supervised clustering. ICML 2004 68 Phân cụm nửa giám sát dựa trên đồ thị [29] Kamvar, S.D., Klein, D., Manning, C.D.: Spectral learning. In: Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. (2003) 561-566 [30] Sugato Basu, Arindam Banerjee, Raymond J. Mooney: Semi-supervised Clustering by Seeding. ICML 2002: 27-34 [31] Eric P. Xing, Andrew Y. Ng, Michael I. Jordan, Stuart J. Russell: Distance Metric Learning with Application to Clustering with Side-Information. NIPS 2002:505-512 [32] Kiri Wagstaff, Claire Cardie, Seth Rogers, Stefan Schro¨dl: Constrained K-means Clustering with Background Knowledge. ICML 2001: 577-584 [33] Amine Bensaid, Lawrence O. Hall, James C. Bezdek, Laurence P. Clarke: Partially supervised clustering for image segmentation. Pattern Recognition 29(5): 859-871 (1996) [34] Viet-Vu Vu, Nicolas Labroche, and Bernadette Bouchon-Meunier. Active Semi-Supervised Density-based Clustering. Submitted to the 20th European Conference on Artificial Intelligence (ECAI-2012), Montpelier, France, August, 2012 [35] [36] Cohn, D., Caruana, R., & McCallum, A. (2003). Semi-supervised clustering with user feedback (Tech. Report TR2003-1892).Cornell University. [37] Klein, D., Kamvar, S. D., & Manning, C. (2002). From instancelevel constraints to space-level constraints: Making the most of prior knowledge in data clustering. Proceedings of the The Nin