Consistent Minimization of Clustering Objective Functions

von Luxburg, U; Bubeck, S; Jegelka, S; Kaufmann, M

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Consistent Minimization of Clustering Objective Functions

MPS-Authors

/persons/resource/persons76237

von Luxburg, U
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;
Max Planck Institute for Biological Cybernetics, Max Planck Society;

/persons/resource/persons83994

Jegelka, S
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;
Max Planck Institute for Biological Cybernetics, Max Planck Society;

External Resource

https://papers.nips.cc/paper/3353-consistent-minimization-of-clustering-objective-functions.pdf
(Publisher version)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

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.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0013-C735-4

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.