结合物品流行度的列表级矩阵因子分解算法

周瑞环，赵宏宇

(西南交通大学 信息科学与技术学院，成都 611756)(*通信作者电子邮箱nuomimick@163.com)

0 引言

近年来，随着信息技术的迅速发展，互联网进入到Web 2.0时代。在Web2.0时代，用户不再是信息的接受者，更是信息的制造者与传播者。而随着越来越多的信息充斥着网络，用户无法从大量的信息中获取对自己真正有用的那部分信息，对信息的使用效率反而降低了，这就造成了“信息过载”问题[1]。

为了解决“信息过载”问题，在互联网的发展过程中出现了分类目录、搜索引擎、个性化推荐系统。个性化推荐系统主要用于预测一个用户是否会喜欢一个特定的物品(评分预测问题)或者是为一个用户推荐感兴趣的N个物品[2](Top-N推荐问题)。协同过滤算法[3]是个性化推荐系统中应用最广泛的算法。协同过滤算法主要的两种技术分别是基于近邻的算法和矩阵因子分解算法。基于近邻的算法考虑的是用户或物品之间的相似关系来解释用户对物品的评分。矩阵因子分解算法，考虑的是用户和物品在隐语义空间中的隐语义因子特征来解释用户对物品的评分。相对于基于近邻的算法，矩阵因子分解算法因其在稀疏数据集上的准确性和稳定性得到广泛的关注。而随着硬件的飞速发展和大数据时代的到来，基于深层神经网络的算法在各个领域都被广泛地研究。基于自动编码器的协同过滤算法[4]解决了评分预测问题。基于降噪自动编码器的协同过滤算法[5]解决了Top-N推荐问题。神经协同过滤算法[6]提出了一个通用框架将矩阵因子分解算法和神经网络结合到一起。基于深层神经网络的推荐算法可以学习出用户和物品之间的非线性关系，而不像矩阵因子分解算法只能学习用户和物品潜在特征的点乘关系。然而，基于深层神经网络的推荐算法网络架构难以改变，也就难以结合其他的信息改进推荐效果。因而，矩阵因子分解算法仍是推荐系统的利器。

隐语义模型(Latent Factor Model， LFM)算法[7]是最简单的矩阵因子分解模型。LFM算法认为正是用户与物品之间的交互作用才导致评分间的差异，因此把评分矩阵近似为用户矩阵和物品矩阵的乘积。用户矩阵的每一行代表了一个用户的隐语义因子向量，可以理解为用户对向量中每个因子的喜好程度。物品矩阵每一行代表了物品的隐语义因子向量，可以理解为物品拥有向量中每个因子的程度。评分中与用户与物品交互作用无关的部分称为偏置因子。产生偏置因子的原因在于每个用户评分的基准，每个物品被评分的基准都是不一致的。Koren[8]提出了奇异值分解(Singular Value Decomposition， SVD)算法，SVD++(transmutative Singular Value Decomposition)算法和Asymmetric-SVD算法。SVD算法认为用户对物品的评分由偏置因子和用户与物品的交互作用组成。SVD++算法在SVD算法的基础上考虑了物品之间的隐式相关性，并意识到隐式反馈数据对只拥有少量显式反馈数据的用户的重要性。Asymmetric-SVD算法将矩阵因子分解思想应用到基于近邻的算法。物品因子相似度模型(Factored Item Similarity Model， FISM)算法[9]是在隐式反馈数据集上提出的算法，其主要思想是物品之间的隐式相关性是物品推荐的重要因素。SVD++算法和Asymmetric-SVD算法的评分规则用到了用户有过行为的物品集合。在模型训练阶段，集合中包括待评分物品。在模型预测阶段，集合不包括待评分物品。算法的评分规则在两个阶段并不一致。

