Hierarchical clustering is a foundational technique in data science, typically implemented through greedy heuristics like AGNES or UPGMA. While efficient, these methods suffer from a significant drawback: early merge errors propagate throughout the tree and cannot be undone. This paper, presented at AAAI 2013, proposes a shift from local heuristics to global optimization by framing hierarchical clustering as an Integer Linear Program (ILP).
The Problem with Greedy Merging
Traditional algorithms start with individual data points and iteratively merge the closest clusters. However, in datasets where the hierarchy represents a physical or historical truth—such as linguistic evolution or brain scan organization—a single noisy data point can lead to a cascade of structural errors. The authors seek the globally optimal tree that best fits the distance data, rather than the one produced by a sequence of local decisions.
Methodology: Clustering as Optimization
The core innovation lies in translating the properties of a dendrogram into a set of linear constraints within an ILP framework.
Linear Constraints
To ensure a valid hierarchical structure, the authors define a merge variable $M(a, b)$ representing the level at which instances $a$ and $b$ first appear in the same cluster. They enforce four key properties:
- Reflexivity: A point is always clustered with itself at the base level.
- Symmetry: The merge level of $a$ and $b$ is identical to that of $b$ and $a$.
- Transitivity: If $a$ and $b$ are in a cluster, and $b$ and $c$ are in the same cluster, then $a$ and $c$ must also be together.
- Hierarchical Property: Merged clusters remain merged at all subsequent higher levels.
Relaxation and Approximation
Because ILP is NP-hard, the authors utilize Linear Programming (LP) relaxation and randomized rounding. This allows for near-optimal solutions at a fraction of the computational cost, providing a factor-two approximation of the true ILP optimum. Empirical tests showed the LP relaxation results were consistently very close to the true ILP optimum.
Experimental Results
The ILP approach was evaluated against standard greedy methods across artificial and real-world datasets.
Robustness to Noise
In artificial datasets, the ILP formulation demonstrated significant resilience to random noise. While greedy algorithms are easily distracted by outliers, the global objective requires the entire tree structure to remain consistent, effectively filtering out local noise.
Superior Accuracy in Ground-Truth Data
On the Languages dataset—where the evolutionary tree is well-established by linguists—the ILP achieved the highest H-Correlation, outperforming Single Linkage and UPGMA.
Similar results were observed in fMRI data, where the ILP produced the most accurate organization of patient cognitive statuses with an H-correlation of 0.3305.
Overlapping Hierarchies
A unique advantage of this mathematical formulation is its flexibility. By relaxing the "transitivity" constraint into a penalty within the objective function, the authors enabled "overlapping" hierarchies. This allows objects to belong to multiple branches simultaneously—a feature tested on MovieLens data, where movies often span multiple genres (e.g., a "Romantic Comedy" belongs to both Romance and Comedy branches). The overlapping LP formulation achieved an F1 score of 0.595, significantly higher than standard rigid hierarchies.
Conclusion
By formalizing hierarchical clustering as a global optimization problem, the authors provide a robust alternative to greedy heuristics for "high-value" small datasets. While the method is computationally more intensive, its ability to handle noise and support overlapping structures makes it a powerful tool for scientific discovery. Future work may involve incorporating domain-specific knowledge as additional linear constraints to further refine the resulting hierarchies.
Summary updated