半監(jiān)督元路徑的異構(gòu)信息網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

陳麗敏，張 巖，楊 柳

(牡丹江師范學(xué)院計算機(jī)與信息技術(shù)學(xué)院，黑龍江牡丹江157011)

1 引 言

異構(gòu)信息網(wǎng)絡(luò)非常普遍，如社會信息網(wǎng)絡(luò)、書目網(wǎng)絡(luò)、醫(yī)療信息網(wǎng)絡(luò)等.異構(gòu)信息網(wǎng)絡(luò)能夠真實(shí)地反映現(xiàn)實(shí)世界，分析異構(gòu)信息網(wǎng)絡(luò)能夠更好地理解網(wǎng)絡(luò)的隱藏結(jié)構(gòu)以及每個社區(qū)數(shù)據(jù)所代表的角色［1，2］.

異構(gòu)信息網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法是研究異構(gòu)信息網(wǎng)絡(luò)的基礎(chǔ)，基于語義相似性度量的異構(gòu)信息網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法是主流［3，4］，其中，語義相似性度量大多數(shù)是基于元路徑計算的，比較典型的基于元路徑的相似性度量有PathCount 和PathSim［5］及 JoinSim［6］.但是，基于元路徑的目標(biāo)對象的相似性度量，其語義表達(dá)并不完整，不能真實(shí)地反映目標(biāo)對象的關(guān)聯(lián)，而目前又缺乏更加準(zhǔn)確地表達(dá)目標(biāo)對象相似性語義的方法.受其影響，異構(gòu)信息網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的準(zhǔn)確度不高.基于語義的異構(gòu)信息網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法往往忽略了異構(gòu)信息網(wǎng)絡(luò)復(fù)雜的拓?fù)浣Y(jié)構(gòu)，從拓?fù)浣Y(jié)構(gòu)的角度分析異構(gòu)信息網(wǎng)絡(luò)［7，8］，能夠掌握數(shù)據(jù)分布的整體結(jié)構(gòu).半監(jiān)督方法能夠提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確率［9，10］.本文將二者有機(jī)結(jié)合，通過譜聚類分析異構(gòu)信息網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，半監(jiān)督校正目標(biāo)對象的相似性，能夠有效提高異構(gòu)信息網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的準(zhǔn)確率.

因?yàn)樽V聚類能夠捕獲數(shù)據(jù)分布的整體結(jié)構(gòu)，而且非負(fù)矩陣分解NMF 方法和譜聚類方法都有可靠的理論支撐，所以本文使用這兩種方法來分析異構(gòu)信息網(wǎng)絡(luò)的社區(qū)，提出半監(jiān)督算法(Semi-Supervised Meta-Path-based Algorithm for Community Detection in Heterogeneous Information Networks SMpC).SMpC 算法由兩部分組成.首先，使用譜聚類算法SRC［8］獲得目標(biāo)數(shù)據(jù)集的整體分布情況，并選取每個類中的代表對象，構(gòu)建先驗(yàn)信息.然后，基于元路徑計算目標(biāo)對象的相似度，使用先驗(yàn)信息校正目標(biāo)對象的相似度，并采用NMF 方法劃分目標(biāo)對象，發(fā)現(xiàn)合理社區(qū).

2 基于元路徑的相似性度量

PathCount 為兩個目標(biāo)對象的加權(quán)路徑總數(shù)，該方法偏向于高度可見對象.為了捕捉到對等對象的相似性語義，Path-Sim 使用兩個目標(biāo)對象的循環(huán)路徑數(shù)的算數(shù)平均調(diào)整加權(quán)路徑總數(shù)，JoinSim 使用兩個目標(biāo)對象的循環(huán)路徑數(shù)的幾何平均調(diào)整加權(quán)路徑總數(shù).

3 基于拓?fù)浣Y(jié)構(gòu)的異構(gòu)信息網(wǎng)絡(luò)劃分

