[论文阅读&翻译]Item-to-Item Collaborative Filtering

Amazon.com Recommendations Item-to-Item Collaborative Filtering

个人感受：

这篇论文首先介绍了历史上的三种算法：传统协同过滤、聚类、基于搜索的算法。第一种方法在计算效率、少量数据上表现欠佳；第二种方法准确率欠佳；第三种方法比较“简单”，因此提出了大量计算在线下的物品-物品的相似记录进行推荐。

揣测一下作者的思路，计算量大是因为数据量大，但是其中有价值的就是其中购买的物品，而且对于购买的物品来说，我们推荐的也是根据购买的物品来推荐的，用户仅仅是提供了物品之间的关系，也就是说物品-用户记录-物品这样的逻辑联系起来的，用户提供了物品的关联信息，最终的目标还是推荐物品，因此作者从计算量的角度来说把大量计算放在线下，而且根据我的关注点——商品来提出了这种算法。

除此之外，大量的测试数据也是作者的宝贵财富，因为实验室可能根本就没有这样大量的真实数据进行测试。

推荐系统使用用户的购买信息来为用户推荐可能感兴趣的信息，当然，除了已有的信息之外，还可以使用用户的感兴趣或者地理或者其他特征信息，这些都是我们可以利用的信息。

在亚马逊上，我们的算法给每个用户制订了一个个性商店，里面根据历史记录来进行未来感兴趣信息的预测，统计结果显示，推荐系统的关键指标——点击率和转化率，这两个数据都要比横幅广告或者热销产品列表这样的推荐方式高。

因此，我们的推荐系统是很有必要的，当然需要满足这么几个条件：

要能处理大量数据；要能在半秒内产生高质量的结果；针对新的用户，没有太多的历史记录，也能产生有效信息；对于老用户，会有大量信息，也是要有效；用户数据的变化应该能及时的反应在推荐系统上。

常用的推荐方式有：传统的协同过滤、聚类模型和基于搜索的方法。

我们的算法：item-to-item协同过滤算法很厉害，几个条件都能达到。

推荐算法：

推荐算法往往是找一个用户群能够使得这个用户群购买的东西包含预测用户购买的东西，然后推荐这个集合中用户没有购买的东西。而我们的算法和基于搜索的算法都是从相似物品的角度出发，推荐最为相似的物品的。

传统协同过滤：

每个用户用一个向量来表示，这个向量很是稀疏，而且为了使得一些非畅销产品可能有更好的结果，向量中的每一项会乘上购买人数的倒数（这似乎确实是一个行之有效的方法，因为这样确实能够显著的降低热销商品的评价，能够从一定程度上来推广非热销商品，假设一个热销商品和一个非热销商品平均打分相同，可能性价比比较类似，但是由于我的算法对于热销商品有抑制，因此在乘上一个倒数之后，非热销商品就更可能被推荐；当然，热销商品可能是因为热销才会购买，因此在相似性上并没有什么效果，就像是中国的大学生都要看数学分析或者高等数学，这个差异性不大，但是如果两个人都读过《平凡的世界》，那么可能相似性会高一些）。

对于两个用户相似性的计算也是使用余弦相似性。

当然，这种协同过滤系统在计算上市很昂贵的，时间复杂度是0(MN),其中M是用户的个数，N是商品的个数。因为要计算个用户，以及每个用户的N个商品。但是因为这个矩阵很稀疏，因此复杂度大约是O(M+N)。检索每个用户大约是O(M)，因为大多是空项，但是其中确实有N个元素，因此是O(N)。因此最终是O(M+N)。对于大尺度的数据，这个算法啊有些吃不消。

不过可能的改进方法是减少数据规模，比如说去掉一些数据太少的用户，或者去掉大热或者不热的物品或者进行分类处理。聚类或者主成分析都是可以采用的显著降维的方法。

但是呢，这些方法都会降低推荐的质量，因为少数的用户可能不是最相似的用户，而且，商品的减少使得我的推荐限定在某些商品中，再有就是如果商品忽略流行或者不流行的商品，那么这些产品永远不会被推荐，那么只买这些商品的用户就买不到。因此降低N的算法会减少商品，降低M的算法会降低相似程度，都会降低推荐质量。

