融合用戶信任度的概率矩陣分解推薦算法

陳輝,王鍇鉞

(安徽理工大學 計算機科學與工程學院，安徽 淮南 232001)

大數據時代，由于互聯網和電子商務的信息量大、種類多、更新速度快，導致了信息超載問題。不斷發展和尋找新的技術來與用戶進行互動、交流和提供個性化的體驗，增加瀏覽量、銷售量并留住用戶是非常重要的。然而，搜索引擎只能被動地接受命令和執行命令，為用戶挖掘感興趣的信息并不是獨立的、主動的。于是，利用數據的力量來預測用戶興趣的推薦系統(RS)得到了大量關注。在用戶不主動搜索的情況下，RS可以根據已有數據將某些項目精確地推薦給有此需求的用戶，幫助用戶應對信息超載難題，提高信息的有效利用。但RS面臨數據稀疏性、冷啟動、負面評價影響、評分情緒傾向、商家信任度評價等問題。

目前，RS已廣泛應用于各個行業，不同的應用行業采用的推薦方法同源異流?；趨f同過濾的推薦系統(CF)應用最為廣泛[1]，它是一種通過從其他類似用戶或項目中收集評價信息來自動預測用戶傾向的技術。以CF算法為基礎，針對用戶傾向相似度問題，很多學者對其進行了進一步研究和改進。Polatidis 等[2]提出了基于協同過濾的多層推薦算法，在衡量相似度時，對相似性進行排序并分成不同等級，每個等級增加相應的限制條件以此來增加相似度衡量的準確性。王付強等[3]提出了一種基于位置的非對稱相似性度量的協同過濾推薦算法(LBASCF)，將余弦相似性與基于位置的相似性融合，得到一個新的非對稱用戶相似性。Suryakant等[4]考慮了用戶的評分習慣，提出一種基于均值散度度量相似性的計算方法，將余弦相似性(COS)、Jaccard相似性和MMD[5]相似性算法相結合，計算總體相似度。于金明等[6]提出了一種基于評分相似性和結構相似性兩部分構成的新的項目相似度量方法，但只考慮聯合評分用戶對相似度的影響[6]。肖文強等[7]在相似度計算中,分別引入了物品時間差、流行物品權重以及用戶共同評分權重來提高相似度度量的準確性。Li等[8]提出一種改進相似度和遺忘曲線相結合的推薦算法，計算用戶之間的相似度時，考慮了具有共同分數項目的數量對相似度的影響，提高了相似用戶集合的準確性。Fu等[9]考慮了部分用戶的個性化需求，結合K-means聚類方法，采用基于社區因子的計算方法代替傳統的相似度計算方法，提高推薦精度。Jiang 等[10]提出了一種基于可信數據和用戶相似度融合的slope one算法，將改進后的相似度算法與slope one算法的權值相加，得到最終的推薦結果。

由于矩陣分解模型具有良好的可擴展性和較強的理論基礎，在基于模型的推薦系統中得到了廣泛的應用,許多學者從不同的角度對其進行了建模。Forsati等[11]介紹了一種基于社交排名的協同過濾模型PushTrust，從用戶的社交環境中提取用戶的潛在特征并進行排名，能夠同時利用信任、不信任和中立關系，將其整合到矩陣分解算法中。Yang等[12]提出了基于概率矩陣分解的TrustPMF推薦模型，該模型對基于矩陣因子分解的社會推薦模型提供了概率解釋，整合用戶評分數據和這些用戶之間的社會信任網絡來提高推薦的性能。Xu[13]提出了一種基于矩陣分解的結合社會信息和物品關系的推薦算法，對物品的特征信息進行正則化約束，在矩陣分解和降維過程中保持數據特征的穩定性。

