前言 Preface

無論是有意還是無意临燃，越來越多投身于互聯(lián)網(wǎng)的人們已經(jīng)制造出了相當(dāng)多的數(shù)據(jù)，這給了我們無數(shù)潛在的機(jī)會(huì)來洞悉用戶體驗(yàn)霎烙、商業(yè)營銷募寨、個(gè)人偏好和通常所謂的人類行為（human behavior）。

本書向大家介紹了一個(gè)新興的領(lǐng)域审葬，稱為聚集型智慧（collective intelligence）深滚。

這一領(lǐng)域涵蓋了諸多方法，借助這些方法我們可以從眾多Web站點(diǎn)處（這些站點(diǎn)的名字或許你曾經(jīng)有所耳聞）提取到值得關(guān)注的重要數(shù)據(jù)涣觉；借助這些方法我們還可以從使用自己應(yīng)用程序的用戶那里搜集信息痴荐，并對(duì)我們所掌握的數(shù)據(jù)進(jìn)行分析和理解。

本書的目的是要帶領(lǐng)你超越以數(shù)據(jù)庫為后端的簡(jiǎn)單應(yīng)用系統(tǒng)旨枯，并告訴你如何利用自己和他人每天搜集到的信息來編寫更為智能的程序蹬昌。

先決條件 Prerequisites

本書的代碼示例是用Python語言編寫的，因此熟悉Python編程將會(huì)有助于你對(duì)算法的理解攀隔，不過筆者給出了所有算法的解釋說明皂贩，所以其他語言的程序員也能看懂栖榨。對(duì)于已經(jīng)了解了像Ruby或Perl這樣高級(jí)語言的程序員，Python代碼應(yīng)該是非常容易理解的明刷。

本書的目的不是要作為一本學(xué)習(xí)編程的指導(dǎo)書婴栽，因此尤為重要的一點(diǎn)在于，為了熟悉基本概念辈末，我們最好已編寫過足夠多的代碼才行愚争。如果懂得遞歸和一點(diǎn)點(diǎn)函數(shù)式編程（functional programming）的基本概念，那么我們就會(huì)發(fā)覺書中的內(nèi)容是很容易理解的挤聘。

本書并不假設(shè)你已經(jīng)具備了任何有關(guān)數(shù)據(jù)分析轰枝、機(jī)器學(xué)習(xí)或統(tǒng)計(jì)學(xué)方面的知識(shí)。筆者在嘗試以盡可能淺顯易懂的方式來解釋數(shù)學(xué)概念组去，不過具備一點(diǎn)三角學(xué)和統(tǒng)計(jì)學(xué)的基本知識(shí)將會(huì)對(duì)你理解算法有所助益鞍陨。

示例風(fēng)格 Style of Examples

本書每一章節(jié)的代碼示例都是以一種教程式的風(fēng)格編寫而成的，它鼓勵(lì)你以循序漸進(jìn)的方式來構(gòu)建應(yīng)用程序从隆，并對(duì)算法的工作原理有一個(gè)深入的理解和認(rèn)識(shí)诚撵。

大多數(shù)情況下，寫完一個(gè)新的函數(shù)或方法之后键闺，我們會(huì)在一個(gè)交互的會(huì)話環(huán)境里使用它寿烟，以此來理解算法的工作原理。通常算法是有簡(jiǎn)單的變體的辛燥，我們可以用多種方式對(duì)其進(jìn)行擴(kuò)展筛武。

通過示例講解并以交互的方式對(duì)其進(jìn)行測(cè)試，我們對(duì)算法將會(huì)有更為深入的理解购桑，從而可以對(duì)其進(jìn)行改造畅铭，以適應(yīng)自己的應(yīng)用程序。

為何選擇Python勃蜘？Why Python?

盡管書中的算法是伴隨著對(duì)相關(guān)公式的解釋硕噩，以文字形式加以描述的，但是假如有針對(duì)算法和示例問題的實(shí)際代碼缭贡，那將會(huì)是更有助益的（而且有可能更易于理解）炉擅。

本書中的所有示例代碼都是用Python，一種優(yōu)秀的高級(jí)語言阳惹，編寫而成的谍失。之所以選擇Python是因?yàn)樗娜缦绿匦浴?/p>

