基于改进布谷鸟搜索的k-means算法的离群点检测

庄丽丽，石鸿雁

(沈阳工业大学理学院，辽宁 沈阳 110870)

0 引 言

离群点检测作为数据挖掘的基本任务之一，该技术的目的在于通过分析离群点的分布特征，高效准确地从海量的数据中挖掘出异常的数据信息[1-2]。传统的离群点检测方法一般分为4类：基于统计学的、基于分类的、基于聚类的和基于密度的[3]。目前，离群点检测技术被应用于诈骗检测、图像处理、异常模式检测等许多领域。k-means算法作为一种经典的聚类算法[4-5]，近年来被广泛地应用于离群点检测领域。基于k-means算法的离群点检测方法简单、高效，可以快速地检测出离群数据，但同时该离群点检测算法对初始聚类中心敏感，导致检测结果出现误差。为了解决这一问题，很多学者将仿生智能优化算法运用于传统k-means算法的离群点检测中，产生了许多k-means算法的离群点检测的衍生算法。例如:傅涛等人[6]将粒子群优化算法(PSO)与k-means算法结合，用于入侵检测，克服了k-means算法容易受到初始聚类中心的影响这一缺点；于佐军等人[7]将蜂群算法用于k-means算法中，提高了算法的收敛速度，消除了算法受初始聚类中心的影响可能。但粒子群和人工蜂群算法参数较多，而且与k-means算法结合后的算法在求解精度方面没有明显改善。

而本文提到的布谷鸟搜索算法(Cuckoo Search, CS)作为一种新型启发式算法，该算法模拟布谷鸟需要寻找宿主鸟窝孵化鸟蛋这种寄生现象的过程，具有参数少、操作简单以及全局寻优能力强的优点。但同时也存在一些缺点：受莱维飞行随机游走的盲目性的影响，在搜索过程中容易陷入局部最优，并且收敛速度慢[8]。为了CS算法的发展与应用，国内外许多学者对CS算法进行了改进研究。例如：Gherboudj等人[9]提出了一种离散二进制布谷鸟搜索算法来处理二进制优化问题；Ouyang等人[10]提出了离散布谷鸟算法，用于解决球形旅行商问题；Wang等人[11]将混沌理论引入CS算法，提出了一种新颖的混沌布谷鸟搜索优化算法等。但这些改进算法并没有平衡局部搜索与全局搜索之间的关系。于是，本文首先对CS算法中的发现概率Pa和莱维飞行步长做自适应改进。通过实验，结果表明改进的CS算法在迭代次数、求解精度、解空间范围等方面优于原始的CS算法。然后将改进后的布谷鸟搜索算法(Improved Cuckoo Search, ICS)与传统的k-means算法的离群点检测相结合，提出一种基于改进布谷鸟搜索的k-means算法的离群点检测(Outlier Detection Based on Improved Cuckoo Search k-means Algorithm, ICS-KM-OD)算法，可解决传统k-means算法的离群点检测易受初始聚类中心的影响陷入局部最优的问题。通过在3个UCI数据集上的实验表明，本文的离群点检测算法能够获得更好的性能指标，其收敛速度和检测效果都得到了改善。

1 相关算法

1.1 基于k-means算法的离群点检测

(1)

其中，d为样本维度，nj为聚类结果中第j个类的类内样本个数，k为聚类参数。

1.2 CS算法

CS算法是以布谷鸟的寄巢产卵特点及少部分生物的莱维飞行模式为参照，具有迭代搜索的特征。其主要思想是通过随机行走方式产生候选鸟巢以及偏好随机游走策略更新鸟巢位置，最终使鸟巢位置达到或者接近全局最优解[13]。CS算法具体思路如下。

基于文献[14]中CS算法的3个理想状态，布谷鸟寻找宿主鸟巢的位置和路径的更新公式如下：

(2)

(3)