受到20世纪末GroupLens研究组和2006年Netflix Prize的影响，在很长一段时间内的学术研究都是基于优化评分预测指标——均方根误差(Root Mean Squared Error， RMSE)。有研究表明，评分预测的准确率和Top-N推荐准确率之间并没有直接关系[10]。直接以提高评分预测准确率为优化目标，并不一定可以提升Top-N推荐准确率。比如，用户对两个物品A和B的实际评分分别为2分和3分，模型一和模型二是由同一种算法采用不同随机数种子训练得到的模型。假设模型一对两个物品的预测评分分别是2.7分和3.5分，那么推荐列表中物品B的位置在物品A前面。模型二对两个物品的预测评分分别是2.7分和2.5分，那么推荐列表中物品A的位置在物品B前面。模型一和模型二的均方根误差相等，两个物品在推荐列表中的顺序却相反。这就可能导致用户感兴趣的物品不在Top-N推荐列表中，从而得不到推荐。为解决这个问题，有研究者提出了将排序学习应用于推荐的一些方法[11]。

排序学习[12]的思想是为每个用户，使用训练好的模型产生一个排序好的推荐列表，而不是为预测每个待推荐物品的评分。排序学习根据输入样本的不同可分为点级、对级、列表级。点级方法对用户的每个待评分物品进行评分，按照评分结果大小进行排序得到最后的推荐列表，本质上是一个回归或者多分类问题。SVD算法的目标函数是所有实际评分和预测评分的平方误差和，是典型的点级方法。对级方法[13]对用户的每一对待评分物品顺序进行判断，按照物品两两之间的顺序得到最后的推荐列表，本质上是一个二分类问题。列表级方法输入所有物品的集合，更加全面考虑了物品之间的顺序关系。列表级方法有两种方法：一种方法是定义列表级的损失函数并求解排序函数[14]；另一种方法将排序函数与最终对其的评价指标相关联，认为最优的排序函数必定会获得最优的评价指标[15]。文献[16]提出了一种列表的Top-N排序概率公式，该概率公式的不足之处在于相同评分的物品在推荐列表中的位置的概率是一样的。

针对上述SVD++算法的评分规则不一致问题和Top-N排序概率公式的不足，本文提出了一种结合物品流行度的列表级矩阵因子分解算法：1)在模型训练阶段，去除评分规则用到的用户有过行为的物品集合中的待评分物品，保证两个阶段评分规则的一致性。2)结合物品流行度改进了列表级Top-N概率公式，保证即使相同评分下，物品在列表中的位置概率也并不相同。3)使用随机梯度下降算法求解目标函数并进行Top-N推荐。在MovieLens和Netflix两个数据集上进行测试和比较分析，实验结果表明，与目标函数为点级和列表级的SVD++算法相比，本文算法有较高的Top-N推荐准确率。

1 基本定义与算法描述

1.1 基本定义

(1)

1.2 SVD++算法

SVD++算法[8]中用户u对物品i的评分规则如下：

(2)

其中pu、yj、qi分别为用户因子矩阵P的第u行向量、物品因子矩阵Y的第j行向量和物品因子矩阵Q的第i行向量。

该算法在SVD算法的基础上考虑了物品之间的隐式相关性。而这部分不需要显式评分，因此可以扩展到隐式反馈数据集上，从而更好地利用了用户行为数据。从另一个角度考虑，SVD++算法添加了第2个物品因子矩阵，这些新的物品因子向量根据用户有过行为的物品集合来描述用户的特征。

1.3 ListRank-MF算法

ListRank-MF算法[14]是一种列表级排序学习思想结合矩阵因子分解的推荐算法。在文献[13]中提出了一种列表的Top-N排序概率，假设用户u的推荐列表为y(i1,i2,…,in)，那么it表示列表t位置上的物品编号，ruit表示用户u对it物品的评分，则产生这个推荐列表的概率为：

(3)

为简化运算，ListRank-MF算法将n取为1，φ(x)=ex，从而得到推荐列表中物品i在列表中第1个位置上的概率，即列表的Top- 1排序概率为：

(4)

接着使用交叉熵表示真实概率分布和预测概率分布的差异。交叉熵越低，则说明两个分布越接近。目标函数为：

(5)

其中g(x)是sigmoid函数，用于限制输出范围。目标函数通过交替固定变量的梯度下降算法进行求解。

2 本文算法

SVD++算法的评分规则的一个问题在于评分规则在模型训练阶段和模型预测阶段的不一致。预测规则中的集合R(u)在模型训练阶段包括了待评分物品，在模型预测阶段不包括待评分物品，造成了预测规则在两个阶段的不一致。理论上来讲，模型训练阶段是不应该有待评分物品的所有信息的，否则会造成信息泄露。文献[9]在其算法中也指出当隐语义因子维度增大时两种情况的算法性能差异，因此，本文算法首先对评分规则进行修正，评分规则修正为：