• 簡(jiǎn)練
  使用像Python這樣的動(dòng)態(tài)類型語言編寫的代碼往往比用其他主流語言編寫而成的代碼更加簡(jiǎn)短。這意味著莹汤，在完成示例的過程中會(huì)有更少的錄入工作快鱼，而且這也意味著我們將更容易記住算法并真正領(lǐng)會(huì)算法的原理。

• 易于閱讀
  Python不時(shí)被人們指為"可執(zhí)行的偽代碼"。雖然很明顯這是一種夸大之詞抹竹，但是它表明线罕，大多數(shù)有經(jīng)驗(yàn)的程序員可以讀懂Python代碼并領(lǐng)會(huì)代碼所要表達(dá)的意圖。Python中一些不是很顯見的語言要素將會(huì)在后面的"Python技巧"一節(jié)中加以解釋窃判。

• 易于擴(kuò)展
  Python隨附了許多標(biāo)準(zhǔn)庫钞楼，這些庫涉及數(shù)學(xué)函數(shù)、XML（擴(kuò)展標(biāo)記語言）解析袄琳，以及網(wǎng)頁下載询件。本書中用到的非標(biāo)準(zhǔn)庫，如RSS（Really Simple Syndication）解析器和SQLite接口唆樊，則是免費(fèi)的宛琅，很容易下載、安裝和使用逗旁。

• 交互性
  在學(xué)習(xí)示例的過程中夯秃，可以嘗試執(zhí)行我們編好的函數(shù)，而無須為此專門編寫額外的程序痢艺，這一點(diǎn)是非常有價(jià)值的。Python可以直接從命令行運(yùn)行程序介陶，它還有交互提示堤舒，允許我們鍵入函數(shù)調(diào)用、創(chuàng)建對(duì)象哺呜，并以交互的形式來對(duì)包進(jìn)行測(cè)試舌缤。

• 多范式
  Python支持面向?qū)ο蟆⑦^程式和函數(shù)式編程風(fēng)格某残。機(jī)器學(xué)習(xí)算法千差萬別国撵，最為清晰的做法是針對(duì)不同算法采用不同的范式。有時(shí)將函數(shù)作為參數(shù)傳入很有用處玻墅，而有時(shí)我們則須要在對(duì)象中捕獲狀態(tài)介牙。對(duì)于這兩種方式Python均予以支持。多平臺(tái)和免費(fèi)Python有一個(gè)針對(duì)所有主流平臺(tái)的單一參考實(shí)現(xiàn)澳厢，并且它對(duì)所有平臺(tái)都是免費(fèi)的环础。本書中所列代碼可以運(yùn)行于Windows、Linux和Macintosh環(huán)境剩拢。

Python技巧 Python Tips

對(duì)于有興趣學(xué)習(xí)Python編程的初學(xué)者而言线得，筆者推薦大家閱讀由Mark Lutz與David Ascher合著的《Learning Python》（O'Reilly），該書有對(duì)Python的全面論述徐伐。

為了更為直觀地表達(dá)算法或基礎(chǔ)性概念贯钩，筆者在整本書中使用了一些Python特有的語法，但是其他語言的程序員應(yīng)該會(huì)發(fā)現(xiàn)，Python的代碼相對(duì)而言還是較為容易掌握的角雷。下面是為非Python程序員提供的一份快速概覽祸穷。

• 列表和字典的構(gòu)造函數(shù)
  Python有一組不錯(cuò)的基本類型，其中有兩種類型在本書中被大量使用谓罗，它們分別是列表和字典粱哼。列表是由一組任意類型的值構(gòu)成的有序列表，它由方括號(hào)構(gòu)造而成：

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

字典是由一組名值對(duì)構(gòu)成的無序集合檩咱，類似于其他語言中的hash map揭措。它由大括號(hào)構(gòu)造而成：

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

可以通過序列名后跟方括號(hào)的形式來訪問列表和字典中的元素：有意義的空白字符
與大多數(shù)語言有所不同，Python實(shí)際上是利用代碼的縮進(jìn)來定義代碼塊的刻蚯。請(qǐng)看下列代碼片段：

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

