彭長生

(江蘇大學計算機科學與通信工程學院，江蘇鎮(zhèn)江212013)

所謂聚類(clustering)，是將物理或抽象對象的集合分成由類似的對象組成的多個類的過程.聚類完成后所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異.目前傳統(tǒng)的聚類算法主要是基于層次聚類和迭代的平方誤差分區(qū)聚類兩種方法［1］.在諸多的聚類算法中，K-Means是應用最廣泛的算法之一.與其他算法相比，K-Means具有算法簡單易實現(xiàn)且聚類效果穩(wěn)定的特點.其算法思想大致如下:首先從n個數(shù)據(jù)對象X={x1，x2，…，xn}中任意選擇k(k＜n)個對象作為初始聚類中心c1，c2，…，ck，而對于所剩下其他對象，則根據(jù)它們與這些聚類中心的歐式距離d(xi，cj)= ‖xi-cj‖(i=1，2，…，n;j=1，2，…，k)，分別將它們劃分到與其最近的聚類.然后重新計算每個所獲得的新聚類的聚類中心c*i=，(n表示屬于類c的對象個數(shù)i=1，2，…，iik)，不斷重復這一過程直到標準測度函數(shù)J=)收斂為止.

而當前隨著網(wǎng)絡和通訊技術的迅速發(fā)展和普及，各類企業(yè)、個人應用產(chǎn)生了大量自治的、分布式的數(shù)據(jù).如何從大量分布數(shù)據(jù)源中進行有效的知識挖掘抽取，已經(jīng)成為一個重要的研究課題.比如在建的大學數(shù)字圖書館國際合作計劃［2］(China academic digital associative library，CADAL)整合了各種圖書資源，在數(shù)字圖書館中，有大量的插圖以及文本信息，同時包括來自互聯(lián)網(wǎng)的相關圖像、視頻信息，要對這些數(shù)據(jù)進行有效的管理并提供好的檢索服務，就需要分布式聚類技術對這些數(shù)據(jù)進行有效的分類、生成良好特征表達并創(chuàng)建索引.由于把如此巨大的海量數(shù)據(jù)全部集中到某一個中心服務器進行全局聚類在計算上是不可能的，因此很多學者在分布式聚類算法上做了大量研究.如文獻［3-8］研究聚類的并行算法，通過將數(shù)據(jù)平攤到各個計算節(jié)點實現(xiàn)聚類的并行化.然而以上算法僅僅是實現(xiàn)了聚類的并行化，現(xiàn)實中存在數(shù)據(jù)隱私安全、傳輸代價等因素，以上算法并未考慮.

近年來，隨著P2P(peer-to-peer)技術的廣泛應用，文件共享、視頻點播等諸多P2P網(wǎng)絡應用［9］在互聯(lián)網(wǎng)上日益興盛.P2P網(wǎng)絡上出現(xiàn)了越來越多的海量數(shù)據(jù)，同時由于P2P網(wǎng)絡的高度自治特點，數(shù)據(jù)資源散落地分布在網(wǎng)絡的各個節(jié)點上，研究適用于P2P分布式環(huán)境的分布式聚類算法可以有效解決P2P網(wǎng)絡上大規(guī)模海量數(shù)據(jù)的挖掘和隱私保護，這引起學術界和工業(yè)界的廣泛興趣［10-15］.文獻［10］提出 Probe/Echo算法，通過多次迭代發(fā)送Probe/Echo消息，完成整個網(wǎng)絡的聚類.M.Dumitrescu等［11］提出了一種高維度數(shù)據(jù)上的集體式主成分分析法CPCA(collective principal component analysis)，該算法可與某種現(xiàn)成的聚類模塊結(jié)合在一起，發(fā)展成一種分布式聚類.S.Nakahara等［12］構(gòu)建了一種分層分布式對等聚類模型HP2PC(hierarchically peer-to-peer clustering)，該模型建立在一種多層覆蓋網(wǎng)絡之上，以模塊化的方式分割聚類問題.Jin Ruoming 等［13］提出了 DFEKM(distributed fast and exact K-means clustering)算法，通過計算一個節(jié)點的聚類置信半徑來消除邊緣數(shù)據(jù)對聚類速度的影響，提高了分布式聚類效率.此外，國內(nèi)的學者也對P2P網(wǎng)絡上的分布式聚類進行了廣泛研究.如張國印等［14］提出一種基于集成學習的分布式聚類思想.唐九陽等［15］提出一種 K-DmeansWM(K-Dmeans without master)算法，其特點在于每次計算時，都會自動去選擇當前資源相對較好的節(jié)點進行聚類.王菁等［16］利用集合差異度實現(xiàn)基于內(nèi)容聚類的P2P搜索模型提高查詢效率和減少冗余消息，利用節(jié)點之間的集合差異度實現(xiàn)基于內(nèi)容的聚類，既降低了查詢時間，又減少了冗余消息.

