适应用户兴趣变化的改进型协同过滤算法

胡伟健 滕飞 李灵芳 王欢

摘要：协同过滤算法可以根据用户的历史行为记录去预测其可能喜欢的物品，是现在业界应用极为广泛的推荐算法。但传统的协同过滤算法并没有考虑到用户兴趣的概念漂移，在一些基于时间的协同过滤算法中对推荐时效性的考虑也有所欠缺。针对这些问题，结合用户兴趣随时间转移的特点，改进了相似度的度量方法，同时引入一种增强的时间衰减模型来度量预测值，并将这两种方式有机地结合起来，解决了用户兴趣的概念漂移问题并考虑了推荐算法的时效性。仿真实验中，分别在不同的数据集中对比了该算法与UserCF、TCNCF、PTCF以及TimeSVD++算法的预测评分准确度和TopN推荐准确度。实验结果表明，改进算法能够降低预测评分的均方根误差（RMSE），并在TopN推荐准确度上均优于对比算法。

关键词：协同过滤；个性化推荐；用户兴趣；欧氏距离；时效性

中图分类号：TP391.4；TP311

文献标志码：A

0引言

随着大数据时代的来临，我们已经由原来的信息匮乏时代迈向了信息过载的时代。人们每天需要面临海量的信息，面对这些海量信息，用户需要根据其信息需求投入大量时间进行信息的过滤和选择，产生信息过载问题[1]。为了解决信息过载给用户带来的困扰，学术界和业界进行了大量信息技术的创新和实践，推荐系统正逐渐成为解决信息过载的主要发展方向[1]。推荐系统可以根据用户的个体信息需求，为其提供个性化信息推荐，在海量信息空间中，以个性化的方式引导用户获得有用的信息对象[2]。如今，推荐系统已经成功应用在诸如电子商务[3]、数字图书馆[4]、新闻[5]等诸多领域，并且取得了不错的成果。

协同过滤（collaborative filtering）算法是应用最广泛，同时也是发展比较成熟的一种推荐算法。协同过滤推荐算法由于其与推荐内容的无关性，并可发现用户的潜在信息需求等优势，已经成为了推荐算法中最具发展前途的方向[6]。著名电子商务网站亚马逊的个性化推荐系统有着"推荐系统之王"的美誉，其核心算法就是协同过滤算法。据悉，亚马逊通过推荐系统，将其销售额提升了30%[3]。传统协同过滤算法没有考虑用户兴趣的变化，造成了推荐准确性的下降。早期的协同过滤算法研究中，通常使用将时间作为加权项与相似度或者预测评分进行结合的方法解决用户兴趣变化的问题。任磊[7]提出了一种将评分时间因子与皮尔逊相关系数相结合的相似度计算方法来模拟用户兴趣变化；丛晓琪等[8]将一种时间加权函数融合到预测值的计算中，提高了推荐的准确度。上述算法没有考虑产生推荐的当前时间，不能够反映推荐产生时用户的兴趣变化，降低了推荐的时效性。

本文旨在解决用户兴趣变化问题，并提高推荐算法时效性，提出了一种适应用户兴趣变化的改进型协同过滤算法（Improved Collaborative Filtering recommendation algorithm incorporated with User Interest Change， ICFUIC）。主要从以下两个方面对传统协同过滤算法进行了改进：首先，提出了一种改进的欧氏距离相似度度量方法，在欧氏距离的计算中引入时间信息来模拟用户的兴趣变化；其次，在预测值计算时引入了一种增强的时间衰减模型，加入了推荐的当前时间，提高了推荐时效性。

1相关研究

1.1传统协同过滤算法

协同过滤技术是推荐系统中应用最为成功的一种信息过滤技术[9]，主要利用与目标用户相似的用户行为（评分、点击次数等）推断目标用户对特定产品的喜好程度，然后根据这种喜好进行相应的推荐[10]。算法输入一般为用户项目评分矩阵，输出可以为用户对项目的预测评分或推荐的项目列表。传统的协同过滤算法又可以分为基于用户的协同过滤（UserCF）算法和基于项目的协同过滤（ItemCF）算法。本文将以UserCF算法作为研究的基础协同过滤算法。UserCF算法首先利用已有的用户行为记录计算出各用户之间的相似程度，常用的计算用户相似度的方法有皮尔逊相关系数方法（式（1））、欧氏距离相似度方法（式（2））、余弦相似度方法等；然后选取最相似的若干用户组成最近邻集合，并通过最近邻集合中用户行为记录来对目标用户可能的行为进行预测，预测函数如式（3）所示；最后根据预测产生推荐结果。

