基于萬有引力的自適應(yīng)近鄰傳播聚類算法

王治和，常筱卿，杜 輝

（西北師范大學(xué)計算機(jī)科學(xué)與工程學(xué)院，蘭州 730070）

（*通信作者電子郵箱1478448005@qq.com）

0 引言

近鄰傳播（Affinity Propagation，AP）算法是一種新的聚類算法［1］，與K 均值聚類（K-means）和模糊C 均值（Fuzzy CMeans，F(xiàn)CM）相比，不需要確定最終的簇數(shù)。聚類中心是數(shù)據(jù)集中的現(xiàn)有數(shù)據(jù)點，而不是生成新的簇中心。該聚類算法的最大缺點是難以獲得參數(shù)（偏向參數(shù)和阻尼系數(shù)）。

為了提高AP算法的聚類效果，許多學(xué)者對該算法進(jìn)行了研究。文獻(xiàn)［2］中提出的基于自適應(yīng)屬性加權(quán)的近鄰傳播聚類（Affinity Propagation clustering algorithm based on Adaptive Feature Weight，AFW_AP）算法利用聚類對象的聚類原理和聚類間對象的耦合原理自適應(yīng)地改變屬性權(quán)重，以更新相似度矩陣，吸引力和隸屬度；文獻(xiàn)［3］中提出基于同類約束的半監(jiān)督近鄰反射傳播聚類方法（Semi-supervised Affinity Propagation clustering method with Homogeneity Constraints，HCSAP），引入了類似的約束項，改善了聚類目標(biāo)函數(shù)；文獻(xiàn)［4］中使用灰狼優(yōu)化算法和二分查找算法分別自適應(yīng)地調(diào)整偏置參數(shù)的上限、下限和中間值；文獻(xiàn)［5］中使用極大團(tuán)和勢函數(shù)計算數(shù)據(jù)樣本的概率密度，并使用該概率密度作為偏向參數(shù)；文獻(xiàn)［6］中使用二分法動態(tài)更新偏差參數(shù)并選擇有效性指標(biāo)的最佳結(jié)果。上述文獻(xiàn)研究得到了較好的聚類效果，但是存在以下兩點不足：1）沒有考慮AP 算法不適用于稀疏數(shù)據(jù)；2）在每次迭代中，正確聚類和錯誤聚類的樣本將出現(xiàn)在同一簇內(nèi)中，當(dāng)更新屬性權(quán)重時，為同一聚類中的樣本賦予相同的權(quán)重，使同一個簇內(nèi)的正確聚類和錯誤聚類的樣本更加緊密，無法獲得良好的聚類群集。鑒于這兩點不足，本文提出了基于萬有引力的自適應(yīng)近鄰傳播聚類（Adaptive Affinity Propagation clustering based on universal Gravitation，GA-AP）算法。

GA-AP算法思想來源于對文獻(xiàn)［7］的學(xué)習(xí)，發(fā)現(xiàn)萬有引力搜索機(jī)制可以更好解決AP算法不適用于稀疏數(shù)據(jù)的問題；通過對文獻(xiàn)［8-9］的學(xué)習(xí)，發(fā)現(xiàn)用分類算法可以很好地檢測出數(shù)據(jù)集中的異常點。因此本文將信息熵［10］和分類算法AdaBoost［11］相結(jié)合，以檢測每個簇內(nèi)中正確聚類和錯誤聚類的樣本點，并計算出樣本點的權(quán)值。用該權(quán)值更新樣本點從而重新調(diào)整相似度、Preference 取值、吸引度和隸屬度，重新聚類。不斷操作以上步驟直到達(dá)到最大迭代次數(shù)。實驗結(jié)果表明，與其他聚類算法相比，GA-AP算法具有更好的聚類結(jié)果。

1 AP算法

AP 算法的基本思想是將所有數(shù)據(jù)點都視為潛在的聚類中心，其次將兩對數(shù)據(jù)點之間連接起來以形成網(wǎng)絡(luò)（相似性矩陣），最后在網(wǎng)絡(luò)的每一端傳遞消息（吸引度和隸屬度）以計算每個樣本的聚類中心［12］。

現(xiàn)有X={x1，x2，…，xn}，X是n×d的矩陣，n是樣本數(shù)，d是維數(shù)。相關(guān)概念［13］如下：

1）相似度矩陣（Similarity matrix，S）：計算n個點之間的相似度（歐氏距離的負(fù)值），這些相似度形成一個相似度矩陣。

