陳琴，史亞輝，蘇一丹

(廣西大學計算機與電子信息學院， 廣西南寧530004)

0 引言

2007年,Frey和Dueck在《Science》上提出了近鄰傳播算法(affinity propagation, AP)[1]，它利用消息傳遞機制進行聚類，具有聚類速度快，不需要事先確定聚類數(shù)目且不易陷入局部最優(yōu)的優(yōu)點，已經(jīng)廣泛應(yīng)用于故障診斷、神經(jīng)網(wǎng)絡(luò)、文本挖掘、圖像識別[2-5]等領(lǐng)域。但該算法存在一個缺陷：需要對偏向參數(shù)調(diào)優(yōu)，若取值不當將直接影響算法的聚類效果，目前國內(nèi)外學者針對此問題展開了一系列研究。文獻[6]引入極大團和勢函數(shù)來計算數(shù)據(jù)樣本的概率密度，將此概率密度作為聚類先驗知識注入到偏向參數(shù)中，提高了聚類效率和精度。文獻[7]提出了一種基于鄰域相似度的近鄰傳播聚類算法，該算法將鄰域相似度注入偏向參數(shù)，提高聚類的準確性。文獻[8]提出了一種自適應(yīng)調(diào)整偏向參數(shù)的近鄰傳播算法，每次迭代動態(tài)調(diào)整偏向參數(shù)。文獻[9]將灰色狼群優(yōu)化算法引入近鄰傳播算法自動搜索偏向參數(shù)。和聲搜索算法是一種新穎的智能搜素算法，該算法模擬音樂的演奏原理，具有結(jié)構(gòu)簡單，搜索能力強等優(yōu)點[10]，已經(jīng)廣泛應(yīng)用于交通運輸[11]、結(jié)構(gòu)優(yōu)化設(shè)計[12]、電力系統(tǒng)等領(lǐng)域[13]。本文把和聲搜索引入近鄰傳播算法。首先對數(shù)據(jù)集進行歸一化處理，消除不同參數(shù)量綱的影響，然后利用和聲搜索全局快速搜索的優(yōu)點對近鄰傳播算法的偏向參數(shù)進行自動尋優(yōu)，最后在標準數(shù)據(jù)集上對改進的算法進行一系列驗證并與PUMG-AP算法進行比較。

1 近鄰傳播算法概述

近鄰傳播算法的原始輸入是相似度矩陣s(i,k)。相似度矩陣的非對角線元素s(i,k)為點I與點X之間的相似關(guān)系，其取值為兩點間歐式距離的負值，s(i,j)=-‖xi-xj‖2。對角線元素s(k,k)為偏向參數(shù),偏向參數(shù)的初始值為相似度矩陣中所有非對角線元素均值, 偏向參數(shù)的初始大小對最后的聚類數(shù)有較大的影響, 偏向參數(shù)越大產(chǎn)生的聚類個數(shù)越多。

近鄰傳播算法的核心為數(shù)據(jù)點之間相互的信息傳遞, 近鄰傳播算法有兩種信息, 它們分別為吸引度矩陣與歸屬度矩陣。算法開始時吸引度矩陣與歸屬度矩陣的初始值為0,r(i,k)反映點K作為點I的聚類中心的合適程度,a(i,k)反映點I選擇點K作為其聚類中心的程度,每次迭代結(jié)束后r(k,k)與a(k,k)之和大于0的點為聚類中心。吸引度矩陣與歸屬度矩陣每次按式(1)、(2)進行更新。

(1)

(2)

(3)

(4)

anew(i,k)=λaold(i,k)+(1-λ)anew(i,k),

(5)

rnew(i,k)=λrold(i,k)+(1-λ)rnew(i,k)。

(6)

2 基于和聲搜索的近鄰傳播算法

偏向參數(shù)代表該點成為聚類中心的可能性的大小，其設(shè)置對近鄰傳播算法的運算結(jié)果有著至關(guān)重要的影響。和聲搜索算法結(jié)構(gòu)簡單，搜索能力強，本文首先把偏向參數(shù)中的每一個值編碼成和聲搜索中和聲的一個音調(diào)，然后利用和聲搜索算法進行全局搜索,搜索結(jié)束后利用搜索到的和聲解碼成偏向參數(shù)按近鄰傳播算法進行計算。本文提出的算法的詳細流程如下：

step1:消除量綱影響，把數(shù)據(jù)集進行歸一化處理以消除不同量綱的影響。

