一种改进的协同过滤推荐算法

一种改进的协同过滤推荐算法摘要：协同过滤算法自提出以来便得到了广泛运用，但协同过滤算法本身具有的数据稀疏性及冷启动问题也制约了算法的性能。通过分析协同过滤算法的原理和不足，提出了一种改进协同过滤算法的思路，并在MovieLens数据集上进行了验证，一定程度上提高了算法性能。关键词关键词：推荐系统；协同过滤；数据稀疏性中图分类号：TP312文献标识码：A文章编号：1672-7800（2016）004-0063-030引言网络技术的迅猛发展使得互联网上的信息呈现爆炸式增长，为人们的生活和学习提供了便利，与此同时，海量的数据也带来了一些问题，其中最主要的就是“信息过载”问题。所谓信息过载问题，是指由于不相关的垃圾数据过多从而导致用户无法准确找到自己想要信息的问题。为应对信息过载问题，人们提出了各种解决方案，其中最为用户所熟悉的无疑是搜索引擎技术。但搜索引擎的服务是被动的，它要求使用者必须先给出一个搜索关键字，然后才能提供与该关键字相关的信息。这种完全依赖于关键字的服务模式要求用户能用关键字准确描述自己所需信息，否则无法提供服务，但是现实中用户很多时候并不能精确描述自己的需求信息。这种情况下，以推荐系统为代表的技术可以较好地解决该问题，提高用户的使用体验。1协同过滤算法1.1算法介绍“协同过滤”技术最早由GlodBerg等于20世纪90年代提出，该技术最初被用来过滤电子邮件[1]，此后这种技术取得了商业上的巨大成功，得到了广泛使用[2-3]。协同过滤的基本思想是，如果两个用户在一些项目上具有相似的评价信息，包括显示的直接评分信息或者点击、购买等隐式评价信息，则这两个用户具有相似兴趣。一般而言，协同过滤需要使用到的用户评价信息会被存储在一个数据表中，该表可以被称为用户评分矩阵。协同过滤技术的关键在于计算两个用户或者项目的相似度，然后根据相似的用户或者项目进行推荐。其中如果根据某一用户的评分数据寻找到与其相似的用户，并依据相似用户的爱好对活动用户进行推荐的思想被称为基于用户的协同过滤。如果知道用户对某一项目评分较高，则可以根据评分矩阵寻找与这一项目相似的项目推荐给用户，这种思想被称为基于项目的协同过滤。两种协同过滤算法的基本步骤比较相似。首先，依据用户对物品的评分建立用户评分矩阵，矩阵的行数为系统中用户的数量，列数为系统中物品的数量，没有评分数据的默认为零；然后依据用户评分矩阵计算相似度，目前比较主流的相似度计算方法有余弦相似度和Pearson相关系数。余弦相似度：将某一用户的评分看作1个N维向量，用户之间的相似度是通过用户的评分向量间夹角的余弦来计算，夹角越小则相似度越高，余弦向量相似度计算公式如下：1.2算法优缺点协同过滤技术是目前最成功的推荐技术，尽管这种技术在商业上取得了巨大成功，但该技术依然有一些关键技术点有待改进。相对于其它各种推荐技术，协同过滤的最大优点在于这种技术不需要被推荐对象具备专业领域知识，不需要分析被推荐对象的特征属性，因为协同过滤推荐完全依赖于用户对项目的评分数据，与被推荐对象的具体特征无关，从而使得这种技术可以运用于各种领域的推荐，使用范围较广。尽管协同过滤有各种优点，但这种算法本身也存在一些不足，主要是数据稀疏性问题和冷启动问题[4]。在一个大的系统中，如购物网站中，存在的项目或者物品数量数以百万计，而一个用户可能评价的项目只占其中非常小的一部分，这就造成了评分矩阵的稀疏性，事实上在大型商用推荐系统中，评分矩阵的密度很少有超过1%的[4]。根据协同过滤算法的原理，用户或项目的相似度是根据两个用户评分向量中的共同项来计算的，在评分矩阵过于稀疏的情况下，可能没有足够的共同项来计算相似度，从而影响推荐精度[5]。除了数据稀疏性问题，协同过滤算法面临的另一个挑战是冷启动问题，冷启动问题可以看成是稀疏性问题的极端情况。当一个新项目加入系统时没有评价数据，则该项目不可能被推荐，推荐系统也就失去作用。2改进的协同过滤算法随着推荐系统规模越来越大，传统推荐算法中的问题也越来越突出。当前的推荐系统有成千上万的物品和用户，由此建立的用户评分矩阵将非常大，计算相似度的过程将非常耗时。同时，系统中物品众多，而一个用户打分的物品可能只有很少几项，这将导致评分矩阵中出现大量的未评分项，从而导致评分矩阵的稀疏性。为改善这些问题，可以使用聚类算法对原始数据进行聚类，划分出不同的聚类簇，这样推荐算法可以在聚类簇中快速找到邻居集合，从而提高算法效率。2.1聚类算法根据上述原理对原始数据进行聚类，将相似项目划分到同一个簇中，此后计算相似度和寻找邻居项目时都使用经过聚类后的聚类簇作为数据源。聚类算法可以选用经典的K-means算法，算法过程如下：输入：原始项目数据和聚类个数K。输出：K个聚类。①从原始项目集合中随机选择K个对象作为初始聚类中心点；②计算每个对象到各中心点的距离，并根据最小距离划分类别；③重新计算每个聚类类别的中心点；④重复②和③直到不再变化。经过上述步骤后，原始项目数据集将被划分到几个不同的聚类簇中，每个聚类簇就是一个子评分矩阵，此后查找活动项目的相似邻居就在目标项目所在的子矩阵中进行。由于一个推荐系统的项目相对固定，变化不大，因此可以事先离线计算，对系统的实时性并无影响。2.2协同过滤推荐考虑到系统中项目数量较大，聚类之后每个子矩阵中的数据可能依然比较稀疏，因此可以使用基于项目的协同过滤对这些需要使用的子矩阵进行一定程度的填充，以降低子矩阵的稀疏度。算法过程如下：①计算子矩阵中的每个项目与其它项目的相似度，并取其中相似度最大的N个作为最近邻；②根据邻居的评价信息，利用预测值公式来计算未评价项的预测值，并将值填入子矩阵。经过以上步骤得到新的、稀疏度降低后的子矩阵，然后使用基于用户的协同过滤算法在该矩阵上进行推荐。3实验结果3.1数据集与评价标准实验采用MovieLens数据集，在实验中使用u1.base训练数据集来实现用户对未评分的电影进行分值预测，将预测的评分与u1.test测试数据集中的分值进行比较。本文采用平均绝对误差（MAE）作为衡量推荐质量的标准，MAE是通过用户的预测评分与实际评分之间的差值来判断预测的精确度，差值越小，则预测精度越高。若预测用户对项目的评分集合为{r1，r2，…，ri，…，rn}，而实际的测试数据集中用户对项目的评分集合为{t1，t2，…，ti，…，tn}，则MAE可定义如下：MAE=∑ni=1ri-tin（6）3.2实验结果本文通过两个实验来检测和比较上文中提出的改进型协同过滤算法（Proposed）的推荐精度和传统推荐算法的性能差异。第1个实验是验证在相同的数据集上选择不同的邻居数时3种推荐算法推荐精度的差异，结果如图1所示；第2个实验中对数据集进行不同程度的填充以得到新的不同稀疏度的数据集，并验证3种推荐算法在不同稀疏度下数据集上的性能稳定性。从实验数据可以发现，协同过滤算法在一定范围内选择的邻居数越多，推荐的精度相对越高。由实验结果可知，本文提出的改进型协同过滤算法的推荐误差均要小于两种传统的协同过滤算法，算法精度有一定程度的提高。从实验数据可以看到，随着数据集中填充数据的增多，推荐的误差有一定减少，算法精度有一定程度的改善。但是这种规律只局限在一定的范围内，当填充的数据过多，数据集的稀疏度低于某一特定值时，算法的误差反而增大。4结语本文介绍了协同过滤算法的基本原理，分析了传统协同过滤算法中存在的数据稀疏性问题，提出了一种改进的协同过滤算法思路，一定程度上改善了协同过滤算法中的数据稀疏性问题，提高了推荐结果的可靠性和稳定性。但试验中也发现了一些问题，有待今后进一步研究。参考文献：[1]GOLDBERGD，NICHOLSD，OKIBM，etal.Usingcollaborativefilteringtoweaveaninformationtapestry[J].CommunicationsoftheACM，1992，35（12）：61-70.[2]GOLDBERGK，ROEDERT，GUPTAD，etal.Eigentaste：aconstanttimecollaborativefilteringalgorithm[J].InformationRetrieval，2001，4（2）：133-151.[3]余明哲.图书馆个人化馆藏推荐系统[D].台湾：台湾“国立交通大学”，2003[4]孔维梁.协同过滤推荐系统关键问题研究[D].武汉：华中师范大学，2013.[5]赵亮，胡乃静.个性化推荐算法设计[J].计算机研究与发展，2002，39（8）：986-991.[6]何安.协同过滤技术在电子商务推荐系统中的应用研究[D].杭州：浙江大学，2007.[7]王永固，邱飞岳，赵建龙，等.基于协同过滤技术的学习资源个性化推荐研究[J].远程教育杂志，2011（3）：66-71.[8]刘建国，周涛，汪秉宏.个性化推荐系统的研究进展[J].自然科学进展，2009（1）：1-15.（责任编辑：孙娟）