基于用户的协同过滤算法的改进研究

第 3 8 卷第 4 期

COMPUTER ENGINEERING & SOFTWARE

Vol. 38, No. 4

国际 IT 传媒品牌

2017,

设讨研尧与启用

基于用户的协同过滤算法的改进研究

苏林宇U，陈学斌U

(1.华北理工大学理学院，河

北唐山

06300; 2.河北省数据科学与应用重点实验室，河

北唐山

06300)

摘要：本文针对传统的基于用户协同过滤算法的稀疏性大，推荐效率，精度低等问题，提出了一种改进的算

法。在计算“用户-评分”矩阵时，通过建立“项目-用户”倒查表，忽略无相同评分项的用户间相似性的计算，降 低了用户评分矩阵的稀疏性，以及传统方法中对所有用户两两计算相似度的工作量。在计算用户相似度时，考虑到 项目热门程度对推荐结果的影响，通过“惩罚”用户共同兴趣列表中的热门项目，避免了传统算法中由于赋予所有 项目相同权重给个性化推荐结果带来的负面影响。最后，通过和数据集检验该算法，并且用十折交叉方法验证结果。 结果表明，改进后的算法节约了运行时间，提高了推荐算法的效率和个性化。

关键词：基于用户的协同过滤；个性化推荐；相似度计算；十折交叉验证；项目-用户倒查表

DOI: 10.3969/j.issn.l003-6970.2017.04.024

本文著录格式：苏林宇，陈学斌.基于用户的协同过滤算法的改进研究[J].软件，2017, 38 (4): 127-132

中图分类号：

文献标识码：

TP301.6 A

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)

【Abstract】：Aiming at data sparseness of matrix, low efficiency and precision of recommendation existing in tra-

ditional 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 users1 similarity calculation, the improvement algorithm punishes the negative influ­ence of popular projects on users' common interest lists. Therefore, it gets around negative impact of popular pro­jects in the results of personalized recommendation. The experiment results of 10-fold cross-validation in Moviel- enslOOK and Het Rec 2011 open dataset shows that improved algorithm could save running time, increase efficiency and personalization of recommendation.

【Key words】：User-based collaborative 他ering; Personalized recommendation; Similarity calculation; 10-fold

cross-validation; Items—users inversion table

1引言

个性化推荐是一种通过研究用户的兴趣或购买

关注推荐行为本身。然而，协同过滤算法在实际应 用中也存在着稀疏性、效率、精确性、冷启动和可 扩展性等问题

在大型的电子商务系统中，如淘宝、亚马逊， 它们有成千上万的商品，但其中被用户评价过的只 占不到1%。这导致了“用户-评分”矩阵的过度稀疏。 此外，传统的协同过滤算法在计算用户间相似度时， 需逐个计算两个用户对同一个项目的评分，这使得 算法的时间复杂度达到了 〇(«2)，当用户数量较多 时，将耗费大量的时间，且难以找到最近邻居，进

行为，主动向用户推荐感兴趣的信息或商品的算法。 它的提出缓解了日益增长的互联息量与用户的 个性化需求间的矛盾。协同过滤是目前应用最广泛， 也是最成功的个性化推荐算法。它的基本思想是依 据用户的兴趣相似性进行建模，根据该模型，把与 当前用户相似的其他用户行为推荐给该用户。该技 术的优点是不需关注行为的具体表现形式，只需要

第38卷第4期软 件

而影响到推荐的效率与精确性。

最后，传统的基于用户的协同过滤算法在计算 用户相似度时，赋予所有项目相同权值，并没有考 虑项目的热门程度对推荐结果的影响。John S.

Breese曾提出[2]，即使两个用户购买或关注过同一

度，C(A)表示用户A曾经评分过的项目集合，|C(A)| 表示集合C(A)中元素个数，C(B)表示用户B曾经评 分过的项目集合，|C(B)|表示集合C(B)中元素个数， 计算公式m如(1)所示：

热门项目，也不能因此认定他们有相似的兴趣。所 以，将热门项目当成普通项目处理将会对个性化推 荐的结果造成负面影响。

WAB=m

VI 中)||C ⑷ I

^B

(1)

John S. Breese曾提出[1],即使两个用户购买过

