基于项目相似度计算改进的协同过滤算法

[摘 要]本文通过对传统相似度计算的分析,对传统相似度计算进行了改进,试验结果表明本文提出的相似度计算能够极大提高相似度计算的精确性,改善推荐精度.

[关 键 词]电子商务推荐系统协同过滤相似度计算数据挖掘

一、引言

电子商务推荐系统是模拟销售人员向网络客户推荐商品的系统,推荐精度的高低直接影响了用户的购写量,也影响着用户对该系统的信任度,信任程度的高低决定了用户对该系统的使用率,从而影响用户浏览实现了推荐功能的网站进行物品购写的次数.

当前的信息推荐技术主要有：协同过滤推荐、基于内容推荐、基于人口统计信息推荐、基于效用推荐、基于知识推荐、基于规则推荐.

二、协同过滤算法介绍

1.基于项的协同过滤算法介绍

基于项的协同过滤是通过相似度的计算,找出当前用户未评分项目的前k个相似项目,根据用户对这k个项目的评分预测当前用户对未评分项目的评分值,按照评分值大小进行推荐.推荐分为两个步骤:①找出当前用户（这里指系统进行项目推荐的对象）的未评分项目的相似项目,②根据每个未评分项目的相似项目评分预测当前用户对未评分项目的评分,根据预测评分的高低,推荐前N个评分较高的项目给用户.

（1）项目相似度的计算

计算方法主要包括三种方法:

①基于余弦的相似度计算

(1)

其中,表示项目i,j的相似性,和表示对于项目i和j存在有共同用户对此两项评分的分别的评分集合.

实际应用中,该公式存在如下问题：因为,数据稀疏性是协同过滤使用中遇到的一个问题,尤其是推荐系统初次使用时,数据库中的用户评分极其稀少,所以在这种情况下,存在两个项目之间只有1～2个共同的用户,如果这1～2个共同用户对这两个项目的品质认为是无差异的,则用余弦相似性进行计算时得出的结果也是认为两者很相似.事实上,基于项目的协同过滤算法是认为如果绝大多数用户对两项目的感觉是无差异的,则证明这两项目具有相同的品质,那么具有相同品质的两项目对于待推荐用户来说也是无差异的.可是,当两项目只有一两个共同评分用户,项目相似性的计算仅仅是反映了这一两个用户所关注的项目特征在这两个项目中是否相同,而这一两个用户所关注的项目特征并不一定是待推荐用户所关注的特征,并且一两个特征的相似也不能真正反映两个项目之间的相似性.

②基于相关性的相似度计算

(2)

其中,U表示对项目i和j都有评分的用户集合,和分别表示用户u对i与j的评分,和表示集合U中所有用户对i和j评分的平均值.

相关性的相似度计算是将用户对项目i、j的打分看作是一个两个随机变量,通过计算两个随机变量分布的相似性得出两项目的相似性.

③调整余弦的相似度计算

(3）

其与余弦相似性不同在于：将不同用户的打分规模考虑进去,其中表示用户u的平均打分.余弦相似性没有考虑不同用户的打分规模会造成平均打分较高的用户对相似度计算作用大于其余用户,使得每个用户的打分对相似度计算的贡献率不相等,造成相似度计算不如调整余弦相似度的计算精确.

在实际应用中,在数据库中打分数据分布极其稀疏的情况下,调整余弦的相似度的度量也会遇到在余弦相似性计算中所遇到的情况,即当项目只有一两个共同评分用户,项目相似性的计算仅仅是反映了这一两个用户所关注的项目特征在这两个项目中是否相同,而这一两个用户所关注的项目特征并不一定是待推荐用户所关注的特征,并且一两个特征的相似也不能真正反映两个项目之间的相似性.另外,在进行算法精度测试试验中,发现调整余弦的相似度计算有出现分母为0的情况.在程序测试过程中发现,分母为0有两种情况：

a)两项目只有一个共同打分的用户,该用户对很少的项目打分且打分值相同,即且.这种情况,按照余弦相似性的思想,可以认为两项目的相似度值为1.

b)两项目有为数很少的共同评分用户,且出现或的情况.在这种情况下,调整余弦无法正确计算出两项目之间的相似度,因此在数据极其稀疏的条件下,不宜采用调整余弦相似度进行度量.

2.评分预测公式

（1）权重和法

