原始论文：Amazon.com Recommendations: Item-to-item collaborative filtering
亚马逊推荐：物到物的协同过滤
推荐算法因在电子商务网站的应用而广为人知，它们用客户的兴趣爱好作为输入来生成物品的推荐列表。许多应用仅仅用用户明确购买的物品来代表兴趣爱好，dan但其实它们可以用更多的其他特征，包括看过的物品，人口统计下数据，主题兴趣以及最爱的艺术。
在Amazon.com，我们使用推荐算法为每个客户个性化在线商店。商店根据客户的兴趣从根本上改变，达到给软件工程师显示编程主题和给一位新妈妈展示婴儿玩具。点击率和转化率这两个基于Web和电子邮件的重要测算结果显示了其二者上的广告效果要远远超过横幅广告等非目标内容和畅销书清单。
电子商务推荐算法经常在不断变化的环境中运行。例如：
- 一个大的零售商一般会有大量的数据。数以千万计的客户和百万级的不同品类的商品。
- 许多应用就需要推荐的结果可以实时返回，不能超过半秒，同时还要保证一定的高质量推荐。
- 新用户是基于其仅有的一些购买和产品评分导致拥有极其有限信息的典型案例。
- 老用户由于有大量的购买和评分数据使得其拥有大量的信息。
- 用户数据是不稳定的：每一次交互都会产生有价值的用户数据，算法必须及时的根据新信息做出反馈。
一般有三种方法来解决推荐问题：传统的协同过滤，聚类模型，基于搜索的方法。这里，我们用这些方法和我们的算法进行比较，我们的算法称为物到物的协同过滤。不像传统的协同过滤，我们算法的在线大规模计算能力不收用户量和产品量以及产品类别的影响。我们的算法可以实时的生成推荐，并且可以大规模地处理数据集，同时能够生成高质量的推荐。
推荐算法
大多数的推荐算法开始都是找一群购买以及评论的产品和推荐目标用户购买过以及评论过的产品有交集的用户。然后从这些相似的用户中聚合出来这些物品，再去除他们已经购买和评论过的物品。这些算法里两个比较流行的版本是协同过滤和聚类模型。其他的算法-包括基于搜索的方法以及我们的物到物的协同过滤，都是集中于找到相似的物品而不是相似的用户。对于每个用户购买和评论过的商品来说，算法尝试去找到相似的物品。然后它聚合出这些相似的物品并推荐它们。
传统的协同过滤
一个传统的协同过滤算法将一个用户表示成一个N维的物品向量，N是不用品类的物品数。向量中的元素正的代表用户购买过或者正向评分过的物品，负的代表负向评分的物品。为了补偿那些畅销的产品，该算法通常将用户向量乘以逆频率（对物品有购买或者评分行为的用户数量），使得较不为人知的物品更具有相关性。对于大多数用户来说，这个向量极度稀疏。
算法基于和目标用户极为相似的一小部分用户产生推荐。有各种各样的方法计算A和B两个用户之间的相似度，普遍采取的方法是两个用户向量之间的cosine角度：
从相似用户的物品中选择推荐物品的算法也有很多，一种通用的方法是按照物品被相似用户购买的数量排序。
使用协同过滤产生推荐计算花费大。最坏的复杂度是O(MN)，其中M是用户数N是产品数，因为对于每个目标用户测试了M个用户以及产品数的上限N。然而，由于用户购买行为的稀疏性，算法最终的花费接近于o(M+N)，因为大部分用户的向量只包含很小数量的物品，不论产品类目有多少。但是有一小部分用户购买和评论了大量的物品质的计算花费时间接近o(N)。因此，算法最终的花费大约为o(M+N)。甚至因此，对于非常大的数据集-例如1000万或更多客户和100万或更多类目产品-算法遇到严重的性能和扩展问题。
可以通过减小数据规模部分解决计算花费问题。我们可以通过随机抽样客户或丢弃购买少的客户减少M，通过丢弃非常受欢迎或不受欢迎的项目减少N。也可以基于产品类别或主题分类的空间通过分割项目的一个小的、恒定的因素来减少检查的项目数量。降维等技术作为聚类和主成分分析可以大幅减少M或N。
不幸的是，所有减小数据规模的方法都会降低推荐质量。首先，如果算法近检测一小部分用户样本，那么这些被选中的用户就不会与目标用户那么的相似。第二，品类空间的划分限制了特定产品和主题领域的推荐。第三，如果算法丢弃了最受欢迎或者最不受欢迎的物品，那么它们经永远不会出现在推荐之中，并且仅购买这些物品的客户也得不到这些推荐。将为技术应用于物品空间往往会起到消除低频品类物品的类似效应。降维技术类似于用户分组有效地应用于用户空间，就如我们现在所描述的，这样的聚类也可以降维推荐质量。
聚类模型
为了找到那些与目标用户相似的客户，聚类模型将用户分为很多segments，将寻找目标用户相似用户的任务视为一个分类任务。算法目标是将目标用户分配到包含最相似用户的segment中，然后使用segment中用户购买的商品和评分产生推荐。
通常segments是用聚类模型或者其他无监督的学习算法构建的，虽然有些应用程序使用手动确定segments。使用相似性矩阵，聚类算法将最相似的客户分组一起形成集群或segments。因为对大数据集进行最优聚类是不切实际的，大多数应用程序使用各种形式贪婪的聚类生成算法。通常这些算法从一组初始段开始，且经常会包含一个随机选择的客户。然后他们反复匹配客户到现有的segments中，通常碎玉创建新的或合并现有的segments有一些规定。对于非常大的数据集-特别是那些高数据集维度 - 抽样或降维也是必要的。
一旦算法生成了segments，就会计算每个用户与每个segments总结向量之间的相似性，然后选择具有最强的相似性segments并根据此对用户进行分类。一些算法将用户分类为多个部分并描述其每个关系的强弱。
聚类模型相比CF有更好的在线可扩展性和表现，因为聚类算法只将用户和可控制的segments数量进行比较而不是所有用户。复杂花费高的聚类计算是在离线进行的。然而，推荐质量却很低。聚类模型将许多用户分组在一起形成一个segment，将一个用户匹配到一个segment中，然后考虑在这个细分市场中说所有客户的相似客户来产生推荐。由于聚类模型找到的相似客户并不一定是最相似的客户，所以他们产生的推荐并没有太大的相关性。为了提高推荐质量，可以增加类别数量，但这会加大用户在线计算类别的花费。
基于搜索的模型
基于搜索或者内容的模型将推荐看作是一个搜索相关物品的问题。给定一些用户的购买和评级的物品，算法会构造搜索查询找到同一作者的其他热门产品，艺术家，导演，以及类似的关键词或
主题。如果客户购买了教父DVD收藏，例如，系统可能会推荐其他犯罪剧集，其他马龙白兰度主演的，或其他弗朗西斯福特科波拉导演的电影。
如果用户只有很少的购买和评分记录，基于搜索的推荐算法可规模化并表现地很好。然而，对于那些有成千上万的购买记录的用户来说，基于一个所有物品的请求来进行推荐是不实际的。算法必须只是用数据集中的一个子集或者汇总数据，这会降低推荐质量。以上例子中，推荐的质量相对较差。推荐结果经常会太宽泛（例如最好卖的电视剧DVD主题）或者太狭隘（例如相同作者的所有书籍）。推荐应该是帮助客户去寻找和发现新的，相关的并且有趣的物品。同一作者的流行作品以及相似主题的类别物品都是不能满足这一目标的。
物到物的协同过滤
Amazon.com将推荐作为许多电子邮件活动以及它的大部分网站页面中的营销工具，包括高流量的Amazon.com主页。点击“您的推荐”链接将会引导客户访问一个推荐区域，在这里他们可以通过产品线和主题领域来进行筛选，也可以评价推荐的产品，评价他们以前购买的物品，同时可以看到为什么这些物品被推荐了（如图片1所示）。
如图2所示，是我们的购物车推荐，根据客户购物车中的物品给他们推荐了一些商品。该功能类似于在超市收银台旁的那些易冲动消费的物品，但我们的冲动项目针对每个客户的。
亚马逊网站基于他们客户的兴趣广泛地使用推荐算法来个性化他们的网站。由于现存的推荐算法无法扩展到亚马逊网站上数以千万的客户和产品，所以我们开发自己的推荐算法。我们的算法是物到物的协同过滤，可以扩展到巨大的数据集并实时产生高质量的推荐。
它是怎么工作的
物到物的协同过滤并不是对目标用户进行匹配到他们相似的客户，而是对他们购买和评论过的物品匹配到相似的物品，然后聚合这些相似的物品生成推荐列表。
为了确定地匹配出给定物品的最相似取票，算法通过寻找那些用户会一起购买的物品来建立了一个相似物品表。我们可以构建产品到产品的矩阵通过迭代所有项目对和计算每对的相似性度量。然而，许多产品对没有共同的客户，因此，这种方法效率低下在处理时间和内存使用情况上面。下面的迭代算法提供了一个更好地方法来计算一个商品和其他所有商品之间的相似性。1
2
3
4
5
6
7
8For each item in product catalog, I_1
For each customer C who purchased I_1
For each item I_2 purchased by
customer C
Record that a customer purchased I_1
and I_2
For each item I_2
Compute the similiarity between I_1 and I_2
有各种各样的方法可以计算两者之间的相似性，但一个常见的方法是使用我们之前描述的余弦量度，其中每个向量对应一个物品而不是一个客户，矢量的M维度对应已购买该商品的客户。
这种相似物品表的离线计算是非常耗时的，O（N2M）为最糟糕的情况。然而，在实践中，它更接近于O（NM），因为大多数客户购买的很少。对购买最畅销主题的客户进行抽样可以进一步减少运行时间，同时会伴随一点质量降低。
给定一个相似物品表，算法会找到与用户购买的每个项目类似的项目评分，汇总这些项目，然后推荐最受欢迎或相关的项目。这个计算非常快，仅取决于用户购买或评级的商品数量。
扩展性：比较
Amazon.com拥有超过2900万客户和数百万品类物品。其他专业零售商拥有相对较大的数据来源。这些数据是一个机会也是一个诅咒，打破了设计算法的背后对于数据集小三个数量级。几乎所有现有的算法都经过了小数据集评估。例如，MovieLens数据set4包含35,000个客户和3,000个项目，并且EveryMovie数据集3包含4,000个客户和1,600项。
对于非常大的数据集，可扩展的推荐算法必须执行最昂贵的离线计算。如下简要比较显示，现有方法不足：
- 传统的协调过滤做很少的甚至没有离线计算，并且它的在线计算的扩展性受到客户和物品数量的限制。算法在大数据集上运行是不现实的，除非它用降维，抽样或者分区等方法，这些都会降低推荐质量。
- 聚类模型可以在离线计算中有很大的表现，但是推荐质量相对很差。为了提升它，可以增加聚类中的segments，但是这会使得在线用户的segment分类变得很复杂。
- 基于搜索的模型离线建立了关键词，品类和作者指标，但是没能够提供一个又去的目标推荐。他们都很难扩展到那些有大量购买和评论的记录的用户。
物到物协同过滤扩展性和表现的关键创建一个花费很高的离线计算得到的相似物品表。这个算法的在线部分就是与寻找用户购买和评论过物品的相似物品，其可扩展性与品类大小和总客户数量不相关；仅仅与用户有多少的购买和评论记录有关。因此，即使在很大的数据集上算法也可以运行的很快。由于算法推荐高度相关的相似物品，因此推荐质量是极高的。不像传统的协同过滤，算法也可以在有限的用户数据的条件下表现得很好，可以基于两到三个物品的数据产生高质量的推荐。
结论
推荐算法通过为每位客户创建个性化的购物体验提供了有效的目标营销形式。对于亚马逊等大型零售商，一个很好的推荐算法可扩展到非常大客户群和产品目录，要求仅仅亚秒处理时间以生成在线推荐，能够对改变用户的数据立即做出反应，并为所有用户提供吸引人的推荐，无论他们的购买和评级物品的数量多少。不像其他的算法，物到物的协同过滤能够迎接这一挑战。
在未来，我们期待零售业更广泛地应用推荐算法来达到有针对性的营销，在线和离线均是如此。而电子商务企业拥有最简单的个性化工具，技术的转换率提高与传统的大规模方法相比这些方法对于离线的零售商来说也会使其脱颖而出，在用户的邮件邮寄，优惠券和其他形式的客户沟通。