基于可信相似度的协同过滤算法

江南　罗军

摘 要： 传统协同过滤算法在计算相似度的时候，未考虑数据稀疏性以及项目类型相似程度，从而影响推荐质量。为了提高推荐精度，提出一种基于可信相似度的协同过滤算法。首先计算项目类型的相似程度与共同评分用户数和所有评分用户数之间的比例，然后根据类型相似程度和共同评分项的比例进行有机结合，计算相似可信度，形成合理的项目可信相似度。实验结果表明，该算法能够有效的提高推荐质量。

关键词： 推荐系统； 协同过滤； 相似度； 可信度

中图分类号：TP301 文献标志码：A 文章编号：1006-8228（2015）04-23-04

Abstract： Traditional collaborative filtering algorithms do not consider the sparsity of the data and the similarity of the item's type. As a result， the systems may not recommend satisfactory items. To improve the recommendation precision， this paper proposes an algorithm based on the trustworthiness of similarity. First， it calculates similarity of item's type and the ratio between common rating user and all user that rated. Then， creating a reasonable item similarity based on the trustworthiness which dynamically combined by the type similarity and the ratio， and finally realize user rating recommendation. The experiment results show that the proposed algorithm can efficiently improve the recommendation quality.

Key words： recommendation system； collaborative filtering； similarity； trustworthiness

0 引言

随着互联网技术的飞速发展，信息分享与获取变得更加容易，丰富多彩的信息改变了人们的生活方式。然而，海量信息的蜂拥而至，也带来数据和信息的指数级增长，人们渐渐迷失在信息的海洋中。搜索引擎的出现缓解了信息过载问题，但是需要用户有明确的需求，如何智能的挖掘用户潜在的个性化信息进而进行信息过滤成为研究的热点，推荐系统由此而生。

推荐系统建立在信息检索和信息过滤的基础之上，是个性化推荐的重要实现形式。推荐算法可以分为基于内容的算法、协同过滤算法和基于模型的算法。协同过滤推荐算法已经成为迄今为止应用最成功的个性化推荐技术之一[1]。其基本思想是相似的用户之间具有相似的兴趣爱好，只要找到目标用户的邻居用户，就可以通过邻居用户对目标用户的偏好进行预测。

经过20多年的发展，协同过滤推荐技术已经被广泛使用，进入我们的日常生活，带来了巨大的商业和社会价值。然而，随着应用范围的扩大和信息量的不断增大，协同过滤算法的一些弊端开始显现，如冷启动问题、稀疏性问题、可扩展性问题、推荐精度低等，为此学者进行了广泛而深入的研究。文献[2]通过引入基于时间的数据权重和基于资源相似度的数据权重，使得推荐系统能够在一定程度上反映用户的兴趣变化。文献[3]使用正则化约束来防止矩阵分解模型的过度拟合，并通过迭代最小二乘法来训练分解模型，改进后的算法在可扩展性和抗稀疏性方面都取得了一定的效果。文献[4]提出一种基于情景的协同过滤推荐算法，通过引入项目情景模式相似度提高了协同过滤算法的推荐质量。文献[5]提出一种新的协同过滤评分矩阵的特征指标“资源关系密度”，进而提出一种虚拟用户填充算法，提高了推荐精度和覆盖率。针对冷启动问题，文献[6]运用基于内容预测的方法预测缺失数据，然后使用协同过滤算法进行推荐。

本文的研究建立在基于项目的协同过滤算法上。传统基于项目的协同过滤算法仅仅基于评分相似度来衡量项目之间的相似程度，而忽略了相似度计算值的可信程度，没有考虑到目标项目与其最近邻集合中项目的相似性以及共同评分项的个数对相似度计算的影响。针对这个问题，本文提出了基于可信相似度的协同过滤算法，在计算相似度的时候，综合考虑评分可信度以及项目类型可信度，计算可信相似度，以此来提高预测的精度。

1 传统相似性度量方法

评分相似度是传统协同过滤算法用来衡量项目之间的相似程度的方法。余弦相似度，Pearson相关相似度和修正的余弦相似度是最为常用的计算方法。

