大數據

前言

本書是在Anand Rajaraman和Jeff Ullman于斯坦福大學教授多年的一門季度課程的材料基礎上總結而成的。該課程名為“Web挖掘”（編號CS345A），盡管它已經成為高年級本科生能接受并感興趣的課程之一，但其原本是一門為高年級研究生設計的課程。本書內容簡單來說，本書是關于數據挖掘的。但是，本書主要關注極大規(guī)模數據的挖掘，也就是說這些數據大到無法在內存中存放。由于重點強調數據的規(guī)模，所以本書的例子大都來自Web本身或者Web上導出的數據。另外，本書從算法的角度來看待數據挖掘，即數據挖掘是將算法應用于數據，而不是使用數據來“訓練”某種類型的機器學習引擎。本書的主要內容包括：（1） 分布式文件系統以及已成功應用于大規(guī)模數據集并行算法構建的Map-Reduce工具；（2） 相似性搜索，包括最小哈希和局部敏感哈希的關鍵技術；（3） 數據流處理以及面對快速到達、須立即處理、易丟失的數據的專用處理算法；（4） 搜索引擎技術，包括谷歌的PageRank、鏈接作弊檢測及計算網頁導航度（hub）和權威度（authority）的HITS方法；（5） 頻繁項集挖掘，包括關聯規(guī)則挖掘、購物籃分析、A-Priori及其改進算法；（6） 大規(guī)模高維數據集的聚類算法；（7） Web應用中的兩個關鍵問題：廣告管理及推薦系統。先修課程盡管從編號CS345A看，本課程屬于高年級研究生課程，但是我們發(fā)現高年級本科生和低年級碩士生也能接受該課程。該課程將來可能會分配一個介于高年級研究生和低年級碩士生水平之間的編號。CS345A的先修課程包括：（1） 數據庫系統的首期課程，包括基于SQL及其他數據庫相關語言（如XQuery）的應用編程；（2） 大二的數據結構、算法及離散數學課程；（3） 大二的軟件系統、軟件工程及編程語言課程。習題本書包含大量的習題，基本每節(jié)都有對應習題。較難的習題或其中較難的部分都用驚嘆號“！”來標記，而最難的習題則標有雙驚嘆號“??！”。致謝本書封面由Scott Ullman設計。感謝Foto Afrati和Arun Marathe精心閱讀本書初稿并提出建設性的意見。感謝Leland Chen、Shrey Gupta、Xie Ke、Haewoon Kwak、Brad Penoff、Philips Kokoh Prasetyo、Mark Storus、Tim Triche Jr.及Roshan Sumbaly指出了本書中的部分錯誤。當然，剩余錯誤均由我們負責。A. R.J. D. U.加利福尼亞州帕洛阿爾托2011年6月

內容概要

《大數據：互聯網大規(guī)模數據挖掘與分布式處理》源自作者在斯坦福大學教授多年的“Web挖掘”課程材料，主要關注大數據環(huán)境下數據挖掘的實際算法。書中分析了海量數據集數據挖掘常用的算法，介紹了目前Web應用的許多重要話題。主要內容包括：分布式文件系統以及Map-Reduce工具；相似性搜索；數據流處理以及針對易丟失數據等特殊情況的專用處理算法；搜索引擎技術，如谷歌的PageRank；頻繁項集挖掘；大規(guī)模高維數據集的聚類算法；Web應用中的關鍵問題：廣告管理和推薦系統?！　?/pre>


