基于用戶相似度的Slope one算法

孫 樂

（安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽淮南232001）

如今互聯(lián)網(wǎng)發(fā)展迅速，數(shù)據(jù)量爆發(fā)式的增長(zhǎng)。為了精確地獲取信息，個(gè)性化推薦系統(tǒng)應(yīng)運(yùn)而生，并在各種場(chǎng)合發(fā)揮著重要的作用[1-2]。slope one算法[3]是傳統(tǒng)協(xié)同過濾推薦算法的一種，計(jì)算過程簡(jiǎn)單且容易理解，但是其計(jì)算過程只參考了用戶評(píng)分之間的關(guān)系，沒有考慮用戶之間的相似關(guān)系，這就導(dǎo)致推薦結(jié)果準(zhǔn)確度降低。針對(duì)該問題，本文通過計(jì)算目標(biāo)用戶與其他用戶的相似度，篩選出最相近的前N個(gè)鄰居用戶組成新的用戶評(píng)分矩陣，減小相似度不高用戶的影響。流行度[4]是指對(duì)一個(gè)項(xiàng)目打出高分的用戶數(shù)，它反映用戶相似度的準(zhǔn)確性。平均因子是用戶對(duì)項(xiàng)目評(píng)分的平均值，是用戶相似度的一種體現(xiàn)。本文采用對(duì)用戶相似度加權(quán)的方法來降低或增加這些因素對(duì)用戶相似度的影響，從而提高推薦結(jié)果的準(zhǔn)確性。

1 相關(guān)算法的介紹

（1）slope one算法。slope one算法是用戶對(duì)物品評(píng)分差的線性算法，它是通過線性回歸模型來計(jì)算預(yù)測(cè)。slope one算法的具體步驟如下所示：

輸入：目標(biāo)用戶u與待檢測(cè)目標(biāo)項(xiàng)目j，用戶項(xiàng)目評(píng)分矩陣。輸出：目標(biāo)用戶u對(duì)項(xiàng)目j的預(yù)測(cè)評(píng)分。

1）遍歷目標(biāo)用戶u評(píng)分向量找出除目標(biāo)項(xiàng)目j外有評(píng)分的項(xiàng)目集合Rj，

2）遍歷用戶項(xiàng)目矩陣，找出對(duì)目標(biāo)項(xiàng)目j與項(xiàng)目集合Rj中項(xiàng)目均有評(píng)分的用戶集合Sj,k，

3）計(jì)算公共評(píng)分項(xiàng)目與目標(biāo)項(xiàng)目之間的平均評(píng)分偏差值dj,k，

4）預(yù)測(cè)目標(biāo)用戶對(duì)目標(biāo)項(xiàng)目j的評(píng)分pu,j，

其中，

Sj,k為對(duì)項(xiàng)目j和項(xiàng)目k均有評(píng)分的用戶集合，ri,j，ri,k為用戶i分別對(duì)項(xiàng)目j與項(xiàng)目k的評(píng)分，Rj為評(píng)分矩陣中與項(xiàng)目j同時(shí)被評(píng)分的項(xiàng)目集合，card(X)為在集合X中的元素個(gè)數(shù)。

（2）weighted slope one 算法。傳統(tǒng)slope one 算法忽略了評(píng)分用戶數(shù)量的影響。假設(shè)評(píng)分用戶矩陣中有100個(gè)用戶對(duì)項(xiàng)目w和目標(biāo)項(xiàng)目j都做出了評(píng)分，而對(duì)目標(biāo)項(xiàng)目j與項(xiàng)目y有200個(gè)用戶做出評(píng)分，顯然目標(biāo)項(xiàng)目j與項(xiàng)目y的平均評(píng)分偏差值比項(xiàng)目w與目標(biāo)項(xiàng)目j的平均評(píng)分偏差值更有說服力。weighted slope one算法在原始slope one算法的基礎(chǔ)上進(jìn)行了加權(quán)處理，預(yù)測(cè)公式為

其中cj,k=card(Sj,k)。

（3）基于用戶的協(xié)同過濾算法?；谟脩舻膮f(xié)同過濾算法[5]通過計(jì)算目標(biāo)用戶與其他用戶的相似度，篩選出與目標(biāo)用戶興趣最相似的鄰居用戶集合，進(jìn)而將鄰居用戶喜歡而目標(biāo)用戶沒有參與過評(píng)價(jià)的項(xiàng)目推薦給目標(biāo)用戶。主要包含4個(gè)步驟：收集用戶對(duì)項(xiàng)目的歷史評(píng)分構(gòu)建用戶評(píng)分矩陣；通過相似度公式計(jì)算目標(biāo)用戶與其他用戶的相似度，并選出前K個(gè)鄰居構(gòu)成集合；計(jì)算近鄰集合中的項(xiàng)目評(píng)分與相似度值的乘積，并求和取平均值作為預(yù)測(cè)值；選出預(yù)測(cè)評(píng)分靠前的項(xiàng)目推薦給目標(biāo)用戶。

2 相似性的度量方法

