Abstract: Evolutionary Algorithm (EA) can effectively overcome the drawback that Kmeans is sensitive to the initial clustering centers, thus enhancing the clustering performance. On the basis of evolutionary Kmeans clustering algorithm (FEAC), considering the randomness and locality in the splitting operator as a mutation operation, two improved splitting operators with global information (global splitting operator) were proposed. The idea of maxmin distance and the information of peripheral clusters were used to guide the selection of the initial splitting centers, in order to make splitting process more beneficial to global partition, furthermore, to improve the efficiency of the evolutionary clustering. The experimental results show that the improved algorithms based on global splitting operator outperform FEAC in terms of clusters number discovering and clustering accuracy.

Key words: Kmeans, Evolutionary Algorithm (EA), mutation operator, global splitting, maxmin distance

摘要： 进化算法可以有效地克服Kmeans对初始聚类中心敏感的缺陷，提高了聚类性能。在进化Kmeans聚类算法 (F-EAC)的基础上，针对其变异操作——簇分裂算子的随机性与局部性，提出了两个全局性分裂算子。结合最大最小距离的思想，利用待分裂簇的周边簇信息来指导簇分裂初始点的选择，使簇的分裂更有利于全局划分，以进一步提高进化聚类的有效性。实验结果表明，基于全局性分裂算子的算法在类数发现及聚类精度方面均优于FEAC。

关键词: K-means, 进化算法, 变异算子, 全局分裂, 最大最小距离