斯坦福數據挖掘教程, 3/e (Mining of Massive Datasets, 3/e) Mining of Massive Datasets, 3/e

【作者簡介】

尤雷.萊斯科夫（Jure Leskovec）
Pinterest公司首席科學家，斯坦福大學計算機科學系副教授，研究方向為大型社交和信息網絡的數據挖掘。
他的研究成果獲得了很多獎項，如Microsoft Research Faculty Fellowship、Alfred P. Sloan Fellowship和Okawa Foundation Fellowship，還獲得了很多最佳論文獎，同時也被《紐約時報》《華爾街日報》《華盛頓郵報》 《連線》、NBC、BBC和CBC等流行的社會媒體刊載。
他還創建了斯坦福網絡分析平台（SNAP）。

阿南德.拉賈拉曼（Anand Rajaraman）
數據庫和Web技術領域領軍者，矽谷連續創業者和風險投資人，斯坦福大學計算機科學系助理教授。
自1996年起創立過多家公司，這些公司先後被亞馬遜、谷歌和沃爾瑪集團收購，而他本人歷任亞馬遜技術總監、沃爾瑪負責全球電子商務業務的副總裁。
之後創立了風投公司Milliways Ventures和Rocketship VC，投資過Facebook、Lyft等眾多公司。
作為學者，他主要研究數據庫系統、Web和社交媒體，他的研究論文在學術會議上獲得了多個獎項，他在2012年被Fast Company雜誌列入“商界Z具創造力100人”。

杰弗裡.大衛.厄爾曼（Jeffrey David Ullman）
計算機科學家，美國國家工程院院士，2020年圖靈獎得主。
早年在貝爾實驗室工作，之後任教於普林斯頓大學，十年後加入斯坦福大學直至退休，一生的科研、著書和育人成果卓著。他是ACM會員，曾獲SIGMOD創新獎、高德納獎、馮諾依曼獎等多項科研大獎；合著有“龍書”《編譯原理》、數據庫名著《數據庫系統實現》等多部經典著作；培養的多名學生已成為數據庫領域的專家，其中包括谷歌聯合創始人Sergey Brin，本書第二作者也是他的得意弟子。目前擔任Gradiance公司CEO。

【譯者簡介】

王斌博士
小米AI實驗室主任，NLP首席科學家。
中國中文信息學會理事，《中文信息學報》編委。加入小米公司之前，是中科院研究員、博導及中科院大學教授。
譯有《信息檢索導論》《大數據：互聯網大規模數據挖掘與分佈式處理》和《機器學習實戰》等書。

王達侃
優刻得AI部門負責人，曾任WeWork Research & Applied Science中國區負責人，並曾在LinkedIn、Twitter和微軟亞洲研究院負責AI以及大數據方向的研發工作。
碩士畢業於美國斯坦福大學計算機系，本科畢業於上海交通大學ACM班。

第1章數據挖掘基本概念1 
1.1數據挖掘的定義1 
1.1.1建模1 
1.1.2統計建模2 
1.1.3機器學習2 
1.1.4建模的計算方法3 
1.1.5數據概括3 
1.1. 6特徵抽取4 
1.2數據挖掘的統計限制5 
1.2.1整體情報預警5 
1.2.2邦弗朗尼原理5 
1.2.3邦弗朗尼原理的一個例子6 
1.2.4習題7 
1.3相關知識7 
1.3. 1詞語在文檔中的重要性7 
1.3.2哈希函數8 
1.3.3索引9 
1.3.4二級存儲器10 
1.3.5自然對數的底e 11 
1.3.6冪定律12 
1.3.7習題13 
1.4本書概要14 
1.5小結15 
1.6參考文獻16 

