融合潛在狄利克雷分布與元路徑分析的用戶相關(guān)性度量方法

徐紅艷 王丹 王富海 王嶸冰

摘 要：用戶相關(guān)性度量是異構(gòu)信息網(wǎng)絡(luò)研究的基礎(chǔ)與核心?，F(xiàn)有的用戶相關(guān)性度量方法由于未充分開(kāi)展多維度分析和鏈路分析，其準(zhǔn)確性尚存在提升空間。為此，提出了一種融合狄利克雷分布（LDA）與元路徑分析的用戶相關(guān)性度量方法。首先利用LDA進(jìn)行主題建模，通過(guò)分析網(wǎng)絡(luò)中節(jié)點(diǎn)的內(nèi)容來(lái)計(jì)算節(jié)點(diǎn)的相關(guān)性;然后，引入元路徑來(lái)刻畫(huà)節(jié)點(diǎn)間關(guān)系類(lèi)型，通過(guò)關(guān)聯(lián)度量（DPRel）方法對(duì)異構(gòu)信息網(wǎng)絡(luò)中的用戶進(jìn)行相關(guān)性測(cè)量;接著，將節(jié)點(diǎn)的相關(guān)性融入到用戶相關(guān)性度量計(jì)算中;最后，采用IMDB真實(shí)電影數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，將所提方法和嵌入LDA主題模型的協(xié)同過(guò)濾推薦方法（ULRCF）、基于元路徑的相關(guān)性度量方法（PathSim）進(jìn)行了對(duì)比分析。實(shí)驗(yàn)結(jié)果表明，所提方法能夠克服數(shù)據(jù)稀疏性弊端，提高用戶相關(guān)性度量的準(zhǔn)確性。

關(guān)鍵詞：用戶相關(guān)性;異構(gòu)信息網(wǎng)絡(luò);主題模型;元路徑;度量

中圖分類(lèi)號(hào)：TP302.1

文獻(xiàn)標(biāo)志碼：A

User relevance measure method combining latent Dirichlet allocation and metapath analysis

XU Hongyan， WANG Dan， WANG Fuhai， WANG Rongbing*

School of Information， Liaoning University， Shenyang Liaoning 110036， China

Abstract：

User relevance measure is the foundation and core of heterogeneous information network research. The existing user relevance measure methods still have improvement space due to insufficient multidimensional analysis and link analysis. Aiming at the fact， a user relevance measure method combining Latent Dirichlet Allocation （LDA） and metapath analysis was proposed. Firstly， the LDA was used to model the topic， and the relevance of nodes was analyzed by the node contents in the network. Secondly， the metapath was introduced to describe the relationship type between nodes， and relevance measure was carried out for users in heterogeneous information network by relevance measure method （DPRel）. Thirdly， the relevance of nodes was incorporated into the calculation of user relevance measure. Finally， the experiment was carried out on IMDB real movie dataset， and the proposed method was compared with the collaborative filtering recommendation method embedded in LDA topic model ULRCF （Unifying LDA and Ratings Collaborative Filtering） and metapath based similarity method （PathSim）.The experimental results show that the proposed method can overcome the drawback of data sparsity and improve the accuracy of user relevance measure.

Key words：

user relevance; heterogeneous information network; topic model; metapath; measure

0?引言

信息網(wǎng)絡(luò)由一系列節(jié)點(diǎn)以及連接節(jié)點(diǎn)的關(guān)系構(gòu)成，按照網(wǎng)絡(luò)中的節(jié)點(diǎn)類(lèi)型和關(guān)系類(lèi)型，可以分為同構(gòu)信息網(wǎng)絡(luò)和異構(gòu)信息網(wǎng)絡(luò)。由于異構(gòu)信息網(wǎng)絡(luò)比同構(gòu)信息網(wǎng)絡(luò)具有更加豐富的信息而更加貼近現(xiàn)實(shí)，如社交網(wǎng)絡(luò)、新媒體網(wǎng)絡(luò)、文獻(xiàn)網(wǎng)絡(luò)等。異構(gòu)信息網(wǎng)絡(luò)中節(jié)點(diǎn)的異構(gòu)性、連接的復(fù)雜性以及數(shù)據(jù)的稀疏性等因素為用戶相關(guān)性度量帶來(lái)更大的難度，而用戶相關(guān)性度量是開(kāi)展異構(gòu)信息網(wǎng)絡(luò)相關(guān)研究的基礎(chǔ)與核心。