2）偏向參數(shù)（Preference）：聚類中心的參考度（不能為0），通常設(shè)置為S相似度值的中位數(shù)，該值越大，聚類中心越多的可能性越大。

3）吸引度矩陣（Responsibility，R）：點xk適合作為數(shù)據(jù)點xi的聚類中心的程度表示為R(xk，xi)。

4）隸屬度矩陣（Availability，A）：點xi選擇點xk作為其聚類中心的適合程度，記為A(xi，xk)。

5）阻尼因子（λ）：主要是起收斂作用的。

傳統(tǒng)AP算法的流程，如圖1所示。

圖1 AP算法流程Fig.1 Flowchart of AP algorithm

2 萬有引力的自適應(yīng)近鄰傳播聚類算法

2.1 算法思想

傳統(tǒng)AP聚類算法的聚類結(jié)果受參數(shù)Preference 的影響很大、不適用于稀疏數(shù)據(jù)且該算法得到的類簇內(nèi)會出現(xiàn)錯誤劃分的樣本點。為了解決這些問題，本文提出新的AP聚類算法——GA-AP算法。GA-AP算法與傳統(tǒng)AP算法的區(qū)別：1）傳統(tǒng)AP 算法容易使得稀疏數(shù)據(jù)陷入局部一致性，因此AP 算法不適用于稀疏數(shù)據(jù)；GA-AP 算法借助萬有引力搜索機(jī)制對樣本進(jìn)行全局尋優(yōu)；2）傳統(tǒng)AP算法中的Preference參數(shù)為固定值，以及傳統(tǒng)AP聚類算法得到的簇內(nèi)會出現(xiàn)錯分的樣本點，從而使得聚類結(jié)果很差。GA-AP算法首先利用信息熵和AdaBoost計算前一次迭代時每個簇內(nèi)正確聚類的樣本權(quán)重和錯誤聚類的樣本權(quán)重；其次用得到的樣本權(quán)值更新樣本特征，從而動態(tài)調(diào)整下一次迭代的相似度和偏向參數(shù)Preference，以減少簇內(nèi)錯分點和自適應(yīng)調(diào)整參數(shù)。

2.2 歐氏距離的局部性

傳統(tǒng)AP算法通常用歐氏距離來衡量對象間的相似度，但是歐氏距離表示的是空間上相鄰的數(shù)據(jù)點之間具有較高的相似性，因此，使用歐氏距離度量AP算法的相似度矩陣，很難使稀疏數(shù)據(jù)達(dá)到全局一致性，進(jìn)而嚴(yán)重影響聚類性能。

為了進(jìn)一步的說明該問題，本文用Compound數(shù)據(jù)對其進(jìn)行分析，如圖2所示。

圖2 歐氏距離無法顯示稀疏數(shù)據(jù)的全局一致性Fig.2 Euclidean distance cannot showing the global consistency of sparse data

由圖2 可以直觀看出：數(shù)據(jù)點1 與數(shù)據(jù)點2 的相似性要比數(shù)據(jù)點1與數(shù)據(jù)點3的大。但是，如果按歐氏距離作為相似度測量，則數(shù)據(jù)點1 與數(shù)據(jù)點3 的直線距離很明顯小于數(shù)據(jù)點1與數(shù)據(jù)點2 的距離，這樣數(shù)據(jù)點1 與數(shù)據(jù)點3 劃分為同一類的概率將大于數(shù)據(jù)點1與數(shù)據(jù)點2。即：用歐氏距離作為數(shù)據(jù)點相似度測量時無法反映圖2 所示的全局一致性。因此，對于稀疏數(shù)據(jù)集，AP算法簡單用歐氏距離計算數(shù)據(jù)點之間相似性會嚴(yán)重影響聚類算法的性能。

2.3 基于萬有引力的AP算法

為了解決傳統(tǒng)AP 算法使稀疏數(shù)據(jù)達(dá)不到全局一致性的問題，本文用萬有引力搜索機(jī)制對傳統(tǒng)AP算法改進(jìn)。

萬有引力定律［14-15］公式如式（1）所示：

其中：M1、M2是物體的質(zhì)量；G是常量6.67*10-11N·m2/kg2，r是物體間的距離。

萬有引力通過物體的質(zhì)量與距離反映物體間的吸引力，質(zhì)量越大，距離越近的物體吸引力越強(qiáng)，這與聚類分析中衡量對象間的相似度類似。

基于萬有引力的AP 算法是采用萬有引力搜索機(jī)制對樣本進(jìn)行全局搜索，以此衡量對象間的相似度，并將此用于AP算法提高聚類效果。

