蘇林宇，陳學(xué)斌

?

基于用戶的協(xié)同過濾算法的改進研究

蘇林宇1,2，陳學(xué)斌1,2

(1. 華北理工大學(xué)理學(xué)院，河北唐山 06300；2. 河北省數(shù)據(jù)科學(xué)與應(yīng)用重點實驗室，河北唐山 06300)

本文針對傳統(tǒng)的基于用戶協(xié)同過濾算法的稀疏性大，推薦效率，精度低等問題，提出了一種改進的算法。在計算“用戶-評分”矩陣時，通過建立“項目-用戶”倒查表，忽略無相同評分項的用戶間相似性的計算，降低了用戶評分矩陣的稀疏性，以及傳統(tǒng)方法中對所有用戶兩兩計算相似度的工作量。在計算用戶相似度時，考慮到項目熱門程度對推薦結(jié)果的影響，通過“懲罰”用戶共同興趣列表中的熱門項目，避免了傳統(tǒng)算法中由于賦予所有項目相同權(quán)重給個性化推薦結(jié)果帶來的負面影響。最后，通過和數(shù)據(jù)集檢驗該算法，并且用十折交叉方法驗證結(jié)果。結(jié)果表明，改進后的算法節(jié)約了運行時間，提高了推薦算法的效率和個性化。

基于用戶的協(xié)同過濾；個性化推薦；相似度計算；十折交叉驗證；項目-用戶倒查表

1 引言

個性化推薦是一種通過研究用戶的興趣或購買行為，主動向用戶推薦感興趣的信息或商品的算法。它的提出緩解了日益增長的互聯(lián)網(wǎng)信息量與用戶的個性化需求間的矛盾。協(xié)同過濾是目前應(yīng)用最廣泛，也是最成功的個性化推薦算法。它的基本思想是依據(jù)用戶的興趣相似性進行建模，根據(jù)該模型，把與當前用戶相似的其他用戶行為推薦給該用戶。該技術(shù)的優(yōu)點是不需關(guān)注行為的具體表現(xiàn)形式，只需要關(guān)注推薦行為本身。然而，協(xié)同過濾算法在實際應(yīng)用中也存在著稀疏性、效率、精確性、冷啟動和可擴展性等問題[1]。

在大型的電子商務(wù)系統(tǒng)中，如淘寶、亞馬遜，它們有成千上萬的商品，但其中被用戶評價過的只占不到1%。這導(dǎo)致了“用戶-評分”矩陣的過度稀疏。此外，傳統(tǒng)的協(xié)同過濾算法在計算用戶間相似度時，需逐個計算兩個用戶對同一個項目的評分，這使得算法的時間復(fù)雜度達到了，當用戶數(shù)量較多時，將耗費大量的時間，且難以找到最近鄰居，進而影響到推薦的效率與精確性。

最后，傳統(tǒng)的基于用戶的協(xié)同過濾算法在計算用戶相似度時，賦予所有項目相同權(quán)值，并沒有考慮項目的熱門程度對推薦結(jié)果的影響。John S. Breese曾提出[2]，即使兩個用戶購買或關(guān)注過同一熱門項目，也不能因此認定他們有相似的興趣。所以，將熱門項目當成普通項目處理將會對個性化推薦的結(jié)果造成負面影響。

2 改進的用戶協(xié)同過濾算法

2.1 建立“項目-用戶”倒查表解決矩陣稀疏性問題

如表1，“—”表示用戶對該商品無評價，這種現(xiàn)象在電子商務(wù)系統(tǒng)中普遍存在。

表1 “用戶-項目”矩陣的稀疏性

Tab.1 Data sparseness of user-rating-data matrix

基于此，本文建立“項目-用戶”表，即每個項目對應(yīng)該項目評分過的用戶列表，并且忽略用戶相似度為0（即兩個用戶之間沒有對任何一個項目同時評分）的情況。例如用戶A和用戶B同時評論過s個項目，就有，從而可以倒查每個項目對應(yīng)的用戶列表，進而得到所有用戶間不為0的。以表1的數(shù)據(jù)為例，建立的“項目-用戶”表如下：

