上周有粉丝私信老shi想要找推荐系统相关的论文，刚好这两天老shi无意中在b站上观看了国内某知名大学教授关于目前博士生就业问题相关论文解说的视频，感觉很有意思，就萌生了给大家翻译一篇经典的推荐系统论文的想法。本期课程老shi决定给大家带来一篇2003年亚马逊曾经发表过的论文《Amazon.com Recommendations Item-to-Item Collaborative Filtering》翻译，这篇论文可谓是一篇比较早的经典的基于Item-to-Item（商品-商品）的协同过滤论文了。废话不多说，马上进入正题。
摘要
推荐算法以它在电子商务网站上的用途而闻名，它是利用顾客的兴趣作为输入，来产生一个推荐的商品列表。很多应用仅仅使用了顾客购买并明确代表顾客兴趣的商品。但它们还可以利用其他属性，包括已经浏览的商品，人口统计数据，主题兴趣以及特别喜爱的艺术家。
在亚马逊网站上，我们利用推荐算法对每一位顾客提供个性化的在线商店，在顾客兴趣的基础上，商店有了彻底的改观。向一位软件工程师展示编程类项目，向一位新手妈妈展示婴儿玩具。点击率和转化率——基于网络和邮件广告的两个重要评估指标——大大超越了那些未定向的内容，例如banner 广告和热卖清单。
电子商务推荐算法经常运行在一个充满挑战的环境里。例如：
- 大型零售商店有海量数据，数以千万计的客户以及数百万不同类目的登记在册的商品。
- 很多应用要求结果实时返回，在不超过半秒内，还要产出高质量的推荐。
- 新顾客典型地只有有限的信息，只能以少量的购买和评级信息为基础。
- 较老的顾客能拿到大量的信息，可以根据大量的购买和评级信息为基础。
- 顾客数据是易变的，每一次交互都能提供可用的顾客数据，算法必须对新的信息立即做出响应。
解决推荐问题的三个常用方法：传统的协同过滤，聚类模型以及基于搜索的方法。这里，我们就这些方法和我们的算法——我们称之为商品到商品的协同过滤进行比较。与传统的协同过滤不同，我们的算法在线计算规模，与顾客数量以及产品目录中的商品无关。我们的算法实时产生推荐，适用于海量数据集，并产生高质量的推荐。
推荐算法
大多数推荐算法都从找顾户数据集开始，他们买过和评论过的商品，与当前用户买过和评论过的商品有重叠。算法就把来自这些相似顾客的商品聚集起来，排除该顾户已经购买过或评论过的商品，并向该顾户推荐其余的商品。这些算法有两个最常见的做法：协同过滤和聚类模型。其他算法——包括基于搜索的方法以及我们自己的商品到商品协同过滤——都集中在寻找相似的商品，而不是相似的顾客。针对用户所购买和评论过的每一件商品，算法都试图找到相似的商品，然后聚集这些相似的商品，并给予推荐。
传统的协同过滤
传统的协同过滤算法把一个顾客描绘成商品的N维向量，其中N是登记在册的不同商品的数量。对于购买过或正面评论过的商品，向量分量为正，对于负面评论的商品，向量分量为负。为了弥补最热卖的商品，算法典型地会把向量分量乘以其反向频率（已购买或评论过该商品的顾客数量的倒数），以使不太知名的商品更加相关。对几乎所有的顾客来说，这个向量非常稀疏。
算法在与该顾户最相似的少数顾客基础上产生推荐。算法能够测量两个顾客的相似性，例如A和B，有多种方法；一种常见的方法是测量这两个向量之间的夹角余弦值：
算法也能从相似顾客的商品里有多种推荐的方法，常见的一种技术是按照购买该商品的相似顾客数量，对每件商品进行排序。
利用协同过滤来产生推荐在计算上是十分昂贵的。最坏的情况是O(MN)，其中M是顾客数量，N是产品目录中商品的数量，因为算法要验算M个顾客，并且对每个顾客最多要计算N种商品。但是，由于顾客向量的平均值很稀疏，算法的执行更倾向于接近O(M +N)。扫描每一个顾客时间复杂度大约是O(M)，而不是O(MN)，因为几乎所有顾客向量都只含有很少的商品，无需考虑产品目录的规模。但有少数顾客，他们购买过或评论过的商品在产品目录中占有值得注意的比重，需要O(N)个处理时间。因此，算法最终执行的时间复杂度大约是O(M + N)。尽管如此，对非常大的数据集来说——比如一千万以上的顾客，以及1百万以上登记在册的商品——算法也会遭受严峻的性能和计算量问题。
通过减小数据量，可能部分缓解这些计算量的问题。我们能够减小M，通过对顾客进行随机抽样，或丢弃那些购买很少的顾客；我们也能减小N，通过丢弃那些极热门和极冷门的商品。我们还可能减少所需计算的商品数量，通过一个很小的常数因子，在产品类别或主题分类的基础上，对商品空间进行区隔。例如聚类和主成分分析等降维技术，也能很大程度减小M和N。
不幸的是，所有这些方法也会以各种形式降低推荐的质量。首先，如果算法只是验算了一小部分顾客样本，那么被选定顾客与当前用户较少相似。其次，商品空间区隔会把推荐限制在特定产品或主题领域之内。第三，如果算法丢弃了最热门或最冷门的商品，这些商品将不会出现在推荐列表当中，并且只购买过这些商品的顾客，将不会得到推荐。向商品空间应用降维技术，会得到与排除冷门商品相同的效果。向顾客空间应用降维技术，能有效地把相似顾客组合为群组，正如我们现在所说的，这样的聚类也会降低推荐的质量。
聚类模型
为了寻找与当前用户相似的顾客，聚类模型对顾客基础进行细分，并把这个任务当作分类问题。算法的目标是把该用户分配到含有最相似顾客的细分人群里，然后，算法再利用该细分顾客人群的购买和评论来生成推荐。典型地说，顾客细分的建立，会采用一种聚类或无监督的学习算法，尽管某些应用也用了手工决定的人群细分。利用一种相似性度量标准，聚类算法把最相似的顾客，分组聚合起来，形成聚类或细分人群。由于对大型数据集进行最理想的聚类不切合实际，大多数应用都采用了各种形式的贪婪聚类算法生成。典型的情况是，这些算法始于各细分人群的一个初始集，每个初始集通常包含一个随机选定的顾客，然后算法不断重复地把顾客与现有的细分人群进行匹配，通常使用某些规则，以创建新的细分人群或是合并人群。对于非常大的数据集——尤其是维度很高的数据集——抽样或降维也是必要的。
一旦算法生成了细分人群，就计算当前用户与概要描述每一细分人群的向量的相似性，然后选择相似性最大的细分人群，并以此来对该用户进行分类。某些算法把用户分类进入多个细分人群，并对每组关系的强度进行描述。
较之协同过滤，聚类模型有更好的在线可扩展性和性能，因为它们把当前用户与可控数量的细分人群进行对比，而不是整个顾客基数。复杂和昂贵的聚类计算会离线运行。然而，推荐质量却是低的。聚类模型把无数的顾客分组进入细分人群，匹配一个用户与一个细分人群，然后以相似顾客细分人群里的所有顾客，来考虑产生推荐的目的。由于聚类模型发现的相似顾客并不是最相似的顾客，因而产生的推荐较少相关。通过大量精细粒度的细分人群，也可能提高推荐的质量，但那样一来，在线的用户-细分人群分类，就会变得与利用协同过滤来寻找相似顾客几乎一样昂贵。
基于搜索的方法
基于搜索或内容的方法，将推荐问题视为相关商品的搜索。给定该用户已买过和评论过的商品，算法构造一个搜索查询，以寻找其他热卖的商品，通过同一作者、艺术家或导演，或利用相似的关键词或主题。例如，如果一个顾客买了Godfather（教父）的DVD系列，系统就会推荐其他的犯罪题材，Marlon Brando出演的其他剧目，或由FrancisFord Coppola导演的其他电影。
如果该用户只有少数购买或评级，基于搜索的推荐算法在计算量和性能上都不错。然而，对于有数千次购买的用户，要以针对所有商品的查询为基础也不太可行。算法必须使用一个数据的子集或概要，因此降低了推荐的质量。在所有各种情况下，推荐质量相对较差。推荐通常就是要么太宽泛（比如最热卖的剧集DVD），要么太狭窄（比如同一个作者的全部图书）。推荐应该要帮助顾客找到和发现新的、相关的、有趣的商品。同一作者或同一主题领域的热卖商品，没有满足这一目标。
商品到商品的协同过滤
亚马逊网站在很多邮件营销活动，以及在其大多数的网页上，包括流量极大的网站首页，都把推荐作为一种定向营销工具。点击“你的推荐”链接，会把顾客引导到一个区域，在那里顾客可以通过产品线和主题领域，进行推荐的筛选，为被推荐的商品进行评级，为以前的购买进行评级，并查看为什么这些商品被推荐了（见图1）。
如图2所示，即我们的购物车推荐，以其购物车中的商品为基础，向顾客给出产品建议。这一特性与超市结账台路线上的冲动购买类商品很类似，但我们的冲动购买类商品定向到每位顾客。
亚马逊网站广泛地采用推荐算法，针对每个顾客的兴趣进行网站的个性化。因为现有的推荐算法，与亚马逊网站千万级的用户和产品数量不相称，我们开发了自己的算法。我们的算法，也就是商品到商品的协同过滤，符合海量的数据集和产品量，并能实时得到高质量的推荐。
它如何工作
把与当前用户匹配到相似顾客的做法不同，商品到商品的协同过滤，把该用户所购买和评级的商品，匹配到相似的商品，然后组合这些相似的商品进入推荐列表。
对于给定的一件商品，为了决定最相似的匹配，算法通过发现顾客倾向于一起购买的商品，建立一个相似商品的表格。利用对所有产品配对的迭代，以及为每个产品配对计算相似性测度，我们能建立一个产品到产品的矩阵。然而，许多产品配对没有普通顾客，因此在处理时间和内存使用上，这种方法没有效率。下述迭代算法提供了一种更好的方法，通过计算一件商品与所有相关产品之间的相似性：
For 每件商品 in 产品目录, I1
For 每位顾客C 购买过I1 的
For 每件商品I2 由顾客C 所购买的
记录一顾客所购买的 I1 和I2
For 每件商品I2
计算相似度 在 I1 与 I2 之间
计算两个商品之间的相似性可以有多种方法，但通常的方法是利用我们前面描述的余弦值，其中每个向量对应于一件商品而不是一位顾客，并且向量的M维度对应于已购买过该商品的顾客。这个相似商品表格的离线计算极费时间，最糟糕时需要O(N2M)。但在实际运行中，它接近O(NM)，因为大多数顾客只有很少的购买。对购买最热门商品顾客的抽样，进一步减少了运行时间，同时对推荐的品质略有降低。
对于给定的相似商品表格，算法发现与当前用户每次购买和评级相似的商品，把这些商品聚集起来，然后推荐最畅销或关联最强的商品。这一计算很快速，仅仅取决于该用户购买或评级过商品的数量。
可扩展性：比较
亚马逊网站上有超过2900万顾客，以及数百万登记在册的商品。其他主要零售商也有同等大小的数据源。在所有这些数据提供机会的同时，也是一种祸害，远远突破了那些针对小三个数量级的数据集所设计的算法的限度。几乎全部的现有算法，都是在小数据集上评估的。例如，MovieLens数据集包含35000名顾客和3000件商品，EachMovie数据集包含4000名顾客和1600件商品。
对于非常大的数据集，一个可扩展的推荐算法必须离线运行最昂贵的计算。正如下面的简要对比所显示的，现有方法达不到这样的要求：
- 传统的协同过滤只做很少或不做离线计算，其在线计算量取决于顾客和登记在册商品的数量。在大数据集的情况下，这样的算法不可行，除非使用维度降低、抽样或区隔——所有这些都降低了推荐的质量。
- 聚类模型能离线运行大量的计算，但推荐品质相对较差。出于改进，可以增加人群细分的数量，但这会使在线的用户-细分人群的分类变得昂贵。
- 基于搜索的模型离线建立起关键词、范畴、作者索引，但不能提供符合兴趣、定向内容的推荐。对于购买和评级很多的顾客来说，这些算法的扩展性不佳。
商品到商品协同过滤的可扩展性和性能的关键是，它离线建立耗时巨大的相似商品表格。该算法的在线部分——针对当前用户的购买和评级来寻找相似的商品——计算量独立于商品目录的规模或顾客的总数；仅仅取决于该用户买过或评级过多少个商品。因此，甚至是对于超大数据集，算法也很快速。由于该算法能推荐高度关联的相似商品，推荐的质量就很出色。与传统的协同过滤不同，该算法在用户数据有限的情况下也能运行良好，在少至2到3件商品的基础上，产生高质量的推荐。
结论
通过为每位顾客建立个性化的购物体验，推荐算法提供了一种有效的定向营销形式。对于亚马逊这样的大型零售商，良好的推荐算法可在海量顾客基数和商品目录上进行扩展，只需要次秒处理时间就能产生在线推荐，能对用户数据里的变化立即做出反应，并能为所有用户提供引人关注的推荐，而无需考虑购买和评级的数量。与其他算法不同，商品到商品的协同过滤能满足这样的挑战。
未来，我们期望零售业为定向营销更广泛地应用推荐算法，包括线上和线下。对个性化来说，电子商务拥有最方便的工具，而与此同时，较之传统广撒网的方式，该技术对转化率的提升，也会引起线下零售商的关注，可以应用于信件、优惠券及其他顾客通信中。
参考：
https://www.researchgate.net/publication/308953917_Amazon_com_recommendations_Item-to-item_collaborative_filtering
https://blog.csdn.net/pearl8899/article/details/89479544