同一热门项目，也不能因此认为他们有相似的兴趣。 因此，赋予热门项目相同权重将会对个性化推荐的 结果造成负面影响。例如，两个用户都买过自行车， 但不能说明他们都喜欢骑自行车，因为自行车作为 基本的交通工具，每个人都会有需求，但如果两个 人都买过昂贵的自行车配件，则可以认为他们兴趣 相似。C(i)表示所有评分项目中包含项目i的集合， |C(i)|表示集合C(i)中元素个数，利用John S. Breese 提出的思想，对用户相似度的公式进行改进：

X l〇g(l+|C(i)|)

rrr = ^(m)nC(/i)

VlC(/n)||C(«)|

, 2 n

2

改进的用户协同过滤算法

2.1建立“项目-用户”倒查表解决矩阵稀疏性问题

如表1，“一”表示用户对该商品无评价，这种 现象在电子商务系统中普遍存在。

1 “用户-项目”矩阵的稀疏性

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

表

用户

ABCD

a

3.52.6

——

b

4.6

—

c

—

d

3.7

——

e

——

4.3

—

1.2

—

2.12

3..6

公式（2)中对项目个数|C(i)|求对数后取倒数， 有效地降低了热门项目对用户相似度计算的影响，“惩罚”了用户m、《共同兴趣列表中，热门项目对他 们相似度的影响，提高了推荐结果的精度。

基于此，本文建立“项目-用户”表，即每个项目 对应该项目评分过的用户列表，并且忽略用户相似 度为〇(即两个用户之间没有对任何一个项目同时 评分）的情况。例如用户A和用户B同时评论过s 个项目，就有C〇Mn^4][5] = s ,从而可以倒查每个 项目应的用户列表，进而得到所有用户间不为0 的

以

表

1的数据为例，建立的“项目-

2.3改进的用户协同过滤算法流程

(1)

将数据集平均分为S份，选出其中的一份

作为测试集，把剩下的S-1份作为训练集。为了保 证评测指标不是过拟合的结果，采用十折交叉法进 行交叉对结果进行验证。需要进行S次试验，每次 使用不同的测试集，然后将S次试验测出的评测指 标均值作为最终的评测指标[4]。

(2)

进行基于用户的协同过滤算法[5]:找到和

用户A有相似兴趣的其他用户，然后把其他用户喜 好的、而用户d没有的项目推荐给用户

Wepl:找到和目标用户兴趣相似的用户集合。

用户”表如下：

2 “项目-用户”倒查表

Tab.2 Items-users inversion table

表

a b c d e A A B A C

对该项目评分过的用户

BCDDD

»印2:给用户推荐和他兴趣最相似的尤个用户 评价过的项目。以下公式计算用户w对项目《的感 兴趣程度：

P(m,n)= X Wnmrnu

⑴

2.2用户相似度公式改进

在传统的基于用户的协同过滤算法中，计算用 户相似度时，赋予所有项目相同权值。并没有考虑 项目的热门程度不同对推荐结果的影响。例如，在 采用余弦相似度公式来计算用户A和B的兴趣相似

《软件》杂志欢迎推荐投稿：cosoft@vip. 163 .com

128

