近鄰的關(guān)聯(lián)加權(quán)SlopeOne協(xié)同過濾算法

王竹婷，夏竹青，周艷玲

(合肥學(xué)院 計算機(jī)科學(xué)與技術(shù)系，合肥 230601)

近鄰的關(guān)聯(lián)加權(quán)SlopeOne協(xié)同過濾算法

王竹婷，夏竹青，周艷玲

(合肥學(xué)院 計算機(jī)科學(xué)與技術(shù)系，合肥 230601)

協(xié)同過濾是目前電子商務(wù)推薦系統(tǒng)中應(yīng)用最為廣泛的一類推薦算法。隨著系統(tǒng)用戶和項(xiàng)目數(shù)量的急劇增加，傳統(tǒng)的協(xié)同過濾算法已經(jīng)很難滿足各類系統(tǒng)的需求。為提高算法處理大規(guī)模數(shù)據(jù)的能力，重點(diǎn)研究SlopeOne協(xié)同過濾推薦算法。將其與關(guān)聯(lián)規(guī)則挖掘相結(jié)合，并選擇近鄰用戶數(shù)據(jù)對目標(biāo)用戶的未知評分項(xiàng)進(jìn)行評分預(yù)測，在movielens數(shù)據(jù)集上的測試結(jié)果表明，改進(jìn)后的算法能夠較為顯著的提高推薦質(zhì)量，適用于處理大規(guī)模數(shù)據(jù)。

協(xié)同過濾；SlopeOne; 關(guān)聯(lián)規(guī)則

電子商務(wù)個性化推薦系統(tǒng)可以根據(jù)用戶的網(wǎng)上瀏覽、購買或評分信息分析用戶的興趣愛好，并快速、準(zhǔn)確的為用戶提供個性化產(chǎn)品推薦。該系統(tǒng)一方面可以幫助在線商品銷售商快速、準(zhǔn)確鎖定目標(biāo)用戶，增加線上商品的銷售量；另一方面幫助用戶解決因信息過載而造成的困擾，提高在線服務(wù)質(zhì)量，增加客戶的滿意度。而協(xié)同過濾技術(shù)作為推薦系統(tǒng)中最為關(guān)鍵的技術(shù)之一，在個性化推薦系統(tǒng)中得到了廣泛的應(yīng)用。[1]

協(xié)同過濾算法通常分為基于模型和基于近鄰的兩大類，基于模型的協(xié)同過濾采用機(jī)器學(xué)習(xí)中的相關(guān)模型通過訓(xùn)練集數(shù)據(jù)產(chǎn)生預(yù)測模塊，再通過該模塊預(yù)測用戶感興趣的項(xiàng)目。[2]基于近鄰的協(xié)同過濾又可細(xì)分為基于用戶和基于項(xiàng)目的兩類，兩者都基于一個非常簡單的思想，即興趣相投的用戶有較大的可能會喜愛同類型的項(xiàng)目，或相似的項(xiàng)目被同一用戶同時喜愛的幾率是比較高的。[3]該算法的關(guān)鍵步驟就是通過系統(tǒng)中的歷史評分?jǐn)?shù)據(jù)計算不同用戶或項(xiàng)目之間的相似性，再根據(jù)近鄰用戶或目標(biāo)用戶已有的評分記錄預(yù)測其他項(xiàng)目的評分，選擇評分值高的推薦給目標(biāo)用戶。

SlopeOne[4]是Daniel Lemire教授在2005年提出的一種非常簡單、高效的基于項(xiàng)目的協(xié)同過濾算法，[5]該算法依然是通過現(xiàn)有項(xiàng)目的評分值產(chǎn)生未知項(xiàng)目的預(yù)測評分，但無需計算項(xiàng)目之間的相似度，而是通過統(tǒng)計不同項(xiàng)目間的平均評分偏差，采用一元線性回歸模型，根據(jù)目標(biāo)用戶現(xiàn)有評分值進(jìn)行未知項(xiàng)目預(yù)測。該算法不僅運(yùn)算速度極快，而且預(yù)測結(jié)果非常接近目前較為先進(jìn)的高精度算法。

