Consistent Minimization of Clustering Objective Functions

2008

Conference Paper

ei


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. As an alternative, we suggest the paradigm of nearest neighbor clustering‘‘. Instead of selecting the best out of all partitions of the sample, it only considers partitions in some restricted function class. Using tools from statistical learning theory we prove that nearest neighbor clustering is statistically consistent. Moreover, its worst case complexity is polynomial by co nstructi on, and it can b e implem ented wi th small average case co mplexity using b ranch an d bound.

Author(s): von Luxburg, U. and Bubeck, S. and Jegelka, S. and Kaufmann, M.
Book Title: Advances in neural information processing systems 20
Journal: Advances in Neural Information Processing Systems 20: 21st Annual Conference on Neural Information Processing Systems 2007
Pages: 961-968
Year: 2008
Month: September
Day: 0
Editors: Platt, J. C., D. Koller, Y. Singer, S. Roweis
Publisher: Curran

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

Address: Red Hook, NY, USA
Digital: 0
Event Name: Twenty-First Annual Conference on Neural Information Processing Systems (NIPS 2007)
Event Place: Vancouver, BC, Canada
ISBN: 978-1-605-60352-0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@inproceedings{4806,
  title = {Consistent Minimization of Clustering Objective Functions},
  author = {von Luxburg, U. and Bubeck, S. and Jegelka, S. and Kaufmann, M.},
  journal = {Advances in Neural Information Processing Systems 20: 21st Annual Conference on Neural Information Processing Systems 2007},
  booktitle = {Advances in neural information processing systems 20},
  pages = {961-968},
  editors = {Platt, J. C., D. Koller, Y. Singer, S. Roweis},
  publisher = {Curran},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Red Hook, NY, USA},
  month = sep,
  year = {2008},
  month_numeric = {9}
}