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

2 评论 10731 浏览 11 收藏 21 分钟

原文发表在:
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。

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

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

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

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

更多精彩内容,请关注人人都是产品经理微信公众号或下载App