基于用戶導(dǎo)向的異構(gòu)網(wǎng)絡(luò)語義預(yù)測(cè)算法研究

王少峰，郭俊霞，盧 罡

北京化工大學(xué) 信息學(xué)院，北京 100029

1 引言

隨著信息網(wǎng)絡(luò)的快速發(fā)展，對(duì)信息網(wǎng)絡(luò)的分析已成為一個(gè)重要的研究方向，包括信息檢索、數(shù)據(jù)挖掘、社交網(wǎng)絡(luò)、關(guān)系預(yù)測(cè)等等。信息網(wǎng)絡(luò)是一種將有向圖作為基本數(shù)據(jù)結(jié)構(gòu)的網(wǎng)絡(luò)，它對(duì)結(jié)點(diǎn)類型和關(guān)系類型進(jìn)行了明確的區(qū)分。如果它只包含一種類型的結(jié)點(diǎn)和一種類型的關(guān)系，則稱為同構(gòu)網(wǎng)絡(luò)；如果包含多種類型的結(jié)點(diǎn)和多種類型的關(guān)系，則被稱為異構(gòu)網(wǎng)絡(luò)?，F(xiàn)實(shí)的信息網(wǎng)絡(luò)往往很復(fù)雜，包含很多種類型的結(jié)點(diǎn)和關(guān)系，所以對(duì)異構(gòu)網(wǎng)絡(luò)的研究十分重要。

隨著異構(gòu)網(wǎng)絡(luò)的信息量與日俱增，用戶在搜索感興趣的信息時(shí)耗費(fèi)大量時(shí)間與精力。相似性搜索作為異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)挖掘的一種基本方法，能夠幫助用戶快速準(zhǔn)確地搜索所需要的信息。為此，有許多相似性度量方法被提出，大致可以分為以下三類：（1）基于結(jié)點(diǎn)特征的相似性度量[1-2]：網(wǎng)絡(luò)中的結(jié)點(diǎn)包含一系列特征，結(jié)點(diǎn)間的相似性可以通過特征相似性來進(jìn)行計(jì)算。這些方法適用于特征豐富的相同類型結(jié)點(diǎn)，不能用于計(jì)算不同類型結(jié)點(diǎn)間的相似性。（2）基于圖特性的相似性度量[3-4]：通過特征子圖、分類圖等圖拓?fù)涓拍钣?jì)算相似性，將結(jié)點(diǎn)間的相似性轉(zhuǎn)化為與結(jié)點(diǎn)有關(guān)的圖結(jié)構(gòu)相似性計(jì)算得到。（3）基于元路徑的相似性度量[5-7]：通過遞歸地計(jì)算結(jié)點(diǎn)鄰居間相似性，最終得到全局相似性。如文獻(xiàn)[5]基于“如果兩個(gè)結(jié)點(diǎn)和被其相似的結(jié)點(diǎn)所引用，那么這兩個(gè)結(jié)點(diǎn)也相似”的思想，提出SimRank算法。這類算法是基于結(jié)點(diǎn)結(jié)構(gòu)的上下文，從全局路徑出發(fā)計(jì)算相似性，需要計(jì)算的路徑數(shù)非常多，帶來計(jì)算量大的問題，無法擴(kuò)展到大規(guī)模數(shù)據(jù)集中。

在相似性搜索中，基于用戶導(dǎo)向去預(yù)測(cè)與用戶搜索相關(guān)的路徑，是減少路徑選擇數(shù)的重要參考依據(jù)。文獻(xiàn)[8]中對(duì)于需要聚類的目標(biāo)，用戶只需要提供小部分與目標(biāo)相關(guān)的特征集，便可根據(jù)該特征集找到相似的結(jié)點(diǎn)。文獻(xiàn)[9]通過考慮用戶對(duì)不同搜索結(jié)果的滿意程度，建立修改度量系數(shù)的目標(biāo)函數(shù)，從而實(shí)現(xiàn)微博中體現(xiàn)用戶興趣的主題時(shí)序相似性計(jì)算，為用戶提供更好的搜索結(jié)果。針對(duì)基于元路徑的相似性搜索算法普遍存在計(jì)算量大的問題，基于利用用戶導(dǎo)向預(yù)測(cè)與用戶搜索相關(guān)的路徑，以減少路徑數(shù)的考慮，本文擬進(jìn)行基于用戶導(dǎo)向的語義預(yù)測(cè)算法研究。本文的主要貢獻(xiàn)為：

