0 引言

随着Internet的快速发展，数据资源每天以几何数量级增加，在如今电子商务蓬勃发展的时代，卖家提供的商品种类和数量非常庞大，如何快速有效地找到最需要的商品成为消费者的一个难题。在这种背景下，推荐系统 (Recommender System, RS) 应运而生，它能够为消费者推荐潜在喜欢的商品。协同过滤 (Collaborative Filtering, CF) 方法^[1]是推荐系统中应用比较广泛的技术，其主要分为两类：基于记忆 (memory-based) 和基于模型 (model-based)。基于记忆的算法通过分析用户的历史喜好信息，寻找相似的用户或项目，然后根据这些相似的用户或项目对目标用户的喜好程度进行预测，如K近邻算法 (K-Nearest Neighbor, KNN)。真实的购买环境中，用户不可能对每一个项目进行评分，导致评分数据极度稀疏。当没有足量的评分可用时，基于记忆的方法很难提供准确的预测^[2]。基于模型的算法主要利用已有用户喜好信息，训练出一个推荐模型进行推荐，如基于矩阵分解^[3-4]、概率模型^[5]、图模型^[6]算法等。

矩阵分解推荐算法是一类实现简单、预测精度高的CF推荐技术。它的目标是将原始评分矩阵分解为两个低维度的潜在特征矩阵，这在一定程度上改善了数据稀疏性问题^[7]。Koren等^[3]详述了矩阵分解算法在推荐系统中的应用，这些算法在一定程度上提高了推荐精度，但没有考虑评分数据的群结构性问题。Salakhutdinov等^[4]提出了一种概率矩阵分解推荐算法，该算法较好地解决了冷启动问题，但也没有考虑评分数据的群结构性问题。Yuan等^[8]提出了一种群稀疏矩阵分解推荐算法，该算法能够挖掘多种类型的评分数据信息，但其仅针对评分数据具有列相关性的问题。

在推荐系统中，输入数据往往是一种类型的评分矩阵，比如常见的图书评分矩阵、电影评分矩阵等。现实生活中，用户可以分为不同的群体，同一个群体内的用户通常具有相似的兴趣爱好，而评分矩阵中的一行表示一个用户的评分行为，这使得评分矩阵的行具有很高的相关性。本文主要利用群稀疏约束将评分矩阵的群聚性转化为用户群与潜在特征的关系。以电影推荐系统为例，用户群与潜在电影特征的关系如表 1所示，存在3类观影群体：年轻观众u¹，女性观众u²，男性观众u³，每部电影用4个潜在特征来表示：恐怖、喜剧、动作和爱情。从表 1中可以看出，u¹选择潜在特征{1}和{2}；u²偏好潜在特征{2}和{4}；u³喜好潜在特征{1}和{3}。本文的目的是根据评分相似性从评分矩阵中找出这3类群体，并筛选出它们喜好的潜在特征，而传统的矩阵分解模型忽略了这些信息，这在一定程度上降低了推荐信息的利用率。

本文针对评分数据的群结构性问题，提出了一种基于评分相似性的群稀疏矩阵分解推荐算法 (Score Similarity based Matrix Factorization recommendation algorithm with Group Sparsity，SSMF-GS)。该算法首先根据评分的相似性对用户进行分群；然后在矩阵分解过程中利用L_{2, 1}范数训练得到一个群稀疏的潜在用户特征矩阵；最后通过潜在用户特征矩阵和潜在项目特征矩阵的内积进行评分预测为目标用户产生推荐。该方法可以自动筛选出不同用户群的共有潜在项目特征和私有潜在项目特征，共有潜在特征表示用户群之间的联系，私有潜在特征则表示用户群之间的差异。实验结果证明本文算法具有较好的预测精度。

1 相关工作 1.1 矩阵分解推荐算法

设用户全集为U={u₁, u₂, …, u_m}，项目全集为V={v₁, v₂, …, v_m}，m表示用户数量，n表示项目数量。记U中用户u_i对项目v_j的评分为r_ij，r_ij=0表示用户u_i对项目v_j没有评分，完整的用户-项目评分矩阵如表 2所示。

