融合多信息的跨域推薦算法

鐘俊偉，張立臣

（廣東工業大學計算機學院，廣州 510006）

0 引言

隨著互聯網的快速發展，如今的信息量也呈幾何式的增長，信息超載已經成為了不可忽視的問題。推薦系統是解決信息超載問題的有效途徑，它能通過用戶和項目的信息向用戶推薦其感興趣的信息和商品，使人們更高效地獲取需要的信息。

協同過濾是推薦系統中效果比較好的算法，其為一個用戶找到與他有相似興趣的其他用戶，將他們感興趣的內容推薦給此用戶，由于其速度與效果均比較良好，是目前互聯網鄰域使用較多的一個算法。然而，在當前的互聯網環境下，隨著用戶規模和項目數量的急劇增長，傳統的協同過濾推薦算法的缺陷逐漸暴露出來，特別是新用戶、新項目和新系統的冷啟動以及用戶行為數據稀疏等問題，這些問題致使協同過濾推薦性能降低，推薦效果不佳。

而來自于不同平臺（社交媒體和電子商務網站等）的用戶興趣偏好或項目特征（屬性、類別等）之間存在很強的關聯性和依賴性?？缬蛲扑]可以從其它鄰域中獲取有效的用戶偏好或項目特征的信息來豐富目標鄰域中的數據，精準地預測用戶行為，提供更加合理和個性化的推薦服務。

近年來，國內外研究人員對跨域推薦進行了不少研究。Li等提出了通過基于碼本的知識轉移（Codebook Transfer，CBT）進行跨域推薦，該方法可以從其他一些鄰域的輔助評分矩陣中轉移有用的知識，以彌補評分矩陣的稀疏性。通過將集群級別的用戶項目評分模式壓縮為信息豐富且緊湊的知碼本進行遷移，可以通過擴展碼本來重建稀疏目標評級矩陣。Yu等提出了一種具有擴展的雙邊跨域協同算法，通過輔助域的潛在因子空間進行用戶和項目特征分類，可以將知識輔助域的用戶和項目側擴展到目標域的原始特征向量。Veeramachaneni等提出了使用最大邊際矩陣分解對評級矩陣進行知識提取，通過重建目標評級矩陣進行跨域推薦。陳燕等利用概率矩陣分解對源域評分矩陣進行提取特征，再利用給予模擬退火和遺傳算法優化的K-means算法進行聚類，最后利用得到的各領域重疊分組得到共享評級。

上述算法從跨域推薦的角度來解決數據稀疏與冷啟動的問題，相對于傳統單域中的協同過濾，在一定程度上減少了數據稀疏帶來的預測問題，提高了預測的準確性。但大多依然停留在僅對評分矩陣進行知識的提取，對于數據源含有的如評論時間、項目分類等信息依然沒有充分地利用，如果能夠將這些信息融入到推薦的過程中，那么推薦的精準度將能有所提升。

為了解決上述問題，本文的工作如下：

（1）提出使用譜聚類取代傳統跨域推薦CBT算法的雙邊K-means聚類，提升提取信息時的準確度。

（2）提出對用戶側數據處理中引入時間信息的加權相似度方法，項目側引入類別信息的加權相似度方法，將多信息融入到推薦中。

（3）在MovieLens-Latest與豆瓣電影數據集中使用改進的算法與對比推薦算法進行實驗分析，結果表明本文的算法準確性優于對比推薦算法。

1 密碼本遷移算法（CBT）

CBT算法是目前通過矩陣分解進行推薦中使用較多的跨域協同過濾算法，其利用正交非負三分解（ONMTF）將源評分矩陣進行三分解，從而獲取評分矩陣中用戶側的聚類知識與項目側的聚類知識，ONMTF不同于非負矩陣分解（NMF）將矩陣分解為兩個部分，ONMTF將非負正交矩陣分解為三個因子，如公式（1）所示：

式（1）中代表了矩陣的行向量的聚類特征，代表了矩陣的列向量的聚類特征，則可以認為是縮放因子。

由于矩陣的正交非負限制，一般來說實現ONMTF會利用對矩陣進行雙邊kernel K-means聚類來獲得分解結果，則對評分矩陣使用ONMTF就可以獲得評分矩陣用戶側的聚類知識與項目側的聚類知識。

獲取到了源域的聚類知識并進行交替更新后，CBT算法根據這些群集的聚類知識構造密碼本，以密碼本作為兩個鄰域的信息傳輸媒介，密碼本的構建方法如公式（2）所示：

式中為源域的評分矩陣；，是二值化矩陣，先從源域中通過ONMTF分解得來的兩個因子，交替更新，每行中最大的表示為1，其余為0；1表示元素全為1的向量。

