唐 敏

（1.安徽礦業(yè)職業(yè)技術(shù)學(xué)院 自動(dòng)化與信息工程系，安徽 淮北 235000；2.淮北煤電技師學(xué)院 自動(dòng)化與信息工程系，安徽 淮北 235000）

0 引 言

近鄰傳播算法是Frey和Dueck2007年在《Science》上提出的基于所有數(shù)據(jù)點(diǎn)相似度的新型聚類算法，目前該算法已經(jīng)成功應(yīng)用在圖像分割［1－2］、視頻拷貝檢測(cè)［3］、文本聚類［4－5］確定等諸多領(lǐng)域，引起國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，例如加拿大學(xué)者Inmar E.Givoni［6］等2009年提出一個(gè)派生的近鄰傳播算法，比原來(lái)更簡(jiǎn)單的基于一個(gè)完全不同的圖形化模型；韓國(guó)學(xué)者Qasim I［7］等2013年提出吸引子傳播算法與文本概念圖半自動(dòng)生成技術(shù)相結(jié)合，獲得概念圖領(lǐng)域?qū)＜业恼J(rèn)可；國(guó)內(nèi)學(xué)者肖宇［8］等提出一種適用于近鄰傳播算法的半監(jiān)督方法，取得了顯著成效；董?。?］等提出可變相似度用于改進(jìn)輸入矩陣等。在研究以上算法基礎(chǔ)上，提出一種基于多尺度變換的近鄰傳播算法，該算法更適合對(duì)高維數(shù)據(jù)聚類。

1 吸引子傳播聚類算法

近鄰傳播算法不同于K均值，K均值對(duì)于初始聚類點(diǎn)的選擇敏感，捕捉到聚類質(zhì)量高的結(jié)果需要進(jìn)行多次不同的初始化聚類參數(shù)，而近鄰傳播算法采用一種將所有數(shù)據(jù)點(diǎn)作為潛在聚類中心的新方法，該算法核心思想是信息傳播過(guò)程中每個(gè)數(shù)據(jù)點(diǎn)都會(huì)找到自己歸屬的類［10］。近鄰傳播算法的輸入值是數(shù)據(jù)點(diǎn)之間的相似性矩陣，見式（1），其中S（k，k）更容易成為聚類中心［11］。而最終聚類效果受偏向參數(shù)P值影響很大，P值一般選取輸入相似度矩陣的中值，會(huì)產(chǎn)生一個(gè)適中的類數(shù)或者最小的類數(shù)［12］。數(shù)據(jù)點(diǎn)之間存在著兩種信息交換，見式（2）和式（3），每個(gè)數(shù)據(jù)點(diǎn)都會(huì)參與兩種類別信息的競(jìng)爭(zhēng)，這兩種信息會(huì)決定在任意時(shí)間數(shù)據(jù)點(diǎn)的歸屬情況，吸引度矩陣R是數(shù)據(jù)點(diǎn)i發(fā)送到候選類中心k的信息，決定k作為數(shù)據(jù)點(diǎn)i聚類中心的適合程度［13］。歸屬度矩陣A是候選類中心k發(fā)送給數(shù)據(jù)點(diǎn)i的信息，決定數(shù)據(jù)點(diǎn)i選擇k做為類中心的適合程度［14］，當(dāng)更多數(shù)據(jù)點(diǎn)和候選聚類中心k吸引度是正數(shù)時(shí)，k作為類中心的可能性會(huì)增大。為了限制吸引度這種巨大影響，歸屬度的迭代公式會(huì)不一樣，是為避免它們之間的和為0。式（4）用來(lái)決定誰(shuí)是真正的聚類中心，當(dāng)聚類中心點(diǎn)重合，或者達(dá)到最大迭代次數(shù)，信息傳遞過(guò)程就會(huì)結(jié)束［15］。同時(shí)，該算法為了避免震蕩性不斷增大，使用式（5）和式（6）解決這個(gè)問題，不斷更新吸引度矩陣和歸屬度矩陣，一般取λ＝0.5，聚類中心連續(xù)10次沒有變化時(shí)，算法結(jié)束［16］。

2 多尺度變換

MDS是基于數(shù)據(jù)點(diǎn)之間的相似性或者距離，并在低維空間表示出來(lái)［17］?；驹砭褪羌s簡(jiǎn)后低維空間任意兩點(diǎn)間的距離應(yīng)該與它們?cè)谠呔S空間中的距離相同［18］，MDS的求解過(guò)程用式（7）～式（9）等合適的準(zhǔn)則函數(shù)來(lái)體現(xiàn)在低維空間中對(duì)高維聚類的重建誤差，可以通過(guò)梯度下降法對(duì)這些函數(shù)求解。

