基于自适应布谷鸟搜索算法的K—means聚类算法及其应用

杨辉华　王克　李灵巧　魏文　何胜韬

摘要：针对原始K-means聚类算法受初始聚类中心影响过大以及容易陷入局部最优的不足，提出一种基于改进布谷鸟搜索（CS）的K-means聚类算法（ACS-K-means）。其中，自适应CS（ACS）算法在标准CS算法的基础上引入步长自适应调整，以提高搜索精度和收敛速度。在UCI标准数据集上，ACS-K-means算法可得到比K-means、基于遗传算法的K-means（GA-K-means）、基于布谷鸟搜索的K-means（CS-K-means）和基于粒子群优化的K-means（PSO-K-means）算法更优的聚类质量和更高的收敛速度。将ACS-K-means聚类算法应用到南宁市青秀区“城管通”系统的城管案件热图的开发中，在地图上对案件地理坐标进行聚类并显示，应用结果表明，聚类效果良好，算法收敛速度快。

关键词：数据挖掘；K-means聚类；布谷鸟搜索算法；数字城管；热图

中图分类号：TP391； TP183

文献标志码：A

0引言

随着我国数字化城市管理事业建设的推进，基于城市管理综合数据的智慧城市应用越来越受到重视。数字城管系统在建设与运行的过程中，不断丰富了城市管理的基础数据，如基础地形图、卫星遥感影像数据、城市管理部件数据、城市管理案件数据等。这些庞大的城市管理综合数据为数据的空间分析、聚类分析、辅助决策等提供了重要载体。而如何从海量的城管数据中发掘出有用的信息为城市管理所运用已成为目前智慧城市建设中研究的热点问题之一。利用数据挖掘技术从城市管理的案件地理数据中发现隐含的有用信息，从时间维度和空间维度分析城市管理问题的高发时段、高发区域，分析城市管理问题的发生、发展等动态变化过程，这在灾害天气频发时进行实时预警、对领导决策提供辅助等方面能起到重要作用。

数据挖掘作为一个热门的多学科交叉应用领域，正在各行各业中扮演着重要的角色。人们可以通过数据挖掘技术从大量的原始数据中提取、发现有重要价值的信息，并应用于实际的生产中。常用的数据挖掘方法有分类、估计、预测、相关性分组、聚类等。聚类分析是一种常用的无监督数据挖掘方法。K-means算法作为一种经典的聚类算法具有简单高效等优点，因此得到广泛应用。因此，在汇集城市案件地理坐标数据的基础上，通过K-means聚类分析算法分析出案件在城区的分布规律，通过热图的形式直观地展现出来，这对于部门领导制定相关策略具有重要的意义。

然而，原始的K-means聚类算法存在对初始聚类中心的选择比较敏感、聚类结果不稳定等缺陷[1]。因此，原始的K-means聚类算法对城市案件地理位置数据的聚类分析效果不是很理想。近年来出现了一些对原始K-means算法改进的新算法。其中，一个重要的研究方向就是将一些元启发式优化算法与K-means算法相结合，利用优化算法的全局优化能力来改善K-means算法的聚类结果。

布谷鸟搜索（Cuckoo Search， CS）算法[2]是一种新型元启发式算法，它采用Lévy飞行搜索机制，具有很强的全局搜索能力。此外，CS算法还具有输入参数少、结构简单、易于实现等优点[3]；但CS算法也存在着局部搜索能力较差、后期收敛速度慢等缺点[4]。因此，陆续出现了一些对原始CS算法的改进算法[5-8]，如动态适应的CS算法[9]、逐维改进的CS算法等[10]。由于CS算法中的步长因子很大程度上控制着算法的搜索精度，因此，本文采用新的自适应的步长因子来改进原始CS算法，使得该算法能够在全局搜索和局部搜索之间保持很好的平衡，提高CS算法的收敛速度。