聚类模型

聚类模型的思想是把用户进行聚类然后将推荐问题归为一个分类问题。

非监督算法进行大规模数据的聚类是个困难的问题，所以现在大多是采用贪心算法进行大规模数据的聚类。

进行聚类之后就判断用户属于哪一个类别或者计算用户和多个类别之间的强度。

从性能上来说，聚类的方法确实好一些，但是从准确率上来说就低一些，因为聚类算法是把很多用户看作一个部分，而把一个用户分配到一个部分中，也许最相似的用户在其他部分中，而这个部分仅仅是比较相似的。解决方法是继续细分，但是这样就和传统的协同过滤效果要差不多了。

基于搜索的算法

基于搜索的算法把推荐问题看作是搜索相关物品的问题，给定用户的购买和打分，算法去寻找其他流行的相同作者或者有关系的商品。但是问题就是这钟（很单纯）的推荐方法对于购买比较少的用户推荐比较好，因为推荐的都是相关的，看了碟中谍1就推荐碟中谍2345，但是对于用户购买很多东西，这个算法就使用数据的子集，降低了质量，要么推荐非常细致，要么就是非常宽泛。

而关键是要寻找新的，用户可能感兴趣的物品。

Item-to-Item Collaborative Filtering

亚马逊给在首页上有给用户推荐商品，还有就是购买了这个商品的人还购买了什么，这样来推荐商品。亚马逊用了这些算法，但是在亚马逊的大数据集上基本上效果不大，因此自己推出了Item-to-Item Collaborative Filtering，不论是从数据尺度上海市质量或者是实时效果上都非常牛逼。（这就是坐着想表达的意思）

如何工作

不是通过计算用户相似度，Item-to-Item Collaborative Filtering会通过用户的购买和评价来计算物品和物品的相似度，这时候再根据物品的相似度来产生一个推荐列表。

为了决定对于特定物品的最相似的物品，这个算法建立了一个相似的物品的列表。我们只需要根据任意两个商品对进行计算就可以求出结果。当然，有些产品没有共同的用户，那么这时候这些情况下这个算法就是无效的。

接下来的算法给出了计算相似性的一个算法：对于任意一个物品，检索购买这个物品的用户购买其他商品的个数并且进行累加。我们可以通过很多方法计算两个物品的相似度，但是一个通常的方法就是使用余弦相似性。

这些计算都是线下的，理论上最坏时间复杂度为O（N^2M)，实际上的时间复杂度约为O(MN)，因为大多数用户的记录都是非常少的。

给一个物品相似度矩阵，算法找到相似的物品和打分是很容易的，这时候再找依据的就仅仅是购买的商品了。

算法的对比：

亚马逊有很多很多很多数据，这既是挑战，也是机遇。很多算法都是基于小数据，但是对于非常大的数据，大量的计算需要线下完成，作为一个比较，我们看一下：

传统的协同过滤算法几乎没有线下工作，线上计算的数据尺度也是有限的，除非能够降维，但是又会降低准确性。

聚类模型算法在线下做了很多工作，但是效果实在是太差，而如果提升效果，那么线上的计算量又上去了。

基于搜索的算法很粗放。

Item-to-Item Collaborative Filtering的关键就是大量计算先下完成。算法的在线就是查找相似的物品，计算就是根据用户的购买总数来决定的。因此算法对于大数据集非常快。因为算法能够推荐非常相关的物品，因此推荐质量也是杠杠的。不像传统的协同过滤，这个算法对于那些只有很少的购买历史的记录也是能够准确推荐的。

总结：

推荐算法根据用户的购买力是提供了一个有效的目标市场，一个好的推荐算法能够在大尺度上表现的非常好，需要的仅仅是很少的时间来计算推荐的结果，而且应该能够很好的对于用户的数据修改进行互动。不像其他的算法Item-to-Item Collaborative Filtering成功解决了重大技术难题。

未来，我们希望零售业能够更广泛的应用推荐系统开拓市场，线上和线下。当电子商务有了个性化的推荐的时候，还是希望线上线下共同发展。