融合并行混沌螢火蟲算法的K-調和均值聚類

朱書偉，周治平,張道文

(江南大學 物聯網工程學院，江蘇 無錫 214122)

?

融合并行混沌螢火蟲算法的K-調和均值聚類

朱書偉，周治平,張道文

(江南大學 物聯網工程學院，江蘇 無錫 214122)

摘要：針對K-調和均值算法易陷于局部最優的缺點，提出一種基于改進螢火蟲算法(firefly algorithm, FA)的K-調和均值聚類算法。將基于FA的粗搜索與基于并行混沌優化FA的精細搜索相結合，其中精細搜索部分首先通過FA搜索到當前最優解及次優解，然后通過改進的logistic映射與并行混沌優化策略產生混沌序列在其附近直接搜索，以增強算法的尋優性能。最終，將這種改進的FA用于K-調和均值算法聚類中心的優化。實驗結果表明：該算法不但對幾種測試函數具有更高的搜索精度，而且對6種數據集的聚類結果均有一定的改善，有效地抑制了K-調和均值算法陷于局部最優的問題，提高了聚類準確性和穩定性。

關鍵詞：K-調和均值；局部最優；螢火蟲算法；聚類；并行混沌優化；混沌局部搜索；映射模型；種群多樣性

中文引用格式：朱書偉，周治平, 張道文. 融合并行混沌螢火蟲算法的K-調和均值聚類[J]. 智能系統學報， 2015, 10(6): 872-880.

聚類分析是一種廣泛使用的數據分析方法，一直被應用于多個領域，特別是在數據挖掘、模式識別、圖像處理等領域應用十分廣泛。K-means[1]是最經典且使用最為廣泛的聚類算法，其過程簡單快捷，容易實現。為了克服K-means對初始聚類中心敏感的缺陷，Zhang等[2]于1999年提出一種K-調和均值(K-harmonic means, KHM)算法，具有較高的穩定性、收斂速度快，但由于其與K-means同樣基于劃分的原理，仍存在易陷于局部最優的問題。

目前，對于KHM算法的研究主要是結合智能優化算法進行改進，以充分利用其全局搜索能力，如融合粒子群[3]、變鄰域搜索[4]、改進候選組搜索[5]等混合聚類算法。此外，將模糊概念引入KHM中也得到了一定的關注[6-7]。目前，各種群智能優化算法已被廣泛地應用于各個領域中[8-11]，并且依據沒有免費的午餐定律，本文提出新的混合聚類算法。螢火蟲算法(firefly algorithm, FA)是由劍橋學者Yang等[12-13]在2008年提出的一種新穎的群智能算法，具有結構簡單、可調參數少、宜于并行處理等特點，可以有效解決各種優化問題，并能夠成功應用到聚類問題中提高算法的準確性和魯棒性[14]。很多學者已經對它開展了不少研究工作，引入混沌原理改進的FA具有一定的優勢，Fister等[15]對現有的混沌螢火蟲算法(chaos-based firefly algorithm, CFA)進行了總結，它們的主要思想都是基于算法參數的改進，其中Gandomi等[16]采用各種混沌映射模型進行了比較全面的對比分析。然而，僅對參數的調整無法更全面有效地利用混沌優化的優點，混沌局部搜索(chaotic local search, CLS)[9-10]是一種能夠有效提高算法優化性能的策略。

本文從進一步提高FA的優化性能出發，提出一種新穎的CFA，并將其融入到KHM以獲得一種更有效的混合聚類方法。在FA中引入一種并行混沌局部搜索策略，將CLS與并行混沌優化(parallel chaotic optimization, PCO)[17-18]相結合，提高FA的局部搜索能力，具有更高的搜索效率，并能夠有效避免局部最優。將這種改進的CFA融入到KHM中優化其目標函數，通過對實際數據集的實驗可以看出本文所提的聚類算法能夠獲得更好的性能指標，有效抑制了陷入局部最優的問題。

1算法概念與定義

1.1K-調和均值算法

K-調和均值算法的原理基本上與K-means是相似的，不同的是其使用調和均值(harmonic means, HM)代替算術均值來計算目標函數，能夠有效解決對初始類中心點選取的敏感性問題。假定數據集X=[x1x2…xn]包含n個數據，它們被劃分到k個聚類簇，每個簇的中心用cj(j=1,2,…,k)表示，KHM的目標函數為[3]

