Near-optimal Explainable $k$-means Clustering under $\ell_p$ Norm

We study explainable $k$-means clustering, introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (2020), and generalize it to $\ell_p$ norms. The goal is to find a clustering represented by a threshold decision tree while minimizing the $k$-means objective. Such a clustering is easy for humans to interpret because each internal node partitions the data by thresholding a single feature, so every cluster can be explained through a sequence of simple decisions. We give algorithms that find threshold trees with $(1+\delta)k$ leaves and competitive ratio $\tilde{O}_p(1/\delta\cdot \log^{2+2/p-2/p^2} k)$ for every finite $p \geq 2$ and $\tilde{O}(1/\delta \cdot d^{2/p-1}\log^2 k)$ for every $1 \leq p < 2$. For $1 \leq p < 2$, we show that this dependence on $d$ is unavoidable with less than $k^2/2$ leaves and provide an $\tilde{O}(\log^{2+2/p-2/p^2} k)$-competitive algorithm with $8k^2$ leaves. We also provide near-optimal algorithms for explainable $k$-means under $\ell_p$ norms with exactly $k$ leaves. Our algorithms achieve the price of explainability of $\tilde{O}(k)$ for every finite $p \geq 2$ and $\tilde{O}(d^{2/p-1} k)$ for $1\leq p \leq 2$. We complement these results with nearly matching lower bounds.