⑴ 标准的余弦相似性

2 改进相似度计算方法的协同过滤算法

2.1 传统相似度计算存在的问题

传统的相似度计算方法建立在两个项目的共同评分数据上，而忽略了用户项目评分矩阵R的极度稀疏性以及项目类型的相关性，这会导致以下问题。

⑴ 传统的相似性计算方法未考虑到项目类型的相似程度对项目相似性的影响。这会导致对于某一类型的项目，其最近邻可能是很多各不相同的项目类型的集合。

例如计算用户U（i）对恐怖片Ij的预测评分值，使用传统的计算方法得到的电影Ij的最近邻集合Pi，j有可能为Pi，j={喜剧片、爱情片、战争片、战争片、儿童片}。显然，由于用户对不同电影的喜好程度是不同的，仅凭借电影的评分，而忽略电影的类型相似信息，来计算电影之间的相似性，偏离了实际，相似度的计算结果就不够可信。较好的方法是能够找到和恐怖片类型最相似，且其与Ij的评分相似度又比较高的电影作为最近邻计算预测评分。最近邻中电影的类型越相似，其计算出来的相似度就越可信，预测评分的准确度也就越高。

⑵ 传统的相似度的计算依赖于对项目进行共同评分的用户数目。然而，在实际的推荐系统中，用户的评分数据往往是极端稀疏的，共同评分的用户数量很少。例如电影i和电影j只有两个用户进行了评分，而且这两个用户的评分又非常接近，那么用传统方法计算出来的相似度就很高，显然这和实际不相符，相似度的计算值不够可信。相反，共同评分的用户数量越多，那么相似度的可信度就越高，就越能够反应用户的真实兴趣偏好。

2.2 可信度的计算

基于以上分析，本文提出一种新的相似性计算方法，通过引入相似可信度来动态调节相似度的计算，以改进传统相似性计算存在的问题。

针对问题⑴，如果我们在计算项目相似度的时候，将项目类型对相似度影响的大小作为项目相似性可信程度的一个度量因子，动态地调节传统相似性计算的结果，那么可以使相似性的计算值更加趋近于实际。因此，本文提出，在计算项目相似度时，将项目类型的相似程度作为项目相似性的一个度量因子，我们称之为项目类型可信度。

2.4 最近邻的选择

目标最近邻的选择，是协同过滤算法最重要的一步。本文根据式（12）计算项目之间的可信相似度，得出可信相似度矩阵Dsim，使用K近邻算法从相似性矩阵中找出可信相似度值最高的K个项目作为目标项目的最近邻Neighbor。算法如下：

输入：用户评分矩阵Rm×n，项目类别矩阵Ts×n，K，用户参评矩阵Xm×n。

输出：最近邻Neighbor。

步骤一：可信相似度Dsim的计算

对Rm×n中的目标项目i：

⑴ 依次从Rm×n中选择和i不同的项目j。

⑵ 根据式⑵计算项目i和项目j的Pearson相似度。

⑶ 根据式（11）计算项目i和项目j的可信度。

⑷ 利用公式（12）计算项目i和项目j的可信相似度，并更新Dsim的值。

⑸ 若Dsim计算全部完成，则执行步骤二，若Dsim未完成计算，回到第1步。

步骤二：生成最近邻集合Neighbor

对Rm×n中的每一个项目i：

从Dsim中，选择最相似的K个项目作为项目i的最近邻Neighbor。

2.5 评分预测

3 实验与分析

3.1 实验数据

MovieLens[8]是明尼苏达大学Grouplens工作组于1997年创建的一个影片推荐系统，它通过收集和分析用户评分和用户对电影的喜好数据，形成推荐。本文选取公开的MovieLens数据集作为实验数据，该数据由10万条评分数据组成，评分数据是由943个用户对1682个电影项目的评分组成的，每个用户对至少20部电影进行了评分，评分的范围为1-5。评分越高表示用户的兴趣度越高。每部电影都被分为18个电影类别中的一类或者几类。

