趙宇紅，薛維佳

(內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014010)

0 引 言

相似性度量是信息網(wǎng)絡(luò)挖掘與分析的重要且基礎(chǔ)的任務(wù)[1]。異構(gòu)信息網(wǎng)絡(luò)[2]可以表達(dá)更豐富且深層次的語義，基于異構(gòu)信息網(wǎng)絡(luò)的相似性度量能夠更全面地發(fā)現(xiàn)節(jié)點(diǎn)間的關(guān)聯(lián)及網(wǎng)絡(luò)中隱藏的知識。因此，如何構(gòu)建一種準(zhǔn)確且高效的異構(gòu)信息網(wǎng)絡(luò)相似性度量算法是一個非常有意義的課題?，F(xiàn)有的異構(gòu)網(wǎng)絡(luò)相似性度量大多是基于節(jié)點(diǎn)間的鏈接關(guān)系，如PathSim[3]、AvgSim[4]、HeteSim[5]算法等。PathSim是最早提出的根據(jù)元路徑來進(jìn)行相似性度量的算法，是一種基于對稱元路徑的相似性算法，在相同類型節(jié)點(diǎn)關(guān)聯(lián)度量中具有較好的代表性。而實際的異構(gòu)網(wǎng)絡(luò)中度量不同類型對象之間的相似性也具有現(xiàn)實意義[6]。HeteSim算法通過雙向隨機(jī)游走到元路徑的中心來度量不同類型節(jié)點(diǎn)相似性，但是，算法復(fù)雜度較高，不適用于大規(guī)模的異構(gòu)網(wǎng)絡(luò)。AvgSim算法是基于單條元路徑下通過正反向兩次游走取平均的方式來度量相似性，但是算法需要預(yù)設(shè)元路徑，而不同的元路徑擁有不同的語義信息，根據(jù)不同元路徑進(jìn)行相似性度量會得到不同的度量結(jié)果，因此選用單條元路徑進(jìn)行度量在一定程度上會影響相似性度量算法的準(zhǔn)確性。鑒于現(xiàn)有異構(gòu)信息網(wǎng)絡(luò)相似性度量在度量類型及準(zhǔn)確性等方面的問題，本文在考慮元路徑對語義表達(dá)貢獻(xiàn)程度的基礎(chǔ)上，融合多條關(guān)鍵元路徑，提出了一種可度量任意類型節(jié)點(diǎn)間的相似性度量的Multi-WPathSim算法。

1 Multi-WPathSim算法

1.1 相關(guān)概念

定義1 異構(gòu)信息網(wǎng)絡(luò): 異構(gòu)信息網(wǎng)絡(luò)是包含多種節(jié)點(diǎn)與關(guān)系的信息網(wǎng)絡(luò)，可以由式(1)表示。其中在網(wǎng)絡(luò)G中，節(jié)點(diǎn)集合為V，鏈接關(guān)系為E，節(jié)點(diǎn)類型集合為T，鏈接關(guān)系所屬類型集合為R

G={V,E,T,R,φ,φ,ψ}

(1)

其中，φ、φ、ψ分別代表節(jié)點(diǎn)間關(guān)系映射、節(jié)點(diǎn)類型映射、鏈接關(guān)系類型映射，并且當(dāng)且僅當(dāng)|T|>1或者|R|>1時，網(wǎng)絡(luò)G為異構(gòu)信息網(wǎng)絡(luò)，若|T|=1和|R|=1則G為同構(gòu)。

定義2 網(wǎng)絡(luò)模式(Network Schema)[7]:網(wǎng)絡(luò)模式S類似于數(shù)據(jù)庫中的ER圖，圖中頂點(diǎn)為網(wǎng)絡(luò)G中的節(jié)點(diǎn)類型集合T，邊為鏈接關(guān)系集合R，記為S=(T,R)。圖1為幾種經(jīng)典異構(gòu)信息網(wǎng)絡(luò)中的網(wǎng)絡(luò)模式圖。

圖1 經(jīng)典異構(gòu)信息網(wǎng)絡(luò)模式實例

