基于云填充和混合相似性的协同过滤推荐算法的研究

成韵姿　陈曦　傅明

摘要：针对传统推荐算法的相似性度量准确性不高及数据极端稀疏性等问题，提出一种基于云填充和混合相似性的协同过滤推荐算法。首先通过云模型填充用户-项目评分矩阵，然后对相似性度量方法进行改进，将基于时间序列的用户间影响力融合到基于Jaccard系数的相似性度量方法中。在MovieLens数据集上的验证结果表明，改进后的算法提高了推荐精度同时在一定程度上克服了数据稀疏性的影响。

关键词：协同过滤推荐算法；云填充；时序行为影响力；Jaccard系数

中图分类号：TP391 文献标识码：A

Abstract：A collaborative filtering recommendation algorithm based on cloud model filling and hybrid similarity was proposed to measure the similarity of the traditional recommendation algorithm with low accuracy and extreme sparsity of data. First， the useritem rating matrix was filled by the cloud model， and then the similarity measure method was improved， and the influence of the user based on time series was fused to the similarity measure method based on the Jaccard coefficient. The validation results on MovieLens data sets show that the improved algorithm can improve the recommendation accuracy and overcome the influence of data sparsity to a certain extent.

Key words：collaborative filtering recommendation algorithm； cloud model filling； temporal behavior influence； Jaccard coefficients

1引言

随着信息技术和互联网的发展，信息的产生、加工、传播变得越来越容易，人们每天都接触大量的信息，进入了信息过载的时代。在这个时代，无论是消费者还是商家都遇到了很大挑战：一方面，对于消费者来说，面对如此海量的数据信息，要从中剔除冗余信息、挑选出自己真正需要的信息，犹如大海捞针；另一方面，对于商家来说，要有针对性地推送商品信息，让自己的商品受到广大消费者的关注，也是一件非常困难的事情。在此背景下，电子商务推荐系统应运而生。

协同过滤推荐算法[1-2]是目前电子商务推荐系统中应用最广泛最成功的推荐技术。它的主要思想是利用已有用户群过去的行为或意见预测当前用户最可能喜欢哪些东西或对哪些东西感兴趣[3]。那么，整个推荐算法的关键是找出目标用户的最近邻居集合。然而，其归根结底在于用户或项目间相似性的度量[4-7]。因此，用户或项目间的相似性度量是否准确，直接关系到整个推荐系统的推荐质量。传统的相似性度量方法主要有：余弦相似性、相关相似性和修正的余弦相似都有其不足之处。在现实的数据中，由于用户评分数据的极端稀疏性，导致用户间相似性的度量不够准确，推荐精度较低。而且，大部分的推荐算法并没有考虑用户相互之间的影响关系，导致推荐系统的推荐质量下降。

与上述相关工作不同，本文利用云模型填充用户-项目评分矩阵，在分析基于时序行为的用户影响力和基于Jaccard系数的相似性度量方法的基础上，对用户间相似性的计算方法进行改进。将改进后的算法在MovieLens数据集上进行了相应的实验，实验结果表明，改进后的算法提高了推荐精度，同时在一定程度上克服了数据稀疏性的影响。

当一个推荐系统搭建好后，需要解决的首要问题是如何判断推荐系统的好坏。然而，推荐系统拥有多种评价标准，这些评价标准可用于评价推荐系统各方面的性能。由于不同的系统在不同的应用背景下表现不同，研究者们很难选取恰当的评价标准对系统的表现进行评估。大多数研究者选择采用准确度来评价推荐算法的好坏。预测准确度是度量一个推荐算法的预测打分与用户实际打分的相似程度，其中一个经典方法是度量预测打分与实际打分的平均绝对误差。然而，标准平均绝对误差[8]（Normalized Mean Absolute Error，简称NMAE）是平均绝对误差在打分值区间内作标准化，从而方便在不同的数据集上对算法的效果进行比较。因此，标准平均绝对误差的值越小表示该算法对用户行为的预测越准确。本文选用标准平均绝对误差的方法来评估推荐算法的优劣性。

2相关工作

2.1云填充

在实际生活中，用户对商品的评分记录是很少的，从而评分矩阵相当稀疏，导致推荐效果大大降低。为解决该问题，本文采用云填充[9-10]的方法解决稀疏问题。云模型[11]是李德毅院士提出的一种定性定量不确定性转换模型，能够实现定性概念与定量数值之间的不确定性转换。云填充的基本思想是：先找出未评分的项目，采用云模型计算项目之间的相似性，找出该项目的相似项目， 利用用户对相似项目的评分来预测未评分项目的评分，从而填充用户项目矩阵。

