原稿----一种基于机器学习的加权 Slope One 算法改进参考模板

1、一种基于机器学习的加权Slope One算法改进张玉连1，2，郇思思1，3，梁顺攀1，2 1 (燕山大学信息科学与工程学院,河北秦皇岛066004)2 (燕山大学信息科学与工程学院计算机教学实验中心,河北秦皇岛066004)3 (河北省计算机虚拟技术与系统集成重点实验室,河北秦皇岛066004)E-mail ：huansisi_ysu摘要：Slope One算法是一种基于内存的协同过滤推荐算法，但在计算时，内存消耗过大、预测结果准确度不高，尤其当用户数量和项目数量较大时，算法的执行效率会很低。基于此，本文将一种基于模型的算法融合到基于内存的Slope One算法中，提出一种使用机器学习中最小二

2、乘法改进的加权Slope One算法，该算法简单直观且计算高效，可以克服传统基于内存推荐算法的诸多缺点。最后，在Filmtrust和Movielens数据集上的对比实验结果表明，融合偏差因子的加权Slope One算法在这两个稀疏度不同的数据集下，均能获得较高的推荐准确度。关键词：协同过滤；机器学习；最小二乘法；加权Slope One算法1 / 8中图分类号：TP 文献标识码：A文章编号：Improved Weighted Slope One Algorithm Based on Machine LearningZHANG Yu-lian1,2，HUAN Si-s

3、i1,3， LIANG Shun-pan1,21 (Information Science and Engineering College, Yanshan University, Qinhuangdao 066004, China)2 (The Basic Computer Teaching Experiment Center, Information Science and Engineering College, Yanshan University, Qinhuangdao 066004, China)3 (The Key Laboratory for Computer Virtual

4、 Technology and System Integration of Hebei Province, Qinhuangdao 066004, China)Abstract: Slope One algorithm is a memory-based collaborative filtering recommendation algorithm, but in computing, the algorithms memory consumption is too large, and prediction accuracy is low, especially when the user

5、 and item number is larger. Therefore, this article puts forward integrate model-based and memory-based methods together ,called improved weighted Slope One algorithm based on machine learning, the algorithm is intuitive and efficient, can overcome the traditional disadvantages of the

6、 memory-based recommendation algorithms. Finally, experiments on the well-known datasets Filmtrust and Movielens show that the biased integrating least squares technique into weighted Slope One algorithm in the case of different sparse datasets can both achieve great improvement of prediction accura

7、cy. Key words: collaborative filtering;machine learning; least squares technique ;weighted Slope One algorithm1引言 随着互联网的发展和普及，信息过载问题愈加严重。在面对海量数据时，用户如何从冗余的信息中找到自己需要的内容，便成了一个值得研究的课题1。为有效解决信息过滤问题，推荐系统应运而生。协同过滤(Collaborative Filtering, CF)算法是推荐系统中较常用的算法之一2，是目前发展的最成熟的推荐技术，它仅仅通过分析用户的历史行为便可为用户进行推荐。按照内存的占用程

8、度和算法的计算效率，协同过滤推荐算法可分为两类：基于内存的协同过滤(Memory-Based Collaborative Filtering)和基于模型的协同过滤(Model-Based Collaborative Filtering)。目前，推荐算法的研究集中在基于内存的推荐上3-8，它为研究者提供了一种简单直观的方法进行预测，但内存消耗太大，且预测效果不明显。而基于模型的方法将数学模型与推荐算法相结合9，为研究者提供了一种内存占用少且高效的方式进行预测。为融合基于内存和基于模型推荐算法各自的优点，将机器学习中较为常用的最小二乘法与Slope One算法(Slope One Algorith

9、m, SO)结合对用户进行推荐。最小二乘法是机器学习方法中一种数字优化技术，计算预测值与实际评分值的误差平方和来得到最佳函数匹配9。Slope One算法是Lemire等人4提出的一种基于项目的协同过滤算法，它运算简便、易于实现和维护且具有良好的可扩展性等优点，但并未考虑到项目间相似度，在处理稍大规模的数据时，会遇到内存耗费过大，且所得预测结果准确度低等问题。针对以上问题，本文提出一种基于机器学习的加权Slope One算法 (Improved Weighted Slope One Algorithm Based on Machine Learning)，算法基本

