基于SVD++隱語義模型的信任網絡推薦算法

陳佩武，束方興

1. 平安科技（深圳）有限公司，廣東 深圳 518031；2. 北京大學互聯網研究院（深圳），廣東 深圳 518055

1 引言

隨著互聯網技術的全面發展，海量數據得以產生，推動人類社會從信息匱乏的時代走入了信息過載的時代。作為解決信息過載問題的利器，推薦系統受到各大互聯網公司以及研究機構的青睞。作為推薦系統的核心，推薦算法成為研究的關鍵和熱點。然而傳統的推薦算法（如協同過濾（collaborative filtering，CF）算法）存在評分數據庫的數據稀疏性和用戶偏好信息數據有限等問題，即推薦系統的數據稀疏和冷啟動問題。以上問題會制約推薦系統的推薦效果，破壞用戶體驗。為了緩解數據稀疏和冷啟動問題，通常會在推薦系統中引入新維度的數據。然而近年來，社交網絡的快速發展給推薦算法的研究帶來了新的推動力[1]。在社交網絡中，用戶不但會展示自己的個性和偏好，還會與偏好類似、相互信任的其他用戶構建聯系。因此如何進一步在社交網絡的研究中利用社會化信息進行信任構建，提升推薦算法的有效性，成為一個重要的研究課題。

隱語義模型（latent factor model，LFM）最早是在文本挖掘鄰域被提出的，其主要被用來尋找文本中的隱含語義。雖然學術界已經提出了多個基于隱語義模型改進的推薦算法，但是信任網絡中還少有以隱語義模型為基礎進行改進的推薦算法[2]，且效果并不理想。為了優化推薦算法的效果，本文采用以隱語義模型為基礎，與其他模型融合的思路進行推薦算法設計。另外，評分預測（rating prediction）也是推薦系統研究的關鍵問題，即通過已知的用戶歷史評分記錄來預測未知的評分。因此，基于隱語義模型與其他模型融合設計推薦算法，并從評分預測的角度進行實驗驗證，具有重要的研究意義和實用價值。本文結合信任網絡的特點與用戶關系數據進行建模，基于用戶之間的相似度設定用戶之間的隱式信任關系，結合顯式信任關系與評分等數據一起進行預處理，生成矩陣。在隱語義模型選擇方面，本文借鑒奇異值分解（single value decomposition，SVD）++模型[3]，結合信任網絡的特點進行改進，并融合鄰域模型，設計了推薦算法的評分預測函數和損失函數，利用隨機梯度下降算法進行迭代求導，得到優化后的推薦算法評分預測值。之后本文在Epinions開源數據集上進行離線對比實驗，驗證了本文設計的推薦算法在信任網絡中的推薦效果優于其他對比算法，對于解決推薦系統的冷啟動問題有良好效果。

本文主要的貢獻如下。

● 與傳統僅基于用戶的物品評分記錄的推薦算法以及相關模型相比，本文加入了信任網絡背景，通過對信任網絡特點和用戶行為進行分析，將用戶反饋數據分為隱式行為數據和顯式行為數據，并進行整合，利用信任信息對推薦算法的評分效果進行改善。

● 在信任網絡的研究背景下，本文借鑒SVD++隱語義模型進行推薦算法的設計和實現，融合顯式信任因子及隱式信任因子優化算法的推薦評分預測效果。

● 本文以隱語義模型為算法基礎，借鑒了基于鄰域模型的推薦算法思想，將兩種模型從全局優化的角度進行融合，并從評分預測的角度對推薦算法設計了對比實驗。本文使用評測指標平均絕對誤差（mean absolute error，MAE）和均方根誤差（root mean square error，RMSE）分別在冷啟動數據集和全體數據集中對比加入信任關系前后的SVD++算法的效果，從而證明信任網絡的加入對原有推薦算法的提升效果。然后將本文設計的推薦算法與其他信任網絡下的典型算法進行對比測試，并證明了本文設計的算法在評分預測問題上的優勢。