对于用户-项目评分矩阵R，用户有未评分项目c，其评分频度向量I=[I0，I1，I2，I3，I4，I5]，其中I0～I5表示6个评分等级出现的次数。通过逆向云发生器，即实现从定量值到定性概念的转换，可以得到该项目的评分特征向量V=[Ex，En，He]，其中Ex、En、He分别为期望、熵、超熵。两个项目之间的相似性由评分特征向量的夹角余弦来表示，如公式（1）。

sim（c，d）=VcVd‖Vc‖‖Vd‖ （1）

由此，找出用户未评分项目的相似项目集D，未评分项目c的预测评分如公式（2），以此来填充用户-项目评分矩阵R。

R（i，c）=∑d∈Dsim（c，d）×R（i，d）∑d∈D（sim（c，d）） （2）

其中，d表示未评分项目c的相似项目，sim（c，d）表示项目c和项目d的相似性，R（i，d）表示用户i对项目d评分。

2.2时序行为影响力

虽然协同过滤推荐算法跟其他推荐算法相比取得了巨大的成功，但是其仍存在着诸多问题，其中很重要的一点是传统的协同过滤推荐算法经常忽略兴趣漂移问题。所谓兴趣漂移，是指用户对商品的兴趣偏好会随着时间的推移而变化。Koren等人[12]提出的TimeSVD++算法将时间信息加入到用户（产品）的特征向量中，有效解决了兴趣漂移问题，取得了良好的结果。

超市购物篮数据常常包含关于商品何时被用户购买的时间信息，可以按照购买时间的先后次序，将用户在一段时间内的购物事件拼接形成一个时间序列[13]。用户或商品的消费时间信息可能会隐藏着一部分规律，利用这些规律可以在一定程度上识别系统的重要特征，或者预测特定事件的未来发生。基于时序信息的推荐算法通过将时序信息加入到现有的推荐模型中，使得模型能够学习到数据的动态变化，从而优化推荐效果[14]。

社会网络中的结点对应的对象之间存在着各种各样的关系，通过这些关系，对象之间也相互影响[15-16]。以用户的关系为例，用户在消费某些商品时经常受到朋友关系的影响，研究表明，通过朋友购买的商品向目标用户推荐商品，往往比简单的利用相似度来推荐商品的方法更可靠[17-19]。

由于传统的协同过滤推荐算法经常忽略了用户之间的关系，基于用户社会化关系挖掘的推荐算法是将用户关系融入到现有的协同过滤算法中，以提高算法的准确度。

孙光福等人[14]提出了一种基于用户间的时序消费行为建模的方法，只需要利用用户的消费时间先后信息来挖掘用户之间的相互隐含影响关系，就可以发现对当前用户影响最大的邻居集合。

在下面的例子中，形象地说明用户间的影响关系，如图1所示。

假设在一定时间段内，用户甲消费了25个商品，用户乙消费了85个商品，用户甲与用户乙消费商品的并集的个数是100个。根据用户甲与用户乙的消费时间先后信息形成序列，在用户甲与用户乙共同消费的商品中，有10件商品用户甲的消费时间比用户乙要早，即用户甲先消费然后用户乙才消费，说明用户甲对用户乙有一定的影响力。由此可得用户甲对用户乙的影响力为10/100=0.1，同理可得用户乙对用户甲的影响力为23/100=0.23。由图可知，甲与丁、丁与丙、乙与丙以及丙与甲之间的影响关系是单向的，也就是说两用户之间的影响关系是不对称的。那么用户之间的影响力如公式（3）。

effect（i，j）=wijunionij （3）

其中，对于用户i与用户j共同消费过的商品，wij表示用户i比用户j先消费的商品数，unionij为用户i和用户j所消费商品的并集，effect（i，j）为用户i对用户j的有向影响力。根据计算出的影响力大小，可以找出影响力最大的k个邻居用户。

2.3Jaccard系数

Jaccard相似性系数也可以用作度量用户相似性，如公式（4）。

sim（i，j）=Itemi∩ItemjItemi∪Itemj （4）

其中，Itemi、Itemj分别表示用户i和用户j评分过的项目集合。

3一种混合相似性的度量方法

3.1改进后的相似性

