推荐系统-传统算法

一、Tapestry[1992]

  1. 1992 年的论文《Using Collaborative Filtering to Weave An Information Tapestry》 中,论文提出了一个基于协同过滤collaborative filtering 的电子邮件过滤系统。

    TapestryXerox Palo Alto 研究中心开发的实验邮件系统,其动机来自于电子邮件的日益使用,导致用户被大量的邮件所淹没。

    处理大量电邮的一种方法是提供邮件列表,这使得每个用户只能订阅他们感兴趣的那些列表。但是,特定用户感兴趣的文档集合很少能够完整的映射到现有的列表。

    更好的解决方式是为每个用户指定一个filter 过滤器,该过滤器将扫描所有的列表,然后在所有列表中选择用户感兴趣的文档。

    目前已经有一些邮件系统支持基于文档内容的过滤。 Tapestry 系统可以在基于内容的过滤之外,通过引入人们的行为来执行更有效的过滤,这种过滤被称作协同过滤 collaborative filtering

    协同过滤通过记录人们对于他/她所阅读文档的反应reaction来协同从而帮助彼此进行过滤,这种反应可能是文档特别有趣(或者特别无趣)。这些反应(通常也被称作注解 annotation )可以由其它过滤器访问。

  2. 下图给出了Tapestry 的整体架构:

    • Indexer:从电子邮件、Netnews 等外部来源读取文档,并将其添加到 Document Store 中。Indexer 负责将文档解析为一组索引字段从而方便在query 中使用。
    • Document store:为所有 Tapestry 文档提供长期存储,该存储仅支持追加。它还在存储的文档上维护索引,以便可以有效地执行对文档数据库的 query
    • Annotation store:为文档关联的注解提供长期存储,该存储也只支持追加。
    • Filterer:重复对文档集合运行用户指定的一组query,那些与query 匹配的文档将被返回。
    • Little box:将特定用户感兴趣的文档排队。每个用户都有一个 little box,它里面的文件由过滤器填充,并由用户的文件阅读器消费。
    • Remailer:通过电子邮件定期的将little box 的内容发送给用户。
    • Appraiser:对用户的文档进行个性化分类(如用户的 little box 中的文档)。该功能可以自动地对文档进行优先级排序和分类。
    • Reader~Browser:提供用于访问Tapestry 服务的用户界面,如添加/删除/编辑过滤器、检索新文档、显示文档等。

  3. Tapestry 系统中,用户需要显式指定协同的用户以及该用户的行为构建协同过滤器。在后续的演变过程中,协同过滤已经改进了这种方式,无需用户手动指定即可实现协同过滤。

二、GroupLens[1994]

  1. 1994 年的论文《GroupLens: An Open Architecture for Collaborative Filtering of Netnews》 进一步的发扬了这种UserBased 协同过滤的思想。

    GroupLens 是一个采用协同过滤的网络新闻过滤系统,它设计了一种机制来帮助用户筛选他/她感兴趣的新闻。GroupLens 基于一个朴素的思想:用户在过去的兴趣会延续到将来。

    GroupLens 利用了用户对文章的评分:

    • 首先计算不同用户的评分序列之间的相关性,从而得到用户兴趣之间的相似性。
    • 然后根据相似用户的评分来预测当前用户对于新文章的评分。
  2. 给定评分矩阵:

    其中 表示用户 对于文章 的评分,该评分可能是已知的,也可能是未知的(因为用户尚未阅读该文章)。当用户评分未知时,我们将其填充为

    GroupLens 首先计算用户兴趣之间的相似性。给定用户 ,定义他们共同评分的文章集合为:

    然后计算用户 在这些共同评分文章上的均值、方差、以及协方差:

    则用户 的兴趣相似性由二者评分集合的相关系数correlation coefficient定义为:

  3. 当预测用户 在未阅读文章 上的评分时,我们首先找出在 上存在评分的用户集合

    然后我们基于用户 和集合 中用户的相似性来预测:

    评分 不仅受到用户 对文章 的偏好的影响,还受到用户 整体打分的影响。如,有的用户倾向于都打高分,有的用户倾向于都打低分。因此这里通过 来剔除整体性偏好的影响,得到文章 的偏好。