2 研究背景

2.1 推薦系統的發展

針對推薦系統的研究開始于20世紀90年代，隨著網絡的普及，該技術被逐步應用到各個行業。推薦系統主要由用戶建模部分、推薦對象建模部分以及推薦算法部分共同組成，其中推薦算法部分是整個推薦系統的核心，也是研究的關鍵和熱點。目前被廣泛使用的協同過濾推薦算法[4]來源于Tapestry和GroupLens系統的論文[5-6]，該算法被用于郵件和新聞的過濾。協同過濾算法也被稱為基于鄰域模型的推薦算法，即鄰域實質相似項的集合。用戶間存在相似的興趣，或者某些物品間存在相似的特征，因此基于鄰域的推薦算法又被分為兩類：基于用戶的協同過濾（UserCF）推薦算法和基于物品的協同過濾（ItemCF）推薦算法[7]。UserCF算法主要包括兩步：找出與目標用戶有相似興趣的用戶集；把用戶集中其他用戶喜歡且目標用戶沒標注過的物品推薦給目標用戶。余弦相似度可用下式計算：

其中，S(a)和S(b)分別表示用戶a、b有反饋信息的物品集合。在推薦系統中，用戶數量往往較大，用戶之間兩兩計算相似度會帶來較高的算法復雜度[8]，因此如何定義用戶間的相似度成為優化研究的重點，如Breese J S等人[9]提出利用用戶行為進行相似度計算。

由于UserCF算法復雜度較高，目前Amazon、Netflix等平臺都將ItemCF算法作為推薦算法的基礎[10]。可使用ItemCF算法向用戶推薦他們喜歡的物品的相似產品，該算法并不使用物品的內容屬性進行相似度計算，而是通過分析用戶的行為數據來計算不同物品之間的相似度。ItemCF算法的步驟包括兩步：進行物品間的相似度計算；基于用戶的行為數據特點推薦產品。ItemCF算法的評分預測式如下：

其中，Si(i,j)表示物品i與j之間的相似度，R(i,k)表示前k個與物品i相似的物品，I(u)表示被用戶u評論的物品集合，ra,j表示用戶a對物品j的興趣，表示感興趣的均值。在有用戶m個、產品n個、用戶行為記錄k個、隱類f個、算法迭代d次的情況下，基于鄰域模型的推薦算法和基于隱語義模型的推薦算法各有優勢，具體見表1。如果在推薦算法的設計中將兩類模型進行融合，可能會起到優勢互補的作用，從而獲得更好的推薦效果。

表1 隱語義模型和鄰域模型特點

隱語義模型的思想最初于文本挖掘領域被提出，后來擴展改進的方法包括隱含狄利克雷分布（latent Dirichlet allocation，LDA）主題模型[11]、概率潛在語義分析（probabilistic latent semantic analysis，PLSA）、主題建模（topic model）等。通過矩陣降維的方式進行評分矩陣補全、應用隱語義模型應對推薦系統中冷啟動問題成為一個有效方法。奇異值分解是一種用于發現文本中潛在因子的方法，它將高度相關并共同出現的相似詞語作為因子，從而把大規模的文本向量矩陣拆解為低階的相似矩陣。除此之外，相關的方法還有主成分分析（principal component analysis，PCA）[12]和隱含狄利克雷分布主題模型等。早期，評分矩陣稀疏且SVD算法計算復雜度較高，導致基于SVD的推薦算法沒有引起重視。直到Koren Y等人[3]在Funk-SVD的基礎上加入偏置項，并且把用戶歷史行為考慮在內提出SVD++模型之后，才大大提升了算法的效果。

2.2 評分預測與TopN推薦問題

