推荐系统——第二章：协同过滤推荐

协同过滤推荐方法的主要思想是，利用已有用户群过去的行为或意见预测当前用户最可能喜欢哪些东西或对哪些东西感兴趣。此类型的系统已经在业界广为使用，主要作为在线零售系统对某个顾客需求个性化定制内容的工具，由此可以促销商品和提升销售额。 从研究角度来看，人们探索此类型的系统已经很多年了，它们的优势、性能和局限也都广为人知。这么多年来，人们提出了各种算法和技术，而且在实际环境和人工测试数据上得以成功验证。 纯粹的协同方法的输入数据只有给定的用户—物品评分矩阵，输出数据一般有以下几种类型：(1) 表示当前用户对物品喜欢或不喜欢程度的预测数值；(2) n项推荐物品的列表。当然，这个top-N列表不会包含当前用户已经购买的物品。 2.1　基于用户的最近邻推荐 我们首先讨论的一种早期方法，称为基于用户的最近邻推荐（user-based nearest neighbor recommendation）。其主要思想简述如下：首先，给定一个评分数据集和当前（活跃）用户的ID作为输入，找出与当前用户过去有相似偏好的其他用户，这些用户有时也被称为对等用户或最近邻；然后，对当前用户没有见过的每个产品p，利用其近邻对p的评分计算预测值。这种方法的潜在假设是：(1) 如果用户过去有相似的偏好，那么他们未来也会有相似的偏好；(2) 用户偏好不会随时间而变化。 2.1.1　第一个例子 来看第一个例子。表2-1显示了当前用户Alice和其他用户的评分数据。举例来说，按1～5分评分标准，Alice给“物品1”评“5”分，这说明她非常喜欢这个物品。在这个简单的例子中，推荐系统的任务是确定Alice是否喜欢她从未见过的“物品5”。如果能预测出Alice非常喜欢这个物品，我们将把它列入Alice的推荐列表。为此，我们寻找那些和Alice有着类似偏好的用户，然后用这组用户对“物品5”的评分来预测Alice是否喜欢这个物品。 表2-1　协同推荐的评分数据库 物品1 物品2 物品3 物品4 物品5 Alice 5 3 4 4 ？ 用户1 3 1 2 3 3 用户2 4 3 4 3 5 用户3 3 3 1 5 4 用户4 1 5 5 2 1 在我们更详细地讨论预测所需的数学计算之前，先介绍以下约定和符号。我们用U={ u1,…,un }代表用户集，用P={ p1,…,pm }代表产品（物品）集，用R代表评分项ri,j的n×m评分矩阵，这里 i∈1…n, j∈1…m。分值定义为从1（非常不喜欢）到5（非常喜欢）。如果某个用户i没有为物品j评过分，则对应的矩阵项ri, j为空。 至于如何确定相似用户集，推荐系统中通用的方法是Pearson相关系数 。给定评分矩阵R，用户a和用户b的相似度sim(a,b)可以用公式（2.1）来表示。符号 代表用户a的平均评分。 （2.1） Alice和用户1的相似度计算如下（ = =4， = =2.4）： （2.2） Pearson相关系数取值从+1（强正相关）到1（强负相关）。Alice和其他用户，即用户2、用户3和用户4的相似度分别为0.70、0.00和-0.79。 根据计算，我们注意到用户1和用户2与Alice的历史评分行为比较相似。我们也注意到，Pearson方法考虑到了用户评分标准并不相同这个事实。有些用户倾向于只给高分，而另一些从不给任何物品5分。Pearson相关系数在计算中不考虑平均值的差异使得用户间可比，也就是说，尽管Alice和用户1的绝对评分值完全不同，但仍然可以发现评分值之间相当明显的线性相关性，进而得出二人相似的结论。 这个事实也能从图2-1中看出，图中同时揭示了Alice和用户1的相似性以及Alice和用户4的差异性。 为了预测物品5，我们需要考虑该重视哪些近邻的评分，以及如何评价他们的意见。在本例中，很明显应该将用户1和用户2作为近邻来预测Alice的评分。下面的公式考虑了最相似的N个近邻与用户a平均评分 的偏差，计算用户a对物品p的预测值： （2.3） 图2-1　比较Alice和其他两个用户 在这个例子中，基于近邻用户1和用户2的评分预测Alice对物品5的评分为： （2.4） 根据这些计算方法，我们现在可以计算出Alice对所有未曾见过物品的预测评分，其中包括推荐列表中有最高预测值的那些物品。在本例中，把物品5放到列表中可能是一个很好的选择。 上面的示例当然只是实际环境的理想化。在实际应用中，评分数据集通常非常大，而且包含了成千上万甚至百万量级的用户和物品，这要求我们必须考虑计算复杂度。此外，评分矩阵通常非常稀疏，每个用户只对所有有效物品非常小的一个子集评分。最后，我们给新用户推荐什么，该如何处理没有评分的新物品，这些问题都还不是很清楚。我们会在后面的章节讨论这方面的问题。 2.1.2　更好的相似度和赋权体系 我们在示例中用到Pearson相关系数衡量用户间的相似度。根据文献资料来看，改进余弦相似度（后面会详细讨论）、Spearman秩相关系数或均方差等其他方法也能用于计算用户间的接近程度。然而实验分析显示，对于基于用户的推荐系统（至少在研究最充分的推荐领域）来说，Pearson相关系数比其他对比用户的方法更胜一筹（Herlocker et al.1999）。不过对于后来发现的基于物品的推荐技术，余弦相似度方法比Pearson相关度量表现更好。 尽管如此，单独使用“纯粹”的Pearson方法来发现近邻以及为这些近邻的评分赋权可能还不是最好的选择。试想一下，很多领域会存在一些所有人都喜爱的物品，让两个用户对有争议的物品达成共识会比对广受欢迎的物品达成共识更有价值，但Pearson这样的相似度方法无法将这种情况考虑在内。为了解决这个问题，Breese et al.(1998)提出对物品的评分进行变换，降低对广受欢迎物品有同样看法的相对重要性。类似于信息检索领域提出的最初概念 ，人们称这个变量为反用户频率（iuf）。Herlocker et al.(1999)通过方差权重因子解决了同样的问题，该方法提高了具有高方差评分值物品，也就是指有争议的物品的作用。 我们在示例中用到的基本相似度方法没有考虑到两位用户是否仅同时给很少的物品评分（他们可能只是碰巧意见相同），或者他们是否对很多物品都意见一致。事实上，基于近邻评分的预测方法在遇到当前用户只为非常少的共同物品评分时会出错，导致不准的预测（Herlocker et al.1999）。Herlocker et al.(1999)因此提出使用另外一种赋权因子，即重要性赋权。尽管Herlocker et al.(1999, 2002)在实验里用到的赋权方案仅是一种基于线性化简相似度权值的简单方法，但在共同评分物品少于50个的时候预测准确率的提升非常显著。然而，这个问题依然有待解决，比如，赋权方案和启发式决定阈值在现实情况中是否有效；评分数据集更小时，我们不能期望找到很多有50个共同评分物品的用户。 最后，另外一种通过精细调整预测权重来提高推荐准确度的方法是样本扩展（Breese et al.1998）。样本扩展指的是强调那些接近+1和1的值，对原始数值乘以一个常量ρ来调整近邻的权值。Breese et al.(1998)在实验中设置ρ为2.5。 2.1.3　选择近邻 在示例中，我们直观上认为不必考虑所有近邻（近邻选择）。为了计算预测值，我们只包括了那些与当前用户有正向关联的用户（当然，也是为我们将要预测物品评过分的用户）。如果我们包括邻近的所有用户，这不仅会对计算时间带来负面影响，而且还会对推荐准确度造成影响，因为那些实际上不可比的用户评分也会加入计算。 降低近邻集合规模的通常方法是为用户相似度定义一个具体的最小阈值，或者将规模大小限制为一个固定值，而且只考虑k个最近邻。Anand and Mobasher(2005)及Herlocker et al.(1999)讨论过这两种方法的潜在问题：如果相似度阈值过高，近邻规模就会很小，这就意味着很多物品没法预测（降低覆盖率）。相反，如果阈值太低，近邻规模就不会显著降低。 k值（近邻规模）的选择不会影响可预测物品的覆盖率。然而这并未解决如何发现一个好k值的问题：当近邻个数k太高，太多只有有限相似度的近邻会给预测带来额外的“噪声”；当k太小（比如在Herlocker et al.(1999)的实验中小于10），预测质量也可能受到负面影响。对MovieLens数据集的分析发现，“在大多数实际情况下，20到50个近邻似乎比较合理”（Herlocker et al. 2002）。 在Herlocker et al. (2002)中可以找到使用不同赋权和相似度方案以及不同近邻规模的详细分析。 2.2　基于物品的最近邻推荐 尽管基于用户的协同过滤方法已经成功应用在了不同领域，但在一些有着数以百万计用户和物品的大型电子商务网站上还是会存在很多严峻挑战。尤其是当需要扫描大量潜在近邻时，这种方法很难做到实时计算预测值。因此，大型电子商务网站经常采用一种不同的技术：基于物品的推荐。这种推荐非常适合做线下预处理 ，因此在评分矩阵非常大的情况下也能做到实时计算推荐（Sarwar et al. 2001）。 基于物品算法的主要思想是利用物品间相似度，而不是用户间相似度来计算预测值。让我们再观察一下评分数据集，并预测Alice对物品5的评分。首先，比较其他物品的评分向量，寻找与物品5有相似评分的物品。在本例中，我们发现物品5的评分（3, 5, 4, 1）与物品1的评分（3, 4, 3, 1）很相似，与物品4（3, 3, 5, 2）部分相似。基于物品推荐的方法就是简单地找到Alice对这些相似物品的评分。Alice给物品1评5分，给物品4评4分，基于物品的推荐算法会按权重计算这些评分的平均值，从而预测物品5的评分会在4和5之间。 2.2.1　余弦相似度度量 为了找到相似物品，需要定义一种相似度度量标准。在基于物品的推荐方法中，余弦相似度由于效果精确，已经被证实是一种标准的度量体系。这种度量标准用两个n维向量之间的夹角来测算相似度。这种方法也被广泛用于信息检索和文本挖掘，用来比较两份文本文档，其中文档可以表示为词语的向量。 将两个物品a和b用对应的评分向量 和 来表示，其相似度可以定义如下： （2.5） 符号•表示向量间的点积， 表示向量的欧式长度，即向量自身点积的平方根。 物品5和物品1的余弦相似度因此可以计算为： （2.6） 相似度值介于0和1之间，越接近1则表示越相似。基本的余弦方法不会考虑用户评分平均值之间的差异。改进版的余弦方法能够解决这个问题，做法是在评分值中减去平均值。相应地，改进余弦方法的取值在1到+1之间，就像Pearson方法一样。 设U为所有同时给物品a和b评分的用户集，改进的余弦相似度计算如下： （2.7） 我们因此可以对原始的评分数据集进行变换，用评分值相对于平均评分值的偏差取代原始值，如表2-2所示。 表2-2　均值调整评分数据库 物品1 物品2 物品3 物品4 物品5 Alice 1.00 1.00 0.00 0.00 ？ 用户1 0.60 1.40 0.40 0.60 0.60 （续） 物品1 物品2 物品3 物品4 物品5 用户2 0.20 0.80 0.20 0.80 1.20 用户3 0.20 0.20 2.20 2.80 0.80 用户4 1.80 2.20 2.20 0.80 1.80 物品5和物品1的改进余弦相似度值为： （2.8） 确定物品间的相似度之后，我们可以通过计算Alice对所有与物品5相似物品的加权评分总和来预测Alice对物品5的评分。形式上，我们预测用户u对物品p的评分为： （2.9） 就像在基于用户的方法中，近邻集合的规模也会受限于一个固定值。也就是说，不是所有的近邻都会拿来做预测。 2.2.2　基于物品过滤的数据预处理 Amazon.com采用物品间协同过滤技术向消费者推荐书和CD。Linden et al. (2003) 介绍了2003年Amazon的在线商店如何在2900万用户和数以百万计的物品上应用这种技术。传统基于用户协同过滤的主要问题是，算法不能很好地适应大规模用户和物品数据。给定M个用户和N个物品，在最坏的情况下，必须评估最多包含这N个物品的所有M 个用户的记录。Linden et al. (2003) 证明在实际情况下，由于大多数用户只评分或购买了非常少量的物品，实际复杂度非常低。尽管如此，当用户的数量M达到几百万，线上环境要求必须在极短的时间内返回结果时，实时计算预测值仍然不可行。 为了在不牺牲推荐精准度的情况下在大规模电子商务网站上应用基于物品的推荐算法，人们通常选择离线预计算数据。其想法是事先构建一个物品相似度矩阵，描述所有物品两两之间的相似度。在运行时，通过确定与p最相似的物品并计算u对这些邻近物品评分的加权总和来得到用户u对物品p的预测评分。近邻数量受限于当前用户评过分的物品个数。由于这样的物品数量一般都比较少，因此计算预测值可以在线上交互应用允许的短时间内完成。 考虑到内存要求，N个物品的相似度矩阵理论上会有N2项。但实际上项数会极低，而且还可以采取进一步的方法降低复杂度。可选的方案有，仅考虑那些与其他物品同时评分数最少的物品，或者对每个物品只记录有限的近邻。然而这种方法会增加无法预测某个特定物品的风险（Sarwar et al.2001）。 原则上，这种离线预计算近邻的方法对基于用户的方法也适用。但在实际情况下，两个用户评分重叠的情况非常少见，这就意味着一些其他的评分值可能影响到用户间的相似度。相对用户相似度而言，物品相似度更稳定，这种预处理计算不会过于影响预测准确度（Sarwar et al.2001）。 除了这些所谓基于模型的方法中采用的不同预处理计算之外，还可以仅利用评分矩阵中的某一部分以降低计算复杂度。一种基本技术是二次采样，这种技术可以随机选取数据的子集，或者忽略那些仅有非常少量评分或仅包含非常热门物品的用户记录。Yu et al.(2003)也提出过一种更加高级且基于信息论的技术用于过滤最“相关”用户。一般来说，可以用这些技术加速计算，但由于推荐用到的信息少了，系统做出精确预测的能力可能会下降。 更多基于模型和基于预处理方法以减少复杂度和维度的内容会在2.4节讨论。 2.3　关于评分 在进一步讨论降低计算复杂度的技术并介绍纯粹基于用户—物品评分矩阵的其他算法之前，我们大致讲一下协同过滤推荐的评分方法。 2.3.1　隐式和显式评分 在所有可供选择的收集用户观点的方法中，直接询问物品的评分可能是最准确的。通常情况下使用的是五分制或七分制的Likert反馈量表，覆盖了从“非常不喜欢”到“非常喜欢”。评分经过内部变换成数字值后，就可以应用先前提到的相似度方法。Cosley et al.(2003) 讨论了使用不同评分尺度的效果，比如，当必须使用不同尺度时，用户的评分行为会如何变化；当评分粒度增加时，推荐质量如何变化。评价电影的五分制可能使得用户选择太少，而十分制更容易被接受。Goldberg et al.(2001) 讨论了在笑话推荐中选择了一种更精细的尺度，使用了从10到+10的连续尺度，并且采取了图形化输入。采用这种方法不会像离散化那样丢失精确性，可以用更精细的粒度刻画用户的偏好，最终用户确实“喜欢”这种图形化交互方法，能够从视觉上“做出直观反应”并给出评分。 推荐精准度会受到怎样的影响？标度系统分级的“最优”值是多少？Cosley et al. (2003) 仅在少量用户库和单个领域得出了结论，这些问题依然有待讨论。 显式评分的主要问题在于需要推荐系统的用户额外付出，而用户很可能由于看不到好处而不愿意提供这些评分。因此，可用的评分会很少，从而导致推荐质量不高。 尽管如此，Shafer et al.(2006)证明收集显式评分并不像人们想象的那么困难，这是因为系统开始运行阶段只需要一小批“早期培育者”提供许多物品的评分就足够了。 除此之外，特别是近几年来可以观察到，随着Web 2.0的出现，在线社区的角色发生了变化，用户越来越愿意主动贡献社区知识。尽管如此，根据最新进展的趋势，还是需要进一步研究开发新的技术和方法，说服在线用户提供更多的评分。 集成了推荐系统的网店或应用程序可以收集隐式评分。比如当用户买了一个物品，很多推荐系统会将这个行为解释为正向评分，系统也会跟踪用户的浏览行为。如果用户访问一篇网页上商品的详细信息并且停留了较长一段时间，推荐系统就会将这个行为解释为针对物品的正向意图。 尽管可以持续地收集隐式评分，而且也不需要用户额外付出，但还是难以确定用户行为是否被正确解释。用户可能不喜欢自己已买的所有书，比如为其他人买的书。尽管如此，如果得到了足够多的评分数据，这些特例还是可以通过大量得到正确解释的例子加以排除。实际上，Shafer et al.(2006)发现，在某些领域（比如个性化在线电台）收集到的隐式反馈甚至比显式评分更能得到精确的用户模型。 Nichols(1998)中可以找到更多关于隐式评分代价和收益的讨论。 2.3.2　数据稀疏和冷启动问题 在前面例子用到的评分矩阵中，只有一个用户物品组合没有评分。但在实际应用中，由于用户一般只会评价（或购买）少部分物品，评分矩阵一般都非常稀疏。 这种情况下的挑战是用相对较少的有效评分得到准确的预测。直接做法就是利用用户的附加信息，比如性别、年龄、教育程度、兴趣等能够帮助分类用户的信息。因此，相似用户（近邻）集合不只是根据显式或隐式评分，也会根据评分矩阵的外部信息来分析。这些系统（Pazzani(1999b)提到的混合系统）利用了人口统计信息以及已经不再“纯粹”的协同方法。这种方法也引出了新问题，比如如何获取额外信息以及如何混合不同的分类器。尽管如此，在刚上线推荐服务的扩张阶段，这种技术对于获取协同方法所需的大量关键用户还是有帮助的。 多年以来，人们提出过一些处理冷启动和数据稀疏问题的方法。我们在这里要详细讨论的例子是Huang et al.(2004)提出的基于图的方法。其主要思想是利用假定用户品味的“传递性”，并由此增强额外信息矩阵。 考虑图2-2中的用户—物品关系，它由表2-3的二进制评分矩阵（摘自Huang et al.(2004)）推导出。 图2-2　用户— 物品关系 在矩阵中，0不是一个显式的（差评）评分，而是一个缺失的评分。假设我们正在为用户1寻找推荐。根据标准的CF方法，用户2会被认为是用户1的同伴，因为他们都买了物品2和物品4。物品3会被推荐给用户1，因为最近邻用户2也买了或喜欢它。Huang et al.(2004)将这种推荐问题看做图分析问题，推荐由用户和物品间的路径决定。在标准的基于用户或基于物品的CF方法中会考虑长度为3的路径，即物品3和用户1相关是因为他们之间存在一条3步路径（用户1—物品2—用户2—物品3）。由于这种长度为3的路径数量在稀疏评分数据中很少，因此这种思路也会考虑更长的路径（间接关联）计算推荐。比如，由于存在两条连接用户1和物品1的5步路径，利用长度为5的路径也可以推荐物品1。 表2-3　扩展激活方法的评分数据库 物品1 物品2 物品3 物品4 用户1 0 1 0 1 用户2 0 1 1 1 用户3 1 0 1 0 由于这些远距离关系的计算代价很高，Huang et al.(2004)提出将评分矩阵转化为用户和物品的双向图，并使用一种称为扩展激活的特殊图搜索方法高效地分析图。对比标准的基于用户和基于物品的算法显示，基于间接关系的技术能显著地提高推荐质量，尤其是在评分矩阵稀疏的时候。同样，相比标准的协同过滤技术，该算法对新用户的推荐也能有明显的提升。然而当评分矩阵达到某种密度之后，相比标准算法的推荐质量也会有所下降。尽管如此，距离关系的计算代价仍然很高，现在还无法实际应用在大规模评分数据上。 缺省投票是Breese et al.(1998)描述的另外一种用来处理稀疏评分数据的技术。回想一下，标准的相似度方法只考虑那些当前用户和用来比较的用户都评过分的物品。当数量很少时，评分碰巧相同或不同都会对相似度计算影响很大。因此这种思路就是给那些只有一两个用户评过分的物品赋以缺省值（可能也会对一些附加的物品），这样可以提高稀疏评分数据上的预测质量（Breese et al.1998）。这些人工缺省投票就像一种缓冲机制，能够减少那些个别巧合因素对相似度的影响。 近来，Wang et al.(2006)还提出过其他解决数据稀疏问题的方法。由于发现大多数协同推荐只用到评分数据中的某部分特定信息（用户相似度或物品相似度），因此研究人员建议将这两种不同类型的相似度组合起来提高预测准确率。此外，他们还在预测函数里利用了先前方法没有考虑到的第三种信息，即相似用户给出的相似的物品评分。通过一种概率机制将来自不同数据源的不同预测进行“融合”和平滑，其中第一组实验显示预测准确率得到提高，尤其是在处理稀疏评分数据时。 冷启动问题是稀疏问题的一个特例（Huang et al.2004）。此类问题包括：(1) 如何向还没给任何物品评分的新用户推荐；(2) 如何处理从未被评过分或购买过的物品。这两类问题都可以通过混合方法来解决，即利用额外的外部信息（Adomavicius and Tuzhilin 2005）。对于新用户问题，其他策略也可能奏效。一种方法是在推荐之前要求用户给出最低限度数量的评分。在这种情况下，系统需要能够从信息论角度智能地获取具有最多信息量的物品评分（Rashid et al.2002）。Goldberg et al.(2001)提出的Eigentaste算法要求用户提供标准集合的评分也是一种类似的策略。 2.4　更多基于模型和预处理的方法 协同推荐技术一般分为两类：基于记忆的和基于模型的。传统的基于用户技术是基于记忆的，这是因为原始评分数据保存在内存中，直接生成推荐结果。而基于模型的方法会首先离线处理原始数据，就像基于物品的过滤和某些降维技术。运行时，只需要预计算或“学习过”的模型就能预测。尽管基于记忆的方法能获得全部数据，在理论上推荐精准度更高，但也会遇到数以百万计用户和物品带来的扩展性问题。 下节我们会讨论更多基于模型的推荐技术，最后讲述一个最新的实用方法。 2.4.1　矩阵因子分解 2009年结束的Nexflix竞赛 表明，很多参赛团队用到的高等矩阵因子分解方法对提高推荐系统的预测准确率非常有帮助。 简单来说，推荐系统使用矩阵因子分解方法从评分模式抽取出一组潜在的（隐藏的）因子，并通过这些因子向量描述用户和物品。在电影领域，这些自动识别的因子可能对应一部电影的常见标签，比如风格或类型（戏剧片或动作片），也可能是无法解释的。当当前用户和物品i在这些因子上相似时会推荐物品i（Koren et al.2009）。 20世纪80年代后期，利用潜在“语义”因子的思想被成功地应用于信息检索领域。Deerwester et al.(1990)提出使用奇异值分解（SVD）方法发现文档中的潜在因子；在信息检索方面，这种潜在语义分析（LSA）技术也被归为潜在语义索引（LSI）。 信息检索领域的问题通常是根据用户的查询词找到一组文档。文档和用户查询词都被解析为词语的向量，这在第3章会详细介绍。简单的检索方法可能只会测量文档与查询词之间在词语上的重复度。然而这种检索方法无法解决文档或查询词中有同义词（比如car和automobile）或者多义词（比如chip或model）的问题。SVD将高度相关且一起出现的词语作为单独因子，把通常很大的文档向量矩阵拆解成更小阶的近似矩阵。这样，基于LSI的检索甚至能够在不包含用户查询词中（很多）词语的情况下检索出相关文档。 像SVD或主成分分析这类利用数据中的潜在关系和矩阵因子分解技术很快都引入了推荐系统（Sarwar et al.2000b; Goldberg et al.2001; Canny 2002b）。下面我们会举个SVD如何用于推荐的例子。这个例子改编自Grigorik(2007)介绍的基于SVD推荐系统。 基于SVD推荐系统的例子。再看一下表2-1的评分矩阵，经过删除Alice项、变换矩阵后，我们可以更清晰地演示不同运算（见表2-4）。 表2-4　基于SVD推荐的评分数据库 用户1 用户2 用户3 用户4 物品1 3 4 3 1 物品2 1 3 2 6 物品3 2 4 1 5 物品4 3 3 5 2 SVD的原理（Golub and Kahan 1965）可以通俗地表述为：将给定矩阵M分解成3个矩阵的乘积，其中U和V分别称为左、右奇异向量，Σ对角线上的值称为奇异值。 （2.10） 因为表2-4中4×4矩阵M是二次的，所以U、Σ和V也都是二次4×4矩阵。而仅观察有最大奇异值的最重要特征就可以近似表示整个矩阵。在本例中，计算U、V和Σ（用到一些线形几何软件）后，只保留U和 的前两列作为两个最重要的特征（见表2-5）。 表2-5　分解矩阵的前两列和奇异值Σ U2 V2 Σ2 0.4312452 0.4931501 0.3593326 0.36767659 12.2215 0 0.5327375 0.5305257 0.5675075 0.08799758 0 4.9282 0.5237456 0.4052007 0.4428526 0.56862492 0.5058743 0.5578152 0.5938829 0.73057242 图2-3显示了U和 在二维空间（ , ）的映射。矩阵V对应用户，矩阵U对应物品。尽管在这个特殊例子中观察不到用户的任何群组，但可以看到U中物品形成了两组（x轴的上方和下方）。分析原始评分可以观察到物品1和物品4有一些相似的评分。x轴下方的物品2和物品3也是如此。在用户方面，我们至少发现用户4离其他人更远一些。 图2-3　在二维空间上基于SVD的映射 由于目标是预测Alice的评分，我们必须首先找出Alice在这个二维空间中可能的位置。 为了得出Alice的数据点，将Alice的评分向量[5, 3, 4, 4]乘以U的两列子集和两列奇异值矩阵Σ的逆。 （2.11） 给定Alice的数据点，可以有不同策略为她推荐。一种方法是寻找压缩后两维空间的近邻用户，用他们的物品评分预测Alice的评分。如果我们用余弦相似度计算用户相似度，用户1和用户2会是本例中最好的预测依据。而且，不同的权重方案、相似度阈值以及填充缺失物品评分的策略（例如基于物品平均评分）都可用于改进预测结果。在压缩空间中搜寻近邻只是预测Alice的一种可能方法。除此之外，潜在因子空间中用户和物品的相互关系（可以由余弦相似度方法度量），也可以用于近似计算Alice对物品的评分（Koren et al. 2009）。 主成分分析——Eigentaste。Goldberg et al.(2001)提出一种不同的降维方法，最初应用在笑话推荐系统。其思想是用主成分分析（PCA）对评分数据预处理，过滤得出数据中“最重要”的方面，以解释大多数变量。作者称这种方法为“Eigentaste”，因为PCA是基于矩阵特征值分解计算的标准统计分析方法。经过PCA处理后，原始评分数据被投射到最相关的主特征向量上。然后，在约简后的数据集上，用户被归类到某个近邻聚类后计算物品的平均评分值。所有这些计算密集型的操作都在线下完成。运行时，要求新用户对一组笑话（标准集合）进行数值评分。这些评分值经过主成分变化后得到正确的聚类。通过查找预处理数据，可以很简单地查询出聚类中评分最高的物品。这样，运行时的计算复杂度是与用户数量无关的“常量时间”算法。通过实验评估和比较发现，在某些实验中，Eigentaste与简单最邻近算法相比能提供大致相当的推荐精准度，同时显著降低计算时间。在某些领域，比如在10个等级的参数要求下，标准集合可能会限制这种方法的广泛应用。 讨论。Sarwar et al.(2000a)分析了基于SVD的降维如何影响推荐质量。实验中有一些有趣的发现。在某些情况下，预测质量会比基于记忆的预测技术差，这可以解释为没有考虑到所有可用信息。另外，某些设置下推荐精准度会更好，这是因为降维技术也会过滤掉一些数据中的“噪声”，甚至能检测出数据中有价值的联系。在很大程度上，推荐质量取决于正确选择约简数据的数量，也就是说，如何选择SVD方法中保留奇异值的数量。很多情况中，这些参数只能基于某个领域内的实验来确定和精调。Koren et al.(2009)讨论过从评分模式中提取出的20至100个因素。 所有的预处理方法都必须解决数据更新问题：如何整合新的评分而不用重新计算整个“模型”。Sarwar et al.(2002) 提出一种基于SVD方法允许增量更新的技术。类似地，George and Merugu (2005)提出一种基于联合聚类方法，可以构建可扩展的协同过滤推荐系统，也支持评分数据库的动态更新。 随着推荐系统早期实验中矩阵因数分解技术的发展，人们提出了一些更复杂和专业的方法。例如，Hofmann（2004；Hofmann and Puzicha 1999）提出应用概率潜在语义分析（pLSA）发现用户社区和评分数据里隐藏的兴趣模式，基于这种方法可以达到很好的准确度级别。Hofmann的pLSA方法和LSA在识别隐藏关系这个目标上很相似，然而pLSA的基础不是线性代数而是统计数据，代表着“在统计上有更坚实基础的主流方法”（Hofmann 1999）。 有关推荐系统中矩阵因数分解的最新高级主题的概述可以在Koren et al.(2009)里找到。其中，Koren et al.重点关注模型的灵活性，例如，如何整合附加信息，比如人口统计数据；如何处理时效性问题，比如改变用户偏好；如何考虑评分偏向性。此外，他们还提出了处理缺失评分数据的更加精细的方法，并公布了在Netflix大赛上应用这些技术的一些见解。 2.4.2　关联规则挖掘 关联规则挖掘是一种在大规模交易中识别类似规则关系模式的通用技术。这种技术的典型应用是从超市里经常同时购买的商品中发掘成对或成组的商品。一个典型的规则是“如果用户买了婴儿食品，那他/她买尿布的可能性会是70%”。知道了这种关系，就可以利用这一知识进行推销和交叉销售，也可以用来设计商店的布局。 这种想法也可以移植到协同推荐，换句话说，目标将变成自动发现规则，比如“如果用户X喜欢物品1和物品2，那么他很可能也喜欢物品5”。通过判断该用哪条挖掘出的规则（在本例中，就是检查用户是否喜欢物品1和物品2），就能为活跃用户进行推荐，而且可以根据交易中同时出现物品的统计数据产生推荐物品的排序列表。 下面我们可以用Sarwar et al.(2000b)定义的符号更为正式地描述这一通用问题。交易T是所有有效产品集合P={p1,…,pm}的子集，表示被一起购买的产品集合。关联规则经常写作XY这种形式，X和Y都是P的子集，且X∩Y=。关联规则XY（例如，婴儿食品尿布）表示只要交易T包含X里的元素（规则体），Y里的元素（规则头）就非常有可能也是相同交易的元素。 规则挖掘算法，比如Apriori（Agrawal and Srikant 1994），其目标是自动发现这样的规则，并计算这些规则的质量。关联规则的衡量标准是支持度和可信度。规则XY的支持度可以计算为包含X∪Y所有商品的交易量相对所有交易量的比例（也就是X和Y同时出现在一次交易的概率）。可信度定义为包含X∪Y所有物品的交易量相对仅包含X的交易量的比值，也就是说可信度对应给定X时Y的条件概率。 更为正式的公式如下： （2.12） （2.13） 我们再看一下如何使用规则挖掘方法对上节所示评分矩阵进行推荐。为了演示方便，我们将五分制评分简化为“喜欢/不喜欢”的二值选择。表2-6显示了对应的评分矩阵：0对应“不喜欢”，1对应“喜欢”。这个矩阵根据表2-2（显示平均化后的评分）得出，如果评分大于平均值则为1，反之为0。 标准规则挖掘算法会分析这个数据，计算出关联规则列表及对应的可信度和支持度。为了只关注相关的规则，支持度和可信度的最低阈值一般需要根据实验确定。 表2-6　规则挖掘的变换评分数据 物品1 物品2 物品3 物品4 物品5 Alice 1 0 0 0 ？ 用户1 1 0 0 1 1 用户2 1 0 1 0 1 用户3 0 0 0 1 1 用户4 0 1 1 0 0 在协同推荐环境中，所有先前的（正向）评分集合或用户的购买行为都可以看做是一次交易。要分析的典型关联是，喜欢物品1的用户也喜欢物品5（物品1物品5）的可能性有多大。在示例数据中，这条规则（不考虑Alice的评分）的支持度是2/4，可信度是2/2。 线下可以计算足够高可信度和支持度的关联规则集合。运行时，根据Sarwar et al.(2000b)中描述的方案就能够高效计算出用户Alice的推荐。 (1) 确定与Alice相关的关联规则XY的集合，即Alice买过（或喜欢）X中的所有元素。因为Alice买了物品1，那么上述规则就与Alice相关。 (2) 计算这些规则的Y集合中没有被Alice购买的物品集合。 (3) 对这些物品根据规则的可信度排序。如果多条规则都推荐一个物品，则取可信度最高的那条规则。 (4) 返回排序列表最前的N个元素作为推荐。 在Sarwar et al.(2000b)描述的方法中只考虑实际购买（“喜欢”评分），并不显式处理“不喜欢”的情况，因此会无法推导出规则。比如，只要用户喜欢物品2就不会喜欢物品3，在我们的例子中却是一个似是而非的规则。 幸运的是，关联规则挖掘很容易就能扩展处理类别属性，因此“喜欢”和“不喜欢”的规则都可以从数据中得出。Lin et al.(2002; Lin 2000)提出将一般的数值型物品评分转换成两类，如示例中显示的那样，然后将评分映射到标准关联规则挖掘技术所谓的“交易”中。挖掘出描述物品之间关系的规则，比如每当用户喜欢物品2……，只是众多选项中的一种；同样的机制还可以用于发现用户间喜欢或不喜欢的关系，比如“90%被用户A和用户B喜欢的物品也被用户C喜欢”。 为了发现推荐规则，Lin et al.(2002)提出一种挖掘算法，利用领域特性专门搜寻规则头中包含某种目标物品（用户或物品）的规则。这种搜寻规则的方法不仅能提高算法的效率，而且能够发现很少购买物品的规则，这些物品可能会因为有限的支持度在全局搜索时被过滤掉。此外，算法还能设置下限和上限约束参数，调整要识别的规则个数。 根据数据挖掘的场景，可以采用不同的策略来决定要推荐的物品集合。假设一个场景是要挖掘用户间关联而不是物品间关联，要发现的规则可能是：“如果用户1喜欢一个物品，用户2不喜欢这个物品，那么Alice（目标用户）会喜欢这个物品。” 为了确定一个物品是否被Alice喜欢，我们会对每个物品检查这一规则（也就是说如果用户1喜欢它，用户2不喜欢它）是否会“激发”这个商品。基于这些规则的可信度和支持度，可以为每个物品计算出一个整体评分如公式（2.14）所示（Lin et al. 2002）： （2.14） 如果这个物品的整体评分超过预定义阈值，物品就会被推荐给目标用户。Lin et al.(2002)根据实验制定出了一个合适的阈值。 当使用物品关联规则时，可以事先定义一个截止参数描述某个最小支持度。这个截止参数不仅可以降低计算复杂度，而且可以发现只有很少评分的物品对应的规则。 Lin et al.(2002)公布的实验实现了一种混合策略，其默认设置是不仅会依靠用户关联，也会在用户关联的支持度低于定义的阈值时转而依靠物品关联。评估显示用户关联一般会比物品关联得到更好的结果，但物品关联计算得更快。可以从实验中观察到有限数量的规则足够产生很好的预测，再增加更多的规则并不能提高预测精准度。第一个观察非常有趣，因为这与之前描述的最近邻方法中的观察相反：该观察认为物品—物品的关联方法效果更好一些。 在热门电影领域，最终的对比评估显示，规则挖掘方法比其他算法在推荐质量上效果更好，比如Billsus and Pazzani(1998a) 提出的算法。在另一个领域，也就是为Web用户推荐感兴趣的网页，Fu et al.(2000)也发现使用关联规则方法预测单个页面相关性的效果不错。相比很多其他方法，它们不依赖Web页面的显式用户评分，而是在一个中央存储器中自动记录许多用户的浏览行为，然后学习哪些用户在兴趣上是相似的。该方向最近的一些研究，比如Mobasher et al(2001)或Shyu et al.(2005)，也会依赖Web访问数据和关联规则挖掘作为核心方法，在自适应用户交互界面和Web页面推荐功能中预测Web页面相关性。 2.4.3　基于概率分析的推荐方法 另外一种预测用户会对某个物品评分的方法是利用概率论已有的形式体系 。 用概率方法实现协同过滤，最初非常简单的方法是将预测问题看做分类问题，这通常可以描述为“将一个对象分配给几个事先定义好的类别”的任务（Tan et al. 2006）。举个分类问题的例子，将收到的邮件分成垃圾邮件和非垃圾邮件两类。为了自动完成这个任务，需要构造函数判断邮件是垃圾邮件还是非垃圾邮件，一般会根据出现在邮件头或内容中的词语来判断。因此分类任务也可以被看成是从训练示例中学习映射函数的问题。这种函数一般被称为分类模型。 贝叶斯分类器是数据挖掘领域用到的一种标准技术。我们用一个简化的例子演示基本概率方法是如何用来计算评分预测值。考虑一个略有不同的评分数据（见表2-7），我们仍关注Alice对物品5的评分。 给定Alice其他评分和其他用户评分情况下，我们将预测任务描述成计算物品5最可能评分值的问题。我们会计算给定Alice其他评分时每个可能评分值的条件概率，然后选择一个最大概率值的评分作为预测值 。 表2-7　概率模型：评分数据 物品1 物品2 物品3 物品4 物品5 Alice 1 3 3 2 ？ 用户1 2 4 2 2 4 用户2 1 3 3 5 1 用户3 4 5 2 3 3 用户4 1 1 5 2 1 为了预测物品5的评分为1时的概率，我们必须计算条件概率P（物品5=1|X），X是Alice的其他评分：X=（物品1=1，物品2=3，物品3=3，物品4=2）。 计算这个概率值用到了贝叶斯理论，该理论允许我们通过类条件概率P（X|Y）、概率Y（即本例中物品5的评分为1时的概率）和概率X一起计算后验概率P（Y|X）。更正式化的公式为： （2.15） 假设这些属性（比如评分用户）之间条件独立，我们可以用朴素贝叶斯分类器计算出每个值Y的后验概率。其公式如下，d是每个X的属性个数： （2.16） 在朴素贝叶斯分类器应用的很多领域里，条件独立的假设并不成立，尽管如此这类分类器仍有很好效果。 由于P(X)为常量，我们可以在计算中忽略这项。根据评分数据可以为每个评分值估算出P(Y)：P(物品5=1)=2/4（物品5的4个评分值有2个是1），P(物品5=2)=0，等等。剩下就是计算所有的条件分类概率P（Xi|Y）： 基于这些计算，给定P(物品5=1)=2/4，并忽略贝叶斯分类器的常量P(X)，物品5的评分值为1的后验概率是P(物品5=1|X)=2/4×0.125=0.0625。在评分数据的例子中，P(物品5=1)比其他概率都要高，这说明Alice最有可能给物品5评分为1。从这个小例子中可以看到，使用这种简单方法会在一项因数为0时估值的后验概率为0，而且在最坏情况下没法对评分向量分类。因此会采用m估值或Laplace平滑技术来平滑条件概率，尤其是对稀疏训练集。当然，也可以像关联规则挖掘方法那样，使用预处理评分数据，以及使用“喜欢”和“不喜欢”来评分或只给缺失值赋以缺省评分。 用于演示的简单方法的计算复杂度很高，在小规模和稀疏评分数据上效果不佳，最终会导致每个评分的概率值彼此之间相差很小，因此需要引入更高级的概率方法。 依赖概率模型最常用方法基于的思想是将相似的用户（或物品）组成聚类，这种技术也会有助于解决数据稀疏性和计算复杂度问题。 Breese et al. (1998)描述的朴素贝叶斯模型额外引入了一个无法观察到的类别变量C，包括少量离散值，分别对应用户库的不同聚类。当假设条件独立成立，下面的公式表示概率模型（混合模型）： （2.17） 其中P（C=c，v1,…,vn）表示对类别c的单个用户能观察到全部评分值的概率。必须从训练数据中提取的是属于类别c成员的概率P（C=c）和当类别已知时观察到某个评分值的条件概率P（vi|C=c）。剩下要确定的问题是模型的参数和估计合适的聚类个数。这些信息并不直接包含在评分数据中，但幸运的是，该领域的标准技术可以确定模型参数，比如期望最大值算法（Dempster et al.1977）。 运行时，根据用户u落入某个聚类的概率和给定用户评分情况下喜欢属于某个聚类的物品i的概率，可以对特定用户u和物品i进行预测。参考Ungar and Foster(1998)可以获得用于协同过滤的聚类概率方法的更多模型评估细节。 其他聚类方法也可以用于推荐领域来降低复杂度问题。Chee et al.(2001)提出利用一种修改后的k-means聚类算法将一组用户区分成同质或聚合的群。这样，在同一群内用户相似度很高，不同分区之间的相似度保持在较低级别。当运行中需要为用户做评分预测时，系统先决定用户的分组，然后只利用分组内一小部分集合成员的评分计算有权重的评分值。这种算法的性能依赖于分组的个数和各个分组的大小。小的分组有利于运行时的性能，但如果分组太小，推荐精准度会降低。通过这种技术可以节省运行时间，但这种放入内存的方法无法在实际大数据库进行扩展。在Xue et al.(2005)中可以找到最新利用k-means将有相同品味用户聚类的方法。 回到概率方法上来，除了朴素贝叶斯方法，Breese et al.(1998)还提出了另外一种贝叶斯分类器的实现形式，并基于贝叶斯信任网络对分类条件概率建模。这些网络允许我们将变量间已有的依赖关系显示出来，并把这些关系编码到一个有向无环图中。建模首先要求系统学习网络结构（见Chickering et al. 1997），其次预估所需的条件概率。 将概率方法与其他方法相比，比如基于用户的最近邻算法，可以发现基于贝叶斯网络的技术在某些测试领域（但还不是所有领域）比其他算法稍好一些。汇总所有数据和评估标准，贝叶斯网络方法仍然表现出最好的性能（Breese et al. 1998）。然而在某些数据上（比如在热门电影领域），贝叶斯方法会比经过缺省投票、反用户频率和样本扩展等改进后的基于用户方法明显差很多。 一般来说，贝叶斯分类方法的优势在于数据中的个别噪声点被平均化，不相关的属性对计算后验概率只有很少或没有影响（Tan et al. 2006）。贝叶斯网络没有过拟合模型的强烈倾向，也就是说几乎总能够学出近似通用化的模型，从而有很好的预测精准度。此外，它还适用于不完整的数据。 说句题外话，这里描述的概率方法由于模型事先在线下已经学习好，其运行性能一般比基于记忆的方法好很多。与此同时，Breese et al.( 1998)证明了概率方法在内存需求方面也是有利的，在一定程度上是由于最终产生的信任网络能保持非常小的规模。 与Breese et al.(1998)的朴素贝叶斯方法相似的另一种方法是Chen and George(1999)所描述的做法，同样提供了更多关于缺失评分处理的细节，以及如何根据引入隐藏（潜在）变量将用户聚集成模型分组成员。Miyahara and Pazzani (2000) 基于简单的贝叶斯分类器提出了一种相对直接且有效的协同过滤技术，而且重点讨论了特征选择方面的技术。这种技术通常用于省略不相关的物品（特征），提高准确率并减少计算时间。 最新使用潜在分类变量发现相似用户和物品分组的统计方法是由Hofmann(2004；Hofmann and Puzicha 1999)提出的，它可以在Breese et al.(1998)结果的基础上进一步提高质量。该方法也已经用于Google的新闻推荐，这将会在下一节讲到。最近关于不同概率方法和混合模型的全面综述和比较可以在Jin et al.(2006)中找到。 Pennock et al.(2000)和Yu et al.(2004)描述了更多概率方法，两者都致力于将基于模型和基于记忆推荐的想法和好处融合在一个概率框架之中。Yu et al.(2004)开发了其称为“用于协同过滤的基于记忆的概率机制”。作为一个机制，它被设计成能够适应特定任务的改进，比如新用户问题或者从评分数据库中挑选一组对等用户；所有的这些改进都以概率方法为基本原则实现。新用户问题可以在这个机制中通过主动学习方法解决，也就是说，要求新用户对一组物品评分（Goldberg et al.(2001)也提出过）。关键的任务是选择新用户最有可能评分的物品，其基础是决策理论和概率论。此外，该方法也说明了产生并更新资料空间的过程是如何融入到同样的概率机制中的，空间包含了用户数据库中最有信息量的用户，而且构造空间可以减少计算复杂度。如作者所述，虽然其主要贡献是提供了一个允许在健全的概率论基础上进行改进的机制，但是实验也证明在这些方法的帮助下，与Breese et al.(1998)描述的概率方法结果相比，该机制能够达到相当或更优的预测精准度。 2.5　近来实际的方法和系统 到目前为止，我们的讨论展示了不同的技术领域，原则上它们都基于用户—物品评分矩阵信息生成预测和推荐。我们可以观察到这些方法不仅在推荐质量上有所不同（这是大多数研究工作的主要目标），而且在算法本身的复杂度方面也有差别。最早的基于记忆算法在实现方面相当直接，但其他方法却要依赖复杂的预处理和模型更新技术。许多方法都可以用到数学软件库，但需要一些深度的数学技巧 ，这也许会限制这些方法的实际使用，尤其是对小规模的企业。最近的一篇论文Lemire and Maclachlan (2005) 提出一种新的相对简单的推荐技术，虽然非常简单但也能得到适当的推荐质量。除了能让“普通工程师”轻松实现这个目标，Slope One预测方案也能够支持动态数据更新和高效的实时查询。我们会在下一节讨论这个已经实际用于若干Web站点的方法。 一般来说，实际商业推荐系统（不管规模大小）公开可用的报告数目仍然有限。在一篇最近的论文中，Das et al.(2007)公布了Google新闻个性化引擎实现的一些细节，这个引擎被设计用来提供实时的个性化推荐。本节以该方法的总结作结，揭示了如何实现一个包含几百万篇新闻和被数以百万计在线用户应用的大规模推荐系统。 2.5.1　Slope One预测器 最初创造“Slope One”预测器的想法很简单，基于作者所谓的“热门度差异”，也就是对用户来说物品相互之间的评分差异。考虑以下示例（表2-8），它基于成对比较不同用户对物品的偏好。 表2-8　对于Alice和物品5＝2+(21)＝3的Slope One预测 物品1 物品5 Alice 2 ? 用户1 1 2 在这个例子中，用户1给物品1打1分，给物品5打2分。Alice给物品1打2分。目标是预测Alice给物品5的评分。一种简单的预测是Alice给物品1的评分加上用户1在这两个物品上评分的相对差值：p（Alice，物品5）=2+（21）=3。评分数据库由许多这样的配对组成，人们可以利用这些差值的平均值来预测。 一般来说，这里的问题是找出形如f(x)=x+b这样的函数（这就是“Slope One”名字的由来），为每对物品根据一个物品的评分预测另一个物品的评分。 让我们看看下面稍微复杂些的示例（表2-9），这里我们要预测Alice给物品3的评分。 表2-9　Slope one预测：更详细的例子 物品1 物品2 物品3 Alice 2 5 ？ 用户1 3 2 5 用户2 4 3 物品1和物品3有2次同时评分。与物品1相比，物品3一次被打高了2分(53=2)，另一次打低了1分(34=1)。因此这些物品的平均距离是(2+(1))/2=0.5。物品3和物品2只有一次同时评分，距离是(52)=3。因此，根据物品1和Alice对物品1的评分2，对物品3的预测应该是2+0.5=2.5。根据物品2，预测应该是5+3=8。整体的预测还要考虑到同时评分的个数，可以给那些有更多数据支持的偏移量更大的权重： （2.18） 具体来说，方法可以描述如下，用到的符号（Lemire and Maclachlan 2005）略有不同，但可以简化描述。通常，整个评分数据被标记为R。某个用户的所有评分保存在一个不完全的数组u中，ui即为用户u对物品i的评分。Lemire and Maclachlan (2005)称这个数组为评分（evaluation），其对应矩阵R中的一行。给定两个物品j和i，令 标记同时包含对物品i和物品j的评分集合。两个物品i和j的平均偏差值dev可以计算如下： （2.19） 就像例子中显示的，我们能根据每一个同时评分的物品i预测用户u对物品j的评分，记为 。这些单个预测的简单组合可以用来计算所有同时评分物品的平均值： （2.20） 函数Relevant(u, j)表示那些至少有1次与物品j被用户u同时评分的相关物品集合。换句话说，Relevant(u, j)={i|i∈S(u), i≠j, |Sj,i (R)|﹥0}，其中S(u)表示u中有评分的元素集合。在实际环境和存在足够稠密的数据的情况下，这个公式可以简化为Relevant(u, j)=S(u){j}，这时j∈S(u)。 直观上看，这个基本方案的问题是没有考虑同时评分物品的数量，尽管很显然，如果同时评分的物品数越多预测器就会越有效。因此对该方案的改进方法是基于同时评分数为单个偏移量赋以权重，公式如下： （2.21） 另一种改进基本预测方案的方法是根据评分数据库中“喜欢和不喜欢”模式为每个偏移量赋权（两极方案）。为了这个目的，当为用户j预测时，相关的物品评分（和偏移量）被分成两组，一组包含用户同时喜爱的物品，另一组包含用户同时不喜爱的物品。最终的预测由这些偏移量组合而成。整体的效果就是，方案只关注用户在正面或负面意见上达成一致的那些评分。尽管这对于已经很稀疏的评分数据库来说可能会存在问题，但期望的效果就是预测方案能“在用户A喜欢物品K而且用户B不喜欢物品K时不做预测”（Lemire and Maclachlan (2005)）。 当把评分划分成喜欢和不喜欢两组时，人们也应该考虑到实际情况中评分数据库的特性。事实上，当给定15分范围时，可以观察到在典型数据集上大约70%的评分高于理论平均值3。这表明，一般来说，用户要么(1) 倾向于给他们喜欢的物品评分；要么(2) 仅仅是倾向于给出相对高的评分，并把3分看做是相对低的评分。在这里讨论的双极预测方案中，阈值因此被设为每个用户的平均评分值，而不是一个整体的阈值。 Slope One预测器在通用测试数据上的评估效果显示，其推荐质量（根据通常指标测量，见7.4.2节）与已有的方法性能相当，比如基于Pearson关联关系和实例增强的协同过滤方法。基本方案的改进（有权重的预测器和两极方案）也能带来性能提升，尽管这些提升相对较小（1%～2%），而且几乎没有什么意义。 总的来说，以上提出的基于物品和基于评分的算法比较简单，但在一般的评分数据上能够有较好的表现。此外这种技术可以同时支持新评分出现时的动态更新预测，以及实时的高效查询（当然这会带来更多的内存需求）。由于这种技术相对简单而且能够获取不同流行编程语言的小型开源代码库，因此在更大范围内有助于在实际环境中实现更多的推荐系统。 从科学角度来看，我们还需要进一步研究并在更多不同数据上评估，才能认清Slope One算法在不同应用和场景下的特性。 2.5.2　Google新闻个性化推荐引擎 Google新闻是一个在线信息门户站点，它聚集数千家信息源的新闻报道（在将相似新闻分组后）并以个性化的方法展现给登录用户（见图2-4）。其推荐方法是一种基于活跃用户的点击历史和更大社区历史信息的协同方法，也就是说，点击一篇报道被认为是正面评分。更多复杂的获取评分和解释的技术可以在Joachims et al.(2005)的研究中找到。 图2-4　Google新闻门户 在新闻门户中，推荐系统一般用于将一组个性化新闻报道组成某个专题。主要的挑战在于：(1) 实时产生列表只允许至多在1秒钟内生成内容；(2) 由于新物品的连续流入，“物品目录”变化频繁，与此同时其他文章很快就变得过时了。此外，还有一个目标是及时反馈用户的交互和要考虑到用户最近阅读的文章。 由于文章和用户数量巨大，以及给定的响应时间要求，纯粹的基于记忆的方法是不适用的，需要组合使用基于模型和基于记忆的技术。基于模型的那部分依赖两种聚类技术：Hofmann(2004)提出的概率潜在语义索引（PLSI）和一种新方法MinHash，后一种哈希方法根据两个用户浏览过物品的交集将两者放入相同的聚类（哈希桶）。为了让这种哈希过程具有可扩展性，采用了一种特殊方法寻找近邻，并采用Google自己的MapReduce技术在几个机群之间分发计算任务。 PLSI方法可以看做是协同过滤的“第二代”概率技术，它和Breese et al.(1998)早前讨论的概率聚类技术思想比较类似，都是为了识别出有相似想法的用户和相关物品的聚类。与Breese et al.(1998)中每个用户都属于某个确定类别相比，Hofmann的方法引入了隐藏变量，对应每个用户—物品对的有限状态集合。因此，该模型也能适应用户可能同时对多个主题感兴趣的情况。混合模型的参数取决于标准期望最大化方法（Dempster et al.1977）。从计算次数和需要内存两方面来看，这个过程在计算上开销很大，因此需要通过MapReduce在多个机器上并行EM计算。并行能够显著加速学习概率分布的过程，但仍不足以在新用户或新物品出现时就实时重新训练网络，因为这些变化在新闻领域内经常发生。因此，需要采用一种近似PLSI的方法来处理实时报道。根据聚类成员的概率和每个聚类在每篇报道上点击次数的统计量，可以计算出推荐分值。这个分值被归一化到[0...1]区间。 为了处理新用户，推荐系统基于记忆的方法分析“伴随浏览量”显得非常重要。“伴随浏览量”指的是一篇文章在预先定义的一段时间内被相同用户浏览过。利用这种信息的理由和前几节描述的基于物品推荐方法差不多。数据不是线下预先处理好的，而是一种不断更新、类似连续点击的特殊数据结构。预测时需要遍历活跃用户最近的历史数据和从内存里获取邻近的文章。为了计算实际分值，要考虑存储在邻接矩阵里的权重，最终结果会被归一化到0~1之间。 运行时，预先设定集合里候选物品的综合推荐评分是这三种方法（MinHash、PLSI和伴随浏览）获得的分数的线性组合计算值。预先挑选合适的候选推荐集合时，可以依据不同的信息，比如语言偏好、新闻时效性或用户特定的个性化设置。另一方面，相同类别里其他用户的点击历史也可以用来限定候选物品集合。 在不同数据（电影和新闻）集上评估该算法显示，当单个数据集被评估时PLSI表现最好，其次是MinHash和标准的基于相似度的推荐算法。实验在实时数据上对比了新技术和一种非个性化的方法，这种方法将文章根据最近的热度排序。为了对比两种方法，推荐列表中间隔插入了两种算法的推荐物品。实验结论根据物品得到的用户点击数衡量。毫无疑问，个性化方法明显占优势（大约38%），除了一些不经常发生的情况，比如极为热门的新闻。如何为单个算法赋权是一个有趣的问题，还有待讨论。 一般来说，从那篇报告中可以得出的结论是，如果我们有一组大规模数据集且数据频繁变化，在算法、设计及并行方面需要费很大力气才有可能应用现有技术和实时推荐。纯基于记忆的方法不能直接应用，对于基于模型的方法来说，必须解决模型的连续更新问题。 这里的研究未能回答的问题是：理解内容的方法是否能产生更好的结果？我们会在下一章看到基于内容的推荐技术，该算法基于文档内容以及明确的或学习到的用户兴趣进行推荐，尤其适合该类型的问题。 2.6　讨论和小结 本书讨论的构建推荐系统的所有方法中，协同过滤是被研究最多的技术。这不仅仅因为20世纪90年代中期的推荐系统都是基于用户社区，可以给物品评分，也因为今天大多数成功的推荐系统都依赖这些技术。早期系统由基于记忆的近邻和基于关联的算法构建而成，后来出现了更多复杂的和基于模型的方法，这些方法应用了机器学习、信息检索和数据挖掘等不同领域的技术，而且经常依赖SVD这样的代数方法。 如Adomavicius and Tuzhilin(2005)所述，近年来研究工作的重心都放在了开发更为复杂的概率模型上，因为这些方法最初公布的预测精准度都很高。 协同过滤作为推荐系统的一个子领域，它的流行有很多原因。其中最重要的原因是有实际环境作为改进的基准，而且用于分析生成推荐的数据结构——物品评分矩阵，非常简单。因此，评价一个新开发的推荐技术，或应用已有技术是否比先前方法更好非常直观，特别是在评估准则本身也标准化的情况下。显而易见，其他算法和协同过滤相比不会总是那么简单，尤其是得到更多知识而不仅仅是简单的评分矩阵时。举个例子，通过会话交互的推荐应用会在交谈中询问用户的偏好，并且还会融入一些额外的领域知识。 然而，不同领域的有效测试数据可以促进协同过滤进一步发展，产生各种更为复杂的协同过滤技术。尽管如此，在某种程度上这也会限制协同过滤技术的应用。最热门的数据是电影和书籍，许多研究者致力于仅在这些数据上提高算法的准确率。遗憾的是，付出再多努力也无法使得某种协同过滤算法在各个领域表现都优异。 事实上，考虑到有那么多的不同方案，即使我们仅限于纯粹的协同过滤方法，在何种情况下使用哪种推荐算法的问题依然没有唯一答案。而且在已知测试数据上得出精确结果并不代表什么。许多研究者将他们的测试结果与来自Breese et al.(1998)中显得相当陈旧的结论做比较，公布他们能够在某个环境和实验里得出更准确的结果。鉴于过去十年里提出的几十种不同技术，我们迫切需要更新的对比基准。有了新的对比基准，才能得到更清晰的描述。 从实用角度来看，Linden et al.(2003)公布并在Amazon.com中使用的基于物品的协同过滤方法能处理非常大规模的评分数据，并能生成质量良好的推荐。关于其他商业应用和相关技术细节的文章目前还不多见，所以在该方向的业界调查有助于研究团体验证新方法是否适合以及如何在业界应用。 我们将在第5章讨论混合推荐方法。这种方法利用了物品或用户的额外信息，并混合不同技术得到显著优于单纯使用协同方法能达到的效果。根据近年来的发展趋势，可以预期未来更多的信息（包括物品目录和用户）都能够以非常低的代价获取，这样有助于组合或混合的方法。这些额外的信息可以来源于方方面面：在线用户在社交网络和在线社区里共享越来越多的信息；公司之间仅以电子格式交换物品信息，并越来越多地采用包含了明确物品分类方案的交换标准。最后，在“语义网络”的帮助下，这些物品和社区信息能够轻易地从已有Web资源中被自动抽取出来。（参见Shchekotykhin et al.2007可以找到这种方法的例子。） 总而言之，假定满足适当的要求，今天的协同过滤方法在实际应用方面已经足够成熟。协同推荐系统不可能应用于每个领域：例如一个没有购买历史的汽车销售系统，或需要更多用户偏好细节的系统。同样，协同过滤技术要求用户社区处于某个特定规模，这意味着即使在书籍和电影领域，如果没有足够的用户或评分数据，也无法应用这些技术。 能够克服这些缺陷的推荐方法必然要付出代价，比如下一章要讨论的基于内容的推荐就需要进一步的开发和维护。 2.7　书目注释 关于推荐系统的报告最早发表于20世纪90年代初期。被引用最多的可能就是讨论Tapestry（Goldberg et al.1992）和GroupLen系统（Resnick et al.1994）的论文，两者最初都发表于1992年。Tapestry在Xerox Parc上开发，用于邮件过滤，基于当时相对新颖的利用其他用户显式反馈（评分和注释）的想法。这篇论文最早使用了“协同过滤”这个词。GroupLens系统 也是为了过滤文本文档（比如新闻报道）而开发的，但是被设计用于开放社区，并初步利用了在数据中自动发现相似用户的思想进行预测。Shardanand and Maes(1995)提出的Ringo系统描述了一个基于协同过滤方法的音乐推荐系统，该系统使用了Pearson关联度量和平均绝对误差（MAE）评估方法。 早前提到过，Breese et al.(1998)仍然是一个重要的参考点，尤其是其提出的特殊技术对比算法。 依赖主成分分析和聚类的Jester笑话推荐系统，其最早的基于模型的版本于1999年左右提出，而且得到进一步发展（Nathanson et al.2007）。Hofmann和Puzicha于1999年发表了基于潜在类别模型的重要方法用于协同过滤。基于SVD的维度削减法由Sarwar et al.(2000a)提出。 Sarwar et al.(2001)分析了基于物品的过滤方法；Linden et al.(2003)简单描述了Amazon.com的专利实现和体验。 Schafer et al.(2006)和Anand and Mobasher(2005)是关于协同过滤的优秀综述性论文，给了本章很大启发，而且也可以作为进一步阅读的起点。另外一篇协同过滤领域的最新技术综述是Adomavicius and Tuzhilin(2005)，附有令人印象深刻的参考文献列表。 由于推荐系统植根于不同领域，协同过滤技术的研究论文也出现在各种期刊和会议中。关于推荐系统的专业出版物有Communications of the ACM（1999）、ACM Transactions on Information Systems（2004），以及最近的Journal of Electronic Commerce（2007）、IEEE Intelligent Systems（2007）和AI Communications（2008）。许多论文也会首先发表在专门的研讨会系列上，比如Intelligent Techniques for Web Personalization Workshop和最近的ACM Recommender Systems 大会。