基于自適應(yīng)布谷鳥搜索算法的K—means聚類算法及其應(yīng)用

楊輝華　王克　李靈巧　魏文　何勝韜

摘要：針對原始K-means聚類算法受初始聚類中心影響過大以及容易陷入局部最優(yōu)的不足，提出一種基于改進布谷鳥搜索（CS）的K-means聚類算法（ACS-K-means）。其中，自適應(yīng)CS（ACS）算法在標準CS算法的基礎(chǔ)上引入步長自適應(yīng)調(diào)整，以提高搜索精度和收斂速度。在UCI標準數(shù)據(jù)集上，ACS-K-means算法可得到比K-means、基于遺傳算法的K-means（GA-K-means）、基于布谷鳥搜索的K-means（CS-K-means）和基于粒子群優(yōu)化的K-means（PSO-K-means）算法更優(yōu)的聚類質(zhì)量和更高的收斂速度。將ACS-K-means聚類算法應(yīng)用到南寧市青秀區(qū)“城管通”系統(tǒng)的城管案件熱圖的開發(fā)中，在地圖上對案件地理坐標進行聚類并顯示，應(yīng)用結(jié)果表明，聚類效果良好，算法收斂速度快。

關(guān)鍵詞：數(shù)據(jù)挖掘；K-means聚類；布谷鳥搜索算法；數(shù)字城管；熱圖

中圖分類號：TP391； TP183

文獻標志碼：A

0引言

隨著我國數(shù)字化城市管理事業(yè)建設(shè)的推進，基于城市管理綜合數(shù)據(jù)的智慧城市應(yīng)用越來越受到重視。數(shù)字城管系統(tǒng)在建設(shè)與運行的過程中，不斷豐富了城市管理的基礎(chǔ)數(shù)據(jù)，如基礎(chǔ)地形圖、衛(wèi)星遙感影像數(shù)據(jù)、城市管理部件數(shù)據(jù)、城市管理案件數(shù)據(jù)等。這些龐大的城市管理綜合數(shù)據(jù)為數(shù)據(jù)的空間分析、聚類分析、輔助決策等提供了重要載體。而如何從海量的城管數(shù)據(jù)中發(fā)掘出有用的信息為城市管理所運用已成為目前智慧城市建設(shè)中研究的熱點問題之一。利用數(shù)據(jù)挖掘技術(shù)從城市管理的案件地理數(shù)據(jù)中發(fā)現(xiàn)隱含的有用信息，從時間維度和空間維度分析城市管理問題的高發(fā)時段、高發(fā)區(qū)域，分析城市管理問題的發(fā)生、發(fā)展等動態(tài)變化過程，這在災(zāi)害天氣頻發(fā)時進行實時預(yù)警、對領(lǐng)導(dǎo)決策提供輔助等方面能起到重要作用。

數(shù)據(jù)挖掘作為一個熱門的多學(xué)科交叉應(yīng)用領(lǐng)域，正在各行各業(yè)中扮演著重要的角色。人們可以通過數(shù)據(jù)挖掘技術(shù)從大量的原始數(shù)據(jù)中提取、發(fā)現(xiàn)有重要價值的信息，并應(yīng)用于實際的生產(chǎn)中。常用的數(shù)據(jù)挖掘方法有分類、估計、預(yù)測、相關(guān)性分組、聚類等。聚類分析是一種常用的無監(jiān)督數(shù)據(jù)挖掘方法。K-means算法作為一種經(jīng)典的聚類算法具有簡單高效等優(yōu)點，因此得到廣泛應(yīng)用。因此，在匯集城市案件地理坐標數(shù)據(jù)的基礎(chǔ)上，通過K-means聚類分析算法分析出案件在城區(qū)的分布規(guī)律，通過熱圖的形式直觀地展現(xiàn)出來，這對于部門領(lǐng)導(dǎo)制定相關(guān)策略具有重要的意義。

然而，原始的K-means聚類算法存在對初始聚類中心的選擇比較敏感、聚類結(jié)果不穩(wěn)定等缺陷[1]。因此，原始的K-means聚類算法對城市案件地理位置數(shù)據(jù)的聚類分析效果不是很理想。近年來出現(xiàn)了一些對原始K-means算法改進的新算法。其中，一個重要的研究方向就是將一些元啟發(fā)式優(yōu)化算法與K-means算法相結(jié)合，利用優(yōu)化算法的全局優(yōu)化能力來改善K-means算法的聚類結(jié)果。

