基于信息熵和时效性的协同过滤推荐

刘江冬　梁刚　冯程　周泓宇

摘要：

针对协同过滤推荐算法存在的噪声数据问题，提出了用户信息熵模型。用户信息熵模型结合信息论中信息熵的概念，采用信息熵的大小衡量用户信息的含量，利用用户评分数据得到用户的信息熵，过滤信息熵低的用户，从而达到过滤噪声数据的目的。同时，将用户信息熵模型和项目时效性模型相结合，项目时效性模型利用评分数据上下文信息获得项目的时效性，能有效缓解协同过滤的数据稀疏性问题。实验结果表明提出的算法能有效过滤噪声数据，提高推荐精度，与基础算法相比，推荐精度提高了1.1%左右。

关键词：

推荐系统；协同过滤；噪声数据；数据稀疏性；信息熵；时效性

中图分类号：

TP181

文献标志码：A

Abstract：

Aiming at the noise data problem in collaborative filtering recommendation， a user entropy model was put forward. The user entropy model combined the concept of entropy in the information theory and used the information entropy to measure the content of user information， which filtered the noise data by calculating the entropy of users and getting rid of the users with low entropy. Meanwhile， combining the user entropy model with the item timeliness model， the item timeliness model got the timeliness of item by using the contextual information of the rating data， which alleviated the data sparsity problem in collaborative filtering algorithm. The experimental results show that the proposed algorithm can effectively filter out noise data and improve the recommendation accuracy， its recommendation precision is increased by about 1.1% compared with the basic algorithm.

英文关键词Key words：

recommender system； collaborative filtering； noise data； data sparsity； information entropy； timeliness

0引言

随着互联网技术日新月异的发展，互联网上拥有海量的信息，过量的信息造成了用户选择的困难，使得用户无法有效获取自身所需信息，这便是所谓的信息过载问题[1]。目前，解决信息过载问题的技术主要分两类：第一类是以搜索引擎为代表的信息检索技术；第二类是以推荐系统[2]为代表的信息过滤技术。搜索引擎在当今获取网络信息方面占据了十分重要的地位，它根据用户提供的关键字匹配信息，匹配结果的好坏很大程度上依赖于用户对信息描述的精准程度，且对于同样的检索输入始终会展现同样的搜索结果，无法实现用户个性化的需求。与搜索引擎技术不同的是，推荐系统能够通过分析用户的历史交易记录或行为挖掘用户兴趣，自动为用户产生满足用户兴趣和需求的推荐。

推荐系统作为解决信息过载问题的一项重要技术，被广泛应用到电子商务、社交网站等互联网平台，已成为Web 2.0应用中不可或缺的个性化信息服务形式。协同过滤算法[3]是一类重要的推荐算法，其实现简单，无需获取项目内容信息，推荐效果好，因而被广泛地研究和应用，已成为Amazon、淘宝网、京东网和当当网等电子商务平台广泛采用的商品信息推荐方法。协同过滤的基本思想是相似用户具有相同的兴趣偏好，它首先根据用户评分信息计算用户之间的相似性，找出一组相似性最高的用户作为邻居用户，然后根据邻居用户加权计算目标用户对于还未产生评分的项目的预测评分，进而产生推荐；但协同过滤技术存在噪声数据和数据稀疏性等问题，影响了其推荐结果的精确度[4]。推荐系统中的噪声数据主要来源于两方面：一是那些由商业利益驱动，为达到影响网络民意、扰乱网络环境等不正当目的，通过操纵软件机器人或水军账号，在互联网中制造和传播的虚假意见和评分[5-6]；二是系统中部分真实用户过于随意的评分行为也会产生噪声数据[7]，例如有些用户习惯性地对所有商品都给最高评分或最低评分。评分数据非常稀疏往往是由于实际网站中项目的数量庞大且不断增加，而用户通常只对一小部分项目评分，一般不超过系统中项目总数的1%。

