一种改进的基于兴趣相似度推荐算法

柯翔敏,陈 江,罗光华

(华侨大学 网络与教育技术中心,福建 厦门 361021)

0 概述

目前,随着物质生活的不断丰富和科学技术的快速发展,人们的生活方式越来越多样化。推荐算法的发展与运用使得用户能够快速发现自己感兴趣的商品,从而在客观上促进社会经济的发展。

推荐算法可以分为基于内容的推荐[1]、基于协同过滤的推荐[2]以及混合推荐[3]三大类。其中,基于协同过滤的推荐算法应用最为广泛,其又可分为基于用户的系统过滤推荐、基于商品的协同过滤推荐[4]和基于模型的协同过滤推荐[5]。协同过滤推荐算法的思想是基于用户-物品矩阵,如果为目标用户进行推荐,选择与目标用户打分行为相似的Top-K个用户打分过的物品,以及与目标用户打分过的物品相似的Top-K个物品作为推荐候选。协同过滤推荐算法性能最重要的影响因素是相似度的计算方式。

在传统的协同过滤推荐算法中,有余弦相似度、修正余弦相似度等常用的相似度计算方法。但是,由于用户-物品矩阵存在数据稀疏性等问题[6-8],导致上述相似度计算方法存在相似度失真、相似度虚高、相似度难以区分等问题[9],进而造成推荐结果不准确的现象,影响了用户体验。

对于传统协同过滤推荐算法相关度计算问题,一些学者提出了改进方式。文献[10]考虑到传统的相似度计算方法存在的数据稀疏问题,结合一些基础相似度计算方法的优势,将余弦相似度、杰卡德系数等相似度计算结果相结合并进行线性组合从而提高预测精度。文献[11]引入元路径、异构网络的思想计算相似度。文献[12]从3个方面对用户相似度度量计算进行改进,其将用户评分的平均差值引入到用户相似度计算中。文献[13]提出一种信任感知聚类的协同过滤方法。文献[14]针对推荐系统中的数据稀疏性问题,提出一种比率相似度计算方法,该方法在计算用户相似度时考虑2个用户的所有偏好数据而非共同评分项。文献[15]提出一种对协同过滤推荐算法进行改进的“用户项目立方体”模型,该模型将相应的权重加入到时间因子中,然后用相应的权重计算相似度。文献[16]为了降低稀疏性问题对相似度带来的影响,利用LDA模型将高维空间转化为低维空间,同时将相似度计算转向低纬空间,从而降低了计算开销。文献[17]考虑到只有当不同用户对相同项目都有很高的评分值时才能证明两者之间具有很高的相似度,引入相似度改进因子和平衡因子的概念,重新计算相似度并对2个计算后的相似度进行加权处理。文献[18]在局部敏感哈希算法的基础上,提出基于精确欧氏局部敏感哈希的改进协同过滤推荐算法,其通过精确欧氏局部敏感哈希计算用户的相似度,然后对用户进行推荐。

上述改进的相似度计算算法均在一定程度上提高了推荐效果,但是多数算法都忽视了一个问题,即在用户-物品矩阵中,不同物品对相似度的影响是不同的。在生活中存在一种现象,2个对冷门事物感兴趣的人比2个对流行事物感兴趣的人更有可能成为朋友,他们的相似度也更高。就事物本身而言,事物流行程度越低,对其感兴趣的用户的兴趣权重分配值会越高。此外,以往的相似度计算算法同时也忽视了用户之间共同感兴趣的事物数量对用户之间相似度的影响。为此,本文提出一种基于兴趣分配与共同兴趣项的相似度计算方法,并基于此构建一种混合协同过滤推荐模型,以提高推荐质量。

1 问题定义

1.1 逆流行度

定义1(逆流行度) 对于一个用户-物品评分矩阵,物品存在逆流行度的特性,即物品的冷门程度的值位于0～1之间,该值越大表明物品的冷门程度越大。

通过上述定义可知,逆流行度是一个物品冷门程度的标准化值,其与流行度存在一种负相关的关系。现有用户-物品评分矩阵如表1所示,其中,5件物品被打分的次数分别为3、4、7、4、2,该数值即为流行度。

表1 用户-物品评分矩阵Table 1 User-item rating matrix

流行度计算公式如下:

Pop(Itemi)=count(rating(j,i)>0),j∈U

(1)

其中,count为统计计算,U为用户集合。

逆流行度是对物品冷门程度的一种度量方式,通过式(1)得到物品流行度之后,统计全局物品的流行度。对每一件物品进行逆流行度计算,逆流行度的度量方式如下:

(2)

