基于網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的標(biāo)簽傳播聚類(lèi)算法①

吳清壽,郭 磊,余文森

1(武夷學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,武夷山 354300)

2(武夷學(xué)院 認(rèn)知計(jì)算與智能信息處理福建省高校重點(diǎn)實(shí)驗(yàn)室,武夷山 354300)

3(智慧農(nóng)林福建省高校重點(diǎn)實(shí)驗(yàn)室,福州 350002)

大數(shù)據(jù)時(shí)代,各個(gè)領(lǐng)域時(shí)刻都在產(chǎn)生大量的數(shù)據(jù),這些數(shù)據(jù)通常都是無(wú)標(biāo)簽的,要確定每一個(gè)樣本的標(biāo)簽通常是困難的.機(jī)器學(xué)習(xí)算法中的無(wú)監(jiān)督學(xué)習(xí)可以對(duì)無(wú)標(biāo)簽的數(shù)據(jù)進(jìn)行學(xué)習(xí),以期能夠揭示數(shù)據(jù)之間的聯(lián)系或存在的內(nèi)在規(guī)律.聚類(lèi)算法是無(wú)監(jiān)督學(xué)習(xí)的代表,可通過(guò)數(shù)據(jù)的相似屬性將數(shù)據(jù)進(jìn)行分組,幫助人們?cè)鲞M(jìn)對(duì)數(shù)據(jù)的理解,如利用聚類(lèi)技術(shù)發(fā)現(xiàn)具有類(lèi)似功能的基因組,檢測(cè)疾病的時(shí)空分布模式等.

傳統(tǒng)的聚類(lèi)算法可大致劃分為基于劃分的方法,基于層次的方法,基于密度的方法,基于譜圖劃分的方法和其他方法[1].K-means 是分割聚類(lèi)的最早也是最出名的研究,其對(duì)初始的質(zhì)心選擇有較強(qiáng)的依賴性,且傾向于尋找圓形集簇.K-means 只考慮了連通性,Kuwil等[2]提出一種重心聚類(lèi)算法(Gravity Center Clustering,GCC),同時(shí)兼顧連通性和內(nèi)聚性,且無(wú)需提供聚類(lèi)的簇?cái)?shù).基于密度的方法中,DBSCAN (Density-Based Spatial Clustering of Application with Noise)[3]可以對(duì)任意形狀的數(shù)據(jù)聚類(lèi),但確定其半徑和包含的樣本數(shù)量是一個(gè)難點(diǎn),且在簇間混合度較大時(shí)對(duì)樣本標(biāo)簽誤判的概率較高.郭艷婕等[4]提出一種改進(jìn)的GS-DBSCAN 算法,通過(guò)計(jì)算數(shù)據(jù)的分布特性,可自適應(yīng)確定半徑和半徑內(nèi)包含的樣本數(shù)。層次聚類(lèi)算法包括分裂法和凝聚法,其中,CURE (Clustering Using REpresentative)算法[5]能夠處理形狀和尺寸差別較大的簇,對(duì)噪音點(diǎn)不敏感,但對(duì)特殊形狀的類(lèi)簇識(shí)別能力較差.基于圖分割方法的譜聚類(lèi)(Spectral Clustering)算法[6]也可以對(duì)任意形狀的樣本進(jìn)行聚類(lèi),且通常能夠收斂于全局最優(yōu)解,但其計(jì)算的時(shí)間復(fù)雜度較高,需要預(yù)先知道簇的數(shù)量,構(gòu)建合適的相似度矩陣是一個(gè)難點(diǎn).胡卓婭等[7]通過(guò)構(gòu)造本征間隙序列,可確定聚類(lèi)的簇?cái)?shù).最新的研究中,Xie等[8]提出一種互為最近鄰的層次聚類(lèi)算法(Reciprocalnearest-neighbors Supported Clustering,RSC),其假設(shè)互為最近鄰居的兩個(gè)樣本一定會(huì)劃分在同一個(gè)簇中.

對(duì)于高維數(shù)據(jù),要通過(guò)低維空間上的可視化觀察其聚類(lèi)特性是困難的,這對(duì)傳統(tǒng)聚類(lèi)方法提出了挑戰(zhàn).近年來(lái),基于復(fù)雜網(wǎng)絡(luò)的機(jī)器學(xué)習(xí)方法得到了研究者的關(guān)注[9].將向量化的數(shù)據(jù)轉(zhuǎn)換為以網(wǎng)絡(luò)表示的數(shù)據(jù),其過(guò)程是無(wú)損的.以網(wǎng)絡(luò)表示的數(shù)據(jù)相比以向量表示的數(shù)據(jù)擁有更多的信息,如樣本之間的關(guān)系結(jié)構(gòu)或者拓?fù)湫畔?通過(guò)觀測(cè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),更易于發(fā)現(xiàn)樣本的聚類(lèi)特性.