协同过滤推荐系统中矩阵分解的思想是把评分矩阵分解为两个低维数的矩阵p∈R^k*m和q∈R^k*n，它们分别用于描述用户特征和项目特征。用户和项目之间的评分关系可以通过这些潜在特征向量的内积来建模，如式 (1) 所示:

$ {\hat r_{ij}} = {\boldsymbol{p}}_{.i}^{\rm{T}}{{\boldsymbol{q}}_{.j}} $

(1)

其中:p_i表示用户u_i的潜在特征向量，q_j表示项目v_j的潜在特征向量，${\hat r_{ij}} $表示用户u_i对项目v_j的预测评分。矩阵分解的目标就是计算得到p_i和q_j，使得式 (1) 能够尽可能地逼近真实评分r_ij。通常评分矩阵只有少部分评分数据，这容易导致模型过拟合，为了避免模型过拟合问题，可通过如下的目标函数进行训练：

$ \mathop {\min }\limits_{{\boldsymbol{p}} * ,{\boldsymbol{q}} * } {\sum\limits_{\left( {i, j} \right) \in K} {\left( {{r_{ij}}-{\boldsymbol{p}}_i^{\rm{T}}{{\boldsymbol{q}}_j}} \right)} ^2} + \lambda \left( {{{\left\| {{{\boldsymbol{p}}_i}} \right\|}^2} + {{\left\| {{{\boldsymbol{q}}_j}} \right\|}^2}} \right) $

(2)

其中：λ表示正则化系数，K表示已有评分集合， λ(‖p_i‖²+‖q_j‖²) 被用来防止训练过拟合。上述模型求解可以应用随机梯度下降 (Stochastic Gradient Descent, SGD) 法和交替最小二乘迭代 (Alternating Least Squares, ALS) 法。

1.2 群稀疏表示

稀疏表示 (Sparse Representation) 在图像分类及图像恢复等很多实际应用中表现出非常良好的性能，因而受到广泛的关注。稀疏表示模型一般采用L₁范数来度量稀疏性，没有考虑稀疏数据的群结构性。在很多实际应用中，数据矩阵本质上具有群结构的特性。比如，相同题材的新闻可以组成一个群，不同主题的文档形成不同的群等。群稀疏表示模型^[9]主要考虑的是稀疏数据的群结构性, 它将稀疏数据进行分群, 分别考虑每个群的稀疏先验，其主要采用L_{2, 1}范数来度量稀疏性。文献[10]将L_{2, 1}范数应用于有效图像特征选择。文献[11]利用L_{2, 1}范数定位采样服务质量 (Quality of Service, QoS) 信息中的结构化噪声行。本文主要将L_{2, 1}范数应用于群稀疏表示潜在用户特征矩阵。对于任意矩阵X∈R^k*m，其L_{2, 1}范数定义如式 (3) 所示:

$ {\left\| {\boldsymbol{X}} \right\|_{2, 1}} = \sum\limits_{i = 1}^k {{{\left\| {{{\boldsymbol{X}}_{i.}}} \right\|}_2}} = {\sum\limits_{i = 1}^k {\left( {\sum\limits_{j = 1}^m {X_{ij}^2} } \right)} ^{1/2}} $

(3)

2 群稀疏矩阵分解推荐算法 2.1 评分预测问题建模

上述式 (2) 正则化矩阵分解模型并没有考虑到评分矩阵的群结构特性，是一种全局优化的学习过程。本文算法在保持矩阵分解算法优点的同时，将用户群结构先验融入到矩阵分解过程中，得到一个群稀疏的潜在用户特征矩阵。最后通过潜在用户特征矩阵和潜在项目特征矩阵的内积对每个用户群内的用户进行评分预测。

在协同过滤推荐系统中，输入数据通常用一个如表 2所示的用户-项目评分矩阵R来表示。R中的一行表示某一个用户对所有物品的评分，可以看作该用户的一个评分行为向量。现实生活中，许多用户具有相同的兴趣爱好，这使他们的评分行为高度相似。本文根据用户的评分信息将用户集合U划分成C个用户群，即：U=(u¹, u², …, u^C)，每个用户群对应一个评分矩阵，即：R=(R¹, R², …, R^C)。对用户进行分群，实际上是一种聚类问题，属于同一簇的用户自然被划分到同一个群。目前的聚类方法有很多，主要有k-means、近邻传播 (Affinity Propagation，AP) 聚类^[12]等。由于聚类算法不是研究的重点，所以本文采用简单高效的k-means算法对用户进行基本聚类。