表2 “項目-用戶”倒查表

Tab.2 Items-users inversion table

2.2 用戶相似度公式改進

在傳統(tǒng)的基于用戶的協(xié)同過濾算法中，計算用戶相似度時，賦予所有項目相同權(quán)值。并沒有考慮項目的熱門程度不同對推薦結(jié)果的影響。例如，在采用余弦相似度公式來計算用戶A和B的興趣相似度，C(A)表示用戶A曾經(jīng)評分過的項目集合，|C(A)|表示集合C(A)中元素個數(shù)，C(B)表示用戶B曾經(jīng)評分過的項目集合，|C(B)|表示集合C(B)中元素個數(shù)，計算公式[3]如(1)所示：

John S. Breese曾提出[1]，即使兩個用戶購買過同一熱門項目，也不能因此認為他們有相似的興趣。因此，賦予熱門項目相同權(quán)重將會對個性化推薦的結(jié)果造成負面影響。例如，兩個用戶都買過自行車，但不能說明他們都喜歡騎自行車，因為自行車作為基本的交通工具，每個人都會有需求，但如果兩個人都買過昂貴的自行車配件，則可以認為他們興趣相似。C(i)表示所有評分項目中包含項目i的集合，|C(i)|表示集合C(i)中元素個數(shù)，利用John S. Breese提出的思想，對用戶相似度的公式進行改進：

（2）

公式（2）中對項目個數(shù)|C(i)|求對數(shù)后取倒數(shù)，有效地降低了熱門項目對用戶相似度計算的影響，“懲罰”了用戶、共同興趣列表中，熱門項目對他們相似度的影響，提高了推薦結(jié)果的精度。

2.3 改進的用戶協(xié)同過濾算法流程

（1）將數(shù)據(jù)集平均分為S份，選出其中的一份作為測試集，把剩下的S-1份作為訓(xùn)練集。為了保證評測指標不是過擬合的結(jié)果，采用十折交叉法進行交叉對結(jié)果進行驗證。需要進行S次試驗，每次使用不同的測試集，然后將S次試驗測出的評測指標均值作為最終的評測指標[4]。

（2）進行基于用戶的協(xié)同過濾算法[5]：找到和用戶A有相似興趣的其他用戶，然后把其他用戶喜好的、而用戶沒有的項目推薦給用戶：

1：找到和目標用戶興趣相似的用戶集合。

2：給用戶推薦和他興趣最相似的個用戶評價過的項目。以下公式計算用戶對項目的感興趣程度:

3 實驗驗證結(jié)果及分析

3.1 Movielens100K和HetRc2011-movielens-2k實驗數(shù)據(jù)集

本文采用Movielens100K數(shù)據(jù)集，包括了700個用戶對9000部電影的100,000條評分記錄，評分范圍是1-5，數(shù)值越大表示評價越高。其中u.data表格如表3所示：

表3 u.data表格式

Tab.3 Format of the u.data table

本文主要對其中的UserId，MovieId，Rating三個字段進行計算。

HetRec2011-movielens-2k數(shù)據(jù)集2，其中包括了2113個用戶對10197部電影的85559條評分記錄，其中的user_ratedmovies表信息如3：下頁表4所示。

和Movielens100K數(shù)據(jù)集一樣，主要對UserID，MovieID，Rating三個字段進行計算。

3.2 精度與個性化評價指標

設(shè)向用戶推薦的個電影集合為R(m)，測試集中用戶評分過的電影集合為T(m)。推薦系統(tǒng)的個性化評測指標一般有召回率、準確率、覆蓋率和新穎度[7]等。

表4 user_ratedmovies表的格式

Tab.4 Format of the user_ratedmovies table