作者簡介
Jeffrey David Ullman 斯坦福大學計算機科學系Stanford W. Ascherman教授，數據庫技術專家。他獨立或與人合作出版了15本著作，發(fā)表了170多篇技術論文。他的研究興趣包括數據庫理論、數據庫集成、數據挖掘和利用信息基礎設施進行教育。他是美國國家工程院成員，曾獲得Knuth獎、SIGMOD貢獻獎、Karlstrom杰出教育家獎和Edgar F. Codd發(fā)明獎。Anand Rajaraman　數據庫和Web技術領域權威,1創(chuàng)業(yè)投資基金Cambrian聯合創(chuàng)始人,斯坦福大學計算機科學系助理教授。Rajaraman職業(yè)生涯非常成功：1996年創(chuàng)辦Junglee公司,兩年后該公司被亞馬遜以2。5億美元收購,Rajaraman被聘為亞馬遜技術總監(jiān),推動亞馬遜從一個零售商轉型為零售平臺；2000年與人合創(chuàng)Cambrian,孵化出幾個后來被谷歌收購的公司；2005年創(chuàng)辦Kosmix公司并任CEO,該公司2011年被沃爾瑪集團收購。Rajaraman生于印度,在斯坦福大學獲得計算機科學碩士和博士學位。求學期間與人合著的一篇論文榮列近20年來被引用次數最多的論文之一。