通过公式(2)进行位置更新后，生成随机数r(r∈[0,1])。将r与Pa进行比较，若r>Pa，则利用莱维飞行偏好游走策略随机更新一次鸟巢位置，否则鸟巢位置不变。莱维飞行的偏好随机游走策略如下[15]：

(4)

2 改进布谷鸟搜索ICS算法及其收敛性分析

2.1 布谷鸟算法的改进

经过研究发现，CS算法中发现概率和莱维飞行步长影响着搜索范围、收敛速度和搜索精度。因此本文对CS算法的发现概率和步长进行自适应调整，并给出使发现概率和步长随算法进程动态变化的自适应策略。

1)发现概率Pa的自适应策略。

CS算法中发现概率Pa平衡着全局搜索和局部搜索。将Pa取固定值不利于全局搜索与局部搜索之间的平衡，因此有必要给出Pa的自适应策略：

(5)

公式(5)实现了Pa随算法进程由小到大的动态变化，使得改进后的算法在运行前期能够保持很好的全局搜索能力，同时兼顾局部搜索，而在后期，局部搜索逐渐增强，兼顾全局搜索，提高了算法收敛速度，避免陷入局部最优。

2)莱维飞行步长的自适应策略。

在莱维飞行机制中，步长的大小主要是通过步长因子α来体现。固定步长因子会影响算法的搜索速度和精度。本文给出一种步长的自适应策略：

(6)

其中，ti为当前迭代次数,tmax为最大迭代次数。此时，公式(2)修改为：

(7)

公式(7)实现了搜索前期范围扩大，收敛速度加快，在搜索后期步长逐渐减小，局部搜索能力增强，提高了搜索的精度。

改进的布谷鸟搜索算法的步骤如下。

步骤3 位置更新后，生成随机数r(r∈[0,1])，并将r与Pa进行比较，若r>Pa，就根据公式(4)随机更新一次鸟巢位置，否则鸟巢位置不变。

2.2 ICS算法的收敛性

本节从随机算法全局收敛准则的角度出发，并结合Markov链模型，对ICS算法收敛性进行证明和分析[16]。

2.2.1 ICS算法的Markov模型

Markov链理论是仿生智能算法收敛性分析的重要手段，已经成功应用在蚁群算法、遗传算法、粒子群算法等随机收敛性分析中。下面建立ICS算法的Markov链模型。

定义1 鸟巢位置的状态和状态空间。鸟巢位置构成了鸟巢状态，记作x,x∈A,A为可行解空间。鸟巢位置所有可能状态组成的集合构成了鸟巢位置的状态空间，记为X={x|x∈A}[17]。

定义2 鸟巢位置的群状态和群状态空间。鸟巢位置群中所有鸟巢的状态构成了鸟巢位置群状态，记作s=(x1,x2,…,xN)，其中xi表示第i个鸟巢位置的状态。鸟巢位置群中所有可能状态组成的集合构成鸟巢位置群状态空间，记为S={s=(x1,x2,…,xN)|xi∈X,1≤i≤N}。

定义3 鸟巢位置的状态转移。∀xi,xj∈X，在ICS算法迭代中，鸟巢位置的状态从xi转移到xj，记为T(xi)=xj。

命题1 在ICS算法中，鸟巢位置状态从xi转移到xj的转移概率为P(T(xi)=xj)。其表达式为P(T(xi)=xj)=P(xi→x′i)P(x′i→xj)，其中P(xi→x′i)是通过ICS算法中公式(7)的位置转移的概率，P(x′i→xj)表示被发现后通过偏好随机游走所产生的位置转移概率。

证明：假设鸟巢位置状态从xi转移到xj的过程中，它们之间有一次的中间转移状态x′i,此时P(T(xi)=xj)为：

P(T(xi)=xj)=P(xi→x′i)P(x′i→xj)

(8)

由位置更新公式(7)可知，鸟巢位置状态xi→x′i的转移概率为：

(9)

其中：

(10)