(1)

這里采用歐式距離計算樣本到聚類中心的距離，參數p對算法的性能具有重要的影響，且當p≥2時聚類的效果比較好[2]。算法通過不斷地迭代使目標函數值不斷減小并保持穩定，每次迭代過程中，各個簇的中心點cj(j=1,2,…，k)的更新如下[3]。

(2)

式中：成員函數mKHM和權重函數wKHM的定義分別為式(3)和式(4)。

(3)

(4)

1.2螢火蟲算法的相關定義

在FA中螢火蟲彼此吸引主要取決于2個因素：亮度和吸引度。亮度決定了個體所處位置的好壞及其移動方向，吸引度決定了移動的距離，通過亮度和吸引度的不斷更新，實現目標優化。通常直接利用目標函數值的大小表示螢火蟲i的亮度Ii，即Ii=f(xi), xi=[xi1xi2…xid]。FA的相關定義如下[12-13]：

定義1螢火蟲i與j之間的吸引度為

(5)

式中：β0為在r=0處的吸引度，一般可取值為1；γ為光強吸收系數，對算法的性能具有重要的影響，通常情況下可以取γ=1；rij為螢火蟲i與j之間的空間距離，一般采用歐氏距離計算。

定義2螢火蟲i被更亮的螢火蟲j吸引而移動的位置為

(6)

式中：xi、xj為螢火蟲i和j的位置；α為步長因子，可設為常數；εi為服從均勻分布的隨機數向量。

2基于改進FA的K-調和均值聚類

2.1并行混沌局部搜索策略改進的FA

基本的FA缺乏變異機制，當處于局部極值時難以擺脫，且當前最優解xpg周圍是搜索到更優解的最有利的區域，而FA在優化過程中采用對其隨機擾動的方式，搜索效率不高。混沌優化方法能夠有效地跳出局部最優并搜索到全局最優解，現有文獻對混沌模型的研究非常廣泛，如logistic映射、Sinusoidal映射、Gaussian映射等[16,19]。文獻[9-10]中采取一種改進logistic映射分別與粒子群(particleswarmoptimization,PSO)算法和差分進化算法融合提出2種有效的基于CLS的混合優化算法，成功用于短期梯級水電系統調度問題，并且在文獻[19]中驗證了這種混沌映射的優勢，它具有較大的李雅普諾夫指數。logistic映射模型為[19]

(7)

式中：l表示迭代次數，需要注意的是混沌變量初始值y(0)?{0.25,0.5,0.75}，若設置y(l)=(z(l)+1)/2，則可以獲得改進的logistic映射如式(8)[19]：

(8)

并且其概率密度分布表達式為

(9)

由式(9)可以看出改進logistic映射可以將混沌變量的搜索空間拓展到(-1,1)，在接近邊界-1和1處具有較大的概率密度值，因此具有更好的遍歷性、隨機性。因此，本文利用改進logistic映射在當前最優解附近直接搜索，其本質上屬于一種混沌干擾法，即產生許多局部最優解的鄰域點，以增強搜索到全局最優解的概率。與此同時，適應度值僅次于最優解xpg的次優解xps同樣對搜索到更優解具有一定的價值，文獻[20]中以最優點和次優點為基礎進行反射、延伸、收縮等步驟的單純形法也為本文提供一定的啟發。為了更直觀地分析，在圖1中分別給出二維的單峰和多峰搜索空間的2種特殊情況的次優解與最優解局部搜索區域，它們的局部搜索半徑均相等，并且假定越往內適應度值越好。從圖1(a)、(b)中可見2種特殊情況下次優解相對于最優解均具有更好的搜索潛力。

(a)單峰

(b)多峰圖1　2種特殊情況的最優解與次優解局部搜索區域Fig.1　Two particular types of local search region around the best and second best solutions

為了進一步提高搜索效率，提出一種并行混沌局部搜索(parallelchaoticlocalsearch,PCLS)策略，采用并行混沌優化的思想產生N個混沌局部變量對次優解和最優解并行擾動，不但克服傳統CLS的串行機制搜索精確解效率不高、收斂穩定性不強等缺點[9-10]，還能夠有效地兼顧最優解與次優解。當最優解和次優解接近時可將它們的作用視為相等，不接近時則能夠有效地拓展局部搜索空間。每次迭代后取N個并行變量與xpg和xps綜合排序獲得新的最優解和次優解，有效地提高算法搜索能力。

