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.

聚类是数据科学和机器学习中最基本的工具之一，k-means 聚类是最常见的方法之一。本文研究了低维数据实例的 k-means 问题，并将其表示为结构化的凸分配问题，利用低维结构解决大数据集的问题。该方法结合了全局优化理论的方法来加速处理程序，并提供了性能的数值结果。