因?yàn)榇a是被縮進(jìn)的绊含，所以語法解釋器知道前兩個(gè)打印語句會(huì)在x為1的時(shí)候被執(zhí)行〈缎冢縮進(jìn)可以是任意數(shù)量的空格躬充，只要它是常量即可。本書使用的縮進(jìn)是兩個(gè)空格讨便。在輸入代碼的時(shí)候充甚，我們須要注意正確拷貝縮進(jìn)。

• 列表推導(dǎo)式
  列表推導(dǎo)式（list comprehension）是一種方便簡(jiǎn)潔的語法形式霸褒，我們可以利用它將一個(gè)列表經(jīng)過濾后轉(zhuǎn)換成另一個(gè)列表伴找，也可以利用它將函數(shù)應(yīng)用于列表中的元素。列表推導(dǎo)式以如下形式書寫：

[表達(dá)式 for 變量 in 列表]

或者：

[表達(dá)式 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]

本書中頻繁地使用了列表推導(dǎo)式技矮，因?yàn)橐獙⒁粋€(gè)函數(shù)應(yīng)用于整個(gè)列表，或是刪除不需要的列表項(xiàng)時(shí)殊轴，這種表達(dá)方法非常簡(jiǎn)練衰倦。列表推導(dǎo)式的另一種常見用法是與dict構(gòu)造函數(shù)結(jié)合在一起使用：

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

上述代碼將會(huì)建立一個(gè)字典，以原先的列表作為鍵旁理，以每個(gè)列表項(xiàng)乘以10作為值：

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

開放的API Open APIs

用于將聚集型智慧合成起來的算法需要來自許多用戶的數(shù)據(jù)樊零。除機(jī)器學(xué)習(xí)的算法外，本書還論及了許多開放的Web APIs（應(yīng)用編程接口）孽文。這些API允許我們通過特殊的協(xié)議對(duì)來自相應(yīng)Web站點(diǎn)的數(shù)據(jù)進(jìn)行訪問淹接；我們可以編寫程序?qū)?shù)據(jù)下載下來并加以處理。這些數(shù)據(jù)通常是由站點(diǎn)的使用者來提供的叛溢，我們可以從中挖掘出新的內(nèi)涵來塑悼。有的時(shí)候，我們可以用現(xiàn)成的Python庫來訪問這些API楷掉；而有時(shí)厢蒜，如果沒有現(xiàn)成的庫霞势，那么最為直接的做法莫過于創(chuàng)建自己的接口來訪問數(shù)據(jù)，為此我們須要利用Python提供的內(nèi)建庫將數(shù)據(jù)下載下來斑鸦，并對(duì)XML加以解析愕贡。

此處列出了一系列提供開放API的Web站點(diǎn)，我們將在本書中陸續(xù)接觸到這些站點(diǎn)巷屿。

• del.icio.us
  一個(gè)社會(huì)型書簽應(yīng)用系統(tǒng)（social bookmarking application）固以，其開放的API允許你根據(jù)標(biāo)簽（tag）或特定的用戶來下載鏈接嘱巾。

• **Kayak **
  一個(gè)提供API的旅游網(wǎng)站憨琳，你可以利用API在自己的程序中集成針對(duì)航班和旅館的搜索旬昭。

• **eBay **
  一個(gè)提供API的在線交易站點(diǎn)篙螟，允許你查詢當(dāng)前正在出售的貨品。

• Hot or Not
  一個(gè)評(píng)分與交友的網(wǎng)站遍略，提供API對(duì)人員進(jìn)行搜索，并獲取其評(píng)分及個(gè)人資料骤坐。

• **Akismet **
  一種用于對(duì)協(xié)作型垃圾信息進(jìn)行過濾的API绪杏。

通過對(duì)來自單一源的數(shù)據(jù)進(jìn)行處理，對(duì)來自多個(gè)源的數(shù)據(jù)進(jìn)行組合寞忿，甚至通過將外部信息與自有系統(tǒng)的用戶輸入信息加以組合，我們可以構(gòu)造出大量的潛在應(yīng)用顶岸。對(duì)人們?cè)诓煌W(wǎng)站以各種不同方式產(chǎn)生的數(shù)據(jù)加以充分利用的能力叫编，便是構(gòu)建聚集型智慧的一個(gè)基本要素辖佣。