第2章MapReduce和新軟件棧17 
2.1分佈式文件系統18 
2.1.1計算節點的物理結構18 
2.1.2大規模文件系統的結構19 
2.2 MapReduce 20 
2.2. 1 Map任務21 
2.2.2按鍵分組21 
2.2.3 Reduce任務22 
2.2.4組合器22 
2.2.5 MapReduce的執行細節23 
2.2.6節點故障的處理24 
2.2.7習題24 
2.3使用MapReduce的算法24 
2.3.1基於MapReduce的矩陣—向量乘法實現25 
2.3.2向量v無法放入內存時的處理26 
2.3.4基於MapReduce的選擇運算28 
2.3.5基於MapReduce的投影運算28 
2.3.6基於MapReduce的並、交和差運算29 
2.3.7基於MapReduce的自然連接運算29 
2.3.8基於MapReduce的分組和聚合運算30 
2.3.9矩陣乘法30 
2.3.10基於單步MapReduce的矩陣乘法31 
2.3.11習題32 
2.4 MapReduce的擴展32 
2.4.1工作流系統33 
2.4.2 Spark 34 
2.4.3 Spark實現36 
2.4.4 TensorFlow 37 
2.4.5 MapReduce的遞歸擴展版本38 
2.4.6整體同步系統40 
2.4.7習題41 
2.5通信開銷模型41 
2.5.1任務網絡的通信開銷42 
2.5.2時鐘時間43 
2.5.3多路連接43 
2.5.4習題46 
2.6 MapReduce複雜性理論47 
2.6.1 Reducer規模及復制率47 
2.6.2一個例子：相似性連接48 
2.6.3 MapReduce問題的一個圖模型51 
2.6.5並非所有輸入都存在時的處理52 
2.6.7案例分析：矩陣乘法54 
2.6.8習題57 
2.7小結58 
2.8參考文獻59 

第3章相似項發現61 
3.1集合相似度的應用62 
3.1.1集合的Jaccard相似度62 
3.1.2文檔的相似度62 
3.1.3協同過濾——一個集合相似問題63 
3.1.4習題64 
3.2文檔的shingling 65 
3.2. 1 k-shingle 65 
3.2.2 shingle大小的選擇65 
3.2.3對shingle進行哈希66 
3.2.4基於詞的shingle 66 
3.2.5習題67 
3.3保持相似度的集合摘要表示67 
3.3.1集合的矩陣表示67 
3.3.2 *小哈希68 
3.3.3 *小哈希和Jaccard相似度69 
3.3.4 *小哈希簽名69 
3.3.5 *小哈希簽名的計算70 
3.3.6對*小哈希加速72 
3.3.7使用哈希加速73 
3.3.8習題75 
3.4文檔的局部敏感哈希算法76 
3.4.1面向*小哈希簽名的LSH 76 
3.4.2行條化策略的分析77 
3.4.3上述技術的綜合79 
3.4.4習題79 
3.5距離測度80 
3.5.1距離測度的定義80 
3.5.2歐氏距離80 
3.5.3 Jaccard距離81 
3.5.4餘弦距離81 
3.5.5編輯距離82 
3.5.6海明距離83 
3.5.7習題83 
3.6局部敏感函數理論85 
3.6.1局部敏感函數85 
3.6.2面向Jaccard距離的局部敏感函數族86 
3.6.3局部敏感函數族的放大處理87 
3.6.4習題89 
3.7面向其他距離測度的LSH函數族89 
3.7.1面向海明距離的LSH函數族89 
3.7.2隨機平面和余弦距離90 
3.7.3梗概91 
3.7.4面向歐氏距離的LSH函數族91 
3.7.5面向歐氏空間的更多LSH函數族92 
3.7.6習題93 
3.8 LSH函數的應用93 
3.8.1實體關聯94 
3.8. 2一個實體關聯的例子94 
3.8.3記錄匹配的驗證95 
3.8.4指紋匹配96 
3.8.5適用於指紋匹配的LSH函數族98 
3.8.7習題99 
3.9面向高相似度的方法99 
3.9.1相等項發現99 
3.9.2集合的字符串表示方法100 
3.9.3基於長度的過濾100 
3.9.4前綴索引101 
3.9.5位置信息的使用102 
3.9.6使用位置和長度信息的索引103 
3.9.7習題105 
3.10小結106 
3.11參考文獻108 

第4章數據流挖掘109 
4.1流數據模型109 
4.1.1一個數據流管理系統109 
4.1.2流數據源的例子110 
4.1.3流查詢111 
4.1.4流處理中的若干問題112 
4.2流當中的數據抽樣112 
4.2.1一個富有啟發性的例子112 
4.2.2代表性樣本的獲取113 
4.2.3一般的抽樣問題114 
4.2.4樣本規模的變化114 
4.2.5習題115 
4.3流過濾115 
4.3.1一個例子115 
4.3.2布隆過濾器116 
4.3.3布隆過濾方法的分析116 
4.3.4習題117 
4.4流中獨立元素的數目統計118 
4.4.1獨立元素計數問題118 
4.4.2 FM算法118 
4.4.3組合估計119 
4.4.4空間需求120 
4.4.5習題120 
4.5矩估計120 
4.5.1矩定義120 
4.5.2二階矩估計的AMS算法121 
4.5.3 AMS算法有效的原因122 
4.5.4更高階矩的估計122 
4.5.5無限流的處理123 
4.5.6習題124 
4.6窗口內的計數問題124 
4.6.1 *確計數的開銷125 
4.6.2 DGIM算法125 
4.6.3 DGIM算法的存儲需求127 
4.6.4 DGIM算法中的查詢應答127 
4.6.5 DGIM條件的保持127 
4.6.6降低錯誤率128 
4.6.7窗口內計數問題的擴展129 
4.6.8習題130 
4.7衰減窗口130 
4.7.1 *常見元素問題130 
4.7.2衰減窗口的定義130 
4.7.3 *流行元素的發現131 
4.8小結132 
4.9參考文獻133 

