非對稱的異質(zhì)信息網(wǎng)絡(luò)推薦算法*

趙 傳，張凱涵，梁吉業(yè)+

1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原030006

2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原030006

3.山西大學(xué) 智能信息處理研究所，太原030006

1 引言

推薦系統(tǒng)是大數(shù)據(jù)時(shí)代解決信息過載問題的重要手段之一[1]。在眾多關(guān)于推薦系統(tǒng)的研究工作中，異質(zhì)信息網(wǎng)絡(luò)作為一種有效的信息建模方法[2]，逐漸受到人們的關(guān)注。異質(zhì)信息網(wǎng)絡(luò)可以通過構(gòu)建多種類型的實(shí)體以及實(shí)體之間的聯(lián)系[3]表示各種數(shù)據(jù)信息，將多種不同的數(shù)據(jù)信息利用到推薦任務(wù)中可以帶來更好的推薦效果[4-5]，因此有越來越多的推薦工作利用異質(zhì)信息網(wǎng)絡(luò)解決[6-7]。基于元路徑進(jìn)行相似性度量是最重要和基礎(chǔ)的一個(gè)方向。目前基于元路徑已經(jīng)開展了大量的研究工作。例如，Sun 等人[8]通過抽取兩個(gè)用戶之間對稱的元路徑度量用戶之間的相似性，提出PathSim 算法；Shi 等人[9]提出基于元路徑的雙向隨機(jī)游走算法HeteSim 度量網(wǎng)絡(luò)中任意節(jié)點(diǎn)之間的相關(guān)性；Lao 等人[10]利用在元路徑上的隨機(jī)游走度量網(wǎng)絡(luò)里任意實(shí)體之間的相似性。

上述基于元路徑計(jì)算用戶相似度的算法均假設(shè)用戶之間的相似度滿足對稱性，而在實(shí)際中利用對稱性相似度計(jì)算方法有時(shí)會(huì)導(dǎo)致用戶相似度存在誤差，比如當(dāng)用戶u與用戶v對物品的評分向量分別為(2,5,4,5,4,1)和(2,-,-,-,-,1)時(shí)（“-”表示用戶未對物品進(jìn)行評分），傳統(tǒng)的對稱性相似度計(jì)算方法根據(jù)共同評分項(xiàng)會(huì)得出用戶u與用戶v具有高相似度的結(jié)果，但用戶v對于其他未評分物品的興趣程度不一定會(huì)與用戶u相同。因此，在這種情況下，用戶間的相似度是非對稱的[11]。另外，基于元路徑度量用戶相似度時(shí)，多條不同的元路徑會(huì)得到不同的相似度[12]，元路徑從不同的角度反映了用戶之間的聯(lián)系，因此為了統(tǒng)一用戶之間的相似程度，有必要對不同的元路徑賦予不同的權(quán)重，通過權(quán)重融合不同元路徑的相似度結(jié)果，能夠更加準(zhǔn)確地體現(xiàn)用戶之間的關(guān)系。

為此，本文在計(jì)算用戶間相似度時(shí)，一方面考慮用戶間相似度的非對稱性；另一方面考慮用戶間不同元路徑的權(quán)重，以準(zhǔn)確度量用戶間的相似度。首先利用用戶的評分信息和物品的屬性信息構(gòu)建異質(zhì)信息網(wǎng)絡(luò)，通過考慮用戶之間共同評分項(xiàng)在已評分項(xiàng)中占的比例，即非對稱系數(shù)，計(jì)算用戶間的非對稱相似度；然后根據(jù)元路徑的特征計(jì)算不同元路徑的權(quán)重，權(quán)重用于融合不同元路徑的相似度結(jié)果，得到用戶總的相似度矩陣；最后利用矩陣分解模型將評分矩陣和相似度矩陣進(jìn)行聯(lián)合分解，計(jì)算用戶和物品的潛在特征向量，預(yù)測未知評分。在數(shù)據(jù)集MovieLens 的三個(gè)不同規(guī)模的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)比較，結(jié)果顯示本文所提算法在評價(jià)指標(biāo)均方根誤差和平均絕對誤差上優(yōu)于已有算法。

2 相關(guān)概念

2.1 加權(quán)異質(zhì)信息網(wǎng)絡(luò)

