改进学习率的一种高效SVD++算法

王燕+李凤莲+张雪英+田玉楚

摘 要： 推荐系统的核心包括推荐算法及其所依赖的大数据。推荐算法的高效计算，是实现实时人机交互的基本要求。在各种推荐算法中，SVD++算法因其特殊优点而得到广泛应用。但是，大数据背景下SVD++推荐算法的突出问题是计算效率低，难以满足实时人机交互要求。为解决这一问题，提出一种新的方法来提高SVD++推荐算法的计算效率，其核心是采用新的学习率函数对目标函数的指标进行优化。该学习率函数结合指数函数和一次函数的升降速率特点，具有初期值大、中期下降迅速以及后期值小且变化缓慢的特点。仿真实验证明了该方法的有效性。

关键词： 推荐系统； 推荐算法； 大数据； SVD++； 计算效率； 学习率

中图分类号： TN911.1?34 文献标识码： A 文章编号： 1004?373X（2018）03?0146?05

Abstract： The core of the recommendation system includes the recommendation algorithm and big data. The efficient computation of the recommendation algorithm is the essential requirement to realize the real?time human?machine interaction. Among various recommendation algorithms， the SVD++ algorithm is widely used because its special advantages. However， in the environment of big data， the SVD++ recommendation algorithm has the prominent problem of low computing efficiency， and is difficult to satisfy the requirement of real?time human?machine interaction. In order to solve this problem， a new method to improve the computation efficiency of the SVD++ recommendation algorithm is proposed， whose kernel is to optimize the indicator of the target function with new learning rate function. In combination with the changing rate characteristics of the exponential function and linear function， the learning rate function has the characteristics of high initial value， low medium?term descend speed and later value， and slow change toward. The effectiveness of the method was verified with simulation experiment.

Keywords： recommendation system； recommendation algorithm； big data； SVD++； computation efficiency； learning rate

0 引 言

推荐系统是解决当前互联网“信息过载”的一项关键技术[1]，其通过收集和分析用户的各种信息来学习用户特征，并根据分析得到的用户兴趣和行为模式来为用户推荐所需要的服务。目前，推荐系统在很多领域获得了广泛应用，例如电子商务、电影、音乐、移动应用等。

推荐算法及其依赖的原始大数据是推荐系统的核心[2]。互联网上每天产生TB及PB级的数据，数据复杂、维度高。在此背景下，有效提高推荐算法的计算效率成为实际应用中实现实时人机交互的关键。在常用的推荐算法中，基于奇异值分解算法（Singular Value Decomposition，SVD）改进的SVD++推荐算法[3]因具有很多优点而被应用于推荐系统，主要优点包括降低数据维度、考虑含蓄隐式行为信息以及预测准确性高等，是推荐算法中一种重要的用于实现目标用户对目标项目进行评分预测的算法。

虽然SVD++推荐算法具有很多优点，但在实际应用中，需要处理的数据量往往属于海量级。对于海量数据，SVD++算法计算效率低的问题格外突出，因而不能满足实时人机交互的基本要求。

本文提出一种新的方法来提高SVD++推荐算法的计算效率，其核心是采用一种新的学习率函数对SVD++推荐算法中的各项指标进行优化学习。该新学习率函数采用指数函数和一次函数的综合函数作为优化函数，从而具有自适应学习的能力，具体表现为初始学习率大、中期下降迅速以及后期学习率小且变化缓慢。

1 推荐算法

目前，主流的推荐算法包括四类：基于内容、协同过滤、基于图结构以及混合的算法。其中，协同过滤算法是当前推荐系统中最广泛应用的推荐算法[2]，其核心思想是寻找目标用户的相似用户群，然后根据相似用户群对目标项目的评分情况预测目标用户对该项目的喜好。协同过滤算法又包括基于项目、基于用户和基于模型三类[2]。基于项目和基于用户的算法原理简单，但效率低。而基于模型的算法原理复杂，但预测准确性高，能够很好地解决数据稀疏性的问题。本文针对基于模型的协同过滤推荐算法进行研究。endprint

基于模型的协同过滤推荐算法中的一种典型算法为SVD推荐算法，该算法的研究方向包括预测准确性和计算效率。针对准确性进行研究的方法主要包括：

1） 在原有SVD算法的基础上加入其他信息，如置信度参数[4]、隐式信息及时间信息，综合提高推荐模型的性能。

2） 在已改进算法的基础上加入其他信息，如用户和项目的偏置信息[5]。

3） 利用其他类型矩阵的特征来完成对评分的预测[6]。

这些方法较经典SVD算法的准确性都有所提高，但效率均低于SVD++推荐算法。

对于计算效率的研究，主要包括两类：

