Interpretable Clustering via Multi-Polytope Machines

Connor Lawless, Jayant Kalagnanam, Lam M. Nguyen, Dzung T. Phan, Chandra Reddy

Abstract

Clustering is a popular unsupervised learning tool often used to discover groups within a larger population such as customer segments, or patient subtypes. However, despite its use as a tool for subgroup discovery and description - few state-of-the-art algorithms provide any rationale or description behind the clusters found. We propose a novel approach for interpretable clustering that both clusters data points and constructs polytopes around the discovered clusters to explain them. Our framework allows for additional constraints on the polytopes - including ensuring that the hyperplanes constructing the polytope are axis-parallel or sparse with integer coefficients. We formulate the problem of constructing clusters via polytopes as a Mixed-Integer Non-Linear Program (MINLP). To solve our formulation we propose a two phase approach where we first initialize clusters and polytopes using alternating minimization, and then use coordinate descent to boost clustering performance. We benchmark our approach on a suite of synthetic and real world clustering problems, where our algorithm outperforms state of the art interpretable and non-interpretable clustering algorithms.

Introduction

Clustering is a cornerstone of unsupervised learning, used to find natural groupings like customer segments or disease subtypes. However, most popular algorithms (like $k$-means or GMMs) are "black boxes"—they tell you which points belong together but don't explain why.

Existing "interpretable" clustering methods usually rely on decision trees. While intuitive, decision trees are restricted to axis-parallel splits (e.g., "Age > 30"), which can be too rigid for complex data. Practitioners are often forced into a trade-off: use a flexible but uninterpretable model, or use a simple model that fails to capture the true structure of the data. This work bridges this gap by providing a framework that is both highly expressive and human-readable.

Methodology: Multi-Polytope Machines (MPC)

The Multi-Polytope Machines (MPC) framework defines each cluster as a polytope—the intersection of several half-spaces (hyperplanes). Instead of clustering first and explaining later (post-hoc), MPC formulates a Mixed-Integer Non-Linear Program (MINLP) that jointly optimizes for cluster quality (using the Silhouette coefficient) and "representation error" (how well the polytopes actually enclose the clusters).

The hyperplanes forming the polytopes can be constrained to match specific interpretability needs:

  • MPC-1: Restricts hyperplanes to be axis-parallel, mimicking the logic of decision trees.
  • MPC-2: Allows sparse hyperplanes with small integer coefficients, creating "scorecard" style explanations (e.g., $3 \times \text{FeatureA} + \text{FeatureB} > 5$).
Comparison of cluster boundaries: axis-parallel (left) vs. oblique/sparse (middle/right) polytopes.

To solve the MINLP, the authors propose a two-stage algorithm. First, an alternating minimization approach initializes clusters and polytopes. Second, a coordinate descent procedure performs local searches to shift boundaries, split clusters, or merge them to maximize the Silhouette score.

Experimental Results

The authors evaluated MPC on two main suites: the Fundamental Clustering and Projection Suite (FCPS) for synthetic challenges and classic UCI datasets for real-world robustness.

On synthetic data, MPC-2 achieved the highest Silhouette score across all 9 datasets, outperforming both uninterpretable methods (like $k$-means++ and GMM) and state-of-the-art interpretable methods (like ICOT and ExKMC).

Silhouette scores on synthetic (FCPS) datasets. MPC-2 consistently achieves the highest performance (starred values).

On UCI datasets, MPC matched or beat the best-performing benchmarks in 7 out of 8 cases. Interestingly, on higher-dimensional data, increasing the complexity of the explanation (moving from MPC-1 to MPC-2) didn't always improve cluster quality, suggesting that simple axis-parallel rules are often sufficient for real-world data, though MPC provides the safety net of extra expressiveness when needed.

Conclusion

MPC offers a more flexible and expressive alternative to decision-tree-based clustering. By generalizing boundaries to polytopes, it can fit complex data shapes that trees cannot, while maintaining interpretability through sparse, integer-coefficient hyperplanes. The framework also provides direct pairwise comparisons between clusters, making it easier for practitioners to understand why a specific point belongs to one group over another. While computationally more intensive than $k$-means, its performance and interpretability make it a powerful tool for subgroup discovery in sensitive domains.

Summary updated

Abstract

Clustering is a popular unsupervised learning tool often used to discover groups within a larger population such as customer segments, or patient subtypes. However, despite its use as a tool for subgroup discovery and description - few state-of-the-art algorithms provide any rationale or description behind the clusters found. We propose a novel approach for interpretable clustering that both clusters data points and constructs polytopes around the discovered clusters to explain them. Our framework allows for additional constraints on the polytopes - including ensuring that the hyperplanes constructing the polytope are axis-parallel or sparse with integer coefficients. We formulate the problem of constructing clusters via polytopes as a Mixed-Integer Non-Linear Program (MINLP). To solve our formulation we propose a two phase approach where we first initialize clusters and polytopes using alternating minimization, and then use coordinate descent to boost clustering performance. We benchmark our approach on a suite of synthetic and real world clustering problems, where our algorithm outperforms state of the art interpretable and non-interpretable clustering algorithms.
BibTeX
@inproceedings{lawless2022interpretable,
  author = {Connor Lawless and Jayant Kalagnanam and Lam M. Nguyen and Dzung T. Phan and Chandra Reddy},
  title = {{Interpretable Clustering via Multi-Polytope Machines}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=BdKp92k4VpU},
}
Figure