王 威， 鄭 駿

（華東師范大學計算中心，上海 200062）

基于用戶相似度的協(xié)同過濾算法改進

王 威， 鄭 駿

（華東師范大學計算中心，上海 200062）

協(xié)同過濾技術作為目前最常見的個性化推薦技術之一，被廣泛認可和應用.作為基于內(nèi)容的算法執(zhí)行方式，協(xié)同過濾在準確性上具有相當?shù)膬?yōu)勢.該算法的核心問題是相似度的計算.本論文介紹了傳統(tǒng)協(xié)同過濾算法，并對原有的相似度公式進行了優(yōu)化，使得相似度計算更具有準確性.實驗表明，文中提出的優(yōu)化方法在推薦精度上有顯著提高，降低了平均絕對誤差（Mean Absolute Error，MAE）.

推薦技術；相似度；協(xié)同過濾；MAE

0 引 言

隨著人們生活越來越信息化，當面對互聯(lián)網(wǎng)上浩瀚的信息海洋，人們會顯得有些手足無措.如今，很多比較著名的商業(yè)組織，如Netflix、Group Lens、Amazon等，都不同程度地使用了各種各樣的推薦系統(tǒng)［1-2］，以幫助人們更好地處理日益龐大的互聯(lián)網(wǎng)信息.推薦系統(tǒng)通過分析用戶的行為習慣，將一些有效信息推薦給用戶，方便用戶能夠更快地獲取需要的信息，在節(jié)省了篩選信息時間的同時，也提高了信息的有效使用率.

在現(xiàn)今的推薦算法中，協(xié)同過濾（Collaborative Filtering，CF）［3］被廣泛認可和采用，它以其出色的速度和穩(wěn)健性，在信息過濾和信息系統(tǒng)中炙手可熱.協(xié)同過濾算法是通過對User-Item評分矩陣的分析，向用戶推薦用戶感興趣的商品.實現(xiàn)協(xié)同過濾的推薦算法，需要進行3個步驟：第一步收集數(shù)據(jù)；第二步找到相似用戶和物品；第三步進行推薦.就目前而言，協(xié)同過濾算法的主流方法有兩種：基于用戶的協(xié)同過濾算法（User-Based CF）［4］和基于物品的協(xié)同過濾算法（Item-Based CF）［5-6］.本文中研究討論的方法是User-Based CF，它的基本思想是根據(jù)當前用戶對物品的愛好，找到具有相似愛好的其他用戶，然后將這些用戶喜歡的物品推薦給當前用戶.傳統(tǒng)協(xié)同過濾算法雖然被廣泛使用，但是還是存在問題：鄰居用戶是基于用戶間的相似度得出的，但是傳統(tǒng)的相似度計算由于考慮的因素不夠全面，導致了精度不高.

本文針對這個問題，提出了新的數(shù)據(jù)加權度量：基于用戶相似度的數(shù)據(jù)權重.將這種權重引入到傳統(tǒng)User-Based CF的相似度計算中，可以提高用戶相似度計算的精確度.

1 傳統(tǒng)User-Based CF

傳統(tǒng)User-Based CF是一種以用戶為主體的算法，它比較強調(diào)的是社會性的屬性，也就是說這類算法更加強調(diào)把和你有相似愛好的其他用戶的物品推薦給你.與之對應的是Item-Based CF，這種方法更加強調(diào)把和你喜歡物品相似的物品推薦給你.User-Based CF是根據(jù)用戶對物品的喜愛程度，在眾多用戶中找到小部分和當前用戶有相似愛好的其他用戶，將這些用戶組成鄰居集合，然后將這些鄰居喜歡的其他物品推薦給當前用戶.

User-Based CF一般分為3個步驟：表示；鄰居用戶形成；推薦生成.

1.1 表示

在傳統(tǒng)User-Based CF中，輸入數(shù)據(jù)通常是采用用戶-項目評分矩陣R（m，n）［7］.R（m，n）是一個m×n階矩陣，其中m表示所有參與評價的用戶的個數(shù)，n表示所有被評價項目的個數(shù).對于任意的i＜m和j＜n，Rij表示用戶i對項目j的評分.矩陣中的評價值可以是由二進制的0和1來表示，其中0表示用戶不喜歡該項目，1表示用戶喜歡該項目；也可以用5分制、10分制或其他度量方式來表示，評分越高代表用戶喜歡程度越高.本論文中采用的數(shù)據(jù)集是MovieLens［8］數(shù)據(jù)集，評分方式采用的是5分制.表1是用戶對資源的評分矩陣.