然而，由于CF的性質，評分矩陣過于稀疏是基于該技術的推薦系統存在的關鍵性問題，如商業推薦系統的可用評分信息密度通常不到1%[14]。傳統的計算相似性的方法，如余弦相似性(COS)、修正余弦相似性(ACOS)、皮爾遜相關系數(PCC)以及約束皮爾遜相關系數(CPC)[15]等都是針對用戶間的聯合評分來進行相似用戶查找的,在面對稀疏的數據集上顯得力不從心。同時，幾乎所有基于內容和基于模型的CF算法都無法處理從未對任何項目進行評分的用戶[16]。但事實上，現實生活中產生的數據是龐大且稀疏的，大部分用戶的評分都低于20項，這使得用戶之間缺少聯合評分，由此計算的推薦結果準確率較低。從這個角度來看，傳統的忽略非聯合評分項的推薦系統可能不再適用。

為了提高傳統協同過濾算法的效果，本文利用KL散度計算用戶間的聯合評分項以及非聯合評分項，充分利用評價信息找到信任度較高的同傾向用戶，提出一種運用用戶信任度正則項約束概率矩陣分解模型的推薦算法。該算法通過在概率矩陣分解模型(PMF)[17]中加入用戶信任度正則項，緩解推薦系統冷啟動以及稀疏性問題，通過實驗逐步建立改進算法所涉及的不同參數值，并在MovieLens 1M和Epinions數據集上進行對比實驗。

1 相關工作

1.1 評分矩陣

在CF中給用戶的建議取決于兩種收集用戶傾向信息的方式，一種是顯式反饋信息，即用戶對該項目的評分；另一種是隱式反饋信息，即瀏覽網頁次數、購買次數等，與該用戶喜好相似的其他用戶對該項目的評分也屬于隱式反饋的一種。用戶對項目的評分可以用一個用戶-項目矩陣來表示，矩陣中的每個項表示各個用戶對各個項目的傾向值。

假設U={u1,u2,…,um}是一個用戶集，I={i1,i2,…,in}是一個項目集，所有用戶對所有項目的評分構成評分矩陣，見表1。

表1 用戶-項目評分矩陣Tab.1 User-item rating matrix

表1中，rui表示用戶u對項目i的評分，代表用戶的傾向程度。如果用戶u對項目i沒有進行評分，則rui=0。實際上，用戶-項目矩陣非常稀疏，它意味著矩陣中有許多項的值為0。為了克服這一問題，本文運用PMF算法對用戶-項目矩陣進行隱式反饋信息的尋找，并且考慮用戶間的信任度，通過KL散度相似性算法尋找傾向程度相似的用戶，設計規范化項來約束目標函數，提高推薦系統的準確率。

1.2 概率矩陣分解模型

PMF是基于模型的CF推薦算法的一種，將高維的評價矩陣降維，得到用戶隱藏特征矩陣和項目隱藏特征矩陣，通過計算二者的內積對評價矩陣的缺失值進行進一步的預測。

給定一個m×n評價矩陣R，采用秩為d的兩個低維矩陣U、V來擬合，擬合式為

R≈UVT，

(1)

式中：U∈m×d；V∈d×n，d≤min{m,n}；U代表每個用戶對d種特征的傾向程度；V代表d種特征在每一個項目中的存在程度。

p(R|U,V,σ2)=

(2)

(3)

2 融合用戶信任度的概率矩陣分解推薦算法

2.1 基于KL散度的相似性計算

相似性計算在CF中處于重要地位，常用的相似性度量方法無法完整地利用評分信息，只考慮了用戶間的聯合評分項，不適宜處理非線性的情況。但在實際生活中，極度稀疏的數據集上的聯合評分項較為匱乏，利用傳統算法尋找相似用戶會出現誤差，影響推薦結果。

KL散度(kullback-leibler divergence) 是一種廣泛應用于評價兩種概率分布差異的度量方法[18]，若兩個對象分別服從兩個相同或不同的概率分布，使用 KL散度能高效地區分重疊現象較為嚴重的對象。因此，本文綜合用戶間的聯合評分項以及非聯合評分項，利用KL散度的優勢提出項目相似度計算模型。

