王潘潘， 錢 謙， 王 鋒

(云南省計算機技術應用重點實驗室 昆明理工大學，云南 昆明 650200)

?

改進加權Slope one協(xié)同過濾推薦算法研究*

王潘潘， 錢 謙， 王 鋒

(云南省計算機技術應用重點實驗室 昆明理工大學，云南 昆明 650200)

協(xié)同過濾推薦是最成功的推薦技術之一，但數(shù)據(jù)稀疏性問題導致推薦準確度和推薦效率不高。針對這個問題，提出了一種改進的加權Slope one協(xié)同過濾推薦算法。計算用戶之間的評分相似度，找出每個用戶的最近鄰；根據(jù)最近鄰用戶評分，使用基于用戶的協(xié)同過濾和改進的加權Slope one算法的加權評分預測目標用戶的未評分項目；給出推薦。實驗過程中采用MovieLens數(shù)據(jù)集作為測試數(shù)據(jù)。實驗結果表明：與原算法相比，算法提高了預測準確度，有效提高了推薦性能。

數(shù)據(jù)稀疏； 用戶相似性； 協(xié)同過濾； 最近鄰用戶； 加權Slope one算法

0 引 言

隨著電子商務的發(fā)展，越來越多的用戶喜歡網(wǎng)絡服務，但隨著商品信息的增加，引起了商品信息過載問題。為了使用戶在大量商品中準確找到喜歡的商品，推薦系統(tǒng)應運而生。個性化推薦是目前最受歡迎的營銷方式之一，推薦用戶支付得起、個性化、匹配度高的商品是推薦領域的核心問題，對技術研究提出了很多挑戰(zhàn)?，F(xiàn)有的推薦技術正在向不同領域提供解決方案，電影，書籍，音樂電臺等都使用了適合自己的推薦系統(tǒng)，比如國外的MovieFinder、Amazon、CDNow；國內(nèi)的豆瓣、京東商城等[1]。同時，推薦系統(tǒng)面臨著冷啟動、數(shù)據(jù)稀疏性、可擴展性等問題[2]。隨著研究的進步，這些問題得到了很大程度地解決，在推薦電影等方面已經(jīng)產(chǎn)生了令人滿意的推薦效果。

目前的推薦算法主要分為4類：基于內(nèi)容的推薦、基于知識的推薦、協(xié)同過濾推薦和混合推薦算法。協(xié)同過濾推薦是目前最廣泛的推薦技術之一，其中Slope one算法是一種簡單的協(xié)同過濾算法，利用用戶之間的評分偏差預測未評分項目。目前，已經(jīng)有了很多類似算法：文獻[1]使用Slope one算法對用戶—項目評分矩陣中的空白評分進行預測填充，對填充后的評分矩陣使用基于用戶的協(xié)同過濾算法進行推薦；文獻[2]提出基于項目的協(xié)同過濾推薦算法并結合Slope one算法模型；文獻[3]提出一種資源分配的用戶相似性度量方法，增加相似用戶的權重，在標準的MovieLens數(shù)據(jù)集上進行實驗，結果表明改進的算法在一定程度上提高了預測精度。

上述研究根據(jù)最近鄰項目集并結合Slope one算法進行推薦傳統(tǒng)的Slope one算法沒有考慮用戶或項目之間的相似性，在數(shù)據(jù)稀疏時沒有傳統(tǒng)的協(xié)同過濾算法效果好。本文基于用戶的協(xié)同過濾提出了一種改進算法，根據(jù)用戶評分相似度計算目標用戶的最近鄰，在最近鄰用戶范圍內(nèi)使用用戶協(xié)同過濾和加權Slope one算法改進預測評分值，提高了推薦質量。

1 基于用戶的協(xié)同過濾推薦算法

