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

盛 伟，王保云，何 苗，余 英

(云南师范大学 信息学院，昆明 650500)

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

盛 伟，王保云*，何 苗，余 英

(云南师范大学 信息学院，昆明 650500)

(*通信作者电子邮箱wspbmly@163.com)

如何提高系统的推荐精度，是当前推荐系统面临的重要问题。对矩阵分解模型进行了研究，针对评分数据的群结构性问题，提出了一种基于评分相似性的群稀疏矩阵分解模型(SSMF-GS)。首先，根据用户的评分行为对评分数据矩阵进行分群，获得相似用户群评分矩阵；然后，通过SSMF-GS算法对相似用户群评分矩阵进行群稀疏矩阵分解；最后,采用交替优化算法对模型进行求解。所提模型可以筛选出不同用户群的偏好潜在项目特征，提升了潜在特征的可解释性。在GroupLens网站上提供的MovieLens数据集上进行仿真实验，实验结果表明，所提算法可以显著提高预测精度，平均绝对误差(MAE)及均方根误差(RMSE)指标均表现出良好的性能。

群稀疏；矩阵分解；L2,1范数正则化；潜在特征

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类观影群体：年轻观众u1，女性观众u2，男性观众u3，每部电影用4个潜在特征来表示：恐怖、喜剧、动作和爱情。从表1中可以看出，u1选择潜在特征{1}和{2}；u2偏好潜在特征{2}和{4}；u3喜好潜在特征{1}和{3}。本文的目的是根据评分相似性从评分矩阵中找出这3类群体，并筛选出它们喜好的潜在特征，而传统的矩阵分解模型忽略了这些信息，这在一定程度上降低了推荐信息的利用率。

表1 用户群与潜在电影特征的关系Tab. 1 Relationship between user groups and latent movie features

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

1 相关工作

1.1 矩阵分解推荐算法

设用户全集为U={u1,u2,…,um}，项目全集为V={v1,v2,…,vm}，m表示用户数量，n表示项目数量。记U中用户ui对项目vj的评分为rij，rij=0表示用户ui对项目vj没有评分，完整的用户-项目评分矩阵如表2所示。

表2 用户-项目评分矩阵Tab. 2 User-Item rating matrix

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

(1)

(2)

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

1.2 群稀疏表示

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

(3)

2 群稀疏矩阵分解推荐算法

2.1 评分预测问题建模

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

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

(4)

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

图1 基于评分相似性的群稀疏矩阵分解Fig. 1 Score similarity based matrix factorization with group sparsity

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

(5)

2.2 模型求解

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

(6)

(7)

(8)

(9)

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

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

(10)

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

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

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

1)

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

2)

fork=1 toK

3)

forc=1 toC

4)

5)

end for

6)

forc=1 toC

7)

8)

end for

9)

通过式(10)更新q.j；

10)

end for Output：pc(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)作为预测精度的评价指标。

(11)

(12)

3.3 结果及分析

为了验证本文算法的预测性能，将其应用于电影评分预测，并与基于用户的K近邻(User-basedK-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，正则化系数λ1=λ2=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 不同稀疏度情形下预测精度比较Tab. 3 Comparison of prediction accuracy under different sparsity

从表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分析一致。

图2 用户群的潜在特征向量Fig. 2 Latent feature vector of user group

3.4 参数γ的影响

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

图3 参数γ对RMSE的影响Fig. 3 Impact of parameter γ on RMSE

图4 参数γ对MAE的影响Fig. 4 Impact of parameter γ on MAE

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

4 结语

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

References)

[1] 冷亚军, 陆青, 梁昌勇. 协同过滤推荐技术综述[J].模式识别与人工智能, 2014, 27(8): 720-734.(LENG Y J, LU Q, LIANG C Y. Survey of recommendation based on collaborative filtering[J]. Pattern Recognition and Artificial Intelligence, 2014, 27(8): 720-734.)

[2] PAGARE R, PATIL S A. Study of collaborative filtering recommendation algorithm-scalability issue[J]. International Journal of Computer Applications, 2013, 67(25):10-15.

[3] KOREN Y, BELL R, VOLINSKY C. Matrix factorization tech-niques for recommender systems[J]. Computer, 2009, 42(8): 30-37.

[4] SALAKHUTDINOV B R, MNIH A. Probabilistic matrix factorization[C]// Proceedings of the 21st Annual Conference on Neural Information Processing Systems. New York: Curran Associate Inc,2008:1257-1264.