利用已有數據信息來預測用戶對未評分的物品集合的評分的研究被稱為推薦系統研究中的評分預測[12]。在評分預測研究中，基本數據集是用戶的歷史評分數據，在該數據集中，通常每條記錄數據用三元組(u,i,r)來表示。其中，u表示用戶，i表示物品，r表示對該物品的評分。評分預測的準確性可以通過RMSE和MAE來衡量。在推薦系統中，真實值rui是用戶u對物品i的評分，預測值r?ui是推薦系統給出的預測結果，又因為在離線實驗中數據集被分為測試集和訓練集，所以觀測次數在這里指的是測試集的大小。RMSE和MAE的定義如下：

其中，T表示整個測試集，Test表示實際測試時使用的測試集。

從指標的定義可以看出，兩個測試指標的值與評分預測的準確性呈現負相關的趨勢，即測評指標越小，評分預測準確性越高。相較于MAE指標，RMSE指標因為平方和的形式更加放大了誤差的影響，對于推薦算法的評測來說，RMSE更加嚴格。

TopN推薦問題指在給用戶的個性化推薦列表中，設置哪些產品進行優先呈現[13]。TopN推薦預測的效果一般使用準確率（precision）和召回率（recall）來衡量，兩者分別表示有多少比例的推薦選項被用戶選中以及有多少比例的推薦選項進入了用戶的最終列表，其定義如下：

其中，R(u)表示訓練集上生成的給用戶的推薦列表，T(u)表示用戶在測試集上生成的行為列表，U表示用戶集。目前大多數推薦算法的相關研究是基于用戶的評分數據的[14]，因此有許多研究人員探索如何優化RMSE和MAE兩個評分指標。同時TopN推薦問題也受到產業界各大互聯網公司的關注[15]。本文結合研究背景進行實驗設計，主要從評分預測的角度來定義推薦算法，并進行評測。

3 算法研究與模型訓練

3.1 基于SVD++的信任網絡推薦算法設計

本文在信任網絡的研究背景下，從推薦算法研究中的評分預測問題出發設計推薦算法，即在確定用戶的相關歷史數據和相關信任關系的情況下，對用戶未評分的物品進行評分預測。傳統的隱語義模型主要利用矩陣因子分解的方式，從評分預測的角度定義推薦算法的損失函數，沒有完全考慮用戶的歷史行為數據[16]。Koren Y提出的Simon模型加入了用戶的歷史行為數據，其設計的SVD++算法取得了良好的評分預測效果。Simon模型的評分預測式如下：

其中，bui表示預測的基準估計值，uu表示從評分矩陣中分解的用戶向量，uu與vi的向量乘積表示用戶的顯式評分對預測結果的影響。N(u)表示與用戶u的潛在偏好有聯系的群體，yj表示N(u)群體的隱式反饋。因為數據集具有稀疏性特點，所以隱式數據的體量多于顯式數據，因而本文設置正則化處理系數-β，β∈ [0 ,1]。β=0表示隱式反饋影響較大，β=1則表示隱式反饋的影響幾乎被抵消，本文選取β=0.5。結合信任網絡中的奇異值分解，首先將用戶向量與信任者向量進行統一，之后逐步把信任關系代入SVD++模型：

其中，Ti(u)表示與用戶u有相關隱式信任關系的群體。為了使推薦算法在評分預測過程中取得良好效果，需要解出評分預測式中的未知系數，本文通過確定損失函數將求解未知系數轉換為對損失函數最小值的求解問題。將待優化的損失函數設定如下：

其中，rui表示獲得的評分，表示預測得分，tuv表示用戶v對用戶u的顯式信任值，代表用戶v對用戶u的隱式信任值，Ω表示用戶與物品集，Φ表示用戶顯式信任關系集，Λ表示用戶間的隱式信任關系集，λt1與λt2分別表示控制顯式及隱式信任的正則化影響因子。在機器學習的擬合過程中，常會遇到過度擬合的情況，在優化損失函數的最小值時因為過度擬合樣本誤差，導致樣本點外的函數計算結果偏移較大。本文使用一個過擬合參數λ來避免過擬合，加入λ后得到的損失函數如下：

