新的小生境螢火蟲劃分聚類算法

王 沖，雷秀娟

(陜西師范大學計算機科學學院，西安 7 10062)

新的小生境螢火蟲劃分聚類算法

王 沖，雷秀娟

(陜西師范大學計算機科學學院，西安 7 10062)

針對傳統的劃分聚類算法過度依賴初始聚類中心并容易陷入局部最優的問題，提出基于螢火蟲算法的改進劃分聚類算法。該算法將螢火蟲個體對應于一組聚類中心的解，類簇的聚合度對應于螢火蟲的亮度，通過螢火蟲個體之間的相互吸引尋找聚類中心的最優解。在尋優過程中使用隨機分布的螢火蟲種群克服劃分聚類過于依賴初始聚類中心的問題，采用自適應步長的策略加強算法尋找精確解的能力。為了避免在尋優過程中因為種群過于集中而導致算法陷入局部最優，引入小生境技術提高螢火蟲的種群多樣性。仿真實驗結果表明，與傳統聚類算法相比，該算法的聚類精度較高，穩定性較好。

劃分聚類；聚類中心；局部最優；螢火蟲算法；自適應步長；小生境

1 概述

隨著信息社會的發展，社會各個領域的數據正在迅速膨脹并變大。數據挖掘作為大數據時代尋找數據背后有用信息的重要工具，越要越受到人們的重視。聚類分析[1-2]是數據挖掘中的一個重要課題，它是將物理或抽象的對象集合分成相似的類簇的過程。通過聚類描述事物間的相似性和差異，從而方便人們掌握事物的內部規律。

劃分聚類是聚類算法中非常常用的聚類方法，因為其簡單高效的優點，被人們廣泛研究及應用到各領域，常見的有K-means[2]、K-medoids[3]以及一些改進算法等。這些啟發式的聚類方法通常適合于發現數據庫中的球狀簇[4]，但為了對大規模的數據集聚類，需要對基于劃分的算法做進一步擴展和改進。

群智能優化算法[5]通過模擬自然界中動物的各種群體行為，利用群體中個體之間的信息交互和合作實現尋優的目的。螢火蟲算法[6-7](Firefly Algorithm, FA)是一種新興的群智能優化算法，是模擬自然界螢火蟲的發光行為發展而來。該算法具有良好的尋優和搜索性能，目前已應用到很多優化問題中，如多目標優化問題[8]、TSP問題[9]、調度問題[10]及災難挖掘方法[11]等。

針對傳統劃分聚類方法存在的問題，本文在螢火蟲算法的基礎上建立聚類模型并進行改進，對常用數據集進行實驗驗證。

2 相關算法及定義

2.1 劃分方法的數學描述

對一個含有n個對象的數據集，指定類簇數為k，劃分方法將這組數據集分成期望的k個類簇，k≤n ，每個類簇表示一個聚類。其中，這組類簇必須滿足如下條件[12]：

(1)每個數據集中的個體必須屬于且僅屬于其中一個類簇。

(2)每個類簇必須至少包含一個對象。

對于期望的類簇數k，從初始的分類方法開始，不斷地通過迭代改變分類情況，使得改變后的分類情況優于之前的分類。評價類簇的一般標準是：同一類簇間個體的距離盡可能小，而不同類簇間個體的距離盡可能大。但傳統的劃分聚類會存在一些缺點，以最常用K-means為例：(1)初始聚類中心選取的好壞會直接影響到整個聚類的效果；(2)算法的全局搜索性能不足從而導致陷入局部最優；(3)對孤立數據和噪聲數據非常敏感，少量的該類數據會對聚類結果產生極大的影響。

2.2 螢火蟲算法

自然中螢火蟲會有節奏地發出短促的熒光，而不同的螢火蟲有著不同的發光目的。一般認為是為了吸引異性或者捕食，還有的以此作為警戒信號。螢火蟲算法通過模擬螢火蟲的發光行為搜索領域內的伙伴，一步步朝著區域內較優的位置移動，從而實現狀態的不斷進化。

螢火蟲算法的尋優要素主要是自身亮度和吸引度。亮度取決于當前位置的目標函數值，如果位置越好則亮度越高。同時亮度也影響螢火蟲的吸引力，亮度高的螢火蟲會擁有更強的吸引力，可以將視野內亮度較弱的伙伴吸引過來。同時隨著距離的增加，傳播媒介吸收熒光后亮度和吸引力都隨之減弱。螢火蟲算法的相關定義如下：

定義1 螢火蟲的熒光亮度：

其中，L0是螢火蟲的最強亮度，也就是r=0處的熒光值；rij是螢火蟲i和j之間的距離，隨著rij傳播媒介距離的增加，熒光亮度L逐漸減弱；γ為傳播媒介的光強吸收系數。