得到密碼本后，由于密碼本含有源域中獲取的群集聚類知識，可以通過目標域的評分矩陣與的交互擴展來取得結合源域中遷移的知識的新目標域預測矩陣。具體重建矩陣方法如公式（3）所示：

通過CBT算法可以將通過信息更新為稠密的輔助源域提取信息，將原來稀疏的目標域評分矩陣擴充為評分信息更為飽滿的評分矩陣，從而達到緩解數據稀疏和冷啟動問題的目的。

2 融合多信息的跨域推薦

本文針對傳統跨域推薦算法在輔助域評分矩陣提取信息時的精確性和未使用域中更多信息的問題，提出一種基于譜聚類的融合多信息的改進跨域推薦算法。首先使用雙邊譜聚類替換在ONMTF分解時使用的雙邊K-means聚類，再利用譜聚類的特性，將用戶評價時間信息和物品分類信息通過相似度矩陣的加權融合加入到提取信息的過程，完成多信息的融合。

2.1 譜聚類

CBT算法中使用ONMTF算法分解獲得輔助域的行聚類特征和列聚類特征，分解過程直接使用與NMF等價的kernel K-means，對輔助域評分矩陣進行雙邊的K-means聚類，但由于評分矩陣的稀疏性，K-means聚類的結果并不一定能達到最好的效果。

譜聚類的主要思想是將數據看作無向權重圖，每條數據當作圖中的點，點與點之間的邊根據權重值來決定，通過對所有數據點組成的圖進行切圖，使得切圖后不同子圖間的邊權重和盡可能低，子圖內的邊權重高，從而達到聚類的目的。

譜聚類由于只需要數據之間的相似度矩陣，因此對于稀疏數據的聚類很有效，與之對比，K-means一般難以達到其精準度，這是非常有利于對稀疏評分矩陣使用的，而譜聚類在使用ncut方式來切圖的時候與kernel K-means是等價的，因此在ONMTF分解時，同樣可以使用雙邊的譜聚類來完成，其依然能夠將矩陣中的數據提取出來。本文提出將ONMTF算法中使用的K-means雙邊聚類替換為使用譜聚類進行雙邊聚類，其不僅可以將提取信息的準確性提升，同時也為引入數據中更多信息用于推薦提供了可能性。

具體的，譜聚類首先需要生成相似矩陣，根據相似矩陣構建鄰接矩陣和度矩陣，再通過鄰接矩陣和度矩陣求出拉普拉斯矩陣，歸一化拉普拉斯矩陣后，生成最小的聚類個數特征值和對應的特征向量，最后將特征向量使用傳統聚類算法聚類即可得到結果，由于譜聚類返回的結果并不包含聚類中心，本文取聚類標簽的點的平均值作為ONMTF中雙邊聚類的結果。

2.2 融入用戶側時間信息

用戶評價時間可以反映用戶的興趣趨勢，由于用戶的興趣點將隨著時間而遷移，因此可能曾經喜歡的物品在當下就會變得沒有那么喜歡，用戶會更傾向于選擇目前興趣最濃厚的物品，如果能夠將時間信息融入到推薦過程中，那么推薦的結果將更為準確。

本文利用用戶隨時間遷移興趣的特征，設計了一種隨時間的變化而改變的函數以表示用戶的興趣度，如公式（4）所示：

式中T表示用戶在評價物品時的時間，表示用戶第一次評價的時間，T表示用戶最新評價的時間。

在獲得了時間興趣度函數F后，目標就是將其整合到推薦過程中，由于譜聚類對相似度矩陣的敏感性，因此將相似度矩陣作為融合切入點，將時間信息融入其中，本文通過將皮爾遜相關系數與F融合得到綜合相似度，從而達到融入信息的目的，具體如公式（5）所示：

得到了融合時間信息的相似度算法后就可以構建用戶側相似度矩陣用于用戶側信息提取。

2.3 融入項目側分類信息

對于項目側，由于項目本身就擁有天然的分類方式——類型信息，同類型項目的相似度一般會比不同類型的相似度更高，本文在項目側引入分類信息。

具體的，由于項目數據中一般都含有項目所屬類型信息，且其一般不只是唯一的，因此如果通過類型信息來決定相似度則需要使用一個相似度的衡量方法。由于類型信息一般都為文本信息，且擁有公共集，兩個項目間擁有交集的可能性也比較大，本文使用Jaccard相似度作為分類信息的相似度度量方法，如公式（6）所示：

式中，表示兩個項目的類型集合。