其中，只/«，幻包含和用户m兴趣最接近的是个 用户，C(〇是对项目；评分过的用户集合uw表示 用户《和用户的兴趣相似度，rnu代表用户《对项 目《的兴趣(由于使用单一行为的隐反馈数据[6],所

苏林宇等：基于用户的协同过滤算法的改进研究

3

实验验证结果及分析

比例，反应了算法发现长尾电影的能力，覆盖率越 高，说明算法越能将长尾（长尾：边缘化）电影推 荐给用户。覆盖率的公式为：

coverage:

3.1 MovielenslOOK 和 HetRc2011-movielens-2k

实验数据集

本文采用MovielenslOOK数据集，包括了 700 个用户对9000部电影的100,000条评分记录，评分 范围是1-5,数值越大表示评价越高。其中u.data 表格如表3所75:

|R(m)|

M

(6)

其中，M代表全部电影的集合，R(m)为向用户 推荐的电影集合。

4)流行度：即滞某项目的用户数。计算公式为:

Popularity =

N

3 u.data表格式

Tab.3 Format of the u.data table

表

(7)

UserlD

用户编号

MovielD

电影编号

Rating

评分

Timestamp

时间戳

其中P为平均流行度，#为推荐的电影数。

3.3实验参数介绍

因为重点是对隐反馈数据进行分析，所以预测 用户会不会对某部电影评分，而不是预测用户在准 备评分的前提下会评多少分，进行离线实验[8]。实 验的评价指标：有召回率、准确率、覆盖率、流行 度4个指标。利用十折交叉法[9]进行交叉验证，对 实验次数取M = 8。

本文主要对其中的Userid, Movield, Rating三个字段进行计算。

HetRec2011-movielens-2k 数据集 2,其中包括

了 2113个用户对10197部电影的85559条评分记 录，其中的user_ratedmovies表信息如3:下页表4所示。

和MovielenslOOK数据集一样，主要对UserlD,

MovielD, Rating三个字段进行计算。

4

实验结果及分析

4.1不同JT值对推荐效果的影响

尤值表示与目标用户相似的其他用户数量。不 同尤值对推荐结果产生不同的影响[1()]，通过赋予尤 不同的取值，可以找到该算法中效果最好的X值。

3.2精度与个性化评价指标

设向用户m推荐的AT个电影集合为R(m),测 试集中用户评分过的电影集合为T(m)。推荐系统的 个性化评测指标一般有召回率、准确率、覆盖率和 新颖度[7]等。

»>===========RESTART==========K20406080100120140160

召回率

准确率

覆盖率

流行度

4 user ratedmovies 表的格式

Tab.4 Format of the user ratedmoyies table

表

Movield

用户编号

电影编号

Rating

评分

date 一 daydate 一 month

曰

月

date_year

年

date—hourdateminutedatesecond

时

分

秒

召回率：也称“查全率”，指在最终的推荐列表中 “用户-电影”评分记录所占的比例，其计算公式为：

17.2%

19.013%19.762%19.127%18.829%18.603%18.362%18.357%

图

21.633%22.419%22.625%22.342%22.031%22.671%21.472%21.394%26.031%18.971%15.871%14.613%13.843%12.871%12.037%11.817%5.4185.5275.5935.6115.6295.5.6515.671

Recall =

u

(4 )

准确率：也称“精度”，指已经发生过的“用

1 MovielenslOOK数据集运行结果

Fig.l Running result of using MovielenslOOK

从图1可以看出，不同的尤值得到的召回率、 准确率、覆盖率和流行度都不相同，且不构成线性关系D

召回率和准确率：X值在60左右会得到较高的 召回率和准确率。因此，合适的尺值对于获得高推 荐精度起到重要的作用。

《软件》杂志欢迎推荐投稿：cosoft@vip.163.com

2)

户-电影”评分记录在最终的推荐列表中有所占比 例。准确率的计算公式为：

^\\

Vicision =

R(m)nT(m)\\

S丨及⑷I

U

,.

3) 覆盖率：指最终的推荐列表中，电影所占的

129

第38卷第4期

软 件

覆盖率：随着尤值增大，覆盖率总体呈下降趋 势。这是因为随着尤值的增大，流行度越也随之增 大，被参考的用户（这里指和目标兴趣相似的用户） 就越多，结果就越趋近于热门电影，从而对长尾电 影的推荐就越少，造成了覆盖率的降低。

流行度：因为尤值决定了在推荐电影时参考的 和目标用户兴趣相似的用户的数量，尤越大，说明 参考的人越多，结果也就越来越趋近于全局热门的 电影。

4.3采用用户相似度改进方法后的对比

对比图2的运行结果，采用公式（2)后，有效 降低了热门项目对用户相似度计算的影响。从图4 可看出，召回率由原来的最局19.411%提升到 19.433%，准确率由原来的最高22.582%提升到 22.870%、覆盖率由原来的26.031%提升到26.713%。 这说明采用改进的用户相似性方法能更好地实现推 荐系统的个性化。

4.2传统用户相似度与倒查表计算方法运行时

间的对比

从图2和图3可以计算出，传统方法计算用户 相似度的时间为166秒，而采用倒查表所用时间为 132秒，说明采用倒查表计算用户相似度能有效提 高效率，这是因为减少了对没有相同评分项的用户 之间相似度的计算，所以提高了时间上的效率。另 一方面，该方法在一定程度上也解决了“用户-项目” 矩阵的稀疏性问题。

»>

»>===========RESTART=

»>

K

20406080100120140160

召回率准确率覆盖率流行度

17.693%19.247%19.433%19.258%18.859%18.523%18.461%18.371%

图

21.8%22.870%22.1%22.478%22.201%21.573%21.514%21.392%26.713%19.529%16.631%14.834%13.714%12.617%12.536%11.0%5.3315.25.5875.45.6385.6515.6585.701

20.971%26.031%22.582%18.829%22.7%16.715%22.325%14.774%22.031%13.809%21.573%12.617%21.491%12.016%21.311%11.0%

