Accelerating the k-means++ Algorithm by Using Geometric Information
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910575184838656 |
|---|---|
| author | Corominas, Guillem Rodríguez Blesa, Maria J. Blum, Christian |
| author_facet | Corominas, Guillem Rodríguez Blesa, Maria J. Blum, Christian |
| contents | In this paper, we propose an acceleration of the exact k-means++ algorithm using geometric information, specifically the Triangle Inequality and additional norm filters, along with a two-step sampling procedure. Our experiments demonstrate that the accelerated version outperforms the standard k-means++ version in terms of the number of visited points and distance calculations, achieving greater speedup as the number of clusters increases. The version utilizing the Triangle Inequality is particularly effective for low-dimensional data, while the additional norm-based filter enhances performance in high-dimensional instances with greater norm variance among points. Additional experiments show the behavior of our algorithms when executed concurrently across multiple jobs and examine how memory performance impacts practical speedup. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_13189 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Accelerating the k-means++ Algorithm by Using Geometric Information Corominas, Guillem Rodríguez Blesa, Maria J. Blum, Christian Machine Learning Artificial Intelligence 91C20 In this paper, we propose an acceleration of the exact k-means++ algorithm using geometric information, specifically the Triangle Inequality and additional norm filters, along with a two-step sampling procedure. Our experiments demonstrate that the accelerated version outperforms the standard k-means++ version in terms of the number of visited points and distance calculations, achieving greater speedup as the number of clusters increases. The version utilizing the Triangle Inequality is particularly effective for low-dimensional data, while the additional norm-based filter enhances performance in high-dimensional instances with greater norm variance among points. Additional experiments show the behavior of our algorithms when executed concurrently across multiple jobs and examine how memory performance impacts practical speedup. |
| title | Accelerating the k-means++ Algorithm by Using Geometric Information |
| topic | Machine Learning Artificial Intelligence 91C20 |
| url | https://arxiv.org/abs/2408.13189 |