如何从无到有建立推荐系统
推荐系统广泛应用于各类网站，电子商务中的商品推荐、博客网站的文章推荐，以及帮助人们寻找音乐和影片的各类应用。但如何才能从无到有的给网站配备一个推荐系统呢？针对这个问题，我在搜索引擎中遍寻多时，但始终没有找到满意的答案。这期间我也加入了国内推荐系统高手聚集的推荐系统邮件列表，其中不乏当当、卓越亚马逊、豆瓣等业内在推荐系统上领先的产品、技术高手，但浸淫多日却始终无法在脑海中形成一个以内容推荐为最终目的的产品框架或产品路线图。这种状态一直持续到我购买了集体智慧编程（Programming Collective Intelligence）后才得以改观，现在我将此书的部分读书笔记予以整理，希望能给同样对推荐系统感兴趣的朋友整理出一个可操作的、适合内容型网站推荐系统产品框架。
——————–正文分割线——————–
我们知道，要想了解内容网站的推荐信息，最没有技术含量的方法莫过于向朋友询问。我们也知道，这其中有一部分人的品位会比其他人的高一些，通过观察这些人是否通常也和我们一样喜欢同样的东西，可以逐渐对这些情况有所了解。不过随着选择越来越多，要想通过询问一小群人来确定我们想要的东西，将会变得越来越不切实际，因为他们可能并不了解所有的选择。这就是为什么人们要发展出一套被称为协同过滤（collaborative filtering）的技术。从实际的情况看，目前我们所能接触到的领先推荐系统，包括Netfilx、豆瓣、Amazon等等都是利用协同过滤技术来实现的。协同过滤又分成几种：基于用户的协同过滤、基于项目的协同过滤、基于模型的协同过滤。
那么到底什么是协同过滤？它需要产品设计者做哪些事情才能实现？（为了让问题简化，这里着重介绍基于用户的协同过滤）
一个基于用户的协同过滤过滤算法通常的做法是对一大群人进行搜索，并从中找出与我们品位相近的一小群人。算法会对这些人所偏爱的其他内容进行考察，并将它们组合起来构成一个经过排名的推荐列表。因此产品设计者需要理解你的网站需要依次做以下这几件事情：
1.搜集偏好（Collecting Preferences）
要搜集偏好意味着要寻找一种表达不同人及其偏好的方法。例如，豆瓣会要求用户对每部电影用1到5颗星来评分，以此来体现包括本人在内的每位影评者对某一给定影片的喜爱程度。假如你正在设计一个购物网站，那不妨用数字1来代表有人过去购买过某件商品，用数字0来代表未曾购买过任何商品。而对于一个新闻故事投票网站，我们可以分别用数字-1、0和1来表达“不喜欢”、“没有投票”、“喜欢”。不管偏好如何表达的，你要做的是建立一种方法来使得你的用户来参与表达，并把他们表达的内容对应到数字以形成相应的数据集合。
2.寻找相近的用户（Finding Similar Users）
有了人们偏好的数据集后，我们需要有一种方法来确定人们在品位方面的相似程度。为此，我们可以将每个人与所有其他人进行对比，并计算他们的相似度评价值。有若干种方法可以达到此目的：欧几里德距离（Euclidean Distance Score）、皮尔逊相关度（Person Correlation Coefficient）、余弦相似性（Cosine-based Similarity）、调整余弦相似性（Adjusted Cosine Similarity）、Jaccard系数或曼哈顿距离算法等。请记住，各种相似度的计算方法各有所长，要根据具体的应用场景来选取一种或几种综合使用。
下面以实际例子简单介绍两种：
欧几里德距离（Euclidean Distance Score）：它以经过人们一致评价的物品为坐标轴，然后将参与评价的人绘制到图上，并考察他们彼此间的距离远近。x轴、y轴分别代表电影Dupree和Snake，而在第一象限偏好空间里的则是每个人对这两部电影的评分。
不难发现，Toby对Snakes和Dupree这两部电影的评分是4.5和1.0，而LaSalle的则是4.0和2.0。按照欧几里德距离的结论，偏好越相似的人，其在偏好空间的距离就越短。至于如何计算两者的距离，运用你初中学的几何知识就行，计算两点每个坐标的差值，求平方后再相加，最后对总和取平方根。值得一提的是此方法对于数量多于两项的评分也同样适用。因此，你可以设计一个函数来计算2个用户间的相似度，当然前提是两者需要有一定重合的评分项。
皮尔逊相关度（Pearson Correlation Score）：它的原理是通过判断两组数据与某一直线拟合程度来判断相似度。它在数据不是很规范（normalized）的时候，如影评者对影片的评价总是相对于平均水平偏离很大时，会倾向于给出更好的结果。
如下图是Mick LaSalle和Gene Seymour分别对5部电影的评分（与上图不同，x轴和y轴对应的是两个人），虚线被称为最佳拟合线（best-fit line），其绘制原则是尽可能地靠近图上的所有坐标点。如果两位评论者对所有影片的评分情况都相同，那么这条直线将成为对角线，并且会与图上所有的坐标点都相交。
下图展示了一个有着更高相关系数的例子，这意味着Lisa Rose和Jack Matthews在这几部电影上有着更高的相似度（各点更靠近最佳拟合曲线）。
采用皮尔逊方法可以修正“夸大分值（grade inflation）”的情况。在上图中，虽然Jack总是倾向于给出比Lisa更高的分数，但最终的直线仍然拟合度较高，这是因为他们两者有着相对近似的偏好。也就是说，如果某人总是倾向于给出比另一人更高的分数，而两者的分差又始终保持一致，则他们依然可能会存在很好的相关性。而此前提到过的欧几里德距离评价方法，会因为一个人的评价始终比另一个人更为“严格”（从而导致评价始终相对较低），而得出两者不相近的结论，即使他们的品位很相似也是如此。而这一行为是否是我们想要的结果，取决于具体的应用场景。
皮尔逊的相关度算法首先会找出两位评论者都曾评价过的物品，然后计算两者的评分总和和平方和，并求得评分的乘积之和。最后，利用这些计算结果计算出相关系数：
PS：公式能看懂，但我还未能从数学上去理解此公式的推导过程，惭愧-_-|||
3.为评论者打分（Ranking the Critics）
理解了上一步后，这步就简单了。现在只需根据指定的人员对每个人进行打分，找出最接近的匹配结果，也即所谓该人的最近邻。回到上面的例子，我们的目的是要寻找与自己品位相似的影评者，那么所需要做的就是以你自己为基准，计算每个人和你的相似度，然后排序输出前几项即可。现在假设你是Toby，那么经过这一步的计算你会得到一个你的最近邻列表，也就是说你可能会知道Lisa、Mick和Claudia可能是和你品位最相近的3个人。
4.推荐物品（Recommending Items）
找到一位和你趣味相投的影评者固然不错，但我们的最终目的是一份影片的推荐列表（上面提到过的以内容推荐为最终目的）。当然，简单的做法是查找与自己品位最相近的人，并从他所喜欢的影片中找出一部自己还未看过的影片，但这样做有些随意或者是粗糙。因为如果该人还未对某些影片做过评论，但这些影片也许就是我们所喜欢的。又或者另外的一种情况就是推荐给你某人特别热衷的一部影片，但有其他可靠数据表明所有的其他评论者都不看好这部影片。
为了解决上述问题，我们需要一个经过加权的评价值来为影片打分：
上图中Critic列是与Toby进行相似度对比的人名，Similarity列表示他们与Toby的相似度系数。Night、Lady和Luck都是电影名，所在列是这些人对这些电影的评分。S.x打头的那几列给出了相似度系数和评分后相乘的结果。如此一来，相比于我们不相近的人，那些与我们相近的人将会对整体评价拥有更多的贡献。
那有人会问为什么不直接采用Total这行，而需要Total/Sim.Sum？这是因为，一部受更多人评论的影片会对结果产生更大的影响，因此我们必须要除以Sim.Sum，它代表了所有对这部电影有过评论的评论者的相似度之和。就像Night这部电影，Total为12.89，有5个人为其评分，而Lady为8.38，4个人评分。假设电影Night有和当前相同的Total分数却多了一倍的人为其评分，那最后的结果也未必一定比电影Lady的Total/Sim.Sum更好。
好了，我们现在已经得到了一个经过排名的影片列表了，你可以决定自己究竟要不要观看其中的某一部，或者干脆什么也别看。其实，有时候什么都不推荐也是一种推荐。
最后我用lovelycharts画了这张流程图（用的时候才现不支持中文噢）。如果你想要设计一个推荐系统，现在应该大概清楚要做哪几件事情了吧：）
协同过滤（Collaborative Filtering）扫盲班（5）
Slope One协同过滤算法
Slope One是一个简单高效的协同过滤算法，由 Daniel Lemire 教授在 2005 年提出。
基本概念
用户X，Y和Z都对Item1打了分。 同时用户X，Y还对Item2打了分，用户Z对Item2可能会打多少分呢?
| 用户 | 对Item1的评分 | 对Item2的评分 |
| X | 5 | 3 |
| Y | 4 | 3 |
| Z | 4 | ? |
计算方法：4 – ((5-3) + (4-3))/2 = 2.5，找到对Item1和Item2都打过分的用户，算出rating差的平均值，这样我们就能推测出对Item1打过分的用户Z对Item2的可能的评分，并据此向Z用户推荐新项目。
Slope One的优点
这里我们能看出Slope One算法的一个很大的优点，在只有很少的数据时候也能得到一个相对准确的推荐, 这一点可以解决Cold Start的问题。
另外一种情况
如果100个用户对Item1和Item2的评分差的平均值是2，1000个用户对Item2和Item3的评分差的平均值是-3，那Item1相对Item3的评分情况又是如何？显然这两个rating差的权重是不一样的。因此我们的计算过程是：
- (100×(Rating 1 to 2) + 1000×(Rating 3 to 2)) / (100 + 1000)
- (100×2 + 1000×(-3)) / (100 + 1000)
- -2800/1100
- 约等于-2.55
也就是说Item1和Item3的评分差的平均值是2.55
协同过滤（Collaborative Filtering）扫盲班（4）
协同过滤的几种应用方式
以使用者为基础（User-based）的协同过滤：
用相似统计的方法得到具有相似爱好或者兴趣的相邻使用者，所以称之为以使用者为基础（User-based）的协同过滤或基于邻居的协同过滤(Neighbor-based Collaborative Filtering)。方法步骤：
1.收集使用者资讯
收集可以代表使用者兴趣的资讯。一般的网站系统使用评分的方式或是给予评价，这种方式被称为「主动评分」。另外一种是「被动评分」，是根据使用者的行为模式由系统代替使用者完成评价，不需要使用者直接打分或输入评价资料。电子商务网站在被动评分的资料获取上有其优势，使用者购买的商品记录是相当有用的资料。
2.最近邻搜索(Nearest neighbor search, NNS)
以使用者为基础（User-based）的协同过滤的出发点是与使用者兴趣爱好相同的另一组使用者，就是计算两个使用者的相似度。例如：寻找n个和A有相似兴趣使用者，把他们对M的评分作为A对M的评分预测。一般会根据资料的不同选择不同的演算法，目前较多使用的相似度演算法有Person Correlation Coefficient、Cosine-based Similarity、Adjusted Cosine Similarity。
3.产生推荐结果
有了最近邻集合，就可以对目标使用者的兴趣进行预测，产生推荐结果。依据推荐目的的不同进行不同形式的推荐，较常见的推荐结果有Top-N推荐和关联推荐。 Top-N推荐是针对个体使用者产生，对每个人产生不一样的结果，例如：透过对A使用者的最近邻使用者进行统计，选择出现频率高且在A使用者的评分项目中不存在的，作为推荐结果。关联推荐是对最近邻使用者的记录进行关联规则(association rules)挖掘。
以项目为基础（Item-based）的协同过滤：
以使用者为基础的协同推荐演算法随着使用者数量的增多，计算的时间就会变长，所以在2001年Sarwar提出了基于项目的协同过滤推荐演算法(Item-based Collaborative Filtering Algorithms)。以项目为基础的协同过滤方法有一个基本的假设：“能够引起使用者兴趣的项目，必定与其之前评分高的项目相似”，透过计算项目之间的相似性来代替使用者之间的相似性。方法步骤：
1.收集使用者资讯
同以使用者为基础（User-based）的协同过滤。
2.针对项目的最近邻搜索
先计算己评价项目和待预测项目的相似度，并以相似度作为权重，加权各已评价项目的分数，得到待预测项目的预测值。例如：要对项目A和项目B进行相似性计算，要先找出同时对A和B打过分的组合，对这些组合进行相似度计算，常用的演算法同以使用者为基础（User-based ）的协同过滤。
3.产生推荐结果
以项目为基础的协同过滤不用考虑使用者间的差别，所以精度比较差。但是却不需要使用者的历史资料，或是进行使用者识别。对于项目来讲，它们之间的相似性要稳定很多，因此可以离线完成工作量最大的相似性计算步骤，从而降低了线上计算量，提高推荐效率，尤其是在使用者多于项目的情形下尤为显著。
以模型为基础（Model- based）的协同过滤：
以使用者为基础（User-based）的协同过滤和以项目为基础（Item-based）的协同过滤统称为以记忆为基础（Memory based）的协同过滤技术，他们共有的缺点是资料稀疏，难以处理大资料量影响即时结果，因此发展出以模型为基础的协同过滤技术。以模型为基础的协同过滤(Model-based Collaborative Filtering)是先用历史资料得到一个模型，再用此模型进行预测。以模型为基础的协同过滤广泛使用的技术包括Latent Semantic Indexing、 Bayesian Networks…等，根据对一个样本的分析得到模型。
协同过滤（Collaborative Filtering）扫盲班（3）
协同过滤的优缺点
优点（使用者的角度）:
- 能够过滤机器难以自动内容分析的资讯，如艺术品，音乐等。
- 共用其他人的经验，避免了内容分析的不完全或不精确，并且能够基于一些复杂的，难以表述的概念（如信息品质、个人品味）进行过滤。
- 有推荐新资讯的能力。可以发现内容上完全不相似的信息，使用者对推荐信息的内容事先是预料不到的。可以发现使用者潜在的但自己尚未发现的兴趣偏好。
- 推荐个性化、自动化程度高。能够有效的利用其他相似使用者的回馈信息。加快个性化学习的速度。
缺点：
虽然协同过滤作为一推荐机制有其相当的应用，但协同过滤仍有许多的问题需要解决。整体而言，最典型的问题有：
- 新使用者问题(New User Problem)，系统开始时推荐品质较差。
- 新项目问题(New Item Problem)，品质取决于历史资料集。
- 稀疏性问题（Sparsity） 。
- 系统延伸性问题（Scalability）。
协同过滤（Collaborative Filtering）扫盲班（2）
协同过滤发展历史
Tapestry（1992）
这是最早应用协同过滤系统的设计，主要是解决Xerox公司在Palo Alto的研究中心资讯过载的问题。这个研究中心的员工每天会收到非常多的电子邮件却无从筛选分类，于是研究中心便发展这项实验性的邮件系统来帮助员工解决这项问题。其运作机制大致如下：
- 个人决定自己的感兴趣的邮件类型；
- 个人旋及随机发出一项资讯需求，可预测的结果是会收到非常多相关的文件；
- 从这些文件中个人选出至少三笔资料是其认为有用、会想要看的；
- 系统便将之记录起来成为个人邮件系统内的过滤器，从此以后经过过滤的文件会最先送达信箱；
以上是协同过滤最早的应用。
GroupLens（1994）
这个系统主要是应用在新闻的筛选上，帮助新闻的阅听者过滤其感兴趣的新闻内容，阅听者看过内容后给一个评比的分数，系统会将分数记录起来以备未来参考之用，假设前提是阅听者以前感兴趣的东西在未来也会有兴趣阅听，若阅听者不愿揭露自己的身分也可以匿名进行评分。和Tapestry不同之处有两点，首先，Tapestry专指一个点（如一个网站内、一个系统内）的过滤机制；GroupLens则是跨点跨系统的新闻过滤机制。再来，Tapestry不会将同一笔资料的评比总和起来；GroupLens会将同一笔资料从不同使用者得到的评比加总。 GroupLens具有以下特点：
- 开放性：所有的新闻阅听者皆可使用，虽然系统委托Better Bit Bureau设计给分的系统，但若有不同的评分机制也适用于GroupLens。
- 方便性：给分并不是一件困难的事情且沟通上非常方便，评分结果容易诠释。
- 规模性：有可能发展成大规模的系统，一旦发展成大规模，储存空间与计算成本问题显得相当棘手。
- 隐密性：如果使用者不想让别人知道他是谁，别人就不会知道。
由此可以看出，现今网络各个推荐系统的雏形已然形成，在GroupLens之后还有性质相近的MovieLens，电影推荐系统；Ringo，音乐推荐系统；Video Recommender，影音推荐系统；以及Jster，笑话推荐系统等等。乃至于今日的YouTube、aNobii皆是相似性值得网络推荐平台，较不同的是经过时间推移，网络越来越发达，使用者越来越多，系统也发展得越来越严密。
电子商务的推荐系统
最著名的电子商务推荐系统应属亚马逊网络书店（Amazon.com），顾客选择一本自己感兴趣的书籍，马上会在底下看到一行“Customer Who Bought This Item Also Bought”，亚马逊是在“对同样一本书有兴趣的读者们兴趣在某种程度上相近”的假设前提下提供这样的推荐。此举也成为亚马逊网络书店为人所津津乐道的一项服务。各网络书店也跟进做这样的推荐服务，如台湾的博客来网络书店。另外一个著名的例子是Facebook的广告，系统根据个人资料、周遭朋友感兴趣的广告等等对个人提供广告推销，也是一项协同过滤重要的里程碑，和前二者Tapestry、GroupLens不同的是，在这里虽然商业气息浓厚，但同时还是带给使用者很大的方便。
最后总结
以上为三项协同过滤发展上重要的里程碑，从早期单一系统内的邮件、文件过滤，到跨系统的新闻、电影、音乐过滤，乃至于今日横行互联网的电子商务，虽然目的不太相同，但带给使用者的方便是大家都不能否定的。
协同过滤（Collaborative Filtering）扫盲班（1）
这是一个关于协同过滤（Collaborative Filtering）的扫盲系列。虽不一定能解决实际问题，但协同过滤作为一种信息处理方式所起的作用将越来越大，那么现在就开始吧：
协同过滤的定义：
协同过滤（Collaborative Filtering）简单来说是利用某兴趣相投、拥有共同经验之群体的喜好来推荐使用者感兴趣的信息。个人透过合作的机制给予信息相当程度的回应（如评分）并记录下来以达到过滤的目的进而帮助别人筛选信息。回应不一定局限于特别感兴趣的，特别不感兴趣信息的记录也相当重要。协同过滤又可分为评比（rating）或者群体过滤（social filtering）。后者成为电子商务当中很重要的一环，即根据某顾客以往的购买行为以及从具有相似购买行为的顾客群的购买行为去推荐这个顾客其“可能喜欢的品项”，也就是藉由社群的喜好提供个性化的信息、商品等的推荐服务。除了推荐之外，近年来也发展出数学运算让系统自动计算喜好的强弱进而使得过滤的内容更有依据，也许不是百分之百完全准确，但由于加入了强弱的评比让这个概念的应用更为广泛。除了电子商务之外尚有资讯检索领域、网络个人影音柜、个人书架等的应用等，豆瓣就是一个使用协同过滤的好例子。
协同过滤的本质及基本假设：
基于一组兴趣相同的用户进行推荐。它基于这样一个假设：为用户找到他真正感兴趣的内容的好方法是首先找到与他兴趣相似的用户，然后将这些用户感兴趣的内容推荐给此用户。
协同过滤的分类：
基于用户（User-based）、基于项目（Item-based）、基于模型（Modal-based）。
哪些地方用到了协同过滤
豆瓣、Amazon、Netfix等等内容或电子商务网站都采用协同过滤来给用户推荐内容。
