李衛(wèi)疆 鄭雅民

(昆明理工大學信息工程與自動化學院 云南 昆明 650000)

0 引 言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，推薦系統(tǒng)得到人們越來越多的關注，提供有效的用戶個性化推薦是目前研究的熱點問題，通過對用戶歷史行為的分析，預測用戶偏好。近年來，結(jié)合用戶社交網(wǎng)絡的推薦算法目前已經(jīng)得到廣泛的應用，TidalTrust通過在信任網(wǎng)絡中找到從用戶到每個其他用戶的最短路徑，然后將每個用戶的信任值聚合到與A直接相鄰的用戶進行推薦[1]。Li等基于奇異值分解的方法，根據(jù)人際關系中的六度分隔理論填充用戶信任矩陣，再通過用戶之間的信任度進行相關推薦[2]。用戶的社交網(wǎng)絡不僅可以有效緩解推薦中冷啟動的問題，還可以通過好友推薦增加推薦的信任度。

但在社交網(wǎng)絡中，好友關系不是基于共同興趣產(chǎn)生的，用戶好友的興趣往往和用戶的興趣不一致。同時，信任網(wǎng)絡通常是一組不相交的子圖，信任無法從一個子圖傳播到另一個子圖上，如果一個項目沒有被子圖中的任何用戶評分，那么它就不會被推薦給子圖中有可能感興趣的用戶。因此，僅僅基于用戶之間的信任關系進行推薦會存在項目的覆蓋問題。同時，推薦算法的覆蓋率和準確率存在內(nèi)在的折中，在提高推薦覆蓋率的同時會降低推薦的準確率，反之亦然。

為此，我們提出了一種融合項目流行度和用戶信任關系的PopTruMF算法。PopTruMF算法利用矩陣分解的傳遞性，將用戶的信任關系與項目評分視為同一層級，在矩陣分解的過程中，項目和信任關系發(fā)生混合，使得信任傳遞和評分預測同時發(fā)生；同時PopTruMF算法根據(jù)項目的流行度，對用戶評分項目和未評分項目分別進行加權(quán)處理，在保證了準確率的基礎上，有效改善了以上方法的覆蓋率。本文的主要創(chuàng)新點在于：

(1) 在基于信任網(wǎng)絡的推薦算法中，提出在不相交的信任網(wǎng)絡中進行推薦。

(2) 在基于項目的流行度的推薦算法中，提出項目流行度對用戶評分項目和未評分項目有不同程度的影響。

(3) 本文在Epinions數(shù)據(jù)集上進行了大量的實驗，實驗結(jié)果表明PopTruMF算法在大幅度改善推薦覆蓋率的同時，保證了推薦的準確率，能夠給于用戶更好的推薦結(jié)果。

1 相關工作

1.1 矩陣分解

(1)

式中：w0代表缺失數(shù)據(jù)賦予的統(tǒng)一權(quán)重。

1.2 信任網(wǎng)絡

美國著名的尼爾森調(diào)查表明83%的用戶更愿意相信朋友對他們的推薦，因此，基于信任關系的推薦可以更好地模擬現(xiàn)實社會。信任網(wǎng)絡是基于信任傳遞構(gòu)建的有向圖，通過使用用戶之間的信任關系和用戶的歷史行為數(shù)據(jù)來預測評分，不僅可以提高推薦系統(tǒng)的推薦質(zhì)量，還可以增加用戶對系統(tǒng)的信任度[2,4-6]。

本文構(gòu)建了一個簡單的信任網(wǎng)絡實例，如圖1所示，其中，節(jié)點代表用戶，邊代表用戶之間的信任關系。信任傳遞是信任網(wǎng)絡的一個重要特征，用戶可以通過具有直接信任關系的用戶作為紐帶傳遞給具有間接信任關系的用戶。如圖1所示，用戶u1對項目i2、i3有歷史評分，用戶u2對項目i1、i2、i3、有歷史評分，用戶u3對項目i2、i3、i4有歷史評分。因為用戶u1和用戶u3在相同的信任網(wǎng)絡中，通過信任傳遞我們可以將用戶u3偏好的項目i4推薦給用戶u1。但由于左側(cè)信任網(wǎng)絡子圖中沒有用戶節(jié)點對項目i4進行評分，則不能通過信任關系將項目i4推薦給用戶u1。

圖1 不相交的用戶信任網(wǎng)絡實例

1.3 項目流行度及數(shù)據(jù)稀疏問題

