本文是关于推荐系统的系列研究文章之一，其他内容将陆续发布。这些内容，大多数来自我在2004年底完成的一篇项目方案建议书。放在这里，抛砖引玉，供大家讨论之用。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

一、引言

Internet的迅猛发展将人类带入了信息社会和网络经济时代，对企业发展和个人生活都产生了深刻的影响。一方面，基于Internet的虚拟企业不再需要像传统的物理环境下企业那样的实体投资，企业与顾客、供应商等建立起更直接的联系，电子商务模式为企业发展提供了更多的机会；同时，Internet的发展正在极大地改变我们每个人的生活，人们不出家门就可随心所欲地得到自己想要的商品，网上购物的经历让我们感受到电子商务带来的惊喜。

在电子商务的虚拟环境下，商家所提供的商品种类和数量非常多，用户不可能通过一个小小的计算机屏幕一眼就知道所有的商品，用户也不可能象在物理环境下那样检查挑选商品。因此，需要商家提供一些智能化的选购指导，根据用户的兴趣爱好推荐用户可能感兴趣或是满意的商品，使用户能够很方便地得到自己所需要得到的商品。而且，从现实经验来看，用户的需求经常是不明确的、模糊的，可能会对某类商品有着潜在的需求，但并不清楚什么商品能满足自己的模糊需求。这时，如果商家能够把满足用户模糊需求的商品推荐给用户，就可以把用户的潜在需求转化为现实的需求，从而提高产品的销售量。

在这种背景下，推荐系统（Recommender Systems）应运而生，它是根据用户的特征，比如兴趣爱好，推荐满足用户要求的对象，也称个性化推荐系统（Personalized Recommender Systems）。实际中应用最多的，是在网上购物（尤其是B2C类型）环境下的、以商品为推荐对象的个性化推荐系统，它为用户推荐符合兴趣爱好的商品，如书籍，音像等。

二、概念

现在被广泛引用的推荐系统（Recommender System）的定义是Resnick & Varian 在1997年给出的：“它是利用电子商务网站向客户提供商品信息和建议，帮助用户决定应该购买什么产品，模拟销售人员帮助客户完成购买过程”。

推荐有三个组成要素：推荐候选对象、用户、推荐方法，如图1所示。推荐活动在我们日常生中普遍存在，根据不同的推荐对象和推荐方法，推荐活动形式多样，如，超市购物导购员为用户推荐用户喜爱的产品，提高销售能力；现实生活中朋友间相互推荐喜爱的电影；推销员向用户推销产品等，都是推荐活动，可以说，只要存在多个候选对象，就存在选择问题，存在选择就有推荐问题存在。

三、作用

个性化推荐的最大的优点在于，它能收集用户特征资料并根据用户特征，如兴趣偏好，为用户主动作出个性化的推荐。而且，系统给出的推荐是可以实时更新的，即当系统中的商品库或用户特征库发生改变时，给出的推荐序列会自动改变。这就大大提高了电子商务活动的简便性和有效性，同时也提高了企业的服务水平。

总体说来，一个成功的个性化推荐系统的作用主要表现在以下三个方面：
1） 将电子商务网站的浏览者转变为购买者：电子商务系统的访问者在浏览过程中经常并没有购买欲望，个性化推荐系统能够向用户推荐他们感兴趣的商品，从而促成购买过程。
2） 提高电子商务网站的交叉销售能力：个性化推荐系统在用户购买过程中向用户提供其他有价值的商品推荐，用户能够从系统提供的推荐列表中购买自己确实需要但在购买过程中没有想到的商品，从而有效提高电子商务系统的交叉销售。
3） 提高客户对电子商务网站的忠诚度：与传统的商务模式相比，电子商务系统使得用户拥有越来越多的选择，用户更换商家极其方便，只需要点击一两次鼠标就可以在不同的电子商务系统之间跳转。个性化推荐系统分析用户的购买习惯，根据用户需求向用户提供有价值的商品推荐。如果推荐系统的推荐质量很高，那么用户会对该推荐系统产生依赖。因此，个性化推荐系统不仅能够为用户提供个性化的推荐服务，而且能与用户建立长期稳定的关系，从而有效保留客户，提高客户的忠诚度，防止客户流失。

