Skip to main content

Consistent procedures for cluster tree estimation and pruning

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

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1jg3s
Full metadata record
DC FieldValueLanguage
dc.contributor.authorChaudhuri, Kamalika-
dc.contributor.authorDasgupta, Sanjoy-
dc.contributor.authorKpotufe, Samory-
dc.contributor.authorLuxburg, Ulrike von-
dc.date.accessioned2021-10-11T14:17:11Z-
dc.date.available2021-10-11T14:17:11Z-
dc.date.issued2014-12en_US
dc.identifier.citationChaudhuri, 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.2361055en_US
dc.identifier.issn0018-9448-
dc.identifier.issn1557-9654-
dc.identifier.urihttp://www.columbia.edu/~skk2175/allpapers.html-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1jg3s-
dc.description.abstractFor 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.en_US
dc.format.extent7900 - 7912en_US
dc.language.isoen_USen_US
dc.relation.ispartofIEEE Transactions on Information Theoryen_US
dc.rightsAuthor's manuscripten_US
dc.titleConsistent procedures for cluster tree estimation and pruningen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1109/TIT.2014.2361055-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
ClusterTreeEstimationPruning.pdf185.66 kBAdobe PDFView/Download


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