A cost function for similarity-based hierarchical clustering
This addresses a fundamental bottleneck in hierarchical clustering algorithms for researchers and practitioners, though it appears incremental as it builds on existing similarity-based approaches.
The authors tackled the problem of hierarchical clustering lacking precise objective functions by introducing a simple cost function based on pairwise similarities, showing it behaves well in canonical instances and admits a top-down procedure with a provably good approximation ratio.
The development of algorithms for hierarchical clustering has been hampered by a shortage of precise objective functions. To help address this situation, we introduce a simple cost function on hierarchies over a set of points, given pairwise similarities between those points. We show that this criterion behaves sensibly in canonical instances and that it admits a top-down construction procedure with a provably good approximation ratio.