How to Find a Good Explanation for Clustering?


  • Sayan Bandyapadhyay University of Bergen
  • Fedor Fomin University of Bergen
  • Petr A Golovach University of Bergen
  • William Lochet University of Bergen
  • Nidhi Purohit University of Bergen
  • Kirill Simonov TU Wien



Data Mining & Knowledge Management (DMKM), Philosophy And Ethics Of AI (PEAI), Machine Learning (ML), Search And Optimization (SO)


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.




How to Cite

Bandyapadhyay, S., Fomin, F., Golovach, P. A., Lochet, W., Purohit, N., & Simonov, K. (2022). How to Find a Good Explanation for Clustering?. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4), 3904-3912.



AAAI Technical Track on Data Mining and Knowledge Management