一种基于线性回归的新型推荐方法

王兆国++谢峰++关毅 薛一波

术学院， 哈尔滨 150001； 2 清华大学 信息科学与技术国家实验室， 北京 100084）

摘要： 关键词： 中图分类号： 文献标志码： A文章编号： 2095-2163（2017）04-0001-05（1 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150006， China；

2 National Lab for Information Sci. & Tech， Tsinghua University， Beijing 100084， China）

Abstract： With the development of social media， Internet is not only people's tool to get information， but also a channel to share information. Usergenerated contents make people face overload information. So that a lot of really valuable information is difficult to be found. On the strength of lower user involvement， the personalized recommendation system has been considered as one of the most potential methods to solve information overload at present. However， currently the most mature and widely used collaborative filtering recommendation method is facing such problems as data sparseness， diversity and so on. Its recommended effect is not ideal. A recommendation method based on linear regression is proposed in this paper. A linear regression model is established by using the rating frequency information of the users or items to predict the uses' scores on nonscored items. The method has the advantages of low complexity， incremental updating， and high accuracy and so on.

Keywords：

基金項目：

作者简介：

收稿日期： 0引言

近年来，社交网络的普及和发展，改变了人们被动获取信息的方式，用户产生内容呈爆炸式增长。对于普通用户来说，面对海量的信息难以找到自己真正感兴趣的部分，这就是信息过载问题＼[1＼]。门户网站按照信息的属性分门别类以帮助用户快速索引，搜索引擎通过分析用户输入的查询返回最相关的内容。尽管两者在很大程度上提高了用户获取信息的效率，但都需要用户过多的参与，不能自动感知用户的兴趣，况且很多时候用户根本不知道自己想要什么，或者不能有效运用关键词描述自己的兴趣。此外，分类和搜索技术返回的结果严重缺乏个性，用户体验不佳。推荐系统＼[2＼]通过分析用户的历史行为，为每一个用户建立个性化的兴趣模型，主动向用户推送可能感兴趣的内容，这被认为是解决信息过载最具潜力的设计研发方式。

目前居于应用流行首位的个性化推荐系统所采用的推荐方法是协同过滤＼[3＼]，维基百科给协同过滤方法的定义是：“利用某兴趣相投、拥有共同经验之群体的喜好来推荐使用者感兴趣的资讯”。协同过滤方法主要分为2类＼[3＼]：基于启发式的方法＼[4-9＼]和基于模型的方法＼[10-16＼]。其中，基于启发式的方法利用用户对物品的隐性或显性行为得到用户物品评分矩阵，然后计算用户或物品间的相似度，最后根据邻居用户或物品的评分及相似度给出评分预测和结果推荐。根据相似性计算的主题是用户还是物品，基于启发式的方法可以进一步分为基于用户的协同过滤方法＼[4＼]和基于物品的协同过滤方法＼[17＼]。目前，启发式方法由于呈现的易部署、高效率的特性，已然广泛应用于商业系统中，如Amazon。然而，由于数据稀疏性、多样性等问题则使得启发式方法的推荐性能难以得到有效提升。

为了提高推荐准确性，基于模型的方法利用用户物品评分矩阵训练更为精准的评分预测模型，比如：聚类＼[16，18＼]、贝叶斯信念网络＼[6，19＼]、马尔可夫决策过程＼[20＼]以及潜在语义模型＼[21＼]等。尽管基于模型的方法提高了预测准确性，但却也同样面临模型复杂、参数较多并且对数据集的统计特性依赖性较大等问题，这也是基于模型的方法难以应用于实际推荐系统的重要原因。

本文提出了一种基于线性回归的推荐方法。该方法利用用户或物品的评分频次信息，建立了用户或物品的某次评分与其最高频次评分的线性回归模型，进而利用该模型对未知评分直接根据历史评分频次进行预测。与传统方法相比，该方法极大地降低了计算复杂性，使得算法在Ω（n）的时间内完成所有计算，便于应用于实际的工业生产；利用群体智慧，采用统计信息估计模型参数，具有很好的抗噪声能力；算法同时具有很好的增量更新能力，可以在常数时间内对新产生的用户行为完成更新，实时性能好。endprint

2.4实验结果

为了比较不同方法对数据稀疏程度的容忍度，本节将MovieLens 1M数据集切分成不同比例的训练集和测试集。比例x%从10%以10%的步长增长到90%。分别比较了2.3节所述方法的评分预測准确性、分类准确性指标，以及模型建立和预测时间的相应结果对照，具体研究阐释论述如下。

2.4.1预测准确性

为了衡量基于线性回归的推荐方法评分预测准确性，本文采用了2.2节介绍的误差指标MAE和RMSE，其中RMSE在应用上要更趋广泛，这里，本文只给出了各方法在不同数据稀疏程度下的RMSE对比结果，如图1所示。

图1RMSE对比实验

Fig. 1RMSE comparative experiment

