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

An Iterated Local Search Algorithm for K-Means Clustering

作　　者：吴景岚[1] 朱文兴[2] 

机构地区：[1]闽江学院计算机科学系,福州350002 [2]福州大学计算机科学与技术系,福州350002

出　　处：《计算机工程与应用》2004年第22期37-41,共5页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(编号:10301009);福建省自然科学基金资助项目(编号:A0310013)

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

关 键 词：聚类问题 K均值算法 迭代局部搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]