前言 Preface

无论是有意还是无意，越来越多投身于互联网的人们已经制造出了相当多的数据，这给了我们无数潜在的机会来洞悉用户体验、商业营销、个人偏好和通常所谓的人类行为（human behavior）。

本书向大家介绍了一个新兴的领域，称为聚集型智慧（collective intelligence）。

这一领域涵盖了诸多方法，借助这些方法我们可以从众多Web站点处（这些站点的名字或许你曾经有所耳闻）提取到值得关注的重要数据；借助这些方法我们还可以从使用自己应用程序的用户那里搜集信息，并对我们所掌握的数据进行分析和理解。

本书的目的是要带领你超越以数据库为后端的简单应用系统，并告诉你如何利用自己和他人每天搜集到的信息来编写更为智能的程序。

先决条件 Prerequisites

本书的代码示例是用Python语言编写的，因此熟悉Python编程将会有助于你对算法的理解，不过笔者给出了所有算法的解释说明，所以其他语言的程序员也能看懂。对于已经了解了像Ruby或Perl这样高级语言的程序员，Python代码应该是非常容易理解的。

本书的目的不是要作为一本学习编程的指导书，因此尤为重要的一点在于，为了熟悉基本概念，我们最好已编写过足够多的代码才行。如果懂得递归和一点点函数式编程（functional programming）的基本概念，那么我们就会发觉书中的内容是很容易理解的。

本书并不假设你已经具备了任何有关数据分析、机器学习或统计学方面的知识。笔者在尝试以尽可能浅显易懂的方式来解释数学概念，不过具备一点三角学和统计学的基本知识将会对你理解算法有所助益。

示例风格 Style of Examples

本书每一章节的代码示例都是以一种教程式的风格编写而成的，它鼓励你以循序渐进的方式来构建应用程序，并对算法的工作原理有一个深入的理解和认识。

大多数情况下，写完一个新的函数或方法之后，我们会在一个交互的会话环境里使用它，以此来理解算法的工作原理。通常算法是有简单的变体的，我们可以用多种方式对其进行扩展。

通过示例讲解并以交互的方式对其进行测试，我们对算法将会有更为深入的理解，从而可以对其进行改造，以适应自己的应用程序。

为何选择Python？Why Python?

尽管书中的算法是伴随着对相关公式的解释，以文字形式加以描述的，但是假如有针对算法和示例问题的实际代码，那将会是更有助益的（而且有可能更易于理解）。

本书中的所有示例代码都是用Python，一种优秀的高级语言，编写而成的。之所以选择Python是因为它的如下特性。

• 简练
  使用像Python这样的动态类型语言编写的代码往往比用其他主流语言编写而成的代码更加简短。这意味着，在完成示例的过程中会有更少的录入工作，而且这也意味着我们将更容易记住算法并真正领会算法的原理。

• 易于阅读
  Python不时被人们指为"可执行的伪代码"。虽然很明显这是一种夸大之词，但是它表明，大多数有经验的程序员可以读懂Python代码并领会代码所要表达的意图。Python中一些不是很显见的语言要素将会在后面的"Python技巧"一节中加以解释。

• 易于扩展
  Python随附了许多标准库，这些库涉及数学函数、XML（扩展标记语言）解析，以及网页下载。本书中用到的非标准库，如RSS（Really Simple Syndication）解析器和SQLite接口，则是免费的，很容易下载、安装和使用。

• 交互性
  在学习示例的过程中，可以尝试执行我们编好的函数，而无须为此专门编写额外的程序，这一点是非常有价值的。Python可以直接从命令行运行程序，它还有交互提示，允许我们键入函数调用、创建对象，并以交互的形式来对包进行测试。

• 多范式
  Python支持面向对象、过程式和函数式编程风格。机器学习算法千差万别，最为清晰的做法是针对不同算法采用不同的范式。有时将函数作为参数传入很有用处，而有时我们则须要在对象中捕获状态。对于这两种方式Python均予以支持。多平台和免费Python有一个针对所有主流平台的单一参考实现，并且它对所有平台都是免费的。本书中所列代码可以运行于Windows、Linux和Macintosh环境。

Python技巧 Python Tips

对于有兴趣学习Python编程的初学者而言，笔者推荐大家阅读由Mark Lutz与David Ascher合著的《Learning Python》（O'Reilly），该书有对Python的全面论述。

为了更为直观地表达算法或基础性概念，笔者在整本书中使用了一些Python特有的语法，但是其他语言的程序员应该会发现，Python的代码相对而言还是较为容易掌握的。下面是为非Python程序员提供的一份快速概览。

