李瑞 冯锋

摘要：传统的协同过滤算法存在着冷启动、数据稀疏性和可扩展性等关键问题，这都使得用户的历史播放列表数据信息难以获得，从而导致推荐电影时精度较低。文章将聚类算法与SVD++模型相结合，通过K-means聚类算法将相似用户根据评分聚类的同时，并利用SVD++模型对聚类后的每个集群中的评分矩阵进行分解，从而解决相似用户查找效率低和评分矩阵数据稀疏性的问题，使得电影推荐系统具有较高的精度。

关键词：推荐系统;协同过滤;聚类;SVD++：数据稀疏性

中图分类号：TP391.3

文献标识码：A

文章编号：1006-8228（2020）09-88-04

Research ori movie recommendation system using clustering and SVD++

Li Rui， Feng Feng

（School of Information Engineering， Ningxia University， Yinchuan， Ningxia 750021， China）

Abstract： There are key problems existed in traditional collaborative filtering algorithms， such as cold start. data sparsity andscalability， which make the user's historical data information difficulty to obtain， thereby resulting in lower accuracy of movierecommendation. In order to solve this problem， this paper combines the clustering algorithm with the SVD++ model. By using theK-means clustering algorithm to cluster similar users according to ratings， and using the SVD++ model to decompose the scorematrix in each cluster after clustering. the problems of low search efficiency of similar users and sparse score matrix data will besolved， so that the movie recommendation system can obtain higher accuracy.

Key words： recommendation system; collaborative filtering; clustering; SVD ++; data sparsitv

0引言

如今，推荐系统已经成为互联网相关服务行业和在线产品销售公司最有前途的技术之一，YouTube、谷歌、Facebook、淘宝和今日头条等系统中都有推荐系统的身影。这些推荐系统根据用户的行为数据来预测用户的偏好，有助于提高用户对推广项目的满意度，可以看出，推荐系统在一些商业模式中扮演着非常重要的角色。推荐系统常采用协同过滤算法，其具有简单、易于实现的优点，被广泛用于各类推荐系统的开发中。协同过滤算法可以分为两类：基于内存的协同过滤算法和基于模型的协同过滤算法。前者根据用户或项目之间的相似性进行预测，而后者通过定义一个参数模型来描述用户与物品，用户与用户（或者物品与物品）之间的关系，然后通过优化过程得到模型参数进行预测。尽管协同过滤算法非常经典，但由于其存在冷啟动，数据稀疏和可伸缩性等缺点，使得推荐时难以实现较高的精度。

本文通过用融合聚类算法和降维的协同过滤进行电影推荐，主要采用k-means算法和SVD++模型。其中k-means算法将是一种迭代求解的聚类分析算法，而SVD++是一种降维技术，它可以提高推荐系统的可扩展性[1]。通过k-means算法和SVD++模型分别对偏好相似的用户进行聚类，对评分矩阵降维，从而提高电影推荐系统的性能，并且克服推荐系统的数据稀疏性和可扩展性问题。

为了结合k-means算法与SVD++模型，我们对电影推荐系统架构进行了设计，系统由三个模块组成：用户行为记录模块、模型分析模块和推荐算法模块。用户行为记录模块主要是保存不同类型的用户行为数据如浏览、收藏等;模型分析模块主要是根据用户的行为数据分析用户潜在的兴趣及其程度;推荐算法模块通过计算将用户最有可能感兴趣的电影推荐给用户。电影推荐整体架构如图1所示。

1相关工作

1.1相关研究

在过 去的十几年里，许多研究人员对推荐算法进行了广泛的研究来解决推荐系统的数据稀疏性问题。如基于项目递归的有争议相似性概念，并将其与协同过滤算法结合，以解决协同过滤算法的数据稀疏性问题[2];从用户角度出发，结合用户属性相似度、用户兴趣相似度和传统用户评价相似度进行推荐来缓解这个问题[3];Yang等人[4]提出了在用户相似度计算过程中，将离散内容与适当的兴趣度相结合，以提高推荐的质量，并且在极端数据稀疏的情况下可以较好地保持良好的性能;Zarzour等人[5]采用改进的k-means聚类算法，并结合主成分分析来提高大数据的推荐精度。Huang等人[6]利用线性回归模型在用户一物品评价矩阵中填充未评价数据，缓解了数据稀疏性，找到更可靠的用户邻域，从而提高评级预测的准确性。