其中,max与min计算可以分别得到物品中最大流行度与最小流行度的值。物品的逆流行度介于0～1之间,值越大,物品的冷门程度越大,其对兴趣的潜在影响也越大。

1.2 共同兴趣项

在一些传统的相似度计算方法中,余弦相似度、修正余弦相似度都是对用户的评分向量进行全量计算,如果2个用户对某项物品均没有评价,则该物品项在两者的评分向量中为0。用户-物品矩阵具有数据稀疏性,如果2个用户评分项较少则可能会有很高的相似度。如果2个用户即使对多数物品进行了评分,并且有许多为共同评分,但是余弦相似度的计算特性也可能会导致两者的评分较低。本文认为如果用户之间的共同评分项越多,他们拥有共同兴趣的概率也就越大,用户之间的相似度理应更高。但是,2个用户对某一事物共同打分不一定代表两者对该事物都有兴趣,在5分为满分的推荐系统中,如果一个用户打5分,另一个用户打1分,则这2个用户对该事物的兴趣差异很大。为此,本文提出共同兴趣项的概念。

定义2(共同兴趣项) 对于一个用户-物品矩阵,如果用户A与用户B均对某一件物品I有评分操作,且A与B对I的评分都超过系统设定的兴趣阈值α,则称物品I为用户A与用户B的共同兴趣项。

2个用户之间的共同兴趣项集合可用式(3)表示:

SA,B={i|rat(A,i)>α}∩{i|rat(B,i)>α}

(3)

其中,rat为评分值。

本文认为用户之间的共同兴趣项越多,且在共同兴趣项中评分方差均值越小,则用户之间的相似度越高。用户的相似度应该通过用户之间有多少共同的相似项来度量,因此,本文基于用户的共同兴趣项提出新的用户相似度计算方法,如下:

(4)

其中,m为用户A、B的共同兴趣项数目,n为用户-物品矩阵中物品的总数,T为一个常数,在式(4)中其为推荐系统中的评分最大值。

2 基于兴趣分配与共同兴趣项的协同过滤推荐

2.1 结合兴趣分配的相关度计算

本文提出逆流行度与共同兴趣项的概念以及相关度计算公式,在共同兴趣项的基础上提出一种新的相关度计算方法,但该方法并未结合逆流行度。本文提出逆流行度是考虑到生活中的“对冷门事物感兴趣的人更可能成为好友,并且相似度更高”这样一种场景。具体而言,对热门事物产生过行为的用户可能并非真正的偏好,也许是受一些社会因素的影响,比如媒体宣传、营销等。但是,如果用户对冷门事物感兴趣,一般是基于用户本人的兴趣偏好而受其他因素干扰较小。基于以上分析,本文在式(4)的基础上结合共同兴趣项的逆流行度进行相关度计算。存在2个用户A、B,计算两者共同兴趣项的逆流行度的平均值,如式(5)所示:

(5)

其中,S为用户A、B的共同兴趣项集。R值越高,表示用户的共同兴趣项流行程度越低,共同兴趣项对兴趣分配的权重越高,受社会化的影响越小,即相似度越高。结合R值,本文提出新的相似度计算公式如下:

(6)

式(6)考虑到了用户共同兴趣的数量以及共同兴趣项对相似度影响的权重,客观合理,本文采用式(6)进行用户之间的相似度度量。

2.2 混合协同过滤模型

通过式(6)可以完成用户相似度计算,利用标准化方法可以将用户相似度限定在0～1范围内,对于目标用户而言,可以生成相似用户的Top-K推荐列表。但是,用户-物品评分矩阵具有稀疏性问题,存在大量打分操作较少的用户,且在评分矩阵中可能会有一些噪声数据。本文为相似用户的共同兴趣项设定一个阈值,即当用户之间的共同兴趣项数量大于某阈值β时,用户之间的相似度计算才有意义。如果只有少数共同兴趣项则会存在一些不确定性,从而导致推荐结果不正确。因此,对于目标用户A而言,其相似用户列表为:

simUserList(A)={B|count(SA,B)>β}

(7)

如果2个用户的共同兴趣项数目小于β值,则其用户相似度为0。

通过式(7)可以得到每一个用户的相似用户列表。此时会出现如下情况:一部分用户会有较多的相似用户,另外一部分用户有较少的相似用户,还有用户的相似用户列表甚至为空。对于此现象,本文提出一种混合协同过滤模型,具体如下:

1)对于第1种用户,他们存在较多的相似用户,因此,采用基于用户的协同过滤模型,本文设置阈值为K。当相似用户的数量大于K时,直接选取相似度排名靠前的前K个用户作为候选推荐用户,将相似用户有过评分操作且目标用户没有评分操作的事物按照均分与相似度的综合进行排序,选取前N个事物形成推荐列表返回给目标用户。

