大數(shù)據(jù)

前言

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

內(nèi)容概要

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


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


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


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




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





圖書封面



圖書標簽Tags
無




評論、評分、閱讀與下載



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


 


    大數(shù)據(jù) PDF格式下載