KNN-maximum dispersion balanced K-means algorithm

Abstract

Clustering analysis is an essential task in data mining and machine learning, and the classical K-means algorithm is widely used due to its efficiency. However, its random initialization often leads to unstable results, especially on complex or nonuniform datasets, where it easily falls into local optima. Moreover, its objective function focuses solely on intra-cluster compactness while overlooking inter-cluster separability, thus limiting global clustering performance. To address these issues, this paper proposes an improved K-means method (MD-Kmeans). The algorithm integrates K-nearest-neighbor– based density estimation with a maximum-dispersion strategy to ensure representative and well-distributed initial centers, and employs a balanced objective that jointly enhances intra-cluster compactness and inter-cluster separability. Experimental results show that MD-Kmeans achieves notable improvements in Adjusted Rand Index (ARI), Silhouette Coefficient (SC), and Davies–Bouldin Index (DBI), outperforming traditional K-means and recent variants, particularly on non-uniform datasets.