• 列表和字典的构造函数
  Python有一组不错的基本类型，其中有两种类型在本书中被大量使用，它们分别是列表和字典。列表是由一组任意类型的值构成的有序列表，它由方括号构造而成：

number_list=[1,2,3,4]
string_list=['a', 'b', 'c', 'd']
mixed_list=['a', 3, 'c', 8]

字典是由一组名值对构成的无序集合，类似于其他语言中的hash map。它由大括号构造而成：

ages={'John':24,'Sarah':28,'Mike':31}

可以通过序列名后跟方括号的形式来访问列表和字典中的元素：有意义的空白字符
与大多数语言有所不同，Python实际上是利用代码的缩进来定义代码块的。请看下列代码片段：

if x==1:
    print 'x is 1'
    print 'Still in if block'
    print 'outside if block'

因为代码是被缩进的，所以语法解释器知道前两个打印语句会在x为1的时候被执行。缩进可以是任意数量的空格，只要它是常量即可。本书使用的缩进是两个空格。在输入代码的时候，我们须要注意正确拷贝缩进。

• 列表推导式
  列表推导式（list comprehension）是一种方便简洁的语法形式，我们可以利用它将一个列表经过滤后转换成另一个列表，也可以利用它将函数应用于列表中的元素。列表推导式以如下形式书写：

[表达式 for 变量 in 列表]

或者：

[表达式 for 变量 in 列表 if 条件]

例如，下列代码：

l1=[1,2,3,4,5,6,7,8,9]
print [v*10 for v in l1 if v1>4]

将打印输出如下列表：

[50,60,70,80,90]

本书中频繁地使用了列表推导式，因为要将一个函数应用于整个列表，或是删除不需要的列表项时，这种表达方法非常简练。列表推导式的另一种常见用法是与dict构造函数结合在一起使用：

l1=[1,2,3,4,5,6,7,8,9]
timesten=dict([(v,v*10) for v in l1])

上述代码将会建立一个字典，以原先的列表作为键，以每个列表项乘以10作为值：

{1:10,2:20,3:30,4:40,5:50,6:60,7:70,8:80,9:90}

开放的API Open APIs

用于将聚集型智慧合成起来的算法需要来自许多用户的数据。除机器学习的算法外，本书还论及了许多开放的Web APIs（应用编程接口）。这些API允许我们通过特殊的协议对来自相应Web站点的数据进行访问；我们可以编写程序将数据下载下来并加以处理。这些数据通常是由站点的使用者来提供的，我们可以从中挖掘出新的内涵来。有的时候，我们可以用现成的Python库来访问这些API；而有时，如果没有现成的库，那么最为直接的做法莫过于创建自己的接口来访问数据，为此我们须要利用Python提供的内建库将数据下载下来，并对XML加以解析。

此处列出了一系列提供开放API的Web站点，我们将在本书中陆续接触到这些站点。

• del.icio.us
  一个社会型书签应用系统（social bookmarking application），其开放的API允许你根据标签（tag）或特定的用户来下载链接。

• **Kayak **
  一个提供API的旅游网站，你可以利用API在自己的程序中集成针对航班和旅馆的搜索。

• **eBay **
  一个提供API的在线交易站点，允许你查询当前正在出售的货品。

• Hot or Not
  一个评分与交友的网站，提供API对人员进行搜索，并获取其评分及个人资料。

• **Akismet **
  一种用于对协作型垃圾信息进行过滤的API。

通过对来自单一源的数据进行处理，对来自多个源的数据进行组合，甚至通过将外部信息与自有系统的用户输入信息加以组合，我们可以构造出大量的潜在应用。对人们在不同网站以各种不同方式产生的数据加以充分利用的能力，便是构建聚集型智慧的一个基本要素。

如果你想寻找更多的提供开放API的Web站点，不妨从访问ProgrammableWeb开始（http://www.programmableweb.com）。

各章概览 Overview of the Chapters

本书的每个算法都来源于某一现实的问题，希望这些问题能够很容易地被广大读者所理解。笔者将尝试尽量避开那些要求大量领域知识的问题，而将焦点集中在那些虽不失复杂性，但对大多数涉足者而言却又是简单易懂的问题上。

• 第1章，聚集型智慧导言
  本章解释了蕴藏于机器学习背后的概念，并解释了如何将其应用于诸多不同的领域，以及如何利用它对搜集自许多不同人群的数据进行分析，并从中得出新的结论。