布谷鳥搜索（Cuckoo Search， CS）算法[2]是一種新型元啟發(fā)式算法，它采用Lévy飛行搜索機制，具有很強的全局搜索能力。此外，CS算法還具有輸入?yún)?shù)少、結(jié)構(gòu)簡單、易于實現(xiàn)等優(yōu)點[3]；但CS算法也存在著局部搜索能力較差、后期收斂速度慢等缺點[4]。因此，陸續(xù)出現(xiàn)了一些對原始CS算法的改進算法[5-8]，如動態(tài)適應(yīng)的CS算法[9]、逐維改進的CS算法等[10]。由于CS算法中的步長因子很大程度上控制著算法的搜索精度，因此，本文采用新的自適應(yīng)的步長因子來改進原始CS算法，使得該算法能夠在全局搜索和局部搜索之間保持很好的平衡，提高CS算法的收斂速度。

本文首先在CS算法的基礎(chǔ)上，對算法中Lévy飛行的步長控制量α作自適應(yīng)調(diào)整，提出自適應(yīng)CS（Adaptive Cuckoo Search， ACS）算法；然后，將ACS算法引入K-means聚類算法，利用ACS算法對聚類中心進行優(yōu)化，提出了一種基于改進布谷鳥搜索算法的K-means聚類算法（ACS-K-means）；最后，將該算法應(yīng)用于南寧市青秀區(qū)“城管通”系統(tǒng)[13]案件數(shù)據(jù)的聚類分析，并結(jié)合熱圖技術(shù)開發(fā)了城管決策輔助系統(tǒng)[12]，有助于相關(guān)領(lǐng)導(dǎo)快速作出決策，提高城管系統(tǒng)的運行效率。

1 K-means聚類算法

K-means聚類算法是一種基于劃分的經(jīng)典聚類算法。該算法的流程如下：

1）從n個數(shù)據(jù)樣本中任意選取k個樣本作為初始的聚類中心點；

2）根據(jù)每個聚類的均值（即中心樣本），計算每個樣本與這些中心樣本的距離，并根據(jù)最小距離對樣本進行劃分；

3）重新計算每個有變化的聚類的均值。

重復(fù)步驟2）到3），直到每個聚類都不再發(fā)生變化為止。

2改進的布谷鳥搜索算法

CS算法通過模擬布谷鳥的寄生繁衍策略來尋找最優(yōu)解。在自然界中，布谷鳥尋找最適合產(chǎn)蛋的鳥巢是一種隨機的或類似隨機的方式。為了模擬布谷鳥的繁衍機制，CS算法設(shè)定了三個理想狀態(tài)：

1）每只布谷鳥每次只產(chǎn)一個蛋并隨機挑選一個鳥巢來孵化；

2）將存放優(yōu)質(zhì)蛋的鳥巢保留到下一代；

3）可用于寄生的鳥巢數(shù)是固定的，鳥巢主人一旦發(fā)現(xiàn)布谷鳥蛋，就會丟棄該布谷鳥蛋或?qū)ふ倚碌镍B巢，發(fā)現(xiàn)概率為pα∈[0，1]。

在以上三個理想狀態(tài)的基礎(chǔ)上，CS算法每次根據(jù)Lévy飛行來確定下一次飛向鳥巢的位置。Lévy飛行的步長控制量α控制著算法全局搜索和局部搜索的精度。由于原始的CS算法的Lévy飛行的步長的控制量α是一個固定的值（一般設(shè)為1），這導(dǎo)致了CS算法在迭代前期的時候搜尋的步長相對太小，全局搜索能力不足；在算法迭代后期的時候飛行距離相對太大，導(dǎo)致算法不易收斂。因此，為了均衡CS算法迭代前后期的搜索步長，提高算法的收斂速度，陸續(xù)出現(xiàn)了一些對CS算法的改進算法。然而，這些算法在對CS算法步長控制量進行改進時只考慮了算法的迭代次數(shù)，并沒有涉及到鳥巢本身的特性。由于布谷鳥在蛋的存活率比較高的鳥巢周圍更容易發(fā)現(xiàn)最優(yōu)鳥巢，因此，本文算法ACS將鳥巢的適應(yīng)度考慮進來，在尋找下一代鳥巢的過程中根據(jù)當前鳥巢的適應(yīng)度及這一代鳥巢中的最小適應(yīng)度、最大適應(yīng)度和當前的迭代次數(shù)等來共同決定飛行的路徑。本文算法ACS是在CS算法的基礎(chǔ)上改進了Lévy飛行的步長控制量，在每一次飛行中根據(jù)當前鳥巢情況來進行自適應(yīng)的步長控制。ACS算法尋找鳥巢的位置的路徑計算公式如下：