從拓?fù)浣Y(jié)構(gòu)角度，基于相容二部圖的思想能夠有效分析多種異構(gòu)數(shù)據(jù)之間的復(fù)雜關(guān)系，其中，譜聚類算法SRC 從相容的角度解決了多種異構(gòu)數(shù)據(jù)協(xié)同聚類的問題.SRC 方法給出了一個通用模型，能夠處理任何結(jié)構(gòu)的異構(gòu)信息網(wǎng)絡(luò).該方法能夠?qū)Ω鞣N數(shù)據(jù)對象同時聚類，把各種類型數(shù)據(jù)對象映射到低維空間，因此，各種類型數(shù)據(jù)對象隱藏的結(jié)構(gòu)很容易被發(fā)現(xiàn).

其中，‖·‖表示矩陣的 Frobenius 范數(shù)，C(p)∈{0，1}np×Kp，當(dāng) L 最小時，則 C 為最佳指示矩陣.通常令指示矩陣C(p)滿足

當(dāng)異構(gòu)信息網(wǎng)絡(luò)結(jié)構(gòu)比較復(fù)雜，不同類型的數(shù)據(jù)集之間的關(guān)系矩陣W(pq)的數(shù)量將非常多，這將導(dǎo)致SRC 算法的計算量過大.因此，本文選擇星型模式的網(wǎng)絡(luò)結(jié)構(gòu)［7，10］來分析目標(biāo)對象的整體分布.星型模式的網(wǎng)絡(luò)結(jié)構(gòu)是指目標(biāo)數(shù)據(jù)集與屬性數(shù)據(jù)集存在關(guān)系，而屬性數(shù)據(jù)集之間不存在關(guān)系.即只分析關(guān)系矩陣{W(1q)∈Rn1×nq}1≤q≤T，則(1)式可表示為:

其中，β1q是關(guān)系矩陣 W(1q)的權(quán)重，∑β1q=1，β1q＞0.整理(2)式，L 可表示為:

其中，tr 是矩陣的跡.L 最小，則aL/aA(1q)=0.那么，A(1q)=(C(1))'W(1q)C(q)，代入(3)式，因?yàn)?C(q))'C(q)=I，tr(W(1q)(W(1q))')是常量，所以，當(dāng) min(C(q))'C(q)=IL，即

求解(4)式最大值是NP 難問題.通過迭代方法能夠計算(4)式的極大值.首先給定T-1 個指示矩陣C(i)，使得

其中

從而，確定最優(yōu)指示矩陣 C(q)，1≤q≤T，q≠i.

4 半監(jiān)督異構(gòu)信息網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

4.1 先驗(yàn)信息的確定

確定先驗(yàn)信息就是在目標(biāo)數(shù)據(jù)集中選取代表對象，并構(gòu)造先驗(yàn)信息矩陣.因?yàn)闊o法直接計算異構(gòu)信息網(wǎng)絡(luò)目標(biāo)對象之間的距離，所以，將目標(biāo)對象映射到低維空間，計算各指示對象之間的距離.根據(jù)指示對象間的距離，則可以基于密度方式篩選代表對象.

設(shè)目標(biāo)數(shù)據(jù)集X1共劃分 K1個類，給定閾值 δ.首先，使用算法1 將X1映射成指示數(shù)據(jù)集C(1)，并將C(1)劃分為K1個類;在C(1)的第k 個類Ck(1)中隨機(jī)選取一個種子cu(k)，1≤k≤K1，指示對象 cu(k)對應(yīng)的目標(biāo)對象xu(1)作為代表對象.

令 Z∈Rn1×n1是 X1的先驗(yàn)信息矩陣，給定 zuv∈Z，如果目標(biāo)對象xu(1)與xv(1)屬于同一個類的代表對象，則zuv=1，否則zuv=0.

每個類中選擇距離大于δ 的指示數(shù)據(jù)對應(yīng)的目標(biāo)對象作為代表對象，這些代表對象能夠把拓?fù)浣Y(jié)構(gòu)上相關(guān)聯(lián)而語義上關(guān)系較弱的數(shù)據(jù)連接起來，從而能夠校正基于元路徑的語義相似度的傾斜或不完整.