基于萬有引力的AP算法原理：通過樣本間的相互引力的作用進(jìn)行優(yōu)化搜索，每個樣本受到空間中其他樣本的引力的影響，產(chǎn)生加速度向特征相近的個體靠近。樣本集中的具有不同特征的樣本，通過萬有引力在解空間中相互吸引，樣本的引力由其特征和樣本間距離決定。樣本在引力的作用下向其特征和距離相近的其他樣本靠近，即逐漸逼近優(yōu)化問題的最優(yōu)解。具體形式如下：

假設(shè)給定現(xiàn)有X={x1，x2，…，xn}，計算數(shù)據(jù)集X的相似度公式如下：

其中：t是迭代次數(shù)對象間特征乘積之和的倒數(shù)，這里之所以取倒數(shù)是因為對象特征不同于物體的質(zhì)量?，F(xiàn)實中兩個物體的質(zhì)量越大引力越強(qiáng)，但是對于兩個樣本的特征卻相反（一個樣本的特征與其他的樣本特征越相近則該樣本對其他樣本的吸引力越強(qiáng)，其他樣本均向其靠近）；是距離度量，取值為對象間歐氏距離的2 次方；G(t)為第t次迭代的萬有引力系數(shù)，該系數(shù)隨著迭代次數(shù)的增大而動態(tài)地減小，能更好地控制搜索過程：

其中：tmax為最大迭代次數(shù)，G0和a為常量。G(t)的取值能更好地平衡算法的全局搜索能力和局部搜索能力。

為了進(jìn)一步說明該原理，對其進(jìn)行詳細(xì)分析，如圖3所示。

圖3 基于萬有引力的相似度Fig.3 Similarity based on universal gravitation

從圖3中看出：樣本點1和3為同一類，與樣本2、4是不同類的。樣本點1 和3 特征相似，與樣本點2、4 特征不相似；樣本點1 和3 距離最遠(yuǎn)，與樣本點2、4 距離近。如果用歐氏距離測量相似度，則樣本點1和3歸屬于一類的概率遠(yuǎn)小于與樣本點2、4 歸屬于一類的概率。用萬有引力測量相似度，則發(fā)現(xiàn)樣本點1 和3 的引力遠(yuǎn)大于與樣本點2、4 的引力，這說明樣本點1和3歸屬于一類的概率遠(yuǎn)大于與樣本點2和4歸屬于一類的概率。因此在AP算法中用萬有引力測量相似度，可以解決傳統(tǒng)AP算法使稀疏數(shù)據(jù)達(dá)不到全局一致性的問題。

算法2 基于萬有引力的AP 算法，給定數(shù)據(jù)集X={x1，x2，…，xn}。

步驟1 算法初始：歸屬度初始化為0，輸入?yún)?shù)λ和最大迭代次數(shù)t。

步驟2 式（2）計算相似度矩陣S(xi，xj)，將相似度矩陣的中值賦值給Preference。

步驟3 用式（5）和式（8）分別更新吸引度矩陣R和歸屬度矩陣A。

步驟4R(xk，xk)+A(xk，xk)＞0(k=1，2，…，N)時，xk是聚類中心，并將各數(shù)據(jù)分配到離其最近的中心點中。

2.4 參數(shù)Preference取值

為了降低參數(shù)Preference 取值對AP算法聚類效果的影響以及減少簇內(nèi)錯分的樣本點，本文利用信息熵和自適應(yīng)增強(qiáng)算法（AdaBoost）對該算法進(jìn)行優(yōu)化。

基于自適應(yīng)增強(qiáng)算法的AP 是用信息熵和AdaBoost 算法計算出前一次迭代的每個簇內(nèi)錯誤聚類和正確聚類的樣本點，并得到這些樣本點權(quán)值，用該權(quán)值更新樣本特征，從而為下次迭代重新獲取合適的Preference參數(shù)值。具體形式如下：

假設(shè)給定數(shù)據(jù)集X={x1，x2，…，xn}，其中xi={xi1，xi2，…，xid}∈X；類別集C={c1，c2，…，cK}，其中ci={x1′，x2′，…，xi′′}∈X，K是類別數(shù)；聚類中心集Q={q1，q2，…，qK}，其 中qi={qi1，qi2，…，qid}；數(shù)據(jù)集權(quán)值W={w1，w2，…，wn}。

算法3算法流程如下：

步驟2 進(jìn)行迭代t=1，2，…，T。

1）計算每個簇內(nèi)的每個樣本的信息熵，如：