在評分矩陣中，可將所有用戶對某兩個項目i和j的評分看成兩個離散數組，替換KL散度公式中的概率密度函數，得到i與j的KL距離計算公式為

(4)

兩項目間的相似性計算公式為

(5)

雖然KL 距離是非對稱的，但在評分矩陣中，運用項目i所有評價信息來近似項目j所得的誤差和運用項目j的所有評價信息來近似項目i所得的誤差具有相同的意義。所以，采用式(6)代替式(5)中的D(i,j):

Ds(i,j)=(D(i,j)+D(j,i))/2,

(6)

則項目i和項目j的KL相似度改寫為

(7)

用戶對某個項目的傾向程度會受到相似用戶的影響，也就是說，用戶的特征向量與他的相似用戶差別不大。對基于KL散度的相似性計算結果進行排序，來獲得用戶間的信任度排名，得到用戶的前K個相似用戶。設用戶u，v對項目i，j評分為(rui,-)和(-,rvj)，沒有聯合評分項，在極度稀疏的評分矩陣中這樣的問題屢見不鮮，為此，利用稀疏數據集中普遍存在的非聯合評分項，計算用戶u和用戶v的信任度：

(8)

2.2 基于用戶信任度的概率矩陣分解模型

為用戶推薦的項目應該與用戶的傾向程度越接近越好，而相似的用戶之間具有相似的傾向程度?；谶@一假設，在計算用戶信任度時利用KL散度，從中選擇信任度最大的K個相似用戶，并在矩陣分解過程中保持這種聯系，使得相似用戶間的特征向量更加接近，并且可以根據信任度的不同而對不同用戶區別對待。因此，在式(3)的損失函數中加入一個正則項：

(9)

式中：K(u)表示用戶u的前K個最為相似的用戶；Uf表示用戶的第f個相似用戶的特征向量；α表示用戶相似度正則系數。該正則項表示相似用戶間的信任度差距，最小化目標函數使它們之間的差距最小，使得用戶特征向量更加貼近其相似用戶的特征向量。得到如下模型：

(10)

目標函數局部最小值采用隨機梯度下降法求得，對式(10)中Uu和Vi的偏導數如下：

(11)

(12)

參數更新方式：

(13)

(14)

式中β為學習速率，選取的值太大會導致迭代結果發散，越來越偏離最小值；β越小雖然會得到更精確的結果，但是時間代價太大，因此需進行實驗，選擇合適的學習速率。

2.3 算法描述

利用2.1節中用戶信任度計算和2.2節中的PMF模型，得到融合KL散度用戶信任度計算的概率矩陣分解協同過濾推薦算法(MDCF-KL) 偽代碼如下：

Algorithm1 MDCF-KL算法 Input:用戶-項目評分矩陣,正則化參數α、λ和η,最大迭代次數H,學習速率β,特征向量維度d,相似用戶數量K以及推薦項目數量N。Output:用戶隱藏特征矩陣U,項目隱藏特征矩陣V,預測評分值Pre_R以及N個推薦項目。Initialize:隨機初始化U、V(σ2=1的標準正態分布),根據3.3節中表3設置參數值。1.forv<=mdo2.fori<=ndo3.forj<=ndo4.calculateKL(i,j)5.calculateS(u,v)6.endfor7.endfor8.N[v]=S(u,v)9.endfor10.Sim-K=sorted(N[v],num=K)11.forh<=Hdo12.forallrui∈Rdo13.Uu←Uu-β?L?Uu14.Vi←Vi-β?L?Vi15.endfor16.h=h+117.endfor18.Pre_R=U?V19.Top-N=sorted(Pre_R[u][],num=N)

3 實驗結果與分析

3.1 數據集

本文實驗采用的數據集為MovieLens1M和Epinions。MovieLens1M只允許對自己看過的電影進行評分，分值在1～5之間。在這組數據中，每個人至少給20部電影打分，電影包括19種類型。Epinions涵蓋了分布在美國和歐洲的消費者對商品的評價。數據集的具體信息見表2。