考慮到文獻[17-18]中PCO結合了粗搜索與細搜索的策略以平衡算法的探索與開發性能，為了使并行混沌局部搜索螢火蟲算法(parallelchaoticlocalsearchfireflyalgorithm,PCLSFA)在前期進行一定的粗搜索，可在前Tmax1次迭代直接執行FA，PCLSFA的具體過程為：

1)初始化螢火蟲個體的位置并計算其對應的目標函數值Ii作為亮度，初始化迭代次數t=0，最大迭代次數設為Tmax，粗搜索迭代次數Tmax1。

2)執行FA不斷更新亮度，最亮的個體即為當前最優解xpg，并且次優解為xps，若t>Tmax1，則采用PCLS在它們附近尋優作為細搜索。

3)設置當前混沌搜索次數l=0，在上文幾個斷點外的區域初始化混沌變量-1

②混沌變量與收縮因子βt成比例，通過混沌擾動產生N個新變量如式(10)所示。

(10)

式中：lPCLS為并行混沌局部搜索的范圍，可將其設置為0.01l~0.1l，l為變量尺度，若ub、lb分別為變量的上下界，則取l=(ub-lb)/2，收縮因子βt為

(11)

式中：C是一個用于控制PCLS精度的正數，根據實驗分析可在[1,10]內選取，一般對于較難搜索到全局最優的問題取較小值。求得N個新變量組成的矩陣為

(12)

③計算每個新變量所對應的目標函數值為f(yi(l+1))，并將Y(l+1)與xpg(l+1)、xps(l+1)合并，對這N+2個變量的適應度值進行排序，得到第l+1次迭代中的最優解xpg(l+1)和次優解xps(l+1)。

④l=l+1，若l

4)t=t+1，若t

2.2提高種群多樣性的策略

由于FA缺乏保持種群多樣性的操作，降低了算法探索到全局最優解的能力，因此需要采取一定的措施來解決這一問題。本文中算法每迭代Np次時，找出適應度值最差的nc%的個體并采用混沌重構法生成新的個體替代它們。對于各維尺度相等的優化問題，直接計算出當前種群所有維空間的最大值xmax和最小值xmin作為各維的統一邊界。對于各維尺度不相等的優化問題，對邊界向量不斷地收縮，初始時第j維的邊界等于定義域[aj,bj]，當達到第Np次迭代的最優個體為x*，根據式(13)收縮邊界。

(13)

式中：φ∈(0,0.5)，并且為了保證新的邊界范圍不會越界，對其進行相應的處理為：若ajnewbj，則bjnew=bj。然后根據式(7)的logistic映射生成比例為nc%的Nc個在(0,1)上的向量Cxi(i=1,2,…,Nc)如式(14)所示。

(14)

最后再將其轉換到當前種群變量的取值空間如式(15)所示，獲得替換種群并更新其適應度值。

(15)

這里隨著迭代次數的增加對邊界范圍不斷收縮，在各個不同階段生成不同尺度的混沌變量，能夠避免直接根據初始的定義域隨機生成替代個體時效率不高的問題，且同樣能夠改善種群多樣性。

2.3改進FA的收斂性分析及復雜度分析

目前，FA還沒有很完備的數學理論基礎[12-13]，但已有的仿真實驗結果表明FA具有較高的尋優精度和收斂速度，是一種有效的優化方法。本文改進算法與基本FA的不同之處為迭代Tmax1次后增加了PCLS過程，故只需證明3)過程的收斂性，即可證明PCLSFA的收斂性優于FA。從測度論上進行分析，由于PCLS屬于下降算法，并且它具有很好的遍歷性，因而設Rg表示全局最優點x*的可行域。總迭代次數為t時(t>Tmax1)，在執行2)后的當前最優解xpg和次優解xps落入Rg的事件集合為A0，P(A0)≤1，PCLS每次迭代后產生的序列矩陣y(l)且與xpg(l)、xps(l)(l=1,2,…,Cmax)合并后落入Rg的事件集合為Al，因此A1?A2?…?ACmax，概率測度單調不減，故P(ACmax)≥…≥P(A2)≥P(A1)。可知執行3)之后具有更高的概率落入全局最優點x*的可行域，故PCLSFA的收斂性優于FA，接下來通過對基準函數的仿真實驗能夠進一步驗證其收斂性。此外，當忽略對目標函數的計算時，FA的時間復雜度為O(TmaxNpop2)，且PCLSFA的時間復雜度為O(TmaxNpop2+Tmax2CmaxN)，(Tmax2=Tmax-Tmax1)。

