@TOC
论文名称：Amazon.com Recommendations Item-to-Item Collaborative Filtering Prediction
原文地址：Amazon.com Item-to-Item
⚡本系列历史文章⚡
【推荐系统论文精读系列】(一)--Amazon.com Recommendations
【推荐系统论文精读系列】(二)--Factorization Machines
【推荐系统论文精读系列】(三)--Matrix Factorization Techniques For Recommender Systems
【推荐系统论文精读系列】(四)--Practical Lessons from Predicting Clicks on Ads at Facebook
【推荐系统论文精读系列】(五)--Neural Collaborative Filtering
【推荐系统论文精读系列】(六)--Field-aware Factorization Machines for CTR Prediction
【推荐系统论文精读系列】(七)--AutoRec Autoencoders Meet Collaborative Filtering
【推荐系统论文精读系列】(八)--Deep Crossing：Web-Scale Modeling without Manually Crafted Combinatorial Features
【推荐系统论文精读系列】(九)--Product-based Neural Networks for User Response Prediction
【推荐系统论文精读系列】(十)--Wide&Deep Learning for Recommender Systems
【推荐系统论文精读系列】(十一)--DeepFM A Factorization-Machine based Neural Network for CTR Prediction
【推荐系统论文精读系列】(十二)--Neural Factorization Machines for Sparse Predictive Analytics
一、摘要
推荐系统算法在电商网站现在已经被广泛使用，特们会使用关于用户兴趣的数据作为输入然后去产生一系列的推荐列表。一些应用只使用顾客购买的物品或者显示他们兴趣的数据，而且他们还会使用用户的其它属性，包括用户浏览过的物品，人口特征画像，感兴趣的话题和最喜爱的艺术家等。
在亚马逊电商网站，他们使用了推荐算法去为每个用户个性化推荐他们的网上商店。这个商城在根本上改变了基于顾客的兴趣，我们会向一个软件工程师展示程序标题，给一个妈妈推荐婴儿玩具。点击率和转化率是两个重要的网站和邮件广告有效性的评估指标，这极大的超过了那些没有针对性的文本，例如横幅广告或者卖得最好的物品列表。
电商推荐算法经常运作于一些具有挑战性的环境，例如：
- 一个大的零售商可能会有巨大的数据量，数千万的顾客和数以百万的不同种类的物品
- 一些应用需要实时的返回结果，不超过0.5秒仍然需要高质量的推荐列表
- 新的顾客通常有有限的信息，只有少量的购买历史或者物品评分
- 老顾客会有过剩的信息，数以千计的购买历史或者评分
- 顾客数据是不稳定的，每个交互都会提供不同的顾客数据，并且算法必须要立刻的进行响应新的信息。
这里有三种方法去解决这些推荐问题，分别是：traditional collaborative filtering，cluster model，search-based。这里，我们会对比这几种方式和我们的算法，叫做 item-to-item collaborative filtering。不想传统的协同过滤，我们的算法线上计算不依赖于大量的顾客和物品类别。我们的算法会实时的产生推荐，囊括巨大的数据集，并且产生高质量的推荐。
二、推荐算法
大多数的推荐算法开始是以发现一系列用户，这些用户会购买或者评分重叠的一些物品，算法会聚集这些相似用户的物品，然后消除目标用户已经购买或者评分过的，然后将剩余的物品推荐给用户。两个受欢迎的算法分别是协同过滤和聚类模型。其它的算法还有基于搜索的方式和我们的物品-物品的协同过滤方法，都是集中区发现相似的物品，而不是相似的用户。对于每个用户购买过或者评分过的物品，算法会尝试发现相似的物品。然后会累积这些相似的物品并且推荐他们。
三、传统协同过滤
传统的协同过滤算法呈现一个用户作为一个N维的向量，N是不同物品门类的数目。向量的不同部分代表用户对该物品的一个积极程度，为了补偿那些卖的最好的物品，这个算法通常会通过转化频率然后乘以相应的向量部分，使那些不怎么受欢迎的物品也变得更加相关，罪域大多数顾客来说，这个向量是非常的稀疏。
这个算法会产生推荐基于一些最相似的用户。它能够衡量两个用户A和B的相似性以某种方式，一种通用的方式就是衡量两个向量的余弦相似度：
这个算法能够从相似用户的物品中进行选择作为推荐，通用的方式就是去对每个物品进行排序，评分的标准就是有多少相似的用户购买过它。
使用协同过滤去产生推荐是计算非常昂贵的。它最坏情况下的复杂度为
它是很可能去部分的解决这些规模问题通过减少数据大小。我们会通过随机采样减少M的数量或者时丢弃一些几乎没买什么物品的顾客，还可以通过丢弃那些受欢迎和不受欢迎的物品来减少N的数量。还有一种方式就是减少物品的数量通过一些因素特征将他们进行分区根据物品的类别或者感兴趣的分类。维度缩减技术例如聚类或者主成分分析成狗通过一些因素来减少M和N的数量。
不幸的是，所有这些方式都会降低推荐的质量，首先，算法只进行计算少量的用户采样，那么算法挑选出来的顾客将会与目标用户的相似性降低。第二，将物品进行分区会导致只能够推荐特定领域的物品。第三，i法国算法丢弃最受欢迎和不受欢迎的物品，他们将不会出现在推荐系统中，并且那些只买个这些物品的顾客将再也不会得到推荐。维度缩减技术适用于物品空间有重叠，可以使用这种方式来消除低频物品。还适用于那些相似用户分到不同的组中，像我们所描述的，聚类也会适当降低推荐质量。
四、聚类模型
为了去发现相似的用户群体，聚类模型会将用户分成几个部分，并且将这个任务转化成分类问题，算法的目标就是去将用户分配到包含最相似用户的部分群体中。然后它会使用这个部分群体的购买记录或者评分去产生推荐。
这个部分通常时使用聚类或者其它无监督的学习算法创建，尽管一些应用使用手动的进行分类。使用一个相似度的指标，一个聚类算法会将最相似的用户聚到一个组中。针对于大量的数据，获得最优聚类显然是不实际的，大多数是使用不同种方式的贪婪算法进行聚类。这些算法通常会以一小部分开始，随机选择一些用户。然后他们会重复进行匹配用户到存在的组别中，使用一些准备好的去创建新的或者合并存在的类。对于非常大的数据集，特别是那些高纬度的，采样或者降维是非常必要的。
一旦算法生成了这些组，他就会计算用户的相似度和不同的组，然后选择最相似的组，将用户分配进去，一些算法会将用户分配到多个组中并且描述互相的关系。
聚类模型有很好的线上可扩展性和表现能力比协同过滤，因为对比用户到一个受约束的类而不是整个的用户群体。复杂度和昂贵的聚类计算通常是线下计算的。然而推荐的质量是很低的，聚类模型会将大多数用户聚到一个类中，然后匹配目标用户到相应的群体，然后考虑所有当前类相似的用户的物品作为推荐。由于通过聚类模型发现的相似用户不是最相似的用户，所以他们推荐的物品往往不是特别相关。通过使用更多的细粒度的数据类别可能会提高推荐质量，但是这带来的影响就是计算起来特别的贵。
五、基于搜索方式
基于搜索或者文本的方式会将推荐问题看作是搜索相关的物品。如果一个用户购买或者评分过一个物品，这个算法会构造一个搜索去查找其它受欢迎的物品通过这个物品相同的作者，艺术家或者是导演，还有就是相似的关键词或者兴趣主题。如果用户买了 Godfather DVD，那么推荐算法可能推荐其它的犯罪戏剧标题，其它的例如 Marlon Brando或者其它的电影被Francis Ford Coppola所导演的电影。
如果用户有很多的购买历史或者评分，基于搜索的推荐算法仍然会表现的很好。对于一个用户如果购买过数以千计的物品，它是不实际的去搜索所有的物品，这个算法必须使用总数据的子集，这样就会减少推荐的质量。在所有的情况，这个算法的推荐质量是相对不好的，这个算法通常要门太笼统要么太狭窄。推荐系统应该帮助一个顾客发现新的、相关的和感兴趣的物品，但是这个算法没有达到这个目的。
六、基于物品的协同过滤
Amazon.com 使用推荐系统作为一个有目的性的营销工具在一些邮件运动或者是大多数的网站，包括高流量的Amazon.com的主页。
点击 "Your Recommendations" 链接会引领顾客去一个能够过滤他们的推荐的一个地方，并且能够看到为什么这些物品会被推荐。
我们的购物车推荐，将会提供顾客物品建议基于他们的购物车的物品。这个是相似的会与那些一时冲动购买的物品在一个超市中，但是我们的是为每个顾客个性化推荐的。
Amazon.com广泛的使用推荐算法去个性化它的网站给符合每个顾客的兴趣。由于现有的推荐算法是不能扩展到千万的顾客和物品数据，所以我们开发了属于我们自己的推荐算法。我们的算法叫做 Item-to-Item Collaborative Fitering ，能够扩展巨大的数据集并且能够实时的产生高质量的推荐列表。
七、怎样工作？
相反使用匹配相似的用户，我们的算法是进行匹配相似的物品，然后结合相似的物品放到推荐列表中。
为了确定最相似的匹配，这个算法会构建一个相似物品的表通过发现物品，那些顾客趋向卖的物品。我们可以构建一个物品和物品的一个矩阵，不断进行迭代成对的物品，然后计算其相似度为每对的物品。
可是，一些商品对没有共同的顾客，并且因此这个方式对处理时间和内存使用是不高效的。下面会提供一个更高的迭代方法通过计算一个物品和其相关物品的相似度。
for each item in prodect catelog I1
for each customer C who purchased I1
for each item I2 purchased by customer C
Record that a customer purchased I1 and I2
for each item I2
Compute the similarity between I1 and I2
计算不同物品之间的相似度存在多种方式，但是最常用的方式就是使用余弦相似度进行计算，每个向量会对应一个物品而不是一个用户，并且向量的M维度对应着那些顾客购买过它们。
这个离线计算需要大量的使劲啊，最坏的复杂度为
给定一个相似物品表，这个算法会发现不同物品的相似性然后根据物品的购买或者评分，然后来接这些物品，然后进行推荐最受欢迎的或者最具关联的物品，这个计算是非常的快，只依赖于用户购买过或者评分过物品的数量。
八、可扩展性
Amazon.com 有着超过2900万的顾客和数百万的物品，其它的零售商的数据可能比这个还要大。尽管这些数据为推荐提供了机会，但是它也是一个诅咒，由于数据量太大，为这些数据设计算法很难，前几个算法的数量级比这些数据小很多。
几乎所有现存在的算法都只使用于小数据集，例如，MovieLend数据集包含35000个用户和3000个物品，而且 EachMovie数据集包含4000个顾客和1600个物品。
对于这些大数据集，这些算法要进行扩展是非常贵的在离线计算部分。作为一个简短的对比展示，现有的算法都达不到标准：
- 传统的协同过滤不需要或者很少需要离线计算，而且它的计算式和用户和物品的数量成正比，这个算法是不实际的对于大的数据集，如果它不适用数据降维或者采样、分区这些方式，但是一旦使用，推荐的质量就会降低。
- 聚类模型能够在线下计算，但是推荐的质量是不怎么好，为了提高这个，就需要增多分类的数据，提高细粒度，但是这会使线上用户类别分类变得非常贵
- 基于搜索的模型会建立关键词、分类和作者的索引在线下，但是它不能够提供感兴趣、有目的的推荐，而且当用户和物品的规模过大时，也会变得表现极差。
Item-to-Item Collaborative Filtering的可扩展性和表现能力的关键地方就是它可以创建昂贵的物品相似矩阵在线下。这个算法的线上部分为根据用户的购买记录或者评分寻找相似的物品，它是仅仅依赖一些用户购买过或者评分过的物品。因此，这个算法时非常快的即使是在大数据的情况下。因为这个算法的推荐是与相似物品是高度关联的，这个推荐质量是非常好的。不像传统的协同过滤，这个算法表现得很好对于有限的用户数据，提供高质量的推荐，尽管一些用户只购买或2个或者3个物品。
九、总结
推荐算法提供了一个有效的方式去做有目的性的营销通过为每个用户做个性化的购物推荐。对于一个大的零售商，例如Amazon.com 一个好的推荐算法是可扩展到很大的用户和物品数据集的，需要次秒级的处理时间然后去产生线上推荐，能够去对用户数据的改变立刻做出相应，并且为用户推荐有吸引力的物品不管用户购买过物品或者评分的数量。不像其它的算法，基于物品的协同过滤是能够面临这个挑战的。
在将来，我们期待零售行业可以更广泛的应用推荐算法去做出有针对性地营销不管是在线下还是在线上。然后电商有着个性化推荐最容易的工具，但与传统的大规模方式相比，这项技术提高了交易率，这也将使离线零售商更具有吸引力地用于邮政邮件、优惠卷和其它形式地客户沟通。
References
1.J.B. Schafer, J.A. Konstan, and J. Reidl, “E-Commerce Recommendation Applications,” Data Mining and Knowledge Discovery, Kluwer Academic, 2001, pp. 115-153.
2.P. Resnick et al., “GroupLens: An Open Architecture for Collaborative Filtering of Netnews,” Proc. ACM 1994 Conf. Computer Supported Cooperative Work, ACM Press, 1994, pp. 175-186.
3.J. Breese, D. Heckerman, and C. Kadie, “Empirical Analysis of Predictive Algorithms for Collaborative Filtering,” Proc. 14th Conf. Uncertainty in Artificial Intelligence, Morgan Kaufmann, 1998, pp. 43-52.
4.B.M. Sarwarm et al., “Analysis of Recommendation Algorithms for E-Commerce,” ACM Conf. Electronic Commerce, ACM Press, 2000, pp.158-167.
5.K. Goldberg et al., “Eigentaste: A Constant Time Collaborative Filtering Algorithm,” Information Retrieval J., vol. 4, no. 2, July 2001, pp. 133-151.
6.P.S. Bradley, U.M. Fayyad, and C. Reina, “Scaling Clustering Algorithms to Large Databases,” Knowledge Discovery and Data Mining, Kluwer Academic, 1998, pp. 9-15.
7.L. Ungar and D. Foster, “Clustering Methods for Collaborative Filtering,” Proc. Workshop on Recommendation Systems, AAAI Press, 1998.
8.M. Balabanovic and Y. Shoham, “Content-Based Collaborative Recommendation,” Comm. ACM, Mar. 1997, pp. 66-72.
9.G.D. Linden, J.A. Jacobi, and E.A. Benson, Collaborative Recommendations Using Item-to-Item Similarity Mappings, US Patent 6,266,649 (to Amazon.com), Patent and Trademark Office, Washington, D.C., 2001.
10.B.M. Sarwar et al., “Item-Based Collaborative Filtering Recommendation Algorithms,” 10th Int’l World Wide Web Conference, ACM Press, 2001, pp. 285-295.