書籍目錄
第1章數據挖掘基本概念 1.1數據挖掘的定義 1.1.1統計建模 1.1.2機器學習 1.1.3建模的計算方法 1.1.4數據匯總 1.1.5特征抽取 1.2數據挖掘的統計限制 1.2.1整體情報預警 1.2.2邦弗朗尼原理 1.2.3邦弗朗尼原理的一個例子 1.2.4習題 1.3相關知識 1.3.1詞語在文檔中的重要性 1.3.2哈希函數 1.3.3索引 1,3.4二級存儲器 1.3.5自然對數的底e 1.3.6冪定律 1.3.7習題 1.4本書概要 1.5小結 1.6參考文獻 第2章大規(guī)模文件系統及Map－RedUCe 2.1分布式文件系統 2.1.1計算節(jié)點的物理結構 2.1.2大規(guī)模文件系統的結構 2.2Map－Reduce 2.2.1Map任務 2.2.2分組和聚合 2.2.3Reduce任務 2.2.4組合器 2.2.5Map－Reduce的執(zhí)行細節(jié) 2.2.6節(jié)點失效的處理 2.3使用Map－Reduce的算法 2.3.1基于Map－Reduce的矩陣－向量乘法實現 2.3.2向量v無法放入內存時的處理 2.3.3關系代數運算 2.3.4基于Map－Reduce的選擇運算 2.3.5基于Map－Reduce的投影運算 2.3.6基于Map－Reduce的并、交和差運算 2.3.7基于Map－Reduce的自然連接運算 2.3.8－般性的連接算法 2.3.9基于Map－Reduce的分組和聚合運算 2.3.10矩陣乘法 2.3.11基于單步Map－Reduce的矩陣乘法 2.3.12習題 2.4Map－Reduce的擴展 2.4.1工作流系統 2.4.2Map－Reduce的遞歸擴展版本 2.4.3Pregel系統 2.4.4習題 2.5集群計算算法的效率問題 2,5.1集群計算的通信開銷模型 2.5.2實耗通信開銷 2.5.3多路連接 2.5.4習題 2.6小結 2.7參考文獻 第3章相似項發(fā)現 3.1近鄰搜索的應用 3.1.1集合的Jaccard相似度 3.1.2文檔的相似度 3.1.3協同過濾——一個集合相似問題 3.1.4習題 3.2文檔的shingling 3.2.1k－Shingle 3.2.2shingle大小的選擇 3.2.3對shingle進行哈希 3.2.4基于詞的shingle 3.2.5習題 3.3保持相似度的集合摘要表示 3.3.1集合的矩陣表示 3.3.2最小哈希 3.3.3最小哈希及Jaccard相似度 3.3.4最小哈希簽名 3.3.5最小哈希簽名的計算 3.3.6習題 3.4文檔的局部敏感哈希算法 3.4.1面向最小哈希簽名的LSH 3.4.2行條化策略的分析 3.4.3上述技術的綜合 3.4.4習題 3.5距離測度 3.5.1距離測度的定義 3.5.2歐氏距離 3.5.3Jaccard距離 3.5.4余弦距離 3.5.5編輯距離 3.5.6海明距離 3.5.7習題 3.6局部敏感函數理論 3.6.1局部敏感函數 3.6.2面向Jaccard距離的局部敏感函數族 3.6.3局部敏感函數族的放大處理 3.6.4習題 3.7面向其他距離測度的LSH函數族 3.7.1面向海明距離的LSH函數族 3.7.2隨機超平面和余弦距離 3.7.3梗概 3.7.4面向歐氏距離的LSH函數族 3.7.5面向歐氏空間的更多LSH函數族 3.7.6習題 3.8LSH函數的應用 3.8.1實體關聯 3.8.2一個實體關聯的例子 3.8.3記錄匹配的驗證 3.8.4指紋匹配 3.8.5適用于指紋匹配的LSH函數族 3.8.6相似新聞報道檢測 3.8.7習題 3.9面向高相似度的方法 3.9.1相等項發(fā)現 3,9.2集合的字符串表示方法 3.9.3基于長度的過濾～ 3.9.4前綴索引 3.9.5位置信息的使用 3.9.6使用位置和長度信息的索引 3,9.7習題 3.10小結 3.11參考文獻 第4章數據流挖掘 4.1流數據模型 4.1.1一個數據流管理系統 4.1.2流數據源的例子 4.1.3流查詢 4.1.4流處理中的若干問題 4.2流當中的數據抽樣 4.2.1一個富于啟發(fā)性的例子 4.2.2代表性樣本的獲取 4.2.3一般的抽樣問題 4.2.4樣本規(guī)模的變化 4.2.5習題 4.3流過濾 4.3.1一個例子 4.3,2布隆過濾器 4.3.3布隆過濾方法的分析 4.3.4習題 4.4流中獨立元素的數目統計 4.4.1獨立元素計數問題 4,4.2FM算法 4.4.3組合估計 4.4.4空間需求 4.4.5習題 4.5矩估計 4.5.1矩定義 4.5.2二階矩估計的AMS算法 4.5.3AMS算法有效的原因 4.5.4更高階矩的估計 4.5.5無限流的處理 4.5.6習題 4.6窗口內的計數問題 4.6.1精確計數的開銷 4.6.2DGIM算法 4.6.3DGIM算法的存儲需求 4.6.4DGIM算法中的查詢應答 4.6.5DGIM條件的保持 4.6.6降低錯誤率 4.6.7窗口內計數問題的擴展 4.6.8習題 4.7衰減窗口 4.7.1最常見元素問題 4.7.2衰減窗口的定義 4.7.3最流行元素的發(fā)現 4.8小結 4.9參考文獻 第5章鏈接分析 5.1PageRank 5.1.1早期的搜索引擎及詞項作弊 5.1.2PageRank的定義 5.1.3Web結構 5.1.4避免終止點 5.1.5采集器陷阱及“抽稅”法 5.1.6PageRank在搜索引擎中的使用 5.1.7習題 5.2PageRank的快速計算 5.2.1轉移矩陣的表示 5.2.2基于Map－Reduce的PageRank迭代計算 5.2.3結果向量合并時的組合器使用 5.2.4轉移矩陣中塊的表示 5.2.5其他高效的PageRank迭代方法 5.2.6習題 5.3面向主題的PageRank 5.3.1動機 5.3.2有偏的隨機游走模型 5.3.3面向主題的PageRank的使用 5.3.4基于詞匯的主題推斷 5.3.5習題 5.4鏈接作弊 5.4.1垃圾農場的架構 5.4.2垃圾農場的分析 5.4.3與鏈接作弊的斗爭 5.4.4TrustRank 5.4.5垃圾質量 5.4.6習題 5.5導航頁和權威頁 5.5.1HITS的直觀意義 5.5.2導航度和權威度的形式化 5.5.3習題 5.6小結 5.7參考文獻 第6章頻繁項集 6.1購物籃模型 6.1.1頻繁項集的定義 6.1.2頻繁項集的應用 6.1.3關聯規(guī)則 6.1.4高可信度關聯規(guī)則的發(fā)現 6.1.5習題 6.2購物籃及A－Priori算法 6.2.1購物籃數據的表示 6.2.2項集計數中的內存使用 6.2.3項集的單調性 6.2.4二元組計數 6.2.5A－Priori算法 6.2.6所有頻繁項集上的A－Priori算法 6.2.7習題 6.3更大數據集在內存中的處理 6.3.1PCY算法 6.3.2多階段算法 6.3.3多哈希算法 6.3.4習題 6.4有限掃描算法 6.4.1簡單的隨機化算法 6.4.2抽樣算法中的錯誤規(guī)避 6.4.3SON算法 6.4.4SON算法和Map－Reduce 6.4.5Toivonen算法 6.4.6Toivonen算法的有效性分析 6.4.7習題 6.5流中的頻繁項計數 6.5.1流的抽樣方法 6.5.2衰減窗口中的頻繁項集 6.5.3混合方法 6.5.4習題 6.6小結 6.7參考文獻 第7章聚類 7.1聚類技術介紹 7.1.1點、空間和距離 7.1.2聚類策略 7.1.3維數災難 7.1.4習題 7.2層次聚類 7.2.1歐氏空間下的層次聚類 7.2.2層次聚類算法的效率 7.2.3控制層次聚類的其他規(guī)則 7.2.4非歐空間下的層次聚類 7.2.5習題 7.3k－均值算法 7.3.1k－均值算法基本知識 7.3.2k－均值算法的簇初始化 7.3.3選擇七的正確值 7.3.4BFR算法 7.3.5BFR算法中的數據處理 7.3.6習題 7.4CURE算法 7.4.1CURE算法的初始化 7.4.2CURE算法的完成 7.4.3習題 7.5非歐空間下的聚類 7.5.1GRGPF算法中的簇表示 7.5.2簇表示樹的初始化 7.5.3GRGPF算法中的點加入 7.5.4簇的分裂及合并 7.5.5習題 7.6流聚類及并行化 7.6.1流計算模型 7.6.2－個流聚類算法 7.6.3桶的初始化 7.6.4桶合并 7.6.5查詢應答 7.6.6并行環(huán)境下的聚類 7.6.7習題 7.7小結 7.8參考文獻 第8章Web廣告 8.1在線廣告相關問題 8.1.1廣告機會 8.1.2直投廣告 8.1.3展示廣告的相關問題 8.2在線算法 8.2.1在線和離線算法 8.2.2貪心算法 8.2.3競爭率 8.2.4習題 8.3廣告匹配問題 8.3.1匹配及完美匹配 8.3.2最大匹配貪心算法 8.3.3貪心匹配算法的競爭率 8.3.4習題 8.4Adwords問題 8.4.1搜索廣告的歷史 8.4.2Adwords問題的定義 8.4.3Adwords問題的貪心方法 8.4.4Balance算法 8.4.5Balance算法競爭率的一個下界 8.4.6多投標者的Balance算法 8.4.7－般性的Balance算法 8.4.8Adwords問題的最后論述 8.4.9習題 8.5Adwords的實現 8.5.1投標和搜索查詢的匹配 8.5.2更復雜的匹配問題 8.5.3文檔和投標之間的匹配算法 8.6小結 8.7參考文獻 第9章推薦系統 9.1一個推薦系統的模型 9.1.1效用矩陣 9.1.2長尾現象 9.1.3推薦系統的應用 9.1.4效用矩陣的填充 9.2基于內容的推薦 9.2.1項模型 9.2.2文檔的特征發(fā)現 9.2.3基于Tag的項特征獲取 9.2.4項模型的表示 9.2.5用戶模型 9.2.6基于內容的項推薦 9.2.7分類算法 9.2.8習題 9.3協同過濾 9.3.1相似度計算 9.3.2相似度對偶性 9.3.3用戶聚類和項聚類 9.3.4習題 9.4降維處理 9.4.1UrV分解 9.4.2RMSE 9.4.3UV分解的增量式計算 9.4.4對任一元素的優(yōu)化 9.4.5一個完整UV分解算法的構建 9.4.6習題 9.5NetFlix競賽 9.6小結 9.7參考文獻 索引


