Supervised clustering with support vector machines

ABSTRACT

Supervised clustering is the problem of training a clustering algorithm to produce desirable clusterings: given sets of items and complete clusterings over these sets, we learn how to cluster future sets of items. Example applications include noun-phrase coreference clustering, and clustering news articles by whether they refer to the same topic. In this paper we present an SVM algorithm that trains a clustering algorithm by adapting the item-pair similarity measure. The algorithm may optimize a variety of different clustering functions to a variety of clustering performance measures. We empirically evaluate the algorithm for noun-phrase and news article clustering.

REFERENCES

• 1: Charu C. Aggarwal , Stephen C. Gates , Philip S. Yu, On the merits of building categorization systems by supervised clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.352-356, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312279]
• 2: Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Machine Learning, v.56 n.1-3, p.89-113 [doi>10.1023/B:MACH.0000033116.57574.95]
• 3: Sugato Basu , Mikhail Bilenko , Raymond J. Mooney, A probabilistic framework for semi-supervised clustering, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014062]
• 4: Mikhail Bilenko , Sugato Basu , Raymond J. Mooney, Integrating constraints and metric learning in semi-supervised clustering, Proceedings of the twenty-first international conference on Machine learning, p.11, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015360]
• 5: Cohen, W., & Richman, J. (2001). Learning to match and cluster entity names. ACM SIGIR workshop on Mathematical/Formal Methods in IR.
• 6: De Bie, T., Momma, M., & Cristianini, N. (2003). Efficiently learning the metric using side-information. ALT2003 (pp. 175--189). Sapporo, Japan: Springer.
• 7: Demaine, E., & Immorlica, N. (2003). Correlation clustering with partial information. RANDOM-APPROX 2003 (pp. 1--13). Princeton, New Jersey.
• 8: Joachims, T. (2003). Learning to align sequences: A maximum-margin approach (Technical Report).
• 9: Toshihiro Kamishima , Fumio Motoyoshi, Learning from Cluster Examples, Machine Learning, v.53 n.3, p.199-233, December 2003 [doi>10.1023/A:1026351106797]
• 10: Gert R. G. Lanckriet , Nello Cristianini , Peter Bartlett , Laurent El Ghaoui , Michael I. Jordan, Learning the Kernel Matrix with Semidefinite Programming, The Journal of Machine Learning Research, 5, p.27-72, 12/1/2004
• 11: Andrew McCallum , Kamal Nigam , Lyle H. Ungar, Efficient clustering of high-dimensional data sets with application to reference matching, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.169-178, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347123]
• 12: McCallum, A., & Wellner, B. (2003). Toward conditional models of identity uncertainty with application to proper noun coreference. IIWeb (pp. 79--84).
• 13: MUC-6 (1995). Proceedings of the Sixth Message Understanding Conference (MUC-6). San Francisco, California: Morgan Kaufmann.
• 14: Vincent Ng , Claire Cardie, Improving machine learning approaches to coreference resolution, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073102]
• 15: Rand, W. M. (1971). Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66, 846--850.
• 16: Wee Meng Soon , Hwee Tou Ng , Daniel Chung Yong Lim, A machine learning approach to coreference resolution of noun phrases, Computational Linguistics, v.27 n.4, December 2001
• 17: Chaitanya Swamy, Correlation Clustering: maximizing agreements via semidefinite programming, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 18: Ben Taskar , Vassil Chatalbashev , Daphne Koller, Learning associative Markov networks, Proceedings of the twenty-first international conference on Machine learning, p.102, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015444]
• 19: Taskar, B., Guestrin, C., & Koller, D. (2003). Max-margin markov networks. NIPS.
• 20: Ioannis Tsochantaridis , Thomas Hofmann , Thorsten Joachims , Yasemin Altun, Support vector machine learning for interdependent and structured output spaces, Proceedings of the twenty-first international conference on Machine learning, p.104, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015341]
• 21: Marc Vilain , John Burger , John Aberdeen , Dennis Connolly , Lynette Hirschman, A model-theoretic coreference scoring scheme, Proceedings of the 6th conference on Message understanding, November 06-08, 1995, Columbia, Maryland [doi>10.3115/1072399.1072405]
• 22: Kiri Wagstaff , Claire Cardie , Seth Rogers , Stefan Schrödl, Constrained K-means Clustering with Background Knowledge, Proceedings of the Eighteenth International Conference on Machine Learning, p.577-584, June 28-July 01, 2001