关键词: k-means算法, 聚类中心, 平均密度, 孤立点, 收敛

Abstract: The existing k-means algorithms based on the density optimization are of the large search range, long time-consuming, and the clustering results are sensitive to isolated points. A k-means algorithm based on the average density optimizing the initial cluster centre, adk-means, is proposed to solve these problems. The isolated points are divided out from data set, and the average density of the remaining sample of data set is calculated out without involving of the isolated points. The isolated points are also ignored in the calculation of all other kinds of sample average in the process of clustering. Then it selects the centre of cluster from the density parameter set whose density is greater than the average density. The isolated point is assigned to the nearest cluster centre according to the principle of minimum distance, until the clustering is completely done. The experimental results show that, the average density based K-means algorithm of optimal initial clustering centre has faster convergence speed, better stability and higher clustering accuracy than the existing density based k-means algorithm, and eliminates the problem that the clustering results are sensitive to isolated points.

Key words: k-means algorithm, clustering centre, average density, isolated points, convergence