近年來(lái)，眾多學(xué)者對(duì)用戶相關(guān)性度量方法進(jìn)行深入研究以準(zhǔn)確獲取用戶間的關(guān)聯(lián)，其中余弦相似度和皮爾森相關(guān)系數(shù)[1]法僅需要用戶對(duì)物品的評(píng)分來(lái)計(jì)算用戶之間的相關(guān)性，但它無(wú)法解決冷啟動(dòng)問(wèn)題，必須依賴大量用戶歷史數(shù)據(jù)。隨著對(duì)信息網(wǎng)絡(luò)的研究不斷加深，學(xué)者們利用網(wǎng)絡(luò)中的節(jié)點(diǎn)信息和鏈接進(jìn)行用戶相關(guān)性度量，提出基于節(jié)點(diǎn)特征的相關(guān)性度量方法[2-3]，將兩個(gè)節(jié)點(diǎn)特征的排名結(jié)果之間的相關(guān)性定義為節(jié)點(diǎn)之間的相關(guān)性，解決了數(shù)據(jù)稀疏問(wèn)題，但其缺點(diǎn)是度量精度不高。目前，異構(gòu)信息網(wǎng)絡(luò)的主流用戶相關(guān)性度量方法是基于元路徑進(jìn)行相關(guān)性度量[4-5]，借助用戶在網(wǎng)絡(luò)中鏈接的方式來(lái)計(jì)算用戶的相關(guān)性， 但此類(lèi)方法并未挖掘網(wǎng)絡(luò)路徑中非用戶節(jié)點(diǎn)的內(nèi)容相關(guān)性，而非用戶節(jié)點(diǎn)信息是用戶偏好和需求的最直觀表現(xiàn)， 故得到的用戶相關(guān)性度量準(zhǔn)確性仍有待提升。

為解決非用戶節(jié)點(diǎn)語(yǔ)義信息缺失帶來(lái)的用戶相關(guān)性度量不準(zhǔn)確問(wèn)題，本文引入狄利克雷分布（Latent Dirichlet Allocation， LDA）主題模型[6]挖掘網(wǎng)絡(luò)中非用戶節(jié)點(diǎn)特征;采用元路徑分析用戶節(jié)點(diǎn)間的關(guān)聯(lián)關(guān)系，提出了融合LDA與元路徑分析的用戶相關(guān)性度量方法（User Relevance Measure Method Combining LDA and Meta Path Analysis，LPUSim）。該方法首先利用網(wǎng)絡(luò)中非用戶節(jié)點(diǎn)的語(yǔ)義信息挖掘用戶偏好;然后，結(jié)合DPRel方法[7]計(jì)算元路徑中用戶節(jié)點(diǎn)間的關(guān)聯(lián)度得到用戶相關(guān)性;最后，使用歸一化方法獲得不同元路徑的相應(yīng)權(quán)值，對(duì)元路徑進(jìn)行加權(quán)整合，從而更全面地度量用戶的相關(guān)性。對(duì)比實(shí)驗(yàn)表明，本文所提方法能更真實(shí)、更準(zhǔn)確地分析用戶相關(guān)性。

1?相關(guān)工作

1.1?文本特征提取

文本分析是機(jī)器學(xué)習(xí)算法的主要應(yīng)用領(lǐng)域之一。它是將文本模型轉(zhuǎn)換為機(jī)器可識(shí)別的格式以進(jìn)行計(jì)算機(jī)處理，同時(shí)盡可能保留文本的原有語(yǔ)義信息[8]。Salton等[9]提出向量空間模型（Vector Space Model， VSM），把對(duì)文本內(nèi)容的處理簡(jiǎn)化為向量空間中向量的運(yùn)算，使問(wèn)題的復(fù)雜性大為降低，但它只關(guān)注特征項(xiàng)的頻率信息從而丟失了文本上下文的語(yǔ)義信息;Deepwester等[10]提出的隱語(yǔ)義分析（Latent Semantic Analysis， LSA）將詞和文檔映射到潛在語(yǔ)義空間，對(duì)詞文檔進(jìn)行降維，從而提高了信息檢索的精確度。相較于傳統(tǒng)向量空間模型，潛在語(yǔ)義空間的維度更小，語(yǔ)義關(guān)系更明確，但存在多義詞等問(wèn)題。Blei等[6]提出的LDA主題模型是在LSA基礎(chǔ)上進(jìn)行了改進(jìn)，可以被用于識(shí)別大規(guī)模文檔集或語(yǔ)料庫(kù)中潛藏的主題信息，同時(shí)考慮了上下文語(yǔ)義之間的關(guān)系，并在一定程度上解決一詞多義問(wèn)題。本文利用LDA可以獲知用戶的偏好主題，為非用戶節(jié)點(diǎn)的特征提取提供支持。

