推荐系统-传统算法

一、Tapestry

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

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

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

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

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

    协同过滤通过记录人们对于他/她所阅读文档的反应来协同从而帮助彼此进行过滤,这种反应可能是文档特别有趣(或者特别无趣)。这些反应(通常也被称作注解 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

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

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

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

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

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

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

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

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

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

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

    其中:

    • 是归一化的相似性,它衡量了用户 的评分对于 的贡献。

    • 评分 不仅受到用户 对文章 的偏好的影响,还受到用户 整体打分的影响。如,有的用户倾向于都打高分,有的用户倾向于都打低分。

      因此这里通过 来剔除整体性偏好的影响,得到文章 的偏好。

三、ItemBased CF

  1. 随着信息数量和用户规模的剧烈增长,传统的UserBased CF 面临两个挑战:

    • 可扩展性scalabilityUserBased CF 能够实时搜索成千上万的相似用户,但是现代系统要求实时搜索千万甚至亿级的相似用户。UserBased CF 的整体计算复杂度为 ,其中 为平均每个用户评分的item 数量,因此随着用户规模的增加,其计算复杂度难以忍受。

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

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

      由于绝大多数用户有行为的 item 非常稀疏,占比甚至低于 1% ,因此基于 UserBased CF 的推荐可能无法为用户提供任何有效的推荐,使得推荐的质量非常差。

    某种程度上这两个挑战是相互冲突的:算法花费在搜索相似用户的时间上越少,则它的可扩展性越强,但是推荐质量越差。论文 《Item-Based Collaborative Filtering Recommendation Algorithms》 提出了 ItemBased CF 来同时解决这两个挑战。

  2. ItemBased CF 首先探索item 之间的相似性,而不是user 之间的相似性;然后向用户推荐她/他喜欢的 item 类似的 item

    因为item 之间的关系是相对静态的(相对于user 之间的关系),所以基于 item 的算法可以预计算item-item 相似性,从而减少在线计算的数量,同时保持较高的推荐质量。

  3. TapestryUserBased CF 的最早实现,该系统依赖于关系紧密的社区内部用户的明确意见,其中每个用户都了解其它用户。但是大型社区的推荐系统不能依赖于每个用户都了解其它用户。

  4. UserBased CF 的基本思想是:根据其它志趣相投用户的意见来推荐。

    ItemBased CF 的基本思想是:根据用户之前喜欢过的 item 来推荐类似的item

3.1 模型

  1. 假设有 个用户 以及 item 。每个用户 有一个 item 评分列表 ,这个列表上用户有过评分,其中 且有可能是空的。

    给定用户 ,协同过滤算法任务包含两种形式:

    • 预测:预测用户 对于item 的评分

    • 推荐:为用户 推荐他/她可能最喜欢的由 item组成的列表 ,且

      这被称作 Top-N 推荐。

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

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

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

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

    • model-based 基于模型的(也称作 item-based):通过建立用户打分模型(如回归模型、knn 模型)来提供item 推荐。这些模型首先根据打分矩阵来训练,然后根据给定用户在其它item 评分的条件下来预测未打分item 上的评分。

  3. ItemBased CF 方法选择目标用户 已经评分的item 集合 ,然后计算评分集合中的每个 item 和未评分集合 中每个 item 的相似度,然后选择 个最相似的、未评分的 item ,并记录对应的相似度。

    一旦得到最相似的item 及其相似度,我们可以通过目标用户对这些相似item 的加权均值来执行预测。

  4. ItemBased CF 最关键的步骤之一是如何计算 item 之间的相似度。计算item 之间相似度的基本思想是:首先挑选既对 打分、又对 打分的用户 ,然后基于这些用户的打分来计算相似度

    下图给出了这一过程,其中矩阵的行代表user、列代表 item 。其中有多种方法可以计算 item 之间的相似度,我们这里介绍三种方法:

    • 基于余弦的相似度cosine-based similarity

      其中我们只考虑

    • 基于相关性的相似度correlation-based similarity

      其中 item 上的打分均值, item 上的打分均值。

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

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

  5. 一旦我们根据相似性得到了目标item 最相似的一组item,则下一步是为用户执行打分预测。这里我们考虑两种技术:

    • 加权和 weighted sum:该方法通过用户已经评分的 item 中,根据和 的相似度进行加权得到预测结果。

      假设用户 已经评分,且与 相似的 item 集合为 ,则有:

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

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

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

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

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

  6. UserBased CF 中,邻域的生成过程,尤其时user-user 相似度计算步骤被证明是性能瓶颈,从而使得整个过程不适合实时推荐。

    这里我们基于两阶段方式来提高scalability:邻域生成过程和预测步骤进行分离。

    • 邻域生成过程:在典型的电子商务场景中,与经常变化的用户数量相比,item 数量相比之下更为静态staticitem 的静态属性使得我们想到了预计算item 相似性的想法。

      预计算 item 相似性的一种可能方法是:计算所有item 之间的相似度,然后执行快速查表从而检索到所需的相似度。尽管节省时间,但是该方法需要 的空间复杂度。

      事实上对于任何一个目标item,我们只需要一小部分最相似的 item 来预测。因此对于每个 item,我们仅计算 个最相似的 item,其中 。我们称 为模型大小。

    • 预测过程:当用户 item 进行预测时,首先获取item 预计算的 个最相似的 item;然后选择这 item 中、哪些被用户 有过打分;最后基于这些打分的 item 来执行 ItemBasec CF 预测算法。

  7. 我们观察到推荐质量quality 和 推荐性能 performance 的折衷。为了确保高质量,我们必须有较大的模型大小 ,而这会导致推荐的实时性问题。

    ItemBased CF 在邻域生成步骤可以确保我们保留最相似的item,在预测步骤这些item 对预测得分的贡献最大。因此即使使用比较小的模型大小 ,我们的方法也能够提供合理的、良好的推荐质量。

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

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

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

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

3.2 实验

  1. 我们使用MovieLens 数据集来评估ItemBased CF 的效果。MovieLens 数据集于 1997 年球季首次公开,该数据集包含 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.5 分及以上的 item 是有效推荐(5 分制),从而根据预测的二元标签和真实的二元标签得到precisionrecallauc 等指标。这种做法基于我们的观察:对于一个无效推荐的item,算法预测它是 1.0 分还是 1.5 分没有任何意义。

    实验中我们使用 MAE 来报告实验结果,因为它最常用并且最容易直观的解释。

    另外我们每次随机选择不同的训练集和测试集,重复进行10-fold 交叉验证并报告MAE 的均值。

  3. baseline 模型:一个 UserBased CF 模型,该模型召回全量的 user-user 相似度而不考虑计算代价。

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

  5. 为了确定各种参数的敏感性,我们仅关注训练集,并将原始的训练集进一步拆分为训练集和测试集。

    • 不同的相似性度量:从不同相似性度量比较的结果可以看出:在余弦相似度计算中减去用户打分均值具有明显的优势,因此我们在剩余的实验中选择 adjusted cosine similarity

    • 不同的训练集测试集拆分比例:我们分别使用两种预测生成技术:最简单的加权和,以及基于回归的加权和。从实验结果看出:预测质量随着 的增加而得到提高。对于较小的 ,基于回归的方法更好;随着 的增加,基于简单加权和的方法反而更好。

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

    • 邻域大小 :我们分别使用两种预测生成技术:最简单的加权和,以及基于回归的加权和。从实验结果可以看出:邻域大小会影响推荐的质量。当邻域大小从 10 增加到 30 时:

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

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

      注意:这里离线预计算 item-item 相似度时,保留全量的相似度。

  6. 一旦获得了最佳参数,我们将UserBased CFItemBased CF 进行比较,我们也比较了非个性化算法non-personalized (如推最热门的),结果如下所示。

    可以看到:

    • ItemBased CF 在所有 (邻域大小为30)、以及所有邻域尺寸( )上的表现都最好。这表明 ItemBased CF 的推荐质量比 UserBased CF 要更好。

    • 基于回归的加权和的ItemBased CF 在非常小的 和非常小的邻域尺寸上战胜了其它两个算法。但是随着 的增加或者邻域尺寸的扩大,它的表现反而更差,甚至比 UserBased CF 效果都要差。

      这表明基于回归的加权和的ItemBased CF 在稀疏数据上的表现更好,而在稠密数据上很容易遭受过拟合。

  7. 考虑到item 的相似度更为静态,这允许我们离线预计算item 的邻域。为了使系统更具有扩展性,我们拆分了离线邻域大小 (也称作模型大小)和在线邻域大小 。模型大小 用于离线预计算 item 时,确定每个 item 需要保留多少个最相似的 item;在线领域大小 用于生成推荐时,为每个item 保留多少个最相似的 item 。其中有 。我们前面讨论的 等于全量的 item

    会影响预测生成中的 的大小。当 较小时,item 的离线邻域规模较小,这使得用户 存在评分、且位于item 离线邻域的 item 规模较低。在线预测时进一步的从 中挑选 个来进行预测。因此 会影响推荐的质量。

    我们将 25 为步长从 25 增加到 200,观察实验效果。可以看到:

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

    • 仅仅使用一小部分item 即可实现很好的效果。在 时,我们保留 1.5% 的模型大小即可得到全尺寸模型96% 的准确率;保留 3% 的模型大小即可得到全尺寸模型 98.3% 的准确率。

      这表明仅使用一小部分 item 来预计算 item 相似度很有效,并且仍然可以获得良好的预测质量。

  8. 我们记录测试集生成预测结果所需要的时间,注意不同的 拥有不同的测试集大小。

    可以看到:小尺寸模型和全尺寸模型的预测结果生成时间存在很大差异。当 (测试集大小 7.5 万) 的模型的运行时间为 2.002 秒,而全尺寸模型为 14.11 秒;当 (测试集大小 2 万) 的模型的运行时间为 1.292 秒,而全尺寸模型为 36.34 秒。

    由于不同 的测试集大小不同,因此我们根据吞吐量重新绘制了下图。可以看到:当 时, 的模型1.487 秒完成 7 万个测试样本的打分,即 47361 个/秒,而全尺寸模型只有 4961 个/秒。 当 时, 的模型吞吐量为 21505 个/秒,全尺寸模型只有 550 个/秒。

四、Amazon I-2-I CF

  1. Amazon 使用推荐算法为每个用户进行个性化推荐,个性化推荐的点击率和转化率大幅超过banner 广告商品和非个性化推荐商品(热门推荐)。

  2. 电商网站的个性化推荐面临以下的挑战:

    • 数据规模巨大。如数千万用户、数百万商品。
    • 性能要求高。要求在不超狗 0.5 秒内实时返回推荐结果,并保证推荐质量。
    • 冷启动。新用户几乎没有什么商品上的行为。
    • 实时更新。用户的行为数据时刻在变,每个user-item 行为都具有价值,因此算法需要立即对新的信息做出响应。
  3. 有三种解决推荐问题的常用方法:

    • 传统协同过滤(user-based CF):传统的协同过滤算法将用户表示为商品的 维向量,其中 为商品规模。向量的元素为:已经购买或者评分正向的元素为正数;评分负向的元素为负数。

      为了惩罚最畅销的商品,user-based CF 也可以将向量的分量乘以倒频(购买或评论该商品的用户数量的倒数),从而打压热门商品、提升长尾商品的相关性。

      user-based CF 算法根据和用户最相似的一批用户来生成推荐。它可以通过各种相似度来衡量用户 的相似度,其中最常用的为余弦相似度:

      有多种方式从相似用户的商品中选择推荐。一种常用的技术是:根据相似用户购买的数量对这些商品进行排名,然后选择 top K 排名的商品。

      user-based CF 的计算代价太高。最坏情况下为每个用户进行推荐的计算复杂度为 ,因为它需要检查 个全量的相似用户,每个相似用户检查 个全量商品。

      由于用户向量非常稀疏,平均而言该算法的复杂度接近 。因为对于 个全量的相似用户,平均只需要检查极少数的商品,因此需要 的处理时间。但是可能某些用户购买或者评论了很大比例的商品,因此对于这极少数用户需要 的处理时间。但是即使如此,对于非常大的数据集,该算法仍然面临严重的性能问题和可扩展问题。

      可以通过降低数据规模来缓解可扩展问题。我们可以通过随机抽样用户、或者丢弃购买次数很低的用户来降低 , 可以通过丢弃太热门或者太冷门的商品来降低 。也可以基于产品类别或者主题分类对商品空间进行划分,从而将 降低到一个很小的值。最后,通过聚类和 PCA 降维等技术也可以很大程度上减少 或者

      但是这些方法以多种方式降低了推荐质量。

      • 首先,如果该算法仅检查少量用户,那么所选择的用户和当前用户可能不太相似,太相似的用户已经在降低数据规模的过程中被丢弃了。
      • 其次,商品空间划分将推荐的商品限定在特定的产品类别或者主题类别。
      • 然后,如果算法丢弃了最热门或者最冷门的商品,那么这些商品永远不会出现在推荐列表中。并且仅购买这些商品的用户也永远得不到推荐。
      • 在商品空间中进行降维从而移除低频成分,其效果和丢弃冷门商品类似。
      • 在用户空间中进行降维可以有效的将相似用户进行聚类,这回把购买次数偏低的用户丢弃,从而很可能丢弃了相似的用户。
    • 聚类模型:为了找到和目标用户相似的用户,聚类模型将用户划分到不同的组,并将任务视为分类问题。任务的目标是:将用户分配到包含最相似用户的簇中,然后使用该簇的用户购买/评分信息来产生推荐。

      聚类模型的簇可以人工生成,但是大多数情况下都是通过聚类算法或者其它无监督学习算法来构建。给定一种相似度计算方式,聚类算法将最相似的用户聚集在一起从而形成簇。

      一旦算法生成了簇,那么给定目标用户,聚类模型计算目标用户和每个簇的相似性,并将目标用户划分到该簇中。也有算法将用户划分到多个簇中,然后给出目标用户和每个簇的相关性。

      聚类模型比协同过滤具有更好的可扩展性和在线性能,因为它将每个用户和数量有限的簇进行比较,这相当于大幅降低了 的规模。而计算耗时的聚类算法是在离线完成计算。

      这种方法的推荐质量很低。聚类模型将大量用户聚合到一个簇中,然后将簇中所有用户都视为目标用户的相似用户。事实上,这些用户不一定都是目标用户的相似用户,因此降低了推荐质量。

      可以通过使用大量细粒度的簇来提高推荐质量,但是这时候在线的分类任务(将目标用户划分到最相似的簇)几乎与user-based CF 寻找相似用户的代价一样大了。

    • 基于搜索(基于内容):基于搜索或者基于内容的方法将推荐问题视为相关商品的搜索。

      给定用户购买/评分的商品,该算法会构建搜索query,从而寻找同一个作者、艺术家、导演、相似关键词、相同主题对应的热门商品。

      如果用户购买/评分的商品很少,那么基于搜索的推荐算法的可扩展性和性能会很好。但是对于有数千次购买的用户,对他/她购买过的商品全部进行 query-based 推荐是不切实际的,这需要使用这批商品的子集或者summary(如一些共同的属性),从而降低推荐质量。

      在所有情况下,推荐效果通常相对较差。推荐通常会过于笼统(如最畅销的喜剧 DVD),或者过于细化(如同一作者的所有书籍)。推荐应该帮助用户发现和挖掘新的、相关的、有趣的商品。同一作者、同一主题类别中的热门商品往往无法实现此目标。

  4. Amazon 拥有超过 2900万用户和数百万商品(2003年),目前已有的推荐算法无法扩展到如此规模的数据集,因此 Amazon 开发了自己的 item-to-item 推荐算法:《Amazon.com Recommendations Item-to-Item Collaborative Filtering》

    Item-to-Item CF 的在线计算量和用户数量无关,也和商品数量无关,因此可以扩展到海量商品,并且可以实时产生高质量的推荐。

  5. Item-to-Item CF 根据用户购买/评分的每个商品匹配到最相似的商品,然后将这些相似的商品向该用户推荐。为了确定商品的最佳匹配,算法首先需要构建商品之间的相似度矩阵。

    考虑到很多 item pair 对之间没有共同用户,因此该方法在计算复杂度和空间复杂度上的效率较低。Item-to-Item CF 提出了一个更好的方法来计算所有商品pair 对之间的相似度:

    for 商品集合的每个商品

    for 购买商品 的每个用户

    for 用户 购买的每个商品 :记录用户 同时购买了商品

    for 每个商品 :计算 之间的相似度

    有多种方式来计算商品之间的相似度,最简单的方式是余弦相似度,其中每个向量对应一个商品,向量的维度为购买该商品的用户数量。

    上述离线计算商品相似度矩阵的步骤非常耗时,最坏情况下为 的计算复杂度。但是,实际上由于大多数用户购买的商品很少,因此它更接近于

    另外,通过对热门商品的用户进行采样,则进一步降低了计算复杂度,而推荐质量几乎没有下降。

  6. 一旦给定相似度矩阵,则 Item-to-Item CF 算法将查找与用户购买/评论中每个商品相似的商品,然后汇总这些相似商品并推荐最热门或者相关性最高的商品。这种计算速度非常快,通常仅取决于用户购买/评论的商品数量。

  7. Item-to-Item CF 可扩展性和高性能的关键在于:离线进行复杂的商品相似度矩阵计算,而在线部分的计算复杂度和商品数量、用户数量无关,仅取决于用户购买/评论的商品数量。

    由于算法会推荐高度相关的相似商品,因此推荐质量非常高。

五、Slope One Rating-Based CF

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

    • 可扩展性scalabilityMemoryBased CF 依赖于的 u-2-u 相似性计算复杂度太高,而这些计算无法通过离线预计算。
    • 数据稀疏的敏感性 sensitivity :为满足推荐的高质量,MemoryBased CF 要求最低数量的用户(如至少 100 个用户)、最低数量的评分(如至少 20 个评分)。
  2. 也有一些 ModelBased CF,如基于线性代数的方法(如SVD、PCA)、基于机器学习的方法(如贝叶斯方法)、基于神经网络的方法、基于聚类的方法。与MemoryBased CF 相比,ModelBased CF 在线计算的性能很高,但是它们具有昂贵的离线学习阶段或者离线更新阶段。

  3. 论文 《Slope One Predictors for Online Rating-Based Collaborative Filtering》 提出了 RatingBased CF 方法。

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

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

    论文的目标并不是比较各种 CF 算法的准确性,而是证明 Slop One 算法可以同时满足这五个目标。相比之下,其它的一些 CF 方法追求其中的一部分目标而牺牲了另外一些目标。

  4. Slope One 算法的基本思想是:不同商品之间的评分差异 。

    我们以 pair 对的方式来决定商品 比商品 要好多少,从而计算评分差异。一种简单的计算方式是:用商品 的评分减去商品 的评分。反之,如果已知商品 的评分,以及 的热度差异,那么商品 的评分就可以计算到。

    考虑下图中的两个用户 以及商品 。用户 给商品 评分 1 分、用户 给商品 评分 1分、用户 给商品 评分 1.5 分。

    我们观察到商品 比商品 的评分更高,差异在 1.5-1=0.5 分,因此我们预计用户 将给商品 的评分为 2 + 0.5 = 2.5 分。我们称 为目标用户,商品 为目标商品。

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

5.1 模型

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

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

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

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

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

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

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

5.1.1 baseline

  1. 最简单的 baselinePER USER AVERAGE

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

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

    它考虑了用户 的评分均值,以及所有其它用户在该商品上的评分和其它用户在该商品上的均值的差异。

  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 :给定商品 ,定义相似度为:

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

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

5.1.2 Slope One

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

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

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

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

    我们通过最小化残差:

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

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

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

    给定训练集 ,以及任意两个商品 ,我们定义商品 到商品 的平均偏移为:

    因此在给定 的条件下, 的预测值为:

    考虑所有这样的 ,因此用户 在商品 上的 predictor 定义为:

    其中 ,即:用户 同时评分的、且与 有共同评分用户的商品的集合。

    当数据足够稠密,即几乎所有商品 pair 对之间都有评分时,有: 。考虑到:

    因此有:

    可以看到:slope one 方法不依赖于用户对具体商品的评分,而依赖于用户的平均评分,以及用户对哪些商品进行评分。

  4. slop one 方法的关键数据是商品之间的偏移矩阵:

    其中

    偏移矩阵 可以预计算,并且当有新数据进来时实时更新。

  5. ItemBased CF 中,我们需要根据相似商品的评分来给出结果。

    • 朴素版本的 predictor 可以视作 的加权聚合结果:

    • 基于回归的predictor 可以视为 的加权聚合结果:

    slope one 方法采用 的聚合结果,但是没有使用相似性进行加权:

    事实上可以进一步的扩展到