類似于頭條新聞、微博熱榜等根據(jù)PV、UV、日均PV或分享率等數(shù)據(jù)，按某種熱度排序推薦給用戶，很多應用也以熱門排行榜、最熱賣排行榜、平均用戶評分等形式展示當下流行的項目。項目被用戶評分的次數(shù)越多，代表項目流行度越高；反之，則越低。作為推薦系統(tǒng)的新用戶，或在人很難做出選擇的時候，項目的歷史評分確實是很有用的參考信息，且人們通常愿意接受流行項目的推薦[6-7]?；陧椖苛餍卸鹊耐扑]算法，可以深度挖掘用戶偏好，給予不同用戶個性化的推薦[9]。

郝立燕等基于TopN推薦預測提出，流行度越高的項目，體現(xiàn)用戶興趣的信息越少，相反，流行度越低的項目，體現(xiàn)用戶興趣的信息越可靠，提高了冷門項目的影響力[8]。但是用戶-項目評分矩陣中評分項目一般不超過項目總數(shù)的1%，更多的是缺失的數(shù)據(jù)，因此，解決數(shù)據(jù)稀疏問題通常是提高推薦質(zhì)量的關鍵。文獻[9]將這些缺失的數(shù)據(jù)統(tǒng)一假定為無關用戶偏好進行建模，極大地減少了建模的工作量，然而這種方法是不現(xiàn)實的，會降低模型的預測性。在此假設的基礎上，文獻[10]將缺失的數(shù)據(jù)賦予統(tǒng)一的權(quán)重，然后在缺失數(shù)據(jù)上設置顯式先驗，當新的用戶或項目評分進入系統(tǒng)時，可以及時更新因子，給與符合最新用戶偏好的推薦，但這樣的假設限制了推薦算法在實際應用中的可擴展性。針對以上問題，參考現(xiàn)有的推薦方法，本文提出了PopTruMF模型。

2 PopTruMF模型

本文首先合并用戶-項目評分矩陣和用戶-用戶信任關系矩陣來構(gòu)建模型；然后，根據(jù)項目流行度的加權(quán)策略構(gòu)建目標函數(shù)；最后，通過矩陣分解的方式同時傳遞信任和推薦項目。

2.1 TruMF算法

2.1.1基于項目節(jié)點傳遞信任

在信任網(wǎng)絡中，由于好友關系不是基于共同興趣產(chǎn)生的，用戶好友的興趣往往和用戶的興趣不一致，而不存在信任關系的用戶卻具有相似的用戶偏好。如圖2所示，用戶u2和用戶u3在不同的信任網(wǎng)絡，但對項目i2、i3都有顯示反饋，本文認為用戶u2和用戶u3具有相似的用戶偏好，只不過他們不認識對方。

圖2 相交的用戶信任網(wǎng)絡實例

本文將項目作為節(jié)點引入信任網(wǎng)絡，相似的用戶偏好作為不同信任網(wǎng)絡子圖之間的紐帶，用戶可以通過項目節(jié)點連接不同的信任網(wǎng)絡子圖。此時，信任網(wǎng)絡將不再是原始的信任網(wǎng)絡，一個用戶節(jié)點具有連接用戶信任關系和用戶相似偏好兩種不同的邊。用戶u2和用戶u3通過相似的用戶偏好建立連接，項目i1通過項目節(jié)點從用戶u2傳遞給用戶u3，再通過信任傳遞從用戶u3最終推薦給用戶u1。

2.1.2 基于矩陣分解傳遞信任

為了解決信任網(wǎng)絡脫節(jié)的問題，首先，通過用戶-項目評分和用戶-用戶信任關系分別構(gòu)建兩個矩陣，如圖3(a)、(b)所示。然后，通過合并這兩個矩陣來構(gòu)建模型，如圖3(c)所示。在模型中，項目評分和用戶之間的信任關系視為同一層級，通過矩陣分解的方式可以同時傳遞信任和推薦項目。也就是說，給定K個潛在特征向量，每個用戶通過這K個特征向量對每個項目進行評分，同時，每個用戶通過相同的K個特征向量來信任其他的用戶。

(a) 用戶-項目 (b) 用戶-用戶

(c) 用戶-項目-用戶圖3 合并評分矩陣和信任關系矩陣

如圖3(c)所示，用戶u2和用戶u3之間不存在信任關系，但對項目i2和項目i3都具有顯示反饋，本文認為用戶u2和用戶u3之間具有相同的特征向量。通過相同的特征向量，用戶u2可以將感興趣的項目i1推薦給用戶u3，再通過用戶之間的信任關系，最終用戶u3可以將項目i1推薦給用戶u1，從而解決了個性化推薦中廣泛存在的信任網(wǎng)絡脫節(jié)的問題。

2.2 項目流行度的加權(quán)策略

隨著Web 2.0的發(fā)展，在所有其他因素相同的情況下，流行度較高的項目更有可能被用戶認識。本文認為，項目流行度對用戶評分項目和未評分項目分別有不同程度的影響。

2.2.1項目流行度對未評分項目的影響