从图1可以看出基于线性回归的推荐方法无论在何种比例的数据集划分下的RMSE值均远远小于基于物品的协同过滤方法，即预测准确性高。同时，也可以看出单纯地以用户的评分频次以及物品评分频次的加权值作为预测结果，其准确性也较高，说明评分频次信息对于评分预测具有较大的价值。尽管当数据集更稀疏的情况下，图中训练集的比例仅为10%的时候，基于线性回归的推荐方法的RMSE值与物品平均评分很接近，但是随着训练集比例不断增加，基于线性回归的推荐方法的评分预测准确性则呈现出明显性能优势。

2.4.2分类准确性

评分预测准确性衡量的是预测评分与实际评分之间的差距，而真实系统中由于只关心给用户推荐出来的前N个物品是否符合用户的兴趣，因此，本文将预测评分和实际评分与评分喜好阈值（数据集采用5分制，这里阈值取3）进行比较，判断预测用户对物品的喜好是否与实际情况一致相符，也就是2.2节所讨论的喜好分类指标，其中，precision和recall值都不能单独衡量预测结果的分类性能高低，本文仅给出了两者合成指标F值的对比，如图2所示。

图2F-Measrue比较实验

Fig. 2F-Measure comparison experiment

从图2可以看出，随着训练集比例的增加，除基于物品的协同过滤方法外，其余方法的F值均有所增加，并且远远大于基于物品的协同过滤方法。此外，基于线性回归的推荐方法在所有方法中获得了最佳效果表现，其F值在训练集比例超过30%开始就大于基于物品平均评分的方法。

2.4.3时间性能

实际生产环境总是对推荐结果的响应时间有一定的需求，特别是用户和商品过亿的大型真实系统对算法的耗时将更加敏感。本节给出了基于线性回归的推荐方法与2.3节所介绍的方法的建模时间和预测时间的对比，结果如表2所示，其中，IA表示Item Average、IC表示Item Correlation、RF表示Rating Frequency、LR表示Linear Regression。

表2建模时间和预测时间的对比分析

Tab. 2Comparison of modeling time and forecast time

训练集比例IAICRFLR20%T建模0.16729.0190.1590.250T预测4.0289.1070.95416.63940%T建模0.30259.1330.2680.441T预测3.1799.0960.67421.92860%T建模0.45584.8340.3700.689T预测2.1535.5770.46222.13380%T建模0.585110.3680.4741.136T预测1.1216.4300.25613.485基于物品平均评分的方法在建模的过程中只需要计算各物品的平均评分，而基于用户和物品评分频次的方法同样只需要简单计算每个用户的最高频次评分和物品的最高频次评分，因此这2种方法的建模时间非常短。建模耗时最长的是基于物品的协同过滤方法，该方法需要计算两两物品之间的Pearson相关系数，即物品相似度，然后为每一个物品选择一定数量的最相似的物品构成邻居物品集合，最终在评分预测过程中利用用户对未评分物品的邻居物品集合中的物品的评分加权得到预测结果。总体来说，基于线性回归的推荐方法的建模时间和预测时间具有较强的竞争力，能够满足真实系统对预测时间性能的要求。

3结束语

本文提出了基于线性回归的推荐方法，该方法巧妙地利用用户的评分频次以及物品的评分频次信息，分别构建了基于用户的线性回归模型和基于物品的线性回归模型，利用这2个模型同时预测用户对未评分物品的评分，最终将两者加权得到预测结果。在公开数据集上的实验结果表明，基于线性回归的推荐方法不仅预测准确性高于现有的主流方法（基于物品的协同过滤方法），而且分类准确性也表现得更优。此外，基于线性回归的推荐方法的时间性能远远高于基于物品的协同过滤方法，能够为更大规模的真实系统所采纳使用。未来工作中，研究将进一步改进基于线性回归的推荐方法，利用增量更新方式建立线性回归模型，并部署配置到真实的系统中检验其设计推荐效果。

参考文献：

[1] 刘建国， 周涛， 汪秉宏. 个性化推荐系统的研究进展[J]. 自然科学进展， 2009， 19（1）：1-15.

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

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

[4] RESNICK P， IACOVOU N， SUCHAK M， et al. Grouplens： An open architecture for collaborative filtering of netnews＼[C＼]// Proceedings of the 1994 ACM conference on Computer supported cooperative work. Chapel Hill， North Carolina， USA：ACM， 1994： 175-186.

[5] SHARDANAND U， MAES P. Social information filtering： Algorithms for automating “word of mouth”＼[C＼]//Proceedings of the SIGCHI conference on human factors in computing systems. Denver，USA：ACM Press， 1995： 210-217.

[6] BREESE J S， HECKERMAN D， KADIE C. Empirical analysis of predictive algorithms for collaborative filtering＼[C＼]// Proceedings of the Fourteenth conference on uncertainty in artificial intelligence. Madison， Wisconsin：ACM， 1998： 43-52.

