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

◆馬翩翩 張新剛 梁晶晶

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

◆馬翩翩 張新剛 梁晶晶

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

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

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

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

1 近鄰傳播聚類算法

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

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

當=時，

當=

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

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

2 螢火蟲算法

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

定義1 相對熒光亮度

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

定義2 吸引度

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

定義3 位置更新

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

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

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

（1）加載數據集同時對數據進行歸一化處理。

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

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

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

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

（6）計算每組偏向參數p和阻尼因子的聚類結果

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

（8）判斷是否達到結束條件，否則轉回（3）。

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

4 實驗與分析

4.1 數據源

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

表1 數據集

4.2 實驗環(huán)境

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

4.3 實驗方法

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

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

（2）Rand指數（）

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

表2 簇個數

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

表3 聚類正確率ACC

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

表4 聚類RI指數

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

表5 聚類運行時間

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

5 總結

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

[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].計算機系統應用，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.

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