以Iris 數(shù)據(jù)集為例,從每個(gè)類(lèi)別中抽取其中的前10 個(gè)樣本,通過(guò)網(wǎng)絡(luò)構(gòu)建,得到的結(jié)果如圖1所示.其中,類(lèi)別標(biāo)簽為Iris-virginica 的節(jié)點(diǎn)中,樣本21 和26的特征與類(lèi)別Iris-versicolor 非常接近,經(jīng)網(wǎng)絡(luò)構(gòu)建后,其與類(lèi)別Iris-versicolor 中樣本的聯(lián)系較為緊密.其余節(jié)點(diǎn)都能與同類(lèi)別的節(jié)點(diǎn)保持稠密的連邊關(guān)系.

圖1 Iris 數(shù)據(jù)集部分樣本的拓?fù)鋱D

通過(guò)圖1中的拓?fù)浣Y(jié)構(gòu),可以看到樣本較為清晰的劃分為3 個(gè)簇,同一簇中節(jié)點(diǎn)間的連邊密度較大,而簇之間的連邊較為稀疏.

對(duì)向量表示的數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)化后,一種有效的聚類(lèi)方法是進(jìn)行社區(qū)發(fā)現(xiàn)[10].通常意義上,社區(qū)內(nèi)部的節(jié)點(diǎn)之間連邊稠密,而社區(qū)之間的連邊稀疏.

Raghavan 等[11]于2007年將一種半監(jiān)督學(xué)習(xí)算法標(biāo)簽傳播算法(Label Propagation Algorithm,LPA)[12]用于社區(qū)發(fā)現(xiàn),取得了良好的效果.LPA 算法具有接近線性的時(shí)間復(fù)雜度,這對(duì)規(guī)模越來(lái)越大的社交網(wǎng)絡(luò)研究具有重要的意義.然而,LPA 算法為每個(gè)節(jié)點(diǎn)初始化一個(gè)標(biāo)簽,容易造成標(biāo)簽傳播的隨機(jī)性,并增加了傳播過(guò)程的迭代次數(shù).將數(shù)據(jù)集進(jìn)行網(wǎng)絡(luò)化,節(jié)點(diǎn)間的連邊較為稀疏,用LPA 發(fā)現(xiàn)的社區(qū)數(shù)量一般遠(yuǎn)大于真實(shí)的類(lèi)簇?cái)?shù)量,聚類(lèi)準(zhǔn)確度較差.

鑒于LPA 具有接近的線性時(shí)間復(fù)雜度,將LPA 算法應(yīng)用于數(shù)據(jù)聚類(lèi)是一種有意義的嘗試.通過(guò)將向量表示的數(shù)據(jù)集構(gòu)建為網(wǎng)絡(luò)(數(shù)據(jù)集中的一個(gè)樣本對(duì)應(yīng)網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)),再用改進(jìn)的LPA 算法進(jìn)行社區(qū)發(fā)現(xiàn),將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分到不同社區(qū),即實(shí)現(xiàn)了數(shù)據(jù)集中樣本的聚類(lèi).本文提出一種低隨機(jī)性的改進(jìn)LPA 算法(Low Randomness Label Propagation Algorithm,LRLPA),用于對(duì)網(wǎng)絡(luò)化后的數(shù)據(jù)進(jìn)行聚類(lèi).LRLPA 算法主要針對(duì)LPA 的兩個(gè)不足進(jìn)行改進(jìn).(1)對(duì)于LPA隨機(jī)性較大的問(wèn)題,采用標(biāo)簽預(yù)處理和融入節(jié)點(diǎn)影響力的標(biāo)簽傳播過(guò)程,可有效降低其隨機(jī)性.(2)LPA 算法在稀疏網(wǎng)絡(luò)上可能會(huì)產(chǎn)生較多的社區(qū),本文提出一種社區(qū)內(nèi)聚度的社區(qū)質(zhì)量衡量指標(biāo),對(duì)內(nèi)聚度低的社區(qū)進(jìn)行優(yōu)化合并,可使得劃分的社區(qū)質(zhì)量更高,且社區(qū)數(shù)量更接近真實(shí)的情況.同時(shí),LRLPA 算法還保留了LPA 的高效性.

1 相關(guān)工作

1.1 社區(qū)發(fā)現(xiàn)算法

社區(qū)發(fā)現(xiàn)的相關(guān)算法中,早期,研究者主要基于圖論及矩陣論,提出用圖分割和譜分析方法進(jìn)行社區(qū)劃分,如KL 算法[13]和譜劃分算法[14,15].基于機(jī)器學(xué)習(xí)中聚類(lèi)算法思想的延伸,Lin 等[16]提出一種整數(shù)規(guī)劃方法用于檢測(cè)網(wǎng)絡(luò)中的分層社區(qū)結(jié)構(gòu),SCAN 算法[17]是基于密度聚類(lèi)的經(jīng)典社區(qū)發(fā)現(xiàn)算法.基于模塊度[18]優(yōu)化的社區(qū)發(fā)現(xiàn)算法中,BGLL[19]在稀疏網(wǎng)絡(luò)上有接近線性的時(shí)間復(fù)雜度,克服了此類(lèi)算法時(shí)間復(fù)雜度較大的缺點(diǎn).基于信息論的方法中,Infomap 算法[20]利用網(wǎng)絡(luò)上信息傳播的規(guī)律來(lái)識(shí)別社區(qū),與Infomap 算法類(lèi)似,CDID 算法[21]通過(guò)模擬網(wǎng)絡(luò)中的信息交換來(lái)發(fā)現(xiàn)社區(qū).