（1）從圖拓?fù)浣Y(jié)構(gòu)的角度出發(fā)，提出一種基于用戶導(dǎo)向進(jìn)行語義預(yù)測(cè)的算法。該算法可用于同類型和不同類型結(jié)點(diǎn)間的語義預(yù)測(cè)，并通過語義預(yù)測(cè)減少了元路徑選擇數(shù)，緩解了計(jì)算量大的問題。并且不需要用戶具備相關(guān)專業(yè)知識(shí)，對(duì)用戶是友好的。

（2）為在多語義路徑上計(jì)算相似性提供一種實(shí)現(xiàn)方法。本文根據(jù)預(yù)測(cè)過程所得到的概率作為多語義路徑的權(quán)重，對(duì)多語義路徑上的相似性分?jǐn)?shù)進(jìn)行加權(quán)組合。

（3）本文實(shí)驗(yàn)表明，通過與實(shí)際情況進(jìn)行比較，本文算法在對(duì)稱與非對(duì)稱路徑上均能夠?qū)Y(jié)點(diǎn)間的語義進(jìn)行準(zhǔn)確預(yù)測(cè)，并且在多語義環(huán)境下的排名結(jié)果質(zhì)量明顯好于對(duì)應(yīng)算法。

2 相關(guān)研究

針對(duì)基于元路徑的相似性度量方法存在路徑選擇數(shù)多的問題，已有一些研究成果，包括針對(duì)SimRank的算法改進(jìn)[10-11]，路徑依賴隨機(jī)行走[12]法等。文獻(xiàn)[10]通過理論上界分析，將每次迭代計(jì)算后不可能進(jìn)入Top-k候選集的節(jié)點(diǎn)對(duì)鎖定，從而在精確度損失不大的情況下大幅提升計(jì)算時(shí)間。文獻(xiàn)[11]提出SimRank的線性遞歸表達(dá)式，結(jié)合蒙特卡洛模擬方法、距離的衰減特性、適應(yīng)性選樣技術(shù)使得搜索的時(shí)間復(fù)雜度獨(dú)立于圖的規(guī)模，方便進(jìn)行并行計(jì)算，使得計(jì)算大規(guī)模的圖成為可能。但這些算法只能應(yīng)用于同構(gòu)圖中，無法應(yīng)用于異構(gòu)網(wǎng)絡(luò)計(jì)算不同類型結(jié)點(diǎn)間的相似性。文獻(xiàn)[12]提出一個(gè)路徑依賴隨機(jī)游走（PCRW）算法，用于度量一個(gè)由文獻(xiàn)庫中元數(shù)據(jù)組成的有向圖中的結(jié)點(diǎn)相似性。其相似度被定義為一個(gè)已知的約束隨機(jī)行走的組合，每個(gè)約束只遵循遠(yuǎn)離搜索結(jié)點(diǎn)的邊標(biāo)簽的一個(gè)特定序列。該算法具有非對(duì)稱屬性，可用于計(jì)算不同類型結(jié)點(diǎn)間的相似性。也因?yàn)槠浞菍?duì)稱屬性，不能用于計(jì)算同類型結(jié)點(diǎn)相似性。

還有一些文獻(xiàn)提出根據(jù)用戶的專業(yè)知識(shí)來選擇與搜索相關(guān)的某一條具體的路徑，即單路徑。文獻(xiàn)[6，13]提出PathSim算法用于計(jì)算相同類型結(jié)點(diǎn)間的相似性。該算法基于單個(gè)對(duì)稱元路徑，雙向隨機(jī)游走，通過可交換矩陣，計(jì)算相同類型結(jié)點(diǎn)間的相似性。用戶需要根據(jù)自己掌握的相關(guān)領(lǐng)域知識(shí)來選擇單個(gè)路徑。該算法只能用于計(jì)算同類型結(jié)點(diǎn)，不能用于不同類型結(jié)點(diǎn)。文獻(xiàn)[7]提出HeteSim算法用于計(jì)算不同類型結(jié)點(diǎn)間的相似性。該算法基于單個(gè)對(duì)稱元路徑，雙向隨機(jī)行走，計(jì)算異構(gòu)網(wǎng)絡(luò)中不同類型實(shí)體間的相似性。同樣的，用戶需要根據(jù)自己掌握的相關(guān)領(lǐng)域知識(shí)來選擇單個(gè)路徑。文獻(xiàn)[14]提出在HeteSim基礎(chǔ)上的矩陣分解方法，可以得到結(jié)點(diǎn)的軟聚類或硬聚類結(jié)果，以此進(jìn)一步縮小路徑的選擇范圍。在這些方法中，用戶可以根據(jù)自己的專業(yè)知識(shí)來選擇相應(yīng)的單路徑，減少了路徑選擇的數(shù)量，減小了計(jì)算量，但要求用戶對(duì)相關(guān)領(lǐng)域?qū)I(yè)知識(shí)的理解較高，具有一定局限性。