1.2 SVD++模型背景介绍

传统的SVD通过矩阵分解的方式将数据最终转化为特征向量，通过提取数据集合特征值，减少数据运算量，以提高算法准确度。但是，由于在计算过程中存在所占內存空间大、计算时间长的问题，使得其发展过程中出现瓶颈。直到2006年Netflix prize后，Simon Funk在博客上公开发布了一种改进的方法Funk-SVD，该方法后来被称为潜在因子模型（LFM）。LFM与传统SVD的最大区别在于传统的SVD将矩阵分解为三个子矩阵（U∑VT），而LFM模型将复杂的评分矩阵分解为两个低维矩上考虑了用户偏见和项目偏置的这些与物品和用户无关的系统阵P和Q相乘的形式（pTQ），以预测用户对产品的评估。将LFM模型添加到SVD算法可以提高预测精度并减少所需的存储空间，并在离线进行训练过程中提供在线推荐计算所需的数据，可以一定程度上提高推荐效率。后续提出的BiasSVD，又在LSM模型的基础上考虑了用户偏见和项目偏置这些与物品和用户无关的系统因素。而SVD++模型则基于BiasSVD，并考虑到用户对项目的显式历史评分能表现出用户喜爱程度外的隐藏信息，如浏览记录或者收藏列表，这些隐藏信息等在一定程度上同样可以从侧面反应用户的偏好，所以，使用SVD++做评分预测更加精确。

2算法研究

我们将聚类算法与SVD++模型相结合，首先采用k-means算法将相似用户根据评分进行聚类，并对聚类后每一个集群中的评分矩阵根据SVD++模型进行矩阵分解，从而解决矩阵稀疏性问题。在进行矩阵分解后，对每一个集群中再次根据评分聚类，反复迭代直到收敛。最后，根据改进的余弦相似度度量方法，依据评分计算两个用户间的相似度，进而形成推荐列表。

2.1相似用户聚类

k-means算法是一种无监督的聚类算法，通过迭代求解聚类问题。首先随机选择k个对象作为初始聚类中心，计算每个对象与每个子聚类中心之间的距离，然后把每个对象分配给最靠近它的聚类中心。用它聚类后，类内的相似度较高，类外的相似度较低。我们使用k-means算法来随机创建k个集群，每个集群包含的用户在评级方面有相似的偏好。因此，考虑集群与包含所有用户的人群相比包含更少的用户，用户集群过程有助于提高推荐性能。

为了适应传统的k-means方法作为推荐系统的相似用户聚类技术，需对其部分步骤改进。①随机选取k个用户作为k个集群的初始中心。②根据用户与每个集群中心之间的距离，将其余用户分配到最近的集群。使用相似度度量来计算距离值。③计算用户集群的新平均值，为每个集群定义新中心。④对每个用户，重新计算距离，以便定义应该将用户添加到哪个集群。⑤根据用户的距离重新分配用户，直到满足终止条件。用户聚类的具体步骤如下。

步骤1：输入用户一条目评价矩阵，以及k个聚类，随机选取k个用户初始聚类中心;

步骤2：计算聚类中心和用户之间的距离，将用户分配到离它最近的集群;

步骤3：对于每个相似用户的集群，进行新的分区中心的平均值计算，使用新的分区中心将用户重新分配到新的集群中;

步骤4：重复步骤3，直到算法收敛到一个稳定的分区;

步骤5：输出k个集群，表示为一个中心项评价矩阵。

如何从初始用户一项目评分矩阵中获得新的聚类中心一项目评价矩阵，首先我们可以统计用户对项目的评价，得到如表1所示用户一项目评价表。其中，列表示项目，行表示用户，rij表示用户i对项目j的评分。

经过用户聚类算法，可以得到如表2所示的聚类中心一项目评级表。其中，列表示项目，行表示用户的集群中心，pij表示用户集群i对项目j的平均评级。

2.2利用SVD++补全矩阵

将用户通过聚类分成不同的集群后，我们将每个集群里的用户评分矩阵通过SVD++模型进行降维，对未评价项目进行评分预测来填补矩阵。

在根据评分做推荐的研究中，人们发现一个评分矩阵的固有属性等和用户无关。就电影评分矩阵来说，有的人习惯给好评，有的人就比较苛刻评分总是很低。对于电影本身来说，有的电影十分经典，很受欢迎，评分很高，而有的电影小众不被人们喜欢。koren等人[7]为了让自己的模型可以体现这个现象，引入基准预测的概念。对于一个未知的评分rui其基准预测具体被定义为如下公式：