2)对于第2种用户,其相似用户数量小于K且大于0,本文仍然采用基于用户的协同过滤模型,但是要进行二次发掘来获取更多的相似用户,即与目标用户相似的用户的相似用户也可能与目标用户相似,如图1所示。

图1 相似用户二次发掘示意图Fig.1 Schematic diagram of similar users’ secondary excavation

在目标用户的相似用户列表中引入相似用户的相似用户,如式(8)所示:

simUserList(A)=simUserList(A)∩simUserList(B)

(8)

其中,B是A的相似用户。

对于通过二次发掘进入目标用户相似用户列表的用户,其与目标用户也有相似度的度量,如式(9)所示:

(9)

其中,n为Sim(B,C)>0的数量。

在完成二次用户的二次发掘之后,即可采用第1种方式对用户进行推荐。

3)针对第3种用户,其没有相似用户。本文从2个方面对该类用户进行分析,如果他们之间存在较多的兴趣项,则采用基于物品的协同过滤模型进行推荐;如果他们之间有很少的兴趣项或者没有兴趣项,则按照冷启动的方式进行处理,可以选择一些流行度高且评价较好的物品进行推荐。

对于每一个用户,混合协同过滤推荐模型流程如图2所示。

图2 混合协同过滤推荐模型流程Fig.2 Procedure of hybrid collaborative filtering recommendation model

本文混合协同过滤推荐算法伪代码如下:

算法1混合协同过滤推荐算法

输入用户集合U,物品集合I,相似用户列表阈值K,共同兴趣项过滤阈值β,兴趣阈值α

1.begin

2.for each u in U:

3.simUserList(u)={}

4.recommendList(u)={}

5.for each u′ in U:

6.if u≠u′:

7.S(u,u′)={}

8.For i in I:

9.if rat(u,i)>α and rat(u′,i)>α:

10.S(u.u′).add(i)

11.if len(S(u,u′))>β:

12.simUserList(u).add([u′,Sim(u,u′)])

13.simUserList.sortBySim() //按相似度进行排序

14.if count(simuserList(u))≥K:

15.recommentList(u)=recommendByUser(simUserList(u))

16.elif count(simUserList(u))0:

17.for [u1,Sim(u,u1)] insimUserList(u):

18.simUserList(u)=simUserList(u)∩simUserList(u1)

19.recommentList(u)=recommendByUser(simUserList(u))

20.else:

21.recommentList(u) =recommendByItem(simUserList(u))

22.end

3 实验结果与分析

3.1 数据集与实验环境

本文选取推荐算法领域中的经典数据集MovieLens,原始数据集中包含用户信息数据(User)、电影信息数据(Movie)与电影评价数据(Rating),本文实验只选取电影评价数据集,大小约为21M,数据集基本信息如表2所示。

表2 MovieLens数据集信息Table 2 MovieLens dataset information

从表2可以看出,该数据集的稀疏程度为95.53%,稀疏程度较高。用户的打分情况与电影被打分情况分别如图3、图4所示。

图3 用户打分统计Fig.3 User scoring statistics

图4 电影得分统计Fig.4 Movie score statistics

从图3、图4可以看出,该数据集中用户的评分情况与电影的得分情况均符合长尾分布,数据集中存在大量的“冷数据”。其中,评分操作高于电影总量10%的用户约占用户总数的10%,如果仅以改进的基于用户的协同过滤推荐模型进行推荐,可预见存在一些用户列表为空的用户。因此,本文提出的混合协同过滤推荐模型具有现实意义。

本文实验环境设置如下:操作系统为Windows7 64位系统旗舰版,CPU为Intel®CoreTMi5-7500 3.40 GHz,内存为8 GB。

3.2 实验评价指标

推荐算法的目的是向用户推荐其可能感兴趣的事物,而非预测用户会对事物如何评分[19-20],基于此思想,本文采用Top-N推荐方法,而不采用RMSE、MAE等基于回归模型的评价指标,从而为用户生成推荐列表。本文将精确率(precision)、召回率(recall)与F1值作为实验评价指标,3个评价指标的计算公式分别如下:

(10)

(11)

(12)

其中,U为用户集合,Ru表示对用户u的推荐列表,Iu表示目标用户喜爱的物品集合,用户感兴趣的评价标准可由前文中共同兴趣项的分数阈值表示。

以MovieLens数据集为例,精确率表示推荐成功的电影占推荐电影总数的比例,召回率表示推荐成功的电影占用户感兴趣的电影的比例。

3.3 结果分析

