A Lightweight Deterministic Initialization Method for K-Means Clustering
TL;DR
The proposed method uses the L2 norm to directly map each multi-dimensional data point into a one-dimensional scalar value, which serves as a sorting criterion and is stored in a dictionary data structure to deterministically extract initial centroids.
Abstract
The K-Means clustering algorithm is a fundamental tool in machine learning, but its performance is often strongly affected by the instability of traditional random initialization methods, which can lead to convergence to poor local optima. Although many studies have proposed deterministic models to address this issue, they often involve high computational cost with O ( n 2 ) complexity. This paper introduces a new engineering approach that is lightweight and efficient. Specifically, the method uses the L2 norm to directly map each multi-dimensional data point into a one-dimensional scalar value. This value serves as a sorting criterion and is stored in a dictionary data structure to deterministically extract K initial centroids. Experimental evaluation shows that the proposed method completely eliminates variability, fixing the Adjusted Rand Index (ARI) at stable values of 0.6345 for the Digits dataset and 0.7302 for the Iris dataset across all runs. These results demonstrate that a practical data structure-based approach can achieve high reliability with very low computational cost.