• 第2章，提供推荐
  本章介绍协作型过滤（collaborative filtering）技术，这项技术被许多在线零售商用来向顾客推荐商品或媒体。本章中有一节介绍了如何向一个社会型书签服务网站的用户提供推荐链接，还介绍了如何根据MovieLens所提供的数据集构筑一个影片推荐系统。

• 第3章，发现群组
  本章基于第2章中给出的某些观点，介绍了两种不同的聚类方法，利用这些方法，我们可以在一个大数据集中自动找出具有相似特征的群组。本章还演示了如何利用聚类算法从一组颇受欢迎的博客之中寻找群组，以及利用聚类算法根据某个社会型网站的用户意愿去寻找群组。

• 第4章，搜索与排名
  本章描述了构成一个搜索引擎的各个不同组成部分，它们包括：爬虫程序（crawler）、索引程序（indexer），以及查询引擎（query engine）。本章介绍了以来自外部网站的链接信息为依据给网页打分的PageRank算法，还向你展示了如何构建神经网络，借此获知与不同结果相关联的关键词。

• 第5章，优化
  本章介绍了优化算法，设计这些算法的目的，是为了对问题的数百万个可能的题解进行搜索，并从中选出最优解来。书中利用示例演示了这些算法的各种不同用法，包括：为一群去往相同地点的旅客寻找最佳航班，寻求为学生安排宿舍的最佳方案，以及给出交叉线数量最小的网络布局。

• 第6章，文档过滤
  本章向读者演示了贝叶斯过滤，这一方法被广泛应用于许多免费的和商业的垃圾信息过滤系统中，用于根据单词类型及出现在文档中的其他特征对文档进行自动分类。我们将其应用于一组RSS搜索结果，以此来说明对内容项的自动分类过程。

• 第7章，决策树建模
  本章介绍了决策树，我们不仅将它作为一种预测方法，而且还用它来为决策过程进行建模。本章中出现的第一棵决策树是根据假想的服务器日志数据构建而成的，我们利用它来预测用户是否有可能成为付费订户（premium subscriber）。本章的另一个例子则使用了来自真实Web站点的数据，用以对住房价格和来自Hot or Not网站的"热度（hotness）"评价进行建模。

• 第8章，构建价格模型
  本章解决的是数值预测问题而非分类问题，期间用到了k-最近邻技术，并且还用到了第5章中的优化算法。我们将这些方法与eBay API结合在一起构造出一个系统，能够根据拍卖品的一组属性，预测出最终的拍卖价格。

• 第9章，高阶分类：核方法与SVM
  本章向读者介绍了如何利用支持向量机（support-vector machines）对在线约会网站的用户进行匹配，以及如何将其用于针对专业交友网站的好友信息搜索。支持向量机是一项非常高阶的技术，本章将之与其他方法进行了对比。

• 第10章，寻找独立特征
  本章介绍了一种相对较新的技术，称为非负矩阵因式分解（non-negative matrix factorization），我们利用这项技术在数据集中寻找独立的特征。对许多数据集而言，其中所包含的内容都是可以借助一组独立特征的组合被重新构造出来的，而这些特征是我们事先不知道的；非负矩阵因式分解的思路便是要寻找这些特征。在本章中，我们利用一组新闻报道说明了该项技术的使用；期间，通过新闻故事来寻找其中的主题，一篇给定的新闻故事中会包含一个或多个这样的主题。

• 第11章，智能进化
  本章介绍了遗传编程（genetic programming）的概念，这是一组非常复杂的技术，它超出了优化的范畴。并且，这项技术实际上借鉴了进化的思想，它是通过自动构造算法的方式来解决特定问题的。我们通过一个简单的游戏来说明这项技术的应用。在游戏中，计算机最初只是一个学艺不精的初级选手，但是随着游戏的不断进行，它会通过逐步改进其所拥有的代码来提升自己的技能。

• 第12章，算法总结
  本章回顾了书中所讲述的所有机器学习算法及统计算法，并将它们与一组人为设计的问题做了对比。这将有助于我们理解算法的工作原理，并形象地说明每种算法划分数据的方法。

• 附录A，第三方函数库
  给出了有关本书所用的第三方库的信息，例如在哪里可以找到这些第三方库，以及如何进行安装。

• 附录B，数学公式
  包含了一部分数学公式及其说明，以及本书通篇引入的、以代码形式描述的诸多数学概念。

位于每章末尾处的练习，为读者提供了许多相关信息，借此我们可以对算法进行扩展并使其变得更加强大。