Agglomerative Bregman Clustering

Matus Telgarsky, Sanjoy Dasgupta

Agglomerative (bottom-up) hierarchical clustering is a staple of unsupervised learning. It typically starts with individual data points as single-item clusters and greedily merges them. While "Ward’s method" is a popular version for minimizing k-means cost, researchers often need to use other distance measures—specifically Bregman divergences, which are mathematically linked to exponential family distributions like Poisson, Gaussian, or Multinomial.

However, applying Bregman divergences to hierarchical clustering faces two major hurdles:

  1. Degeneracy at the Start: Most Bregman divergences (like KL-divergence) are undefined for single points. For example, you cannot compute a full-rank covariance matrix for a cluster containing only one or two points, making the "merge cost" infinite or meaningless at the very beginning of the algorithm.
  2. Mathematical Rigidity: Standard theory requires "minimal representations" and differentiable functions. Many real-world problems use "overcomplete" representations where the math becomes messy or non-differentiable.

This paper provides a robust theoretical framework for performing agglomerative clustering using any Bregman divergence, solving these fundamental issues.

Methodology: Extending Bregman Clustering

The authors extend the theory of Bregman clustering in three key ways to handle complex models like Gaussians and multinomials, even when starting from single-point clusters.

1. Generalized Bregman Divergence They redefine the divergence using directional derivatives instead of standard gradients. This mathematical adjustment allows the theory to work with convex functions that aren't perfectly smooth (non-differentiable) and handles redundant parameters gracefully, meaning you don't need to force your data into a "minimal" representation.

Geometric representation of Bregman divergence between points.

2. A Generalized "Ward" Rule The paper proves that for a broad class of functions, the cost of merging two clusters can be calculated simply by looking at their centers and sizes. This generalizes the classic Ward’s merge rule (which the authors show is just a special case using squared Euclidean distance for spherical Gaussians) to any Bregman divergence.

3. Geometric Smoothing To solve the "singleton problem" where initial clusters lack variance, they introduce a smoothing map. This essentially "nudges" the cluster statistics into the interior of their valid domain. For Gaussians, this looks like adding a tiny bit of variance (a "bandwidth") to every point, ensuring that even a single point has a valid, non-degenerate covariance matrix. Without this smoothing, bottom-up clustering with complex models like full-covariance Gaussians is mathematically impossible.

Key Results and Performance

The authors evaluated their generalized agglomerative algorithm on both Euclidean data (UCI Glass, MNIST digits, Spambase) and Text data (20 Newsgroups subsets of varying difficulty).

  • Dendrogram Purity: On text data, the multinomial Bregman model (multi) achieved a purity score of 0.93 on an easy task, vastly outperforming standard single-link (0.50) and complete-link (0.60) linkages.
  • Gaussian Superiority: For MNIST digits (e.g., classifying 3s vs 5s), the full-covariance Gaussian model (g-n) outperformed the standard Ward/k-means approach, demonstrating that capturing cluster shape (covariance) matters significantly.
  • Feature Generation: The authors used the resulting cluster hierarchy to generate features for a supervised classifier. On text tasks, these "tree-based" features significantly outperformed features derived from Singular Value Decomposition (SVD), especially as the number of features increased.
Performance comparison of tree-based features generated by Bregman clustering versus SVD and standard linkages on MNIST and 20 Newsgroups datasets.

Limitations and Future Work

While theoretically robust, the approach comes with practical trade-offs:

  • Computational Complexity: While the merge rule is simplified, some divergences remain expensive. For full-covariance Gaussians, the algorithm requires inverting matrices, leading to an $O(n^3)$ cost per merge in terms of the dimension $n$.
  • Scalability: Like most agglomerative methods, the core algorithm scales at $O(m^2 \log m)$ or $O(m^3)$ relative to the number of data points $m$. This may be prohibitive for massive datasets without further optimization.
  • Smoothing Parameters: The choice of the smoothing parameter ($\alpha$) and the "nudge" point ($z$) are somewhat heuristic. While the authors suggest data-dependent schemes, more formal methods for choosing these hyperparameters could be explored in future work.

Summary updated

Abstract

This manuscript develops the theory of agglomerative clustering with Bregman divergences. Geometric smoothing techniques are developed to deal with degenerate clusters. To allow for cluster models based on exponential families with overcomplete representations, Bregman divergences are developed for nondifferentiable convex functions.
BibTeX
@inproceedings{telgarsky2012agglomerative,
  author = {Matus Telgarsky and Sanjoy Dasgupta},
  title = {{Agglomerative Bregman Clustering}},
  booktitle = {International Conference on Machine Learning},
  year = {2012},
  url = {https://openreview.net/forum?id=B1bRboZdWr},
}
Figure