4.2 SMpC 算法

使用先驗(yàn)信息校正目標(biāo)對象基于元路徑計算的相似度，以改進(jìn)目標(biāo)對象語義相似性的缺失或不完整.首先，基于元路徑計算目標(biāo)對象的相似矩陣H，正則化相似性矩陣H 和先驗(yàn)信息矩陣Z.然后，使用先驗(yàn)信息矩陣Z 校正相似矩陣H，校驗(yàn)矩陣為aH+bZ，其中，a+b=1.校驗(yàn)矩陣能夠更合理地表達(dá)目標(biāo)對象的關(guān)系，在其上使用NMF 方法能夠得到更加合理的社區(qū).具體算法如下:

SMpC 算法既考慮到目標(biāo)對象在拓?fù)浣Y(jié)構(gòu)上的相關(guān)性，又考慮到目標(biāo)對象在語義上的相關(guān)性，因此，目標(biāo)對象的相似性度量更合理，從而使得劃分的社區(qū)更合理.而SMpC 算法的兩部分采用的SRC 算法和NMF 算法都具有可靠的推理，所以使用這兩種算法劃分的社區(qū)準(zhǔn)確率相對更高.另外，SMpC算法半監(jiān)督過程不需要人為干預(yù).SMpC 算法中第1 步將目標(biāo)數(shù)據(jù)集X1映射成指示數(shù)據(jù)集C(1)，涉及到特征向量的計算，采用近似計算矩陣特征向量方法，能夠?qū)⑺惴◤?fù)雜度從O(n3)降到近似 (n2).第2 步-第12 步確定指示數(shù)據(jù)集每個類的種子，也即目標(biāo)數(shù)據(jù)集的代表對象，計算復(fù)雜度為O(n2).第13 步-第18 步計算校驗(yàn)矩陣aH+bZ，計算復(fù)雜度為O(n2).第19 步 NMF 分解計算復(fù)雜度為 O(n2).所以，SMpC算法的計算復(fù)雜度近似 (n2).

5 實(shí) 驗(yàn)

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

從DBLP 選取真實(shí)數(shù)據(jù)建立實(shí)驗(yàn)數(shù)據(jù)集，DBLP 是一個典型的異構(gòu)信息網(wǎng)絡(luò)，其中包括4 種類型數(shù)據(jù)對象，分別命名為 papers，authors，terms 和 venues.抽取一個小數(shù)據(jù)集 Ss，即文獻(xiàn)［11］使用的稱為“four-area dataset"的數(shù)據(jù)集.小數(shù)據(jù)集Ss選取了4 個學(xué)術(shù)區(qū)域，這4 個區(qū)域?yàn)?database，data mining，information retrieval 及 machine learning.每個區(qū)域取 5 個有代表性的會議，共20 個會議，20 個會議的所有authors，papers 及出現(xiàn)在論文題目中的所有terms.

本文又抽取了由中國自動化研究所提供的中國DBLP 數(shù)據(jù)集作為另外一個測試數(shù)據(jù)集，這個大的數(shù)據(jù)集稱為Sl.該數(shù)據(jù)集包括34 個計算機(jī)科學(xué)期刊，2，671 個 papers，4，576 個 authors 及 4，962 個 terms.

5.2 參數(shù) b 分析

圖1 以papers 為目標(biāo)對象的參數(shù)b 分析Fig.1 Parameter analysis for papers in Ss

本實(shí)驗(yàn)分別選用 PathCount、PathSim 和 JoinSim 計算目標(biāo)對象的語義相似性，構(gòu)造相似矩陣H.a 是相似矩陣H 的系數(shù)，b 是先驗(yàn)信息矩陣 Z 的系數(shù)，且 a+b=1，0≤b≤1.b 分別取 0，0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1.0，則相應(yīng)的參數(shù) a 分別為 1.0，0.9，0.8，0.7，0.6，0.5，0.4，0.3，0.2，0.1，0.使用小數(shù)據(jù)集Ss分析參數(shù)b 對實(shí)驗(yàn)結(jié)果的影響.參數(shù)b 對目標(biāo)對象papers 劃分結(jié)果的影響如圖1 所示，參數(shù)b 對目標(biāo)對象authors 劃分結(jié)果的影響如圖2 所示.從圖1 和圖2 可以看出，b 取值過小或過大，社區(qū)發(fā)現(xiàn)的準(zhǔn)確率都不高，當(dāng)0.4≤b≤0.6 社區(qū)發(fā)現(xiàn)的準(zhǔn)確率較高.圖1 和圖2 也說明了參數(shù)b的魯棒性較好.以下實(shí)驗(yàn)參數(shù)b 均取值b=0.5.