為了減少網(wǎng)絡中分布式聚類迭代的次數(shù)，降低網(wǎng)絡中分布式聚類對帶寬的消耗.DFEKM算法發(fā)現(xiàn)聚類中同一類數(shù)據(jù)分布上存在稀疏或稠密的現(xiàn)象，在聚類過程中通過保持稠密數(shù)據(jù)的類別屬性不發(fā)生改變，而不考慮稀疏數(shù)據(jù)對聚類的影響，如此可提高分布式聚類過程中網(wǎng)絡帶寬資源的利用效率，并達到聚類精度很高的近似聚類效果.應用此原理，文中提出一種基于Fisher判別來確定置信半徑的分布式K-Means聚類算法，通過應用Fisher線性判別確定節(jié)點在聚類過程中的置信半徑，將此半徑用以指導下一步的聚類，并將此算法與DFEKM聚類算法進行比較.

1 基于Fisher判別置信半徑的分布式K-Means聚類算法

由于P2P網(wǎng)絡上的分布式聚類算法大都需要在網(wǎng)絡中多次迭代聚類，以使聚類達到穩(wěn)定狀態(tài)，存在著P2P網(wǎng)絡帶寬使用率高等問題.為此，文中根據(jù)數(shù)據(jù)在P2P網(wǎng)絡節(jié)點中的分布的稀疏或稠密情況，提出一種基于 Fisher判別置信半徑的分布式K-Means聚類算法，該算法應用Fisher線性判別比率找到同一類數(shù)據(jù)節(jié)點的稠密和稀疏分布，確定聚類的置信半徑并指導下一步的聚類，從而可以用較少的迭代數(shù)使P2P網(wǎng)絡上的聚類能快速達到穩(wěn)定狀態(tài)，減少了P2P網(wǎng)絡在聚類過程中所需傳遞的網(wǎng)絡流量.

1.1 Fisher線性判別率介紹

Fisher線性判別的基本思想［17］就是把空間中的數(shù)據(jù)點投影到一條直線上去，使得不同類的樣本點在空間中能夠形成互相分離的、且各自內(nèi)部緊湊的集合.為了達到這樣的分類效果，必須選擇合適的投影直線，以最大限度地區(qū)分各類數(shù)據(jù)點的投影方向.

假設有n個d維數(shù)據(jù)樣本X={x1，x2，…，xn}，它們分屬于2個不同的類別，其中大小為n1的樣本子集D1屬于類別ω1，大小為n2的樣本子集D2屬于類別ω2.如果對X中的各個成分做線性組合，就得到一個標量點積y=WTX.Fisher線性可分性準則要求在投影y=WTX下，以下準則函數(shù)達到最大化.

式中:SB=(m1-m2)(m1-m2)T是總類間散布矩陣是該類樣本均值;S=S+S是W12類內(nèi)散布矩陣之和.使準則函數(shù)最大化的W必須滿足SW=BλSWW.因為SBW總是位于m1-m2的方向上.由于W的模對問題無關緊要，因此易得使準則函數(shù)最大化時的W*即為

1.2 基于Fisher線性判別率的置信半徑

根據(jù)以上Fisher判別準則，將之應用到本文研究:假設某一類數(shù)據(jù)共有N個數(shù)據(jù)對象，考慮將其分為兩類問題，假設N個數(shù)據(jù)對象的中心為μ，對N個數(shù)據(jù)對象，分別計算其到中心的距離，并按照升序排列，得到一個按照距離排序的集合{di，i=1，2，…，N}，及其對應的數(shù)據(jù)對象集合為{Xi，i=1，2，…，N}.其中，Xi是第i個到中心距離最近的數(shù)據(jù)對象，其到中心的距離為di.Fisher線性判別率表示為

式中和分別為所有數(shù)據(jù)對象以Xr為分隔點的兩個聚類均值距離以及距離方差和，即為

