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

One of the most popular clustering algorithms is the celebrated $D^\alpha$seeding algorithm (also know as $k$-means++ when $\alpha=2$) by Arthur andVassilvitskii (2007), who showed that it guarantees in expectation an$O(2^{2\alpha}\cdot \log k)$-approximate solution to the ($k$,$\alpha$)-meanscost (where euclidean distances are raised to the power $\alpha$) for any$\alpha\ge 1$. More recently, Balcan, Dick, and White (2018) observedexperimentally that using $D^\alpha$ seeding with $\alpha>2$ can lead to abetter solution with respect to the standard $k$-means objective (i.e. the$(k,2)$-means cost).  In this paper, we provide a rigorous understanding of this phenomenon. Forany $\alpha>2$, we show that $D^\alpha$ seeding guarantees in expectation anapproximation factor of $$ O_\alpha \left((g_\alpha)^{2/\alpha}\cdot\left(\frac{\sigma_{\mathrm{max}}}{\sigma_{\mathrm{min}}}\right)^{2-4/\alpha}\cdot(\min\{\ell,\log k\})^{2/\alpha}\right)$$ with respect to the standard$k$-means cost of any underlying clustering; where $g_\alpha$ is a parametercapturing the concentration of the points in each cluster,$\sigma_{\mathrm{max}}$ and $\sigma_{\mathrm{min}}$ are the maximum and minimumstandard deviation of the clusters around their means, and $\ell$ is the numberof distinct mixing weights in the underlying clustering (after rounding them tothe nearest power of $2$). We complement these results by some lower boundsshowing that the dependency on $g_\alpha$ and$\sigma_{\mathrm{max}}/\sigma_{\mathrm{min}}$ is tight.  Finally, we provide an experimental confirmation of the effects of theaforementioned parameters when using $D^\alpha$ seeding. Further, wecorroborate the observation that $\alpha>2$ can indeed improve the $k$-meanscost compared to $D^2$ seeding, and that this advantage remains even if we runLloyd's algorithm after the seeding.

An Analysis of $D^\alpha$ seeding for $k$-means