Formalizing Hierarchical Clustering as Integer Linear Programming

Sean Gilpin, Siegfried Nijssen, Ian N. DavidsonAAAI 2013 · DOI

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:

  1. Reflexivity: A point is always clustered with itself at the base level.
  2. Symmetry: The merge level of $a$ and $b$ is identical to that of $b$ and $a$.
  3. 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.
  4. 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.

Figure 1: F1 Score vs. Noise for various clustering algorithms. The ILP approach (blue) maintains higher accuracy as noise increases compared to greedy methods.

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.

Figure 4: H-Correlation results for the Languages dataset, showing ILP's superior performance over traditional algorithms.

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

BibTeX
@inproceedings{gilpin2013formalizing,
  author = {Sean Gilpin and Siegfried Nijssen and Ian N. Davidson},
  title = {{Formalizing Hierarchical Clustering as Integer Linear Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8671},
}
Figure