圖2 DBLP網(wǎng)絡(luò)模式及元路徑實例

1.2 任意類型節(jié)點(diǎn)相似性度量

PathSim算法是通過矩陣相乘的方式來計算相同類型節(jié)點(diǎn)間的相似度。相似度用s(x,y)表示，其中x,y表示同類型節(jié)點(diǎn)。其計算公式如下

(2)

P是已事先確定的元路徑，px→y代表了在當(dāng)前元路徑下，從節(jié)點(diǎn)x到y(tǒng)的所有路徑實例；px→x代表了從節(jié)點(diǎn)x到x的所有路徑實例；py→y代表了從節(jié)點(diǎn)y到y(tǒng)的所有路徑實例。這里x、y節(jié)點(diǎn)代表同種類型的節(jié)點(diǎn)，它們之間的相似性由路徑數(shù)目決定。

PathSim算法僅針對相同類型節(jié)點(diǎn)即局限于對稱元路徑，且元路徑是預(yù)設(shè)的單條路徑，異構(gòu)信息網(wǎng)絡(luò)中包含了多類型節(jié)點(diǎn)及多條元路徑，為更準(zhǔn)確地進(jìn)行相似性度量，本文在PathSim算法的基礎(chǔ)上進(jìn)行了改進(jìn)，提出了可以度量任意類型節(jié)點(diǎn)間相似性的相似性度量方法

(3)

其中，Tx=Ty代表節(jié)點(diǎn)類型相同。當(dāng)Tx≠Ty時，px→x、py→y的計算公式為

px→x=r(x)r(x)px→x∈P′

(4)

py→y=r(y)r(y)py→y∈P′

(5)

其中，元路徑P′=PP-1，以DBLP數(shù)據(jù)集為例，當(dāng)元路徑P為APC，則元路徑P′代表了APCPA。r是M的主特征向量，MP′為元路徑P′的關(guān)系矩陣。

1.3 Multi-WPathSim算法

異構(gòu)信息網(wǎng)絡(luò)中節(jié)點(diǎn)序列構(gòu)成了許多元路徑，每一條元路徑既蘊(yùn)含了不同的語義，也在語義表達(dá)中占據(jù)著不同的重要程度。任何獨(dú)立的元路徑或?qū)ΨQ元路徑集合都不能全面覆蓋異構(gòu)信息網(wǎng)絡(luò)中豐富的語義信息，為提高相似性度量的準(zhǔn)確性和計算效率，既要包括多樣化的元路徑又要考慮不同元路徑對語義表達(dá)的影響力，同時設(shè)計高效的計算模式也是非常必要的。基于上述目標(biāo)，本文提出的Multi-WPathSim算法，利用加權(quán)融合元路徑的方法來進(jìn)行相似性度量。本文的算法框架如圖3所示。

1.3.1 獲取元路徑

為更準(zhǔn)確地度量相似性，應(yīng)該確定關(guān)鍵的元路徑集合，并按照元路徑在語義表達(dá)的貢獻(xiàn)程度進(jìn)行路徑融合。

圖3 Multi-WPathSim算法框架

首先，基于相似度度量的目標(biāo)實體確定元路徑的出節(jié)點(diǎn)與入節(jié)點(diǎn)。譬如，在DBLP數(shù)據(jù)集中，如果要衡量作者與出版社之間的相似度，那么元路徑的出節(jié)點(diǎn)與入節(jié)點(diǎn)就是作者與出版社。

其次，設(shè)定元路徑的路徑長度l，隨機(jī)游走遍歷所有的元路徑，得到所有的元路徑的路徑集合。Sun等[3]通過大量實驗證實，元路徑長度相對短時就可以很好地度量相似性，并且隨著路徑長度的增大，路徑實例數(shù)也呈現(xiàn)指數(shù)級的增長。借鑒這樣的研究結(jié)論，本文將元路徑長度l設(shè)為2～5。