基于时序行为的最近邻建模方法是根据用户消费时间先后信息构建用户关系网络图，计算出用户之间的相互影响力，可以找到对目标用户影响最大的邻居集合。Jaccard系数相似性是通过两个用户评分分布来度量两个用户之间的相似性，两用户共同评分的项目所占的比例越大，相似性越高。以上两种方法的侧重点不同，都在一定程度上提高了推荐质量，笔者希望找到一种融合方法，对上述两种方法有所发展。

为了进一步提高相似度的准确性，将时序行为影响力融入到基于Jaccard的相似性度量中，得到改进后的用户相似性如公式（5）。

simfinal（i，j）=αsim（i，j）+（1-α）effect（i，j） （5）

其中，effect（i，j）表示用户i对用户j的影响力，sim（i，j）表示用户i与用户j基于Jaccard系数的用户相似性。

改进后的算法融合了两种相似性度量方法的优点，适用范围将更广泛。改进后的方法考虑到不同用户的关注项目集合的不同对相似性的影响，并且考虑了用户的消费时间先后信息反映出的用户间隐含影响关系，增加了度量用户相似性的信息量，降低了数据稀疏性的影响，提高了相似度的准确性。但改进后的相似性度量方法较基于时序行为的影响力和基于Jaccard系数的相似性复杂，对算法的可扩展性造成一定影响。

3.2算法流程

基于云填充和混合相似性的协同过滤推荐算法的基本思想是：首先利用云模型对用户-项目评分矩阵进行填充，从而降低数据稀疏性的影响；其次，建立用户-项目评分时间矩阵，根据用户对共同评分项目的评分时间先后顺序，计算用户之间的影响力；最后， 将时序行为影响力融入到基于Jaccard系数的相似性度量中，找出最近邻居，产生推荐结果。

具体步骤如下：

步骤1：利用云模型填充用户-项目评分矩阵R，得到R；

步骤2：由R根据公式（3）计算出用户的影响力矩阵effect；

步骤3：由R根据公式（4）计算出基于Jaccard系数的相似性矩阵sim；

步骤4：根据公式（5）计算出改进后的用户相似性矩阵simfinal；

步骤5：由simfinal计算出用户k个最近邻居，根据最近邻居的偏好为目标用户进行推荐。

4实验结果及分析

4.1数据集和推荐质量的评价标准

为了测试改进的推荐算法的有效性，本文采用了GroupLens Research网站提供的包含100000个电影评分数据的MovieLens数据集，涉及943个用户和1682部电影。该数据集中每个用户都至少评价过20部电影，其评分值是从1到5的整数，评分数值越高表示用户对该电影越喜欢。在实验中，随机地将80%的数据划分为训练集，剩余的20%的数据作为测试集。

常用的推荐质量评估方法有平均绝对误差（Mean Absolute Error，简称MAE）[17]、平均平方误差和标准平均绝对误差NMAE[18-19] 。

对于用户i，平均绝对误差MAEi公式如式（6）。

MAEi=∑nic=1pic-ricni （6）

其中，ni表示用户i在测试集中已经评分过的项目的个数（ni≤n），pic、ric分别为用户i对项目c的预测评分及其对应的实际评分。

对于所有用户的平均绝对误差见公式（7），标准平均绝对误差见公式（8）。

MAE=∑mi=1MAEim （7）

NMAE=MAErmax -rmin （8）

其中，rmax和rmin分别为用户打分区间的最大值和最小值。

标准平均绝对误差（NMAE）就是平均绝对误差在打分值区间内作归一化，从而方便在不同的数据集上对同一个算法的表现进行比较。NMAE能够较为直观地对推荐质量进行评估，容易理解。如果NMAE的值越小，那么推荐的准确性就越高。

4.2实验结果及分析

实验1 参数α对算法的影响。

本文中最终相似度由影响力和Jaccard系数两部分组成，而参数α是平衡两者的权重。α越大，说明基于Jaccard系数的相似性在最终相似性中的比重越大。实验首先比较了本文算法在参数α的不同取值下的结果。在实验中，分别设定了参数α的不同取值α=[0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9]，算法的其他参数均设置为使算法最优时的相应值。

比较不同的α值对NMAE值的影响，实验结果如图2所示。

根据结果可以看出，参数α对算法有较大的影响，随着α的增加，本文算法的标准平均绝对误差NMAE不断增加，说明了引入基于时序行为的有向影响力对用户间的相似性有更加重要的影响。同时发现，当α=0.5时变化趋于平缓。

实验2 最近邻居个数对算法的影响。