章節(jié)摘錄
版權頁：   插圖：   然而，當項對的數目太多而無法在內存中對所有的項對計數時，上述簡單的方法就不再可行。A-Priori算法被設計成能夠減少必須計數的項對數目，當然其代價是要對數據做兩遍而不是一遍掃描。 1.A-Priori算法的第一遍掃描 第一遍掃描中，我們要建立兩張表。如有必要，第一張表要將項的名稱轉換為1到n之間的整數（參考6.2.2節(jié)中的描述）。另一張表則是一個計數數組，第i個數組元素是上述第i個項的出現次 數。這些所有項的計數值的初始值都是0。 在讀取購物籃時，我們檢查購物籃中的每個項并將其名稱轉換為一個整數。然后，將該整數作為計數數組的下標找到對應的數組元素，最后，對該數組元素加1。 2.A-Priori算法兩遍掃描之間的處理 第一遍掃描之后，我們檢查所有項的計數值，以確定哪些項構成單元素頻繁項集。我們可能會看到，大部分單元素項集都是不頻繁的。這一點可能會有點出人意料。但是，前面提到，我們常常將閾值s設置得足夠高以保證頻繁集不會太多。一個典型的s值為所有購物籃數目的1%。想象一下自己到超市購物的情況，我們購買某些商品的次數肯定會超過總次數的1%，這些商品可能是牛奶、面包、可口可樂或百事可樂什么的。我們甚至相信，雖然我們不購買尿布，但是會有1%的顧客會購買尿布。然而，貨架上的大部分商品的顧客購買比例肯定都不會超過1%，比如奶油凱撒沙拉汁。 對于A-Priori算法的第二遍掃描，我們會只給頻繁項重新編號，編號范圍是1到m。此時的表格是一個下標為1到n的數組，如果第i項不頻繁，則對應的第IAI數組元素為0，否則為1到m之間的一個唯一整數。我們應將此表格稱為頻繁項表格。 3.A-Priori算法的第二遍掃描 在第二遍掃描中，我們對兩個頻繁項組成的所有項對計數。從6.2.3節(jié)的討論可知，除非一個項對中的兩個項都頻繁，否則這個項對也不可能是頻繁的。因此，在掃描過程中我們不可能會丟掉任何頻繁項對。如果采用前面提到的三角矩陣方法來計數的話，則第二遍掃描所需的空間是2n2而不是2n2。需要注意的是，如果要使用一個大小正確的三角矩陣，那么就一定要只對頻繁項進行重新編號處理。第一遍和第二遍掃描中所使用的完整內存結構集合如圖6-3所示。 需要注意的另外一點是，上述非頻繁項去除的好處會被放大：如果只有一半的項是頻繁項，那么在計數過程中僅需要原來空間的1/4。類似地，如果使用三元組方式，我們只需要對至少出現在一個購物籃中的兩個頻繁項組成的項對進行計數。 第二遍掃描的技術細節(jié)如下： （1）對每個購物籃，在頻繁項集表中檢查哪些項是頻繁的； （2）通過一個雙重循環(huán)生成所有的頻繁項對； （3）對每個頻繁項對，在存儲計數值的數據結構中相應的計數值上加1； 最后，在第二遍掃描結束時，檢查計數值結構以確定哪些項對是頻繁項對。




編輯推薦
《大數據?互聯網大規(guī)模數據挖掘與分布式處理》由拉賈拉曼Anand Rajarama、厄爾曼Jeffrey David Ullman所著，主要關注極大規(guī)模數據的挖掘。由于重點強調數據的規(guī)模，所以《大數據?互聯網大規(guī)模數據挖掘與分布式處理》的例子大都來自web本身或者web上導出的數據。另外，《大數據?互聯網大規(guī)模數據挖掘與分布式處理》從算法的角度來看待數據挖掘，即數據挖掘是將算法應用于數據，而不是使用數據來“訓練”某種類型的機器學習引擎。





圖書封面



圖書標簽Tags
無




評論、評分、閱讀與下載



還沒讀過(98)
勉強可看(712)
一般般(121)
內容豐富(5041)
強力推薦(413)


 


    大數據 PDF格式下載