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

吳清壽,郭 磊,余文森

1(武夷學院 數(shù)學與計算機學院,武夷山 354300)

2(武夷學院 認知計算與智能信息處理福建省高校重點實驗室,武夷山 354300)

3(智慧農(nóng)林福建省高校重點實驗室,福州 350002)

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

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

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

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

圖1 Iris 數(shù)據(jù)集部分樣本的拓撲圖

通過圖1中的拓撲結構,可以看到樣本較為清晰的劃分為3 個簇,同一簇中節(jié)點間的連邊密度較大,而簇之間的連邊較為稀疏.

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

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

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

1 相關工作

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

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

1.2 LPA 算法

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

步驟1.為各節(jié)點選擇一個唯一的標簽,通常將各節(jié)點標簽初始化為節(jié)點的編號.

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

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

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

1.3 LeaderRank 算法

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

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

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

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

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

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

2.1 網(wǎng)絡構建

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

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

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

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

2.2 標簽預處理

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

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

其中,vj∈Γi,即只計算當前節(jié)點vi和鄰居節(jié)點的相似度.

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

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

2.3 融合節(jié)點影響力的標簽傳播

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

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

當|maxk|=1 時,lbi=lbmaxk.當|maxk|>1 時,進一步計算每個標簽對應節(jié)點的影響力(LR) 之和,選擇節(jié)點LR值之和最大的標簽作為目標標簽.式(7)計算標簽對應的節(jié)點影響力之和,并選擇LR值之和最大者l作為節(jié)點vi的標簽：

其中,Γik表示節(jié)點vi的鄰居節(jié)點中標簽為k的節(jié)點集合.因為此處討論的節(jié)點vj是vi的鄰居節(jié)點,所以δij=1.

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

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

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

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

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

當|t|=1 時,lbi∈c=t；當|t|>1 時,lbi∈c=rand(t).

2.5 算法偽代碼

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

算法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ù)集轉換為對應的網(wǎng)絡,其主要步驟如下：

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

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

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

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

5)最后返回構建完成的網(wǎng)絡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é)點間的共同鄰居數(shù)對節(jié)點進行標簽初始化,主要步驟如下：

1)初始化節(jié)點標簽為其對應的編號(第1 行)；

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

3)根據(jù)定義1 對標簽進行預處理(第4-8 行)；

4)用新的標簽更新標簽集合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 算法計算節(jié)點的LR值,用于后續(xù)的標簽選擇(第1 行)；

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

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

4)part函數(shù)根據(jù)節(jié)點的標簽將節(jié)點劃分為不同的社區(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)聚度進行社區(qū)優(yōu)化合并,其主要步驟如下：

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

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

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

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

2.6 時間復雜度分析

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

算法2 中初始化節(jié)點標簽的時間復雜度為O(N)；設節(jié)點的平均度為k,計算無向圖中相鄰節(jié)點的共同鄰居數(shù)的時間復雜度為O(k),每個節(jié)點需要與k/2 個鄰居節(jié)點求交集,則求N個節(jié)點與鄰居節(jié)點相似度的時間復雜度為O(Nk2/2).之后,當前節(jié)點從鄰居節(jié)點中選擇一個標簽的時間為O(k),為N個節(jié)點選擇標簽的時間復雜度為O(kN).算法2 的總體時間復雜度為O(Nk2/2+Nk+k),又因為k=2M/N,則總時間復雜度可簡單表達為O(kM).

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

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

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

3 實驗及結果分析

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

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

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

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

表2 make_blobs 參數(shù)值

3.2 評價指標

對于已知樣本標簽的數(shù)據(jù)集,可采用標準化互信息(NMI)和調(diào)整蘭德系數(shù)(ARI)兩個指標對聚類算法準確性進行評價.

NMI定義為：

其中,A是樣本真實標簽,B是算法聚類后的樣本標簽,N是樣本數(shù).CA是真實簇數(shù)量,CB是經(jīng)算法聚類的簇數(shù)量.M是混淆矩陣,Mi·是矩陣M中第i行元素之和,表示A中第i個簇的樣本數(shù).相應的,M·j表示B中第j個簇的樣本數(shù),即矩陣M中第j列元素之和.Mij表示A中第i個簇的樣本屬于B中第j個簇的樣本數(shù).NMI的值域為[0,1],值越大則表示算法的聚類效果越好,當NMI(A,B)=1 時,表示A和B的結構完全相同.

ARI定義為：

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

3.3 聚類精度實驗

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

圖2 不同算法在真實網(wǎng)絡上的精度實驗

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

圖3 不同算法在人工網(wǎng)絡上的精度實驗

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

3.4 算法穩(wěn)定性實驗

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

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

4 結論與展望

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

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