MDS是一種非監(jiān)督的降維方法，文中選用Matlab軟件自動(dòng)生成三維二項(xiàng)分布數(shù)據(jù)，如圖1和圖2所示。

圖1 二項(xiàng)分布數(shù)據(jù)三維視圖

圖2 MDS后二項(xiàng)分布數(shù)據(jù)視圖

圖1是該數(shù)據(jù)的空間分布，經(jīng)過(guò)MDS映射到二維空間，圖2是該數(shù)據(jù)的平面映射分布。從視覺上看，兩種數(shù)據(jù)分布情況空間距離感是一致的，數(shù)據(jù)點(diǎn)間的距離保持不變。

3 基于多尺度變換的近鄰傳播算法MDSAP

近鄰傳播算法對(duì)于高維數(shù)據(jù)的處理性能不佳，維度增高，算法收斂速度變慢，甚至無(wú)法收斂。聚類精度也越來(lái)越低，因此，文中采用MDS降維方法，從圖1和圖2可以看到數(shù)據(jù)點(diǎn)間的空間距離沒有變化，也就是說(shuō)，原本是一類的數(shù)據(jù)還是歸屬到一類中，這符合聚類假設(shè)的原理，利用MDS降維后對(duì)于數(shù)據(jù)點(diǎn)歸屬和產(chǎn)生的類的個(gè)數(shù)沒有影響。

基于穩(wěn)定閾值的吸引子傳播聚類算法如下：

1）輸入相似性矩陣S（i，j）；

2）設(shè)置輸入矩陣，MDS運(yùn)算；

3）設(shè)置搜索偏向參數(shù)，初始偏向參數(shù)是相似性矩陣S（i，j）的中位數(shù)；

4）更新矩陣R和矩陣A；

5）更新吸引度和歸屬度矩陣；

6）達(dá)到最大迭代次數(shù)，算法結(jié)束。

4 仿真模擬實(shí)驗(yàn)

仿真模擬實(shí)驗(yàn)環(huán)境為Pentium G645 2.9GHz CPU，4GB內(nèi)存。所有編程都在Matlab R2012b上完成和仿真。實(shí)驗(yàn)數(shù)據(jù)集參數(shù)及AP和MDSAP聚類算法實(shí)驗(yàn)結(jié)果比較分別見表1和表2。

表1 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)

表2 AP和MDSAP聚類算法實(shí)驗(yàn)結(jié)果比較

實(shí)驗(yàn)所采用的數(shù)據(jù)集都是UCI標(biāo)準(zhǔn)數(shù)據(jù)集，保持?jǐn)?shù)據(jù)的真實(shí)性和有效性，為驗(yàn)證該算法的聚類效果，選用同種實(shí)驗(yàn)數(shù)據(jù)，并采用Silhouette指標(biāo)作為約束規(guī)則的考量標(biāo)準(zhǔn)，該指標(biāo)利用類內(nèi)平均距離和最小類間距離評(píng)價(jià)聚類結(jié)果，Sil值大于0.5，說(shuō)明聚類空間界限分明，Sil值小于0.5，說(shuō)明聚類空間出現(xiàn)重疊，而Sil小于0.2代表聚類結(jié)果失真［19］，通過(guò)此指標(biāo)來(lái)衡量改進(jìn)后算法的好壞，而對(duì)于聚類結(jié)果有重大影響的偏向參數(shù)P值，都采用相似性矩陣的中值，不做任何改變。以上控制了影響算法結(jié)果的所有外在參數(shù)，保證對(duì)比試驗(yàn)得出的結(jié)論是科學(xué)有效的。

表1選用2個(gè)低維數(shù)據(jù)集Iris和Haberman，2個(gè)高維數(shù)據(jù)集Wine和Ionosphere，方便觀察MDSAP在低維和高維的表現(xiàn)，表2是AP和MDSAP實(shí)驗(yàn)結(jié)果對(duì)比，可以看出，低維數(shù)據(jù)集Iris和Haberman差距較小，MDSAP精度值只有較小幅度提高，而Wine數(shù)據(jù)集維度是13，稍高于其它數(shù)據(jù)集，精度差距只有0.8左右。對(duì)于34維的Ionosphere數(shù)據(jù)集，可以很清楚地看到改進(jìn)的MDSAP聚類算法的優(yōu)越性，面對(duì)高維數(shù)據(jù)，能夠較好地改良傳統(tǒng)算法的收斂性和增加聚類精度。以上結(jié)果說(shuō)明，基于多尺度變換的近鄰傳播算法聚類性能是高于原算法的，而且維度越高，MDSAP聚類算法的優(yōu)越性越大。

