融合雙重語義相似度的混合協同過濾推薦算法

張茂宇，李海明

(上海電力大學 計算機科學與技術學院，上海 201306)

0 引 言

傳統的推薦算法主要包括基于協同過濾的推薦、基于內容的推薦和混合推薦[1]。其中協同過濾推薦算法是研究最多且推薦效果最好的算法之一[2]。協同過濾算法的優勢在于不需要像基于內容那樣對物品進行復雜的特征提取與建模[3]。而其缺點是太過依賴評分數據，且缺乏考慮用戶與物品自身的特征，當評分數據稀疏時推薦性能則會下降。文獻[4]將社區結構和個人興趣與矩陣分解模型進行融合推薦，緩解了數據稀疏問題。文獻[5]提出了一種融合地點影響力的POI推薦算法，通過融入地理位置特征來緩解簽到數據稀疏的問題。

知識嵌入模型如TransE、TransH和TransR是將實體和關系嵌入到潛在向量中完成知識圖譜[6]。文獻[7]通過對物品知識圖譜嵌入，并融合基于語義和評分矩陣的物品相似近鄰集，來提升推薦性能。而文獻[8]直接將語義相似度與評分矩陣相似度融合，從而緩解數據稀疏問題。本文將物品語義相似度融入基于物品的協同過濾中。且提出構建用戶知識圖譜，計算用戶語義相似度并與基于用戶的協同過濾融合推薦，最后融合兩種推薦結果。

1 相關理論

1.1 協同過濾

自20世紀90年代中期以來，協同過濾推薦系統在業界已經非常流行[9]。傳統的協同過濾算法主要分為基于用戶的協同過濾[10]和基于物品的協同過濾[11]。基于用戶和基于物品是兩種類型的協同過濾，在業界和學術界都被廣泛用于解決信息超載問題[12]。協同過濾的關鍵在于相似度的計算，并據此來尋找相似近鄰的物品或用戶。而眾多的相似度計算方式中，應用最為廣泛的當屬余弦相似度[13]。

基于用戶集合和物品集合建立評分矩陣，m和n分別表示用戶和物品的個數，rui代表用戶u對物品i的評分 (1≤u≤m，1≤i≤n)， 評分矩陣如圖1所示。

物品i即可以表示為所有用戶對其評分的向量，如式(1)所示

Si=(r1i，r2i，…，rmi)T

(1)

rmi表示第m個用戶對物品i的評分，則物品余弦相似度計算公式如式(2)所示

(2)

式中：simmrt(i，j) 為物品i和j基于評分矩陣的相似度，Si和Sj分別為所有用戶對物品i和j的評分向量。

用戶u則可以表示為其對所有物品的評分向量，如式(3)所示

Ru=(ru1，ru2，…，run)T

(3)

run表示用戶u對第n個物品的評分，則用戶余弦相似度計算公如式(4)所示

(4)

式中：simurt(u，v) 為用戶u和用戶v的基于評分矩陣的相似度，Ru和Rv分別為用戶u和用戶v對所有物品的評分向量。

1.2 知識圖譜的表示學習

受到知識圖譜應用于多種任務成功的啟發，研究者們也試圖利用知識圖譜來提高推薦系統的性能[14]。知識圖譜是Google公司為提高搜索引擎性能而提出的一種概念，并且定義了知識圖譜組成結構中的三元組即“實體-關系-實體”。而知識圖譜的表示學習即知識表示則是將實體與關系映射到統一的向量空間，并且映射向量能夠很好地表示實體和關系在語義上的聯系[15]。

TransE算法作為比較經典的算法，具備計算容易和易于理解等優點。此模型直觀上是將三元組(頭實體記作h， 關系記作r， 尾實體記作t)中的關系看作是頭實體到尾實體的翻譯，通過不斷調整h、r和t， 使得 (h+r) 盡可能與t相等，即h+r≈t。 TransE如圖2所示。

圖2 TransE

如果不滿足上述的關系，我們就認為這是一個錯誤的三元組。所以可得模型的損失函數如式(5)所示

(5)

我們的目標就是讓正確的三元組距離越來越小，錯誤的三元組距離越來越大，整體三元組的損失函數如式(6)所示

