一种引力搜索和K-means的混合聚类算法

A hybrid clustering algorithm based on gravitational search algorithm and K-means

K-means算法是解决聚类问题的一种经典算法,具有算法简单、速度快和容易实现等特点.但它依赖初始值,容易陷入局部最优解.引力搜索算法是在2009年由伊朗的Esmat Rashedi教授等人基于引力定律提出的一个新算法,该算法已成功应用于聚类,但存在收敛速度慢等问题.鉴于K-means原理简单,聚类速度快的特点,本文提出了一种K-means和引力搜索相结合的算法,该算法将全局搜索能力强的引力搜索算法和局部搜索能力较强的K-means算法结合在一起,减少了引力搜索算法的运行时间,解决了引力搜索易受初始种群影响的问题,并且避免了K-means陷入局部最优的问题.实验结果表明,改进算法比K-means和引力搜索算法都能得到更优的解,并且比引力搜索算法收敛速度更快.

K-means algorithm is a classical algorithm to solve the clustering problem.The algorithm is simple,fast and easy to implement,but it is dependent on the initial value,and easy to fall into local optimal solution.Gravitational Search Algorithm(GSA) based on the Law of Gravity is proposed recently by Professor Esmat Rashedi in 2009.And applied to the clustering,it has some shortcomings such as slow convergence.In view of the K-means simple to implement and efficient in most cases,a hybrid clustering algorithm based on K-means and GSA(KM-GSA-KM) was proposed.The new algorithm has strong global search ability of GSA,and has strong local search ability with the help of the Kmeans.It reduces operation time,and solves the problem of GSA easily influenced by initial population.Experimental results show that the performance of KM-GSA-KM is much better than that of GSA.