在用户聚类的基础上，通过对潜在用户特征矩阵施加L_{2, 1}范数约束，得到一个群稀疏的潜在用户特征矩阵，即：p=(p¹, p², …, p^C)。类似于式 (1)，用户群u^c对物品v_j的预测评分可通过p_.i^c和q_.j的内积获得，如式 (4) 所示:

$ {{\hat r}^c}_{ij} = {({\boldsymbol{p}}_{.i}^c)^{\rm{T}}}{{\boldsymbol{q}}_{.j}} $

(4)

如图 1基于评分相似性的群稀疏矩阵分解所示，原始评分矩阵被划分为3部分：R¹、R²和R³，分别对应评分用户群u¹、u²和u³，分解后得到的群稀疏潜在用户特征矩阵为p^c(c=1, 2, 3)(p^c中灰色和白色行分别表示1和0)。由式 (4) 可知，p^c中值为1的行可以筛选出u^c用户群的偏好潜在特征。从图 1可以看出，为u¹、u²和u³筛选出的潜在项目特征分别为{1, 2, 3}，{1, 2, 4}和{1, 3, 4}。比较u¹和u²偏好的潜在特征，{1, 2}是两个用户群的共有潜在特征，{3}和{4}是各自的私有潜在特征。通过对p^c(c=1, 2, 3) 施加群稀疏约束，本文算法能够学习到这些不同用户群间的共有和私有潜在特征。

基于上述对矩阵分解和群稀疏的分析，本文引入L_{2, 1}范数正则化项到矩阵分解模型中，将评分预测问题建模为如下问题:

$ \left\{ {\begin{array}{*{20}{l}} {\mathop {{\text{min}}}\limits_{p,q} L\left( {{\mathbf{p}},{\mathbf{q}}} \right) = \sum\limits_{c = 1}^c {{\beta _c}} ({f_c}({{\mathbf{p}}^c},{\mathbf{q}}) + \gamma {{\left\| {{{\mathbf{p}}^c}} \right\|}_{2,1}}) + } \\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\lambda (\left\| {\mathbf{p}} \right\|_F^2 + \left\| {\mathbf{q}} \right\|_F^2)} \\ {{f_c}\left( {{{\mathbf{p}}^c},{\mathbf{q}}} \right) = \sum\limits_{i = 1}^{{m_c}} {\sum\limits_{j = 1}^n {{\mathbf{I}}_{ij}^c{{\left( {{\mathbf{r}}_{ij}^c - {{\left( {{\mathbf{p}}_{.i}^c} \right)}^{\text{T}}}{{\mathbf{q}}_{.j}}} \right)}^2}} } } \end{array}} \right. $

(5)

其中，f_c(p^c, q) 被用来确保用户群u^c对物品v_j的预测评分$\hat r_{ij}^c $尽可能地接近真实评分r_ij^c，I_ij为指示函数，如果用户u_i^c对物品v_j已评分，则I_ij的取值为1，反之为0。β_c是一个控制用户群作用的可调参数。γ和λ被用来正则化模型，称为正则化系数。

2.2 模型求解

由于目标函数L(p, q) 含有两个变量，无法直接进行求解，为了避免同时存在多个变量，本文采用交替优化方法将式 (5) 分解成下述子问题交替求解变量p^c和q：

$ \mathop {\min }\limits_{{\boldsymbol{{p}^c}}} L\left( {{\boldsymbol{{p}^c}}} \right) = {\beta _c}\left( {{f_c}\left( {{\boldsymbol{{p}^c}}, \boldsymbol{{q}}} \right) + \gamma {{\left\| {{\boldsymbol{{p}^c}}} \right\|}_{2, 1}}} \right) + \lambda \left\| \boldsymbol{{p}} \right\|_F^2 $

(6)

$ \mathop {\min }\limits_\boldsymbol{{q}} L\left( \boldsymbol{{q}} \right) = \sum\limits_{c = 1}^C {{\beta _c}{f_c}\left( {{\boldsymbol{{p}^c}}, \boldsymbol{{q}}} \right) + \lambda \left\| \boldsymbol{{q}} \right\|_F^2} $