(6)

式中：(h，r，t)∈M與 (h′，r，t′)∈M′分別表示正確與錯誤三元組的集合，disTrE(h，r，t) 和disTrE(h′，r，t′) 分別表示正確和錯誤三元組的損失函數，γ為常數間距。

但是TransE算法在處理一對多等自反關系時存在一定的劣勢，會導致不同的實體具有相同或者相似的向量表示。而TransH算法的核心思想是在TransE的基礎上定義一個關系的超平面Wr， 和一個關系向量dr， TransH如圖3所示。

圖3 TransH

(7)

所以整體三元組的損失函數如式(8)所示

disTrH(h′，r，t′)+γ)

(8)

式中：(h，r，t)∈M與 (h′，r，t′)∈M′分別表示正確與錯誤三元組的集合，disTrH(h，r，t) 和disTrH(h′，r，t′) 分別表示正確與錯誤三元組的損失函數，γ為常數間距。

TransE與TransH在訓練時都是采取隨機替換原則，即隨機替換正確三元組的頭實體或尾實體，如此便得到一個錯誤三元組。而為了最小化損失函數LossTrE和LossTrH， 就要使正確三元組集合即正樣本的損失函數disTrE(h，r，t) 和disTrH(h，r，t) 無限趨于0，錯誤三元組集合即負樣本的損失函數disTrE(h′，r，t′) 和disTrH(h′，r，t′) 無限趨于無窮大。

2 融合雙重語義相似度的混合協同過濾推薦

針對傳統協同過濾算法過分依賴用戶與物品的評分矩陣問題，并且缺乏考慮用戶和物品自身的特征信息。本文提出一種融合雙重語義相似度的混合協同過濾推薦算法，包含如下內容：①構建用戶知識圖譜并進行知識表示，然后獲得用戶語義向量，計算用戶語義相似度并與用戶評分矩陣相似度直接融合，據此進行基于用戶的協同過濾Top-K推薦；②構建物品知識圖譜并進行知識表示，然后獲得物品語義向量，計算物品語義相似度并與物品評分矩陣相似度直接融合，據此進行基于物品的協同過濾Top-K推薦；③最后將兩者的Top-K推薦集合進行融合。算法從用戶和物品雙重語義視角來緩解協同過濾算法面對評分數據稀疏的問題。算法流程如圖4所示。

圖4 算法流程

2.1 融合用戶語義相似度的協同過濾推薦

2.1.1 用戶語義相似度

將用戶的人口信息統計數據抽取到知識圖譜中，用戶知識圖譜如圖5所示。

圖5 用戶知識圖譜

用戶知識圖譜中的三元組示例如：“u1-Age-Under18”表示用戶u1年齡小于18歲，“u2-Gender-W”表示用戶u2性別為女。我們從圖例中可以看出用戶知識圖譜的三元組基本滿足一對一的實體對應關系，例如一個用戶基本只會對應一個年齡、一個性別和一種職業等。滿足TransE算法的優勢條件，所以我們利用TransE算法將用戶知識圖譜的實體和關系嵌入到了一個維度為λ的語義向量空間。則我們作如下定義和假設。

定義1 用戶的語義向量表示如式(9)所示

ui=(E1i，E2i，…，Edi)T

(9)

ui為用戶i的語義向量，Edi表示用戶i第d個屬性實體值的嵌入值。

假設1：用戶之間的年齡、性別和職業等屬性值越接近，則兩個用戶的相似度越高。

因此所有屬性值之間的差距，即為用戶之間的差距。因TransE算法中的損失函數計算方法是源于歐氏距離，為保持一致，我們同樣使用歐氏距離來衡量用戶屬性值之間的差距，則用戶語義向量差距的計算如式(10)所示

(10)

將其規約到(0，1]之間即為用戶語義相似度，計算如式(11)所示

(11)

simukg(i，j) 的值則表示用戶i和用戶j之間的相似度，值越小表示越不相似，越大表示越相似，為1則表示極其相似或相同。

