【论文阅读】推荐算法之基础 Amazon.com Recommendations Item-to-Item Collaborative Filtering

写在前面：

基于位置的业务场景和不考虑位置信息只考虑相关性或者说相似程度的业务场景，使用item2item的方式还不太一样。举个例子，餐饮中，用户吃饭，不会跑个三五十公里，就算三五十公里外的那个item与用户之前喜欢的item相似度很高，我觉得用户应该不会过去。因此基于位置的业务场景，很大一部分需要考虑距离因素，那么可行的一条路便是：在构建item2item的相似矩阵时，加入距离元素。具体如何加入，怎样设置权重值，根据业务理解，可调整设置。比如用户超级喜欢item0，现在有个item1，距离item0是1km，相似度为0.6；有个item2，距离item0是8km，相似度是0.9，那么此时用户距离item0很近的情况下，基本会去item1就餐。

概要：

该文章发表于2003年.

背景：

推荐算法以其在电子商务网站的用途而著称，它们利用有关一个顾客的兴趣作为输入，来产生一个推荐商品的列表。很多应用仅仅使用顾客购买并明确表示代表其兴趣的商品，但它们也可以利用其他属性，包括已浏览的商品、人口统计特征数据、主题兴趣，以及偏爱的艺术家。

解决的问题：

对每位顾客提供在线商店个性化。

采用的方法：

与把当前用户匹配到相似顾客的做法不同，商品到商品的协同过滤，把该用户所购买和评级的商品，匹配到相似的商品，然后组合这些相似的商品进入推荐列表。

难点：

创新点：

在线计算规模，与顾客数量和产品目录中的商品数量无关，实时产生推荐，计算适应海量数据集，并生成高质量的推荐

结果：

翻译：

摘要

推荐算法以其在电子商务网站的用途而著称，它们利用有关一个顾客的兴趣作为输入，来产生一个推荐商品的列表。很多应用仅仅使用顾客购买并明确表示代表其兴趣的商品，但它们也可以利用其他属性，包括已浏览的商品、人口统计特征数据、主题兴趣，以及偏爱的艺术家。

在Amazon.com，我们利用推荐算法，对每位顾客提供在线商店个性化。在顾客兴趣的基础上，商店有了彻底的改观，向一个软件工程师展示编程类标题，向一位新妈妈展示婴儿玩具。点击率和转化率——基于网络和邮件广告的两个重要评估指标——极大地超越了那些未定向内容，比如banner广告和热卖列表。

电子商务推荐算法经常要运行在一个充满挑战的环境里。例如：

• 大型零售商有海量的数据，以千万计的顾客，以及数以百万计的登记在册的不同商品。
• 许多应用要求结果实时返回，在半秒之内，还要产生高质量的推荐。
• 新顾客很典型，他们的信息很有限，只能以少量购买或产品评级为基础。
• 较老的顾客信息丰沛，以大量的购买和评级为基础。
• 顾客数据不稳定：每一次交互都可提供有价值的顾客数据，算法必须立即对新的信息作出响应。

解决推荐问题有三个通常的途径：传统的协同过滤，聚类模型，以及基于搜索的方法。在此，我们就这些方法与我们的算法——我们称之为商品到商品的协同过滤——进行对比。与传统协同过滤不同，我们算法的在线计算规模，与顾客数量和产品目录中的商品数量无关。我们的算法实时产生推荐，计算适应海量数据集，并生成高质量的推荐。

推荐算法

大多数推荐算法，都始于先找出一个顾客集合，他们买过和评级过的商品，与当前用户买过和评级过的商品有重叠。算法把来自这些相似顾客的商品聚集起来，排除该用户已经购买过或评级过的商品，并向该用户推荐其余的商品。这些算法有两个最常见的版本：协同过滤和聚类模型。其他算法——包括基于搜索的方法以及我们自己的商品到商品协同过滤——都集中于寻找相似的商品，而不是相似的顾客。针对用户所购买和评级的每一件商品，算法试图找到相似的产品，然后聚集这些相似的商品，并给予推荐。

传统的协同过滤

