Statistical Properties of the Single Linkage Hierarchical Clustering Estimator
Authors:
Preprint
Abstract
Distance-based hierarchical clustering (HC) methods are widely used in unsupervised data analysis but few authors take account of uncertainty in the distance data. We incorporate a statistical model of the uncertainty through corruption or noise in the pairwise distances and investigate the problem of estimating the HC as unknown parameters from measurements. Specifically, we focus on single linkage hierarchical clustering (SLHC) and study its geometry. We prove that under fairly reasonable conditions on the probability distribution governing measurements, SLHC is equivalent to maximum partial profile likelihood estimation (MPPLE) with some of the information contained in the data ignored. At the same time, we show that direct evaluation of SLHC on maximum likelihood estimation (MLE) of pairwise distances yields a consistent estimator. Consequently, a full MLE is expected to perform better than SLHC in getting the correct HC results for the ground truth metric.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Classifying Clustering SchemesFoundations of Computational Mathematics, 2013
- Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopesAdvances in Applied Mathematics, 2010
- Using hierarchical agglomerative clustering in wireless sensor networks: An energy-efficient and flexible approachAd Hoc Networks, 2010
- Efficient Mining of the Multidimensional Traffic Cluster Hierarchy for Digesting, Visualization, and Anomaly IdentificationIEEE Journal on Selected Areas in Communications, 2006
- Hierarchical Clustering, Languages and Cancer2006
- On the Skeleton of the Metric Polytope2001
- Macroscopic Diversity in Frequency Reuse Radio SystemsIEEE Journal on Selected Areas in Communications, 1987
- 800-MHz Attenuation Measured In and Around Suburban HousesAT&T Bell Laboratories Technical Journal, 1984
- Metrics on spaces of finite treesJournal of Mathematical Psychology, 1973
- Six theorems about injective metric spacesCommentarii Mathematici Helvetici, 1964