# Towards Explainable Clustering: A Constrained Declarative based Approach

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 44 references that are in the map.
- First posted on arXiv 26 Mar 2024.

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

- [Zero-Shot Learning -- A Comprehensive Evaluation of the Good, the Bad and the Ugly](https://mlsanity.com/paper/1707.00600/) (2017)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [ExKMC: Expanding Explainable k-Means Clustering](https://mlsanity.com/paper/2006.02399/) (2020)
- [On the price of explainability for some clustering problems](https://mlsanity.com/paper/2101.01576/) (2021)
- [Nearly-Tight and Oblivious Algorithms for Explainable Clustering](https://mlsanity.com/paper/2106.16147/) (2021)
- [How to Find a Good Explanation for Clustering?](https://mlsanity.com/paper/2112.06580/) (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)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [Interpretable Clustering via Multi-Polytope Machines](https://mlsanity.com/paper/2112.05653/) (2021)
- [Efficient Algorithms for Generating Provably Near-Optimal Cluster Descriptors for Explainability](https://mlsanity.com/paper/2002.02487/) (2020)
- [Constraint-Based Clustering Selection](https://mlsanity.com/paper/1609.07272/) (2016)
- [Cluster Explanation via Polyhedral Descriptions](https://mlsanity.com/paper/2210.08798/) (2022)
- [Deep Descriptive Clustering](https://mlsanity.com/paper/2105.11549/) (2021)

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

- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)
- [CohEx: A Generalized Framework for Cohort Explanation](https://mlsanity.com/paper/2410.13190/) (2024)

## Abstract (arXiv)

The domain of explainable AI is of interest in all Machine Learning fields, and it is all the more important in clustering, an unsupervised task whose result must be validated by a domain expert. We aim at finding a clustering that has high quality in terms of classic clustering criteria and that is explainable, and we argue that these two dimensions must be considered when building the clustering. We consider that a good global explanation of a clustering should give the characteristics of each cluster taking into account their abilities to describe its objects (coverage) while distinguishing it from the other clusters (discrimination). Furthermore, we aim at leveraging expert knowledge, at different levels, on the structure of the expected clustering or on its explanations. In our framework an explanation of a cluster is a set of patterns, and we propose a novel interpretable constrained clustering method called ECS for declarative clustering with Explainabilty-driven Cluster Selection that integrates structural or domain expert knowledge expressed by means of constraints. It is based on the notion of coverage and discrimination that are formalized at different levels (cluster / clustering), each allowing for exceptions through parameterized thresholds. Our method relies on four steps: generation of a set of partitions, computation of frequent patterns for each cluster, pruning clusters that violates some constraints, and selection of clusters and associated patterns to build an interpretable clustering. This last step is combinatorial and we have developed a Constraint-Programming (CP) model to solve it. The method can integrate prior knowledge in the form of user constraints, both before or in the CP model.