The computational complexity of some explainable clustering problems

Machine learning models and algorithms have been used in a number of systems that take decisions that affect our lives. Thus, explainable methods are desirable so that people are able to have a better understanding of their behavior, which allows for comfortable use of these systems or, eventually, the questioning of their applicability [1]. Recently, there has been some effort to devise explainable methods for unsupervised learning tasks, in particular, for clustering [2, 3]. We investigate the framework discussed by [2], where an explainable clustering is given by a partition, induced by the leaves of an axis-aligned decision tree, that optimizes some predefined objective function. Figure 1 shows a decision tree that defines a clustering for the Iris dataset.