由于x、g是多维数据，公式(9)中的绝对值表示超空间立方体的体积。

由文献[14]布谷鸟算法的理想状态(3)结合ICS算法的步骤3可知，鸟巢位置状态x′i→xj的概率为：

(11)

其中：

(12)

定义4 鸟巢位置群状态转移。在ICS算法迭代中，∀si=(xi1,xi2,…,xiN)∈S, ∀sj=(xj1,xj2,…,xjN)∈S，鸟巢位置的群状态从si到sj，记作T(si)=sj。

命题2 在ICS算法中，鸟巢位置的群状态从si转移到sj的转移概率为：

(13)

证明：鸟巢位置群状态包含了所有鸟巢位置状态。当鸟巢位置群状态从si转移到sj时，群状态中所有位置状态都会同时转移，即T(xi1)=xj1,T(xi2)=xj2,…,T(xiN)=xjN同时成立，则鸟巢位置群状态转移的概率为：

P(T(si)=sj)=P(T(xi1)=xj1)P(T(xi2)=xj2)…P(T(xiN)=xjN)

(14)

定理1 ICS算法中鸟巢位置群状态序列{s(t):t≥0}，是有限齐次Markov链。

证明：算法的搜索空间是有限的，鸟巢位置状态xi是有限的，因此鸟巢位置状态空间X也是有限的。群状态s=(x1,x2,…,xN)是由N个鸟巢位置状态组成，N为有限正整数，则鸟巢位置的群状态空间S也是有限的。由命题2可知群状态序列{s(t):t≥0}中，∀s(t-1),s(t)∈S，其转移概率P(T(s(t-1))=s(t))是由鸟巢群体中所有鸟巢位置的转移概率P(T(x(t-1))=x(t))决定，由命题1可知转移概率与t-1时刻的状态相关，而与时间t-1无关，即鸟巢的群体状态有Markov性和齐次性，而状态空间为可列集，因此其构成一个有限齐次Markov链[18]。

2.2.2 ICS算法的收敛性分析

定义5 设优化问题〈A，f〉全局最优解为g*，定义鸟巢位置最优状态集M={s*=(x)|f(x)=f(g*),x∈A,s∈S}。

引理1 ICS算法中，对鸟巢位置群状态序列{s(t):t≥0}而言，最优状态集M是群状态空间S上的闭集。

证明：∀si,sj∈M，对于任意转移步长l,l≥1，由Chapman-Kolmogorov方程可得：

P(T(sr1)=sr2)…P(T(sr(l-1))=sj)

(15)

(16)

引理2 鸟巢位置的群状态空间S中不存在非空闭集B，使得B∩M=∅。

证明：用反证法。假设鸟巢位置群状态空间S中存在非空闭集B，且B∩M=∅，则设si=(g*,g*,…,g*)∈M, ∀sj=(xj1,xj2,…,xjN)∈B，有f(xjc)>f(g*)，由命题1和命题2可得，对每个P(T(sj)=si)都有P(T(xj)=xi)=P(xj→x′j)P(x′j→xi)，由于P(xj→x′j)P(x′j→xi)>0，则P(T(xj)=xi)≠0，因此B不是闭集，这与假设矛盾。因此群状态空间S中不可能存在M之外的非空闭集。

由上述引理1～引理3可知，当群内部迭代次数趋于无穷时，群状态序列一定会进入最优状态集M。

定理2 ICS算法收敛到全局最优。

证明：由于ICS算法的适应度函数是非递增的，所以ICS算法满足文献[16]中随机算法收敛准则假设1，由上述结论可知，ICS算法满足文献[16]中随机算法收敛准则假设2，故ICS算法收敛于全局最优。

3 基于改进布谷鸟搜索的k-means算法的离群点检测

