Summary
This research introduces Hierarchical-Revenue, a novel global objective function for hierarchical clustering (HC) specifically designed for Euclidean space. The authors provide the first theoretical justification for the widely used "bisecting $k$-means" algorithm, proving it acts as a constant-factor approximation for this global objective.
Introduction: The Gap in Hierarchical Clustering Theory
Hierarchical clustering is a fundamental tool in data science, traditionally implemented via "greedy" heuristics—either merging points (agglomerative) or splitting clusters (divisive). While Sanjoy Dasgupta proposed a breakthrough global cost function in 2016, it struggled in metric spaces because most trees appeared as decent approximations, failing to distinguish high-quality structures from mediocre ones. Furthermore, although the "bisecting $k$-means" algorithm is a practitioner's favorite, it lacked a formal global objective it was intended to optimize. This paper bridges that gap by introducing a metric that rewards the specific divisive behavior of $k$-means.
The Hierarchical-Revenue Objective
The proposed Hierarchical-Revenue objective is built on a "Guiding Principle": a split is effective if the distances between points in different clusters (inter-cluster) are significantly larger than the distances of points to their own cluster centers (intra-cluster).
Key Components:
- Revenue for a Pair: When two points $i$ and $j$ are separated into different clusters, "revenue" is earned. This value is maximized when the points are much closer to their respective centroids than to each other.
- Global Optimization: The total revenue of a tree is the sum of revenues from every pair of points at the moment of their first separation.
- Theoretical Foundation: Using geometric analysis, the authors demonstrate that an optimal 2-means split captures a significant fraction of potential revenue. This allows them to prove that recursive bisecting $k$-means achieves a constant-factor approximation of the optimal tree.
Experimental Evaluation
The authors tested their objective using two real-world datasets from the UCI Machine Learning Repository: Census (socio-economic features) and Bank (marketing campaign data). They compared bisecting $k$-means against standard agglomerative methods and a random baseline.
Key Results:
- Empirical Near-Optimality: In tests on the Census and Bank datasets, bisecting $k$-means consistently achieved within approximately 1% of the theoretical maximum revenue, outperforming popular agglomerative methods like average-linkage.
- The "Random" Litmus Test: Unlike previous objectives where random splitting could yield a constant-factor approximation, the Hierarchical-Revenue objective penalizes poor clustering, with the Random algorithm achieving only an $O(1/n)$ approximation.
- Ground-Truth Alignment: The objective correctly identifies the "generating tree" as optimal for ultrametric datasets, where a perfect hierarchy exists.
Discussion and Future Work
This work provides the "missing link" for bisecting $k$-means, showing it is a provably robust method for optimizing global tree structures rather than just a local heuristic.
However, several avenues for future research remain. While the approximation is "constant," the exact optimal constant remains to be calculated. Additionally, since finding an optimal 2-means split is NP-hard, the study relies on heuristics like Lloyd’s algorithm. Future work could explore whether specialized variations of $k$-means might optimize the Hierarchical-Revenue objective even more effectively.
Summary updated