Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917569151107072 |
|---|---|
| author | Manthey, Bodo van Rhijn, Jesse |
| author_facet | Manthey, Bodo van Rhijn, Jesse |
| contents | We analyze the running time of the Hartigan-Wong method, an old algorithm for the $k$-means clustering problem. First, we construct an instance on the line on which the method can take $2^{Ω(n)}$ steps to converge, demonstrating that the Hartigan-Wong method has exponential worst-case running time even when $k$-means is easy to solve. As this is in contrast to the empirical performance of the algorithm, we also analyze the running time in the framework of smoothed analysis. In particular, given an instance of $n$ points in $d$ dimensions, we prove that the expected number of iterations needed for the Hartigan-Wong method to terminate is bounded by $k^{12kd}\cdot poly(n, k, d, 1/σ)$ when the points in the instance are perturbed by independent $d$-dimensional Gaussian random variables of mean $0$ and standard deviation $σ$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_10368 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering Manthey, Bodo van Rhijn, Jesse Data Structures and Algorithms Computational Geometry Probability We analyze the running time of the Hartigan-Wong method, an old algorithm for the $k$-means clustering problem. First, we construct an instance on the line on which the method can take $2^{Ω(n)}$ steps to converge, demonstrating that the Hartigan-Wong method has exponential worst-case running time even when $k$-means is easy to solve. As this is in contrast to the empirical performance of the algorithm, we also analyze the running time in the framework of smoothed analysis. In particular, given an instance of $n$ points in $d$ dimensions, we prove that the expected number of iterations needed for the Hartigan-Wong method to terminate is bounded by $k^{12kd}\cdot poly(n, k, d, 1/σ)$ when the points in the instance are perturbed by independent $d$-dimensional Gaussian random variables of mean $0$ and standard deviation $σ$. |
| title | Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering |
| topic | Data Structures and Algorithms Computational Geometry Probability |
| url | https://arxiv.org/abs/2309.10368 |