# Interpretable Clustering via Multi-Polytope Machines

arXiv: https://arxiv.org/abs/2112.05653 · HTML: https://mlsanity.com/paper/2112.05653/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 36 references that are in the map.
- First posted on arXiv 10 Dec 2021.

## Builds on (most cited first, 8 of 8)

- [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [From Clustering to Cluster Explanations via Neural Networks](https://mlsanity.com/paper/1906.07633/) (2019)
- [ExKMC: Expanding Explainable k-Means Clustering](https://mlsanity.com/paper/2006.02399/) (2020)
- [Learning Optimized Or's of And's](https://mlsanity.com/paper/1511.02210/) (2015)
- [Supersparse Linear Integer Models for Interpretable Classification](https://mlsanity.com/paper/1306.6677/) (2013)
- [Fair Decision Rules for Binary Classification](https://mlsanity.com/paper/2107.01325/) (2021)

## Built on by (most cited first, 11 of 11)

- [Interpretable Deep Clustering for Tabular Data](https://mlsanity.com/paper/2306.04785/) (2023)
- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)
- [Cluster Explanation via Polyhedral Descriptions](https://mlsanity.com/paper/2210.08798/) (2022)
- [NeurCAM: Interpretable Neural Clustering via Additive Models](https://mlsanity.com/paper/2408.13361/) (2024)
- [Towards Explainable Clustering: A Constrained Declarative based Approach](https://mlsanity.com/paper/2403.18101/) (2024)
- [Interpretable Multi-View Clustering](https://mlsanity.com/paper/2405.02644/) (2024)
- [Interpretable Sequence Clustering](https://mlsanity.com/paper/2309.01140/) (2023)
- [Using Constraints to Discover Sparse and Alternative Subgroup Descriptions](https://mlsanity.com/paper/2406.01411/) (2024)
- [Understanding Fixed Predictions via Confined Regions](https://mlsanity.com/paper/2502.16380/) (2025)
- [Algorithm-Agnostic Interpretations for Clustering](https://mlsanity.com/paper/2209.10578/) (2022)
- [Weight-Informed Self-Explaining Clustering for Mixed-Type Tabular Data](https://mlsanity.com/paper/2604.05857/) (2026)

## Abstract (arXiv)

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.