陳梅梅，董晨光，王 淇，戴偉輝

1(東華大學(xué) 旭日工商管理學(xué)院，上海200051)

2(復(fù)旦大學(xué) 管理學(xué)院，上海200433)

E-mail：cmm@dhu.edu.cn

1 引 言

電子商務(wù)的深入發(fā)展要求企業(yè)盡可能滿足不同用戶的興趣愛好，個性化推薦技術(shù)應(yīng)運而生.基于內(nèi)存的協(xié)同過濾算法由于其推薦準確、效率高等特點在電商、影視、圖書、音樂等平臺得到廣泛應(yīng)用，但是，數(shù)據(jù)稀疏性一直是該類算法面臨的一大瓶頸問題[1].用戶-項目評分矩陣是協(xié)同過濾推薦算法的重要輸入，源于用戶的瀏覽、交易行為或評價結(jié)果.但在眾多的項目中，每個用戶都存在著大量未評分項目，因而，數(shù)據(jù)稀疏問題不可避免，且給協(xié)同過濾推薦算法中用戶/項目相似性的精確計算帶來了很大困難，并最終影響推薦準確度的提升.因此，對比協(xié)同過濾算法中數(shù)據(jù)稀疏性導(dǎo)致推薦精度問題的現(xiàn)有解決方案，選擇簡單有效的方案并針對其存在的不足加以改進，具有重要的理論和現(xiàn)實意義.

2 研究綜述

為了降低數(shù)據(jù)稀疏性對協(xié)同過濾推薦的影響，現(xiàn)有研究中的主流方案一般有4類.

2.1 用戶/項目聚類

先對用戶或者項目進行聚類，再在幾個具有相似性關(guān)系的組內(nèi)分別對用戶進行推薦[2]，通過縮小近鄰用戶的范圍，在確保個性化同時最大限度地降低數(shù)據(jù)稀疏性影響，但用戶或項目的聚類會導(dǎo)致一些有用個性化信息丟失.

2.2 改進用戶/項目相似度計算方法

利用用戶/項目的特征信息，基于用戶/項目屬性以及用戶/項目之間的相似關(guān)系計算用戶[3-5]或項目[6]特征相似度，通過避開對用戶-項目評分矩陣的依賴，在一定程度上緩解數(shù)據(jù)稀疏性對推薦的影響，但融入基于社交網(wǎng)絡(luò)等的用戶/項目特征信息一定程度上會增加算法復(fù)雜度以及數(shù)據(jù)采集、清理和存儲的要求.

2.3 基于矩陣分解技術(shù)的評分矩陣降維

主要采用奇異值分解法SVD(Singular Value Decomposition)[7，8]，通過將高維度的評分矩陣映射到低維度，能有效降低矩陣規(guī)模和數(shù)據(jù)稀疏性，但在矩陣運算的過程中將一個矩陣分解為多個矩陣的乘積，難免會丟失用戶相似性信息.為此，林建輝等提出了一種基于SVD和模糊聚類的協(xié)同過濾算法，降維同時縮小近鄰范圍，緩解數(shù)據(jù)稀疏性同時提升可拓展性[9];劉晴晴等提出基于SVD的混合協(xié)同過濾推薦算法，先用SVD方法分解用戶-項目評分矩陣，通過隨機梯度下降法填充稀疏矩陣，并優(yōu)化相似度計算方法以有效提高推薦準確性[10];Nilashi等則提出了基于SVD和本體論的混合協(xié)同過濾推薦方法，降維的同時利用本體論提高推薦的準確性[11].王運等在傳統(tǒng)的概率矩陣分解算法基礎(chǔ)上，利用用戶項目評分數(shù)據(jù)及項目信息提出了融合用戶偏好和項目相似度的概率矩陣分解推薦算法，雖沒有根本降低矩陣分解技術(shù)計算復(fù)雜度，但仿真實驗表明該算法獲得了更好的評分預(yù)測準確性[12]，一定程度上緩解了該類方法推薦失真的問題.但由于奇異值分解的復(fù)雜度，計算耗時較長[13].

