改進(jìn)加權(quán)Slope one協(xié)同過(guò)濾推薦算法研究*

王潘潘， 錢 謙， 王 鋒

(云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室 昆明理工大學(xué)，云南 昆明 650200)

?

改進(jìn)加權(quán)Slope one協(xié)同過(guò)濾推薦算法研究*

王潘潘， 錢 謙， 王 鋒

(云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室 昆明理工大學(xué)，云南 昆明 650200)

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

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

0 引 言

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

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

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

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

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

1)余弦相似性

用戶的評(píng)分可看做n維項(xiàng)目空間上的向量，如果用戶對(duì)項(xiàng)目沒有評(píng)分，則用戶對(duì)項(xiàng)目的評(píng)分為0。設(shè)用戶i和用戶j在n維項(xiàng)目空間上的評(píng)分表示為向量i→和向量j→，用戶i，j之間的相似性計(jì)算公式為

(1)

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

2)修正的余弦相似性

設(shè)用戶i和用戶j共同評(píng)分過(guò)的項(xiàng)目集合用Ii,j表示，用戶i和用戶j之間的相似性計(jì)算公式為

(2)

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

設(shè)用戶i和用戶j共同評(píng)分過(guò)的項(xiàng)目集合用Ii,j表示，Ii,j=Ii∩Ij，用戶i和用戶j之間的相似性計(jì)算公式

(3)

本文使用相似度計(jì)算方法來(lái)確定目標(biāo)用戶的最近鄰居，計(jì)算用戶與用戶之間的相似度，通過(guò)實(shí)驗(yàn)確定用戶與用戶之間的相似度計(jì)算方法，空白評(píng)分的預(yù)測(cè)公式為

(4)

2 加權(quán)Slope one算法

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

表1 三個(gè)項(xiàng)目的評(píng)分

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

(5)

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

(6)

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

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

(7)

式中 cj,i為加權(quán)值cj,i=card(Sj,i(χ));預(yù)測(cè)評(píng)分值用PwSl(u)j表示。

3 改進(jìn)加權(quán)Slope one協(xié)同過(guò)濾推薦算法

加權(quán)Slopeone算法的缺點(diǎn)是沒有考慮用戶之間和項(xiàng)目之間的相似度問題，改進(jìn)算法根據(jù)用戶的協(xié)同過(guò)濾，選出目標(biāo)用戶的前k個(gè)最近鄰，最近鄰集合用S(k)表示，根據(jù)最近鄰用戶集合S(k)使用加權(quán)Slopeone算法預(yù)測(cè)未評(píng)分值。計(jì)算目標(biāo)用戶和其他鄰居用戶的相似度，對(duì)共同評(píng)分的項(xiàng)目可以得到一個(gè)評(píng)分相似度權(quán)值Weight為

(8)

式中 Ri,t≠0，Ri,t為用戶i對(duì)目標(biāo)項(xiàng)目t的評(píng)分;card(Ri,t)為評(píng)分總數(shù)。通過(guò)改進(jìn)的加權(quán)Slopeone算法，給出推薦結(jié)果，改進(jìn)的預(yù)測(cè)評(píng)分公式為

(9)

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

輸入：用戶—項(xiàng)目評(píng)分?jǐn)?shù)據(jù)集，目標(biāo)用戶為u，目標(biāo)項(xiàng)目為itemj。

輸出：目標(biāo)用戶對(duì)項(xiàng)目的預(yù)測(cè)評(píng)分值P(u)j。

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

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

3)在最近鄰用戶集合S(k)條件下，獲取鄰居用戶id值，計(jì)算每個(gè)用戶評(píng)分過(guò)的項(xiàng)目之間的評(píng)分差值，使用式(10)計(jì)算目標(biāo)用戶的未評(píng)分值。如果目標(biāo)用戶的鄰居用戶沒有對(duì)當(dāng)前項(xiàng)目評(píng)分，則項(xiàng)目預(yù)測(cè)評(píng)分值由當(dāng)前用戶對(duì)所有項(xiàng)目的評(píng)分均值代替。

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

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

4.2 度量標(biāo)準(zhǔn)

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

(10)

式中Pi為預(yù)測(cè)評(píng)分值;Ri為用戶的實(shí)際評(píng)分值。MAE值越小，預(yù)測(cè)精確度越高。

4.3 實(shí)驗(yàn)結(jié)果

1)相似度計(jì)算方法

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

表2 不同相似度計(jì)算方法下的MAE

2)最近鄰居集

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

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

3)不同算法下的MAE值

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

圖1 不同算法下的MAE

5 結(jié)束語(yǔ)

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

[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] 柴 華,劉建毅.一種改進(jìn)的Slope one推薦算法研究[J].信息網(wǎng)絡(luò)安全,2015(2):77-81.

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

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

[6] 賀懷清,李圖波,李鐵軍.資源分配的改進(jìn)Slope One算法[J].小型微型計(jì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61462053， 31300938)

TP 311

A

1000—9787(2017)07—0138—04

王潘潘(1992-)，女，碩士研究生，主要研究方向?yàn)橥扑]算法和人工智能。

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