step2:初始化和聲種群大小、學習和聲庫的概率、音調(diào)調(diào)整率、距離帶寬、最大迭代次數(shù)、搜索區(qū)間。

和聲種群大小(HMS)的初始值為5，學習和聲庫的概率(HMCR)的初始值為0.9，音調(diào)調(diào)整率(PAR)的初始值為0.9，最大迭代次數(shù)(NI)的初始值為1 000 000次，搜索區(qū)間[Xmin、Xmax]的設(shè)置如式(7)、(8),其方法取自參考文獻[14],距離帶寬bw的設(shè)置如公式(9)。

(7)

(8)

bw=0.1(Xmax-Xmin)。

(9)

Step3:初始化和聲庫。在解空間范圍內(nèi)隨機生成和聲庫,利用和聲算法搜索產(chǎn)生的和聲的適應(yīng)度并將其存儲在種群中。

Step4:利用和聲搜索算法搜索偏向參數(shù)。和聲搜索的主要過程是每次用比較優(yōu)秀的和聲替換質(zhì)量差的和聲已達到尋優(yōu)的目的,即每次迭代時產(chǎn)生新和聲，計算和聲的質(zhì)量，更新和聲庫。具體流程如step 4.1～step 4.3：

Step4.1:產(chǎn)生新和聲。新和聲的產(chǎn)生方式有兩種：①從和聲庫中隨機選擇并進行音調(diào)調(diào)整；②在整個解空間中隨機選擇產(chǎn)生新的和聲。隨機產(chǎn)生隨機數(shù)，如果隨機數(shù)小于學習和聲庫的概率，則新解在和聲庫內(nèi)隨機取得；否則在和聲庫外隨機取得，新和聲如果來自和聲庫，則每個音調(diào)變量由下面公式進行微調(diào)。

(10)

Step4.2:更新和聲庫。如果新和聲的適應(yīng)度比和聲庫中最差的和聲的適應(yīng)度更好，那么用搜索到的和聲替換和聲庫里面最差的和聲。

Step4.3:判斷是否達到終止條件。重復(fù)step 4.1～step 4.2，直到達到指定最大迭代次數(shù)或者在給定的迭代次數(shù)內(nèi)，適應(yīng)度不變。

Step5:利用搜索到偏向參數(shù)運算。利用搜索到的最佳和聲替換矩陣中的偏向參數(shù)，按式(1)～(6)進行計算。

3 仿真實驗與分析

實驗所用計算機的處理器為Intel i5，內(nèi)存為8 G；操作系統(tǒng)為Windows 7 64bit, 使用Matlab對算法進行實現(xiàn)。

本實驗驗證算法采用5個標準UCI數(shù)據(jù)集，數(shù)據(jù)集的信息見表1。

表1 UCI數(shù)據(jù)集信息Tab.1 Information of UCI data sets

將本文HS-AP算法與AP算法、K-AP算法、M-AP算法以及PUMG-AP算法進行對比，采用蘭德指數(shù)、正則化互信息、準確率對各算法聚類結(jié)果進行評測。

① 蘭德指數(shù)(arand index, RI)，用R表示，其定義為：

(11)

其中:TP為同一類的數(shù)據(jù)樣本被分到同一個簇內(nèi)的數(shù)目，TN為不同類的數(shù)據(jù)樣本被分到不同簇中的數(shù)目，F(xiàn)P為不同類的數(shù)據(jù)樣本被分到同一簇中，F(xiàn)N為同一類的數(shù)據(jù)樣本被分到不同簇中。RI指數(shù)是在不知道聚類所得的一個簇與真實簇之間的對應(yīng)關(guān)系下評價聚類結(jié)果的準確性，數(shù)值越大準確的越高。

② 正則化互信息(normalized mutual information, NMI),用M表示，其定義為：

(12)

其中:K為簇的總數(shù)目，N(i,j)為聚類結(jié)果的第i簇中屬于第j類(簇)的樣本數(shù)目，Ni、Nj分別為第i、j簇中數(shù)據(jù)樣本的數(shù)目，N為數(shù)據(jù)樣本總數(shù)。NMI指標為聚類個數(shù)與真實類別個數(shù)之間不匹配的容忍度，取值范圍為[0,1]。指標值越接近1，表示聚類結(jié)果與真實類別的匹配度越高，聚類效果越好。

③ 準確率(accuracy, ACC),用A表示，其定義為：

(13)