通過引入用戶導(dǎo)向，預(yù)測(cè)與用戶搜索相關(guān)元路徑的方法[15-20]也可以用來改善路徑選擇數(shù)大的問題，而且在用戶滿意度方面表現(xiàn)更好。其中包括幾類算法：利用種子的半監(jiān)督算法[15-16]、關(guān)系預(yù)測(cè)算法[17-18]，和監(jiān)督與半監(jiān)督組合算法[19-20]。利用種子的半監(jiān)督算法是在半監(jiān)督的基礎(chǔ)上，將用戶提供的標(biāo)簽樣例和未提供標(biāo)簽的樣例結(jié)合起來，進(jìn)一步提高檢索效率。關(guān)系預(yù)測(cè)算法是在用戶輸入搜索和導(dǎo)向的情況下，根據(jù)輸入之間的關(guān)系，利用建好的預(yù)測(cè)算法去預(yù)測(cè)搜索與路徑之間的相似概率。監(jiān)督與半監(jiān)督組合算法分別克服了監(jiān)督學(xué)習(xí)需要大量標(biāo)注語料以及半監(jiān)督學(xué)習(xí)標(biāo)注語料受限于一定應(yīng)用環(huán)境的缺點(diǎn)，可以在少量標(biāo)注語料的情況下方便快捷地移植到其他標(biāo)注語料受限的應(yīng)用環(huán)境中。但這些算法主要適用于同構(gòu)網(wǎng)絡(luò)或異構(gòu)網(wǎng)絡(luò)中的同類型結(jié)點(diǎn)。在異構(gòu)網(wǎng)絡(luò)不同類型結(jié)點(diǎn)上的語義預(yù)測(cè)仍有待進(jìn)一步研究。

文獻(xiàn)[4]利用最大公共子圖和最小公共超圖等圖結(jié)構(gòu)信息的方法與PathSim的結(jié)果集合有相當(dāng)數(shù)量是重合的，表明了該文所提方法確實(shí)能有效度量各節(jié)點(diǎn)的相似程度。在文獻(xiàn)[3]中進(jìn)一步表明，利用類圖信息所得到的結(jié)點(diǎn)相似性的準(zhǔn)確性相較基于元路徑所得實(shí)體相似性的準(zhǔn)確性要好很多。由于利用圖的結(jié)構(gòu)信息不需要用戶的專業(yè)知識(shí)，并且圖中可以包含有不同類型的結(jié)點(diǎn)，再基于以上文獻(xiàn)的實(shí)驗(yàn)結(jié)果，可以得出以下結(jié)論：利用圖的結(jié)構(gòu)信息來對(duì)不同類型和相同類型結(jié)點(diǎn)間的語義進(jìn)行預(yù)測(cè)是可行的。

本文從用戶導(dǎo)向的角度出發(fā)，提出一個(gè)面向異構(gòu)網(wǎng)絡(luò)、基于用戶導(dǎo)向的語義預(yù)測(cè)算法。該算法不僅考慮同類型結(jié)點(diǎn)，同時(shí)也考慮不同類型結(jié)點(diǎn)。該算法不需要用戶具備一定的專業(yè)知識(shí)，而是利用圖的結(jié)構(gòu)信息，計(jì)算用戶搜索匹配各相關(guān)路徑的概率，通過選擇概率最大的路徑，可以減少候選路徑數(shù)，從而減小計(jì)算量。同時(shí)，可預(yù)測(cè)得到各相關(guān)路徑的概率，為多語義環(huán)境下計(jì)算相似性提供一種具體實(shí)現(xiàn)方法。

3 用戶導(dǎo)向-語義預(yù)測(cè)算法

由于異構(gòu)網(wǎng)絡(luò)中語義的多樣性，用戶搜索往往含有歧義性，所以需要更好地理解用戶搜索意向，以減少路徑選擇數(shù)。例如，在圖1所示的網(wǎng)絡(luò)中，作者和會(huì)議之間可以通過“Author-Paper-Venue-Conf”（APVC），“Author-Paper-Venue-Subj-Paper-Venue-Conf”（APSPVC）等路徑來連接。其中，APVC路徑表示作者寫的文獻(xiàn)發(fā)表在會(huì)議上，著重于作者參加的會(huì)議；而APSPVC路徑表示在會(huì)議中發(fā)表的文獻(xiàn)，這些文獻(xiàn)與作者發(fā)表的文獻(xiàn)有相同主題，著重于與作者文獻(xiàn)有相同主題的其他會(huì)議文獻(xiàn)。所以，在度量結(jié)點(diǎn)相似性之前，先進(jìn)行語義預(yù)測(cè)，降低語義歧義性，可減少候選路徑數(shù)。