三、ItemBased CF[2001]

  1. 世界上信息量的增长速度远远超过我们处理信息的能力。我们都有体会:被每年出版的海量的新书、期刊文章和会议纪要所淹没的感觉。技术大大降低了发布publishing 和分发 distributing 信息的障碍。现在是时候创造新的技术,从而可以帮助我们从所有可用信息中找到最有价值的信息。

    此类最有前途的技术之一是协同过滤 collaborative filtering。协同过滤的工作原理是建立用户对 item 的偏好数据库。对于一个新用户,假设叫做 Neo,我们从数据库中匹配邻居,这些邻居是历史上与 Neo 有相似品味taste 的其它用户。然后我们将邻居喜欢的 item 推荐给 Neo,因为 Neo 可能也会喜欢这些 item。协同过滤在研究和实践中都非常成功,在信息过滤应用和电商应用中都非常成功。然而,协同过滤推荐系统有两个基本挑战仍然未能克服:

    • 可扩展性scalability:这些算法能够实时搜索数以万计的潜在邻居,但是现代系统需要搜索数千万个潜在邻居。由于整体计算复杂度为 ,其中 为用户数量、 为平均每个用户评分的item 数量,因此随着用户规模的增加其计算复杂度难以忍受。

      此外,现有算法对于拥有大量历史行为的单个用户individual user 也存在性能问题。例如,某些用户可能在成千上万个item 上有过行为,那么这批用户会拖慢每秒可以搜索的相似用户的数量(因为计算用户之间的相似度的计算复杂度为 为用户评分的 item 数量),从而进一步降低了可扩展性。

    • 推荐质量 quality:用户需要他们可以信任的推荐,从而帮助他们找到感兴趣的 item。对于质量较差的推荐,用户一般都是“用脚投票”,直接拒绝使用该推荐系统。

    某种程度上这两个挑战是相互冲突的:算法花在搜索邻居上的时间越少,它的可扩展性就越强、推荐质量也就越差。出于这个原因,同时处理这两个挑战很重要,这样的解决方案既有效又实用。 论文 《Item-Based Collaborative Filtering Recommendation Algorithms》 提出了 Item-Based CF 来同时解决这两个挑战。

    传统的协同过滤算法的瓶颈是在大量用户中搜索邻居,而 Item-Based 算法通过首先探索 item 之间的关系、而不是用户之间的关系来避免这个瓶颈。通过查找用户喜欢item 相似的其它 item 来获取对用户的推荐。 由于 item 之间的关系是相对静态static 的, Item-Based 算法可以减少在线计算的数量,同时保持与 User-Based 算法相同的推荐质量。

    论文主要贡献:

    • 分析 Item-Based 的预测算法,并识别 identification 实现其子任务的不同方法。
    • 形式化 item 相似度的预计算模型 pre-computed model,从而提高 Item-Based 推荐的在线可扩展性。
    • 几种不同的 Item-Based 算法与经典的 User-Based 算法(最近邻)的实验效果比较。
  2. 相关工作:这里我们简要介绍一些与协同过滤、推荐系统、数据挖掘、以及个性化相关的研究文献。

    • Tapestry 是基于协同过滤的推荐系统的最早实现之一。该系统依赖于来自紧密社区close-knit community (如办公室工作组)的人们的显式意见 explicit opinion,其中每个用户都了解其它用户。但是大型社区的推荐系统不能依赖于每个用户都了解其它用户。

      后来,人们开发了几个基于评级ratings-based 的自动推荐系统。

      • GroupLens 研究系统为 Usenet 新闻和电影提供了匿名协同过滤解决方案。
      • RingoVideo Recommender 是分别生成音乐推荐和电影推荐的 email-based 系统和 web-based 系统。
    • ACM 的通讯特刊《Recommender Systems》介绍了许多不同的推荐系统。

    • 其他技术也已经应用于推荐系统,包括贝叶斯网络、聚类clustering 、以及Horting

      • 贝叶斯网络创建一个基于训练集的模型,每个节点都有一个决策树,边代表用户信息。该模型可以在几个小时或者几天内离线构建。生成的模型非常小,速度非常快,并且基本上与最近邻方法一样准确。

        贝叶斯网络被证明可能适用于用户偏好缓慢变化(相对于构建模型所需的时间)的环境,但是不适用于必须快速或频繁更新用户偏好模型的环境。

      • 聚类技术通过识别似乎具有相似偏好的用户组 user group 来工作。一旦创建了簇 cluster,就可以通过对该簇中其它用户的意见进行平均来对单个用户进行预测。

        某些聚类技术将每个用户划分到多个 cluster,然后预测时按照跨 cluster 取加权平均值,权重是参与这个 cluster 的程度。

        聚类技术通常比其它方法产生较少个性化的推荐,并且在某些情况下聚类的准确性比最近邻算法更差。然而,一旦聚类完成,性能就会非常好,因为必须分析的组的数量要小得多。

        聚类技术也可以作为 first step 来应用,用于在最近邻算法中缩小候选集、或者在多个推荐引擎之间分配最近邻计算。虽然将用户划分为 clusters 可能会损害 cluster 边缘附近用户的准确性或推荐,但是 pre-clustering 可能是准确性和吞吐量之间的一个值得的 trade-off

      • Horting 是一种 graph-based 技术,其中节点是用户、节点之间的边表示两个用户之间的相似程度。预测是通过游走到附近节点,然后结合附近用户的意见来产生的。

        Horting 和最近邻不同,因为它探索了graph 上的高阶关系而最近邻仅探索 graph 上的一阶关系(直接关系),从而探索最近邻算法中没有考虑的信息传递。在一项使用人工合成数据的研究中,Horting 产生了比最近邻更好的预测算法。

    • 《Recommender Systems in E-Commerce》 展示了电商中使用的推荐系统的详细分类和示例,以及它们如何提供一对一的个性化,同时可以捕获客户忠诚度loyalty

    尽管这些系统在过去取得了成功,但是它们的广泛使用暴露了它们的一些局限性,例如数据集的稀疏性问题、与高维相关的问题等。

    • 推荐系统中的稀疏性问题已经在

      《Using Filtering Agents to Improve Prediction Quality in the GroupLens Research Collaborative Filtering System》《Combining Collaborative Filtering With Personal Agents for Better Recommendations》 中得到解决。

    • 推荐系统中与高维相关的问题已经在 《Learning Collaborative Information Filters》 中讨论过,在 《Application of Dimensionality Reduction in Recommender System -- A Case Study》 中已经研究了应用降维技术解决这些问题。

    我们的工作探索了 Item-Based 推荐算法(一类新的推荐算法)能够在多大程度上解决这些问题。

3.1 模型