1.2?用戶相關(guān)性度量

相關(guān)性度量作為數(shù)據(jù)挖掘領(lǐng)域研究的重要方向之一，眾多學(xué)者已經(jīng)對(duì)其開(kāi)展了較為深入的研究：面向同構(gòu)信息網(wǎng)絡(luò)，Jeh等[11]提出的個(gè)性化PageRank方法;Kusumoto等[12]在SimRank中提出的線性遞歸表達(dá)式能應(yīng)用于并行計(jì)算，使得大規(guī)模圖計(jì)算成為可能，但這些方法忽略了對(duì)象和鏈接的類(lèi)型區(qū)別; Huang等[13]提出了基于元結(jié)構(gòu)在大規(guī)模文獻(xiàn)異構(gòu)網(wǎng)絡(luò)中的相關(guān)性度量方法; Meng等[14]提出了一種FSPG貪婪的方法來(lái)選擇最相關(guān)的元路徑進(jìn)行相關(guān)性計(jì)算。這些方法都與異構(gòu)信息網(wǎng)絡(luò)的結(jié)構(gòu)相關(guān)性度量有關(guān)，具有一定的局限性。Sun等[15]提出PathSim相關(guān)性度量方法可以系統(tǒng)地區(qū)分連接兩個(gè)用戶路徑間的語(yǔ)義;Gupta等[7]提出的DPRel方法是一種比較新穎的、半度量的用戶相關(guān)性度量方法，可用于相同和不同類(lèi)型的節(jié)點(diǎn)。盡管這些方法已經(jīng)取得了良好的應(yīng)用效果，但它們并未考慮節(jié)點(diǎn)的內(nèi)容，從而導(dǎo)致計(jì)算結(jié)果不夠準(zhǔn)確。

2?融合LDA與元路徑的用戶相關(guān)性度量

本文不僅考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)之間的直接關(guān)系，而且考慮了網(wǎng)絡(luò)中非用戶節(jié)點(diǎn)特征之間的潛在相關(guān)性。首先，利用網(wǎng)絡(luò)中非用戶節(jié)點(diǎn)特征挖掘出用戶偏好，實(shí)現(xiàn)基于節(jié)點(diǎn)主題的用戶相關(guān)性度量;然后，引入元路徑來(lái)刻畫(huà)節(jié)點(diǎn)間關(guān)系類(lèi)型，利用基于元路徑的半度量DPRel方法[7]計(jì)算用戶的相關(guān)性;最后，利用本文提出的LPUSim方法對(duì)非用戶節(jié)點(diǎn)的相關(guān)性分?jǐn)?shù)進(jìn)行加權(quán)整合并應(yīng)用到用戶的相關(guān)性度量中。

2.1?基于節(jié)點(diǎn)主題的用戶相關(guān)性度量

LDA是一種文檔主題生成模型，它包含詞、主題和文檔三層結(jié)構(gòu)，也稱為一個(gè)三層貝葉斯概率模型。生成模型可以看成是一個(gè)文檔的產(chǎn)生過(guò)程，即認(rèn)為文章中的每個(gè)單詞都是通過(guò)“選擇具有一定概率的主題并以一定概率從主題中選擇某個(gè)單詞”的過(guò)程獲得的。主題的文檔遵循多項(xiàng)式分布，并且該單詞的主題遵循多項(xiàng)式分布。因此，如果要生成一篇文檔，則每個(gè)單詞出現(xiàn)在其中的概率如式（1）所示：

p（詞語(yǔ)|文檔）=

∑主題p（詞語(yǔ)|主題）×p（主題|文檔）（1）