本文認(rèn)為SlopeOne算法利用所有的歷史評分?jǐn)?shù)據(jù)進(jìn)行預(yù)測，難免會引入噪聲數(shù)據(jù)，從而增加預(yù)測產(chǎn)生的誤差，擬將其與基于用戶的近鄰算法相結(jié)合，采用近鄰用戶數(shù)據(jù)進(jìn)行評分預(yù)測；其次，經(jīng)過實(shí)驗(yàn)測試得出在SlopeOne的三種算法模型中，加權(quán)SlopeOne算法的預(yù)測效果最優(yōu)，但其權(quán)值選擇過于簡單，加權(quán)改進(jìn)效果并不十分理想，本文認(rèn)為關(guān)聯(lián)規(guī)則挖掘中的置信度更能反映兩項(xiàng)目間的關(guān)聯(lián)關(guān)系，以置信度為權(quán)值則更為合適。實(shí)驗(yàn)結(jié)果證明，本文提出的改進(jìn)算法可以得到更為精確的預(yù)測結(jié)果。

1 問題描述和相關(guān)工作

1.1問題定義假設(shè)一個推薦系統(tǒng)中有m個用戶和n個推薦項(xiàng)目，用戶集合為U={U1,U2,…,Um}，項(xiàng)

目集合為I={I1,I2,…,In}，系統(tǒng)中的歷史評分?jǐn)?shù)據(jù)采用用戶-項(xiàng)目評分矩陣表示，如表1所示，Rij為用戶i對項(xiàng)目j的評分值。如果用戶未對某一項(xiàng)目評分，則用0表示。實(shí)際推薦系統(tǒng)中由于用戶和項(xiàng)目數(shù)量十分龐大，而每位用戶評分過的項(xiàng)目數(shù)量又非常有限，用戶-項(xiàng)目矩陣中存在大量空缺值，協(xié)同過濾算法的任務(wù)是計算出空缺項(xiàng)的預(yù)測評分，以此為依據(jù)預(yù)測用戶的喜好程度進(jìn)行項(xiàng)目推薦。

表1 用戶-項(xiàng)目評分矩陣

1.2SlopeOne算法SlopeOne算法分為三個步驟：首先利用歷史評分?jǐn)?shù)據(jù)，如上表所示，構(gòu)建用戶-項(xiàng)目矩陣；在用戶-項(xiàng)目矩陣基礎(chǔ)上，統(tǒng)計每兩個項(xiàng)目被同一用戶共同評分的次數(shù)和全部評分差值的總和，計算項(xiàng)目評分偏差的均值；最后根據(jù)每位用戶現(xiàn)有評分值和項(xiàng)目評分偏差，利用一元線性回歸模型，預(yù)測未知項(xiàng)目評分值。Daniel Lemire教授在給出SlopeOne基本算法時，同時給出了其兩種改進(jìn)型算法：加權(quán)SlopeOne和雙極SlopeOne，算法介紹如下。

(1)SlopeOne。SlopeOne算法屬于基于項(xiàng)目的評分預(yù)測算法，其采用一元線性回歸模型f(v)=v+b預(yù)測評分，b為用戶對兩個項(xiàng)目評分偏差的均值，例如有兩個用戶U1和U2，同時給項(xiàng)目Ii評分，U1給了1分，U2給了2分，同時U1又對項(xiàng)目Ij評分為1.5，那么此時可以預(yù)測，用戶U2給項(xiàng)目Ij的評分為2+0.5=2.5，其中2為已知用戶U2對項(xiàng)目Ii的評分，b=1.5-1=0.5為項(xiàng)目Ii和項(xiàng)目Ij的評分偏差。當(dāng)系統(tǒng)中某兩個項(xiàng)目有多個用戶同時給過評分時，b則為多個用戶評分偏差的均值，具體算法細(xì)節(jié)如下所述。

對于給定的訓(xùn)練集χ，其中的任意兩個項(xiàng)目Ii和Ij，找出共同評分過該兩個項(xiàng)目的用戶集Sij(χ)，則評分偏差均值devij計算方法如下，card(Sij(χ))為集合Sij(χ)中用戶數(shù)量。

(1)

根據(jù)上述一元回歸模型，Rai+devij為用戶Ua對項(xiàng)目Ij的預(yù)測評分，當(dāng)且僅當(dāng)用戶Ua只對項(xiàng)目Ii進(jìn)行了評分。一般情況下，用戶已有的評分項(xiàng)不只一項(xiàng)，那么此時，就要將多個預(yù)測結(jié)果的均值作為最終的預(yù)測評分，計算方法如下所示，Ra表示所有用戶Ua評分過的項(xiàng)目。

(2)

