# Interpretable clustering via optimal multi-way decision trees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 27 references that are in the map.
- First posted on arXiv 14 Feb 2026.

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

- [European Union regulations on algorithmic decision-making and a "right to explanation"](https://mlsanity.com/paper/1606.08813/) (2016)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [Scalable Optimal Multiway-Split Decision Trees with Constraints](https://mlsanity.com/paper/2302.06812/) (2023)
- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)

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

- [Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments](https://mlsanity.com/paper/2609.23308/) (2026)

## Abstract (arXiv)

Clustering is a fundamental unsupervised learning technique for uncovering data structures to facilitate knowledge discovery and decision-making. While clustering accuracy is crucial, interpretability significantly impacts the practical value of clustering results, particularly in high-risk decision-making contexts. Although decision-tree-based clustering methods offer high interpretability through explicit splitting rules, existing approaches often rely on local greedy search or require expensive computational costs limited to binary splits, resulting in deeper, less interpretable trees. To overcome these limitations, we establish a high-performance computational framework named Interpretable Clustering via Optimal Multi-way Trees (ICOMT). We make three primary contributions. First, we propose a new discretization method for numerical features using one-dimensional K-means clustering to capture data distributions. Second, we formulate a binary linear optimization (BLO) problem to guarantee tree optimality. Third, extensive validation on four public datasets demonstrates that our ICOMT method outperforms existing baselines, achieving superior clustering accuracy while maintaining shallow, concise tree structures.