對損失函數中加入的避免過擬合項進行正則化處理，并進行系數處理，得到基于隱語義模型的信任網絡推薦算法的損失函數：

其中，Ui和Uj分別表示對物品i和物品j進行過評分的用戶集，X(v)和Xi(v)分別表示顯式信任用戶集合以及隱式信任用戶集合，正則化的懲罰規則主要用于可能造成評分過擬合的冷門對象，完成基于SVD++隱語義模型針對信任網絡進行的推薦算法的評分預測式以及損失函數的設計，下一步進行隱語義模型與鄰域模型的融合。

3.2 信任網絡中鄰域模型和隱語義模型的推薦算法融合

基于鄰域模型的推薦算法分為ItemCF算法和UserCF算法兩類，本文將從ItemCF算法的角度設計適合與隱語義模型進行融合的鄰域模型。兩類模型基于同一數據集，只是從不同的角度來推測用戶的興趣。本文把兩類模型的不確定參數放入同一損失函數中進行求解，然后對評分預測的結果進行擬合，從而將兩類模型進行融合。整合鄰域模型的評分預測式，將評分預測式進行正則化后，將其中的基準評分估計值設置為隱語義模型中的評分預測式（式（10）），則得到式（14）：

其中，wv表示用戶顯式反饋的未知參數，sij表示用戶i與j之間的相關性對基準估值的偏移度，cij表示用戶i對j的隱式反饋對評分預測帶來影響的權重，以優化算法的空間復雜度和時間復雜度。本文使用式（14）作為評分預測式，參考式（13）得到融合后的預測損失函數：

綜上，式（14）與式（15）即基于隱語義模型和鄰域模型融合后的適用于信任網絡的推薦算法評分預測式與預測損失函數。

3.3 模型的迭代訓練

對目標函數的最優值進行求解通常會使用梯度下降（gradient desent）法，其中梯度為多元函數的偏導向量。逐步求出損失函數的最小值，需要確定每個步驟的步長以及方向，通過梯度計算可以得到函數下降最快的方向。對于未確定參數，采用梯度下降算法，可表示為：

如圖1所示，對于參數θ而言，損失函數L對其求偏導即表示梯度，其中α表示該方向上的步長，也被稱為學習速率。梯度算法可以分為兩類：隨機梯度下降（stochastic gradient descent，SGD）算法、批梯度下降（batch gradient descent，BGD）算法。其中，BGD算法為通過最小化所有訓練樣本的損失函數而得到的全局最優解，而SGD算法則大體向全局最優的方向求解，但是SGD算法可以不用每次迭代過程中都使用全體訓練樣本，因此SGD的復雜度相對較小，本文使用復雜度優先的SGD算法。

圖1 采用梯度下降算法求解損失函數的最優解

首先，定義評分值、顯式信任數值以及隱式信任數值的表達誤差：

由式（17）～式（19）的計算可以得到參數的偏導結果，下面給出其關鍵運算步驟的偽代碼，算法1的作用是通過文本進行數據輸入預處理，生成3個矩陣，算法2為采用隨機梯度下降算法進行推薦算法迭代訓練模型的偽代碼流程，并在最后給出其評分預測結果。

4 實驗

本文的實驗部分主要是在開源數據集Epinions上對本文設計的推薦算法與經典的TrustMF算法進行對比，實驗方法采用離線實驗。將離線的實驗數據集分為訓練集和測試集，在訓練集上進行用戶的興趣模型訓練，然后在測試數據集上對訓練的模型進行預測測試，并用相關指標算法進行評分。在對比對象的選擇方面，選擇TrustMF的原因是：相較于其他相關研究信任網絡下的推薦算法（如SoRech[17]、SocialMF[18]等相關算法[19-22]），該算法可以在評分預測問題中取得較好的成績。

本文實驗選擇的Epinions數據集為開源數據，分為兩個部分：rating_data和trust_data，其中rating_data為用戶歷史完成評分的數據，格式為三元組(user_id, item_id, rating_value)；trust_data為表示用戶間信任關系的數據，格式為三元組形式(source_user_id, target_user_id,trust_statement_value)；該數據集的基本信息見表2、表3。