在推薦系統(tǒng)中用戶相似度[6]的計(jì)算是比較重要的環(huán)節(jié)。當(dāng)前衡量用戶相似性的方法主要有余弦相似性、修正余弦相似性、皮爾遜相關(guān)系數(shù)。余弦相似度的計(jì)算公式：

這里Iab為用戶ua與ub均有評(píng)分的項(xiàng)目集合，rac與rbc為用戶ua和ub分別對(duì)項(xiàng)目ic的評(píng)分。修正余弦相似性的計(jì)算公式如下：

3 改進(jìn)的slope one算法

3.1 基于用戶相似度的slope one算法

基于slope one算法的不足[7]，考慮將基于用戶的協(xié)同過濾算法與weighted slope one算法相結(jié)合[8-9]，以去除這些噪聲數(shù)據(jù)。采取K近鄰算法（KNN）[10]的思想計(jì)算選取與目標(biāo)用戶最相近的N個(gè)鄰居。在得到N個(gè)鄰居的項(xiàng)目-評(píng)分矩陣之后，通過weighted slope one算法對(duì)目標(biāo)用戶的未評(píng)分項(xiàng)目進(jìn)行評(píng)分預(yù)測(cè)，進(jìn)而推薦評(píng)分較高的項(xiàng)目。在計(jì)算的過程中將鄰居與目標(biāo)用戶的相似度值作為權(quán)值加入到平均評(píng)分偏差值，平均評(píng)分偏差值公式改進(jìn)后為，其中su,i為用戶i與目標(biāo)用戶u的用戶相似度。因此改進(jìn)算法的流程層次簡(jiǎn)單可分為3個(gè)層次：（1）在用戶評(píng)分矩陣中通過計(jì)算用戶相似度獲得目標(biāo)用戶的最相近鄰居集合。（2）在獲得的鄰居項(xiàng)目評(píng)分矩陣基礎(chǔ)上采用weighted slope one算法對(duì)目標(biāo)用戶沒有評(píng)價(jià)的項(xiàng)目進(jìn)行預(yù)測(cè)評(píng)分并排序。（3）將經(jīng)過排序后的前K個(gè)物品推薦給目標(biāo)用戶。值得注意的是N的取值大小，如果N的取值過小，會(huì)使數(shù)據(jù)嚴(yán)重流失；如果N的取值過大，則本文的改進(jìn)算法將沒有意義，因此鄰居個(gè)數(shù)的選擇至關(guān)重要。

3.2 流行度

上文已經(jīng)利用用戶之間的相似度提高了預(yù)測(cè)結(jié)果的準(zhǔn)確性，但是影響用戶相似度的因素還有很多，項(xiàng)目的流行程度就是其中一個(gè)因素。在一段時(shí)間內(nèi)每個(gè)用戶可能對(duì)熱門項(xiàng)目都傾向于打出高分[11]，這些流行項(xiàng)目通常只具有短暫的流行期，這些用戶受風(fēng)潮影響而打出更高的評(píng)分，卻并不代表喜歡這些項(xiàng)目的用戶更相似。這些熱門項(xiàng)目會(huì)將一些興趣并不相似的用戶作為鄰居，使得給目標(biāo)用戶推薦的結(jié)果不準(zhǔn)確，甚至只推薦熱門項(xiàng)目而并非個(gè)性化項(xiàng)目，所以在用戶相似度計(jì)算中進(jìn)行了加權(quán)處理：

其中|c|是表示對(duì)項(xiàng)目C評(píng)價(jià)過的用戶數(shù)量，通過1/ln(1+ |c|)削弱了流行度對(duì)用戶相似度的影響。

3.3 平均因子

用戶間的相似性還體現(xiàn)在用戶對(duì)項(xiàng)目的平均評(píng)分。兩個(gè)用戶越相似，他們對(duì)項(xiàng)目的偏好越相近，對(duì)于共同喜歡的項(xiàng)目?jī)A向于給予高分，對(duì)于共同厭惡的項(xiàng)目常打低分。顯然兩個(gè)用戶相似性越高，他們對(duì)項(xiàng)目的平均分就會(huì)越接近。所以，用戶之間對(duì)項(xiàng)目的平均評(píng)分的相似程度同樣影響著用戶之間的相似程度的準(zhǔn)確性，雖然傳統(tǒng)的協(xié)同過濾算法間接地考慮了平均評(píng)分因素，但是還需要增強(qiáng)其對(duì)相似度的影響?；谝陨系姆治鲈诹餍卸燃訖?quán)的用戶相似度公式的基礎(chǔ)上進(jìn)行加權(quán)，平均評(píng)分因子為A(x,y)=其中A（x,y）是用戶x與用戶y的平均評(píng)分因子分別為用戶x與用戶y對(duì)各自評(píng)價(jià)過的項(xiàng)目的評(píng)分平均值。平均評(píng)分因子的取值范圍為0至1，可以看出用戶之間相似度越高平均因子越接近1，相反用戶之間的相似度越低，平均因子越接近0。加權(quán)后的用戶相似度為

4 實(shí) 驗(yàn)