针对协同过滤中噪声数据的问题，国内外学者进行了广泛的研究，常见的有基于统计特征、分类和聚类等研究方法。Chirita等[7]分析了恶意用户的评分行为统计特征，如用户评分标准偏差（Standard Deviation in Users Ratings）和TopN相似用户的平均相似度（Degree of Similarity with Top Neighbors）等特征，再利用这些统计特征来构建分类模型识别恶意用户；Bilge等[8]提出二分决策树的方法，该方法通过迭代执行二分Kmeans聚类算法生成二分決策树，从而将水军账号和正常用户聚类到不同的簇，达到过滤噪声数据的目的；Cao等[9]提出一种新的半监督学习算法（SemiShilling Attack Detection， SemiSAD），该算法先在少量有标记的用户集中训练得到一个贝叶斯分类器（Bayes），然后在大量无标记的用户集中采用期望最大化（Expectation Maximization， EM）算法优化初始得到的贝叶斯分类器。以上这些研究方法都采用了机器学习的相关算法，也能取得比较好的效果，但是都需要训练出复杂的模型。本文从信息论的角度，根据文献[7]中指出的水军用户具有评分集中性、评分极端性和针对特定目标等特征，直接采用信息熵衡量用户评分所含信息量的多少，过滤信息熵低的用户，达到过滤噪声数据的目的。

在利用时效性解决协同过滤中数据的稀疏性问题方面，文献[10]提出了一种基于项目时效性的解决算法，该算法挖掘评分数据的上下文信息，利用用户对于项目的评分记录构建项目时效性模型，为当前用户推荐时效性高的项目。

为进一步提高推荐系统性能，本文综合考虑用户信息熵模型和项目时效性模型，提出了融合用户信息熵和项目时效性的矩阵分解算法（Matrix Factorization combining User Entropy and Item Timeliness， UEITMF），进一步提高了推荐系统的推荐精度。

2系统模型

2.1用户信息熵模型

1962年，香农（Claude Shannon）在他著名的论文“通信的数学原理”（The Mathematic Theory of Communication）中提出了“信息熵”的概念，解决了信息的度量问题，它主要通过随机变量取值的不确定性程度来刻画信息含量的多少[12]。

这里用X表示一个随机变量，X取值为x的概率用p（x）表示，那么可以用信息熵表示它的不确定性程度，H（X）的计算如式（1）所示：

H（X）=-∫xp（x） lb p（x）dx（1）

由式（1）可知，信息熵H（X）只与变量X的概率分布有关，而与其具体取值无关。这在某种程度上说明信息熵能有效地避免噪声数据的干扰，可以有效地过滤掉评分系统中评分信息含量少的用户。系统中的用户对推荐引擎的作用效果不同，有的用户提供的评分所含的信息量多些，而有的少些，因而有效地过滤信息量少的用户可以有效提升推荐精度。

本文为了在推荐系统中引入用户信息熵模型，对于用户u，其评分集合用Ru={r1，r2，…，rm，…，rp}表示，在1到5分的评分系统中rm∈{1，2，3，4，5}，其中p=Ru表示用户u在系统中产生的评分数。对用户u，根据式（1），其信息熵为：

H（u）=∑Ck=1-puk lb（puk）（2）

其中：C表示评分区间数目，在5分制的评分系统中C=5；puk是用户u的评分落在区间k的概率。puk的计算过程如下：

puk=[∑rm∈RuI{rm=k}]/Ru；k∈{1，2，3，4，5}（3）

其中：I{*}为指示函数，I{true}=1，I{false}=0。联合式（2）和式（3）即可根据用户的评分值计算其信息熵。本文从信息论的角度，根据产生噪声数据的水军用户或少量正常用户具有评分集中性、评分极端性等特征，直接采用信息熵衡量用户评分所含信息量的多少，过滤信息熵低的用户，达到过滤噪声数据的目的。例如，在1到5分的评分系统中，用户u评价了20个项目，评分从1到5分别有4个，则其信息熵H（u）=∑51-420 lb（420）≈2.32，其信息熵达到最大值，因为其评分均匀分布，可以表示其对于相应项目的评分更加谨慎和客观。再看一种极端情况，用户u对所有项目的评分都为1分，即pu1=1，代入公式计算可得H（u）=0，所以用戶信息熵达到最低值，属于噪声数据，从直观上也可以看出这个用户的评分行为过于随意和极端，可信度较低。

为了过滤噪声数据，需要确定系统中的信息熵阈值Ht，即当H（u）

2.2项目时效性模型

文献[10]为缓解数据极端稀疏性情况下的冷启动问题，通过评分上下文信息构建项目时效性模型，融合到矩阵分解的推荐过程中，进一步提高了矩阵分解算法的推荐性能。

