随着互联网时代的来临，网络资源数量呈爆炸式增长，个性化推荐系统建立在大量用户数据的基础上，能够为每位用户推荐出最感兴趣或者最需要的信息。近年来，个性化推荐算法已经成为学术界的研究热点之一。推荐系统中应用最广泛的是协同过滤推荐算法(CF, Collaborative Filtering)，其概念最早由1992年Goldberg等^[1]在开发Tapestry邮件过滤系统时首次提出，其核心思想是通过算法对用户的历史行为数据进行分析，并挖掘出用户的兴趣偏好，根据不同的兴趣偏好对用户进行类别划分并推荐偏好相似的物品。目前，在推荐算法中还存在数据稀疏性、可扩展性、冷启动等问题。数据的稀疏性是造成推荐系统精确度不高的主要原因之一。广泛应用的推荐系统中，用户项目(user-item)评分矩阵提供了反映用户对项目喜好程度的重要信息。当项目数量巨大时，评分矩阵往往具有高度的稀疏性，缺失率甚至会达到90%以上。极度稀疏的用户评分矩阵会使得利用经典的协同过滤算法计算的相似性精度不高，无法准确找出目标用户的最近邻居。为解决评分矩阵的稀疏性问题，常用的方法有两类，一类是基于预测项目评分的协同过滤算法，例如，韩亚楠等^[3]和Liji等^[4]分别利用用户属性偏好和用户的属性来对评分矩阵进行填充。另一类解决稀疏性的方法是利用奇异值分解(SVD, Singular Value Decomposition)对评分矩阵进行降维^[5-7]。但在维数很高的情形中，降维将会导致信息损失，影响模型预测效果。Bokde等^[8-9]指出将多种传统推荐算法相结合可以有效提高推荐精确度。当用户与项目数量巨大时，计算量较大，推荐算法很难在短时间内作出响应。在推荐算法中融合聚类方法可以有效提高推荐系统的响应速度^[9-11]。

除了上述基于协同过滤算法建立的个性化推荐系统，也有很多基于机器学习方法建立的推荐系统，例如，胡思才等^[12]建立了基于深度神经网络和概率矩阵分解的混合推荐算法；Wei等^[13]结合协同过滤与深度学习方法解决冷启动问题。Wang等^[14]提出的树增强嵌入方法并结合树模型和嵌入模型的优点，使得推荐模型同时具有可泛化性和可解释性。Chen^[15]提出了XGBoost (eXtreme Gradient Boosting)算法，它是一种集成树模型，能在梯度提升(Gradient Boosting)框架下实现大规模集成学习，其特点是计算高效，能够解决实际问题。分析结果显示，XGBoost算法有助于提升推荐问题中的精确度^[17-18]。这归功于XGBoost算法能从大规模数据集中学习到数据之间复杂的相关性。

为了解决评分矩阵的稀疏性问题，提高推荐精确度，文中提出基于矩阵分解与XGBoost集成学习方法构建的个性化推荐算法MFXGB(Matrix Factorization XGBoost algorithm)。该推荐算法实质为一个监督模型，可以充分利用用户项目评分矩阵中的信息和用户及项目自身的特征，利用聚类方法降低计算时间，并且能够有效提高推荐的准确度。

1 融合矩阵分解与XGBoost的推荐算法 1.1 填充评分矩阵(SVD++算法)

MFXGB推荐算法可分为3个阶段，第一阶段就是采用矩阵分解的方法来填充用户项目评分矩阵。假设用户项目评分矩阵R=(r_ui)_n×m，它包含了n个用户对m个项目的评分，其中，元素r_ui表示用户u对项目i的评分。经典的矩阵分解方法为SVD算法^[18]，是将含有缺失值的用户项目评分矩阵R，用$ \mathit{\boldsymbol{\widehat R}} = \mathit{\boldsymbol{PQ}}$来近似，即选择一个小于n和m的d，去估计维度为n×d的矩阵P_n×d和维度为d×m的矩阵Q_d×m。假设$\boldsymbol{q}_{i} \in \mathbb{R}^{d} $为矩阵Q的第i列向量，${\mathit{\boldsymbol{p}}_u} \in {\mathbb{R}^d} $为矩阵P的第u行向量，则它们的内积$ \boldsymbol{q}_{i}^{\mathrm{T}} \boldsymbol{p}_{u}$代表用户u对项目i的兴趣偏好，即预测评分，记为${{\hat r}_{ui}} $。需要估计P和Q，使得它们的乘积近似等于评分矩阵R，${{\hat r}_{ui}} $≈r_ui。考虑到用户和项目都存在个体偏差，用户u对项目i的预测评分${{\hat r}_{ui}} $可表示为