表1 用戶-項目評分矩陣Tab.1 User-item rating matrix

1.2 鄰居用戶形成

在User-Based CF中，鄰居用戶形成是最關鍵的步驟.我們可以根據(jù)用戶-項目評分矩陣R（m，n）計算用戶之間的相似度，然后產(chǎn)生一個按照相似度大小排列的鄰居集合，這個過程的核心是相似度的計算［9-10］.一般來講，相似度的計算主要有余弦相似性（Cosine Similar-ity）［11］和皮爾遜相關系數(shù)（Pearson Correlation Coefficient）［12-13］.

（1）余弦相似性為

對于User-Based CF而言，相似度

其中，Sim（u1，u2）表示用戶u1和用戶u2之間的相似度，Ru1i和Ru2i分別表示用戶u1、用戶u2對項目i的評分，Iu1u2表示用戶u1和用戶u2共同評分的項目集合，即Iu1u2＝｛i∈I|Ru1i≠0，Ru2i≠0｝（其中I表示所有項目的集合），向量u1、向量u2表示用戶u1和用戶u2在Iu1u2上的評分.

（2）皮爾遜相關系數(shù)為

對于User-Based CF而言，相似度

通過相似度公式可以得到用戶間的相似度，根據(jù)相似度的大小從大到小排序，對于用戶u1可以產(chǎn)生一個鄰居集合N＝｛N1，N2，…，Nk｝，即N中的第一個用戶N1與用戶u1的相似度對于用戶u1來說是最大的.

1.3 推薦生成

根據(jù)第1.2節(jié)中產(chǎn)生的鄰居集合N＝｛N1，N2，…，Nk｝，可以計算出用戶對所有項目的喜愛程度的預測值［9］

其中，Pu1i表示用戶u1對未評分項目i的預測評分，表示用戶u1對所有評分過的項目的平均評分，表示用戶u2對所有評分過的項目的平均評分.

2 改進的相似度度量方法

2.1 改進分析

在傳統(tǒng)User-Based CF中，公式（2）和公式（4）未考慮到用戶對共同評價項目的評分所占的比重帶來的影響.假設兩個用戶共同參與評價的項目有很多，這不一定能說明兩個用戶的愛好是一樣的.因為如果這些被共同評價過的項目的評分都不高，那么只能說明這兩個用戶都不喜歡這些項目，若這樣推薦給用戶的項目就會有偏差.假設兩個用戶共同評分的項目不多，但是兩個用戶對共同評分項目的評分都很高，這些項目很有可能是用戶所喜愛的，那么這兩個用戶的愛好有很大概率是很相似的.因此我們在相似度計算過程中需要考慮用戶對共同評分項目的評分所占的比重，這樣才有助于提高相似度計算的精度.

本論文對相似度的公式進行改進，提出加權余弦相似性方法和加權皮爾遜相關系數(shù)方法，具體描述如下.

步驟1 從矩陣R（m，n）中計算用戶u1和用戶u2對共同評價項目的評分總和：

步驟2 從矩陣R（m，n）中計算用戶u1和用戶u2對各自評分過的所有項目的評分總和：（Iu1表示用戶u1所有評過分的項目集）；（Iu2表示用戶u2所有評過分的項目集）.

步驟3 對公式（2）和公式（4）中用戶相似度進行改進，改進后的相似度計算公式為

則經(jīng)過加權后計算預測評分公式為

2.2 時間復雜度分析

3 實驗結果及分析

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

本實驗所采用的數(shù)據(jù)集是MovieLens_100k數(shù)據(jù)集［14］.MovieLens_100k數(shù)據(jù)集的評分制度是5分制，它包含了943個用戶以及1682部電影，其中每個用戶至少對20部以上的電影進行了評分.數(shù)據(jù)集的內(nèi)容是用Table表示，共有4列：用戶ID；物品ID；評分；時間戳.在該數(shù)據(jù)集中主要分成兩部分：Base數(shù)據(jù)集和Test數(shù)據(jù)集.Base數(shù)據(jù)集是訓練樣本，通過對Base數(shù)據(jù)集進行訓練，可以計算出用戶對未評分項目的預測評分；而Test數(shù)據(jù)集則是用戶對未評分項目的實際評分，通過對比預測評分和實際評分，可以直觀地了解推薦精度.

3.2 評分標準MAE