本文首先在CS算法的基础上，对算法中Lévy飞行的步长控制量α作自适应调整，提出自适应CS（Adaptive Cuckoo Search， ACS）算法；然后，将ACS算法引入K-means聚类算法，利用ACS算法对聚类中心进行优化，提出了一种基于改进布谷鸟搜索算法的K-means聚类算法（ACS-K-means）；最后，将该算法应用于南宁市青秀区“城管通”系统[13]案件数据的聚类分析，并结合热图技术开发了城管决策辅助系统[12]，有助于相关领导快速作出决策，提高城管系统的运行效率。

1 K-means聚类算法

K-means聚类算法是一种基于划分的经典聚类算法。该算法的流程如下：

1）从n个数据样本中任意选取k个样本作为初始的聚类中心点；

2）根据每个聚类的均值（即中心样本），计算每个样本与这些中心样本的距离，并根据最小距离对样本进行划分；

3）重新计算每个有变化的聚类的均值。

重复步骤2）到3），直到每个聚类都不再发生变化为止。

2改进的布谷鸟搜索算法

CS算法通过模拟布谷鸟的寄生繁衍策略来寻找最优解。在自然界中，布谷鸟寻找最适合产蛋的鸟巢是一种随机的或类似随机的方式。为了模拟布谷鸟的繁衍机制，CS算法设定了三个理想状态：

1）每只布谷鸟每次只产一个蛋并随机挑选一个鸟巢来孵化；

2）将存放优质蛋的鸟巢保留到下一代；

3）可用于寄生的鸟巢数是固定的，鸟巢主人一旦发现布谷鸟蛋，就会丢弃该布谷鸟蛋或寻找新的鸟巢，发现概率为pα∈[0，1]。

在以上三个理想状态的基础上，CS算法每次根据Lévy飞行来确定下一次飞向鸟巢的位置。Lévy飞行的步长控制量α控制着算法全局搜索和局部搜索的精度。由于原始的CS算法的Lévy飞行的步长的控制量α是一个固定的值（一般设为1），这导致了CS算法在迭代前期的时候搜寻的步长相对太小，全局搜索能力不足；在算法迭代后期的时候飞行距离相对太大，导致算法不易收敛。因此，为了均衡CS算法迭代前后期的搜索步长，提高算法的收敛速度，陆续出现了一些对CS算法的改进算法。然而，这些算法在对CS算法步长控制量进行改进时只考虑了算法的迭代次数，并没有涉及到鸟巢本身的特性。由于布谷鸟在蛋的存活率比较高的鸟巢周围更容易发现最优鸟巢，因此，本文算法ACS将鸟巢的适应度考虑进来，在寻找下一代鸟巢的过程中根据当前鸟巢的适应度及这一代鸟巢中的最小适应度、最大适应度和当前的迭代次数等来共同决定飞行的路径。本文算法ACS是在CS算法的基础上改进了Lévy飞行的步长控制量，在每一次飞行中根据当前鸟巢情况来进行自适应的步长控制。ACS算法寻找鸟巢的位置的路径计算公式如下：

Lévy（λ）表示莱维搜索路径，服从参数为λ（1<λ<3）的莱维分布产生的一个随机搜索向量。这些搜索路径本质上形成了一个服从幂律分布的随机游走过程。一些新解是在目前的最优解的基础上形成的，这样能够加快局部搜索；另一部分新解必须在远离最优解的地方产生，这样能确保算法不会陷入局部最优。ACS算法描述如下：

1）初始化算法的各个参数，如算法的种群规模n、发现概率pα、算法的迭代次数G、最小步长αL、最大步长αU和目标函数等。

2）初始化n个鸟巢xi（i=1，2，…，n），下蛋并评估每个鸟巢适应度的值，找出当前最优鸟巢并保留。

3）根据式（1）更新鸟巢位置。

4）评估每个鸟巢的位置，将当前鸟巢的适应度与上代鸟巢适应度进行对比，若当前鸟巢的适应度更优则用当前鸟巢代替上代鸟巢，找出当前最好的鸟巢与目前所得到的最优鸟巢对比，若更好，则将此鸟巢置为最优鸟巢。

5）生成随机数r∈[0，1]并与发现概率对比，若r>pα，则抛弃该鸟巢，随机构建新鸟巢；否则，不改变鸟巢。