$ {\hat r_{ui}} = \mu + {b_i} + {b_u} + \mathit{\boldsymbol{q}}_i^{\rm{T}}{\kern 1pt} {\mathit{\boldsymbol{p}}_u}, $

(1)

其中：μ为基准评分；b_i为项目i的个体偏差；b_u为用户u的个体偏差。

SVD++算法^[18]在SVD算法的基础上进一步引入了用户对有过评分行为的项目的“隐式反馈”信息。假设用户u对项目i有评分，代表该用户u对项目i有偏好，在式(1)中进一步增加用户u的已有偏好信息。定义$\mathit{\boldsymbol{x}}_{j} \in \mathbb{R}^{d}, j=1, \cdots, m $为每个项目对应的因子向量，表示项目j的评分特征向量。用户u对项目i的近似评分可以表示为式(2)。

$ {\hat r_{ui}} = \mu + {b_i} + {b_u} + \mathit{\boldsymbol{q}}_i^{\rm{T}}\left( {{\mathit{\boldsymbol{p}}_u} + \frac{1}{{\sqrt {|N(u)} |}}\sum\limits_{j \in N(u)} {{\mathit{\boldsymbol{x}}_j}} } \right), $

(2)

其中：N(u)表示用户u评价过的项目集合；|N(u)|表示用户u给出评价的项目数。式(2)相较于式(1)增加了已有评分的所有隐含信息项$ \boldsymbol{q}_{i}^{\mathrm{T}}\left(\frac{1}{\sqrt{\mid N(u)}} \sum\limits_{j \in N(u)} \boldsymbol{x}_{j}\right)$。估计特征矩阵P和Q可以通过最优化式(3)中的目标函数来实现，该目标函数是由损失函数加上正则项构成，λ为正则项中的调节参数。

$ \begin{array}{l} \mathop {\min }\limits_{{b_i},{b_u},{\mathit{\boldsymbol{q}}_i},{\mathit{\boldsymbol{p}}_u},{x_j}} \sum\limits_{{r_{ui}} \in \mathit{\boldsymbol{R}}} {{{\left( {{r_{ui}} - \mu - {b_i} - {b_u} - \mathit{\boldsymbol{q}}_i^{\rm{T}}\left( {{\mathit{\boldsymbol{p}}_u} + \frac{1}{{\sqrt {\mid N(u)\mid } }}\sum\limits_{j \in N(u)} {{\mathit{\boldsymbol{x}}_j}} } \right)} \right)}^2}} + \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \lambda \left\{ {\sum\limits_u {\left( {b_u^2 + {{\left\| {{\mathit{\boldsymbol{p}}_u}} \right\|}^2}} \right)} + \sum\limits_i {\left( {b_i^2 + {{\left\| {{\mathit{\boldsymbol{q}}_i}} \right\|}^2}} \right)} } \right\}。\end{array} $

(3)

MFXGB推荐算法采用SVD++算法填充用户项目评分矩阵，将最优化式(3)得到的特征矩阵估计${\mathit{\boldsymbol{\hat P}}} $和$ {\mathit{\boldsymbol{\hat Q}}}$带回式(2)，对用户项目评分矩阵中R中的缺失值进行填充。

1.2 特征的构造

