大數據 互聯網大規模數據挖掘與分佈式處理(第2版)

[美] 萊斯科夫(Jure Leskovec)拉賈拉曼(Anand Rajaraman) 厄爾曼(Jeffrey David Ullman)

  • 出版商: 人民郵電
  • 出版日期: 2020-04-01
  • 定價: $474
  • 售價: 8.5$403
  • 語言: 簡體中文
  • 頁數: 372
  • ISBN: 711539525X
  • ISBN-13: 9787115395252
  • 相關分類: 大數據 Big-data

下單後立即進貨 (約4週~6週)

  • 大數據 互聯網大規模數據挖掘與分佈式處理(第2版)-preview-1
大數據 互聯網大規模數據挖掘與分佈式處理(第2版)-preview-1

相關主題

商品描述

本書由斯坦福大學“Web挖掘”課程的內容總結而成,主要關註極大規模數據的挖掘。主要內容包括分佈式文件系統、相似性搜索、搜索引擎技術、頻繁項集挖掘、聚類算法、廣告管理及推薦系統。其中相關章節有對應的習題,以鞏固所講解的內容。讀者更可以從網上獲取相關拓展材料。

作者簡介

Jure Leskovec 斯坦福大学计算机科学系助理教授,研究方向是大型社交和信息网络的数据挖掘。他的研究成果获得了很多奖项,如Microsoft Research Faculty Fellowship、Alfred P. Sloan Fellowship和Okawa Foundation Fellowship,还获得了很多**佳论文奖,同时也被《纽约时报》《华尔街日报》《华盛顿邮报》《麻省理工科技评论》《连线》、NBC、BBC等流行的社会媒体刊载。他还创建了斯坦福网络分析平台(SNAP,http://snap.stanford.edu)。Twitter账号是@jure。

Anand Rajaraman 数据库和Web技术领域**,创业投资基金Cambrian联合创始人,斯坦福大学计算机科学系助理教授。Rajaraman的职业生涯非常成功:1996年创办Junglee公司,两年后被亚马逊以2.5亿美元收购,Rajaraman被聘为亚马逊技术总监,推动亚马逊从一个零售商转型为零售平台;2000年与人合创Cambrian,孵化出几个后来被谷歌收购的公司;2005年创办Kosmix公司并任CEO,该公司于2011年被沃尔玛集团收购,Rajaraman被聘为沃尔玛负责全球电子商务业务的**副总裁。Rajaraman生于印度,在斯坦福大学获得计算机科学硕士和博士学位。求学期间与人合著的一篇论文荣列近20年来被引用次数**多的论文之一。Twitter账号是@anand_raj。

Jeffrey David Ullman 美国国家工程院院士,计算机科学家。早年在贝尔实验室工作,之后任教于普林斯顿大学,十年后加入斯坦福大学直到退休,一生的科研、著书和育人成果**。他是ACM会员,曾获SIGMOD创新奖、高德纳奖、冯诺依曼奖等多项科研大奖;他是“龙书”《编译原理》、数据库名著《数据库系统实现》等多部经典著作的合著者;麾下多名学生成为了数据库领域的专家,其中**有名的当属谷歌创始人Sergey Brin;本书**作者也是他的得意弟子。Ullman目前任Gradiance公司CEO。

目錄大綱

目錄

第 1 章 數據挖掘基本概念 1

1.1 數據挖掘的定義 1

1.1.1 統計建模 1

1.1.2 機器學習 1

1.1.3 建模的計算方法 2

1.1.4 數據匯總 2

1.1.5 特徵抽取 3

1.2 數據挖掘的統計限制 4

1.2.1 整體情報預警 4

1.2.2 邦弗朗尼原理 4

1.2.3 邦弗朗尼原理的一個例子 5

1.2.4 習題 6

1.3 相關知識 6

1.3.1 詞語在文檔中的重要性 6

1.3.2 哈希函數 7

1.3.3 索引 8

1.3.4 二級存儲器 9

1.3.5 自然對數的底e 10

1.3.6 冪定律 11

1.3.7 習題 12

1.4 本書概要 13

1.5 小結 14

1.6 參考文獻 15

第 2 章 MapReduce及新軟件棧 16

2.1 分佈式文件系統 17

2.1.1 計算節點的物理結構 17

2.1.2 大規模文件系統的結構 18

2.2 MapReduce 19

2.2.1 Map 任務 20

2.2.2 按鍵分組 20

2.2.3 Reduce 任務 21

2.2.4 組合器 21

2.2.5 MapReduce 的執行細節 22

2.2.6 節點失效的處理 23

2.2.7 習題 23

2.3 使用MapReduce 的算法 23

2.3.1 基於MapReduce 的矩陣—向量

乘法實現 24

2.3.2 向量v 無法放入內存時的處理 24

2.3.3 關系代數運算 25

2.3.4 基於MapReduce 的選擇運算 27

2.3.5 基於MapReduce 的投影運算 27

2.3.6 基於MapReduce 的並、交和差運算 28

2.3.7 基於MapReduce 的自然連接運算 28

2.3.8 基於MapReduce 的分組和聚合運算 29

2.3.9 矩陣乘法 29

2.3.10 基於單步MapReduce 的矩陣乘法 30

2.3.11 習題 31

2.4 MapReduce 的擴展 31

2.4.1 工作流系統 32

2.4.2 MapReduce 的遞歸擴展版本 33

2.4.3 Pregel 系統 35

2.4.4 習題 35

2.5 通信開銷模型 36

2.5.1 任務網絡的通信開銷 36

2.5.2 時鐘時間 37

2.5.3 多路連接 38

2.5.4 習題 41

2.6 MapReduce 復雜性理論 41

2.6.1 Reducer 規模及復制率 41

2.6.2 一個例子:相似性連接 42

2.6.3 MapReduce 問題的一個圖模型 44

2.6.4 映射模式 45

2.6.5 並非所有輸入都存在時的處理 46

2.6.6 復制率的下界 46

2.6.7 案例分析:矩陣乘法 48

2.6.8 習題 51

2.7 小結 51

2.8 參考文獻 53

第3 章 相似項發現 55

3.1 近鄰搜索的應用 55

3.1.1 集合的Jaccard 相似度 55

3.1.2 文檔的相似度 56

3.1.3 協同過濾——一個集合相似問題 57

3.1.4 習題 58

3.2 文檔的shingling 58

3.2.1 k-shingle 58

3.2.2 shingle 大小的選擇 59

3.2.3 對shingle 進行哈希 59

3.2.4 基於詞的shingle 60

3.2.5 習題 60

3.3 保持相似度的集合摘要表示 61

3.3.1 集合的矩陣表示 61

3.3.2 **小哈希 62

3.3.3 **小哈希及Jaccard 相似度 62

3.3.4 **小哈希簽名 63

3.3.5 **小哈希簽名的計算 63

3.3.6 習題 66

3.4 文檔的局部敏感哈希算法 67

3.4.1 面向**小哈希簽名的LSH 67

3.4.2 行條化策略的分析 68

3.4.3 上述技術的綜合 69

3.4.4 習題 70

3.5 距離測度 70

3.5.1 距離測度的定義 71

3.5.2 歐氏距離 71

3.5.3 Jaccard 距離 72

3.5.4 餘弦距離72

3.5.5 編輯距離 73

3.5.6 海明距離 74

3.5.7 習題 74

3.6 局部敏感函數理論 75

3.6.1 局部敏感函數 76

3.6.2 面向Jaccard 距離的局部敏感函數族 77

3.6.3 局部敏感函數族的放大處理 77

3.6.4 習題 79

3.7 面向其他距離測度的LSH 函數族 80

3.7.1 面向海明距離的LSH 函數族 80

3.7.2 隨機超平面和餘弦距離 80

3.7.3 梗概 81

3.7.4 面向歐氏距離的LSH 函數族 82

3.7.5 面向歐氏空間的更多LSH函數族 83

3.7.6 習題 83

3.8 LSH 函數的應用 84

3.8.1 實體關聯 84

3.8.2 一個實體關聯的例子 85

3.8.3 記錄匹配的驗證 86

3.8.4 指紋匹配 87

3.8.5 適用於指紋匹配的LSH函數族 87

3.8.6 相似新聞報道檢測 88

3.8.7 習題 89

3.9 面向高相似度的方法 90

3.9.1 相等項發現 90

3.9.2 集合的字符串表示方法 91

3.9.3 基於長度的過濾 91

3.9.4 前綴索引 92

3.9.5 位置信息的使用 93

3.9.6 使用位置和長度信息的索引 94

3.9.7 習題 96

3.10 小結 97

3.11 參考文獻 98

第4 章 數據流挖掘 100

4.1 流數據模型 100

4.1.1 一個數據流管理系統 100

4.1.2 流數據源的例子 101

4.1.3 流查詢 102

4.1.4 流處理中的若乾問題 103

4.2 流當中的數據抽樣 103

4.2.1 一個富於啟發性的例子 104

4.2.2 代表性樣本的獲取 104

4.2.3 一般的抽樣問題 105

4.2.4 樣本規模的變化 105

4.2.5 習題 106

4.3 流過濾 106

4.3.1 一個例子 106

4.3.2 布隆過濾器 107

4.3.3 布隆過濾方法的分析 107

4.3.4 習題108

4.4 流中獨立元素的數目統計 109

4.4.1 獨立元素計數問題 109

4.4.2 FM 算法 109

4.4.3 組合估計 110

4.4.4 空間需求 111

4.4.5 習題 111

4.5 矩估計 111

4.5.1 矩定義 111

4.5.2 二階矩估計的AMS 算法 112

4.5.3 AMS 算法有效的原因 113

4.5.4 更高階矩的估計 113

4.5.5 無限流的處理 114

4.5.6 習題 115

4.6 窗口內的計數問題 116

4.6.1 **計數的開銷 116

4.6.2 DGIM 算法 116

4.6.3 DGIM 算法的存儲需求 118

4.6.4 DGIM 算法中的查詢應答 118

4.6.5 DGIM 條件的保持 119

4.6.6 降低錯誤率 120

4.6.7 窗口內計數問題的擴展 120

4.6.8 習題 121

4.7 衰減窗口 121

4.7.1 **常見元素問題 121

4.7.2 衰減窗口的定義 122

4.7.3 **流行元素的發現 123

4.8 小結 123

4.9 參考文獻 124

第5 章 鏈接分析 126

5.1 PageRank 126

5.1.1 早期的搜索引擎及詞項作弊 126

5.1.2 PageRank 的定義 128

5.1.3 Web 結構 130

5.1.4 避免終止點 132

5.1.5 採集器陷阱及“抽稅”法 134

5.1.6 PageRank 在搜索引擎中的使用 136

5.1.7 習題 136

5.2 PageRank 的快速計算 137

5.2.1 轉移矩陣的表示 137

5.2.2 基於MapReduce 的PageRank迭代計算 138

5.2.3 結果向量合並時的組合器使用 139

5.2.4 轉移矩陣中塊的表示 140

5.2.5 其他高效的PageRank 迭代方法 141

5.2.6 習題 142

5.3 面向主題的PageRank 142

5.3.1 動機 142

5.3.2 有偏