图书信息

内 容 简 介

译者序

前 言

目 录

图书信息

智能Web算法（美）玛若曼尼斯（Marmanis, H.），（美）巴宾寇（Babenko, D.）著

阿稳，陈钢译

ISBN 978-7-121-13919-2

2011 年7 月出版

定 价：65.00 元

16开

400页

内 容 简 介

本书涵盖了五类重要的智能算法：搜索、推荐、聚类、分类和分类器组合，并结合具体的案例讨论了它们在Web 应用中的角色及要注意的问题。除了第1 章的概要性介绍以及第7 章对所有技术的整合应用外，第2～6 章以代码示例的形式分别对这五类算法进行了介绍。

本书面向的是广大普通读者，特别是对算法感兴趣的工程师与学生，所以对于读者的知识背景并没有过多的要求。本书中的例子和思想应用广泛，所以对于希望从业务角度更好地理解有关技术的技术经理、产品经理和管理层来说，本书也有一定的价值。

译者序

在这篇文章里，我会谈谈自己在翻译本书过程中的一些比较深刻的感受，以期让读者在正式阅读本书之前对它有一个整体的了解。比如，书中算法讲解背后所隐含的更重要的思想，又如作者使用了什么样的方式来传递书中的知识，以及本书的受众群体。

虽然书中各章论述的是不同的理论和不同的应用，但作者一直在试图传递一些这个领域里不变的朴素而实用的思想，其中一个最重要的思想是：组合不同的技术，以得到更好的结果。这无论是在学术界，还是在业界，都已经逐渐成为风气。不久前的2011中国推荐系统峰会上，张栋博士在总结自己参加netflix竞赛感受时就曾说到：一个好的推荐器无法打败无数技术组合起来的推荐器。而书中第3章也引述了netflix竞赛获胜者的话说：“我们没有发现完美的模型，而我们最好的结果是来自对具有互补作用的模型预测结果的组合”。

此外，书中还反复强调了一些很具有现实参考意义的观点，限于篇幅，简要列举几点如下：

<1>对问题本质及数据性质的理解比使用什么算法更重要。2011中国推荐系统峰会同样有一个类似的为人们所争议的热点，有与会者认为以重要性而论，领域知识>数据>算法。作为有过一定从业经验的算法工作者，对此应能有深刻体会。

<2>实验环境的数据要能代表现实数据。从统计与抽样理论的角度来说，这个命题的重要性毋庸置疑。而对于先在离线环境中训练模型，然后在生产环境中使用模型的智能应用模式而言，这点尤其重要，你是不可能把一个在北京计算得到的空气质量预测模型直接拿到北海道去用的。

<3>当你想了解你的改变所产生的效果时，最好一次只改变一个因素。这其实与AB-Test的思想具有异曲同工之妙，要想研究某个参数或某个变量修改前后的差异，需要尽量保证除此之外的其他因素不变。

所以，这不单是一本介绍算法之术的书，更是一本介绍算法之道的书。读者在学习其中各种具体算法的同时，不妨更多地思考作者总结出来的这些实战性很强的经验，因为那些算法不一定是最新最有效的，但那些经验教训则是需要经历实际的成败方能总结出来的。此外，我们建议读者不要只看代码的实现，而更要关注蕴涵于其中的一些设计原理以及对问题建模的方式。因为在实际的应用环境中，你需要考虑的可能不仅仅是一两个算法，而是一个具体的系统问题。

无论是多么朴素和实用的思想，传授起来也难免让人觉得枯燥，所以作者尽其最大努力希望从工程化的角度来介绍这些算法。其中一种尝试就是尽量摒弃对数学公式的使用，而代之以论述具体问题与代码说明的方式来解释算法。是否依赖数学公式来说明问题是一个值得商榷的事情，数学公式就好像是一种共同的语言或标准一样，只要大家都懂这种语言，沟通基本上不会存在问题，而且显得简练、优雅，无二义性。但霍金也曾经说过，多一个数学公式，就会吓跑一半的读者，所以在他那本经典著作《时间简史》中只保留了最重要的一个公式。近年来，面向大众的技术书籍也有这种尽量摆脱乏味的数学公式堆砌的风潮，特别是国外的很多优秀著作，即使只用很少的公式也能把问题说清楚。

