基于修正相似度的User-Based協(xié)同過(guò)濾推薦算法

王竹婷 夏竹青 周艷玲

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

基于修正相似度的User-Based協(xié)同過(guò)濾推薦算法

王竹婷 夏竹青 周艷玲

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

運(yùn)用傳統(tǒng)的User-Based協(xié)同過(guò)濾算法計(jì)算用戶相似度時(shí)，因數(shù)據(jù)過(guò)度稀疏而易造成較大的計(jì)算偏差。為了有效提高該算法的準(zhǔn)確性，研究改進(jìn)相似度計(jì)算方法。根據(jù)用戶現(xiàn)有的評(píng)分?jǐn)?shù)據(jù)計(jì)算每個(gè)項(xiàng)目的自信息量，根據(jù)自信息量為不同的項(xiàng)目分配權(quán)值，利用權(quán)值來(lái)修正傳統(tǒng)的相似度計(jì)算方法。當(dāng)用戶共同評(píng)分項(xiàng)目數(shù)量較少時(shí)，增加懲罰因子，以避免評(píng)分相似所致相似度過(guò)高的問(wèn)題。

推薦系統(tǒng)； 協(xié)同過(guò)濾； 相似度； 自信息量； 平均絕對(duì)偏差

0 前 言

推薦系統(tǒng)的主要功能是，根據(jù)網(wǎng)絡(luò)用戶在線消費(fèi)及瀏覽行為歷史數(shù)據(jù)進(jìn)行用戶的消費(fèi)偏好分析及感興趣商品預(yù)測(cè)，為用戶提供個(gè)性化推薦信息。 優(yōu)秀的推薦系統(tǒng)，可以使用戶在信息過(guò)載的情況下準(zhǔn)確獲取所需信息，也可以使企業(yè)精準(zhǔn)地向潛在客戶展示自身形象。個(gè)性化推薦系統(tǒng)目前已廣泛應(yīng)用于各類電子商務(wù)網(wǎng)站、社交網(wǎng)站及門戶網(wǎng)站。推薦系統(tǒng)中常用的協(xié)同過(guò)濾算法成為當(dāng)前研究的熱點(diǎn)問(wèn)題。

推薦系統(tǒng)的協(xié)同過(guò)濾算法可以分為基于近鄰 (Neighborhood-Based)的算法和基于模型 (Model-Based)的算法兩大類[1-2]?；谀Ｐ偷耐扑]算法利用了統(tǒng)計(jì)學(xué)或機(jī)器學(xué)習(xí)相關(guān)方法建立推薦模型，通過(guò)推薦模型進(jìn)行預(yù)測(cè)。常用的建模方法包括樸素貝葉斯[3]、貝葉斯網(wǎng)絡(luò)[4]、潛在因子分析[5]等。這些算法雖然在推薦系統(tǒng)中得到了一定程度的應(yīng)用，但貝葉斯模型的建立需要處理除評(píng)分?jǐn)?shù)據(jù)之外的大量語(yǔ)義信息，加重了系統(tǒng)的負(fù)擔(dān)。通過(guò)奇異值分解(SVD)矩陣降維技術(shù)可以得到用戶興趣潛因子和項(xiàng)目潛因子，但會(huì)有部分信息丟失，從而影響推薦效果。

基于近鄰的推薦算法又可細(xì)分為基于用戶[6](User-Based)的算法和基于項(xiàng)目[7](Item-Based)的算法?；谟脩舻耐扑]算法，首先利用了用戶的歷史評(píng)分?jǐn)?shù)據(jù)，計(jì)算出目標(biāo)用戶與其他用戶之間的相似度，選擇相似度高的用戶作為近鄰用戶，再將近鄰用戶感興趣項(xiàng)目推薦給目標(biāo)用戶。基于項(xiàng)目的推薦算法，則先是計(jì)算項(xiàng)目之間的相似度，然后再找出與目標(biāo)用戶感興趣的項(xiàng)目相似度較高的項(xiàng)目予以推薦。