6）评估每个鸟巢的位置，将当前鸟巢的适应度与上代鸟巢适应度进行对比，若当前鸟巢的适应度更优则用当前鸟巢代替上代鸟巢，找出当前最好的鸟巢与目前所得到的最优鸟巢对比，若更好，则将此鸟巢置为最优鸟巢。

7）若未达到算法终止条件，则返回3）继续执行；否则，输出全局最优鸟巢的位置。

3基于ACS算法的K-means聚类算法

原始的K-means聚类算法易于陷入局部最优解，导致聚类结果不稳定。因此，陆续出现了一些对K-means聚类算法的改进算法，如基于遗传算法（Genetic Algorithm， GA）的K-means聚类算法[16-17]、基于粒子群优化（Particle Swarm Optimization， PSO）算法的K-means聚类算法[19]等。然而，由于这些优化算法本身的局限性，这些改进的K-means算法的聚类精确度及时间复杂度都不是很理想。本文将ACS算法应用到K-means聚类算法中，提出ACS-K-means聚类算法，以期能够更有效地优化聚类的结果。

3.2ACS-K-means聚类算法的实现步骤

在给出ACS-K-means聚类算法的编码方法和适应度函数定义的基础上，算法的实现步骤如下：

1）给定待聚类样本和聚类数k。

2）在可行解空间中随机初始化n个鸟巢的位置和其他的参数。

3）进行聚类划分，根据式（5）计算每个鸟巢的适应度值并保留最优鸟巢。

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

5）根据更新后的鸟巢进行聚类划分并求新的适应度值，将更新后的鸟巢与上代的鸟巢进行对比，若更好则代替。

6）按发现概率pα抛弃鸟巢并重建。

7）进行聚类划分并计算鸟巢的适应度，选出最好的鸟巢，与目前所得到的最优鸟巢对比，若更好，则将此鸟巢置为最优鸟巢。

8）如果未达到最大的迭代次数或最优值不满足条件则

返回4）继续执行；否则输出最优的聚类中心点、簇内距离和簇间距离。

4实验结果与分析

4.1仿真实验

为了验证基于ACS-K-means聚类算法的有效性，选用4个UCI标准数据集Iris、Wine、Habermans survival【和Synthetic（http：//archive.ics.uci.edu/ml）作为实验测试数据，4个数据集的类数、样本数、维数等信息如表1所示。

实验的仿真环境为Windows 10操作系统，Intel 2.40GHz CPU，4GB RAM，仿真软件为Matlab 2014a。分别采用原始K-means聚类算法、基于改进的遗传算法的K-means聚类算法（GA-K-means）[16-17]、基于改进的粒子群优化算法的K-means聚类算法（PSO-K-means）[19]、基于布谷鸟搜索算法的K-means聚类算法（CS-K-means）以及基于改进的布谷鸟搜索算法的K-means聚类算法（ACS-K-means）进行仿真实验。其中，CS-K-means聚类算法和ACS-K-means聚类算法发现鸟巢概率为pα=0.25，鸟巢规模为20，迭代次数为20。

五种算法分别在各个数据集上单独运行20次，假设ri为数据集第i维数据取值范围的绝对值，根据实验情况，当αL=0.2ri，αU=0.8ri时，实验效果最好。在此基础上，计算出适应度函数的值与四种改进聚类算法一次迭代所需要的时间，如表2、3所示。

从实验结果可以看出，在低维的Iris数据集上，本文算法和CS-K-means聚类算法取得了相同的适应度函数值，都优于原始K-means聚类算法、GA-K-means聚类算法和PSO-K-means聚类算法的适应度值。在高维的Wine、Habermans survival【和Synthetic数据集上，本文算法的结果都要优于其他四种算法。这主要是因为本文算法在每次的鸟巢搜索过程中考虑了鸟巢本身的特性，由于在适应度更好的鸟巢周围更容易发现最优鸟巢，在鸟巢的变异过程中将鸟巢自身的适应度加入进来并结合了算法的迭代次数，有效地均衡了算法前后期的搜索步长，提高了算法的搜索精度，使算法具有更好的寻优能力。