第5章鏈接分析134 
5.1 PageRank 134 
5.1.1早期的搜索引擎及詞項作弊134 
5.1.2 PageRank的定義136 
5.1.3 Web結構138 
5.1.4避免終止點140 
5.1.5採集器陷阱和“抽稅”法142 
5.1.6 PageRank在搜索引擎中的使用144 
5.1.7習題144 
5.2 PageRank的快速計算145 
5.2.1轉移矩陣的表示146 
5.2 .2基於MapReduce的PageRank迭代計算146 
5.2.3結果向量合併時的組合器使用147 
5.2.4轉移矩陣中塊的表示148 
5.2.5其他高效的PageRank迭代方法149 
5.2.6習題150 
5.3面向主題的PageRank 150 
5.3.1動機150 
5.3.2有偏的隨機遊走模型151 
5.3.3面向主題的PageRank的使用153 
5.3.5習題153 
5.4鏈接作弊153 
5.4.1垃圾農場的架構154 
5.4 .2垃圾農場的分析155 
5.4.3與鏈接作弊的鬥爭156 
5.4.4 TrustRank 156 
5.4.5垃圾質量156 
5.4.6習題157 
5.5導航頁和*威頁157 
5.5.1 HITS的直觀意義158 
5.5. 2導航度和*威度的形式化158 
5.5.3習題161 
5.6小結161 
5.7參考文獻164 

第6章頻繁項集165 
6.1購物籃模型165 
6.1.1頻繁項集的定義165 
6.1.2頻繁項集的應用167 
6.1.3關聯規則168 
6.1.4高可信度關聯規則的發現169 
6.1.5習題170 
6.2購物籃和A-Priori算法171 
6.2.1購物籃數據的表示171 
6.2.2項集計數中的內存使用172 
6.2.3項集的單調性173 
6.2.4二元組計數174 
6.2.5 A-Priori算法174 
6.2.6所有頻繁項集上的A-Priori算法176 
6.2.7習題177 
6.3更大數據集在內存中的處理178 
6.3.1 PCY算法179 
6.3.2多階段算法180 
6.3.3多哈希算法182 
6.3.4習題183 
6.4有限掃描算法185 
6.4.1簡單的隨機化算法185 
6.4.2抽樣算法中的錯誤規避186 
6.4.3 SON算法187 
6.4.4 SON算法和MapReduce 187 
6.4.5 Toivonen算法188 
6.4.6 Toivonen算法的有效性分析189 
6.4.7習題189 
6.5流中的頻繁項計數190 
6.5.1流的抽樣方法190 
6.5.2衰減窗口中的頻繁項集191 
6.5.3混合方法191 
6.5.4習題192 
6.6小結192 
6.7參考文獻194 

第7章聚類195 
7.1聚類技術介紹195 
7.1.1點、空間和距離195 
7.1.2聚類策略196 
7.1.3維數災難197 
7.1.4習題198 
7.2層次聚類198 
7.2.1歐氏空間下的層次聚類198 
7.2.2層次聚類算法的效率202 
7.2.3控制層次聚類的其他規則202 
7.2.4非歐空間下的層次聚類204 
7.2.5習題205 
7.3 k-均值算法206 
7.3.1 k-均值算法基本知識206 
7.3.2 k-均值算法的簇初始化206 
7.3.3選擇正確的k值207 
7.3.4 BFR算法208 
7.3.5 BFR算法中的數據處理210 
7.3.6習題211 
7.4 CURE算法212 
7.4.1 CURE算法的初始化213 
7.4.2 CURE算法的完成214 
7.4.3習題214 
7.5非歐空間下的聚類215 
7.5.1 GRGPF算法中的簇表示215 
7.5.2簇表示樹的初始化215 
7.5.3 GRGPF算法中的點加入216 
7.5.4簇的分裂及合併217 
7.5.5習題218 
7.6流聚類及並行化218 
7.6.1流計算模型218 
7.6.2一個流聚類算法219 
7.6.3桶的初始化219 
7.6.4桶合併219 
7.6.5查詢應答221 
7.6.6並行環境下的聚類221 
7.6.7習題222 
7.7小結222 
7.8參考文獻224 