bui=μ+bu+bi

（l）其中，μ为所有已知评分的平均值，bu和bi分别代表用户u和项目i的评分偏置。例如，假设我们需要对用户Tom观看电影《蜘蛛侠》的评级进行基准预测，现在整个网站的电影评分μ为3.9星，《蜘蛛侠》比一般的电影要好，所以它的评级往往比一般电影高0.5星，而Tom是一个很挑剔的用户，他每次给出评分倾向于比平均水平低0.2星。因此，通过计算3.9-0.2+0.5，Tom对《蜘蛛侠》的评级的基线估计将是4.2颗星。

我们采用SVD++模型，通过降维的思想将稀疏的评分矩阵分解为用户因子矩阵P∈Rf*m和项目因子矩阵Q∈Rfxn相乘形式，其中f<

（2）其中Nu为用户u所产生隐式反馈行为的项目集合，yj为用户隐式评价了电影j反映出的个人喜好偏置，Nu|-1/2是一个经验公式。模型参数bu，bi，qi，pu，yj，通过梯度下降法优化公式（3）获得：

（3）

最后，通过聚类算法和SVD++模型运算反复迭代趋于稳定后，我们使用改进余弦相似度进行相似用户的计算，生成推荐列表。改进的余弦相似度计算公式为：

（4）其中，sim（i，j）表示用户i与用户j的相似度，Iij是用户i和用户j对同一项目都评过分的项目集合。Ii，Ij分别是用户i和用户j对项目评过分的集合，Ri，r，Rj，r分别是用户i，用户j对项目r的评分，Ri，Rj分别表示用户i和用户j的对所有评分项目的平均值。

3结束语

本文通过将k-means算法与SVD++模型相结合。首先，通过将用户聚类再进行相似用户查找，比一般直接在所有用户中查找减少了计算时间，提高了查找效率。其次，利用SVD++模型对聚类后每个集群中的用户电影评分矩阵进行分解，并在评分预测时考虑了显示反馈和隐式反馈，缓解数据稀疏性问题，提高了推荐系统的预测精度。此外，我们还通过降维降低了计算复杂性。但由于本系统根据用户的评分进行聚类，而用户首次进入系统时所有的电影评分为0，此时不能为用户准确地推荐适合的电影。因此，在后续的工作中，我们将通过为用户推荐本系统中较为热门的电影或结合其他推荐算法解决这个问题。另外，本文目前仅是提出了这样的想法，下一步我们将会在豆瓣上爬取的数据集和MovieLens等数据集上验证算法的实际效果，并将算法应用到电影推荐系统中。

参考文献（References）：

[1] Koren Y， Bell R， Volinsky C. Matrix factorizationtechniques for recommender systems[J]. Computer，2009.42（8）：30-37

[2]张学胜.面向数据稀疏的协同过滤推荐算法研究[D]，中国科学技术大学硕士学位论文，2011.

[3]高倩，何聚厚.改进的面向数据稀疏的协同过滤推荐算法[J].计算机技术与发展，2016.26（3）：63-66

[4] Weiyangj， Shuqin L I， Xinyu L I， et al. CollaborativeFiltering Recommendation Algorithm Based onDiscrete Quantity and User Interests Approach Degree[J]. computer engineering，2018.

[5]Zarzour H， Maazouzi F， Soltani M. et al. An improvedcollaborative filtering recommendation algorithm for bigdata[C]//IFIP International Conference on Computa-tional Intelligence and Its Applications. Springer， Cham，2018：660-668

[6] Huang M， Wang Y， Zhou L. Collaborative FilteringAlgorithm based on Linear Regression Filling[C]//2019 IEEE 3rd Information Technology， Networking，Electronic and Automation Control

Conference（ITNEC）.IEEE，2019：1831-1834

收稿日期：2020-05-21

基金項目：宁夏重点研发计划重点项目（2018BFG02003）

作者简介：李瑞（1995-），女，宁夏银川人，硕士研究生，主要研究方向为信息系统工程。

通讯作者：冯锋（1971-），男，宁夏银川人，博士，教授，硕士生导师，主要研究方向：信息系统工程、物联网技术及应用。