关键词: 聚类, K-medoids算法, 初始聚类中心, 密度峰值, 准则函数

Abstract: To overcome the deficiencies of the fast K-medoids and the variance based K-medoids clustering algorithms whose number of clusters of a dataset must be provided manually and their initial seeds may locate in a same cluster or cannot be totally found etc. Stimulated by the density peak clustering algorithm, this paper proposes two new K-medoids clustering algorithms. The new algorithms define the local density ρ_i of point x_i as the reciprocal of the sum of the distance betweenxiand its t nearest neighbors, and new distance δ_i of point x_i is defined as well, then the decision graph of a point distance relative to its local density is plotted. The points with higher local density and apart from each other located at the upper right corner of the decision graph, which are far away from the rest points in the same dataset, are chosen as the initial seeds for K-medoids, so that the seeds will be in different clusters and the number of clusters of the dataset is automatically determined as the number of initial seeds. In order to get a better clustering, a new measure function is proposed as the ratio of the intra-distance of clusters to the inter-distance between clusters. The proposed two new K-medoids algorithms are tested on the real datasets from UCI machine learning repository and on the synthetic datasets. The clustering results of the proposed algorithms are evaluated in terms of the initial seeds selected, iterations, clustering time, Rand index, Jaccard coefficient, Adjusted Rand index and the clustering accuracy. The experimental results demonstrate that the proposed new K-medoids clustering algorithms can recognize the number of clusters of a dataset, find its proper initial seeds, reduce the clustering iterations and the clustering time, improve the clustering accuracy, and are robust to noises as well.

Key words: clustering, K-medoids algorithm, initial seeds, density peak, measure function