定義2 第i只螢火蟲的位移公式：

其中，xnext是位移后的值；β為螢火蟲i，j之間的吸引因子；step是步長因子；δ小于1大于0且服從均勻分布的隨機數。

2.3 小生境技術

小生境技術[13-14]就是通過模仿自然界中相同種類生物一起生活，形成一個生活的小環境，從而分離不同種類個體。其中，基于排擠機制的選擇策略步驟如下：

(1)設置一個排擠因子CF(一般取2或3)；

(2)從種群中隨機選取1/CF個個體組成排擠成員；

(3)依據新個體與排擠成員的相似性排擠掉種群中相類似的個體。

小生境技術能夠保持種群的多樣性，避免種群陷入局部最優，從而得到更好的全局搜索能力。螢火蟲算法雖然有較好的尋優能力，但是算法缺乏避免種群個體過于集中的能力，在算法后期容易導致局部最優。

本文將小生境技術用到螢火蟲算法中，使算法在求解聚類問題過程中避免陷入局部極值從而得到更好的求解精度。

3 小生境螢火蟲聚類模型定義

3.1 螢火蟲編碼

針對聚類問題，將一組聚類中心對應于一只螢火蟲，每只螢火蟲的狀態就是問題的一個可行解。假設期待聚類個數為k，第i只螢火蟲ffi的編碼形式表示如下：

3.2 螢火蟲自身亮度和吸引度

在劃分聚類中，距離是用來評價任意2個個體相異度的標準，而對于一個類簇來說，它的類間距離的和反映了該類聚合程度的強弱，同時這也是聚類問題通常采用的準則函數，定義如下：

其中，D( ci)表示聚類中心ci對應的類間聚類的和。在本文中，使用D( ci)反映螢火蟲個體的優劣，也就是說螢火蟲的亮度L在r=0處的計算公式如下：

由式(1)和式(4)可以看到，D( ci)越小，則該類內部就聚集得越緊密，而螢火蟲的亮度也就越高，周圍領域的螢火蟲聚集的機會也就越高。

3.3 目標函數

目標函數也就是適應度函數，是評價一個算法結果的標準。對聚類問題來說，需要使生成的結果簇盡可能地緊湊和獨立。本文通過計算類簇集的內間距離的和，作為目標函數來評價全局聚類結果的好壞，定義如下：

3.4 螢火蟲種群初始化

造成K-means過于依賴初始聚類中心缺陷的原因，很大程度上是由于一開始隨機選取數據點作為初始聚類中心的方法。因為在沒有先驗知識的情況下，無法從一開始就估計聚類中心的位置，最壞的情況下就導致同一類簇中的個體作為不同的聚類中心劃分出去。而對于螢火蟲算法來說，多樣性正是它的優勢之一，為了避免K-means這樣的缺點的產生，將螢火蟲隨機分布到空間坐標中，得到更加隨機多樣的初始種群分布。具體做法如下：

3.5 自適應的步長設置

螢火蟲算法作為智能算法之一，擁有較好的尋優性能，但也同樣擁有很多智能算法的缺陷，在多峰值的尋優過程中，如果步長設置得不合理就會導致算法陷入局部最優的問題。在步長step的設置中，雖然過高的步長能很快地跳出局部最優卻可能因此而跳過精確解導致算法精度降低。為了解決這個問題，本文采用自適應的步長，在移動的過程中根據目標函數值fitness的變化自適應調整步長step。通過下式計算自適應的步長：

其中，step'為每一只螢火蟲根據預先設置的step計算得到的自適應步長；fitnessnext為螢火蟲移動后的目標函數值；fitness為移動前的目標函數值，由式(6)可以看出，使用自適應的方式，當目標函數快速收斂的時候，step較高，螢火蟲個體會保持較快的尋優能力，而當fitness趨于穩定的時候，螢火蟲個體則趨向于搜索自身周圍領域的精確解。

3.6 小生境技術的引入

螢火蟲算法通過相互吸引的行為達到尋優的目的，但是對于復雜問題特別是多峰優化問題來說卻同樣面臨陷入局部最優的情況。為了提高種群的多樣性和全局搜索能力，保持解的多樣性，引入基于排擠策略的小生境技術。具體做法是，首先用統計學中的離散系數gather描述種群的聚集情況：

