K*-Means: A Parameter-free Clustering Algorithm
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908368998760448 |
|---|---|
| author | Mahon, Louis Lapata, Mirella |
| author_facet | Mahon, Louis Lapata, Mirella |
| contents | Clustering is a widely used and powerful machine learning technique, but its effectiveness is often limited by the need to specify the number of clusters, k, or by relying on thresholds that implicitly determine k. We introduce k*-means, a novel clustering algorithm that eliminates the need to set k or any other parameters. Instead, it uses the minimum description length principle to automatically determine the optimal number of clusters, k*, by splitting and merging clusters while also optimising the standard k-means objective. We prove that k*-means is guaranteed to converge and demonstrate experimentally that it significantly outperforms existing methods in scenarios where k is unknown. We also show that it is accurate in estimating k, and that empirically its runtime is competitive with existing methods, and scales well with dataset size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_11904 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | K*-Means: A Parameter-free Clustering Algorithm Mahon, Louis Lapata, Mirella Machine Learning Artificial Intelligence Information Theory Clustering is a widely used and powerful machine learning technique, but its effectiveness is often limited by the need to specify the number of clusters, k, or by relying on thresholds that implicitly determine k. We introduce k*-means, a novel clustering algorithm that eliminates the need to set k or any other parameters. Instead, it uses the minimum description length principle to automatically determine the optimal number of clusters, k*, by splitting and merging clusters while also optimising the standard k-means objective. We prove that k*-means is guaranteed to converge and demonstrate experimentally that it significantly outperforms existing methods in scenarios where k is unknown. We also show that it is accurate in estimating k, and that empirically its runtime is competitive with existing methods, and scales well with dataset size. |
| title | K*-Means: A Parameter-free Clustering Algorithm |
| topic | Machine Learning Artificial Intelligence Information Theory |
| url | https://arxiv.org/abs/2505.11904 |