基于改进磷虾群算法的K-means算法

刘 唐 ，周 炜， 李志鹏，权 文

(1.空军工程大学，陕西 西安 710051；2.西安财经学院行知学院，陕西 西安 710038；3.中国人民解放军75837部队，广东 广州 510630)

0 引言

聚类是一种常用的无监督学习方法[1]，广泛应用于入侵检测、机器学习、图像处理、数据挖掘等领域。聚类试图将数据中的样本划分为若干类，使同一类的样本尽可能彼此相似，不同类的样本尽可能不同。通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。

K-means算法作为一种基于中心的经典聚类算法，结构简单、收敛速度快，但易受初始聚类中心选择的影响，导致陷入局部最优，使聚类结果不稳定[2]，初始类别数的设定直接影响聚类结果的优劣。而实际情况中，最佳聚类数很难预知，算法自身自动得到最佳聚类数就尤为重要。

群智能优化算法是一种模拟自然界的生物活动以及群体智能行为的计算智能算法。常用的算法有粒子群算法、蚁群算法、遗传算法、人工蜂群算法等。Gandomi等人在研究自然界磷虾群觅食活动的规律后，于2012年提出了一种新型的群智能优化算法——磷虾群(Krill Herd，KH)算法[3]，该算法结构简单、需要控制的参数少、收敛速度快。群智能优化算法因其具有极好的全局寻优能力而常被应用于聚类领域，文献[4—5]提出了应用粒子群算法来优化聚类算法，文献[6—7]提出了一种采用蚁群算法来解决聚类问题，文献[8]提出了遗传算法的聚类算法，文献[9—10]采用人工蜂群算法来解决聚类问题。

针对磷虾群算法易陷入局部最优、搜索能力弱，及K-means算法易受初始聚类中心选择影响的问题，提出了改进磷虾群算法的K-means算法。该算法先对磷虾群算法进行改进，改善算法性能，再用改进后的磷虾群算法优化K-means算法的聚类中心，降低初始聚类中心的影响，避免陷入局部最优，提升算法的稳定性，同时引入聚类综合有效性评价函数自动得到最佳聚类数。

1 聚类与标准磷虾群算法

1.1 聚类概述

聚类问题通常是给定一个数量为m的样本集D={x1,x,…xm}，将其聚类划分为k个不同类C={C1,C2,…,Ck}，这里聚类目标函数取均方误差：

(1)

式(1)中，zj为聚类中心，E值越小，聚类效果越好。

1.1.1K-means算法

K-means算法的主要流程具体如下：

1)从样本集D中随机选择k个样本作为初始聚类中心；

2)计算各样本与各聚类中心的距离：dji=‖xi-zj‖2，根据距离远近把各样本划入相应的聚类；

3)计算更新聚类中心：

(2)

重新转入2)计算。

1.1.2聚类有效性评价

为了与最小化聚类间的相似度和最大化聚类内相似度的目标相符合，本文用聚类结果分布的自然属性来评价聚类间的分离性和聚类内的同一性，构造聚类综合有效性评价函数，利用此函数分析不同情况下的聚类效果，获得最佳聚类数[11]。

聚类密集性与聚类内方差有关，给定样本集D={x1,x2,…,xm}，聚类内方差定义为：

(3)

根据聚类结果分布，聚类密集性定义为：

(4)

由此可以看出聚类内方差越小，聚类密集性越好，数据样本的同一性越高。特殊的某一样本个体被单独分为一类，则聚类密集性取值为0。

聚类邻近性定义为：

(5)

式(5)中，d(zi,zj)表示聚类中心zi与聚类中心zj之间的欧氏距离，σ是高斯常数，聚类邻近性与聚类间距离成反比，即邻近性越小越好。特殊的某一样本个体被单独分为一类，则聚类邻近性取值为0。

综合以上聚类密集性与聚类邻近性构造出聚类综合有效性评价函数：

Cp=1-[α×Cv+(1+α)×Prox]

(6)

式(6)中，α∈[0,1]，聚类综合有效性评价函数Cp值越大说明聚类效果越好。

1.2 标准磷虾群算法

磷虾群算法[12-14](krill herd，KH)是一种模拟磷虾群觅食行为的启发式优化算法，以每只磷虾表示问题的可能解，通过模拟每只磷虾觅食过程中位置的不断更新来寻找最优解。

在KH算法中，将磷虾个体的移动主要分为以下三个部分，其第k次的移动可表示为：

(7)

(8)

(9)

(10)

(11)

式(11)中，Dmax为的最大随机扩散速度，Imax为最大迭代次数，δi为当前的随机扩散方向向量，且为[-1,1]区间的随机数。

每只磷虾在上述3种因素的综合影响下，不断更新自身位置，直至当前最优磷虾位置对应的解符合条件要求或达到最大迭代次数后停止。

