非對稱的異質信息網絡推薦算法*

趙 傳，張凱涵，梁吉業+

1.山西大學 計算機與信息技術學院，太原030006

2.山西大學 計算智能與中文信息處理教育部重點實驗室，太原030006

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

1 引言

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

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

為此，本文在計算用戶間相似度時，一方面考慮用戶間相似度的非對稱性；另一方面考慮用戶間不同元路徑的權重，以準確度量用戶間的相似度。首先利用用戶的評分信息和物品的屬性信息構建異質信息網絡，通過考慮用戶之間共同評分項在已評分項中占的比例，即非對稱系數，計算用戶間的非對稱相似度；然后根據元路徑的特征計算不同元路徑的權重，權重用于融合不同元路徑的相似度結果，得到用戶總的相似度矩陣；最后利用矩陣分解模型將評分矩陣和相似度矩陣進行聯合分解，計算用戶和物品的潛在特征向量，預測未知評分。在數據集MovieLens 的三個不同規模的數據集上進行實驗比較，結果顯示本文所提算法在評價指標均方根誤差和平均絕對誤差上優于已有算法。

2 相關概念

2.1 加權異質信息網絡

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

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

Fig.1 Diagram of weighted heterogeneous information network圖1 加權異質信息網絡圖

Fig.2 Network schema圖2 網絡模式圖

元路徑是異質信息網絡最重要的概念，它定義在網絡模式上，用來描述異質信息網絡中任意兩節點間的不同路徑類型[16]。它可以表示為P=A1→A2→…→Al→Al+1，A1,A2,…,Al+1表示節點類型。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 的加權異質信息網絡中，元路徑User→Movie→User和 元 路 徑User→Movie→Type→Movie→User所 連接的用戶之間具有不同的語義關系，前者將看過相同電影的用戶連接起來，后者將看過相同電影類型的用戶連接起來。

2.2 矩陣分解模型

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

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

3 基于異質信息網絡的推薦算法

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

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

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

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

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

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

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

其中，Iu代表用戶u的評分項。

根據非對稱系數，用戶u對v的非對稱相似度：

3.2 元路徑權重的確定

由于從不同元路徑角度計算得到的用戶相似度不同，為了相似度結果的統一，本文從元路徑的特點出發，賦予各個元路徑不同的權重。針對權重的確定，本文從兩個角度進行分析：

（1）元路徑的長度。元路徑的長度指的是該條元路徑的邊數。直觀上說，短的元路徑比長的元路徑具有更高的權重，因為短的元路徑使對象之間關系更加直接，元路徑應該被賦予更高的權重。具體用公式表示為：

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

（2）元路徑的路徑數。元路徑的路徑數指的是在異質信息網絡內滿足該條元路徑條件的路徑數量。路徑數多的元路徑代表對象之間的聯系更密切，元路徑權重應該更高。用公式表示為：

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

根據以上兩方面，利用下式計算元路徑P的權重：

結合不同的元路徑權重和不同元路徑計算的相似度結果，計算用戶之間的相似度：

3.3 利用矩陣分解模型預測未知評分

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

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

對目標函數進行求導，分別得到U、V、Z的梯度：

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

3.4 算法流程

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

輸入：用戶-物品評分矩陣R，評分矩陣和相似度矩陣的平衡因子λS，特征維度d，隨機梯度下降學習率α，正則項系數λU、λV、λZ。

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

步驟2根據式（5）～式（7）計算每條元路徑的權重。

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

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

步驟5利用式（11）預測評分。

4 實驗及結果分析

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

4.1 數據集

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

Table 2 Statistic information of 3 datasets表2 3 個數據集的統計信息

4.2 評價指標

本文在衡量推薦性能時，為體現預測評分的準確度，采用推薦系統中廣泛使用的平均絕對誤差（mean absolute error，MAE）和均方根誤差（root mean squared error，RMSE）兩個評價指標。這兩個評價指標的值越小表示預測效果越好。

MAE的定義如下：

其中，|Rtest|表示測試集中的評分數量。

RMSE的定義如下：

4.3 實驗設置

為了驗證本文算法的有效性，在MAE、RMSE兩個指標上，同以下算法進行比較：

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

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

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

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

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

4.4 實驗結果

實驗結果如表3～表5 所示。參數λS的不同取值對評價指標MAE和RMSE的影響如圖4、圖5 所示。

Table 3 Experimental results on dataset MovieLens100K表3 在數據集MovieLens100K 上的實驗結果

4.5 實驗分析

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

Table 4 Experimental results on dataset MovieLens1M表4 在數據集MovieLens1M 上的實驗結果

Table 5 Experimental results on dataset MovieLens10M表5 在數據集MovieLens10M 上的實驗結果

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

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

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

5 結束語

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