Consistent Procedures for Cluster Tree Estimation and Pruning

DOI10.1109/TIT.2014.2361055MaRDI QIDQ2979179zbMATH OpenOpenAlexFDO

Authors Kamalika Chaudhuri, Sanjoy Dasgupta, Samory Kpotufe, Ulrike Von Luxburg

Publication date 2 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.1546

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Information theory (general) (94A15)

Abstract: For a density $f$ on ${mathbbR}^d$, a {it high-density cluster} is any connected component of $x:f(x)geqlambda$, for some $lambda>0$. The set of all high-density clusters forms a hierarchy called the {it cluster tree} of $f$. We present two procedures for estimating the cluster tree given samples from $f$. The first is a robust variant of the single linkage algorithm for hierarchical clustering. The second is based on the $k$-nearest neighbor graph of the samples. We give finite-sample convergence rates for these algorithms which also imply consistency, and we derive lower bounds on the sample complexity of cluster tree estimation. Finally, we study a tree pruning procedure that guarantees, under milder conditions than usual, to remove clusters that are spurious while recovering those that are salient.

Cited in

(12)

• Multiscale inference for a multivariate density with applications to X-ray astronomy
• Nonlocal-interaction equation on graphs: gradient flow structure and continuum limit
• Automatic topography of high-dimensional data sets by non-parametric density peak clustering
• Generalized cluster trees and singular measures
• Consistency of the \(k\)-nearest neighbors rule for functional data
• Barycenters for the Hellinger-Kantorovich distance over \(\mathbb{R}^d\)
• DBSCAN: optimal rates for density-based cluster estimation
• Hellinger–Kantorovich barycenter between Dirac measures
• Moving Up the Cluster Tree with the Gradient Flow
• QuickDSC: clustering by quick density subgraph estimation
• Skeleton Clustering: Dimension-Free Density-Aided Clustering
• An axiomatic definition of hierarchical clustering

This page was built for publication: Consistent Procedures for Cluster Tree Estimation and Pruning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2979179)