給定一個(gè)有向圖G=(V,E,W)。G里每一個(gè)對象v∈V是一個(gè)特殊的對象類型φ(v)∈A，A 是對象類型的集合；每一個(gè)連邊e∈E是一個(gè)特殊的鏈接類型ψ(e)∈R，R 是鏈接類型的集合；每一個(gè)屬性值w∈W是一個(gè)特殊的屬性值集合θ(w)∈W 。如果對象類型數(shù)量|A|＞1 或者關(guān)系類型數(shù)量|R|＞1，該網(wǎng)絡(luò)叫作異質(zhì)信息網(wǎng)絡(luò)[13]，如果權(quán)重?cái)?shù)量|W|＞1，該網(wǎng)絡(luò)叫作加權(quán)異質(zhì)信息網(wǎng)絡(luò)[14]。圖1 為一個(gè)包含用戶、電影、電影類型、導(dǎo)演的加權(quán)異質(zhì)信息網(wǎng)絡(luò)。

網(wǎng)絡(luò)模式是異質(zhì)信息網(wǎng)絡(luò)的模板[15]。用δ=(A,R)來表示網(wǎng)絡(luò)模式。圖2 為圖1 的網(wǎng)絡(luò)模式圖。

Fig.1 Diagram of weighted heterogeneous information network圖1 加權(quán)異質(zhì)信息網(wǎng)絡(luò)圖

Fig.2 Network schema圖2 網(wǎng)絡(luò)模式圖

元路徑是異質(zhì)信息網(wǎng)絡(luò)最重要的概念，它定義在網(wǎng)絡(luò)模式上，用來描述異質(zhì)信息網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)間的不同路徑類型[16]。它可以表示為P=A1→A2→…→Al→Al+1，A1,A2,…,Al+1表示節(jié)點(diǎn)類型。P-1=Al+1→Al→…→A2→A1代表相反的元路徑。在兩條元路徑P1=A1→A2→…→Al→Al+1和P2=A′1→A′2→…→A′l→A′l+1中，如果Al+1=A′1，則兩條元路徑可以合并為一條元路徑，表示為P=P1P2，比如元路徑User→Movie和元路徑Movie→User連接成元路徑User→Movie→User。用戶之間可以通過不同的元路徑連接，不同的元路徑包含不同的語義[17-18]。在圖1 的加權(quán)異質(zhì)信息網(wǎng)絡(luò)中，元路徑User→Movie→User和 元 路 徑User→Movie→Type→Movie→User所 連接的用戶之間具有不同的語義關(guān)系，前者將看過相同電影的用戶連接起來，后者將看過相同電影類型的用戶連接起來。

2.2 矩陣分解模型

在推薦系統(tǒng)里，矩陣分解模型的基本思想是將用戶-物品的評分矩陣R分解成兩個(gè)低維潛在特征矩陣U和V，通過U和V的點(diǎn)積可以得到一個(gè)擬合評分矩陣，從而實(shí)現(xiàn)評分預(yù)測。矩陣分解模型是通過最小化目標(biāo)函數(shù)L(R,U,V)得到低維特征矩陣：

式中，Iij是一個(gè)指示函數(shù)，如果用戶i對物品j有過評分，為1，否則為0。U∈?n×d，V∈?m×d，d是用戶和物品的潛在特征維度，d?min(n,m)，λU和λV是正則化系數(shù)，通過隨機(jī)梯度下降可以對目標(biāo)函數(shù)進(jìn)行求解。

3 基于異質(zhì)信息網(wǎng)絡(luò)的推薦算法

本文融合評分信息與物品屬性信息，綜合考慮元路徑的權(quán)重與非對稱相似性這兩個(gè)因素對用戶相似度的影響，提出一種基于異質(zhì)信息網(wǎng)絡(luò)的推薦算法。通過計(jì)算用戶和物品的潛在特征表示，從而預(yù)測未知評分。本章將重點(diǎn)分析以下3 個(gè)問題：（1）如何基于元路徑計(jì)算用戶之間的非對稱相似度；（2）如何度量不同元路徑的權(quán)重；（3）如何利用評分信息與用戶相似度信息預(yù)測未知評分。圖3 為本文的算法流程圖，表1 為本文使用的主要符號。

Fig.3 Flow chart of algorithm圖3 算法流程圖

3.1 用戶之間非對稱相似度的確定

