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.

本文提出了一种新的基于 SAT 的可解释聚类框架，支持聚类约束，同时提供强有力的解决方案质量理论保证，并给出了关于解释性和满足用户约束之间权衡的新见解。