依我的观点，一本书籍对数学公式的取舍与使用量的多少，取决于作者对读者范围的界定，以及如何找到这一读者群中公认的沟通标准。无疑，在通常的IT技术从业者中，按通用性而论：自然语言>代码>数学公式。虽然作为这一领域的从业者，懂得基本的数学知识是必需的，但为了使本书适用于更广泛的程序员阶层人群，作者尽力使用代码与自然语言来描述那些算法，而不是数学公式。于是，你将会很惊讶地看到，一本讲述算法的著作里，居然找不到几个数学公式，而且这一点都不妨碍你对这些算法的含义的理解。

另一方面，要填平从理论到实践、从学校到业界的鸿沟并不是件容易的事情，特别是在我国现有的教育体系下，在校期间的学习与现实需求的差异尤其大。本书作者既有工程的从业背景，又有非常丰富的机器学习研究经历，使得他可以用一种实用性较强的方式把业界所需要的知识点传递出来。被证明最直接有效的传递知识的方式当然就是案例化的教学，书中每一个讲授具体算法的章节都会辅之以一个现实中的问题，比如文档搜索引擎、在线音乐推荐商店、用户的信用等级分类等。

除了案例化的知识传授方式，每章后的To Do事项则充分体现了西方人所崇尚的启发式的教学思想，虽然经过我们传统教育的读者也许并不乐意自己再去探索，而更愿意作者把所有的东西都一一告诉我们，但如果对照着现成的代码把一个个具有探索性意味的To Do事项完成，你获得的知识都是自己的，也是超越本书所教授的内容的。学会独立思考、独立实践，也是一名普通工程师走向优秀工程师的重要分水岭。

虽然有不少的优点，但本书也仍有其不足之处。书中对智能技术的主要方面都有所论及，但在如此篇幅的书中把所有问题都论述清楚是不可能的，过于追求全面就会导致深度方面稍有缺乏，所有领域相关的问题未必能方方面面都讨论透彻，对于资深从业人员来说，未免会有点意犹未尽的感觉。此外，虽然本书是本着工程的理念来讲述，在代码实现方面也考虑了一些工程上效率的因素，但毕竟只是一套教学演示代码，未免为追求简明易懂而显得简陋，所以也不能寄希望于把它们直接用于自己的生产环境中。

这不是一本适用于所有对该领域感兴趣的读者的书，它有其适用人群。适用人群之一：软件或互联网从业工程师，如果你原来没有接触过相关的知识，而又想让自己的代码拥有更多的智能化特性，这本书也许能给你带来新的启发和新的思维。人群之二：如果你已经是书中所涉及领域的从业人员，那么阅读该书也许会帮助你梳理一下原有的知识体系，但如果你在寻求某个领域的最新技术动向，此书则不合适，因为该书讲述的都是业界上已经获得成熟应用的概念与算法。人群之三：想在数据挖掘、智能技术上用力的企业管理人员或产品经理。据我的了解，一些互联网公司在发展到达一定的阶段后，纯粹的人力与资金上的增加已经无法带动效益的同比增长，他们都在寻求发展模式上的转变，转粗放型增长为技术型增长，希望这本书关于智能技术的概念与案例能给有这方面需求的人带去一定的帮助。人群之四：在自己的职业规划之路中，有算法工程师、数据挖掘工程师、数据分析师这些关键词的在校学生。

本书由我及我的搭档陈钢联合翻译完成。我们很希望，该书的出版能为正在思考自己出路的在校学生，或每天在计算机面前敲打着代码的工程师们，提供多一种职业发展的可能性。只有更多优秀的人才投身于这个领域，才能使国内IT公司对智能技术应用产生广泛的重视，进而推动国内IT事业的创新性。如果这本书能成为未来许多年大量算法工程师的入门书籍，则是它最大的成功之处。

这本书的翻译出版，首先要感谢我所任职的公司豆瓣网，如果没有这个宽松自主的工作环境，我很难把两三个月几乎所有的业余时间都花在这件事情上。当然，如果没有在这个地方三年来的从业经验，以及在那帮优秀的同事身边成长的经历，我从一开始就不会有信心把这件事情做好。我还要特别感谢豆瓣电台，正是它知心动听的歌曲陪伴我度过了那一个个枯燥的夜晚。还有有道词典，它在网络释义与例句上给予了我莫大的帮助。而恰巧，这两个个性鲜明的互联网产品正是本书所叙述的智能Web技术应用的杰出代表。同样要感谢电子工业出版社博文视点公司的编辑们，以及给我们提出过宝贵意见的中国推荐社区的朋友们。