10、思想为：(1)基于内存的方法简单直观，易于理解，而基于模型的方法在普遍比基于内存的方法可以得到更准确的预测结果，本文考虑将基于模型和基于内存的推荐方法两者的优点，提出一种新的算法为用户产生推荐；(2)加权Slope One算法在进行计算产生预测时，将系统中所有的项目视为平等的，仅计算了共同评论两个项目的用户的个数，并没有详细评定两个项目间的相似性。本文使用梯度下降的方法为两项目间相似度进行衡量，动态调节预测评分，进而提高预测准确度。2相关工作 协同过滤推荐算法是常用的推荐算法之一，其中，基于内存的协同过滤推荐算法2是现下研究者们比较常用的推荐算法， Slope One算法4 (Slope On

11、e algorithm, SO)就是一种基于项目的协同过滤推荐算法，它通过计算用户已评分项目间的偏差来产生预测，即使用线性关系来表示项目间的关系，具有计算简便、易于实现和维护、能为新用户提供推荐服务、具有高效的查询相应、具有合理的准确性等优点。但该算法在计算时，将项目间的相似度一视同仁，并未对相似度问题进行详细的衡量。文献4中还提出了一种加权Slope One算法(Weighted Slope One algorithm, WSO)，它考虑了同时评论两个项目的用户数量，但对项目间的不同却一视同仁，没有细致的区别开，这使得预测结果相较于Slope One算法预测结果的改善并不明显。Wang等人5

12、用Slope One算法填充用户-项目矩阵中的空缺值，而后使用基于用户的算法进行预测，提高了推荐的准确度。文献6也使用上述方法进行填充，不同的是在产生推荐时使用了基于项目的推荐算法。这两种方法都对用户-评分矩阵进行填充，但是这个方法存在偶然性，所得预测结果并不稳定。Gao等人7将基于内容的算法与Slope One算法相结合，但该模型在数据稀疏和可扩展性上所得的效果并不理想。如上所述，考虑到在现有的推荐系统中，由于用户数量和项目数量的快速增长，导致算法在进行计算时内存占用过度，导致运行较慢等问题。为提高算法效率，降低计算的复杂性，本文考虑将基于模型的协同过滤推荐算法也融入到算法改进中。其中，最小

13、二乘法9是机器学习方法中最简单有效的算法之一，使用最小二乘法可以简便地获得未知的预测数据，并使得预测数据与实际评分值之间的误差平方和最小。文献9就使用了最小二乘法对推荐算法进行改进，基本获得了较好的预测结果，但是算法的稳定性不强，在数据集较为稀疏时，得到的预测结果并不理想。3相关定义Lemire等人在文献4提出了一种新的协同过滤推荐算法，即Slope One算法(Slope One algorithm，SO)，它是一种基于项目的协同过滤推荐算法。该算法在实践中展现了自身的诸多优点，例如计算简单方便、易于实现和维护、能为新用户提供较为准确的推荐、具有快速的查询响应、具有较高的推荐准确性等优点，它

14、是通过计算用户共同评分项目之间的偏差来产生预测，相较于传统的协同过滤推荐算法，本算法展现了自身良好的计算性能。定义1. Slope One算法Slope One算法的计算过程，即找出如的函数形式，对两项目间的相似关系进行表示，即为每对项目根据其中一个项目的评分来预测另一个项目的评分。等式中的b表示两个项目被同一用户评分的评分偏差，x表示用户对已知项目的评分值。那么，给定两个项目i和j()，偏差计算公式devij如下所示： (1)其中，rui表示用户u对项目i的评分，Sij表示同时对项目i与j()有评分的用户集合，表示用户集合Sij中用户的数量。得到项目i与j()之间的偏差devij后，用户u即

15、可对项目i进行预测，预测公式preui如下： (2)其中，S(u)表示用户u所评分的所有项目的集合，表示集合中至少有一个项目(即i除外的项目)与项目i同时被用户u评分的项目集合。定义2. 加权Slope One算法上面讲到的Slope One算法没有考虑到同时被评分的项目的数量，显而易见，如果被不同用户同时进行评分的共同项目数量越多，那么预测结果就会越准确。故Lemire等人在文献4中还提出加权Slope One算法(Weighted Slope One Algorithm, WSO)如下： (3)等式中的表示共同评论项目i和j()的用户个数。4基于机器学习的加权Slope One算法改进接下

