刘江冬,梁刚,杨进(.四川大学计算机学院,成都 60065;.乐山师范学院计算机科学学院,乐山 64000)
基于时效性的冷启动解决算法
刘江冬1,梁刚1,杨进2
(1.四川大学计算机学院,成都610065;2.乐山师范学院计算机科学学院,乐山614000)
随着Web 2.0时代的到来,社交媒体、电子商务等越来越普及和流行,网上用户行为发生了巨大的变化。在线用户不仅仅消费信息,而且每个用户还会生产信息,信息量以指数规律迅猛地增长和扩展,造成了信息过载问题。信息过滤的一种重要解决方法是推荐系统[1]技术,已经成为Web 2.0时代的电子商务、社交媒体场景中一种重要的个性化信息服务形式。目前推荐系统主要采用的是协同过滤算法[2],由于其简单有效的实际应用效果,已经被广泛的研究和应用,其基本原理是相似用户也具有相似的偏好,它首先通过相似性计算获取当前用户的KNN最近邻,然后根据邻居用户的评分记录计算目标用户对还未产生过评分的项目的预测评分。但协同过滤技术由于仅仅是利用评分数据产生推荐,因而存在稀疏性问题、冷启动问题、扩展性问题等[2]。任何推荐系统在使用过程中都无法避免冷启动问题,因为刚投入应用或正在使用的推荐系统都会有随时加入的新用户和新项目,如果为新用户和新项目进行有效推荐,则能有效地保留客户和挖掘潜在用户。
为解决协同过滤中的冷启动问题,相关学者专家进行了大量的研究和尝试,现有的研究方向主要分为两类:一类是直接利用评分数据而不考虑新用户或新项目内容属性信息,主要有随机推荐的方法、平均值法、众数法、相似度度量改进法;第二类是将新用户或新项目的内容属性信息与评分数据相结合的方法,主要有基于原始评分矩阵扩充的方法、构建概率统计模型的方法、与机器学习相结合的方法。
随机推荐法是最简单最直观的方法,系统随机地推荐项目给新用户,这是比较冒险的方式,能为新用户推荐满意的项目的概率不会很高。平均值法[3]首先将新用户对未评分项目的预测值用所有项目的评分均值进行填充,然后在填充之后的评分矩阵上计算目标用户的KNN最近邻,最后采用协同过滤为目标用户产生推荐,这也是一种非常简单的方法。众数法[4]依据用户一般都有从众心理,采用所有用户对项目的评分个数最多的那个值作为新用户对未评分项目的预测评分值。相似度度量改进法[5]解决的是两个用户共同评分个数较少,相似度计算精确度不高的问题,对于没有评分的冷启动问题无能为力。冷启动问题产生是由于评分信息不足造成的,第一类方法都只是单一地考虑了评分信息,没有能够更进一步地挖掘评分数据的上下文信息。
基于原始评分矩阵扩充[6]的基本思想是在原始用户-项目评分矩阵中添加用户的人口统计信息和项目的内容特征信息,在扩充后的矩阵上再利用协同过滤算法进行推荐。构建概率统计模型的方法[7]是利用用户、项目、评分构建相应概率分布,利用期望最大化迭代算法获得用户在评分给定的情况下某项目出现的概率,然后将概率大于给定阈值或前TopN的项目推荐给用户。与机器学习相结合方法[8]的基本原理是挖掘评分和内容的隐含关系,在用户或项目的内容信息数据基础之上训练出学习模型,给新用户产生相应的推荐。因为考虑了用户或项目的内容属性信息,第二类方法提高了推荐精度而且改善了冷启动问题,一定程度上缓解了第一类方法中由于信息单一而推荐精度不高的问题。但是在实际应用中,由于隐私问题,获取用户的属性信息存在一定难度,而且对于非结构化的项目,获取内容属性信息也不是一件容易的事情。
针对于以上问题,本文提出了基于项目时效性模型的冷启动解决方法,充分利用评分数据上下文信息,利用系统中过往的点击记录,建立项目的时效性评价模型,在为新用户产生推荐的过程中,选择时效性高的项目推荐给新用户,既充分利用了已有的评分数据信息,又避免了用户的属性信息难以获取的问题。
本文利用评分数据上下文信息构建项目时效性模型,将所有用户对项目的评分记录作为考察集S,把集合S以项目为单位进行子集划分,从而将集合S划分成一系列的子集s。对于项目i,si={t1,t2,t3,…,tk,…,tq},其中q表示系统中对项目i产生过评分行为的用户数,tk表示某用户对项目i产生评分行为的具体时刻,在t时刻项目i的时效性表示为Ci(t)。由于推荐系统中的项目评分等信息属于广义上信息的一种,所以也满足信息价值老化的经典模型[9],如式(1)所示:
其中t表示当前时间,tf表示项目s发布的时间,Cs(t)表示项目在t时刻的时效性大小,a代表的是信息老化率系数。在推荐系统中,本文引入项目的生命周期、半衰期两个概念,以便于更好地描述。项目从发布的时刻tf到项目不再被点击或评论为止的时刻tf+Ta之间的时间段为项目生命周期Ta。项目自发布的时刻tf开始到项目的影响力降为一半的时刻tf+Th之间的时间段为项目的半衰期Th。
公式(1)从数学角度定量地描述了项目在生命周期Ta中的每个时刻的时效性大小,本文设计的冷启动解决算法结合了信息老化的模型,对项目的时效性做如下的定义:
定义1项目s在t时刻的时效性CS(t)为:项目在时间段(t,tf+Ta)内被点击或评论的数量R(t,tf+Ta)与在生命周期Ta内被点击的数量R(Ta)之比,如公式(2)所示。
为了能够由公式(1)快速计算出项目在当前时刻t的时效性大小,须求得系统中的信息老化率系数a,通过公式(1)化简可得:
其中T=t-tf,根据公式(2),首先计算一个项目s在经过时间段T后还拥有的时效性Cs(t)值,然后代入公式(3)得到项目的老化率系数a。我们由公式(2)计算出项目在时刻t拥有的时效性的大小Cs(t),但公式(2)考察的目标是单个项目s,无法表达出整个数据集的统计特性,本文通过公式(4)计算S中的子集s对应T=t-tf的平均值,记为T。
其中|S|为考察集合S中子集的个数,把公式(3)和(4)结合得到公式(5):
在公式(5)中,我们选择Cs(t)=1/2,即T=t-tf实际上是s的半衰期Th,则T为所有项目半衰期的平均值Th,公式(5)简化为:
通过公式(6),得到每个子集s的半衰期Th就计算出了系统中信息老化率系数a。本文有单个项目评分量的集合si={t1,t2,t3,…,tk,…,tq},在其中找出中间的评分时刻tm,则Th=tm-tf,根据公式(6)计算出系统中项目的老化率a。得到老化率a之后利用公式(4)计算出在当前时刻项目i的时效性Ci(T),最后选择时效性最高的TopN个项目推荐给新用户,N由交叉验证确定。
3.1实验数据集
本文采用的实验数据集为明尼苏达大学(University of Minnesota)GroupLens研究院小组的MovieLens (1M)数据集[10],该数据集包含6040名用户对3900部电影的1000209次1~5分的评分数据,每位用户至少对20部电影进行过评分。用户评分表(rating.dat)由用户ID、项目ID、项目评分值与评分时间4个字段构成。本文将数据集随机分为训练集和测试集,其中训练集所占比例为80%,测试集所占的比例为20%。
3.2评价指标
本文采用TopN推荐准确度(precision)作为度量标准,验证本文提出算法的有效性。TopN推荐准确度指取前N个(TopN)推荐给目标用户,根据TopN推荐列表中某个被推荐项目是否出现在了目标用户的测试集中,判断是否生成了一个正确推荐[11],计算公式如(7)式:
其中Ut表示测试集中的用户集合,Ru(N)表示推荐给用户u的项目集合,Tu表示测试集中用户u的项目集合。
3.3实验步骤
为了验证本文提出的基于项目时效性的冷启动解决算法(Timeliness-based Algorithm for Cold Start,TACS)的有效性,将TACS算法和文献[4]中的众数法(Mode-based Algorithm for Cold Start,MACS),以及文献[7]中的概率统计模型解决方法(Probability Statistical Model for Cold Start,PSMCS)进行对比实验。首先在测试集中随机抽取6组不同个数的用户作为新用户,6组取值依次为 100个、200个、300个、500个、700个、1000,然后训练集中对应的用户的评分信息依次置为0。然后分别将TACS算法、MACS算法、PSMCS算法在处理后的训练集和测试集中进行实验,实验结果如表1所示:
表1 对比实验结果
由表1可知,在不同新用户数目情况下,本文提出的TACS算法的准确度均为最高,这说明了TACS算法解决新用户冷启动问题的有效性。同时,随着新用户数目的增加,三个算法的准确度都会下降,这是因为新用户的增加导致了测试集中新用户类别的增加,而三个算法在解决冷启动问题方面都存在一定的局限性,不可能为所有类别的新用户都产生准确的推荐。
冷启动问题是协同过滤推荐算法中一个重要的研究方向,本文提出了基于项目时效性的解决算法,为新用户推荐时效性高的项目,从而缓解新用户冷启动问题,最后的对比实验验证了该算法的有效性。时效性是衡量推荐系统中项目的一个重要属性,但是为了进一步提高为新用户推荐的准确度,可将时效性与用户或项目的内容属性信息相结合,充分利用已知信息解决新用户或新项目的冷启动问题,这也是下一步的研究方向。
[1]XU HL,WU X,LI XD,et al.Comparison Study of Internet Recommendation System[J].Journal of Software,2009,20(2):350-362.
[2]BASILICO J,HOFMANN T.A Joint Framework for Collaborative and Content Filtering[C.ACM SIGIR 2004:2004Association of Computing Machinery and Special Interest Group on Information Retrieval.New York,NY,USA,2004:550-551.
[3]郭艳红.推荐系统的协同过滤算法与应用研究[D].大连:大连理工大学,2008.
[4]Ahn H J.A New Similarity Measure for Collaborative Filtering to Alleviate the New User Cold-Starting Problem[J].Information Sci-ences,2008,178(1):37-51.
[5]孙少华.协同过滤系统的稀疏性与冷启动问题研究[D].杭州:浙江大学,2005.
[6]Balabanovic M,Shoham Y.Fab:Content-base,Collaborative Recommendation[J].Communications of the ACM,1997,40(3):66-72.
[7]Lam X N,Vu T,Le T D,et al.Addressing Cold-Start Problem in Recommendation Systems[C].ICUIMC'08.New York,USA,2008: 208-211.
[8]Park S T,Pennock D M,Madani O,et al.Nave Filterbots for Robust Cold-Start Recommendations[C].KDD'06,2006:699-705.
[9]YIN G,CUI X,MA Z,et al.Web Services Evaluation Model based on Variant Time Utility[J].Journal of Southwest Jiaotong University, 2012,47(4):652-661.
[10]MovieLens 1M Dataset.http://grouplens.org/datasets/movielens/1m/.
[11]Music Recommendation Using Content and Context Information Mining[J].IEEE Intelligent Systems,2010,25(1):16-26.
Recommender System;Collaborative Filtering;Cold Start;Timeliness
Timeliness-Based Algorithm for Cold Start
LIU Jiang-dong1,LIANG Gang1,YANG Jin2
(1.College of Computer Science,Sichuan University,Chengdu 610065;2.College of Computer Science,Leshan Normal University,Leshan 614000)
1007-1423(2016)05-0003-04
10.3969/j.issn.1007-1423.2016.05.001
刘江冬(1989-),男,湖北荆门人,硕士研究生,研究方向为机器学习、推荐系统
梁刚(1976-),男,四川成都人,博士,讲师,研究方向为机器学习、智能计算、网络安全
杨进(1980-),男,四川成都人,博士,讲师,研究方向为机器学习、网络安全
2016-01-07
2016-01-25
在推荐系统研究领域,协同过滤推荐技术是一种重要的技术方法,但新用户和新项目等冷启动问题是该技术方法所面对的一个重要问题。为解决新用户冷启动问题,充分利用评分数据上下文信息,提出一种基于项目时效性模型的解决算法,把时效性高的项目推荐给刚加入系统的新用户,从而缓解新用户冷启动问题。实验结果验证所提出的算法在保证推荐精度的情况下能为新用户产生有效的推荐。
推荐系统;协同过滤;冷启动;时效性
四川省科技厅项目(No.2014JY0036)、四川省教育厅创新团队基金(No.13TD0014)
Collaborative filtering recommendation technology is the most important technology in recommender systems,but the technology is facing new users and new items cold start problem.To solve the new users cold start problem,proposes a solution algorithm based on item timeliness model by making full use of the context information of rating data,and recommends high timeliness items for new users.The experimental results verify that the algorithm proposed produces effective recommendation for new users.