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

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

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

2 相關(guān)概念

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

給定一個(gè)有向圖G=(V,E,W)。G里每一個(gè)對(duì)象v∈V是一個(gè)特殊的對(duì)象類型φ(v)∈A，A 是對(duì)象類型的集合；每一個(gè)連邊e∈E是一個(gè)特殊的鏈接類型ψ(e)∈R，R 是鏈接類型的集合；每一個(gè)屬性值w∈W是一個(gè)特殊的屬性值集合θ(w)∈W 。如果對(duì)象類型數(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)來(lái)表示網(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ò)模式上，用來(lái)描述異質(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。用戶之間可以通過(guò)不同的元路徑連接，不同的元路徑包含不同的語(yǔ)義[17-18]。在圖1 的加權(quán)異質(zhì)信息網(wǎng)絡(luò)中，元路徑User→Movie→User和 元 路 徑User→Movie→Type→Movie→User所 連接的用戶之間具有不同的語(yǔ)義關(guān)系，前者將看過(guò)相同電影的用戶連接起來(lái)，后者將看過(guò)相同電影類型的用戶連接起來(lái)。

2.2 矩陣分解模型

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

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

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

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

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

3.1 用戶之間非對(duì)稱相似度的確定

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

Table 1 Main symbols used in this paper表1 本文用到的主要符號(hào)

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

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

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

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

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

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

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

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

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

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

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

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

3.3 利用矩陣分解模型預(yù)測(cè)未知評(píng)分

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

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

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

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

3.4 算法流程

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

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

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

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

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

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

步驟5利用式（11）預(yù)測(cè)評(píng)分。

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

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

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

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

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

MAE的定義如下：

其中，|Rtest|表示測(cè)試集中的評(píng)分?jǐn)?shù)量。

RMSE的定義如下：

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

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

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

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

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

（4）基于語(yǔ)義路徑的個(gè)性化推薦算法（semantic path based recommendation，SemRec[4]）。該方法在利用PathSim 計(jì)算用戶相似性的基礎(chǔ)上，考慮不同元路徑的權(quán)重對(duì)評(píng)分結(jié)果的影響，通過(guò)學(xué)習(xí)權(quán)重，得到不同元路徑對(duì)用戶評(píng)分影響的權(quán)值，最后預(yù)測(cè)評(píng)分。本文選取其中利用單條元路徑計(jì)算用戶相似度的算法SemRecSgl和針對(duì)所有用戶的統(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 份作為測(cè)試集，剩余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的不同取值對(duì)評(píng)價(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é)同過(guò)濾算法和概率矩陣分解算法，說(shuō)明通過(guò)引入額外的屬性信息確實(shí)有利于推薦算法準(zhǔn)確性的提升。而且，對(duì)比基于單條元路徑的異質(zhì)信息網(wǎng)絡(luò)算法（SemRecSgl算法）、基于多條元路徑的異質(zhì)信息網(wǎng)絡(luò)算法（SemRecAll算法和本文算法）在各個(gè)數(shù)據(jù)集上都有比較好的表現(xiàn)。另外對(duì)比SemRecAll算法，由于在計(jì)算用戶相似度時(shí)，本文算法考慮到用戶之間的非對(duì)稱情況，可以更加客觀地反映用戶之間的相似關(guān)系；而且與SemRecAll算法不同，本文算法將不同的元路徑考慮為不同的權(quán)重，體現(xiàn)出不同元路徑對(duì)于用戶相似度的影響程度，使得融合不同元路徑的相似度結(jié)果更加全面。在評(píng)價(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 的取值對(duì)MAE 的影響

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

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

5 結(jié)束語(yǔ)

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