一种改进粒子群和K-means结合的聚类算法

摘要：本文首先提出一种基于适应度权重的改进粒子群算法，该算法能够根据群中粒子收敛情况动态地调整构成粒子运行速度。然后将已提出的改进粒子群算法与K-means算法结合，使结合后的聚类算法取改进粒子群算法之所长，补K-means算法之所短。通过分析证明，在算法的有效性和算法效率上比其他算法都有明显的提高。

关键词：粒子群算法；聚类算法

1. 引言

粒子群优化(Particle Swarm Optimization，PSO)是一种群智能(Swarm Intelligence)方法的进化计算技术。其具有原理简单，便于理解，算法容易实现、操作参数少、易于收敛等优点。聚类分析(Cluster Analysis)利用数据间的相似性对数据进行分类。使得不同类别中的数据尽可能相异，而同一类数据之间尽可能相似，从而发现数据其中隐含的、有用的信息[1]。各种聚类算法中，K-means算法凭借其便于理解，算法简单易行，以及收敛速度快等特点，成为了最著名、最常用的聚类算法。但是其本身具有易陷入局部最优解，处理海量数据效率低下等不足。如何改进K-means算法，一直以来受到了广泛的关注和研究。

2. 基于适应度权重的改进粒子群算法

基于对粒子群优化算法的分析，本文将引入粒子运动适应度权重这一概念，并以此为核心提出一种改进的粒子群优化算法FWPSO。FWPSO将每个粒子的适应度和整个粒子群粒子的适应度进行计算，得出粒子的适应度权重，并将该权重引入到粒子速度的计算中。虽然增加了一定的计算量，但能够使粒子的运动速度和方向更加合理，从而提高算法收敛解的精度，有效避免算法陷入局部最优解，提高算法的性能。

2.1 适应度权重

本文通过测算每次迭代时粒子群中粒子适应度的差异情况，以此得出粒子群适应度权重，并将其作为判断粒子群收敛程度的标准。粒子群适应度权重 定义如下：

其中，t为迭代的次数；n为粒子群粒子个数；σ(t)为第t次次迭代时的适应度权重；fi(t)为第t次循环时i个粒子的适应度，favg(t)为第t次循环时所有粒子的适应度均值。

2.2 基于适应度权重改进的惯性权重

在标准粒子群优化算法中，惯性权重w随迭代次数线性减小，而不是根据粒子群收敛情况进行动态调整，并不适合粒子群实际的情况。本文将适应度权重引入到惯性权重中，具体定义为：

其中：w(t)为第t次迭代时的惯性权重；wmax、wmin分别为最大惯性权重和最小惯性权重；fmax(t)为第t次循环时粒子群最大适应度；fmin(t)为第t次循环时粒子群最小适应度。

2.3 基于适应度权重改进的学习因子

以σ为依据，定义根据适应度权重改进的学习因子分别为：

2.4 FWPSO改进粒子群优化算法

将改进的惯性权重w(t)和学习因子c1(t)和c2(t)应用到算法中，得到FWPSO优化算法为：

算法具体流程如下：

(1)算法初始化，确定参数，产生初始种群，随机初始化粒子的位移和速度；

(2)根据适应度函数计算各个粒子的适应度值

(3)对所有粒子的当前适应度和自体最优解，若当前适应度优于自体最优解，则将自体最优解设为当前适应度

(4)将每一个粒子适应度与群体最优解比较，若某粒子的适应度优于群体最优解，则将群体最优解设为该粒子适应度值，并将全局极值下标改为该粒子下标

(5)根据公式（6）、（7）、（8）（9）（10）确定惯性权重和学习因子，更新粒子的速度和位置，产生新粒子群

(6)判断是否达到最大迭代次数或收敛解达到指定精度，若达到则算法结束，否则转向步骤（2）。

3 改进粒子群与K-means结合的聚类算法

3.1 K-means算法

K-means算法首先从n个数据对象中任意选择k个作为初始聚类的簇心，再将剩余数据对象分配给离其最近的的簇心所在的聚类中。然后以减小目标函数值为方向，通过迭代不断调整每个类的簇心和数据对象在类中的分布。当迭代进行使得目标函数收敛，相邻两次算法的聚类中心相同时，聚类调整结束。

K-means聚类算法具有算法简单，计算执行速度快，资源耗费少。当聚类是密集的，类与类间区分明显时，算法的效果好。但K-means算法也具有易陷入局部最优解而找不到全局最优解，在处理海量大数据集时较为费时等缺点。这些缺点在很大程度上限制了算法的应用范围。

3.2 结合算法算法思想

由于粒子群算法的并行性和分布式处理问题的特点适合处理数据库形式的海量数据，且较聚类算法具有较强的全局搜索能力。与粒子群算法结合的聚类算法不但具有粒子群算法优良的全局搜索能力，同时具备了聚类算法局部搜索能力强的特点，在处理大规模数据集上也比单纯的聚类算法效果好。基于此，本文将已提出的FWPSO算法与K-means算法相结合，提出了一种改进的粒子群聚类算法——FWP-K算法。

在FWP-K聚类算法中，一个粒子表示一种聚类划分的情况，粒子的每一维表示聚类一个簇的质心，任意粒子i定义如下：

xi=(mi1,…,mij,…mik)

其中mij为第i个粒子所表示的第j个簇Cij的质心；

算法初始化m个粒子，粒子的维数为k，随机分配粒子的位置，将每个粒子作为一个候选划分。对于每个粒子，根据最小距离原则，将聚类的数据对象划分在以粒子各维为质心的簇中。运用FWPSO算法迭代运算，每次迭代均更新聚类数据划分，直至求出最优粒子。该最优粒子的位置表示最优聚类划分的簇质心。

3.3 结合算法的算法描述

1. 初始化m个j维粒子的粒子群，随机产生粒子的速度；

2. 对每个粒子，按照最小距离原则，将聚类的数据对象划分在以粒子各维为质心的簇中，计算各个粒子的适应度值；

3. 对每个粒子，比较其当前适应度值和其经历过最好位置的适应度，若干当前适应度更好，则更新最好位置；

4. 对每个粒子，比较其当前适应度值和群体经历最好位置的适应度，若干当前适应度更好，则更新全局位置；

5. 根据式（5）和式（6）调整粒子的速度和位置；

6. 当达到最大迭代次数或粒子群达到收敛状态，则该最优粒子的位置表示最优聚类划分的簇质心

7. 结束

4 结束语

本文基于粒子群粒子适应度差异提出了适应度权重这一概念，并以此为核心提出了一种基于适应度权重的改进粒子群算法。并将该改进算法与K-means聚类算法结合，结合聚类算法克服了K-means算法的缺点，提高了算法的有效性和算法效率。

参考文献

[1] Jiawei Han，Michelin. Camber．数据挖掘概念与技术[M]，机械工业出版社，2007.3

[2] Shi Y ， Ebethart R C．Empirical study of Particle swarmoptimization[A] ． In ： Proceedings of the 1999 Congress onEvolutionary Computation[C]. Piscataway，NJ：IEEE Service Center，1999：1945-1950．

[3] 王万良，唐宇，微粒群算法的研究现状与展望[J]，浙江，浙江工业大学学报，2007，35(2)；136-141.

作者简介：

钱伟强（1982-），西安电子科技大学在读研究生，讲师，工作单位：陕西交通职业技术学院，从事计算机数据库方向教学工作。