协同过滤算法改进及研究

摘要：针对协同过滤中存在的稀疏性问题，提出改进方法——BAS算法。该算法结合贝叶斯度量方法和奇异值降维分解方法，利用传统的基于奇异值分解获得活跃用户的邻居，通过改进后的相似性度量方法得出预测值。对改进后的算法进行理论分析和实验对比。结果表明，该方法在所用数据集上能够有效缓解数据稀疏性问题，并且改善推荐精度的准确性，在一定程度上提高了推荐引擎的推荐质量。

关键词关键词：推荐引擎；协同过滤算法；数据稀疏；奇异值分解

DOIDOI：10.11907/rjdk.104179

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2015）002007404

作者简介作者简介：苏杨茜（1988-），女，广西南宁人，中南民族大学计算机科学学院硕士研究生，研究方向为软件工程与复杂网络。

0引言

协同过滤（Collaborative Filtering ，CF）是目前推荐引擎中应用最广泛的个性化推荐技术之一。其通过研究用户历史行为，分析用户兴趣（或项目属性），为用户建立模型，依据活跃用户对项目的评价，来寻找与活跃用户兴趣相同的用户组，然后用该用户组中评价比较高的一组项目序列为活跃用户作出相关推荐＼[12＼]。

现有协同过滤算法分为基于用户的协同过滤、基于项目的协同过滤和基于模型的协同过滤＼[3＼]。基于用户的协同过滤是向用户推荐与其兴趣相似的其他用户喜欢的物品，依据的是用户之间的相似度；基于项目的协同过滤是向用户推荐与其先前喜欢的项目相似的项目，依据的是项目之间的相似度；基于模型的协同过滤则依据已有的部分成熟算法建立模型，然后为用户进行推荐，常见的有聚类、关联规则、贝叶斯网络等。

1协同过滤中的数据稀疏性问题及解决方法

协同过滤算法推荐需利用用户对项目资源的评价信息矩阵。如果用户对项目资源的评价不够多，则无法产生精确的推荐，导致用户体验不佳，这就是协同过滤算法中存在的数据稀疏性问题。信息矩阵的数据稀疏性本质上是由高维数据引起的，是协同过滤算法的经典问题。现有解决数据稀疏性方法主要有聚类分析＼[4， 5＼]、奇异值分解等。

2改进的BAS（Bayes After SVD）算法

协同过滤技术的关键是找到最优邻居集合，要解决计算信息矩阵稀疏性问题，可以从两个方面着手：①寻找一个更为精确的相似性度量方法，在同等稀疏程度情况下，得到更好的邻居集合；②对计算信息矩阵进行降维处理，并填补计算信息矩阵中的缺失项，使其成为一个稠密的计算信息矩阵，为协同过滤后的计算提供更多的数据源，从而提高推荐质量。

2.1主要技术

（1）贝叶斯（Bayes）度量。

sim（i，j）=F（i·j）F（i）（F（j））α（1）

F（i）是对项目i感兴趣的用户数目。α为惩罚因子，取值0～1，在实际应用中以物品的热度来进行度量。对热销用品，与其有关联的物品越多，则α越接近1。需要注意的是，当α=0时，则变成了传统的贝叶斯公式；当α=1时，则所有物品都影响物品间相似度。

（2）奇异值分解（SVD）。计算矩阵R代表用户的评分行为，其中R[u][i]表示用户u对项目i的评分。首先将计算矩阵R分解为两个低维相乘矩阵。

R=PTQ（2）

其中，P∈Rf×m和Q∈Rf×n是两个降维后的矩阵。

用户u对项目i的评价预测值R（u，i）=rui，可通过下式计算：

rui=∑fpufqif（3）

其中，puf=P（u，f），qif=Q（i，f）。矩阵分解思想为利用最小化RMSE思想，直接通过训练集中所观察的数据对P、Q矩阵进行学习。在利用RMSE作为评测指标时，加入防止过拟合项λ（‖pu‖2+‖qi‖2），其中λ是正则化参数，从而得到损失函数。

C（p，q）=∑（u，i）∈Train（rui-∑Ff=1pufqif）2+λ（‖pu‖2+‖qi‖2（4）

2.2算法过程

首先采用SVD方法预测未打分的评分预测值，得到一个稠密的计算矩阵；然后，利用填补后的计算矩阵，配合加入惩罚因子的贝叶斯公式，采用获取最优邻居集合的方法，求取实际未评分的项目的预测值，该方法称为BAS（Bayes After SVD）算法。BAS算法流程如下：①获取用户项目信息矩阵，将计算矩阵R规范为Rn；②利用SVD对信息矩阵进行降维处理，同时进行缺失项填充；③选中一个用户，利用修正后的贝叶斯公式求得活跃用户与其他用户的相似度；④依照与活跃用户的相似性度量大小进行排序，选择前N个用户作为活跃用户的最优邻居；⑤求出每个活跃用户i对未评分项目j的预测值。