16、来，首先介绍一种基于最小二乘法的传统Slope One算法改进，然后再介绍四种基于最小二乘法的加权Slope One算法改进。4.1 基于最小二乘法的Slope One算法改进本文首先提出了一种基于最小二乘法的Slope One算法改进 (Integrating Least Squares Technique into Slope One Algorithm，LSO)。LSO算法的预测公式与加权Slope One算法的预测公式相似，由于在实验时，加权Slope One算法所得的预测结果要略优于Slope One算法，因此，本文依照加权Slope One算法模式，先提出了基于最小二乘法的Slop

17、e One算法，预测公式如下所示： (4)其中，将初始值设为1，即为原始的Slope One算法。通过解决最小二乘法的问题来确定的取值： (5)其中，表示测试集中用户对项目评分的真实值，最小二乘法通过真实评分值与预测评分值得残差平方和最小来确定拟合曲线的位置，从而得到更为接近真实评分值的预测值。本文将使用梯度下降的方法来确定最合适的值：if 其中，为预测偏差，计算方式为，表示划分的测试集中用户对项目评分的真实数值，表示使用Slope One算法预测所得到的用户对项目的评分预测值。是学习速率，其选取需要通过交叉验证，即反复试验来确定其取值。4.2基于最小二乘法的加权Slope One算法改进接下

18、来，提出一种基于最小二乘法的加权Slope One算法 (Integrating Least Squares Technique into Weighted Slope One Algorithm，LWSO)。由于加权Slope One算法考虑了权重问题，故在考虑因子时，可将因子视为衡量项目与项目的相似程度的指标10，则改进后的预测公式如下所示： (6)其中，的初始值仍设为1，即为加权Slope One算法。仍然通过解决最小二乘法的问题来确定的取值： (7)之后，依旧采用梯度下降的方法来确定最合适的值，但是，为了对比不同的梯度下降方法对预测结果的影响，本文采用两种不同的梯度下降方式来验证LWS

19、O算法，分别命名为LWSO1和LWSO2。LWSO1的梯度下降方式和LSO采用的方式一样，如下所示：if 其中，为预测偏差，计算方式为，与3.2中计算方式一样，不同的是，表示使用加权Slope One算法预测所得的用户对项目的评分预测值。而LWSO2的梯度下降方式则采用如下形式：if 显然，第二种梯度下降方式比第一种梯度下降方式在梯度间隔的选取时更为密集，之后的实验将验证两种梯度间隔的选取对实验结果的影响。4.3融合偏差因子的加权Slope One算法改进在现实生活中，人们在网上购物或者浏览网页进行评价时，往往会加入自己的偏见，这就是所谓的用户偏见，考虑到用户及项目的偏好，则需要对原始数据进行

20、归一化处理，用以消除用户及项目的偏好对算法的影响，因此，本文在接下来的改进中，把用户偏好问题也考虑到算法中，提出了一种新的融合偏差因子的加权Slope One算法(The Biased Integrating Least Squares Technique into Weighted Slope One Algorithm，BLWSO)。本文先定义用户u对项目i的偏好如下： (8)其中，是定值，即数据集中所有项目所得评分的平均值，是用户偏差，表示某个用户对已评分项目的所有评分平均值相对于数据集中所有评分平均分的偏差，是项目偏差，表示某个项目所得评分的平均分相对于数据集中所有评分平均分的偏差。改

21、进后的预测公式如下所示： (9)其中，的初始值仍设为1，和 初始化为0。通过解决最小二乘法的问题来确定的取值： (10)其中，加号后面的部分是为了防止训练过拟合。依旧采用梯度下降的方法来确定最合适的、和值，同上一种方法一样，为了对比不同的梯度下降方法对预测结果的影响，BLWSO算法也将采用两种不同的梯度下降方式来验证，分别命名为BLWSO1和BLWSO2。BLWSO1采用的梯度下降方式如下所示：if 而BLWSO2的梯度下降方式采用如下形式：if 5实验及结果分析 5.1 数据集为了更好的验证提出的五个算法的优劣，本文分别使用两个数据集对其进行试验。1）Filmtrust数据集。在这个数据集中