本文首先利用均方差（mean squared difference，MSD）[19]相似度公式計(jì)算用戶之間的對稱相似度；然后根據(jù)非對稱系數(shù)，計(jì)算用戶之間的非對稱相似度。具體包含以下兩步：

Table 1 Main symbols used in this paper表1 本文用到的主要符號

（1）由于用戶之間在不同的物品上存在評分差異，評分差異的大小反映了用戶之間的相似程度，因此本文利用均方差相似度公式通過用戶之間的評分差異來計(jì)算用戶相似度，在給定元路徑P的基礎(chǔ)上，計(jì)算用戶u和用戶v之間的對稱相似度：

（2）本文把共同評分項(xiàng)在用戶已評分項(xiàng)中占的比例定義為非對稱系數(shù)，該系數(shù)反映了上述對稱相似度對于用戶的參考程度。用戶u對v在元路徑P上的非對稱系數(shù)為：

其中，Iu代表用戶u的評分項(xiàng)。

根據(jù)非對稱系數(shù)，用戶u對v的非對稱相似度：

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

由于從不同元路徑角度計(jì)算得到的用戶相似度不同，為了相似度結(jié)果的統(tǒng)一，本文從元路徑的特點(diǎn)出發(fā)，賦予各個(gè)元路徑不同的權(quán)重。針對權(quán)重的確定，本文從兩個(gè)角度進(jìn)行分析：

（1）元路徑的長度。元路徑的長度指的是該條元路徑的邊數(shù)。直觀上說，短的元路徑比長的元路徑具有更高的權(quán)重，因?yàn)槎痰脑窂绞箤ο笾g關(guān)系更加直接，元路徑應(yīng)該被賦予更高的權(quán)重。具體用公式表示為：

其中，L代表所有的元路徑的集合，len(P)代表元路徑P的長度。

（2）元路徑的路徑數(shù)。元路徑的路徑數(shù)指的是在異質(zhì)信息網(wǎng)絡(luò)內(nèi)滿足該條元路徑條件的路徑數(shù)量。路徑數(shù)多的元路徑代表對象之間的聯(lián)系更密切，元路徑權(quán)重應(yīng)該更高。用公式表示為：

其中，num(P)代表元路徑P的路徑數(shù)。

根據(jù)以上兩方面，利用下式計(jì)算元路徑P的權(quán)重：

結(jié)合不同的元路徑權(quán)重和不同元路徑計(jì)算的相似度結(jié)果，計(jì)算用戶之間的相似度：

3.3 利用矩陣分解模型預(yù)測未知評分

已知用戶-物品的評分信息和用戶-用戶的相似度信息，本文算法利用矩陣分解模型，同時(shí)將評分矩陣R和相似度矩陣S進(jìn)行分解，得到用戶特征矩陣U、物品特征矩陣V、用戶相似特征矩陣Z。模型的目標(biāo)函數(shù)為：

由于評分信息的取值范圍為[1,5]，相似度信息的取值范圍為[0,1]，為了統(tǒng)一評分信息和相似度信息的取值范圍，本文利用函數(shù)f(x)將評分信息限制在[0,1]之間，f(x)=(x-1)/(Rmax-1) 。為了與上述取值范圍統(tǒng)一，利用函數(shù)g(x)約束在[0,1]之間，g(x)=1/(1+exp(-x)) 。λS是平衡評分信息和相似度信息的系數(shù)，若λS=0，表示矩陣分解模型只利用評分信息，若λS＞0，表示矩陣分解模型同時(shí)考慮評分信息和相似度信息。

對目標(biāo)函數(shù)進(jìn)行求導(dǎo)，分別得到U、V、Z的梯度：

其中，g′(x)=exp(x)/(1+exp(x))2，代表g(x)的導(dǎo)函數(shù)。用隨機(jī)梯度下降方法對U、V、Z進(jìn)行迭代更新。經(jīng)過有限次數(shù)迭代后，利用已經(jīng)更新的用戶潛在特征矩陣U和物品潛在特征矩陣V預(yù)測用戶u對物品i的預(yù)測評分：

3.4 算法流程

基于以上對算法的介紹，本文所提算法描述如下：

輸入：用戶-物品評分矩陣R，評分矩陣和相似度矩陣的平衡因子λS，特征維度d，隨機(jī)梯度下降學(xué)習(xí)率α，正則項(xiàng)系數(shù)λU、λV、λZ。

