Abstract
Bayesian hierarchical clustering (BHC) is an agglomerative clustering method, where a probabilistic model is defined and its marginal likelihoods are evaluated to decide which clusters to merge. While BHC provides a few advantages over traditional distance-based agglomerative clustering algorithms, successive evaluation of marginal likelihoods and careful hyperparameter tuning are cumbersome and limit the scalability. In this paper we relax BHC into a non-probabilistic formulation, exploring small-variance asymptotics in conjugate-exponential models. We develop a novel clustering algorithm, referred to as relaxed BHC (RBHC), from the asymptotic limit of the BHC model that exhibits the scalability of distance-based agglomerative clustering algorithms as well as the flexibility of Bayesian nonparametric models. We also investigate the reducibility of the dissimilarity measure emerged from the asymptotic limit of the BHC model, allowing us to use scalable algorithms such as the nearest neighbor chain algorithm. Numerical experiments on both synthetic and real-world datasets demonstrate the validity and high performance of our method.
Introduction
Hierarchical clustering is a fundamental tool in data analysis, yet practitioners often face a trade-off between efficiency and statistical rigor. Traditional distance-based methods like Ward’s linkage are computationally efficient but lack a principled way to determine the number of clusters. Conversely, Bayesian Hierarchical Clustering (BHC) provides a probabilistic framework for model selection but suffers from high computational complexity ($O(n^2 \log n)$ time and $O(n^2)$ space) and extreme sensitivity to hyperparameter settings. This paper introduces Relaxed Bayesian Hierarchical Clustering (RBHC), which bridges this gap by applying small-variance asymptotics to the BHC framework.
Methods: Small-Variance Asymptotics and Reducibility
The core of RBHC lies in the application of small-variance asymptotics to conjugate-exponential models. By taking the limit as the variance of the underlying distributions approaches zero, the complex marginal likelihood calculations of BHC simplify into a dissimilarity measure $d_*$ based on Bregman divergences. This measure generalizes squared Euclidean distance and KL divergence, providing a non-probabilistic yet mathematically grounded clustering criterion.
A critical property for efficient hierarchical clustering is reducibility. A dissimilarity measure is reducible if merging two clusters does not make a third cluster appear closer than the original pair. While $d_*$ is not strictly reducible for all distributions, the authors demonstrate that it is asymptotically reducible as clusters grow or variance decreases. As shown in the table below, the number of non-reducible cases in practice is negligible across various distributions.
This practical reducibility allows the use of the Nearest Neighbor Chain algorithm, reducing the time complexity to $O(n^2)$ and space complexity to $O(n)$. Furthermore, RBHC retains a natural stopping criterion $\lambda$ (derived from the BHC prior), allowing it to automatically determine the number of clusters and output a "forest" of trees rather than forcing a single root.
Experimental Evaluation
The authors evaluated RBHC on synthetic datasets (Poisson, Multinomial, Gaussian) and real-world data (MNIST, Caltech101). In synthetic tests, RBHC consistently matched or exceeded the performance of the original BHC and traditional methods like Ward’s method. Notably, when assuming a Gaussian distribution, RBHC effectively becomes Ward’s method but with a built-in way to decide the number of clusters.
On the MNIST dataset, RBHC achieved an Adjusted Rand Index (ARI) of 0.637, significantly outperforming the original BHC (0.253) and Ward’s method (0.485). The method also proved robust to hyperparameter settings; while BHC requires careful prior tuning, RBHC’s threshold $\lambda$ can be effectively set using a simple $k$-means-based heuristic.
Conclusion
RBHC offers a scalable and flexible alternative to traditional hierarchical clustering. By leveraging small-variance asymptotics, it maintains the advantages of Bayesian nonparametric models—such as automatic cluster discovery—while achieving the efficiency of distance-based algorithms. While the algorithm depends on the threshold $\lambda$, it is significantly less sensitive than the original BHC priors. Future work may focus on further automating the selection of $\lambda$ and exploring edge cases where strict reducibility is not maintained.
Summary updated