Abstract
Constrained clustering is a semi-supervised task that employs a limited amount of labelled data, formulated as constraints, to incorporate domain-specific knowledge and to significantly improve clustering accuracy. Previous work has considered exact optimization formulations that can guarantee optimal clustering while satisfying all constraints, however these approaches lack interpretability. Recently, decision-trees have been used to produce inherently interpretable clustering solutions, however existing approaches do not support clustering constraints and do not provide strong theoretical guarantees on solution quality. In this work, we present a novel SAT-based framework for interpretable clustering that supports clustering constraints and that also provides strong theoretical guarantees on solution quality. We also present new insight into the trade-off between interpretability and satisfaction of such user-provided constraints. Our framework is the first approach for interpretable and constrained clustering. Experiments with a range of real-world and synthetic datasets demonstrate that our approach can produce high-quality and interpretable constrained clustering solutions.
Abstract (translated)
约束聚类是一种半监督任务,使用少量的标记数据,将其作为约束,以引入领域特定知识,并显著改善聚类准确性。先前的工作考虑了可以确保最优聚类同时满足所有约束的精确优化 formulation,但这些方法缺乏解释性。最近,决策树被用于产生具有内在解释性聚类解决方案,但现有方法不支持聚类约束,并未提供 strong theoretical guarantee 于 solution 质量。在本工作中,我们提出了一种新 SAT 为基础的框架,用于可解释聚类,支持聚类约束,并提供了 strong theoretical guarantee 于 solution 质量。我们还探讨了解释性和满足此类用户约束之间的权衡。我们的框架是可解释和约束聚类的第一步方法。与各种真实和合成数据集的实验表明,我们的方法可以产生高质量的解释性约束聚类解决方案。
URL
https://arxiv.org/abs/2301.12671