2.4KHM-PCLSFA算法流程

本文采用K-調和均值的目標函數KHM(X,C)作為螢火蟲i的亮度Ii，并以此確定其移動方向，其本質上是將聚類問題轉化為一種優化問題。若k為聚類的數量，m為數據的維數，則用一個k×m列的一維向量x=(x11,x12,…，x1m,…,xk1,xk2,…，xkm)來表示一個聚類中心，即一個螢火蟲個體。由于算法對初始值不敏感，可從數據集中隨機選擇k個不同的點并對其進行較小的擾動以構成一個中心向量x，確定Psize個這樣的向量作為種群初始位置。由于本文算法的總迭代次數Itermax較小，不需要執行粗搜索。

綜上所述，本文算法KHM-PCLSFA的流程為：

1)初始化算法的基本參數γ、 α、β、Cmax、 N、l并隨機初始化螢火蟲種群的位置。

2)根據螢火蟲的位置計算其目標函數值作為亮度，初始化當前迭代次數gen=0。

3)執行PCLSFA進行搜索，迭代運行gen1次，求出當前的最優個體Gbest以及對應的最優目標函數值Fg，進入下一步操作。并且，選出占種群比例為nc%的最差個體并采用混沌重構法將其替換。

4)以Gbest為聚類中心執行KHM操作，迭代運行gen2次，得到目標函數值KHM(X,C)和聚類中心并將其轉化為一維向量xKHM，若KHM(X,C)< Fg，則用xKHM代替Gbest，并以xKHM隨機替換一個螢火蟲。

5)gen=gen+1，若gen

若數據集中有n個數據，則KHM每次迭代的時間復雜度為O(knm)，本文聚類算法FA部分采用的是同步的適應度更新方式[15]，故3)中PCLSFA的時間復雜度為O(gen1(Psize(Psize+knm)+CmaxNknm))，4)中KHM的時間復雜度為O(gen2knm)，并且Psize

3實驗數據與分析

3.1PCLSFA的性能測試

選取了4個標準的無約束測試函數f1~f4[17-18]:

Ackley(xi∈[-30,30])、Rosenbrock(xi∈[-2.048,2.048])、Rastrigin(xi∈[-5.12,5.12])、Griewank(xi∈[-600,600]) 進行仿真測試，它們的最優解都是0。通過FA、采用串行CLS分別改進PSO和FA算法的CLSPSO[9]和CLSFA進行對比分析，以驗證PCLSFA的收斂性能及尋優能力。各算法種群規模都為Npop=40，最大迭代數Tmax=2 000，3種具有CLS機制的算法中取Cmax=10，C=5。考慮FA對不同函數的收斂性能不同，在CLSFA和PCLSFA前期執行粗搜索的迭代數也不相同，對f1和f4取Tmax1=500，對f2取Tmax1=0，對f3取Tmax1=200。CLSPSO中采用線性遞減的慣性權重w[9]，且wmax=0.9，wmin=0.4，學習因子為c1=c2=1.496。FA型算法中統一設置γ=1，隨機步長α隨著迭代次數t的增加不斷減小為

仿真實驗基于MATLAB2010b平臺，計算機的硬件配置為：IntelCorei5-4 200MCPU2.5GHz、4GBRAM。各函數的維數均為30，每種算法獨立運行30次，計算各自的最大值、最小值、平均值和標準差，記錄至表1。對各函數的收斂曲線為30次運行的平均結果，分別如圖2所示，為了更明顯的比較，圖中縱坐標是對最優解求lg(f )后的平均值。

表1　4個基準函數的實驗結果

