An Objective for Hierarchical Clustering in Euclidean Space and Its Connection to Bisecting K-means

Yuyan Wang, Benjamin Moseley

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).

Conceptual diagram of intra-cluster and inter-cluster pairs used to calculate revenue.

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.

Empirical results comparing bisecting k-means against other algorithms and the theoretical upper bound.

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

Abstract

This paper explores hierarchical clustering in the case where pairs of points have dissimilarity scores (e.g. distances) as a part of the input. The recently introduced objective for points with dissimilarity scores results in every tree being a 1/2 approximation if the distances form a metric. This shows the objective does not make a significant distinction between a good and poor hierarchical clustering in metric spaces. Motivated by this, the paper develops a new global objective for hierarchical clustering in Euclidean space. The objective captures the criterion that has motivated the use of divisive clustering algorithms: that when a split happens, points in the same cluster should be more similar than points in different clusters. Moreover, this objective gives reasonable results on ground-truth inputs for hierarchical clustering. The paper builds a theoretical connection between this objective and the bisecting k-means algorithm. This paper proves that the optimal 2-means solution results in a constant approximation for the objective. This is the first paper to show the bisecting k-means algorithm optimizes a natural global objective over the entire tree.
BibTeX
@inproceedings{wang2020objective,
  author = {Yuyan Wang and Benjamin Moseley},
  title = {{An Objective for Hierarchical Clustering in Euclidean Space and Its Connection to Bisecting K-means}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.6099},
}
Figure