步驟1利用式（2）～式（4）計(jì)算不同元路徑下用戶之間的非對稱相似度。

步驟2根據(jù)式（5）～式（7）計(jì)算每條元路徑的權(quán)重。

步驟3利用式（8）結(jié)合不同元路徑的相似度信息，得到用戶之間總的相似度矩陣。

步驟4根據(jù)式（9）、式（10），利用隨機(jī)梯度下降法對用戶潛在特征矩陣U和物品潛在特征矩陣V進(jìn)行迭代更新。

步驟5利用式（11）預(yù)測評分。

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

為驗(yàn)證本文所提算法的有效性，在數(shù)據(jù)集Movie-Lens100K、MovieLens1M 和MovieLens10M 上進(jìn)行實(shí)驗(yàn)，并與其他推薦算法進(jìn)行比較分析，最后通過實(shí)驗(yàn)結(jié)果分析本文所提算法中參數(shù)的選取對實(shí)驗(yàn)性能的影響。

4.1 數(shù)據(jù)集

本文用到的數(shù)據(jù)集都包括用戶-電影評分信息，以及用戶和電影的屬性信息，包括用戶性別、用戶年齡、用戶職業(yè)、電影名稱、電影類別、上映時(shí)間等，評分值在1 到5 之間，且每個(gè)用戶至少評分過20 部電影。MovieLens100K 數(shù)據(jù)集包含了943 位用戶對1 682 部電影的100 000 條評分信息，MovieLens1M 數(shù)據(jù)集中包含6 040 位用戶對3 900 部電影的1 000 209條評分?jǐn)?shù)據(jù)。MovieLens10M 數(shù)據(jù)集包含71 567 位用戶對10 681 部電影的10 000 054 條評分，本文從中隨機(jī)抽取10 000 名用戶對10 681 個(gè)物品的評分記錄作為訓(xùn)練集和測試集的數(shù)據(jù)。表2 統(tǒng)計(jì)這3 個(gè)數(shù)據(jù)集的相關(guān)信息。

Table 2 Statistic information of 3 datasets表2 3 個(gè)數(shù)據(jù)集的統(tǒng)計(jì)信息

4.2 評價(jià)指標(biāo)

本文在衡量推薦性能時(shí)，為體現(xiàn)預(yù)測評分的準(zhǔn)確度，采用推薦系統(tǒng)中廣泛使用的平均絕對誤差（mean absolute error，MAE）和均方根誤差（root mean squared error，RMSE）兩個(gè)評價(jià)指標(biāo)。這兩個(gè)評價(jià)指標(biāo)的值越小表示預(yù)測效果越好。

MAE的定義如下：

其中，|Rtest|表示測試集中的評分?jǐn)?shù)量。

RMSE的定義如下：

4.3 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證本文算法的有效性，在MAE、RMSE兩個(gè)指標(biāo)上，同以下算法進(jìn)行比較：

（1）基于用戶的協(xié)同過濾推薦算法（user-based collaborative filtering，UCF）。通過預(yù)先定義的相似度度量方法計(jì)算用戶的相似用戶集合，根據(jù)相似用戶，計(jì)算出目標(biāo)用戶對目標(biāo)物品的預(yù)測評分。

（2）基于物品的協(xié)同過濾推薦算法（item-based collaborative filtering，ICF）。與UCF 類似，根據(jù)預(yù)先定義的相似度度量方法計(jì)算物品之間的相似度，通過用戶已評分的物品和目標(biāo)物品的相似關(guān)系，預(yù)測用戶對目標(biāo)物品的評分。

（3）基于概率矩陣分解的推薦算法（probabilistic matrix factorization，PMF）[20]。它是以用戶-項(xiàng)目評分矩陣為基準(zhǔn)，利用矩陣分解模型計(jì)算用戶和項(xiàng)目的潛在特征表示，通過這兩個(gè)潛在特征表示的點(diǎn)積，可以得到對原始評分矩陣的一個(gè)擬合矩陣，從而對未知的評分進(jìn)行預(yù)測。