最后，根據(jù)元路徑遍歷得到所有的路徑實例。輸入到已構(gòu)建的CBOW(continuous bag of words)模型，其模型結(jié)構(gòu)如圖4所示。通過學(xué)習(xí)訓(xùn)練，得到中心節(jié)點(diǎn)與其它節(jié)點(diǎn)同時出現(xiàn)的概率，使用節(jié)點(diǎn)出現(xiàn)概率確定元路徑的存在概率，它表達(dá)了該路徑對語義表達(dá)的貢獻(xiàn)程度，該概率將作為路徑的權(quán)重。

圖4 CBOW模型結(jié)構(gòu)

1.3.2 基于CBOW的元路徑權(quán)重計算

CBOW模型也稱為連續(xù)詞袋模型，該模型根據(jù)中心詞的上下文來預(yù)測句子的概率[9]，即已知當(dāng)前詞wt的上下文為wt-n,wt-n+1,……,wt+n-1,wt+n，預(yù)測當(dāng)前詞wt，該模型通過詞向量間的空間相似度來衡量文本語義上的相似度，本文將詞向量空間關(guān)聯(lián)引用至節(jié)點(diǎn)序列關(guān)聯(lián)。

利用CBOW模型學(xué)習(xí)元路徑權(quán)重的具體步驟如下：

(1)獲取路徑實例，在路徑長度的約束下，循環(huán)遍歷得到所有的路徑實例。例如，在DBLP數(shù)據(jù)集中要計算元路徑為APTP下的路徑實例數(shù)，則需要對DBLP數(shù)據(jù)集鏈接關(guān)系集進(jìn)行分解，得到關(guān)于AP，PT，TP的鄰接矩陣，然后隨機(jī)以一節(jié)點(diǎn)Ai開始，根據(jù)鄰接矩陣確定下一跳節(jié)點(diǎn)，利用循環(huán)遍歷得到基于元路徑APTP的所有路徑實例；

(2)將路徑實例作為語料庫輸入到CBOW模型中，通過隱藏層將輸入層輸入的節(jié)點(diǎn)初始化向量做求和累加運(yùn)算，在輸出層得到哈夫曼樹。在哈夫曼樹中每一個非葉子節(jié)點(diǎn)代表一次二分類問題，葉子節(jié)點(diǎn)代表網(wǎng)絡(luò)中出現(xiàn)的每一個節(jié)點(diǎn)，利用每個葉子節(jié)點(diǎn)對應(yīng)的哈夫曼編碼以及二分類處理計算任意兩節(jié)點(diǎn)同時出現(xiàn)的概率。

(3)通過兩兩節(jié)點(diǎn)出現(xiàn)概率確定元路徑實例的存在概率，最終，確定當(dāng)前元路徑的存在概率。具體計算方法如式(6)-式(11)：

計算隱藏層的輸出h

(6)

其中，C代表窗口大小，xi代表第i個節(jié)點(diǎn)，W為權(quán)重矩陣。該輸出h代表對輸入層輸入的節(jié)點(diǎn)向量加權(quán)求平均。

計算在輸出層每個節(jié)點(diǎn)的輸入

(7)

計算輸出層的輸出

(8)

其中，V代表網(wǎng)絡(luò)中包含的節(jié)點(diǎn)數(shù)，c代表窗口內(nèi)的任意節(jié)點(diǎn)數(shù)，yc,j代表輸出層中節(jié)點(diǎn)j與窗口中的任意節(jié)點(diǎn)數(shù)的概率值。

計算單條路徑實例的存在概率

(9)

其中，yk代表當(dāng)前路徑實例的存在概率，l代表元路徑長度。

根據(jù)式(9)得到的結(jié)果，來計算當(dāng)前元路徑的存在概率。計算公式如下

(10)

其中，n代表路徑實例個數(shù)。Pm代表在當(dāng)前元路徑的存在概率。

在確定好所有元路徑的存在概率后，利用存在概率極限值δ來確定有效元路徑集合。通過元路徑存在概率，計算不同有效元路徑所占的權(quán)重，然后，加權(quán)融合進(jìn)行最終的相似性度量計算。其中，概率極限值δ需要通過實驗來確定。

