On the price of explainability for some clustering problems

• URL: http://arxiv.org/abs/2101.01576v2
• Date: Sat, 13 Feb 2021 14:39:39 GMT
• Title: On the price of explainability for some clustering problems
• Authors: Eduardo Laber, Lucas Murtinho
• Abstract summary: 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.
• Score: 1.52292571922932
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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.

Related papers

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. We construct an efficient-time algorithm that turns out to be minimax optimal for this classification problem.
  arXiv  Detail & Related papers  (2024-08-27T18:28:31Z)
• Explainable k-means. Don't be greedy, plant bigger trees! [12.68470213641421]
  We provide a new bi-criteria $tildeO(log2 k)$ competitive algorithm for explainable $k$-means clustering. Explainable $k$-means was recently introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020)
  arXiv  Detail & Related papers  (2021-11-04T23:15:17Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  We propose an ensemble learning algorithm called textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) for imbalanced classification problems.
  arXiv  Detail & Related papers  (2021-09-01T14:10:38Z)
• Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
  We study the problem of explainable clustering in the setting first formalized by Moshkovitz, Dasgupta, Rashtchian, and Frost (ICML 2020) A $k$-clustering is said to be explainable if it is given by a decision tree where each internal node data points with a threshold cut in a single dimension (feature) We give an algorithm that outputs an explainable clustering that loses at most a factor of $O(log2 k)$ compared to an optimal (not necessarily explainable) clustering for the $k$-medians objective.
  arXiv  Detail & Related papers  (2021-06-30T15:49:41Z)
• Near-Optimal Explainable $k$-Means for All Dimensions [13.673697350508965]
  We show an efficient algorithm that finds an explainable clustering whose $k$-means cost is at most $k1 - 2/dmathrmpoly(dlog k)$. We get an improved bound of $k1 - 2/dmathrmpolylog(k)$, which we show is optimal for every choice of $k,dge 2$ up to a poly-logarithmic factor in $k$.
  arXiv  Detail & Related papers  (2021-06-29T16:59:03Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  We introduce a new approach based on A* search for clustering. We overcome the prohibitively large search space by combining A* with a novel emphtrellis data structure. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks.
  arXiv  Detail & Related papers  (2021-04-14T18:15:27Z)
• ExKMC: Expanding Explainable $k$-Means Clustering [19.702066333512548]
  We study algorithms for $k$-means clustering, focusing on a trade-off between explainability and accuracy. We develop a new explainable $k$-means clustering algorithm, ExKMC, that takes an additional parameter $k' geq k$ and outputs a decision tree with $k'$ leaves. ExKMC produces a low cost clustering, outperforming both standard decision tree methods and other algorithms for explainable clustering.
  arXiv  Detail & Related papers  (2020-06-03T17:14:55Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  We consider using a small decision tree to partition a data set into clusters, so that clusters can be characterized in a straightforward manner. We show that popular top-down decision tree algorithms may lead to clusterings with arbitrarily large cost. We design an efficient algorithm that produces explainable clusters using a tree with $k$ leaves.
  arXiv  Detail & Related papers  (2020-02-28T04:21:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.