本文将数据集分为训练集与测试集,因为评分数据集中存在时间戳特征,鉴于推荐算法的时间特性,即用户对物品的兴趣值受时间影响,本文将训练集与测试集按时间划分,时间靠前的前80%数据为训练数据,余下为测试数据。实验中采用的对比算法为3种协同过滤算法,分别记为Cosin、Corrcosin和Pearson,三者分别采用余弦相似度、修正余弦相似度和皮尔逊系数进行相似度计算,将本文相似度计算方法记为New。

1)相同参数下不同推荐算法的比较

本次实验比较推荐列表数目为20、每个用户的相似用户列表K值为20时各算法的性能,实验计算每批次500个用户的精确率与召回率,共取10个批次的平均值作为评价指标结果。从图5可以看出,本文混合协同过滤推荐算法的精确率、召回率与F1值3个评估指标均优于其他3种基线算法,基于修正余弦相似度的推荐算法效果最差。

图5 不同推荐算法的评估指标结果Fig.5 Evaluation index results of different recommendation algorithms

2)不同参数对推荐算法的影响

(1)推荐列表长度N。本次实验比较最相似用户的K值一定时(本实验中K=20)推荐列表长度对推荐效果的影响。实验进行10个批次,每个批次随机选择500个目标用户,每个批次对用户的推荐列表长度以增量为5进行划分。

从图6可以看出,随着推荐列表长度的增加,精确率总体比较平稳,在N<35时,精确率有一定的提升,但N超过35之后,精确率开始下降,其他2个指标在N取5～50值时都有相对较高的提升,特别是F1值,其在N值为5～40时与推荐列表长度呈正相关关系。在图7中,本文比较不同的推荐列表长度下4种协同过滤推荐算法的F1值大小。从图7可以看出,在推荐列表长度为5～15时,不同相似度计算算法的推荐效果几乎相同,当推荐列表长度增加后,本文相似度计算算法的F1值优于对比推荐算法,并且随着推荐列表长度的进一步增加,本文相似度计算算法与修正余弦相似度计算算法明显优于其他2种相似度计算算法。

图6 推荐列表长度对推荐效果的影响Fig.6 Effect of recommendation list length on recommendation effect

图7 4种相似度计算算法在不同列表长度下的F1值Fig.7 F1 values of four similarity calculation algorithms under different list lengths

(2)最相似用户列表长度K。在推荐列表长度一定时,分析最相似用户列表长度对推荐效果的影响。实验过程同样进行10个批次,每个批次随机选择500个目标用户,每个批次对用户的推荐列表长度以增量为5进行划分。在推荐列表长度为定值的情况下,不同的相似用户列表长度对推荐结果的影响较小。由图8可以看出,精确率、召回率与F1值3条曲线变化比较平稳。在K=25时,3个评估指标均达到最大。然后,随着K值的增大,3个指标均有所下降,不过整体变化不大。综上,推荐列表长度对推荐结果的影响大于最相似用户列表长度。

图8 最相似用户列表长度对推荐效果的影响Fig.8 Influence of the length of the most similar user list on the recommendation effect

3.4 算法性能分析

比较本文相似度计算算法与其他相似度计算算法在同样硬件条件与实验参数下,计算不同量级用户之间相似度所消耗的时间,10次实验的平均结果如表3所示。从表3可以看出,本文相似度计算算法计算效率最高,其次是Cosin和Pearson算法,两者时间开销基本一致,时间开销最大的是Corrcosin算法,大约为本文算法的20倍。本文相似度计算算法在时间性能上有较大优势,原因是本文算法设置一个共同兴趣项的阈值,用户达到阈值后会被认为是好友,一个用户的好友列表平均值肯定小于其他相似度计算算法。在基线相似度计算算法中,用户列表会考虑全部用户并进行排序,用户相似度的排序会消耗大量时间。

表3 相似度计算算法时间性能比较Table 3 Time performance comparison of similarity calculation algorithms s

4 结束语

本文针对基于协同过滤的推荐模型中原有相似度计算方法存在一定失真性的问题,结合事物流行度对用户兴趣权重分配与用户共同偏好事物数目的影响,设计一种新的用户相似度计算方法,并在该方法的基础上构建一种混合协同过滤推荐模型。实验结果表明,该模型的推荐效果优于基于基线相似度计算方法的推荐模型。下一步将针对用户推荐时的数据稀疏性与冷启动问题,结合更多影响相似度的潜在因素来提高推荐效果,并优化推荐算法的多样性与覆盖率等其他指标。此外,协同过滤推荐算法普遍存在复杂度较高的问题,且本文混合推荐模型涉及较多的参数,因此,进行高效调参调优以降低算法复杂度也是今后的研究重点。