叶锡君,龚 玥
(南京农业大学信息科技学院,南京 210095)
基于项目类别的协同过滤推荐算法多样性研究
叶锡君,龚 玥
(南京农业大学信息科技学院,南京 210095)
推荐系统的多样性正日益成为评价推荐质量的重要指标。为提高传统协同过滤推荐算法的个体多样性,在基于项目的协同过滤推荐算法的基础上,加入项目的类别属性信息,定义项目类别贡献函数以改进预测评分公式,提高与目标项目类别不完全相同的项目得分,实现最优项目推荐。实验结果表明,在保证一定推荐精确度的前提下,改进算法增强了推荐系统的个体多样性,具有更高的推荐质量。
协同过滤;多样性;项目类别;贡献函数;预测评分;列表内相似度指标
DO I:10.3969/j.issn.1000-3428.2015.10.009
信息化社会的到来给人们带来了一大难题:如何从丰富的网络资源中快速准确地找到自己需要的信息。传统搜索引擎技术的智能化程度较低,且以被动方式为用户提供服务,已不能满足用户需求,为了更好地解决这一难题,推荐系统应运而生。推荐系统的核心是推荐算法。目前,推荐算法并没有一个统一的分类,大多数学者将推荐算法分为3类:基于内容的推荐算法,协同过滤推荐算法以及混合推荐算法。协同过滤推荐算法是目前应用最广泛且最成功的推荐算法,特别是在电子商务领域。
目前,对协同过滤推荐算法的研究主要集中于解决数据稀疏性、冷启动、概念漂移和可扩展等问题,经过长期研究,学者们提出了多种解决方案,并从理论和实验上得到了证明。然而新的问题也不断涌出,例如推荐多样性程度低、推荐系统脆弱以及推荐系统评估效果不理想等。推荐系统的多样性正日益成为评价推荐系统推荐质量的重要度量指标。文献[1]指出在MovieLens电影数据集上实施标准协同过滤算法时,只有15%的电影会获得推荐机会,其中最热门的电影会被推荐给高达 70%的用户。2014年3月,阿里巴巴举行了大数据竞赛,比赛内容
为基于天猫海量真实用户访问数据的推荐算法。参加比赛过程中,参赛者发现热门商品几乎出现在了80%用户的推荐列表中。除热门商品影响外,推荐系统还存在另外一种多样性程度低的推荐问题,例如某用户在某购物网站搜索了某种产品,接下来他将会在各种推荐中看到此类商品的推荐。本文将针对推荐多样性程度低的问题,在基于项目的协同过滤算法基础上,加入对项目类别属性,对推荐算法进行改进,提高推荐多样性。
2.1 算法描述
基于项目的协同过滤推荐算法的思想是根据用户对项目的评分,计算出项目间的相似度,然后为每个用户未评分的项目构造最近邻,通过用户对最近邻的评分预测出对未评分项目的评分[2],最后将得分最高的前N项项目推荐给用户。N值可根据需要自由设定,协同过滤推荐流程[3]如图 1所示。
图1 协同过滤推荐流程
根据推荐流程,推荐主要分为3个步骤:
步骤1 数据描述。基于项目的协同过滤推荐算法的数据通常描述为一个用户-项目评分矩阵R:其中,rij表示用户i对项目j的评分,评价值及单位与具体场景有关,可根据实际情况设定。
步骤2 获得最近邻。基于项目的协同过滤算法的关键步骤在于计算项目间的相似度,找出最相似项目集[4]。传统相似度计算方法有以下 3种:余弦相似度,修正的余弦相似度以及相关相似度(也称为Pearson相关系数)[5]。
(1)余弦相似度:在用户-项目评分矩阵R中,将项目评分看成是m维用户空间上的向量,然后用向量间的夹角度量两项目的相似度,角度越小也即余弦值越大,说明相似度越高。项目i和项目j的余弦相似度计算如下:
其中,rui表示用户u对项目i的评分。未得到评分的项目评分值设置为0。
(2)修正的余弦相似度:在余弦相似度的基础上考虑各项目被评价的标准问题,通过减去各项目被评分的平均值弥补余弦相似度的缺陷[6],具体计算如下:
其中,Uij为项目i与项目j被共同评分的用户集合;分别为项目i、项目j被评分的用户集合表
(3)相关相似度:项目i和项目j的相关相似度计算如下:
其中,Uij为项目i与项目j被共同评分的用户集合。
当数据稀疏时,不同项目被同一个用户共同评过分的情况将很少,这时修正的余弦相似度和相关相似度将难以发挥作用,相关相似度计算公式甚至可能出现分母为0的情况,导致计算无意义。所以,在计算相似度时,需要根据实际数据情况选取合适的公式。
步骤3 实现推荐。常用方法是运用平均加权策略计算目标用户对不同项目的预测评分。然后选取评分值最高的前N项(TOP-N推荐策略)推荐给用户。用户u对项目i的预测评分的计算如下:
其中,I表示项目i的最近邻项目集合。
2.2 现有协同过滤推荐算法研究
通过对已有文献的研究发现,2013年前大多数学者对推荐算法的研究主要集中在数据稀疏性、冷启动、概念漂移等问题上,算法研究已经达到比较成熟的阶段。然而,周涛[7]在 2012年提出了个性化推荐系统面临的十大挑战,除了前面提到的问题,
推荐系统还面临多样性程度低、推荐系统脆弱性、系统效果评估等问题[8]。目前的推荐系统是基于用户的历史行为,通过计算被打分项目的相似度进行推荐,从而导致热门项目对推荐产生的影响越来越大,这种推荐虽能达到较好的准确率,但从长远看,热门项目会占满所有用户的推荐列表,使得推荐系统变得毫无意义,推荐列表成为排行榜的复制品[9]。而一个好的推荐系统应该为不同用户提供个性化的推荐,为用户找到潜在的兴趣,同时为服务提供商提供额外收益。因此,推荐系统的多样性变得尤为重要。在此给出多个多样性比精确率更重要的应用场景,例如:当被推荐的商品有“长期消耗品”或“周期性消耗品”或“体验性商品”等特点时,当用户选择该类商品后,可能短期内或永久都不会再有选择它们的欲望,这时多样性的推荐甚至能提高推荐的精确率,这类商品有家具、月饼、旅游地点等。当被推荐的商品受时间影响价值会发生变化时,对于提供下载或租赁这类商品的商家,多样性推荐可以通过推荐一些非热门的商品降低商家的成本,这类商品有电影、小说、音乐等,对于这类商品通常用户的兴趣不会仅限于一二种类型,多样性推荐十分必要。以一个学术文献推荐系统为例,假设系统推荐的是同一个作者的论文,即使准确性很高,用户可能也会认为这是一次很差的推荐,因为用户很容易通过其他方式找到这些论文[10]。由此可以看出,多样性推荐能为服务提供商获得更多的收益,为用户提供更好的用户体验,提高用户的置信度。
近年来,越来越多的学者开始关注推荐系统的推荐多样性问题。文献[11]提出一种能够提高会话推荐多样性的融合协同过滤算法,在用户会话期内建立会话推荐列表,有效避免会话推荐树中出现推荐环路,从而消除重复推荐。文献[12]提出集合多样性的概念,通过增设预测评分的阈值来改变原有的推荐排序方法,以提高整体推荐的多样性。文献[13]提出时间多样性的概念,强调随着时间的推移,推荐系统对用户推荐应呈现多样性。
上述提高推荐多样性的方法要么是从推荐想要达到的效果出发,要么是从影响推荐多样性的外在原因出发改进算法,忽略了导致推荐多样性低的根本原因。本文结合基于项目的协同过滤算法,通过在项目的原始信息中分析协同过滤推荐过程中导致多样性低的原因,从根本上进行改进,提高推荐的多样性。
3.1 算法设计思想
本文研究目的在于提高推荐多样性,多样性分为个体多样性和总体多样性,个体多样性又可分为个体内部多样性和个体外部多样性。个体内部多样性是指在对单个用户的一次推荐中,推荐列表内部项目之间具有多样性。个体外部多样性是指在对多个用户的推荐中,多个用户的推荐列表之间具有多样性[11]。总体多样性是对全体用户而言,系统所产生的全部推荐项目所表现的多样性[14]。总体多样性可以通过个体外部多样性来体现。个体外部多样性越大,则总体多样性也越大[11]。由于推荐系统大多数为个性化推荐,即为每个不同用户提供不同推荐,因此本文关注的多样性为个体多样性。
推荐算法的关键在于相似度计算,余弦相似度在数学上用来考虑两向量的方向,应用到推荐算法中,用来计算用户的相似度,表现为用户兴趣的相似程度;用来计算项目的相似度,表现为项目特征的相似程度。而项目特征通常可以通过项目的类别体现,因此,联想到在传统的推荐算法上考虑项目类别属性的影响,通过推荐与用户喜欢的项目类别较相似的项目来提高推荐的多样性。
传统的协同过滤算法并不涉及用户或项目的具体特征,输入值只有用户-项目评分矩阵,而通过上文分析,基于项目的推荐是将与用户喜欢的项目相似度最高的项目推荐给用户,这样推荐的项目通常为一种项目或者是与用户喜欢的项目相同的项目,也即项目的特征是高度一致的,这就导致推荐多样性程度很低。因此,可以借助项目的类别属性信息,提高具有较相似而不完全相似类别属性的项目被推荐的可能,使得它们能被推荐给用户,从而提高推荐的多样性。在这个过程中,由于依然是根据相似度进行推荐,因此推荐的精确度也不会很低。由于改进算法使用了项目属性信息,因此本文的改进算法也可以看作是结合基于内容的推荐算法和协同过滤推荐算法的混合推荐算法。
定义1(项目类别贡献函数) 对于项目 i的最近邻项目j,项目j的类别贡献函数f(j)=n/N,其中,n表示两项目共有的类别属性个数;N表示项目i的类别属性总个数。分析可知,f(j)=1的情况有2种:(1)项目 i和项目 j的类别属性完全相同,根据改进算法的思想,需要降低这种项目被推荐的可能,因此在贡献函数中引入惩罚因子 α。当f(j)=1时,0<α<1,当f(j)<1时,α=1。(2)项目j的类别属性个数大于项目i的属性个数,这时它们的类别属性不完全相同,为与第(1)种情况相区分,在这种情况下,定义 f(j)=n/N′,其中,n表示两项目共有的类别属性个数;N′表示项目j的类别属性总个数。
定义2(综合预测评分) 项目 i和项目 j的综
合预测评分公式具体如下:
其中,α为定义1中的惩罚因子,用来降低与目标项目类别完全相同的项目的预测评分;f(j)为项目j对项目i的项目类别贡献函数。
3.2 算法步骤
根据上述分析和定义,改进算法步骤具体如下:
(1)根据用户-项目评分矩阵,利用式(2)计算出目标项目与其他各项目的相似度;
(2)根据相似度计算目标项目的K最近邻;
(3)根据定义1计算最近邻中各项目对目标项目的项目类别贡献函数;
(4)根据定义2,利用式(6)计算出用户对目标项目的综合预测评分;
(5)用TOP-N推荐策略将前N项得分最高的项目推荐给用户。
3.3 算法分析
本文算法的改进目的是为了提高推荐算法的个体多样性,其具体策略是使得与用户最喜欢的项目的类别属性相似度高但并不完全相同的项目得到更多推荐,因此,在改进时需要降低类别属性完全相同的项目相似度,以及类别属性差距过大的项目的相似度。
根据定义1可知,当最近邻项目与目标项目的共有属性个数越多时,贡献函数值越大,即与目标项目类别属性相似度越大的项目被推荐的概率越大。通过将定义1中的惩罚因子 α取一个0~1之间的数来降低项目的预测评分,从而降低与目标项目类别属性完全相同的项目被推荐的可能性。目前,如何平衡精确性和多样性还没有一个统一的标准,考虑到不同应用场合的需求,可以通过设置一个变量的具体取值来调控两者之间的关系。本文α的取值将会平衡推荐的多样性与精确性。当对推荐的精确性要求较高时,α可以取1,而当对精确性要求不高时,可通过调整α的取值来适当降低推荐的精确性、提高推荐的多样性。
4.1 实验数据及评价指标
目前提供给学术界用于推荐系统测试的数据不多,大多数学者都采用MovieLens[15]数据集进行实验。本文实验也选取该网站提供的数据集。该数据集是由明尼苏达大学计算机科学与工程系的GroupLens小组提供并维护,记录了用户对电影的评分,评分值一共分为5个等级,1表示最不喜欢,5表示最喜欢。目前它提供了 3个不同大小的数据集供实验使用,分别是包含1×105条、1×106条和1×107条评分数据的数据集,每个用户都至少对20部电影进行了评价。本文实验选取1×105条数据集进行实验,共有943个用户对1 682部电影进行评价。
对推荐算法的评价是推荐算法研究中的重要组成部分,然而,由于推荐系统的研究和应用领域十分广泛,推荐算法的评价缺乏统一性,不同应用环境对推荐算法的要求也存在很大差别,因此在选择评价指标时要综合考虑实验数据的特征以及算法改进两方面。
现有提出的评价指标基本是针对精确性的,本文实验的目的是提高推荐多样性,此方向的研究相对较少,大多数研究者在对改进算法进行评价时都是提出各自的多样性评价指标,而这些指标尚未得到广泛认可和使用。文献[16]阐述了推荐系统精确性和精确性外的评价指标的研究进展,提出平均海明距离来度量推荐系统的多样性,并且总结了现有推荐系统多样性的主要度量指标。根据本文研究目的,实验将选取列表内相似度(Intra-list Similarity,ILS)[16]来评价推荐算法的多样性,并选用精确率P来评价推荐算法的精确性。
列表内相似度主要指针对单个用户,推荐列表中所有项目的平均两两相似度[17-18]。一般来说,ILS值越大,推荐列表多样性效果越差[16]。ILS计算公式具体如下:
其中,R表示推荐列表中推荐项目的集合;i和j是推荐列表中的项目;k是推荐项目的个数。精确率 P的计算公式具体如下:
其中,Nrt表示推荐项目集合与用户真实选择项目集合的交集个数;Nr表示推荐项目的个数。
4.2 结果分析
考虑到数据稀疏性问题,本文实验选取余弦相似度计算项目相似度,实验共涉及传统的基于项目的协同过滤推荐算法和本文改进的加入项目类别贡献函数进行推荐的协同过滤算法。虽然本文改进了推荐算法的多样性,并且多样性与精确性是一对矛盾的概念,但实验依然关注精确性,力求在保证一定精确性的前提下改进算法多样性。关于惩罚因子的取值,分别取0.4,0.5,0.6,0.7,0.8进行实验,发现当α取0.5时,改进算法的P值最大,因此实验中α取0.5。精确性实验结果如图2所示。
图2 推荐算法精确性比较
从图2可以看出,2种算法在最近邻数递增时,呈现先上升后下降的趋势,这是由于用户所看电影一般都不会只是一种或少数几种类别,当最近邻取值增大时,更多类别的项目打分将会影响最终的预测评分,这时推荐效果会更好,而当最近邻数大于一定值时,由于影响最终评分的项目太多,其中很多可能是无用的,导致推荐效果不理想。从图2中还可以看出,当k=20时,算法精确性最高,因此在多样性实验中,最近邻的值取20。
多样性实验结果如图3所示,可以看出,无论推荐个数是多少,传统协同过滤算法的ILS值都大于改进后的 ILS值,即改进算法提高了推荐多样性。随着推荐个数的增加,ILS值不断变小,这是由于越来越多的项目被推荐导致。实验结果表明,改进算法在提高推荐多样性的同时降低了精确性,但由图2可知,精确性差距并不大。该结果与实验前的预期结果相吻合,即多样性得到提高的同时,精确率稍有降低,这是因为改进的协同过滤算法仍是根据相似度进行推荐,所以精确率不会有大幅下降。
图3 推荐算法多样性比较
目前,到底是多样性提高获得的收益大,还是精确率下降带来的损失大还没有明确的结果,这个问题的难点在于学术界没有符合条件的实验环境,也无法获得多样性比精确率更重要的场景下的收益情况。然而,从文献[13,19-20]以及上述实验中可以得出以下规律:在精确率降低较小的情况下,通常可以得到大幅提高多样性。以文献[19]中的实验结果做具体说明,因为该文献中用到的实验数据集之一是Netflix提供的数据集,在2.2节提到的多样性比精确率更重要的应用场景中,Netflix类似的电影租赁商符合该应用场景。文献[19]给出了5种算法的多样性提高以及精确率损失情况,列出当精确率降低0.1%~10%时,多样性提高比例。以精确率降低0.1%为例,多样性提高最小的一组实验结果为,当精确率降低0.1%时,多样性提高7.3%;多样性提高最大的一组实验结果为,当精确率降低0.1%时,多样性提高20.1%。这种多样化的推荐结果能够鼓励用户去租赁“长尾”类型的电影(即位于销售分布尾部的冷门电影),而此类电影相对新发行或热门电影通常只需支付更少的版权费用,从而可提高商家收益。
本文通过原始信息分析推荐系统多样性低的原因,考虑到项目属性可以区分同类项目,提出在传统协同过滤推荐算法中加入项目属性信息进行推荐的改进算法。实验结果证明,改进算法提高了推荐多样性,但精确率稍有降低,然而目前没有明确的结论证明多样性提高带来的收益大于精确率下降带来的损失,同时在实验过程中,因为数据量大导致实验时间较长,对计算机硬件要求也较高。并且考虑到大数据时代的到来,将改进算法应用于大数据环境,解决精确性和多样性相互制约的矛盾问题以及寻找符合条件的实验环境来论述多样性提高对算法的影响,是下一步研究的主要方向。
[1] Zhou Tao,Kuscsik Z,Liu Jianguo.Solving the Apparent Diversity-accuracy Dilemma of Recommender Systems[J]. Proceedings of National Academy of Sciences of the United States of America,2010,107(10):4511-4515.
[2] 刘建国.周 涛.汪秉宏.个性化推荐系统的研究进展[J].自然科学进展,2009,19(1):1-15.
[3] 叶锡君,曹 萍.ASUCF:基于平均相似度的协同过滤推荐算法[J].计算机工程与设计,2014,35(12):61-67.
[4] 韦素云,业 宁,吉根林,等.基于项目类别和兴趣度的协同过滤推荐算法[J].南京大学学报,2013,49(2):142-149.
[5] 杨 博,赵鹏飞.推荐算法综述[J].山西大学学报,2011,34(3):337-350.
[6] 邓爱林,朱扬勇,施伯乐.基于项目评分预测的协同过滤推荐算法[J].软件学报,2003,14(9):1621-1628.
[7] 周 涛.个性化推荐的十大挑战[J].中国计算机学会通讯,2012,8(7):48-61.
[8] Lv Linyuan,Medo M,Yeung Chi-Ho,et al.Recommender System[J].Physics Reports,2012,519(1):1-49.[9] 黄杜鹃.基于多样性的社会化推荐系统研究与实现[D].成都:电子科技大学,2012.
[10] 安 维,刘启华,张李义.个性化推荐系统的多样性研究进展[J].图书情报工作,2013,57(20):127-135.
[11] 李晶皎,孙丽梅,王 骄.Web-based推荐系统中的会话推荐多样性研究[J].小型微型计算机系统,2014,35(6):1265-1269.
[12] Gediminas A,Young O K.Improving Aggregate Recommendation Diversity Using Ranking-based Techniques[J].IEEE Transactions on Know ledge and Data Engineering,2011,24(5):896-911.
[13] Neal L,Stephen H,Licia C,et al.Temporal Diversity in Recommender Systems[C]//Proceedings of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval.New York,USA:ACM Press,2010:210-217.
[14] 岳可诚.个性化推荐技术的多样性研究[D].合肥:安徽大学,2013.
[15] Grouplens[EB/OL].[2014-04-15].http://grouplens. org/datasets/movielens/.
[16] 刘建国,周 涛,郭 强,等.个性化推荐系统评价方法综述[J].复杂系统与复杂性科学,2009,6(3):1-10.
[17] Zhang Mi,Hurley N.Avoiding Monotony:Improving the Diversity of Recommendation Lists[C]//Proceedings of ACM Conference on Recommender Systems.New York,USA:ACM Press,2008:123-130.
[18] Ziegler C N,Lausen G.Making Product Recommendations More Diverse[J].IEEE Data Engineering Bulletin,2009,32(4):23-32.
[19] Adomavicius Y K.Toward More Diverse Recommendations:Item Re-ranking Methods for Recommender Systems[C]//Proceedings of the 19th Workshop on Information Technologies and System s.Berlin,Germ any:Springer,2009:3-10.
[20] Chen Jinpeng,Liu Yu,Hu Jun,et al.A Novel Framework for Improving Recommender Diversity[M]//Cao Longbing,Motoda H,Srivastava J,et al. Behavior and Social Computing.Berlin,Germany:Springer,2013:129-138.
编辑 陆燕菲
Study on Diversity of Collaborative Filtering Recommendation Algorithm Based on Item Category
YE Xijun,GONG Yue
(School of Information Science and Technology,Nanjing Agricultural University,Nanjing 210095,China)
Diversity of recommendation system becomes an important index of evaluating the quality of the recommendation.To improve the individual diversity of traditional collaborative filtering recommendation algorithm,the improved algorithm is based on item-based collaborative filtering recommendation algorithm,which adds item category information and defines a contribution function to optimize the formula of prediction score.It increases the item s scores which have not exactly the same item category with the objective item,and achieves the best item s recommendation. Experimental result proves the improved algorithm strengthens the individual diversity of recommendion system which at the same time keeps a high precision.As a result,it has a higher quality of recommendation.
collaborative filtering;diversity;item category;contribution function;prediction score;Intra-list Similarity(ILS)index
叶锡君,龚 玥.基于项目类别的协同过滤推荐算法多样性研究[J].计算机工程,2015,41(10):42-46,52.
英文引用格式:Ye Xijun,Gong Yue.Study on Diversity of Collaborative Filtering Recommendation Algorithm Based on Item Category[J].Computer Engineering,2015,41(10):42-46,52.
1000-3428(2015)10-0042-05
A
TP391
国家自然科学基金资助项目(61403205);江苏省高等教育教改研究基金资助项目(2013JSJG195)。
叶锡君(1964-),男,副教授、博士,主研方向:数据挖掘,知识发现,生物信息学;龚 玥,硕士研究生。
2014-09-17
2014-11-27E-m ail:yexj@njau.edu.cn