刘起东2016.pdf

兰州大学 信息科学与工程学院 作者简介作者简介:刘起东(1990),男（汉族）,河南省新乡市人,硕士,主要研究方向为个性化推荐、社交网络、数据挖掘以及大数据等等,.协同过滤：相似度在 Slope One 算法的作用*刘起东1 (1.信息科学&工程学院 兰州大学,兰州市 730000)摘摘 要要:Slope One 是一种 Item-based 的协同过滤算法。作为一个最近提出的算法，Slope One 算法有许多优点，比如简单、易扩展、计算复杂度低等。尽管 Slope One 算法广泛应用到大数据中，但是 Slope One 算法在精确度方面并不是太理想，因为 Slope One 算法没有考虑用户的相似度。在本文我们通过在 MovieLen 数据集上的实验分析出 Slope One 算法只适应于相似的群组里面，那些与当前用户拥有不同偏好的用户产生了很大的噪声。基于我们的发现，我们提出了一种新的加权 Slope One 算法，并在最后的实验中证明了我们算法的精确性。关键词关键词:协同过滤;推荐系统；Slope One 算法；相似度 中图分类号中图分类号:*文献标文献标志志码码:A 文章编号：文章编号：（作者可不填）doi:10.3969/j.issn.1001-3695(作者可不填)Collaborative Filtering:Similarity in Slope One Algorithm LIU Qi-dong1(1.School of information science&engineering,LanZhou University,LanZhou 730000,China)Abstract:Abstract:Slope One algorithm was kind of item-based collaborative filtering.As a recent proposed algorithm,Slope One have several desirable properties such as simple,being updatable on the fly,efficient to compute.Even though the Slope One algorithm was widely used on large datasets,it performs not so well in terms of accuracy.The reason is that the Slope One algorithm ignored a important factor:similarity between users.Using MovieLens data,we find that the Slope One algorithm is only applicable to similar user groups,the noise which the users have the opposite profile leads to the low accuracy.Based on our findings,we proposed an improved weighted Slope One algorithm which more accuracy.In the end,the results of the experiments on MovieLens datasets confirmed the effectiveness of our methods.Key words:Key words:collaborative filtering;recommender system;slope one;similarity 0 引言引言 随着互联网的快速发展，数据呈现爆炸式增长。信息超载问题使的用户无法从中获取对自己有用的部分。如何从海量的大数据中挖掘出有用信息变得越来越重要。推荐系统利用数据挖掘或者信息过滤技术为用户提供个性化信息、商品和服务推荐。随着大数据时代的到来，推荐系统得到了广泛的应用并吸引了大量的学者，原本仅仅是计算机科学的一个领域，渐渐变成数学家，物理学家和心里学家共同的研究热点1。作为推荐系统最常见的算法之一，协同过滤通过对过去交易记录进行分析找出与当前用户相似用户从而进行提供个性化推荐已广泛应用于各个领域2，3。随着电子商务的兴起，越来越多高精度的协同过滤算法被提出。但是这些算法往往计算复杂度较高并且难以实现。所以一个简单、易扩展并能运行在大数据上的算法非常重要4。Slope One 算法，第一次由 Lemire,D 在5中提出，吸引了很多研究者的目光。相比一些其它协同过滤算法，Slope One 算法拥有简单、易扩展以及计算复杂度低等优点。但是，Slope One 算法在精确度方面并不是太理想，很大一部分原因是没有考虑用户之间的相似度。Slope One 算法假设两个item 之间存在某种线性关系,如:()=+，但是这种假设并不是没有条件的。举个例子说明：假设我们要预测某君对某美剧的评分，已知对某韩剧的评分为。通过已知的数据可以计算出和之间的评分差：=。则根据 Slope One 算法对的评分为：=+。这里的取值非常关键。我们都知道男生大部分喜欢美剧而女生则更倾向于韩剧。如果此时的观测数据大部分来自女生，则计算出来的并不能很好的应用于身上。所以我们假设 Slope One算法只应用于相似的群组里面，那些与当前用户拥有不同偏好的用户产生了很大的噪声。在本文我们将用 MovieLens数据集验证这一观点，并基于这一发现提出一种新的加权Slope One 算法。1 Slope One 算法算法 1.1 基础基础Slope One算法算法 Slope One 算法作为协同过滤算法的一种，第一次由Lemire,D 在5中提出。Slope One 算法有许多优点，比如简单、易扩展、计算复杂度低并且不需要太大的计算内存。Slope One 算法的思想是假设两个 item 之间存在某种线性关系()=+，这里表示已知评分的 item，表示两个item 的平均差值。对于任意一个用户(,)，对 item 和的评分分别为和，则 item 和的平均差为：dev,=1card(,)()(,).（1）这里s(i,j)表示对 item 和共同评分的用户集合，只要和任何一个值不存在则 (,)。由 Eq.1 计算得到平均差之后，dev,+便可以计算兰州大学 信息科学与工程学院 出预测值。=1card()(dev,+).（2）这里=|已知且 表示与i相关的 item 集合，是已知数据表示用户对 item 的评分，dev,由 Eq.1 计算得到，表示 item 和的平均差。1.2 加权加权Slope One算法算法 由于对于不同的 item，用户评分的数量不同，即对任意j ,card(,)不同，Daniel Lenmire 又提出了一个加权 Slope One 算法，该算法将card(,)作为权值，card(,)越大意味着该预测评分越可靠。=(dev,+),（3）其中 ,=card(,).（4）这里=|已知且 表示与相关的 item 集合，是已知数据表示用户对 item 的评分，dev,由 Eq.1 计算得到，表示 item 和的平均差。1.3 Slope One算法的研究现状算法的研究现状 在 Slope One 算法提出之后，一系列的优化 Slope One算法被提出来，例如 Xing chen 等等将聚类方法应用到Slope One 算法中从而减少计算量6；Efthalia Karydi在7中提出了一个并行的Slope One算法加快执行的速度，从而提高算法的效率。除此之外，3,8提出将 Slope One算法与一些其他的算法相结合来解决数据稀疏性问题。在9中作者则将社交网络的一些内容融入进 Slope One 算法中，而10则结合了语义相似性。这些算法都是对 Slope One算法的一些扩展，但是这些方法都忽略了用户相似度的重要性。在本文我们将用 MovieLens 数据集来分析相似度在Slope One 算法中的作用，并基于我们的发现提出一种新的加权 Slope One 算法。2 用户相似度在用户相似度在 Slope One 算法中的算法中的作用作用 2.1 用用户相似度户相似度 为了分析相似度在 Slope One 算法中的作用，我们首先要找出一个合适的相似度计算方法。相似度计算方法在协同过滤算法中扮演着一个非常重要的角色，从用户中选取邻居并赋予权值，所以如何计算两个用户之间的相似度是协同过滤算法的一个关键问题11。目前常用的相似度计算方法有：皮尔逊系数（PCC）12以及余弦相似度（VS）13。利用 PCC 计算用户和的相似度公式为：,=()()(,)()2(,)()2(,).（5）而利用 VS 计算和的相似度公式为：,=(,)2(,)2(,).（6）这里(，)=|已知 已知表示用户和所有评分过的 item 集合，分别表示用户和对所有 item 评分的平均分。Hao Ma 等人在14一文中提出加入一个阈值来优化相似度方法 ,=min(,),),.（7）我们将Eq.7应用到PCC和VS中，分别记为SPCC和SVS，然后我们将对比 PCC,VS,SPCC 和 SVS 这四个相似度方法。在整个对比过程中我们将采用 Eq.8 产生预测评分，并分别采用平均绝对值误差(MAE)和均方根误差(RMSE)作为评测标准。=+,()(,),(,).（8）MAE 和 RMSE 的公式分别为：MAE=1|(,),（9）RMSE=1|()2(,).（10）这里表示测试集，|=card()表示测试集元素的个数。图 1 为 PCC,VS,SPCC 和 SVS 算法的对比结果，为了使实验更为可靠，我们采用 5 折验证法，然后取平均值。从实验结果中我们可以看出，SPCC 和 SVS 算法效果较好(MAE 和RMSE 值小)，尤其是邻居个数较少的时候，这是因为 PCC 和VS 算法在计算相似度的时候只考虑共同评分的 item，数据本身是稀疏的，所以能够用到的数据更少，甚至有的用户共同评分的个数只有一个，在这种情况下，计算得到的相似度是不可靠的。而 Hao Ma 等人提出优化相似度的方法在一定程度上缓解了这个问题。虽然目前有很多更精准的相似度计算方法，如15,16,17，但这些方法计算复杂度高且本文的重点不在于相似度，因此在此不再详细介绍。在以后的计算过程中，我们将采用 SPCC 作为相似度计算方法，因为 SPCC在四个方法中表现最好。2.2 相似度对相似度对Slope One算法的影响算法的影响 在找到合适的相似度计算方法之后，我们再来分析用户相似度对 Slope One 算法的影响。从第一节 Slope One 算法的介绍中我们可以看出，Slope One 算法并不考虑用户相似度，它仅仅假设在两个 item 之间存在某种线性关系。但仔细想想，这种假设并不完全正确。如果所有人的喜好都相同，则算法可行，若有一部分人不相同，正如我们在引言部分讲述的例子，可能会产生很大的噪声。因此，我们假设 Slope One 算法只适用于相似的群组里。但是，相似度为多少时才可以认为是相似的群组，相似度的阈值是多少？是否相似度的阈值越高，Slope One 算法的准确性就越高？在本节，我们将针对这些问题进行实验分析。首先我们对 Slope One 算法计算 item 平均差的公式进行重写，即对 Eq.1 重写。dev,=1card(,)()(,).（11）其中 (,)=|(,),.（12）图 1 相似度算法对比 01002003004005000.70.750.80.850.90.9511.05邻 居 数MAE vspccsvsspcc01002003004005000.90.9511.051.11.151.21.251.31.351.4邻 居 数RMSE vspccsvsspcc兰州大学 信息科学与工程学院 这里表示相似度阈值，,表示用户和的相似度。图 2 为 Slope One 算法在不同相似度阈值的结果，从图中可以看出，随着相似度阈值的增加MAE和RMSE逐渐减小并在=0.11左右达到极值。值得注意的是，MAE和RMSE在一开始变化较为平坦，并在 0.11之后开始出现快速反弹。对于第一个问题，我们对 MoiveLens 数据集相似度的分布进行了统计，如图 3 所示。从图中可以看到，相似度分布在-0.2之后的数据非常少，因此在=1,0.2这个区间，相似度阈值对 Slope One 算法的影响较小，所以图 2 中 MAE 和RMSE 在1,0.2区间变化较为平坦。对于第二个问题，我们认为是产生了过拟合的原因。在=0.11时已经过滤掉大约 50%的数据，随着阈值的继续增加，过滤掉的数据越来越多，能用的数据越来越少，得到的平均差也越来越不可靠。实验的结果证实了我们的假设，即 Slope One 算法只适用于相似的群组里，那些与当前用户拥有相反的偏好的用户产生了噪声。但相似度阈值并不是越大越好，阈值过大会造成过拟合的问题。这里 Slope One 算法在=0.11达到最优，最优结果 MAE=0.736502，RMSE=0.938758。3 改进加权改进加权 Slope One 算法算法 目前的Slope One算法大多数忽略了用户相似度的重要性。根据第二节的发现，本节我们将提出一种新的加权Slope One算法，与加权Slope One算法不同的是在计算item平均差的时候我们将利用相似度作为权值。公式如下：dev,=(),(,),(,).（13）这里,表示用户与的相似度，相似度越高说明和的偏好越相同，因此计算的差值也越可靠。而集合(,)则保证了过滤掉产生噪声的信息。预测评分公式我们仍将采用 Eq.3，但对于公式中的权值,我们有三种选择方案：方案 1：,=1.（14）即不考虑权值，对所有的 产生的预测值的权重相同。方案 2：方案2我们仍采用加权Slope One算法中Eq.4的权重。即将用户评分数量作为权值。方案 3：,=,(,).（15）我们分别将这三种方法记为 1-Slope One，N-Slope One，和 S-Slope One。稍后在下节的实验中我们将这三个方法分别与 Slope One 算法和加权 Slope One 算法。4 实验实验 在本节，我们将详细的介绍数据集、评价准则、运行环境以及参数设置，并在数据集上验证上面提到的所有方法，最后对实验结果进行分析。4.1 MovieLens数据集数据集 在本文，我们采用由美国明尼苏达大学的 GroupLens工作组研究人员基于 Web 开发的 MovieLens 数据集18。在本数据集中包含了 10 万条记录，包括 943 个用户对 1682部电影的评分，每个用户至少评价过 20 部电影。4.2 评价准则评价准则 为了测试算法的准确性，我们采用平均绝对值误差 MAE和均方根误差 RMSE 作为评价准则。MAE 和 RMSE 广泛应用于统计学中用来测量预测值与真实值的接近程度。4.3 运行环境及参数设置运行环境及参数设置 所 有 试 验 运 行 在 部 署 有Eclipse3.6.0（内 置JDK1.6.021）和 Matlab7.10.0.499 的 pc 机上，主要测试算法的精确度。相似度阈值我们将采用=0.11，其他参数会在实验过程中确定。4.4 算法对比算法对比 4.4.1 Slope One 算法对比 为了测试算法在各种稀疏程度的数据集中的精确度，我们分别将 MovieLens 数据集取90%,80%,70%,60%作为训练集，剩下的10%,20%,30%,40%作为测试集。从图中可以看出，我们提出的三种方法比 Slope One算法和加权 Slope One 算法更精确，特别是当训练数据比较多的时候，随着训练数据的减少，我们提出的方法的优势开始下降，但仍然比 Slope One 算法和加权 Slope Ones 算法图 2 相似度阈值对 Slope One 算法的影响-1-0.500.50.730.740.750.760.770.780.790.80.81MAE相 似 度 阈 值-1-0.500.50.920.940.960.9811.021.04RMSE相 似 度 阈 值 图 3MovieLens 数据集相似度分布-1-0.8-0.6-0.4-0.200.20.40.60.8100.10.20.30.40.50.60.70.80.91比例相 似 度 阈 值图 4 Slope One 算法对比 9:18:27:36:40.710.720.730.740.750.760.77MAE训 练 集:测 试 集 9:18:27:36:40.910.920.930.940.950.960.97RMSE训 练 集:测 试 集 SOWSO1SONSOSSOSOWSO1SONSOSSO兰州大学 信息科学与工程学院 精确度高，而在 6:4 的数据集上 1-Slope One 算法的 RMSE稍高于加权 Slope One，这是因为随着数据越来越稀疏，我们提出的阈值过滤了太多的数据，致使我们提出的加权方法的作用被削弱。为了验证是阈值的设置原因导致算法在数据稀疏的数据集上优势被削弱，同时为了验证我们的方法不仅仅是因为阈值的原因比其他算法更精确，而且我们提出的加权方法也提高了算法的精确度，在下面我们会针对这两个问题进行实验。4.4.2 相似度阈值在稀疏数据上的实验 此次实验我们选取 60%的数据作为训练集，40%的数据作为测试集。为了验证上面提到的两个问题，我们将对所有的方法都加上我们提出的阈值，在这里的范围为0.5,0.2，间隔为0.01。从上图可以看出，在阈值 0时，随着阈值的增加我们算法的优势逐渐减弱，这一现象证明了我们的另一个假设即阈值过大削弱了我们算法的作用，出现了过拟合现象。从图中我们还可以看出每个算法的最优阈值并不相同，在表 1 中我们列出了最佳的实验结果与最优阈值。从表中可以看出我们提出的方法的精确度高于 Slope One 算法和加权 Slope One 算法，同时也说明我们的方法也适用于稀疏的数据集中。表 1 最佳实验结果 so wso oso nso sso MAE 0.74374 0.73918 0.73845 0.73468 0.73504 RMSE 0.94806 0.94183 0.93970 0.93388 0.93597 0.07 0.07 -0.09 -0.09 -0.09 结束语结束语 本文针对目前 Slope One 算法精确度不高的问题，分析其原因，并通过 MovieLens 数据集验证了我们的想法即Slope One 算法只适用于相似的群组里。基于我们的发现我们提出了一种新的加权方法，实验结果表明，该方法可以很好的提高算法的精确度并适用于任何稀疏程度上的数据集。将来我们的重点将研究简单而且准确的相似度计算方法，我们相信更可靠的相似度方法能够提升我们算法的精确度。参考文献参考文献:1 L L,Medo M,Yeung C H,et al.Recommender systemsJ.Physics ReportsPhysics Reports,2012,519(1):1-49.2 Konstan J A,Miller B N,Maltz D,et al.GroupLens:applying collaborative filtering to Usenet newsJ.Communications Communications of the ACMof the ACM,1997,40(3):77-87.3 Zhang D J.An item-based collaborative filtering recommendation algorithm using slope one scheme smoothingC/Electronic Commerce and Security,Electronic Commerce and Security,2009.ISECS09.Second International Symposium on.IEEE,2009,2:215-217.4 Song S,Wu K.A creative personalized recommendation algorithmUser-based Slope One algorithmC/Systems and Systems and Informatics(ICSAI)Informatics(ICSAI),2012 International Conference on.IEEE,2012:2203-2207.5 Lemire D,Maclachlan A.Slope One Predictors for Online Rating-Based Collaborative FilteringC/SDMSDM.2005,5:1-5.6 Chen X,Hongfa W.Clustering Weighted Slope One for distributed parallel computingC/Computer Science and Computer Science and Network Technology(ICCSNT)Network Technology(ICCSNT),2011 International Conference on.IEEE,2011,3:1595-1598.7 Karydi E,Margaritis K G.Multithreaded Implementation of the Slope One Algorithm for Collaborative FilteringM/Artificial Intelligence Applications and Artificial Intelligence Applications and InnovationsInnovations.Springer Berlin Heidelberg,2012:117-125.8 Wang P,Ye H W.A personalized recommendation algorithm combining slope one scheme and user based collaborative filteringC/Industrial and Information SyIndustrial and Information Systemsstems,2009.IIS09.International Conference on.IEEE,2009:152-154.9 Jiang T,Lu W,Xiong H.Personalized collaborative filtering based on improved slope one alogarithmC/Systems and Systems and Informatics(ICSAI)Informatics(ICSAI),2012 International Conference on.IEEE,2012:2312-2315.10 Heng-yue W Y L O U.Improved Slope One Algorithm for Collaborative FilteringJ.Computer Science,2011:S1.11 Jin R,Chai J Y,Si L.An automatic weighting scheme for collaborative filteringC/Proceedings of the 27th Proceedings of the 27th annual annual international ACM SIGIR conference on Research and international ACM SIGIR conference on Research and development in information retrieval.ACMdevelopment in information retrieval.ACM,2004:337-344.12 Breese J S,Heckerman D,Kadie C.Empirical analysis of predictive algorithms for collaborative filteringC/Proceedings of the Fourteenth cProceedings of the Fourteenth conference on onference on Uncertainty in artificial intelligence.Morgan Kaufmann Uncertainty in artificial intelligence.Morgan Kaufmann Publishers IncPublishers Inc.,1998:43-52.13 Resnick P,Iacovou N,Suchak M,et al.GroupLens:an open architecture for collaborative filtering of netnewsC/Proceedings of the 1994 ACM conferenceProceedings of the 1994 ACM conference on on Computer supported cooperative work.ACMComputer supported cooperative work.ACM,1994:175-186.14 Ma H,King I,Lyu M R.Effective missing data prediction for collaborative filteringC/Proceedings of the 30th Proceedings of the 30th annual international ACM SIGIR conference on Research and annual international ACM SIGIR conference on Research and development in infdevelopment in information retrieval.ACMormation retrieval.ACM,2007:39-46.15 Luo H,Niu C,Shen R,et al.A collaborative filtering framework based on both local user similarity and global user similarityJ.Machine LearningMachine Learning,2008,72(3):231-245.16 Gori M,Pucci A.ItemRank:A Random-Walk Based Scoring Algorithm for Recommender EnginesC/IJCAIIJCAI.2007,7:2766-2771.17 Fouss F,Pirotte A,Renders J M,et al.Random-walk computation of similarities between nodes of a graph with application to collaborative recommendationJ.K Knowledge nowledge and Data Engineeringand Data Engineering,IEEE Transactions on,2007,19(3):355-369.18 http:/grouplens.org/datasets/movielens/-0.5-0.4-0.3-0.2-0.100.10.20.7340.7360.7380.740.7420.7440.7460.7480.750.7520.754相 似 度 阈 值MAE sowso1sonsosso兰州大学 信息科学与工程学院