表2 數據集信息Tab.2 Datasets information

3.2 評價標準

在對算法性能和有效性進行評價時，采用平均絕對誤差(MAE)、準確率(Precision)和召回率(Recall)三種指標，計算表達式為：

(15)

(16)

(17)

3.3 實驗結果與分析

為了得到理想的對比結果，本文根據參考文獻推薦的參數值以及參數調優的結果選擇最優實驗參數，實驗參數設置見表3。

表3 參數設置Tab.3 Parameter settings

MDCF-KL算法和HITUCF[8]、ICCF[9]以及trust-CF[10]三種對比算法在MovieLens1M和Epinions兩個數據集上的MAE測試效果如圖1所示。

(a)MovieLens 1M數據集

(b)Epinions數據集圖1 兩種數據集上MAE比較Fig.1 Comparison of MAE values on two datasets

從圖1可以看出，隨著相似用戶數量的增加，四種算法的曲線都呈下降走向，而且逐步趨于平緩。在MovieLens1M數據集上trust-CF、ICCF在相似用戶數量為70時達到最優值，MDCF-KL、HITUCF在相似用戶數量為50時更快地達到最優值，MDCF-KL算法相比較于其他三種算法平均絕對誤差明顯減少。在Epinions數據集上ICCF與其他三種算法有較大差距，主要原因是ICCF算法過于追求用戶的個性化需求，導致符合條件可以參與計算的評分項目極其稀少，不適用于更為稀疏的數據集。其他三種算法的平均絕對誤差雖然有所增加，但仍能保持一個相對良好的性能，尤其是MDCF-KL算法，能通過非聯合評分項判斷相似用戶并結合概率矩陣分解，在較為稀疏的Epinions數據集上更有優勢。

為了進一步驗證MDCF-KL算法的有效性，分別在MovieLens1M和Epinions數據集上針對不同相似用戶數量，采用召回率和準確率兩個指標對各算法的表現進行實驗比較，如圖2、圖3所示。

(a)準確率比較

(b)召回率比較圖2 MovieLens 1M數據集上準確率和召回率比較Fig.2 Comparison of precision and recall on MovieLens 1M dataset

從圖2可以看出，在MovieLens1M這個評分矩陣密度相對較高的數據集上，MDCF-KL、HITUCF和trust-CF的準確率和召回率較為相近，相似用戶數量少于30時，三種算法表現各有優劣，但在相似用戶數量為40時，MDCF-KL準確率得到了最優結果。隨著相似用戶取值逐漸增加，推測出的用戶喜歡物品范圍越來越小，導致MDCF-KL召回率下降，但仍然優于其他三種算法。

(a)準確率比較

(b)召回率比較圖3 Epinions數據集上準確率和召回率比較Fig.3 Comparison of precision and recall on Epinions dataset

從圖3可以看出，Epinions數據集上，隨著數據稀疏程度增大，MDCF-KL算法在相似用戶數量小于40時，準確率相比較于其他三種算法有明顯的提高，并在相似用戶數量達到60時準確率和召回率取得最優結果。這是由于本文算法充分考慮了非聯合評分項，增加了評分的利用率，在面對更為稀疏的數據集時有著較為明顯的優勢。

4 結束語

為了解決冷啟動以及數據稀疏的問題，本文將用戶非聯合評分引入PMF推薦系統，提出了一種基于概率矩陣分解和正則約束用戶信任度關系的算法。通過對MovieLens1M以及Epinions數據集的實驗分析表明，MDCF-KL方法能有效提升推薦性能，并且在更稀疏的Epinions數據集上取得了明顯成效。在下一步的研究工作中，將會考慮需求中的長尾效應，挖掘零散、個性化但數量極大的尾部需求；利用拉普拉斯等分布來更有效地擬合潛在特征向量，貼合實際情況，提高長尾項目建模的能力。