Near-Optimal Explainable k -Means for All Dimensions
Moses Charikar, Lunjia Hu · Society for Industrial and Applied Mathematics eBooks · 2022
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 k1–2/d poly(d log k) times the minimum cost achievable by a clustering without the explainability constraint, assuming k, d ≥ 2. Taking the minimum of this bound and the k 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 k1–2/d polylog(k), which we show is optimal for every choice of k, d ≥ 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).