圖1 ACM數(shù)據(jù)集網(wǎng)絡(luò)模式

3.1 異構(gòu)網(wǎng)絡(luò)的相關(guān)定義

Han和Yu等人在文獻(xiàn)[21]和文獻(xiàn)[22]中正式提出和倡導(dǎo)信息網(wǎng)絡(luò)這一概念，并探索信息網(wǎng)絡(luò)的元結(jié)構(gòu)，即網(wǎng)絡(luò)模式，同時(shí)提出元路徑的概念。利用元路徑所包含的語義來查找用戶搜索的信息，是相似性搜索領(lǐng)域一個(gè)主要的研究方向。本文在前人提出的信息網(wǎng)絡(luò)、網(wǎng)絡(luò)模式、元路徑和基于用戶導(dǎo)向的相似性搜索定義基礎(chǔ)上，提出以下兩個(gè)定義。

定義1路徑回溯

在一個(gè)數(shù)據(jù)集中，對(duì)于一個(gè)搜索q，在某個(gè)語義下，可以得到一系列相關(guān)或不相關(guān)結(jié)果集，則訓(xùn)練集可以形式化為：D=(qii=1,2,…,N ，其中是正相關(guān)結(jié)果集，q-i是不相關(guān)結(jié)果集。直觀上，可以知道：有相似結(jié)果的搜索應(yīng)該有相似的語義，而有不相似結(jié)果的搜索應(yīng)該有不同的語義。對(duì)于D中的一個(gè)候選結(jié)果r（用戶導(dǎo)向），正相關(guān)搜索可以收集并定義為不相關(guān)搜索為。則該候選結(jié)果r和正相關(guān)搜索所對(duì)應(yīng)的語義，就是用戶搜索隱含的候選路徑。

定義2正則路徑數(shù)

本文定義正則路徑數(shù)來表示網(wǎng)絡(luò)中兩個(gè)結(jié)點(diǎn)的整體連通性，表示如下：

其中P(qi,ui)表示在候選路徑下搜索qi到用戶導(dǎo)向ui的路徑實(shí)例數(shù)，P(qi,)表示在候選路徑下從結(jié)點(diǎn)qi開始的路徑實(shí)例數(shù)，P(, ui)表示在候選路徑下到達(dá)結(jié)點(diǎn)ui的路徑實(shí)例數(shù)，l表示路徑長(zhǎng)度。

3.2 語義預(yù)測(cè)過程

在進(jìn)行語義預(yù)測(cè)前，首先準(zhǔn)備一個(gè)數(shù)據(jù)集，數(shù)據(jù)集是以搜索的格式準(zhǔn)備的。然后對(duì)這個(gè)數(shù)據(jù)集使用路徑回溯方法，得到與用戶搜索相關(guān)的所有候選路徑。在此基礎(chǔ)上，統(tǒng)計(jì)搜索和導(dǎo)向在各候選路徑上的路徑實(shí)例數(shù)。然后將各路徑上的路徑實(shí)例數(shù)代入公式（1），得到對(duì)應(yīng)路徑上的正則路徑數(shù)。

由于語義之間的含義不同，可以把語義預(yù)測(cè)看作一個(gè)多分類問題。Softmax模型是logistic回歸模型在多分類問題上的推廣，可以用來對(duì)語義預(yù)測(cè)問題進(jìn)行概率建模。在多分類問題中，類標(biāo)簽可以取兩個(gè)以上的值。本文中，自變量是語義路徑的正則路徑數(shù)，因變量是搜索匹配該語義路徑的概率。具體形式如公式（2）所示：

p(S=j|qi,ui,θ)表示基于用戶導(dǎo)向ui和搜索qi屬于語義 j的概率，k是對(duì)應(yīng)語義數(shù)，其中xji是路徑 j的正則路徑數(shù)對(duì)概率分布進(jìn)行歸一化，使得所有概率之和為 1。

為了得到搜索匹配各候選路徑的最優(yōu)概率θj，本文訓(xùn)練模型參數(shù)θ，使其能夠最小化代價(jià)函數(shù) ：

1{值為真的表達(dá)式}=1，1{值為假的表達(dá)式}=0。

對(duì)于J(θ)的最小化問題，由于J(θ)不是嚴(yán)格非凸的，回歸中對(duì)參數(shù)的最優(yōu)化求解不只一個(gè)。為了求出唯一解，使得J(θ)成為一個(gè)嚴(yán)格凸函數(shù)，通過添加一個(gè)權(quán)重衰減項(xiàng)來修改代價(jià)函數(shù)。有了這個(gè)權(quán)重衰減項(xiàng)以后(λ＞0)，代價(jià)函數(shù)就變成了嚴(yán)格的凸函數(shù)，這樣就可以保證得到唯一的解。并且因?yàn)镴()θ是凸函數(shù)，利用梯度下降法等優(yōu)化算法可以保證收斂到全局最優(yōu)解?，F(xiàn)在代價(jià)函數(shù)變?yōu)椋?/p>