元路徑的權(quán)重計算公式為

(11)

其中，m代表了當(dāng)前的元路徑，k代表了符合條件的元路徑的條數(shù)。

1.3.3 元路徑融合

本文采用線性融合的方式對元路徑進(jìn)行加權(quán)融合。在此基礎(chǔ)上得到最終的相似性度量算法計算方式。其具體公式為

(12)

其中，sm(x,y)是基于式(3)計算在元路徑m中的相似性度量結(jié)果。

2 實驗與分析

2.1 數(shù)據(jù)集與評價標(biāo)準(zhǔn)

本文選取的數(shù)據(jù)集為ACM數(shù)據(jù)集以及DBLP數(shù)據(jù)集。ACM數(shù)據(jù)集和DBLP數(shù)據(jù)集均為異構(gòu)信息網(wǎng)絡(luò)中的經(jīng)典數(shù)據(jù)集，其網(wǎng)絡(luò)模式圖如圖1(a)和圖1(b)所示。

DBLP數(shù)據(jù)集中選取計算機(jī)四大研究領(lǐng)域的20個會議，2277篇論文，5000個作者，13 576個關(guān)鍵字，以及與論文之間存在鏈接的會議、作者、關(guān)鍵字這3類節(jié)點(diǎn)的關(guān)系數(shù)23 757條。

ACM數(shù)據(jù)集包含14個科學(xué)會議，以及在這些會議上發(fā)表的論文1.2萬篇，1.7萬作者，1800個作者從屬機(jī)構(gòu)，73個論文主題以及1500個關(guān)鍵字。

為評價算法的有效性、準(zhǔn)確性，仿真實驗分別采用標(biāo)準(zhǔn)相似性算法衡量指標(biāo)AUC(area under the receiver ope-rating characteristic curve)[10]、Precision[10]來驗證度量的準(zhǔn)確性以及在相同聚類算法的基礎(chǔ)上，用歸一互化信息NMI[11]指標(biāo)來驗證聚類的效果。

AUC指標(biāo)從全局來衡量算法的精確度，其定義為

(13)

其中，n代表總共比較的次數(shù)，n′代表隨機(jī)從測試集中取出的邊的分?jǐn)?shù)值大于不存在的邊的分?jǐn)?shù)次數(shù)，n″代表兩分?jǐn)?shù)值相等次數(shù)[11]。

Precision值是度量排在前L個預(yù)測結(jié)果中被度量準(zhǔn)確的比例。如果有m個結(jié)果準(zhǔn)確，則Precision定義為

(14)

顯然，AUC與Precision分別從整體性及局部命中率方面，衡量了算法的準(zhǔn)確性，在相近的AUC的情況下，Precision值越大表明結(jié)果越準(zhǔn)確。

歸一化互信息NMI(normalized mutual information)值是度量聚類結(jié)果與給定標(biāo)準(zhǔn)劃分間的相似程度[11]。NMI值越高，說明所提出的相似度算法的聚類效果更有效和準(zhǔn)確。

2.2 仿真方案設(shè)計

本文中我們選擇與3種經(jīng)典的相似性度量算法來進(jìn)行對比。這3種算法分別是：PathSim算法，HeteSim算法和AvgSim算法。PathSim算法在單條元路徑上通過矩陣相乘度量相同類型節(jié)點(diǎn)相似性；HeteSim算法與AvgSim算法都是通過雙向隨機(jī)游走度量不同類型節(jié)點(diǎn)間相似性[6]。所以在對比過程中，HeteSim算法與AvgSim算法可以直接用非對稱元路徑來進(jìn)行對比，PathSim算法采用對稱元路徑來展開對比。

