基于教與學優化改進的近鄰傳播聚類算法①

馬翩翩,張新剛,梁晶晶

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

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

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

1 教與學的自適應近鄰傳播聚類

1.1 教與學優化算法

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

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

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

1.1.1 教師階段

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

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

1.1.2 學生階段

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

1.2 近鄰傳播聚類算法

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

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

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

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

如果i=k,則:

如果i=k,則:

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

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

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

1.3 基于教與學優化的近鄰傳播聚類

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

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

?

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

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

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

2 實驗與分析

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

表1 數據集性質

實驗中最大迭代次數為5000,連續收斂次數為50.將本文算法與原AP 算法、自適應AAP 從簇的個數、準確率、正則化信息、芮氏指標、時間等方面對聚類結果進行評估.

1)準確率(ACC)

準確率代表的是聚類正確的樣本數占總樣本數的比例.

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

2)正則化互信息(NMI)

正則化信息表示的是聚類后簇個數與真實簇之間的關聯程度,指標范圍為[0,1].越接近1,表示關聯程度越高,聚類效果越好.

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

3)Rand 指數(RI)

Rand 指數是聚類性能度量中將聚類結果與外部“某個參考模型”相對比的外部指標.

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

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

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

表2 簇個數

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

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

表3 各聚類算法ACC、NMI 和RI 聚類評價指標比較

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

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

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

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

由表4可知,本文算法的計算效率優于AP、AAP.在數據集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 總結

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