CS 789 THEORY SEMINAR [home]

Speaker:  Jon Kleinberg
Affiliation: Computer Science, Cornell University
Date: Monday, January 27, 2003
Title: An Impossibility Theorem for Clustering

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. I'll propose 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 --- essentially scale-invariance, a `richness' requirement that all partitions be achievable, and a consistency condition on the shrinking and stretching of individual distances --- one can 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.