（4）基于語義路徑的個(gè)性化推薦算法（semantic path based recommendation，SemRec[4]）。該方法在利用PathSim 計(jì)算用戶相似性的基礎(chǔ)上，考慮不同元路徑的權(quán)重對評分結(jié)果的影響，通過學(xué)習(xí)權(quán)重，得到不同元路徑對用戶評分影響的權(quán)值，最后預(yù)測評分。本文選取其中利用單條元路徑計(jì)算用戶相似度的算法SemRecSgl和針對所有用戶的統(tǒng)一權(quán)重學(xué)習(xí)算法SemRecAll進(jìn)行比較。

本文算法中，用戶和項(xiàng)目的潛在特征維度d設(shè)置為5，λS值設(shè)置為15。λU=λV=λZ=0.001，隨機(jī)梯度下降的學(xué)習(xí)率α=0.001。實(shí)驗(yàn)采用五折交叉驗(yàn)證方法，將數(shù)據(jù)集隨機(jī)分為5 份，每次取其中1 份作為測試集，剩余4 份作為訓(xùn)練集，最終結(jié)果為5 次實(shí)驗(yàn)結(jié)果的平均值。本文選取的元路徑是User→Movie→User和User→Movie→Type→Movie→User。

4.4 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果如表3～表5 所示。參數(shù)λS的不同取值對評價(jià)指標(biāo)MAE和RMSE的影響如圖4、圖5 所示。

Table 3 Experimental results on dataset MovieLens100K表3 在數(shù)據(jù)集MovieLens100K 上的實(shí)驗(yàn)結(jié)果

4.5 實(shí)驗(yàn)分析

由表3～表5 可以看到，基于異質(zhì)信息網(wǎng)絡(luò)的SemRecAll算法和SemRecSgl算法以及本文算法在各數(shù)據(jù)集上的表現(xiàn)均優(yōu)于傳統(tǒng)的協(xié)同過濾算法和概率矩陣分解算法，說明通過引入額外的屬性信息確實(shí)有利于推薦算法準(zhǔn)確性的提升。而且，對比基于單條元路徑的異質(zhì)信息網(wǎng)絡(luò)算法（SemRecSgl算法）、基于多條元路徑的異質(zhì)信息網(wǎng)絡(luò)算法（SemRecAll算法和本文算法）在各個(gè)數(shù)據(jù)集上都有比較好的表現(xiàn)。另外對比SemRecAll算法，由于在計(jì)算用戶相似度時(shí)，本文算法考慮到用戶之間的非對稱情況，可以更加客觀地反映用戶之間的相似關(guān)系；而且與SemRecAll算法不同，本文算法將不同的元路徑考慮為不同的權(quán)重，體現(xiàn)出不同元路徑對于用戶相似度的影響程度，使得融合不同元路徑的相似度結(jié)果更加全面。在評價(jià)指標(biāo)MAE和RMSE上要小于SemRecAll算法。

Table 4 Experimental results on dataset MovieLens1M表4 在數(shù)據(jù)集MovieLens1M 上的實(shí)驗(yàn)結(jié)果

Table 5 Experimental results on dataset MovieLens10M表5 在數(shù)據(jù)集MovieLens10M 上的實(shí)驗(yàn)結(jié)果

Fig.4 Influence of λS on MAE圖4 λS 的取值對MAE 的影響

Fig.5 Influence of λS on RMSE圖5 λS 的取值對RMSE 的影響

從圖4、圖5 可以看到，λS=0 時(shí)表示只利用評分信息。隨著用戶相似關(guān)系的引入，λS＞0 時(shí)，推薦效果逐漸提升，但在λS＞15 后推薦效果有所下降，說明適當(dāng)引入相似度信息有利于推薦效果的提升，因此本文選取15 作為λS的取值。

5 結(jié)束語

本文提出了一種基于異質(zhì)信息網(wǎng)絡(luò)的推薦算法，該算法通過不同的元路徑計(jì)算用戶的非對稱相似度，并且考慮將不同元路徑的相似度結(jié)果加權(quán)融合，得到用戶之間總的相似度信息。最后利用矩陣分解方法融合評分信息和相似度信息，計(jì)算用戶對未評分物品的預(yù)測評分。實(shí)驗(yàn)結(jié)果表明，利用非對稱性處理用戶相似關(guān)系并且將相似度結(jié)果加權(quán)融合有助于推薦效果的提升。未來工作中，將考慮針對不同的用戶引入不同的元路徑權(quán)重，從用戶角度進(jìn)一步提升相似度的準(zhǔn)確性。