MFXGB算法的第二阶段就是利用聚类算法构造用户和项目的特征。第一阶段已经利用矩阵分解的方法得到了填充完整的用户评分矩阵，即预测得到了用户项目的“评分”特征，可以用作模型的自变量。但在实际应用中，用户和项目的个数都可能巨大，将其作为自变量直接利用XGBoost算法进行训练的计算成本过高，对处理大数据时产生的计算量巨大的问题尤为突出。为此，采用聚类方法将用户和项目按相似度分门别类，再计算每个用户和项目的“类别”特征，以节约计算时间。

具体来说，用户评分矩阵的行向量代表用户的评分向量。基于n个用户的评分向量，将这n个用户分成K₁个类别，每个类别代表用户的评分偏好属性。例如，有些用户比较挑剔，总是给予很低的评分，可以将其归入一个类别；有些用户总是给予较高的评分，则将其归入另一个类别。文中采用K-均值方法进行聚类，类别数K₁可根据实际问题自行设定。特别地，若K₁=n，则代表不对用户进行聚类，以每个用户的评分向量作为其“评分”特征。同理，将m个项目分成K₂个类别，每个类别代表项目的类别评分属性。例如，有些小众的文艺电影总是评分不高，而有些动作大片受到很多人的关注和欢迎，可以分别将它们归入不同的类别。同理，若K₂=m，则代表不对项目进行聚类。

进行聚类后，可分别计算得到每类用户和项目的中心向量，再通过计算每个用户的评分向量与K₁类用户的中心向量之间的相似度，这就是用户的“评分”特征。这里采用Pearson相关系数来计算评分向量与中心向量之间的相似度。相似度越高，表明该用户与某个类别用户的评分偏好越相似。例如，将用户聚为三类，计算得到用户1的评分向量与三类的中心向量的相似度分别为0.7、0.5和0.4，这表明用户1和第一类用户的评分偏好最为相似。将(0.7, 0.5, 0.4)这个向量作为用户1的“评分”特征，在下一步中放入XGBoost模型进行训练。同理，可以计算得到每个项目的评分向量与K₂类项目的中心向量之间的相似度，作为项目的“评分”特征。

除此之外，每个用户和每个项目还有其自身的特征，例如，基于电影的数据集中，用户的年龄、性别、职业、电影的类别等。假设共有K₃个这样的特征，称为基础特征。那么，将K₁个用户“评分”特征、K₂个项目“评分”特征和K₃个用户与项目的基础特征结合在一起，构成(nm)×(K₁+K₂+K₃)维的特征矩阵，用于训练预测模型。

1.3 建立XGBoost预测模型

MFXGB算法的第三阶段就是利用XGBoost算法训练推荐模型。XGBoost算法^[15]利用集成树模型预测响应变量，并用梯度提升树算法优化求解。假设数据集中有n个样本，p个特征，记为$ \left\{\left(y_{i}, \boldsymbol{X}_{i}\right)\right\}_{i=1}^{n}$，其中, $y_{i} \in \mathbb{R}, \boldsymbol{X}_{i} \in \mathbb{R}^{p} $。集成树模型是利用多棵回归树的结果对y_i进行预测，即

$ {\hat y_i} = \sum\limits_{m = 1}^M {{f_m}} ({\mathit{\boldsymbol{X}}_i}), $

(4)

其中，f_m为第m棵回归树的函数表达式。常用的回归树为加法形式，即$f_{m}\left(X_{i}\right)=\sum\limits_{j=1}^{T} \omega_{j} I\left(q\left(\boldsymbol{X}_{i}\right)=j\right) $，其中，T表示回归树中的叶节点个数；q(X_i)表示回归树的划分规则；ω_j表示第j个叶节点上的输出值；I(·)为示性函数。为了估计式(4)中的树结构和参数，定义目标函数为

$ L = \sum\limits_i l \left( {{{\hat y}_i},{y_i}} \right) + \sum\limits_k \varOmega \left( {{f_k}} \right), $

(5)

