內容簡介
本書由史丹福大學“Web 挖掘”課程的內容總結而成，主要關注極大規模數據的挖掘。主要內容包括分散式檔案系統、相似性搜尋、搜尋引擎技術、頻繁項集挖掘、聚類算法、廣告管理及推薦系統、社會網路圖挖掘和大規模機器學習等。其中每一章節有對應的習題，以鞏固所講解的內容。讀者更可以從網上獲取相關拓展材料。
作者簡介
Jure Leskovec
史丹福大學計算機科學系助理教授，研究方向是大型社交和信息網路的數據挖掘。他的研究成果獲得了很多獎項，如Microsoft Research Faculty Fellowship、Alfred P. Sloan Fellowship和Okawa Foundation Fellowship，還獲得了很多最佳論文獎，同時也被《紐約時報》《華爾街日報》《華盛頓郵報》《麻省理工科技評論》《連線》、NBC、BBC等流行的社會媒體刊載。他還創建了斯坦福網路分析平台
Anand Rajaraman
資料庫和Web技術領域權威，創業投資基金Cambrian聯合創始人，史丹福大學計算機科學系助理教授。Rajaraman的職業生涯非常成功：1996年創辦Junglee公司，兩年後被亞馬遜以2.5億美元收購，Rajaraman被聘為亞馬遜技術總監，推動亞馬遜從一個零售商轉型為零售平台；2000年與人合創Cambrian，孵化出幾個後來被谷歌收購的公司；2005年創辦Kosmix公司並任CEO，該公司於2011年被沃爾瑪集團收購，Rajaraman被聘為沃爾瑪負責全球電子商務業務的高級副總裁。Rajaraman生於印度，在史丹福大學獲得計算機科學碩士和博士學位。求學期間與人合著的一篇論文榮列近20年來被引用次數最多的論文之一。
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 有偏的隨機遊走模型 143
5.3.3 面向主題的PageRank 的使用 144
5.3.4 基於辭彙的主題推斷 144
5.3.5 習題 145
5.4 連結作弊 145
5.4.1 垃圾農場的架構 145
5.4.2 垃圾農場的分析 147
5.4.3 與連結作弊的鬥爭 147
5.4.4 TrustRank 148
5.4.5 垃圾質量 148
5.4.6 習題 149
5.5 導航頁和權威頁 149
5.5.1 HITS的直觀意義 150
5.5.2 導航度和權威度的形式化 150
5.5.3 習題 153
5.6 小結 153
5.7 參考文獻 155
第6章 頻繁項集 157
6.1 購物籃模型 157
6.1.1 頻繁項集的定義 157
6.1.2 頻繁項集的套用 159
6.1.3 關聯規則 160
6.1.4 高可信度關聯規則的發現 161
6.1.5 習題 162
6.2 購物籃及A-Priori算法 163
6.2.1 購物籃數據的表示 163
6.2.2 項集計數中的記憶體使用 164
6.2.3 項集的單調性 165
6.2.4 二元組計數 166
6.2.5 A-Priori算法 166
6.2.6 所有頻繁項集上的A-Priori算法 168
6.2.7 習題 169
6.3 更大數據集在記憶體中的處理 170
6.3.1 PCY算法 171
6.3.2 多階段算法 172
6.3.3 多哈希算法 174
6.3.4 習題 175
6.4 有限掃描算法 177
6.4.1 簡單的隨機化算法 177
6.4.2 抽樣算法中的錯誤規避 178
6.4.3 SON算法 179
6.4.4 SON算法和MapReduce 179
6.4.5 Toivonen算法 180
6.4.6 Toivonen算法的有效性分析 181
6.4.7 習題 181
6.5 流中的頻繁項計數 182
6.5.1 流的抽樣方法 182
6.5.2 衰減視窗中的頻繁項集 183
6.5.3 混合方法 183
6.5.4 習題 184
6.6 小結 184
6.7 參考文獻 186
第7章 聚類 187
7.1 聚類技術介紹 187
7.1.1 點、空間和距離 187
7.1.2 聚類策略 188
7.1.3 維數災難 189
7.1.4 習題 190
7.2 層次聚類 190
7.2.1 歐氏空間下的層次聚類 191
7.2.2 層次聚類算法的效率 194
7.2.3 控制層次聚類的其他規則 194
7.2.4 非歐空間下的層次聚類 196
7.2.5 習題 197
7.3 k-均值算法 198
7.3.1 k-均值算法基本知識 198
7.3.2 k-均值算法的簇初始化 198
7.3.3 選擇正確的k值 199
7.3.4 BFR算法 200
7.3.5 BFR算法中的數據處理 202
7.3.6 習題 203
7.4 CURE算法 204
7.4.1 CURE算法的初始化 205
7.4.2 CURE算法的完成 206
7.4.3 習題 206
7.5 非歐空間下的聚類 207
7.5.1 GRGPF算法中的簇表示 207
7.5.2 簇表示樹的初始化 207
7.5.3 GRGPF算法中的點加入 208
7.5.4 簇的分裂及合併 209
7.5.5 習題 210
7.6 流聚類及並行化 210
7.6.1 流計算模型 210
7.6.2 一個流聚類算法 211
7.6.3 桶的初始化 211
7.6.4 桶合併 211
7.6.5 查詢應答 213
7.6.6 並行環境下的聚類 213
7.6.7 習題 214
7.7 小結 214
7.8 參考文獻 216
第8章 Web廣告 218
8.1 線上廣告相關問題 218
8.1.1 廣告機會 218
8.1.2 直投廣告 219
8.1.3 展示廣告的相關問題 219
8.2 線上算法 220
8.2.1 線上和離線算法 220
8.2.2 貪心算法 221
8.2.3 競爭率 222
8.2.4 習題 222
8.3 廣告匹配問題 223
8.3.1 匹配及完美匹配 223
8.3.2 最大匹配貪心算法 224
8.3.3 貪心匹配算法的競爭率 224
8.3.4 習題 225
8.4 adwords問題 225
8.4.1 搜尋廣告的歷史 226
8.4.2 adwords問題的定義 226
8.4.3 adwords問題的貪心方法 227
8.4.4 Balance算法 228
8.4.5 Balance算法競爭率的一個下界 228
8.4.6 多投標者的Balance算法 230
8.4.7 一般性的Balance算法 231
8.4.8 adwords問題的最後論述 232
8.4.9 習題 232
8.5 adwords的實現 232
8.5.1 投標和搜尋查詢的匹配 233
8.5.2 更複雜的匹配問題 233
8.5.3 文檔和投標之間的匹配算法 234
8.6 小結 235
8.7 參考文獻 237
第9章 推薦系統 238
9.1 一個推薦系統的模型 238
9.1.1 效用矩陣 238
9.1.2 長尾現象 239
9.1.3 推薦系統的套用 241
9.1.4 效用矩陣的填充 241
9.2 基於內容的推薦 242
9.2.1 項模型 242
9.2.2 文檔的特徵發現 242
9.2.3 基於Tag的項特徵獲取 243
9.2.4 項模型的表示 244
9.2.5 用戶模型 245
9.2.6 基於內容的項推薦 246
9.2.7 分類算法 247
9.2.8 習題 248
9.3 協同過濾 249
9.3.1 相似度計算 249
9.3.2 相似度對偶性 252
9.3.3 用戶聚類和項聚類 253
9.3.4 習題 254
9.4 降維處理 254
9.4.1 UV分解 255
9.4.2 RMSE 255
9.4.3 UV分解的增量式計算 256
9.4.4 對任一元素的最佳化 259
9.4.5 一個完整UV 分解算法的構建 259
9.4.6 習題 261
9.5 NetFlix競賽 262
9.6 小結 263
9.7 參考文獻 264
第10章 社會網路圖挖掘 265
10.1 將社會網路看成圖 265
10.1.1 社會網路的概念 265
10.1.2 將社會網路看成圖 266
10.1.3 各種社會網路的例子 267
10.1.4 多類型節點構成的圖 268
10.1.5 習題 269
10.2 社會網路圖的聚類 269
10.2.1 社會網路圖的距離計算 269
10.2.2 套用標準的聚類算法 270
10.2.3 中介度 271
10.2.4 Girvan-Newman算法 271
10.2.5 利用中介度來發現社區 274
10.2.6 習題 275
10.3 社區的直接發現 275
10.3.1 團的發現 276
10.3.2 完全二部圖 276
10.3.3 發現完全二部子圖 277
10.3.4 完全二部子圖一定存在的原因 277
10.3.5 習題 279
10.4 圖劃分 280
10.4.1 圖劃分的好壞標準 280
10.4.2 歸一化割 280
10.4.3 描述圖的一些矩陣 281
10.4.4 拉普拉斯矩陣的特徵值 282
10.4.5 其他圖劃分方法 284
10.4.6 習題 284
10.5 重疊社區的發現 285
10.5.1 社區的本質 285
10.5.2 極大似然估計 286
10.5.3 關係圖模型 287
10.5.4 避免成員隸屬關係的離散式變化 288
10.5.5 習題 290
10.6 Simrank 290
10.6.1 社會網路上的隨機遊走者 290
10.6.2 帶重啟的隨機遊走 291
10.6.3 習題 293
10.7 三角形計數問題 293
10.7.1 為什麼要對三角形計數 294
10.7.2 一個尋找三角形的算法 294
10.7.3 三角形尋找算法的最優性 295
10.7.4 基於MapReduce尋找三角形 295
10.7.5 使用更少的Reduce任務.297
10.7.6 習題 297
10.8 圖的鄰居性質 298
10.8.1 有向圖和鄰居 298
10.8.2 圖的直徑 299
10.8.3 傳遞閉包和可達性 300
10.8.4 基於MapReduce的傳遞閉包求解 301
10.8.5 智慧型傳遞閉包 303
10.8.6 基於圖歸約的傳遞閉包 304
10.8.7 鄰居規模的近似計算 305
10.8.8 習題 306
10.9 小結 307
10.10 參考文獻 310
第11章 降維處理 312
11.1 特徵值和特徵向量 312
11.1.1 定義 312
11.1.2 特徵值與特徵向量計算 313
11.1.3 基於冪疊代方法的特徵對求解 315
11.1.4 特徵向量矩陣 317
11.1.5 習題 317
11.2 主成分分析 318
11.2.1 一個示例 318
11.2.2 利用特徵向量進行降維 321
11.2.3 距離矩陣 322
11.2.4 習題 323
11.3 奇異值分解 323
11.3.1 SVD的定義 323
11.3.2 SVD解析 325
11.3.3 基於SVD的降維 326
11.3.4 將較低奇異值置為0後有效的原因 327
11.3.5 使用概念進行查詢處理 328
11.3.6 矩陣SVD的計算 329
11.3.7 習題 330
11.4 CUR 分解 331
11.4.1 CUR 的定義 331
11.4.2 合理選擇行和列 332
11.4.3 構建中間矩陣 333
11.4.4 完整的CUR 分解 334
11.4.5 去除重複行和列 335
11.4.6 習題 335
11.5 小結 336
11.6 參考文獻 337
第12章 大規模機器學習 338
12.1 機器學習模型 338
12.1.1 訓練集 338
12.1.2 一些例子 339
12.1.3 機器學習方法 341
12.1.4 機器學習架構 342
12.1.5 習題 344
12.2 感知機 344
12.2.1 訓練閾值為0 的感知機 344
12.2.2 感知機的收斂性 347
12.2.3 Winnow算法 347
12.2.4 允許閾值變化的情況 349
12.2.5 多類感知機 350
12.2.6 變換訓練集 351
12.2.7 感知機的問題 351
12.2.8 感知機的並行實現 353
12.2.9 習題 354
12.3 支持向量機 354
12.3.1 支持向量機的構成 354
12.3.2 超平面歸一化 356
12.3.3 尋找最優逼近分界面 357
12.3.4 基於梯度下降法求解SVM 359
12.3.5 隨機梯度下降 363
12.3.6 SVM的並行實現 363
12.3.7 習題 363
12.4 近鄰學習 364
12.4.1 近鄰計算的框架 364
12.4.2 最近鄰學習 365
12.4.3 學習一維函式 365
12.4.4 核回歸 367
12.4.5 處理高維歐氏空間數據 368
12.4.6 對非歐距離的處理 369
12.4.7 習題 369
12.5 各種學習方法的比較 370
12.6 小結 371
12.7 參考文獻 372
文摘
第9章介紹推薦系統。很多Web套用中都有給用戶推薦其感興趣的數據項的功能。Netflix競賽就是一個例子，該競賽期望對用戶感興趣的電影進行預測。而Amazon希望根據顧客的購買興趣來推薦一款商品。推薦主要有兩種方法。一種方法是，我們可以將數據項通過其特徵來刻畫，比如電影中的明星，然後推薦與已知的用戶喜歡的物品具有同樣特徵的物品。另一種方法是，我們可以考察那些與當前用戶具有相似愛好的用戶，根據他們喜歡的物品來向當前用戶推薦（該技術通常稱為協同過濾）。
第10章介紹社會網路及分析算法。最典型的社會網路的例子是Facebook的朋友關係圖，其中節點代表人，而兩個人如果是朋友的話，他們之間就有邊相連。而像Twitter上的冬粉關注構成的有向圖也可以看成社會網路。社會網路中一個要解決的普遍問題是識別其中的“社區”，即一個個小規模的節點集合，但是集合內節點之間卻有大量的邊將它們連線起來。社會網路的其他問題也是圖的一般性問題，比如傳遞閉包或圖直徑的計算，但是在網路規模如此巨大的情況下問題也變得十分困難。
第11章介紹降維技術。給定一個極大的、通常比較稀疏的矩陣。我們可以將該矩陣想像為兩類實體之間的關係表示，比如觀眾對影片的評級關係。直觀上看，只會存在很少量的概念，而且概念的數目會比影片或觀眾的數目少很多，這些概念可以解釋為什麼某些觀眾喜歡某些影片。我們提供了多個將矩陣簡化為多個矩陣的乘積的算法，簡化後的矩陣某一維要小很多。其中，一個矩陣將一類實體與這些少量的概念相關聯，另一個矩陣將概念和另一類實體相關聯。如果處理正確的話，這些小矩陣的乘積會十分接近原始矩陣。
最後，第12章討論極大規模數據集上的機器學習算法。其中的技術包括感知機、支持向量機、基於梯度下降的模型求解、近鄰模型和決策樹等。
