  We study the problem of explainability-first clustering where explainability
becomes a first-class citizen for clustering. Previous clustering approaches
use decision trees for explanation, but only after the clustering is completed.
In contrast, our approach is to perform clustering and decision tree training
holistically where the decision tree's performance and size also influence the
clustering results. We assume the attributes for clustering and explaining are
distinct, although this is not necessary. We observe that our problem is a
monotonic optimization where the objective function is a difference of
monotonic functions. We then propose an efficient branch-and-bound algorithm
for finding the best parameters that lead to a balance of cluster distortion
and decision tree explainability. Our experiments show that our method can
improve the explainability of any clustering that fits in our framework.
