协调过滤推荐的算法框架.doc

An algorithmic framework for performing collaborative filtering摘要：自动的协同过滤技术迅速成为减少信息过载的流行工具，经常用于基于内容的信息过滤系统。我们通过本文献来展示协同过滤应用的算法框架，以及能增加协同预测算法准确率的新的算法元素，并给出了选择正确的协同过滤算法组件的建议。1、介绍自动的协同过滤技术迅速成为减少信息过载的流行工具，经常用于基于内容的信息过滤系统。自动的协同过滤技术在因特网领域取得了很多成功，比如在亚马逊网站、CDNow网站以及MovieFinder网站。基于内容的和协同的过滤使用不同类型的数据来得到一个过滤决策。内容过滤工具通过对文件中包含的信息与用户感兴趣的内容信息进行比较，选择正确的信息给正确的人。内容过滤在使用向量空间查询、智能代理和信息可视化等技术的涉及话题的文本文件查找方面非常有效率。自动化的协同过滤系统的运行是通过收集人对某一领域内项目的判断（比如评分），并与分享了相同信息需求或相同兴趣的人进行匹配。协同过滤系统的用户分享他们对每个项目的分析判断和意见，使得系统中的其他用户能够更好的决定选择哪个项目。同时，协同过滤系统为每个有趣的项目提供个性化的推荐。在信息过滤中，相比基于内容的过滤，协同过滤提供了三个关键的额外优点：（1）支持对项目的过滤（项目的内容不方便通过自动处理过程进行分析）；（2）对项目进行过滤的功能是基于质量和兴趣的；（3）提供偶然性推荐的能力。首先，在协同过滤中，人们决定信息流中项目的相关性、质量和兴趣。其结果就是，过滤技术能用于分析类似于电影、想法、感觉、人和政治等计算机难以分析的事物。其次，协同过滤系统能强化信息过滤系统，通过在维度而不仅仅是简单的从内容角度来衡量一个项目有多符合用户的需求和兴趣的方法，人们可以从质量或兴趣的维度来分析，这对于电脑是很难处理的。基于内容的搜索可以得到美联社关于Minnesota Governor Jesse Ventura的所有文章，但是结合协同过滤，可以得到相关文章中所有写得好的。最后，协同过滤系统有时可用于偶然性推荐，即推荐项目包含的内容可能并不符合用户预期的，但却对用户有价值（事先不知道有这个项目，但推荐系统给出推荐后，发现也是自己喜欢的）。我们发现，偶然性推荐频繁使用于电影领域，通过协同过滤系统精确推荐用户可能从没有想过的电影。协同过滤用于强化信息过滤工具的潜力是巨大的，但是为了达到最大的潜力，它必须结合现有的基于内容的信息过滤技术。协调过滤本身能很好的预测满足用户兴趣或口味的项目，但不能很好的适用于对具体信息内容需求的定位。在本文献中，我们提出了一个应用协调过滤的算法框架，并验证了已有的算法变量在该框架下是如何表现的，并提出一个对已有预测算法的新的有效改善，最后通过一组对预测算法变量选择的建议作为总结。2、问题域自动化的协同过滤存在的问题是，给定一系列用户决策的历史参考，如何预测用户对他未评分的项目的喜欢程度。参考的决策行为可以是用户的可见的观点记录，或者是对用户行为中的有价值数据的隐式计量。可见的计量通常是一个简单的对每个项目的数字评分，高分值代表很强的兴趣，低分值代表很不感兴趣。当用户看到一个预测的项目时，通常需要他们对该项目进行评分。隐式的评分通常来源于类似于消费记录或web logs等数据源，因此leveraging 数据已经收集，并用于其他目的。 其他隐式表现的数据来源还有阅读使用的时间、在Usenet posting 上的URL链接。对使用隐式评分的自动化协同过滤所做的研究还比较少，尽管有一种方法已经在考虑用于支持隐式评分，即将阅读时间等隐式行为与显性评分范围进行映射，然后使用已有的协同过滤算法。从本文献的目的出发，我们将考虑用户评分数据，从1到5分布。预测引擎收集所有的评分，并使用协同过滤技术提供预测。一个活跃用户提供一组项目给预测引擎，而预测引擎返回对这些项目的预测评分。大多数预测引擎也提供一个推荐模型，返回一个前N个最高评分的项目给当前用户。为了提供一个动态的用户界面，预测引擎存在性能约束。潜在的预测请求必须少于1秒，而且预测引擎必须能频繁支持每秒钟几百次预测请求。问题域可以通过由用户和项目组成的矩阵来构造，每个矩阵元素代表一个用户对某个项目的评分。因此，问题在于预测某个空元素的值。在协同过滤中，矩阵通常是稀疏的，因为每个用户仅会对少数项目进行评分。协同过滤中最常用的算法是“基于邻居的算法”。在这个算法中，通过与当前用户相似性比较，选出合适的用户子集，然后使用他们的评分权重合计，产生对当前用户的推荐。其他使用过的算法有贝叶斯网络、神经网络分类和规则学习。本文中我们将探讨基于邻居的协同过滤方法，并描述一些我们新发展的更好的表现算法。基于邻居的算法可以分为三个步骤：（1）基于与当前用户的相似度给所有用户赋权值。（2）选择一个用户子集作为预测集（可能对于一个指定的项目）。（3）对评分进行标准化处理，在所选邻居评分的权重集中得出一个预测。在具体的系统中，这些步骤可能相互包含，或者顺序可能有些不同。我们将开始讨论在协同过滤领域中的相关工作，并且在适当的时候检测哪种技术用于实施基于邻居的算法中的三个步骤。3、相关工作协同过滤的概念相对比较新，而且在信息过滤领域中就更少。协同过滤术语由Goldberg etal首先提出，他是第一个发布关于在信息过滤领域使用协同过滤技术报告的人。他们建立了一个用于过滤邮件的系统Tapestry，允许用户注释消息。注释信息作为消息的虚拟领域变得可获得，而且用户能建立过滤查询获取这些领域。用户能生成查询，比如“展示出所有Bill认为重要的office memos”。Tapestry 提供的协同过滤不是自动的，而且需要用户使用一种特殊的查询语言为某个任务建立复杂的查询。GroupLens首先介绍了一个自动化的协同过滤系统，它使用基于邻居的算法。GroupLens 为Usenet新闻文章提供了个性化的预测。原始的GroupLens 系统使用Pearson相关系数来对用户相似性赋权值，使用所有有用的相关邻居，通过执行邻居平均数偏差的权重平均数，计算出最终的预测：其中Pa,i 代表对项目i的当前用户的预测。n代表邻居数量，wa,u 是当前用户与邻居u的相似性权重，通过Pearson 相关系数进行定义：Ringo音乐推荐系统和Bellcore Video推荐系统基于上述原始GroupLens算法进行了扩展。Ringo注重更好的执行效果，它通过使用限定的Pearson相关系数计算相似性权重：其中4 是选定的，因为它是7分制的中间值。Ringo通过只选择相关系数大于固定阈值的邻居的方式，限定了邻居间的成员关系，通过更大的阈值产生更高的精确率，但是减少了Ringo可产生预测的项目的数量。为了产生预测，Ringo计算邻居中所有用户评分权重的均值。BellcoreVideo 推荐系统使用Pearson相关性来权衡邻居中的一个随机样本，选择最佳邻居，并对邻居进行多次回归产生预测。Breese等对基于邻居的协同过滤算法中的若干变量进行经验分析，对于计算相似性权重，使用了Pearson相关性和cosine向量相似性。其他不使用基于邻居的预测算法的协同过滤系统也得到发展。Fab系统通过从内容角度定义用户兴趣、收集用户评分，并向相似用户推送高评分的文件，以集成内容和协同过滤。还有其他系统用于推荐web资源等。4、方法学4.1数据、实验技术为了比较不同的基于邻居的预测算法的结果，我们运行一个使用从MovieLens电影推荐网站上匿名收集来的历史评分数据的预测引擎。历史数据包含了1173位用户的122176条评分，每个用户至少对20部电影进行了评分。我们随机选择10%的用户作为测试集。对于测试集中的每个用户，保留下来对5个项目的评分，预测结果就是从这5个项目中产生，使用了测试的基于邻居的预测算法中的每个变量。对于每个预测的项目，选择对该项目进行过评分的且排名最高的邻居，用于计算预测项。需要注意的是，这意味着一个用户针对每个项目都可能有不同的邻居。数据集中所有的用户都作为某个用户的潜质邻居进行检测。评价一个预测算法的质量，可以通过比较保留评分的预测值与真实值。4.2度量标准 有三个关键维度来度量预测算法的质量。覆盖面：覆盖面是推荐系统能提供预测的项目百分比的度量标准。一个基本的覆盖面度量是用于有效预测的项目百分比。一般的能减少覆盖率的系统特征是小的邻居数量和用于查找邻居的用户样本数量。我们计算覆盖率是作为一个预测请求以及系统能够产生一个预测的所需的所有用户的项目的百分比。除非另有说明，否则所有的实验结果都有最大的覆盖率，由于对于特定的项目没有评分，或者很少的人对某个项目进行了评分且这些项目与当前用户相关系数为0，可能使最大覆盖率稍微小于最佳的（99.8%）。精确性：许多度量标准用于评价一个协同过滤系统的精确性，可以分为两大类：基于统计的精确性度量和决策支持准确性度量。基于统计的精确性度量通过比较具有预测和和评分的项目的预测数值和用户评分值来得到。平均绝对误差（MAE）之前被Shardanand &Maes和Sarwar等用于度量预测引擎的表现。其他使用的度量是均方根误差和评分与预测值之间的相似度。上述的度量都是在结果数据上计算，并通常得到相同的结论，因此我们只阐述平均绝对误差。决策支持精确度的度量评估预测结果对用户从项目集中选择高质量项目产生帮助的有效性来评估。它们基于观察来得到，即对大多数用户来说，过滤是一个二向选择。用户要么会，要么不会看这部电影。如果是这种情况，那么对于只看预测值是4以上的推荐电影的用户来说，1.5和2.5的预测值是毫无区别的。我们的决策支持精确度评估使用了ROC敏感度。ROC敏感度是一个对过滤系统拥有判定能力的度量。实际上，它是受试者工作特征曲线（感受型曲线ROC，描绘测试者敏感性和特异性的曲线）下方的面积。敏感性参照一个随机选择的好的项目被过滤器接受的可能性。特异性是一个随机选择的差的项目被过滤器拒绝的可能性。ROC曲线描绘了敏感性（01）和特异性（01），包含一个预测分数阈值超过被接受的电影分数的点集。例如，一个单独的点可能映射到设置过滤器在分数为4的水平，即看任何预测分数大于等于4的电影。曲线下的面积随着过滤器能保留更多好项目并接受更少差项目而增加。作为一个度量来使用，我们必须确定那个项目是好的是坏。我们使用用户自己的评分，考虑“好”的模型为评分是4和5的表示一个信号数据，评分是1、2和3的表示噪音数据，这个模型我们称之为ROC-4。ROC敏感性的数值在01间分布，0.5表示随机，1表示最好。ROC曲线与查全率-错误率曲线（recall-fallout curve）相联系，在文献【24，22】中对这点进行了更深入的扩展解释。4.3实验设计文献展示了从对预测算法组件的经验分析中继承而来的总结。组件测试在图2中与每个组件的变量一起列出来了。对于每一个组件在使用每个变量时的表现结果都进行了度量。除了被度量的组件外，所有其他组件都保持不变，以确保能测试出反映组件之间区别的结果。在每种情况下，对组件的变量的测试是在最佳的表现算法的试验时间上。图2：5、对可能的邻居进行赋权重5.1相似性权重基于邻居的预测算法的第一步是根据与当前用户的的相似性对所有用户进行赋权重。当你从电影或书籍中得到推荐时，你更可能相信来自曾经证明他们是精确推荐提供者给出的推荐。同样的，当自动产生一个推荐时，我们希望通过基于他们的相似度来衡量邻居，以提高一个精确的预测。几种不同的相似性权重度量可以使用。Pearson相关性系数是最通常的权重度量。Pearson相关性度量两个变量间存在的一个线性关系水平。Pearson相关性系数（等式2）是从一个线性回归模型中继承而来，这个模型依赖于一系列假设，即数据，或称为关系必须是线性的，且误差必须是独立且有一个平均值为0的概率分布且对每个独立变量集是常量。当这些模型假设不成立，Pearson相关性就变得不准确。 在协同过滤的数据中，违反这些模型假设的情况是很常见的。Spearman等级相关系数（等式3）类似于Pearson，但不依赖于模型假设，且通过等级之间的相关性来计算度量，而不是通过评分值。在我们的试验中，发现Spearman相关性与Pearson相关性的表现相似。图3展示了两种相关性的结果，实验使用了在“邻居选择”部分讨论过的几种不同的邻居选择机制。值得注意的是，两者之间的结果非常接近。绑定等级的大量数据导致了Spearman相关性准确性的降低（在此每个用户只有5个独立等级）。将来的工作可以决定是否增加等级范围的大小能增加Spearman与Pearson之间准确性的区别。其他的相似性度量包括向量相似性，“cosine”度量，基于熵的不确定性度量和均方差算法。向量相似性度量在信息检索领域很成功19，但Breese发现在协同过滤领域却并不如Pearson相关性表现的好5。基于熵的关联度量16使用传统的概率技术来度量由于知道其他用户评分而导致的当前用户评分的熵的减少量。在我们的测试中，熵没有Pearson相关性表现的好。我们同样发现均方差算法（在Ringo 系统中介绍的）没有Pearson相关性表现的好。5.2重要性权重在之前公布的系统中没有解决的一个问题是放在与邻居的关联性中的信任的数量。在我们的协同过滤系统试验中，发现对于当前用户来说，拥有基于非常少的相互评分项目而产生的高相关性的邻居是很常见的。这些基于小样本（通常有3到5个互评项目）的邻居通常都是糟糕的预测。两个用户间观点需要比较的数据点越多，我们越能相信计算得到的相关性更能代表两个用户之间的真实相关性。我们假定，如果增加一个基于小样本互评项目的能降低相似性权重的重要性权重因素，预测算法的精确性能够提高。在试验中，如果两个用户有少于50个共同评分项目，我们赋给的重要性权重是n/50，n代表互评项目数。如果多于50，那么重要性权重是1。因此，具有少量互评项目的相关性会适当的减少，但有多于50个互评项目的相关性却并不依赖于互评项目数量。图4比较了使用和未使用devaluing term的基于Spearman相关性预测算法的结果。从图中可以看出，使用重要性权重能增加预测算法的精确性。在Pearson相关性中也有类似的结果。5.3variance weighting （方差权重？）所有上面描述的相似性度量都把每个项目平等的看成是一个用户与用户间的相关性。然而，知道一个用户对特定项目的评分在识别用户兴趣上比其他因素更有价值。比如，我们发现大多数用户给“泰坦尼克号”评分很高，那么，知道两个用户对泰坦尼克号评分很高却并不能得出两个用户的共同兴趣。通过对其他电影的评价可以区分用户间的兴趣。电影“sleepless in seattle”可以区分喜欢动作类与浪漫类影片的用户，了解两个用户同时对“sleepless in seattle”感兴趣相比titanic能得到更多关于两个用户共同兴趣的信息。我们假设提供不同的电影对决定相关性有更多的影响，能提高预测算法的准确性。为了达到这个目的，我们修改了Pearson相关性算法以包含一个项目方差权重因素。在评分数据被扩展为Z-score类型（平均值为0，标准差是1）后，Pearson相关性（等式2）能用两个用户评分的协方差代替。这在等式4中进行了表示。（等式4）通过包含进一个方差权重，我们将增加评分中具有高方差的项目的影响力，并降低低方差项目的影响力。包含了方差权重的新的相关性系数如等式5.计算项目的方差权重的等式为：，其中，且分别是所有项目的最小和最大的方差。与原来的假设相反，使用方差权重的相关性对预测算法的精确性没有显著影响。这些结果显示在图表5中。我们通常检测不同的产生项目方差的方法来确定假设是否错误或实验是否完善。一个解释是，我们的方差权重模式没有考虑不同意大众感觉能提供许多信息的观点的用户。6、选择邻居当在数据库中设置好了用户相似性权重后，必须决定哪些其他用户的数据用于计算给当前用户的预测。相对于使用整个用户数据来说，选择一个用户子集（或邻居集）来计算预测在准确性和效率上都是很好的手段21。图6表现了预测项的平均相对误差与邻居集大小之间的关系（邻居集增加，平均相对误差增加）。另外，商业协同过滤系统开始处理百万计的用户，使得考虑每个邻居变得不可行。系统必须选择最佳邻居，丢弃保留的用户。在选择邻居上的，Breese提出的另一个需要考虑的方面是，高相关性（比如相关性系数大于0.5的）比低相关性系数更有价值。两种技术，即相关性阈值和最佳N个邻居，用于决定选择多少个邻居。使用这两种技术，当在设计能给出可接受的覆盖率的算法时，少数有价值的高相关性分布将迷失在许多低相关性的噪音当中。第一个技术，用于Shardanand 和Maes中的，是设定一个绝对相关性阈值，即所有绝对相关性大于给定阈值的邻居才被选中。设置一个高阈值能限定你的邻居保持高的相关性，但是对于大多数用户来说，高相关性不可用，它会产生一个小的邻居集，导致不能对许多项目提供预测覆盖，这在图7中进行了强调。设置一个较低的相关性阈值会导致大量的低相关性邻居，使阈值设置失效。第二个技术是选择最佳的N个相关联人。它没有限制预测覆盖率，理论上的表现是很好的。但是，选择一个更大的N将对高相关性的邻居产生大量的噪音。选择较小的N值将导致给缺乏高相关性的用户产生低质量的预测，尽管在我们的试验中，这种效果没有出现，知道邻居集的大小低于10时。在图6中可以看到上述这些影响效果。图8展现了一个效果最好的邻居选择算法的概览。权重阈值算法使用一个效果最好的高阈值，但失去了许多覆盖率。最佳N邻居算法在不失去覆盖率的前提下提供了很高的效率。将低相似性权重阈值与最佳N邻居算法结合起来，没有使最佳N邻居算法得到很大的改进。我们相信这是由于极端低的相关性（小于0.1）与中等相关性（0.1到0.3）之间的预测值几乎没有差别。7、产生预测一旦邻居已经选择好了，在可能的把这些邻居的评分处理成一个常见分布后，这些评分就能结合起来计算出一个预测。将所有邻居的评分结合成一个预测的基本方法是：使用相关性作为权重，计算评分的加权平均值。基本的加权平均值形成一个假设，即所有的用户评分都有相似的分布。这个被GroupLens使用的方法就是从邻居平均评分中计算邻居评分的均误差，而平均评分是由该邻居评过的所有项目中得到的。平均偏差的方法在方程1中进行了说明。使用这个方法的理由是，用户的评分分布会围绕不同的点，一个用户可能趋向于高的分值，比如好的项目给5分，差的项目给3分，而其他用户可能主要给1分、2分和3分。直观上，如果一个用户不经常的给5分，那么那个用户应该得不到很多为5的预测值，除非这些预测值非常的重要。从所有邻居中计算出的平均值中得到的均误差被转换成当前用户的评分分布（通过把均误差添加到当前用户的评价评分中）。一个对GroupL