将所有用户对项目的评分记录作为考察集S，把集合S以项目为单位进行子集划分，从而将集合S划分成一系列的子集si。对于项目i，si={t1，t2，t3，…，tk，…，tq}，其中q表示系统中对项目i产生过评分行为的用户数，tk表示某用户对项目i产生评分行为的具体时刻，在t时刻项目i的时效性表示为Ci（t），其计算式如下：

Ci（t）=e-a（t-tf）（4）

其中：t表示当前时间；tf表示项目i发布的时间；a代表的是信息老化率系数。

本文将用户信息熵模型和项目时效性模型融合到矩阵分解法中，融合了用户信息熵模型和项目时效性模型的损失函数为：

3实验结果及分析

3.1实验数据集

本文采用的实验数据为MovieLens（1M）数据集，该数据集由明尼苏达大学（University of Minnesota）GroupLens研究院小组提供，其中包含6040名用户和3900部电影，用户评分范围为1～5分，每位用户至少对20部不同的电影进行过评分，总的评分次数为1000209次。数据集的每一行（rating.dat）由用户ID、项目ID、项目评分值与评分时间4个字段构成，数据集被随机分为训练集和测试集。

3.2评价指标

本文实验算法的评价标准为均方根误差（Root Mean Squared Error， RMSE），它通过计算预测的用户评分与实际的用户评分之间的偏差来度量预测的准确性。RMSE能够直观地衡量推荐质量，是最常用的一种推荐质量度量方法，在Netflix大赛中被广泛采用。推荐算法整体RMSE越小，则推荐的质量越高。测试数据集用RT表示，rui∈RT表示用户u对项目i的实际评分，ui表示推荐系统中用户u对于项目i的预测评分，RMSE的计算为式（8）：

RMSE=[∑rui∈RT（rui-ui）2]/RT（8）

3.3实验步骤

3.3.1过滤噪声数据

首先计算数据集中每一个用户的信息熵，得到用户信息熵分布图，如图1所示，横轴表示数据集中用户的ID，纵轴表示用户的信息熵值。观察图1中用户的信息熵分布，可以发现绝大部分用户的信息熵值大于1.0，可以认为信息熵偏低的用户的评分数据为噪声数据。

为了过滤噪声数据，需要确定信息熵阈值Ht，合理地选择信息熵阈值，对于提高最终的推荐精度有很大影响。本文分

别设置Ht为0，0.5，0.6，0.7，0.8，0.9，1.0，1.1，1.2，1.3，1.4，1.5这12个值，对于每一个Ht，通过十折交叉验证得到本文提出的融合用户信息熵和项目时效性的矩阵分解（UEITMF）算法对应的RMSE值（此时算法中隐含因子向量维度f取值为50）。不同Ht对应的RMSE值如图2所示。

观察图2，当信息熵阈值Ht取为1.1左右时，UEITMF算法的RMSE值达到最小值，这也与图1中用户的信息熵分布图相吻合，图1中绝大部分用户的信息熵值都分布在1.1以上，所以信息熵值低于1.1的用户评分数据即可以认为是噪声数据，过滤这部分噪声数据可以有效地提高推荐精度。当Ht取值小于1.1时，随着Ht的增加，RMSE值逐渐减小，这说明在一定范围内，过滤的噪声数据越多，越能有效提高推荐精度。当Ht取值大于1.1时，随着Ht的增加，RMSE值快速地增长，这是因为当信息熵阈值过大时，在过滤掉噪声数据的同时，也会大量地丢失正常用户评分数据，进一步加剧数据的稀疏性，从而使得算法的RMSE值偏大。对于不同的数据集，用户的信息熵会有不同的分布，达到最优效果的信息熵阈值也会不同，所以信息熵阈值的选取要考察实际的数据集。

对过滤的噪声数据进行统计分析，可以得到所有噪声数据用户的评分总次数为1957次，其中评分为5分的次数是1279次，评分为4分的次数是366次，评分为1分的次数是255次，所以评分为5分、4分和1分的总次数有1900次，占到噪聲数据评分总次数的97%，这充分说明了噪声数据用户具有评分极端性的特征。这些极端的评分对于推荐算法具有更大的影响，因而有效过滤这部分数据能够提高推荐精度。

3.3.2对比实验