用戶語義信息主要源于用戶自身的特征信息，例如用戶的年齡、性別、職業等，以上信息構成了用戶的語義信息。在用戶知識圖譜中這些特征信息關聯較多的話，所得用戶之間的語義向量就比較接近，相似度也會更高。

2.1.2 相似度融合

將用戶語義相似度與用戶評分矩陣相似度以線性加權求和的方式進行融合，融合計算公式如式(12)所示

simu(i，j)=α·simukg(i，j)+(1-α)simurt(i，j)

(12)

式中：simu(i，j) 表示融合之后的相似度；simukg(i，j) 表示用戶的語義相似度，計算見式(11)；simurt(i，j) 表示用戶評分矩陣的相似度，計算見式(4)。α為權重值，在[0，1]中取值，當α為0時表示未融入用戶語義相似度，α為1時表示未融入用戶評分矩陣相似度。

傳統基于用戶的協同過濾推薦算法是直接建立在用戶-物品評分矩陣上的推薦算法，所以會面臨矩陣數據稀疏問題。用戶語義相似度是站在用戶自身語義特征的角度計算用戶的相似度，不依賴于用戶與物品的交互信息，而是基于用戶自身的特征信息，其準確程度由用戶特征信息描述是否準確和全面來決定。兩種相似度的融合后能夠有效利用用戶特征信息，尋找更為準確的用戶相似近鄰集合，從而緩解傳統推薦算法面對評分矩陣稀疏的問題。

2.1.3 基于用戶的協同過濾推薦

根據融合后的用戶之間的相似度計算用戶u對一個沒有評價過的物品f的感興趣程度，計算如式(13)所示

(13)

式中：Puf為用戶u對物品f的感興趣程度，simu(u，v) 表示用戶融合后的相似度，計算見式(12)，U為用戶u的相似用戶集合，rvf為用戶v對物品f的感興趣程度或評分。

用戶之間的相似度和評分的高低都會影響目標用戶對物品的感興趣程度，最終結果越高則代表感興趣程度越高。按照式(13)來計算目標用戶對物品的感興趣程度，按照結果由高到低排序，選取Top-K物品推薦給目標用戶。

2.2 融合物品語義相似度的協同過濾推薦

2.2.1 物品語義相似度

以電影為例，將電影特征信息數據抽取到知識圖譜中，電影知識圖譜如圖6所示。

電影知識圖譜三元組示例如：“m1-Direct-d1”表示電影m1由導演d1執導，“m1-Gener-War”表示電影m1的類型為戰爭。我們從電影知識圖譜中可以看出電影三元組多為一對多的關系，例如一部電影可以有多種類型、可以有多個演員出演等。所以我們選擇TransH算法對電影知識圖譜進行知識表示。TransH算法將物品知識圖譜中實體和關系嵌入到η維的語義向量空間。則有如下定義和假設。

定義2 物品語義向量表示如式(14)所示

mi=(F1i，F2i，…，Fdi)T

(14)

mi表示物品i的語義向量，Fdi表示物品i第d個屬性所對應的向量。

定義3 物品屬性向量表示如式(15)所示

(15)

假設2：電影之間的導演、演員和類型等屬性值越接近，則兩部電影的相似度越高。

所以對應屬性值之間的差距，即為電影之間的差距。為保持與TransH算法的一致性，這里依然選擇用歐氏距離來衡量電影屬性值之的差距，計算如式(16)所示

(16)

Gd表示Fdi對應屬性值的總個數，由于每種屬性所對應的值的數量可能不同，所以每個屬性差距都取其均值。物品向量的差距計算如式(17)所示

(17)

將其規約到(0，1]之間即為物品語義相似度，計算如式(18)所示

(18)

simmkg(i，j) 的值越小表示兩個物品越不相似，越大表示越相似，為1則表示極其相似或相同。

電影的特征信息包括導演、演員、類型、制片公司和上映時間等。電影之間的特征信息交集越多的話，在知識圖譜中的關聯也就越多，語義上也就越相似。

2.2.2 相似度融和

依然采用線性加權求和的方式來融合物品的語義相似度和物品的評分矩陣相似度，計算公式如式(19)所示

simm(i，j)=β·simmkg(i，j)+(1-β)·simmrt(i，j)