Lévy（λ）表示萊維搜索路徑，服從參數(shù)為λ（1<λ<3）的萊維分布產(chǎn)生的一個隨機搜索向量。這些搜索路徑本質(zhì)上形成了一個服從冪律分布的隨機游走過程。一些新解是在目前的最優(yōu)解的基礎(chǔ)上形成的，這樣能夠加快局部搜索；另一部分新解必須在遠離最優(yōu)解的地方產(chǎn)生，這樣能確保算法不會陷入局部最優(yōu)。ACS算法描述如下：

1）初始化算法的各個參數(shù)，如算法的種群規(guī)模n、發(fā)現(xiàn)概率pα、算法的迭代次數(shù)G、最小步長αL、最大步長αU和目標函數(shù)等。

2）初始化n個鳥巢xi（i=1，2，…，n），下蛋并評估每個鳥巢適應(yīng)度的值，找出當前最優(yōu)鳥巢并保留。

3）根據(jù)式（1）更新鳥巢位置。

4）評估每個鳥巢的位置，將當前鳥巢的適應(yīng)度與上代鳥巢適應(yīng)度進行對比，若當前鳥巢的適應(yīng)度更優(yōu)則用當前鳥巢代替上代鳥巢，找出當前最好的鳥巢與目前所得到的最優(yōu)鳥巢對比，若更好，則將此鳥巢置為最優(yōu)鳥巢。

5）生成隨機數(shù)r∈[0，1]并與發(fā)現(xiàn)概率對比，若r>pα，則拋棄該鳥巢，隨機構(gòu)建新鳥巢；否則，不改變鳥巢。

6）評估每個鳥巢的位置，將當前鳥巢的適應(yīng)度與上代鳥巢適應(yīng)度進行對比，若當前鳥巢的適應(yīng)度更優(yōu)則用當前鳥巢代替上代鳥巢，找出當前最好的鳥巢與目前所得到的最優(yōu)鳥巢對比，若更好，則將此鳥巢置為最優(yōu)鳥巢。

7）若未達到算法終止條件，則返回3）繼續(xù)執(zhí)行；否則，輸出全局最優(yōu)鳥巢的位置。

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

原始的K-means聚類算法易于陷入局部最優(yōu)解，導(dǎo)致聚類結(jié)果不穩(wěn)定。因此，陸續(xù)出現(xiàn)了一些對K-means聚類算法的改進算法，如基于遺傳算法（Genetic Algorithm， GA）的K-means聚類算法[16-17]、基于粒子群優(yōu)化（Particle Swarm Optimization， PSO）算法的K-means聚類算法[19]等。然而，由于這些優(yōu)化算法本身的局限性，這些改進的K-means算法的聚類精確度及時間復(fù)雜度都不是很理想。本文將ACS算法應(yīng)用到K-means聚類算法中，提出ACS-K-means聚類算法，以期能夠更有效地優(yōu)化聚類的結(jié)果。

3.2ACS-K-means聚類算法的實現(xiàn)步驟

在給出ACS-K-means聚類算法的編碼方法和適應(yīng)度函數(shù)定義的基礎(chǔ)上，算法的實現(xiàn)步驟如下：

1）給定待聚類樣本和聚類數(shù)k。

2）在可行解空間中隨機初始化n個鳥巢的位置和其他的參數(shù)。

