王竹婷，夏竹青，周艷玲

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

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

王竹婷，夏竹青，周艷玲

(合肥學(xué)院 計(jì)算機(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ù)對(duì)目標(biāo)用戶的未知評(píng)分項(xiàng)進(jìn)行評(píng)分預(yù)測(cè)，在movielens數(shù)據(jù)集上的測(cè)試結(jié)果表明，改進(jìn)后的算法能夠較為顯著的提高推薦質(zhì)量，適用于處理大規(guī)模數(shù)據(jù)。

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

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

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

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

本文認(rèn)為SlopeOne算法利用所有的歷史評(píng)分?jǐn)?shù)據(jù)進(jìn)行預(yù)測(cè)，難免會(huì)引入噪聲數(shù)據(jù)，從而增加預(yù)測(cè)產(chǎn)生的誤差，擬將其與基于用戶的近鄰算法相結(jié)合，采用近鄰用戶數(shù)據(jù)進(jìn)行評(píng)分預(yù)測(cè)；其次，經(jīng)過實(shí)驗(yàn)測(cè)試得出在SlopeOne的三種算法模型中，加權(quán)SlopeOne算法的預(yù)測(cè)效果最優(yōu)，但其權(quán)值選擇過于簡(jiǎ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ù)測(cè)結(jié)果。

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

(4)

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

在加權(quán)SlopeOne算法中為每一項(xiàng)評(píng)分預(yù)測(cè)結(jié)果分配不同的權(quán)值是非常有必要的。因?yàn)?，SlopeOne算法實(shí)則是根據(jù)不同項(xiàng)目評(píng)分之間的關(guān)聯(lián)性進(jìn)行預(yù)測(cè)，不同項(xiàng)目之間的關(guān)聯(lián)強(qiáng)度也有所差別，簡(jiǎn)單的采用共同評(pí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ù)測(cè)效果。

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

(5)

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

關(guān)聯(lián)規(guī)則原理中的支持度和置信度往往能夠較為準(zhǔn)確的反映不同項(xiàng)目之間的關(guān)聯(lián)程度，在使用SlopeOne算法進(jìn)行評(píng)分預(yù)測(cè)之前，首先進(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ù)測(cè)的準(zhǔn)確性會(huì)比原方法有所提高。

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

(6)

2.3基于近鄰的關(guān)聯(lián)加權(quán)SlopeOne算法公式(6)可以通過用戶評(píng)分?jǐn)?shù)據(jù)計(jì)算出目標(biāo)用戶與其他所有用戶間的相似度值，選擇一個(gè)合適的閾值，將相似度大于該閾值的用戶作為近鄰用戶，再采用近鄰用戶已有項(xiàng)目的評(píng)分?jǐn)?shù)據(jù)通過關(guān)聯(lián)加權(quán)SlopeOne算法預(yù)測(cè)目標(biāo)用戶的未知評(píng)分項(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)的測(cè)試數(shù)據(jù)集，該數(shù)據(jù)集包含943位用戶對(duì)1682部電影的100 000個(gè)評(píng)分項(xiàng)，評(píng)分值在1-5之間，其中1為用戶給予的最低評(píng)分，表示用戶非常不喜歡該電影，5為最高評(píng)分，表示用戶非常喜歡該電影。每位用戶至少有20部電影的評(píng)分記錄，除此之外，還包括一些簡(jiǎn)單的用戶信息，如年齡、性別、職業(yè)等。本次實(shí)驗(yàn)只需處理用戶編號(hào)、電影編號(hào)和評(píng)分值這三部分信息。采用五折交叉法對(duì)改進(jìn)前后的算法進(jìn)行對(duì)比分析。

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

(7)

(8)

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

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

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

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

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

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

4 結(jié)束語

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

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

TP301.6

A

2096-2371(2017)05-0089-04

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