基于教與學(xué)優(yōu)化改進的近鄰傳播聚類算法①

馬翩翩,張新剛,梁晶晶

(南陽師范學(xué)院 計算機與信息技術(shù)學(xué)院,南陽 473061)

近鄰傳播聚類算法是2007 由Frey BJ 和Dueck D提出的一種新型的發(fā)展較快的聚類算法[1],與K-means算法相比它把所有的數(shù)據(jù)點作為潛在的簇中心,通過消息傳遞不停迭代進而確定最終的簇中心.該算法對點與點之間的相似性沒有絕對的要求,可以根據(jù)具體的應(yīng)用來選擇對應(yīng)的相似性度量方法,相似性的值可以是正的或負的,也可以是非對稱的.該算法已經(jīng)被廣泛應(yīng)用在數(shù)據(jù)流聚類、圖像處理、文本聚類、基因序列等領(lǐng)域[2–5].但是該算法在實際應(yīng)用中也有一定的局限性:1)該算法屬于無監(jiān)督聚類,不能利用已有的標(biāo)記信息來進行聚類;2)偏向參數(shù)的取值對最終簇的結(jié)果有較大的影響,取值過大,最終劃分的簇集偏多,取值過小,最終簇的集合偏小;3)對形狀復(fù)雜的數(shù)據(jù)集的聚類效果不佳、時間復(fù)雜度較高.

針對以上問題,不同的學(xué)者從不同的角度進行了改進.為了利用已有的標(biāo)記信息,文獻[6]根據(jù)半監(jiān)督聚類的思想,使用少量已知的標(biāo)簽數(shù)據(jù)和成對點約束對數(shù)據(jù)集形成的相似度矩陣進行調(diào)整,進而達到提高AP 算法的聚類性能;文獻[7]在半監(jiān)督聚類的基礎(chǔ)上利用懲罰參數(shù)添加軟約束來調(diào)整相似性度量,從而提高聚類質(zhì)量.為了克服預(yù)設(shè)偏向參數(shù)和阻尼系數(shù)對聚類結(jié)果的影響,有學(xué)者利用群體智能優(yōu)化算法對偏向參數(shù)和阻尼系數(shù)尋優(yōu):文獻[8]提出了將偏向參數(shù)和阻尼系數(shù)作為粒子群算法中的粒子,使用粒子群算法對系數(shù)尋優(yōu),從而提高聚類質(zhì)量;為了尋找較優(yōu)的偏向參數(shù)值,文獻[9]通過改進的布谷鳥搜索對偏向參數(shù)和阻尼系數(shù)進行調(diào)整,從而提高聚類效果;文獻[10]使用量子優(yōu)化中量子疊加態(tài)和旋轉(zhuǎn)門對偏向參數(shù)編碼和尋優(yōu)以提高AP 算法聚類的精確度和時間.為了處理復(fù)雜形狀的數(shù)據(jù)集:文獻[11]通過對數(shù)據(jù)集構(gòu)建概率圖模型,分析數(shù)據(jù)集的概率密度,并將其注入偏向參數(shù)進而進行近鄰傳播聚類;文獻[12]提出了一種基于全局核與高斯核的混合核函數(shù)的相似性度量,增強了泛化能力,從而提高了提高聚類質(zhì)量;文獻[13]在密度分布的基礎(chǔ)上,利用最近鄰搜索的方法進行相似性度量來對球面和非球面分布的數(shù)據(jù)進行聚類.也有學(xué)者使用其他方法來對近鄰傳播聚類進行改進,文獻[14]使用遷移思想,在綜合考慮源數(shù)據(jù)域和目標(biāo)數(shù)據(jù)域的數(shù)據(jù)特性及幾何特征的基礎(chǔ)上改進AP 算法中的消息傳遞機制提高聚類效果;文獻[15]提出了一種進化親和傳播聚類方法,考慮潛在的動態(tài)和保存時間平滑性同時對多個時間點收集的數(shù)據(jù)進行聚類.本文則使用教與學(xué)的群體智能優(yōu)化算法來對近鄰傳播聚類算法中的偏向參數(shù)和阻尼因子尋優(yōu),進而提高聚類質(zhì)量.

1 教與學(xué)的自適應(yīng)近鄰傳播聚類

1.1 教與學(xué)優(yōu)化算法

教與學(xué)優(yōu)化算法(Teaching Learning-Based Optimization algorithms,TLBO)是由Rao RV 等[16]于2010年提出的新的群體智能優(yōu)化算法,具有簡單、無參、快速收斂、易于實現(xiàn)等特點.它被廣泛應(yīng)用在機電工程、結(jié)構(gòu)優(yōu)化、模式識別、圖片處理、人工神經(jīng)網(wǎng)絡(luò)等領(lǐng)域.