為了使用優(yōu)化算法，需要求得這個(gè)新函數(shù)J()θ的導(dǎo)數(shù)，如下：

有了上面的偏導(dǎo)數(shù)公式以后，就可以將它代入到優(yōu)化算法中。本文使用梯度下降法來實(shí)現(xiàn)最優(yōu)概率θj。在梯度下降法的標(biāo)準(zhǔn)實(shí)現(xiàn)中，每一次迭代需要進(jìn)行如下更新：

當(dāng)?shù)欢ù螖?shù)后，得到最優(yōu)的θj，進(jìn)而得到最優(yōu)θ。其中α表示沿梯度下降方向的步長(zhǎng)。在得到最優(yōu)的θ后，選擇最大的分量θj，利用相似性算法公式對(duì)相應(yīng)的路徑進(jìn)行計(jì)算，給出最終結(jié)果。

3.3 算法描述

首先基于用戶搜索q和導(dǎo)向u，得到各候選路徑的正則路徑數(shù)，然后利用softmax函數(shù)得到搜索q匹配各候選路徑的初始概率。再利用優(yōu)化算法求出搜索q匹配各候選路徑的最優(yōu)概率，最后代入softmax函數(shù)得到最終概率。具體過程如算法1所示。

算法1語義預(yù)測(cè)算法

輸入：用戶搜索q，用戶導(dǎo)向u，圖S=( )A,R

輸出：搜索q匹配相關(guān)語義的概率列表result

1. for eachq，u do

2. 路徑回溯（q，u）->Pl(q , u)；

3. Pl(q ,u)->xl(q , u)；

4. end for

5.for allxl(q ,u ) do

6. p(S=j|q,u,θ)；

7.end for

8.for each xl(q ,u ) do

9. J(θ)；

10. repeat

11. ?θjJ(θ)；

12. θj=θj-α?θjJ(θ)；

13. until迭代次數(shù)>107

14. end

15. end for

16.for allθjdo

17. p(S=j|q,u,θ)；

18.return result{θopt}其中，Pl( )

q,u是在路徑 j上的路徑實(shí)例數(shù)。p(S=j|q,u,θ)表示基于用戶導(dǎo)向u，搜索q屬于語義 j的概率。?θjJ()θ是利用梯度下降法來求最優(yōu)概率θopt。

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

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

本文使用DBLP數(shù)據(jù)集作為實(shí)驗(yàn)對(duì)象，其中包含1 928 000個(gè)文獻(xiàn)，109 000個(gè)作者，1 000個(gè)會(huì)議和193 000個(gè)關(guān)鍵字，以及總共4 244 000個(gè)關(guān)系。它的網(wǎng)絡(luò)模式如圖2所示。

圖2 DBLP網(wǎng)絡(luò)模式

4.2 實(shí)驗(yàn)設(shè)計(jì)

考慮到實(shí)驗(yàn)環(huán)境對(duì)路徑步長(zhǎng)的影響，為了能得到有效的正則路徑數(shù)，本實(shí)驗(yàn)的路徑步長(zhǎng)控制在4步之內(nèi)，路徑語義如表1所示。

為了驗(yàn)證本文提出算法的有效性，設(shè)計(jì)如下三個(gè)實(shí)驗(yàn)問題：

（1）基于用戶導(dǎo)向的語義預(yù)測(cè)算法能否準(zhǔn)確預(yù)測(cè)用戶搜索意向

表1 DBLP數(shù)據(jù)集4步長(zhǎng)路徑語義表

預(yù)測(cè)算法通過所給的搜索和導(dǎo)向，得到搜索屬于各候選路徑的最終概率。當(dāng)選擇概率最大的路徑時(shí)，與實(shí)際選擇情況進(jìn)行比較，驗(yàn)證是否能準(zhǔn)確預(yù)測(cè)。