进一步，通过对比表3中的CPU时间可以看出，本文算法在每次迭代所花费的CPU时间和CS-K-means算法相当，都要优于其他对比算法。这主要是由于本文算法采用了Lévy飞行搜索机制，算法的输入参数少，结构简单，因此具有更快的计算速度。

为了验证算法的收敛性能，选择在Haberman标准数据集上对四种算法进行测试，得到算法的收敛曲线如图1所示。

由图1可见，GA-K-means聚类算法和PSO-K-means聚类算法通过13次迭代可以收敛到最优值， CS-K-means聚类算法需要11次迭代收敛到最优值，而本文算法只需要7次迭代即可取得最优适应度函数值。这主要是因为ACS算法采用了随机性很强的Lévy飞行搜索机制，在算法迭代一开始可以在解空间内搜索最优值，并且随着迭代次数的增加逐渐缩小搜索的范围，便于在局部范围内进行更细致的搜索。因此，ACS算法兼顾了全局搜索能力和局部搜索能力，能够更快地搜索到最优解。

为了测试五种聚类算法聚类的准确率，在4个数据集上分别进行了实验，结果如表4所示。

从表4中可以看出，对于任一个数据集，原始的K-means聚类算法的准确率都是最低的，这是由于原始的K-means聚类算法对初始聚类中心的选取比较敏感、聚类结果的波动性较大造成的。相对于原始K-means聚类算法，经过优化算法优化的K-means聚类算法具备更好的全局寻优能力，在一定程度上消除了随机选择聚类中心对聚类结果的影响，从而使聚类的准确率得到了提高。而本文算法的聚类准确率要优于对比算法，这主要是因为本文算法在每次迭代产生下一代鸟巢的过程中都考虑了当前鸟巢自身的情况，在适应度更好的鸟巢周围更容易发现最优解，增加了算法获得正确分类的概率。

4.2实例应用

为了验证本文算法在城管案件地理坐标的聚类效果，选取南宁市青秀区某一天的城管案件坐标数据M作为实验数据，数据集M有1037个案件坐标数据，其经度lan（1081802， 108.5152），纬度lat∈（22.7224， 22.8887），聚类的中心点数设为100个。基于四种算法实现的热力图效果如图2～5所示（由于原始K-means聚类算法聚类结果不稳定，这里没有给出热力图实现）。

通过对比图2～5可以发现，本文提出的ACS-K-means聚类算法的热图的聚类划分更加明确，各个聚类中心也更加明显，更加有利于观察、辨别案件的发生地。

总的来看，通过分析在UCI标准数据集的实验结果可以看出本文算法无论是适应度函数值还是聚类速度上都要优于原始K-means聚类算法、GA-K-means聚类算法、PSO-K-means聚类算法及CS-K-means聚类算法，有效地改善了传统K-means聚类算法的缺陷，与其他算法相比具有更好的全局寻优能力和聚类效果。

5结语

本文针对K-means聚类算法的不足，使用布谷鸟搜索算法来优化聚类中心并引入了自适应步长因子，有效地均衡了算法执行前后期的搜索精度，提高了算法的收敛速度。通过与原始K-means聚类算法、改进的GA-K-means聚类算法、改进的PSO-K-means聚类算法及CS-K-means聚类算法的对比实验验证了本文算法可以明显提高聚类效果，提高聚类的速度，应用于城市案件地理坐标的聚类中能够有效地改善生成热图的质量。

参考文献：

[1]FONG S， DEB S， YANG X-S， et al. Towards enhancement of performance of K-means clustering using nature-inspired optimization algorithms[J]. The Scientific World Journal， 2014， 2014： 564829.

[2]YANG X-S， DEB S. Cuckoo search via Lévy flights [C]// NaBIC 2009： Proceedings of the 2009 World Congress on Nature & Biologically Inspired Computing. Piscataway， NJ： 2009： 210-214.

[3]FISTER I， Jr.， YANG X-S， FISTER D， et al. Cuckoo search： a brief literature review [M]// Cuckoo Search and Firefly Algorithm， Volume 516 of the Series Studies in Computational Intelligence. Berlin： Springer-Verlag， 2013： 49-62.