3.1.1 CF-Based 推荐系统

  1. 推荐系统主要解决以下问题:通过为给定用户生成预测的可能性得分、或者 top-N 的推荐 item 列表,从而帮助用户找到他们想在电商网站上购买的 item

    可以使用不同的方法进行 item 推荐,例如基于用户的人口统计 demographics、热门 item 、或者用户历史购买习惯。协同过滤 Collaborative Filtering: CF 是迄今为止最成功的推荐技术。基于 CF 的算法的基本思想是:根据其他志趣相投用户的意见提供 item 推荐或预测。用户的意见可以显式explicitly 地从用户那里获取,也可以通过一些隐式implicit 的手段获取。

  2. 协同过滤处理 Overview:协同过滤算法的目标是根据用户历史偏好、或者其他志趣相投用户的意见,为目标用户推荐新 item 或者预测某个 item 的效用 utility

    在典型的 CF 场景中,有一个 个用户的列表 、以及一个包含 item 的列表 。每个用户 都有一个 item 列表 ,对该列表中的每个 item,用户 已经表达了他/她的意见opinion 。 意见可以由用户显式给出(如位于某个数字区间的评级分数 rating score),也可以通过分析日志从购买记录中隐式地获取。注意,,并且 可能是空集。

    给定目标用户 ,协同过滤算法的任务是为 找到一个 item 偏好item likeliness 。这种偏好有两种形式:

    • 预测:预测用户 对于item 的评分
    • 推荐:为用户 推荐他/她可能最喜欢的由 item组成的列表 。注意,推荐列表必须位于目标用户尚未购买的 item 上,即 。这被称作 Top-N 推荐。

    下图给出了协同过滤任务的示意图。CF 算法将整个 user-item 数据表示为一个评分矩阵 ,矩阵中的每一个元素 表示第 user 在第 item 上的评分。每个评分在一定范围之内(如 1~5 ),也可以为 0 ,表示用户尚未对该 item 评分。

    协同过滤算法可以分为两类:

    • memory-based基于内存的(也称作 user-based)协同过滤:利用整个评分矩阵来生成预测。

      该算法采用统计技术来找出与目标用户最相似的一组用户(称作邻居),然后使用不同的组合方式来组合这些邻居的偏好,从而为目标用户生成推荐或 Top-N 推荐。因此该技术也被称为最近邻nearest-neighbor 或者 UserBased CF 技术。

    • model-based 基于模型的(也称作 item-based)协同过滤:通过建立用户打分模型来提供item 推荐。

      这些方法首采用概率性的方法probabilistic approach ,然后根据给定用户在其它item 评分的条件下来预测未打分item 上的评分。模型构建过程由不同的机器学习算法执行,例如贝叶斯网络、聚类、以及基于规则rule-based 的方法。

      • 贝叶斯网络模型为协同过滤问题形式化了概率模型。
      • 聚类模型将协同过滤视为分类问题,并通过将相同类别的相似用户聚类,并估计给定用户属于特定类别 的概率来工作,并由此计算评分的条件概率。
      • 基于规则的方法应用关联规则挖掘association rule discovery 算法来发现共同购买co-purchaseitem 之间的关联,然后根据 item 之间的关联强度生成 item 推荐。
  3. User-Based CF 的挑战:User-Based 协同过滤系统在过去非常成功,但是它们的广泛使用暴露了一些潜在的挑战,例如:

    • 稀疏性 Sparsity:在实践中,许多商业推荐系统用于评估大型 item 集合(如 Amazon.com 推荐书籍、CDnow.com 推荐音乐专辑)。在这些系统中,即使是活跃用户购买的 item 也可能占比远低于 1%200 万本书的 1%2 万本书)。因此,基于最近邻算法的推荐系统,其推荐的准确性可能很差。

      注意:因为 user 的行为太稀疏,导致 user-to-user 的相似度不可置信。

    • 可扩展性 Scalability :最近邻算法的计算复杂度随着用户数量和 item 数量的增长而增长。对于数以百万的用户和 item,运行现有算法的、典型的 web-based 推荐系统将面临严重的可扩展性问题。

    最近邻算法在大型稀疏数据集上的弱点促使我们探索替代的推荐系统算法。

    我们的第一种方法试图将半智能过滤代理 semi-intelligent filtering agent 结合到推荐系统中来,从而弥合稀疏性。这些代理使用文法特征 syntactic feature 对每个 item 进行评估和打分。通过提供稠密的评分集合,它们有助于缓解覆盖度 coverage并提高推荐质量quality 。然而,过滤代理解决方案并没有解决志趣相同、但是评分稀疏的用户之间关系不佳的根本问题。为了探索这一点,我们采用了一种算法方法,并使用潜在语义索引 Latent Semantic Indexing: LSI 来捕获降维空间中用户和 item 之间的相似度。

    在本文中我们研究了另一种技术,即 model-based 方法,来应对这些挑战,尤其是可扩展性挑战。这里的主要思想是分析 user-item 表示矩阵 representation matrix 来识别不同 item 之间的关系,然后利用这些关系来计算目标 user-item pair 的预测分。这种方法背后的直觉是:用户有兴趣购买历史喜欢 item 类似的 item,并倾向于厌恶历史不喜欢 item 类似的 item。这些技术不需要在请求推荐时识别用户的相似用户,因此它们往往会更快地给出推荐。

    已经有很多不同的方案来计算 item 之间的关联,从概率性方法到更传统的 item-item 相关性。接下来我们将详细分析我们的方法。

3.1.2 Item-Based CF

  1. 这里我们研究了一类 Item-Based 的推荐算法,用于对用户进行推荐预测。与前面讨论的 User-Based CF 算法不同,Item-Based 的方法查看目标用户历史评分 item 集合并计算它们与目标 item 的相似度,然后选择 top-k 最相似的 item 。同时,top-k 对应的相似度 也被计算。

    一旦得到最相似的item 及其相似度,我们可以通过目标用户对这些相似item 已有评分的加权均值来执行预测。我们这里详细描述了这两个方面,即相似度计算和预测生成。

  2. Item 相似度计算:Item-Based CF 最关键的步骤之一是如何计算 item 之间的相似度。计算item 之间相似度的基本思想是:首先挑选既对 打分、又对 打分的用户 ,然后基于这些用户的打分来计算相似度 。下图给出了这一过程,其中矩阵的行代表user、列代表 item

    其中有多种方法可以计算 item 之间的相似度,我们这里介绍三种方法,即基于余弦cosine-based 的相似度、基于相关系数correlation-based 的相似度、基于修正余弦adjusted-cosine based 的相似度。

    • 基于余弦的相似度cosine-based similarity:两个 item 被认为是 维用户空间中的两个向量。它们之间的相似度是通过计算这两个向量之间夹角的余弦来衡量的。

      其中 为用户 item 上的评分。我们只考虑

    • 基于相关系数的相似度correlation-based similarity :两个 item 之间的相似度是通过计算 Pearson-r 相关系数 来衡量的。

      其中 item 上的打分均值。

      如果令 ,则上式等价于:

    • 基于修正余弦的相似度adjusted-cosine similarity :基于余弦的相似度有个缺陷:未考虑不同用户之间的打分差异。修正的余弦相似度通过从每个用户的打分中减去该用户的打分均值来修复这个问题:

      其中 是用户 在他/她所有打分item 上的打分均值。

      如果令 ,则上式等价于: 。它和基于相关系数的相似度区别在于:后者仅考虑 item item 的评分,而前者考虑了整个评分矩阵的评分。

  3. 预测:协同过滤系统中最重要的一步是生成预测。一旦我们根据相似性得到了目标item 最相似的一组item,则下一步是为用户执行打分预测。这里我们考虑两种技术:

    • 加权和 weighted sum:该方法通过计算用户 item 相似 item 给出的评分的加权和,从而计算用户 item 的预测。加权的权重为 item 之间的相似度

      使用下图中的概念,我们可以将预测 表示为:

      这种方式捕获了目标用户 对相似 item 的评分。加权的权重进行了归一化,从而确保预测打分在预定范围内。

      下图中,使用了 5 个相似的 item 来进行预测。

    • 回归regression:这种方式类似于加权和,但是不是直接使用相似item 的打分,而是基于回归模型来拟合的修正打分。

      实践中使用余弦相似度或者相关系数相似度可能导致两个向量相似度很高,但是实际上差距很远(夹角相同,长度差异较大)。这种情况下使用原始评分来计算,可能会导致预测不佳。

      回归方法的思想是:采用加权和相同的公式,但是不使用原始打分 ,而是使用基于线性回归的近似值 。假设目标 item 的打分向量为 ,相似 item 的修正打分为:

      然后根据 最小化来求解参数 。最终有:

  4. 性能分析:User-Based CF 中,邻域的生成过程,尤其时user-user 相似度计算步骤被证明是性能瓶颈,从而使得整个过程不适合实时推荐。在本文中,我们提出了一种 model-based 方法来预计算 item-item 相似度得分。相似度计算方案仍然是基于相关性的(如基于相关系数或者基于余弦),但是计算是在 item 空间上执行的。在典型的电子商务场景中,与经常变化的用户数量相比,item 数量相比之下更为静态staticitem 的静态属性使得我们想到了预计算item 相似性的想法。

    预计算 item 相似度的一种可能方法是计算所有item 之间的相似度,然后执行快速查表从而检索到所需的相似度。这种方法虽然节省时间,但是对于 item 需要 的空间。事实上对于任何一个目标item,我们只需要一小部分最相似的 item 来预测,这使得我们找到了一种替代的 mode-based 方案。因此对于每个 item,我们仅计算 个最相似的 item,其中 。我们称 为模型大小。

    基于这个模型构建步骤,为目标用户 生成对目标 item 的预测的工作原理如下。

    • 邻域生成过程:首先检索与目标 item 对应的、预计算的 个最相似的 item

      这里的 表示预测时使用的相似 item 数量,它不同于模型大小 (表示预计算相似度的 item 数量)。

    • 预测生成过程:查看用户 购买了这 item 中的多少个,基于此交集使用 Item-Based CF预测算法。

    这里有质量和性能的权衡quality-performance trade-off :为了确保高质量,我们必须有较大的模型大小 ,而这会导致推荐的可扩展性问题。在极端情况下我们可以将模型大小设置为 ,这将确保与原始Item-Based CF完全相同的质量,但是具有很高的空间复杂度。然而,我们的替代方案确保我们保留最相似的 item,在生成预测时这些 item 对预测结果的贡献最大。因此,我们假设这种替代方案即使在 很小时也能够提供相当好的预测质量,从而提供良好的可扩展性。

    我们后续实验验证了我们的假设。具体而言,我们通过改变 值来验证模型大小对整个系统的质量和性能的影响。

  5. 读者注:理论上也可以将 User-Based CF 拆分为两阶段:邻域生成 + 预测生成。考虑到用户行为非常稀疏,因此用户的任何新的行为对 user-user 相似度影响较大。因此user-user 相似度必须根据最近的用户行为在线实时计算。

    相对来说,用户的任何新的行为对 item-item 相似度影响较小,因此 item-item 相似度相对静态,可以离线计算。

    如:假设user-item 矩阵规模为 1000 万用户、100item。假设平均每个用户对 5item 进行打分,则平均每个item 包含50 个用户。假设某个用户 刚刚对一个新的item 进行打分,则它会影响所有涉及到uuser-user 相似度,相似度波动范围大致为 20% ;它也会影响所有涉及到 item-item 相似度,但是相似度波动范围大致为 2% 。因此相对而言,item-item 相似度要稳定得多。

    其本质是 user-item 矩阵的行比列更为稀疏。

