◆馬翩翩 張新剛 梁晶晶

基于螢火蟲算法的近鄰傳播聚類研究

◆馬翩翩 張新剛 梁晶晶

（南陽師范學院計算機與信息技術(shù)學院 河南 473061）

針對近鄰傳播聚類（AP）中偏向參數(shù)和阻尼因子對聚類效果的影響，將偏向參數(shù)和阻尼因子作為螢火蟲算法中的亮度和吸引度，通過群體智能算法在搜索空間中尋找偏向參數(shù)和阻尼因子，從而提高AP算法的聚類質(zhì)量。實驗表明，該算法能提高聚類質(zhì)量。

近鄰傳播；偏向參數(shù)；阻尼因子；螢火蟲算法

聚類算法屬于機器學習中的無監(jiān)督學習，尋找數(shù)據(jù)內(nèi)在特征的一種劃分過程。近鄰傳播聚類算法是BJ Frey和D Dueck在2007年提出的近年來發(fā)展較快聚類算法[1]。該算法在聚類過程將所有的數(shù)據(jù)點作為潛在簇中心，通過消息傳遞確定最終簇中心，在數(shù)據(jù)流聚類、圖像處理、文本聚類、基因序列等領(lǐng)域都有廣泛的應用。但是該算法的最終聚類結(jié)果受偏向參數(shù)的影響，若偏向參數(shù)取值過大，則最終劃分的簇的個數(shù)偏多；若偏向參數(shù)取值過少，則最終劃分的簇的個數(shù)偏少。針對偏向參數(shù)對聚類結(jié)果影響的問題，不同的學者從不同的角度進行了改進：為了克服設(shè)定的偏向參數(shù)和阻尼系數(shù)對聚類結(jié)果的影響，文獻[2]設(shè)計了一種根據(jù)數(shù)據(jù)結(jié)構(gòu)自動調(diào)整參數(shù)的核函數(shù)，對核空間中的數(shù)據(jù)集進行近鄰傳播聚類；文獻[3]提出了將偏向參數(shù)和阻尼系數(shù)作為粒子群算法中的粒子，使用粒子群算法對系數(shù)尋優(yōu)，從而提高聚類質(zhì)量；文獻[4]通過改進的布谷鳥搜索對偏向參數(shù)和阻尼系數(shù)進行調(diào)整，從而提高聚類效果；文獻[5]通過對數(shù)據(jù)集構(gòu)建概率圖模型，分析數(shù)據(jù)集的概率密度，并將其注入偏向參數(shù)進而進行近鄰傳播聚類。本文則使用螢火蟲群體智能優(yōu)化算法來對近鄰傳播聚類算法中的偏向參數(shù)和阻尼因子尋優(yōu)，進而提高聚類質(zhì)量。

1 近鄰傳播聚類算法

近鄰傳播聚類算法是基于中心點的聚類算法。聚類中首先需要構(gòu)建任意點與點之間的相似度矩陣，默認為負的歐式距離，即（，）=-||x-x||2| ；其中自身與自身的相似性（，）定義為偏向參數(shù)，參數(shù)會影響最終簇個數(shù)。

其次近鄰傳播聚類算法的聚類過程是通過點與點之間的消息傳遞來實現(xiàn)的。傳遞的信息有兩類，吸引度（，）和歸屬度（，）。（，）代表的是通過和其他點的比較，數(shù)據(jù)點作為數(shù)據(jù)點的程度，具體如公式（1）所示；（，）代表的是數(shù)據(jù)點選擇數(shù)據(jù)點作為簇中心的程度，具體如公式（3）所示。

當=時，

當=

最后對于任意數(shù)據(jù)點，找到滿足（，）+（，）最大化值的點。如果=，則點為簇中心；如果≠時，則表示點屬于簇中心的成員。同時消息傳遞過程中對消息進行阻尼以防止出現(xiàn)振蕩，每個消息都被設(shè)置為和前一次迭代的乘積加上1-乘以新的更新值。具體如下所示：

最終根據(jù)所確定的簇中心將數(shù)據(jù)集劃分為個不相交的簇{l|l=1，2，…，} 其中’∩’≠=且=∪l=1使簇內(nèi)距離最小，具體如公式（7）所示。

2 螢火蟲算法

螢火蟲算法是Xin-She Yang于2008年根據(jù)自然界中螢火蟲的活動所提出來的一種群體智能優(yōu)化算法[6]。自然界中螢火蟲主要借助于亮光進行活動，光亮較強的螢火蟲吸引光亮較弱的螢火蟲；但是隨著距離的靠近，螢火蟲相對吸引力降低，在優(yōu)化算法中，用目標函數(shù)值代表亮光強度。

定義1 相對熒光亮度

其中（x）表示為第x螢火蟲的光亮程度，即聚類的目標函數(shù)值。

定義2 吸引度

其中0表示最大吸引度，r表示螢火蟲和螢火蟲的距離。

定義3 位置更新

其中x和x分別表示螢火蟲和和在空間中的兩個位置；表示的是步長因子；ε代表的是隨機數(shù)；x代表的是更新后的位置。

3 近鄰傳播聚類算法的改進

近鄰傳播聚類的改進是（FAAP）是一種基于螢火蟲算法的改進，將參數(shù)和阻尼因子看作是螢火蟲算法中的相對熒光亮度和吸引度，同時根據(jù)式（10）不斷調(diào)整偏向參數(shù)和阻尼因子的值，然后進行近鄰傳播聚類，最終確定最優(yōu)的聚類結(jié)果?；贔A的AP算法具體過程如下：

（1）加載數(shù)據(jù)集同時對數(shù)據(jù)進行歸一化處理。

（2）在偏向參數(shù)空間和阻尼因子中隨機選擇組和值，最大迭代次數(shù)為max。

