English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Consistent Minimization of Clustering Objective Functions

von Luxburg, U., Bubeck, S., Jegelka, S., & Kaufmann, M. (2008). Consistent Minimization of Clustering Objective Functions. In C. Platt, D. Koller, Y. Singer, & S. Roweis (Eds.), Advances in Neural Information Processing Systems 20: 21st Annual Conference on Neural Information Processing Systems 2007 (pp. 961-968). Red Hook, NY, USA: Curran.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-C735-4 Version Permalink: http://hdl.handle.net/21.11116/0000-0003-3805-9
Genre: Conference Paper

Files

show Files

Creators

show
hide
 Creators:
von Luxburg, U1, 2, Author              
Bubeck, S, Author              
Jegelka, S1, 2, Author              
Kaufmann, M, Author
Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              

Content

show
hide
Free keywords: -
 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. As an alternative, we suggest the paradigm of nearest neighbor clusteringamp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lsquo;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lsquo;. 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.

Details

show
hide
Language(s):
 Dates: 2008-09
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: 4806
 Degree: -

Event

show
hide
Title: Twenty-First Annual Conference on Neural Information Processing Systems (NIPS 2007)
Place of Event: Vancouver, BC, Canada
Start-/End Date: 2007-12-03 - 2007-12-06

Legal Case

show

Project information

show

Source 1

show
hide
Title: Advances in Neural Information Processing Systems 20: 21st Annual Conference on Neural Information Processing Systems 2007
Source Genre: Proceedings
 Creator(s):
Platt, C, Editor
Koller, D, Editor
Singer, Y, Editor
Roweis, ST, Editor
Affiliations:
-
Publ. Info: Red Hook, NY, USA : Curran
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 961 - 968 Identifier: ISBN: 978-1-605-60352-0