元路徑的概率極限值δ是指判斷元路徑存在的概率為多大時可以影響整個相似性度量算法的準(zhǔn)確度。取值過大，會導(dǎo)致有效的元路徑過少，丟失一些異構(gòu)信息網(wǎng)絡(luò)的語義信息；取值過小，可能會使得一些對相似性度量算法影響較小的元路徑存在，導(dǎo)致算法的復(fù)雜度過高，影響算法的效率。實驗所選用的路徑關(guān)系為DBLP中“撰寫關(guān)系”，路徑長度l為2-5，用AUC值進(jìn)行參數(shù)估計，圖5為不同概率極限值下的相似性度量結(jié)果準(zhǔn)確率比較。由仿真結(jié)果圖可知，算法的準(zhǔn)確率在概率極限值為0.3時達(dá)到最高，并隨著極限值的增大而減小，因此本文所選定的概率極限值δ為0.3。

圖5 不同概率極限值下的AUC值比較

2.3 結(jié)果與分析

2.3.1 元路徑的選擇與存在概率的確定

在進(jìn)行元路徑的確定時，首先需要確定計算的目標(biāo)實體，也就是元路徑的出節(jié)點(diǎn)與入節(jié)點(diǎn)。以往解決方案中，對稱路徑的考慮較多，在本文中，度量的重點(diǎn)在于非對稱元路徑，所以選擇的元路徑的出節(jié)點(diǎn)與入節(jié)點(diǎn)是不同類型的節(jié)點(diǎn)。本文選用的度量對象是作者與論文。表1為元路徑長度為2-5時，遍歷的元路徑、元路徑實例個數(shù)以及當(dāng)前元路徑的存在概率。

2.3.2 元路徑的權(quán)重確定

通過參數(shù)討論中的概率極限值比較，最終確定的概率極限值為0.3，選擇概率大于0.3的元路徑來進(jìn)行融合加權(quán)。因此，確定了最終的元路徑條數(shù)以及根據(jù)上述的權(quán)重計算式(11)得到最終的元路徑權(quán)重。表2為最終得到的元路徑集合以及相應(yīng)的權(quán)重。

2.3.3 算法準(zhǔn)確性驗證

表3給出了在ACM數(shù)據(jù)集中，元路徑為APVCVPA下，根據(jù)不同的相似性度量算法，檢索與作者Christos Faloutsos最相近的前5位作者以及他們之間的相似性度量分?jǐn)?shù)。元路徑APVCVPA表示兩個作者在同一個會議中發(fā)表論文。如表3所示，在相似性度量結(jié)果中，找出的作者集合有部分是重合的，表明本文提出的算法是有效的。而根據(jù)元路徑可知，如果作者的研究領(lǐng)域相同，那么他們發(fā)表的論文屬于同一個會議的可能性就更大，因此可知與Christos Faloutsos最相似的作者是Philip Yu、Jian Pei、Jiawei Han等。

表1 DBLP數(shù)據(jù)集中不同元路徑實例個數(shù)及其存在概率

表2 元路徑集合以及權(quán)重分配

表4是在元路徑為APVC下，根據(jù)不同的相似性度量算法，檢索與作者Christos Faloutsos最相近的前5個會議以及他們之間的相似性度量分?jǐn)?shù)。因為PathSim算法是度量對稱元路徑間的相似性，所以本部分實驗選用其它幾種相似形式度量算法進(jìn)行比較。已知Christos Faloutsos是KDD的一位非常有影響力的研究員，根據(jù)表4得出的結(jié)果，那么與Christos Faloutsos相似度較高的幾位作者所在的影響力比較大的幾家期刊也應(yīng)該與Christos Faloutsos相似度比較高。而VLDB，SIGMOD，SIGIR中Philip Yu，Jian Pei，Jiawei Han等的影響力比較高，社區(qū)排名分?jǐn)?shù)比較靠前。所以，本文的度量結(jié)果是準(zhǔn)確的。

表3 ACM數(shù)據(jù)集中對稱元路徑下與作者“Christos Faloutsos”相關(guān)Top-5

表4 ACM數(shù)據(jù)集中非對稱元路徑下與作者“Christos Faloutsos”相關(guān)的期刊Top-5

為了驗證本文的算法可適用于任意類型節(jié)點(diǎn)的相似性度量，分別在對稱元路徑與非對稱元路徑下進(jìn)行準(zhǔn)確率的仿真實驗。

