Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für biologische Kybernetik     Collection: Biologische Kybernetik     Display Documents



ID: 420062.0, MPI für biologische Kybernetik / Biologische Kybernetik
Consistent Minimization of Clustering Objective Functions
Authors:von Luxburg, U.; Bubeck, S.; Jegelka, S.; Kaufmann, M.
Editors:Platt, J. C.; Koller, D.; Singer, Y.; Roweis, S.
Date of Publication (YYYY-MM-DD):2008-09
Title of Proceedings:Advances in Neural Information Processing Systems 20: Proceedings of the 2007 Conference
Start Page:961
End Page:968
Physical Description:8
Audience:Not Specified
Intended Educational Use:No
Abstract / Description: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 construction, and
it can b
e implem
ented wi
th small
average
case co
mplexity
using b
ranch an
d bound.
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Holger Fischer
Affiliations:MPI f�r biologische Kybernetik/Empirical Inference (Dept. Sch�lkopf)
Identifiers:LOCALID:4806
URL:http://books.nips.cc/papers/files/nips20/NIPS2007_...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.