Pruning nearest neighbor cluster trees

Abstract

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. This is the first such finite sample result in the context of clustering.

References in corpus (1)

• Optimal construction of k-nearest neighbor graphs for identifying noisy clusters

Cited by in corpus (14)

• Fully adaptive density-based clustering
• Quickshift++: Provably Good Initializations for Sample-Based Mean Shift
• Demystifying Fixed k-Nearest Neighbor Information Estimators
• Density Level Set Estimation on Manifolds with DBSCAN
• DeBaCl: A Python Package for Interactive DEnsity-BAsed CLustering
• Modal-set estimation with an application to clustering
• Mapping Topographic Structure in White Matter Pathways with Level Set Trees
• Finite-Sample Analysis of Fixed-k Nearest Neighbor Density Functional Estimators
• Generalized Cluster Trees and Singular Measures
• A Comprehensive Approach to Mode Clustering
• DBSCAN: Optimal Rates For Density Based Clustering
• Unsupervised Embedding of Hierarchical Structure in Euclidean Space
• Adaptive Clustering Using Kernel Density Estimators
• Density-based Clustering with Best-scored Random Forest