運(yùn)用基于近鄰的推薦算法時(shí)，無(wú)須獲知用戶或項(xiàng)目屬性信息，僅通過(guò)分析歷史評(píng)分?jǐn)?shù)據(jù)即可實(shí)施推薦。該算法在實(shí)際推薦系統(tǒng)中得到了最為廣泛的應(yīng)用，但也存在數(shù)據(jù)稀疏性、冷啟動(dòng)和擴(kuò)展性等方面的問(wèn)題。

本次研究針對(duì)傳統(tǒng)的用戶相似性度量方面存在的缺陷，提出一種修正的相似性度量算法。根據(jù)每個(gè)項(xiàng)目的受用戶歡迎程度為其賦予不同的權(quán)值，對(duì)傳統(tǒng)的相似度算法予以修正，為共同評(píng)分項(xiàng)目數(shù)過(guò)少的用戶設(shè)計(jì)懲罰因子。MovieLens數(shù)據(jù)集測(cè)試結(jié)果證明，改進(jìn)后的相似性度量公式可以在一定程度上修正因數(shù)據(jù)稀疏性而導(dǎo)致的相似度計(jì)算結(jié)果偏差，從而改善User-Based協(xié)同過(guò)濾算法推薦效果。

1 User-Based協(xié)同過(guò)濾算法

分步執(zhí)行User-Based協(xié)同過(guò)濾算法：建立用戶興趣模型；根據(jù)用戶興趣模型計(jì)算出用戶之間的相似度，并選擇相似度高的用戶作為近鄰用戶；根據(jù)近鄰用戶感興趣的項(xiàng)目預(yù)測(cè)目標(biāo)用戶對(duì)這些項(xiàng)目感興趣的程度，再執(zhí)行推薦。

1.1 用戶興趣推薦模型

設(shè)系統(tǒng)中有m個(gè)用戶和n個(gè)推薦項(xiàng)目，用戶集合為U={U1,U2,…，Ui，…,Um}，項(xiàng)目集合為I={I1,I2,…，Ij，…,In}，用戶的歷史評(píng)分?jǐn)?shù)據(jù)通過(guò)用戶-項(xiàng)目評(píng)分矩陣表示(見(jiàn)表1)。表1中，Rij為用戶i對(duì)項(xiàng)目j的評(píng)分。

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

在用戶-項(xiàng)目評(píng)分矩陣中，行向量反映的是同一用戶對(duì)不同項(xiàng)目的評(píng)分?jǐn)?shù)據(jù)。User-Based推薦算法則是通過(guò)用戶共同評(píng)分項(xiàng)目的評(píng)分差異來(lái)度量用戶間的相似性。但實(shí)際推薦系統(tǒng)中，用戶評(píng)分項(xiàng)目往往非常有限，用戶-項(xiàng)目矩陣存在大量空缺值，難以準(zhǔn)確描述用戶的興趣愛(ài)好。

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

相似度計(jì)算結(jié)果決定了近鄰集合的選擇和最終的推薦結(jié)果預(yù)測(cè)，在整個(gè)推薦過(guò)程中起到了至關(guān)重要的作用。傳統(tǒng)的相似度計(jì)算方法包括余弦相似性、修正的余弦相似性、Pearson相關(guān)系數(shù)、Jaccard相似性系數(shù)等[8]。總體來(lái)說(shuō)，修正的余弦相似性和Pearson相關(guān)系數(shù)推薦的精度更高。

(1) 修正的余弦相似性。余弦相似性是將用戶在n個(gè)項(xiàng)目上的評(píng)分?jǐn)?shù)據(jù)視為一個(gè)n維向量，通過(guò)計(jì)算用戶n維空間向量的夾角余弦值來(lái)度量用戶間的相似度。但余弦相似性沒(méi)有考慮到不同用戶在評(píng)分習(xí)慣上的差異性，衡量效果不夠理想。修正的余弦相似性則通過(guò)用戶評(píng)分值減去該用戶的平均評(píng)分值所得到的偏差來(lái)改善不同用戶的評(píng)分差異性。通過(guò)式(1)計(jì)算：

