基于BiasSVD 和聚类用户最近邻的协同过滤算法研究

2020-06-15李佳张牧

现代计算机 2020年13期

李佳，张牧

（成都体育学院，成都 610041）

0 引言

随着网络科技的发达，信息泛滥的时代已经到来，一般的搜索引擎不能为用户提供准确的搜索结果，而个性化推荐系统能够主动学习与分析用户的行为，自主对信息过滤，为用户提供适合自己需求的推荐。个性化推荐系统的算法有多种，其中协同过滤算法是最成熟的[1]，面对如今的大数据时代，协同过滤算法存在可扩展性问题。Sarwar 等人[2]将SVD 技术运用到协同过滤算法，得到低秩矩阵，降低矩阵复杂度。Rashid 等人[3]采用聚类技术为每个聚类生成代理用户，与目标用户相似度最高的代理用户进行最近邻的推荐，大大减小对最近邻的搜索范围。Karypis 等人[4]指出通过增加服务器数量，提高算法吞吐量。李改等人[5]在SVD 模型中进行正则化约束来训练数据，用最小二乘法来训练分解模型。

为了解决协同过滤算法的可扩展问题，本文提出基于BiasSVD 和聚类用户最近邻的协同过滤算法，首先选用的是BiasSVD 降维技术，该方法在原有的LFM模型上加入偏置项，使得BiasSVD 模型更加贴近现实和精细，该方法对扩展性的问题改善程度较为显著，但是仍然会造成信息丢失以及存在一定的偏差，所以最终得到的目标用户预测评分将通过聚类用户最近邻预测评分和真实评分的平均偏差值来调整，从而提高协同过滤算法的推荐质量。

1 相关工作

协同过滤算法为用户产生推荐大概分为三个步骤，通过自主收集学习用户行为信息，建立用户项目评分矩阵Rm×n，接着计算用户或者项目之间的相似度产生最近邻集合，最后根据最近邻产生预测评分或者商品推荐。

本文评分矩阵有m行n列，m代表用户个数，n代表项目个数。其中，u、v表示用户，i、j表示项目，rui为用户u对项目i的评分。

1.1 BiasSVD

BiasSVD 又叫偏差矩阵分解[6]，它是通过降维的方法把高维的项目评分矩阵Rm×n分解为两个低维矩阵相乘，即Rm×n=Pm×fQf×n，其中f

bui为用户u对项目i的偏好评分，μ为数据训练集中所有评分记录的平均值，bu[u]表示用户u评分偏差，bi[i]表示项目i的偏好。

例如预测用户Grace 对《计算机导论》这本书的偏好评分，其中总体平均值为3 分。《计算机导论》的质量比大部分书籍都好，对它的评分比其他书籍平均分高于0.6 分。而且用户Grace 评分是比较严谨的，偏向于给书籍打低0.2 分，所以用户Grace 对《计算机导论》的偏好评分bui=3+0.6-0.2=3.4。从上述分析，利用偏差矩阵分解的评分预测公式如下：

pui为用户u对项目i的预测评分，p和q表示经过降维后的用户特征矩阵以及项目特征矩阵。

基于BiasSVD 预测出来的评分加上偏置项，不仅降低数据复杂度，而且使得预测评分更接近真实评分，但是依然存在一定偏差，需要通过最近邻用户真实评分和预测评分的平均差值来调整目标用户的预测评分。

1.2 聚类用户最近邻

聚类的方法有很多种，本文采用的是K-means 聚类方法。基于K-means 聚类协同过滤算法首先确定k个聚类中心，然后计算用户与每个聚类中心之间的相似度，比较这些相似度的大小，用户就和相似度最高的聚类中心是一个类别的，以此反复计算，直到所有用户都已经聚类，最后为目标用户寻找最近邻，第一步是计算目标用户和聚类中心的相似度，找到目标用户所属类别，第二步就是在该类别的集合中找到目标用户的最近邻，由此可以看出，最近邻的搜索空间已经大大地减小。

在该聚类的集合中计算用户之间的相似度，本文选取的用户相似度公式是在皮尔逊系数基础上作了一点改进。皮尔逊系数公式：

公式（3）中计算目标用户u与用户v相似度，ruv表示用户u与v共同评分的项目集合。rui和rvi分别表示用户u和v对项目i的评分，分别表示用户u和v评分平均值。

公式⑷是改进的相似度公式，N(u)⋂N(v)表示用户u和v共同评分个数，N(u)⋃N(v)表示用户u和v评分项目数的并集。这在一定程度上惩罚共同评分项目数少的用户相似度，提高相似度计算的准确性。

通过公式（4）计算目标用户u和其他用户v的相似度sim(u,v)，相似度大小取值范围为[-1，1]，然后降序排列，选取前N 个作为目标用户u的最近邻集合。

2 基于BiasSVD和聚类用户最近邻的协同过滤算法

本文提出的基于BiasSVD 和聚类用户最近邻的协同过滤算法的中心思想是通过公式（2）得到预测评分pui，然后采用公式（4）计算相似度获取目标用户u最近邻集合user(u)，最后结合最近邻真实评分rvi与预测评分pvi之间差的平均差值evi来调整目标用户的最终预测评分即公式如下：

其中 N 是集合 user（u）的元素个数，eui相当于是一个偏移量。当eui的值大于零时，表示实际上真实评分比预测评分高很多，所以增加偏移量eui到原来基准评分pui上；当eui值为零时，表示预测出来的评分已经很精确接近真实评分，不需要再调整；当eui值小于零时，真实评分比预测出的评分低很多，相应的在基准分pui上减去偏移量evi。所以最终预测评分公式如下：

为了得到最合适的用户、项目特征矩阵p、q和用户、项目偏好向量bu、bi，利用随机梯度算法来优化，首先定义误差公式由于防止过拟化加上规范化因子最终误差公式如下：

公式（8）利用随机梯度下降法得到的更新规则为：

算法2 基于BiasSVD 和用户最近邻的协同过滤算法

输入：项目评分矩阵Rm×n，目标用户u，项目i，用户项目特征数f，迭代次数step，以及梯度下降步长γ，惩罚因子λ

输出：用户u对项目i的预测评分

步骤：

（1）计算总体平均值μ

（2）初始化bu、bi为全 0

（3）初始化p、q矩阵

（4）过随机梯度下降法的迭代得到优化好的p、q矩阵和bu，bi向量

（5）对所有用户进行K-means 聚类

（6）通过公式（5）计算evi的值

（7）找到目标用户聚类的集合，基于该集合利用公式计算p'ui预测评分

3 实验结果及分析

3.1 实验数据集

为了验证改进算法的准确性，首先应该选择合适的数据集，本文采用的数据集是由美国Minnesota 大学的GroupLens 研究小组从MovieLens 网站提取而来[7]。该数据集有943 个用户，1682 部电影，总共有100000条记录，每个用户至少要为20 部电影评分，分值范围是1-5，分数高低表示用户对电影的喜好程度。数据集分为训练集和测试集，按80%和20%的比例来分。