TY - JOUR
AU - Bandyapadhyay, Sayan
AU - Fomin, Fedor
AU - Golovach, Petr A
AU - Lochet, William
AU - Purohit, Nidhi
AU - Simonov, Kirill
PY - 2022/06/28
Y2 - 2024/06/18
TI - How to Find a Good Explanation for Clustering?
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 36
IS - 4
SE - AAAI Technical Track on Data Mining and Knowledge Management
DO - 10.1609/aaai.v36i4.20306
UR - https://ojs.aaai.org/index.php/AAAI/article/view/20306
SP - 3904-3912
AB - k-means and k-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable k-means and k-median clustering in ICML 2020. In this model, a decision tree with k leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the ``best explanation'' by using a decision tree with k leaves? (2) For a given set of points, how to find a decision tree with k leaves minimizing the k-means/median objective of the resulting explainable clustering?To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.
ER -