张 昪

(兰州财经大学 信息工程学院，甘肃 兰州 730000)

基于概率矩阵分解的推荐算法

张 昪

(兰州财经大学 信息工程学院，甘肃 兰州 730000)

为了解决传统协同过滤推荐算法的可扩展性差和数据稀疏性的问题，提出了一种基于随机梯度下降的概率矩阵分解推荐算法。该算法是生成两个服从高斯分布的随机数矩阵，不断训练和更新使得这两个矩阵的内积趋近于用户评分矩阵，为了避免模型过度拟合训练数据，在此基础上加入正则项进行约束，并通过批处理的随机梯度下降法来优化模型。在MovieLens提供的数据集上进行实验验证，与传统的协同过滤算法相比较，该算法不仅缓解了可扩展性问题和稀疏性问题，而且推荐的准确度也得以提升。

推荐算法；协同过滤；概率矩阵分解(PMF)；随机梯度下降法(SGD)

0 引言

随着互联网技术的飞速发展，当今社会已经进入了信息爆炸的时代，人们想要从海量的数据中搜索到自己需求的信息无异于大海捞针，在这种情况下，个性化推荐技术迅速的发展起来。这是一种信息过滤手段，可以挖掘用户的兴趣爱好，针对不同的用户提供个性化服务，解决了信息过载的问题。通过个性化推荐能使用户从浏览者变为购买者，提高用户对网站的忠诚度，从而增加网站效益。目前几乎所有电子商务、在线音乐视频网站都不同程度的使用了推荐技术，例如国外的Amazon、Youtube、Pandora以及国内的阿里巴巴、豆瓣电影、虾米音乐等。

目前主流的推荐算法有六种[1]，即：协同过滤推荐、基于内容推荐、基于关联规则推荐、基于效用推荐、基于知识推荐和在以上五种推荐技术上的混合推荐算法。文献[2]分析了各类算法的优点和不足，提出了改进的方法和未来可能研究的方向。其中应用最为广泛的是协同过滤算法[3]，但协同过滤算法仍存在以下几种问题，如：推荐的实时性难以保证、算法的可扩展性差、冷启动问题和稀疏性问题，针对这些问题有许多学者在协同过滤算法上进行了不同的改进。

为了提高推荐的实时响应速度，邓爱林等提出项目聚类协同过滤算法[4]，根据用户对项目评分的相似性对项目进行聚类，生成相应的聚类中心，在此基础上计算目标项目与聚类中心的相似性，在推荐中考虑与目标项目在同一类中的其他项目，该算法可以有效地提高在线最近邻查询速度，但是推荐精度没有显著降低。李海霞提出将蚁群算法融合到协同过滤算法中[5]，该算法使用蚁群算法实现用户聚类，从而在一定程度上降低了候选邻居集的数量，然后在用户簇中运用融合用户和项目的协同过滤推荐算法对用户进行推荐，虽然能够解决候选邻居集较大的问题，但是蚁群算法簇数目过高，并且存在蚁群算法的孤立点。

为了解决可扩展性差的问题，Sarwar BM等人提出基于奇异值分解的协同过滤算法[6]，将一个比较复杂的矩阵用更小更简单的3个子矩阵的相乘来表示，这3个小矩阵描述了大矩阵重要的特性，该算法可以有效的解决一义多词问题，显著提高推荐系统的伸缩性，但是降维会导致信息损失，并且在空间维数很高的情况下，降维效果难以保证。

为了解决冷启动问题，何佳知提出基于内容和协同过滤的混合算法[7]，使用用户-特征评分矩阵代替传统的用户-项目评分矩阵，根据用户对项目特征，对具有相同特征偏好的用户进行聚类，生成相应的聚类中心，推荐时，首先确定目标用户喜好的特征类型，再计算与所有聚类中心的相似性，从而确定最近邻居的所属簇，最后借助最近邻完成对目标用户的推荐。

为了解决数据稀疏性问题，许多研究者通过矩阵分解来降维，最早的矩阵分解模型利用的是奇异值分解[8]，但这个方法在一开始时需要对矩阵的缺失值进行填充，从而将一个稀疏矩阵转化成一个稠密矩阵，然后进行分解，然而，对高维稠密矩阵进行分解的时间复杂度和空间复杂度都特别高。此外，常用的解决数据稀疏性问题的方法还有主成分分析方法[9]，通过主成分分析，降低矩阵的稀疏性，保留了最能代表用户兴趣的维度，提高了推荐的质量，但该算法舍弃了部分用户评价或用户，不可避免的要损失一些有价值的信息。