1.2 LPA 算法

LPA 算法[11]的基本思想：統(tǒng)計(jì)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的社區(qū)歸屬情況,某個(gè)標(biāo)簽對(duì)應(yīng)的節(jié)點(diǎn)數(shù)量最多,則選擇該標(biāo)簽作為當(dāng)前節(jié)點(diǎn)的標(biāo)簽.其算法步驟如下.

步驟1.為各節(jié)點(diǎn)選擇一個(gè)唯一的標(biāo)簽,通常將各節(jié)點(diǎn)標(biāo)簽初始化為節(jié)點(diǎn)的編號(hào).

步驟2.將所有節(jié)點(diǎn)隨機(jī)洗牌后,逐一更新節(jié)點(diǎn)標(biāo)簽.根據(jù)當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)標(biāo)簽情況,選擇對(duì)應(yīng)節(jié)點(diǎn)數(shù)量最多的標(biāo)簽作為目標(biāo)標(biāo)簽,用以更新當(dāng)前節(jié)點(diǎn)的標(biāo)簽.如果滿足條件的標(biāo)簽有多個(gè),則隨機(jī)選擇一個(gè)標(biāo)簽.

步驟3.重復(fù)步驟2,直到每一個(gè)節(jié)點(diǎn)的標(biāo)簽都不再發(fā)生變化為止.

步驟4.將具有相同標(biāo)簽的節(jié)點(diǎn)劃分為同一個(gè)社區(qū),算法終止.

1.3 LeaderRank 算法

LeaderRank[22,23]是基于PageRank[24]提出的用于網(wǎng)絡(luò)中節(jié)點(diǎn)排序的算法.與PageRank 相比,其增加了背景節(jié)點(diǎn)(ground node)g.在有向網(wǎng)絡(luò)中,將g與所有其他節(jié)點(diǎn)雙向連接,而在無(wú)向網(wǎng)絡(luò)中就是將g與所有節(jié)點(diǎn)建立連邊.計(jì)算每個(gè)節(jié)點(diǎn)的LR值,該值越大,表示該節(jié)點(diǎn)越重要.社交網(wǎng)絡(luò)中,LRi值可視為節(jié)點(diǎn)vi在網(wǎng)絡(luò)中的影響力[25].

算法初始設(shè)定LRg(0)=0,LRi(0)=1,即節(jié)點(diǎn)背景節(jié)點(diǎn)g的初始LR值為0,網(wǎng)絡(luò)中的其他節(jié)點(diǎn)初始的重要性相同,都為1 單位LR值.在t時(shí)刻,節(jié)點(diǎn)vi的LR值根據(jù)式(1)計(jì)算：

其中,Γi表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合,表示節(jié)點(diǎn)vj的出度,LRj(t-1)表示vj在t-1 時(shí)刻的LR值.在有向圖中,vj是指向vi的節(jié)點(diǎn),在無(wú)向圖中,vj是vi的鄰居節(jié)點(diǎn),所以δij=1.

重復(fù)式(1)的計(jì)算直至LR值不再發(fā)生變化或變化程度小于閾值,再根據(jù)式(2)修正所有節(jié)點(diǎn)的LR值.

其中,tc是式(1)收斂的迭代次數(shù),LRg(tc) 表示節(jié)點(diǎn)g迭代至收斂狀態(tài)時(shí)的LR值.

2 算法定義與實(shí)現(xiàn)

2.1 網(wǎng)絡(luò)構(gòu)建

一個(gè)包含n個(gè)樣本的數(shù)據(jù)集表示為X={x1,x2,···,xn},xi表示第i個(gè)樣本,其具有r個(gè)屬性,即xi=(xi1,xi2,···,xir).將X中的樣本構(gòu)建為無(wú)權(quán)無(wú)向的全連接網(wǎng)絡(luò),其對(duì)應(yīng)的網(wǎng)絡(luò)用G=(V,E)表示,V={v1,v2,···,vn}是網(wǎng)絡(luò)中節(jié)點(diǎn)的集合,E={e1,e2,···,em}表示網(wǎng)絡(luò)中邊的集合,em={(vi,vj)|vi≠vj?vi,vj∈V}.經(jīng)過(guò)網(wǎng)絡(luò)構(gòu)建,原數(shù)據(jù)集X中的樣本xi對(duì)應(yīng)網(wǎng)絡(luò)G中的節(jié)點(diǎn)vi.

網(wǎng)絡(luò)構(gòu)建的目標(biāo)是將空間中具有較近距離的樣本之間建立連邊關(guān)系,且構(gòu)建出的網(wǎng)絡(luò)是一個(gè)連通圖,節(jié)點(diǎn)之間的連邊盡量稀疏.本文采用kNN 和ε-radius 組合方法進(jìn)行網(wǎng)絡(luò)構(gòu)建.組合方法可以確保所有樣本點(diǎn)都出現(xiàn)在網(wǎng)絡(luò)中,且高密度區(qū)域的樣本點(diǎn)具有較多的連邊關(guān)系.