(1)

(2)

與式(1)不同的是，式(2)中分母部分只計(jì)算用戶共同評(píng)分項(xiàng)目偏差和的乘積。

1.3 相似度計(jì)算方法缺陷

運(yùn)用余弦相似性方法在計(jì)算用戶相似度時(shí)，先將用戶未評(píng)分項(xiàng)目標(biāo)記為0，再將評(píng)分?jǐn)?shù)據(jù)帶入公式計(jì)算。而用戶-評(píng)分矩陣的極度稀疏是由于用戶購(gòu)買能力有限所造成的， 并非是對(duì)未評(píng)分項(xiàng)目不感興趣，用0標(biāo)記未評(píng)分項(xiàng)顯然與實(shí)際情況不符。運(yùn)用Pearson相關(guān)系數(shù)方法計(jì)算時(shí)，則只考慮用戶共同的評(píng)分項(xiàng)目，當(dāng)共同評(píng)分項(xiàng)目過(guò)少時(shí)不足以衡量用戶間的相似性。

2 基于自信息量修正的相似度計(jì)算方法

2.1 自信息量

Shannon在1948年提出并發(fā)展了信息論的觀點(diǎn)，主張用數(shù)學(xué)方法度量和研究信息，并提出自信息量的概念[9]。自信息量是對(duì)離散信源發(fā)出信號(hào)不確定性的一種度量，自信息量越大，不確定性也越大。計(jì)算公式如式(3)所示：

Inf(ai)=log2p(ai)

(3)

式中：ai的自信息量為Inf(ai)；p(ai)是取值為ai的概率。

2.2 項(xiàng)目自信息量

在推薦問(wèn)題中，項(xiàng)目自信息量反映的是該項(xiàng)目能否得到用戶認(rèn)可的不確定性，通過(guò)式(4)、(5)來(lái)計(jì)算：

(4)

Inf(Ii)=log2p(Ii)

(5)

式中：p(Ii)表示項(xiàng)目i被用戶接受的概率；Fre(Ii)表示項(xiàng)目i被用戶評(píng)分的次數(shù)；Pop(Ii)表示對(duì)項(xiàng)目i的評(píng)分高于用戶平均評(píng)分的次數(shù)。Inf(Ii) 是項(xiàng)目i的自信息量，自信息量越高表示項(xiàng)目能夠被用戶接受的不確定性越大，越符合噪聲項(xiàng)目的特征。

2.3 修正的相似度計(jì)算方法

Pearson相關(guān)系數(shù)通過(guò)計(jì)算用戶共同評(píng)分項(xiàng)目的評(píng)分差異來(lái)衡量用戶間的相似程度。所有的項(xiàng)目在衡量用戶相似度時(shí)所產(chǎn)生的影響力是均等的，忽略了噪聲數(shù)據(jù)的干擾及用戶間共同評(píng)分的項(xiàng)目數(shù)量對(duì)相似度的影響。

為提高相似度計(jì)算方法的精度，在Pearson相關(guān)系數(shù)計(jì)算公式的基礎(chǔ)上為每個(gè)項(xiàng)目增加權(quán)值，權(quán)值大小由項(xiàng)目的自信息量決定。自信息量越大的項(xiàng)目，越符合噪聲項(xiàng)目的特征，權(quán)值也應(yīng)適當(dāng)減小。自信息量越小的項(xiàng)目則越受用戶歡迎，越能代表用戶的興趣愛(ài)好，權(quán)值應(yīng)適當(dāng)增加。項(xiàng)目權(quán)值通過(guò)式(6)來(lái)計(jì)算：

(6)

式中：wi是項(xiàng)目i的權(quán)值；Infmax和Infmin分別為所有項(xiàng)目中自信息量最大值和最小值。式(7)為本次研究所提出的改進(jìn)后的相似度計(jì)算方法。

