Nearly-Tight and Oblivious Algorithms for Explainable Clustering

Abstract

We study the problem of explainable clustering in the setting first formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A k-clustering is said to be explainable if it is given by a decision tree where each internal node splits data points with a threshold cut in a single dimension (feature), and each of the k leaves corresponds to a cluster. We give an algorithm that outputs an explainable clustering that loses at most a factor of O(^2 k) compared to an optimal (not necessarily explainable) clustering for the k-medians objective, and a factor of O(k ^2 k) for the k-means objective. This improves over the previous best upper bounds of O(k) and O(k^2), respectively, and nearly matches the previous ( k) lower bound for k-medians and our new (k) lower bound for k-means. The algorithm is remarkably simple. In particular, given an initial not necessarily explainable clustering in R^d, it is oblivious to the data points and runs in time O(dk ^2 k), independent of the number of data points n. Our upper and lower bounds also generalize to objectives given by higher _p-norms.

Tasks

Reproductions