Amazon.com的推荐：从商品到商品的协同过滤

原文发表在：
Greg Linden, Brent Smith, Jeremy York, “Amazon.com Recommendations: Item-to-Item Collaborative Filtering,”  IEEE Internet Computing , vol. 7, no. 1, pp. 76-80, Jan./Feb. 2003, doi:10.1109/MIC.2003.1167344

以下全文翻译的PDF点此下载。

Amazon.com 的推荐

从商品到商品的协同过滤

Greg Linden, Brent Smith, and Jeremy York •Amazon.com

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

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

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

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

推荐算法

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

传统的协同过滤

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

算法也能从相似顾客的商品里选择推荐，有多种可以利用的方法，常见的一种技术是，按照购买该商品的相似顾客数量，对每件商品进行排序。

利用协同过滤来产生推荐，很耗计算。最坏的情况是O(MN)，其中M是顾客数量，N是产品目录中商品的数量，因为算法要验算M个顾客，并且对每个顾客最多要计算N种商品。但是，由于顾客向量的平均值很稀疏，算法的执行更倾向于接近O(M + N)。扫描每一个顾客大约是O(M)，而不是O(MN)，因为几乎所有顾客向量都只含有很少的商品，无需考虑产品目录的规模。但有少数顾客，他们买过或评级过的商品在产品目录中占有值得注意的百分比，需要O(N)处理时间。因此，算法最终执行的大约是O(M + N)。尽管如此，对非常大的数据集来说——比如1千万以上的顾客，以及1百万以上登记在册的商品——算法也会遭受严峻的性能和计算量问题。
通过减小数据量，可能部分缓解这些计算量的问题4。我们能够减小M，通过对顾客进行随机抽样，或丢弃那些购买很少的顾客；我们也能减小N，通过丢弃那些极热门和极冷门的商品。我们还可能减少所需计算的商品数量，通过一个小的常数因子，在产品类别或主题分类的基础上，对商品空间进行区隔。诸如聚类和主分量分析等维度降低技术，也能很大程度减小M和N。
不幸的是，所有这些方法也会以各种形式降低推荐的品质。首先，如果算法只是验算了一小部分顾客样本，那么被选定顾客与当前用户会较少相似。其次，商品空间区隔会把推荐限制在特定产品或主题领域之内。第三，如果算法丢弃了最热门或最冷门的商品，这些商品将不会出现在推荐中，并且，只购买过这些商品的顾客，将不会得到推荐。向商品空间应用维度降低技术，会得到与排除冷门商品那样相同的效果。向顾客空间应用维度降低技术，能有效地把相似顾客组合为群组，正如我们现在所说的，这样的聚类也会降低推荐的品质。

聚类模型

为了寻找与当前用户相似的顾客，聚类模型对顾客基础进行细分，并把这个任务当做为分类问题。算法的目标是，把该用户分配到含有最相似顾客的细分人群里，然后，算法再利用该细分顾客人群的购买和评级，来生成推荐。典型地说，顾客细分的建立，会采用一种聚类或其他无人管理的学习算法，尽管某些应用也用了手工决定的人群细分。利用一种相似性度量标准，聚类算法把最相似的顾客，分组聚合起来，形成聚类或细分人群。由于对大型数据集进行最理想的聚类不切合实际，大多数应用都采用了各种形式的greedy聚类生成。典型的情况是，这些算法始于各细分人群的一个初始集，每个初始集通常包含一个随机选定的顾客，然后算法不断重复地把顾客与现有的细分人群进行匹配，一般也会某些规定，以创建新的细分人群或是合并人群6。对于非常大的数据集——尤其是维度很高——抽样或维度降低也是必要的。
一旦算法生成了细分人群，就计算当前用户与概要描述每一细分人群的向量的相似性，然后选择相似性最大的细分人群，并因此而对该用户进行分类。某些算法把用户分类进入多个细分人群，并对每组关系的强度进行描述。
较之协同过滤，聚类模型有更好的在线可扩展性和性能3，因为它们把当前用户与可控数量的细分人群进行对比，而不是整个顾客基数。复杂和昂贵的聚类计算会离线运行。然而，推荐品质却是低的1。聚类模型把无数的顾客分组进入细分人群，匹配一个用户与一个细分人群，然后，以相似顾客细分人群里的所有顾客，来考虑产生推荐的目的。由于聚类模型发现的相似顾客并不是最相似的顾客，因而产生的推荐较少相关。通过大量精细粒度的细分人群，也可能提高推荐的品质，但那样一来，在线的用户-细分人群分类，就会变得与利用协同过滤来寻找相似顾客几乎一样昂贵。

基于搜索的方法

