基于K均值的迭代局部搜索聚类算法

K均值聚类算法(KM)是解决聚类问题的一个常用的方法,该方法的主要缺点是其找到的局部极小值与全局最优值的偏差往往较大。论文构造一种基于KM算法的迭代局部搜索算法(称之为IKM)。该算法以KM算法所得到的解作为初始解,从该初始解开始作局部搜索,在搜索过程中接受部分劣解。当解无法改进时,算法对所得到的局部极小解做适当强度的扰动后进行下一次的迭代,以跳出局部极小,从而拓展了搜索的范围。试验结果表明IKM算法得到的聚类结果比KM算法得到的聚类结果有明显的改进,平均改进达100%以上。当数据集越大,簇的个数越多时,改进的效果越是显著,可以达到300%以上。因而,IKM算法是一个确实可行的有效的方法。

An Iterated Local Search Algorithm for K-Means Clustering

K-means clustering algorithm(KM)is one of the common local search approaches used in clustering problem.But the main drawback of KM is that it often gets trapped in local minimum that are significantly worse than the global optimum.This paper presents an Iterated Local Search framework based on KM(IKM),it takes the solution by K-means algorithm as its initial solution,from which local search process is started;during the searching,some bad solu-tions are accepted.When a solution can no more be improved,the algorithm makes the next iteration after an appropri-ate disturbance on the local minimum solution,in order to skip out of the local minimum,consequently enlarging the search space.Clustering results obtained from the proposed algorithm are averagely100%plus improvement over tradi-tional K-means algorithm.For larger dataset and more clusters,the improvement exceeds300%in certain cases.