（2）多語義路徑下的排名是否比單語義路徑的排名更準(zhǔn)確

為了得到更為準(zhǔn)確的結(jié)果，文獻(xiàn)[7]和文獻(xiàn)[13]都曾提出在多語義環(huán)境下計(jì)算相似性，但沒有給出解決方法。本文利用用戶搜索與導(dǎo)向在各語義路徑下的概率作為該路徑下的權(quán)重，然后將相似性算法在各相關(guān)路徑上的相似性分?jǐn)?shù)進(jìn)行加權(quán)組合，得到多語義路徑上的相似性分?jǐn)?shù)，再與原相似性算法的相似性分?jǐn)?shù)進(jìn)行比較。

（3）本文算法與對(duì)應(yīng)相似性算法的效率對(duì)比

本文實(shí)驗(yàn)中將對(duì)本文算法與對(duì)應(yīng)算法的效率進(jìn)行實(shí)驗(yàn)比較與分析。

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

4.3.1 算法時(shí)間復(fù)雜度分析

本文算法主要分為路徑回溯、語義預(yù)測(cè)兩部分。在路徑回溯部分，由于是對(duì)搜索和用戶導(dǎo)向結(jié)點(diǎn)雙向回溯，算法的時(shí)間復(fù)雜度為O()n2。在語義預(yù)測(cè)部分，用到的是調(diào)整的softmax函數(shù)，時(shí)間復(fù)雜度為O()n。在對(duì)該算法的參數(shù)θ進(jìn)行優(yōu)化時(shí)使用了梯度下降法，梯度下降法的時(shí)間復(fù)雜度為O(tn)，t表示迭代次數(shù)。所以本算法的時(shí)間復(fù)雜度為O(n2+(t +1) n)，而HeteSim算法的時(shí)間復(fù)雜度為O(k dn2T4)，其中k表示迭代次數(shù)，d表示結(jié)點(diǎn)出度和入度乘積的平均值，T表示結(jié)點(diǎn)類型數(shù)；PathSim算法的時(shí)間復(fù)雜度為O(n2)。

4.3.2 實(shí)驗(yàn)參數(shù)的選擇

迭代步長(zhǎng)只影響速度，不影響收斂性。在梯度下降法中，往往需要設(shè)置一個(gè)合適的步長(zhǎng)。步長(zhǎng)設(shè)置太大，使得要估計(jì)的系數(shù)在迭代過程中不斷增大，最后趨于無窮大，程序陷入死循環(huán)或溢出；太小可能永遠(yuǎn)到不了最優(yōu)點(diǎn)。由相關(guān)證明文件（http://research.cs.buct.edu.cn/WDBLab/Appendix.pdf）可知，當(dāng)假定正則項(xiàng)系數(shù)λ=1時(shí)，步長(zhǎng)α在（0，2）范圍內(nèi)對(duì)所有預(yù)定義路徑來說是比較合適的。并且迭代達(dá)到1 000萬次時(shí)，迭代停止。本實(shí)驗(yàn)中，設(shè)定迭代步長(zhǎng)的初始值為0.1（因?yàn)楦髀窂降某跏几怕手稻捅容^低，步數(shù)設(shè)置太大時(shí)最優(yōu)解會(huì)出現(xiàn)負(fù)數(shù)，也就意味著步數(shù)太大導(dǎo)致越過了最優(yōu)解），每次迭代步長(zhǎng)的值由下面公式確定：

α=α*0.8

4.3.3 與其他算法的比較

PathSim[13]和HeteSim[7]是異構(gòu)網(wǎng)絡(luò)中兩個(gè)經(jīng)典的相似性搜索算法。它們都是基于單個(gè)元路徑，計(jì)算異構(gòu)網(wǎng)絡(luò)中實(shí)體間的相似性。對(duì)于一個(gè)對(duì)稱元路徑P=(Pl)，算法PathSim和HeteSim都可以應(yīng)用在該元路徑上，而對(duì)于非對(duì)稱元路徑，HeteSim可以應(yīng)用。本實(shí)驗(yàn)中，分別在對(duì)稱與非對(duì)稱元路徑上與上述算法進(jìn)行比較。

在對(duì)稱路徑上，給出一個(gè)用戶搜索Christos Faloutsos和導(dǎo)向Spiros Papadimitriou，結(jié)果如表2和表3所示。

表2 路徑APA上，用PathSim得到的Top-10與Christos Faloutsos最相似的作者

表3 路徑APA上，用HeteSim得到的Top-10與Christos Faloutsos最相似的作者