2.4 基于評分預(yù)測的矩陣填充

對用戶未評分項目進行評分預(yù)測，回填到評分矩陣中進行協(xié)同過濾推薦，個性化程度和精確度都有所提高[14].缺省值預(yù)測常用的方法如下：使用N個近鄰用戶對項目i的平均評分作為用戶u對未知項目i的預(yù)測評分P(u，i)[15-17]，這種方法將近鄰用戶同等對待，忽視了不同近鄰用戶特征對預(yù)測評分的貢獻程度的影響，大大降低了預(yù)測結(jié)果的個性化程度.彭石等提出一種基于加權(quán)Jaccard系數(shù)的綜合項目相似度度量方法[18]，使用項目綜合相似度對評分矩陣進行填充，但是項目屬性的選取沒有統(tǒng)一規(guī)則，所以可靠性和普適性不強;盧棪提出了一種以迭代的方式進行缺失值預(yù)測評分矩陣填充方法[19]，這種方法在每一次迭代中僅考慮項目間的相似度來生成預(yù)測評分.

向小東等使用Slope-One算法計算得到的評分預(yù)測值來填充評分矩陣中的未評分項目，該方法有效地降低數(shù)據(jù)稀疏性，相比其它方法算法簡單，易于實現(xiàn)，執(zhí)行效率高[20]，但依然只從項目相似度角度進行未知項目的評分預(yù)測;劉林靜等提出了一種基于用戶相似性的加權(quán)Slope-One 算法，將用戶間的相似性作為預(yù)測評分權(quán)重[21]，但去除評價次數(shù)小于0.01%的極度不活躍用戶僅考慮活躍用戶的影響作用，失去了一定的有效信息;張玉連等提出的加權(quán)Slope-One算法在預(yù)測評分時進一步考慮了不同項目的用戶評論數(shù)量差異的影響[22];李桃迎等則針對Slope-One算法未考慮用戶興趣變化和用戶相似性的問題，提出了基于用戶興趣遺忘函數(shù)和用戶最近鄰居篩選策略的改進方案，以期提高推薦的質(zhì)量[23];王衛(wèi)紅提出基于用戶自身屬性的加權(quán)Slope One算法，將用戶對項目類別的評分添加到評分矩陣以降低數(shù)據(jù)稀疏性的同時，在計算用戶間相似度時考慮了用戶年齡、性別和職業(yè)等屬性，提升了推薦準確性和算法可拓展性[24].但無論是基于用戶相似性還是考慮用戶自身屬性的加權(quán)Slope-One算法，用戶-項目評分中仍然忽略了用戶話語權(quán)這一重要用戶本身屬性的影響.

2.5 綜述小結(jié)

用戶/項目聚類和用戶/項目相似度計算改進兩類方法并沒有根本解決數(shù)據(jù)稀疏性問題本身，且存在部分丟失或忽視最能反映用戶偏好的用戶/項目信息、過于依賴用戶/項目特征數(shù)據(jù)等缺陷;基于評分預(yù)測對用戶-項目矩陣的缺失數(shù)據(jù)進行填充的矩陣填充法，克服了SVD等矩陣降維方法計算復(fù)雜的缺點，近年來引起了學(xué)術(shù)界和企業(yè)界的關(guān)注.因此，本文擬對矩陣缺省項預(yù)測的Slope-One算法和現(xiàn)有的加權(quán)Slope-One算法原理及局限進行分析，在考慮評分用戶數(shù)量不同對于計算項目評分偏差影響的同時，充分考慮用戶屬性的不同對于評分預(yù)測的影響，提出一種兼顧用戶話語權(quán)這一重要用戶屬性的改進的加權(quán)Slope-One算法，以期在解決數(shù)據(jù)稀疏性問題同時進一步提升評分預(yù)測的精度.

3 Slope-One算法的局限

3.1 Slope-One算法的原理