ε-radius 方法對(duì)樣本xi尋找半徑為eps的范圍內(nèi)的其他樣本NBi={xj|dist(xi,xj)

kNN 方法對(duì)樣本xi尋找歐氏空間中距離最近的k個(gè)樣本NNi={xj|與xi最近的k個(gè)節(jié)點(diǎn)},并在對(duì)應(yīng)的網(wǎng)絡(luò)中構(gòu)建節(jié)點(diǎn)vi與NNi中樣本對(duì)應(yīng)節(jié)點(diǎn)的連邊.kNN 方法保證空間中處于邊緣的點(diǎn)(噪音點(diǎn))也能夠與網(wǎng)絡(luò)中其它節(jié)點(diǎn)建立連邊關(guān)系,使得數(shù)據(jù)集X中的所有樣本都能出現(xiàn)在網(wǎng)絡(luò)中.

2.2 標(biāo)簽預(yù)處理

LPA 算法步驟1 中,初始標(biāo)簽分布散亂,標(biāo)簽傳播的隨機(jī)性較大,容易導(dǎo)致標(biāo)簽誤傳播,并增加算法的迭代次數(shù).一種可行的方法是對(duì)標(biāo)簽進(jìn)行預(yù)處理,使得相似度較高的節(jié)點(diǎn)具有相同的標(biāo)簽,提升后續(xù)標(biāo)簽傳播的穩(wěn)定性,縮減迭代次數(shù).

用節(jié)點(diǎn)的共同鄰居數(shù)衡量節(jié)點(diǎn)的相似度是一種常用的方法,其定義如式(3)：

其中,vj∈Γi,即只計(jì)算當(dāng)前節(jié)點(diǎn)vi和鄰居節(jié)點(diǎn)的相似度.

定義1.標(biāo)簽初始化規(guī)則.對(duì)于?vj∈Γi,計(jì)算CNi,j,將CNi,j值最大的節(jié)點(diǎn)對(duì)應(yīng)的標(biāo)簽作為vi的標(biāo)簽.式(4)求與vi公共鄰居數(shù)最大的節(jié)點(diǎn)編號(hào)k.當(dāng)與vi具有最大公共鄰居數(shù)的節(jié)點(diǎn)不止一個(gè)時(shí),隨機(jī)選擇一個(gè)節(jié)點(diǎn)標(biāo)簽作為vi的標(biāo)簽,vi的標(biāo)簽記為lbi.標(biāo)簽初始化規(guī)則定義為式(5)：

其中,rand(k)表示從集合k中隨機(jī)選擇一個(gè).

2.3 融合節(jié)點(diǎn)影響力的標(biāo)簽傳播

標(biāo)簽傳播階段,LPA 算法選擇標(biāo)簽的方法是統(tǒng)計(jì)鄰居節(jié)點(diǎn)的標(biāo)簽,一個(gè)標(biāo)簽對(duì)應(yīng)一組節(jié)點(diǎn),選擇對(duì)應(yīng)節(jié)點(diǎn)數(shù)最多的標(biāo)簽作為當(dāng)前節(jié)點(diǎn)的標(biāo)簽.有多個(gè)標(biāo)簽滿足條件的,就隨機(jī)選擇一個(gè)標(biāo)簽.在節(jié)點(diǎn)連邊較為稀疏的情況下,尤其是當(dāng)節(jié)點(diǎn)處于兩個(gè)社區(qū)的連接路徑上時(shí),以上方法容易造成標(biāo)簽誤傳播.引入節(jié)點(diǎn)影響力,在需要隨機(jī)選擇的情況下,依據(jù)標(biāo)簽對(duì)應(yīng)的節(jié)點(diǎn)LR值之和進(jìn)行輔助選擇,進(jìn)一步消除標(biāo)簽傳播的隨機(jī)性.

定義2.融合節(jié)點(diǎn)影響力的標(biāo)簽傳播規(guī)則.節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)中可能存在多個(gè)標(biāo)簽,統(tǒng)計(jì)每個(gè)標(biāo)簽對(duì)應(yīng)的節(jié)點(diǎn)數(shù)量,某個(gè)標(biāo)簽對(duì)應(yīng)的節(jié)點(diǎn)數(shù)量最多,則選擇該標(biāo)簽作為vi的標(biāo)簽.式(6)統(tǒng)計(jì)節(jié)點(diǎn)vi鄰居節(jié)點(diǎn)的標(biāo)簽歸屬情況,并選出最大者：

當(dāng)|maxk|=1 時(shí),lbi=lbmaxk.當(dāng)|maxk|>1 時(shí),進(jìn)一步計(jì)算每個(gè)標(biāo)簽對(duì)應(yīng)節(jié)點(diǎn)的影響力(LR) 之和,選擇節(jié)點(diǎn)LR值之和最大的標(biāo)簽作為目標(biāo)標(biāo)簽.式(7)計(jì)算標(biāo)簽對(duì)應(yīng)的節(jié)點(diǎn)影響力之和,并選擇LR值之和最大者l作為節(jié)點(diǎn)vi的標(biāo)簽：

