王竹婷 夏竹青 周艷玲

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

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

王竹婷 夏竹青 周艷玲

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

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

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

0 前 言

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

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

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

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

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

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

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

1.1 用戶興趣推薦模型

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

表1 用戶-項目評分矩陣

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

1.2 相似度計算方法

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

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

(1)

(2)

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

1.3 相似度計算方法缺陷

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

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

2.1 自信息量

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

Inf(ai)=log2p(ai)

(3)

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

2.2 項目自信息量

在推薦問題中，項目自信息量反映的是該項目能否得到用戶認可的不確定性，通過式(4)、(5)來計算：

(4)

Inf(Ii)=log2p(Ii)

(5)

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

2.3 修正的相似度計算方法

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

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

(6)

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

(7)

(8)

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

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

利用上述改進方法計算用戶間的相似度，根據(jù)用戶相似度確定目標用戶的最近鄰居集，通過近鄰用戶對目標項目的評分值進行預(yù)測。計算方法如式(9)所示：

(9)

式中：Pui為用戶u對項目i的預(yù)測評分；NBu為用戶u的近鄰集。

4 實驗結(jié)果及分析

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

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

4.2 評估標準

以平均絕對偏差MAE作為評估算法推薦質(zhì)量評價指標，其計算方法如下：

(10)

(11)

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

4.3 實驗結(jié)果對比

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

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

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

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

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

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

4.4 實驗結(jié)果分析

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

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

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

5 結(jié) 語

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

項目被用戶接受的不確定性越大，那么其確認為噪聲項目的可能性也越大。根據(jù)自信息量的大小為項目分配不同的權(quán)值，對于用戶受歡迎的項目，增加其在相似度計算時的權(quán)重，對于噪聲項目則削弱其在相似度計算時產(chǎn)生的不利影響。在用戶共同評分項目極少的情況下，在相似度值計算過程中加入了懲罰因子，以避免極少數(shù)項目評分相似而使相似度過高的問題。利用MovieLens數(shù)據(jù)集對本次改進算法和傳統(tǒng)的相似性度量方法進行測試，測試結(jié)果證明改進算法在一定程度上克服了數(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é)同過濾推薦算法[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].北京：國防工業(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é)資助項目“基于上下文相關(guān)性的網(wǎng)絡(luò)編碼可靠多播技術(shù)的研究”(KJ2016A609)；合肥學(xué)院科研發(fā)展基金資助項目“面向電子商務(wù)的個性化推薦系統(tǒng)研究”(14KY11ZR)；合肥學(xué)院重點建設(shè)學(xué)科資助項目(2014XK08)；合肥學(xué)院學(xué)科帶頭人培養(yǎng)對象資助項目(2014DTR08)

王竹婷(1984 — )，女，碩士，助理實驗師，研究方向為人工智能與數(shù)據(jù)挖掘。

TP301

A

1673-1980(2016)06-0075-05