Explainable k-means. Don't be greedy, plant bigger trees!
This work addresses the need for interpretable clustering methods in machine learning, offering a more efficient algorithm for explainable k-means with theoretical guarantees, though it is incremental as it builds on prior work.
The paper tackles the problem of explainable k-means clustering by developing a randomized bi-criteria algorithm that partitions data into (1+δ)k clusters with a cost at most Õ(1/δ·log² k) times the optimal unconstrained k-means cost, improving upon the previous Õ(k) competitive bound.
We provide a new bi-criteria $\tilde{O}(\log^2 k)$ competitive algorithm for explainable $k$-means clustering. Explainable $k$-means was recently introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). It is described by an easy to interpret and understand (threshold) decision tree or diagram. The cost of the explainable $k$-means clustering equals to the sum of costs of its clusters; and the cost of each cluster equals the sum of squared distances from the points in the cluster to the center of that cluster. The best non bi-criteria algorithm for explainable clustering $\tilde{O}(k)$ competitive, and this bound is tight. Our randomized bi-criteria algorithm constructs a threshold decision tree that partitions the data set into $(1+δ)k$ clusters (where $δ\in (0,1)$ is a parameter of the algorithm). The cost of this clustering is at most $\tilde{O}(1/ δ\cdot \log^2 k)$ times the cost of the optimal unconstrained $k$-means clustering. We show that this bound is almost optimal.