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

本書由斯坦福大學“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有偏