Question

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 model、search-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：传统的协同过滤算法将用户表示为一个 $ N $ 维 item 空间的向量，其中 $ N $ 为 item 数量。向量的分量对于购买过的或者正面评价的 item 是正数、对于负面评价的 item 是负数。为了打压最热门的 item，该算法通常将向量分量乘以逆频率inverse frequency （购买/评价该 item 的用户数量的倒数），从而使得冷门的 item 更具相关性。对于几乎所有用户来说，这个向量都非常稀疏。

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

   $ \text{sim}(A,B) = \cos\left(\mathbf{\vec A},\mathbf{\vec B}\right) = \frac{\mathbf{\vec A}\cdot \mathbf{\vec B}}{\|\mathbf{\vec A}\|\times \|\mathbf{\vec B}\|} $

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

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

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

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

   这里评估的是单个用户的推荐性能，如果是所有用户那么算法性能为 $ O(M\times (M+N)) $ 。

   可以通过减少数据规模来解决可扩展性问题。我们可以通过随机采样用户、或者丢弃购买量少的用户从而降低 $ M $ ，也可以通过丢弃非常热门或者非常冷门的 item 从而降低 $ N $ 。还可以通过基于 item 类别或者主题分类划分 item 空间，从而减少一定比例的 item 数量。诸如聚类或者 PCA 之类的降维技术可以将 $ M $ 或者 $ N $ 减少一个大的因子 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 之间的相似度，从而提供了更好的方法：

   
   xxxxxxxxxx
   41
   遍历 item 集合，对集合中的每个 item i1 :2
       遍历购买/评分 i1 的用户集合，对集合中的每个用户 u:3
           遍历用户 u 购买/评分的 item 集合，对集合中的每个 item i2 ，记录 pair (i1,i2)4
       对每个 pair (i1,i2)，计算它们之间的相似度

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

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

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

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

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

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