English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Clustering is a popular form of unsupervised learning for geometric data.Unfortunately, many clustering algorithms lead to cluster assignments that arehard to explain, partially because they depend on all the features of the datain a complicated way. To improve interpretability, we consider using a smalldecision tree to partition a data set into clusters, so that clusters can becharacterized in a straightforward manner. We study this problem from atheoretical viewpoint, measuring cluster quality by the $k$-means and$k$-medians objectives: Must there exist a tree-induced clustering whose costis comparable to that of the best unconstrained clustering, and if so, how canit be found? In terms of negative results, we show, first, that populartop-down decision tree algorithms may lead to clusterings with arbitrarilylarge cost, and second, that any tree-induced clustering must in general incuran $\Omega(\log k)$ approximation factor compared to the optimal clustering. Onthe positive side, we design an efficient algorithm that produces explainableclusters using a tree with $k$ leaves. For two means/medians, we show that asingle threshold cut suffices to achieve a constant factor approximation, andwe give nearly-matching lower bounds. For general $k \geq 2$, our algorithm isan $O(k)$ approximation to the optimal $k$-medians and an $O(k^2)$approximation to the optimal $k$-means. Prior to our work, no algorithms wereknown with provable guarantees independent of dimension and input size.

Explainable $k$-Means and $k$-Medians Clustering