nips nips2002 nips2002-27 nips2002-27-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jon M. Kleinberg
Abstract: Although the study of clustering is centered around an intuitively compelling goal, it has been very difficult to develop a unified framework for reasoning about it at a technical level, and profoundly diverse approaches to clustering abound in the research community. Here we suggest a formal perspective on the difficulty in finding such a unification, in the form of an impossibility theorem: for a set of three simple properties, we show that there is no clustering function satisfying all three. Relaxations of these properties expose some of the interesting (and unavoidable) trade-offs at work in well-studied clustering techniques such as single-linkage, sum-of-pairs, k-means, and k-median. 1
[1] M. Anderberg, Cluster Analysis for Applications, Academic Press, 1973.
[2] K. Arrow, Social Choice and Individual Values, Wiley, New York, 1951.
[3] M. Bern, D. Eppstein, “Approximation algorithms for geometric prolems,” in Approximation Algorithms for NP-Hard Problems, (D. Hochbaum, Ed.), PWS Publishing, 1996.
[4] R. Duda, P. Hart, D. Stork, Pattern Classification (2nd edition), Wiley, 2001.
[5] P. Hansen, F. Roberts, “An impossibility result in axiomatic location theory,” Mathematics of Operations Research 21(1996).
[6] A. Jain, R. Dubes, Algorithms for Clustering Data, Prentice-Hall, 1981.
[7] N. Jardine, R. Sibson, Mathematical Taxonomy Wiley, 1971.
[8] A. Kalai, C. Papadimitriou, S. Vempala, A. Vetta, personal communication, June 2002.
[9] P. Mirchandani, R. Francis, Discrete Location Theory, Wiley, 1990.
[10] M. Osborne A. Rubinstein, A Course in Game Theory, MIT Press, 1994.
[11] D. Pennock, E. Horvitz, C.L. Giles, “Social choice theory and recommender systems: Analysis of the axiomatic foundations of collaborative filtering,” Proc. 17th AAAI, 2000.
[12] J. Puzicha, T. Hofmann, J. Buhmann “A Theory of Proximity Based Clustering: Structure Detection by Optimization,” Pattern Recognition, 33(2000).