為更好地說(shuō)明所提方法，本文以IMDB電影數(shù)據(jù)集為例，該數(shù)據(jù)集中不僅包含用戶對(duì)電影的評(píng)分記錄，還包含了電影的劇情信息。為了能夠方便地計(jì)算出用戶所關(guān)注的電影主題，即用戶偏好特征，本文利用LDA主題模型把文本信息轉(zhuǎn)化為了易于建模的數(shù)字信息。用戶看過(guò)由同一導(dǎo)演執(zhí)導(dǎo)的電影，但這些電影的主題可能有很大差異，以往只考慮了元路徑對(duì)用戶相關(guān)性的影響，并沒(méi)有考慮電影主題也會(huì)對(duì)用戶的相關(guān)性產(chǎn)生影響。假設(shè)所有電影的文檔主題概率分布向量集合為T(mén)= [T1 ，T2，T3，…]，則節(jié)點(diǎn)主題相關(guān)度采用余弦相似度對(duì)同一個(gè)演員飾演電影的文檔主題概率分布向量進(jìn)行計(jì)算，如式（2）：

SimL（u，v）=Sim（Tau，Tav）=∑|A|a=1COS（Tau，Tav）N（2）

其中：Tau表示用戶u看演員a演過(guò)的所有電影主題概率分布向量集合，N表示Tau和Tav集合中元素?cái)?shù)量的最小值，A表示演員的數(shù)量。

本文基于用戶觀看同一個(gè)演員飾演的電影評(píng)分來(lái)求用戶相關(guān)性計(jì)算公式如式（3）：

SimS（u，v）=∑|A|a=1Simscore（u，v）（3）

其中，Simscore（u，v）為基于用戶屬性和評(píng)分的協(xié)同過(guò)濾推薦算法[16]中提出的相似度計(jì)算公式，避免了傳統(tǒng)相似度計(jì)算的弊端，提高了用戶相關(guān)度的區(qū)分性，有利于評(píng)分預(yù)測(cè)和推薦。

用戶看了相同主題的電影并且對(duì)它們的評(píng)分相似才能夠說(shuō)明是喜歡這些電影，即他們的興趣偏好相似，因此，基于電影主題與用戶評(píng)分共同度量用戶相關(guān)性的公式如式（4）：

SimLS（u，v）=SimL（u，v）×SimS（u，v）（4）

2.2?基于元路徑的用戶相關(guān)性度量

2.2.1?基本定義

建立在Sun等[15]描述的框架之上，首先給出構(gòu)建異構(gòu)信息網(wǎng)絡(luò)中相關(guān)性度量所需的一些定義。

定義1?信息網(wǎng)絡(luò)是一個(gè)帶有對(duì)象類(lèi)型映射函數(shù)τ：V→A和連接類(lèi)型映射函數(shù)φ：ε→R的有向圖G（V，ε）其中每個(gè)對(duì)象v∈V屬于一個(gè)特定的對(duì)象類(lèi)型τ（v）∈A，每個(gè)鏈接e∈ε屬于一個(gè)特定的關(guān)系Φ（e）∈R。

當(dāng)對(duì)象的類(lèi)型A>1或關(guān)系類(lèi)型R>1，網(wǎng)絡(luò)是異構(gòu)信息網(wǎng)絡(luò);否則它是一個(gè)同構(gòu)信息網(wǎng)絡(luò)。

為更好地描述所提方法，本文以IMDB電影信息網(wǎng)絡(luò)為例。該網(wǎng)絡(luò)為異構(gòu)信息網(wǎng)絡(luò)，其中節(jié)點(diǎn)和邊均符合異質(zhì)信息網(wǎng)絡(luò)的定義，圖1顯示了IMDB信息網(wǎng)絡(luò)的實(shí)體關(guān)聯(lián)。網(wǎng)絡(luò)中包含5種類(lèi)型節(jié)點(diǎn)，分別為用戶（U）、電影（M）、演員（A）、導(dǎo)演（D）、電影類(lèi)型（G）。4種類(lèi)型的鏈接關(guān)系分別為演員和電影之間的參演（act）關(guān)系、用戶和電影之間的評(píng)分（rate）關(guān)系及電影類(lèi)型和電影之間的屬于（attribute）關(guān)系、導(dǎo)演和電影之間的指導(dǎo)（direct）關(guān)系。