2 改进的磷虾群算法

作为启发式的智能优化算法，磷虾群算法在周围磷虾的引导运动和磷虾本身的觅食运动中都体现出全局寻优能力和局部探索能力[15]。算法必须协调好两者之间的关系，才能使得算法性能更好地发挥。

在迭代次数增加到一定后，大多数磷虾都会向同一方向运动，从而导致磷虾群的个体特异性降低，易陷入局部最优。迭代过程中磷虾群的历史最优解信息未存储，导致在最大迭代次数时得到的最优解未必是真正最优解，这可能造成算法的稳定性能下降。本文提出一种动态分群策略，并在迭代过程中引入精英引领机制，在磷虾本身的随机扩散运动中添加一种随机变异因子对算法进行改进[16-17]。

2.1 混沌初始化

在磷虾群算法寻优过程中，编码形成的初始种群的聚散程度与分布关系到整个解空间的均匀程度，将影响算法的寻优性能，导致聚类效果不理想。本文首先随机生成k个混沌序列初始值Xi(0)，再利用Logistic混沌映射：

Xi(n+1)=μXi(n)[1-Xi(n)]

(12)

迭代生成若干新的混沌序列。其中μ为混沌映射参数，μ∈[1,4]，Xi(n)是第n次迭代时的位置。

通过混沌映射生成的混沌序列Xi可以覆盖整个解空间，计算生成的混沌序列的适应度值，选出N个适应度较优的混沌序列获得规模为N的初始种群。这种生成策略既能保证种群初始化的多样性、随机性，又有利于通过混沌映射实现对整个解空间的遍历。

2.2 动态分群

在磷虾群算法寻优过程中，随着迭代次数增加，磷虾群会向局部最优逼近，寻优范围逐渐减小，可能导致磷虾群个体位置更新变慢甚至停滞，算法出现早熟现象。因此，考虑每次迭代后，通过混沌映射来改变磷虾群个体位置，遍历解空间来避免陷入局部最优，但这必定会造成重复搜索，计算量增大，降低算法效率。针对这种情况，本文提出一种动态分群策略，根据适应度值的大小把磷虾群划分成不同的类，再对不同的类采取相应的调整机制，使得避免早熟的同时减少重复搜索，提高算法效率。

动态分群依据磷虾群个体适应度将每次迭代的种群分为退化磷虾、常规磷虾、精英磷虾。主要按照以下策略分群：

对不同的类采取相应的调整机制：

1)退化磷虾是当前磷虾群中适应度值较差的个体，可能会对磷虾群的优化造成阻碍，使算法效率降低。因此，考虑通过混沌映射生成新的混沌序列，并将退化磷虾用新的适应度较好的混沌序列替换来改进，对退化磷虾进行混沌映射的具体过程如下：首先，按照前面混沌初始化方法生成新的混沌序列；然后迭代计算各新的混沌序列的适应度值并记录最优值；最后达到最大迭代次数后，比较当前种群的最优磷虾与新的最优混沌序列，若新的序列适应度更好，则将退化磷虾当前的最优磷虾用新的最优混沌序列替换，否则用此序列随机替换当前种群的某一磷虾个体。

2)常规磷虾是介于退化磷虾与精英磷虾之间的磷虾个体，在迭代过程中随机性很大，对此采用双边引导，即在基本搜索的同时进行混沌映射，使其可以在更大范围搜索。

3)精英磷虾是当前种群中适应度值较优的磷虾个体，与最优解的距离较近，因此让其继续按照标准磷虾群算法进行搜索。

2.3 精英引领与随机变异

在标准磷虾群算法迭代过程中，随着迭代次数的增加，磷虾种群逐渐逼近最优，但是由于磷虾本身的随机扩散运动的不确定性，并不能保证各磷虾都向最优方向逼近，使得后面迭代磷虾的最优并不一定是历史最优，可能导致最终的最优解不是全局最优解。

针对这个问题，首先在迭代过程中引入精英引领机制：在更新当前磷虾个体位置前，对比各磷虾个体的适应度值，取适应度最优的磷虾个体为精英并记录，在迭代更新当前磷虾个体位置后，再将当前磷虾个体与精英对比，选择适应度更优的作为新的精英并记录。从而确保算法迭代结束时，得到的最优解是历史最优解。其次，再对磷虾本身的随机扩散运动添加一种随机变异因子进行改进。本文引入的随机变异因子λ，如下：

λ=μ·fit

(13)

(14)

易知，磷虾本身的随机扩散幅度由μ和fit一起决定。在算法迭代的前期，μ值较大，能产生较大幅度的变异，使求参数最优解的全局遍历能力增加，随着迭代次数的增加，μ值逐渐减小，全局磷虾本身的随机扩散幅度减小，而磷虾个体在自身周边搜索较精确，此时算法就有较好的局部探索能力，加快了收敛速度。在算法迭代的后期，磷虾个体都会向全局最优的位置逼近，易陷入局部最优。而此时较大fit值的磷虾就拥有较强的随机变异能力，这些磷虾能有更大随机扩散幅度，这样就增加了磷虾个体的特异性，使得算法寻优范围扩大，避免陷入局部最优。