Slope-One算法是一個增量算法，基于該算法的協(xié)同過濾推薦對評分很少的用戶也可以產(chǎn)生推薦，并且精確度比基于用戶和基于項目的協(xié)同過濾推薦算法的表現(xiàn)要好[20，21]，Slope-One算法核心的思想是根據(jù)所有用戶對項目的評分推算出項目集合中兩兩項目之間的評分差值，從而根據(jù)項目之間的評分差值和用戶已有的評分記錄來近似地預(yù)測該用戶對目標項目的評分.

下面用一個簡單的例子來闡述Slope-One算法的原理.假設(shè)有U1、U2、U3、U4、U5這5個用戶分別對I1、I2、I3、I4這4個項目的評分記錄，如圖1(a)所示，其中：“-”表示未評分，“？”代表需要預(yù)測的評分.

原始的Slope-One算法預(yù)測用戶U1對項目I3評分的流程如下：

Step 1.篩選用戶集合.

先篩選出對目標項目I3進行過評分的所有用戶的集合，即{U2，U4，U5}，如圖1(b)所示.

Step 2.篩選項目集合.

在用戶集合{U2，U4，U5}中，尋找與目標用戶U1同時進行過評分的所有項目，包括目標項目在內(nèi)構(gòu)成項目集合{I2，I3，I4}，如圖1(c)所示，從而鎖定Slope-One算法所需要的用戶-項目評分數(shù)據(jù).

圖1 Slope-One算法原理示意圖Fig.1 Schematic diagram of Slope-One algorithm

Step 3.預(yù)測目標項目評分.

項目j與項目i的評分偏差devj，i如公式(1)所示：

(1)

用戶u對項目j預(yù)測評分P(u)j如公式(2)所示：

(2)

其中：Uj，i表示同時對項目j和i評過分的用戶集合;Ij表示用戶u所有已評分且滿足條件(i≠j∩Uj，i≠φ)的項目集合;ru，i和ru，j分別表示用戶u對項目i和j的評分;card()表示集合中的元素個數(shù).

3.2 加權(quán)Slope-One算法及局限

原始的Slope-One算法中，項目之間共現(xiàn)的次數(shù)無論是多少，最終考慮的都是平均評分差，那么考慮項目之間共現(xiàn)次數(shù)的影響.對于項目i和j來說，在計算評分偏差devj，i的時候并沒有考慮評分用戶數(shù)量差異對devj，i可信度的影響，假如有1000個用戶都給項目i和j打了分，而只有一個用戶給項目i和k打分，那么devj，i的可信度是要遠遠高于devj，k的.在此基礎(chǔ)之上，加權(quán)Slope-One考慮了共現(xiàn)次數(shù)，項目和目標項目共現(xiàn)次數(shù)越多，所預(yù)測的得分置信度越高.

加權(quán)Slope-One算法考慮到兩兩項目之間共現(xiàn)次數(shù)即不同的評分用戶數(shù)量對于計算項目評分偏差時的貢獻不同，對不同項目計算得到的平均偏差進行加權(quán)，改進后的計算如公式(3)所示：

(3)

其中，card(Uj，i)是對項目i和j都做出過評價的用戶數(shù)量.

加權(quán)Slope-One算法在原始的Slope-One算法基礎(chǔ)上既考慮了項目平均評分差異，又針對項目的評分用戶數(shù)量進行了加權(quán)處理，通過用戶評分數(shù)量的加權(quán)得到項目之間的評分偏差的加權(quán)平均，從而克服了原始Slope-One算法在項目的評分預(yù)測中不同項目的評分用戶數(shù)量差異對評分偏差的影響[21].

但是傳統(tǒng)的加權(quán)Slope-One算法仍然是基于項目考慮評分用戶數(shù)量的差異，卻忽略了用戶本身屬性尤其是不同用戶活躍度差異的影響.比如，用戶a評論總數(shù)是2000次，而用戶b只有20次，兩個用戶的活躍度不同，活躍度越高的用戶，對于推薦系統(tǒng)中同一項目評分預(yù)測的貢獻越大，意味著該用戶的話語權(quán)越高.因而，傳統(tǒng)的加權(quán)Slope-One算法忽略了用戶話語權(quán)的作用，限制了評分預(yù)測的可信度，進而一定程度上影響基于該算法的協(xié)同過濾推薦的準確性.