該算法模擬一個班級的教師與學(xué)生的學(xué)習(xí)過程.其中班級相當(dāng)于智能優(yōu)化算法中的種群,教師和學(xué)生相當(dāng)于種群中的個體,所學(xué)科目為智能優(yōu)化算法中的變量,各科成績?yōu)槟繕?biāo)函數(shù)的適應(yīng)度值,全局最優(yōu)即為目標(biāo)函數(shù)的極值.假設(shè)最優(yōu)化問題用式z=maxF(x)表示,則X=(x1,x2,···,xi,···,xd)表示自變量,對應(yīng)學(xué)生個體;Xi表示任意一個決策變量,對應(yīng)學(xué)生的某一個科目;d表示決策變量的維度,對應(yīng)學(xué)生所學(xué)科目數(shù);S={X|XiL≤Xi≤XiH}表示有個體構(gòu)成的種群,即由學(xué)生構(gòu)成的班級;其中XiL和XiH分別代表個體Xi的下界和上界.

教師是從學(xué)生種群中選取出來的最優(yōu)秀個體,即z=argmaxF(x).為了找到在決策空間中的目標(biāo)函數(shù)極值,需要經(jīng)歷兩個階段.(1)教學(xué)階段.該階段主要借鑒在學(xué)習(xí)場景中教師是最優(yōu)學(xué)習(xí)者,其他學(xué)生在教師的教授下得到進步,所以首先找到在該次迭代中的最優(yōu)學(xué)習(xí)者即具有最優(yōu)目標(biāo)函數(shù)值的參數(shù)作為教師,其他參數(shù)向此輪最優(yōu)參數(shù)學(xué)習(xí);(2)學(xué)習(xí)階段.該階段主要借鑒于學(xué)生與學(xué)生之間互相學(xué)學(xué)習(xí)的場景,從眾多參數(shù)中隨機選取和自己相異的參數(shù)進行學(xué)習(xí),以改變自己的參數(shù)從而提高目標(biāo)函數(shù)值.

1.1.1 教師階段

在此階段,在整個搜索空間中隨機生成解.最優(yōu)函數(shù)值將在所有隨機生成解中進行選擇,并把最優(yōu)搜索解稱為教師Xteacher,而教師通過教授學(xué)生Xi,從而提高群體的整體知識水平,使平均成績得到一定提高.具體如式(1)、式(2)所示:

其中,Xmean代表的是整群體的平均水平,而老師講授知識,學(xué)生接受新知識的過程是一個隨機的過程,具體學(xué)習(xí)效果取決于學(xué)習(xí)補長r和教學(xué)因子TF,r為取值范圍為[0,1]的隨機數(shù),TF=roud[1+rand(0,1)].式(2)中Xnew,i代表的是第i個學(xué)生學(xué)習(xí)之后的知識水平,Xold,i代表的是學(xué)習(xí)前的知識水平,知識水平是否得到提升取決于個體的目標(biāo)函數(shù)是否朝著優(yōu)化方向前進.

1.1.2 學(xué)生階段

如上所述,根據(jù)教與學(xué)的過程,學(xué)生可以學(xué)習(xí)知識;通過學(xué)生之間的互動,學(xué)生也可以增加他們的知識.因此,一個搜索空間中的解(學(xué)生Xi)與總體中的其他解(學(xué)生Xj)隨機互動,肯定有一方會學(xué)到新的東西.如果Xi優(yōu)于Xj,則Xj將向Xi移動,如式(3)所示;反之Xi將向X移動,如式(4)所示.具體描述如下:

1.2 近鄰傳播聚類算法

聚類算法是尋找數(shù)據(jù)內(nèi)在特征的一種劃分過程.在一組含有N個樣本D={x1,x2,···,xi,···,xN},維度為d,xid={xi1,xi2,···,xid}的數(shù)據(jù)集中,聚類算法是將樣本數(shù)據(jù)集劃分為k個不相交的簇{Cl|l=1,2,···,k}其中CL’∩L’≠LCL=?且D=∪l=1k.近鄰傳播是近年來發(fā)展較快的聚類算法,它按照聚類定義找出簇中心,使簇內(nèi)距離最小.

其中,i=1,···,k,代表該聚類結(jié)果中有k個簇.Ci為簇中心,Ci≠?,且Ci∩Cj=?.