因为自身水平有限，在理解与翻译本书的过程中，一些知识的传递未必到位，但认识总是可以通过交流与思考来加深的。所以，接下来我们也希望借助豆瓣的读书笔记功能把我们在翻译过程中得到的一些认识写下来与大家分享交流。大家在阅读过程中也不妨通过这种形式来分享自己的理解，提出自己的问题，形成一种思想上的互动。因为与同行交流是促进思考与进步的最重要手段。读者可以在博客或豆瓣上找到我们。

阿稳

感谢昆明理工大学的彭玮老师和中国推荐系统小组中的各位同学在百忙之中抽时间审读我们的译稿。感谢电子工业出版社博文视点的各位编辑在本书翻译过程中给予的指点和帮助。特别要感谢本书的另外一位译者阿稳在技术上的指点。没有你们的支持和帮助，本书的翻译工作不可能这么顺利。在翻译本书的几个月里，尤其是最后审稿的阶段，我不得不将本应该陪伴已怀孕的妻子的时间投入到本书的翻译工作中，特将本书献给我的妻子王倩和我们即将到来的孩子。

陈钢

前 言

在读研究生时，我开始接触到机器学习，尤其是模式识别。我的工作主要是数学建模和数值模拟，但海量数据的模式识别其实在很多领域都有着广泛的应用。以前也未曾想到，这些年我会如此深入地进入机器学习领域。

1999年，我完成学业，开始进入企业工作。在我担任顾问的一个项目中，我们试图根据患者的心电图判断出他们患心脏病的概率。显然，对这种问题，不存在也不可能推导出一个精确的数学公式。现实中，心脏病专家已经对大量的患者患心脏病的风险做出了诊断，而我们建模所使用的方法要能从这些病历中学习如何预测患心脏病的风险。通俗地说，我们要寻找的是能从用户输入的数据中不断地“学习”新知识的方法。

同时，在20世纪90年代，各种因素汇聚在一起导致了一个新产业的飞速发展——网络变得无处不在！根据摩尔定律，CPU的运行速度变得更快，而且价格更便宜。RAM模组、硬盘等各种计算机硬件的性能变化也是日新月异的，而价格则是一降再降。随之而来的是，网络连接的带宽不断增长，价格也能被更多的人接受。此外，健壮的Web应用开发技术已经成熟，而各种开源项目的蓬勃发展更是促进了相关技术的进步。所有的这些因素构成了现在我们称为Web的庞大生态系统。

显然，作为软件工程师和Web开发人员，我们首要的任务就是为构建健壮、可扩展、美观的Web应用提供足够的技术保障。正是如此，在过去的十年里，人们为此做出了巨大的努力，也获得了可观的成绩。当然，没有最好，只有更好，我们依然有进步的空间。虽然我们一直在追求更健壮、可扩展性更好、更美观的Web应用，然而我们已经遇到了瓶颈。在我们看来，单调乏味的互联网应用已经成为过去，仅仅是聚合数据，简单地根据预定逻辑工作的用户请求/响应模型也已经走到了尽头。

现在，在某些应用中已经出现了一股新的浪潮，让人们对互联网应用有了新的认识。这就是本书中所说的智能应用（intelligent application）。不同于传统的应用，智能应用能根据用户的输入调整自己的行为，就像我那个能根据心电图预测患心脏病概率的建模软件。

最近五年，我渐渐地发现，对于大部分软件开发人员来说，构建智能应用的技术依然保持着神秘的面纱。在我看来，这是由两方面的原因造成的。一方面，这些技术潜在的商业价值可以带来巨大的经济回报。所以从经济方面考虑，对这些应用进行保护，隐藏其中的关键细节是可以理解的。另一方面，几乎所有的相关技术都源自学术研究，需要较强的数学背景才能理解。对于第一个原因，我们无能为力，但在随时能获取海量知识的今天，第二个原因依然是不可逾越的障碍吗？我可以简短而明确地回答“不是！”。如果想要详细地回答，那就阅读本书吧！

我决定写这本书，是为了说明这些技术是可以用算法来表示的，并不需要读者有很强的数学基础。本书的目的是让读者掌握一些有助于在应用中构建智能行为的技术，同时尽可能地降低掌握这些技术的数学门槛。代码以算法的形式包含了所有必要的数学知识。