召回率：也稱“查全率”，指在最終的推薦列表中“用戶-電影”評分記錄所占的比例，其計算公式為：

2）準確率：也稱“精度”，指已經(jīng)發(fā)生過的“用戶-電影”評分記錄在最終的推薦列表中有所占比例。準確率的計算公式為：

3）覆蓋率：指最終的推薦列表中，電影所占的比例，反應(yīng)了算法發(fā)現(xiàn)長尾電影的能力，覆蓋率越高，說明算法越能將長尾（長尾：邊緣化）電影推薦給用戶。覆蓋率的公式為：

（6）

其中，M代表全部電影的集合，R(m)為向用戶推薦的電影集合。

4）流行度：即評價某項目的用戶數(shù)。計算公式為：

其中為平均流行度，為推薦的電影數(shù)。

3.3 實驗參數(shù)介紹

因為重點是對隱反饋數(shù)據(jù)進行分析，所以預(yù)測用戶會不會對某部電影評分，而不是預(yù)測用戶在準備評分的前提下會評多少分，進行離線實驗[8]。實驗的評價指標：有召回率、準確率、覆蓋率、流行度4個指標。利用十折交叉法[9]進行交叉驗證，對實驗次數(shù)取M = 8。

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

4.1 不同值對推薦效果的影響

值表示與目標用戶相似的其他用戶數(shù)量。不同值對推薦結(jié)果產(chǎn)生不同的影響[10]，通過賦予不同的取值，可以找到該算法中效果最好的值。

>>>===========RESTART========== >>> K召回率準確率覆蓋率流行度 2017.892%21.633%26.031%5.418 4019.013%22.419%18.971%5.527 6019.762%22.625%15.871%5.593 8019.127%22.342%14.613%5.611 10018.829%22.031%13.843%5.629 12018.603%22.671%12.871%5.64 14018.362%21.472%12.037%5.651 16018.357%21.394%11.817%5.671

從圖1可以看出，不同的值得到的召回率、準確率、覆蓋率和流行度都不相同，且不構(gòu)成線性關(guān)系。

召回率和準確率：值在60左右會得到較高的召回率和準確率。因此，合適的值對于獲得高推薦精度起到重要的作用。

覆蓋率：隨著值增大，覆蓋率總體呈下降趨勢。這是因為隨著值的增大，流行度越也隨之增大，被參考的用戶（這里指和目標興趣相似的用戶）就越多，結(jié)果就越趨近于熱門電影，從而對長尾電影的推薦就越少，造成了覆蓋率的降低。

流行度：因為值決定了在推薦電影時參考的和目標用戶興趣相似的用戶的數(shù)量，越大，說明參考的人越多，結(jié)果也就越來越趨近于全局熱門的電影。

4.2 傳統(tǒng)用戶相似度與倒查表計算方法運行時間的對比

從圖2和圖3可以計算出，傳統(tǒng)方法計算用戶相似度的時間為166秒，而采用倒查表所用時間為132秒，說明采用倒查表計算用戶相似度能有效提高效率，這是因為減少了對沒有相同評分項的用戶之間相似度的計算，所以提高了時間上的效率。另一方面，該方法在一定程度上也解決了“用戶-項目”矩陣的稀疏性問題。

>>>===========RESTART========== >>> K召回率準確率覆蓋率流行度 2017.783%20.971%26.031%5.471 4019.232%22.582%18.829%5.541 6019.411%22.547%16.715%5.593 8019.154%22.325%14.774%5.609 10018.842%22.031%13.809%5.63 12018.423%21.573%12.617%5.641 14018.361%21.491%12.016%5.658 16018.179%21.311%11.054%5.672 程序運行初始時間：2017-02-20 11:03:27 程序運行結(jié)束時間：2017-02-20 11:06:13