本文实验将10万条数据按照8：2的比例进行划分，其中训练集占80%（100000×80%=80000条数据），测试集占20%（100000×20%=20000条数据）。实现语言采用Python。

3.2 评价标准

推荐系统的预测评分值与用户的实际评分值越接近，其推荐质量就越高。MAE（Mean Absolute Error）[9]是一种计算所有单个观测值与算术平均值偏差的绝对值的平均值的方法。平均绝对误差能较好地反映预测值与实际值误差的真实情况。MAE的定义如式（14），通过累计计算实际的用户评分与预测的用户评分的偏差的平均值来度量预测的准确性，MAE值越小，表明算法越精确。

3.3 实验结果

对于项目类型可信度的计算，需要先确定项目的属性矩阵T。MovieLens数据集中的电影共有18种特征属性，每部电影都可以同时具有一个或者多个属性，实验中，使用这些属性构造电影的属性矩阵T。对于评分可信度的计算，我们使用式（9）根据用户项目评分矩阵R构造用户参评矩阵X。

实验中，不断改变项目邻居个数K的数目，使用可信相似度来度量项目间的相似性，以传统的基于项目的协同过滤算法CF作为基准参考方法，对基于可信相似度的协同过滤算法MSCF进行了实验，验证优化效果。实验结果如图1所示。

可以看出，一开始随着最近邻数目的增加，两种相似度算法的MAE值都呈现下降的趋势，并且随着近邻数量的不断增大而趋于平稳。在最近邻数量相同的时候，MSCF的实验效果好于CF的实验效果。这是因为传统相似性计算方法未考虑项目类型的相似性和共同评分用户数量对相似性计算结果的影响，导致求得的最近邻可能不符合实际，从而影响了推荐质量。而改进的基于可信相似度的算法MSCF则综合考虑了两者对相似度计算的影响，因而具有较小的平均绝对偏差MAE。

实验证明，本文提出的基于可信相似度的协同过滤算法的推荐效果要优于传统的协同过滤算法。

4 结束语

在传统的基于项目的协同过滤算法中，项目间相似性计算的精确度是影响推荐质量的关键因素。实际应用中，数据的稀疏性对传统的协同过滤算法产生了很大的影响。同时，最近邻集合中项目的类型的不相似性也对推荐系统的推荐精度产生了消极的影响。本文针对传统相似度计算的问题，提出了一种改进的相似性度量方法，从项目类型的相似性和共同评分的用户数两个方面考虑，计算可信相似度，并将改进的算法在真实数据集上进行了实验。实验的结果表明，改进的方法有效地提高了推荐质量。

参考文献：

[1] Sarvar B. Karypis G， Konstan J， et al. Item-based Collaborativefiltering recommendation algorithms[C]. Proceedings of the 10th International World Wild Web Conference. New York，2001：285-295

[2] 邢春晓，高凤荣，思南等.适应用户兴趣变化的协同过滤推荐算法[J].计算机研究与发展，2007.44（2）：296-301

[3] 李改，李磊.基于矩阵分解的协同过滤算法[J].计算机工程与应用，2011.47（30）：4-7

[4] 李荟，谢强，丁秋林.一种基于情景的协同过滤推荐算法[J].计算机技术与发展，2014.24（10）：42-46

[5] 董丽，邢春晓，王克宏.协作过滤稀疏性算法[J].清华大学学报（自然科学版），2009.49（10）：154-157

[6] 郭艳红，邓贵仕.协同过滤系统项目冷启动的混合推荐算法[J].计算机工程，2008.34（23）：11-13

[7] 彭石，周志彬，王国军.基于评分矩阵预填充的协同过滤算法[J].计算机工程，2013.1（39）：175-178

[8] GroupLens lab at the University of Minnesota. MovieLens Dataset.Available at： http：//www.grouplens.org/node/12.

[9] B Jeong， J Lee， H Cho. Improving memory-based collaborativefiltering via similarity updating and prediction modulation[J].Information Sciences，2010.180（5）：602-612