(7)

(8)

式中：| Iui∩Iua|為用戶i和用戶a的共同評(píng)分項(xiàng)目數(shù)；T為事先設(shè)定好的閾值。

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

利用上述改進(jìn)方法計(jì)算用戶間的相似度，根據(jù)用戶相似度確定目標(biāo)用戶的最近鄰居集，通過(guò)近鄰用戶對(duì)目標(biāo)項(xiàng)目的評(píng)分值進(jìn)行預(yù)測(cè)。計(jì)算方法如式(9)所示：

(9)

式中：Pui為用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分；NBu為用戶u的近鄰集。

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

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

采用GroupLens研究小組提供的MovieLens數(shù)據(jù)集ml-100k，對(duì)改進(jìn)后的相似度計(jì)算方法進(jìn)行評(píng)估測(cè)試。該數(shù)據(jù)集包含7組數(shù)據(jù)，每組數(shù)據(jù)分為訓(xùn)練集和測(cè)試集。其中，訓(xùn)練集中包括943名用戶對(duì)1 682部電影的100 000項(xiàng)評(píng)分?jǐn)?shù)據(jù)，評(píng)分值的取值范圍為1～5，每位用戶至少有20個(gè)評(píng)分項(xiàng)。通過(guò)訓(xùn)練集數(shù)據(jù)來(lái)預(yù)測(cè)用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分值，再對(duì)預(yù)測(cè)結(jié)果與測(cè)試集數(shù)據(jù)進(jìn)行對(duì)比分析。

4.2 評(píng)估標(biāo)準(zhǔn)

以平均絕對(duì)偏差MAE作為評(píng)估算法推薦質(zhì)量評(píng)價(jià)指標(biāo)，其計(jì)算方法如下：

(10)

(11)

式中：pij為通過(guò)訓(xùn)練集產(chǎn)生的預(yù)測(cè)評(píng)分；qij為測(cè)試集提供的實(shí)際評(píng)分；Ni為測(cè)試集提供的用戶i的評(píng)分項(xiàng)目數(shù)量；MAEi為用戶i對(duì)Ni個(gè)項(xiàng)目預(yù)測(cè)評(píng)分的平均絕對(duì)偏差；M為全體用戶總數(shù)；MAE為全體用戶的平均絕對(duì)偏差。MAE的值越小，算法預(yù)測(cè)的結(jié)果與實(shí)際評(píng)分值越接近，算法推薦的準(zhǔn)確性也越高。

4.3 實(shí)驗(yàn)結(jié)果對(duì)比

本次研究所提出的相似性度量方法，是在Pearson相關(guān)系數(shù)的基礎(chǔ)進(jìn)行了改進(jìn)。為驗(yàn)證改進(jìn)策略的有效性，并確定參數(shù)T的最佳取值，設(shè)計(jì)實(shí)驗(yàn)進(jìn)行對(duì)比。分別將基于Pearson相關(guān)系數(shù) (PCC)、自信息量修正相似性 (IPCC)和加懲罰因子的自信息量修正相似性 (WIPCC)這3種度量方法與User-Based推薦算法相結(jié)合，比較改進(jìn)策略對(duì)推薦結(jié)果產(chǎn)生的影響。

與傳統(tǒng)的Pearson相關(guān)系數(shù)相比，自信息量修正的相似性度量方法在推薦質(zhì)量上有較大的改進(jìn)。圖1所示為不同T值下的MAE結(jié)果對(duì)比。加懲罰因子的自信息量修正相似性在T值取3～9的情況下，可將MAE值改進(jìn)到0.086～0.012。當(dāng)T為4時(shí)，改進(jìn)效果最佳。在后面的對(duì)比實(shí)驗(yàn)中，T全部取4。

