Explainable Clustering via Exemplars: Complexity and Efficient Approximation Algorithms

Explainability in clustering has been largely neglected: While explainable AI is growing as a field, the paper identifies that clustering—a fundamental machine learning task—has received relatively little attention for explainability, suggesting a significant gap in making AI systems transparent to users.

Exemplars provide psychologically grounded explanations: The approach uses exemplars (representative examples) to explain clusters, which is supported by psychological research on how humans understand concepts, making this method more aligned with how people naturally learn and reason about categories.

Finding good explanations is mathematically hard: The researchers prove that even explaining a single cluster with exemplars is computationally intractable, meaning there's no known efficient way to find perfect solutions—a fundamental challenge that justifies the need for practical approximation methods.

Trade-offs between explanation completeness and simplicity: The paper develops two algorithms offering different trade-offs: one that explains every instance in a cluster but may use many exemplars, and another that uses fewer exemplars while still covering most instances, allowing practitioners to choose based on their needs.

Practical value for complex AI systems: Experimental results demonstrate the approach works on difficult-to-interpret outputs like deep learning embeddings of images and text, suggesting real-world applicability for making modern AI systems more understandable to users and stakeholders.