1） 利用矩阵的特性提取出一个新的矩阵作为目标函数对SVD推荐算法进行优化[7]，此方法虽然有效提高了算法推荐效率，但准确性却低于SVD++推荐算法。

2） 针对算法适应性进行研究，如基于SVD增量算法的模型不会随着数据的变化而产生大的变化，该方法虽然能够有效地提高算法计算效率[8]，但缺点是没有考虑含蓄隐式信息。

针对以上方法的准确性低以及没有考虑含蓄隐式信息的缺点，本文在SVD++推荐算法的基础上，提出一种新的学习率函数对算法的模型进行训练，该学习率函数具有自适应的特点，以此来解决大数据背景下推荐算法计算效率低的问题。

2 新的SVD++推荐算法

2.1 基本SVD++推荐算法预测公式

假设给定个用户，个项目以及用户对项目的评分矩阵是稀疏矩阵，表示用户对项目的评分，推荐算法最终目标是对的项目进行预测。

最初该算法把高维的用户?项目?评分矩阵分解为两个降维矩阵乘积的形式其中表示的近似矩阵，和分别是降维后的用户特征向量矩阵和项目特征向量矩阵，是降维后向量的维数，用户对项目的预测评分公式为：

后来研究人员把用户和项目自身的差异性，以及用户的历史浏览记录和观看记录等含蓄隐式信息加入到推荐模型，得到SVD++推荐算法的预测评分公式如下：

式中：用户的特征向量被模型化为为用户的显式评分信息的特征向量，为用户的隐式反馈信息的特征向量， 表示用户有过行为的项目数量，该行为包括用户对项目的浏览、观看以及评分等；表示对项目有过行为的用户特征向量；表示项目的特征向量；是全局的平均数；是用户的偏置向量；是项目的偏置向量。

2.2 梯度下降法

对SVD++算法的预测评分函数的各个参数进行优化求解的方法有两种：一种是梯度下降法；另一种是最小二乘法。因后者的原理相对复杂，研究时一般采用前者[8]。

梯度下降法是一种最常用的优化算法。假设要求一个目标函数的极小值，首先要对待优化的指标进行求导，确定每次迭代的搜索方向，然后需要确定一个学习率作为每次搜索寻优的步长，最终使得待优化的指标迭代至目标值附近。

梯度下降法的一种简单形式是：其中为学习速率，可以是较小的常数，也可以是一个函数表达式；是的梯度；为迭代次数。

2.3 基于新学习率的SVD++推荐模型

在SVD++推荐模型的训练阶段，对目标函数进行优化，学习率的选择极其重要。若取值较大，即梯度下降迭代的步长较大，可以快速迭代至最优解附近，但是可能一直在最优解附近徘徊，无法计算出最优解，对于特殊的函数也可能会导致不收敛，始终发散求不出解；若取值较小，即梯度下降迭代的步长较小，下降速度较慢，其迭代出的解精度较高，但会耗费很长时间，这将不利于实际应用。

分析该模型训练过程可知，梯度下降法中所用的学习率是一个自适应减函数，即学习初期时，采用较大的学习率，此时梯度下降的步长较大；中期时，迅速下降迭代至最优解附近；末期时，学习率很小并且变化缓慢，以一个很小的值来寻找最优解。若采用一个恒定不变的经验值或是按经验先取较大值后取较小值，则需要进行多次实验才能找到合适的值，并且模型的训练过程较长，精确度也不高。目前应用最多的学习率方法是采用指数函数调整大小，其公式为：

式中：为迭代次数；分别为该指数学习率函数的参数。大多数研究都采用该函数，该函数虽然可以通过调节参数满足学习率先大后小的条件，但因为可控参数少，不够灵活，在SVD++模型中应用时效率仍然很低。

综合考虑以上情况，本文提出一种新的可用于SVD++算法的新学习率函数，该学习率函数表达式为：

式中：为迭代次数；和为学习率函数的三个参数。

基于新学习率函数的SVD++推荐算法包括模型训练及性能测试两部分。具体步骤如下：

输入：训练数据文件u?train，历史数据文件u?his，学习率初值，迭代最大次数维度

输出：迭代停止次数训练时间和均方根误差RMSE。

1） 初始化特征矩阵和使向量中的值为0～0.1的任意数，并把偏置项和向量中的值初始化为0。

2） 根据SVD++推荐算法的预测评分式（2）求解训练数据中用户对项目的预测评分再根据求得预测评分与实际评分的误差值。

3） 学习模型中用户和项目的特征变量和方法是使用梯度下降法最小化损失函数，损失函数如下所示：