定義2?元路徑P是在網(wǎng)絡(luò)模式TG=（A，R）的圖上的一條路徑，它的形式是A1→R1A2→R2…→RlAl+1，定義了類(lèi)型A1和類(lèi)型Al+1間的復(fù)合關(guān)系R=R1R2…Rl，其中，代表關(guān)系上的復(fù)合運(yùn)算。

在異構(gòu)信息網(wǎng)絡(luò)中，可以通過(guò)不同的路徑連接兩個(gè)對(duì)象，這些路徑將具有不同的語(yǔ)義含義。例如，IMDB網(wǎng)絡(luò)模式中兩個(gè)元路徑UMU（用戶電影用戶）和UMAMU（用戶電影演員電影用戶）分別如圖2（a）和（b）所示。

定義3?給定網(wǎng)絡(luò)G=（V，ε）及其網(wǎng)絡(luò)模式TG，本文將元路徑P=（A1→A2→…→Al）下的鄰接矩陣稱作關(guān)系矩陣，并定義M=WA1A2WA2A3…WAl-1Al，其中WAiAj為類(lèi)型Ai和類(lèi)型Aj間的鄰接矩陣。M（i，j）代表元路徑P上對(duì)象xi∈A1和對(duì)象yi∈Al之間的路徑實(shí)例的數(shù)目。

定義4?給定一個(gè)元路徑P=（A1→A2→…→Am→…→Al→Al+1），若A1與Al+1是不同的對(duì)象類(lèi)型，那么將異構(gòu)網(wǎng)絡(luò)用只有A1與Al+1對(duì)象類(lèi)型的二分網(wǎng)絡(luò)表示，源對(duì)象a1i∈A1與目標(biāo)對(duì)象b（l+1）j∈Al+1之間的相關(guān)性如式（5）：

DPRel（a1i，b（l+1）j|PRel）=

ω（a1i，b（l+1）j）1deg（a1i）+1deg（b（l+1）j）1deg（a1i）∑ jω（a1i，b（l+1）j）+1deg（b（l+1）j）∑ iω（a1i，b（l+1）j）（5）

其中：ω（a1i，b（l+1）j）是來(lái)自交換矩陣M（a1i，b（l+1）j）中的值，即表示在指定元路徑中實(shí)體類(lèi)型a1i∈A1與b（l+1）j∈Al+1之間的路徑實(shí)例條數(shù)，deg（a1i）與deg（b（l+1）j）是a1i和b（l+1）j分別在二分網(wǎng)絡(luò)中節(jié)點(diǎn)的度。

在本文的工作中，需要測(cè)量相同類(lèi)型對(duì)象之間的相關(guān)性，即元路徑的源和目標(biāo)對(duì)象類(lèi)型是相同的。計(jì)算公式如式（6）：

SimP（u，v）=DPRel（a1i，b（l+1）j|PRel）=

X·Y‖X‖2+‖Y‖2-X·Y（6）

其中：對(duì)于PLRel=（A1A2…Am）， X=DPRel（a1i，bmk|PLRel）用來(lái)計(jì)算源節(jié)點(diǎn)a1i和所有中間對(duì)象之間的相關(guān)度，bmk∈Am，k。同樣地，對(duì)于P-1RRel=（Al+1Al…Am），Y=DPRel（a（l+1）j，bmk|P-1RRel），用來(lái)計(jì)算目標(biāo)對(duì)象a（l+1）j和所有中間對(duì)象之的相關(guān)度，bmk∈Am，k。

2.2.2?元路徑的生成與選擇

如何生成所有可能的和有效的元路徑是基于元路徑的相關(guān)性度量工作中的重要環(huán)節(jié)。本文探索異構(gòu)信息網(wǎng)絡(luò)的網(wǎng)絡(luò)模式，以生成從目標(biāo)對(duì)象類(lèi)型開(kāi)始和結(jié)束的所有元路徑。生成元路徑過(guò)程如圖3所示。

本文中要研究的元路徑是由起點(diǎn)和終點(diǎn)均是用戶類(lèi)型的節(jié)點(diǎn)組成的路徑。根據(jù)無(wú)限長(zhǎng)度元路徑下PathSim的有限行為定理[15]可以推斷，無(wú)限增加元路徑長(zhǎng)度不會(huì)提升相關(guān)性度量效果，于是本文采用了長(zhǎng)度限制在4以內(nèi)的元路徑結(jié)合式（6）進(jìn)行相關(guān)度計(jì)算。如表1所示，考慮了4條元路徑，從一定程度上解決了數(shù)據(jù)稀疏問(wèn)題，從而提高了信息推薦的準(zhǔn)確性。