个性化推荐系统具有良好的发展和应用前景。目前，几乎所有的大型电子商务系统，如Amazon、eBay等，都不同程度的使用了各种形式的推荐系统。各种提供个性化服务的Web站点也需要推荐系统的大力支持。在日趋激烈的竞争环境下，个性化推荐系统能有效的保留客户，提高电子商务系统的服务能力。成功的推荐系统会带来巨大的效益。

四、现有推荐系统

目前，推荐系统已经运用到多个行业中，推荐对象包括书籍、音像、网页、文章、新闻等，如表1。大多数的推荐系统主要应用在电子商务和Web中，其中已应用到商业中的推荐系统主要有电子商务、电影和音乐等领域。这反映推荐系统想要运用到商业中，必须能够为用户提供一个确实有价值的推荐功能，从而为商业企业带来一定的经济价值。

表1 主要推荐系统一览表
领域	推荐系统
电子商务	Amazon.com，eBay，Levis，Ski-europe.com
网页	Fab，Foxtrot，ifWeb，MEMOIR，METIOREW，ProfBuilder，QuIC，Quickstep，R2P，Siteseer，SurfLen
音乐	CDNOW，CoCoA，Ringo
电影	Moviefinder.com，MovieLens，Reel.com
新闻过滤	GroupLens，PHOAKS，P-Tango

转载自：google黑板报，http://googlechinablog.com/2006/04/blog-post.html。

发表者: 吴军, Google 研究员

系列一： 统计语言模型 (Statistical Language Models)

Google 的使命是整合全球的信息，所以我们一直致力于研究如何让机器对信息、语言做最好的理解和处理。长期以来，人类一直梦想着能让机器代替人来翻译语言、识别语音、认识文字（不论是印刷体或手写体）和进行海量文献的自动检索，这就需要让机器理解语言。但是人类的语言可以说是信息里最复杂最动态的一部分。为了解决这个问题，人们容易想到的办法就是让机器模拟人类进行学习 - 学习人类的语法、分析语句等等。尤其是在乔姆斯基（Noam Chomsky 有史以来最伟大的语言学家）提出 “形式语言” 以后，人们更坚定了利用语法规则的办法进行文字处理的信念。遗憾的是，几十年过去了，在计算机处理语言领域，基于这个语法规则的方法几乎毫无突破。

其实早在几十年前，数学家兼信息论的祖师爷 香农 (Claude Shannon)就提出了用数学的办法处理自然语言的想法。遗憾的是当时的计算机条件根本无法满足大量信息处理的需要，所以他这个想法当时并没有被人们重视。七十年代初，有了大规模集成电路的快速计算机后，香农的梦想才得以实现。

首先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师贾里尼克 (Fred Jelinek)。当时贾里尼克在 IBM 公司做学术休假 (Sabbatical Leave)，领导了一批杰出的科学家利用大型计算机来处理人类语言问题。统计语言模型就是在那个时候提出的。

给大家举个例子：在很多涉及到自然语言处理的领域，如机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询中，我们都需要知道一个文字序列是否能构成一个大家能理解的句子，显示给使用者。对这个问题，我们可以用一个简单的统计模型来解决这个问题。

如果 S 表示一连串特定顺序排列的词 w1， w2，…， wn ，换句话说，S 可以表示某一个由一连串特定顺序排练的词而组成的一个有意义的句子。现在，机器对语言的识别从某种角度来说，就是想知道S在文本中出现的可能性，也就是数学上所说的S 的概率用 P(S) 来表示。利用条件概率的公式，S 这个序列出现的概率等于每一个词出现的概率相乘，于是P(S) 可展开为：

P(S) = P(w1)P(w2|w1)P(w3| w1 w2)…P(wn|w1 w2…wn-1)