损失函数包括误差部分和正则化部分，误差部分是式（5）中的第一部分，正则化部分为第二部分，该部分的作用是防止训练过程中出现过拟合现象。

最小化损失函数的方法是对每个特征变量求偏导，得到相应特征的梯度向量，特征变量将沿着梯度方向进行更新，直到梯度向量接近零时特征更新结束。式（5）为特征和的学习更新公式，每个特征学习采用的学习率均同式（4）。

4） 根據更新得到以上特征参数，执行步骤2），判断得到的误差是否小于阈值若小于则停止训练，否则继续步骤2）。

5） 根据最终训练出来的用户和项目的特征参数，对测试数据里的用户项目进行预测评分，并得到迭代次数训练时间和预测准确性指标RMSE。其中RMSE的求解见4.1评价指标部分。endprint

上述步骤中，从步骤1）～步骤4）为采用训练数据对特征和的值进行训练的过程；步骤5）为对测试数据进行预测评分的过程，根据训练出来的特征和的值对测试数据进行预测。

与现在常用的学习率函数相比，新学习率函数的主要优点是通过三个参数灵活有效地控制学习率的变化，具有自适应的特点。根据本实验及数学理论分析可知，新旧学习率函数均为减函数，式（3）利用指数函数下降的特性，需要满足条件。式（4）在指数函数的基础上加入一次函数，增大了学习率的变化速率，并在此基础上取倒数，最终也得到了一个减函数，式（4）需满足条件和。与式（3）相比，首先，式（4）在两个参数的基础上又增加了一个参数，通过控制能更灵活地控制初值的大小，具有较大的初值；其次，式（4）的下降速率在指数函数基础上加入了一次函数，下降速度较单纯的指数函数更快；最后，随着逐渐增大，会越来越小，相同的值条件下，比小很多，可以以一个更小的步长寻找到更精确的最优解。

3 实验设计

3.1 数据集

本文采用MovieLens网站上的10万、100万和1 000万条评分信息的数据集进行相应的实验[9]，分别代表三类不同规模的推荐数据集，其数据量分别相差约一个数量级，如表1所示。这些数据集是对推荐算法性能进行测试的最常用的数据集合[8]，包含用户对电影的评分和电影属性等内容。数据集中每个用户至少对20部电影进行过评分，评分值均为1～5的整数值，评分越高代表用户对相应电影的评价越高，即越喜欢。该数据集能满足本文实验的要求。实验时，对每个数据集按82的比例随机分割为训练集和测试集。

3.2 实验平台

本实验的实验平台采用Windows 7操作系统，Intel CoreTM i5?2410M的CPU，6 GB的RAM以及eclipse环境。

3.3 推荐算法参数设定

实验分别采用本文提出的新学习率和已有的旧学习率对算法进行调试，最终得到两个学习率函数的合理参数。其中两种方法的正则化参数和维度相同，分别为0.007和30。采用本文提出的新学习率对SVD++推荐模型进行训练时，参数分别取为采用旧学习率函数对模型训练时的参数取为0.007，0.9。两种学习率随迭代次数变化曲线的对比情况如图1所示。

迭代次数（m≥4）变化对比

因迭代次数小于4时，新学习率的初值比旧学习率大1个数量级（新为0.047，旧为0.007），不能直观比较差别，图中不作显示。

当迭代次数大于等于4时，由图1可以看出，新学习率函数从0.005开始下降，迭代至20次时，学习率基本趋于零；而旧学习率函数从0.004 4开始下降，迭代至60次时，学习率才基本趋于零。在相同的迭代次数下，新学习率值小于旧学习率。该结果表明，与旧学习率函数相比，本文提出的新学习率函数，在学习初期以较大的学习率开始学习，然后以相对较快的速度下降，在后期以很小的学习率以及很少的迭代次数寻找到最优解。

4 评价指标及结果分析

4.1 评价指标

本实验从三个方面来确定评价指标[10]：第一，为了提高推荐算法的效率，采用推荐模型训练所用迭代次数作为评价指标之一，越小，则表示推荐性能越好；第二，随着数据集的增大，为了使算法适应数据集的可扩展性，采用训练时间作为第二个评价指标；第三，在提高效率的同时，需要保证算法的预测准确性，采用均方根误差RMSE作为第三个指标，RMSE越小则准确性越高，其表达式如下所示：

式中：表示推荐算法预测的用户对项目的评分；表示用户对项目的实际评分；表示测试的样本集；表示中测试样本的个数。

4.2 结果分析

实验分别采用基于新学习率和传统旧学习率的SVD++推荐算法对各实验数据集进行测试，得到的训练迭代次数训练时间RMSE的结果对比如图2～图4所示。实验结果是相同实验环境下重复执行20次，对实验结果取均值所得。