(7)

固定q求解p   函数L(p^c) 对p_.i^c求偏导数得：

$ \frac{{\partial L\left( {{\boldsymbol{{p}^c}}} \right)}}{{\partial \boldsymbol{{p}_{.i}^c}}} = \lambda \boldsymbol{{p}}_{.i}^c + {\beta _c}\left( {\gamma {\boldsymbol{{D}}^c}\boldsymbol{{p}}_{.i}^c + \sum\limits_{j = 1}^n {I_{ij}^c\left( {{\boldsymbol{{q}_{.j}}}\boldsymbol{{q}}_{.j}^{\rm{T}}\boldsymbol{{p}}_{, i}^c-r_{ij}^c{\boldsymbol{{q}}_{.j}}} \right)} } \right) $

(8)

其中:D^c是一个k×k的对角矩阵，第i个对角线元素为D_ii^c=1/‖p_i.^c‖₂²，其中p_i.^c为p^c的第i行。令$ \frac{{\partial L\left( {{\mathit{\boldsymbol{p}}^c}} \right)}}{{\partial \mathit{\boldsymbol{p}}_{.i}^c}} = 0$，可得：

$ \begin{array}{*{20}{l}} \boldsymbol{p} \end{array}_{.i}^c = {\left( {\frac{\lambda }{{{\beta _c}}}\boldsymbol{E} + \gamma {\boldsymbol{D}^c} + \sum\limits_{j = 1}^n {\boldsymbol{I}_{ij}^c\boldsymbol{{q}_{.j}}\boldsymbol{q}_{.i}^T} } \right)^ - }\left( {\sum\limits_{j = 1}^n {\boldsymbol{I}_{ij}^c\boldsymbol{r}_{ij}^c{\boldsymbol{q}_{.j}}} } \right) $

(9)

其中E是一个k×k的单位矩阵。

固定p求解q   类似地，L(q) 对q_.j求导，并令求导结果等于0，可得：

$ {\mathit{\boldsymbol{q}}_{.j}} = {(\lambda \mathit{\boldsymbol{E}} + \sum\limits_{c = 1}^C {{\beta _c}} \sum\limits_{i = 1}^{{m_c}} {{I_{ij}}} \mathit{\boldsymbol{p}}_{.i}^c{(\mathit{\boldsymbol{p}}_{.i}^c)^{\rm{T}}})^-}(\sum\limits_{c = 1}^C {{\beta _c}} \sum\limits_{i = 1}^{{m_c}} {{I_{ij}}} r_{ij}^c\mathit{\boldsymbol{p}}_{.i}^c) $

(10)

综上，本文将问题 (5) 的求解过程命名为基于评分相似性的群稀疏矩阵分解推荐算法 (SSMF-GS)，详细步骤如算法1所示。

算法1   评分相似性的群稀疏矩阵分解推荐算法。

Input：聚类后评分矩阵R^c(c=1, 2, …, C) 参数β_c，γ，λ

1)   initialize：p^c(c=1, 2, …, C)，q

2)   for k=1 to K

3)    for c=1 to C

4)    计算对角矩阵D^c，对角线元素D_ii^c=1/‖p_i.^c‖₂²；

5)    end for

6)    for c=1 to C

7)    通过式 (9) 更新p_.i^c；

8)    end for

9)   通过式 (10) 更新q_.j；

10)  end for

Output：p^c(c=1, 2, …, C)，q

3 实验验证 3.1 实验设置