在近鄰傳播聚類算法執(zhí)行過程中需輸入任意兩點i和k之間的相似性s(i,k)所構(gòu)造的相似度矩陣,默認為負的歐式距離,即s(i,k)=–||xi–xk||2;設(shè)定自相似性s(k,k)又叫偏向參數(shù)p,因為近鄰傳播聚類算法不需要指定簇的個數(shù),而是通過參數(shù)p來影響最終的簇個數(shù).

其次近鄰傳播聚類算法的聚類過程是點與點之間的消息傳遞來實現(xiàn)的.信息有兩類,吸引度r(i,k)和歸屬度a(i,k).r(i,k)代表的是從簇成員i發(fā)送到簇中心k的消息,表示數(shù)據(jù)點i作為以k為簇中心的簇成員的度量;a(i,k)代表的是從簇中心k發(fā)送到簇成員i的消息,表示數(shù)據(jù)點k作為數(shù)據(jù)點i的簇中心的度量;結(jié)合歸屬度和吸引度,對于數(shù)據(jù)點i,找到使a(i,k)+r(i,k)達到最大化值的k時,如果k=i,則點k為簇中心;如果k≠i時,則表示數(shù)據(jù)點k作為數(shù)據(jù)點i的簇中心.初始時r(i,k)=0,a(i,k)=0;當(dāng)循環(huán)終止時尋找(diag(A)+diag(R))>0 的點k作為簇中心.r(i,k)和a(i.k)更新公式如下:

如果i=k,則:

如果i=k,則:

根據(jù)式(8)可知歸屬度a(i,k)被設(shè)置為吸引度r(k,k)加上潛在簇中心k從其他點獲得吸引度的總和,而且只添加傳入吸引度為正值的那一部分,再次驗證了一個好的簇中心只需要表明他很適合作為一些數(shù)據(jù)點的簇中心即可(所以只添加正值的吸引度),而不管他多么不適合做為其他點的簇中心 (負值的吸引度).如果自吸引度r(k,k)是負的,則表明點k不適合做為簇中心;如果r(i,k)為正值,那么a(i,k)也會增加.為了限制強勢吸引度r(i,k)的影響,對總和進行閾值,使其不能超過零.

根據(jù)近鄰傳播聚類算法的消息傳遞過程可知,在迭代過程中,當(dāng)一些點被分配到合適的簇中心時,它們的歸屬度a(i,k)如式(8)所示將會降到0 及其以下.根據(jù)式(6)可知這些負歸屬度可減少一些輸入相似性s(i,k)的有效值,從而從競爭中刪除相應(yīng)的候選范例.在式(7)中如果i=k時,吸引度r(k,k)的值為s(k,k)減去點i和所有其他候選簇中心之間的相似性的最大值,這種“自我吸引”即偏向參數(shù)p反映了在聚類迭代過程中k點是否適合做為一個簇中心,即偏向參數(shù)p的設(shè)定會影響最終的聚類效果.較高的偏向參數(shù)值表示成為簇中心的點較多,結(jié)果導(dǎo)致劃分的簇集較多;較低的偏向參數(shù)值代表成為簇中心的點較少,結(jié)果導(dǎo)致劃分的簇偏少.

同時在更消息更新過程中,為避免在某些情況下出現(xiàn)振蕩,需對消息即吸引度和歸屬度進行阻尼.具體如下所示:

1.3 基于教與學(xué)優(yōu)化的近鄰傳播聚類

教與學(xué)優(yōu)化的近鄰傳播聚類(TLBOAP)是一種基于AP 的改進聚類方法,是在計算目標(biāo)函數(shù)過程中進行近鄰傳播聚類,即通過群體智能優(yōu)化中的教與學(xué)優(yōu)化算法來尋找最優(yōu)偏向參數(shù)p從而提高AP 的聚類效果,同時該算法在聚類過程中會調(diào)整阻尼因子λ防止發(fā)生震蕩.算法1 為基于TLBO 的AP 算法.

算法1.TLBOAP 算法1)加載數(shù)據(jù)集.2)對數(shù)據(jù)集進行歸一化處理.算法種群規(guī)模為n,對應(yīng)數(shù)據(jù)集中樣本個數(shù),決策變量為偏向參數(shù)p,最大迭代次數(shù)為Tmax.3)采用負的歐式距離建立相似度矩陣S.4)根據(jù)式(6)～(9)執(zhí)行近鄰傳播聚類,同時根據(jù)聚類目標(biāo)函數(shù)(5)計算目標(biāo)函數(shù)值.

