# Efficient Algorithms for Generating Provably Near-Optimal Cluster Descriptors for Explainability

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2020.

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

- [Deep Descriptive Clustering](https://mlsanity.com/paper/2105.11549/) (2021)
- [Text-Guided Image Clustering](https://mlsanity.com/paper/2402.02996/) (2024)
- [Towards Explainable Clustering: A Constrained Declarative based Approach](https://mlsanity.com/paper/2403.18101/) (2024)
- [Explainable Clustering via Exemplars: Complexity and Efficient Approximation Algorithms](https://mlsanity.com/paper/2209.09670/) (2022)
- [Towards Practical Explainability with Cluster Descriptors](https://mlsanity.com/paper/2210.10662/) (2022)
- [Interpreting Inflammation Prediction Model via Tag-based Cohort Explanation](https://mlsanity.com/paper/2410.14082/) (2024)
- [Disjunctive and Conjunctive Normal Form Explanations of Clusters Using Auxiliary Information](https://mlsanity.com/paper/2504.20846/) (2025)

## Abstract (arXiv)

Improving the explainability of the results from machine learning methods has become an important research goal. Here, we study the problem of making clusters more interpretable by extending a recent approach of [Davidson et al., NeurIPS 2018] for constructing succinct representations for clusters. Given a set of objects S, a partition π of S (into clusters), and a universe T of tags such that each element in S is associated with a subset of tags, the goal is to find a representative set of tags for each cluster such that those sets are pairwise-disjoint and the total size of all the representatives is minimized. Since this problem is NP-hard in general, we develop approximation algorithms with provable performance guarantees for the problem. We also show applications to explain clusters from datasets, including clusters of genomic sequences that represent different threat levels.