精英引领机制和随机变异因子λ的引入综合考虑了迭代过程和磷虾个体的具体情况，使得磷虾的变异具有目的性和多样性，加快了收敛速度，同时更好地避免了算法陷入局部最优，增加了算法的稳定性。

3 改进磷虾群算法的K-means算法

遵循K-means算法的基本聚类准则，用改进后的磷虾群算法优化K-means算法的聚类中心，降低初始聚类中心的影响，获得在不同聚类数下的聚类情况，同时引入聚类综合有效性评价函数自动得到最佳聚类数。

这里选取均方误差E为适度函数fit，即

(15)

用改进后的磷虾群算法优化K-means算法的聚类中心，主要是因为磷虾群算法是一种不受初始值影响的随机优化算法，同时拥有全局寻优能力和局部探索能力，可以避免陷入局部最优，使得可以在全局寻优空间中获得的聚类中心有较小的均方误差，并通过改进磷虾群算法使得结果尽可能向最优逼近。而且由于对数据划分是按照与聚类中心的欧氏距离最小准则，则聚类中心的细微差别对结果不会有太大的影响，那么用改进后的磷虾群算法优化K-means算法的聚类中心得到的结果就可以当作最佳聚类结果。再通过聚类综合有效性评价函数可以自动得到对应情况下的最佳聚类数。

算法的主要流程：

1)规定聚类数的取值范围，令初始聚类数k=2；

2)根据当前聚类数对样本数据进行混沌初始化，再计算聚类目标函数获得并记录当前最优解；

3)循环迭代进行改进磷虾群算法的三个运动，循环迭代结束得到本次操作的最优聚类结果，并计算聚类综合有效性评价函数Cp；

4)令k=k+1，当k

5)按照聚类综合有效性评价函数Cp计算最佳聚类数，然后获得对应的聚类结果。

4 实验结果与分析

实验主要验证了算法以下两方面性能：改进的磷虾群算法的寻优能力；改进磷虾群算法的K-means算法获取最佳聚类数的性能。

4.1 改进磷虾群算法寻优性能分析

本文将改进磷虾群算法(IKH)与标准磷虾群(KH)、协同人工蜂群算法(CABC)、混合遗传算法(HGA)、协同粒子群算法(CPSO)进行比较，通过多种基准函数[10,18]来测试算法的性能。

种群规模设定为100，limit=100，所有样本变量维数设定为30，以函数评估次数FEs(function evalutions)为评测标准 (FEs≤100,000)。表1是IKH与几种算法在基准函数下的均值和标准差(算法运行30次，部分算法结果来自文献[10,18])。

表1 IKH与几种算法性能对比

由表1可知，对于实验的6种基准函数，KH算法在2种基准函数的结果为性能最优，CPSO算法在基准函数Schwefel的结果表现最优，而IKH算法在其中5种基准函数的结果表现性能最优，其他算法性能略差。IKH算法与KH算法单独相比，IKH算法在4种基准函数上性能更优。纵观全局，IKH算法在实验中更好地避免陷入局部最优，整体性能表现最优。

4.2 最佳聚类数寻找性能分析

实验通过人造数据和UCI机器学习数据集来测试验证算法在最佳聚类数寻找的效果。实验数据有人造数据S及Iris、Wine、Glass、Synthetic，如表2所示。

验证算法的聚类正确率时，根据数据集资料先给出其标准聚类数，验证算法最佳聚类数寻找性能时，记录运行20次得到正确的最佳聚类数的次数，具体情况见表3。

表2 数据集描述

表3 各类数据集运行20次的情况

由表3可知，本文算法在人造数据集和UCI真实数据都有较好的聚类正确率，而对于最佳聚类数寻找，本文算法对分离性能较好的人造数据集S和真实数据集Iris效果良好，对于其他数据集，也能找到标准最佳聚类数，效果较好，但有待进一步提高。总体来看本文算法性能较好，能够适用各类数据集。

5 结论

本文提出了基于改进磷虾群算法的K-means算法，该算法通过混沌初始化、动态分群、精英引领和随机变异策略对磷虾群算法进行改进，协调好算法的全局寻优能力和局部探索能力，提高了算法的综合寻优能力。实验验证表明，改进磷虾群算法在保证较快收敛速度的基础上提升了全局寻优能力，与其他算法进行性能对比分析，该算法各方面性能优势明显。再针对K-means算法的缺点提出改进磷虾群算法的K-means算法，并引入最佳聚类数自适应机制，通过实验测试验证了算法的有效性。