1.2基于时间的协同过滤算法

为了解决用户兴趣的概念漂移问题，文献[11]中提出了一种时间加权协同过滤算法，即引入时间加权函数来改进相似度的计算，通过时间加权函数对用户的相似度进行加权处理，评分时间较近的两个物品权重更高；反之，权重越低。文献[12]中通过引入了艾宾浩斯记忆曲线来模拟用户兴趣的变化，并将遗忘曲线进行拟合后的拟合函数作为时间加权函数引入到相似度度量中。文献[13]中了将时间信息引入到奇异值分解（Singular Value Decomposition， SVD）方法中，提出了一种TimeSVD++算法，从而将时间信息加入到了用户的特征向量中。文献[14]中将时间作为第三个维度引入到算法中，并使用张量分解的方式模拟动态变化。以上文献中的这些方法通过不同的形式将时间信息考虑进了推荐算法的计算过程中，从实验结果来看，都在一定程度上提高了推荐的准确性。

与上述方法不同，本文通过将评分的相对时间信息引入欧氏距离中来计算相似度，并引入了一种增强型的时间衰减函数用来计算预测值，提出了一种适应用户兴趣变化的改进型协同过滤算法。

2适应用户兴趣变化的改进型协同过滤算法

2.1算法的提出

2.1.1改进的欧氏距离相似度方法

传统的推荐算法中用欧氏距离度量相似度时采用了如式（2）中的方法。在信息建模的过程中，根据用户对物品的评分建立一个用户物品评分矩阵，即R（U，I），然后对矩阵通过式（2）中的方法计算用户与用户或者物品与物品之间的相似度。

改进的欧氏距离算法中在信息建模时不仅建立了用户物品评分矩阵，而且建立了一个对应的评分时间矩阵T（U，I），记录了用户对物品产生评分的时间，矩阵T与矩阵R一一对应，若用户未对该物品评分（以“—”表示），则矩阵中对应项为0即可。如用户1对物品1的评分为3.0，评分时间为2015年11月1日；用户2对物品1无评分；用户2对物品2的评分为5.0，评分时间为2015年12月15日；用户1对物品2的评分为4.0，评分时间为2015年10月3日。信息建模后可得出如下两个矩阵（为方便数学计算，已经将时间信息转化为时间戳格式）：

2.1.3适应用户兴趣变化的改进型协同过滤算法

改进的欧氏距离算法不仅能够解决皮尔逊相关系数在度量相似度上的不足，而且通过引入时间信息到欧氏距离的计算中，考虑了历史行为记录的相对时间，从而能够得到用户之间更加真实、准确的相似度；将增强的衰减函数加入到预测值的计算中，引入了推荐的当前时间，使得推荐的结果更接近于用户的当前兴趣，提高了推荐时效性。因此，改进算法ICFUIC将两种方式有机结合起来，利用改进的欧氏距离算法来度量相似度，利用引入了增强的时间衰减函数的预测值计算方法来度量预测值，形成了一种更加全面的、能够更好适应用户兴趣变化的改进型协同过滤算法。

2.2算法过程描述

根据协同过滤算法的基本原则与式（4）～（10），可以总结出适应用户兴趣变化的改进型协同过滤算法（ICFUIC）过程如下：

3实验数据与结果分析

3.1实验数据集

为了比较时间因素对推荐结果产生的影响，实验数据集中应该包含有评分信息以及产生评分的时间信息，因此，实验中选择了以下两个数据集对算法进行验证：1）美国Minnesota大学提供的最新电影数据集MovieLens Latest Datasets；2）HP/Compad的DEC（Digital Equipment Corporation）研究中心提供的EachMovie数据集（由于实验机器硬件资源有限，采用随机抽样的方法从中抽取了部分数据）。

3.2实验结果度量标准

本文主要从评分预测和TopN推荐这两个方面来度量推荐算法的准确度。对于评分预测采用了均方根误差（Root Mean Square Error， RMSE）。RMSE通过计算预测值与实际值之间的偏差来衡量推荐质量，其得到的值越小，说明推荐算法的准确性越高，反之亦然。对于TopN推荐采用了F1-Measure指标，F1-Measure是由准确率（precision）和召回率（recall）共同计算得出，其得到的值越大，说明推荐算法的准确性越高，反之亦然。

