基於SVD++隱語義模型的信任網路推薦演算法
陳佩武1, 束方興2
1 平安科技（深圳）有限公司，廣東 深圳 518031
2 北京大學網際網路研究院（深圳），廣東 深圳 518055
摘要：
推薦演算法通常基於使用者的行為資料進行建模，然而顯式行為資料的稀疏性可能會引起推薦演算法的冷啟動問題。為了降低資料稀疏和冷啟動問題對推薦演算法效果的影響，在已有顯式信任關係的基礎上，基於使用者相似度引入隱式信任關係，透過SVD++隱語義模型設計了新的推薦演算法。為了提升演算法效果，進一步融合鄰域模型，推匯出演算法評分預測式及損失函式。在Epinions開源資料集中將RMSE和MAE作為測試指標，在全體使用者集和冷啟動使用者集上進行對比實驗。實驗結果顯示，設計的推薦演算法可以在一定程度上改善原推薦演算法的冷啟動問題，並取得更好的評分預測效果。
關鍵詞：
推薦演算法 ； 隱語義模型 ； 信任網路 ； 評分預測
1 引言
隨著網際網路技術的全面發展，海量資料得以產生，推動人類社會從資訊匱乏的時代走入了資訊過載的時代。作為解決資訊過載問題的利器，推薦系統受到各大網際網路公司以及研究機構的青睞。作為推薦系統的核心，推薦演算法成為研究的關鍵和熱點。然而傳統的推薦演算法（如協同過濾（collaborative filtering，CF）演算法）存在評分資料庫的資料稀疏性和使用者偏好資訊資料有限等問題，即推薦系統的資料稀疏和冷啟動問題。以上問題會制約推薦系統的推薦效果，破壞使用者體驗。為了緩解資料稀疏和冷啟動問題，通常會在推薦系統中引入新維度的資料。然而近年來，社交網路的快速發展給推薦演算法的研究帶來了新的推動力。在社交網路中，使用者不但會展示自己的個性和偏好，還會與偏好類似、相互信任的其他使用者構建聯絡。因此如何進一步在社交網路的研究中利用社會化資訊進行信任構建，提升推薦演算法的有效性，成為一個重要的研究課題。
隱語義模型（latent factor model， LFM）最早是在文字挖掘鄰域被提出的，其主要被用來尋找文字中的隱含語義。雖然學術界已經提出了多個基於隱語義模型改進的推薦演算法，但是信任網路中還少有以隱語義模型為基礎進行改進的推薦演算法，且效果並不理想。為了最佳化推薦演算法的效果，本文采用以隱語義模型為基礎，與其他模型融合的思路進行推薦演算法設計。另外，評分預測（rating prediction）也是推薦系統研究的關鍵問題，即透過已知的使用者歷史評分記錄來預測未知的評分。因此，基於隱語義模型與其他模型融合設計推薦演算法，並從評分預測的角度進行實驗驗證，具有重要的研究意義和實用價值。本文結合信任網路的特點與使用者關係資料進行建模，基於使用者之間的相似度設定使用者之間的隱式信任關係，結合顯式信任關係與評分等資料一起進行預處理，生成矩陣。在隱語義模型選擇方面，本文借鑑奇異值分解（single value decomposition， SVD）++模型，結合信任網路的特點進行改進，並融合鄰域模型，設計了推薦演算法的評分預測函式和損失函式，利用隨機梯度下降演算法進行迭代求導，得到最佳化後的推薦演算法評分預測值。之後本文在Epinions開源資料集上進行離線對比實驗，驗證了本文設計的推薦演算法在信任網路中的推薦效果優於其他對比演算法，對於解決推薦系統的冷啟動問題有良好效果。
本文主要的貢獻如下。
● 與傳統僅基於使用者的物品評分記錄的推薦演算法以及相關模型相比，本文加入了信任網路背景，透過對信任網路特點和使用者行為進行分析，將使用者反饋資料分為隱式行為資料和顯式行為資料，並進行整合，利用信任資訊對推薦演算法的評分效果進行改善。
● 在信任網路的研究背景下，本文借鑑SVD++隱語義模型進行推薦演算法的設計和實現，融合顯式信任因子及隱式信任因子最佳化演算法的推薦評分預測效果。
● 本文以隱語義模型為演算法基礎，借鑑了基於鄰域模型的推薦演算法思想，將兩種模型從全域性最佳化的角度進行融合，並從評分預測的角度對推薦演算法設計了對比實驗。本文使用評測指標平均絕對誤差（mean absolute error，MAE）和均方根誤差（root mean square error，RMSE）分別在冷啟動資料集和全體資料集中對比加入信任關係前後的SVD++演算法的效果，從而證明信任網路的加入對原有推薦演算法的提升效果。然後將本文設計的推薦演算法與其他信任網路下的典型演算法進行對比測試，並證明了本文設計的演算法在評分預測問題上的優勢。
2 研究背景
2。1 推薦系統的發展
針對推薦系統的研究開始於20世紀90年代，隨著網路的普及，該技術被逐步應用到各個行業。推薦系統主要由使用者建模部分、推薦物件建模部分以及推薦演算法部分共同組成，其中推薦演算法部分是整個推薦系統的核心，也是研究的關鍵和熱點。目前被廣泛使用的協同過濾推薦演算法來源於Tapestry和GroupLens系統的論文，該演算法被用於郵件和新聞的過濾。協同過濾演算法也被稱為基於鄰域模型的推薦演算法，即鄰域實質相似項的集合。使用者間存在相似的興趣，或者某些物品間存在相似的特徵，因此基於鄰域的推薦演算法又被分為兩類：基於使用者的協同過濾（UserCF）推薦演算法和基於物品的協同過濾（ItemCF）推薦演算法。UserCF演算法主要包括兩步：找出與目標使用者有相似興趣的使用者集；把使用者集中其他使用者喜歡且目標使用者沒標註過的物品推薦給目標使用者。餘弦相似度可用下式計算：
其中，S（a）和S（b）分別表示使用者a、b有反饋資訊的物品集合。在推薦系統中，使用者數量往往較大，使用者之間兩兩計算相似度會帶來較高的演算法複雜度，因此如何定義使用者間的相似度成為最佳化研究的重點，如Breese J S等人提出利用使用者行為進行相似度計算。
由於UserCF演算法複雜度較高，目前Amazon、Netflix等平臺都將ItemCF演算法作為推薦演算法的基礎。可使用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。如果在推薦演算法的設計中將兩類模型進行融合，可能會起到優勢互補的作用，從而獲得更好的推薦效果。
隱語義模型的思想最初於文字挖掘領域被提出，後來擴充套件改進的方法包括隱含狄利克雷分佈（latent Dirichlet allocation，LDA）主題模型、機率潛在語義分析（probabilistic latent semantic analysis，PLSA）、主題建模（topic model）等。透過矩陣降維的方式進行評分矩陣補全、應用隱語義模型應對推薦系統中冷啟動問題成為一個有效方法。奇異值分解是一種用於發現文字中潛在因子的方法，它將高度相關並共同出現的相似詞語作為因子，從而把大規模的文字向量矩陣拆解為低階的相似矩陣。除此之外，相關的方法還有主成分分析（principal component analysis，PCA）和隱含狄利克雷分佈主題模型等。早期，評分矩陣稀疏且SVD演算法計算複雜度較高，導致基於SVD的推薦演算法沒有引起重視。直到Koren Y等人在Funk-SVD的基礎上加入偏置項，並且把使用者歷史行為考慮在內提出SVD++模型之後，才大大提升了演算法的效果。
2。2 評分預測與TopN推薦問題
利用已有資料資訊來預測使用者對未評分的物品集合的評分的研究被稱為推薦系統研究中的評分預測。在評分預測研究中，基本資料集是使用者的歷史評分資料，在該資料集中，通常每條記錄資料用三元組（u，i，r）來表示。其中，u表示使用者，i表示物品，r表示對該物品的評分。評分預測的準確性可以透過RMSE和MAE來衡量。在推薦系統中，真實值
rui
是使用者u對物品i的評分，預測值
是推薦系統給出的預測結果，又因為在離線實驗中資料集被分為測試集和訓練集，所以觀測次數在這裡指的是測試集的大小。RMSE和MAE的定義如下：
其中，T表示整個測試集，Test表示實際測試時使用的測試集。
從指標的定義可以看出，兩個測試指標的值與評分預測的準確性呈現負相關的趨勢，即測評指標越小，評分預測準確性越高。相較於MAE指標，RMSE指標因為平方和的形式更加放大了誤差的影響，對於推薦演算法的評測來說，RMSE更加嚴格。
TopN推薦問題指在給使用者的個性化推薦列表中，設定哪些產品進行優先呈現。To p N推薦預測的效果一般使用準確率（precision）和召回率（recall）來衡量，兩者分別表示有多少比例的推薦選項被使用者選中以及有多少比例的推薦選項進入了使用者的最終列表，其定義如下：
其中，R（u）表示訓練集上生成的給使用者的推薦列表，T（u）表示使用者在測試集上生成的行為列表，U表示使用者集。目前大多數推薦演算法的相關研究是基於使用者的評分資料的，因此有許多研究人員探索如何最佳化RMSE和MAE兩個評分指標。同時TopN推薦問題也受到產業界各大網際網路公司的關注。本文結合研究背景進行實驗設計，主要從評分預測的角度來定義推薦演算法，並進行評測。
3 演算法研究與模型訓練
3。1 基於SVD++的信任網路推薦演算法設計
本文在信任網路的研究背景下，從推薦演算法研究中的評分預測問題出發設計推薦演算法，即在確定使用者的相關歷史資料和相關信任關係的情況下，對使用者未評分的物品進行評分預測。傳統的隱語義模型主要利用矩陣因子分解的方式，從評分預測的角度定義推薦演算法的損失函式，沒有完全考慮使用者的歷史行為資料。Koren Y提出的Simon模型加入了使用者的歷史行為資料，其設計的SVD++演算法取得了良好的評分預測效果。Simon模型的評分預測式如下：
其中，bui表示預測的基準估計值，
表示從評分矩陣中分解的使用者向量，
與
的向量乘積表示使用者的顯式評分對預測結果的影響。N（u）表示與使用者u的潛在偏好有聯絡的群體，yj表示N（u）群體的隱式反饋。因為資料集具有稀疏性特點，所以隱式資料的體量多於顯式資料，因而本文設定正則化處理係數-β，β∈［0，1］。β=0表示隱式反饋影響較大，β=1則表示隱式反饋的影響幾乎被抵消，本文選取β=0。5。結合信任網路中的奇異值分解，首先將使用者向量與信任者向量進行統一，之後逐步把信任關係代入SVD++模型：
其中，pv表示可以反映顯式信任的被信任者，
表示使用者u信任的使用者v對使用者u進行未知物品評分預測的影響，
表示使用者u作為顯式信任者對評分預測的影響。然後需要考慮隱式信任關係的影響，同理可用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 採用梯度下降演算法求解損失函式的最優解
首先，定義評分值、顯式信任數值以及隱式信任數值的表達誤差：
損失函式對引數bu、bi、uu、vi、yj、pv、wv、sij、cij求偏導：
由式（17）～式（19）的計算可以得到引數的偏導結果，下面給出其關鍵運算步驟的虛擬碼，演算法1的作用是透過文字進行資料輸入預處理，生成3個矩陣，演算法2為採用隨機梯度下降演算法進行推薦演算法迭代訓練模型的虛擬碼流程，並在最後給出其評分預測結果。
演算法1：輸入資料預處理
1。R = Matrix（m，n）， T = Matrix（m，m）， Ti = Matrix（m，m） //3個空矩陣宣告
2。open（“ratings。txt”， “trust。txt”） as file_r， file_t； //讀取原始檔資料
3。for line_r， line_t in file_t， file_t：
4。addToMatrix（line_r， R）；
5。addToMatrix（line_t， T）；//逐行進行矩陣R、T的構建
6。Ti = PCC（R）； //採用PCC進行相似度計算，並轉換為隱式信任矩陣
演算法2：利用本文的推薦演算法進行評分預測
1。Input： R， T， Ti， d， λ， λt1， λt2， α， iter
2。for count = 1 to iter do：
3
， u = 1， … ， m
4。
，i = 1， … ， n
5。
，u = 1， … ， m
6。
，i = 1， … ， n
7。
，∀j∈N（u）
8。
，
9。
， ∀ v∈Ti（u）
10。
11。
12。end
13。Output： RMSE， MAE
在演算法的複雜度分析方面，本文設定t為損失函式的迭代次數，d為隱語義模型降維後的向量維度，|Ω|為評分矩陣中所有非空項的數目，|Φ|為顯式信任矩陣中所有非空項的數目，|Λ|為隱式信任矩陣中所有非空項的數目。因為在求解損失函式的過程中包含了評分預測值的計算，所以在計算時間複雜度時需要先透過式（15）計算評分預測損失函式的時間複雜度，為
。然後由式（17）~式（19）求導 得：
。假設
，則可以得到本文推薦演算法的時間複雜度為
，其與隱語義模型的向量維度和訓練迭代的次數線性相關。
4 實驗
本文的實驗部分主要是在開源資料集Epinions上對本文設計的推薦演算法與經典的TrustMF演算法進行對比，實驗方法採用離線實驗。將離線的實驗資料集分為訓練集和測試集，在訓練集上進行使用者的興趣模型訓練，然後在測試資料集上對訓練的模型進行預測測試，並用相關指標演算法進行評分。在對比物件的選擇方面，選擇TrustMF的原因是：相較於其他相關研究信任網路下的推薦演算法（如SoRech、SocialMF等相關演算法），該演算法可以在評分預測問題中取得較好的成績。
本文實驗選擇的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。
實驗評測指標主要選取RMSE和MAE，這兩個指標數值都反比於推薦預測的準確性，即指標數值越小，則誤差越小，準確性越高。在進行實驗前，將Epinions資料集隨機劃分為5份，1份是測試集，其餘4份是訓練集，演算法中已知引數的設定見表4。
為了說明本文設計的演算法對冷啟動問題的最佳化作用，實驗先從推薦系統冷啟動的角度開始進行。推薦系統的冷啟動是指在進行評分預測時，測試集中只選用評分物品數量小於5的使用者來進行測試。實驗結果見表5。
從實驗結果可以得出，除個別情況下某一指標（d=10時本文演算法的MAE略大於TrustMF的MAE）稍差，其他情況下本文演算法都優於其他各個推薦演算法的冷啟動效果。可以證明，相比於其他參考演算法，本文的推薦演算法在解決冷啟動問題方面更好。迭代最佳化實驗則使用所有使用者作為測試集，得到的評分預測結果見表6。
從表6可以看出，所有演算法的實驗評測效果均好於冷啟動實驗組的評測結果。這是因為在冷啟動時遇到的資料稀疏問題影響了推薦系統的效果。而採用全部使用者集上的資料時，因為包括熱門使用者和產品，所以提升了演算法的推薦效果。同時從實驗結果看，相比其他演算法，本文演算法的評測結果有一定的最佳化提升。
為了進一步瞭解信任網路對推薦演算法最佳化的影響，本文以使用者在信任網路中的度為依據進行使用者群體的劃分設計測試集。將使用者視為圖論中的點，修改點的出度和入度之和就是修改點在信任網路圖中的度。本文取隱式向量維度d=10，與TrustMF進行對比測試，如圖2所示。
從圖2可以看出，隨著信任網路中度數的增加，推薦演算法對使用者興趣的預測準確率基本呈上升趨勢。而且，在多數情況下，本文的推薦演算法因為結合了隱語義模型和顯式信任關係，推薦結果的評分預測精度更高，效果優於對比演算法TrustMF。
圖2 當d=10時，不同信任網路度數的MAE值和RMSE值
5 結束語
作為推薦系統的核心，對推薦演算法的研究受到學術界和產業界的廣泛關注和重視，評分預測是推薦演算法研究中的核心問題。傳統推薦演算法在面對顯式行為資料稀疏時容易出現冷啟動的問題，為了緩解該問題對推薦演算法進行評分預測的準確度的影響，本文結合信任網路的特點和使用者信任關係資料進行建模，設計了適用於信任網路的推薦演算法，並進行了相關實驗評測。本文將使用者行為資料分為顯式行為資料和隱式行為資料，因為輸入的使用者關係資料中具有二元顯式信任關係，本文基於使用者之間的相似度來設定使用者之間的隱式信任關係，結合顯式信任關係資料、評分資料以及隱式信任關係資料一起進行預處理，生成矩陣，進行建模。
在隱語義模型的選擇上，本文借鑑SVD++模型，結合信任網路的特點進行改進，並融合了鄰域模型進行推薦演算法的評分預測函式和損失函式的設計。然後利用隨機梯度下降演算法進行函式中的引數迭代求導，直至損失函式收斂於最小值，從而求得最佳化後的相關引數，將其代入評分預測函式後得到推薦演算法評分預測值。最後本文透過開源資料集，採用離線測試的方案，使用RMSE和MAE兩個典型評測指標對本文設計的推薦演算法和TrustMF演算法進行評測實驗。實驗結果證明，本文設計的推薦演算法在信任網路中優於其他參照演算法，對於解決推薦系統的冷啟動問題有良好的效果，並具有一定的實用意義。
聯絡我們:
Tel:
010-81055448
010-81055490
010-81055534
E-mail:
bdr@bjxintong。com。cn
http：//www。infocomm-journal。com/bdr
http：//www。j-bigdataresearch。com。cn/
轉載、合作：
010-81055537
大資料期刊
《大資料（Big Data Research，BDR）》雙月刊是由中華人民共和國工業和資訊化部主管，人民郵電出版社主辦，中國計算機學會大資料專家委員會學術指導，北京信通傳媒有限責任公司出版的期刊，已成功入選中國科技核心期刊、中國計算機學會會刊、中國計算機學會推薦中文科技期刊，並被評為2018年、2019年國家哲學社會科學文獻中心學術期刊資料庫“綜合性人文社會科學”學科最受歡迎期刊。
關注《大資料》期刊微信公眾號，獲取更多內容
