Abstract
Standard agglomerative clustering follows a greedy "smallest-distance-first" approach, often neglecting sparse data regions until late in the process. This paper introduces Reliable Agglomerative Clustering, a meta-strategy that merges all mutual nearest-neighbor pairs simultaneously at each step. This approach creates a more balanced, density-aware hierarchy that is more robust to outliers and better suited for early stopping. Evaluation across diverse benchmarks shows consistent improvements over standard linkage methods across multiple metrics.
Introduction
Agglomerative (bottom-up) clustering typically works by finding the two most similar clusters in the entire dataset and merging them. While simple, this "smallest-distance-first" approach is highly sensitive to data density. In datasets containing both dense and sparse regions, standard algorithms often spend the initial stages merging points within dense "clouds" while ignoring sparse regions or outliers. This can result in a hierarchy where, if stopped early, one finds a few highly detailed clusters alongside a massive collection of unorganized individual points. The authors propose that a "reliable" linkage should be a two-way street—where both clusters agree that the other is their closest neighbor.
The Reliable Linkage Strategy
The core innovation of this work is the Reliable Linkage Strategy, which redefines how merges are prioritized and executed.
- Mutual Attraction Criterion: A link between cluster A and cluster B is considered "reliable" if and only if A is the nearest neighbor of B and B is the nearest neighbor of A.
- Simultaneous Merging: Instead of picking only the single pair with the absolute minimum distance, the algorithm identifies all reliable pairs at the current level and merges them simultaneously.
- Algorithmic Flexibility: This is a meta-strategy applicable to existing criteria such as Single Linkage, Complete Linkage, Average Linkage, and Ward’s Method.
By merging all reliable links at once, the dendrogram grows across the entire data space simultaneously, providing a more "global" view of the data at every level of resolution. This method naturally adapts to different densities; a point in a sparse region won't be forced into a dense cluster prematurely unless that dense cluster also "sees" it as its closest neighbor.
Experimental Evaluation
The authors evaluated the reliable strategy against standard approaches using three metrics: Mutual Information, Rand Score, and V-measure. The benchmarks included:
- UCI Machine Learning Repository: Classic datasets like Iris, Wine, Seeds, Ecoli, and Lung Cancer.
- 20-Newsgroups: Text document clustering subsets (COMP, REC, SCI).
- Corporate Scanned Documents: High-dimensional vectors (4,096 dimensions) from scanned documents (Real I, II, III).
Results and Discussion
The "Reliable" (rlbl) strategy consistently matched or outperformed the "Standard" (stnd) approach across almost all datasets and criteria.
Key findings include:
- Significant Gains in Average Linkage: The Average Linkage criterion saw substantial boosts, such as on the Seeds dataset where Mutual Information improved from 0.608 to 0.705.
- Improved Text Clustering: On the SCI newsgroup dataset using Ward’s method, the V-measure jumped from 0.2546 to 0.3407, as shown in the results table.
- Outlier Detection: The level at which a point finally joins a cluster serves as a strong indicator of its "outlier-ness." Points joining very late are statistically more likely to be noise.
- Efficiency in Early Stopping: Because the algorithm builds representatives for all parts of the data simultaneously, it is significantly more effective for researchers who stop the hierarchy at $K$ clusters to obtain a usable partition.
Conclusion
Reliable Agglomerative Clustering offers a robust alternative to standard greedy hierarchical methods. By enforcing mutual nearest-neighbor criteria and allowing for simultaneous merges, the method produces hierarchies that better reflect the global structure of the data. Future work may explore more sophisticated tie-breaking mechanisms and the formal parameterization of the "reliability" threshold.
Summary updated