本书以机器学习和统计为主题背景,专门讲述如何挖掘和分析Web上的数据和资源,解释如何从用户体验、市场数据、用户个人偏好等诸多信息中进行分析并得出有用结论,通过复杂的算法来从Web网站获取数据、收集和分析用户数据和反馈信息,以便创造新的用户价值和商业价值。全书内容详实,包括协作过滤技术、集群数据分析、搜索引擎核心技术、搜索海量信息并进行分析统计得出结论的优化算法、贝叶斯过滤技术、用决策树技术实现预测和决策建模功能、社交网络的信息匹配技术、机器学习和人工智能应用等。
旧书重新包装出版,现在机器学习的大环境远优于上一版,建议重出。
前言
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}
可以通过序列名后跟方括号的形式来访问列表和字典中的元素:
string_list[2] # returns 'c'
ages['Sarah'] # returns 28
有意义的空白字符
与大多数语言有所不同,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 v>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 API(应用编程接口)。这些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,数学公式
包含了一部分数学公式及其说明,以及本书通篇引入的、以代码形式描述的诸多数学概念。
位于每章末尾处的练习,为读者提供了许多相关信息,借此我们可以对算法进行扩展并使其变得更加强大。
排版约定
Conventions
本书使用了下列排版约定。
普通字体
用于指示菜单标题、菜单选项、菜单按钮,以及键盘快捷键(诸如Alt和Ctrl)。
斜体(Italic)
用于指示新的术语、URL、E-mail地址、文件名、文件扩展名、路径名、目录,以及UNIX工具。
等宽字体(Courier New)
用于指示命令(command)、命令选项(option)、命令开关(switch)、变量(variable)、属性(attribute)、键值(key)、函数(function)、类型(type)、类(class)、名字空间(namespace)、方法(method)、模块(module)、成员属性(property)、参数(parameter)、值(value)、对象(object)、事件(event)、事件处理器(event handler)、XML标签、HTML标签、宏、文件内容或命令的输出结果。
等宽粗体(Courier New)
用于显示命令或其他应该由用户手工逐字输入的文本。
等宽斜体(Courier New)
用于显示可替换文本,这些文本应该被替换成用户提供的内容。
该图标代表了提示、建议,或者一般性注释。
使用示例代码
Using Code Examples
本书旨在帮助你完成手头的工作。一般而言,你可以在自己的程序和文档中随意使用书中代码。除非原样引用大量的代码,否则你无须征得我们的许可。例如,在编写程序时引用了本书的若干代码片段是无须许可的。而销售或发行O’Reilly图书的示例光盘则是需要许可的。通过引用书中内容及示例代码的方式来答疑解难是无须许可的。而将书中的大量示例代码加入到你的产品文档中则是需要许可的。
如果你在引用时注明出处,我们将不胜感激,但是这并非必须。引用通常包含了标题、作者、出版商,以及ISBN号。例如:“Programming Collective Intelligence by Toby Segaran. Copyright 2007 Toby Segaran, 978-0-596-52932-1”。
如果你发现自己对示例代码的使用有失公允或违反了上述条款,敬请通过permissions@ oreilly.com与我们取得联系。
如何联系我们
How to Contact Us
请将对本书的评价和存在的问题通过如下地址告知出版者:
美国:
O’Reilly Media, Inc.
1005 Gravenstein Highway North
Sebastopol, CA 95472
中国:
北京市西城区西直门南大街2 号成铭大厦C 座807 室(100035)
奥莱利技术咨询(北京)有限公司
与本书有关的在线信息如下所示:
http://www.oreilly.com/catalog/9780596529321(原书)
如果你想就本书发表评论或提问技术问题,请发送E-mail至:
bookquestions@oreilly.com
致谢
Acknowledgments
我想对每一位曾经参与本书编写与出版的O’Reilly工作人员表达我的感谢之情。首先,我要感谢Nat Torkington,是他告诉我写书这个想法值得一试,我还要感谢Mike Hendrickson和Brian Jepson,是他们听了我的絮叨并令我兴致勃勃地撰写本书,我尤其要感谢Mary O’Brien,他接手Brian的编辑工作,并且总是能够缓解我对工程浩大的担忧。
在出版团队中,我要感谢Marlowe Shaeffer、Rob Romano、Jessamyn Read、Amy Thomson和Sarah Schneider,是他们将我的插图与书稿编辑成读者想要看到的形式。
感谢每一位参与本书审校工作的人,尤其是Paul Tyma、Matthew Russell、Jeff Hammerbacher、Terry Camerlengo、Andreas Weigend、Daniel Russell和Tim Wolters。
感谢我的父母。
最后,万分感谢我的几位朋友,他们帮助我利用头脑风暴形成了有关本书的一些想法,并且总能对我无暇陪伴他们表示理解:Andrea Matthews、Jeff Beene、Laura Miyakawa、Neil Stroup和Brooke Blumenstein。如果没有你们的支持,写作本书会更为艰难,而且我必会漏掉一些更为有趣的示例。