(2)加權(quán)SlopeOne。直觀上講，兩個項(xiàng)目同時被用戶評分的次數(shù)越多，那么以這兩個項(xiàng)目的評分偏差預(yù)測評分的結(jié)果越準(zhǔn)確，加權(quán)SlopeOne則基于這樣的思想，為每項(xiàng)預(yù)測評分增加了權(quán)值cij，cij即共同評分過項(xiàng)目Ii和Ij的用戶數(shù)。

(3)

(4)

2 關(guān)聯(lián)加權(quán)的SlopeOne

在加權(quán)SlopeOne算法中為每一項(xiàng)評分預(yù)測結(jié)果分配不同的權(quán)值是非常有必要的。因?yàn)椋琒lopeOne算法實(shí)則是根據(jù)不同項(xiàng)目評分之間的關(guān)聯(lián)性進(jìn)行預(yù)測，不同項(xiàng)目之間的關(guān)聯(lián)強(qiáng)度也有所差別，簡單的采用共同評分項(xiàng)的數(shù)量作為權(quán)值去衡量這種關(guān)聯(lián)性雖然較基本模型有所改進(jìn)，但這種衡量方式難免有失偏頗。本文認(rèn)為將關(guān)聯(lián)規(guī)則分析引入該模型用于改善加權(quán)系數(shù)應(yīng)該能夠得到更為準(zhǔn)確的預(yù)測效果。

2.1關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則最早被零售行業(yè)用于進(jìn)行購物籃分析，從中找出哪些商品被用戶同時購買的可能性較大，將其捆綁銷售可以極大的增加商品的銷售量。[6]本文采用關(guān)聯(lián)規(guī)則基本原理，針對待推薦項(xiàng)目挖掘一階和二階頻繁項(xiàng)集，并計算所有二階頻繁項(xiàng)集的置信度，以置信度為加權(quán)SlopeOne算法的權(quán)值，計算方法如下。

(5)

公式(5)中，P(Ii)表示項(xiàng)目Ii出現(xiàn)的概率，也叫項(xiàng)目的Ii支持度，當(dāng)支持度高于事先設(shè)定的閾值時，我們稱該項(xiàng)目為一階頻繁項(xiàng)集；P(Ii∩Ij)為項(xiàng)目Ii和Ij同時出現(xiàn)的概率，也稱為該二階項(xiàng)集的支持度，同樣當(dāng)該支持度高于給定的閾值時，稱之為二階頻繁項(xiàng)集。confij為項(xiàng)目Ii對項(xiàng)目Ij的置信度，即項(xiàng)目Ii出現(xiàn)時項(xiàng)目Ij同時出現(xiàn)的概率。

關(guān)聯(lián)規(guī)則原理中的支持度和置信度往往能夠較為準(zhǔn)確的反映不同項(xiàng)目之間的關(guān)聯(lián)程度，在使用SlopeOne算法進(jìn)行評分預(yù)測之前，首先進(jìn)行關(guān)聯(lián)規(guī)則挖掘，可除去關(guān)聯(lián)性較弱的噪聲數(shù)據(jù)，并采用置信度confij取代公式(3)中的權(quán)值cij，以項(xiàng)目間的關(guān)聯(lián)強(qiáng)度為權(quán)值，預(yù)測的準(zhǔn)確性會比原方法有所提高。

2.2用戶相似度SlopeOne算法將所有用戶的評分不經(jīng)過任何篩選全部用于做預(yù)測難免會增加其預(yù)測誤差。本文將借鑒基于用戶的協(xié)同過濾算法，首先計算用戶相似度，再選擇近鄰用戶的評分?jǐn)?shù)據(jù)進(jìn)行預(yù)測。傳統(tǒng)的用戶相似性度量方法主要包括Pearson相關(guān)系數(shù)和余弦相似性，考慮到Pearson相關(guān)系數(shù)要求兩個向量之間必須線性相關(guān)，而實(shí)際兩用戶的評分?jǐn)?shù)據(jù)很難保證線性相關(guān)；余弦相似性則通過衡量兩用戶評分向量的夾角余弦作為用戶相似度值，但未考慮到不同用戶的評分尺度問題。因此，本文采用修正的余弦相似性，計算方法如下。

(6)