在推薦系統(tǒng)中，缺失數(shù)據(jù)(未評分項目)是負反饋和未知反饋的混合物，然而區(qū)分這兩種情況是眾所周知的困難。文獻[12]提出，在缺失數(shù)據(jù)中，流行的項目更可能是用戶的負反饋而非未知的反饋，因此，在模型訓練的過程中應該給予更高的權(quán)重。本文引入文獻[11]中的一個權(quán)重因子：

ci=c0×item_pop(i)

(2)

(3)

2.2.2項目流行度對評分項目的影響

隨著互聯(lián)網(wǎng)的發(fā)展，通過網(wǎng)絡傳播、媒體曝光、社區(qū)討論等方式，流行度較高的項目，更有可能被用戶認識，因此會獲得更多偏離用戶個人偏好的評分。對于矩陣中評分項目的數(shù)據(jù)，文獻[8]認為項目的流行度越高，用戶評分體現(xiàn)用戶偏好的信息越少，相反，項目的流行度越低，用戶評分體現(xiàn)用戶偏好的信息越可靠。參考文獻[8]，本文提出了一個與項目流行度相關的誤差權(quán)重因子：

(4)

式中：r=wuirui表示體現(xiàn)用戶偏好的項目評分。fi最小為1，此時wui為最大值1。fi越低，wui越大，用戶項目評分rui越接近用戶偏好評分r；反之，wui越小，用戶項目評分rui越偏離用戶偏好評分r。

2.3 PopTruMF算法

根據(jù)以上分析，本文設計了一個基于項目流行度的目標函數(shù)：

(5)

首先，本文對用戶項目評分根據(jù)項目流行度進行預處理，得到更接近用戶偏好的評分r。式(5)中: 第一項代表用戶偏好評分預測的誤差，在顯示評分預測中廣泛使用[12]；第二項代表缺失數(shù)據(jù)中負反饋對評分預測的影響[11]；第三項代表一個正則項來防止目標函數(shù)的過擬合。為了獲得目標函數(shù)的最小值，本文通過在pik、qku上使用梯度下降的方法訓練模型:

(6)

(7)

(8)

(9)

基于項目流行度的加權(quán)策略，本文模型訓練如算法1所示：

算法1Matrix Factorization

輸入：合并矩陣R，潛在特征向量K，預測評分的誤差權(quán)重wui，缺失數(shù)據(jù)的權(quán)重c0

輸出：用戶潛在特征矩陣P，項目潛在特征矩陣Q

1. Randomly initializePandQ;

2. for (u,i)∈Rdorui=puqi;

3. while Stopping criteria is not

4. //Update user、item factors

5. fori←1 to len (R)

6. foru←1 to len (R1)

7. fork←1 toK

8.wui,ci←Eq.(2,3,4);

11. fori← 1 to len (R)

12. foru← 1 to len (Ri)

14. fork← 1 toK

16. Ife<0.001

17. break;

18. ReturnP,Q·T;

預測評分由模型訓練得到的用戶特征向量pu和項目特征向量qi的內(nèi)積產(chǎn)生。在預測評分構(gòu)成的新矩陣中，由于信任矩陣部分通常被認為是算法的次要結(jié)果，本文對此先進行過濾，再生成最終的推薦列表。本文推薦算法的基本框架如圖4所示，主要輸入是用戶-項目評分矩陣、用戶-用戶信任矩陣和項目的流行權(quán)重。該算法的主要步驟是合并矩陣、引入項目流行度的加權(quán)策略、模型訓練、預測評分、過濾信任矩陣、生成推薦列表。

圖4 PopTruMF模型基本框架

3 實驗結(jié)果與分析

3.1 實驗設置

數(shù)據(jù)集 本文采用公開的Epinions數(shù)據(jù)集，其中包括40 163個用戶對139 738個項目的664 824條評分，評分數(shù)值在1～5之間，用戶之間的信任信息包括487 181條，數(shù)據(jù)的稀疏度為0.011 845 84%。由于原始數(shù)據(jù)集的高稀疏性，使得推薦算法在模型訓練的過程中存在一定的難度。例如，一半以上的用戶只有一個評論。對此，本文按照文獻[13]的方法先進行數(shù)據(jù)過濾，使得本實驗中數(shù)據(jù)的稀疏度為99.89%。

(1) 度量方法 我們采用均方根誤差(RMSE)、準確率(precison)、覆蓋率(coverage)、F值四個性能指標評估推薦算法的推薦質(zhì)量。

(10)

(11)

式中：I表示所有物品的集合，coverage表示推薦列表中的物品占總物品數(shù)的比例。其中，RMSE的值越小，代表推薦效果越好。由于實際評分和預測評分之間最大差值是5-1=4，本文算法的最差精度為：

(12)