3算法实现与实验分析

3.1评价指标

（1）均方根误差（RMSE）和平均绝对误差（MAE）。评分预测的准确度一般通过均方根误差（RMSE）和平均绝对误差（MAE）计算。对于测试集中的一个用户u和项目i，令rui是用户u对项目i的实际评分，而r'ui是推荐引擎计算出的预测评分，则：

RMSE=∑u，i∈T（rui-rui）2|T|（5）

MAE采用绝对值计算预测误差，定义为：

MAE=∑u，i∈T|（rui-rui）||T|（6）

（2）Top N推荐。Top N推荐的预测准确率通常通过准确率（precision）/召回率（recall）来进行度量。

令R（u）表示用户u推荐N个物品，而T（u）是用户在测试集上的行为列表，则推荐结果的召回率为：

Recall=∑u∈U|R（u）∩T（u）|∑u∈U|T（u）|（7）

推荐结果的准确率为：

Precision=∑u∈U|R（u）∩T（u）|∑u∈U|R（u）|（8）

（3）覆盖率（Coverage）。该指标描述一个推荐引擎对项目长尾的发觉能力。最直观的描述为推荐引擎能够推荐出来的项目占总项目集合的比例。假设系统的用户集合为U，推荐引擎向每个用户推荐一个长度为N的项目列表R（u）。则推荐引擎的覆盖率可定义为：

Coverage=|∪u∈UR（u）||I|（9）

为更细致地描述推荐引擎挖掘长尾的能力，需要统计推荐列表中不用项目出现次数的分布。可以参考信息论中的信息熵：

H=-∑ni=1p（i）logp（i）（10）

其中，p（i）是项目i的流行度除以所有项目流行度之和。

3.2数据集说明

为评估不同算法的推荐效果，使用以下公开数据集：

（1）MovieLens数据集。该数据集（http：//www.grouplens.org/node/73）包含3个不同版本，本次实验选用中等大小的数据集。该数据集包含约100万条评分，涵盖了6 000多个用户对4 000多部电影的评分情况，用户可以对电影评5个不同等级的分数（1-5分），并且每位用户至少曾为20部电影作过评价。

（2）Jester数据集。该数据集是加州大学伯克利分校发布的一个关于笑话的数据集（http：//www.ieor.berkeley.edu/～goldberg/jesterdata/），包含约410万记录，收集了73 421个用户对100个笑话的评分（评分范围从-10～10）。该数据集分为3个部分，本次实验采用了第三部分，该部分为24 938个用户的评分，且打分项目数目在15～35之间。

定义用户计算矩阵中未评分条目所占的百分比作为稀疏密度来度量采用数据集的稀疏特性，比如MovieLens数据集的稀疏密度约为：

1-1 000 000/（6 000*4 000）=0.958 3

3.3实验分析

本次实验中采用MovieLens数据集和Jester数据集进行试验。

3.3.1数据稀疏性对推荐结果的影响

大多使用推荐引擎的网站，尤其是一些大型的电子商务网站，比如淘宝、京东商城等，用户真正接触的物品信息数量以及进行评价的信息常常达不到物品信息总量的1%，这就导致了计算信息矩阵的极端稀疏，容易导致推荐质量令用户不满意，或者用户体验不佳。

通过实验来比较常规协同过滤（采用余弦相关性和加入惩罚因子的贝叶斯公式）在MovieLens与Jester两个数据集中不同稀疏密度下的推荐效果。选取MovieLens数据集和Jester数据集中各两组数据集作对比，结果分别如表1、表2所示。其中： MI15为MovieLens数据集中前1 500个用户的评分；MII15为MovieLens数据集中前1 500个用户中评分数目小于30的评分；JI15为Jester数据集中前1 500个用户的评分；JII15为Jester数据集中前1 500个用户中评分数目小于30的评分。对每个数据集根据实验需要将其划分为训练集和测试集，且二者比例约为4∶1。

从表1、表2可以看出，当数据比较稀疏（即当选定MII15和 JII15两个数据集）时，SVD与常规的协同过滤方法（不论是采用加入惩罚因子的贝叶斯方法还是余弦相似度）推荐结果类似，唯一不同的是随着数据集稀疏密度的变化，相较与其它两种算法，SVD算法预测结果变化幅度比较小，即其对数据稀疏的敏感程度要优于常规的协同过滤方法。随着抽取子数据集系数密度越来越大，推荐引擎的推荐效果越好，但当数据子集比较稠密时，可以看出常规的协同过滤方法（特别是采用加入惩罚因子的贝叶斯方法）比SVD算法要好。实验证明数据集的稀疏性是影响推荐引擎效果的重要因素。

3.3.2针对选定数据集，选定适当的k值