基于改进布谷鸟搜索的k-means算法的离群点检测ICS-KM-OD算法利用ICS算法克服了传统k-means离群点检测容易受到初始聚类中心影响的缺点。该算法首先在原始布谷鸟搜索算法的基础上，基于发现概率和步长进行自适应改进，使其摆脱收敛速度偏慢、求解精度低的缺陷；然后将改进后的布谷鸟搜索算法与基于k-means的离群点检测算法进行并行融合，解决原始k-means算法受初始聚类中心影响陷入局部最优问题。

在离群点检测算法过程中通常采用适应度函数来评价检测结果，本文采用欧氏距离度量的方法，实现样本数据的k-means划分。样本x与样本y的距离公式为：

(17)

因此适应度函数为：

(18)

其中，λ为任意实数，cj(j=1,2,…,k)为聚类中心。显然适应度值越大，划分效果越好[21-23]。

3.1 ICS-KM-OD算法步骤

步骤1 给定待检测数据集和初始聚类参数k。

步骤2 在待检测数据集中随机选取n个数据样本作为初始鸟巢位置，并且设置初始参数。

步骤3 进行k-means聚类划分，计算每个鸟巢的适应度值并保留最优鸟巢。

步骤4 按照改进的布谷鸟搜索算法对其他的鸟巢进行更新。

步骤5 根据更新后的鸟巢进行k-means划分并求新的适应度值，将更新后的鸟巢与上一代鸟巢进行对比，若更好则代替。

步骤6 按发现概率Pa抛弃鸟巢并重建。

步骤7 进行k-means划分并计算鸟巢的适应度，选出最好的鸟巢，与目前的最优鸟巢对比，若更好，则将此鸟巢置为最优鸟巢。

步骤8 如果未达到最大的迭代次数或不满足终止条件则返回步骤4继续执行；否则输出最优的聚类中心点、簇内距离和簇间距离。

3.2 仿真结果

实验的仿真环境为Windows 10操作系统，Intel 2.20 GHz CPU, 4 GB RAM，仿真软件为Matlab 2017a。

实验1 改进后的布谷鸟搜索算法(ICS)的仿真实验。

本文选取4个基准测试函数对ICS进行仿真测试，将其实验结果与原始CS算法进行对比，以验证其收敛性能和寻优能力。参数设置和测试函数如表1和表2所示。

表1 实验参数

表2 测试函数

1)为了验证ICS算法的收敛性能，本文选取4个测试函数进行试验仿真，将其实验结果与原始的CS算法进行比较。图1给出了2种算法对各测试函数的收敛曲线。从图1(a)～图1(c)可以看出，对于测试函数f1、f2、f3来说，ICS算法的最小适应度值明显比CS算法下降得快；从图1(d)可以看出，由于函数本身比较复杂，容易陷入局部最优，ICS算法的精度虽然不高但还是优于CS算法，在迭代500次后，最小适应度值明显比CS算法下降得快。因此，ICS算法在收敛速度上优于CS算法，较好地解决了原始CS算法收敛速度慢的问题，改善了全局寻优能力。

(a) f1

(b) f2

(c) f3

(d) f4

2)为了验证ICS算法的优越性，分析其寻优效果，将ICS算法与CS算法在不同维度进行多次独立的实验，对比结果如表3～表5所示。从表3可以看出，在10维的条件下，对测试函数f1和f2，2种算法都能达到所要求的精度，但ICS算法的运行时间和迭代次数明显少于CS算法，对测试函数f3和f4，ICS算法的优势更加明显，可以更快地达到目标精度。从表4可以看出，在30维的条件下，对于测试函数f1和f2，ICS算法有更好的搜索精度，并且迭代次数最少，对测试函数f3，ICS算法以最快的速度收敛至全局最优，而此时CS算法无法收敛于全局最优，对测试函数f4，虽然2种算法的寻优能力相差不大，但ICS算法的计算结果要优于CS算法。从表5可以看出，在50维的条件下，对于测试函数f1，CS算法无法收敛于全局最优，但ICS算法却以最快的速度收敛于全局最优，并且可以较快地达到目标精度，对测试函数f2和f3，2种算法都可以收敛于全局最优，但ICS算法在收敛速度和计算精度上有明显的优势，对测试函数f4，虽然ICS算法和CS算法都没有达到目标精度，但ICS算法具有更快的收敛速度。