（3）依據(jù)歐式距離和偏向參數(shù)建立相似度矩陣。

（4）根據(jù)公式（1）、（2）、（3）、（4）、（5）、（6）執(zhí)行近鄰傳播聚類。

（5）判斷是否達到聚類結(jié)束條件，如不結(jié)束則返回步驟（4）中。

（6）計算每組偏向參數(shù)p和阻尼因子的聚類結(jié)果

（7）根據(jù)目標函數(shù)值和式（8）、（9）（10）進行移動。

（8）判斷是否達到結(jié)束條件，否則轉(zhuǎn)回（3）。

在步驟（2）中參數(shù)的搜索空間在文獻[7]得知的下限為=1-2，1為聚類結(jié)果只有1個簇的時候的凈相似度值，2為聚類結(jié)果簇為2的凈相似度值。具體公式（11）、（12）所知。在文獻[8]中可以得因此的上限取值為/2。阻尼因子的搜索范圍為[0.5，1]。

4 實驗與分析

4.1 數(shù)據(jù)源

數(shù)據(jù)源采用的是驗證機器學習的標準數(shù)據(jù)庫UCI。具體如表1所示。

表1 數(shù)據(jù)集

4.2 實驗環(huán)境

實驗環(huán)境中硬件為Intel（R） Core（TM）i7；內(nèi)存為4G；軟件依賴于Windows7操作系統(tǒng)，MATLAB R2012a。

4.3 實驗方法

實驗最大迭代次數(shù)為5000，連續(xù)收斂次數(shù)為50。將本文算法與原AP算法、自適應AAP從簇的個數(shù)準確率、芮氏指標、時間等方面對聚類結(jié)果進行評估。

準確率是指聚類結(jié)果中正確的樣本數(shù)占總樣本數(shù)的比例。為最終簇的個數(shù)，L為第個簇中正確聚類的樣本數(shù)，該度量為聚類的直觀展示。

（2）Rand指數(shù)（）

指數(shù)將聚類樣本中的結(jié)果和外界簇劃分進行對比而得到的一種結(jié)果測評。表示屬于同一個簇被劃分到相同的簇中的樣本數(shù)；表示在聚類簇C中隸屬于同一簇但在參考劃分中屬于不簇的樣本數(shù)；表示在聚類結(jié)果中屬于不同簇但在參考簇中于同一簇的樣本數(shù)；表示在度量中不屬于同一簇且在參考簇中也不屬于同一簇的樣本數(shù)。

表2 簇個數(shù)

在近鄰傳播聚類過程中，因為值得設(shè)定導致最終簇的數(shù)量偏多。從表2可知AP、AAP算法中產(chǎn)生的簇數(shù)目偏多，而FAAP因為通過螢火蟲算法尋找合適的參數(shù)值所以產(chǎn)生適當個數(shù)的簇。

表3 聚類正確率ACC

由表3可知在ACC指標上FAAP算法相比較AP、AAP算法有一定的提升。如在Iris、Glass、Wine、Zoo據(jù)集中，F(xiàn)AAP算法相比較于AP算法分別提升了40.12%、37.36%、96.33%、8.9%；相較于APP算法分別提升了97.19%、29.11%、1.08倍、8.9%。

表4 聚類RI指數(shù)

由表4可知在RI指標上FAAP算法相比較AP、AAP算法有一定的提升。如在Iris、Glass、Wine、Zoo據(jù)集中，F(xiàn)AAP算法相比較于AP算法分別提升了9.73%、24.94%、10.47%、16.54%；相較于APP算法分別提升了20.33%、27.75%、10.73%、16.53%。

表5 聚類運行時間

由表5可知，本文算法的時間效率優(yōu)于算法AP、AAP。在數(shù)據(jù)集Iris、Glass、Wine、Zoo上，F(xiàn)AAP算法的運算速率較AP算法分別提升了是5.5倍、3.5倍、1.64倍、3.13倍；較AAP算法也有一定程度的提升。

5 總結(jié)

本文主要是通過在偏向參數(shù)p和阻尼因子的取值范圍內(nèi)使用螢火蟲群體智能算法FA來尋找最優(yōu)參數(shù)，同時和已有的算法AP、AAP進行了對比試驗，該算法在聚類質(zhì)量和聚類效率上有一定的提高，但是該算法在復雜數(shù)據(jù)集上還有一定的局限性，下一步將結(jié)合特征提取工程來提高聚類質(zhì)量。

[1]Frey B J，Dueck D. Clustering by passing messages between data points[J]. Science， 2007， 315（5814）：972-976.

[2]付迎丁，蘭巨龍.基于核自適應的近鄰傳播聚類算法[J]. 計算機應用研究，2012，29（5）.

[3]謝文斌，童楠，王忠秋，等. 基于粒子群的近鄰傳播算法[J].計算機系統(tǒng)應用，2014，23（3）：103-107.

[4]Jia B，Yu B，Wu Q，et al. Adaptive affinity propagation method based on improved cuckoo search[J]. Knowledge-Based Systems，2016：111.

[5]覃華，詹娟娟，蘇一丹.基于概率無向圖模型的近鄰傳播聚類算法[J].控制與決策，2017（10）.

[6]Yang X S. Firefly Algorithms for Multimodal Optimization[J]. Mathematics，2009，5792：169-178.

[7]Yu J，Cheng Q. The upper bound of the optimal number of clusters in fuzzy clustering[J]. Science in China. Series F， 2001，44（2）：119-125.

[8]王開軍，張軍英，李丹，等.自適應仿射傳播聚類[J].自動化學報，2007，33（12）：1242-1246.

河南省科技攻關(guān)項目（182102210114）；南陽師范學院校級科研項目（2019QN020）。