其中，fiti表示當前第i只螢火蟲的適應度函數值；fitavg是當前的螢火蟲種群適應度平均值。離散系數可以用來反映數據集內個體間的離散程度，對于本文算法來說，由于螢火蟲之間相互吸引會不斷聚集到一起，適應度值也會逐漸趨于一致，gather值也越來越小，說明此時種群也越來越集中，離散程度越來越低。極限情況下，當gather值等于0時，種群的離散程度為0，整個種群完全重合到同一位置，此時算法要么是達到全局最優，要么是早熟收斂于局部最優，因此通過gather值可以判斷當前種群的收斂情況。為了加強算法跳出局部最優的能力，再設置一個閾值δ，根據實際問題的不同，給δ設置一個較小的值，通常可以取δ值為0～0.3之間。當gather＜δ時，認為螢火蟲種群已經過于集中，此時引入小生境機制，從螢火蟲群體的取值空間中隨機產生1/3的個體cj組成排擠成員，然后對行動后的螢火蟲種群與排擠成員cj比較相似度并進行排擠操作，排擠掉相似度高的個體，從而保持螢火蟲種群的多樣性，避免陷入局部最優。

4 算法描述

算法步驟如下：

步驟1輸入數據集，為了評價方便對數據進行歸一化處理。確定螢火蟲種群規模N、迭代次數iterNum以及期待的類簇數k，按照3.4節所示將聚類中心隨機分布到數據空間從而完成螢火蟲種群初始化。

步驟2根據式(4)計算每只螢火蟲各自的亮度，將目標函數最優的螢火蟲個體狀態賦值給公告板。其中，公告板是一個d+1維的全局變量，前d維用于保存當前最優的螢火蟲個體狀態，第d+1維保存其對應的全局最優適應度值。然后判斷是否已達到算法終止條件，達到則輸出結果后退出，否則繼續執行步驟3。

步驟3搜索視野內的螢火蟲狀態及亮度，選擇亮度最強的螢火蟲所在位置作為移動的方向，根據3.5節所示的方法設置自適應的步長step，模擬螢火蟲的相互吸引行為。如果追逐后狀態比先前狀態更優，則執行吸引行為，否則重新選擇下一個次優的螢火蟲個體進行追逐，若得到更優的狀態則移動。如果在tryNum次數內都無法完成追逐操作，則默認執行隨機行為。假如行動后的螢火蟲個體超出邊界則執行如下操作：

步驟4依次計算螢火蟲種群目標函數值與公告板值，如果得到了更優的適應度值，則更新公告板。完成該輪螢火蟲種群尋優行為后，判斷種群是否過于集中，如果是則執行小生境算法，否則進入步驟5。

步驟5判斷算法是否已到終止條件，若達到則輸出結果，否則轉到步驟3，iter=iter+1。

5 仿真實驗及分析

本文分別進行了2組實驗，以分析和比較本文算法的效果。實驗平臺均為Matlab7.0。

實驗1 為了更加直觀地了解本文算法的尋優過程，先以一組隨機產生的二維數據集為例。分別以(3,7)，(2,2)，(7,8) 及(6,4)為中心，隨機產生3個類，每個類分別有150個數據點且服從高斯分布。最大種群尋優次數為150代，種群大小50，默認step為1，用Matlab繪制出大致的尋優圖像如圖1～圖9所示。

圖1 第1代聚類結果

圖2 第1代種群分布

圖3 第25代聚類結果

圖4 第25代種群分布

圖5 第50代聚類結果

圖6 第50代種群分布

圖8 第100代種群分布

圖9 目標函數曲線

通過圖1～圖9可以看到，本文算法在初始化聚類中心時將螢火蟲種群隨機分布到了取值空間內，使算法具有更好的全局搜索條件。由于引入了小生境機制，使種群不會完全集中到一點，得到了更多樣性的解和螢火蟲個體，自適應的步長使算法在收斂后期能夠逐步求得精確解。

實驗2 通過對UCI數據集中的Iris數據集和Cancer數據集進行實驗比較本文算法的性能，主要與K-means算法、PSO算法[15]和改進前的螢火蟲算法進行比較，每種算法分別運行20次，分別取聚類結果的最低、最高精度和平均精度。精度的計算公式如下[16]：

其中，S表示標準數據集中的聚類結果集；R表示實驗結果數據集；precision反映了聚類算法實驗結果的正確率。

由表1、表2可以看到，對于K-means算法，由于過度依賴初始聚類中心，導致平均精度較低而且算法穩定性較差，而融入小生境機制的NFA算法聚類不但在精度方面有所提高，而且在魯棒性方面也得到了增強。

表1 I ris數據集上的聚類結果比較 %

表2 Can cer數據集上的聚類結果比較 %

6 結束語

本文通過分析劃分聚類方法的特性，在基本螢火蟲算法的基礎上，針對聚類問題做出一系列改進：為了提高聚類尋優的精確性使用自適應步長，避免了固定步長所帶來的算法魯棒性不高的問題，在聚類過程中引入小生境技術，提高了螢火蟲算法種群的多樣性，加強算法避免陷入局部最優的能力。雖然本文對于螢火蟲算法應用于聚類問題提出了一些改進方法，但螢火蟲算法作為一種新穎的智能算法，需繼續改進。