基于搜索或内容的方法，将推荐问题视为相关商品的搜索8。给定该用户已买过和评级过的商品，算法构造一个搜索查询，以寻找其他热卖的商品，通过同一作者、艺术家或导演，或利用相似的关键词或主题。例如，如果一个顾客买了Godfather（教父）的DVD系列，系统就会推荐其他的犯罪剧，Marlon Brando出演的其他剧目，或由Francis Ford Coppola导演的其他电影。
如果该用户只有少数购买或评级，基于搜索的推荐算法在计算量和性能上都不错。然而，对于有数千次购买的用户，要以针对所有商品的查询为基础也不太可行。算法必须使用一个数据的子集或概要，因此降低了推荐的品质。在所有各种情况下，推荐品质相对较差。推荐通常就是要么太宽泛（比如最热卖的剧集DVD），要么太狭窄（比如同一个作者的全部图书）。推荐应该要帮助顾客找到和发现新的、相关的、有趣的商品。同一作者或同一主题领域的热卖商品，没有满足这一目标。

商品到商品的协同过滤
Amazon.com在很多邮件营销活动，以及在其大多数的网页上，包括流量极大的网站首页，都把推荐作为一种定向营销工具。点击“你的推荐”链接，会把顾客引向一个区域，在那里，顾客可以通过产品线和主题领域，进行推荐的筛选，为被推荐的商品进行评级，为以前的购买进行评级，并查看为什么这些商品被推荐了（见图1，图在最后）。
如图2（图在最后）所示，即我们的购物车推荐，以其购物车中的商品为基础，向顾客给出产品建议。这一特性与超市结账台路线上的冲动购买类商品很类似，但我们的冲动购买类商品定向到每位顾客。
Amazon.com广泛地采用推荐算法，针对每个顾客的兴趣进行网站的个性化。因为现有的推荐算法，与Amazon.com千万级的用户和产品数量不能相称，我们开发了自己的算法。我们的算法，也就是商品到商品的协同过滤，符合海量的数据集和产品量，并能实时得到高品质的推荐。

它如何工作

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

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件商品。
对于非常大的数据集，一个可扩展的推荐算法必须离线运行最昂贵的计算。正如下面的简要对比所显示的，现有方法达不到这样的要求：
• 传统的协同过滤只做很少或不做离线计算，其在线计算量取决于顾客和登记在册商品的数量。在大数据集的情况下，这样的算法不可行，除非使用维度降低、抽样或区隔——所有这些都降低了推荐的品质。
• 聚类模型能离线运行大量的计算，但推荐品质相对较差。出于改进，可以增加人群细分的数量，但这会使在线的用户-细分人群的分类变得昂贵。
• 基于搜索的模型离线建立起关键词、范畴、作者索引，但不能提供符合兴趣、定向内容的推荐。对于购买和评级很多的顾客来说，这些算法的扩展性不佳。
商品到商品协同过滤的可扩展性和性能的关键是，它离线建立耗时巨大的相似商品表格。该算法的在线部分——针对当前用户的购买和评级来寻找相似的商品——计算量独立于商品目录的规模或顾客的总数；仅仅取决于该用户买过或评级过多少个商品。因此，甚至是对于超大数据集，算法也很快速。由于该算法能推荐高度关联的相似商品，推荐的品质就很出色10。与传统的协同过滤不同，该算法在用户数据有限的情况下也能运行良好，在少至2到3件商品的基础上，产生高品质的推荐。

结论

通过为每位顾客建立个性化的购物体验，推荐算法提供了一种有效的定向营销形式。对于Amazon.com这样的大型零售商，良好的推荐算法可在海量顾客基数和商品目录上进行扩展，只需要子秒处理时间就能产生在线推荐，能对用户数据里的变化立即做出反应，并能为所有用户提供引人关注的推荐，而无需考虑购买和评级的数量。与其他算法不同，商品到商品的协同过滤能满足这样的挑战。
未来，我们期望零售业为定向营销更广泛地应用推荐算法，包括网上和网下。对个性化来说，电子商务拥有最方便的工具，而同时，较之传统撒大网的方式，该技术对转化率的提升，也会引起网下零售商的关注，可用于信件、优惠券及其他顾客通信中。

作者

Greg Linden是Amazon.com个性化部门的共同创始人、研究员及高级经理，他设计和开发了推荐算法。他目前是斯坦福大学商业研究生院Sloan Program中的管理学研究生。他的研究兴趣包括推荐系统、个性化、数据挖掘以及人工智能。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。

图1 Amazon.com主页上“你的推荐”特性。
利用这一特性，顾客能够对推荐进行排序，并加入他们自己的产品评级。

图2 Amazon.com的购物车推荐。
该推荐的基础是顾客购物车中的商品：Pragmatic Programmer 和 Physics for Game Developers。

来源：http://blog.sina.com.cn/s/blog_586631940100pduh.html