其中,Γik表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)中標(biāo)簽為k的節(jié)點(diǎn)集合.因?yàn)榇颂幱懻摰墓?jié)點(diǎn)vj是vi的鄰居節(jié)點(diǎn),所以δij=1.

2.4 社區(qū)優(yōu)化合并

將向量表示的數(shù)據(jù)集進(jìn)行網(wǎng)絡(luò)化,一般情況下要求構(gòu)建的網(wǎng)絡(luò)在確保全連通的前提下盡量稀疏,網(wǎng)絡(luò)中節(jié)點(diǎn)度通常不滿足冪律分布.用社區(qū)發(fā)現(xiàn)算法進(jìn)行節(jié)點(diǎn)聚類(lèi),在未指定社區(qū)數(shù)量的情況下,得到的社區(qū)數(shù)通常會(huì)大于真實(shí)的簇的數(shù)量,所以需要進(jìn)行優(yōu)化合并.

定義3.內(nèi)度與外度.假設(shè)C={c1,c2,···,cl}是G的一次社區(qū)劃分結(jié)果,cl稱為一個(gè)社區(qū).節(jié)點(diǎn)vi∈cl的內(nèi)度表示vi與社區(qū)cl內(nèi)部節(jié)點(diǎn)的連邊數(shù)量,記為diin(cl).外度表示vi與社區(qū)cl外部節(jié)點(diǎn)的連邊數(shù)量,記為diout(cl).

定義4.社區(qū)內(nèi)聚度.社區(qū)內(nèi)聚度定義為社區(qū)c中的節(jié)點(diǎn)的內(nèi)度之和與外度之和的比值,比值越大,表示內(nèi)聚度越高,社區(qū)質(zhì)量越好.當(dāng)比值小于設(shè)定的閾值時(shí),該社區(qū)需要與相鄰社區(qū)合并.社區(qū)內(nèi)聚度表示為cohc：

定義5.社區(qū)優(yōu)化合并規(guī)則.當(dāng)cohc< γ,社區(qū)c需要與相鄰社區(qū)進(jìn)行合并,選擇c中最多外度所歸屬社區(qū)作為目標(biāo)合并社區(qū),如式(9)：

當(dāng)|t|=1 時(shí),lbi∈c=t；當(dāng)|t|>1 時(shí),lbi∈c=rand(t).

2.5 算法偽代碼

根據(jù)以上定義,本文算法分為4 個(gè)步驟：首先對(duì)數(shù)據(jù)集進(jìn)行網(wǎng)絡(luò)化；之后,利用節(jié)點(diǎn)相似度對(duì)節(jié)點(diǎn)標(biāo)簽進(jìn)行預(yù)處理,以提高后續(xù)標(biāo)簽傳播的穩(wěn)定性；在標(biāo)簽傳播階段,用節(jié)點(diǎn)影響力輔助標(biāo)簽選擇,進(jìn)一步降低標(biāo)簽傳播的隨機(jī)性；最后,通過(guò)對(duì)社區(qū)的內(nèi)聚度進(jìn)行判斷,對(duì)內(nèi)聚度較小的社區(qū)進(jìn)行合并優(yōu)化,以提高社區(qū)的質(zhì)量.

算法1.CreatGraph輸入：X,y,maxk,eps輸出：G 1 X=MinMaxScaler(X)2 dist=kNN(X,maxk)3 Foreach xi∈X do 4 NBi={xj|dist(xi,xj)

算法1 用于將數(shù)據(jù)集轉(zhuǎn)換為對(duì)應(yīng)的網(wǎng)絡(luò),其主要步驟如下：

1)首先對(duì)數(shù)據(jù)進(jìn)行最大最小值歸一化,即將各列特征值縮放到[0,1]之間,以消除列之間特征值量綱不同引起的問(wèn)題,歸一化的公式為：

2)利用kNN 算法求樣本之間的距離,并使用kd 樹(shù)進(jìn)行求解.對(duì)于高維數(shù)據(jù),用k-d 樹(shù)可將時(shí)間復(fù)雜度降低為O(NlogN)(第2 行)；

3)求與樣本xi的距離在半徑eps范圍內(nèi)的樣本點(diǎn)(第4 行)；

4)如果在半徑距離內(nèi)的樣本數(shù)大于等于k,在圖G中添加節(jié)點(diǎn)vi與NBi中所有樣本對(duì)應(yīng)的節(jié)點(diǎn)的邊；否則計(jì)算NNi,并建立vi與NNi中節(jié)點(diǎn)的連邊.其中addEdge函數(shù)用于在節(jié)點(diǎn)對(duì)之間建立邊,因?yàn)闃?gòu)建的是無(wú)向圖,兩個(gè)節(jié)點(diǎn)之間最多只建立一條邊(第5-10 行)；

5)最后返回構(gòu)建完成的網(wǎng)絡(luò)G(第12 行).

算法2.InitLabel輸入：G=(V,E),γ輸出：LB 1 LB={lbi=i|vi∈V}2 Foreach vi ∈V do k=argmax j∈Γi 3 4 if |k|==1 then 5 lbi=lbk 6 else 7 lbi=lbrand(k)8 end 9 update(LB,lbi)10 end 11 return LB CNi,j