3）進行聚類劃分，根據(jù)式（5）計算每個鳥巢的適應(yīng)度值并保留最優(yōu)鳥巢。

4）按照改進的布谷鳥搜索算法對其他的鳥巢進行更新。

5）根據(jù)更新后的鳥巢進行聚類劃分并求新的適應(yīng)度值，將更新后的鳥巢與上代的鳥巢進行對比，若更好則代替。

6）按發(fā)現(xiàn)概率pα拋棄鳥巢并重建。

7）進行聚類劃分并計算鳥巢的適應(yīng)度，選出最好的鳥巢，與目前所得到的最優(yōu)鳥巢對比，若更好，則將此鳥巢置為最優(yōu)鳥巢。

8）如果未達到最大的迭代次數(shù)或最優(yōu)值不滿足條件則

返回4）繼續(xù)執(zhí)行；否則輸出最優(yōu)的聚類中心點、簇內(nèi)距離和簇間距離。

4實驗結(jié)果與分析

4.1仿真實驗

為了驗證基于ACS-K-means聚類算法的有效性，選用4個UCI標準數(shù)據(jù)集Iris、Wine、Habermans survival【和Synthetic（http：//archive.ics.uci.edu/ml）作為實驗測試數(shù)據(jù)，4個數(shù)據(jù)集的類數(shù)、樣本數(shù)、維數(shù)等信息如表1所示。

實驗的仿真環(huán)境為Windows 10操作系統(tǒng)，Intel 2.40GHz CPU，4GB RAM，仿真軟件為Matlab 2014a。分別采用原始K-means聚類算法、基于改進的遺傳算法的K-means聚類算法（GA-K-means）[16-17]、基于改進的粒子群優(yōu)化算法的K-means聚類算法（PSO-K-means）[19]、基于布谷鳥搜索算法的K-means聚類算法（CS-K-means）以及基于改進的布谷鳥搜索算法的K-means聚類算法（ACS-K-means）進行仿真實驗。其中，CS-K-means聚類算法和ACS-K-means聚類算法發(fā)現(xiàn)鳥巢概率為pα=0.25，鳥巢規(guī)模為20，迭代次數(shù)為20。

五種算法分別在各個數(shù)據(jù)集上單獨運行20次，假設(shè)ri為數(shù)據(jù)集第i維數(shù)據(jù)取值范圍的絕對值，根據(jù)實驗情況，當αL=0.2ri，αU=0.8ri時，實驗效果最好。在此基礎(chǔ)上，計算出適應(yīng)度函數(shù)的值與四種改進聚類算法一次迭代所需要的時間，如表2、3所示。

從實驗結(jié)果可以看出，在低維的Iris數(shù)據(jù)集上，本文算法和CS-K-means聚類算法取得了相同的適應(yīng)度函數(shù)值，都優(yōu)于原始K-means聚類算法、GA-K-means聚類算法和PSO-K-means聚類算法的適應(yīng)度值。在高維的Wine、Habermans survival【和Synthetic數(shù)據(jù)集上，本文算法的結(jié)果都要優(yōu)于其他四種算法。這主要是因為本文算法在每次的鳥巢搜索過程中考慮了鳥巢本身的特性，由于在適應(yīng)度更好的鳥巢周圍更容易發(fā)現(xiàn)最優(yōu)鳥巢，在鳥巢的變異過程中將鳥巢自身的適應(yīng)度加入進來并結(jié)合了算法的迭代次數(shù)，有效地均衡了算法前后期的搜索步長，提高了算法的搜索精度，使算法具有更好的尋優(yōu)能力。

進一步，通過對比表3中的CPU時間可以看出，本文算法在每次迭代所花費的CPU時間和CS-K-means算法相當，都要優(yōu)于其他對比算法。這主要是由于本文算法采用了Lévy飛行搜索機制，算法的輸入?yún)?shù)少，結(jié)構(gòu)簡單，因此具有更快的計算速度。

為了驗證算法的收斂性能，選擇在Haberman標準數(shù)據(jù)集上對四種算法進行測試，得到算法的收斂曲線如圖1所示。

