协同过滤的推荐算法

探索推荐引擎内部的秘密，第2部分:深入推荐引擎相关算法-协同过滤本系列的第一篇为读者概要介绍了推荐引擎，下面几篇文章将深入介绍推荐引擎的相关算法，并帮助读者高效的实现这些算法。在现今的推荐技术和算法中，最被大家广泛认可和采用的就是基于协同过滤的推荐方法。它以其方法模型简单，数据依赖性低，数据方便采集,推荐效果较优等多个优点成为大众眼里的推荐算法“No.1”。本文将带你深入了解协同过滤的秘密，并给出基于ApacheMahout的协同过滤算法的高效实现。ApacheMahout是ASF的一个较新的开源项目，它源于Lucene，构建在Hadoop之上，关注海量数据上的机器学习经典算法的高效实现。内容o集体智慧和协同过滤o基于ApacheMahout实现高效的协同过滤推荐o总结o参考资料IBM技术文档：=search&sort_by=Date&sort_order=desc&view_by=Search&search_by=%E6%8E%A2%E7%B4%A2%E6%8E%A8%E8%8D%90%E5%BC%95%E6%93%8E%E5%86%85%E9%83%A8%E7%9A%84%E7%A7%98%E5%AF%86&dwsearch.x=12&dwsearch.y=11&dwsearch=Go集体智慧和协同过滤什么是集体智慧集体智慧(CollectiveIntelligence)并不是Web2.0时代特有的，只是在Web2.0时代，大家在Web应用中利用集体智慧构建更加有趣的应用或者得到更好的用户体验。集体智慧是指在大量的人群的行为和数据中收集答案，帮助你对整个人群得到统计意义上的结论，这些结论是我们在单个个体上无法得到的，它往往是某种趋势或者人群中共性的部分。Wikipedia和Google是两个典型的利用集体智慧的Web2.0应用：Wikipedia是一个知识管理的百科全书，相对于传统的由领域专家编辑的百科全书，Wikipedia允许最终用户贡献知识，随着参与人数的增多，Wikipedia变成了涵盖各个领域的一本无比全面的知识库。也许有人会质疑它的权威性，但如果你从另一个侧面想这个问题，也许就可以迎刃而解。在发行一本书时，作者虽然是权威，但难免还有一些错误，然后通过一版一版的改版，书的内容越来越完善。而在Wikipedia上，这种改版和修正被变为每个人都可以做的事情，任何人发现错误或者不完善都可以贡献他们的想法，即便某些信息是错误的，但它一定也会尽快的被其他人纠正过来。从一个宏观的角度看，整个系统在按照一个良性循环的轨迹不断完善，这也正是集体智慧的魅力。Google：目前最流行的搜索引擎，与Wikipedia不同，它没有要求用户显式的贡献，但仔细想想Google最核心的PageRank的思想，它利用了Web页面之间的关系，将多少其他页面链接到当前页面的数目作为衡量当前页面重要与否的标准；如果这不好理解，那么你可以把它想象成一个选举的过程，每个Web页面都是一个投票者同时也是一个被投票者，PageRank通过一定数目的迭代得到一个相对稳定的评分。Google其实利用了现在Internet上所有Web页面上链接的集体智慧，找到哪些页面是重要的。什么是协同过滤协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤(CollaborativeFiltering,简称CF)，首先想一个简单的问题，如果你现在想看个电影，但你不知道具体看哪部，你会怎么做？大部分的人会问问周围的朋友，看看最近有什么好看的电影推荐，而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。协同过滤一般是在海量的用户中发掘出一小部分和你品位比较类似的，在协同过滤中，这些用户成为邻居，然后根据他们喜欢的其他东西组织成一个排序的目录作为推荐给你。当然其中有一个核心的问题：如何确定一个用户是不是和你有相似的品位？如何将邻居们的喜好组织成一个排序的目录？协同过滤相对于集体智慧而言，它从一定程度上保留了个体的特征，就是你的品位偏好，所以它更多可以作为个性化推荐的算法思想。可以想象，这种推荐策略在Web2.0的长尾中是很重要的，将大众流行的东西推荐给长尾中的人怎么可能得到好的效果，这也回到推荐系统的一个核心问题：了解你的用户，然后才能给出更好的推荐。深入协同过滤的核心前面作为背景知识，介绍了集体智慧和协同过滤的基本思想，这一节我们将深入分析协同过滤的原理，介绍基于协同过滤思想的多种推荐机制，优缺点和实用场景。首先，要实现协同过滤，需要一下几个步骤收集用户偏好找到相似的用户或物品计算推荐收集用户偏好要从用户的行为和偏好中发现规律，并基于此给予推荐，如何收集用户的偏好信息成为系统推荐效果最基础的决定因素。用户有很多方式向系统提供自己的偏好信息，而且不同的应用也可能大不相同，下面举例进行介绍：表1用户行为和用户偏好用户行为类型特征作用评分显式整数量化的偏好，可能的取值是[0,n]；n一般取值为5或者是10通过用户对物品的评分，可以精确的得到用户的偏好投票显式布尔量化的偏好，取值是0或1通过用户对物品的投票，可以较精确的得到用户的偏好转发显式布尔量化的偏好，取值是0或1通过用户对物品的投票，可以精确的得到用户的偏好。如果是站内，同时可以推理得到被转发人的偏好（不精确）保存书签显示布尔量化的偏好，取值是0或1通过用户对物品的投票，可以精确的得到用户的偏好。标记标签(Tag)显示一些单词，需要对单词进行分析，得到偏好通过分析用户的标签，可以得到用户对项目的理解，同时可以分析出用户的情感：喜欢还是讨厌评论显示一段文字，需要进行文本分析，得到偏好通过分析用户的评论，可以得到用户的情感：喜欢还是讨厌点击流隐一组用户的点击，用户对物用户的点击一定程度上反映了用户的(查看)式品感兴趣，需要进行分析，得到偏好注意力，所以它也可以从一定程度上反映用户的喜好。页面停留时间隐式一组时间信息，噪音大，需要进行去噪，分析，得到偏好用户的页面停留时间一定程度上反映了用户的注意力和喜好，但噪音偏大，不好利用。购买隐式布尔量化的偏好，取值是0或1用户的购买是很明确的说明这个项目它感兴趣。以上列举的用户行为都是比较通用的，推荐引擎设计人员可以根据自己应用的特点添加特殊的用户行为，并用他们表示用户对物品的喜好。在一般应用中，我们提取的用户行为一般都多于一种，关于如何组合这些不同的用户行为，基本上有以下两种方式：将不同的行为分组：一般可以分为“查看”和“购买”等等，然后基于不同的行为，计算不同的用户/物品相似度。类似于当当网或者Amazon给出的“购买了该图书的人还购买了...”，“查看了图书的人还查看了...”根据不同行为反映用户喜好的程度将它们进行加权，得到用户对于物品的总体喜好。一般来说，显式的用户反馈比隐式的权值大，但比较稀疏，毕竟进行显示反馈的用户是少数；同时相对于“查看”，“购买”行为反映用户喜好的程度更大，但这也因应用而异。收集了用户行为数据，我们还需要对数据进行一定的预处理，其中最核心的工作就是：减噪和归一化。减噪：用户行为数据是用户在使用应用过程中产生的，它可能存在大量的噪音和用户的误操作，我们可以通过经典的数据挖掘算法过滤掉行为数据中的噪音，这样可以是我们的分析更加精确。归一化：如前面讲到的，在计算用户对物品的喜好程度时，可能需要对不同的行为数据进行加权。但可以想象，不同行为的数据取值可能相差很大，比如，用户的查看数据必然比购买数据大的多，如何将各个行为的数据统一在一个相同的取值范围中，从而使得加权求和得到的总体喜好更加精确，就需要我们进行归一化处理。最简单的归一化处理，就是将各类数据除以此类中的最大值，以保证归一化后的数据取值在[0,1]范围中。进行的预处理后，根据不同应用的行为分析方法，可以选择分组或者加权处理，之后我们可以得到一个用户偏好的二维矩阵，一维是用户列表，另一维是物品列表，值是用户对物品的偏好，一般是[0,1]或者[-1,1]的浮点数值。找到相似的用户或物品当已经对用户行为进行分析得到用户喜好后，我们可以根据用户喜好计算相似用户和物品，然后基于相似用户或者物品进行推荐，这就是最典型的CF的两个分支：基于用户的CF和基于物品的CF。这两种方法都需要计算相似度，下面我们先看看最基本的几种计算相似度的方法。相似度的计算关于相似度的计算，现有的几种基本方法都是基于向量（Vector）的，其实也就是计算两个向量的距离，距离越近相似度越大。在推荐的场景中，在用户-物品偏好的二维矩阵中，我们可以将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，或者将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度。下面我们详细介绍几种常用的相似度计算方法：欧几里德距离（EuclideanDistance）最初用于计算欧几里德空间中两个点的距离，假设x，y是n维空间的两个点，它们之间的欧几里德距离是：可以看出，当n=2时，欧几里德距离就是平面上两个点的距离。当用欧几里德距离表示相似度，一般采用以下公式进行转换：距离越小，相似度越大皮尔逊相关系数（PearsonCorrelationCoefficient）皮尔逊相关系数一般用于计算两个定距变量间联系的紧密程度，它的取值在[-1，+1]之间。sx,sy是x和y的样品标准偏差。Cosine相似度（CosineSimilarity）Cosine相似度被广泛应用于计算文档数据的相似度：Tanimoto系数（TanimotoCoefficient）Tanimoto系数也称为Jaccard系数，是Cosine相似度的扩展，也多用于计算文档数据的相似度：相似邻居的计算介绍完相似度的计算方法，下面我们看看如何根据相似度找到用户-物品的邻居，常用的挑选邻居的原则可以分为两类：图1给出了二维平面空间上点集的示意图。固定数量的邻居：K-neighborhoods或者Fix-sizeneighborhoods不论邻居的“远近”，只取最近的K个，作为其邻居。如图1中的A，假设要计算点1的5-邻居，那么根据点之间的距离，我们取最近的5个点，分别是点2，点3，点4，点7和点5。但很明显我们可以看出，这种方法对于孤立点的计算效果不好，因为要取固定个数的邻居，当它附近没有足够多比较相似的点，就被迫取一些不太相似的点作为邻居，这样就影响了邻居相似的程度，比如图1中，点1和点5其实并不是很相似。基于相似度门槛的邻居：Threshold-basedneighborhoods与计算固定数量的邻居的原则不同，基于相似度门槛的邻居计算是对邻居的远近进行最大值的限制，落在以当前点为中心，距离为K的区域中的所有点都作为当前点的邻居，这种方法计算得到的邻居个数不确定，但相似度不会出现较大的误差。如图1中的B，从点1出发，计算相似度在K内的邻居，得到点2，点3，点4和点7，这种方法计算出的邻居的相似度程度比前一种优，尤其是对孤立点的处理。图1.相似邻居计算示意图计算推荐经过前期的计算已经得到了相邻用户和相邻物品，下面介绍如何基于这些信息为用户进行推荐。本系列的上一篇综述文章已经简要介绍过基于协同过滤的推荐算法可以分为基于用户的CF和基于物品的CF，下面我们深入这两种方法的计算方法，使用场景和优缺点。基于用户的CF（UserCF）基于用户的CF的基本思想相当简单，基于用户对物品的偏好找到相邻邻居用户，然后将邻居用户喜欢的推荐给当前用户。计算上，就是将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，找到K邻居后，根据邻居的相似度权重以及他们对物品的偏好，预测当前用户没有偏好的未涉及物品，计算得到一个排序的物品列表作为推荐。图2给出了一个例子，对于用户A，根据用户的历史偏好，这里只计算得到一个邻居-用户C，然后将用户C喜欢的物品D推荐给用户A。图2.基于用户的CF的基本原理基于物