(19)

simm(i，j) 表示兩物品融合之后的相似度；simmkg(i，j) 表示兩物品語義相似度，計算見式(18)；simmrt(i，j) 表示兩物品基于評分矩陣的相似度，計算見式(2)。β為權重值，在[0，1]中取值，當為0時表示未融入物品的語義相似度，為1時表示未融入物品評分矩陣相似度。

根據融合相似度所得的相似物品，包含了物品語義上的相似成分，不完全依賴評分的相似性，從而緩解了傳統算法過分依賴評分數據的問題。

2.2.3 基于物品的協同過濾推薦

根據融合的物品相似度計算目標用戶對沒有評價過的物品的感興趣程度，其計算公式如式(20)所示

(20)

Puf表示用戶u對未評分的物品f的感興趣程度，simm(x，f)表示物品x和f的融合相似度，計算見式(19)，X表示用戶u評分過的物品集合，rux表示用戶u對物品x的評分。然后利用式(20)計算用戶對物品的感興趣程度，按從高到低排序，優先向用戶推薦Top-K物品。

2.3 兩種Top-K推薦融合

為了綜合用戶語義信息和物品語義信息對緩解評分數據稀疏的效果，提出將兩種融合語義信息之后的協同過濾Top-K推薦結果進行融合，得到最終的Top-K推薦結果。在下面的融合算法中，和分別是基于用戶協同過濾和基于物品協同過濾Top-K推薦集合，集合中的元素 {E0，E1，…，Ek} 和 {F0，F1，…，Fk} 都是按照感興趣程度由高到低的有序數列。算法將兩個推薦集合的交集作為必推薦項目，空缺的推薦項目一半取自的剩余元素，一半取自的剩余元素。

融合算法如下

(6) if n 為奇數:

(7) a=(n+1)/2;

(8) b=(n-1)/2;