表2 Epinions數據集基本信息

表3 Epinions數據集數據范圍

實驗評測指標主要選取RMSE和MAE，這兩個指標數值都反比于推薦預測的準確性，即指標數值越小，則誤差越小，準確性越高。在進行實驗前，將Epinions數據集隨機劃分為5份，1份是測試集，其余4份是訓練集，算法中已知參數的設置見表4。

表4 算法中已知參數

為了說明本文設計的算法對冷啟動問題的優化作用，實驗先從推薦系統冷啟動的角度開始進行。推薦系統的冷啟動是指在進行評分預測時，測試集中只選用評分物品數量小于5的用戶來進行測試。實驗結果見表5。

表5 冷啟動測試評測結果

從實驗結果可以得出，除個別情況下某一指標（d=10時本文算法的MAE略大于TrustMF的MAE）稍差，其他情況下本文算法都優于其他各個推薦算法的冷啟動效果。可以證明，相比于其他參考算法，本文的推薦算法在解決冷啟動問題方面更好。迭代優化實驗則使用所有用戶作為測試集，得到的評分預測結果見表6。

從表6可以看出，所有算法的實驗評測效果均好于冷啟動實驗組的評測結果。這是因為在冷啟動時遇到的數據稀疏問題影響了推薦系統的效果。而采用全部用戶集上的數據時，因為包括熱門用戶和產品，所以提升了算法的推薦效果。同時從實驗結果看，相比其他算法，本文算法的評測結果有一定的優化提升。

表6 使用數據集中所有用戶進行測試的評測結果

為了進一步了解信任網絡對推薦算法優化的影響，本文以用戶在信任網絡中的度為依據進行用戶群體的劃分設計測試集。將用戶視為圖論中的點，修改點的出度和入度之和就是修改點在信任網絡圖中的度。本文取隱式向量維度d=10，與TrustMF進行對比測試，如圖2所示。

從圖2可以看出，隨著信任網絡中度數的增加，推薦算法對用戶興趣的預測準確率基本呈上升趨勢。而且，在多數情況下，本文的推薦算法因為結合了隱語義模型和顯式信任關系，推薦結果的評分預測精度更高，效果優于對比算法TrustMF。

圖2 當d=10時，不同信任網絡度數的MAE值和RMSE值

5 結束語

作為推薦系統的核心，對推薦算法的研究受到學術界和產業界的廣泛關注和重視，評分預測是推薦算法研究中的核心問題。傳統推薦算法在面對顯式行為數據稀疏時容易出現冷啟動的問題，為了緩解該問題對推薦算法進行評分預測的準確度的影響，本文結合信任網絡的特點和用戶信任關系數據進行建模，設計了適用于信任網絡的推薦算法，并進行了相關實驗評測。本文將用戶行為數據分為顯式行為數據和隱式行為數據，因為輸入的用戶關系數據中具有二元顯式信任關系，本文基于用戶之間的相似度來設定用戶之間的隱式信任關系，結合顯式信任關系數據、評分數據以及隱式信任關系數據一起進行預處理，生成矩陣，進行建模。

在隱語義模型的選擇上，本文借鑒SVD++模型，結合信任網絡的特點進行改進，并融合了鄰域模型進行推薦算法的評分預測函數和損失函數的設計。然后利用隨機梯度下降算法進行函數中的參數迭代求導，直至損失函數收斂于最小值，從而求得優化后的相關參數，將其代入評分預測函數后得到推薦算法評分預測值。最后本文通過開源數據集，采用離線測試的方案，使用RMSE和MAE兩個典型評測指標對本文設計的推薦算法和TrustMF算法進行評測實驗。實驗結果證明，本文設計的推薦算法在信任網絡中優于其他參照算法，對于解決推薦系統的冷啟動問題有良好的效果，并具有一定的實用意義。