式中:μi是集合{di，i=1，2，…，r}的均值;類似地，μj是集合{di，i=r+1，r+2，…，N}的均值則是{di，i=1，2，…，r}的方差;是{di，i=r+1，r+2，…，N}的方差;JFisher(r)則是以{Xi，i=1，2，…，r}和{Xi，i=r+1，r+2，…，N}為兩類的 Fisher線性判別率.所有數(shù)據(jù)對象集上的Fisher線性判別率越大，說明通過該方法得到的兩類數(shù)據(jù)越明顯，從而找到以聚類中心的數(shù)據(jù)稠密與稀疏的分界點，即當Fisher判別率最大時，假設為JFisher(R)，此時數(shù)據(jù)對象XR為聚類的最佳分隔數(shù)據(jù)點，所得置信半徑為

1.3 基于置信半徑的分布式K-Means聚類算法

文中采用Probe/Echo消息傳遞機制［10］來實現(xiàn)基于置信半徑的分布式K-Means聚類.在網(wǎng)絡中隨機選擇一個節(jié)點作為起始節(jié)點，然后隨機選擇k個數(shù)據(jù)作為初始聚類中心;初始節(jié)點將當前的聚類中心數(shù)據(jù)作為Probe消息轉(zhuǎn)發(fā)給鄰居節(jié)點，節(jié)點接收到Probe消息后向其鄰居節(jié)點轉(zhuǎn)發(fā)該Probe消息并更新其聚類中心;節(jié)點在發(fā)出Probe消息后就等待其鄰居節(jié)點回發(fā)Echo消息，當一個節(jié)點接收到的消息總數(shù)等于其鄰居數(shù)時，將接收到Echo消息中包含的聚類信息與自身節(jié)點的聚類信息進行合并同時更新Further變量的值，若該節(jié)點不是初始節(jié)點就回發(fā)Echo消息給前一個其發(fā)Probe消息的節(jié)點，若是初始節(jié)點就判斷聚類是否結(jié)束，如果初始節(jié)點前后兩次聚類中心的距離小于置信半徑并且接收到Echo消息中所包含的Further變量均為false，則聚類迭代過程結(jié)束;否則重復上述過程.

以上是分布式聚類的整體迭代過程，網(wǎng)絡中某個節(jié)點P更新聚類數(shù)據(jù)的具體算法過程如圖1所示.

由圖1可見，節(jié)點P等待從鄰居節(jié)點接收消息，第1次接收到Probe消息時(假設發(fā)送此Probe消息的節(jié)點是Pa)，將接收到的消息數(shù)置1，并記Pa為節(jié)點P的父節(jié)點，然后將接收到的Probe消息轉(zhuǎn)發(fā)給除節(jié)點Pa外的所有鄰居節(jié)點并更新聚類中心并根據(jù)公式(2)-(5)計算新的置信半徑，繼續(xù)等待接收其他消息，每收到一條消息則消息數(shù)自增1，若節(jié)點P接收到的消息數(shù)等于其鄰居節(jié)點數(shù)則首先判斷是否需要進一步聚類，若節(jié)點P前后兩次聚類中心的距離超過置信半徑或者接收到Echo消息中所包含的Further變量不全為false，說明該節(jié)點或者其鄰居節(jié)點需要進一步聚類將Further變量置true，否則將Further變量置false;然后合并節(jié)點聚類信息并向節(jié)點Pa發(fā)Echo消息，結(jié)束本節(jié)點的消息處理過程.合并節(jié)點聚類信息公式為

式中:cPj為節(jié)點P的第j類的聚類中心為節(jié)點P的第j類的類內(nèi)數(shù)據(jù)對象數(shù);cij為P的第i個鄰居節(jié)點內(nèi)第j個聚類的中心;wij為P的第i個鄰居節(jié)點內(nèi)第j個聚類的類內(nèi)點數(shù);Nb為P的鄰居節(jié)點個數(shù).

圖1 節(jié)點消息處理流程圖

2 試驗結(jié)果

2.1 試驗數(shù)據(jù)和度量標準

本試驗在裝有Intel Core Duo E7500處理器，內(nèi)存為2 GB，安裝了Windows 7系統(tǒng)的PC機上運行.采用java編程語言用棧來模擬Probe/Echo機制來進行分布式聚類，其中節(jié)點與節(jié)點之間的連接采用Gnutella協(xié)議［18］的隨機連接拓撲結(jié)構(gòu).網(wǎng)絡中設置了500個節(jié)點.本試驗首先在3類2維高斯混合分布中取60 000個模擬數(shù)據(jù)作為試驗數(shù)據(jù)，其參數(shù)設置如下:均值分別為(0，0)，(6，2)，(8，8);協(xié)方差矩陣均為二維單位矩陣;將60 000個模擬數(shù)據(jù)平均分配給500個網(wǎng)絡節(jié)點;聚類的k值設為3.數(shù)據(jù)分布如圖2所示.