如果你想尋找更多的提供開放API的Web站點(diǎn)，不妨從訪問ProgrammableWeb開始（http://www.programmableweb.com）搓逾。

各章概覽 Overview of the Chapters

本書的每個(gè)算法都來源于某一現(xiàn)實(shí)的問題卷谈，希望這些問題能夠很容易地被廣大讀者所理解。筆者將嘗試盡量避開那些要求大量領(lǐng)域知識(shí)的問題世蔗，而將焦點(diǎn)集中在那些雖不失復(fù)雜性，但對(duì)大多數(shù)涉足者而言卻又是簡(jiǎn)單易懂的問題上朗兵。

• 第1章，聚集型智慧導(dǎo)言
  本章解釋了蘊(yùn)藏于機(jī)器學(xué)習(xí)背后的概念余掖，并解釋了如何將其應(yīng)用于諸多不同的領(lǐng)域，以及如何利用它對(duì)搜集自許多不同人群的數(shù)據(jù)進(jìn)行分析，并從中得出新的結(jié)論赁豆。

• 第2章，提供推薦
  本章介紹協(xié)作型過濾（collaborative filtering）技術(shù)魔种，這項(xiàng)技術(shù)被許多在線零售商用來向顧客推薦商品或媒體析二。本章中有一節(jié)介紹了如何向一個(gè)社會(huì)型書簽服務(wù)網(wǎng)站的用戶提供推薦鏈接节预，還介紹了如何根據(jù)MovieLens所提供的數(shù)據(jù)集構(gòu)筑一個(gè)影片推薦系統(tǒng)叶摄。

• 第3章心铃，發(fā)現(xiàn)群組
  本章基于第2章中給出的某些觀點(diǎn)准谚，介紹了兩種不同的聚類方法去扣，利用這些方法柱衔，我們可以在一個(gè)大數(shù)據(jù)集中自動(dòng)找出具有相似特征的群組愉棱。本章還演示了如何利用聚類算法從一組頗受歡迎的博客之中尋找群組唆铐，以及利用聚類算法根據(jù)某個(gè)社會(huì)型網(wǎng)站的用戶意愿去尋找群組。

• 第4章艾岂，搜索與排名
  本章描述了構(gòu)成一個(gè)搜索引擎的各個(gè)不同組成部分，它們包括：爬蟲程序（crawler）朋其、索引程序（indexer），以及查詢引擎（query engine）梅猿。本章介紹了以來自外部網(wǎng)站的鏈接信息為依據(jù)給網(wǎng)頁打分的PageRank算法，還向你展示了如何構(gòu)建神經(jīng)網(wǎng)絡(luò)袱蚓，借此獲知與不同結(jié)果相關(guān)聯(lián)的關(guān)鍵詞钞啸。

• 第5章喇潘，優(yōu)化
  本章介紹了優(yōu)化算法体斩，設(shè)計(jì)這些算法的目的颖低，是為了對(duì)問題的數(shù)百萬個(gè)可能的題解進(jìn)行搜索絮吵，并從中選出最優(yōu)解來忱屑。書中利用示例演示了這些算法的各種不同用法源武，包括：為一群去往相同地點(diǎn)的旅客尋找最佳航班，尋求為學(xué)生安排宿舍的最佳方案粱栖，以及給出交叉線數(shù)量最小的網(wǎng)絡(luò)布局话浇。

• 第6章，文檔過濾
  本章向讀者演示了貝葉斯過濾闹究，這一方法被廣泛應(yīng)用于許多免費(fèi)的和商業(yè)的垃圾信息過濾系統(tǒng)中幔崖，用于根據(jù)單詞類型及出現(xiàn)在文檔中的其他特征對(duì)文檔進(jìn)行自動(dòng)分類。我們將其應(yīng)用于一組RSS搜索結(jié)果渣淤，以此來說明對(duì)內(nèi)容項(xiàng)的自動(dòng)分類過程赏寇。

