Slope One 算法是由 Daniel Lemire 教授在 2005 年提出的一个 Item-Based 推荐算法。
Slope One 算法试图同时满足这样的的 5 个目标：
- 易于实现和维护：普通工程师可以轻松解释所有的聚合数据，并且算法易于实现和测试。
- 运行时可更新的：新增一个评分项，应该对预测结果即时产生影响。
- 高效率的查询响应：快速的执行查询，可能需要付出更多的空间占用作为代价。
- 对初次访问者要求少：对于一个评分项目很少的用户，也应该可以获得有效的推荐。
- 合理的准确性：与最准确的方法相比，此方法应该是有竞争力的，准确性方面的微小增长不能以简单性和扩展性的大量牺牲为代价。
使用这个图可以简明扼要的说明一下 Slope One 算法。
- User A 给 Item I 打分为 1；给 Item J 打分为 1.5。
- Uesr B 给 Item I 打分为 2。
- 问题是：User B 给 Item J 打分为多少？
- 使用 Slope One 算法，答案是：2.5，2+(1.5-1)=2.5。
是不是非常简单？！Slope One 算法就是这么简单，而且它居然还相当有效！详细的试验分析可以看这里“Slope One Predictors for Online Rating-Based Collaborative Filtering”。
喜欢 Python 的朋友可以看这篇 Blog，“tutorial about how to implement Slope One in Python”，非常详细的介绍了 Slope One 算法在 Python 下的实现步骤。当然了，这只是一个非常简单的实现，你可以使用 MovieLens 或者 EachMovie 的数据集进行一些简单地试验。但如果真正要把它投入到商业环境，还有许多其他的工作必须做好。
我正在使用 Python 实现一个推荐算法模块集，其中也实现了 Slope One 算法，但现在还比较简陋，不太适合开源，等完善一些之后，我会把它开源出来，和大家共享。
说起 Item-based collaborative filtering，还有一段有意思的争论，是关于它的起源的。
GroupLens 研究小组的 Sarwar 教授等人，于2001年5月在香港召开的第 10 届 WWW 大会上，发表了题为《Item-based Collaborative Filtering Recommendation Algorithms》的 paper[1]。现在看来，这篇 paper 在 Item-based Collaborative Filtering 方面是影响最广的，被引用的次数也最多，基本上见 Item-based 必见此文。在 2000 的时候，同是上文作者之一的 Karypis 曾经完成了《Evaluation of Item-based Top-N Recommendation Algorithms》，但它仅作为明尼苏达计算机系的一篇 Technical Report 进行了发表，可以看作是 paper[1] 的工作基础。
但实际上，早在 1998 年，Amazon 就已经开发出了自己的 Item-based 推荐系统，并投入了使用。同年，当时 Amazon 推荐系统的设计师、现在 Findory 的创始人 Greg，连同 Jacobi 和 Benson，使用“Collaborative Recommendations Using Item-to-Item Similarity Mappings”的名字对该项技术申请了专利。但该专利直到 2001 年才正式通过！并且在 Sarwar 等人的 paper[1] 里，并没有标明引用了此专利的内容。Greg 在自己的 blog 上专门撰文说明了此事 [1] [2]，并得到了 Economist 编辑 Tom Standage 的承认。在 2003 年，Greg 发表了题为《Amazon.com Recommendations: Item-to-Item Collaborative Filtering》的 paper，对 1998 年的专利内容进行了详细的说明。
这是一段挺有意思的事情。但更能引起我兴趣的，是这项已经被实践证明确实行之有效的技术——Item-based (or item-to-item) collaborative filtering ！
Item-based 方法也有一个基本的假设：能够引起用户兴趣的项，必定与其之前评分高的项相似。这个假设也是与我们日常生活中的行为相一致的，基本上喜欢《长尾理论》的人，都会去看《世界是平的》，不知道你怎么想，反正豆瓣就是这么认为的。
同 User-based 方法类似，Item-based 方法需要同样的三个步骤：1）得到User-item的评分数据；2）针对项的最近邻搜索，即对项进行相似度计算；3）产生推荐。但相对于 User-based 方法，Item-based 方法最大的改进是提高了协同过滤方法的扩展性及性能。
从上一篇中可以看到，在 User-based 方法中，随着用户数量的不断增多，在大数量级的用户范围内进行“最近邻搜索”会成为整个算法的瓶颈。Item-based 方法通过计算项之间的相似性来代替用户之间的相似性。对于项来讲，它们之间的相似性要稳定很多，因此可以离线完成工作量最大的相似性计算步骤，从而大大降低了在线计算量，提高推荐效率。
在 Item-based 方法中，要对 A 和 B 进行项相似性计算，通常分为两步：1）找出同时对 A 和 B 打过分的组合；2）对这些组合进行相似度计算，常用的算法包括：皮尔森相关系数、余弦相似性、调整余弦相似性和条件概率等。
在 paper[1] 里，Sarwar 教授通过试验得到 Item-based 方法的推荐效果要略好于 User-based 方法的结伦。但其实这也并不尽然。在 2003 年，Mild 教授从批判的角度重新审视了各种推荐算法，指出基于 Item-based 方法并不一定好，算法准确度与采用的实验数据数据有关，大多数情况下还是 User-based 方法好。我个人倒是认为，其实没有绝对的好坏之分，而应该根据问题的不同和数据集的特点，选择最合适的方法。
上面所说的偏重于学术界一些，算法的出发点还是基于打分，多数使用的是 MovieLens 的数据。工业界实际使用的多是在基本 Item-based 方法基础上的变形，例如基于关联规则的方法，这些方法最大的变化就是在计算项的相似度方面做文章。其实正如 Greg 曾经说过的，协同过滤最大的特点是“以数据为先”的，只当有了大量的数据积累，才可能找到最有效的、最适宜的方法。
后面我将会陆续写一些实际算法方面的东西，欢迎互动交流。
还有一些图片，不过也得等海那边的光缆修好之后，我才能发上来。
协同过滤（Collaborative Filtering）技术，是推荐系统中应用最为广泛的技术之一。顾名思义，“Collaborative” 本身就已经说明了协同过滤算法的主要意思，它基于一组兴趣相同的用户进行推荐。协同过滤基于这样的假设：为用户找到他真正感兴趣的内容的好方法是，首先找他与他兴趣相似的用户，然后将这些用户感兴趣的内容推荐给此用户。这个基本思想是不是和现在颇为流行的“口碑传播(word-of-mouth)”有点儿类似？其实这个非常直观，相信大家都有体会，在现实生活里，对自己最有效的信息，往往是来自于朋友们的推荐。
协同过滤技术可以分为三类：基于用户（User-based）的协同过滤；基于项目（Item-based）的协同过滤；基于模型（Model-based）的协同过滤。这篇文章针对基于用户（User-based）的协同过滤技术。建立一个基于用户的协同过滤系统通常需要三个步骤。
步骤一，收集可以代表用户兴趣的信息。
传统的系统一般使用打分的方式，最著名的例如 MovieLens 。豆瓣上经常出现在右侧的“我来评价”也是这种方法。这种方式被称为“显式评分”方法。但它有一个明显的缺点，收集数据比较困难，用户通常并不愿意费力气为你贡献这种数据。这导致这种系统通常更多出现在实验室或者论文里面。在实际的商业系统中，即使使用了这种方法，也多会被包装为一种更加 user-friendly 的样子。
另外一种被认为更有效的方法是“隐式评分”方法。这种方法不需要用户直接输入评价数据，而是根据用户的行为特征由系统代替用户完成评价。一种研究得比较多的方法是 Web Mining 。电子商务网站在隐式评分的数据获取上有先天的优势，用户购买的商品记录是非常有用的数据。你在豆瓣上写书评，其实也是在为豆瓣贡献着这种评分数据。
步骤二，最近邻搜索。
协同过滤的出发点是与你兴趣相同的一组用户，术语叫做“最近邻”。最近邻搜索的核心是计算两个用户的相似度。例如用户A和用户B，首先需要获取用户A和用户B所有的评分项，然后选择一个合适的相似度计算方法，基于评分项数据，计算得到用户A和用户B的相似度数值。目前使用比较多的相似度算法包括，皮尔森相关系数（Person Correlation Coefficient）、余弦相似性（Cosine-based Similarity）以及调整余弦相似性（Adjusted Consine Similarity）。这里有一个试验，结论是“调整余弦相似性”算法的准确性较好。不知道豆瓣使用的是哪种算法？肯定不会仅使用一种，通常情况下，会根据数据集的不同选择不同的算法。
步骤三，生成推荐结果。
有了最近邻集合，就可以对目标用户的兴趣进行预测，生成推荐结果。通常根据推荐目的的不同，可以进行多种形式的推荐。最常见的推荐结果有两种，Top-N 推荐和关联推荐。
Top-N 推荐，这里的 Top-N 和一般网站（比如 digg）上见到的“最热门”列表是不同的。热门列表是基于全部数据集产生的，它对每个人都是一样的；Top-N 推荐是针对单个用户产生的，它对每个人是不一样的：通过对你的最近邻用户进行统计，选择出现频率最高且在你的评分项目中不存在的项目作为推荐结果。豆瓣上的“排行”栏目，应该是传统的“热门”列表，不是 Top-N 推荐。
关联推荐，也称为基于关联规则的推荐。与传统关联规则针对全部数据进行挖掘不同的是，此方法仅对最近邻用户的购买记录进行关联规则挖掘。如果你曾经购买过关联规则左边的商品，而没有购买过关联规则右边的商品，那么就把右边的这个商品推荐给你。它最突出的优点就是，可以帮助你发现你感兴趣的而以前却从来没有注意过的商品。在 Amazon 介绍书的详细信息的页面上，可以看到这种推荐的一个实际应用。例如在《The Search》的页面上，Amazon 给我的推荐是，
基于用户的协同推荐算法随着用户数量的增多，计算量成线性加大，其性能会越来越差。而对于 Web 应用系统，响应速度绝是影响用户体验的最重要因素之一。这一点极大的限制了基于用户的协同过滤技术在实际系统中的使用。Amazon 更多地使用了基于项目（Item-based）的协同过滤技术，而且随着 Amazon 的成功，Item-based 方法也大为流行起来。豆瓣主要使用的也是 Item-based 方法。在下一篇文章里，我会重点介绍 Item-based 方法。
Answers 上面关于 Collaborative Filtering 的 Topic 是一个好的学习起点。另外在 del.icio.us 上可以找到不少关于协同过滤的资料。