2.3基于近鄰的關(guān)聯(lián)加權(quán)SlopeOne算法公式(6)可以通過用戶評分?jǐn)?shù)據(jù)計算出目標(biāo)用戶與其他所有用戶間的相似度值，選擇一個合適的閾值，將相似度大于該閾值的用戶作為近鄰用戶，再采用近鄰用戶已有項(xiàng)目的評分?jǐn)?shù)據(jù)通過關(guān)聯(lián)加權(quán)SlopeOne算法預(yù)測目標(biāo)用戶的未知評分項(xiàng)。

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

3.1數(shù)據(jù)集實(shí)驗(yàn)采用Minnesota大學(xué)GroupLens項(xiàng)目研究小組提供的movielens數(shù)據(jù)集，選取其中的m100k為本實(shí)驗(yàn)的測試數(shù)據(jù)集，該數(shù)據(jù)集包含943位用戶對1682部電影的100 000個評分項(xiàng)，評分值在1-5之間，其中1為用戶給予的最低評分，表示用戶非常不喜歡該電影，5為最高評分，表示用戶非常喜歡該電影。每位用戶至少有20部電影的評分記錄，除此之外，還包括一些簡單的用戶信息，如年齡、性別、職業(yè)等。本次實(shí)驗(yàn)只需處理用戶編號、電影編號和評分值這三部分信息。采用五折交叉法對改進(jìn)前后的算法進(jìn)行對比分析。

3.2評價指標(biāo)本文擬采用平均絕對偏差(Mean Absolute Error, MAE)為評估算法推薦效果優(yōu)劣的指標(biāo)，其計算方法如公式(7)所示，pij是由訓(xùn)練集數(shù)據(jù)計算產(chǎn)生的預(yù)測評分，qij是測試集中用戶的實(shí)際評分，Ni是測試集中所提供的用戶i的評分?jǐn)?shù)量，MAEi是用戶i對Ni個項(xiàng)目預(yù)測評分的平均絕對偏差，公式(8)中M是全體用戶總數(shù)，MAE則是全體用戶的平均絕對偏差。該公式就是通過計算用戶預(yù)測評分與實(shí)際評分的差值來評價算法推薦效果的。如果MAE值越小，表明算法的預(yù)測結(jié)果越接近實(shí)際評分，推薦效果越理想。

(7)

(8)

3.3實(shí)驗(yàn)結(jié)果及分析正如本文第一部分所介紹，Daniel Lemire教授為SlopeOne算法設(shè)計了三種模型，分別為SlopeOne、加權(quán)SlopeOne和雙極加權(quán)SlopeOne。我們首先設(shè)計實(shí)驗(yàn)驗(yàn)證該三種算法在movielens數(shù)據(jù)集上的測試結(jié)果。實(shí)驗(yàn)采用5折交叉法，即將數(shù)據(jù)集隨機(jī)分成5等份，選擇其中的4份做訓(xùn)練集、1

份做測試集，執(zhí)行5次，將5次實(shí)驗(yàn)得到的平均MAE值作為算法的最終測試結(jié)果。如表2所示。無論是單次測試結(jié)果還是平均值，都表明加權(quán)SlopeOne算法的預(yù)測結(jié)果與實(shí)際值最接近。

表2 三種SlopeOne模型的測試結(jié)果

為驗(yàn)證本文所提出的改進(jìn)策略具有的有效性，在相同的數(shù)據(jù)集下，將改進(jìn)后的基于近鄰的關(guān)聯(lián)加權(quán)SlopeOne與加權(quán)SlopeOne進(jìn)行對比分析。由于傳統(tǒng)的加權(quán)SlopeOne算法在進(jìn)行預(yù)測評分時選用用戶共同評分的項(xiàng)目數(shù)量作為權(quán)值，方法略顯簡單。本文引入關(guān)聯(lián)規(guī)則挖掘中的置信度作為權(quán)值，更能夠準(zhǔn)確

的反映出不同項(xiàng)目間的關(guān)聯(lián)關(guān)系，而基于余弦相似度的近鄰用戶的選擇可以過濾掉一部分噪聲數(shù)據(jù)，進(jìn)一步提高預(yù)測的的精確度。如表3所示，實(shí)驗(yàn)測試結(jié)果表明關(guān)聯(lián)加權(quán)和基于近鄰的改進(jìn)策略均可以一定程度上提高協(xié)同過濾算法預(yù)測的準(zhǔn)確性。

表3 本文算法與加權(quán)SlopeOne測試結(jié)果

4 結(jié)束語

