唐 丹,張正軍,王俐莉

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

基于改進的近鄰傳播聚類算法的Gap統(tǒng)計研究

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

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

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

聚類分析;近鄰傳播聚類;偏向參數(shù);K-means算法;Gap統(tǒng)計

0 引 言

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

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

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

1 mAP模型

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

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

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

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

(1)

(2)

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

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

(3)

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

(4)

其中，Npref是輸入?yún)?shù)，表示設置Npref個不同P。

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

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

(5)

(6)

其中

(7)

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

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

2 mAP算法

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

(8)

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

(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)

②引入阻尼系數(shù)λ，消除可能出現(xiàn)的震蕩。

(12)

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

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

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

3 mAPGap模型(Gap Statistic Based on mAP)

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

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

(13)

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

再令：

(14)

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

由此定義Gap統(tǒng)計量：

(15)

為了區(qū)分基于不同算法的Gap統(tǒng)計，這里把基于K-means算法的原Gap統(tǒng)計記作KMGap。

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

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

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

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

(16)

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

(17)

4 仿真實驗與分析

文中實驗采用MATLAB7.0開發(fā)環(huán)境，在Windows7操作系統(tǒng)的計算機上運行通過。

4.1 實驗數(shù)據(jù)集

表1 實驗數(shù)據(jù)集描述

4.2 實驗評價標準

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

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

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

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

(18)

其中，TC為正確聚類的數(shù)據(jù)數(shù)；FC為錯誤聚類的數(shù)據(jù)數(shù)。

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

4.3 結果與分析

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

圖1 Haberman數(shù)據(jù)集中的KMGap、APGap、mAPGap隨類數(shù)k的變化曲線

數(shù)據(jù)集算法類數(shù)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

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

5 結束語

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

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

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

[3] 陸琴琴.基于矩Gap統(tǒng)計的圖像分割方法[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] 邢長征，劉 劍.基于近鄰傳播與密度相融合的進化數(shù)據(jù)流聚類算法[J].計算機應用,2015,35(7):1927-1932.

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

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

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

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

[14] 馮 予,陳 萍.概率論與數(shù)理統(tǒng)計[M].第2版.北京：國防工業(yè)出版社,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

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

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

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