項目的相似度單獨使用類型信息來衡量的話顯然不是很好的選擇，因此本文還使用了項目側評分矩陣的余弦相似度作為加權組合，余弦相似度如公式（7）所示：

最終的相似度矩陣由對類型信息使用Jaccard相似度取得的相似矩陣和對項目側評分矩陣使用余弦相似度取得的相似矩陣加權綜合求出，如公式（8）所示：

得到了融入類別信息的加權相似度算法后則能夠構建項目側相似度矩陣，結合之前獲取到的用戶側相似度矩陣則能夠進行雙邊的譜聚類，獲取融合了多信息的知識聚類，從而能夠構建更為準確的密碼本進行知識的遷移。

3 實驗驗證

3.1 實驗數據集

（1）豆瓣電影數據集：包含416萬條電影評分，63萬用戶，14萬部電影，評分范圍為1～5。從中提取擁有較稠密評分的子矩陣作為轉移信息的輔助域，其中包含173個用戶和247個項目，數據總條目為12775條，其密度為29.89%。同時，也提取部分數據作為目標域，為了稀疏矩陣的模擬，提取其中的500個評分數目大于20的用戶，提取后的數據總條目為17656條，擁有500個用戶，975個項目。其中300個用戶共10935條評分條目作為訓練集，200個用戶共6721條評分條目作為測試集。

（2）MovieLens-Latest數據集：包含10萬條電影評分，600名用戶，9000個項目，評分范圍為1～5。同樣提取出500個評分數目大于20的用戶，提取后的數據總條目為55372條，擁有500個用戶，1297個項目。其中300個用戶共32741條評分條目作為訓練集，200個用戶共22631條評分條目作為測試集，數據稀疏度如表1所示。

表1 數據稀疏度

3.2 評價指標

本文采用平均絕對誤差（MAE）作為評價指標，MAE評價值越低越好，計算見公式（9）：

式中p為預測評分，r為真實評分，為測試的次數。

3.3 實驗算法

（1）奇異值分解SVD：一種經典的單域協同過濾算法，這里主要使用的是User-Based SVD，可以與跨域協同算法比較預測結果。

（2）非負矩陣分解NMF：同樣是經典的單域協同過濾算法，這里用來與SVD進行比較，防止單個算法的預測不佳是由于對數據的不支持所導致。

（3）CBT：一種跨域協同過濾算法，是本文改進算法的基礎算法，用于比較改進算法的效果。

（4）SC-CBT（Spectral Clustering-CBT）：本文提出的基于譜聚類的CBT算法，主要用于比較加入多信息后的GSC-CBT是否效果更佳。

（5）GSC-CBT（Gathered Spectral Clustering-CBT）：本文提出的算法，與其他算法進行對比。

3.4 實驗流程

實驗首先對兩個稀疏數據集使用傳統的協同過濾算法SVD和NMF，在不同的近鄰個數下查看預測MAE，實驗結果使用matplotlib進行繪圖，以便與跨域協同過濾算法進行對比。

從圖1和圖2可以看到，對稀疏度如此高的評分矩陣使用SVD與NMF兩種單域算法的效果并不好，預測的結果較差，傳統單域推薦算法在數據稀疏條件下的發揮并不理想。

圖1 對豆瓣數據集使用SVD與NMF的結果

圖2 對MovieLens-Latest數據集使用SVD與NMF的結果

之后對跨域協同過濾算法進行對比實驗，實驗中遷移密碼本用戶側聚類數目和項目側聚類數目設置為*，用提取的密度較高的豆瓣數據對稀疏的豆瓣數據和稀疏的MovieLens-Latest數據進行跨域推薦實驗。

圖3 不同跨域推薦算法在豆瓣數據集下的MAE對比

圖4 不同跨域推薦算法在MovieLens數據集下的MAE對比

實驗結果表明，加入多信息的GSC-CBT比單純改用譜聚類的SC-CBT的預測結果更優秀，且兩個改進算法都比原始CBT算法更精準。值得注意的是聚類個數為40時，三個算法在MovieLens-Latest數據集中的差別并不大，且在豆瓣數據集中SC-CBT效果比CBT要差，推測在這個聚類數目時三種算法從輔助域提取的信息差別不大?？傮w來看，融入多信息的GSC-CBT是最佳的選擇。

4 結語

本文提出了一種基于譜聚類融入多信息的跨域推薦算法，可以較好地解決協同過濾中冷啟動用戶和評分矩陣稀疏度較高的問題。實驗結果表明，GSC-CBT算法可以對傳統單域推薦無法得到較好結果的推薦問題進行跨域知識遷移，獲得一個不錯的預測結果，與現有算法對比準確度也有所提升。