传统的协同过滤算法把顾客描绘成商品的N维向量，其中N是登记在册的不同商品的数量。对于买过或正面评级的商品，向量分量为正，对于负面评级的商品，向量分量为负。为弥补最热卖的商品，算法典型地会把向量分量乘以反向频率（已购买或评级该商品的顾客数量的倒数），以使不太知名的商品更加相关3。对几乎所有的顾客来说，这个向量非常稀疏。在与该用户最相似的少数顾客基础上，算法产生推荐。算法能够测量两个顾客的相似性，如A和B，有多种方式；一种常见的方法是测量这两个向量之间的夹角余弦值：

算法也能从相似顾客的商品里选择推荐，有多种可以利用的方法，常见的一种技术是，按照购买该商品的相似顾客数量，对每件商品进行排序。利用协同过滤来产生推荐，很耗计算。最坏的情况是O(MN)，其中M是顾客数量，N是产品目录中商品的数量，因为算法要验算M个顾客，并且对每个顾客最多要计算N种商品。但是，由于顾客向量的平均值很稀疏，算法的执行更倾向于接近O(M +N)。扫描每一个顾客大约是O(M)，而不是O(MN)，因为几乎所有顾客向量都只含有很少的商品，无需考虑产品目录的规模。但有少数顾客，他们买过或评级过的商品在产品目录中占有值得注意的百分比，需要O(N)处理时间。因此，算法最终执行的大约是O(M + N)。尽管如此，对非常大的数据集来说——比如1千万以上的顾客，以及1百万以上登记在册的商品——算法也会遭受严峻的性能和计算量问题。

通过减小数据量，可能部分缓解这些计算量的问题。我们能够减小M，通过对顾客进行随机抽样，或丢弃那些购买很少的顾客；我们也能减小N，通过丢弃那些极热门和极冷门的商品。我们还可能减少所需计算的商品数量，通过一个小的常数因子，在产品类别或主题分类的基础上，对商品空间进行区隔。诸如聚类和主分量分析等维度降低技术，也能很大程度减小M和N。不幸的是，所有这些方法也会以各种形式降低推荐的品质。首先，如果算法只是验算了一小部分顾客样本，那么被选定顾客与当前用户会较少相似。其次，商品空间区隔会把推荐限制在特定产品或主题领域之内。第三，如果算法丢弃了最热门或最冷门的商品，这些商品将不会出现在推荐中，并且，只购买过这些商品的顾客，将不会得到推荐。向商品空间应用维度降低技术，会得到与排除冷门商品那样相同的效果。向顾客空间应用维度降低技术，能有效地把相似顾客组合为群组，正如我们现在所说的，这样的聚类也会降低推荐的品质。

聚类模型

为了寻找与当前用户相似的顾客，聚类模型对顾客基础进行细分，并把这个任务当做为分类问题。算法的目标是，把该用户分配到含有最相似顾客的细分人群里，然后，算法再利用该细分顾客人群的购买和评级，来生成推荐。典型地说，顾客细分的建立，会采用一种聚类或其他无人管理的学习算法，尽管某些应用也用了手工决定的人群细分。利用一种相似性度量标准，聚类算法把最相似的顾客，分组聚合起来，形成聚类或细分人群。由于对大型数据集进行最理想的聚类不切合实际，大多数应用都采用了各种形式的greedy聚类生成。典型的情况是，这些算法始于各细分人群的一个初始集，每个初始集通常包含一个随机选定的顾客，然后算法不断重复地把顾客与现有的细分人群进行匹配，一般也会某些规定，以创建新的细分人群或是合并人群。对于非常大的数据集——尤其是维度很高——抽样或维度降低也是必要的。