2）找到每個簇內(nèi)錯誤的聚類樣本點（簇內(nèi)最大的樣本點信息熵）xu′和xu′所對應(yīng)的類權(quán)值wi，計算其誤差率et：

3）計算每個簇內(nèi)的每個樣本權(quán)值。

正確聚類樣本點的權(quán)值（用除x′u以外樣本點的權(quán)值分別除以2 ×(1-et)：

錯誤聚類樣本點（xu′）的權(quán)值：

步驟3 用得到的樣本點權(quán)值更新數(shù)據(jù)集。

步驟4 重新計算相似度矩陣、Preference值，重新聚類。

2.5 GA-AP的算法步驟

為了解決AP 不適用于稀疏數(shù)據(jù)的問題、降低參數(shù)Preference 值對算法的影響以及減少簇內(nèi)錯分的樣本點，本文提出了GA-AP 算法。該算法在傳統(tǒng)的AP 算法的基礎(chǔ)上采用引力搜索機(jī)制對樣本全局尋優(yōu)，有效解決了AP不適用于稀疏數(shù)據(jù)的問題，并且在此基礎(chǔ)上用信息熵與AdaBoost 算法自適應(yīng)地調(diào)整參數(shù)Preference 以及減少簇內(nèi)錯分點，提高AP 算法的聚類效果。GA-AP算法流程如圖4。

圖4 GA-AP算法流程Fig.4 Flowchart of GA-AP algorithm

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

3.1 實驗環(huán)境

實驗環(huán)境為Windows7 64 位操作系統(tǒng)，Intel Core i7 2.7 GHz CPU，16 GB 內(nèi)存，使用Matlab2016a 軟件進(jìn)行實驗。本文做了5 次實驗，取評價指標(biāo)的均值來評估算法的聚類效果。算法中的迭代次數(shù)t設(shè)置為50，阻尼因子λ為0.8，G0取值為100，a取值為20。

3.2 Preference參數(shù)的變化

Preference 參數(shù)對AP 算法有著很大的影響，Preference 值越大，則算法得到的聚類結(jié)果越好。傳統(tǒng)AP 算法的Preference 參數(shù)為固定值，而GA-AP 算法的Preference 值會隨著每次的聚類結(jié)果進(jìn)行調(diào)整以達(dá)到一個優(yōu)越的值。圖5 顯示GA-AP 算法在運行Iris、Seeds-dataset、Wine、Haberman 四組數(shù)據(jù)時，每次迭代Preference 的變化?？梢钥闯鲞@四組數(shù)據(jù)的Preference 值隨著迭代次數(shù)的增長而不斷地增大。Iris、Wine兩組數(shù)據(jù)在第30 次迭代時，Preference 取值基本達(dá)到穩(wěn)定；Seeds-dataset、Haberman兩組數(shù)據(jù)在第40次迭代時，Preference 取值基本達(dá)到穩(wěn)定。這四組數(shù)據(jù)的Preference 取值在第50次迭代時基本趨近于-1。

圖5 偏向參數(shù)值的變化Fig.5 Change of Preference

3.3 對稀疏數(shù)據(jù)的比較

GA-AP 算法克服了AP 算法不適用于稀疏數(shù)據(jù)這一不足之處。為了驗證其效果，本文選取三組數(shù)據(jù)（Threecircles、Lineblobs、Compound）在GA-AP 算法、AP 算法、K-means 算法和FCM 算法上運行，判斷GA-AP 算法是否有效地克服這一不足。效果圖為圖6。

圖6 四種算法對稀疏數(shù)據(jù)的聚類結(jié)果Fig.6 Clustering results of four algorithms on sparse data

綜合圖6 明顯看出在Threecircles、Lineblobs 和Compound三組數(shù)據(jù)上，GA-AP 算法相對于AP 算法、K-means 算法和FCM 算法在處理稀疏數(shù)據(jù)時可以得到很好的聚類效果，因此GA-AP算法能更好地平衡全局搜索能力和局部搜索能力。

3.4 與其他聚類算法性能對比

在本節(jié)中，將通過UCI 和人工數(shù)據(jù)集對GA-AP 算法進(jìn)行驗證，使用以下的數(shù)據(jù)集：UCI 數(shù)據(jù)、人工數(shù)據(jù)（Threecircles、Lineblobs）。為了更好地評估該算法的聚類性能，本文用純度（Purity）、F-measure［16-17］和準(zhǔn)確性（ACC）［18］三種評價指標(biāo)比較GA-AP 算法與AFW_AP 算法、AP 算法、K-means 算法和FCM算法的聚類結(jié)果。