（1）實(shí)驗(yàn)數(shù)據(jù)集。本文采用了Movie Lens數(shù)據(jù)集[12]，該數(shù)據(jù)是由用戶對(duì)電影的評(píng)分?jǐn)?shù)據(jù)、用戶ID、電影ID等組成，該數(shù)據(jù)集常用的有3種規(guī)格，分別為Movie Lens100 K,Movie Lens1 M,Movies Lens10 M。這里選用Movie Lens100 K數(shù)據(jù)集，該數(shù)據(jù)集包含943位用戶為1 682部電影的打分?jǐn)?shù)據(jù)集合，評(píng)分?jǐn)?shù)值為1至5的整數(shù)值，數(shù)值越低表示對(duì)該電影越不喜歡，數(shù)值越高表示越喜愛該電影。

（2）實(shí)驗(yàn)工具介紹。實(shí)驗(yàn)采用的是基于java的開源算法庫Librec，它包含了70余種推薦算法，4種評(píng)分評(píng)估指標(biāo)和10種排行評(píng)估指標(biāo)等多種功能組件，基本能夠滿足推薦系統(tǒng)的要求。Librec項(xiàng)目的系統(tǒng)分為3個(gè)模塊：用Data Model可以讀取、分割數(shù)據(jù)，并且可以導(dǎo)入其他數(shù)據(jù)；用Recommender可以完成對(duì)模型數(shù)據(jù)的預(yù)測(cè)、相似度計(jì)算、模型的持久化等；用evaluate和filter對(duì)預(yù)測(cè)結(jié)果篩選及評(píng)估。因Librec模塊之間的耦合度低且易于擴(kuò)展，所以本文采用Librec作為工具庫。

（3）檢驗(yàn)標(biāo)準(zhǔn)。在推薦系統(tǒng)中常用的評(píng)估方法是平均絕對(duì)誤差（MAE）和均方根誤差（RMSE），這兩種方法容易理解并且計(jì)算簡(jiǎn)單，對(duì)推薦質(zhì)量的好壞有比較直觀的體現(xiàn)。本文用平均絕對(duì)誤差M作為結(jié)果評(píng)估的標(biāo)準(zhǔn)其中pi是項(xiàng)目i的預(yù)測(cè)評(píng)分，qi是項(xiàng)目i的實(shí)際評(píng)分，ω為權(quán)重，N為評(píng)分的總個(gè)數(shù)。M的值越小，表示推薦結(jié)果的準(zhǔn)確性越高。

（4）實(shí)驗(yàn)流程。先確定合適的相似度度量方法。通過實(shí)驗(yàn)對(duì)余弦相似度、修正的余弦相似度以及皮爾遜相關(guān)系數(shù)這3種度量方法[13]的精確度進(jìn)行對(duì)比，鄰居個(gè)數(shù)的選取采取以10為單位的增長(zhǎng)方式，評(píng)估標(biāo)準(zhǔn)采用平均絕對(duì)誤差，最終的實(shí)驗(yàn)比較結(jié)果如圖1所示。

圖1 3種相似度度量方法的比較

由圖1可以看出，修正的余弦相似度的M值隨著鄰居個(gè)數(shù)的增加趨于平穩(wěn)，且低于其余兩種相似度計(jì)算方法，說明其精確度更高，因此本文采用修正的余弦相似度作為相似度度量方法。

接著需要確定改進(jìn)slope one 算法中鄰居N的取值，這里以10%為間隔取值，分別取N為數(shù)據(jù)集的10%、20%、30%、…、80%。通過實(shí)驗(yàn)得到N分別取不同值時(shí)M值，如圖2所示。

圖2 鄰居N取不同值時(shí)的M值

通過實(shí)驗(yàn)可以看出，隨著N取值的增大M值慢慢減小，當(dāng)N為數(shù)據(jù)集的60%時(shí)M最小，之后M隨著N值的增大慢慢增加，因此N的取值為數(shù)據(jù)集的60%，此時(shí)精確度最高。之后將改進(jìn)的算法與slope one算法、weighted slope one算法進(jìn)行評(píng)估對(duì)比，實(shí)驗(yàn)結(jié)果如圖3所示。

通過對(duì)比可以看出，本文改進(jìn)算法的M值低于slope one算法、weighted slope one算法，說明改進(jìn)的slope one的推薦精確度要比其他兩種算法高。

圖3 3種算法的比較

5 總 結(jié)

本文分析了slope one算法以及weighted slope one算法，針對(duì)算法中只考慮了用戶評(píng)分之間的線性關(guān)系而沒有考慮用戶之間的相似性的問題，提出將基于用戶相似度的協(xié)同過濾算法與weighted slope one算法相結(jié)合的方法。在此基礎(chǔ)上，本文還分析了項(xiàng)目流行度與平均因子對(duì)用戶相似度的影響，通過對(duì)用戶相似度加權(quán)來降低流行度的影響，同時(shí)用平均因子加權(quán)來增加其對(duì)用戶相似度的影響。通過實(shí)驗(yàn)對(duì)比證明，改進(jìn)的slope one算法比現(xiàn)有的slope one算法具有更高的預(yù)測(cè)精度。