>>>===========RESTART========== >>> K召回率準確率覆蓋率流行度 2017.80%20.97%26.03%5.471 4019.23%22.58%18.83%5.541 6019.41%22.55%16.88%5.593 8019.19%22.38%14.77%5.609 10018.84%22.03%13.82%5.63 12018.45%21.60%12.62%5.641 14018.36%21.49%12.02%5.658 16018.18%21.31%11.05%5.672 程序運行初始時間：2017-02-20 11:10:14 程序運行結(jié)束時間：2017-02-20 11:12:26

4.3 采用用戶相似度改進方法后的對比

對比圖2的運行結(jié)果，采用公式（2）后，有效降低了熱門項目對用戶相似度計算的影響。從圖4可看出，召回率由原來的最高19.411%提升到19.433%，準確率由原來的最高22.582%提升到22.870%、覆蓋率由原來的26.031%提升到26.713%。這說明采用改進的用戶相似性方法能更好地實現(xiàn)推薦系統(tǒng)的個性化。

>>>===========RESTART========== >>> K召回率準確率覆蓋率流行度 2017.693%21.854%26.713%5.331 4019.247%22.870%19.529%5.542 6019.433%22.641%16.631%5.587 8019.258%22.478%14.834%5.644 10018.859%22.201%13.714%5.638 12018.523%21.573%12.617%5.651 14018.461%21.514%12.536%5.658 16018.371%21.392%11.054%5.701

圖5 采用用戶相似度改進方法后與改進前的對比

4.4 Moviel-ens100K與HetRec2011數(shù)據(jù)集對比

從圖1與圖5的結(jié)果可以發(fā)現(xiàn)：使用不同的數(shù)據(jù)集，推薦效果最優(yōu)時對應(yīng)K值不同，Moviel-ens100K在K=50左右獲得較好的推薦，而HetR-ec2011數(shù)據(jù)集在K=150左右獲得較好的推薦效果。

從Het Rec 2011數(shù)據(jù)集的運行結(jié)果來看，相比Movielens100K數(shù)據(jù)集，召回率有所下降，但準確率有了較大的提高。如果希望推薦的內(nèi)容數(shù)量越多越好，則是在追求高召回率；如果希望推薦的內(nèi)容中，真正想要的越多越好，則是在追求高準確率。根據(jù)本文的實驗結(jié)果，兩者無法同時實現(xiàn)。但是在較大數(shù)據(jù)集上，基于用戶的協(xié)同過濾推薦算法較為有優(yōu)勢．這是因為使用大數(shù)據(jù)集后，項目覆蓋率降低，流行度增加，表明算法所推薦的項目隨著數(shù)據(jù)集的增大，越來越接近熱門項目。

>>>===========RESTART========== >>> K召回率準確率覆蓋率流行度 407.39%33.67%4.75%6.931 607.61%34.37%3.59%6.96 807.80%35.03%3.03%6.991 1007.90%35.43%2.71%7.013 1207.94%35.60%2.57%7.015 1407.96%35.69%2.44%7.018 1607.95%35.68%2.35%7.023 1807.94%35.58%2.2077.028

4.5 采用不同計算相似度結(jié)果的方法對比

本文采用Jaccard系數(shù)、歐式距離和Pearson系數(shù)計算用戶的相似度，得出召回率、準確率，覆蓋率和流行率四個指標的值，并將三種方法的結(jié)果與改進后的算法結(jié)果相對比，通過圖7-圖10的對比可以看出，改進后的算法在召回率、準確率，覆蓋率方面比其他方法要高，但流行度較低。

圖7 不同相似度計算方法對比-準確率

5 結(jié)論

本文給出了一種改進的協(xié)同過濾算法，通過引入“項目-用戶”，只計算有相同評分項的用戶間的相似度，相比傳統(tǒng)計算方法，有效節(jié)約了運行時間。另一方面，利用“懲罰”用戶的方法，避免了用戶共同興趣列表中，項目對用戶相似度的影響，改進了用戶相似度的計算，進而更好地實現(xiàn)推薦系統(tǒng)的個性化。最后，本文比較了在不同數(shù)據(jù)集下推薦算法的評價指標，分析了對算法質(zhì)量的影響因素，以及產(chǎn)生影響的原因，并對比了不同計算相似度的方法，得出采用余弦相似度方法，獲得的推薦結(jié)果的平均效果最好的結(jié)論。