在推薦算法實驗中，通常通過計算平均絕對誤差［15-16］（Mean Absolute Error，MAE）來表示推薦精度.如第3.1節(jié)，實驗通過對訓練樣本Base數(shù)據(jù)集進行訓練，計算用戶對未評分項目i的預測評分pi，再根據(jù)Test數(shù)據(jù)集中對應的用戶對項目i的實際評分Ri；通過計算預測評分和用戶的實際評分之間的偏差的絕對值，以此來表示對未評分項目i的推薦精度，即越小，對未評分項目i的推薦精度越高，相反，越高，則說明對未評分項目i的推薦精度越低，偏差越大.假設集合P＝｛p1，p2，p3，…，pn｝代表用戶對未評分項目的預測評分集合，集合R＝｛R1，R2，R3，…，Rn｝代表用戶對未評分項目的實際評分集合，則定義MAE為

根據(jù)公式（9）可以發(fā)現(xiàn)，MAE值越小即偏差越小，代表預測評分越準確，推薦精度越高.

3.3 實驗結果及分析

為了驗證本文提出的加權相似性度量的有效性，設計將其與傳統(tǒng)User-Based CF進行比較.

3.3.1 驗證相似度度量改進的有效性

首先，我們采用Movie Lens數(shù)據(jù)集中的訓練數(shù)據(jù)集u1.base與測試集u1.test進行對比實驗.通過對u1.base進行訓練，從而預測用戶對尚未評價項目的評分，將預測結果與u1.test中數(shù)據(jù)進行比較，最終得出MAE實驗結果，如圖1、圖2所示.

圖1 余弦相似度改進對比圖Fig.1 The improvement of cosine similarity

在圖1、圖2中藍色曲線是原算法的實驗結果，紅色曲線是采用改進后的相似度公式產(chǎn)生的實驗結果，曲線上的點的橫坐標代表鄰居數(shù)k，縱坐標代表在對應鄰居數(shù)k的情況下所得到的MAE.如圖2中藍色曲線的第一個點表示當鄰居數(shù)k＝5時，MAE接近0.82，即預測評分的平均絕對誤差接近0.82；而在圖2中可以發(fā)現(xiàn)在采用改進后的相似度公式的情況下（即圖2中紅色曲線表示的那部分），當k＝5時，MAE約為0.78，很明顯要小于采用原公式的平均誤差.

圖2 皮爾遜相似度改進對比圖Fig.2 The improvement of Pearson similarity

在本文第2.1節(jié)中提到過，通過對原相似度公式進行加權計算，將用戶對共同評價項目的評分所占的比重這個重要因素考慮在內(nèi)，可以有助于提高精確度；而且通過對圖1、圖2的分析，我們發(fā)現(xiàn)本文中對相似度度量方法的改進是有明顯效果的，在不同鄰居數(shù)目的情況下，MAE都要小于傳統(tǒng)算法，可見公式（6）和公式（7）能夠有效地提高推薦精度，降低預測評分偏差.

3.3.2 鄰居數(shù)k的選擇

本次實驗采用的數(shù)據(jù)集是MovieLens數(shù)據(jù)集中的u1，u2，u3，u4，u5，u6，u7，采用改進后的相似度度量公式（7），實驗結果如圖3所示.

圖3 不同鄰居數(shù)k的實驗結果Fig.3 The experiment results caused by different number of neighbors

當最近鄰居數(shù)k很小時，如果鄰居集合N中有一些和用戶愛好存在差別，那么預測評分的誤差會偏大；但當最近鄰居數(shù)k很大時，會帶入很多與用戶愛好有較大偏差的其他用戶，從而會導致推薦精度降低，使MAE偏大，所以函數(shù)MAE-鄰居數(shù)k應該存在最小值［8］.由圖3中可知，針對改進后的算法，當最近鄰居數(shù)k屬于（40，60）時，MAE最小，推薦精度最高.

4 總 結

在如今信息化高速發(fā)展的時代，推薦系統(tǒng)幫助人們處理了很多干擾信息，將有效信息及時推薦給用戶.推薦系統(tǒng)作為一個仍在不斷發(fā)展和完善的技術，任何一個細小的問題都值得研究.推薦系統(tǒng)中最常用的算法就是協(xié)同過濾算法，但很多現(xiàn)有的改進算法沒有對相似性度量進行分析.考慮到用戶和項目之間的聯(lián)系，本文通過對相似性度量的加權處理，有效降低了預測偏差，提高了推薦精度.

