# Optimal Decision Trees For Interpretable Clustering with Constraints (Extended Version)

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 47 references that are in the map.
- First posted on arXiv 30 Jan 2023.

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

- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [ExKMC: Expanding Explainable k-Means Clustering](https://mlsanity.com/paper/2006.02399/) (2020)
- [Nearly-Tight and Oblivious Algorithms for Explainable Clustering](https://mlsanity.com/paper/2106.16147/) (2021)

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

- [NeurCAM: Interpretable Neural Clustering via Additive Models](https://mlsanity.com/paper/2408.13361/) (2024)
- [SpEx: A Spectral Approach to Explainable Clustering](https://mlsanity.com/paper/2511.00885/) (2025)
- [Cross-Modal Rationale Transfer for Explainable Humanitarian Classification on Social Media](https://mlsanity.com/paper/2603.18611/) (2026)

## Abstract (arXiv)

Constrained clustering is a semi-supervised task that employs a limited amount of labelled data, formulated as constraints, to incorporate domain-specific knowledge and to significantly improve clustering accuracy. Previous work has considered exact optimization formulations that can guarantee optimal clustering while satisfying all constraints, however these approaches lack interpretability. Recently, decision-trees have been used to produce inherently interpretable clustering solutions, however existing approaches do not support clustering constraints and do not provide strong theoretical guarantees on solution quality. In this work, we present a novel SAT-based framework for interpretable clustering that supports clustering constraints and that also provides strong theoretical guarantees on solution quality. We also present new insight into the trade-off between interpretability and satisfaction of such user-provided constraints. Our framework is the first approach for interpretable and constrained clustering. Experiments with a range of real-world and synthetic datasets demonstrate that our approach can produce high-quality and interpretable constrained clustering solutions.