程序运行初始时间：2017-02-20 11:03:27 程序运行结束时间：2017-02-20 11:06:13

图

K20406080100120140160

17.783%19.232%19.411%19.1%18.842%18.423%18.361%18.179%

召回率准确率覆盖率流行度

5.4715.15.5935.6095.635.15.6585.672

4用户相似度改进方法的运行结果

Fig.4 Running result of calculating users similarity by

using improved method

30.00025.000

211

0-oo o 5- 0-oo5-o 0-

ooo ooo ooo

图

召回率

准确率

覆盖率

流行度

2传统方法计算用户相似度的运行时间

Fig.2 Running time of calculating users similarity

»>

20.97%26.03%22.58%18.83%22.55%16.88%22.38%14.77%22.03%13.82%

12.62%21.60%

21.49%12.02%21.31%11.05%

程序运行初始时间：2017-02-20 11:10:14 程序运行结束时间：2017-02-20 11:12:26

图

K20406080100120140160

5采用用户相似度改进方法后与改进前的对比 Fig.5 Comparison result between calculating user similarity after by using improved method and before

4.4 MovielenslOOK 与 HetRec2011 数据集对比

从图1与图5的结果可以发现：使用不同的数 据集，推荐效果最优时对应K值不同，Moviel­

enslOOK 在 K=50 左右获得较好的推荐 ，而 HetR- ec2011数据集在K=150左右获得较好的推荐效果。

召回率

17.80%

19.23%19.41%19.19%18.84%18.45%18.36%18.18%

准确率覆盖率流行度

5.4715.15.5935.6095.635.15.6585.672

从Het Rec 2011数据集的运行结果来看，相比

MovielenslOOK数据集，召回率有所下降，但准确

3倒查表计算用户相似度的运行时间

Fig.3 Running time of calculating users similarity by

using inversion table

《软件》杂志欢迎推荐投稿：cosoft@vip.163.com

130

率有了较大的提高。如果希望推荐的内容数量越多 越好，则是在追求高召回率；如果希望推荐的内容 中，真正想要的越多越好，则是在追求高准确率。

苏林宇等：基于用户的协同过滤算法的改进研究

根据本文的实验结果，两者无法同时实现。但是在 较大数据集上，基于用户的协同过滤推荐算法较为 有优势.这是因为使用大数据集后，项目覆盖率降 低，流行度增加，表明算法所推荐的项目随着数据 集的增大，越来越接近热门项目。

用户相似度的计算，进而更好地实现推荐系统的个 性化。最后，本文比较了在不同数据集下推荐算法 的评价指标，分析了对算法质量的影响因素，以及 产生影响的原因，并对比了不同计算相似度的方法， 得出采用余弦相似度方法，获得的推荐结果的平均 效果最好的结论。

:RESTART:

K

406080100120140160180

召回率

7.39%7.61%7.80%7.90%7.94%7.96%7.95%7.94%33.67%34.37%35.03%35.43%35.60%35.69%35.68%35.58%

准确率覆盖率

4.75%3.59%3.03%2.71%2.57%2.44%2.35%2.207

流行度

25.000%

20.000%

不同计算相似度度方法的召回率对比

6.9316.966.9917.0137.0157.0187.0237.028

^ 15.000%km 10.000% 5.000%

0.000%

^r^Tx\"

6 Het Rec 2011数据集的运行结果

Fig.6 Running result of using Het Rec 2011 dataset

图

20 40 60 80 100 120 140 160

K的取值