算法2 根據(jù)相鄰節(jié)點(diǎn)間的共同鄰居數(shù)對(duì)節(jié)點(diǎn)進(jìn)行標(biāo)簽初始化,主要步驟如下：

1)初始化節(jié)點(diǎn)標(biāo)簽為其對(duì)應(yīng)的編號(hào)(第1 行)；

2)計(jì)算節(jié)點(diǎn)vi與鄰居節(jié)點(diǎn)的共同鄰居數(shù),k中保留與vi具有最多共同鄰居數(shù)的節(jié)點(diǎn)標(biāo)簽(第3 行)；

3)根據(jù)定義1 對(duì)標(biāo)簽進(jìn)行預(yù)處理(第4-8 行)；

4)用新的標(biāo)簽更新標(biāo)簽集合LB,此處采用異步更新(第9 行).

算法3.InfluLPA輸入：G,LB輸出：C 1 LR=LeaderRank(G)2 finished=false 3 LBO=LB 4 While not finished do 5 LBN=Φ 6 Foreach vi ∈V do maxk=argmax k∑7 8 if |maxk|=1 then 9 lbi=lbmaxk 10 else l=argmax k∈maxk j∈Γki δij 11 12 lbi=lbl 13 end∑j∈Γki LR j 14 LBN=LBN lbi 15 end 16 if LBN==LBO then 17 finished=true∪

18 else 19 LBO=LBN 20 end 21 end 22 C=part(LBO)23 return C

算法3 的主要步驟如下：

1)用LeaderRank 算法計(jì)算節(jié)點(diǎn)的LR值,用于后續(xù)的標(biāo)簽選擇(第1 行)；

2)根據(jù)定義2 進(jìn)行一趟標(biāo)簽傳播(第6-15 行)；

3)一趟標(biāo)簽傳播后,如果所有標(biāo)簽未發(fā)生變化,迭代結(jié)束；否則進(jìn)行下一趟的標(biāo)簽傳播(第16-20 行)；

4)part函數(shù)根據(jù)節(jié)點(diǎn)的標(biāo)簽將節(jié)點(diǎn)劃分為不同的社區(qū)(第22 行).

算法4.CombComm輸入：C,輸出：C’γ 1 C’=C 2 Foreach c ∈ C do∑3 cohc=i∈cdin i(c)∑i∈cdout i(c)4 if cohc< then t=argmax l γ∑i∈c|dout i ∈cl|,c≠cl 5 6 if |t|==1 then 7 lbi∈c=t 8 else 9 lbi∈c=rand(t)10 end∪11 ct=ct c 12 C'=updata(C',c,ct)13 end 14 end 15 return C'

算法4 根據(jù)社區(qū)內(nèi)聚度進(jìn)行社區(qū)優(yōu)化合并,其主要步驟如下：

1)復(fù)制原始社區(qū)C到C'(第1 行)；

2)根據(jù)定義4 計(jì)算當(dāng)前社區(qū)的內(nèi)聚度(第3 行)；

3)當(dāng)內(nèi)聚度小于閾值 γ,根據(jù)定義5 計(jì)算合并的目標(biāo)社區(qū)t,將c中節(jié)點(diǎn)的標(biāo)簽更改為t(第5-10 行)；

4)對(duì)C'中的社區(qū)進(jìn)行更新,刪除社區(qū)c,用更新后的社區(qū)ct更新C'(第11-12 行).

2.6 時(shí)間復(fù)雜度分析

算法1 中進(jìn)行數(shù)據(jù)歸一化的時(shí)間復(fù)雜度為O(N)；利用基于k-d 樹(shù)的kNN 算法求N個(gè)節(jié)點(diǎn)的最近鄰節(jié)點(diǎn)和距離的時(shí)間復(fù)雜度為O(NlogN)；第3-11 行構(gòu)建圖的時(shí)間復(fù)雜度為O(N).算法1 的總體時(shí)間復(fù)雜度為O(NlogN).

算法2 中初始化節(jié)點(diǎn)標(biāo)簽的時(shí)間復(fù)雜度為O(N)；設(shè)節(jié)點(diǎn)的平均度為k,計(jì)算無(wú)向圖中相鄰節(jié)點(diǎn)的共同鄰居數(shù)的時(shí)間復(fù)雜度為O(k),每個(gè)節(jié)點(diǎn)需要與k/2 個(gè)鄰居節(jié)點(diǎn)求交集,則求N個(gè)節(jié)點(diǎn)與鄰居節(jié)點(diǎn)相似度的時(shí)間復(fù)雜度為O(Nk2/2).之后,當(dāng)前節(jié)點(diǎn)從鄰居節(jié)點(diǎn)中選擇一個(gè)標(biāo)簽的時(shí)間為O(k),為N個(gè)節(jié)點(diǎn)選擇標(biāo)簽的時(shí)間復(fù)雜度為O(kN).算法2 的總體時(shí)間復(fù)雜度為O(Nk2/2+Nk+k),又因?yàn)閗=2M/N,則總時(shí)間復(fù)雜度可簡(jiǎn)單表達(dá)為O(kM).