• 第7章，決策樹建模
  本章介紹了決策樹价认，我們不僅將它作為一種預(yù)測(cè)方法嗅定，而且還用它來為決策過程進(jìn)行建模。本章中出現(xiàn)的第一棵決策樹是根據(jù)假想的服務(wù)器日志數(shù)據(jù)構(gòu)建而成的用踩，我們利用它來預(yù)測(cè)用戶是否有可能成為付費(fèi)訂戶（premium subscriber）渠退。本章的另一個(gè)例子則使用了來自真實(shí)Web站點(diǎn)的數(shù)據(jù)，用以對(duì)住房價(jià)格和來自Hot or Not網(wǎng)站的"熱度（hotness）"評(píng)價(jià)進(jìn)行建模脐彩。

• 第8章碎乃，構(gòu)建價(jià)格模型
  本章解決的是數(shù)值預(yù)測(cè)問題而非分類問題，期間用到了k-最近鄰技術(shù)惠奸，并且還用到了第5章中的優(yōu)化算法梅誓。我們將這些方法與eBay API結(jié)合在一起構(gòu)造出一個(gè)系統(tǒng)，能夠根據(jù)拍賣品的一組屬性佛南，預(yù)測(cè)出最終的拍賣價(jià)格梗掰。

• 第9章，高階分類：核方法與SVM
  本章向讀者介紹了如何利用支持向量機(jī)（support-vector machines）對(duì)在線約會(huì)網(wǎng)站的用戶進(jìn)行匹配嗅回，以及如何將其用于針對(duì)專業(yè)交友網(wǎng)站的好友信息搜索及穗。支持向量機(jī)是一項(xiàng)非常高階的技術(shù)，本章將之與其他方法進(jìn)行了對(duì)比妈拌。

• 第10章，尋找獨(dú)立特征
  本章介紹了一種相對(duì)較新的技術(shù)尘分，稱為非負(fù)矩陣因式分解（non-negative matrix factorization），我們利用這項(xiàng)技術(shù)在數(shù)據(jù)集中尋找獨(dú)立的特征丸氛。對(duì)許多數(shù)據(jù)集而言，其中所包含的內(nèi)容都是可以借助一組獨(dú)立特征的組合被重新構(gòu)造出來的缓窜，而這些特征是我們事先不知道的谍咆；非負(fù)矩陣因式分解的思路便是要尋找這些特征私股。在本章中摹察，我們利用一組新聞報(bào)道說明了該項(xiàng)技術(shù)的使用倡鲸；期間，通過新聞故事來尋找其中的主題峭状，一篇給定的新聞故事中會(huì)包含一個(gè)或多個(gè)這樣的主題。

• 第11章优床，智能進(jìn)化
  本章介紹了遺傳編程（genetic programming）的概念，這是一組非常復(fù)雜的技術(shù)胆敞，它超出了優(yōu)化的范疇。并且竿秆，這項(xiàng)技術(shù)實(shí)際上借鑒了進(jìn)化的思想，它是通過自動(dòng)構(gòu)造算法的方式來解決特定問題的幽钢。我們通過一個(gè)簡(jiǎn)單的游戲來說明這項(xiàng)技術(shù)的應(yīng)用。在游戲中匪燕，計(jì)算機(jī)最初只是一個(gè)學(xué)藝不精的初級(jí)選手，但是隨著游戲的不斷進(jìn)行帽驯，它會(huì)通過逐步改進(jìn)其所擁有的代碼來提升自己的技能龟再。

• 第12章尼变，算法總結(jié)
  本章回顧了書中所講述的所有機(jī)器學(xué)習(xí)算法及統(tǒng)計(jì)算法，并將它們與一組人為設(shè)計(jì)的問題做了對(duì)比嫌术。這將有助于我們理解算法的工作原理，并形象地說明每種算法劃分?jǐn)?shù)據(jù)的方法度气。

• 附錄A，第三方函數(shù)庫
  給出了有關(guān)本書所用的第三方庫的信息磷籍，例如在哪里可以找到這些第三方庫现柠，以及如何進(jìn)行安裝。

• 附錄B够吩，數(shù)學(xué)公式
  包含了一部分?jǐn)?shù)學(xué)公式及其說明，以及本書通篇引入的废恋、以代碼形式描述的諸多數(shù)學(xué)概念。

位于每章末尾處的練習(xí)鱼鼓，為讀者提供了許多相關(guān)信息，借此我們可以對(duì)算法進(jìn)行擴(kuò)展并使其變得更加強(qiáng)大迄本。