圖2 數(shù)據(jù)分布圖

其次還采用了從LIBSVM［19］上下載的真實數(shù)據(jù)a8a和ijcnn進行試驗，其中a8a含有22 696個123維數(shù)據(jù)，聚類的k值設為5，ijcnn中包含141 691個22維數(shù)據(jù)，聚類的k值設為12.

為評價數(shù)據(jù)聚類的效果，引入PMM(percentage membership mismatch)［18］作為衡量聚類精度的標準.PMM定義為

式中:Lcent(x)為數(shù)據(jù)點x通過集中式K-Means聚類后所屬類別;LP2P(x)為x通過本算法聚類后所屬類別;PMM則代表原始數(shù)據(jù)通過集中式K-Means聚類后得到的結(jié)果和通過本文算法聚類后所得到結(jié)果之間的誤差率.PMM的值越小，說明聚類結(jié)果越接近集中式K-Means聚類效果.

同時，為了衡量分布式聚類的速度，同時也是評價網(wǎng)絡中的帶寬消耗量，將聚類所需的迭代數(shù)作為衡量分布式聚類帶寬消耗的評價指標，顯然，迭代數(shù)越多，聚類的速度越慢，帶寬消耗也越大.

2.2 仿真結(jié)果

為了更好地進行比較，本試驗首先對正態(tài)模擬數(shù)據(jù)，應用文中算法與DFEKM算法重復進行了50次分布式聚類試驗，并計算出每次的PMM值和迭代數(shù)，結(jié)果如圖3，4所示.

圖3 文中算法聚類結(jié)果、DFEKM聚類結(jié)果和原始數(shù)據(jù)之間的PMM

從圖3可見試驗數(shù)據(jù)通過文中算法聚類后的結(jié)果的PMM值大都小于1.5，并且非常接近DFEKM聚類算法的結(jié)果，精度十分可觀.

圖4 文中算法和DFEKM聚類算法50次試驗的迭代數(shù)

圖4中藍色線代表文中算法運行50次，每次的所需迭代數(shù)，每次試驗大致需要1～3次迭代能夠完成聚類，50次試驗所需迭代數(shù)的均值為1.82;紅色線代表DFEKM聚類算法運行50次每次試驗所需的迭代數(shù)，50次試驗迭代數(shù)的均值為2.52.在速度上較DFEKM聚類算法有將近30%的提升.

對從LibSVM網(wǎng)站上下載的兩組真實數(shù)據(jù)集合a8a和ijcnn進行了聚類試驗和對比分析，結(jié)果如表1所示.

表1 不同數(shù)據(jù)集合下文中方法和DFEKM算法聚類性能的比較

從表1可見，文中方法相對于DFEKM雖然帶寬的消耗稍有增加但是在聚類精度上有了很大的提高，另外DFEKM算法對計算置信半徑的參數(shù)的設置非常敏感，而文中方法可以根據(jù)數(shù)據(jù)的分布自動計算置信半徑不受參數(shù)的限制，因此比DFEKM方法有更強的健壯性.

3 結(jié)論

文中提出一種基于置信半徑的分布式K-Means算法，該算法根據(jù)各節(jié)點中數(shù)據(jù)分布緊密程度，應用Fisher線性判別比率找到同一類數(shù)據(jù)在節(jié)點的稠密和稀疏分布，從而確定聚類的置信半徑.試驗表明，相比DFEKM聚類算法，在聚類結(jié)果和聚類速度上，文中算法能根據(jù)數(shù)據(jù)的分布不同，能夠兼顧速度與精度，達到很好的平衡效果.這表明算法具有更強的健壯性.今后將進一步研究分布式聚類算法，并且將算法應用于圖像分割、模式識別等領域.

References)

［1］Jain A K，Murty M N，F(xiàn)lynn P J.Data clustering:a review［J］.ACM Computing Surveys，1999，31(3):264-323.

［2］杜晨陽.分布式聚類算法研究與應用［D］.杭州:浙江大學計算機學院與技術學院，2011.

［3］Chamam A，Pierre S.A distributed energy-efficient clustering protocol for wireless sensor networks［J］.Computers＆Electrical Engineering，2010，36(2):303-312.

