Ultrametric Cluster Hierarchies: I Want 'em All!
This work provides a method for exploratory data analysis by extending hierarchical clustering capabilities, though it appears incremental as it builds on existing cluster tree concepts.
The paper tackles the problem of efficiently generating multiple hierarchical clusterings from a given cluster tree, proving that optimal solutions for center-based objectives like k-means can be found quickly and remain hierarchical, enabling access to diverse meaningful hierarchies for partition selection.
Hierarchical clustering is a powerful tool for exploratory data analysis, organizing data into a tree of clusterings from which a partition can be chosen. This paper generalizes these ideas by proving that, for any reasonable hierarchy, one can optimally solve any center-based clustering objective over it (such as $k$-means). Moreover, these solutions can be found exceedingly quickly and are themselves necessarily hierarchical. Thus, given a cluster tree, we show that one can quickly access a plethora of new, equally meaningful hierarchies. Just as in standard hierarchical clustering, one can then choose any desired partition from these new hierarchies. We conclude by verifying the utility of our proposed techniques across datasets, hierarchies, and partitioning schemes.