Statistical properties of the single linkage hierarchical clustering estimator

DOI10.1016/J.JSPI.2016.12.002zbMATH Open1360.62367arXiv1511.07715OpenAlexW2963569116MaRDI QIDQ514178FDOQ514178

Authors: Dekang Zhu, Dan P. Guralnik, Xuezhi Wang, Xiang Li, W. Moran 

Publication date: 28 February 2017

Published in: Journal of Statistical Planning and Inference (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1511.07715

Recommendations

• Statistical analysis of a hierarchical clustering algorithm with outliers
• Statistical theory in clustering
• On the properties of \(\alpha\)-unchaining single linkage hierarchical clustering
• Characterization, stability and convergence of hierarchical clustering methods
• Hierarchical clustering better than average-linkage

zbMATH Keywords

consistencymaximum likelihood estimationminimum spanning treedendrogramultra-metricexponential family distributions

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Cites Work

• Partial likelihood
• Title not available (Why is that?)
• Consistent Estimates Based on Partially Consistent Observations
• Title not available (Why is that?)
• Introduction to Information Retrieval
• Title not available (Why is that?)
• Integrated likelihood methods for eliminating nuisance parameters. (With comments and a rejoinder).
• Six theorems about injective metric spaces
• Energy minimization methods in computer vision and pattern recognition. 4th international workshop, EMMCVPR 2003, Lisbon, Portugal, July 7--9, 2003. Proceedings.
• Lectures on natural exponential families and their variance functions
• A time series illustration of approximate conditional likelihood
• Wireless sensor network localization techniques
• Title not available (Why is that?)
• A Laplace transform algorithm for the volume of a convex polytope
• Characterization, stability and convergence of hierarchical clustering methods
• Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
• Computing the volume, counting integral points, and exponential sums
• On the Extreme Rays of the Metric Cone
• Title not available (Why is that?)
• Likelihood Based Hierarchical Clustering
• Metrics on spaces of finite trees

Cited In (5)

• On the properties of \(\alpha\)-unchaining single linkage hierarchical clustering
• Shannon’s entropy of partitions determined by hierarchical clustering trees in asymmetry and dimension identification
• Approximate single linkage cluster analysis of large data sets in high-dimensional spaces
• Edge erasures and chordal graphs
• Functorial hierarchical clustering with overlaps

This page was built for publication: Statistical properties of the single linkage hierarchical clustering estimator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q514178)