Skip to main content

Consistent procedures for cluster tree estimation and pruning

Author(s): Chaudhuri, Kamalika; Dasgupta, Sanjoy; Kpotufe, Samory; Luxburg, Ulrike von

To refer to this page use:
Abstract: For a density f on R d , a high-density cluster is any connected component of {x : f (x) ≥ λ}, for some λ > 0. The set of all high-density clusters forms a hierarchy called the 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.
Publication Date: Dec-2014
Citation: Chaudhuri, Kamalika, Sanjoy Dasgupta, Samory Kpotufe, and Ulrike Von Luxburg. "Consistent procedures for cluster tree estimation and pruning." IEEE Transactions on Information Theory 60, no. 12 (2014): 7900-7912. doi:10.1109/TIT.2014.2361055
DOI: 10.1109/TIT.2014.2361055
ISSN: 0018-9448
Pages: 7900 - 7912
Type of Material: Journal Article
Journal/Proceeding Title: IEEE Transactions on Information Theory
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.