第8章Web廣告226 
8.1在線廣告相關問題226 
8.1.1廣告機會226 
8.1.2直投廣告227 
8.1.3展示廣告的相關問題227 
8.2在線算法228 
8.2.1在線和離線算法228 
8.2.2貪心算法229 
8.2.3競爭率230 
8.2.4習題230 
8.3廣告匹配問題231 
8.3.1匹配及*美匹配231 
8.3.2極大匹配貪心算法232 
8.3.3貪心匹配算法的競爭率232 
8.3.4習題233 
8.4 adwords問題233 
8.4.1搜索廣告的歷史234 
8.4.2 adwords問題的定義234 
8.4.3 adwords問題的貪心方法235 
8.4.4 Balance算法236 
8.4.5 Balance算法競爭率的一個下界236 
8.4.6多投標者的Balance算法238 
8.4.7一般性的Balance算法239 
8.4.8 adwords問題的*後論述240 
8.4.9習題240 
8.5 adwords的實現240 
8.5.1投標和搜索查詢的匹配241 
8.5.2更複雜的匹配問題241 
8.5.3文檔和投標之間的匹配算法242 
8.6小結243 
8.7參考文獻245 

第9章**系統246 
9.1 **系統的模型246 
9.1.1效用矩陣246 
9.1.2長尾現象247 
9.1.3 **系統的應用249 
9.1.4效用矩陣的填充249 
9.2基於內容的** 249 
9.2.1項模型250 
9.2.2文檔的特徵發現250 
9.2.3基於Tag的項特徵獲取251 
9.2.4項模型的表示252 
9.2.5用戶模型253 
9.2.6基於內容的項** 254 
9.2.7分類算法254 
9.2.8習題256 
9.3協同過濾257 
9.3.1相似度計算257 
9.3.2相似度對偶性259 
9.3.3用戶聚類和項聚類261 
9.3.4習題262 
9.4降維處理262 
9.4.1 UV分解262 
9.4.2 RMSE 263 
9.4.3 UV分解的增量式計算264 
9.4.4對任一元素的優化267 
9.4.5一個完整UV分解算法的構建269 
9.5 Netflix競賽270 
9.6小結271 
9.7參考文獻272 

第10章社會網絡圖挖掘273 
10.1將社會網絡看成圖273 
10.1 .1社會網絡的概念273 
10.1.2將社會網絡看成圖274 
10.1.3各種社會網絡的例子275 
10.1.4多類型節點構成的圖276 
10.1.5習題277 
10.2社會網絡圖的聚類277 
10.2.1社會網絡圖的距離計算277 
10.2.2應用標準的聚類算法278 
10.2.3中介度279 
10.2.4 Girvan-Newman算法279 
10.2.5利用中介度來發現社區282 
10.2.6習題283 
10.3社區的直接發現283 
10.3.1團的發現284 
10.3.2完全二部圖284 
10.3.3發現完全二部子圖285 
10.3.4完全二部子圖一定存在的原因285 
10.3.5習題287 
10.4圖劃分287 
10.4.1圖劃分的好壞標準288 
10.4.2歸一化割288 
10.4.3描述圖的一些矩陣289 
10.4.4拉普拉斯矩陣的特徵值290 
10.4.5其他圖劃分方法292 
10.4.6習題292 
10.5重疊社區的發現293 
10.5.1社區的本質293 
10.5.2極大似然估計294 
10.5.3關係圖模型295 
10.5.4社區分配的離散優化296 
10.5.5避免成員隸屬關係的離散式變化297 
10.5 .6習題298 
10.6 Simrank 299 
10.6.1社會網絡上的隨機遊走者299 
10.6.2帶重啟的隨機遊走300 
10.6.3近似Simrank 302 
10.6.4近似Simrank有效的原因303 
10.6.5 Simrank在社區發現中的應用304 
10.6.6習題305 
10.7三角形計數問題. 306 
10.7.1為什麼要對三角形計數306 
10.7.2一個尋找三角形的算法307 
10.7.3三角形尋找算法的*優性308 
10.7.4基於MapReduce尋找三角形308 
10.7.5使用更少的Reduce任務310 
10.7.6習題310 
10.8圖的鄰居性質311 
10.8.1有向圖和鄰居311 
10.8.2圖的直徑312 
10.8.3傳遞閉包和可達性313 
10.8.4基於MapReduce的可達性計算314 
10.8.5半樸素求值315 
10.8.6線性傳遞閉包315 
10.8.7基於雙重遞歸的傳遞閉包316 
10.8.8智能傳遞閉包317 
10.8.9多種方法的比較319 
10.8.10基於圖歸約的傳遞閉包320 
10.8.11鄰居規模的近似計算321 
10.8.12習題323 
10.9小結324 
10.10參考文獻326 