表5為在對稱元路徑下，通過不同的路徑關(guān)系分別驗證算法的準(zhǔn)確率。其中，PathSim算法、HeteSim算法、AvgSim算法中作者關(guān)系的元路徑為APCPA，會議關(guān)系的元路徑為CPAPC，論文關(guān)系的元路徑為PAPCPAP。實驗結(jié)果表明：在聚類結(jié)果上，本文算法相比PathSim、Hete-Sim、AvgSim算法NMI值分別提高了10.27%、5.73%和0.56%，說明本文算法相比其它相似性度量算法在聚類任務(wù)中的表現(xiàn)更好；在全局相似度度量結(jié)果上，本文算法的AUC值相比其它算法平均提升了4.65%、3.93%和2.97%；從局部準(zhǔn)確率結(jié)果來看，本文Precision值相比其它算法分別提升了6.33%、2.33%和2%，說明本文算法的相似性度量準(zhǔn)確率更高，度量效果更好。

表5 在對稱元路徑下不同相似性度量算法的準(zhǔn)確度比較

表6為在非對稱元路徑下的相似性度量算法準(zhǔn)確率比較，因為PathSim算法只能度量同類節(jié)點(diǎn)間的相似性，因此本次實驗選用HeteSim算法、AvgSim算法與本文算法進(jìn)行比較。其中，HeteSim算法與AvgSim算法的撰寫關(guān)系的元路徑為APCPTP，發(fā)表關(guān)系的元路徑為APTPC。對比實驗結(jié)果可知，在相似性度量結(jié)果上，本文的算法相比HeteSim算法和AvgSim算法，AUC準(zhǔn)確率分別提升了3.52%和3.01%；對比Precision值，較HeteSim算法提升了2%，較AvgSim算法降低了1%，但是Precision僅從局部考慮算法準(zhǔn)確率，AUC是從整體上衡量算法的準(zhǔn)確性，因此說明本文算法在非對稱元路徑上的整體度量效果更好。

表6 在非對稱元路徑下不同相似性度量算法的準(zhǔn)確度比較

綜上所述，本文算法不僅僅局限于對稱路徑，在非對稱路徑上表現(xiàn)同樣優(yōu)秀，算法適用于任意類型節(jié)點(diǎn)的度量，普適性好，而且本文的算法準(zhǔn)確率相較其它傳統(tǒng)的相似性度量算法都有較大的提升，因此，Multi-WPathSim對異構(gòu)信息網(wǎng)絡(luò)相似性度量是可行的、有效的且準(zhǔn)確性較好。

3 結(jié)束語

異構(gòu)信息網(wǎng)絡(luò)能夠更全面地反映真實網(wǎng)絡(luò)中節(jié)點(diǎn)的類型與關(guān)聯(lián)，本文在研究了現(xiàn)有異構(gòu)信息網(wǎng)絡(luò)的相似性度量算法的基礎(chǔ)上，重點(diǎn)針對PathSim算法在計算異構(gòu)信息網(wǎng)絡(luò)節(jié)點(diǎn)間相似性時，只能在預(yù)設(shè)的元路徑中度量同種類型節(jié)點(diǎn)而不能更準(zhǔn)確地度量異構(gòu)信息網(wǎng)絡(luò)中任意節(jié)點(diǎn)的相似性問題，提出一種加權(quán)融合多條元路徑的相似性度量算法。算法充分考慮了多元路徑在異構(gòu)信息的語義表達(dá)，細(xì)化了不同元路徑對相似性度量的影響，解決了PathSim算法在元路徑及節(jié)點(diǎn)類型的局限性，擴(kuò)展了算法的普適性，提高了節(jié)點(diǎn)相似性度量的準(zhǔn)確性。實驗結(jié)果表明，本算法可以有效提高算法的準(zhǔn)確率且普適性更廣。但同時算法還有較大的提升空間，例如權(quán)重的融合方式除了線性融合，還有非線性融合方式，以及如何將該算法更好地應(yīng)用于推薦系統(tǒng)或者社區(qū)發(fā)現(xiàn)等研究領(lǐng)域。