为了充分考察本文提出的融合用户信息熵和项目时效性的矩阵分解算法（UEITMF）的有效性，本文将UEITMF算法与文献[10]中提出的基于项目时效性的冷启动解决（Timelinessbased Algorithm for Cold Start， TACS）算法，以及带有偏项的矩阵分解 （Matrix Factorization combining Biases， BMF）算法[11]进行对比实验。在矩阵分解算法中，用户和项

目隐含因子向量维度f的选择对于实验精度有重大影响，本文分别选取f值为10、20、50、80、100进行对比实验（UEITMF算法中Ht取值均为1.1），这里训练集占80%，测试集占20%，实验结果如表2所示。

观察表2可得，在相同f取值下，RMSE取值由小到大依次为UEITMF、TACS和BMF，说明本文提出的UEITMF算法能有效提高推荐精度，在f依次取值为10、20、50、80、100时，UEITMF相对于BMF的精度提升依次为1.08%、1.03%、1.07%、1.09%、1.09%（精度提升的计算公式为（BMF-UEITMF）/BMF×100% ，BMF和UEITMF分别代表在同样的f下对应的RMSE值），这些数值说明在不同的隐含因子维度f取值下UEITMF的精度提升在一定范围内是稳定的。进一步观察表2中数据可得，在同等f取值下，UEITMF相对于TACS的精度提升基本上都大于TACS相对于BMF的精度提升，这说明噪声数据对于精度提升有更大的影响。

4结语

本文提出了用户信息熵模型，解决了协同过滤推荐中存在的噪声数据问题，同时将用户信息熵模型和项目时效性模型相结合，提出融合用户信息熵和项目时效性的矩阵分解算法，实验结果表明本文提出的算法能有效提高推荐精度。

在过滤噪声数据的过程中，采取的是直接删除噪声数据用户的方式，但是其中不可避免地存在误分类的正常用户，如何既为噪声数据用户产生推荐同时又消除噪声数据对于推荐结果的影响，是进一步的研究方向。

参考文献：

[1]

许海玲，吴潇，李晓东，等.互联网推荐系统比较研究[J].软件学报，2009，20（2）：350-362.（XU H L， WU X， LI X D， et al. Comparison study of Internet recommendation system [J]. Journal of Software， 2009， 20（2）： 350-362.）

[2]

RESNICK P， VARIAN H R. Recommender system [J]. Communications of the ACM， 1997， 40（3）： 56-58.

[3]

CHU W， PARK S T. Personalized recommendation on dynamic contents using predictive bilinear models [C]// WWW 2009： Proceedings of the 2009 18th International Conference on World Wide Web. New York： ACM， 2009： 691-700.

[4]

孟祥武，刘树栋，张玉洁，等.社会化推荐系统研究[J].软件学报，2015，26（6）：1356-1372.（MENG X W， LIU S D， ZHANG Y J， et al. Research on social recommender systems [J]. Journal of Software， 2015， 26（6）： 1356-1372.）

[5]

WANG G， XIE S， LIU B， et al. Review graph based online store review spammer detection [C]// ICDM 2011： Proceedings of the 2011 International Conference on Data Mining. Washington， DC： IEEE Computer Society， 2011： 1242-1247.

[6]

SONG J， LEE S， KIM J. Spam filtering in twitter using senderreceiver relationship [C]// RAID 11： Proceedings of the 2011 14th International Conference on Recent Advances in Intrusion Detection. Berlin： Springer， 2011： 301-317.

[7]

CHIRITA P A， NEJDL W， ZAMFIR C. Preventing shilling attacks in online recommender systems [C]// WIDM 05： Proceedings of the 2005 7th Annual ACM International Workshop on Web Information and Data Management. New York： ACM， 2005： 67-74.

[8]

BILGE A， ZDEMIR Z， POLAT H. A novel shilling attack detection method [J]. Procedia Computer Science， 2014， 31： 165-174.

[9]

CAO J， WU Z， MAO B， et al. Shilling attack detection utilizing semisupervised learning method for collaborative recommender system [J]. World Wide Web， 2013， 16（5/6）： 729-748.

[10]

劉江冬，梁刚，杨进.基于时效性的冷启动解决算法[J].现代计算机，2016（2）：3-6. （LIU J D， LIANG G， YANG J. Timelinessbased algorithm for cold start [J]. Modern Computer， 2016（2）： 3-6.）

[11]

KOREN Y， BELL R， VOLINSKY C. Matrix factorization techniques for recommender systems [J]. Computer， 2009， 42（8）： 30-37.