A cutting plane algorithm for globally solving low dimensional k-means clustering problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913238483992576 |
|---|---|
| author | Ryner, Martin Kronqvist, Jan Karlsson, Johan |
| author_facet | Ryner, Martin Kronqvist, Jan Karlsson, Johan |
| contents | Clustering is one of the most fundamental tools in data science and machine learning, and k-means clustering is one of the most common such methods. There is a variety of approximate algorithms for the k-means problem, but computing the globally optimal solution is in general NP-hard. In this paper we consider the k-means problem for instances with low dimensional data and formulate it as a structured concave assignment problem. This allows us to exploit the low dimensional structure and solve the problem to global optimality within reasonable time for large data sets with several clusters. The method builds on iteratively solving a small concave problem and a large linear programming problem. This gives a sequence of feasible solutions along with bounds which we show converges to zero optimality gap. The paper combines methods from global optimization theory to accelerate the procedure, and we provide numerical results on their performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_13595 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A cutting plane algorithm for globally solving low dimensional k-means clustering problems Ryner, Martin Kronqvist, Jan Karlsson, Johan Optimization and Control Machine Learning 90C26 (Primary) 90C27 (Secondary) G.1.6 Clustering is one of the most fundamental tools in data science and machine learning, and k-means clustering is one of the most common such methods. There is a variety of approximate algorithms for the k-means problem, but computing the globally optimal solution is in general NP-hard. In this paper we consider the k-means problem for instances with low dimensional data and formulate it as a structured concave assignment problem. This allows us to exploit the low dimensional structure and solve the problem to global optimality within reasonable time for large data sets with several clusters. The method builds on iteratively solving a small concave problem and a large linear programming problem. This gives a sequence of feasible solutions along with bounds which we show converges to zero optimality gap. The paper combines methods from global optimization theory to accelerate the procedure, and we provide numerical results on their performance. |
| title | A cutting plane algorithm for globally solving low dimensional k-means clustering problems |
| topic | Optimization and Control Machine Learning 90C26 (Primary) 90C27 (Secondary) G.1.6 |
| url | https://arxiv.org/abs/2402.13595 |