余弦相似度召回率^♦ jaccard系数召回率 欧式距离召回率 )(皮尔逊系数召回率

4.5采用不同计算相似度结果的方法对比

本文采用Jaccard系数、欧式距离和Pearson系 数计算用户的相似度，得出召回率、准确率，覆盖 率和流行率四个指标的值，并将三种方法的结果与 改进后的算法结果相对比，通过图7-图10的对比可 以看出，改进后的算法在召回率、准确率，覆盖率 方面比其他方法要高，但流行度较低。

不同计算相似度度方法的准确率对比

8不同相似度计算方法对比-召回率

Fig.8 Comparison result among calculating users simi­

larity by different methods recall ratio

图

30.000%25.000%20.000%條埘自 15.000% 18 10.000%

5.000%

0.000%

不同计算相似度度方法的覆盖率对比

25.000%20.000%15.000%$10.000%05.000%

0.000%

12 3 46 7 8

K的取值

余弦相似度覆盖率—• jaccard系数覆盖率

欧式距离覆盖率

皮尔逊系数覆盖率

20 40 60 80 100 120 140 160

K的取值

9不同相似度计算方法对比-覆盖率

Fig.9 Comparison result among calculating users simi­

larity by different methods coverage

图

不同计算相似度度方法的流行度对比

jaccard系数准确率余弦相似度准确率欧式距离准确率 • 皮尔逊系数准确率

7不同相似度计算方法对比-准确率

Fig.7 Comparison result among calculating users simi­

larity by different methods accuracy

图

鹋IHi

5

结论

2

本文给出了一种改进的协同过滤算法，通过引 入“项目-用户”，只计算有相同评分项的用户间的相 似度，相比传统计算方法，有效节约了运行时间。 另一方面，利用“惩罚”用户的方法，避免了用户共 同兴趣列表中，项目对用户相似度的影响，改进了

131

K的取值

余弦相似度流行度 jaccard系数的流行度叙式距會出的森行度 •皮尔逊紊流行度

1 2 3 4 5 6 7 8

10不同相似度计算方法对比流行度

Fig.10 Comparison result among calculating users similarity by different methods popularity

图

《软件》杂志欢迎推荐投稿：cosoft@vip.163.com

第38卷第4期软 件

参考文献：

[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 filter- ing[M], Morgan Kaufinann 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 rec­

ommendation based on collaborative filtering[J]. Pattern R ecognition and Artificial Intelligence, 2014, 27(8): 720-734.[5] Shi Feng-xian, Chen En-hong. Combining the Items' dis-

criminabilities 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 recom­

[7]

[8]

[9]

[10]

mendation based on large-scale implicit feedback[J]. Journal of Software, 2014, 25(9): 1953-1966.

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

Chen Nuo-yan. The design and implementation of recom- madation system based on personalized recommendation en­gine combination[D]. Guangzhou: South China University of Technology, 2012.

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

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

歡狹高管洪士弍：要让毒个人部可4用到Al技术

人工智能技术在这几年内，不论是数据采集能力、算法的优化以及响应速度都有了突飞猛进的突破。AI已经“60 岁”了，而机器和人类的未来却在此刻成为这个时代最热门的话题。“让计算机像人类一样观察和描述这个世界”，曾经是一件听起来非常遥远的事情。但几个月前，微软宣布其语音 识别技术在行业标准测试中率先达到了人类专业水平。“微软小冰”的“读心术”能力也给行业带来很多惊喜。

在最近举办的第八期微软加速器Demo Day上，腾讯科技专访微软全球资深副总裁洪小文，聊了聊微软的人工智 能战略发展方向、目前人工智能领域的技术难点以及未来的竞争和三个话题。

微软的理念是将

AI普及化

“我们的理念是把AI普及化洪小文表示，“AI已经存在60年，为什么最近这么火?因为现在使用AI技术的门 檻被大大降低了。我们最近这几年非常火的测颜龄的应用How-01d.net,就是一个很好的例子。通过调用API,程序员 只用了不到十行代码就完成了。这样大家可以很容易实现各种人工智能应用，每个人要用AI的技术时都可以调用。”

微软一直称其为“一家平台公司”，希望帮助合作伙伴来做最后一层创新和应用。微软认知服务(Cognitive Services) 就是通过开放API的形式，将人工智能技术更简便开放地提供给开发者，让开发者能够利用API并结合自身数据、技 术来开发出更多应用。

同样，在2017年1月于德国慕尼黑举办的科技行业大会中，微软CEO萨提亚•纳德拉也曾经表示，对于微软来说， 最激动的并不是呈现于各种产品中的最新人工智能技术，“而是要把这样的能力，提交到每一个开发者和每一个组织的 手中。”

微软的API可以对第三方和开发者开放到什么样的程度呢?洪小文表示，微软的目标是每个人都可以调用。当然 人工智能技术的研究和发展不是一蹴而就的。比如人脸识别可以做，那么是否还可以识别其他东西，比如表情、图像、 文字、视频等。有些我们已经取得了重要进展并开放了相关API,同时我们还在不断探索和试验，这就需要时间去尝 试利用大量数据对计算机进行训练，这也是微软研究院一直在努力的。

其实从很早开始，微软就在人工智能领域进行相关技术探索。早在1991年，当比尔•盖茨创建微软研究院时，曾 提出过一个愿景：让计算机能看会听，并可理解人类的想法。这一理念吸引了许多顶尖天才加入微软研究院。自1998年

(下转141页）

《软件》杂志欢迎推荐投稿：cosofl@vip.l63.com

132