22、，包含有1508个用户对2071部电影共35497条评分记录。该数据集的评分范围为0.5-4.0分，用户给电影所打的评分越高，表示该用户对这部电影的喜爱程度越高。数据集的稀疏度为98.86%。2）Movielens数据集。这个数据集中，包含943个用户对1682部电影共100000条评分记录，该数据集的评分范围也为1-5分，据稀疏度为93.70%。选择数据集的标准，是为了验证在稀疏度相差较大的两个数据集中，改进后的五种方法是否都能获得较为理想的预测结果。为了防止训练过拟合，在实验时，采用了五折交叉验证法进行实验，即将这两个数据集分别均等的划为5份，取其中4份为训练集，剩下的1份为测试集。然后分

23、别进行五次实验，那么这五次实验所得结果的平均值即为实验结果。5.2 测量指标本实验采用平均绝对误差MAE(Mean Absolute Error, MAE)和均方根误差RMSE(Root Mean Squared Error, RMSE)对提出的五种方法的预测准确度进行验证。MAE计算方法如下： (11)其中，rui为用户u对项目i的实际评分，preui为用户u对用户i通过预测算法计算出来的预测评分。T为测试集，表示测试集中元素的个数。MAE越小，说明算法结果预测值与用户评分真实值越接近，结果就越准确，预测效果越好。RMSE计算方法如下： (12)同样，RMSE值越小，表示预测值与评分真实值越

24、接近，预测效果越好。5.3 实验结果与讨论本文设计了2组实验，来验证这五种算法在不同数据集下的算法性能。即分别在Filmtrust和Movielens数据集上将改进后的五种算法LSO、LWSO1、LWSO2、BLWSO1和BLWSO2算法分别与文献4中提出的SO算法和WSO算法进行比较。实验1 在Filmtrust数据集中，按各个算法进行计算，得到结果预测值，计算得出MAE（图1）和RMSE值（图2）并进行比较。其中，横坐标按照梯度下降的迭代次数进行设置，迭代次数分别为10、20、100次。由于文献4中提出的原始SO算法和加权SO算法在计算时不用迭代，故它们的MAE和RMSE结果没有任何变化趋

25、势，所得结果在图上表示即为一条直线。同时，由于它们的MAE和RMSE值比改进后的算法结果值偏大，为了使改进后的五种算法的MAE和RMSE值变化趋势更加明显，故用表1将原始SO算法和加权SO算法的结果单独进行展示。图1 各算法在Filmtrust数据集上MAE值比较Figure 1 Comparison of MAE between relevant recommendation algorithms on the Filmtrust dataset.图2 各算法在Filmtrust数据集上RMSE值比较Figure 2 Comparison of RMSE between relevant r

26、ecommendation algorithms on the Filmtrust dataset.表1 SO、WSO算法在Filmtrust数据集上MAE和RMSE值比较Table 1 Comparison of MAE and RMSE between SO、WSO algorithms on the Filmtrust dataset.MAERMSESO0.6372876630.845336008WSO0.6347011950.840286949从图1 、图2、表1中的数据可以看出，在Filmtrust数据集中， BLWSO2算法相比其他几个算法而言，包括文献4中提出的原始的SO算法和W

27、SO算法，能获得更小的MAE值，但同时考虑到预测准确度和算法的表现性能上来看，BLWSO1算法的效果更好。另外，比较两幅图在不同迭代次数时的MAE和RMSE值，可以看出，随着迭代次数的增多，LSO和LWSO1算法的性能一直很稳定，迭代次数的多少对其产生的影响不大。LWSO2、BLWSO1和BLWSO2算法收敛速度很快，且当迭代次数越多时，MAE和RMSE值也更小，预测结果越准确。实验2 在Movielens数据集上，分别对提出的五个算法进行计算，同实验1一样，将MAE（图3）和RMSE值（图4）进行比较，横坐标也按照梯度下降的迭代次数进行设置，迭代次数分别为10、20、100次。为了方便实验结

