基于網絡社區發現的標簽傳播聚類算法①

吳清壽,郭 磊,余文森

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

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

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

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

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

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

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

圖1 Iris 數據集部分樣本的拓撲圖

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

對向量表示的數據進行網絡化后,一種有效的聚類方法是進行社區發現[10].通常意義上,社區內部的節點之間連邊稠密,而社區之間的連邊稀疏.

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

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

1 相關工作

1.1 社區發現算法

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

1.2 LPA 算法

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

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

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

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

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

1.3 LeaderRank 算法

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

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

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

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

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

2 算法定義與實現

2.1 網絡構建

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

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

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

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

2.2 標簽預處理

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

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

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

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

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

2.3 融合節點影響力的標簽傳播

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

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

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

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

2.4 社區優化合并

將向量表示的數據集進行網絡化,一般情況下要求構建的網絡在確保全連通的前提下盡量稀疏,網絡中節點度通常不滿足冪律分布.用社區發現算法進行節點聚類,在未指定社區數量的情況下,得到的社區數通常會大于真實的簇的數量,所以需要進行優化合并.

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

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

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

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

2.5 算法偽代碼

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

算法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 用于將數據集轉換為對應的網絡,其主要步驟如下：

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

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

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

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

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

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

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

3)根據定義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 算法計算節點的LR值,用于后續的標簽選擇(第1 行)；

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

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

4)part函數根據節點的標簽將節點劃分為不同的社區(第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 根據社區內聚度進行社區優化合并,其主要步驟如下：

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

2)根據定義4 計算當前社區的內聚度(第3 行)；

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

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

2.6 時間復雜度分析

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

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

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

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

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

3 實驗及結果分析

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

實驗環境：Intel(R) Core(TM) i7-8650U CPU,16 GB內存,Windows 10 操作系統,算法采用Python 3.7 實現.

3.1 實驗數據集

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

表2 make_blobs 參數值

3.2 評價指標

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

NMI定義為：

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

ARI定義為：

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

3.3 聚類精度實驗

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

圖2 不同算法在真實網絡上的精度實驗

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

圖3 不同算法在人工網絡上的精度實驗

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

3.4 算法穩定性實驗

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

圖4 LRLPA 和LPA 的精度即穩定性實驗

4 結論與展望

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

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