其中，l(·, ·)为损失函数，$\Omega\left(f_{k}\right)=\gamma^{\mathrm{T}}+\frac{1}{2} \lambda\|\omega\|^{2} $为正则项，用于控制模型的复杂程度。XGBoost算法采用梯度提升树(Gradient Tree Boosting)算法求解式(5)的最优化问题，即使得目标函数L达到最小。为求解该优化问题，采用迭代法，在每一次迭代中都加入一棵新的回归树去减小估计误差，则第t次迭代的目标函数定义为

$ {L^{(t)}} = \sum\limits_{i = 1}^n l \left( {{y_i},\hat y_i^{(t - 1)} + {f_t}\left( {{\mathit{\boldsymbol{X}}_i}} \right)} \right) + \varOmega \left( {{f_t}} \right)。$

(6)

将上述目标函数在$\hat{y}_{i}^{(t-1)} $处进行二阶泰勒展开，并省略其中的已知项$ l y_{i}, \hat{y}_{i}^{(t-1)}$，可得到第t次迭代的目标函数为

$ L(t) \cong \sum\limits_{i = 1}^n {\left[ {{g_i}{f_t}\left( {{\mathit{\boldsymbol{X}}_i}} \right) + \frac{1}{2}{h_i}f_t^2\left( {{\mathit{\boldsymbol{X}}_i}} \right)} \right]} + \varOmega \left( {{f_t}} \right), $

(7)

其中，g_i和h_i分别为损失函数在$\hat{y}_{i}^{(t-1)} $处的一阶和二阶导数。此处用二阶泰勒展开近似目标函数是XGBoost算法区别于经典梯度提升树算法的特点之一，有利于对目标函数的快速优化。给定一个回归树结构及划分规则q(X_i)，定义$ I_{j}=\left\{i \mid q\left(\boldsymbol{X}_{i}\right)=j\right\}$为被划分到叶节点j上的样本集合。经过推导, 可确定第t次迭代中的最优权重和响应的目标函数值，表达式为

$ \omega _j^* = - \frac{{\sum\limits_{i \in {I_j}} {{g_i}} }}{{\sum\limits_{i \in {I_j}} {{h_i}} + \lambda }},{\rm{ }}{\tilde L^{(t)}}(q) = - \frac{1}{2}\sum\limits_{j = 1}^T {\frac{{{{\left( {\sum\limits_{i \in {I_j}} {{g_i}} } \right)}^2}}}{{\sum\limits_{i \in {I_j}} {{h_i}} + \lambda }}} + \gamma T。$

(8)

然后采用贪婪算法(Exact Greedy Algorithm)寻找最优的q(·)，使得$\widetilde{L}^{(t)}(q) $达到最小，第t次迭代完成，进入下一次迭代，直到满足停止条件。

MFXGB算法第三阶段将第二阶段中构建的特征矩阵中用户和项目特征作为自变量$ \boldsymbol{X}_{i} \in \mathbb{R}^{K_{1}+K_{2}+K_{3}}$，以用户对项目的评分作为因变量y_i，i=1, …, nm。再利用XGBoost算法训练模型，并且对算法中的参数进行调优，例如，优化过程中的学习率、停止条件中的树的最大深度、子模型的最大数量、正则化项中的参数λ和γ。最后，利用训练好的模型可以得到目标用户对未评分项目的预测评分，并以预测评分由高到低的顺序向该用户产生推荐结果。

1.4 MFXGB算法步骤

基于矩阵分解的XGBoost个性化推荐算法(MFXGB)主要包括以下3个步骤，其算法步骤如图 1所示。

步骤1.使用SVD++的矩阵分解方法填充用户项目评分矩阵中缺失的元素；

步骤2.利用填充完整的矩阵通过聚类算法构造用户和项目的特征，即分别将用户和项目进行聚类，计算每个用户和项目的“类别”特征，再加入用户和项目的基础信息，最终将数据集处理成一个适用于有监督训练的数据集。

步骤3.使用XGBoost算法对目标项目进行评分预测，根据预测结果生成推荐列表。

2 实验结果与分析 2.1 数据来源与数据描述

