Near-Optimal Explainable $k$-Means for All Dimensions

Abstract

Many clustering algorithms are guided by certain cost functions such as the widely-used $k$-means cost. These algorithms divide data points into clusters with often complicated boundaries, creating difficulties in explaining the clustering decision. In a recent work, Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020) introduced explainable clustering, where the cluster boundaries are axis-parallel hyperplanes and the clustering is obtained by applying a decision tree to the data. The central question here is: how much does the explainability constraint increase the value of the cost function? Given $d$-dimensional data points, we show an efficient algorithm that finds an explainable clustering whose $k$-means cost is at most $k^{1-2/d}\mathrm{poly}(d\log k)$ times the minimum cost achievable by a clustering without the explainability constraint, assuming $k,d\ge 2$. Taking the minimum of this bound and the $k\mathrm{polylog}(k)$ bound in independent work by Makarychev-Shan (ICML 2021), Gamlath-Jia-Polak-Svensson (2021), or Esfandiari-Mirrokni-Narayanan (2021), we get an improved bound of $k^{1-2/d}\mathrm{polylog}(k)$, which we show is optimal for every choice of $k,d\ge 2$ up to a poly-logarithmic factor in $k$. For $d=2$ in particular, we show an $O(\log k\log \log k)$ bound, improving near-exponentially over the previous best bound of $O(k\log k)$ by Laber and Murtinho (ICML 2021).

34 pages, 2 figures, to appear in SODA 2022

References in corpus (5)

• Scalable Fair Clustering
• ExKMC: Expanding Explainable $k$-Means Clustering
• Near-optimal Algorithms for Explainable k-Medians and k-Means
• Nearly-Tight and Oblivious Algorithms for Explainable Clustering
• Better Algorithms for Individually Fair $k$-Clustering

Cited by in corpus (1)

• Nearly-Tight and Oblivious Algorithms for Explainable Clustering