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/

Zendy Plus

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

Zendy Tools

Zendy Open

Many clustering algorithms are guided by certain cost functions such as thewidely-used $k$-means cost. These algorithms divide data points into clusterswith often complicated boundaries, creating difficulties in explaining theclustering decision. In a recent work, Dasgupta, Frost, Moshkovitz, andRashtchian (ICML 2020) introduced explainable clustering, where the clusterboundaries are axis-parallel hyperplanes and the clustering is obtained byapplying a decision tree to the data. The central question here is: how muchdoes the explainability constraint increase the value of the cost function?  Given $d$-dimensional data points, we show an efficient algorithm that findsan explainable clustering whose $k$-means cost is at most $k^{1 -2/d}\,\mathrm{poly}(d\log k)$ times the minimum cost achievable by a clusteringwithout the explainability constraint, assuming $k,d\ge 2$. Taking the minimumof this bound and the $k\,\mathrm{polylog} (k)$ bound in independent work byMakarychev-Shan (ICML 2021), Gamlath-Jia-Polak-Svensson (2021), orEsfandiari-Mirrokni-Narayanan (2021), we get an improved bound of $k^{1 -2/d}\,\mathrm{polylog}(k)$, which we show is optimal for every choice of$k,d\ge 2$ up to a poly-logarithmic factor in $k$. For $d = 2$ in particular,we show an $O(\log k\log\log k)$ bound, improving near-exponentially over theprevious best bound of $O(k\log k)$ by Laber and Murtinho (ICML 2021).

Near-Optimal Explainable $k$-Means for All Dimensions