从图2可以看出，在三个不同规模的数据集和上进行实验时，采用新学习率对模型进行训练迭代的次数大约为30次，相比旧学习率大约减少120次。该结果表明，采用本文提出的学习率函数可以明显地降低对SVD++推荐算法训练所用的迭代次数。

从图3可以看出，在数据量依次增大且分别相差一个量级的三个数据集和上进行实验时，采用新学习率对算法进行训练时所用训练时间增长速度非常小，而采用旧学习率的时间增长速度较大。该结果表明，随着数据集的增大，与旧学习率相比，采用新学习率对模型进行训练可以明显地缩短训练所用的时间，同时也说明本文提出的新学习率函数可以明显地改善SVD++算法在针对大数据集时计算效率低的缺點。

从图4可以看出：在和数据集上进行实验时，与旧学习率相比，采用新学习率对模型训练后所得的RMSE略微减小；无论采用新或旧学习率，随着数据集的增大，RMSE均逐渐减小。以上两点可以说明，采用新学习率对模型进行训练后可以略微增大算法的准确性。同时，随着用户和电影数量的增多，采用新旧学习率实验后的准确性均逐步提高。

综上可知，与旧学习率方法相比，采用本文方法对SVD++模型进行训练后，迭代次数和训练时间大幅减少，而且所得结果的准确度也有所提高。该结果说明本文方法在保证推荐模型预测准确性的前提下，可有效地提高SVD++推荐算法的计算效率。

另外，采用该方法在SVD系列其他推荐算法上也进行了测试，结果表明，本文提出的学习率函数既能明显提高算法计算效率，又能保证推荐准确性，具有广泛的适应性。

5 结 论

本文针对SVD++推荐算法在推荐系统应用过程中计算效率低的问题，提出一种新的自适应学习率函数来优化推荐模型，通过在MovieLens三个不同规模的数据集上的实验表明，本文提出的方法可使算法的计算效率明显提高，且不影响预测结果的准确性。下一步要进行的研究是利用三维张量用户?项目?标签信息，采用高阶奇异值分解算法对用户的喜好进行概率分析。endprint

参考文献

[1] MISHRA R， KUMAR P， BHASKER B. A Web recommendation system considering sequential information [J]. Decision support systems， 2015， 75（C）： 1?10.

[2] 王国霞，刘贺平.个性化推荐系统综述[J].计算机工程与应用，2012，48（7）：66?76.

WANG G X， LIU H P. Survey of personalized recommendation system [J]. Computer engineering & applications， 2012， 48（7）： 66?76.

[3] KOREN Y， BELL R， VOLINSKY C. Matrix factorization techniques for recommender systems [J]. IEEE computer， 2009， 42（8）： 30?37.

[4] 张超，秦永彬，黄瑞章.结合置信度和SVD的协同过滤算法[J].计算机与数字工程，2015，43（5）：758?761.

ZHANG Chao， QIN Yongbin， HUANG Ruizhang. Collaborative filtering algorithms based on confidence level and SVD [J]. Computer & digital engineering， 2015， 43（5）： 758?761.

[5] 季芸，胡雪蕾.基于Baseline SVD主动学习算法的推荐系统[J].现代电子技术，2015，38（12）：8?11.

JI Yun， HU Xuelei. Recommender system based on Baseline SVD active learning algorithm [J]. Modern electronics technique， 2015， 38（12）： 8?11.

[6] 吴扬，林世平.基于正负反馈矩阵的SVD推荐模型[J].计算机系统应用，2015，24（6）：14?18.

WU Yang， LIN Shiping. SVD recommendation model based on positive and negative feedback matrix [J]. Computer system & application， 2015， 24（6）： 14?18.

[7] 方耀宁，郭云飞，丁雪涛，等.一种基于局部结构的改进奇异值分解推荐算法[J].电子与信息学报，2013，35（6）：1284?1289.

FANG Yaoning， GUO Yunfei， DING Xuetao， et al. An improved singular value decomposition recommender algorithm based on local structures [J]. Journal of electronics & information techno?logy， 2013， 35（6）： 1284?1289.

[8] ZHOU X， HE J， HUANG G， et al. SVD?based incremental approaches for recommender systems [J]. Journal of computer & system sciences， 2015， 81（4）： 717?733.

[9] GroupLens. MovieLens [EB/OL]. [2017?01?21]. http：//grouplens.org/datasets/movielens/.

[10] 陈清浩.基于SVD的协同过滤推荐算法研究[D].成都：西南交通大学，2015.

CHEN Qinghao. The research of collaborative filtering recommendation algorithm based on SVD [D]. Chengdu： Southwest Jiao Tong University， 2015.endprint