(6)

其中R(u) {i}表示除了i物品外，用户u有过行为的物品的集合。

式(5)处的Top- 1列表概率的不足之处在于相同评分的物品的概率是一样的。而现实生活中，评分的等级是有限的。例如豆瓣电影网站，用户给看过的电影的评分等级就只有很差、较差、还行、推荐、力荐五个等级。假如豆瓣电影网站为某用户推荐的电影都在力荐这个等级，如果存在某种限制使得用户只能看列表中的部分电影，那么相同评分下，确定电影的位置顺序是很有意义的。尤其对于不活跃的用户来说，往往只观看推荐列表中的部分电影。

在现实生活中，物品流行度[18]和用户活跃度分布满足长尾分布。一般认为，不活跃的用户更倾向于浏览流行度高的物品，而活跃用户在浏览完热门的物品后会开始浏览流行度低的物品[3]。本文定义物品的流行度为物品被评分的次数。物品被评分的次数越多，说明该物品越流行。

基于以上分析，本文认为大量物品评分一样的情况下，流行度高的物品被推荐的概率越大，即排在列表第一个位置的概率越大，因此，对式(5)进行改进得到：

δ(i)=ci/(cmax+α)

(7)

其中：δ(i)表示物品i对评分的修正函数,δ(i)∈(0,1)；ci表示物品i被评分的次数；cmax表示最流行物品被评分的次数；伸缩系数α≥1，控制δ(i)的范围。将δ(i)限制到(0,1)区间的原因是本文认为物品流行度带来的影响应该小于直接由用户对物品的评分带来的影响。

接着，本文使用与ListRank-MF算法一样的交叉熵构造目标函数。在加入正则化参数后，最终的目标函数如下：

(8)

不同于文献[17]的方法，本文使用随机梯度下降算法求解该最优化问题。随机梯度下降算法有收敛速度快、时间复杂度低的优点。令：

(9)

则各参数的迭代计算公式如下：

(10)

其中：γ表示学习率；λ表示正则化系数。模型训练阶段算法伪代码描述如下：

输入：训练数据集D，学习率γ，正则化系数λ，隐语义因子特征维数f，迭代次数T。

输出：向量b(u)、b(i)，矩阵P、Q、Y。

向量b(u)、b(i)的值初始化为0

矩阵P、Q、Y的值随机初始到区间(0,1/sqrt(f))

fort=0,1,…,T-1 do

foru=0,1,…,m-1 do

计算fu,i

sum← 0

fori∈R(u) do

fori∈R(u) do

forj∈R(u) {i} do

yj-=γ(sum(nu-1)-1/2qi+λyj)

模型预测阶段，根据式(8)为每个用户计算其未评分物品排在列表第一个位置的概率。对于一个用户的所有物品，式(8)分母部分是一样的，因此只需要计算分子部分，选择值最大的Top-N的物品即可。

3 实验结果及分析

3.1 数据集和实验设置

本文的实验基于两个公开数据集，分别是MovieLens和Netflix数据集。MovieLens是GroupLens研究小组公布的MovieLens电影推荐系统中用户对电影评分数据集。Netflix数据集是美国Netflix公司在2006年举办评分预测竞赛时公布的数据集。对于每个数据集，本文随机选择75%的评分数据作训练集，剩余25%的评分数据作测试集。数据集说明如表1所示。

本文实验采用归一化折损累积增益(Normalized Discounted Cumulative Gain， NDCG)指标[18]。NDCG是一种应用广泛的、和顺序相关的Top-N推荐准确率评价指标，其计算方法如下：

(11)

其中：U表示用户集合，R(u,p)是用户u对推荐列表中第p个位置上物品的评分，DCG(Discounted Cumulative Gain)即折损累积增益，IDCG@N(u)为所有DCG@N(u)的最大值。如果推荐列表有物品不在测试集中，则相应评分为0。对于不同的NDCG@N，测试集中应保证每个用户至少有N个评分对象。

表1 实验中使用的数据集

本文将基于以下几个算法作比较分析。

PopularRec 基于物品流行度的推荐算法。为每个用户推荐未有过行为的物品中最流行的N个物品。

