# Interpretable Clustering via Optimal Trees

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2018.

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

- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (2021)
- [Shallow decision trees for explainable k-means clustering](https://mlsanity.com/paper/2112.14718/) (2021)
- [Near-Optimal Explainable k-Means for All Dimensions](https://mlsanity.com/paper/2106.15566/) (2021)
- [Near-optimal Algorithms for Explainable k-Medians and k-Means](https://mlsanity.com/paper/2107.00798/) (2021)
- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)
- [Algorithm-Agnostic Explainability for Unsupervised Clustering](https://mlsanity.com/paper/2105.08053/) (2021)
- [Explaining Kernel Clustering via Decision Trees](https://mlsanity.com/paper/2402.09881/) (2024)
- [Optimal Recourse Summaries via Bi-Objective Decision Tree Learning](https://mlsanity.com/paper/2605.07598/) (2026)
- [Algorithm-Agnostic Interpretations for Clustering](https://mlsanity.com/paper/2209.10578/) (2022)
- [Forecasting Auxiliary Energy Consumption for Electric Heavy-Duty Vehicles](https://mlsanity.com/paper/2311.16003/) (2023)

## Abstract (arXiv)

State-of-the-art clustering algorithms use heuristics to partition the feature space and provide little insight into the rationale for cluster membership, limiting their interpretability. In healthcare applications, the latter poses a barrier to the adoption of these methods since medical researchers are required to provide detailed explanations of their decisions in order to gain patient trust and limit liability. We present a new unsupervised learning algorithm that leverages Mixed Integer Optimization techniques to generate interpretable tree-based clustering models. Utilizing the flexible framework of Optimal Trees, our method approximates the globally optimal solution leading to high quality partitions of the feature space. Our algorithm, can incorporate various internal validation metrics, naturally determines the optimal number of clusters, and is able to account for mixed numeric and categorical data. It achieves comparable or superior performance on both synthetic and real world datasets when compared to K-Means while offering significantly higher interpretability.