根據表1可見，PCLSFA對各函數求出的最優解的平均值及標準差均為最小，表明算法具有較高的尋優精度與穩定性。雖然對f1和f2，CLSPSO能搜索到更佳的最小值，但相應的概率較小，從其偏大的平均值和標準差可以看出。并且，CLSFA對于f1和f4能夠獲得的最小值與PCLSFA接近，但其很不穩定使其平均值相對較差，有效驗證了并行CLS相對于串行CLS的優勢。由圖2可見PCLSFA對f1和f4的收斂性均取得了顯著的提高，對于相對較難尋優的f2和f3也取得了一定的提高。因此，表1和圖2中的實驗結果有效驗證了本文算法的收斂性。盡管PCLSFA對復雜函數的尋優精度方面還有待改進，但是本文中其擁有最好的尋優能力，表明了PCLS機制的引入是有效的。

3.2KHM-PCLSFA的實驗數據與分析

為了驗證本文算法的聚類性能，選取了UCI數據庫中的6個常用的數據集Iris、Ionosphere、Wine、Image Segmentation(本文簡稱為Image)、CMC和Satellite進行測試，它們的特性如表2所示。

(a) f1: Ackley

(b)f2: Rosenbrock

(c)f3: Rastrigin

(d)f4: Griewank圖2　各函數的收斂曲線Fig.2　The convergence curves for test functions

數據集類數維數數據個數Iris34150Ionosphere233351Wine313178Image719210CMC391473Satellite6336435

分別采用KHM、KHM-FA、KHM-PSO[3]和本文的KHM-PCLSFA對幾種數據集進行實驗，其中KHM-FA與文本算法的不同體現在2.1節的3)中執行的是FA。各算法參數設置為：種群規模與文獻[3]保持一致Psize=18；KHM的最大迭代次數Maxgen=100，且在迭代過程中若目標函數值不再變化則停止；3種混合聚類算法各部分迭代次數統一設置為Itermax=5，gen1=8，gen2=10。KHM-PSO中PSO的相關參數為w=0.729 8，c1=c2=1.496，FA及PCLSFA的相關參數為γ=1，α=0.1，β同式(17)。這里為了控制PCLS的執行時間，取Cmax=4，N=6，C=3，lPCLS=0.1l。本文分別取p=2.5、3、3.5時對聚類結果進行比較，每種算法獨立運行20次，計算各自的KHM(X,C)、F-measure和運行時間的平均值，并分別記錄在表3~表5中，需注意其中數據集Ionosphere用Sphere表示。

從表3~5可以看出對不同特性的數據集，3種混合聚類算法所得的KHM(X,C)和F-measure值相對于KHM算法均得到了一定的改善。從KHM(X,C)值的降低看出，Iris和Ionosphere在p=3.5時最大程度均降低了0.56%；Wine在p=3.5時最大程度降低了47.77%；Image在p=3.5時最大程度降低了78.91%；CMC在p=3時最大程度降低了0.13%；Satellite在p=3.5時最大程度降低了0.28%。從F-measure值的提升可以看出，Wine在p=3時最大程度提高了5.79%；Image在p=3時最大程度提高了1.63%；CMC在p=3.5時最大程度提高了1.10%；Satellite在p=3時最大程度提高了2.23%。對于Iris和Ionosphere，3種混合算法的F-measure難以獲得提高，這里主要通過KHM(X,C)值的降低看出3種混合聚類算法的性能改善，其中本文算法能夠獲得最小的值，表現出更好的尋優能力。對于Wine和Satellite，幾種混合聚類算法的F-measure均取得比較明顯的提高。雖然對于CMC和Image的F-measure提高有時比較有限，但是對KHM(X,C)的降低取得了不錯的效果，尤其是對于Image，比如在p=2.5時發現KHM算法總是會早熟收斂于KHM(X,C)=9.636 4×107左右的狀態，而實驗中算法可獲得的實際最優值在2.232 6×107左右，這時使得其最終的均值較大，而3種混合算法能夠有效減少陷入局部最優的次數，可以看出其均值都有較大程度的降低。

表3　p=2.5時4種算法實驗結果