協(xié)同過濾分為基于內(nèi)存的協(xié)同過濾算法和基于模型的協(xié)同過濾算法。前者直接根據(jù)用戶的歷史評分數(shù)據(jù)尋找相似用戶，分為基于用戶和基于項目的協(xié)同過濾。基于用戶的協(xié)同過濾的算法核心是網(wǎng)站給用戶u作推薦，只要找出和用戶u行為相似的用戶，將行為推薦給用戶u，算法核心步驟是：首先,找到和目標用戶興趣相似的用戶集合；然后,找到這個集合中的用戶喜歡且目標用戶沒有評過分的物品推薦給目標用戶，確定鄰居用戶集合根據(jù)用戶評分相似度，此算法和聚類算法[4]核心思想一致?；谟脩粝嗨菩杂嬎惴椒╗5]有余弦相似性、修正余弦相似性和相關相似性。

1)余弦相似性

用戶的評分可看做n維項目空間上的向量，如果用戶對項目沒有評分，則用戶對項目的評分為0。設用戶i和用戶j在n維項目空間上的評分表示為向量i→和向量j→，用戶i，j之間的相似性計算公式為

(1)

分子為兩個用戶評分向量的內(nèi)積，分母為兩個用戶評分向量模的乘積。

2)修正的余弦相似性

設用戶i和用戶j共同評分過的項目集合用Ii,j表示，用戶i和用戶j之間的相似性計算公式為

(2)

3)相關相似性(Pearson相關系數(shù))

設用戶i和用戶j共同評分過的項目集合用Ii,j表示，Ii,j=Ii∩Ij，用戶i和用戶j之間的相似性計算公式

(3)

本文使用相似度計算方法來確定目標用戶的最近鄰居，計算用戶與用戶之間的相似度，通過實驗確定用戶與用戶之間的相似度計算方法，空白評分的預測公式為

(4)

2 加權Slope one算法

Slope one算法是由Daniel Lemire 和Anna Maclachlan在2005年提出的一種協(xié)同過濾算法[6]。Slope one是一種容易理解的推薦算法，因其簡單、易于實現(xiàn)和維護而備受關注。每對物品根據(jù)一個物品的評分預測另一個物品的評分，可以解決新用戶問題和部分冷啟動問題，及時獲取新用戶評分并對用戶推薦結果產(chǎn)生影響，且算法運行速度快，可即時響應用戶需求，在數(shù)據(jù)稠密的情況下，Slope one算法優(yōu)于傳統(tǒng)算法?；維lope one算法思想來自簡單的一元線性模型[3]為y=mx+b，x為評分差值，b為一個常量，m=1為基本的Slope one算法。如表1為一組用戶評分值，計算user3對item 3的評分。

表1 三個項目的評分

首先找到user1，user2和user3共同評分的項目item1，計算user1和user2對item1和item3的評分偏差為((5-3)+(4-2))/2=2，user3對item3的預測評分為4-2=2。Slope one算法的基本步驟：1)定義itemi相對于itemj的平均偏差

(5)

式中 uj為用戶u對itemj的評分;ui為用戶u對itemi的評分;Sj,i(χ)為同時對itemi和itemj給予了評分的用戶集合;card()為集合包含的元素數(shù)量。2)計算出每對項目之間的平均評分差值：首先,獲取所有評過分的用戶id，然后計算每個用戶評分過的產(chǎn)品間的平均評分差值。計算評分偏差后，為某個用戶推薦時，取出該用戶評分過的項目，使用devj,i+ui獲得用戶u對itemj的預測值。將所有這種可能的預測平均起來，可以得到

(6)

式中 P(u)j為項目j的預測評分;card(Rj)為所有用戶已經(jīng)給予評分且滿足條件 (i≠j且S(u)非空) 的項目集合。

但是Slopeone算法在計算itemi相對于itemj的平均偏差devj,i時沒有考慮不同的用戶數(shù)量，可信度不一樣。假設有1 000個用戶同時評分了itemj和k，而只有10個用戶同時評分了itemj和l，顯然devj,k比devj,l更具有說服力，而且推薦系統(tǒng)的應用中，用戶評分數(shù)一般大于2，使用加權Slopeone更符合實際應用，本文使用加權Slopeone算法，預測評分公式為

(7)

式中 cj,i為加權值cj,i=card(Sj,i(χ));預測評分值用PwSl(u)j表示。

3 改進加權Slope one協(xié)同過濾推薦算法

