Interpretable Clustering via Multi-Polytope Machines
This addresses the need for interpretable clustering in applications like customer segmentation or patient subtyping, offering a novel approach but with incremental improvements in method design.
The paper tackles the problem of clustering algorithms lacking interpretability by proposing a method that clusters data points and constructs polytopes to explain the clusters, with results showing it outperforms state-of-the-art interpretable and non-interpretable clustering algorithms on synthetic and real-world benchmarks.
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.