SlopeOne算法是一種基于項(xiàng)目的協(xié)同過濾算法，其突出特點(diǎn)是算法簡單，計算速度快，而且相比傳統(tǒng)的推薦協(xié)同過濾算法，該算法的推薦質(zhì)量較高，適用于進(jìn)行大規(guī)模數(shù)據(jù)處理，尤其當(dāng)推薦系統(tǒng)中用戶數(shù)量遠(yuǎn)遠(yuǎn)大于項(xiàng)目數(shù)量時，無需計算用戶間的相似度，實(shí)際應(yīng)用時可以較大程度上提高算法的推薦速度。本文首先介紹了3種SlopeOne算法模型，并通過真實(shí)數(shù)據(jù)集分別測試這3種模型，得出加權(quán)SlopeOne算法的推薦精度最高，分析加權(quán)SlopeOne存在的不足之處，引入關(guān)聯(lián)規(guī)則加以改進(jìn)，同時，參考基于用戶的協(xié)同過濾算法，選擇近鄰用戶數(shù)據(jù)進(jìn)行預(yù)測評分。實(shí)驗(yàn)結(jié)果證明，兩種改進(jìn)策略均能一定程度上提高算法的推薦效果。在實(shí)際推薦系統(tǒng)中，我們建議當(dāng)項(xiàng)目數(shù)量遠(yuǎn)大于用戶數(shù)量時，采用基于近鄰的加權(quán)SlopeOne算法，用戶相似度和關(guān)聯(lián)規(guī)則的提取可以離線完成，無需消耗在線資源；當(dāng)用戶數(shù)量遠(yuǎn)大于項(xiàng)目數(shù)量時，則無需選擇近鄰用戶，直接采用關(guān)聯(lián)加權(quán)SlopeOne即可得到較為滿意的推薦效果。

[1] Adomavicius G，Tuzhilin A. Toward the Next Gneration of Recommender Systems: a Survey of the State-of-the-art and Possible Extensions[J]. IEEE Transactions on Knowledge and Data Engineering,2005,17(6):734-749.

[2] Hofmann T.Latent Semantic Models for Collaborative Filtering[J]. ACM Transactions on Information Systems,2004,22(1):89-115.

[3] Choi K, Suh Y.A New Similarity Function for Selecting Neighbors for Each Target Item Incollaborative Filtering[J]. Knowledge-Based Systems, 2013,37 :146-153.

[4] Lemire D，Maclachlan A.Slope One Predictors for Online Rating-Based Collaborative Filtering[C]// SIAM International Conference on Data Mining,2005:471-480.

[5] 張玉連; 郇思思; 梁順攀;融合機(jī)器學(xué)習(xí)的加權(quán)Slope One算法[J]. 小型微型計算機(jī)系統(tǒng),2016,6(6):1174-1178.

[6] Leung C W, Chan S C,Chung F .An Empirical Study of a Cross-level Association Rule Mining Approach to Cold-start Recommendations[J]. Knowledge-Based Systems,2008,21(7):515-529.

AnImprovedSlopeOneCollaborativeFilteringRecommendationAlgorithmBasedonNearNeighborsandAssociationRules

WANG Zhu-ting，XIA Zhu-qing，ZHOU Yan-ling

(Department of Computer Science and Technology ,Hefei University, Hefei 230601, China)

Collaborative filtering is one of the most widely used Recommendation algorithms in E-commerce Recommender Systems. As the number of users and projects increase rapidly, the traditional collaborative filtering algorithm has been difficult to meet the needs of various systems. To improve the ability of processing large-scale data, we pay more attention on study of SlopeOne collaborative filtering recommendation algorithm. Combining SlopeOne with association rules, and then selecting the nearest neighbor data to predict the unknown scoring items of target users. The test of the results on the movielens dataset show that the improved algorithm can significantly improve the recommendation quality, and is suitable for dealing with large-scale data.

collaborative filtering; SlopeOne; association rules

2017-06-26

2017-09-21

安徽省教育廳自然科學(xué)資助項(xiàng)目(KJ2016A609)，安徽省創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項(xiàng)目(201511059266)，合肥學(xué)院科研發(fā)展基金資助項(xiàng)目(14KY11ZR)，合肥學(xué)院重點(diǎn)建設(shè)學(xué)科(2016xk05)資助。

王竹婷(1984— )，女，安徽馬鞍山人，合肥學(xué)院計算機(jī)科學(xué)與技術(shù)系助理實(shí)驗(yàn)師。

TP301.6

A

2096-2371(2017)05-0089-04

[責(zé)任編輯：張永軍]