此外，對于Satellite在p=3.5時，KHMPSO的目標函數值為最小，而其Fmeasure值卻低于其他聚類算法，其中的原因值得進一步研究。經過綜合對比分析，比較不同p值下的聚類結果可以看出，本文算法在總體上具有最佳的聚類準確性和穩定性，并且對于較復雜數據的改進效果更明顯，能夠有效避免陷入局部最優解。3種混合聚類算法中都引入了群智能算法的搜索過程，因此它們的運行時間大于KHM，并且本文算法中又引入了PCLS策略，使得其運行時間更長一些，這無法滿足于數據規模非常大的聚類問題。在時間效率要求不是很高時適當增加PCLSFA的搜索次數能夠進一步獲得更佳的結果，并且在很多情況下算法精度方面的要求也顯得更為重要。

表4　p=3時4種算法實驗結果

表5　p=3.5時各算法實驗結果

4結束語

由于傳統的KHM算法具有易陷于局部最優解的問題，本文基于一種高效的群智能優化算法提出了一種混合的聚類算法，在KHM中融合了混沌優化改進的螢火蟲算法，不斷優化其聚類中心。實驗結果表明，本文算法的綜合性能優于KHM以及2種混合聚類算法KHM-FA和KHM-PSO，具有更高的聚類準確性和穩定性，能夠有效地避免陷入局部最優。但是本文算法的運行時間相對比較長，在數據量較大的情況下具有較大的計算開銷而影響了算法的效率，接下來可以針對算法效率的改善開展進一步研究工作。此外，可以嘗試將PCLSFA應用于其他的優化問題中。

參考文獻:

[1]JAIN A K. Data clustering: 50 years beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8): 651-666.

[2]ZHANG Bin, HSU M, DAYAL U. K-harmonic means-a data clustering algorithm. Technical Report HPL-1999-124[R]. Hewlett-Packard Laboratories, 1999.

[3]YANG Fengqin, SUN Tieli, ZHANG Changhai. An efficient hybrid data clustering method based on K-harmonic means and particle swarm optimization[J]. Expert Systems with Applications, 2009, 36(6): 9847-9852.

[4]ALGUWAIZANI A, HANSEN P, MLADENOVIC N, et al. Variable neighborhood search for harmonic means clustering[J]. Applied Mathematical Modelling, 2011, 35(6): 2688-2694.

[5]HUNG C H, CHIOU H M, YANG Weining. Candidate groups search for K-harmonic means data clustering[J]. Applied Mathematical Modelling, 2013, 37(24): 10123-10128.

[6]汪中, 劉貴全, 陳恩紅. 基于模糊K-harmonic means的譜聚類算法[J]. 智能系統學報, 2009, 4(2): 95-99.

WANG Zhong, LIU Guiquan, CHEN Enhong. A spectral clustering algorithm based on fuzzy K-harmonic means[J]. CAAI Transactions on Intelligent Systems, 2009, 4(2): 95-99.

[7]WU Xiaohong, WU Bin, SUN Jun, et al. A hybrid fuzzy K-harmonic means clustering algorithm[J]. Applied Mathematical Modelling, 2015, 39(12): 3398-3409.

[8]王建峰, 孫超, 姜守達. 基于粒子群優化的組合測試數據生成算法[J]. 哈爾濱工程大學學報, 2013, 34(4): 477-482.

WANG Jianfeng, SUN Chao, JIANG Shouda. Improved algorithm for combinatorial test data generation based on particle swarm optimization[J]. Journal of Harbin Engineering University, 2013, 34(4): 477-482.

[9]HE Yaoyao, YANG Shanlin, XU Qifa. Short-term cascaded hydroelectric system scheduling based on chaotic particle swarm optimization using improved logistic map[J]. Communications in Nonlinear Science and Numerical Simulation, 2013, 18(7): 1746-1756.

[10]HE Yaoyao, XU Qifa, YANG Shanlin, et al. A novel chaotic differential evolution algorithm for short-term cascaded hydroelectric system scheduling[J]. International Journal of Electrical Power & Energy Systems, 2014, 61: 455-462.

[11]廖煜雷, 劉鵬, 王建, 等. 基于改進人工魚群算法的無人艇控制參數優化[J]. 哈爾濱工程大學學報, 2014, 35(7): 800-806.

LIAO Yulei, LIU Peng, WANG Jian, et al. Control parameter optimization for the unmanned surface vehicle with the improved artificial fish swarm algorithm[J]. Journal of Harbin Engineering University, 2014, 35(7): 800-806.