表1 介紹了9 個數(shù)據(jù)集的特征，分別是數(shù)據(jù)數(shù)目、特征值和類別數(shù)。

表1 數(shù)據(jù)集的基本信息Tab.1 Basic information of datasets

為了更好地驗證GA-AP 算法的聚類效果，本文將該算法與AFW_AP 算法、AP 算法、K-means 算法和FCM 算法的聚類效果進(jìn)行對比，如表2（準(zhǔn)確率評價表）、圖7（F-measure 評價圖）和圖8（純度（Purity）評價圖）。

圖7 五種算法聚類效果F-measure評價Fig.7 F-measure evaluation of clustering effect of five algorithms

圖8 五種算法聚類效果Purity評價Fig.8 Purity evaluation of clustering effect of five algorithms

表2 五種算法聚類效果準(zhǔn)確率評價表 單位：%Tab.2 Accuracy evaluation table for clustering effect of five algorithms unit：%

從表2 可以分析出，GA-AP 算法針對Threecircles、Lineblobs、Iris、Seeds-dataset、Wine、Haberman、Lenses、Balancescale 和Glass 這9 組數(shù)據(jù)集的聚類結(jié)果的準(zhǔn)確率高于AFW_AP 算法、AP 算法、K-means 算法和FCM 算法，這說明GA-AP 算法提高聚類正確的樣本數(shù)，且其對于稀疏數(shù)據(jù)有更好的處理。如在Threecircles 數(shù)據(jù)集上，GA-AP 算法得到的ACC 為90.17%；AFW_AP 算法、AP算法、K-means算法和FCM算 法 得 到 的ACC 分 別 為82.36%、38.37%、62.33% 和61.45%。在Seeds-dataset 數(shù)據(jù)集上，GA-AP 算法得到的ACC為80.76%；AFW_AP 算法、AP 算法、K-means 算法和FCM 算法得到的ACC分別為75.13%、24.28%、35.45%和39.56%。

由圖7 可以分析出，GA-AP 算法針對Threecircles、Lineblobs、Iris、Seeds-dataset、Wine、Haberman、Lenses、Balancescale 和Glass這9組數(shù)據(jù)集的聚類結(jié)果的F-measure高于AFW_AP算法、AP算法、K-means算法和FCM算法。如在Threecircles 數(shù)據(jù)集上，GA-AP 算法得到的F-measure 為100%；AFW_AP算法、AP算法、K-means算法和FCM算法得到的F-measure 分別為59.19%、32.7%、46.38% 和49.35%。在Lenses數(shù)據(jù)集上，GA-AP算法得到的F-measure為80%；AFW_AP算法、AP算法、K-means算法和FCM算法得到的F-measure 分別為67.04%、39.80%、42.36%和45.23%。

由圖8 可以分析出，GA-AP 算法針對表1 中這9 組數(shù)據(jù)集的聚類結(jié)果的純度高于AFW_AP 算法和AP 算法，這說明GAAP算法得到的簇內(nèi)樣本數(shù)與真實標(biāo)簽的簇內(nèi)樣本數(shù)很接近。如在Lineblobs 數(shù)據(jù)集上，GA-AP 算法得到的Purity 為0.91；AFW_AP算法、AP算法、K-means算法和FCM算法得到的Purity 分別為0.87、0.22、0.25 和0.3。在Balance-scale 數(shù)據(jù)集上，GA-AP 算法得到的Purity 為0.52；AFW_AP 算法、AP 算法、K-means 算法和FCM 算法得到的Purity 分別為0.34、0.25、0.35和0.36。

結(jié)合上述實驗，從Purity、F-measure 和準(zhǔn)確率這三個評估指標(biāo)的測量結(jié)果分析出：GA-AP 算法相比于AFW_AP 算法、AP 算法、K-means 算法和FCM 算法，GA-AP 算法得到的簇內(nèi)樣本點與真實標(biāo)簽的簇內(nèi)樣本點更接近。

4 結(jié)語

對于AP 算法不適用于稀疏數(shù)據(jù)、對Preference 參數(shù)敏感以及簇內(nèi)會出現(xiàn)錯分點的問題，本文提出基于萬有引力的自適應(yīng)AP 算法（GA-AP 算法）。實驗結(jié)果表明，與AFW_AP 算法、AP 算法、K-means 算法和FCM 算法相比，GA-AP 算法的聚類結(jié)果更接近真實類別標(biāo)簽。后續(xù)研究將關(guān)注如何加快GAAP算法的運行，進(jìn)一步提高該算法的運行效率。