圖8 不同相似度計算方法對比-召回率

圖9 不同相似度計算方法對比-覆蓋率

圖10 不同相似度計算方法對比流行度

[1] Wen Wu, Liang He, Jing Yang. Evaluating recommender systems[C]. Digital Information Management (ICDIM), 2012 Seventh International Conference on, 2012: 56-61.

[2] John S Breese, David Heckerman, Carl Kadie． Empirical analysis of predictive algorithms for collaborative filtering[M]. Morgan Kaufmann Publishers, 1998.

[3] Zhang Jin. Collaborative filtering algorithm analysis and research in E-commerce recommendation system[D]. Beijing: Capital University of Economics and Business, 2012．

[4] Leng Ya-jun, Lu Qing, Liang Chang-yong. Survey of recommendation based on collaborative filtering[J]. Pattern Ｒecognition and Artificial Intelligence, 2014, 27(8): 720-734.

[5] Shi Feng-xian, Chen En-hong. Combining the Items' discriminabilities on user interests for collaborative filtering[J]. Jounal of Chinese Computer Systems, 2012, 33(6): 1533- 1536.

[6] Yin Jian, Wang Zhi-sheng, Li Qi, et al. Personalized recommendation based on large-scale implicit feedback[J]. Journal of Software, 2014, 25(9): 1953-1966.

[7] Liu Jian-guo, Zhou Tao, Guo Qiang, et al. Overview of the evaluated algorithms for the personal recommendation systems[J]. Complex Systems and Complexity Science, 2009, 6(3): 1-10.

[8] Chen Nuo-yan. The design and implementation of recommadation system based on personalized recommendation engine combination[D]. Guangzhou: South China University of Technology, 2012.

[9] Liu Bei-lin. A study of personalized recommendation evaluation based on customer satisfaction in E-commerce[J]. Computer Science and Service System (CSSS), 2011 International Conference, 2011: 129-135.

[10] Zhang Jin-bo, Lin Zhi-qing, Xiao Bo, et al. An optimized itembased collaborative filtering recommendation algorithm[C]. Network Infrastructure and Digital Content, 2009, IC-NIDC 2009, IEEE International Conference on, 2009: 414-418.

Improvement and Research of User-based Collaborative Filtering Algorithm

SU Lin-yu1,2, CHEN Xue-bin1,2

(1. College of Science North China University of Science and Technology, 063000, China; 2. Province Key Laboratory for date science, He'bei 063000, China)

Aiming at data sparseness of matrix, low efficiency and precision of recommendation existing in traditional user-based collaborative filtering algorithm, an improvement recommendation algorithm is put forward in this paper. The algorithm introduces item-user inversion table and calculates users' similarity of whom with the same rating items in user-rating-data matrix. Therefore, it can reduce data sparseness of matrix and avoid huge workload, which is brought by the calculation of pair-wise users' similarity in traditional algorithm. Considering the impact of different hot degree of items in users' similarity calculation, the improvement algorithm punishes the negative influence of popular projects on users' common interest lists. Therefore, it gets around negative impact of popular projects in the results of personalized recommendation. The experiment results of 10-fold cross-validation in Movielens100K and Het Rec 2011open dataset shows that improved algorithm could save running time，increase efficiency and personalization of recommendation．

User-based collaborative filtering;Personalized recommendation;Similarity calculation; 10-fold cross-validation; Items—users inversion table

TP301.6

A

10.3969/j.issn.1003-6970.2017.04.024

本文著錄格式：蘇林宇，陳學(xué)斌. 基于用戶的協(xié)同過濾算法的改進研究[J]. 軟件，2017，38（4）：127-132