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

鐘俊偉，張立臣

（廣東工業(yè)大學(xué)計算機學(xué)院，廣州 510006）

0 引言

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

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

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

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

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

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

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

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

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

1 密碼本遷移算法（CBT）

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

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

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

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

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

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

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

2 融合多信息的跨域推薦

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

2.1 譜聚類

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

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

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

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

2.2 融入用戶側(cè)時間信息

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

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

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

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

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

2.3 融入項目側(cè)分類信息

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

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

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

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

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

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

3 實驗驗證

3.1 實驗數(shù)據(jù)集

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

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

表1 數(shù)據(jù)稀疏度

3.2 評價指標(biāo)

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

式中p為預(yù)測評分，r為真實評分，為測試的次數(shù)。

3.3 實驗算法

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

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

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

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

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

3.4 實驗流程

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

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

圖1 對豆瓣數(shù)據(jù)集使用SVD與NMF的結(jié)果

圖2 對MovieLens-Latest數(shù)據(jù)集使用SVD與NMF的結(jié)果

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

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

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

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

4 結(jié)語

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