4 基于改進加權(quán)Slope-One的協(xié)同過濾推薦算法

4.1 兼顧用戶話語權(quán)的加權(quán)Slope-One算法

本文在傳統(tǒng)的加權(quán)Slope-one算法考慮不同項目之間評分用戶數(shù)量差異影響的基礎(chǔ)上，進一步考慮了不同活躍度用戶的話語權(quán)差異對評分預(yù)測的影響，提出改進的加權(quán)Slope-One算法.

作為協(xié)同過濾推薦算法重要輸入的用戶-項目評分矩陣，評分次數(shù)不同的用戶，其活躍度存在差異，對評分預(yù)測的話語權(quán)顯然不能等同對待，充分考慮用戶話語權(quán)的大小對評分偏差的影響，可以有效避免出現(xiàn)愛好大相徑庭的用戶被計算為相似用戶的問題.當然，為了避免人為刷評論或者惡意評論等行為的影響，需要對用戶-項目評分數(shù)據(jù)進行有用性甄別.以一個例子說明如下：假如現(xiàn)在用戶U2，評分次數(shù)為100，他對于項目I2和I3的評分分別是2和5，I2和I3的共同評分用戶數(shù)是30;另一用戶U4，評分次數(shù)為20，其對項目I2和I3的評分分別是5和2，I2和I3的共同評分用戶數(shù)是50;而用戶U5的評分次數(shù)是50;其他的用戶-項目評分同圖1，那么，根據(jù)加權(quán)Slope-One算法首先據(jù)公式(1)計算項目I2和I3、項目I3和I4的評分偏差分別是：

如果考慮用戶評分數(shù)量差異作為權(quán)重，項目I2和I3、項目I3和I4的評分偏差則分別是：

顯然，考慮用戶話語權(quán)有利于消除了加權(quán)平均評分差所帶來的偶然因素導(dǎo)致的加權(quán)評分差為0的現(xiàn)象，這個方法也大大降低了由于偶然因素導(dǎo)致的愛好不一樣的用戶被計算為相似用戶的概率.因此這種基于用戶話語權(quán)的加權(quán)Slope-One算法總結(jié)如公式(4)和公式(5)：

(4)

(5)

其中，Nu代表數(shù)據(jù)集中每個用戶的評分次數(shù)，它反映了用戶活躍度.

4.2 基于改進加權(quán)Slope-One算法的協(xié)同過濾推薦流程

針對協(xié)同過濾算法中數(shù)據(jù)稀疏的問題，本文在傳統(tǒng)加權(quán)Slope-One算法基礎(chǔ)上提出了考慮用戶話語權(quán)的改進算法，用戶活躍度越高則對項目評分的話語權(quán)越大.據(jù)此對用戶未評分項目進行預(yù)測以實現(xiàn)用戶-項目評分矩陣的填充，作為協(xié)同過濾算法的輸入.

U為用戶集合，I是具有預(yù)測評分的候選項目集合，M0是用戶-項目初始評分矩陣，Mi為用戶-項目填充后的評分矩陣，N為給每個用戶推薦的項目個數(shù)，L0是初始候選列表，L1是候選列表，Len(ui)為用戶評分列表填充長度，L(u)為給所有用戶的最終推薦列表，則基于改進加權(quán)Slope-One算法的協(xié)同過濾推薦流程描述如圖2所示.

圖2 基于改進的加權(quán)Slope-One算法協(xié)同過濾推薦流程Fig.2 Flow chart of collaborative filtering recommendation algorithm based on improved weighted Slope-One algorithm

5 仿真實驗

5.1 實驗數(shù)據(jù)