3.2 实验

  1. 数据集:我们使用MovieLens 数据集来评估Item-Based CF 的效果。MovieLens 是一个 web-based 的研究research 推荐系统,于 1997 年秋季首次亮相。每周都有数百名用户访问 MovieLens 来评估和接受电影推荐。该网站现在拥有超过 43000 名用户,他们对 3500 多部电影进行评分。我们随机选择打分超过20 部电影的用户及其对应的电影评分,得到十万个打分,其中包括943 个用户、1682 部电影。即我们的 user-item 矩阵

    我们将数据集随机拆分为训练集和测试集,拆分比例为 。如, 表示 80% 的训练集和 20% 的测试集。实验中我们还考虑了数据集的稀疏水平 sparsity level。给定一个矩阵,我们定义它的稀疏水平为:

    其中 表示矩阵非零元素的总数, 表示矩阵所有元素的总数。我们数据集的稀疏水平为

  2. 评估指标:推荐系统用来评估推荐质量的指标主要可以分为两类:

    • 统计准确性指标statistical accuracy metrics :通过测试集上user-item 的真实打分和预测打分的对比,从而评估推荐的准确性。

      平均绝对误差 MAE 是其中应用广泛的指标。对每个真实打分和预测打分pair ,平均绝对误差为 。考虑所有的 组测试数据,则有:

      MAE 越低则推荐质量越好。

      另外,均方误差RMSE、相关系数Correlation 也是类似的统计意义上的准确率指标。

    • 决策支持准确性指标decision support accuracy metrics :评估推荐系统帮助用户筛选高质量item 的有效性。

      事实上给用户推荐item 之后,用户会在被推荐item 上给出反馈:推荐有效(用户感兴趣)还是推荐无效(用户不感兴趣)。因此这是一个典型的二元分类:有效推荐则为1、无效推荐则为 0 。我们认为用户打分在4.0 分及以上的 item 是有效推荐(5 分制),从而根据预测的二元标签和真实的二元标签得到precisionrecallauc 等指标。这种做法基于我们的观察:对于一个无效推荐的item,算法预测它是 1.5 分还是 2.5 分没有任何意义。

     