实验首先比较最近邻居个数对不同的相似性度量方法的影响。在实验中，选择的相似性度量方法分别为本文算法、余弦相似性、修正的余弦相似性、相关相似性。实验从不同的最近邻居个数比较算法的推荐质量，测试邻居个数分别为5、10、15、20、25、30、35，实验结果如图3所示。

从实验结果可以看出：①随着邻居个数的增加，在一定程度上增加了运算的复杂度，标准平均绝对误差NMAE有所上升，当邻居个数增加到一定的值时这种变化趋于平缓。②本文中改进的相似性度量方法与传统的相似性度量方法有较大提高，进一步说明基于时序行为的用户有向影响力与基于Jaccard系数相似性相结合的方法能比较有效提高协同过滤算法的推荐精度。

5结束语

本文对传统的协同过滤算法中度量用户间相似性的方法进行改进。首先比较传统算法中度量用户间相似性的方法，然后将基于时间序列的用户间影响力融合到基于Jaccard系数的相似性度量方法中。改进的方法考虑到了用户共同评分项目个数对相似性的影响，并且考虑了用户间的隐含影响关系，增加了时效性，从而提高了相似度的准确性，在某种程度上降低了数据稀疏性的影响并且提高了推荐结果的准确性。接下来将会对如何更好地选取参数α以及如何考虑空间、任务等因素更好地完成推荐进行研究。

参考文献

[1]马宏伟， 张光卫， 李鹏. 协同过滤推荐算法综述[J]. 小型微型计算机系统， 2009， 30（7）： 1282-1288.

[2]LIU Q，CHEN E H，XIONG H，et al.Enhancing collaborative filtering by user interests expansion via personalized ranking[J]. IEEE Trans. on Systems， Man and Cybernetics—B， 2012， 42（1）： 218-233.

[3]JANNACH D，ZANKER M，FELFERNING A，et al.推荐系统[M]. 蒋凡，译. 北京：人民邮电出版社， 2013.

[4]SU J H， YEH H H， YU P S， et al. Music recommendation using content and context information mining[J]. IEEE Intelligent Systems， 2010， 25（1）： 16-26.

[5] 冷亚军， 陆青， 梁昌勇. 协同过滤推荐技术综述[J]. 模式识别与人工智能， 2014， 27（8）： 720-734.

[6]王立才， 孟祥武， 张玉洁. 上下文感知推荐系统[J]. 软件学报， 2012， 23（1）： 1-20.

[7]孟祥武， 胡勋， 王立才， 等. 移动推荐系统及其应用[J]. 软件学报， 2013， 24（1）： 91-108.

[8]刘建国， 周涛， 郭强， 等. 个性化推荐系统评价方法综述[J]. 复杂系统与复杂性科学， 2009， 6（3）： 1-10.

[9]张光卫，李德毅，李鹏，等.基于云模型的协同过滤推荐算法[J].软件学报，2007，18（10）：2403-2411.

[10]毛志勇，赵盼盼.基于云填充和蚁群聚类的协同过滤图书推荐算法[J].现代情报，2015，35（5）.

[11]李德毅，杜鹢.不确定性人工智能[M].北京：国防工业出版社，2005，143-144.

[12]KOREN Y. Collaborative filtering with temporal dynamics[C].In： Proc. of the ACM SIGKDD Conf. on Knowledge Discovery and Data Mining. ACM Press， 2009. 89-97.

[13]TAN Pangning，STEINBACH M，kUMAR V.数据挖掘导论[M]. 范明， 范宏建， 等， 译. 北京：人民邮电出版社， 2011.

[14]孙光福，吴乐，刘淇，等.基于时序行为的协同过滤推荐算法[J].软件学报，2013，24（11）：2721-2733.

[15]刘红岩. 社会计算：用户在线行为分析与挖掘[M]. 北京：清华大学出版社， 2014.

[16]郭强， 刘建国. 在线社会系统的用户行为分析研究进展[J]. 复杂系统与复杂性科学， 2015， 12（2）： 97-102.

[17]孟祥武， 刘树栋， 张玉洁， 等. 社会化推荐系统研究[J]. 软件学报， 2015， 26（6）： 1356-1372.

[18]WANG Z，SUN L F，ZHU W W，et al.Joint social and content recommendation for usergenerated videos in online social network[J]. IEEE Trans. on Multimedia， 2013， 15（3）： 698-710.

[19]QUIJANOSANCHEZ L，RECIOGARCIA J， DIAZAGUDO B. Social factors in group recommender systems[J]. ACM Trans. on Intelligent Systems and Technology， 2013， 4（1）： Article No.8.