(4）

其中,表示项目i和j的相似度,表示用户u对项目j的评分,n表示选出n个数目的最近邻项目.该预测公式适用于用户评分数目相当大的情况.（基于项目相似度计算经典算法）当用户评分数目较少的情形下,相似度的计算本身就不精确,而该公式对未评分项目的预测,完全依赖于不精确的相似度值选择的相似项目的打分进行预测,精度很低.

（2）线性回归法

目标项目i对应向量为,相似项目N对应向量为,则线性回归模型为(5)

其中,的值由目标向量与相似向量确定,为误差项.

三、基于项目相似度计算改进算法

在第2节中,提到余弦相似度和调整余弦相似度都会碰到的问题：当两项目只有一两个共同评分用户,项目相似性的计算仅仅是反映了这一两个用户所关注的项目特征在这两个项目中是否相同,而这一两个用户所关注的项目特征并不一定是待推荐用户所关注的特征,并且一两个特征的相似也不能真正反映两个项目之间的相似性.

基于上述问题,本节提出了对这两种相似度计算的改进公式.本节认为,两项目分别的评分用户越多,则这两项目的共同评分项目也应该越多,因为一用户对一个项目感兴趣且有打分,则他对该项目的相似项目也应感兴趣且应有打分.基于这种观点,本节对余弦相似度和调整余弦相似度公式进行改进,并用基于改进的余弦相似度公式和传统余弦相似度公式计算项目间相似性来进行实验.由于在第2节中提到在数据稀疏的条件下,调整余弦相似度公式计算中会遇到分母为零的可能,且对调整余弦相似度公式的改进与余弦相似度公式改进方式是相同,故可以认为基于余弦相似度公式和改进公式的对比试验结果可以代表调整余弦改进公式的改进效果.

1.改进的相似度计算公式

（1）改进的余弦相似度计算公式

(6）

其中,mutual_num为对项目i、j都评分的用户数目,item_num表示对项目i、j中任何一个有评分的用户集合的数目.

（2）改进的调整余弦相似度计算

(7)

2.本文提出的对基于项的评分预测的公式

（1）提出的评分预测公式

(8）

其中,为用户u所有评分的平均值,为i和j项目的相似度,n为选择前n个最近邻.当时,令.

（2）说明

①从用户对相似项目评分的相似性考虑,相似项目评分与该用户平均评分的偏差和预测项目的评分与该用户平均评分的偏差也相似.

②与基于向量评分不同在于：基于向量的评分只适合于评分数目十分大的用户,当用户评分数量小时,最相似的几个项目可能用户没有评分,因此导致预测精度降低；另外,当每个项目的评分数量很少时,项目相似性预测精度下降,使得预测精度降低,而本文提出的预测公式可以降低相似项目对预测项目评分的贡献率.

③在计算中若,即当用户u对相似项目j没有评分时,令,消除没评分时,的影响.

实验证明,在数据极其稀疏条件下,本文提出的预测公式有很好的预测效果.

四、实验过程及结果分析

1.数据来源

本文采用Movielens站点提供的数据集,该数据集包括943个用户对1682部电影的100000条评分,评分取值为（1,2,3,4,5）中任一个数,值越大说明用户喜好程度越高,每个用户至少评价了20部电影.

2.测试方法

本文随机抽取其中80000条评分作为训练集,剩余20000条数据作为测试集,分别采用余弦相似性（公式1）和本文提出的改进地余弦相似性（公式6）进行相似度度量,并都采用本文提出的评分预测公式进行预测.

3.评测标准

本文采用平均绝对误差MAE作为评测标准,它是常用的推荐算法质量评价标准.

(9）

num为算法评分项目数目,为基于算法预测的评分,测试集中用户原始打分.

4.试验结果

图

五、结论

从上图可以看到,本文提出的改进算法的精度明显优于传统算法,这证明改进的余弦相似度计算方法比传统余弦相似度算法准确度高,因为它将每个项目的被评分规模考虑进去,排除了传统余弦相似度算法因为某些项目的打分用户数目大导致与其他并非很相似的项目计算结果很相似的可能.图中显示,当最近邻数目为10时,改进算法的精度最高；当最近数目大于10时,随着最近邻数目的增多,预测精度反而降低,从10以后的最近邻的相似度开始降低.在传统算法中,最近邻数目从40到50之间时,预测精度反而上升,这说明最近邻从40到50之间的存在着可能更相似的用户.通过这些对比,证明了本文的改进算法的有效性.