最初，我想用开源的库来演示这些技术，但大部分的此类库都是为了解决具体问题而开发的，并不是为了演示底层的技术。因此，这些库的源代码通常都是冗长且晦涩难懂的。显然，如果能有清晰、带注释的代码，一定会让本书的读者获益更多。Dmitry就是在这个时候加入了本书的写作，并最终编写完成了本书中的大部分代码。

尽管增长缓慢，但关于这个激动人心的新领域的书籍肯定将逐渐增多。本书只是一本有关这个依然在迅速增长的大领域的入门书籍。所以，本书所涉及的算法是很有限的，对算法的解释也比较简要。我的目标是选择并探讨一些有代表性的话题，而不是写一本代码手册或是有可能让读者晕头转向，内容包罗万象的书。

我希望能通过以下四个方面来实现我的目标：

集中精力关注清晰易懂的例子。

使用高级脚本语言来演示算法的使用，就像读者在自己的应用中使用这些算法一样。

通过大量的ToDo事项让读者有机会尝试并思考这些代码。

编写高水平的、易读的代码。

那么，端着您最喜爱的热饮，坐好，来试试这些聪明的应用吧！它们就在本书中！

HARALAMBOS MARMANIS

目 录

1 什么是智能Web？ 1

1.1 智能Web应用实例 3

1.2 智能应用的基本要素 4

1.3 什么应用会受益于智能? 5

1.3.1 社交网络 6

1.3.2 Mashup 7

1.3.3 门户网站 8

1.3.4 维基 9

1.3.5 文件分享网站 9

1.3.6 网络游戏 11

1.4 如何构建智能应用？ 11

1.4.1 检查功能和数据 12

1.4.2 获取更多的数据 12

1.5 机器学习、数据挖掘及其他 16

1.6 智能应用中八个常见的误区 17

1.6.1 误区1：数据是可靠的 18

1.6.2 误区2：计算能马上完成 19

1.6.3 误区3：不用考虑数据规模 19

1.6.4 误区4：不考虑解决方案的可扩展性 19

1.6.5 误区5：随处使用同样的方法 19

1.6.6 误区6：总是能知道计算时间 20

1.6.7 误区7：复杂的模型更好 20

1.6.8 误区8：存在无偏见的模型 20

1.7 小结 20

1.8 参考资料 21

2 搜索 22

2.1 用Lucene实现搜索 23

2.1.1 理解Lucene代码 24

2.1.2 搜索的基本步骤 31

2.2 为什么搜索不仅仅是索引？ 33

2.3 用链接分析改进搜索结果 35

2.3.1 PageRank简介 35

2.3.2 计算PageRank向量 37

2.3.3 alpha：网页间跳转的影响 38

2.3.4 理解幂方法 40

2.3.5 结合索引分值和PageRank分值 45

2.4 根据用户点击改进搜索结果 47

2.4.1 用户点击初探 48

2.4.2 朴素贝叶斯分类器的使用 50

2.4.3 整合Lucene索引、PageRank和用户点击 54

2.5 Word、PDF等无链接文档的排序 58

2.5.1 DocRank算法简介 58

2.5.2 DocRank的原理 60

2.6 大规模实现的有关问题 65

2.7 用户得到了想要的结果吗？精确度和查全率 67

2.8 总结 69

2.9 To Do 70

2.10 参考资料 72

3 推荐系统 73

3.1 一个在线音乐商店：基本概念 74

3.1.1 距离与相似度的概念 75

3.1.2 走近相似度的计算 80

3.1.3 什么才是最好的相似度计算公式？ 83

3.2 推荐引擎是怎么工作的 84

3.2.1 基于相似用户的推荐 85

3.2.2 基于相似条目的推荐 94

3.2.3 基于内容的推荐 98

3.3 推荐朋友、文章与新闻报道 104

3.3.1 MyDiggSpace com简介 105

3.3.2 发现朋友 106

3.3.3 DiggDelphi的内部工作机制 108

3.4 像Netflix com那样推荐电影 114

3.4.1 电影数据集的介绍及推荐器 114

3.4.2 数据标准化与相关系数 117

3.5 大规模的实现与评估 123

3.6 总结 124

3.7 To Do 125

3.8 参考资料 127

4 聚类：事物的分组 128

4.1 聚类的需求 129

4.1.1 网站中的用户组：案例研究 129

4.1.2 用SQL order by子句分组 131

4.1.3 用数组排序分组 132

