An Impossibility Theorem for Clustering

By Jon M. Kleinberg. Neural Information Processing Systems, 2002

738 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/8061fc1eda55e82748ef4aa6a71bb9635d50b7c9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Graph Cuts and Efficient N-D Image Segmentation (2006, background): “Impossibility theorem in Kleinberg (2002) shows that no cluster-”
Clustering: Science or Art? (2009, background): “For example, one can use clustering to define certain sub-categories of diseases in medicine, or as a means for quality control to detect undesirable groupings that suggest experimental artifacts or confounding factors in the data.”
An Evolutionary Approach to Multiobjective Clustering (2007, background): “tering objectives can be conflicting or complementary, and that no single clustering objective can deal with every conceivable cluster structure [32], [33].”
An axiomatic approach for result diversification (2009, methodology): “Kleinberg [12] proposed a set of three natural axioms for clustering functions and showed that no clustering function satisfies all three axioms.”
Meta-Learning to Cluster (2019, background): “Kleinberg’s impossibility theorem [Kleinberg, 2002] states that clustering is impossible because there is no clustering algorithm that can simultaneously satisfy three very intuitive axioms that any clustering algorithm should follow (the so called axioms of Scale-Invariance, Richness, and…”
Combining multiple weak clusterings (2003, background): “In contrast to supervised classification, clustering is an inherently ill-posed problem, whose solution violates at least one of the common assumptions about scaleinvariance, richness, and cluster consistency [1].”
Topology and data (2009, background): “, [43] and [39]), and functoriality provides the right general mathematical framework for addressing them.”
A Mixture Model for Clustering Ensembles (2004, background): “Data clustering is a difficult inverse problem, and as such is ill-posed when prior information about the underlying data distributions is not well defined [15, 16, 21].”
Clustering ensembles: models of consensus and weak partitions (2005, background): “I N contrast to supervised classification, clustering is inherently an ill-posed problem whose solution violates at least one of the common assumptions about scaleinvariance , richness, and cluster consistency [33].”
Challenges in unsupervised clustering of single-cell RNA-seq data (2019, background): “More generally, finding a clustering method that is best for all situations may be futile because it has been shown that it is impos sible for a single algorithm to achieve the full range of desired properties 37 .”
Comparing clusterings: an axiomatic view (2005, background): “It is interesting to note that an impossibility result for clustering exists in (Kleinberg, 2002).”
Understanding Machine Learning: From Theory to Algorithms (2014, methodology): “However, Kleinberg (2003) has shown the following “impossibility” result:”
A classification for community discovery methods in complex networks (2011, background): “We are not formally building an axiomatic approach, such as the one built in [15] for spatial clustering.”