一旦算法生成了细分人群，就计算当前用户与概要描述每一细分人群的向量的相似性，然后选择相似性最大的细分人群，并因此而对该用户进行分类。某些算法把用户分类进入多个细分人群，并对每组关系的强度进行描述。较之协同过滤，聚类模型有更好的在线可扩展性和性能，因为它们把当前用户与可控数量的细分人群进行对比，而不是整个顾客基数。复杂和昂贵的聚类计算会离线运行。然而，推荐品质却是低的。聚类模型把无数的顾客分组进入细分人群，匹配一个用户与一个细分人群，然后，以相似顾客细分人群里的所有顾客，来考虑产生推荐的目的。由于聚类模型发现的相似顾客并不是最相似的顾客，因而产生的推荐较少相关。通过大量精细粒度的细分人群，也可能提高推荐的品质，但那样一来，在线的用户-细分人群分类，就会变得与利用协同过滤来寻找相似顾客几乎一样昂贵。

基于搜索的方法

基于搜索或内容的方法，将推荐问题视为相关商品的搜索。给定该用户已买过和评级过的商品，算法构造一个搜索查询，以寻找其他热卖的商品，通过同一作者、艺术家或导演，或利用相似的关键词或主题。例如，如果一个顾客买了Godfather（教父）的DVD系列，系统就会推荐其他的犯罪剧，Marlon Brando出演的其他剧目，或由FrancisFord Coppola导演的其他电影。

如果该用户只有少数购买或评级，基于搜索的推荐算法在计算量和性能上都不错。然而，对于有数千次购买的用户，要以针对所有商品的查询为基础也不太可行。算法必须使用一个数据的子集或概要，因此降低了推荐的品质。在所有各种情况下，推荐品质相对较差。推荐通常就是要么太宽泛（比如最热卖的剧集DVD），要么太狭窄（比如同一个作者的全部图书）。推荐应该要帮助顾客找到和发现新的、相关的、有趣的商品。同一作者或同一主题领域的热卖商品，没有满足这一目标。

商品到商品的协同过滤

Amazon.com在很多邮件营销活动，以及在其大多数的网页上，包括流量极大的网站首页，都把推荐作为一种定向营销工具。点击“你的推荐”链接，会把顾客引向一个区域，在那里，顾客可以通过产品线和主题领域，进行推荐的筛选，为被推荐的商品进行评级，为以前的购买进行评级，并查看为什么这些商品被推荐了（见图1）。

如图2所示，即我们的购物车推荐，以其购物车中的商品为基础，向顾客给出产品建议。这一特性与超市结账台路线上的冲动购买类商品很类似，但我们的冲动购买类商品定向到每位顾客。

Amazon.com广泛地采用推荐算法，针对每个顾客的兴趣进行网站的个性化。因为现有的推荐算法，与Amazon.com千万级的用户和产品数量不能相称，我们开发了自己的算法。我们的算法，也就是商品到商品的协同过滤，符合海量的数据集和产品量，并能实时得到高品质的推荐。

它如何工作

与把当前用户匹配到相似顾客的做法不同，商品到商品的协同过滤，把该用户所购买和评级的商品，匹配到相似的商品，然后组合这些相似的商品进入推荐列表。

对于给定的一件商品，为了决定最相似的匹配，算法通过发现顾客倾向于一起购买的商品，建立一个相似商品的表格。利用对所有产品配对的迭代，以及为每个产品配对计算相似性测度，我们能建立一个产品到产品的矩阵。然而，许多产品配对没有普通顾客，因此在处理时间和内存使用上，这种方法没有效率。下述迭代算法提供了一种更好的方法，通过计算一件商品与所有相关产品之间的相似性：

For 每件商品 in 产品目录, I1

For 每位顾客C 购买过I1 的

For 每件商品I2 由顾客C 所购买的

记录一顾客所购买的 I1 和I2

For 每件商品I2

计算相似度 在 I1 与 I2 之间

计算两个商品之间的相似性可以有多种方法，但通常的方法是，利用我们前面描述的余弦值，其中每个向量对应于一件商品而不是一位顾客，并且向量的M维度对应于已购买过该商品的顾客。这个相似商品表格的离线计算极费时间，最糟糕时需要O(N2M)。但在实际运行中，它接近O(NM)，因为大多数顾客只有很少的购买。对购买最热门商品顾客的抽样，进一步减少了运行时间，同时对推荐的品质略有降低。