5 結(jié) 語(yǔ)

近鄰傳播聚類算法作為一種無(wú)須事先指定類數(shù)的算法廣受關(guān)注，文中針對(duì)該算法面向高維數(shù)據(jù)聚類效果不好的弊端，利用多尺度變換能夠?qū)⒏呔S數(shù)據(jù)映射到低維空間的特點(diǎn)，將二者結(jié)合，增強(qiáng)近鄰傳播算法在高維數(shù)據(jù)挖掘領(lǐng)域的應(yīng)用能力。經(jīng)過(guò)標(biāo)準(zhǔn)數(shù)據(jù)集的比較測(cè)試得出，文中提出的基于多尺度的近鄰傳播算法比傳統(tǒng)算法精度更高，聚類效果更好。

［1］ 許曉麗，盧志茂，張格森，等.改進(jìn)近鄰傳播聚類的彩色圖像分割［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，24（4）：514－519.

［2］ 施成湘.基于二次分水嶺和近鄰傳播聚類的彩色圖像分割算法研究與實(shí)現(xiàn)［J］.西南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，38（8）：125－129.

［3］ 許喆，薛智鋒，陳福才，等.基于改進(jìn)的近鄰傳播學(xué)習(xí)算法的視頻拷貝檢測(cè)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2014，35（9）：3185－3189.

［4］ 文翰，肖南峰.基于強(qiáng)類別特征近鄰傳播的半監(jiān)督文本聚類［J］.模式識(shí)別與人工智能，2014（7）：646－654.

［5］ 盧志茂，李純，張琦，等.近鄰傳播的文本聚類集成譜算法［J］.哈爾濱工程大學(xué)學(xué)報(bào)，2012，33（7）：899－905.

［6］ Inmar E Givoni，F(xiàn)rey B J.A binary variable model for affinity propagation［J］.Neural Computation，2009，21（6）：1589－1600.

［7］ Qasim I，Jeong J W，Heu J U，et al.Concept map construction from text documents using affinity propagation［J］.Journal of Information Science，2013（11）：1281－1290.

［8］ 肖宇，于劍.基于近鄰傳播算法的半監(jiān)督聚類［J］.軟件學(xué)報(bào)，2008，19（11）：2803－2813.

［9］ 董俊，王鎖萍，熊范綸，等.可變相似性度量的近鄰傳播聚類［J］.電子與信息學(xué)報(bào)，2010，32（3）：509－514.

［10］ 魯偉明，杜晨陽(yáng)，魏寶剛，等.基于MapReduce的分布式近鄰傳播聚類算法［J］.計(jì)算機(jī)研究與發(fā)展，2012，49（8）：1762－1772.

［11］ 王娟，王萍.直接零件標(biāo)志條碼區(qū)域定位算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2014，26（7）：1159－1166.

［12］ Dueck D，F(xiàn)rey B J.Non－metric affinity propagation for unsupervised image categorization［C］／／Computer Vision，2007.［S.l.］：IEEE 11th International Conference on IEEE，2007：1－8.

［13］ Lu Z，Carreira－Perpinan M A.Constrained spectral clustering through affinity propagation［C］／／Computer Vision and Pattern Recognition，2008.［S.l.］：Conference on IEEE，2008：1－8.

［14］ 杜錫壽，陳庶樵，張建輝，等.P2P流量的精細(xì)化識(shí)別方法研 究［J］.電 子 與 信 息 學(xué) 報(bào)，2012，34（7）：1709－1714.

［15］ 冷亞軍，梁昌勇，陸文星，等.基于改進(jìn)近鄰傳播算法的Web用戶聚類［J］.情報(bào)學(xué)報(bào)，2012，31（9）：993－997.

［16］ Leone M，Weigt M.Clustering by soft－constraint affinity propagation：applications to gene－expression data［J］.Bioinformatics，2007，23（20）：2708－2715.

［17］ 何光輝，張?zhí)?，唐遠(yuǎn)炎，等.非監(jiān)督子空間學(xué)習(xí)中關(guān)聯(lián)度量多維尺度分析［J］.中國(guó)圖象圖形學(xué)報(bào)，2011，16（12）：2152－2158.

［18］ 孫鍵，趙紅，趙宇彤，等.基于多維尺度分析的企業(yè)社會(huì)責(zé)任重疊測(cè)評(píng)實(shí)證研究［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011，41（9）：106－114.

［19］ 劉曉楠，尹美娟，李明濤，等.面向大規(guī)模數(shù)據(jù)的分層近鄰傳播聚類算法［J］.計(jì)算機(jī)科學(xué)，2014，41（3）：185－188，192.