实验采用Minnesota大学GroupLens研究小组提供的MovieLens实验数据集(http://grouplens.org/datasets/movielens/)，其中包括2组不同规模的数据集，如表 1所示。数据集的记录格式为用户ID、项目ID、评分值、评分时间，其中每个用户至少对15部电影进行评分，评分范围为1~5的正整数，值越高表示用户对该电影的喜爱程度越高。

除了用户评分数据集外，还有用户和电影的信息记录维表。在用户信息维表中，记录了每个用户的年龄、性别、职业与邮政编码等信息。在电影信息维表中，记录了电影的名称、发布时间、链接以及所属的类别等信息，原数据集中将所有电影共分为19个类别，每一部电影可能会属于几个不同的类别。

实验环境配置如下：PC Inter(R)Core(TM)i5-8300H CPU @2.30GHz64位操作系统，虚拟内存24 G，编程语言：python3.7。

2.2 评价指标

为了衡量算法的预测准确度，采用平均绝对误差(MAE, mean absolute error)和均方根误差(RMSE, root mean square error)对算法进行评价，其定义如下：

$ {\rm{MAE}} = \frac{1}{m}\sum\limits_{i = 1}^m {\left| {{{\hat y}_i} - {y_i}} \right|} $

$ {\rm{RMSE}} = \frac{1}{m}\sqrt {\sum\limits_{i = 1}^m {{{\left( {{{\hat y}_i} - {y_i}} \right)}^2}} } $

其中，${{\hat y}_i} $和y_i分别为第i个项目的预测得分和真实得分。MAE或RMSE的值越小，说明预测值与实际值越接近，预测结果的准确度越高.

为了避免偶然性对实验结果的影响，文中利用五折交叉验证的方法对推荐算法的效果进行评估，即将原始数据集等分为5个子集，每次选择其中的4个子集作为训练集，剩下的1个子集作为测试集。最终将5次实验中得到的预测误差取平均值，来衡量算法的推荐精确度。将文中MFXGB推荐算法的结果与传统的协同过滤推荐算法进行对比。

2.3 结果分析 2.3.1 算法的效果展示

将MFXGB算法与矩阵分解(SVD++)推荐算法、基于项目的协同过滤推荐算法(Item-CF)和基于用户的协同过滤推荐算法(User-CF)进行比较，以验证MFXGB算法的有效性。取聚类数为60，在MFXGB算法中取K₁=K₂=60，基于数据集MovieLens_100k计算得到的实验结果，如图 2所示。

可以看出，MFXGB推荐算法的RMSE和MAE明显小于传统的协同过滤推荐算法和矩阵分解算法。特别地，不进行聚类的MFXGB模型的预测效果最好，RMSE比SVD++算法提升了26.61%，比Item-CF和User-CF算法分别提升了27.64%和28.93%，MAE相比于SVD++算法、Item-CF和User-CF算法分别提升了28.93%、30.08%和31.51%。当聚类数K₁=K₂=60时，MFXGB算法的RMSE比SVD++、和Item-CF和User-CF算法分别提升了8.91%、10.18%和11.79%，MAE分别提升了8.79%、10.26%和12.10%，推荐精确度也有明显提高。但是，不进行聚类的MFXGB算法计算成本非常高，它的计算时间是MFXGB算法(K₁=K₂=60)的14.96倍。可见利用聚类方法构造特征将有效提升计算速度。

为了避免小数据集带来的偶然性，采用数据量更大的MovieLens_1M数据集验证算法的普适性，仍取聚类数为60，实验结果如图 3所示。不聚类的MFXGB算法计算量较大，计算时间将超过30 h，因此未记录不聚类的MFXGB算法结果。同样可以看出，针对MovieLens_1M数据集，MFXGB推荐算法的精确度都明显好于其他3种算法。

2.3.2 MFXGB算法的稳健性分析

MFXGB算法的稳健性主要从聚类数、矩阵填充和加入用户与项目的基础特征这3个方面进行分析，实验结果均基于MovieLens_100k数据集。

1) 聚类数对计算时间和推荐算法效果的影响。