[1] Jain A K, Murty M N, Flynn P J. Data Clustering: A Review[J]. ACM Computing Surveys, 1999, 31(3): 264-323.

[2] Ding C, Li Tao. Adaptive Dimension Reduction Using Discriminate A nalysis and K-means Clustering[C]//Proc. of the 24th International Conference on Machine Learning. New York, USA: ACM Press, 2007: 521-528.

[3] Chen Xinq uan, P eng Hong, Hu Jing-song. K-medoids Substitution C lustering Method and a New C lustering Validity Index Method[C]//Proc. of the 6th World Congress on Intelligent Control and Automati on. [S. l.]: IEEE Press, 2006: 5896-5900.

[4] Han Jiawei, Kamber M, Jian Pei. Data Mining Concepts and Techniques[M]. 2nd ed. [S. l.]: Morgan Kaufmann Publishers, 2006.

[5] 雷秀娟. 群智能優化算法及其應用[M]. 北京: 科學出版社, 2012.

[6] Y ang Xinshe. Nature-inspired Metaheuristic Algorithms[M]. [S. l.]: Luniver Press, 2008.

[7] Yang Xinshe. Firefly Algorithms for Multimodal Optimization[C]//Proc. of the 5th International Conference on Stochastic Algorithms: Foundations and Applications. Berlin, Germany: Springer-Verlag, 2009: 169-178.

[8] 袁際軍. 基于多目標螢火蟲算法的可調節產品族優化設計[J]. 計算機集成制造系統, 2012, 18(8): 1801-1809.

[9] 周永權, 黃正新. 求解TSP的人工螢火蟲群優化算法[J].控制與決策, 2012, 27(12): 1816-1821.

[10] 郭麗萍, 李向濤, 谷文祥, 等. 改進的螢火蟲算法求解阻塞流水線調度問題[J]. 智能系統學報, 2013, 8(1): 1-7.

[11] 胡明生, 賈志娟, 吉曉宇, 等. 基于改進螢火蟲群的區域災害鏈挖掘方法[J]. 計算機應用與軟件, 2012, 29(11): 29-31.

[12] Dunham M H. 數據挖掘教程[M]. 郭崇慧, 田鳳占, 靳曉明, 等, 譯. 北京: 清華大學出版社, 2005.

[13] Z hang J un, Huang Deshuang, Lo k T M, et a l. A No vel Adaptive Sequential Niche T echnique for Multimodal Function Optimization[J]. Neurocomputing, 2006, 69(16/18): 2396-2401.

[14] 喻壽益, 郭觀七. 一種改善遺傳算法全局搜索性能的小生境技術[J]. 信息與控制, 2001, 30(6): 526-530.

[15] 劉靖明, 韓麗川. 粒子群優化k均值的混合聚類算法研究[J]. 中國管理科學, 2004, 12(10): 96-99.

[16] Zhang Aidong. Protein Interaction Networks[M]. New York, USA: Cambridge University Press, 2009.

編輯 顧逸斐

New Partition Clustering Algorithm of Niching Firefly

WANG Chong, LEI Xiu-juan

(School of Computer Science, Shaanxi Normal University, Xi’an 710062, China)

Traditional partition clustering method has the problem of over-reliance on the initial cluster centers and the method is prone to fall into local optimum. So an improved partition clustering algorithm based on the firefly algorithm is proposed. The algorithm considers a firefly as a set of cluster centers and class cohesion is rega rded as brightness of the fi refly. Then find the optimal cluste ring center by the fireflies attracting each other. In the process of opt imization, randomly distributed fi refly population is used to overco me the problem of over-reliance on the initial cluster centers and adaptive step st rategy is adopted to st rengthen the ability to find the exa ct solution of the algorithm. In order to prevent the algorithm from local optimum for population concentration, the niche technology is introduced to improve the diversity of the fireflies’ population. Experimental results indicate that the algorithm is improved in clustering precisio n and stability compared with traditional clustering algorithm.

partition clustering; clustering center; local optimum; firefly algorithm; adaptive step; niche

10.3969/j.issn.1000-3428.2014.05.036

國家自然科學青年基金資助項目(61100164, 61 173190)；中央高校基本科研業務費專項基金資助項目(GK201302025)；教育部留學回國人員科研啟動基金資助項目(教外司留[2012]1707號)；陜西省2010年自然科學基礎研究計劃青年基金資助項目(2010JQ 8034)。

王 沖(1985－)，男，碩士研究生，主研方向：數據挖掘，智能計算；雷秀娟，教授、博士、CCF會員。

2013-04-07

2013-05-16E-mail：alaso2009@126.com

1000-3428(2014)05-0173-05

A

TP391.4