本文仿真實驗選取了稀疏度不同的兩個數(shù)據(jù)集Movie-Lens和Amazon-Clothes作為實驗數(shù)據(jù).Movie-Lens數(shù)據(jù)集是由明尼蘇達大學(xué)的Grouplens團隊收集的真實電影評分數(shù)據(jù)，經(jīng)清洗得到了包含943個用戶對1682部電影共100000條有效評分數(shù)據(jù)，其中每個用戶至少對20部電影進行了評分，平均評論數(shù)為106次.Amazon-Clothes數(shù)據(jù)集由加州大學(xué)Julian McAuley教授團隊收集的亞馬遜服裝銷售的真實評分數(shù)據(jù)，經(jīng)清洗得到了包含6962個用戶對5000個項目的226956條有效評分數(shù)據(jù)，平均評論數(shù)33次.兩個數(shù)據(jù)集的評分值均為1～5之間的整數(shù)，數(shù)值越高用戶滿意度越高.

借鑒文獻[21]關(guān)于數(shù)據(jù)稀疏度的計算方法，Movie-Lens數(shù)據(jù)集的稀疏度為0.937，相對較低;Amazon-Clothes數(shù)據(jù)集的稀疏度為0.9934，相對較高.

本實驗主要目的是驗證本文提出的基于改進評分矩陣填充算法的協(xié)同過濾推薦的準確性.采用五折交叉法，將數(shù)據(jù)集隨機分為5個不相交的子集，每次實驗選擇其中一個子集作為測試集，其余的4個子集作為訓(xùn)練集，如此重復(fù)5次的平均結(jié)果作為最終結(jié)果.每個數(shù)據(jù)集的4個訓(xùn)練集用于本文算法計算用戶對項目的預(yù)測評分，而測試集則不參與預(yù)測評分，僅用于評估本文算法的推薦效果，之后將預(yù)測評分與實際評分進行MAE值的比較.

5.2 仿真對比的算法和指標

基于奇異值分解(SVD)的協(xié)同過濾算法通過降維來減小數(shù)據(jù)稀疏性的影響[7，8]，因此作為仿真對比的算法之一;其次，選擇原始的協(xié)同過濾算法和基于傳統(tǒng)加權(quán)Slope-One的協(xié)同過濾算法，作為本文基于改進加權(quán)Slope-One的協(xié)同過濾算法的對照組.

本文采用調(diào)整余弦相似度(Adjusted Cosine Similarity)[6]計算相似度;采用平均絕對偏差MAE(Mean Absolute Error)作為推薦準確度的評價指標，對比上述4種算法在兩個不同稀疏度的數(shù)據(jù)集Movie-Lens和Amazon-Clothes上的MAE表現(xiàn).MAE越小，算法準確性越高[1].

5.3 確定最優(yōu)填充比例

按照Slope-One填充的評分矩陣，先通過仿真實驗1來得到最優(yōu)的填充比例，即對每個用戶填充的預(yù)測評分數(shù)目，來驗證矩陣填充比例變化對本文算法的絕對誤差的影響，實驗1中，矩陣填充比例分別取10%、20%、30%、40%、50%、60%，70%.本文改進Slope-One算法在Movie-Lens數(shù)據(jù)集和Amazon-Clothes數(shù)據(jù)集上的MAE值表現(xiàn)如圖3所示.

圖3 不同填充比例下本文算法的MAE值表現(xiàn)Fig.3 Comparison of MAE values of proposed algorithm under different filling ratios

由圖3可知，本文算法在Movie-Lens數(shù)據(jù)集上的表現(xiàn)要好于在Amazon-Clothes數(shù)據(jù)集，同時本文算法在兩種數(shù)據(jù)集上的MAE值均在填充比例在30%左右趨于穩(wěn)定，因此后續(xù)實驗中本文算法填充比例將采用30%.

5.4 確定最優(yōu)近鄰數(shù)