选取聚类数K₁=K₂分别为10、20、30、40、50、60、70、80、90、100、200，K₁=n, K₂=m(不聚类)，将MFXGB算法的预测误差和计算时间绘制成折线图，如图 4所示。可见随聚类数量的增加，算法的RMSE和MAE均呈下降趋势；当不进行聚类时，算法预测精度明显提升，但计算时间成本较高。因此，在实际应用中，应兼顾计算时间成本与预测效果来选择聚类数。

2) 矩阵填充对算法效果的影响。

MFXGB推荐算法的特点之一就是事先对用户评分矩阵进行填充。将MFXGB算法与未进行缺失值填充的XGBoost算法进行效果对比，实验结果如图 5所示。使用未填充用户评分矩阵的XGBoost算法时，先将评分矩阵中的缺失值填充为零，再进行聚类。可以看出，随聚类数量k的增加，填充矩阵对模型的效果提升显著。当取聚类数为60时，MFXGB算法比XGBoost算法的RMSE和MAE均减小了4.5%，结果表明，矩阵分解对用户评分矩阵进行填充，能够提高算法的精确度。

3) 加入用户和项目的基础特征对模型的影响。

MFXGB推荐算法的另一大特点是建立了基于XGBoost算法的有监督模型，在聚类后产生的用户和项目特征基础上再加入年龄、性别、职业作为用户的基础特征，加入电影类型作为项目的基础特征。

图 6绘制了MFXGB算法加入基础特征与不含加入基础特征的预测误差RMSE和MAE并随聚类数变化的折线图。实验结果表明，加入用户和项目基础特征对算法有一定的提升效果。无论聚类数为多少，加入用户和项目的基础特征的MFXGB算法的预测误差始终小于不加入基础特征的算法。进一步说明增加基础信息会提升推荐精确度。

2.3.3 推荐结果展示

运用MFXGB算法训练的模型，生成所选取的用户的推荐列表。表 2展示了2个用户的Top10推荐列表。

以用户1为例，在Top10的推荐列表中，有6部电影都有用户1的5分评分，表明该用户非常喜爱这6部电影。考虑到只挑选了预测评分排名前10的电影进行推荐，而这些电影的推荐评分大多都在4.5分以上，基于数据集MovieLens_100k，计算所有用户产生的Top10推荐列表中，用户评价为5分的电影数量占MFXGB算法推荐的10部电影的平均比例为28.57%。说明MFXGB算法对用户评价为5分的电影的推荐精确率(precision)达到28.57%。考虑到各个用户评为5分的电影数量可能各不相同，针对这一情况，计算Top10推荐列表对用户评为5分电影的召回率，即Top10列表中所推荐的电影中用户真实评价为5分的电影所占比例。基于数据集MovieLens_100k，计算得到用户评价为5分的电影召回率为19.18%。除此之外，在Top10推荐列表中，推荐给用户的未评分电影平均数为6.63，表明MFXGB算法能推荐大约6部给用户未看过但可能感兴趣的电影，可以为商家带来盈利。

3 结论

随着网络资源数量的快速增加，传统推荐算法受限于高度稀疏的用户项目的评分矩阵，推荐效果不佳。针对评分矩阵高度稀疏性问题，文中提出的融合矩阵分解和XGBoost的推荐算法MFXGB，能够有效解决用户项目评分矩阵的稀疏性问题并提升推荐精确度。MFXGB算法具有三大特点：一是事先对用户项目评分矩阵进行填充，避免过多的缺失值对模型预测结果产生影响；二是对用户和项目进行K-均值聚类，对用户和项目进行特征提取，克服计算成本过高的困难；三是利用XGBoost算法训练一个有监督模型用于预测用户评分，该模型还允许加入用户和电影的自身属性作为自变量，使信息量更加丰富，有利于提升模型预测效果。实证结果表明，MFXGB的推荐效果明显优于传统的推荐算法。MFXGB算法可以广泛应用于各个领域，如旅游景点、商品、音乐、新闻、图书等推荐问题中，帮助消费者找到自己感兴趣的东西，同时也能够为商家创造不菲的收益。