Fixed-sized clusters k-Means

2025/01/27 by Mikko Malinen, Malinen, Mikko I., Pasi Fränti +1
Computer Science · #62H30 #Advanced Clustering Algorithms Research #E.0 #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2501.16113

openalex publication_date 2025/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a k-means-based clustering algorithm, which optimizes the mean square error, for given cluster sizes. A straightforward application is balanced clustering, where the sizes of each cluster are equal. In the k-means assignment phase, the algorithm solves an assignment problem using the Hungarian algorithm. This makes the assignment phase time complexity O(n³). This enables clustering of datasets of size more than 5000 points.

Related

• K*-Means: A Parameter-free Clustering Algorithm
• k2-means for fast and accurate large scale clustering
• Big-Data Clustering: K-Means or K-Indicators?
• Dimensionality Reduction for k-means Clustering
• An efficient k-means clustering algorithm: analysis and implementation