加權Slopeone算法的缺點是沒有考慮用戶之間和項目之間的相似度問題，改進算法根據(jù)用戶的協(xié)同過濾，選出目標用戶的前k個最近鄰，最近鄰集合用S(k)表示，根據(jù)最近鄰用戶集合S(k)使用加權Slopeone算法預測未評分值。計算目標用戶和其他鄰居用戶的相似度，對共同評分的項目可以得到一個評分相似度權值Weight為

(8)

式中 Ri,t≠0，Ri,t為用戶i對目標項目t的評分;card(Ri,t)為評分總數(shù)。通過改進的加權Slopeone算法，給出推薦結果，改進的預測評分公式為

(9)

每個用戶評分的項目數(shù)量有限，某些項目可能沒有被評過分，所以影響算法推薦效果。為了克服這個問題，引入用戶相似度，在鄰居范圍內(nèi)，項目預測評分通過基于用戶的協(xié)同過濾和改進加權Slopeone算法進行加權平均求得，改進的評分公式如下

輸入：用戶—項目評分數(shù)據(jù)集，目標用戶為u，目標項目為itemj。

輸出：目標用戶對項目的預測評分值P(u)j。

1)構建用戶項目—評分矩陣，首先確定用戶共同評分的項目，建立用戶—項目評分矩陣R(m×n)，根據(jù)式(3)計算用戶之間的相似性，目標用戶和其他用戶沒有共同評分項目，則用戶之間相似度值置為-1。

2)產(chǎn)生鄰居，計算用戶之間的相似度，確定鄰居個數(shù)k值，取前k個最大的相似度值用戶，形成最近鄰用戶集合S(k)，并使用式(8)計算評分相似度權值Weight。

3)在最近鄰用戶集合S(k)條件下，獲取鄰居用戶id值，計算每個用戶評分過的項目之間的評分差值，使用式(10)計算目標用戶的未評分值。如果目標用戶的鄰居用戶沒有對當前項目評分，則項目預測評分值由當前用戶對所有項目的評分均值代替。

4)輸出預測值，產(chǎn)生TopN推薦，計算平均絕對偏差(Mean Absolute Error，MAE)值。根據(jù)用戶對項目評分的預測值高低向用戶做出推薦。

4 實驗結果與分析

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

實驗數(shù)據(jù)集分為訓練集和測試集，采用5折交叉驗證法。首先將數(shù)據(jù)集分成5個不相交的子集，將其中4份作為訓練集，其余1份作為測試集，用訓練集得到預測模型，然后用測試集對預測結果進行評價。

4.2 度量標準

衡量推薦質量的度量標準包括決策支持精度度量和統(tǒng)計精度度量[7～10]。本文使用MAE作為度量標準，計算公式如下

(10)

式中Pi為預測評分值;Ri為用戶的實際評分值。MAE值越小，預測精確度越高。

4.3 實驗結果

1)相似度計算方法

首先,對相似度計算方法進行了對比，在基于用戶的協(xié)同過濾下，相似度計算分別采用修正余弦相似性、余弦相似性、相關相似性，在測試集和訓練集上進行了5次對比實驗，實驗結果如表2所示，實驗表明,相關相似性的MAE值最低，準確率最高，所以,本文相似度計算采用相關相似性。

表2 不同相似度計算方法下的MAE

2)最近鄰居集

按照相似度值形成用戶的鄰居用戶集，然后通過實驗確定鄰居數(shù)目k的大小。鄰居數(shù)目過少或過多均會影響推薦結果選取合適的k值可以使推薦結果更加準確。實驗中,分別取k=2，5，10，15，20，25，30，35，40，45，50，每個k值對應采用5個不同的數(shù)據(jù)集，并將5次實驗的MAE均值作為衡量算法優(yōu)劣的指標。如表3所示，隨著鄰居數(shù)目的增大，MAE值逐漸增大，k=10時推薦質量最好，也可看出用戶鄰居的數(shù)量影響很大。

表3 不同鄰居數(shù)下的MAE

3)不同算法下的MAE值

