Overfitting of Clustering and how to avoid it

Sébastien Bubeck 1 Ulrike von Luxburg 2
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : Clustering is often formulated as a discrete optimization problem. The objective is to find, among all partitions of the data set, the best one according to some quality measure. However, in the statistical setting where we assume that the finite data set has been sampled from some underlying space, the goal is not to find the best partition of the given sample, but to approximate the true partition of the underlying space. We argue that the discrete optimization approach usually does not achieve this goal, and instead can lead to overfitting. We construct examples which provably have this behavior. As in the case of supervised learning, the cure is to restrict the size of the function classes under consideration. For appropriate ``small'' function classes we can prove very general consistency theorems for clustering optimization schemes. As one particular algorithm for clustering with a restricted function space we introduce ``nearest neighbor clustering''. Similar as the k-nearest neighbor classifier in supervised learning, this algorithm can be seen as a general baseline algorithm to minimize arbitrary clustering objective functions. We prove that it is statistically consistent for all commonly used clustering objective functions.
Complete list of metadatas

Contributor : Sébastien Bubeck <>
Submitted on : Wednesday, November 7, 2007 - 9:27:35 AM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Monday, September 24, 2012 - 2:56:10 PM


Files produced by the author(s)


  • HAL Id : inria-00185780, version 1


Sébastien Bubeck, Ulrike von Luxburg. Overfitting of Clustering and how to avoid it. 2007. ⟨inria-00185780v1⟩



Record views


Files downloads