算法3 中,計(jì)算節(jié)點(diǎn)的LR值的時(shí)間復(fù)雜度為O(M+N),第2-21 行的主體是LPA 算法,其時(shí)間復(fù)雜度為O(TM+N),T為迭代次數(shù).第11 行需要計(jì)算節(jié)點(diǎn)的LR值之和,最壞情況下,一次計(jì)算的時(shí)間復(fù)雜度為O(k),一般需要執(zhí)行該計(jì)算的次數(shù)小于0.1×N,本文研究中的k值一般小于10,即最壞情況下該步驟的時(shí)間復(fù)雜度為O(N)；最后,將節(jié)點(diǎn)劃分到社區(qū)所需的計(jì)算量為O(N).所以,算法3 總的時(shí)間復(fù)雜度為O(TM+N).

算法4 中,計(jì)算一個(gè)節(jié)點(diǎn)的內(nèi)度和外度所需時(shí)間為O(k),計(jì)算所有社區(qū)的內(nèi)聚度需要計(jì)算所有節(jié)點(diǎn)的內(nèi)度和外度,其時(shí)間復(fù)雜度為O(kN)；對(duì)于不滿足內(nèi)聚度的社區(qū),需要查詢節(jié)點(diǎn)外度的歸屬社區(qū),所需查詢的節(jié)點(diǎn)數(shù)小于N,則該步驟所需的計(jì)算機(jī)小于O(kN)；第12 行更新社區(qū)的計(jì)算量為O(N).算法4 的總體時(shí)間復(fù)雜度為O(kN),即O(M).

綜上,以上4 個(gè)步驟的總體時(shí)間復(fù)雜度為O(NlogN+kM+TM+N+M),實(shí)驗(yàn)結(jié)果表明,迭代次數(shù)T一般小于10,節(jié)點(diǎn)度k也一般小于10,則時(shí)間復(fù)雜度可簡(jiǎn)化為O(M+NlogN).

3 實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證算法的有效性,本文選取Sklearn 工具包中的K-means,DBSCAN 和Spectral Clustering (SC) 3 個(gè)算法作為對(duì)比算法,各算法在不同數(shù)據(jù)集上的參數(shù)設(shè)定以取得最大NMI值為準(zhǔn)則進(jìn)行設(shè)置.實(shí)驗(yàn)數(shù)據(jù)為15 次運(yùn)行結(jié)果的平均值。

實(shí)驗(yàn)環(huán)境：Intel(R) Core(TM) i7-8650U CPU,16 GB內(nèi)存,Windows 10 操作系統(tǒng),算法采用Python 3.7 實(shí)現(xiàn).

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文用Sklearn 工具包中的make_blobs 函數(shù)生成4 個(gè)人工數(shù)據(jù)集,用make_circles 函數(shù)生成一個(gè)數(shù)據(jù)集,并選擇UCI 上的Iris,Wine,Letter-recognition(LR),WDBC 和Glass 等5 個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).真實(shí)數(shù)據(jù)集的樣本數(shù)量、特征數(shù)和簇?cái)?shù)如表1所示,make_blobs的參數(shù)值設(shè)定如表2所示,make_circles 的參數(shù)設(shè)定為n_samples=160,noise=0.1,factor=0.5.為方便后續(xù)描述,將make_circles 生成的數(shù)據(jù)集命名為N5.

表2 make_blobs 參數(shù)值

3.2 評(píng)價(jià)指標(biāo)

對(duì)于已知樣本標(biāo)簽的數(shù)據(jù)集,可采用標(biāo)準(zhǔn)化互信息(NMI)和調(diào)整蘭德系數(shù)(ARI)兩個(gè)指標(biāo)對(duì)聚類(lèi)算法準(zhǔn)確性進(jìn)行評(píng)價(jià).

NMI定義為：

其中,A是樣本真實(shí)標(biāo)簽,B是算法聚類(lèi)后的樣本標(biāo)簽,N是樣本數(shù).CA是真實(shí)簇?cái)?shù)量,CB是經(jīng)算法聚類(lèi)的簇?cái)?shù)量.M是混淆矩陣,Mi·是矩陣M中第i行元素之和,表示A中第i個(gè)簇的樣本數(shù).相應(yīng)的,M·j表示B中第j個(gè)簇的樣本數(shù),即矩陣M中第j列元素之和.Mij表示A中第i個(gè)簇的樣本屬于B中第j個(gè)簇的樣本數(shù).NMI的值域?yàn)閇0,1],值越大則表示算法的聚類(lèi)效果越好,當(dāng)NMI(A,B)=1 時(shí),表示A和B的結(jié)構(gòu)完全相同.

ARI定義為：

其中,n是混淆矩陣,nij表示混淆矩陣中第i行第j列元素,ni·是混淆矩陣中第i行元素之和,n·j是混淆矩陣中第j列元素之和,表示從n個(gè)節(jié)點(diǎn)中取2 個(gè)節(jié)點(diǎn)的組合數(shù).ARI的取值范圍為[-1,1],值越大,說(shuō)明社區(qū)劃分結(jié)果與真實(shí)社區(qū)越吻合.