User-Based協(xié)同過(guò)濾算法的推薦質(zhì)量，在很大程度上還受近鄰個(gè)數(shù)的影響，通常情況下近鄰個(gè)數(shù)越多，推薦的準(zhǔn)確率越高。為驗(yàn)證本算法在不同近鄰個(gè)數(shù)下實(shí)施推薦的有效性，將實(shí)驗(yàn)中近鄰個(gè)數(shù)從10依次遞增到100，比較其與傳統(tǒng)的Pearson相關(guān)系數(shù)(PCC)和修正的余弦相似性(AC)推薦結(jié)果的MAE值。圖2 所示為3種算法在不同近鄰個(gè)數(shù)下的MAE結(jié)果對(duì)比。

圖1 不同T值下的MAE結(jié)果對(duì)比

圖2 3種算法在不同近鄰個(gè)數(shù)下的MAE結(jié)果對(duì)比

由圖(2)可知，修正相似度計(jì)算方法優(yōu)于傳統(tǒng)的Pearson相關(guān)系數(shù)和修正的余弦相似性，在近鄰個(gè)數(shù)較少時(shí)推薦質(zhì)量尤為明顯，具有更高的穩(wěn)定性。

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

傳統(tǒng)的Pearson相關(guān)系數(shù)僅僅通過(guò)用戶的共同評(píng)分項(xiàng)目計(jì)算相似度，會(huì)因?yàn)閿?shù)據(jù)的極端稀疏造成共同評(píng)分項(xiàng)目數(shù)過(guò)少，且又受到噪聲項(xiàng)目的影響，導(dǎo)致計(jì)算結(jié)果與實(shí)際情況出現(xiàn)較大偏差。

修正的余弦相似性雖然整體推薦質(zhì)量?jī)?yōu)于Pearson相關(guān)系數(shù)，但其在近鄰數(shù)量低于30時(shí)表現(xiàn)出的性能并不理想。從計(jì)算公式中，不難發(fā)現(xiàn)其分母項(xiàng)將用戶各自的評(píng)分項(xiàng)都納入計(jì)算，分子項(xiàng)中卻只有共同評(píng)分項(xiàng)。因此，余弦相似性的整體計(jì)算結(jié)果偏低，用戶近鄰數(shù)量少，推薦效果不穩(wěn)定。

本次提出的修正相似度計(jì)算方法，以Pearson相關(guān)系數(shù)為基礎(chǔ)，不存在余弦相似性計(jì)算結(jié)果偏低的缺陷；同時(shí)針對(duì)Pearson相關(guān)系數(shù)存在的問(wèn)題進(jìn)行修正，為用戶共同評(píng)分項(xiàng)目數(shù)設(shè)置閾值，并對(duì)所有項(xiàng)目根據(jù)其自信息量確定權(quán)值，削弱噪聲項(xiàng)目的不利影響，有效提高了協(xié)同過(guò)濾算法的推薦質(zhì)量。

5 結(jié) 語(yǔ)

針對(duì)User-Based協(xié)同過(guò)濾推薦算法，提出了一種新的衡量用戶間相似性的度量方法。該方法以傳統(tǒng)的Pearson相關(guān)系數(shù)為基礎(chǔ)，在計(jì)算相似度前首先計(jì)算每個(gè)項(xiàng)目的自信息量。自信息量越大表示該

項(xiàng)目被用戶接受的不確定性越大，那么其確認(rèn)為噪聲項(xiàng)目的可能性也越大。根據(jù)自信息量的大小為項(xiàng)目分配不同的權(quán)值，對(duì)于用戶受歡迎的項(xiàng)目，增加其在相似度計(jì)算時(shí)的權(quán)重，對(duì)于噪聲項(xiàng)目則削弱其在相似度計(jì)算時(shí)產(chǎn)生的不利影響。在用戶共同評(píng)分項(xiàng)目極少的情況下，在相似度值計(jì)算過(guò)程中加入了懲罰因子，以避免極少數(shù)項(xiàng)目評(píng)分相似而使相似度過(guò)高的問(wèn)題。利用MovieLens數(shù)據(jù)集對(duì)本次改進(jìn)算法和傳統(tǒng)的相似性度量方法進(jìn)行測(cè)試，測(cè)試結(jié)果證明改進(jìn)算法在一定程度上克服了數(shù)據(jù)稀疏性和噪聲數(shù)據(jù)的影響，取得了較好的推薦效果。

