基于改進的近鄰傳播聚類算法的Gap統計研究

唐 丹,張正軍,王俐莉

(1.南京理工大學 理學院 統計與金融數學系,江蘇 南京 210094;2.海軍指揮學院科研部,江蘇 南京 210016)

基于改進的近鄰傳播聚類算法的Gap統計研究

唐 丹1,張正軍1,王俐莉2

(1.南京理工大學 理學院 統計與金融數學系,江蘇 南京 210094;2.海軍指揮學院科研部,江蘇 南京 210016)

由于K-means算法初始聚類中心的選取具有隨機性，聚類結果可能不穩定，導致Gap統計估計的聚類數也可能不穩定。針對這些不足，提出一種改進的近鄰傳播算法-mAP。該算法考察數據的全局分布特性，不同的點賦予不同的P值。在Gap統計中用mAP算法代替K-means算法,提出基于mAP的Gap統計mAPGap。mAP能在較短的時間內得到較好的聚類效果，而且不需要預先設定初始聚類中心，聚類結果更穩定。實驗結果表明,mAPGap在估計聚類數的穩定性和聚類精度上都優于原Gap。

聚類分析;近鄰傳播聚類;偏向參數;K-means算法;Gap統計

0 引 言

數據集的聚類數估計是數據分析中的一項重要課題。2000年，R.Tibshirani等提出確定最佳聚類數的Gap統計量[1]，采用的聚類算法是K-means算法，該算法需要選取初始聚類中心，通常隨機選取K個樣本點作為初始聚類中心。2013年，劉倩基于Gap統計方法研究了K-means算法，提出了一種基于數據分布規律具有自適應特點的DSA-K-means算法[2]。2013年，陸琴琴針對基于矩Gap統計的圖像分割算法中K-means算法存在的缺陷，提出了MMGSK算法[3]。

2007年，Frey[4]和MezardM[5]提出了屬于劃分聚類方法的近鄰傳播(AffinityPropagation,AP)算法。該算法具有如下優點：能在較短時間內得到較好的聚類效果[6]；算法中類代表點是原始數據中的點，而不是數據的均值點；以誤差平方和作為衡量算法優劣程度的準則函數時，算法聚類的誤差平方和顯著低于其他方法聚類的誤差平方和。但是AP算法對偏向參數P的設定，沒有考慮數據的分布結構，認為所有數據點成為類代表點的可能性相同。

文中提出了利用全局數據信息設置偏向參數P的改進的AP算法-mAP(modifiedAffinityPropagation)，同時提出了自適應的增加步長，得到數據集的聚類數，運用Gap統計量估計出該數據集的合理聚類數。

1 mAP模型

AP是一種基于近鄰信息傳播的聚類算法，根據N個數據點之間的相似度進行聚類[7]。這些相似度組成N×N的相似度矩陣S。S矩陣的對角線上的數值s(k,k)稱為偏向參數preference,記作P,表示數據點k作為類代表點的適合程度。該值越大，k點成為類代表點的可能性也越大,同時得到的聚類數越多[8]。AP算法中傳遞兩種類型的消息，即歸屬度a(i,j)和吸引度r(i,j)，前者表示xi選擇xj作為類代表的合適程度，后者表示xi對xj作為類代表點的支持程度[9]。AP算法通過迭代過程不斷更新每一個點的吸引度和歸屬度值，直到迭代過程收斂，類代表也隨之固定，同時將其余的數據點分配到相應的聚類中[10]。