3.3比较算法及参数设定

本文选择了改进算法ICFUIC与前文介绍的传统UserCF算法[9]、TCNCF算法[11]、PTCF算法[8]和TimeSVD++算法[13]进行对比。

在实验中，为了保证实验的准确性与可行性，将数据集随机划分为训练集与测试集，其中训练集为原数据集的80%，测试集为原数据集的20%。同时设置了两组对比实验：实验1主要验证算法的预测评分准确度；实验2主要验证TopN准确度。实验1中，为了验证各个算法在不同邻居数下的表现，邻居数设置为10～35，步长为5；由于TimeSVD++算法与邻居数无关，因此实验1中选择了特征数为10时，TimeSVD++算法的RMSE值。实验2选取用户的邻居数为20，观察了推荐数目K从10～35每次增加5时，各个推荐算法的性能。

3.4实验结果分析

实验1预测评分准确度比较。

图1中给出了D1、D2数据集下不同邻居数时五个对比算法对应的RMSE值比较结果，从中可以看出：

1）随着邻居数的不断增加，各个算法的预测评分准确度整体上在不断地提高并趋于稳定。

2）TCNCF与PTCF在数据集D1上比UserCF预测评分准确度都有了提高，主要是因为考虑了时间问题，可见用户兴趣变化对推荐准确性的影响；但在数据集D2上其准确度并不优于UserCF，说明改进算法的通用性上还存在不足。

3）ICFUIC在数据集D1和D2上，其预测评分的准确度均明显优于传统UserCF算法、TCNCF和PTCF，说明本文提出的改进方法能够更好地模拟用户兴趣变化，有效提高推荐的预测评分准确度。

4）TimeSVD++在D1、D2数据集下预测评分准确度均高于其他四种协同过滤算法，这主要是由于TimeSVD++采用了奇异值分解的方法进行推荐，该方法通过将评分矩阵进行分解提炼出潜在维度数（特征值），从而简化了数据，去除了噪声，可以更准确地计算用户间相似度；但特征值的选取具有不确定性，且分解后的向量具有不可解释性，同时在大规模稠密矩阵上进行分解时，算法的时间开销巨大，这些问题也限制了该方法在实际中的应用。

从表2的实验结果可以得出：

1）随着推荐数目不断增加，各个算法的TopN准确度都在不断提高。

2）结合实验1，TCNCF和PTCF虽然在数据集D1上的预测评分准确度比UserCF有了提高，但在TopN准确度的度量上，其F1-Measure低于UserCF，说明其改进方法仍然存在一定的缺陷与不足。

3）ICFUIC的F1-Measure值均明显高于UserCF、TCNCF和PTCF，说明ICFUIC在TopN准确度上较UserCF、TCNCF、PTCF也有了明显的提高；同时虽然TimeSVD++在预测评分准确度上优于ICFUIC，但是ICFUIC具有更高的TopN推荐准确度。

实验1与实验2中通过将五种算法的预测评分准确度和TopN准确度进行对比，可以发现本文提出的ICFUIC在预测评分准确度均优于同类型的传统算法与改进算法；同时在TopN准确度上均优于其他四种算法。因此，可以说ICFUIC在推荐准确度上有了明显的提高。

4结语

通过对协同过滤算法的研究与分析，传统算法中未考虑用户兴趣的概念漂移问题，在推荐准确度与时效性方面表现不佳。本文针对此不足之处，提出了一种适应用户兴趣变化的改进型协同过滤算法。算法在度量相似度时为了避免皮尔逊相关系数方法在数据稀疏时无法计算相似度的问题从而采用了欧氏距离来计算相似度，并且将时间因素引入到传统的欧氏距离的计算中，在一定程度上解决了用户兴趣的概念漂移问题。同时，又通过将增强的时间衰减模型引入到预测值的计算中来更好地解决推荐的时效性问题。最后将对相似度的改进计算方法与预测值的改进计算方法有机地结合起来。实验结果表明改进后的算法在推荐算法的准确度上有了明显的提高。

本文算法仍存在以下两个不足之处：1）对用户的相似度进行计算时，由于又新构建了评分时间矩阵，因此加大了对内存的开销，增加了计算的时间；2）实验中数据集来自于电影领域，因此在算法的应用场合上有一定的局限性。在接下来的工作中，主要针对上面提到的两点不足进行改进，尝试将相似度模型进行优化，以减少内存开销与计算时间；将算法运用到其他的应用场合中，来验证算法的有效性。