[4]YANG X-S， DEB S. Cuckoo search： recent advances and applications [J]. Neural Computing and Applications， 2014， 24（1）： 169-174.

[5]SRIVASTAVA P R， KHANDELWAL R， KHANDELWAL S， et al. Automated test data generation using cuckoo search and tabu search （CSTS） algorithm [J]. Journal of Intelligent Systems， 2012， 21（2）：195-224.

[6]BEZDELC J C. Pattern Recognition with Fuzzy Objective Function Algorithms [M]. Berlin： Springer-Verlag， 1981： 46-52.

[7]LI X， WANG J， YIN M. Enhancing the performance of cuckoo search algorithm using orthogonal learning method [J]. Neural Computing and Applications， 2014， 24（6）：1233-1247.

[8]ONG P. Adaptive cuckoo search algorithm for unconstrained optimization [J]. Scientific World Journal， 2014， 2014： 943403.

[9]张永韡，汪镭，吴启迪.动态适应布谷鸟搜索算法[J].控制与决策，2014，29（4）：617-622. （ZHANG Y W， WANG L， WU Q D. Dynamic adaptation cuckoo search algorithm [J]. Control and Decision， 2014， 29（4）： 617-622.）

[10]王李进，尹义龙，钟一文.逐维改进的布谷鸟搜索算法[J].软件学报，2013（11）：2687-2698. （WANG L J， YIN Y L， ZHONG Y W. Cuckoo search algorithm with dimension by dimension improvement [J]. Journal of Software， 2013， 24（11）： 2687-2698.）

[11]胡欣欣，尹义龙.求解连续函数优化问题的合作协同进化布谷鸟搜索算法[J].模式识别与人工智能，2013，26（11）：1041-1049. （HU X X， YIN Y L. Cooperative co-evolutionary cuckoo search algorithm for continuous function optimization problems[J]. Pattern Recognition and Artificial Intelligence， 2013， 26（11）：1041-1049.）

[12]吴希玉.深化城管改革建设宜居南宁[N]. 广西日报，2015-12-30（7）. （WU X Y. Deepen the reform of urban construction of livable Nanning[N]. Guangxi Daily， 2015-12-30（7）.）

[13]向志强，朱丽莉.“互联网+城管”的“青秀探索”[N].新华每日电讯，2016-02-03（7）. （XIANG Z Q， ZHU L L. The exploration of Qingxiu based on Internet and urban management [N]. Xinhuashenet， 2016-02-03（7）.）

[14]BAGHERI E， DELDARI H. Dejong function optimization by means of a parallel approach to fuzzified genetic algorithm [C]// ISCC 06： Proceedings of the 11th IEEE Symposium on Computers and Communications. Washington， DC： IEEE Computer Society， 2006： 675-680.

[15]HALL L O， OZYURT I B， BEZDEK J C. Clustering with a genetically optimized approach [J]. IEEE Transactions on Evolutionary Computation， 1999， 3（2）：103-112.

[16]陆林花，王波.一种改进的遗传聚类算法[J].计算机工程与应用，2007，43（21）：170-172. （LU L H， WANG B. Improved genetic algorithm-based clustering approach [J]. Computer Engineering and Applications， 2007， 43（21）： 170-172.）

[17]傅景广，许刚，王裕国.基于遗传算法的聚类分析[J].计算机工程，2004，30（4）：122-124. （FU J G， XU G， WANG Y G. Clustering based on genetic algorithm[J]. Computer Engineering， 2004， 30（4）：122-124.）

[18]AHMADYFARD A， MODARES H. Combining PSO and k-means to enhance data clustering[C]// IST 2008： Proceedings of the 2008 International Symposium on Telecommunications. Piscataway， NJ： IEEE， 2008： 688-691.

[19]陈小全，张继红.基于改进粒子群算法的聚类算法[J].计算机研究与发展，2012，49（增刊）：287-291. （CHEN X Q， ZHANG J H. Clustering algorithm based on improved particle swarm optimization [J]. Journal of Computer Research and Development， 2012， 49（Suppl.）： 287-291.）