论文标题
通过示例解释的聚类：复杂性和有效近似算法
Explainable Clustering via Exemplars: Complexity and Efficient Approximation Algorithms
论文作者
论文摘要
可解释的AI（XAI）是一个重要的发展领域，但在聚类方面仍然相对研究。我们提出了一种可解释的按设计聚类方法，不仅可以找到集群，而且还可以解释每个群集。基于典范的心理学概念学院的使用支持了示例示例的理解。我们表明，找到一小部分示例来解释即使是一个群集也是计算上很棘手的。因此，总体问题具有挑战性。我们开发了一种近似算法，该算法在聚类质量以及所使用的示例数方面可提供可证明的性能保证。该基本算法解释了每个群集中的所有实例，而另一种近似算法则使用有界数的示例来允许更简单的解释，并证明涵盖了所有实例中的很大一部分。实验结果表明，我们的工作在涉及图像和文本的深层嵌入的领域中很有用。
Explainable AI (XAI) is an important developing area but remains relatively understudied for clustering. We propose an explainable-by-design clustering approach that not only finds clusters but also exemplars to explain each cluster. The use of exemplars for understanding is supported by the exemplar-based school of concept definition in psychology. We show that finding a small set of exemplars to explain even a single cluster is computationally intractable; hence, the overall problem is challenging. We develop an approximation algorithm that provides provable performance guarantees with respect to clustering quality as well as the number of exemplars used. This basic algorithm explains all the instances in every cluster whilst another approximation algorithm uses a bounded number of exemplars to allow simpler explanations and provably covers a large fraction of all the instances. Experimental results show that our work is useful in domains involving difficult to understand deep embeddings of images and text.