傳統的AP算法中相似度矩陣對角線上的偏向參數P是相同的，一般取所有相似度的中值(median(s(:,3))，意味著數據點在開始時被選擇作為類代表點的概率是相同的。但是，P值的這種初始設置方法是不科學、不精確的，因為它忽略了數據點結構的差異對某點成為類代表點的可能性的影響。類代表點的選擇與點的位置密切相關：對給定的數據集X和點xi,xj，如果xi是邊緣數據點而xj是中心數據點，那么從其他點到xi的距離和大于到xj的距離和，xj成為類代表的可能性要大于xi。

針對如上假設，文中提出基于全局數據點設置P的值，同時為了獲得不同的聚類數，提出一種自適應設置步長獲得不同聚類數的方法。具體步驟如下：

(1)對任意點xi，計算從其他所有點到xi的相似度之和：

(1)

(2)

(3)對AP算法設置步長，獲得不同聚類數。

根據上述討論可知，當每個數據點的P值相同時，聚類數隨P值的增大而增大。所以為了得到不同的聚類數，P存在取值區間[Pmin,Pmax]。WangCD[11]通過研究得到:

(3)

由于AP算法每個點的P值相同，可以通過下式獲得：

(4)

其中，Npref是輸入參數，表示設置Npref個不同P。

(4)對mAP算法設置步長，獲得不同聚類數。

對i=1,2,…,n(n代表樣本點個數)，有：

(5)

(6)

其中

(7)

由于對每個點的PiMin都是Pmin乘以一個權重，所以會使得每個點的初始P值變小。為了確保能夠取到1～maxK類，這里把Pmin取得更小，是用相似度矩陣元素的最小值乘以樣本點個數n。

對于連續的k，mAP算法得到的分類情況會大量重復。文中根據mAP算法的聚類結果動態計算步長，在不改變結果的基礎上優化了算法的運行時間。

2 mAP算法

s(i,k)=-‖xi-xk‖,i≠k

(8)

(2)對于每一個Npref，根據式(5)～(7)計算每個點的偏向參數，能得到Npref個1*n數組。

(3)消息傳遞。

①更新吸引度矩陣r(i,k)和歸屬度矩陣a(i,k)。

r(i,k)=s(i,k)-max{a(i,k')+s(i,k')}(k'≠k)

(9)

(10)

(11)

②引入阻尼系數λ，消除可能出現的震蕩。

(12)

其中，λ(0<λ<1)越大越能消除震蕩，但會減緩算法收斂的速度。

(4)循環執行步驟(3),直到滿足終止條件。終止條件為達到最大迭代次數maxits或聚類劃分連續Convits次不變。

(5)輸出聚類結果。輸出Npref組類代表點及其對應的數據點劃分。

3 mAPGap模型(Gap Statistic Based on mAP)

原Gap統計方法的主要思想是：選擇一個參考分布，將待分類數據的離散程度與由參考分布生成數據集的離散程度進行比較，以分類數為自變量，建立一個比較統計量，通過分析該統計量關于類數的變化情況確定最佳聚類數[12]。

原Gap統計的主要內容是：假設數據是通過K-means算法已被聚為k類:C1,C2,…,Ck，nr=|Cr|。令：

(13)

其中，Dr表示聚類r中所有數據兩兩之間的距離平方之和。

再令：

(14)

其中，Wk表示k類離差程度的總和。

由此定義Gap統計量：

(15)

為了區分基于不同算法的Gap統計，這里把基于K-means算法的原Gap統計記作KMGap。

由于KMGap統計需要預先生成大量的參考數據集，因而不適宜通過mAP算法實現不同類數的聚類，而且參考數據集類內離差程度是均勻分布下大量數據集類內離差程度的期望，根據Khinchin大數定律[14]知，使用K-means算法聚類能夠保證結果的穩定性。鑒于以上兩點，對參考數據集的聚類方法仍使用K-means算法。

使用mAP算法對樣本數據集進行聚類，當選擇負的歐氏距離作為兩個樣本點的相似度時，mAP算法的準則函數也即是使每個樣本點到其類代表點的平方距離之和最小，這與K-means算法的準則函數一致。因此使用mAP算法對樣本數據集進行聚類，使用K-means算法對參考數據集進行聚類，再利用Gap統計量估計該數據集的聚類數是合理的。

mAPGap的計算可分為以下3步:

(1)利用mAP算法，將樣本數據集聚集為k(k=1,2,…,K)類，計算Wk(在偏向參數不同時會出現相同的分類數k，這里Wk取它們的平均值)。

(16)

Gap(k)≥Gap(k+1)-sk+1

(17)

4 仿真實驗與分析

文中實驗采用MATLAB7.0開發環境，在Windows7操作系統的計算機上運行通過。

4.1 實驗數據集

表1 實驗數據集描述

4.2 實驗評價標準

實驗采用3種評價指標對聚類結果進行評價：

(1)對三個數據集,分別利用KMGap、APGap、mAPGap重復運行20次，估計出最佳聚類數的正確率p。

(2)算法運行時間t。雖然AP算法復雜度為O(N*N*logN)，而K-means的是O(N*K)，但當樣本容量不是非常大時，兩者時間相近。故這里對具體數據集的運行時間進行比較。

(3)聚類精度。定義為：

(18)

其中，TC為正確聚類的數據數；FC為錯誤聚類的數據數。

由于AP算法和mAP算法都會出現在估計的最佳聚類數相同時，具體的聚類結構不同的情況，所以對某個特定的聚類，聚類精度有不同的值。結果分析中，AP算法和mAP算法的精度記錄的都是最小值。當最小值都優于KMGap時，說明APGap算法和mAPGap算法聚類的精度優于KMGap。

4.3 結果與分析

對三個數據集分別執行KMGap、APGap、mAPGap聚類，聚類結果及性能如圖1、表2所示(由于版面有限，這里只給出Haberman的聚類結果)。

圖1 Haberman數據集中的KMGap、APGap、mAPGap隨類數k的變化曲線

數據集算法類數p/%t/saData1KMGap295412．8920．8571APGap2100613．4260．8905mAPGap2100533．1970．9048Haber-manKMGap270430．3720．4902APGap2100771．0510．5261mAPGap2100661．1090．5327SeedsKMGap390225．9750．83APGap3100330．170．8667mAPGap3100303．9430．85

實驗結果表明，相比于KMGap，APGap、mAPGap

雖然運行時間增加了一點，但二者具有很好的穩定性，同時二者均可以提高分類精度。而且mAPGap與APGap相比，在不影響穩定性和精度的情況下，減少了算法運行時間。總體來說，mAPGap算法優勢明顯的原因是：利用數據結構設置每個數據點的偏向參數，減少了算法運行時間；不需要預先設定初始聚類中心和聚類數，使得聚類結果更穩定，精度更高。

5 結束語

文中提出根據數據的全局分布特性設置偏向參數P的AP算法(mAP),在Gap統計中，用mAP算法替換K-means算法，提出基于mAP的Gap統計量(mAPGap)。通過實驗證明了mAPGap在聚類結果的穩定性，并且在精度上要優于原算法。

[1]TibshiraniR,WaltherG,HastieT.Estimatigthenumberofclusterinadatasetviathegapstatistic[J].JournaloftheRoyalStatisticalSociety,2001,63(2):411-423.

[2] 劉 倩.基于GS方法的圖像分割估計數的多信息動態研究[D].南京:南京理工大學,2013.

[3] 陸琴琴.基于矩Gap統計的圖像分割方法[D].南京:南京理工大學,2014.

[4]FreyBJ,DueckD.Clusteringbypassingmessagesbetweendatapoints[J].Science,2007,315(5814):972-976.

[5]MezardM.Wherearetheexamplars?[J].Science,2007,315(5814):949-951.

[6] 馮曉磊,于洪濤.密度不敏感的近鄰傳播聚類算法研究[J].計算機工程,2012,38(2):159-162.

[7] 邢 艷，周 勇.基于互近鄰一致性的近鄰傳播算法[J].計算機應用研究,2012,29(7):2524-2526.

[8] 段麗莉.改進的近鄰傳播算法及其在圖像處理中的應用[D].西安:西安電子科技大學,2014.

[9] 邢長征，劉 劍.基于近鄰傳播與密度相融合的進化數據流聚類算法[J].計算機應用,2015,35(7):1927-1932.

[10] 肖 宇，于 劍.基于近鄰傳播算法的半監督聚類[J].軟件學報,2008,19(11):2803-2813.

[11]WangCD,LaiJH,SuenCY,etal.Multi-exemplaraffinitypropagation[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2013,35(9):2223-2237.

[12] 童 波.基于MFGS方法圖像最佳分隔數的研究[D].南京:南京理工大學,2011.

[13] 黃陳蓉,張正軍,吳慧中.圖像邊緣檢測的多尺度灰度Gap統計模型[J].中國圖象圖形學報,2005,10(8):1018-1023.

[14] 馮 予,陳 萍.概率論與數理統計[M].第2版.北京：國防工業出版社,2015:114-117.

Study on Gap Statistic Based on Modified Affinity Propagation Clustering

TANG Dan1,ZHANG Zheng-jun1,WANG Li-li2

(1.Department of Statistic and Financial Mathematics,College of Science,Nanjing University of Science and Technology,Nanjing 210094,China; 2.Scientific Research Department of Naval Command College,Nanjing 210016,China)

Due to the randomness of choosing the initial clustering ofK-meansmethod,itmaycausetheinstabilityofclusteringresultsandthenleadtothatofclusteringnumberswhichareestimatedbyGapstatistic.Takingconsiderationofthosedisadvantages,anmodifiedAPclustering(mAP)ispresentedwhichutilizestheglobaldistributiontogivedifferentPtodifferentpoints.mAPmethodisputforwardtosubstitutetheK-meansinGapstatisticnamedmAPGap.mAPmethodhasmorestableclusteringcenterbecausetheinitialclusteringcenterandnumbersarenotneededinadvanceanditcangetbetterclusteringinshorttime.TheexperimentalresultsdemonstratemAPGapissuperiortoGapinclusteringstabilityandaccuracy.

cluster analysis;affinity propagation clustering;preference;K-meansalgorithm；Gapstatistic

2016-03-15

2016-06-22

時間：2017-01-04

全國統計科學研究計劃重點項目(2013LZ45)

唐 丹(1990-),女,碩士研究生,研究方向為數據分析與數據挖掘;張正軍,博士,副教授,研究方向為數據分析與數據挖掘、馬爾可夫鏈理論與方法等。

http://www.cnki.net/kcms/detail/61.1450.TP.20170104.1102.086.html

TP

A

1673-629X(2017)01-0182-04

10.3969/j.issn.1673-629X.2017.01.041