本文为了解决数据稀疏性问题，也是以矩阵分解为基础，提出了基于概率矩阵分解[10](Probabilistic Matrix Factorization，PMF)的方法，从概率的角度将用户和项目的一些潜在信息映射到低维的特征空间，然后利用低维的特征向量的线性组合来解释特定用户对特定项目的喜好程度。此外，为了提高推荐速度，还加入了批处理模块，使模型收敛更加稳定，以得到用户个性化的推荐。

1 问题描述

其中用户未评分的项目用0代替，推荐算法就是要预测出用户未测评的项目。

1.1 矩阵分解

矩阵分解的思想是每一个用户和每一个项目都有自己的一些特性，矩阵分解的方法可以从用户评分矩阵中分解出用户-特征矩阵，项目-特征矩阵。

1.2 基于用户的协同过滤

基于用户的协同过滤算法(CF-User)主要利用整个用户-项目评分矩阵进行推荐，寻找与目标用户相似度高的用户，认为目标用户与其有相同的爱好，将该用户选择的项目推荐给目标用户[11]。

该算法可以概括为两步：

①计算用户之间的相似度，构造用户相似度矩阵；

②采用相应的算法估计评分，并据此为目标用户进行推荐。

常用的相似度的计算方法有皮尔森相关系数[12]

(1)

余弦相似度[13]

(2)

按照相似度的大小进行排序，选择前k个用户或者相似度大于指定阈值的用户作为最近邻居集N。通过计算目标用户x的最近邻居集N来预测x未作评分的项目，具体方法如公式(3)：

(3)

最终可以选择预测分数较高的前S个项目作为推荐结果。然而在一个系统中，用户的数量是不断发生变化的，此时基于用户的协同过滤算法往往需要重新计算不同用户间的相似度，更新用户相似度矩阵，时间复杂度高，可扩展性差。

1.3 基于项目的协同过滤算法

基于项目的协同过滤算法(CF-Item)通过用户-项目评价数据建模，也是利用用户-项目评价数据进行推荐，计算不同项目之间的相似度，认为用户会喜欢同一类项目，将相似度较高的项目推荐给目标用户[14]。

该算法可以概括为两步：

①计算项目之间的相似度，构造项目相似度矩阵；

②采用相应的算法估计评分，并据此将相似度较高的项目推荐给相关用户。

构造项目相似度矩阵的方法以及目标用户对项目预测评分的方法与基于用户协同过滤的计算方法相类似。

基于项目的协同过滤算法同样也存在着当项目不断变化时，也要重新计算不同项目间的相似性，更新项目相似度矩阵，仍然存在着可扩展性差、时间复杂度高等问题。

2 基于概率矩阵分解的算法

(4)

其中，Iij为指示函数，Iij=1表示用户i对项目j进行过评分，Iij=0表示用户i对项目j未进行过评分。

(5)

(6)

由公式(4)、(5)、(6)可得到U和V的联合概率分布：

(7)

对U和V的概率分布取对数得：

(8)

求解公式(8)的最大值可等价替换为求带正则化参数的误差函数的最小值，如公式(9)：

(9)

为了解出目标函数，本文采用随机梯度下降法(SGD)，这种算法通过对参数求导的方法来找到目标函数的参数下降最快的方向，让变量沿着这个方向不断移动，直到移动到极小值点。

对它求导，可以发现每次迭代的时候，Ui和Vj的更新公式变成：

(11)

Ui←Ui+α×(e×Vj-λ×Ui)

(12)

Vj←Vj+α×(e×Ui-λ×Vj)

(13)

其中，α为随机梯度下降的学习率。

此外，为了提高算法的推荐效率，加入了批处理模块，对于实验中的90000条训练数据，将其分成9个批次，每次处理10000条数据，这样很大程度上减少了模型训练的运算量，同时也减小了对每条训练数据进行计算时造成的模型收敛的不稳定性。

基于概率矩阵分解的推荐算法如下：

输入：训练集train_vec，测试集probe_vec

输出：预测评分pred_out，平方根误差RMSE

