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

In domains such as healthcare and marketing, clustering serves as a critical exploratory tool for identifying distinct subgroups, such as patient phenotypes or consumer segments. While traditional algorithms like $k$-means or Gaussian Mixture Models (GMMs) are effective at grouping data, they operate as "black boxes," offering no inherent explanation for cluster assignments.

Existing interpretable methods typically rely on decision trees. However, these are constrained to axis-parallel splits, which struggle to capture clusters defined by diagonal relationships or complex feature interactions. There remains a significant gap between the flexibility of unconstrained clustering and the interpretability of rigid, rule-based models.

The Multi-Polytope Machine (MPC) Framework

To bridge this gap, we introduce Multi-Polytope Machines (MPC). This framework defines each cluster as a polytope—the intersection of several half-spaces. This geometric approach allows for a more expressive representation of clusters while maintaining human-readability.

Mathematical Formulation

We frame the clustering problem as a Mixed-Integer Non-Linear Program (MINLP). The objective is to maximize the Silhouette Coefficient, which measures cluster cohesion and separation, while simultaneously minimizing the representation error of the polytopes.

Balancing Interpretability and Flexibility

A key advantage of MPC is the ability to constrain the hyperplanes that form the polytopes:

  • Axis-Parallel Boundaries: Similar to decision trees, these use only one feature per split.
  • Sparse Integer Hyperplanes: These allow for "scorecard" style rules (e.g., $2 \times \text{Feature A} + 1 \times \text{Feature B} \le \text{Threshold}$), which are common in clinical settings and offer significantly more flexibility than axis-parallel splits.
Visualizing the progression from rigid axis-parallel boundaries to flexible, sparse integer polytopes.

Optimization Strategy

Solving the MINLP directly is computationally prohibitive. We employ a two-phase heuristic:

  1. Initialization: An alternating minimization procedure (akin to $k$-means) establishes initial clusters and boundaries.
  2. Refinement: A coordinate descent phase utilizes local search operations—Boundary Shift, Cluster Splitting, and Cluster Merging—to optimize the Silhouette score and automatically determine the optimal number of clusters ($K$).

Experimental Evaluation

We evaluated MPC against state-of-the-art interpretable (ICOT, ExKMC) and non-interpretable (GMM, DBSCAN, $k$-means++) baselines across two benchmark suites: the Fundamental Clustering and Projection Suite (FCPS) and real-world datasets from the UCI repository.

Results on Synthetic Data (FCPS)

On the FCPS suite, which includes datasets with varying shapes and densities, the MPC-2 variant (utilizing sparse integer hyperplanes) achieved the highest Silhouette scores across all nine benchmarks.

Comparison of Silhouette scores on the FCPS synthetic datasets. MPC-2 consistently outperforms both interpretable and non-interpretable baselines.

Real-World Performance

In tests on UCI datasets (e.g., Iris, Wine, Spam), MPC matched or exceeded the performance of the best-performing algorithms in 7 out of 8 cases. The results demonstrate that moving from simple axis-parallel boundaries (MPC-1) to sparse integer boundaries (MPC-2) provides a significant performance boost on complex data without sacrificing auditability.

Conclusion

Multi-Polytope Machines offer a powerful new paradigm for interpretable clustering. By jointly optimizing for cluster quality and geometric simplicity, MPC provides "cages" of explanation that are more flexible than decision trees yet far more transparent than traditional black-box models. Future work will focus on scaling the MINLP formulation to high-dimensional datasets and exploring alternative clustering metrics.

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