本文改進算法與基于用戶的協(xié)同過濾和加權Slope one算法做了比較。如圖1所示，在鄰居數(shù)k=10的條件下，每個算法在測試集和訓練集上分別做了5次實驗，由實驗可知：改進加權Slope one算法的預測效果明顯比基于用戶的協(xié)同過濾算法和加權Slope one算法的MAE值低，表明改進算法的推薦準確率高，算法的改進有很大的進步。

圖1 不同算法下的MAE

5 結束語

本文針對傳統(tǒng)Slope one算法在數(shù)據(jù)稀疏狀況下推薦準確度不高的影響，提出了改進加權Slope one協(xié)同過濾算法。算法首先根據(jù)用戶之間的相似性找出目標用戶的鄰居用戶，預測目標用戶的未評分項目的評分，通過對空白評分的填充，降低了數(shù)據(jù)的稀疏性，提高了推薦質量。而且本文考慮了用戶之間的相似性，提高了推薦算法的推薦精度。實驗結果表明：改進的加權Slope one算法的準確率較高，并在數(shù)據(jù)稀疏下達到滿意的推薦效果。

[1] Wang P,Ye H W.A personlized recommendation algorithm combining slope one scheme and user based collaborative filtering[C]∥International Conference on Industrial and Information Systems,2009:152-154.

[2] Zhang D J.An item-based collaborative filtering recommendation algorithm using Slope one scheme smoothing[C]∥2009 the 2nd International Symposium on Electronic Commerce and Security,Nanchang,China: IEEE Computer Society,2009:215-217.

[3] 柴 華,劉建毅.一種改進的Slope one推薦算法研究[J].信息網(wǎng)絡安全,2015(2):77-81.

[4] 惠周利,楊 明,潘晉孝.基于遺傳算法與FCSS相結合的模糊球殼聚類算法[J].傳感器與微系統(tǒng),2008,27(12):109-111.

[5] 安計勇,高貴閣,史志強,等.一種改進的k均值文本聚類算法[J].傳感器與微系統(tǒng),2015,34(5):130-133.

[6] 賀懷清,李圖波,李鐵軍.資源分配的改進Slope One算法[J].小型微型計算機系統(tǒng),2015,36(5):1056-1058.

[7] Lemire D,Maclachlan A.Slope one predictors for online rating based collaborative filtering[C]∥Proceedings of the 2005 SIAM Data Mining Conference,2005:471-480.

[8] Zhao J L,Ma J B.An improved slope one algorithm based on tag frequency[C]∥2013 the 3rd International Conference on Computer Science and Network Technology,IEEE,2013:369-372.

[9] Sarwar B.Item-based collaborative filtering recommendation algorithms[C]∥Proceedings of the 10th International Conference on World Wide Web,Hong Kong,China,2001:285-295.

[10] Wang Y,Lou H Y.Improved slope one algorithm for collaborative filtering[J].Computer Science,2011,38(A1):192-194.

Study on improved weighted Slope one collaborative filtering algorithm*

WANG Pan-pan, QIAN Qian, WANG Feng

(Yunnan Key Laboratory of Computer Technology Applications,Kunming University of Science and Technology,Kunming 650200,China)

Collaborative filtering is one of the most successful recommendation technologies,but the data sparsity results in low recommendation accuracy and poor efficiency.So an improved weighted Slope one and collaborative filtering algorithm is proposed.Based on users’ ratings,it calculates the similarity between users,so that to find user’s the nearest neighbors.Based on the score of user’s nearest neighbors,user-based collaborative filtering and weighted Slope one algorithm is used to predict the unknown rating of the target users and to present recommendation results.In the experiment,MovieLens data set is used as test data.The experimental results suggest that the improved algorithm improves prediction accuracy and recommendation performance.

data sparsity; user similarity; collaborative filtering; nearest neighbors; weighted Slope one algorithm

10.13873/J.1000—9787(2017)07—0138—04

2016—07—13

國家自然科學基金資助項目(61462053， 31300938)

TP 311

A

1000—9787(2017)07—0138—04

王潘潘(1992-)，女，碩士研究生，主要研究方向為推薦算法和人工智能。

錢 謙(1981-)，男，通訊作者，博士,副教授，碩士研究生導師，從事視覺認知與計算智能研究工作，E—mail:qianqian_yn@126.com。