Analysis of Ward's method

DOI10.1137/1.9781611975482.182MaRDI QIDQ5236375zbMATH OpenOpenAlexFDO

Authors Anna Großwendt, Heiko Röglin, Melanie Schmidt

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: We study Ward's method for the hierarchical $k$-means problem. This popular greedy heuristic is based on the emph{complete linkage} paradigm: Starting with all data points as singleton clusters, it successively merges two clusters to form a clustering with one cluster less. The pair of clusters is chosen to (locally) minimize the $k$-means cost of the clustering in the next step. Complete linkage algorithms are very popular for hierarchical clustering problems, yet their theoretical properties have been studied relatively little. For the Euclidean $k$-center problem, Ackermann et al. show that the $k$-clustering in the hierarchy computed by complete linkage has a worst-case approximation ratio of $Theta(logk)$. If the data lies in $mathbb{R}^d$ for constant dimension $d$, the guarantee improves to $mathcalO(1)$, but the $mathcalO$-notation hides a linear dependence on $d$. Complete linkage for $k$-median or $k$-means has not been analyzed so far. In this paper, we show that Ward's method computes a $2$-approximation with respect to the $k$-means objective function if the optimal $k$-clustering is well separated. If additionally the optimal clustering also satisfies a balance condition, then Ward's method fully recovers the optimum solution. These results hold in arbitrary dimension. We accompany our positive results with a lower bound of $Omega((3/2{)}^d)$ for data sets in $mathbb{R}^d$ that holds if no separation is guaranteed, and with lower bounds when the guaranteed separation is not sufficiently strong. Finally, we show that Ward produces an $mathcalO(1)$-approximative clustering for one-dimensional data sets.

Recommendations

• Improved analysis of complete-linkage clustering
• Minkowski generalizations of Ward's method in hierarchical clustering
• Improved analysis of complete-linkage clustering
• Ward's hierarchical agglomerative clustering method: which algorithms implement Ward's criterion?
• Analysis of agglomerative clustering

Cited in

(8)

• Feature relevance in Ward's hierarchical clustering using the L_p norm
• Ward's hierarchical agglomerative clustering method: which algorithms implement Ward's criterion?
• Minkowski generalizations of Ward's method in hierarchical clustering
• scientific article; zbMATH DE number 4157773 (Why is no real title available?)
• Analysis of the drop weight method
• scientific article; zbMATH DE number 123291 (Why is no real title available?)
• The price of hierarchical clustering
• The price of hierarchical clustering

This page was built for publication: Analysis of Ward's method

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