Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912226152022016 |
|---|---|
| author | Spalding-Jamieson, Jack Robson, Eliot Wong Zheng, Da Wei |
| author_facet | Spalding-Jamieson, Jack Robson, Eliot Wong Zheng, Da Wei |
| contents | For very large values of $k$, we consider methods for fast $k$-means clustering of massive datasets with $10^7\sim10^9$ points in high-dimensions ($d\geq100$). All current practical methods for this problem have runtimes at least $Ω(k^2)$. We find that initialization routines are not a bottleneck for this case. Instead, it is critical to improve the speed of Lloyd's local-search algorithm, particularly the step that reassigns points to their closest center. Attempting to improve this step naturally leads us to leverage approximate nearest-neighbor search methods, although this alone is not enough to be practical. Instead, we propose a family of problems we call "Seeded Approximate Nearest-Neighbor Search", for which we propose "Seeded Search-Graph" methods as a solution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_06163 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search Spalding-Jamieson, Jack Robson, Eliot Wong Zheng, Da Wei Machine Learning Computational Geometry For very large values of $k$, we consider methods for fast $k$-means clustering of massive datasets with $10^7\sim10^9$ points in high-dimensions ($d\geq100$). All current practical methods for this problem have runtimes at least $Ω(k^2)$. We find that initialization routines are not a bottleneck for this case. Instead, it is critical to improve the speed of Lloyd's local-search algorithm, particularly the step that reassigns points to their closest center. Attempting to improve this step naturally leads us to leverage approximate nearest-neighbor search methods, although this alone is not enough to be practical. Instead, we propose a family of problems we call "Seeded Approximate Nearest-Neighbor Search", for which we propose "Seeded Search-Graph" methods as a solution. |
| title | Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search |
| topic | Machine Learning Computational Geometry |
| url | https://arxiv.org/abs/2502.06163 |