為了更好地評估算法的推薦質(zhì)量，本文引入F值指標，將準確率和覆蓋率結(jié)合在一個數(shù)字度量中。其中，F(xiàn)值越大，代表推薦算法的總體效果越好。

(13)

(2) 對比方法 將本文算法與下面的算法進行比較,評估各算法的性能。

SocialMF算法[4]基于矩陣分解的方法，結(jié)合用戶之間的信任關系，學習用戶和項目的潛在特征向量，提出每個用戶的特征向量依賴于社交網(wǎng)絡中他直接鄰居特征向量的加權(quán)平均。

SocialSVD算法[2]基于奇異值分解的方法，根據(jù)人際關系中的六度分隔理論計算用戶之間信任度，填充用戶信任矩陣，提高了預測的準確率。

TrustWalker算法[5]結(jié)合用戶之間的信任關系，在信任網(wǎng)絡上隨機游走以預測項目評分。如果在特定的深度閾值內(nèi)未找到該項目，則基于相似的項目預測項目評分。

3.2 實驗結(jié)果及分析

本文采用上述的Epinions數(shù)據(jù)集，依次對SocialMF算法、SocialSVD算法、TrustWalker算法和本文提出的合并矩陣TruMF算法以及完整的PopTruMF算法做對比實驗。在實驗中，我們設置潛在特征向量K=25、β=0.01，且所有方法都是用python實現(xiàn)的，以便公平比較所有方法。實驗結(jié)果如表1所示。

表1 TruMF算法與各算法實驗結(jié)果

如表1所示，本文提出的TruMF算法的F值最大，推薦效果最好。在現(xiàn)有的推薦算法中，TrustWalker算法是推薦結(jié)果覆蓋范圍最廣的方法之一，高達95.4%，而本文的TruMF算法相比TrustWalker算法項目覆蓋率略有提高，約98.7%。TruMF算法的覆蓋率同樣也高于其他兩種算法，因為SocialMF算法和SocialSVD算法都是基于信任網(wǎng)絡中的信任傳遞進行推薦，因此存在信任網(wǎng)絡脫節(jié)的問題。但在準確率方面，TruMF算法分別低于SocialMF算法、SocialSVD算法和TrustWalker算法。

本文結(jié)合項目流行度加權(quán)策略，在TruMF算法的基礎上作出進一步優(yōu)化，提出PopTruMF算法。其中c0代表缺失數(shù)據(jù)的總權(quán)重，?控制項目流行度對以上權(quán)重的影響。首先，本文將缺失數(shù)據(jù)賦予的統(tǒng)一權(quán)重，即?=0。如圖5所示，當c0取128左右時，RMSE最小，達到預測準確性的峰值，而當c0變小或設置的太大時，RMSE的值顯著升高，這說明在TruMF算法中適當考慮缺失數(shù)據(jù)的必要性。

圖5 c0(?=0)

然后，我們將c0設置為128，來觀察項目流行度對推薦效果的影響。如圖6所示，隨著α的增加，RMSE的值會再次減小，到達一個最優(yōu)值后又會大幅度升高，這說明在TruMF算法中適當考慮項目流行度的有效性。本文設置c0=128、?=0.4，同時引入項目流行度的誤差權(quán)重因子wui，適度增加?，會達到更好的預測效果。如圖6所示，根據(jù)項目流行度對用戶評分項目和未評分項目分別進行加權(quán)處理，可以更有效提高推薦算法的準確率。

圖6 ?(c0=128)

PopTruMF算法與各算法的實驗結(jié)果如表2所示。可以看出，PopTruMF算法的F值在TruMF算法的基礎上得到進一步的改善，準確率和覆蓋率得到了更好的折中。與前幾種方法相比，PopTruMF算法雖然損失了5%的RMSE，但在推薦中覆蓋項目的范圍最廣，能夠給于用戶更好的推薦效果。

表2 PopTruMF算法與各算法實驗結(jié)果

4 結(jié) 語

針對現(xiàn)有推薦算法在推薦中項目覆蓋范圍有限的問題(如用戶信任網(wǎng)絡不相容、項目評分矩陣的高稀疏性、用戶個性化推薦存在偏差等)，本文提出了一種基于合并用戶信任關系和項目流行度的PopTruMF算法，并討論了如何通過信任關系將項目推薦給不同信任網(wǎng)絡的用戶，以及在推薦算法中考慮缺失數(shù)據(jù)和項目流行度的有效性。通過在Epinions上的實驗表明，PopTruMF算法在大幅度改善推薦覆蓋率的同時，保證了推薦的準確率，能夠給于用戶更好的推薦效果。

在下一步的研究中，我們將進一步探索項目和用戶基于多個潛在特征對個性化推薦的影響，以及通過給與用戶實時的推薦，進一步提升模型性能。