← Back to papers
2010 NIPS NeurIPS 2010

Rates of convergence for the cluster tree

Abstract

For a density f on R^d, a high-density cluster is any connected component of {x: f(x) >= c}, for some c > 0. The set of all high-density clusters form a hierarchy called the cluster tree of f. We present a procedure for estimating the cluster tree given samples from f. We give finite-sample convergence rates for our algorithm, as well as lower bounds on the sample complexity of this estimation problem.

🧭 Keyword Pioneer — cluster tree
🐣 Hot Topic Early Bird — unsupervised learning
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Security & Privacy, Speech & Audio

Authors

Kamalika Chaudhuri , Sanjoy Dasgupta

Topics

Machine Learning > Core Methods > Clustering Machine Learning > Learning Types > Unsupervised Learning Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Statistical Learning Machine Learning > Optimization & Theory > Statistics

Keywords

statistical learning unsupervised learning density estimation sample complexity hierarchical clustering cluster tree convergence rate
Download PDF

Related papers

Link Discovery using Graph Feature Tracking 2010
Trading off Mistakes and Don't-Know Predictions 2010
A Novel Kernel for Learning a Neuron Model from Spike Train Data 2010
Decomposing Isotonic Regression for Efficiently Solving Large Problems 2010
Learning Kernels with Radiuses of Minimum Enclosing Balls 2010