①设置正则化参数，最大迭代次数maxepoch，分解维度feat

②生成电影数量(1682)feat和用户数量(943)feat两个标准正态分布矩阵

③if迭代次数epoch

④采用批处理，分为9个批次，每次处理10000条评分记录，if批处理次数batch<9，

⑤计算损失函数p,根据负梯度方向不断更新2)的两个矩阵

⑥end

⑦读入测试集，根据2的两个矩阵计算测试集的预测评分，将大于5的评分替换为5，将小于1的评分替换为1

⑧计算RMSE

⑨end

3 实验实证与分析

3.1 实验环境

本文所涉及的实验均在DELL计算机上实现，操作系统采用Windows7 32位，内存为2G，处理器为AMDAthlon(tm)ⅡNeoK345Dual-CoreProcessor1.40GHz,本文提出的模型均在Matlab2012b平台上用Matlab语言编写实现。

3.2 数据集

本文将随机选取90000条记录作为训练集，剩余10000条记录作为测试集。

3.3 度量标准

预测评分准确度用来衡量算法计算出来的预测评分与用户给出的真实评分之间的吻合程度，通过误差来表示推荐结果是否符合用户的需求。主要的评价指标有平均绝对误差(MAE)和平均方根误差(RMSE)[15]，而RMSE加大了对预测不准的用户项目评分的惩罚(平方项的惩罚)，因而对推荐算法的评测更加苛刻。本文选用RMSE作为评价指标。

RMSE通过计算预测的用户评分与实际的用户评分之间的偏差来度量预测的准确性。推荐算法整体的RMSE越小，意味着推荐的质量越高，算法的RMSE表示为公式(14)：

(14)

3.4 实验结果分析

3.4.1 参数对实验结果的影响

由图1可以看出，当λ∈[0.05，0.1]时，模型的平方根误差明显获得了较低的误差，在下面的实验中，统一取λ=0.1为最优值。

3.4.2 分解维度和迭代次数对实验结果的影响

实验中动态考虑分解维度和迭代次数的影响，分别取迭代次数为10、20、30、40、50，分解维度为2、5、10、15、20，实验结果如图2所示。

由图2可以看出，当分解维度不变的情况下随着迭代次数的增加，RMSE略有下降；当迭代次数不变的情况下分解维度先下降后又上升，在分解维度为5时取得最小的RMSE，因此迭代次数为50次，分解维度为5时，RMSE取得最小值。

3.4.3 不同算法预测准确度的比较

为了验证PMF算法预测准确度的实际效果，将其与传统的基于用户和基于项目的协同过滤算法进行比较，分别选取邻居个数为10、20、30、40、50，实验结果如图3所示。

由图3可以看出，随着邻居个数的增加，CF-User和CF-Item算法的RMSE均有所上升，CF-Item算法的RMSE要低于CF-User算法，而PMF算法相比于其他两种算法在不同的邻居个数的情况下均能获得较低的RMSE值，由此也证明了PMF算法确实能提高推荐算法的预测准确度。

3.4.4 数据稀疏性对实验结果的影响

为了验证PMF算法的抗稀疏性的效果，下面将分为4组对比实验，查看数据越来越稀疏的情况下，PMF算法和CF算法的推荐效果，实验结果如图4所示。

*注：①将数据集中训练集随机取80000条作为训练集，测试集保持不变；②将数据集中训练集随机取70000条作为训练集，测试集保持不变；③将数据集中训练集随机取60000条作为训练集，测试集保持不变；④将数据集中训练集随机取50000条作为训练集，测试集保持不变由图4可以看出，随着数据越来越稀疏，三种算法的RMSE都略有上升，但PMF算法的RMSE始终低于CF-Item和CF-User算法，有着更好的抗稀疏性。

3.4.5 可扩展性对实验结果的影响

将实验数据集由原来的943个用户对1682部电影的100000条评价记录扩展到6040个用户对3952部电影的1000209条评价记录，各个算法所需的时间如表1所示。

表1 三种算法的时间比较

由表1可以看出，由于用户和项目的数量发生变化，传统的协同过滤算法需要重新计算用户相似矩阵和项目相似矩阵，花费大量的时间，CF-User所需的时间几乎是PMF算法的100倍，而CF-Item则是PMF算法的125倍，该实验表明PMF在算法扩展性方面明显优于传统的协同过滤算法。