2.3?LPUSim相關(guān)性度量方法

本文考慮了元路徑UMAMU對(duì)用戶相關(guān)性度量影響的基礎(chǔ)上，同時(shí)也考慮了電影主題信息對(duì)挖掘結(jié)果的影響。設(shè)想一些用戶看來(lái)同一個(gè)演員飾演的電影，但是電影主題風(fēng)格迥異，如用戶U1和U2分別看了演員A1飾演的以愛(ài)情和驚悚為主題的電影。因此，本文將求得用戶偏好的相關(guān)性得分作為節(jié)點(diǎn)間路徑權(quán)重，與基于元路徑計(jì)算獲得的用戶相關(guān)度相融合計(jì)算用戶相關(guān)性。

為了方便后續(xù)計(jì)算，本文將元路徑UMGMU、UMAMU、UMDMU、UMU依次編號(hào)為1、2、3、4。本文計(jì)算第i（i=1，2，3，4）條元路徑的相關(guān)度方法如式（7）：

Simi（u，v）=SimLS（u，v）×SimP（u，v）（7）

其中SimP表示基于元路徑的用戶相關(guān)度。

為防止式（7）求得的相關(guān)度過(guò)小而失去相似度比較的特征，本文對(duì)式（7）所得的相關(guān)度進(jìn)行同比放大，放大策略如式（8）：

Simi′（u，v）=Simi（u，v）Max（S1，S2，S3，S4）（8）

其中：Si表示第i條元路徑所有用戶相關(guān)度集合， Max（S1，S2，S3，S4）表示4條元路徑所有用戶相關(guān)度集合中的最大值。本文將式（7）中計(jì)算出的相關(guān)度值進(jìn)行同比放大后，雖然用戶相關(guān)度的值會(huì)發(fā)生變化，但每個(gè)相關(guān)度的排序順序是不變的。這樣既解決了因相關(guān)度過(guò)小而失去相似度比較特征的問(wèn)題，同時(shí)也保證了相關(guān)度依舊在[0，1]。

2.3.1?多重元路徑的組合

由于在異構(gòu)信息網(wǎng)絡(luò)中，可能存在具有不同語(yǔ)義的若干條元路徑。不同元路徑度量的用戶相關(guān)度不同，因此，應(yīng)該將較高的權(quán)重分配給具有重要關(guān)系的元路徑。此外，僅遵循一條元路徑，可能會(huì)錯(cuò)過(guò)其他語(yǔ)義上有意義的元路徑。因此，考慮到對(duì)以上分析得到的4條元路徑進(jìn)行組合可以更全面、更準(zhǔn)確地度量用戶相關(guān)性。本文通過(guò)按比例分配的原則計(jì)算元路徑的權(quán)重，第i條元路徑的權(quán)重如式（9）：

ωi=Simi∑4i=1Simi（9）

其中Simi表示第i條元路徑下所有用戶的相關(guān)度之和。

在獲得元路徑的權(quán)重之后，最終兩個(gè)用戶的相關(guān)度如式（10）：

Sim（u，v）=∑4i=1ωi×Simi′（u，v）（10）

2.3.2?LPUSim方法在推薦中的應(yīng)用

綜上，現(xiàn)將融合LDA與元路徑的分析用戶相關(guān)性度量方法應(yīng)用于推薦的流程描述如下，其中，u表示目標(biāo)用戶u0評(píng)分過(guò)的項(xiàng)目評(píng)分均值，v表示鄰居用戶v評(píng)分過(guò)的項(xiàng)目評(píng)分均值，rv，i表示用戶v對(duì)項(xiàng)目i的實(shí)際評(píng)分。

輸入?IMDB電影信息網(wǎng)絡(luò)，元路徑集L={P1，P2，P3，P4}，目標(biāo)用戶u0;

輸出?對(duì)目標(biāo)用戶的TopN推薦結(jié)果。

1）通過(guò)IMDB電影數(shù)據(jù)集中5種節(jié)點(diǎn)、4種邊類(lèi)型構(gòu)建異質(zhì)信息網(wǎng)絡(luò)，提取兩個(gè)用戶之間長(zhǎng)度在4以內(nèi)的元路徑集P。