对于MovieLens数据集，从用户评分数据中选择评分数目小于40的用户，得到数据集包括约200多个用户和1 200多部电影，然后将数据集随机划分为训练集与测试集，训练集和测试集的比例为4∶1。

对于Jester数据集，直接选取用户评分项目从15～35的用户，得到数据集包括约24 900个用户的评分，将数据集随机分成训练集与测试集，二者之间的比例约为4∶1。

在基于SVD分解的模型中，矩阵最终维数k是关键参数，如果k过大，则失去了SVD分解的意义，如果k过小，则不能很好反映原有矩阵的信息特性，故首先需要确定参数k，然后再采用本文提出的BAS算法。

从图1中可以看出，当k=25时，平均绝对误差（MAE）最小，所以对于该数据集，维数k=25是最佳的，在采用BAS算法实验中，针对MovieLens数据集，选取k=25。从图2中可以看出，针对Jester数据集，当k=8时，平均绝对误差（MAE）最小，所以对于Jester数据集，维数k=8是最佳的，在采用BAS算法的实验中，针对Jester数据集，选取k=8。

3.3.3在选定的数据集上进行不同算法的推荐

利用实验中所用的数据集确定k值，图3和图4分别为选定的MovieLens数据集和Jester数据集上不同算法的预测结果。

从图3可以看出，BAS算法比朴素贝叶斯及SVD算法得到的推荐效果都要好，但当邻居数目超过20时，BAS方法的结果和朴素贝叶斯方法（即常规协同过滤方法）的结果趋于相交，所以当邻居数目超过一定数量时，BAS方法的优越性不明显，考虑到现实中用户只对为其推荐的前几条信息感兴趣，所以20个邻居在选定数据集下是可以接受的。同时以上结果也可以从另一个方面反映MAE可以比较好地评价推荐引擎结果推荐的准确性。

图4Jester数据集下不同算法的预测结果比较

协同过滤所需的计算信息矩阵经过奇异值分解处理后，原始的计算信息矩阵维度减小了，使得原本高维模型的计算转换成了指定维度下的矩阵运算，有效缩减了原有问题的规模。实验表明，奇异值分解应用于协同过滤时，尤其是应用于数据稀疏度比较高的信息矩阵计算时，能有效提高推荐引擎的推荐精度，虽然矩阵的奇异值分解计算量比较大，但可以离线进行，从而弥补运算量大带来的损耗。从实验结果看出，BAS方法的推荐质量与其它常见的方法相比有一定的提高。

4结语

个性化推荐中协同过滤应用广泛。其主要思想是利用用户的历史信息计算用户之间的相似性＼[6，7＼]，利用与目

标用户相似性较高的邻居对产品的评价来预测目标用户

对特定产品的喜好程度。计算矩阵稀疏性的问题是协同

过滤算法需解决的关键问题。本文主要针对协同过滤中数据稀疏性问题导致推荐效果不理想，用户体验不佳问题，提出一种混合推荐的BAS算法。利用公开实验数据集MovieLens和Jester进行试验，实验结果表明本文提出的BAS方和现有的解决方法相比，能够一定程度的缓解数据稀疏性问题，提高推荐引擎的推荐精度。

参考文献参考文献：

＼[1＼]DANIEL BILLSUS ， MICHAEL J. Pazzani， Learning collaborative information filters＼[C＼]. Proceedings of the Fifteenth International Conference on Machine Learning，1998：4654.

＼[2＼]李勇， 徐振宁， 张维明. Internet 个性化信息服务研究综述＼[J＼]. 计算机工程与应用， 2002， 38（19）： 183188.

＼[3＼]曹一鸣. 协同过滤推荐瓶颈问题综述＼[J＼]. 软件， 2012，33（12）： 315321.

＼[4＼]SHI K，K ALI. GetJar mobile application recommendations with very sparse datasets＼[C＼]. Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining，2012：204212.

＼[5＼]李华， 张宇， 孙俊华. 基于用户模糊聚类的协同过滤推荐研究＼[J＼]. 计算机科学， 2012. 39（12）：8386.

＼[6＼]KIM W. Inference of recommendation information on the internet using improved FAM＼[J＼]. Future Generation Computer Systems， 2004， 20（2）： 265273.

＼[7＼]杨阳， 向阳， 熊磊. 基于矩阵分解与用户近邻模型的协同过滤推荐算法＼[J＼]. 计算机应用， 2012， 32（2）： 395398.

＼[8＼]熊忠阳， 刘芹， 张玉芳. 结合项目分类和云模型的协同过滤推荐算法＼[J＼]. 计算机应用研究， 2012， 29（10）： 36603664.

＼[9＼]黄国言. 基于项目属性的用户聚类协同过滤推荐算法＼[J＼].计算机工程与设计， 2010（5）： 10381041.

责任编辑（责任编辑：陈福时）