对于给定的相似商品表格，算法发现与当前用户每次购买和评级相似的商品，把这些商品聚集起来，然后推荐最畅销或关联最强的商品。这一计算很快速，仅仅取决于该用户购买或评级过商品的数量。

可扩展性：比较

Amazon.com有超过2900万顾客，以及数百万登记在册的商品。其他主要零售商也有同等大小的数据源。在所有这些数据提供机会的同时，也是一种诅咒，远远突破了那些针对小三个数量级的数据集所设计的算法的限度。几乎全部的现有算法，都是在小数据集上评估的。如，MovieLens数据集4包含35000名顾客和3000件商品，EachMovie数据集3包含4000名顾客和1600件商品。

对于非常大的数据集，一个可扩展的推荐算法必须离线运行最昂贵的计算。正如下面的简要对比所显示的，现有方法达不到这样的要求：

• 传统的协同过滤只做很少或不做离线计算，其在线计算量取决于顾客和登记在册商品的数量。在大数据集的情况下，这样的算法不可行，除非使用维度降低、抽样或区隔——所有这些都降低了推荐的品质。
• 聚类模型能离线运行大量的计算，但推荐品质相对较差。出于改进，可以增加人群细分的数量，但这会使在线的用户-细分人群的分类变得昂贵。
• 基于搜索的模型离线建立起关键词、范畴、作者索引，但不能提供符合兴趣、定向内容的推荐。对于购买和评级很多的顾客来说，这些算法的扩展性不佳。

商品到商品协同过滤的可扩展性和性能的关键是，它离线建立耗时巨大的相似商品表格。该算法的在线部分——针对当前用户的购买和评级来寻找相似的商品——计算量独立于商品目录的规模或顾客的总数；仅仅取决于该用户买过或评级过多少个商品。因此，甚至是对于超大数据集，算法也很快速。由于该算法能推荐高度关联的相似商品，推荐的品质就很出色。与传统的协同过滤不同，该算法在用户数据有限的情况下也能运行良好，在少至2到3件商品的基础上，产生高品质的推荐。

结论

通过为每位顾客建立个性化的购物体验，推荐算法提供了一种有效的定向营销形式。对于Amazon.com这样的大型零售商，良好的推荐算法可在海量顾客基数和商品目录上进行扩展，只需要子秒处理时间就能产生在线推荐，能对用户数据里的变化立即做出反应，并能为所有用户提供引人关注的推荐，而无需考虑购买和评级的数量。与其他算法不同，商品到商品的协同过滤能满足这样的挑战。

未来，我们期望零售业为定向营销更广泛地应用推荐算法，包括网上和网下。对个性化来说，电子商务拥有最方便的工具，而同时，较之传统撒大网的方式，该技术对转化率的提升，也会引起网下零售商的关注，可用于信件、优惠券及其他顾客通信中。

作者

Greg Linden是Amazon.com个性化部门的共同创始人、研究员及高级经理，他设计和开发了推荐算法。他目前是斯坦福大学商业研究生院SloanProgram中的管理学研究生。他的研究兴趣包括推荐系统、个性化、数据挖掘以及人工智能。Linden在华盛顿大学获得了计算机科学的理学硕士。联系方式：Linden_Greg@gsb.stanford.edu。

Brent Smith领导着Amazon.com的自动化销售团队。他的研究兴趣包括数据挖掘、机器学习以及推荐系统。他在San Diego的加州大学获得了数学的学士，在华盛顿大学获得了数学的理学硕士，并在那里做了些微分几何的研究工作。联系方式：smithbr@amazon.com。

Jeremy York领导着Amazon.com的自动化内容选择和交付团队。他的兴趣包括分类数据的统计模型、推荐系统，以及网站展示内容的最佳选择。他从华盛顿大学获得了统计学的博士学位，在那里，他的论文获得了Leonard J. Savage奖的贝叶斯应用计量经济学和统计学的最佳论文奖。联系方式：jeremy@amazon.com。

转自：http://www.idouba.net/amazon-com-recommendations-item-to-item-collaborative-filtering/