[5] ZHANG Y, KOREN J. Efficient Bayesian hierarchical user modeling for recommendation system[C]// Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2007: 47-54.

[6] PHAM T A N, LI X, CONG G, et al. A general graph-based model for recommendation in event-based social networks[C]// Proceedings of the 2015 IEEE 31st International Conference on Data Engineering. Piscataway, NJ: IEEE, 2015: 567-578.

[7] BOKDE D, GIRASE S, MUKHOPADHYAY D. Matrix factorization model in collaborative filtering algorithms: a survey [J]. Procedia Computer Science, 2015, 49(1):136-146.

[8] YUAN T, CHENG J, ZHANG X, et al. Recommendation by mining multiple user behaviors with group sparsity[EB/OL]. [2016-10-11]. http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/download/8267/8424.

[9] HUANG J, ZHANG T. The benefit of group sparsity[J]. The Annals of Statistics, 2010, 38(4): 1978-2004.

[10] 郑秋中, 徐军. 一种基于群稀疏特征选择的图像检索方法[J]. 计算机应用研究, 2014, 31(9):2867-2872.(ZHENG Q Z, XU J. Group sparse based feature selection for image retrieval [J]. Application Research of Computers, 2014, 31(9):2867-2872.)

[11] 陈蕾, 杨庚, 陈正宇,等. 基于结构化噪声矩阵补全的Web服务QoS预测[J]. 通信学报, 2015, 36(6):49-59. (CHEN L, YANG G, CHEN Z Y, et al. Web services QoS prediction via matrix completion with structural noise [J]. Journal on Communications, 2015, 36(6):49-59.)

[12] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.

[13] BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]// Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. San Francisco, CA: Morgan Kaufmann Publishers, 1998: 43-52.

[14] LIN Z, CHEN M, MA Y. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[EB/OL]. [2016-10-11].https://arxiv.org/pdf/1009.5055v3.pdf.

This work is partially supported by the Scientific Research Foundation of Education Department of Yunnan Province (2014Y145), the Philosophical and Social Science Program of Yunnan Province (QN2015067), the Doctoral Research Starting Foundation of Yunnan Normal University (01000205020503064).

SHENG Wei, born in 1988, M. S. candidate. His research interests include recommender system.

WANG Baoyun, born in 1977, Ph. D., lecturer. His research interests include machine learning.

HE Miao, born in 1990, M. S. candidate. Her research interests include machine learning.

YU Ying, born in 1965, M. S., associate professor. Her research interests include network communication.

Score similarity based matrix factorization recommendation algorithm with group sparsity

SHENG Wei, WANG Baoyun*, HE Miao,YU Ying

(SchoolofInformationScienceandTechnology,YunnanNormalUniversity,KunmingYunnan650500,China)

How to improve the accuracy of recommendation is an important issue for the current recommendation system. The matrix decomposition model was studied, and in order to exploit the group structure of the rating data, a Score Similarity based Matrix Factorization recommendation algorithm with Group Sparsity (SSMF-GS) was proposed. Firstly, the scoring matrix was divided into groups according to the users’ rating behavior, and the similar user group scoring matrix was obtained. Then, similar users’ rating matrix was decomposed in group sparsity by SSMF-GS algorithm. Finally, the alternating optimization algorithm was applied to optimize the proposed model. The latent item features of different user groups could be filtered out and the explanability of latent features was enhanced by the proposed model. Simulation experiments were tested on MovieLens datasets provided by GroupLens website. The experimental results show that the proposed algorithm can improve recommendation accuracy significantly, and the Mean Absolute Error (MAE) and Root Mean Squared Error (RMSE) both have good performance.

group sparsity; matrix factorization;L2,1-norm regularization; latent feature

2016-10-13;

2016-12-21。 基金项目:云南省教育厅科学研究基金资助项目(2014Y145);云南省哲学社会科学规划项目(QN2015067);云南师范大学博士启动基金资助项目(01000205020503064)。

盛伟(1988—)，男，江苏丰县人，硕士研究生，主要研究方向：推荐系统； 王保云(1977—)，男，云南玉溪人，讲师，博士，主要研究方向:机器学习； 何苗(1990—)，女，云南曲靖人，硕士研究生，主要研究方向：机器学习； 余英(1965—)，女，云南昆明人，副教授，硕士，主要研究方向：网络通信。

1001-9081(2017)05-1397-05

10.11772/j.issn.1001-9081.2017.05.1397

TP181

A