大數(shù)據(jù)

前言

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


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


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


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




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





圖書(shū)封面



圖書(shū)標(biāo)簽Tags
無(wú)




評(píng)論、評(píng)分、閱讀與下載



還沒(méi)讀過(guò)(98)
勉強(qiáng)可看(712)
一般般(121)
內(nèi)容豐富(5041)
強(qiáng)力推薦(413)


 


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