每個用戶都有自己的愛好，每個項目也有各自的屬性，如何將用戶的愛好和項目的屬性聯(lián)系起來是今后研究的課題.另外，對于協(xié)同過濾算法的研究還有其他的思路，比如說結合User-based和Item-based的協(xié)同過濾算法、聚類算法等；如何結合各種思路的優(yōu)點也是今后研究的課題之一.

［1］劉建國，周濤，汪秉紅.個性化推薦系統(tǒng)的研究發(fā)展［J］.自然科學進展，2009，19（1）：1-15.

［2］孟祥武，紀威宇，張玉潔.大數(shù)據(jù)環(huán)境下的推薦系統(tǒng)［J］.北京郵電大學學報，2015，38（2）：1-15.

［3］碩良勛，柴變芳，張新東.基于改進最近鄰的協(xié)同過濾推薦算法［J］.計算機工程與應用，2015，51（5）：137-141.

［4］ZHAO Z D，SHANG M S.User-based collaborative-filtering recommendation algorithms on Hadoop［C］／／Proceedings of the 2010 3rd International Conference on Knowledge Discovery and Data Mining.IEEE，2010：478-481.

［5］鄧愛林，朱揚勇，施伯樂.基于項目評分預測的協(xié)同過濾推薦算法［J］.軟件學報，2003，114（9）：1621-1628.

［6］彭玉，程小平，徐藝萍.一種改進的Item-based協(xié)同過濾推薦算法［J］.西南大學學報（自然科學版），2007，29（5）：146-149.

［7］劉芳先，宋順林.改進的協(xié)同過濾推薦算法［J］.計算機工程與應用，2011，47（8）：72-75.

［8］汪靜，印鑒，鄭利榮，等.基于共同評分和相似性權重的協(xié)同過濾推薦算法［J］.計算機科學，2010，37（2）：99-104.

［9］ADOMAVICIUS G，TUZHILIN A.Toward the next generation of recommender systems：A survey of the stateof-the-art and possible extensions［J］.IEEE Transactions on Knowledge and Data Engineering，2015，17（6）：734-749.

［10］孟慶慶，張勝男，盧楚雍.基于用戶特征和商品特征的組合協(xié)同過濾算法［J］.軟件導刊，2015，14（3）：41-43.

［11］孫輝，馬躍，楊海波，等.一種相似度改進的用戶聚類協(xié)同過濾推薦算法［J］.小型微型計算機系統(tǒng)，2014，35（9）：1967-1970.

［12］傅鶴崗，彭晉.基于模范用戶的改進協(xié)同過濾算法［J］.計算機工程，2011，37（3）：70-74.

［13］王立印，張輝，陳勇.一種基于Dice-Euclidean相似度計算的協(xié)同過濾算法［J］.計算機應用研究，2015，32（10）：2891-2895.

［14］朱毅萌，謝穎華.分步篩選鄰居的協(xié)同過濾改進算法［J］.計算機系統(tǒng)應用，2015，24（6）：132-137.

［15］張丙奇.基于領域知識的個性化推薦算法研究［J］.計算機工程，2005，31（21）：7-9.

［16］蔡淑琴，袁乾，周鵬，等.基于信息傳播理論的微博協(xié)同過濾推薦模型［J］.系統(tǒng)工程理論與實踐，2015，35（5）：1267-1275.

（責任編輯：李 藝）

Improved collaborative filtering algorithm based on user-similarity

WANG Wei， ZHENG Jun
（Computer Center，East China Normal University，Shanghai 200062，China）

Collaborative filtering is widely accepted and applied currently as one of the most popular personalized recommendation methods.It is an implementation method based on content that has considerable advantages in accuracy.The core issue of collaborative filtering is how to work out the calculation of similarity.In this paper，we introduce the traditional collaborative filtering algorithm and make similarity calculation more accurately by optimizing the traditional formula of similarity.Experimental results show that the optimized algorithm can improve the accuracy of the recommendation and reduce the MAE（Mean Absolute Error，MAE）efficiently.

recommendation methods；similarity；collaborative filtering；MAE

TP391

A

10.3969／j.issn.1000-5641.2016.03.007

1000-5641（2016）03-0060-07

2015-05

國家高技術研究發(fā)展計劃（2013AA01A211）

王 威，男，碩士研究生，主要研究方向為Web開發(fā)及應用.E-mail：610151625@qq.com.通信作者：鄭 駿，男，教授，主要研究方向為Web開發(fā)及應用.E-mail：jzheng@cc.ecnu.edu.cn.