(10) for i (0

(12) end do;

(13) for j (0

(15) end do;

(16) if n 為偶數:

(17) c=n/2;

(18) for m (0<=m<=c) do

(21) end do;

3 實驗過程以及分析

3.1 實驗設置

3.1.1 實驗數據

我們選取MovieLens-1M數據集，該數據集是一組從上世紀末到本世紀初的由MovieLens用戶提供的電影評分數據。其中數據文件主要包括用戶人口統計信息user.dat、電影簡單信息movies.dat和評分信息ratings.dat，即6040個用戶對3883部電影的1 000 209條評分信息。電影的詳細信息從IMDB網站爬取，去除信息不完整的電影，最后保留了6040個用戶，3332部電影，930 000條評分。用戶知識圖譜數據見表1，電影知識圖譜數據見表2。

表1 用戶知識圖譜數據

表2 電影知識圖譜數據

3.1.2 實驗環境

實驗在個人電腦上運行，實驗環境見表3。

表3 實驗環境

3.2 評價指標

本文采用F1值來評價推薦算法的推薦性能，計算公式如式(21)所示

(21)

Precision表示準確率，Recall表示召回率，計算公式如式(22)和式(23)所示

(22)

(23)

其中，NTP表示推薦正確的物品數量，NFP表示推薦不正確的物品數量。NFN表示沒有推薦的物品數量。

為了準確測試算法的性能，實驗隨機劃分數據集70%作為訓練集，30%作為測試集，一共進行5次實驗，取測試結果的平均值作為最終結果。

3.3 實驗以及結果分析

3.3.1 實驗步驟

實驗運用本文算法在數據集上進行Top-1、Top-5、Top-10、Top-15和Top-20推薦，并計算對應F1值的平均值作為衡量結果。具體步驟如下：

步驟1 根據用戶人口統計信息和電影詳細信息分別構建用戶知識圖譜和電影知識圖譜。

步驟2 分別以表示學習算法TransE和TransH訓練用戶知識圖譜和電影知識圖譜，分別得出用戶和電影的語義向量表示。

步驟3 分別根據式(11)和式(18)，計算用戶語義相似度和電影語義相似度。

步驟4 根據式(12)進行用戶相似度融合，據此進行基于用戶的協同過濾推薦，得出Top-K推薦結果。

步驟5 根據式(19)進行電影相似度融合，據此進行基于物品的協同過濾推薦，得出Top-K推薦結果。

步驟6 根據融合算法將兩種推薦結果融合，得出最終Top-K推薦結果。

步驟7 隨機劃分訓練集和測試集，重復步驟4～步驟6過程，一共進行5次實驗。

3.3.2 結果和分析

知識圖譜的實體和關系選擇不同的嵌入維度時，會對實驗結果產生影響，并且不同的知識圖譜所選擇的最優嵌入維度可能不同。所以我們選取維度為50、100、150和200這4個組進行對比實驗。在基于用戶和基于物品的協同過濾算法中，分別設定融合因子α和β均為0.1，相似用戶個數和相似電影個數均設為20，不同嵌入維度實驗結果對比如圖7所示。

圖7 不同嵌入維度實驗結果對比

從實驗結果中我們可以看出不同的知識圖譜對嵌入維度的敏感度不同，物品知識圖譜對嵌入維度的變化要比用戶知識圖譜更敏感一點，但是總體上而言，嵌入維度對實驗結果的影響幅度并不是很大。我們要盡量選擇最優的維度，所以在F1均值表現較好時，基于用戶和基于物品所選嵌入維度分別為150維和100維。

不同的相似近鄰數量同樣會影響實驗結果，實驗分別選取20、40、60、80、100、120作為相似近鄰數量進行實驗。分別選定對應嵌入維度為150維和100維，融合因子α和β均為0.1，不同相似近鄰數實驗結果對比如圖8所示。

圖8 不同相似近鄰數實驗結果對比

從圖8中可以看出隨著相似近鄰數量的遞增，基于用戶的推薦效果呈遞增趨勢并趨于平穩，而基于物品的推薦效果呈遞減趨勢，總體上相似近鄰數量對推薦結果的影響較大。所以圖中當F1均值最好時，基于用戶和基于物品所選相似用戶數量和相似電影數量分別為100和20。

權重因子是一個比較重要的參數，它控制著語義相似度的融合比例，也是本文算法中綜合利評分數據和用戶與物品自身語義信息的關鍵所在。通過不斷調節融合因子，使得實驗結果達到最佳。融合因子取值[0，1]，從0開始步長為0.1。選定對應嵌入維度分別為150維和100維，選定對應相似近鄰數量分別為100和20。不同融合權重因子實驗結果對比如圖9所示。

圖9 不同融合權重因子實驗結果對比

從實驗結果可以看出隨著權重因子值的遞增，兩種算法的F1均值都呈現先增后減的趨勢，并且均在0.2處效果達到最佳。且此時兩種推薦算法都要比沒有融入語義相似度時(融合因子為0)的效果要好，說明傳統的協同過濾在融入語義相似度之后，能夠更準確地尋找相似用戶和相似物品，從而進行更好的推薦。這也驗證了文中的假設是成立的。

使用以上確定的最優參數，進行兩種協同過濾推薦算法的Top-K推薦結果融合實驗，并且與傳統的基于用戶的協同過濾(user-based collaborative filtering，User-CF)、基于物品的協同過濾(item-based collaborative filtering，Item-CF)和文獻[8]的算法進行實驗對比，與其它算法實驗結果對比如圖10所示。

圖10 與其它算法實驗結果對比

從對比實驗中我們可以發現，本文算法要比傳統的協同過濾推薦算法和文獻[8]的算法具有更高的F1均值，說明本文算法要優于其它算法。

4 結束語

本文針對傳統的協同過濾推薦算法過分依賴于評分數據、缺乏考慮用戶和物品自身特征信息的問題，提出構建用戶知識圖譜，并將用戶與物品雙重語義相似度融合至協同過濾推薦算法中，形成一種高效算法。此算法綜合利用了評分數據和用戶與物品自身的語義信息，并以此緩解了傳統的協同過濾算法面對數據稀疏的問題。實驗結果驗證了本文算法具備更好的推薦性能。但是該算法也具有一定不足，即沒有充分考慮用戶對物品興趣度的時效性，這點或將成為未來研究的新方向。