4 结语

伴随着信息大爆炸的背景，越来越多的研究者开始关注推荐算法，但是传统的推荐算法依然存在着一些不足，如算法的可扩展性低、抗稀疏性差等问题，针对这些问题，本文提出了基于概率矩阵分解的推荐算法，在MovieLens数据集下，对提出的算法和传统的协同过滤算法进行了对比分析。实验表明，基于概率矩阵分解的推荐算法能够有效的缓解这些问题，同时提高了推荐的准确度。但PMF算法包含了太多的人为经验参数，在以后的工作中，将考虑使用贝叶斯矩阵分解来研究推荐问题。

[1] ADOMAVICIUS.G,TUZHILIN.A.Toward the Next Generation of Recommender Systems:A Survey of the State-of-the-Art and Possible Extensions[J].IEEE Transactions on knowledge and Data Engineering,2005,17(17):734-749.

[2] 杨博,赵鹏飞.推荐算法综述[J].山西大学学报(自然科学版),2011,34(3):337-350.

[3] 陈洁敏,汤庸,李建国,等.个性化推荐算法研究[J].华南师范大学学报(自然科学版),2014(5):8-15.

[4] 邓爱林,左子叶,朱扬勇.基于项目聚类的协同过滤推荐算法[J].小型微型计算机系统,2004,25(9):1665-1670.

[5] 李海霞.基于蚁群聚类的电子商务个性化推荐算法研究[D].山东:山东师范大学,2014.

[6] SARWAR BM,KARYPIS G,KONSTAN JA,et al.Application of dimensionality reduction in recommender system-A case study[C].ACM WebKDD 2000 Workshop,2000.

[7] 何佳知.基于内容和协同过滤的混合算法在推荐系统中的应用研究[D].上海:东华大学,2016.

[8] BILLSUS D,PAZZANI MJ.Learning Collaborative Information Filters[C].ICML.1998,98:46-54.

[9] 李远博,曹菡.基于PCA降维的协同过滤推荐算法[J].计算机技术与发展,2016(2):26-30.

[10] MNIH A,SALAKHUTDINOV R. Probabilistic matrix factorization[C].Advances in Neural Information Processing Systems.2007:1257-1264.

[11] 熊海涛.面向复杂数据的推荐分析研究[M].北京：北京理工大学出版社，2015.

[12] RESNICK P,IAKOVOU N,SUSHAK M,et al.GroupLens:An open Architecture for Collaborative Filtering of Netnews[C].Process of the 1994 Computer Supported Cooperative Work Conference,1994:175-186.

[13] BREESE JS,HECKERMAN D,KADIE C.Empirical Analysis of Predictive Algorithms for Collaborative Filtering[C].Process of the 14th Coference on Uncertainty in Artificial Intelligence,1998:43-52.

[14] DUECK D,FREY B.Probabilistic sparse matrix factorization[J].University of Toronto,Toronto:Technical Report:PSI-2004-23,2004.

[15] RICCI F,ROKACHL,SHAPIRA B,et al.Recommender system hand-book[M].[S.l.]:Springer,2011.

[16] 张航,叶东毅.一种基于多正则化参数的矩阵分解推荐算法[J].计算机工程与应用,2017,53(3):74-79.

[责任编辑、校对：周 千]

A Recommendation Algorithm Based on Probabilistic Matrix Factorization

ZHANGBian

(College of Information Engineering,Lanzhou University of Finance and Economics,Lanzhou 730000,China)

In this paper,we propose a probabilistic matrix factorization recommendation algorithm based on stochastic gradient descent to solve the problem of poor scalability and data sparsity.This algorithm is to generate two random number matrices with Gaussian distribution,which are then continuously trained and updated to make their inner product close to user rating matrix.In order to avoid over-fitting the training data,the regularization constraint is applied,and the model is optimized through the batch process of stochastic gradient descent.Data from experiment on the MovieLens show that the proposed algorithm not only relieves the problem of poor scalability and data sparsity,but also improves the accuracy compared with the traditional collaborative filtering algorithm.

recommendation algorithm;collaborative filtering;probabilistic matrix factorization;stochastic gradient descent

2017-02-21

张昪(1994-)，女，山西临汾人，硕士研究生，主要从事数据挖掘个性化理论与方法研究。

TP301.6

A

1008-9233(2017)03-0078-06