采用最優(yōu)填充比例30%使用本文改進加權(quán)Slope-One算法對兩個數(shù)據(jù)集的評分矩陣進行填充，然后分別使用另外3種算法對2個數(shù)據(jù)集進行仿真實驗2確定近鄰數(shù)N的大小.在實驗2中分別取N=10，20，30，40，50，60，70，80，90，觀察近鄰數(shù)的多少對推薦準確性的影響.如圖4所示，整體而言，對于4種算法，隨著近鄰數(shù)的增大，MAE 值逐漸降低，并在N= 50 時逐漸趨于穩(wěn)定，因此，最優(yōu)近鄰數(shù)目選擇50.

圖4 不同近鄰數(shù)下4種算法MAE值對比Fig.4 Comparison of MAE values of four algorithms under different neighbor numbers

5.5 仿真結(jié)果分析

對4種算法進行MAE值仿真對比實驗3，結(jié)果如圖5所示.

由圖5可知，從算法精度來看，4種算法中，本文算法在不同稀疏度的兩個數(shù)據(jù)集上的平均絕對誤差值都表現(xiàn)最佳;表現(xiàn)其次的是基于SVD的協(xié)同過濾算法和原始加權(quán)Slope-One算法;原始的協(xié)同過濾算法表現(xiàn)最差.表明本文算法相對其它3種算法能夠更有效地降低數(shù)據(jù)稀疏對推薦準確度的影響.

圖5 4種算法在2個數(shù)據(jù)集上的MAE值對比Fig.5 Comparison of MAE values of four algorithms on two datasets

從數(shù)據(jù)集角度來看，各算法在數(shù)據(jù)稀疏度略高的Amazon-Clothes數(shù)據(jù)集上的總體表現(xiàn)都略微比Movie-lens數(shù)據(jù)集差，說明稀疏度的升高的確會影響算法的準確度;SVD協(xié)同過濾算法和原始的加權(quán)Slope-One算法在Amazon-Clothes數(shù)據(jù)集仿真中的表現(xiàn)差別不大，但是在Movie-lens數(shù)據(jù)集仿真中，原始的加權(quán)Slope-One算法明顯要比SVD協(xié)同過濾算法表現(xiàn)好，說明基于原始加權(quán)Slope-One的協(xié)同過濾推薦算法在稀疏度較低的數(shù)據(jù)集上相對SVD略有優(yōu)勢一些;本文提出的基于改進加權(quán)Slope-One的協(xié)同過濾推薦算法在不同稀疏度的數(shù)據(jù)集上的仿真中表現(xiàn)穩(wěn)定且都相對最優(yōu)，進一步驗證了本文改進算法的優(yōu)越性.

6 結(jié)束語

針對目前基于內(nèi)存的協(xié)同過濾算法中數(shù)據(jù)稀疏性導(dǎo)致的推薦結(jié)果準確度不高的問題，本文在加權(quán)Slope-One算法基礎(chǔ)上提出了兼顧項目之間差異和用戶之間差異的改進算法，在對用戶-項目評分矩陣進行填充預(yù)測時考慮用戶話語權(quán)的影響;并通過仿真實驗確定了該算法的最優(yōu)填充比例和最優(yōu)近鄰數(shù)等重要參數(shù)，有效緩解數(shù)據(jù)稀疏性的同時，確保用戶-項目的評分預(yù)測最大限度地體現(xiàn)用戶相似性.基于Movie-Lens和Amazon-Clothes兩個不同稀疏度數(shù)據(jù)集的仿真實驗顯示，相對于經(jīng)典協(xié)同過濾算法、基于SVD的協(xié)同過濾算法以及原始加權(quán)Slope-One算法3種算法，本文提出的基于改進加權(quán)Slope-One的協(xié)同過濾算法的推薦結(jié)果的MAE值最低.

為了揭示4種算法在不同稀疏度數(shù)據(jù)集上的表現(xiàn)和適用性，本文采用的兩個數(shù)據(jù)集的稀疏度差別還不夠突出，今后將會嘗試在稀疏度反差更大的若干個數(shù)據(jù)集上分別驗證4種算法的性能表現(xiàn).