現(xiàn)實(shí)中，Spiros Papadimitriou是Christos Faloutsos的共作者，所以用戶搜索隱含的語義是找到Christos Faloutsos的其他共作者。所以PathSim和HeteSim算法所走路徑都是APA。而在用預(yù)測(cè)算法進(jìn)行預(yù)測(cè)時(shí)，在定義路徑APA、APVPA和APTPA上的歸一化概率如表4所示。其中概率最大的路徑為APA，概率為0.433 8。選擇概率最大路徑為APA，與PathSim和HeteSim相符；而當(dāng)選擇組合路徑時(shí)，各路徑權(quán)重即為上述概率。

表4 基于不同導(dǎo)向，作者Christos Faloutsos在對(duì)稱元路徑上的匹配概率

而對(duì)于同一個(gè)搜索Christos Faloutsos，此時(shí)給出的導(dǎo)向是Philip S.Yu，結(jié)果如表5和表6所示。

現(xiàn)實(shí)中，Philip S.Yu是在數(shù)據(jù)挖掘領(lǐng)域與Christos Faloutsos名聲相當(dāng)?shù)淖髡?，所以用戶搜索隱含的語義是找到與Christos Faloutsos在數(shù)據(jù)挖掘領(lǐng)域名聲相當(dāng)?shù)钠渌髡摺Ｋ訦eteSim算法所走路徑是APVPA。而在用預(yù)測(cè)算法進(jìn)行預(yù)測(cè)時(shí)，在定義路徑APA、APVPA和APTPA上的歸一化概率如表4所示。其中概率最大的路徑為APVPA，其概率為0.581 5。選擇概率最大路徑為APVPA，與PathSim和HeteSim相符；而當(dāng)選擇組合路徑時(shí)，各路徑權(quán)重即為上述概率。

表5 路徑APCPA上，用PathSim得到的Top-10與Christos Faloutsos最相似的作者

表6 路徑APVPA上，用HeteSim得到的Top-10與Christos Faloutsos最相似的作者

在非對(duì)稱路徑上，給出一個(gè)用戶搜索Christos Faloutsos和導(dǎo)向KDD，結(jié)果如表7所示。

表7 路徑APC上，Top-10與作者相關(guān)的會(huì)議

現(xiàn)實(shí)中，KDD是Christos Faloutsos主要參加的會(huì)議，所以HeteSim可以根據(jù)用戶的專業(yè)知識(shí)去選擇特定的元路徑APC。而在用預(yù)測(cè)算法進(jìn)行預(yù)測(cè)時(shí)，在定義路徑APC，和APTPC上的歸一化概率如表8所示。其中概率最大的路徑為APC，其概率為0.600 3。概率最大路徑為APC，與HeteSim相符；而當(dāng)選擇組合路徑時(shí)，各路徑權(quán)重即為上述概率。

表8 基于用戶搜索Christos Faloutsos和導(dǎo)向KDD的各路徑概率

根據(jù)以上實(shí)驗(yàn)，可以得出下面兩個(gè)結(jié)論：

（1）基于用戶導(dǎo)向，由語義預(yù)測(cè)算法得到概率最高的路徑與實(shí)際選擇的路徑是相同的，說明預(yù)測(cè)算法能夠準(zhǔn)確地對(duì)用戶搜索意向進(jìn)行預(yù)測(cè)。

（2）本實(shí)驗(yàn)利用用戶搜索與導(dǎo)向在各語義路徑下的概率作為該路徑下的權(quán)重，然后將PathSim和HeteSim在各相關(guān)路徑的相似性分?jǐn)?shù)進(jìn)行加權(quán)組合，分別與PathSim和HeteSim進(jìn)行比較。由表2和表3可以看到，當(dāng)給出用戶搜索Christos Faloutsos和導(dǎo)向Spiros Papadimitriou時(shí)，多語義路徑下的得分比PathSim和HeteSim高。但在給出用戶搜索Christos Faloutsos和導(dǎo)向Philip S.Yu時(shí)，得分比PathSim和HeteSim低。這是由于多語義路徑下對(duì)語義的區(qū)分度不高，勢(shì)必會(huì)將相關(guān)語義的得分拉低，同時(shí)將不太相關(guān)語義的得分拉高，造成了多語義路徑得分并不一定總是比單語義路得分高。同時(shí)也說明了相似性得分只是評(píng)價(jià)相似性度量的一個(gè)方面，還需要對(duì)實(shí)際的排名質(zhì)量進(jìn)行比較。

4.3.4 排名的質(zhì)量比較

