2015/11/24 by Dekang Zhu, Dan P. Guralnik, Zhu, Dekang +7 · 2 citations
Computer Science · Mathematics · #Advanced Clustering Algorithms Research #Bayesian Methods and Mixture Models #Data Management and Algorithms #FOS: Computer and information sciences #Machine Learning (stat.ML) #stat.ML
paper · pdf · doi:10.48550/arxiv.1511.07715
21 pages, 6 figures
openalex publication_date 2015/11/24 · arxiv created 2016/09/01 · arxiv updated 2016/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.