[12]YANG Xinshe. Firefly algorithm, stochastic test functions and design optimisation[J]. International Journal of Bio-Inspired Computation, 2010, 2(2): 78-84.

[13]趙玉新, YANG X S, 劉利強. 新興元啟發式優化方法[M]. 北京: 科學出版社, 2013: 148-157.

[14]SENTHILNATH J, OMKAR S N, MANI V. Clustering using firefly algorithm: performance study[J]. Swarm and Evolutionary Computation, 2011, 1(3): 164-171.

[15] FISTER Jr I, PERC M, KAMAL S M. A review of chaos-based firefly algorithms: perspectives and research challenges[J]. Applied Mathematics and Computation, 2015, 252: 155-165.

[16]GANDOMI A H, YANG X S, TALATAHARI S, et al. Firefly algorithm with chaos[J]. Communications in Nonlinear Science and Numerical Simulation, 2013, 18(1): 89-98.

[17]YUAN Xiaofang, ZHAO Jingyi, YANG Yimin, et al. Hybrid parallel chaos optimization algorithm with harmony search algorithm[J]. Applied Soft Computing, 2014, 17: 12-22.

[18]YUAN Xiaofang, ZHANG Ting, XIANG Yongzhong, et al. Parallel chaos optimization algorithm with migration and merging operation[J]. Applied Soft Computing, 2015, 35: 591-604.

[19]YANG Dixiong, LIU Zhenjun, ZHOU Jilei. Chaos optimization algorithms based on chaotic maps with different probability distribution and search speed for global optimization[J]. Communications in Nonlinear Science and Numerical Simulation, 2014, 19(4): 1229-1246.

[20]莫愿斌, 馬彥追, 鄭巧燕, 等. 單純形法的改進螢火蟲算法及其在非線性方程組求解中的應用[J]. 智能系統學報, 2014, 9(6): 747-755.

MO Yuanbin, MA Yanzhui, ZHENG Qiaoyan, et al. Improved firefly algorithm based on simplex method and its application in solving non-linear equation groups[J]. CAAI Transactions on Intelligent Systems, 2014, 9(6): 747-755.

朱書偉，男，1990年生，碩士研究生，主要研究方向為人工智能與模式識別。

周治平，男，1962年生，教授，博士，主要研究方向為智能檢測、自動化裝置、網絡安全等。

張道文，男，1989年生，碩士研究生，主要研究方向為數據挖掘與人工智能。

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20151110.1354.006.html

英文引用格式：ZHU Shuwei, ZHOU Zhiping, ZHANG Daowen. K-harmonic means clustering merged with parallel chaotic firefly algorithm[J]. CAAI Transactions on Intelligent Systems, 2015, 10(6): 872-880.

K-harmonic means clustering merged with

parallel chaotic firefly algorithm

ZHU Shuwei, ZHOU Zhiping, ZHANG Daowen

(School of Internet of Things Engineering, Jiangnan University, Wuxi 214122, China)

Abstract：The K-harmonic means algorithm (KHM) has the disadvantage of easily falling into a local optimum. To solve this problem, we propose a hybrid KHM based on an improved firefly algorithm (FA). In this paper, we combined raw FA-based searching with parallel chaotic FA-based elaborate searching. In the elaborate searching, we found the current best and second-best solutions using the FA, then we used an improved logistic map model combined with parallel chaotic optimization to search this area in order to enhance the searching ability of the algorithm. Finally, we used the improved FA to optimize the cluster centers obtained by the KHM. Experimental results demonstrate that the proposed algorithm not only had higher search precision for several test functions, but also improved the clustering accuracy and stability of six datasets, effectively avoiding being trapped into a local optimum.

Keywords：K-harmonic means; local optimum; firefly algorithm; clustering; parallel chaotic optimization; chaotic local search; map model; diversity of population

作者簡介：

通信作者：朱書偉. E-mail：6131905056@vip.jiangnan.edu.cn.

基金項目：江蘇省產學研聯合創新資金-前瞻性聯合研究基金資助項目(BY2013015-33).

收稿日期：2015-05-27. 網絡出版日期：2015-11-10.

中圖分類號：TP18

文獻標志碼：A

文章編號：1673-4785(2015)06-0872-09

DOI:10.11992.tis.201505043