第11章降維處理328 
11.1特徵值和特徵向量328 
11.1.1定義328 
11.1. 2特徵值與特徵向量計算329 
11.1.3基於冪迭代方法的特徵對求解331 
11.1.4特徵向量矩陣333 
11.1.5習題333 
11.2主成分分析334 
11.2.1一個示例334 
11.2.2利用特徵向量進行降維337 
11.2.3距離矩陣338 
11.2.4習題339 
11.3奇異值分解339 
11.3.1 SVD的定義339 
11.3.2 SVD解析341 
11.3.3基於SVD的降維342 
11.3.4將較低奇異值置為0後有效的原因343 
11.3 .5使用概念進行查詢處理344 
11.3.6矩陣SVD的計算345 
11.3.7習題346 
11.4 CUR分解347 
11.4.1 CUR的定義347 
11.4.2合理選擇行和列348 
11.4.3構建中間矩陣349 
11.4. 4完整的CUR分解350 
11.4.5去除重複行和列351 
11.4.6習題352 
11.5小結352 
11.6參考文獻353 

第12章大規模機器學習354 
12.1機器學習模型354 
12.1.1訓練集354 
12.1.2一些例子355 
12.1.3機器學習方法357 
12.1.4機器學習架構358 
12.1.5習題360 
12.2感知機360 
12.2.1訓練閾值為0的感知機361 
12.2.2感知機的收斂性363 
12.2 .3 Winnow算法364 
12.2.4允許閾值變化的情況365 
12.2.5多類感知機366 
12.2.6變換訓練集367 
12.2.7感知機的問題368 
12.2.8感知機的並行實現369 
12.2.9習題370 
12.3支持向量機371 
12.3.1支持向量機的機理371 
12.3.2平面歸一化372 
12.3.3尋找*優逼近分界面374 
12.3.4基於梯度下降法求解SVM 380 
12.3.6 SVM的並行實現380 
12.3.7習題381 
12.4近鄰學習381 
12.4.1近鄰計算的框架381 
12.4.2 *近鄰學習382 
12.4.3學習一維函數383 
12.4.4核回歸384 
12.4.5處理高維歐氏空間數據385 
12.4.6對非歐距離的處理386 
12.4.7習題386 
12.5決策樹387 
12.5.1使用決策樹387 
12.5.2不純度度量方法389 
12.5.3決策樹節點的設計390 
12.5.4選擇基於數值型特徵的測試390 
12.5.5選擇基於分類型特徵的測試392 
12.5.6決策樹的並行設計393 
12.5.7節點剪枝394 
12.5.8隨機森林395 
12.5.9習題396 
12.6各種學習方法的比較397 
12.7小結397 
12.8參考文獻399 

第13章神經網絡與深度學習400 
13.1神經網絡簡介400 
13.1.1神經網絡概述402 
13.1.2節點間的連接403 
13.1.3卷積神經網絡403 
13.1.4神經網絡的設計事項404 
13.1.5習題404 
13.2密集型前饋網絡405 
13.2.1基於線性代數的記法405 
13.2.2激活函數406 
13.2.3 sigmoid函數407 
13.2.4雙曲正切函數407 
13.2.5 softmax函數408 
13.2.6修正線性單元409 
13.2.7損失函數410 
13.2.8回歸損失函數410 
13.2.9分類損失函數411 
13.2.10習題412 
13.3反向傳播與梯度下降413 
13.3.1計算圖414 
13.3.2梯度、雅可比矩陣與鍊式法則415 
13.3.3反向傳播算法416 
13.3.4梯度下降的迭代計算418 
13.3.5張量419 
13.3.6習題420 
13.4卷積神經網絡420 
13.4 .1卷積層421 
13.4.2卷積與互相關423 
13.4.3池化層424 
13.4.4 CNN架構424 
13.4.5實現與訓練426 
13.4.6習題427 
13.5循環神經網絡427 
13.5.1 RNN的訓練428 
13.5.2梯度消失與爆炸430 
13.5.3長短期記憶網絡431 
13.5.4習題433 
13.6正則化433 
13.6.1範式懲罰434 
13.6.2 dropout 434 
13.6.3提前停止434 
13.6.4數據增強435 
13.7小結435 
13.8參考文獻436