Adaptive K-means Algorithm Combining Nearest-Neighbor Matrix and Local Density

Abstract

To overcome the deficiencies of traditional K-means algorithms which are sensitive to the initial cluster centers and outliers, and their variants introducing densities, which need giving arbitrary parameters, this paper proposes an adaptive K-means clustering algorithm combining the nearest neighbor matrix and local density. Ins-pired by the nearest-neighbors and the density peaks, the adjacency matrix is constructed by introducing the distance difference between objects. Then the local density is calculated without any parameters except for the adjacency matrix. After that, the initial centers and the number of clusters of K-means are simultaneously determined by using the nearest-neighbor matrix and local density, and the rest objects are assigned as well. Experiments on synthetic datasets, and on real world datasets from UCI machine learning repository, and the comparisons with traditional K-means algorithm, and the improved K-means algorithms based on outliers or densities all demonstrate that the pro-posed adaptive K-means algorithm is robust to outliers on synthetic datasets, and obtains more accurate clustering results for real world datasets from UCI machine learning repository.

Keywords

• adaptive k-means clustering algorithm; density peak principle; nearest-neighbor principle; local density