圖2 以authors 為目標(biāo)對象的參數(shù)b 分析Fig.2 Parameter analysis for authors in Ss

5.3 先驗(yàn)信息比率分析

參數(shù)δ 的選取，直接決定代表對象的數(shù)目，也即一個類中先驗(yàn)信息的百分比.使用小數(shù)據(jù)集Ss分析先驗(yàn)信息的比率對目標(biāo)對象papers 劃分結(jié)果的影響，取5 個不同的δ，獲得papers 先驗(yàn)信息的比率分別為 10.7%、22.1%、39.4%、53.4%、60.8%.取 b=0.5，結(jié)果如圖3 所示.

圖3 先驗(yàn)信息比率分析Fig.3 Prior information analysis

先驗(yàn)信息率的選取與異構(gòu)信息網(wǎng)絡(luò)的結(jié)構(gòu)關(guān)系緊密.如果代表對象能夠比較好的刻畫出所在類的整體結(jié)構(gòu)，就能夠很好地提高準(zhǔn)確率，如果代表對象過多，則會降低語義的作用，也會降低準(zhǔn)確率.因此，代表對象的比率20%-50%之間即可.

5.4 準(zhǔn)確率對比

本次實(shí)驗(yàn)分別對數(shù)據(jù)集Ss和Sl的authors 和papers 作為目標(biāo)對象進(jìn)行分析.首先使用PathCount 計算目標(biāo)對象相似性，使用NMF 方法對目標(biāo)對象劃分，社區(qū)發(fā)現(xiàn)的準(zhǔn)確率如表1 中的第2 列所示;然后使用本文算法SMpC 對目標(biāo)對象相似性進(jìn)行校驗(yàn)，其相應(yīng)的社區(qū)發(fā)現(xiàn)準(zhǔn)確率如表1中的第3列所示.以此類推，分別使用PathSim 和JoinSim 計算目標(biāo)對象相似性，使用NMF 方法對目標(biāo)對象劃分，社區(qū)發(fā)現(xiàn)的準(zhǔn)確率如表1 中的第4 列和第6 列所示;然后使用本文算法SMpC，其相應(yīng)的社區(qū)發(fā)現(xiàn)準(zhǔn)確率如表1 中的第5 列和第7 列所示.表1 的實(shí)驗(yàn)結(jié)果說明本文算法SMpC 社區(qū)發(fā)現(xiàn)的準(zhǔn)確率有明顯提高.說明本文算法能夠有效提高異構(gòu)信息網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的準(zhǔn)確率.

表1 社區(qū)準(zhǔn)確率比較(%)Table 1 Comparision of community Accuracy(%)

6 結(jié) 論

由于使用了先驗(yàn)信息關(guān)聯(lián)矩陣，有效校正了基于元路徑的語義相似性缺失或不健全造成的異構(gòu)網(wǎng)絡(luò)劃分的偏頗或傾斜.因此，本文SMpC 算法能夠有效提高異構(gòu)信息網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的準(zhǔn)確率.而且本文的半監(jiān)督算法不需要人為干預(yù)調(diào)控，提高了算法的自適應(yīng)性.但是，由于需要分析異構(gòu)信息網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，增加了算法的計算復(fù)雜度，處理大數(shù)據(jù)的能力不足，下一步在保證社區(qū)發(fā)現(xiàn)準(zhǔn)確率的前提下，研究降低算法復(fù)雜度.