智慧型Web算法

《智慧型Web算法》是2011年電子工業出版社出版的圖書，作者是Haralambos Marmanis。

基本介紹

• 書名：智慧型Web算法
• 又名：智慧型Web算法
• 作者：Haralambos Marmanis / Dmitry Babenko
• 原版名稱：Algorithms of the Intelligent Web
• 譯者：阿穩 / 陳鋼 
• ISBN：9787121139192
• 頁數：374
• 定價：65.00元
• 出版社：電子工業出版社
• 出版時間：2011-11
• 裝幀：平裝
• 開本：16開

內 容 簡 介

本書涵蓋了五類重要的智慧型算法：搜尋、推薦、聚類、分類和分類器組合，並結合具體的案例討論了它們在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