　　Jure Leskovec 斯坦福大學計算機科學係助理教授，研究方嚮是大型社交和信息網絡的數據挖掘。他的研究成果獲得瞭很多奬項，如Microsoft Research Faculty Fellowship、Alfred P. Sloan Fellowship和Okawa Foundation Fellowship，還獲得瞭很多論文奬，同時也被《紐約時報》《華爾街日報》《華盛頓郵報》《麻省理工科技評論》《連綫》、NBC、BBC等流行的社會媒體刊載。他還創建瞭斯坦福網絡分析平颱（SNAP，http://snap.stanford.edu）。
　　
　　Anand Rajaraman 數據庫和Web技術領域專傢，創業投資基金Cambrian聯閤創始人，斯坦福大學計算機科學係助理教授。Rajaraman的職業生涯非常成功：1996年創辦Junglee公司；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 有偏

精彩書摘

　　第9章介紹推薦係統。很多Web應用中都有給用戶推薦其感興趣的數據項的功能。Netflix競賽就是一個例子，該競賽期望對用戶感興趣的電影進行預測。而Amazon希望根據顧客的購買興趣來推薦一款商品。推薦主要有兩種方法。一種方法是，我們可以將數據項通過其特徵來刻畫，比如電影中的明星，然後推薦與已知的用戶喜歡的物品具有同樣特徵的物品。另一種方法是，我們可以考察那些與當前用戶具有相似愛好的用戶，根據他們喜歡的物品來嚮當前用戶推薦（該技術通常稱為協同過濾）。　　第10章介紹社會網絡及分析算法。最典型的社會網絡的例子是Facebook的朋友關係圖，其中節點代錶人，而兩個人如果是朋友的話，他們之間就有邊相連。而像Twitter上的粉絲關注構成的有嚮圖也可以看成社會網絡。社會網絡中一個要解決的普遍問題是識彆其中的“社區”，即一個個小規模的節點集閤，但是集閤內節點之間卻有大量的邊將它們連接起來。社會網絡的其他問題也是圖的一般性問題，比如傳遞閉包或圖直徑的計算，但是在網絡規模如此巨大的情況下問題也變得十分睏難。　　第11章介紹降維技術。給定一個極大的、通常比較稀疏的矩陣。我們可以將該矩陣想象為兩類實體之間的關係錶示，比如觀眾對影片的評級關係。直觀上看，隻會存在很少量的概念，而且概念的數目會比影片或觀眾的數目少很多，這些概念可以解釋為什麼某些觀眾喜歡某些影片。我們提供瞭多個將矩陣簡化為多個矩陣的乘積的算法，簡化後的矩陣某一維要小很多。其中，一個矩陣將一類實體與這些少量的概念相關聯，另一個矩陣將概念和另一類實體相關聯。如果處理正確的話，這些小矩陣的乘積會十分接近原始矩陣。　　最後，第12章討論極大規模數據集上的機器學習算法。其中的技術包括感知機、支持嚮量機、基於梯度下降的模型求解、近鄰模型和決策樹等。　　……