How to find a good explanation for clustering?

DOI10.1016/J.ARTINT.2023.103948MaRDI QIDQ6136087zbMATH OpenOpenAlexFDO

Authors Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, William Lochet, Nidhi Purohit, Kirill Simonov

Publication date 28 August 2023

Published in Artificial Intelligence (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2112.06580

zbMATH Keywords

clustering with outliersexplainable clusteringmultivariate analysis

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Abstract: $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 [ICML 2020] proposed an elegant model of explainable $k$-means and $k$-median clustering. 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.

Cites work

• A Lottery Model for Center-Type Problems With Outliers
• Algorithms for facility location problems with outliers. (Extended abstract)
• Approximation schemes for clustering with outliers
• Clustering large graphs via the singular value decomposition
• Constant approximation for k-median and k-means with outliers via iterative rounding
• Definitions, methods, and applications in interpretable machine learning
• Fundamentals of parameterized complexity
• Generalized additive models
• scientific article; zbMATH DE number 5764796 (Why is no real title available?)
• scientific article; zbMATH DE number 7650294 (Why is no real title available?)
• Interpretable clustering using unsupervised binary trees
• Interpretable clustering: an optimization approach
• Kernelization. Theory of parameterized preprocessing
• Linear-time approximation schemes for clustering problems in any dimensions
• NP-hardness of Euclidean sum-of-squares clustering
• On Tackling Explanation Redundancy in Decision Trees
• On the complexity of k-SAT
• On the Parameterized Complexity of Approximating Dominating Set
• Parameterized algorithms
• Random forests
• Supersparse linear integer models for optimized medical scoring systems
• The non-uniform k-center problem
• The planar \(k\)-means problem is NP-hard
• Which problems have strongly exponential complexity?

Cited in

(3)

• Multi-objective optimization algorithm based on clustering guided binary equilibrium optimizer and NSGA-III to solve high-dimensional feature selection problem
• Transparency of combinatorial optimisations via machine learning and explainable AI
• Explaining commonalities of clusters of RDF resources in natural language

This page was built for publication: How to find a good explanation for clustering?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136087)