2）為了提高查詢效率本文引用文獻(xiàn)[17]中剪枝策略。從L中任選一條元路徑pi，以UMAM為例，如果兩個(gè)用戶沒(méi)有看同一個(gè)演員演的電影則必定不相關(guān)，返回步驟2）重新選擇，否則執(zhí)行步驟3）。

3）構(gòu)建用戶電影評(píng)分矩陣Rm×n，用式（3）求用戶相關(guān)性。

4）根據(jù)式（4），利用節(jié)點(diǎn)主題與用戶評(píng)分共同度量用戶相關(guān)性。

5）根據(jù)式（6）的DPRel相關(guān)性度量方法求取基于元路徑的相關(guān)度。

6）根據(jù)式（7）計(jì)算總的相關(guān)度。

7）根據(jù)歸一化方法獲取權(quán)重，擬合4條元路徑相關(guān)性，獲得最終的用戶相關(guān)度。

8）利用步驟7）中的用戶相關(guān)度選擇與其最相似的K個(gè)鄰居作為目標(biāo)用戶u的最近鄰居集Neighbor（u）。

9）根據(jù)目標(biāo)用戶的相似用戶集合，用式（11）為目標(biāo)用戶的未知項(xiàng)目預(yù)測(cè)評(píng)分，最后生成TopN推薦集。

u，i=u+∑ v∈Neighbor（u）Sim（u，v）（rv，i-v）∑ v∈Neighbor（u）Sim（u，v）（11）

假設(shè)該網(wǎng)絡(luò)中有n個(gè)用戶，m部電影，k表示實(shí)例路徑數(shù)，融合LDA與元路徑分析的用戶相關(guān)性度量方法復(fù)雜度分析如下：步驟3）～4）過(guò)程計(jì)算用戶興趣偏好，假設(shè)有t（t

3?實(shí)驗(yàn)分析

3.1?數(shù)據(jù)集和實(shí)驗(yàn)環(huán)境描述

本文使用themoviesdataset數(shù)據(jù)集，它是IMDB電影數(shù)據(jù)集的子集。該數(shù)據(jù)集是從https：//www.kaggle.com/rounakbanik/themoviesdataset網(wǎng)站下載的。該數(shù)據(jù)集包含了從1995—-2017年發(fā)布的電影信息。本文實(shí)驗(yàn)使用的IMDB電影數(shù)據(jù)集包含45-000部電影、19種電影類(lèi)型、5-741名演員、10-656名用戶、1-398名導(dǎo)演和16-198個(gè)鏈接。

根據(jù)實(shí)驗(yàn)需要將整個(gè)實(shí)驗(yàn)數(shù)據(jù)集進(jìn)一步地劃分為訓(xùn)練集和測(cè)試集，隨機(jī)抽取數(shù)據(jù)集75%作為訓(xùn)練集，另外25%作為測(cè)試集。本文的實(shí)驗(yàn)環(huán)境：操作系統(tǒng)為 Windows XP，處理器為Intel core i5和8GB內(nèi)存，代碼使用Python語(yǔ)言實(shí)現(xiàn)。

3.2?評(píng)價(jià)指標(biāo)

本文選取3個(gè)在推薦方法測(cè)評(píng)中應(yīng)用最為廣泛的評(píng)價(jià)指標(biāo)：準(zhǔn)確率（precision）、召回率（recall）和綜合值F，如式（12）～（14）所示：

Precision=∑u∈UR（u）∩T（u）∑u∈UR（u）（12）

Recall=∑u∈UR（u）∩T（u）∑u∈UT（u）（13）

F=2×Precision×RecallPrecision+Recall（14）

其中：R（u）是用戶在訓(xùn)練集上的行為給用戶給出的推薦列表，而T（u）是用戶在測(cè)試集上的行為列表。

3.3?實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文提出的融合LDA與元路徑分析的用戶相關(guān)性度量方法的有效性，將它與當(dāng)前主流用戶相關(guān)性度量方法：ULRCF方法[18]與PathSim方法[15]進(jìn)行比較。圖4描述了隨著TopN（5，10，20）的變化，各方法的準(zhǔn)確率、召回率及綜合指標(biāo)F值的變化趨勢(shì)。

