paper-with-me

홈 › Papers

On the price of explainability for some clustering problems

2021-01-05 · Eduardo Laber, Lucas Murtinho

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 clustering problems: $k$-means, $k$-medians, $k$-centers and maximum-spacing. We provide upper and lower bounds for a natural model where explainability is achieved via decision trees. For the $k$-means and $k$-medians problems our upper bounds improve those obtained by [Moshkovitz et. al, ICML 20] for low dimensions. Another contribution is a simple and efficient algorithm for building explainable clusterings for the $k$-means problem. We provide empirical evidence that its performance is better than the current state of the art for decision-tree based explainable clustering.

📄 PDF Abstract BibTeX arXiv:2101.01576

Code (0)

등록된 구현이 없습니다.

Tasks

Clustering

Similar Papers 제목 키워드 기반

The computational complexity of some explainable clustering problems

2022-08-20 · Eduardo Sany Laber

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 $…

Clustering

SpEx: A Spectral Approach to Explainable Clustering

2025-11-02 · Tal Argov, Tal Wagner arxiv

Explainable clustering by axis-aligned decision trees was introduced by Moshkovitz et al. (2020) and has gained considerable interest. Prior work has focused on minimizing the price of explainability for specific cluster…

graph partitioning

Rough Sets for Explainability of Spectral Graph Clustering

2025-12-13 · Bartłomiej Starosta, Sławomir T. Wierzchoń, Piotr Borkowski, Dariusz Czerski 외 arxiv

Graph Spectral Clustering methods (GSC) allow representing clusters of diverse shapes, densities, etc. However, the results of such algorithms, when applied e.g. to text documents, are hard to explain to the user, especi…

Graph Clustering

XClusters: Explainability-first Clustering

2022-09-22 · Hyunseung Hwang, Steven Euijong Whang

We study the problem of explainability-first clustering where explainability becomes a first-class citizen for clustering. Previous clustering approaches use decision trees for explanation, but only after the clustering …

Clustering

The Random Walk behind Volatility Clustering

2016-12-29

Financial price changes obey two universal properties: they follow a power law and they tend to be clustered in time. The second regularity, known as volatility clustering, entails some predictability in the price change…

Clustering