Interpretable Clustering via Multi-Polytope Machines

Authors

  • Connor Lawless Cornell University
  • Jayant Kalagnanam IBM Research, Thomas J. Watson Research Center
  • Lam M Nguyen IBM Research, Thomas J. Watson Research Center
  • Dzung Phan IBM Research, Thomas J. Watson Research Center
  • Chandra Reddy IBM Research, Thomas J. Watson Research Center

DOI:

https://doi.org/10.1609/aaai.v36i7.20693

Keywords:

Machine Learning (ML)

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.

Downloads

Published

2022-06-28

How to Cite

Lawless, C., Kalagnanam, J., Nguyen, L. M., Phan, D., & Reddy, C. (2022). Interpretable Clustering via Multi-Polytope Machines. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7), 7309-7316. https://doi.org/10.1609/aaai.v36i7.20693

Issue

Section

AAAI Technical Track on Machine Learning II