由圖4（a）和圖4（b）可以看出，無(wú)論N取何值，ULRCF方法的準(zhǔn)確率、召回率普遍低于替他推薦方法，原因是該方法基于傳統(tǒng)協(xié)同過(guò)濾推薦算法，并結(jié)合LDA主題模型挖掘電影本身特征來(lái)生成推薦列表，但由于電影本身特征提取的精確度原因，導(dǎo)致推薦效果不太理想;PathSim基于多條元路徑獲取更多用戶信息，進(jìn)而計(jì)算用戶相關(guān)度，在一定程度上化解了協(xié)同過(guò)濾推薦中數(shù)據(jù)稀疏的問(wèn)題，進(jìn)而得到相對(duì)較高的準(zhǔn)確率和召回率，說(shuō)明引入元路徑可以在很大程度上提高推薦質(zhì)量;而本文提出的LPUSim相關(guān)性度量方法，一方面引入LDA主題模型，挖掘了電影本身所攜帶的語(yǔ)義信息，考慮了用戶主題偏好，另一方面引入元路徑來(lái)度量用戶的相關(guān)性，并且對(duì)多條元路徑進(jìn)行加權(quán)整合后能夠更加全面度量用戶相關(guān)性，因此準(zhǔn)確率、召回率指標(biāo)上的表現(xiàn)都遠(yuǎn)遠(yuǎn)超過(guò)了其他兩個(gè)方法。從圖4（a）可看出，所提方法在最近鄰居數(shù)為10時(shí)，取得最大的準(zhǔn)確率，推薦效果最好，充分說(shuō)明綜合元路徑分析和引入LDA模型可以顯著提高推薦的質(zhì)量。而圖4（c）也進(jìn)一步證實(shí)了本文所提方法的可行性，確實(shí)在一定程度上改善了推薦系統(tǒng)的推薦效果。

[12]? KUSUMOTO M， MAEHARA T， KAWARABAYASHI K I. Scalable similarity search for SimRank[C]// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2014： 325-336.

[13]? HUANG Z， ZHENG Y， CHENG R， et al. Meta structure： computing relevance in large heterogeneous information networks[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2016： 1595-1604.

[14]? MENG C， CHENG R， MANIU S， et al. Discovering metapaths in large heterogeneous information networks[C]// Proceedings of the 24th International Conference on World Wide Web. Republic and Canton of Geneva， Switzerland： International World Wide Web Conferences Steering Committee， 2015：754-764.

[15]? SUN Y， HAN J， YAN X， et a. PathSim： meta pathbased topKsimilarity search in heterogeneous information networks[J]. Proceedings of the VLDB Endowment， 2011， 4（11）： 992-1003.

[16]? 丁少衡，姬東鴻，王路路. 基于用戶屬性和評(píng)分的協(xié)同過(guò)濾推薦算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2015， 36（2）：487-491. （DING S H， JI D H， WANG L L， et al. Collaborative filtering recommendation algorithm based on user attributes and scores[J]. Computer Engineering and Design， 2015， 36（2）：487-491.）

[17]? 邱慶羽，李婧，全兵，等. 基于文獻(xiàn)信息網(wǎng)絡(luò)語(yǔ)義特征的相似性搜索[J]. 計(jì)算機(jī)應(yīng)用， 2018， 38（5）：1327-1333. （QIU Q Y， LI J， QUAN B， et al. Similarity search based on semantic features of bibliographic information network[J]. Journal of Computer Applications， 2018， 38（5）：1327-1333.）

[18]? 高娜，楊明. 嵌入LDA主題模型的協(xié)同過(guò)濾推薦算法[J]. 計(jì)算機(jī)科學(xué)， 2016， 43（3）：57-61. （GAO N， YANG M. Topic model embedded in collaborative filtering recommendation algorithm[J]. Computer Science， 2016， 43（3）：57-61.）

This work is partially supported by the National Natural Science Foundation of China （71771110）， theSocial Science Planning Foundation of Liaoning Province of China （L18AGL007）， the Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education in Jilin University （93K172018K01）.

XU Hongyan， born in 1972， M. S.， associate professor. Her research interests include deep Web， personal recommendation， data mining.

WANG Dan， born in 1994， M. S. candidate. Her research interests include personal recommendation， data mining.

WANG Fuhai， born in 1990， M.S. candidate. His research interests include deep learning， personal recommendation.

WANG Rongbing， born in 1979， Ph. D.， associate professor. His research interests include big data analysis， cloud computing.