由圖1可見，GA-K-means聚類算法和PSO-K-means聚類算法通過13次迭代可以收斂到最優(yōu)值， CS-K-means聚類算法需要11次迭代收斂到最優(yōu)值，而本文算法只需要7次迭代即可取得最優(yōu)適應(yīng)度函數(shù)值。這主要是因為ACS算法采用了隨機性很強的Lévy飛行搜索機制，在算法迭代一開始可以在解空間內(nèi)搜索最優(yōu)值，并且隨著迭代次數(shù)的增加逐漸縮小搜索的范圍，便于在局部范圍內(nèi)進行更細致的搜索。因此，ACS算法兼顧了全局搜索能力和局部搜索能力，能夠更快地搜索到最優(yōu)解。

為了測試五種聚類算法聚類的準確率，在4個數(shù)據(jù)集上分別進行了實驗，結(jié)果如表4所示。

從表4中可以看出，對于任一個數(shù)據(jù)集，原始的K-means聚類算法的準確率都是最低的，這是由于原始的K-means聚類算法對初始聚類中心的選取比較敏感、聚類結(jié)果的波動性較大造成的。相對于原始K-means聚類算法，經(jīng)過優(yōu)化算法優(yōu)化的K-means聚類算法具備更好的全局尋優(yōu)能力，在一定程度上消除了隨機選擇聚類中心對聚類結(jié)果的影響，從而使聚類的準確率得到了提高。而本文算法的聚類準確率要優(yōu)于對比算法，這主要是因為本文算法在每次迭代產(chǎn)生下一代鳥巢的過程中都考慮了當前鳥巢自身的情況，在適應(yīng)度更好的鳥巢周圍更容易發(fā)現(xiàn)最優(yōu)解，增加了算法獲得正確分類的概率。

4.2實例應(yīng)用

為了驗證本文算法在城管案件地理坐標的聚類效果，選取南寧市青秀區(qū)某一天的城管案件坐標數(shù)據(jù)M作為實驗數(shù)據(jù)，數(shù)據(jù)集M有1037個案件坐標數(shù)據(jù)，其經(jīng)度lan（1081802， 108.5152），緯度lat∈（22.7224， 22.8887），聚類的中心點數(shù)設(shè)為100個?；谒姆N算法實現(xiàn)的熱力圖效果如圖2～5所示（由于原始K-means聚類算法聚類結(jié)果不穩(wěn)定，這里沒有給出熱力圖實現(xiàn)）。

通過對比圖2～5可以發(fā)現(xiàn)，本文提出的ACS-K-means聚類算法的熱圖的聚類劃分更加明確，各個聚類中心也更加明顯，更加有利于觀察、辨別案件的發(fā)生地。

總的來看，通過分析在UCI標準數(shù)據(jù)集的實驗結(jié)果可以看出本文算法無論是適應(yīng)度函數(shù)值還是聚類速度上都要優(yōu)于原始K-means聚類算法、GA-K-means聚類算法、PSO-K-means聚類算法及CS-K-means聚類算法，有效地改善了傳統(tǒng)K-means聚類算法的缺陷，與其他算法相比具有更好的全局尋優(yōu)能力和聚類效果。

5結(jié)語

本文針對K-means聚類算法的不足，使用布谷鳥搜索算法來優(yōu)化聚類中心并引入了自適應(yīng)步長因子，有效地均衡了算法執(zhí)行前后期的搜索精度，提高了算法的收斂速度。通過與原始K-means聚類算法、改進的GA-K-means聚類算法、改進的PSO-K-means聚類算法及CS-K-means聚類算法的對比實驗驗證了本文算法可以明顯提高聚類效果，提高聚類的速度，應(yīng)用于城市案件地理坐標的聚類中能夠有效地改善生成熱圖的質(zhì)量。

參考文獻：

[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]張永韡，汪鐳，吳啟迪.動態(tài)適應(yīng)布谷鳥搜索算法[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].軟件學(xué)報，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]胡欣欣，尹義龍.求解連續(xù)函數(shù)優(yōu)化問題的合作協(xié)同進化布谷鳥搜索算法[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]吳希玉.深化城管改革建設(shè)宜居南寧[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]向志強，朱麗莉.“互聯(lián)網(wǎng)+城管”的“青秀探索”[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].計算機工程與應(yīng)用，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].計算機研究與發(fā)展，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.）