28、果与Filmtrust数据集实验结果进行对比，实验2中的其他设置与实验1相同。结果如图3、图4和表2所示：图3 各算法在Movielens数据集上MAE值比较Figure 3 Comparison of MAE between relevant recommendation algorithms on the Movielens dataset.图4 各算法在Movielens数据集上RMSE值比较Figure 4 Comparison of RMSE between relevant recommendation algorithms on the Movielens dataset.表2

29、SO、WSO算法在Movielens数据集上MAE和RMSE值比较Table 2 Comparison of MAE and RMSE between SO、WSO algorithms on the Movielens dataset.MAERMSESO0.7448660790.946691342WSO0.7408973390.940817242从图3、图4和表2分析得出，在Movielens数据集上，MAE和RMSE值的实验结果所呈现的趋势与在Filmtrust数据集上一致，都呈现下降趋势。随着迭代次数的增多，改进后的算法计算所得到的MAE和RMSE值，都比在Filmtrust数据集中所得

30、的结果要好，算法稳定性也略优于Filmtrust数据集。与Filmtrust数据集中一样，随着迭代次数的增多，LSO和LWSO1算法的性能一直很稳定，迭代次数的多少对其产生的影响不大。本文提出的BLWSO2方法在Movielens数据集也能获得较准确的推荐结果。另外，各个算法在Movielens数据集上算法的收敛速度比Filmtrust慢，说明本文提出的算法在数据稠密的情况下能获得更好的结果和稳定性。总体而言，BLWSO2算法相比本文提出的其他算法，MAE和RMSE值小很多，预测评分较准确，推荐精度较高，预测质量较好，具有良好的扩展性。综合图1-4中LWSO1和LWSO2算法、BLWSO1和B

31、LWSO2的算法结果可知，最小二乘法在不同的梯度下降方式中，所得的预测结果也是不同的，虽然变化趋势一致，但是第二种梯度下降方式明显比第一种梯度下降方式所得的预测结果更加准确，说明了第二种梯度下降的选取方式更加合理，由于梯度间跨度较小，故算法的收敛速度变慢，变化趋势更加明显。6结束语 本文重点研究了加权Slope One算法改进，该算法在计算时并未对项目间相似度进行详细的划分，同时考虑到基于模型的算法所得的结果普遍优于基于内存的算法，因此，本文在此基础上分别提出了五种方法，并将文献4中提出的SO和WSO算法与改进后的五种算法在两个数据集上分别进行比较，实验表明，改进后的五种算法相较于SO和WSO

32、算法预测结果更为准确。其中，BLWSO2算法的表现结果更为突出，预测结果好。同时，本文也验证了最小二乘法在不同的梯度下降的方式中所得的结果也是不同的，梯度间隔越小，数值选取越密集，算法的收敛速度越慢，趋势变化越明显，反之收敛速度变快。在未来的改进中，如何将加权Slope One算法使用其他机器学习的算法进行改进并提高算法的预测精度，更好的在数据稀疏的情况下高效的进行推荐，以及更合理满足用户偏好将是工作的中心和重点。References: 1 Xu Hai-ling, Wu Xiao, Li Xiao-dong, et al. Comparison study of Internet recom

33、mendation system J. Journal of Software, 2009, 20(2):350-362.2 Wang Peng, Wang Jing-Jing, Yu Neng-hai. A kernel and user-based collaborative filtering recommendation algorithmJ. Journal of Computer Research and Development, 2013, 50(7): 1444s-1451.3 Luo Jun, Zhu Wen-qi. User similarity function cons

34、idering weight of items similarity J. Computer Engineer-ing and Applications, 2013.4 Lemire D, Maclachlan A. Slope One Predictors for Online Rating-Based Collaborative FilteringC. In: Proceedings of the Fifth SIAM International Conference on Data Mining, 2005, 471-480. 5 Wang P, Ye H W. A Personalized Recommendation Algorithm Combining Slope One Scheme and User Based Collaborative FilteringC. In: Proceedings of the 2009 International Conference on Industrial and Information Systems, 2009: 152-154. 6 Zhang D J. An