表3 10维情况下算法性能比较

表4 30维情况下算法性能比较

表5 50维情况下算法性能比较

实验2 基于改进布谷鸟搜索的k-means算法的离群点检测的仿真实验。

为了验证基于改进布谷鸟搜索的k-means算法的离群点检测的有效性，本文选择UCI中标准数据集Iris、Wine与Synthetic进行测试分析。数据集的基本信息如表6所示。

表6 测试数据集

对基于k-means算法的离群点检测(KM-OD算法)、基于布谷鸟搜索的k-means算法的离群点检测(CS-KM-OD算法)和本文的基于改进布谷鸟搜索的k-means算法的离群点检测(ICS-KM-OD算法)进行仿真实验。其中CS-KM-OD算法中的鸟巢发现概率Pa=0.25，步长因子α=1，鸟巢规模为20，迭代次数为20。3种算法分别在各数据集上运行10次。在此基础上计算出各算法在各数据集上的适应度值、运行时间以及精确度。

由表7可知，从整体分析这3种算法在3个数据集上的收敛性，本文的ICS-KM-OD算法的适应度函数值较大并且波动范围小。与KM-OD算法相比，无论是在低维数据集Iris上还是在高维数据集Wine和Synthetic上，本文算法的检测效果都有明显的提高。对比CS-KM-OD算法，虽然适应度函数值相差不大，但也有所提高，这是由于本文算法在搜索过程中考虑了鸟巢本身的特性——适应度高的鸟巢周围更容易发现最优鸟巢，在鸟巢的更新过程中加入了自适应发现概率和步长，有效地控制了算法前后期的搜索范围和搜索速度，提高了搜索精度，使得算法的寻优能力更好。由表8可以看出，本文的ICS-KM-OD算法在运行时间上和CS-KM-OD算法相当，但却优于KM-OD算法，主要是因为本文算法运用了莱维飞行搜索机制，算法的参数少，结构简单，有更快的计算速度。

表8 在3个数据集上各算法的平均运行时间对比 单位：s

表7 在3个数据集上各算法的适应度值对比

由表9可以看出，从3个数据集上的算法精确度的角度分析，本文提出的ICS-KM-OD算法得到了较好的检测精确度，相比于KM-OD算法的效果最为明显，在3个数据集上精确度分别提高了12.1个百分点、4.6个百分点和5.3个百分点。对比CS-KM-OD算法，在数据集Iris上改善效果最好，提高了2.2个百分点，其次是数据集Synthetic，增加了1.2个百分点。这是由于KM-OD算法容易受到初始聚类中心的影响，导致最终结果波动性大造成的。而本文提出的ICS-KN-OD算法在一定程度上消除了算法对初始聚类中心的敏感度，从而提高了算法精确度。

表9 算法精确度对比

4 结束语

本文利用布谷鸟搜索解决了传统k-means算法的离群点检测易受初始聚类中心的影响陷入局部最优的问题。首先，对原始的布谷鸟搜索进行自适应改进，并且讨论了改进后的布谷鸟搜索算法的收敛性问题，同时对改进后的布谷鸟搜索算法进行实验仿真，结果表明，改进后的算法有效地均衡了算法运行前后期的搜素范围和精度，提高了算法的收敛速度。其次将改进后的布谷鸟搜索算法与传统的k-means算法的离群点检测融合，提出了一种基于改进布谷鸟搜索的k-means算法的离群点检测。最后将本文提出的离群点检测算法与基于k-means算法的离群点检测算法及基于布谷鸟搜索的k-means算法的离群点检测算法进行实验数据仿真，结果验证了本文的算法无论在收敛速度还是检测精度上都优于其他2种离群点检测算法。