SVD++_rmse 基于修正的SVD++评分规则，使用点级目标函数，即实际评分与预测评分的平方误差和，记为点级SVD++算法。

SVD++_ce 基于修正的SVD++评分规则，使用列表级目标函数，即实际评分分布和预测评分分布的交叉熵，记为列表级SVD++算法。

SVD++_cep 基于修正的SVD++评分规则，根据物品流行度改进了列表的Top- 1排序概率，使用列表级目标函数，即实际评分分布和预测评分分布的交叉熵，是本文提出的算法，即结合物品流行度的列表级矩阵因子分解算法。

本文所有算法均在Windows操作系统下使用Python在Pycharm开发平台上编写，计算机配置为4核Intel Core i7处理器2.8 GHz、24 GB内存。

3.2 实验结果

3.2.1 不同算法性能对比

图1是本文算法的学习率为0.01，正则化系数为0.001时，在Movielens- 100k数据集上，NDCG值随着迭代次数变化的趋势图。从图1中可以看出本文算法在迭代次数为15以后，NDCG值变化幅度已经不大，算法已经收敛。

图1 本文算法随迭代次数变化的性能趋势

表2是PopularRec算法在两个数据集上的不同推荐列表长度的性能对比。从表2可以看出，PopularRec算法不稳定，不同推荐列表长度的NDCG值在Movielens- 100k数据集上远大于在Netflix-s数据集上。也就是说PopularRec算法在Movielens- 100k数据集上能够有效地进行Top-N推荐，在Netflix-s数据集上却不能。

图2展示了除PopularRec算法外，其他3种算法在两个数据集上的不同推荐列表长度的性能对比。

表2 PopularRec算法在两个数据集上的性能对比

图2 不同算法在两个数据集上的性能

从图2中可以看出，同一种算法，不同推荐列表长度的NDCG值不同，推荐列表长度越长，NDCG值越大。都是基于修正的SVD++评分规则，不同算法在相同推荐列表长度下的NDCG值不同，列表级SVD++算法的NDCG值在两个数据集上都明显高于点级SVD++算法。在Netflix-s数据集上和推荐列表长度为5的时候，列表级SVD++算法和点级SVD++算法的NDCG值差异更为显著。本文算法相比列表级SVD++算法，不同推荐列表长度的NDCG值都有所提升，具体提升程度如表3所示。

表3 本文算法较列表级SVD++算法的性能提升程度 %

3.2.2 评分规则包括待评分物品与否对算法的影响

图3是在MovieLens- 100k数据集上，评分规则中的用户有过行为的物品集合中是否包括待评分物品对点级SVD++算法和本文算法的性能影响(N=10)。图3中后缀为ex的表示不包括待评分物品，in表示包括待评分物品。

从图3中可以看出是否包括待评分物品对本文提出算法的影响不大，两者曲线基本重合。这种情况下，应尽量避免信息泄露带来的影响，保证评分规则在两个阶段保持一致，选择不包括待评分物品更加合理。而对于点级SVD++算法，尽管包括待评分物品会导致两个阶段预测规则的不一致，但是从实验结果看来，算法性能反而更好。随着隐语义因子维度增大，两种算法性能都有所提升。

图3 算法在不同隐语义因子维度的性能

3.2.3 伸缩系数α大小对本文算法的影响

图4展示了推荐列表长度为10，本文算法性能在两个数据集上，随着伸缩系数α增大的性能趋势变化。从图4中可以看到，随着α增大，算法性能在MovieLens数据集上逐渐下降，而在Netflix数据集上性能有微小的提升。α的取值跟具体数据集有关。

图4 本文算法在不同伸缩系数α的性能(N=10)

4 结语

针对SVD++算法预测规则和ListRank-MF算法Top- 1排序概率存在的问题，本文提出了一种结合物品流行度的列表级矩阵因子分解算法。实验结果表明本文算法的Top-N推荐准确率优于点级SVD++算法和列表级SVD++算法，同时说明了排序学习中的列表级方法更加接近Top-N推荐的本质，以及物品流行度对用户选择的影响。该方法仅仅只使用了用户对物品的评分信息，没有考虑用户和物品的边信息(side information)。下一步的工作将研究在矩阵因子分解算法的基础上如何有效地利用边信息，以及关注神经网络在推荐领域的最新研究。