本文实验数据采用Movielens-100k数据集 (http://grouplens.org/datasets/movielens/)，包含943个用户对1682部电影的评分，共100000条评分记录，评分区间为1~5分。为了全面地评价推荐模型，本文在3种训练集上 (80%、60%、40%) 做了相关实验来验证SSMF-GS算法在不同稀疏情形下的性能。比如，80%的训练集是从原始评分矩阵中随机选取80%的评分数据作为训练集，剩余的20%作为测试集。

3.2 度量标准

预测精度可以度量出真正评分和预测评分之间的接近程度，本文选择平均绝对方差 (Mean Absolute Error, MAE) 和均方根误差 (Root Mean Squared Error, RMSE) 作为预测精度的评价指标。

$ MAE = \sum\limits_{\left( {i, {\rm{ }}j} \right) \in T} {{{\left| {{r_{ij}}-{{\hat r}_{ij}}} \right|}}} /\left| T \right| $

(11)

$ RMSE = \sqrt {\sum\limits_{\left( {i, {\rm{ }}j} \right) \in T} {{{({r_{ij}}-{{\hat r}_{ij}})}^2}} /\left| T \right|} $

(12)

其中:|T|表示测试集的规模。MAE和RMSE越小表示预测精度越高，算法性能越好。

3.3 结果及分析

为了验证本文算法的预测性能，将其应用于电影评分预测，并与基于用户的K近邻 (User-based K-Nearest Neighbors, UserKNN)^[13]算法、矩阵填充 (Matrix Completion, MC)^[14]算法、概率矩阵分解 (Probabilistic Matrix Factorization, PMF)^[4]算法和正则化的矩阵分解 (Regularized Matrix Factorization, RMF)^[3]算法进行比较。

在UserKNN中，主要参数设置为目标用户的邻居数目e=10。在RMF模型中，主要参数设置为潜在特征维度k=5，正则化系数λ=0.01。MC算法的实现代码下载于http://perception.csl.illinois.edu/matrix-rank/Files/inexact_alm_mc.zip，其参数按照设计者的方法设置。PMF算法的实现代码下载于http://www.cs.toronto.edu/~rsalakhu/BPMF.html，主要参数设置为潜在特征维度k=5，正则化系数λ₁=λ₂=0.01。在SSMF-GS中，固定用户群数目为50，主要参数设置为潜在特征维度k=5，正则化系数λ=0.08，为简单起见β_c(c=1, 2, …, 50)=1，80%训练集中γ=120，60%训练集中γ=120，40%训练集中γ=150。文本利用Matlab (2014b) 进行相关实验，实现结果如表 3所示。

从表 3中可以看出，基于矩阵分解的两种算法PMF和RMF预测精度明显优于基于记忆算法的UserKNN，这与上述对它们的分析是吻合的，在数据非常稀疏的情况下，基于记忆的算法无法找到足量的相似用户，导致预测精度较差。随着训练数据集稀疏度的增加，几种算法的预测性能也在下降，在40%的训练集中PMF和RMF预测精度优势并不是十分明显，这表明基于矩阵分解的算法也受到了数据稀疏性的制约。本文算法融入了评分数据中相似用户群的评分信息，相对于其他几种算法，SSMF-GS算法在预测精度上得到了显著提升。

本文随机抽取2个用户群的潜在特征向量进行分析。由于每个用户群的用户数量不等，本文选取用户群的前5个用户，潜在用户特征数向量中值为0的用叉号表示，值不为0的用圆圈表示。从图 2可以看出，用户群1偏好潜在特征为{1, 2, 3, 4}，用户群2偏好的潜在特征为{1, 2, 3}。其中{1, 2, 3}为共有潜在特征，{4}为用户群1的私有潜在特征。这表明在真实数据中，本文算法能够为不同的用户群筛选出共有和私有潜在特征，这也和上述图 2分析一致。

3.4 参数γ的影响

参数γ为群稀疏正则化系数，在SSMF-GS算法中扮演了重要的角色。如果γ取值过小，则无法区分不同用户群的潜在项目特征；如果γ取值过大，潜在项目特征矩阵则会产生过多的0行，导致极少的潜在项目特征被筛选出来。参数γ对MAE和RMSE的影响见图 3和图 4。

从图 4和图 5可以看出，80%及40%训练集中γ为120，20%训练集中γ为150时，RMSE及MAE最低，算法预测精度最优。

4 结语

矩阵分解推荐算法能有效地改善评分数据稀疏性问题，而群稀疏表示能够挖掘评分数据呈现出的特殊群结构。结合两者的优点，提出一种基于评分相似性的群稀疏矩阵分解推荐算法，该算法群稀疏表示潜在用户特征矩阵，为用户群筛选出共有和私有潜在项目特征，通过潜在用户特征向量和潜在项目特征向量的内积来预测用户群中用户对项目的评分形成推荐结果。与其他几种推荐算法相比，本文算法获得了更好的预测精度。