参考文献：

[1]RESNICK P， IACOVOU N， SUCHAK M， et al. GroupLens： an open architecture for collaborative filtering of netnews [C]// CSCW94： Proceedings of the 1994 ACM Conference on Computer Supported Cooperative Work. New York： ACM， 1994： 175-186.

[2]ADOMAVICIUS G， TUZHILIN A. Toward the next generation of recommender systems： a survey of the state-of-the-art and possible extensions [J]. IEEE Transactions on Knowledge & Data Engineering， 2005， 17（6）：734-749.

[3]SCHAFER J B， KONSTAN J， RIEDL J. Recommender systems in E-commerce [C]// EC99： Proceedings of the 1st ACM Conference on Electronic Commerce. New York： ACM， 1999： 158-166.

[4]JAYAWARDANA C， HEWAGAMAGE K P， HIRAKAWA M. A personalized information environment for digital libraries [J]. Information Technology & Libraries， 2001， 20（4）：185-196.

[5]KONSTAN J A， MILLER B N， MALTZ D， et al. GroupLens： applying collaborative filtering to Usenet news [J]. Communications of the ACM， 2000， 40（3）： 77-87.

[6]郑先荣，曹先彬. 线性逐步遗忘协同过滤算法的研究[J].计算机工程，2007，33（6）：72-73. （ZHENG X R， CAO X B. Research on lineal gradual forgetting collaborative filtering algorithm [J]. Computer Engineering， 2007， 33（6）： 72-74.）

[7]任磊.一种结合评分时间特性的协同推荐算法[J].计算机应用与软件，2015，32（5）：112-115. （REN L. A collaborative recommendation algorithm in combination with rating time characteristic[J]. Computer Applications and Software， 2015， 32（5）： 112-115.）

[8]丛晓琪，杨怀珍，刘枚莲.基于时间加权的协同过滤算法研究[J].计算机应用与软件，2009，26（8）：120-121. （CONG X Q， YANG H Z， LIU M L. On collaborative filtering algorithm based on time weight [J]. Computer Applications and Software， 2009， 26（8）： 120-121.）

[9]OWEN S， ANIL R， DUNNING T， et al. Mahout in Action [M]. Greenwich， CT： Manning Publications， 2011： 34-47.

[10]许海玲，吴潇，李晓东，等.互联网推荐系统比较研究[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.）

[11]李佳，陈亚军.基于时间和共同评分项目数的协同过滤算法研究[J].软件导刊，2015，14（7）：61-63. （LI J，CHEN Y J. A filtering algorithm research based on time and the number of common grading[J]. Software Guide， 2015， 14（7）： 61-63.）

[12]孙光辉.基于时间效应和用户兴趣变化的改进推荐算法研究[D].北京：北京邮电大学，2014：10-19. （SUN G H. Research of improved recommendation algorithm based on time effect and changes in users interest [D]. Beijing： Beijing University of Posts and Telecommunications， 2014： 10-19.）

[13]KOREN Y. Collaborative filtering with temporal dynamics [J]. Communications of the ACM， 2010， 53（4）： 89-97.

KDD 09： Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2009： 447-456.【

[14]XIONG L， CHEN X， HUANG T K， et al. Temporal collaborative filtering with bayesian probabilistic tensor factorization [C]// SDM 2000： Proceedings of the 2010 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2010： 211-222.

[15]FAN X， HU Y， ZHANG R， et al. Modeling temporal effectiveness for context-aware Web services recommendation [C]// ICWS 2015： Proceedings of the 2015 IEEE International Conference on Web Services. Washington， DC： IEEE Computer Society， 2015： 225-232.

[16]范家兵，王鹏，周渭博，等.在推荐系统中利用时间因素的方法[J]. 计算机应用，2015，35（5）：1324-1327. （FAN J B， WANG P， ZHOU W B， et al. Method by using time factors in recommender system[J]. Journal of Computer Applications， 2015， 35（5）： 1324-1327.）

[17]项亮. 推荐系统实践[M].北京：人民邮电出版社，2012：35-77. （XIANG L. Recommended System Practice [M]. Beijing： Posts and Telecom Press， 2012： 35-77.）

[18]王岚，翟正军.基于时间加权的协同过滤算法[J]. 计算机应用，2007，27（9）：2302-2303. （WANG L， ZHAI Z J. Collaborative filtering algorithm based on time weight [J]. Journal of Computer Applications， 2007， 27（9）： 2302-2303.）