?

在步驟2)中為了提高教與學(xué)尋找最優(yōu)參數(shù)的效率,需指定參數(shù)p的搜索空間.在文獻[17]中驗證了當(dāng)p的上限取值為pm/2;文獻[18]中根據(jù)凈相似度來求出p值的下限p=dpsim1－dpsim2.凈相似性指的是數(shù)據(jù)集中任一點和它所對應(yīng)的簇中心的相似性之和.式(11)中dpsim1 代表的是聚類后簇個數(shù)為1 的的凈相似度值,

式(12)中dpsim2 代表的是聚類后簇個數(shù)為2 的的凈相似度值.

在步驟4)進行近鄰傳播聚類過程中,通過監(jiān)控窗口的設(shè)置監(jiān)控震蕩.設(shè)置監(jiān)控窗口大小為v=40,如果窗口中長度有三分之二簇個數(shù)不斷發(fā)生變化,則認為發(fā)生震蕩,此時以步長0.05 的速度調(diào)整阻尼因子λ的值,λ默認值為0.5,同時阻尼因子λ有上限,需小于1.因為當(dāng)阻尼因子過大時,會導(dǎo)致聚類速度過慢.

2 實驗與分析

為了驗證TLBOAP 算法的聚類效率,在內(nèi)存4 GB、處理器為Intel(R)Core(TM)i7—7700Q、Windows7 64 位的計算機上用Matlab R2012a 來實現(xiàn).已在6 個UCI 數(shù)據(jù)集上進行了測試,具體數(shù)據(jù)集如表1所示.

表1 數(shù)據(jù)集性質(zhì)

實驗中最大迭代次數(shù)為5000,連續(xù)收斂次數(shù)為50.將本文算法與原AP 算法、自適應(yīng)AAP 從簇的個數(shù)、準(zhǔn)確率、正則化信息、芮氏指標(biāo)、時間等方面對聚類結(jié)果進行評估.

1)準(zhǔn)確率(ACC)

準(zhǔn)確率代表的是聚類正確的樣本數(shù)占總樣本數(shù)的比例.

其中,k為聚類后所得簇的個數(shù),Li為第i個簇中聚類正確的樣本個數(shù),是一個直觀的度量指標(biāo).

2)正則化互信息(NMI)

正則化信息表示的是聚類后簇個數(shù)與真實簇之間的關(guān)聯(lián)程度,指標(biāo)范圍為[0,1].越接近1,表示關(guān)聯(lián)程度越高,聚類效果越好.

其中,K為聚類后所得簇的個數(shù);N為樣本總數(shù);Ni、Nj表示第i、j簇中樣本數(shù)目;Nij表示樣本在第i個簇中但屬于第j個簇的數(shù)目.

3)Rand 指數(shù)(RI)

Rand 指數(shù)是聚類性能度量中將聚類結(jié)果與外部“某個參考模型”相對比的外部指標(biāo).

其中,聚類結(jié)果用C={Cl|l=1,2,···,k}表示,外部參考模型用C*={C*l|l=1,2,···,s}表示.其中a表示在C中隸屬于同一簇且在C*中也隸屬于同一簇的樣本數(shù);b表示在C中隸屬于同一簇但在C*屬于不簇的樣本數(shù);c表示在C屬于不同簇但在C*隸屬于同一簇的樣本數(shù);d表示在C中不屬于同一簇且在C*中也不屬于同一簇的樣本數(shù).是在簇Cl和C*不明確簇的對應(yīng)情況下的聚類結(jié)果度量.

在近鄰傳播聚類過程中,由于偏向參數(shù)p的取值不同,產(chǎn)生的簇數(shù)目也不同.對于原始近鄰傳播聚類算法AP,p初始值默認為相似矩陣的均值,在傳遞過程中不發(fā)生改變;對于AAP 算法來說,主要通過調(diào)節(jié)阻尼系數(shù)λ 進而調(diào)節(jié)偏向參數(shù)p,相較于原始近鄰傳播算法來說,側(cè)重點在于防止發(fā)生震蕩,而不在于尋找最優(yōu)參數(shù);而在本文中所提到的TLBOAP 算法,側(cè)重點在于通過群體智能優(yōu)化算法教與學(xué)對方法在聚類過程中尋找最優(yōu)偏向參數(shù).

由表2可知在AP、AAP 方法中產(chǎn)生的簇較多,而TLBOAP 在多數(shù)數(shù)據(jù)集中產(chǎn)生的正確個數(shù)的簇,當(dāng)維數(shù)過高時產(chǎn)生的簇的數(shù)目會多于實際產(chǎn)生的數(shù)目,但是較AP、AAP 方法來說產(chǎn)生的簇數(shù)目還是更接近真實簇數(shù)目.

