ExplainCC：基于节点标签解释相关聚类
原文：ExplainCC: Explaining Correlated Clusters by Node Labels
聚类算法日益重要的一项要求是，其决策和结果需要能够被人类用户清晰理解。我们针对相关聚类（CC）问题处理这一要求，适用于待聚类对象附带标签的情形。在CC中，目标是基于成对相似与不相似信息将一组对象划分为簇。我们提出的模型仅考虑可由标签树解释的簇，标签树本质上是一棵根据标签划分对象的决策树。目标是找到数据的一个可解释划分，使CC目标函数最小化。我们从理论视角形式化该问题，并证明了若干近似难度结果，包括对树大小施加约束时的情况。我们提出的贪心方法寻找局部最优分裂，并以自顶向下的方式递归工作。为高效计算最佳分裂，我们精心维护某些计数器。实验评估证明了其有效性。所提算法可在几分钟内处理超过百万条边的图，能在合成数据中找到真实解，并能在真实世界网络中产生可解释的簇。作者：Nadeesha Shyami Kumari Herath Mudiyanselage, Florian Adriaens, Nikolaj Tatti 类别：cs.LG,cs.DS