其中 P (w1) 表示第一个词w1 出现的概率；P (w2|w1) 是在已知第一个词的前提下，第二个词出现的概率；以次类推。不难看出，到了词wn，它的出现概率取决于它前面所有词。从计算上来看，各种可能性太多，无法实现。因此我们假定任意一个词wi的出现概率只同它前面的词 wi-1 有关(即马尔可夫假设），于是问题就变得很简单了。现在，S 出现的概率就变为：

P(S) = P(w1)P(w2|w1)P(w3|w2)…P(wi|wi-1)…
(当然，也可以假设一个词又前面N-1个词决定，模型稍微复杂些。）

接下来的问题就是如何估计 P (wi|wi-1)。现在有了大量机读文本后，这个问题变得很简单，只要数一数这对词（wi-1,wi) 在统计的文本中出现了多少次，以及 wi-1 本身在同样的文本中前后相邻出现了多少次，然后用两个数一除就可以了,（P(wi|wi-1) = P (wi)/[P(wi-1,wi)]。

也许很多人不相信用这么简单的数学模型能解决复杂的语音识别、机器翻译等问题。其实不光是常人，就连很多语言学家都曾质疑过这种方法的有效性，但事实证明，统计语言模型比任何已知的借助某种规则的解决方法都有效。比如在 Google 的中英文自动翻译中，用的最重要的就是这个统计语言模型。去年美国标准局(NIST) 对所有的机器翻译系统进行了评测，Google 的系统是不仅是全世界最好的，而且高出所有基于规则的系统很多。

现在，读者也许已经能感受到数学的美妙之处了，它把一些复杂的问题变得如此的简单。当然，真正实现一个好的统计语言模型还有许多细节问题需要解决。贾里尼克和他的同事的贡献在于提出了统计语言模型，而且很漂亮地解决了所有的细节问题。十几年后，李开复用统计语言模型把 997 词语音识别的问题简化成了一个 20 词的识别问题，实现了有史以来第一次大词汇量非特定人连续语音的识别。

我是一名科学研究人员 ，我在工作中经常惊叹于数学语言应用于解决实际问题上时的神奇。我也希望把这种神奇讲解给大家听。当然，归根结底，不管什莫样的科学方法、无论多莫奇妙的解决手段都是为人服务的。我希望 Google 多努力一分，用户就多一分搜索的喜悦。

最近在作一个搜索引擎相关的项目，不说大家也清楚肯定是基于Lucene进行开发的，站在前人的肩膀上啊，呵呵！熟悉Lucene的人都知道，Lucene中并没有很好的中文分词实现，本人目前已经完成了中文分词部分的功能，初步测试效果还不错。围绕中文分词的讨论已经不少了，但通过这次实际的开发，本人确实还是有了一些自己的体会，本打算就这方面写一篇博文，没想到今天突然发现，自己的合作伙伴已经写了一篇，细读了一下，感觉自己想要说的，他都提到了，因此，转载了过来。

以下为转载内容，《小议分词》，勇者之心，http://leaphy.cnblogs.com/archive/2006/07/06/Segment.html。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

全文信息检索系统中，创建倒排索引时应当使用什么分词方式一直是众说纷纭，毫无定论。

具我所知，已有某某 paper “研究指出”采用二元切分的方式构建索引是“最好的”；也看到过园子里的一位兄弟认为单字切分最准确（sorry，忘记具体出处）；当然，将某个基于词典或者共现频率的中文分词组件包装一下加入自己的项目中也是非常流行的做法。

既然存在这么多的看法与做法，难免会让人生出一较高下或者明辨真伪的决心；

不过作为一个成熟而又理智的热血青年，偶认为这种决心并无必要，原因在于信息检索系统的评价标准是多样化的——召回率、准确率与查询效率三个指标相互矛盾，只有取舍、不能调和；人们关心的指标不尽相同自然会提出不同的观点、奉行不同的做法。假设你在做一个Web搜索引擎，首先要保证的一定是查询效率，因为它所要处理的海量数据与并发请求是一种天然的障碍；其次，在召回率与准确率中你会更倾向于后者，因为最终用户与Web搜索引擎的关系恰如负心男人与痴情女人的关系——用户希望尽快得到最满意的结果，并在下一个瞬间把你抛弃，直到他们再次需要你为止（当然，如果你提供了代号为 Good Morni 的竞价排名服务，为了不致客户投诉，最好还是关心一下召回率。所以说，广大小白和一小撮VIP之间的利益冲突是深刻、长远以及不可调和的。。。）；同时，对于一个传统的图书信息检索系统，情况会大不相同——书籍与文章有良好的关键字索引，包括标题、作者、摘要、正文、收录时间等定义明确的结构化数据，文档集合相对稳定并且规模相对较小——这一切都使你的决策更倾向于提高系统的召回率，原因很简单，你有这么做的可能性或者说是先天优势。

既然我们已经明确评价信息检索系统的指标是多元化的，现在让我们来看看不同的索引分词策略到底如何影响这些指标。

首先让我们来比较两个对立的策略，单字切分 vs 中文分词：

单字切分的支持者们最强有力的证据大概如下：
“世界杯”是一个词，用单字切分的话，查“世界”也可以命中这篇文档，而用中文分词就查不到了；
而中文分词的支持者们的反驳大概是：
“参加过世界杯”，用单字切分的话，查“过世”也可以命中这篇文档，但事实上并没有人挂掉；

通过以上陈述我们可以观察得到这样的结论，采用单字切分会提高系统的召回率，而降低准确率；而中文分词则恰恰相反，它提高了准确率，并降低的召回率，并且分词的颗粒越粗糙（平均词长越长）这种趋势就越明显。

这个结论似乎有助于理解为什么 google、百度等等这些理论上更需要高准确率的Web搜索引擎都采用了中文分词技术。但是如果我们的认识仅停留在这种水平就未免显得过于肤浅：事实情况是，需要高吞吐量的Web搜索引擎在处理中文内容时必须采用中文分词技术。

让我们把倒排索引想象成一张表，其中每一行都有一个TermText以及所有包含该TermText的文档编号列表。这样在我们查询某个关键字时，可以一次性获得所有包含该关键字的文档，而不用在原始文档集合中逐一查找。 而采用不同的分词策略创建索引，事实上既是将文档编号集合以不同的程度打散到索引中不同的行。单字切分可以说是打散程度最低的一种方式，行数仅等于汉字数目，而整个倒排索引表会非常的“宽”；相反，颗粒较粗的中文分词将文档编号集合分配到更多的不同行，使得倒排索引表的宽度变小。并且随着分词粒度的增加宽度会逐渐减小，最极端的情况就是将每一篇文档看作一个“词”，此时倒排索引表的宽度处处等于1。

基于以上讨论，我们看出以下两点：
一、在文档集合数量非常庞大时，系统的吞吐量会受到存储倒排索引文件的磁盘的性能限制，因此，采用中文分词，缩短倒排索引表的宽度将有助于提高系统的吞吐量。
二、无论使用布尔查询或者是基于位置信息的查询（如 Lucene 中的 PhraseQuery）单字切分的单词查询性能不会好于中文分词。

这样看来，在Web搜索引擎中使用中文分词就不是一件难以理解的事情了；同样，在文档规模较小时，使用单字切分的策略也不会有什么重大问题。

至于二元切分，在偶看来，这种方法试图以一种战场外科手术的粗犷气质实现中庸之道的思想，单字切分与中文分词之间形成了一种在某些方面不尽人意的折中（歧义、无意义的二元组等）。在实现上它更接近单字切分，而非中文分词。按照偶滴设想，如果实现一种对标准意义的中文分词策略的改进，使其能够在一定程度上缓解中文分词降低召回率的问题，也许会成为一种在各方面都更加平衡的解决方案。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

因为本次做的是一个商业项目，因此不能公布源代码以及相关的技术文档。但稍后会放出本人实现的中文分词算法所依据的一篇论文，并就其中的一些问题进行讨论。有兴趣的朋友欢迎讨论，wendell.gu@gmail.com。

google和百度的火热，把人们的眼球都吸引到了“搜索”上面。现在大家都很清楚，做通用搜索，有这样的两座摩天大山在前面，要超越的可能性是微乎其微了，真正即使想要生存，都非常困难。搜索这东西，一旦做好了有很强的排他性。比方说我，如果只想查中文的内容，我会“百度一下”；如果中英文的都要，那我就google it！其他的搜索引擎，我基本上不会去用了。对用户来说，这样用着习惯。但对互联网的从业者来说，这就是悲哀，因为眼看着这么大张香喷喷的肉饼，自己除了闻闻味儿，却很难咬上一口。

于是，“垂直搜索”的概念产生了！垂直搜索，关注的是某一个行业或某一类搜索对象。比如博客搜索、购物搜索、租房搜索、职位搜索等等。既然通用的咱们没戏了，我可以找一个方向深入挖掘，争取能在内容上和质量上超越通用搜索，从而进入搜索市场。乍一看，这个思路是可行的！但仔细分析一下，问题还是不少。“垂直”是对的。垂直使得用户的目的性增强。比如，在百度上我搜“软件开发”，百度不可能知道我究竟想要什么，它会猜：他想要软件开发的相关知识网页，或者他想要软件开发方面的书籍页面，或者他想找软件开发的职位……算了，反正我猜不出来，我把结果都给他得了。这样，你得到了一大堆的搜索结果。但其实呢，我想要搜的是软件开发方面的职位。如果有一个这样的垂直搜索网站，比如http://www.globehr.com/，我输入“软件开发”，那它一下子就可以知道，我要找的是“软件开发”相关的职位，目的明确了，自然搜索的结果就有效的多了！对于“垂直”来说，“搜索”是一个好的切入点，既吸引眼球，又能满足用户的实际需要，但是，我们得弄明白，不应该把搜索定成垂直的终极目标。就目前的互联网情况来看，它仅仅就是一个好的切入点，而已。如果你的目标是做一个垂直搜索引擎，那么有一天，百度在他的搜索框的上面、MP3的旁边，加上两个字：“职位”！你就歇了，你得面对一个如此强大的对手，无论是资本、技术还是人员，你觉得这样的机会大吗？

个人以为，“垂直”的关键，在于“深入”，而不是“搜索”！你得把服务做扎实了，用“搜索”来吸引用户，而目标应该是帮助用户尽少的使用搜索，即使要搜，也得帮助用户最准确地完成搜索。还拿职位搜索来说，我进入一个职位“垂直”网站A，我的目标显然就是寻找一个合适的职位。搜索是目前实现这个目标的一个方法，我输入“软件开发”，网站返回来搜索结果，告诉我现在有哪些相关的职位，我一个一个的点击查看，判断自己和该职位是否合适，合适的发送简历，不合适的关闭网页。周而复始，长此以往，你感觉如何？如果我进入了另外一个职位“垂直”网站B，我刚想输入“软件开发”进行搜索，突然，网站告诉我，有10个和“软件开发”相关的职位，有两个“软件开发”的培训，你看看合不合适你。你的感觉又如何！人家都给我准备好了，那我还搜什么啊！这其实也是搜，但是网站自动搜的，而不需要用户再手动完成。术语管这种技术叫做“个性化推荐”。

点击百度MP3旁边的那个“职位”标签，当然也可能产生这样的效果。但是，百度会做吗？毕竟，百度更专注于通用，这个市场更大，用户也更多，现在的通用搜索还有太多的难关需要去攻克，而可以“垂直”的又这么多，百度不可能把每一个“垂直”都做深入。如果你花时间研究一下“个性化推荐”，你会发现要实现它，你得分析用户的喜好，你得查找用户的邻居用户，你得给搜索对象打分……搞搜索引擎，搜索结果质量不高，你可以把责任推给用户，告诉他你输入的关键字不好；但做个性化推荐，你只能把最合适的结果推荐给用户，一个错误的推荐还不如不推荐！要做好它，难度着实不小！

但是，技术上有难度，领先的厂商又无力顾及，不恰恰是一个很好的机会吗？