The computational complexity of some explainable clustering problems
We study the computational complexity of some explainable clustering problems in the framework proposed by [Dasgupta et al., ICML 2020], where explainability is achieved via axis-aligned decision trees. We consider the $k$-means, $k$-medians, $k$-centers and the spacing cost functions. We prove that the first three are hard to optimize while the latter can be optimized in polynomial time.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
How to Find a Good Explanation for Clustering?
$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. Mo…
ClusteringOn the price of explainability for some clustering problems
The price of explainability for a clustering task can be defined as the unavoidable loss,in terms of the objective function, if we force the final partition to be explainable. Here, we study this price for the following …
ClusteringComputational lower bounds in latent models: clustering, sparse-clustering, biclustering
In many high-dimensional problems, like sparse-PCA, planted clique, or clustering, the best known algorithms with polynomial time complexity fail to reach the statistical performance provably achievable by algorithms fre…
ClusteringFast and explainable clustering based on sorting
We introduce a fast and explainable clustering method called CLASSIX. It consists of two phases, namely a greedy aggregation phase of the sorted data into groups of nearby data points, followed by the merging of groups i…
ClusteringSPINEX-Clustering: Similarity-based Predictions with Explainable Neighbors Exploration for Clustering Problems
This paper presents a novel clustering algorithm from the SPINEX (Similarity-based Predictions with Explainable Neighbors Exploration) algorithmic family. The newly proposed clustering variant leverages the concept of si…
BenchmarkingClustering