Towards Explainable Clustering: A Constrained Declarative based Approach
Mathieu Guilbert Christel Vrain Thi-Bich-Hanh Dao
The domain of explainable AI is of interest in all Machine Learning fields,
and it is all the more important in clustering, an unsupervised task whose
result must be validated by a domain expert. We aim at finding a clustering
that has high quality in terms of classic clustering criteria and that is
explainable, and we argue that these two dimensions must be considered when
building the clustering. We consider that a good global explanation of a
clustering should give the characteristics of each cluster taking into account
their abilities to describe its objects (coverage) while distinguishing it from
the other clusters (discrimination). Furthermore, we aim at leveraging expert
knowledge, at different levels, on the structure of the expected clustering or
on its explanations. In our framework an explanation of a cluster is a set of
patterns, and we propose a novel interpretable constrained clustering method
called ECS for declarative clustering with Explainabilty-driven Cluster
Selection that integrates structural or domain expert knowledge expressed by
means of constraints. It is based on the notion of coverage and discrimination
that are formalized at different levels (cluster / clustering), each allowing
for exceptions through parameterized thresholds. Our method relies on four
steps: generation of a set of partitions, computation of frequent patterns for
each cluster, pruning clusters that violates some constraints, and selection of
clusters and associated patterns to build an interpretable clustering. This
last step is combinatorial and we have developed a Constraint-Programming (CP)
model to solve it. The method can integrate prior knowledge in the form of user
constraints, both before or in the CP model.