其中:K為聚類后所得簇的總數(shù)，Li為第i個簇內(nèi)的數(shù)據(jù)樣本中聚類正確的樣本數(shù)目。ACC將聚類后一個簇內(nèi)的樣本與相應(yīng)真實簇中的樣本相比較來判斷正確聚類樣本數(shù)的準確率。

圖1～圖3是聚類算法AP算法，K-AP算法、M-AP算法以及PUMG-AP算法與HS-AP算法在數(shù)據(jù)集IRIS，WINE，VOTE，PIMA，SOYBEAN上的對比結(jié)果。

圖1 IRIS, WINE, VOTE, PIMA, SOYBEAN數(shù)據(jù)集在HS-AP, PUMG-AP, M-AP, K-AP, AP算法的準確率對比Fig.1 IRIS, WINE, VOTE, PIMA, SOYBEAN accuracy rate comparison chart in HS-AP, PUMG-AP, M-AP, K-AP, AP

準確率是評價聚類結(jié)果的一個重要指標。偏向參數(shù)作為近鄰傳播算法中的一個參數(shù)，其設(shè)置對準確率具有直接影響，從圖1中可以看出，HS-AP算法在準確率方面比AP算法，K-AP算法，M-AP算法，PUMG-AP算法都要高。

蘭德指數(shù)是對類內(nèi)純度的一個評價，即類內(nèi)含有的屬于此類的樣本點的程度。近鄰傳播算法是一個基于消息傳遞機制的算法，每次迭代都是在傳遞各個點能否成為聚類中心以及自己屬于哪一類，偏向參數(shù)是對該點作為聚類中心的可能的初始描述。其準確與否能夠直接影響聚類的形態(tài)，即蘭德指數(shù)，由于和聲搜索對近鄰傳播算法的偏向參數(shù)進行了調(diào)優(yōu)，所以蘭德指數(shù)在實驗的數(shù)據(jù)集上有不同程度的提高。

圖3 IRIS, WINE, VOTE, PIMA, SOYBEAN數(shù)據(jù)集在HS-AP, PUMG-AP, M-AP, K-AP, AP算法的正則化互信息對比Fig.3 IRIS, WINE, VOTE, PIMA, SOYBEAN regularized mutual information comparison chart in HS-AP, PUMG-AP, M-AP, K-AP, AP

正則化互信息也是評價聚類的結(jié)果和真實情況符合度的一個指標，數(shù)值越大表示越符合真實的情況，聚類效果越好。

從圖1～圖3可以看出，HS-AP算法在準確率，蘭德指數(shù)和正則化互信息三個指標上表現(xiàn)均優(yōu)于另外四種算法，PUMG-AP算法表現(xiàn)次之。PUMG-AP算法的平均準確率為76.74 %，HS-AP算法的平均準確率為83.1 %，準確率平均提升了6.36 %。PUMG-AP算法蘭德指數(shù)平均為0.782 6，HS-AP算法蘭德指數(shù)平均為0.819 2，平均提升4.677 %。在正則化互信息方面PUMG-AP算法的平均指標為0.493，HS-AP算法的平均正則化互信息為0.587，HS-AP算法平均提升了19.04 %。在原始算法準確率最高的數(shù)據(jù)集IRIS上，HS-AP算法在準確率方面提升了0.07 %，在準確率最低的數(shù)據(jù)集SOYBEAN上，HS-AP算法準確率提升最多，提高了13.8 %。綜上所述，本文通過利用和聲搜索算法對近鄰傳播算法的偏向參數(shù)進行準確設(shè)置，有效地提升了算法的準確性。

4 結(jié)語

本文通過對近鄰傳播算法流程的研究提出了一種基于和聲搜索的近鄰傳播算法，通過運用歸一化和聲搜索，分別優(yōu)化了相似度矩陣和偏向參數(shù)。仿真結(jié)果表明在準確率，蘭德指數(shù)，正則化互信息三個評價指標方面均有提升。

通過對基于和聲搜索的近鄰傳播算法的分析可以得到如下結(jié)論：

偏向參數(shù)的大小代表該點成為聚類中心的可能的大小，以前的近鄰傳播算法中各個點的偏向參數(shù)都相同，本文通過引入和聲搜索對最佳偏向參數(shù)進行搜索。然后對偏向參數(shù)進行替換，提高了運算的準確率；用和聲算法自動搜索偏向參數(shù),克服了近鄰傳播算法需要手工篩選最優(yōu)偏向參數(shù)系數(shù)的問題。