表2 簇個數(shù)

偏向參數(shù)p值的選擇不但會影響簇中心的多少,也會確定最終的簇中心,簇中心的確定會影響最終簇聚類的質(zhì)量.原始近鄰傳播聚類算法AP,偏向參數(shù)p值固定且不變;對于AAP 算法來說,為調(diào)整阻尼系數(shù)的基礎(chǔ)上以固定步長調(diào)整偏向參數(shù);TLBOAP 算法,則通過教與學(xué)優(yōu)化算法在有限有空間中尋找最優(yōu)偏向參數(shù)p,所以會導(dǎo)致聚類性能指標(biāo)差別也較大.

表3中的Iris 數(shù)據(jù)集是聚類分析最常用的數(shù)據(jù)集,有150 個樣本,3 個類簇.本文TLBOAP 算法能達到0.9457 的聚類準(zhǔn)確率,相較于AP 算法、AAP 算法ACC指標(biāo)分別提升43.44%,71.10%;TLBOAP 算法對Iris 數(shù)據(jù)集聚類結(jié)果的NMI和RI評價指標(biāo)也優(yōu)于AP、APP 算法,NMI指標(biāo)為0.8322,較AP、AAP 算法分別提升了20.61%、34.74%;RI指標(biāo)為0.9341,較AP、AAP 算法分別提升了10.92%、15.12%.

表3 各聚類算法ACC、NMI 和RI 聚類評價指標(biāo)比較

在含有178 個樣本,3 個類簇,13 個特征的數(shù)據(jù)集Wine 中,本文TLBOAP 算法能達到0.7427 的聚類準(zhǔn)確率,相較于AP 算法、AAP 算法ACC指標(biāo)分別提升1.04 倍,1.18 倍;NMI指標(biāo)中分別提升了29.12%、21.92%;在RI指標(biāo)上分別提升了6.09%、6.33%

在高維特征的數(shù)據(jù)集中Zoo、Sonar 為例,雖然在NMI、RI指標(biāo)上基本持平,但是在ACC指標(biāo)上有較大提升.在Zoo 數(shù)據(jù)集中,ACC指標(biāo)較AP 算法、APP 算法均提升了14.94%;在Sonar 數(shù)據(jù)集中,ACC指標(biāo)較AP 算法、APP 算法分別提升了1.64 倍、88.47%.

總之,在度量聚類效果時,要進行整體考慮,因為不同的指標(biāo)方法不同,側(cè)重點也不同.由表3可知,在6 個UCI 數(shù)據(jù)集中,本文中的TLBOAP 算法聚類效果整體上均優(yōu)于AP 算法、AAP 算法.

原始近鄰傳播聚類算法AP 因為偏向參數(shù)p取值較大,所以收斂速度慢;自適應(yīng)AAP 算法,因為迭代過程中需要針對每次阻尼因子的取值調(diào)整偏向參數(shù)p值,然后在該偏向參數(shù)p值下再次循環(huán)調(diào)整阻尼因子;TLBOAP 算法,因為教與學(xué)優(yōu)化算法無參數(shù),魯棒性強,所以在有限有空間中尋找偏向參數(shù)p值較快.

由表4可知,本文算法的計算效率優(yōu)于AP、AAP.在數(shù)據(jù)集Iris、Glass、Wine、Zoo、Soybean、Sonar 上,TLBOAP 算法的運算速率較AP 算法分別提升了是12.1 倍、6.7 倍、7.7 倍、3.1 倍、9.8 倍、21.2 倍;較AAP 算法分別提升了61.82%、88.67%、33.03%、基本相同、44.95%、18.28%.

表4 運行時間

3 總結(jié)

本文依據(jù)聚類的度量標(biāo)準(zhǔn),通過使用群體智能算法中的教與學(xué)優(yōu)化在偏向參數(shù)p空間中尋找合適的偏向參數(shù)取值,同時通過步長調(diào)整來防止震蕩,最終確定最終聚類結(jié)果.同時和已有的算法AP,AAP 進行了對比試驗,在度量指標(biāo)ACC、NMI、RI 運行時間上均有一定的提高.但是該算法在相似性度量上采用的是歐式距離,對于非凸數(shù)據(jù)集的聚類有一定的局限性,下一步將結(jié)合特征提取工程和核函數(shù)來提高聚類質(zhì)量.