3.3 聚類(lèi)精度實(shí)驗(yàn)

在Iris 等5 個(gè)真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果如圖2所示,圖2(a)是算法得到的NMI值,圖2(b)是算法得到的ARI值.對(duì)于NMI指標(biāo),本文算法在Iris,WDBC,Glass和LR 等4 個(gè)數(shù)據(jù)集上獲得最優(yōu)值.在Wine 數(shù)據(jù)集上,Spectral Clustering 算法取得最優(yōu)值,本文算法得到的結(jié)果優(yōu)于K-means 和DBSCAN.在ARI指標(biāo)上得到的實(shí)驗(yàn)結(jié)果與在NMI上得到的結(jié)果類(lèi)似.

圖2 不同算法在真實(shí)網(wǎng)絡(luò)上的精度實(shí)驗(yàn)

在人工數(shù)據(jù)集上,本文算法也取得了較好的結(jié)果.圖3(a)中,在N1 數(shù)據(jù)集上,本文算法和Spectral Clustering 都能夠完全正確的對(duì)數(shù)據(jù)進(jìn)行劃分,得到的NMI和ARI值都是1.在N2 數(shù)據(jù)集上,本文算法得到的結(jié)果與K-means 和Spectral 較為接近.在N3 和N4數(shù)據(jù)集上,本文算法得到的結(jié)果明顯優(yōu)于對(duì)比算法.圖3(b)中的ARI實(shí)驗(yàn)結(jié)果與NMI的結(jié)果類(lèi)似.

圖3 不同算法在人工網(wǎng)絡(luò)上的精度實(shí)驗(yàn)

在前4 個(gè)數(shù)據(jù)集中,都存在標(biāo)準(zhǔn)差為3 的簇,使得數(shù)據(jù)集中存在較多的噪音點(diǎn),DBSCAN 算法依賴于于樣本密度,對(duì)噪音點(diǎn)的識(shí)別能力較弱,所以在4 個(gè)數(shù)據(jù)集上的準(zhǔn)確性都比較差.本文算法在網(wǎng)絡(luò)構(gòu)建過(guò)程同時(shí)考慮了密度和k個(gè)最近鄰樣本,保證了距離簇中心較遠(yuǎn)的樣本也能與該簇中節(jié)點(diǎn)保持較多的連邊,有利于后續(xù)的社區(qū)發(fā)現(xiàn).N5 數(shù)據(jù)集是兩個(gè)同心圓,兩個(gè)圓之間有部分節(jié)點(diǎn)重疊,Spectral Clustering 算法無(wú)法區(qū)分簇之間的界限,劃分出的結(jié)果與真實(shí)情況差別較大,K-means 算法對(duì)這種特殊類(lèi)型的圖形無(wú)法識(shí)別,得到的NMI和ARI都為0,而LRLPA 和DBSCAN 基于密度,能夠在密度較小的區(qū)間進(jìn)行劃分,所以兩者得到的結(jié)果比較接近.

3.4 算法穩(wěn)定性實(shí)驗(yàn)

LRLPA 和LPA 兩種算法在人工數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如圖4所示.無(wú)論是在NMI還是ARI指標(biāo)上,本文提出的LRLPA 都比原始LPA 具有更高的精確度,且具有更小范圍的誤差.對(duì)數(shù)據(jù)集X進(jìn)行網(wǎng)絡(luò)化后,一般會(huì)比較稀疏,LPA 識(shí)別出的社區(qū)數(shù)較多,使得準(zhǔn)確度指標(biāo)不高.而LRLPA 最后一步根據(jù)內(nèi)聚度進(jìn)行優(yōu)化合并,使得社區(qū)數(shù)與真實(shí)簇?cái)?shù)相同或接近,提高了算法的精確度.同時(shí),標(biāo)簽預(yù)處理與融入節(jié)點(diǎn)影響力的標(biāo)簽傳播對(duì)降低算法隨機(jī)性有較為明顯的效果,在4 個(gè)數(shù)據(jù)集上的波動(dòng)范圍都小于2%.

圖4 LRLPA 和LPA 的精度即穩(wěn)定性實(shí)驗(yàn)

4 結(jié)論與展望

本文提出了一種基于網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的低隨機(jī)性標(biāo)簽傳播聚類(lèi)算法LRLPA.在5 個(gè)真實(shí)數(shù)據(jù)集和5 個(gè)人工數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn),與其他算法相比,LRLPA 算法在大部分?jǐn)?shù)據(jù)集上都具有最大的NMI和ARI值.與LPA的對(duì)比中,本文算法的準(zhǔn)確率和穩(wěn)定性都高于LPA.

下一步研究中,一個(gè)改進(jìn)的方向是通過(guò)動(dòng)態(tài)網(wǎng)絡(luò)構(gòu)建,將LRLPA 算法應(yīng)用于增量式聚類(lèi).另一個(gè)值得注意的方向是改進(jìn)標(biāo)簽傳播方式,將標(biāo)簽選擇過(guò)程并行化,提高算法效率,以適應(yīng)大規(guī)模數(shù)據(jù)集的應(yīng)用.