為了比較排名結(jié)果的質(zhì)量，本文使用DCG指標(biāo)[23]來評(píng)價(jià)本文方法和其他算法分別在對(duì)稱路徑APA、APTPA、APCPA和非對(duì)稱路徑APC，APTPC上搜索Christos Faloutsos的表現(xiàn)。

在本文實(shí)驗(yàn)中，將實(shí)驗(yàn)結(jié)果按1～10進(jìn)行打分。10分表示排名最好的結(jié)果，1分表示排名最差的結(jié)果。

在APA路徑上，PathSim和HeteSim與本文方法的DCG分?jǐn)?shù)如圖3所示。

圖3 APA路徑上，本文方法與PathSim、HeteSim的DCG分?jǐn)?shù)

在APCPA路徑上，PathSim和HeteSim與本文方法的DCG分?jǐn)?shù)如圖4所示。

圖4 APCPA路徑上，本文方法與PathSim、HeteSim的DCG

在APC路徑上，HeteSim和本文方法的DCG分?jǐn)?shù)如圖5所示。

圖5 APC路徑上，HeteSim和本文方法的DCG分?jǐn)?shù)

可以看到，在對(duì)稱路徑和非對(duì)稱路徑上，本文方法在原有相似性算法的基礎(chǔ)上，利用多語義環(huán)境下的相似性分別與PathSim和HeteSim進(jìn)行了比較，都表現(xiàn)出了較好的性能。說明雖然多語義路徑下的得分不一定比單語義路徑得分高，但排名質(zhì)量是好于單語義路徑的。

4.3.5 算法效率對(duì)比

為了比較本文算法和對(duì)應(yīng)算法的效率，本文將在對(duì)稱路徑和非對(duì)稱路徑上搜索Christos Faloutsos的運(yùn)行時(shí)間進(jìn)行比較。

在APA路徑上，基于用戶導(dǎo)向Spiros Papadimitriou，PathSim和HeteSim與本文方法的運(yùn)行時(shí)間如圖6所示。

圖6 APA路徑上，本文方法與PathSim、HeteSim的運(yùn)行時(shí)間

在APCPA路徑上，基于用戶導(dǎo)向Philip S.Yu，PathSim和HeteSim與本文方法的運(yùn)行時(shí)間如圖7所示。

在APC路徑上，基于用戶導(dǎo)向KDD，HeteSim和本文方法的運(yùn)行時(shí)間如圖8所示。

圖7 APCPA路徑上，本文方法與PathSim、HeteSim的運(yùn)行時(shí)間

圖8 APC路徑上，本文方法與PathSim、HeteSim的運(yùn)行時(shí)間

由以上實(shí)驗(yàn)可以看到，本文算法的運(yùn)行時(shí)間高于對(duì)應(yīng)算法。這是由于本文首先基于用戶導(dǎo)向?qū)λ阉髟诟髡Z義路徑下的匹配概率進(jìn)行預(yù)測(cè)，并將概率作為對(duì)應(yīng)路徑上的權(quán)重，然后利用相似性算法在各對(duì)應(yīng)路徑上計(jì)算得到的相似性分?jǐn)?shù)進(jìn)行加權(quán)組合，即本文方法的運(yùn)行時(shí)間包括語義預(yù)測(cè)和相似性計(jì)算兩部分。而且本文算法在預(yù)測(cè)部分為了得到準(zhǔn)確的預(yù)測(cè)結(jié)果，需要進(jìn)行迭代更新，當(dāng)?shù)螖?shù)逐漸增加時(shí)，本文算法與對(duì)應(yīng)算法之間的運(yùn)行時(shí)間差距會(huì)逐步增大。因此需要在運(yùn)行時(shí)間和結(jié)果準(zhǔn)確性之間進(jìn)行權(quán)衡。

5 結(jié)束語

本文提出的用戶搜索導(dǎo)向-語義預(yù)測(cè)算法，可用于同類型和不同類型結(jié)點(diǎn)間的語義預(yù)測(cè)，能夠較好地預(yù)測(cè)用戶搜索的語義，且不需要用戶具備相關(guān)專業(yè)知識(shí)。并且本算法減少了元路徑選擇數(shù)，以一種新的方法緩解了計(jì)算量大的問題。本文根據(jù)預(yù)測(cè)過程所得到的概率作為多語義路徑的權(quán)重，為多語義環(huán)境下的相似性計(jì)算提供了具體的實(shí)現(xiàn)方法。實(shí)驗(yàn)表明，本文提出的算法能夠準(zhǔn)確對(duì)同類型和不同類型結(jié)點(diǎn)間語義的預(yù)測(cè)，在排名質(zhì)量上好于對(duì)應(yīng)的相似性算法。