4.2 聚类算法概述 135

4.2.1 基于分组结构的聚类算法分类 136

4.2.2 基于数据类型和结构的聚类算法分类 137

4.2.3 根据数据规模的聚类算法分类 137

4.3 基于链接的算法 138

4.3.1 树状图：基本的聚类数据结构 139

4.3.2 基于链接的算法概况 141

4.3.3 单链接算法 142

4.3.4 平均链接算法 144

4.3.5 最小生成树算法 147

4.4 k-means算法 149

4.4.1 初识k-means算法 150

4.4.2 k-means的内部原理 151

4.5 鲁棒的链接型聚类（ROCK） 153

4.5.1 ROCK简介 154

4.5.2 为什么ROCK这么强大？ 154

4.6 DBSCAN 159

4.6.1 基于密度的算法简介 159

4.6.2 DBSCAN的原理 162

4.7 超大规模数据聚类 165

4.7.1 计算复杂性 166

4.7.2 高维度 167

4.8 总结 168

4.9 To Do 169

4.10 参考资料 171

5 分类：把事物放到它该在的地方 172

5.1 对分类的需求 173

5.2 分类器的概述 177

5.2.1 结构分类算法 178

5.2.2 统计分类算法 180

5.2.3 分类器的生命周期 181

5.3 邮件的自动归类与垃圾邮件过滤 182

5.3.1 朴素贝叶斯分类 184

5.3.2 基于规则的分类 197

5.4 用神经网络做欺诈检测 210

5.4.1 交易数据中关于欺诈检测的一个用例 210

5.4.2 神经网络概览 212

5.4.3 一个可用的神经网络欺诈检测器 214

5.4.4 神经网络欺诈检测器剖析 218

5.4.5 创建通用神经网络的基类 226

5.5 你的结果可信吗？ 232

5.6 大数据集的分类 235

5.7 总结 237

5.8 To Do 239

5.9 参考资料 242

6 分类器组合 244

6.1 信贷价值：分类器组合案例研究 246

6.1.1 数据的简要说明 247

6.1.2 为真实问题生成人工数据 250

6.2 用单分类器做信用评估 255

6.2.1 朴素贝叶斯的基准线 255

6.2.2 决策树基准线 258

6.2.3 神经网络基线 260

6.3 在同一个数据集中比较多个分类器 263

6.3.1 McNemar检验 264

6.3.2 差额比例检验 266

6.3.3 Cochran Q检验与F检验 268

6.4 Bagging: bootstrap聚合（bootstrap aggregating） 270

6.4.1 bagging实例 272

6.4.2 bagging分类器底层细节 274

6.4.3 分类器集成 276

6.5 Boosting：一种迭代提高的方法 279

6.5.1 boosting分类器实例 280

6.5.2 boosting分类器底层细节 282

6.6 总结 286

6.7 To Do 288

6.8 参考资料 292

7 智能技术大汇集：一个智能新闻门户 293

7.1 功能概览 295

7.2 获取并清洗内容 296

7.2.1 各就位、预备、开抓！ 296

7.2.2 搜索预备知识回顾 298

7.2.3 一个抓取并处理好的新闻数据集 299

7.3 搜索新闻 301

7.4 分配新闻类别 304

7.4.1 顺序问题 304

7.4.2 使用NewsProcessor类进行分类 309

7.4.3 分类器 310

7.4.4 分类策略：超越底层的分类 313

7.5 用NewsProcessor类创建新闻分组 316

7.5.1 聚类全部文章 317

7.5.2 在一个新闻类别中聚类文章 321

7.6 基于用户评分的动态内容展示 325

7.7 总结 328

7.8 To Do 329

7.9 参考资料 333

附录A BeanShell简介 334

A.1 什么是BeanShell？ 334

A.2 为什么使用BeanShell？ 335

A.3 运行BeanShell 335

A.4 参考资料 336

附录B 网络采集 337

B.1 爬虫组件概况 337

B.1.1 采集的步骤 338

B.1.2 我们的简单爬虫 338

B.1.3 开源Web爬虫 339

B.2 参考资料 340

附录C 数学知识回顾 341

C.1 向量和矩阵 341

C.2 距离的度量 342

C.3 高级矩阵方法 344

C.4 参考资料 344

附录D 自然语言处理 345

D.1 参考资料 347

附录E 神经网络 348

E.1 参考资料 349

索引 350