[7] DELGADO J， ISHII N. Memorybased weighted majority prediction for recommender systems[C]//ACM SIGIR 1999 Workshop on Recommender Systems： Algorithms and Evaluation.Berkeley UC：Citeseer， 1999：1-5.

[8] NAKAMURA A， ABE N. Collaborative filtering using weighted majority prediction algorithms＼[C＼]//ICML '98 Proceedings of the Fifteenth International Conference on Machine Learning.San Francisco， CA， USA： Morgan Kaufmann Publishers Inc，1998： 395-403.

[9] YANG J M， LI K F. Recommendation based on rational inferences in collaborative filtering＼[J＼]. KnowledgeBased Systems， 2009， 22（1）：105-114.

[10]GOLDBERG K， ROEDER T， GUPTA D， et al. Eigentaste： A constant time collaborative filtering algorithm＼[J＼]. Information Retrieval， 2001， 4（2）：133-151.

[11]BILLSUS D， PPZZANI M J. Learning collaborative information filters＼[C＼]//Proceeding ICML'98 proceedings of the Fifteenth International Conference on Machine Learning.San Francisco， CA， USA：Morgan Kaufmann Publishers Inc，1998：46-54.

[12]GETOOR L， SAHAMI M. Using probabilistic relational models for collaborative filtering＼[C＼]// Workshop on Web Usage Analysis and User Profiling （WEBKDD'99）. New York， NY， USA：Citeseer， 1999：1-6.

[13]HOFMANN T. Collaborative filtering via gaussian probabilistic latent semantic analysis＼[C＼]// Proceedings of the 26th annual international ACM SIGIR conference on Research and development in information retrieval. Toronto， Canada：ACM， 2003： 259-266.

[14]MARLIN B M. Modeling user rating profiles for collaborative filtering＼[C＼]// Advances in neural information processing systems. Vancouver and Whistler， British Columbia， Canada：DBLP， 2003：1-8.

[15]PAVLOV D X， PENNOCK D M. A maximum entropy approach to collaborative filtering in dynamic， sparse， highdimensional domains＼[C＼]//Advances in neural information processing systems.Cambridge， MA， USA：MIT Press， 2002： 1441-1448.endprint

[16]UNGAR L H， FOSTER D P. Clustering methods for collaborative filtering＼[C＼]// AAAI workshop on recommendation systems.Menlo Park， California， AAAI Press， 1998：1-16.

[17]SARWAR B， KARYPIS G， KONSTAN J， et al. Itembased collaborative filtering recommendation algorithms＼[C＼]//Proceedings of the 10th international conference on World Wide Web. Hong Kong ：ACM， 2001： 285-295.

[18]CHEE S H S， HAN J， WANG K. Rectree： An efficient collaborative filtering method＼[M＼]// KAMBAYASHI Y， WINIWARTER W， ARIKAWA M. Data Warehousing and Knowledge Discovery.DaWaK 2001. Lecture Notes in Computer Science. Berlin： Springer， 2001： 141-151.

[19]SU X， KHOSHGOFTAAR T M. Collaborative filtering for multiclass data using belief nets algorithms[C]//Tools with Artificial Intelligence， 2006. ICTAI'06. 18th IEEE International Conference on.Arlington， VA： IEEE， 2006： 497-504.

[20]SHANI G， HECKERMAN D， BRAFMAN R I. An mdpbased recommender system＼[J＼].The Journal of Machine Learning Research，2005，6：1265-1295 .

[21]HOFMANN T. Latent semantic models for collaborative filtering＼[J＼]. ACM Transactions on Information Systems （TOIS）， 2004， 22（1）：89-115.

[22]SARWAR B， KARYPIS G， KONSTAN J， et al. Analysis of recommendation algorithms for ecommerce＼[C＼]// Proceedings of the 2nd ACM conference on Electronic commerce.Minneapolis， Minnesota， USA ： ACM， 2000： 158-167.

[23]KARATZOGLOU A， AMATRIAIN X， BALTRUNAS L， et al. Multiverse recommendation： Ndimensional tensor factorization for contextaware collaborative filtering＼[C＼]// Proceedings of the fourth ACM conference on Recommender systems. Barcelona， Spain：ACM，2010： 79-86.

[24]JAMALI M， ESTER M. A matrix factorization technique with trust propagation for recommendation in social networks＼[C＼]// Proceedings of the fourth ACM conference on Recommender systems.Barcelona， Spain ：ACM， 2010： 135-142.

[25]CREMONESI P， KOREN Y， TURRIN R. Performance of recommender algorithms on topn recommendation tasks＼[C＼]//Proceedings of the fourth ACM conference on Recommender systems.Barcelona， Spain： ACM， 2010： 39-46.

[26]Sarwar B， Karypis G， Konstan J， et al. Application of dimensionality reduction in recommender system-a case study＼[R＼]. Minneapolis： University of Minnesota， 2000.endprint