[1] SHI Y,LARSON M,HANJALIC A.Exploiting User Similarity Based on Rated-Item Pools for Improved User-Based Collaborative Filtering[C]∥Proc of the 3rd Acm Conf on Recommender Systems.2009:125-132.

[2] LU J,WU D S,MAO M S,et al.Recommender System Application Developments: a Survey [J].Knowledge-Based Systems ,2015,74:12-32.

[3] 李大學(xué),謝名亮,趙學(xué)斌.基于樸素貝葉斯方法的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)應(yīng)用，2010,30(6):1523-1526.

[4] YEUNG C K F,YANG Y Y,NDZI D.A Proactive Personalized Mobile Recommendation System Using Analytic Hierarchy Process and Bayesian Network [J].Journal of Internet Services and Applications,2012,3(2): 195-214.

[5] PATEREK A.Improving Regularized Singular Value Decomposition for Collaborative Filtering[C]∥Proceeding of KDD Cup Workshop at 13th ACM Int.Conf.on Knowledge Discovery and Data Mining.2007: 39-42.

[6] HERLOKCER J L,KONSTAN J A,BORHCESR A,et al.An Algorithmic Framework for Performing Collaborative Filtering[C]∥Proceedings of SIGIR99 :22nd International Conference on Research and Development in Information Retrieval.1999:230-237.

[7] SARWAR B,KARYPIS G,KONSTAN J,et al.Item-Based Collaborative Filtering Recommendation Algorithms[C]∥Proceedings of the 10th International World Wide Web Conference.2001:285-295.

[8] BIDYUT K P，RAIMO L，VILLE O，et al.A New Similarity Measure Using Bhattacharyya Coefficient for Collaborative Filtering in Sparse Data[J].Knowledge Based Systems,2015,82: 163-177.

[9] 廖芹，郝志峰，陳志宏.數(shù)據(jù)挖掘與數(shù)學(xué)建模[M].北京：國(guó)防工業(yè)出版社，2010:152-154.

[10] BREESE J S,HECKERMAN D,KADIE C.Empirical Analysis of Predictive Algorithms for Collaborative Filtering[C]∥ Proc 14th Conf on Uncertainty in Artificial Intelligence Conference.1998: 43-52.

A User-Based Collaborative Filtering Recommendation Algorithm Based on Modified Similarity

WANGZhutingXIAZhuqingZHOUYanling

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

An improved method of similarity calculation is proposed in this paper because the traditional user-based collaborative filtering algorithm are not suitable in sparse data. First of all, we utilize the user′s rating data to calculate self information quantity of each item, which can be used to determine the weights of the item, and improved the traditional similarity measure. Then, we add a penalty factor to avoid the high similarity caused by the fewer similar rating behavior when the number of co-rated items is few.

recommendation system; collaborative filtering; similarity; self information quantity; mean absolute error

2016-03-16

安徽省教育廳自然科學(xué)資助項(xiàng)目“基于上下文相關(guān)性的網(wǎng)絡(luò)編碼可靠多播技術(shù)的研究”(KJ2016A609)；合肥學(xué)院科研發(fā)展基金資助項(xiàng)目“面向電子商務(wù)的個(gè)性化推薦系統(tǒng)研究”(14KY11ZR)；合肥學(xué)院重點(diǎn)建設(shè)學(xué)科資助項(xiàng)目(2014XK08)；合肥學(xué)院學(xué)科帶頭人培養(yǎng)對(duì)象資助項(xiàng)目(2014DTR08)

王竹婷(1984 — )，女，碩士，助理實(shí)驗(yàn)師，研究方向?yàn)槿斯ぶ悄芘c數(shù)據(jù)挖掘。

TP301

A

1673-1980(2016)06-0075-05