Fetching the paper…

Reading the bibliography…

2011

Pruning nearest neighbor cluster trees

Kpotufe, Samory, von Luxburg, Ulrike

Original
PDF
Post on X

Understand

Nearest neighbor (k-NN) graphs are widely used in machine learning and data mining applications, and our aim is to better understand what they reveal about the cluster structure of the unknown underlying distribution of points.

Moreover, is it possible to identify spurious structures that might arise due to sampling variability? Our first contribution is a statistical analysis that reveals how certain subgraphs of a k-NN graph form a consistent estimator of the cluster tree of the underlying distribution of points.
Our second and perhaps most important contribution is the following finite sample guarantee.
We carefully work out the tradeoff between aggressive and conservative pruning and are able to guarantee the removal of all spurious cluster structures at all levels of the tree while at the same time guaranteeing the recovery of salient clusters.

Pruning nearest neighbor cluster trees · Around

Built on

Mode analysis: A generalization of nearest neighbor which reduces chaining effects
Wishart, D · 1969
Earlier work this paper cites.
The strong uniform consistency of nearest neighbor density estimates
Devroye, L.P. and Wagner, T.J · 1977
Earlier work this paper cites.
Fast probabilistic algorithms for Hamiltonian circuits and matchings
Angluin, D. and Valiant, L.G · 1979
Earlier work this paper cites.
Consistency of single linkage for high-density clusters
Hartigan, J.A · 1981
Earlier work this paper cites.
A kth nearest neighbor clustering procedure
Wong, M. and Lane, T · 1983
Earlier work this paper cites.

Similar

Introduction to statistical learning theory
Bousquet, O., Boucheron, S., and Lugosi, G · 2004
Cited alongside, same era.
Optimal construction of k-nearest neighbor graphs for identifying noisy clusters
Maier, M., Hein, M., and von Luxburg, U · 2009
Cited alongside, same era.
Fast rates for plug-in estimators of density level sets
Rigollet, P. and Vert, R · 2009
Cited alongside, same era.
Adaptive hausdorff estimation of density level sets
Singh, A., Scott, C., and Nowak, R · 2009
Cited alongside, same era.
Clustering with confidence: A binning approach
Stueltze, W. and Nugent, R · 2009
Cited alongside, same era.

Then

Rates of convergence for the cluster tree
Chaudhuri, K. and Dasgupta, S · 2010
Later among the works it cites.
Generalized density clustering
Rinaldo, A. and Wasserman, L · 2010
Later among the works it cites.
Stability of density based clustering
Original
Rinaldo, A., Singh, A., Nugent, R., and Wasserman, L · 2010
Later among the works it cites.
A generalized single linkage method for estimating the cluster tree of a density
Stueltze, W. and Nugent, R · 2010
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…