实验中我们使用 MAE 来报告实验结果,因为它最常用并且最容易直观的解释。另外我们每次随机选择不同的训练集和测试集,重复进行10-fold 交叉验证并报告MAE 的均值。

  1. baseline 模型:一个 User-Based CF 模型(基于 Pearson 最近邻算法 ),该模型召回全量的 user-user 相似度而不考虑计算代价。我们调优了该算法的超参数,从而得到最好的 Pearson 最近邻算法。

  2. 实验配置:我们首先将数据集划分为训练集和测试集 。在开始对不同算法进行全面的实验评估之前,我们确定了不同算法对不同超参数的敏感性,并从敏感性实验中确定了这些超参数的最佳值,并且将这些最佳超参数用于剩余的实验。

    为了确定超参数敏感性,我们仅使用训练集,并将其进一步细分为 “训练--训练集” 和 “训练--验证集”,并对其进行实验。

    所有的实验都是使用 C 语言实现,在基于 linuxPC 上运行实验。PC 配置为 600M HZIntel Pentium III 处理器以及 2GM 内存。

  3. 实验结果主要分为推荐质量结果和推荐性能结果两部分。为了得到较高的推荐质量,我们首先确定了一些超参数敏感性,包括:邻域大小 、训练集拆分比例 、不同的相似度度量。

  4. 超参数敏感性:为了确定各种超参数的敏感性,我们仅关注训练集,并将原始的训练集进一步拆分为 “训练--训练集” 和 “训练--验证集”。

    • 相似度算法的影响:我们实现了三种不同的相似度算法,包括基础的余弦相似度、修正的余弦相似度、相关性相似度,并在我们的数据集上测试它们。对于每种相似度算法,我们基于加权和算法来生成预测。实验结果如下图所示,我们给出了验证集的 MAE 。可以看到:修正的余弦相似度效果最好,因为它的 MAE 明显更低。因此,在接下来的实验中我们选择修正的余弦相似度。

    • 训练集测试集拆分比例的影响:为了确定数据集密度的敏感性,我们以 0.1 的增量将 的值从 0.2 增加到 0.9 。我们分别使用两种预测生成技术:最简单的加权和,以及基于回归的加权和。实验结果如下图所示。

      可以看到:预测质量随着 的增加而得到提高。对于较小的 ,基于回归加权和的方法更好;随着 的增加,基于简单加权和的方法反而更好。

      我们从曲线图中选择 作为后续实验的参数。

    • 邻域大小 :邻域大小 对预测质量有着显著的影响。 为了确定该参数的敏感性,我们针对不同 值得到了验证 MAE。我们分别使用两种预测生成技术:最简单的加权和,以及基于回归的加权和。实验结果如下图所示。

      可以看到:邻域大小 确实会影响预测的质量。但是这两种预测生成技术表现出不同的敏感性:当邻域大小从 10 增加到 30 时:

    • 简单加权和的方法的推荐质量一直得到改善,但是改善的速度逐渐降低,MAE 曲线趋于平缓。

      • 基于回归的加权和的方法推荐质量反而逐渐下降。

      我们选择 作为最佳邻域大小。

      注意:这里离线预计算 item-item 相似度时,保留全量的相似度(即模型大小 )。

  5. 推荐质量:一旦获得了最佳超参数,我们将User-Based CFIte-Based CF 进行比较,我们也比较了非个性化算法non-personalized (如推最热门的),结果如下所示。

    可以看到:

    • 简单加权和的 Item-Based CF 在所有 (邻域大小为30)、以及所有邻域尺寸( )上的表现都最好。例如在 (邻域大小为 30)时,User-Based CF 的测试 MAE = 0.755,而简单加权和 Item-Based CF 的测试 MAE = 0.749 ;而在邻域大小为 60) 时,User-Based CF 的测试 MAE = 0.732,而简单加权和 Item-Based CF 的测试 MAE = 0.726
    • 回归加权和的Item-Based CF 的表现比较有趣:它在非常小的 和非常小的邻域大小上战胜了其它两个算法。但是随着 的增加或者邻域尺寸的扩大,它的表现反而更差,甚至比 User-Based CF 效果都要差。
    • 我们还将我们的算法与朴素的非个性化算法进行了比较。

    我们从这些结果中得出两个结论:

    • 首先,简单加权和的Item-Based CF 算法在所有稀疏级别上都比 User-Based CF 算法提供更好的推荐质量。
    • 其次,回归加权和的Item-Based CF 算法在非常稀疏的数据集上表现更好,但是随着我们添加更多数据,推荐质量会下降。我们认为这是由于模型过拟合。

  6. 推荐性能:在表明Item-Based CF 算法比 User-Based CF 算法提供更好的预测质量之后,我们将重点放在可扩展性问题上。如前所述,Item-Based 的相似度更加静态,并允许我们预计算 item 邻居。模型的这种预计算具有一定的性能优势。为了提高系统的可扩展性,我们研究了模型大小 的敏感性,然后研究了模型大小对响应时间和吞吐量的影响。

  7. 推荐质量对模型大小 的敏感性:我们将相似度计算的 item 数量 25 增加到 200 ,增量为 25 。模型大小 意味着我们仅考虑 个最相似的 item 来构建模型,然后使用其中的 个用于预测生成过程,其中 。我们前面讨论的 等于全量的 item 。下图给出了不同 值在不同模型大小上的验证MAE 。另外我们还给出全量 的测试 MAE(虚线之后的最后一个点)。

    可以看到:

    • 随着 的增加,MAE 的值会改善,但是改善的效果逐渐降低。

    • 仅仅使用一小部分item 即可实现高准确性。在 时,我们保留 1.5% 的模型大小( 时,验证 MAE=0.754 )即可得到全尺寸模型( 时,MAE=0.72696% 的准确性;保留 3% 的模型大小( 时,验证 MAE=0.738 )即可得到全尺寸模型 98.3% 的准确率。

      这种模型大小敏感性具有重要的性能影响,这表明仅使用一小部分 item 来预计算 item 相似度很有效,并且仍然可以获得良好的预测质量。

  8. 模型大小 对于运行时间和吞吐量的影响:我们记录测试集生成预测结果所需要的时间,注意不同的 拥有不同的测试集大小。

    可以看到:小尺寸模型和全尺寸模型的预测结果生成时间存在很大差异。

    • (测试集大小 7.5 万) 的模型的运行时间为 2.002 秒,而全尺寸模型为 14.11 秒。
    • (测试集大小 2 万) 的模型的运行时间为 1.292 秒,而全尺寸模型为 36.34 秒。

    由于不同 的测试集大小不同,因此我们根据吞吐量重新绘制了下图。可以看到:

    • 时, 的模型1.487 秒完成 7 万个测试样本的打分,即 47361 个/秒,而全尺寸模型只有 4961 个/秒。
    • 时, 的模型吞吐量为 21505 个/秒,全尺寸模型只有 550 个/秒。

  9. 讨论:从 Item-Based CF 的试验评估中,我们得出了一些重要的观察:

    • 首先, Item-Based CF 比使用 User-Based CF 提供更好的预测质量。预测质量的提高在不同邻域大小 和训练集比例 上是一致的,但是改进并不显著。
    • 其次,item 邻域是相当静态的,可以预计算,这会导致非常高的在线性能。
    • 此外,model-based 方法可以只保留一小部分 item 并产生相当好的预估质量。我们的实验结果支持这一说法。因此, Item-Based CF 能够解决电商推荐系统中的两个最重要的挑战:预测质量和预测性能。

四、Amazon I-2-I CF[2003]

  1. 推荐算法以其在电商网站上的使用而闻名,这些算法使用有关用户兴趣的输入来生成推荐 item 列表。许多应用程序仅使用用户购买/评分的 item 来表示他们的兴趣,但是也可以使用其它属性,如浏览过的 item、人口统计数据 demographic data 、主题兴趣、最喜欢的艺术家等。在 Amazon.com,我们使用推荐算法为每位用户个性化在线商城 online store 。商城根据用户兴趣发生了根本性的变化:向软件工程师展示编程书籍、向新妈妈展示婴儿玩具。结果,点击率 click-through rate: CTR 和转化率 conversion rate: CVR (它们是 web-based 广告和 email 广告的效果指标) 大大超过了 untargeted 内容(如 banner 广告和热门列表)的点击率和转化率。

    电商推荐算法通常在具有挑战性的环境中运行。如:

    • 大型零售商可能有海量数据,如数千万用户、数百万的 item
    • 许多应用程序要求在不超过半秒的时间内实时返回结果集合,同时仍然能够产生高质量的推荐。
    • 新用户的信息通常极其有限,仅仅只有极少数的购买/评分记录。
    • 老用户的信息通常较大大,可能具有数以千计的购买/评分记录。
    • 用户数据易变:每次交互都提供有价值的用户数据,算法必须立即响应新信息。

    解决推荐问题的常用方法有三种:传统的协同过滤traditional collaborative filtering 、聚类模型cluster modelsearch-based 方法。在论文 《Amazon.com Recommendations: Item-to-Item Collaborative Filtering》 中,我们提出了item-to-item collaborative filtering ,并与这些方法进行比较。与传统的协同过滤不同,我们的算法的在线计算与用户数量、item 数量无关。我们的算法实时生成推荐,可以扩展到海量数据集,并生成高质量的推荐。

4.1 三种推荐方法

  1. 大多数推荐算法首先找到目标用户历史购买/评分 item 有重叠的一组用户(称作相似用户),然后算法聚合来自这些相似用户的历史购买/评分 item、剔除目标用户已购买/评分过的 item、并将剩余的 item 推荐给目标用户。这些算法的两个流行版本是协同过滤和聚类模型 cluster model

    其它的一些方法,包括 search-based 方法以及我们的 item-to-item 协同过滤方法,专注于寻找相似的 item 而不是相似的用户。对于用户购买/评分过的每个 item,这些方法都尝试找到相似的 item,然后聚合相似的 item 并进行推荐。

  2. 传统 Collaborative Filtering: CF:传统的协同过滤算法将用户表示为一个 item 空间的向量,其中 item 数量。向量的分量对于购买过的或者正面评价的 item 是正数、对于负面评价的 item 是负数。为了打压最热门的 item,该算法通常将向量分量乘以逆频率inverse frequency (购买/评价该 item 的用户数量的倒数),从而使得冷门的 item 更具相关性。对于几乎所有用户来说,这个向量都非常稀疏。

    该算法根据目标用户最相似的几个用户生成推荐。它可以通过多种方式衡量两个用户 的相似度。一种常用的方法是余弦相似度:

    一旦找到目标用户的相似用户,该算法使用各种方法从相似用户的 item 中选择推荐。一种常见的技术是根据相似用户购买的数量对每个 item 进行排序。

    为单个目标用户使用协同过滤生成推荐的计算成本很高。在最坏的情况下它是 ,其中 是用户数量、item 数量,因为它需要检查 个用户、每个用户最多 item 。然而,由于平均而言用户向量极其稀疏,因此算法的性能往往更接近

    • 扫描每个用户大约是 而不是 ,因为几乎所有用户向量都包含稀疏的 item(而不是 )。
    • 但是有些用户已经购买/评价了很大一部分 item,所以需要 处理时间。

    因此,该算法的最终性能约为 。即便如此,对于非常大的数据集,例如 1000 万或者更多的用户、100 万或者更多的 item , 算法会遇到严重的性能和可扩展性问题。

    这里评估的是单个用户的推荐性能,如果是所有用户那么算法性能为

    可以通过减少数据规模来解决可扩展性问题。我们可以通过随机采样用户、或者丢弃购买量少的用户从而降低 ,也可以通过丢弃非常热门或者非常冷门的 item 从而降低 。还可以通过基于 item 类别或者主题分类划分 item 空间,从而减少一定比例的 item 数量。诸如聚类或者 PCA 之类的降维技术可以将 或者 减少一个大的因子 factor

    不幸的是,所有这些降低数据规模的方法也以不同的方式降低了推荐质量。

    • 首先,如果算法仅检查了一小部分用户,那么所选择的相似用户与目标用户的相似度将有所下降(相比在全量用户中选择相似用户)。

      因为最相似的用户可能不在我们检查的一小部分用户中。

    • 其次,item 空间的划分使得推荐限制在特定类别或者主题的区域。

    • 第三,如果算法丢弃最热门或者最冷门的 item,那么这些 item 将永远不会被推荐到,只购买这些 item 的用户也将不会得到推荐。

    • 第四,应用于 item 空间的降维技术通过消除低频 item 往往也具有相同的效果(丢弃冷门 item )。

    • 第五,应用于用户空间的降维技术有效地将相似的用户分组,正如我们前面所描述的(仅检查了一小部分用户),这种聚类也将降低推荐质量。

  3. 聚类模型 Cluster Model :为了找到与目标用户相似的用户,聚类模型将用户集合划分为许多部分 segment,并将任务视为分类问题。该算法的目标是将用户分配到包含最相似用户的 segment 。然后,它使用 segment 中用户的购买/评级来生成推荐。

    这些 segment 通常是使用聚类或其它无监督学习算法创建的,尽管有一些应用程序使用人工确定的 segment 。使用一种相似性度量,聚类算法将最相似的用户分组在一起从而形成 segment 。由于对大型数据集进行最佳聚类是不切实际的,因此大多数应用程序使用各种形式的贪心聚类生成。这些算法通常从一组初始 segment 集合开始,每个 segment 通常包含一个随机选择的用户。然后,算法反复将用户与现有的 segment 匹配,通常会根据规则创建新的 segment 或者合并现有的 segment 。对于非常大的数据集,尤其是那些高维特征的数据集,采样或降维也是必要的。

    一旦生成了 segment 之后,算法会计算目标用户与每个 segment 的相似度,然后选择相似度最高的 segment 并相应地对目标用户进行分类。一些算法将目标用户划分到多个 segment,并描述目标用户与每个 segment 的关系强度。

    cluster model 比协同过滤具有更好的在线可扩展性和性能,因为它们将目标用户与可控数量的 segment、而不是整个用户集合相比较。复杂且昂贵的聚类计算是离线运行的。

    但是这种方法推荐质量较差。cluster model 将众多用户分组到一个 segment 中,将一个目标用户与一个 segment 相匹配,然后将 segment 中所有用户都考虑为目标用户相似的用户,从而进行推荐。因为 cluster model 找到的相似用户并不是最相似的用户,因此它们产生的推荐不太相关。可以通过使用大量的细粒度 segment 来提高推荐质量,但是在线的 user-segment 分类将变得几乎与使用协同过滤查找相似用户一样昂贵。

  4. 基于搜索search-based的方法:基于搜索或者基于内容的方法将推荐问题视为对相关 item 的搜索。给定用户购买/评分的 item,该算法构建一个搜索 query,从而查找同一作者、艺术家、导演、或者相似关键字或主题的其它热门 item。例如,如果用户购买教父 DVD 合集,那么系统可能会推荐其它犯罪剧、Marlon Brando 主演的其它作品、或者 Francis Ford Coppola 导演的其它电影。

    如果用户很少购买/评分,基于搜索的推荐算法的可扩展性和表现都很好。然而,对于购买量数以千计的用户而言,基于所有 item 进行 query 是不切实际的。该算法必须使用数据的子集或者 summary,从而降低质量。

    无论是哪种情况(用户购买量太少或者太多),推荐质量都相对较差。这些推荐通常要么太宽泛(例如,最畅销的戏剧 DVD 作品)、要么太狭隘(例如,同一作者的所有书籍)。推荐系统应该帮助用户找到和发现新的、相关的、和有趣的 item 。同一作者或者同一主题中的热门 item 无法实现该目标。

4.2 Item-to-Item CF

  1. Amazon.com 在许多电子邮件营销 campaign 和大多数网站页面(包括高访问量的 Amazon.com 主页)中使用推荐作为一个定向营销工具 targeted marketing tool 。点击 Your Recommendations 链接会将用户引导至一个区域,在这个区域中用户可以根据item 类别、主题类型来过滤推荐,并且对推荐的 item 进行评分、对用户历史购买的item 进行评分,以及了解推荐item 的推荐原因。如下图所示。

    下图为我们的购物车推荐,它根据用户购物车中的item为用户提供推荐建议。它该功能类似于超市收银台中的冲动商品 impulse item,但是我们的冲动商品针对每个用户个性化定制。

    Amazon.com 广泛使用推荐算法来根据每个用户的兴趣个性化其网站。由于现有的推荐算法无法扩展到 Amazon.com 的数千万用户和数百万 item,因此我们开发了自己的算法,即item-to-item 协同过滤 。我们的算法可以扩展到海量数据并实时生成高质量的推荐。

    即使现代的深度神经网络模型在预测用户个性化兴趣方面的能力远远超越了传统协同过滤模型,但是传统协同过滤模型在可解释性方面更好,这有助于引导用户接受和信任推荐系统,从而得到更好的转化。

  2. 工作原理:item-to-item 协同过滤不是将用户与相似用户进行匹配match,而是将用户购买/评分的每个item 与相似 item 进行匹配,然后将这些相似 item 组合到推荐列表中。

    为了确定目标 item 的最相似匹配,该算法通过查找用户共同购买的 item 来构建 similar-items table 。我们可以通过迭代所有 item,并为每对 item 计算相似度来构建 item-to-item 矩阵。然而,许多 item pair 没有共同的用户,因此该方法在计算时间和内存占用方面效率低下。以下迭代算法通过计算单个 item 与所有相关 item 之间的相似度,从而提供了更好的方法:

    可以通过多种方式计算两个 item 之间的相似度,但是一种最常用的方法是使用我们之前描述的余弦相似度,其中每个向量对应于一个 item 而不是一个用户,向量的 维对应于购买/评分了该 item 的用户。

    similar-items table 的这种离线计算非常耗时,最坏情况为 。然而,在实践中它更接近 ,因为大多数用户的购买量很少。对购买热门 item 的用户进行采样(热门 item 列向量的元素进行采样)会进一步降低运行时间,而推荐质量几乎没有降低。

    给定一个 similar-items table ,该算法找到与目标用户的每个购买/评分相似的 item,聚合这些 item,然后推荐最热门或最相关的 item。这种计算非常快,仅取决于用户购买/评分的 item 数量。

  3. 可扩展性:Amazon.com 拥有超过 2900 万用户和数百万个 item。几乎所有现有算法都是在小数据集上进行评估的。例如 MovieLens 数据集包含 35000 个用户和 3000item,而 EachMovie 数据集包含 4000 个用户和 1600item。对于非常大的数据集,可扩展的推荐算法必须离线执行最昂贵的计算。如前所述,现有方法存在不足:

    • 传统的协同过滤很少或者从不进行离线计算,其在线计算会随着用户数量和 item 数量而增加。该算法在大型数据集上是不切实际的,除非它使用降维、采样、或者划分 partitioning,而所有这些操作都会降低推荐质量。
    • cluster model 可以离线执行大部分计算,但是推荐质量相对较差。为了改进它,可以增加 segment 的数量,但是这又会使得 user-segment 分类变得代价昂贵。
    • search-based model 离线构建关键字、类别、作者的索引,但是无法提供有趣的、个性化的item 推荐。对于具有大量购买/评分的用户,该方法的可扩展性也很差。

    item-to-item 协同过滤的可扩展性和性能的关键在于它离线创建昂贵的 similar-items table 。该算法的在线部分(为用户的购买/评分 item 查找相似的 item)独立于 item 数量和用户数量,仅取决于用户购买/评分了多少个 item。因此,即使对于非常大的数据集,该算法也很快。由于该算法推荐高度相关的相似 item,所以推荐质量非常好。与传统的协同过滤不同,该算法在用户数据有限的情况下也表现良好,甚至可以基于少到两三个 item 来生成高质量的推荐。

五、Slope One Rating-Based CF[2005]

  1. 基于评分的协同过滤RatingBased CF 方法是从其它用户的评分中预估目标用户如何对目标商品进行评分的过程。一个理想的 RatingBased CF 需要满足以下条件:

    • 易于实现和维度:算法的可解释性强,并且易于实现和维护。
    • 即时更新:添加新的评分之后,模型能够立即更新预测。
    • 高性能:在线推荐速度应该非常快速,这可能需要以内存为代价。
    • 数据需求低:能够为评分数量较少的目标用户提供高质量的推荐。
    • 合理的推荐准确性:和效果最好的推荐相比具有可比的推荐质量,其中推荐质量的小幅提升并不值得牺牲简单性 simplicity 和可扩展性 scalability

    为此,论文 《Slope One Predictors for Online Rating-Based Collaborative Filtering》 提出的 Slope One 算法满足上述五个目标。论文的目标并不是比较各种 CF 算法的准确性,而是证明 Slop One 算法可以同时满足这五个目标。相比之下,其它的一些 CF 方法追求其中的一部分目标而牺牲了另外一些目标。

    Slope One 算法的基本思想是:不同item 之间的流行度差异 popularity differential 。我们以 pair 对的方式来决定item item 要好多少,从而计算流行度差异。一种简单的计算方式是:用item 的评分减去item 的评分。反之,如果已知item 的评分,以及 的流行度差异,那么item 的评分就可以计算到。

    考虑下图中的两个用户 以及item 。用户 item 评分 1 分、用户 item 评分 2分、用户 item 评分 1.5 分。我们观察到item item 的评分更高,差异在 1.5 - 1 = 0.5 分,因此我们预计用户 将给item 的评分为 2 + 0.5 = 2.5 分。我们称 为目标用户,item 为目标商品。

    对于每个未知的评分,在训练集中存在大量的这种差异,则我们可以取这些差异的均值。Slop One 算法提供了三种方式来选择差异,并最终得到单个预测结果。Slope One CF 的预测形式为 ,其中 为平均的流行度差异。

    论文的主要贡献是提出了一个 Slope One CF 算法,并证明它和 memory-based 算法相比具有几乎相同的准确性,同时更适合 CF 任务。

  2. 相关工作:

    • MemoryBased CF 使用 u-2-u 相似性来执行预测,其中相似函数的选择决定了推荐的质量。其缺点包括:

      • 可扩展性scalabilityMemoryBased CF 依赖于的 u-2-u 相似性计算复杂度太高,而这些计算无法通过离线预计算。
      • 数据稀疏的敏感性 sensitivity :为满足推荐的高质量,MemoryBased CF 要求最低数量的用户(如至少 100 个用户)、最低数量的评分(如至少 20 个评分)。

      本文中我们将 Slope One CF 和众所周知的 MemoryBased CF 算法 Pearson 进行对比。

    • 也有一些 ModelBased CF,如基于线性代数的方法(如SVD、PCA)、基于机器学习的方法(如贝叶斯方法)、基于神经网络的方法、基于聚类的方法。与MemoryBased CF 相比,ModelBased CF 在线计算的性能很高,但是它们具有昂贵的离线学习阶段或者离线更新阶段。当在线速度至关重要时,ModelBased CF 算法相比 MemoryBased CF 更可取。

    • 我们的 Slope One CF 的形式为:,其中 为常数、 表示评分变量,因此该方法叫做 slope one 。对于任何 item pair 对,我们试图找到从一个 item 评分中预测另一个 item 评分的最佳函数 ,不同 item pair 的函数 可能不同。

      • 《Item-based collaborative filtering recommender algorithms》 中,作者考虑了 item pair 之间的相关性,然后将用户评分的加权均值作为评分变量,其中权重为相关系数。

        在该论文的简单版本中,预估形式为 ;在该论文的回归版本中,预估形式为

      • 在论文 《A regression-based approach for scaling-up personalized recommender systems in e-commerce》 中,作者也使用了 形式的预估。

      这两篇论文工作的一个自然扩展是考虑 形式的预估。相反,本文中我们使用形式为 的预估。在 《A regression-based approach for scaling-up personalized recommender systems in e-commerce》 中观察到,即使他们使用基于回归的 算法也没有导致相对 MemoryBased CF 算法的较大改进。因此,证明 形式的预估可以与 MemoryBased CF 算法竞争,这是本文的一个重要结果。

5.1 模型

  1. 给定用户 ,定义他/她的评分 array 记作:

    其中第 个元素 对应于item 的评分。由于存在大量的未评分item ,因此这个向量是不全的 incomplete

    定义用户 评分的所有item,用户 的平均打分为

    定义训练集的所有评分 array ,其中 为所有用户。

    定义 为包含item 的用户集合 : 。定义同时包含item 的用户集合为: 。定义用户 共同评分的item 集合为:

    定义预测 ,其中每个元素代表一个预测结果。

  2. RatingBased CF 在线预测时, 首先提供一个评分 array (称作 query array), 它包含用户的所有评分item ;模型返回一个预测array(称作 response array),其中包含用户尚未评分的item 及其预估的评分。

5.1.1 baseline

  1. 最简单的 baselinePER USER AVERAGE

    即:预测用户的所有未评分item 的评分为该用户的评分均值。

  2. 针对PER USER AVERAGE 的一种改进方式为 BIAS FROM MEAN(也被称作 NON PERSONNALIZED),其预测结果为:

    它考虑了用户 的评分均值,以及所有其它用户在该item 上的评分差异(其它用户在该 item 上的评分减去用户平均均值)。

  3. 基于MemoryBased CF 的一个经典实现是 PEARSON 方案:

    它在 BIAS FROM MEAN 的基础上考虑了用户 之间的相似性。其中 Pearson 相关系数,它刻画了用户之间的相似性:

    其中 Case Amplification 系数,它降低了数据中的噪音。

    • 如果相关系数很高,如 corr = 0.9,则经过 Case Amplification 之后它仍然很高:
    • 如果相关系数很低,如 corr = 0.1,则经过 Case Amplification 之后它可以忽略不计:

    尽管存在更准确的方法,但是 PEARSON 相关系数以及 Case Amplification 一起已经能够提供相当好的推荐质量。

  4. 采用 adjusted cosine 相似度的 ItemBased CF :给定item ,定义相似度为:

    使用基于回归Regression 的预测为:

    其中 为回归系数,它根据最小化目标来求得:

5.1.2 Slope One

  1. slope one 方法同时考虑了来自相同 item 的其它用户的评分(就像ItemBased CF )、来自相同用户的其它 item 的评分(就像 MemoryBased CF),除此之外slope one 方法还依赖于既不是相同 item 、也不是相同用户的那些评分。因为这些评分数据都有助于我们进行预测。

    slope one 方法的大部分优势都来自于 ItemBased CFMemoryBased CF 未考虑的数据。

  2. 给定用户 ,我们寻找最佳的预测器 predictor 来从 的评分中预测 的评分。

    slope one 方法选择的 predictor 为斜率为1 的线性函数 ,这就是名字 slope one 的由来。 具体而言,我们需要拟合方程:

    我们通过最小化残差:

    通过残差的偏导数为0,我们得到:

    因此 是用户 的评分差异的均值。

  3. 类似地,我们可以通过利用item 的评分来预测item 的评分。同样的推导过程,我们有: