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\ge 2$ and $\tilde{O}(1/\delta \cdot d^{2/p-1}{\log }^{2}k)$ for every $1\le p<2$. For $1\le 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\ge 2$ and $\tilde{O}(d^{2/p-1}k)$ for $1\le p\le 2$. We complement these results with nearly matching lower bounds.