［4］Hammouda K M，Kamel M S.Models of distributed data clustering in peer-to-peer environments［J］.Knowledge and Information Systems，2014，38(2):303-329.

［5］徐 楠，孫亞民，黃 波，等.無線傳感器網(wǎng)絡跨層自適應周期分簇路由模型［J］.計算機科學，2011，38(5):56-59，78.Xu Nan，Sun Yamin，Huang Bo，et al.Cross-layer adaptive round distributed clustering routing model for wireless sensor networks［J］.Computer Science，2011，38(5):56-59，78.(in Chinese)

［6］Ma Yajie，Guo Yike，Tian Xiangchuan，et al.Distributed clustering-based aggregation algorithm for spatial correlated sensor networks［J］.IEEE Sensors Journal，2011，11(3):641-648.

［7］魯偉明，杜晨陽，魏寶剛，等.基于MapReduce的分布式近鄰傳播聚類算法［J］.計算機研究與發(fā)展，2012，49(8):1762-1772.Lu Weiming，Du Chenyang，Wei Baogang，et al.Distributed affinity propagation clustering based on MapReduce［J］.Journal of Computer Research and Development，2012，49(8):1762-1772.(in Chinese)

［8］宋余慶，王春紅，陳健美，等.基于高斯混合密度模型的醫(yī)學圖像聚類方法［J］.江蘇大學學報:自然科學版，2009，30(3):293-296.Song Yuqing，Wang Chunhong，Chen Jianmei，et al.Clustering of medical image based on Gaussian mixture density model［J］.Journal of Jiangsu University:Natural Science Edition，2009，30(3):293-296.(in Chinese)

［9］Ramzan N，Park H，Izquierdo E.Video streaming over P2P networks:challenges and opportunities［J］.Signal Processing:Image Communication，2012，27(5):401-411.

［10］Eisenhardt M，Müller W，Henrich A.Classifying documents by distributed P2P clustering［J］.GI Jahrestagung，2003，35(2):286-291.

［11］Dumitrescu M，Andonie R.Clustering superpeers in P2P networks by growing neural gas［C］∥Proceedings of2012 20th Euromicro Conference on Parallel，Distributed and Network-based Processing. Garching， Germany:IEEE Computer Society，2012:311-318.

［12］Nakahara S，Ohta T，Kakuda Y.Experimental evaluation of MANET based on autonomous clustering and P2P overlay network［C］∥Proceedings of2013First International Symposium on Computing and Networking.Matsuyama，Ehime，Japan:IEEE Computer Society，2013:480-483.

［13］Jin Ruoming，Goswami Anjan，Agrawal Gagan.Fast and exact out-of-core and distributed K-means clustering［J］.Knowledge and Information Systems，2006，10(1):17-40.

［14］張國印，李 軍.移動對等網(wǎng)絡覆蓋網(wǎng)［J］.軟件學報，2013，24(1):139-152.Zhang Guoyin，Li Jun.Overlays in mobile P2P networks［J］.Journal of Software，2013，24(1):139-152.(in Chinese)

［15］李 榴，唐九陽，葛 斌，等.k-DmeansWM:一種基于P2P網(wǎng)絡的分布式聚類算法［J］.計算機科學，2010，37(1):39-41.Li Liu，Tang Jiuyang，Ge Bin，et al.k-DmeansWM:an effective distributed clustering algorithm based on P2P［J］.Computer Science，2010，37(1):39-41.(in Chinese)

［16］王 菁，張煥杰，楊壽保，等.利用集合差異度實現(xiàn)基于內(nèi)容聚類的P2P搜索模型［J］.中國科學院研究生院學報，2007，24(2):241-247.Wang Jing，Zhang Huanjie，Yang Shoubao，et al.Content-based clustered P2P search model depending on set distance［J］.Journal of the Graduate School of Chinese Academy of Sciences，2007，24(2):241-247.(in Chinese)

［17］Richard O Duda，Peter E Hart，David Stork.模式分類［M］.李宏東，姚天翔，譯.2版.北京:機械工業(yè)出版社，2003:96-100.

［18］Datta S，Giannella C R，Kargupta H.Approximate distributed K-means clustering over a Peer-to-Peer network［J］.IEEE Transactions on Knowledge and Data Engineering，2009，21(10):1372-1388.

［19］Chang C C，Lin C J.LIBSVM:a library for support vector machines［J］.ACM Transactions on Intelligent SystemsandTechnology， 2011， doi:10.1145/1961189.1961199.