文稿成果講稿

SuqiDirectedbyNanjingUniversityMaySubmittedinpartialfulfilmentoftherequirementsforthedegreeofMasterinComputerTheresultstestedonseveraldatasetaindicatebothparallizedalgorithmsnotonlyguar-anteedhighaccuracybutalsoimprovedtheminingefficiency. ····································································緒論···························································11················································2 3 ·············································6的問(wèn)題和··············································7本文主要工作和安排············································89Hadoop的及發(fā)展過(guò)程·······································9Hadoop的分布式文件系統(tǒng)HDFS································· HDFS的體系結(jié)構(gòu)與工作機(jī)制···························· ·················引言···········································································································U-Apriori·················································· PU-Apriori算法總體框架圖······························· 實(shí)驗(yàn)環(huán)境················································評(píng)判標(biāo)準(zhǔn)················································不確定數(shù)據(jù)下精確的概率頻繁項(xiàng)集并行挖掘算法·················引言··························································································· ···································· ···········································不確定數(shù)據(jù)下近似的概率頻繁項(xiàng)集并行挖掘算法·················引言···························································常用的概率估計(jì)方法············································ ··························· ········································································· 總結(jié)與展望·····················································參考文獻(xiàn)·······························································簡(jiǎn)歷與科研成果····························································································································· 不確定數(shù)據(jù)集 表3.1的可能世界 · 數(shù)據(jù)集的特征 不確定數(shù)據(jù)集 不確定數(shù)據(jù)集 數(shù)據(jù)集的特征 各個(gè)符號(hào)含義 數(shù)據(jù)集的參數(shù)信息 3 ]項(xiàng)集D的支持度概率分布 項(xiàng)集D的頻繁概率 PAAPFI和PAPFI算法的擴(kuò)展性 PAAPFI和PAPFI算法的加速比 隨著大數(shù)據(jù)(BigDt)時(shí)代的來(lái)臨，全球的數(shù)總量呈增長(zhǎng)。最提出大據(jù)代的球名詢公麥錫說(shuō)“數(shù)，經(jīng)滲到一個(gè)行eseigend也曾經(jīng):已然據(jù)時(shí)，傳統(tǒng)的數(shù)據(jù)挖掘算法往往人們?cè)跁r(shí)間和空間上的要求，甚至有些算法根本就無(wú)法處理海量的數(shù)據(jù)。MapReduc編程模型和Hdoop近年來(lái)，不確定性數(shù)據(jù)廣泛出現(xiàn)在諸多應(yīng)用領(lǐng)域，例如傳感器網(wǎng)絡(luò)、RFID應(yīng)用、數(shù)據(jù)集成、LBS(LocaionBsedSerics、b應(yīng)用等，其特點(diǎn)是每個(gè)數(shù)據(jù)對(duì)象不是單個(gè)的數(shù)據(jù)點(diǎn)，而是按照概率在多個(gè)數(shù)據(jù)點(diǎn)上出現(xiàn)[。事實(shí)上，基于不確定數(shù)據(jù)的數(shù)據(jù)挖掘目前已經(jīng)吸引了很多研究者的注意[。比如：在[32][][]中，樸素貝葉斯和決策樹(shù)的分類方法也在不確定數(shù)據(jù)庫(kù)中得到應(yīng)用。由于數(shù)據(jù)的不確定性對(duì)挖掘結(jié)果產(chǎn)生了重要的影響，傳統(tǒng)的針對(duì)確定數(shù)據(jù)的挖掘算法已經(jīng)不能滿足現(xiàn)實(shí)應(yīng)用的迫切需求求。而在針對(duì)不確定數(shù)據(jù)挖掘的眾多算法中，頻繁項(xiàng)集的挖掘是重點(diǎn)研究的問(wèn)在時(shí)間和空間上往往人們的要求，甚至往往無(wú)法處理。因此，并行化是提高基于不確定性數(shù)據(jù)的頻繁項(xiàng)集挖掘算法的有效途徑。隨著計(jì)算機(jī)以及網(wǎng)絡(luò)的普及，數(shù)據(jù)量呈式增長(zhǎng)，相應(yīng)的數(shù)據(jù)設(shè)備也計(jì)算機(jī)日志、車載GPS、零售數(shù)據(jù)等等。那么，如何從海量的數(shù)據(jù)中獲得有數(shù)據(jù)的[21][12][26]等等，不確定數(shù)據(jù)的挖掘成為了數(shù)據(jù)挖掘領(lǐng)域的一新的熱門研究話題。不確定數(shù)據(jù)挖掘主要包括聚類、分類、關(guān)聯(lián)規(guī)則的挖掘、孤立點(diǎn)檢測(cè)等方面，其中頻繁項(xiàng)集的挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)基礎(chǔ)。因此，不確定頻繁項(xiàng)集的挖掘成為了研究的熱點(diǎn)[48][10][11][18][17][34][45]D它包含了n條事務(wù)(trasatio),t1,t2,t3,...,tti包含了一系列的項(xiàng)(itm，而對(duì)于ti中的每一個(gè)項(xiàng)都含有一個(gè)非零的概率Pi()它表示項(xiàng)可能出現(xiàn)在ti中的概率。因此存在著兩種可能。一種是出現(xiàn)在ti中，一種是不出現(xiàn)在ti我們稱這兩種可能性為兩種可能世界(Possileorld，分別為1和W。我們并不知道哪個(gè)世界才是真實(shí)的，但是從數(shù)據(jù)集中我們知道每個(gè)世界成為真實(shí)世界的概率。假設(shè)，我們把世界i成為真實(shí)世界的概率命名為P(i，那么P(1)=Pti(),而P(2)=1?Pi(ti中出現(xiàn)的其他項(xiàng)。再假設(shè)，y也出現(xiàn)在ti中，概率為Pti(y),且與是相互獨(dú)立的。此時(shí)，我們有四個(gè)可能的世界，和y同時(shí)出現(xiàn)在ti中的概率是Pi(Pi(y。類似的，我們AB以及兩條事務(wù)。那么我們可以得到1個(gè)可能的世界，如圖11X的支持度為X在確定型數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)，出現(xiàn)的次數(shù)即為XX是否一定會(huì)出ABAABABABAB ABABABABABABAABABABAB ABABABABAB在確定性數(shù)據(jù)中，頻繁項(xiàng)集的定義是非常明確的，即：當(dāng)一個(gè)項(xiàng)集在數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)大于等于用戶指定的閾值的時(shí)候，它就是頻繁項(xiàng)集6][725][52]。然而，在不確定數(shù)據(jù)中關(guān)于頻繁項(xiàng)集有兩種不同的定義：第一種是基于期望支持度(EpctdSort的[4][，另一種是基于概率的[。這兩種定義都是將項(xiàng)集的支持度看做是離散的隨量，然而在使用隨量來(lái)定義頻繁項(xiàng)集的時(shí)候卻有所不同?；谄谕С侄鹊念l繁項(xiàng)集，是通過(guò)它的期望支持度來(lái)衡量它是否是頻繁的項(xiàng)集?；谶@個(gè)定義，只且僅當(dāng)一個(gè)項(xiàng)集的期望支持度大于等于用戶預(yù)定義的最小期望支持度minsu)的時(shí)候，我們才認(rèn)為該項(xiàng)集是不確定數(shù)據(jù)中的頻繁項(xiàng)集[][1][1][3][47[][][][],是通過(guò)一個(gè)項(xiàng)集在超過(guò)minsupp條事物中出現(xiàn)的概率來(lái)衡量它松分布的隨量，即一個(gè)項(xiàng)集的支持度與隨量的期望是等價(jià)的[51]。因此，計(jì)算一個(gè)項(xiàng)集的頻繁概率等價(jià)于計(jì)算隨量的累積分布函數(shù)。目前大量已存在[0。根據(jù)yaun[],而且泊松二項(xiàng)分布有一個(gè)顯著的特性：它的期望和方差是相同的，即計(jì)算期望和方差的復(fù)雜度是相同的。因此，在不確定數(shù)據(jù)中當(dāng)數(shù)據(jù)量足夠大的時(shí)候，只要我們已知這個(gè)項(xiàng)集的支持度的期望和方差，我們就可以直接計(jì)算出這個(gè)項(xiàng)集是否是頻繁的概率[1。換句話說(shuō)，只有當(dāng)?shù)谝环N定義也同樣考慮了支持度的方差的時(shí)候，[。基于期望支持度的頻繁項(xiàng)集挖掘算法主要是以通過(guò)求得項(xiàng)集的期望支持度的O(N),N是數(shù)據(jù)庫(kù)中事務(wù)的個(gè)數(shù)。精確的概率頻繁項(xiàng)集挖掘算法主要是通過(guò)求得項(xiàng)集的頻繁概率來(lái)確定它是否O(NlogN。近似的概率頻繁項(xiàng)集挖掘算法主要是通過(guò)求得項(xiàng)集的近似頻繁的概率來(lái)確定正態(tài)分布來(lái)計(jì)算概率頻繁項(xiàng)集。通常單機(jī)模式下求一個(gè)項(xiàng)集的頻繁概率為O(N?；谄谕С侄鹊念l繁項(xiàng)集挖掘算法，包括三個(gè)最具代表性的方法，他們是：U-Apriori、UH-Mine、UFP-Growth，下面將分別對(duì)他們進(jìn)行介紹。U-Apriori算法是Chui在2007年不確定頻繁項(xiàng)集挖掘算法，它是基于期望支些候選集是否是頻繁的。它采用自底向上的產(chǎn)生―檢驗(yàn)的模式來(lái)搜索所有的頻戶指定的最小期望支持度得到長(zhǎng)度為1的頻繁項(xiàng)集L1。然后從L1中產(chǎn)生長(zhǎng)度為2的候選集C2,掃描數(shù)據(jù)庫(kù)通過(guò)候選集計(jì)算長(zhǎng)度為2的頻繁項(xiàng)集，結(jié)果保存在L2Ck為空(k?1)。迭代結(jié)束，即求出所有U-Min算法[]采用的是分而治之以及深度優(yōu)先搜索的策略這個(gè)算法同樣是對(duì)傳統(tǒng)數(shù)據(jù)模式下的-Min算法[]的一個(gè)擴(kuò)展，它尤其適應(yīng)于稀疏的數(shù)據(jù)庫(kù)中頻繁項(xiàng)集的挖掘。-Min算法的基本流程是這樣的：首先瀏覽數(shù)據(jù)庫(kù)，找到數(shù)據(jù)庫(kù)中所有的頻繁一項(xiàng)集，并且建立一個(gè)包含所有頻繁一項(xiàng)集的頭表。而頭表中的每個(gè)項(xiàng)包含有三個(gè)元素：一個(gè)用來(lái)項(xiàng)它本身的；一個(gè)用來(lái)它的支持度的期望值；最后一個(gè)是指針域，用來(lái)指針的指向。建立完頭表之后，數(shù)據(jù)庫(kù)中所有的事務(wù)都會(huì)入到UH-Struct的這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)中。在UH-Struct中的每個(gè)項(xiàng)也占有三個(gè)空間，分別是：一個(gè)用來(lái)項(xiàng)本身的，一個(gè)用來(lái)這個(gè)項(xiàng)在事務(wù)中出現(xiàn)的概率，最后一個(gè)同樣是個(gè)指針域。growthF?list(frequentlist),然后根據(jù)F?list建立一顆UFP-tree來(lái)這個(gè)不確定數(shù)據(jù)庫(kù)。根據(jù)UFP-tree，算法遞歸地建立子F?list以及條 所以一個(gè)項(xiàng)集的支持度可以用分布或者正態(tài)分布來(lái)有效的估計(jì)。而且，如2005年以前，人們都能預(yù)期可以一直提升處理器主頻。然而由于VLSI集成度不可能提高、處理器的指令級(jí)并行度提升接近極限、處理器速度和存儲(chǔ)器速度差異越來(lái)越大以及功耗和散熱大幅增加已經(jīng)超過(guò)了的承受能力等共享內(nèi)存變量的方法。采用多線程共享變量的方式實(shí)現(xiàn)并行程序設(shè)計(jì)，但會(huì)引起數(shù)據(jù)不一致，導(dǎo)致資源和數(shù)據(jù)，需要同步機(jī)制。tr和M。 I和MapReduce作為兩個(gè)主要的方法，有著各自的優(yōu)缺點(diǎn)以及各自的適用范圍。但是在應(yīng)用的廣泛程度以及實(shí)現(xiàn)的難度上，MapReduc有著相當(dāng)?shù)膬?yōu)勢(shì)。通過(guò)簡(jiǎn)單的Mp和Reduce的函數(shù)，不需要關(guān)注底層的實(shí)現(xiàn)，算法可以很輕易的被并行化實(shí)現(xiàn)。而底層的Hdoop和F，為MapReduc提供了相應(yīng)的計(jì)算功能和功能，因而即使是在實(shí)際的應(yīng)用中，MapReduce也可以很好應(yīng)用于算法的實(shí)現(xiàn)。通過(guò)MapReduc進(jìn)行算法的并行化是目前比較熱門的方式之一，h的Mhou，就是其中比較出色的一個(gè)例子。hout作為ph旗下的一個(gè)開(kāi)源項(xiàng)目，其主要是以一個(gè)工具箱的形式，去并行化的實(shí)現(xiàn)機(jī)器學(xué)習(xí)的算法。所有的源代就是開(kāi)源，不僅僅項(xiàng)目組部，任何人可以者是提交并行化實(shí)現(xiàn)的代碼。通過(guò)pReduce的方法，大量的現(xiàn)有機(jī)器學(xué)習(xí)算法被實(shí)現(xiàn)，hout目前已經(jīng)更新到0，并行分類算法。已實(shí)現(xiàn)的包括：、支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)、隨即森 盡管這諸多的，我們依然相信并行化是解決海量數(shù)據(jù)下不確定頻繁項(xiàng)集的挖掘的重要。原因如下：首先，基于riori算法的不確定頻繁項(xiàng)集于MapReduce的機(jī)制，riori類算法不需要對(duì)數(shù)據(jù)集進(jìn)行大量的掃描，這使得掃描數(shù)據(jù)庫(kù)的時(shí)間大大的縮短；最后基于riori類算法本身的可并行性，我們認(rèn)為海量數(shù)據(jù)下的不確定頻繁項(xiàng)集的挖掘是適合并行化的。本文主要討論了頻繁項(xiàng)集挖掘的算法，對(duì)其并行化實(shí)現(xiàn)進(jìn)行了相關(guān)的探索和研究。主要包括以下三個(gè)方面的算法：基于期望支持度的不確定頻繁項(xiàng)集挖掘算法、精確的概率頻繁項(xiàng)集挖掘算法、近似的概率頻繁項(xiàng)集挖掘算法。其中基于期望支持度的并行化的主要是對(duì)-rri算法進(jìn)行了并行化，該算法在加速比各方面均表現(xiàn)良好。精確的概率頻繁項(xiàng)集挖掘算法，由于其要計(jì)算每個(gè)項(xiàng)集的頻繁概率，故本文在采用rri算法進(jìn)行挖掘的基礎(chǔ)上，對(duì)于進(jìn)行了稍稍的改進(jìn)，引進(jìn)了產(chǎn)生式來(lái)求項(xiàng)集頻繁的概率。最后，在近似的頻繁項(xiàng)集挖掘算法中，本文主要采用了正態(tài)分布來(lái)估計(jì)概率頻繁項(xiàng)集，算法上采用的仍然是priri算法來(lái)進(jìn)行挖掘。這種方法在取得了較好加速比的情況下，也取得了第六章進(jìn)行對(duì)本文算法的總結(jié)以及展望。第二章Hadoop平計(jì)算技術(shù)已經(jīng)深刻地改變了我們的工作、學(xué)習(xí)和生活。其中，分布式云計(jì)云計(jì)算的計(jì)劃吸引了很多高校、以及科研機(jī)構(gòu)的關(guān)注；在產(chǎn)業(yè)界，各個(gè)大型的T公司也在加大投入的資源和精力；而各種的學(xué)術(shù)會(huì)議和期也都加入了臺(tái)，像：mzon公司的EC2和S，谷歌公司Ein，微軟的zur，BM的虛擬資源整合池，ah軟件開(kāi)源組織的Hdoop等。其中，Hdoop作為h基于會(huì)開(kāi)發(fā)的開(kāi)源項(xiàng)目，為開(kāi)發(fā)者提供了一個(gè)分布式系統(tǒng)基礎(chǔ)架構(gòu)。用戶在不了解分布式底層細(xì)節(jié)的情況下，開(kāi)發(fā)分布式程序。很多大型的互聯(lián)網(wǎng)公司，都用Hdoop來(lái)進(jìn)行數(shù)據(jù)處理和數(shù)據(jù)挖掘。特別是在數(shù)據(jù)挖掘領(lǐng)域，Hdoop的分布式文件系統(tǒng)解決了海量數(shù)據(jù)的問(wèn)題，同時(shí)它的MapReduce計(jì)算框架能夠充分利用集群的來(lái)進(jìn)行高速的運(yùn)算和，最終完成數(shù)據(jù)挖掘任務(wù)，這大大提高了它的計(jì)算能力。本章抓喲介紹Hdoop平臺(tái)的及發(fā)展過(guò)程，接著介紹了F，最后介紹了MapReduc大數(shù)據(jù)的今天，我們正在被數(shù)據(jù)所包圍。人們上載、用拍照、發(fā)短訊個(gè)朋友、更新人人網(wǎng)或者、網(wǎng)上留言、搜索資料等等都使機(jī)器產(chǎn)生和保留了越來(lái)越多的數(shù)據(jù)。這些數(shù)據(jù)呈指數(shù)級(jí)的增長(zhǎng)，給市場(chǎng)上占主導(dǎo)地位的大型的IT公司，比如：、Yahoo！、Amazon、微軟、 等提出了。他們需要遍歷TB甚至PB級(jí)的數(shù)據(jù)來(lái)發(fā)現(xiàn)哪些更受歡迎、哪些書(shū)有需求，那種更加吸引人。已有的工具正在變得越來(lái)越無(wú)力處理這樣龐大的數(shù)據(jù)。Hdoo是開(kāi)源組織ah下的一個(gè)分布式開(kāi)源軟件項(xiàng)目，于另外兩個(gè)開(kāi)源項(xiàng)目——aheLucene和Nutc。Lucen是一個(gè)用開(kāi)發(fā)的開(kāi)源高性能全文檢索引擎工具包，提供了一個(gè)簡(jiǎn)單卻強(qiáng)大的應(yīng)用程式接口，能夠做全文索引和搜尋。；Nutch開(kāi)始于200年，它是一個(gè)可以運(yùn)行網(wǎng)頁(yè)的爬去工具和搜索引擎的系統(tǒng)。但是很快，開(kāi)發(fā)者發(fā)現(xiàn)這一架構(gòu)的可擴(kuò)展性不高，不能解決數(shù)十億網(wǎng)頁(yè)的搜索問(wèn)題。2003年，公司了一篇描述谷歌文件系統(tǒng)（GF）架構(gòu)的文章[，這一架構(gòu)可以幫助他們解決網(wǎng)頁(yè)爬取和索引過(guò)程中產(chǎn)生的超大文件的需求。不盡如此，GF的這一架構(gòu)還能夠節(jié)省系統(tǒng)管理所花的大量時(shí)間。200年，谷歌又向全世界介紹他們的MapReduce系統(tǒng)[2。基于的兩篇 ，Nutch相繼開(kāi)發(fā)了自己的分布式文件系統(tǒng)NDFS(uhDsritedFilestm)和MapReduc系統(tǒng)。200年月，Nutc的F和pRduc被移出，形成Lucene一個(gè)子項(xiàng)目，稱為Hdoo。大同一時(shí)間，aheLucen創(chuàng)始人Dougutting加入o！門一團(tuán)資將Hdoop打造成一個(gè)能夠處理海量的e年，Hdoop成功晉升為ph的頂級(jí)項(xiàng)目。目前為止，它已被多家公司使用，如：o， ，淘寶，，中國(guó)移動(dòng)等。Hdoo主要包括兩個(gè)部分：分布式文件系統(tǒng)FS（由FS改名而來(lái)）和MapReduc編程框架。隨著HadoopHs為一種分布式數(shù)據(jù)庫(kù)，使用FS作為底層，同時(shí)是谷歌Bgle的一個(gè)開(kāi)源實(shí)現(xiàn)；i，一種分布式數(shù)據(jù)倉(cāng)庫(kù)，可以用于管理FS中的數(shù)據(jù)；i，一種為了讓研究員和工程師能更簡(jiǎn)單地挖掘大規(guī)模數(shù)據(jù)集而發(fā)明的工具）近年來(lái)，dop作為一種典型的云計(jì)算平臺(tái)，正在得到越來(lái)越多人的關(guān)注，并被廣泛應(yīng)用于學(xué)術(shù)界和工業(yè)界。除了因?yàn)樗且粋€(gè)開(kāi)源項(xiàng)目之外，它還]：可擴(kuò)展。同時(shí)體現(xiàn)在的可擴(kuò)展和計(jì)算的可擴(kuò)展兩方面，它們都可靠。HDFS的備份恢復(fù)機(jī)制及MapReduce的任務(wù)機(jī)制保證了分布式高效。分布式文件系統(tǒng)的高效數(shù)據(jù)交互實(shí)現(xiàn)及MapReduce結(jié)合LocalDa-tem。它主要借鑒了谷歌的GFS（FileSystem）系統(tǒng)而設(shè)計(jì)，可以部署在程模型很好的結(jié)合，從而為應(yīng)用程序提供高吞吐量的數(shù)據(jù)。本節(jié)首先介紹的文件過(guò)程和寫文件過(guò)程的剖析，來(lái)進(jìn)一步理解HDFS的工作機(jī)制，最后硬件錯(cuò)誤是常態(tài)而不是異常。HFS被設(shè)計(jì)成能夠運(yùn)行在成千上萬(wàn)廉價(jià)的硬是S流式數(shù)據(jù)。運(yùn)行在HDFS上的應(yīng)用主要是以流式讀為主，做批量處理；與關(guān)注數(shù)據(jù)的低延遲問(wèn)題相比，更注重?cái)?shù)據(jù)的高吞吐量。大規(guī)模數(shù)據(jù)集。FS以支持大數(shù)據(jù)集合為目標(biāo)，一個(gè)在上面的典型文件大小一般都在千兆甚至T字節(jié)，而且提供整體上高的數(shù)據(jù)傳輸帶寬。一個(gè)單一的FS實(shí)例應(yīng)該能支撐數(shù)以千萬(wàn)計(jì)的文件，并且能在一個(gè)集群里異構(gòu)軟硬件平臺(tái)間的可移植性。這種特性便于HFS作為大規(guī)模數(shù)據(jù)應(yīng)用平臺(tái)的推廣。成的。其中NameNode作為主服務(wù)器，管理文件系統(tǒng)名空間和客戶端對(duì)文件的操作；集群中的DNod管理的數(shù)據(jù)。DFS允許用戶以文件的形式數(shù)據(jù)。從內(nèi)部來(lái)看，文件被分成若干個(gè)數(shù)據(jù)塊（默認(rèn)為64MB，而且這若干個(gè)數(shù)據(jù)塊盡可能分散地存放在一組DNod上。NmNod執(zhí)行文件系統(tǒng) 名空間操作，比如打開(kāi)、關(guān)閉、重命名文件或 等，它也負(fù)責(zé)存放文件系統(tǒng)的元數(shù)據(jù)信息，這些元數(shù)據(jù)信息主要包括兩類的映射關(guān)系，即：文件和數(shù)據(jù)塊的映射關(guān)系；數(shù)據(jù)塊和具體存放的DNode之間的映射。Doe負(fù)責(zé)處理文件系統(tǒng)客戶端的文件讀寫請(qǐng)求，并在Nmde的統(tǒng)一調(diào)度下進(jìn)行數(shù)據(jù)塊的創(chuàng)建、刪除和工作。如圖21給出了HDFS的體系結(jié)。NmNod管理文件系統(tǒng)的元數(shù)據(jù)，DaNode實(shí)際數(shù)據(jù)。客端聯(lián)+')60HWDGDWD1DPHUHSOLFDVKRPHRR0HWDGDWD%ORFN2.1:HDFS系NameNod以獲取文件的元數(shù)據(jù)，而真正的文件/O操作是直接和DatNod進(jìn)行交互的。DatNod和NameNod建立連接以后，就會(huì)不斷地和NameNode保持心跳。心跳的返回也包含了NameNod對(duì)DatNod的一些命令，如刪除數(shù)據(jù)庫(kù)或者是把數(shù)據(jù)塊到另一個(gè)DtaNod。應(yīng)該注意的是：NameNode不會(huì)發(fā)起到DataNode的請(qǐng)求，在這個(gè)通信過(guò)程中，它們是嚴(yán)格的客戶端/服務(wù)器架構(gòu)。DataNode當(dāng)然也作為服務(wù)器接受來(lái)自客戶端的，處理數(shù)據(jù)塊讀/寫請(qǐng)求。DtaNode之間還會(huì)相互通信，執(zhí)行數(shù)據(jù)塊任務(wù)，同時(shí)，在客戶端執(zhí)行寫操作的時(shí)候，DtNod一個(gè)用于檢測(cè)HDFS集群狀態(tài)的輔助守護(hù)進(jìn)程。每個(gè)集群中都有一個(gè)SecondaryNameNode，它通常獨(dú)占一臺(tái)服務(wù)器，直接與NameNode通信，根據(jù)集群所配置的時(shí)間間隔獲取FS元數(shù)據(jù)的快照，以此來(lái)減少停機(jī)的時(shí)間并降低數(shù)據(jù)丟失和HadoopHadoop集群只有一個(gè)JobTracker服務(wù)器集群的NameNode節(jié)點(diǎn)上。一旦提交代碼到集群上，JobTracker會(huì)確定執(zhí)行的計(jì)劃，包括處理那些文件、為不同的任務(wù)分配節(jié)點(diǎn)以及所有任JobTracker會(huì)自動(dòng)重啟任務(wù)。TaskTracker執(zhí)行由JobTracker分配的任務(wù)，每個(gè)TaskTracker可以生成多個(gè)JVM來(lái)并行的處理許多假定TaskTracker已經(jīng)了，進(jìn)而重新提交相應(yīng)的任務(wù)到集群中的其他節(jié)點(diǎn)上MapReduce由最早分布式數(shù)據(jù)處理系統(tǒng)，用于并行計(jì)算的編明，然后整個(gè)分布式過(guò)程可以看做是由map和reduce組成的類函數(shù)過(guò)程。本小受一個(gè)鍵值對(duì)le，產(chǎn)生一組中間鍵值對(duì)。MapReduce框架會(huì)將mp函數(shù)產(chǎn)生的中間鍵值對(duì)里鍵相同的值傳遞給同一個(gè)reduceRedcer類的reduce函數(shù)接受map端傳來(lái)的一個(gè)鍵，以及相關(guān)的一組值，將這組值進(jìn)行合并產(chǎn)生一組規(guī)模更小的值。Mapper類和edcer類除了有map函數(shù)或者reduce函setup()和cleanup()來(lái)管理Mapper或者Reducer生命行map動(dòng)作前執(zhí)行的，所有需要預(yù)先的共享數(shù)據(jù)都有setup()函數(shù)進(jìn)行預(yù)讀根據(jù)key的值，MapReduce系統(tǒng)對(duì)各個(gè)鍵值對(duì)進(jìn)行shuffleandsort，具有相對(duì)于oporsrcr作業(yè)的整個(gè)過(guò)程如圖23所示。整個(gè)過(guò)程包含了4個(gè)獨(dú)立實(shí)體，他們分別是：提交MpucorcrsrcrS。當(dāng)客戶端進(jìn)程提交了任務(wù)之后，Job 的ruJob()方法將新建Job 例并調(diào)用submitJob()方法。提交作業(yè)后，ruJo()方法每隔幾秒詢問(wèn)作業(yè)的進(jìn)展情況，把進(jìn)度信息報(bào)告給控制臺(tái)。作業(yè)完成后，如果成功就顯示作業(yè)計(jì)數(shù)器。如果失敗，導(dǎo)致作業(yè)是失敗的錯(cuò)誤信息也將報(bào)告給控制臺(tái)。Job 用submitJob()方法實(shí)現(xiàn)的作業(yè)提交過(guò)程如下： )LOHV)LOHVORDGHGIURPORFDO+')6)LOHVORDGHGIURPORFDO+')65R5HDGUH5HDGU,X?DUNYLUQUPHD?YDUUHGD???LUāXLQRHV,WUHGDNY3DLUVKJ%DOOLD???UD???DU:UWEDFNWR+'6:UWEDFNWR+'6:將運(yùn)行作業(yè)所需要的資源(包括作業(yè)AR文件、配置文件和計(jì)算所得的輸入分片)到一個(gè)以作業(yè)I命名的下obrcer的文件系統(tǒng)中。作業(yè)R的副本較多,因此在運(yùn)行作業(yè)的任務(wù)時(shí)，集群中有很多個(gè)副本可供tasktrackr。如圖中的步驟。UXQMRE-FOLHQW-JHQHZMREVXEPLW - FOLQHWSXMREWUDFNHUFRS\MREUHWXUQV?HJ&KLOG-WDVNWUDFNHU:當(dāng)orcr收到對(duì)其sbmitJob()方法的調(diào)用后，會(huì)把此調(diào)用放入一個(gè)內(nèi)列中，交由作業(yè)調(diào)度器進(jìn)行調(diào)度，并對(duì)其進(jìn)行初始化。初始化包括創(chuàng)建一個(gè)表示正在運(yùn)行的作業(yè)的對(duì)象-封裝任務(wù)和記錄信息，便于任務(wù)的狀態(tài)和進(jìn)程。如圖中的步驟。因?yàn)閠sktracer會(huì)運(yùn)行一個(gè)簡(jiǎn)單的循環(huán)來(lái)定期發(fā)送hrtbt給orcrhertbet告知rcrtsktrackr是否還存活，同時(shí)也充當(dāng)兩者之間的消息通道。作為hartbat的一部分，tsktrackr會(huì)指明它是否已經(jīng)準(zhǔn)備好運(yùn)行新的任務(wù)，如果是，obtrcr會(huì)為它分配一個(gè)任務(wù)，并經(jīng)被分配了一個(gè)任務(wù)，下一步就是運(yùn)行該任務(wù)。首先，通過(guò)從HDFS把作業(yè)的JAR文件到tasktracker所在的本地文件系統(tǒng)，同時(shí)將應(yīng)用程序所需要的文件從分布式緩存到本地磁盤，如圖步驟8。接著，tasktracker為新建一個(gè)本地工作，并把JAR文件中的內(nèi)容解壓到這個(gè)文件夾下。最后，tasktracker新和狀態(tài)，當(dāng)作業(yè)完成時(shí)便把作業(yè)的狀態(tài)設(shè)置為“成功”，失敗時(shí)即設(shè)置為“失物中所的商品。在這樣的一個(gè)數(shù)據(jù)集中，我們可以發(fā)現(xiàn)商品與商品之的確[44][31]；戶將來(lái)的行為[5][8]；表3.1是一個(gè)不確定數(shù)據(jù)集，假設(shè)它是Lucy和Jack在某個(gè)平臺(tái)的一個(gè)瀏覽行為的記錄的整合。每個(gè)商品后面跟著一個(gè)大于0小于等于1的概率，它代表這個(gè)用戶可能近期這個(gè)商品的概率。比如，Lucy在過(guò)去的幾周內(nèi)瀏覽了十次這個(gè)平臺(tái)，有十次點(diǎn)擊了“clothing”這個(gè)產(chǎn)品，那么我們可以推出：Purchase(phone:1.0),3.1為更好的解釋不確定數(shù)據(jù)集，經(jīng)常借助于可能世界語(yǔ)義(PossibleWorldSemantics,簡(jiǎn)稱PWS)[19]。事實(shí)上，傳統(tǒng)的確定性數(shù)據(jù)集可以看做是一個(gè)不確定世界。假設(shè)有這樣一個(gè)可能世界W，Lucy確定了clothing，而Jack了phon。由表31可知Luyclothing(1?0.8)?(1?0.5)?1.0=0,而coe的概率為：(1?05)?10=0.。那么W的概率為0105=00據(jù)PWS計(jì)算的結(jié)果一樣[][4。盡管PWS非常有用，但是基于PWS數(shù)據(jù)挖掘的代價(jià)都是極大的。因?yàn)閷?duì)于一個(gè)不確定數(shù)據(jù)來(lái)說(shuō)，他用有著幾萬(wàn)幾百萬(wàn)條事務(wù)，包含了上千個(gè)項(xiàng)iem),它的PS更是巨大的且根本無(wú)法計(jì)算。舉個(gè)例子，表31中含有233.。WW{clothing,{clothing,food};{clothing,phone,food};{{clothing};{phone,{clothing,food};{phone,:由此可知，在PWS下進(jìn)行數(shù)據(jù)挖掘任務(wù)是一項(xiàng)極大的。而基于不確定假設(shè)有一個(gè)不確定數(shù)據(jù)集UDB,它包含了n條事務(wù)(transaction),{t1,t2,t3,···,,I=i1,i2,i3,···,im}代表UDB中出現(xiàn)的所有的項(xiàng)，這些項(xiàng)各自不相同。在UDB中，每一條事務(wù)都是由<td,X>的這樣一個(gè)元組組成的，其中tid用來(lái)區(qū)別各個(gè)事務(wù)，而X=1(p1),2(p2),3(3),···,xm(pm)，X包含m個(gè)單元且是I的一個(gè)子集。每個(gè)單元都是由一個(gè)項(xiàng)x和一個(gè)存在概率pi()組成，pti()表示x出現(xiàn)在ti可以確定某個(gè)可能世界中，它的支持度的值。假如我們已知UDB中每個(gè)可能世界的概率，且在每個(gè)可能世界中項(xiàng)集X的支持度也可以計(jì)算得到，那么可以計(jì)算出項(xiàng)集XSe(X。假設(shè)給定一個(gè)可能世界Wi和一個(gè)項(xiàng)集X,我們定義P(Wi)是可能世界Wi為真實(shí)世界的概率，S(X,Wi)是在世界Wi中，項(xiàng)集X出現(xiàn)的個(gè)數(shù)。我們用Ti,j表示事務(wù)tj包含在Wi中的項(xiàng)。假設(shè)項(xiàng)與項(xiàng)之間在事務(wù)中的存在是相互獨(dú)立的，那么P(Wi)以及X的期望支持度Se(X)可以這樣表示：P(Wi)

(p(x))

(1?Ptj j=1 Se(X)=W|P(Wi)×S(X, 其中，W是從不確定數(shù)據(jù)庫(kù)UDB中得到的可能世界的集合，|W|代表可能世由上面的可知，可以窮舉出所有的可能世界，然后在每個(gè)可能世界中計(jì)算項(xiàng)集X的支持度。但是這種方法是不可能行的，因?yàn)閷?duì)于一個(gè)有m個(gè)不確定項(xiàng)的數(shù)據(jù)庫(kù)來(lái)說(shuō)，它的可能世界就有2個(gè)。這個(gè)數(shù)量是極大的。假設(shè)，Sj(X,)是在可能世界中，項(xiàng)集X在事務(wù)tj中的支持度，那么如果X∈T,)那么Sj(X,i)=;否則Sj(X,i)=。那么我們可以得到以下

W ||

P(Wi)S(X,Wi)

Stj(X,|W

| P(W)St(X,W)

P(W)

P

j=1

j=1最終，Chui等人定義了這樣的一個(gè)計(jì)算項(xiàng)集X的期望支持度的Se(X)

Ptj j=1樣定義：當(dāng)且僅當(dāng)一個(gè)項(xiàng)集的期望支持度不小于minexpsup×N時(shí)，這個(gè)項(xiàng)集才是頻繁的。其中minexpsup是用戶指定的一個(gè)最小期望支持度的閾值，是一個(gè)大于0小于1的數(shù),N是數(shù)據(jù)集中事物集的個(gè)數(shù)。對(duì)于3.1中的例子，假設(shè)此minexpsup=0.5。根據(jù)定義，我們得到這個(gè)數(shù)據(jù)集中的頻繁項(xiàng)集為：許多的頻繁模式或者頻繁項(xiàng)集的挖掘算法都是基于Apriori算法[7]的改進(jìn)。不頻繁的。Apriori算法是基于先驗(yàn)知識(shí)，采用自底向上迭代的方式來(lái)產(chǎn)生頻加1。最后輸出那些總支持度大于等于指定閾值的候選集，得到頻繁k項(xiàng)集。Apriori算法的偽代碼如算法1和算法2所示：法效率的主要有兩個(gè)方面：(1)需要多次掃描數(shù)據(jù)庫(kù)，計(jì)算每個(gè)候選k項(xiàng)集的支持度，最后產(chǎn)生頻繁k項(xiàng)集，當(dāng)數(shù)據(jù)集很大的時(shí)候，非常耗時(shí)；(2)由頻繁k項(xiàng)集產(chǎn)生頻繁k+1項(xiàng)集的候選集的這個(gè)計(jì)算過(guò)程涉及到“交”的操作，比較耗時(shí)且占用內(nèi)存。(3)在將k項(xiàng)集的超級(jí)裁剪為頻繁k+1項(xiàng)集的候選集時(shí)，需要對(duì)k項(xiàng)集Algorithm1Apriori3:4:L1=findfrequent1-5:for(k=1;Lk?=?;k++) Ck+1=apriorigen(Lk,min forCt=subset(Ck+1,t) end end Lk+1={c∈Ck+1|c.count≥min13:end14:returnL

?????????仁?N畝?仁?N畝?????□?仁?N畝??仁?N畝??在不確定模型中，hui等人提出了單機(jī)模式下的-iori[]算法來(lái)挖掘頻繁項(xiàng)集。這個(gè)算法修訂了統(tǒng)計(jì)候選集支持度的這個(gè)過(guò)程，因?yàn)樵趥鹘y(tǒng)數(shù)據(jù)庫(kù)中統(tǒng)計(jì)的是候選集出現(xiàn)的次數(shù)而在不確定模型中，需要求的是每個(gè)候選集的期是大部分項(xiàng)的存在概率都很低的時(shí)候。假如一條事物中有三個(gè)項(xiàng)A,B,C且它們的存在概率分別為0.05,0.005,0.001,在統(tǒng)計(jì){ABC}期望支持度的時(shí)候過(guò)程中，項(xiàng)集{ABC}的在這條事物中增加0.05×0.005×0.001=0. 面對(duì)的海量數(shù)據(jù)時(shí)，單機(jī)平臺(tái)下的-iori算法常常顯得力不從心。因此針對(duì)以上制約riori算法效率的兩個(gè)主要因素，本文提出了MapReduc平臺(tái)下的改進(jìn)的Upriori算法，我們簡(jiǎn)稱為Uiorirllelized-iori算法。針對(duì)問(wèn)題一，Hdoop的并行策略大大縮短了多次掃描數(shù)據(jù)集所花的時(shí)間。由于-iori算法統(tǒng)計(jì)每個(gè)項(xiàng)集期望支持度的過(guò)程本質(zhì)上就是詞頻統(tǒng)計(jì)的過(guò)程，因此我們選擇項(xiàng)集作為每個(gè)map的，而項(xiàng)集對(duì)應(yīng)的概率作為每一次map的lu。這樣在rduc端就可以得到每個(gè)項(xiàng)集對(duì)應(yīng)的期望支持度，進(jìn)而輸出那些期望支持度大于等于用戶指定閾值的項(xiàng)集，得到頻繁項(xiàng)集。并行統(tǒng)計(jì)項(xiàng)了并行的方法來(lái)產(chǎn)生頻繁項(xiàng)集的超集[主要介紹下并行產(chǎn)生頻繁k項(xiàng)集的超集以及由超集裁剪為+1由Apriori算法我們可知，要生成頻繁k項(xiàng)集的超集，我們只需要將經(jīng)過(guò)排序的頻繁k項(xiàng)集中前k-1項(xiàng)相同但是尾部不同的項(xiàng)進(jìn)行連接即可。比如：我們有頻繁3項(xiàng)集{A,B,C},{A,B,D},{A,B,E},{C,D,E}成超集的時(shí)候，只需要將{A,B,C},{A,B,D},{A,B,E}三個(gè)項(xiàng)集分別進(jìn)行兩兩連接生成超集{A,B,C,D},{A,B,C,E},{A,B,D,E}三項(xiàng)集的超集示意圖如圖3.2所示。由圖可知，在并行產(chǎn)生超集的過(guò)程中，我們把頻繁k項(xiàng)集中的k-1項(xiàng)作為keyvalue。因此，那些k-1項(xiàng)相同的頻繁k項(xiàng)集將被發(fā)送到同一個(gè)reducereduce的value進(jìn)行組合，最后和相應(yīng)的value進(jìn)行連接產(chǎn)生三項(xiàng)集的超集。如圖所示的{C,D},{D,E},{C,E}就是{C,D,E}的組合，最后和它們共同的前綴組成了A,B,C,DA,B,C,EA,B,D,E}。而C,D,E}$&1主模式相同的產(chǎn)生模式的組合與主模式一起構(gòu)成項(xiàng)集的超集。由以上的分析可知，在并行產(chǎn)生超集的過(guò)程中，主模式是具有關(guān)鍵作用的。因此，在并行化的過(guò)程中，主模式作為，而將產(chǎn)生模式作為lu。這樣值相同的頻繁rcruc$&$%$%$%&?а$%$%&$%$%'$&&&'$'$'在單機(jī)的riroi算法中，我們知道在對(duì)k項(xiàng)集的超集進(jìn)行裁剪的過(guò)程中，需要超集的每個(gè)長(zhǎng)度為k的子集進(jìn)行比對(duì)，如果超集的每個(gè)長(zhǎng)度為k的項(xiàng)集都是頻繁k項(xiàng)集，那么這個(gè)超集就是+1項(xiàng)集的候選集，如果不是，那么這個(gè)超集不構(gòu)成+1項(xiàng)候選集k+。在產(chǎn)生k項(xiàng)集的超集的過(guò)程中，我們?cè)趓due端生成了k項(xiàng)集的超集，此時(shí)我們可以對(duì)超集進(jìn)行裁剪。即載入所有的k長(zhǎng)度為k的子集進(jìn)行比較。我們知道超集都是由兩個(gè)主模式相同的頻繁k項(xiàng)集生成的，因此，去掉產(chǎn)生模式中的任何一個(gè)組成的k查那些由主模式去掉任何一個(gè)項(xiàng)與產(chǎn)生模式組成的k項(xiàng)集是否是頻繁k項(xiàng)集就可以了。對(duì)于上面的例子中的ABC,D我們只需要檢查{AC,D,BCD是否是步驟1產(chǎn)生頻繁1項(xiàng)集。并行掃描在HDFS上的數(shù)據(jù)集，以每一項(xiàng)作為key，以每一項(xiàng)對(duì)應(yīng)的概率作為value，在reduce繁1項(xiàng)集，結(jié)果在HDFS上。若頻繁一項(xiàng)集不為空則繼續(xù)步驟2，若為步驟2產(chǎn)生頻繁2項(xiàng)集的候選集。步驟一種輸出的頻繁1項(xiàng)集進(jìn)行排序，將排序后的頻繁1項(xiàng)集進(jìn)行組合組成頻繁2項(xiàng)集的候選集，結(jié)果同樣步驟3若頻繁k項(xiàng)集候選集為空，則停止迭代；否則載入頻繁k項(xiàng)集候選集，并步驟4由頻繁k項(xiàng)集生成k+1項(xiàng)候選集。并行的掃描頻繁kk-1項(xiàng)PU-Apriori算法的整體框架圖如圖3.33.3可知，在用PU-Apriori算法產(chǎn)生min3.3)仁?畝???仁?N仁?畝???仁?NN畝??' '6):務(wù)中出現(xiàn)一次，它對(duì)應(yīng)的支持度增加1，即按照<key=item,value=1>這樣等于它在這條事務(wù)中出現(xiàn)的概率。對(duì)于在HDFS上的事務(wù)數(shù)據(jù)集，我們按個(gè)Mapper一個(gè)分割后的塊，按照<key=item,value=pro>這樣的鍵值對(duì)進(jìn)行輸出。item代表事務(wù)中出現(xiàn)的項(xiàng)，而pro代表項(xiàng)”item”在當(dāng)前的事務(wù)中出現(xiàn)的概率。最終key相同的鍵值對(duì)將被發(fā)送到同一個(gè)reduce節(jié)點(diǎn)，按照公的閾值minexpsup，輸出那些期望支持度大于等于minexpsup的頻繁1項(xiàng)集。具OrderedFrequent1Itemsets是已經(jīng)排好序的頻繁1項(xiàng)集，將這些頻繁1項(xiàng)集進(jìn)行生成頻繁項(xiàng)集是一個(gè)并行化的迭代過(guò)程。在mp端檢查每一條事務(wù)是否包含有某一項(xiàng)候選集，若包含則輸出<y=klue=pro>,其中k即是候選k項(xiàng)集，pro是這個(gè)候選集在當(dāng)前事務(wù)中出現(xiàn)的概率。若k包含有n個(gè)項(xiàng)，12···,n他們?cè)谑聞?wù)中分別出現(xiàn)的概率為p1p2···,pn由于事務(wù)中的項(xiàng)都是相互獨(dú)立的，因此候選集在當(dāng)前事務(wù)中出現(xiàn)的概率pro=∏i=npi。在reduce端，那些key值相同的鍵值對(duì)將會(huì)被發(fā)送到同一個(gè)reduce用3.3在reduce端進(jìn)行累加，得到當(dāng)前候選集的期望支持度。那些期望支持度大于等于minexpsup的項(xiàng)集即是頻繁k項(xiàng)集。具體如算法14：生成k+1項(xiàng)集的候選集也是一個(gè)并行化的迭代過(guò)程。在這個(gè)過(guò)程中主要是利用頻繁k項(xiàng)集來(lái)生成k+1項(xiàng)集的候選集。面我們介紹了如何并行生成k+1項(xiàng)候選集的思路。在map端，將頻繁k項(xiàng)集進(jìn)行分割，得到k個(gè)項(xiàng)。把前k-1項(xiàng)進(jìn)行連接組成主模式形成key，而把最后一項(xiàng)作為產(chǎn)生模式基形同，很多節(jié)點(diǎn)都是廉價(jià)的配置的機(jī)器。每個(gè)節(jié)點(diǎn)上的ubuntu和jdk版本也不中Mpr和cr的具體個(gè)數(shù)會(huì)影響實(shí)驗(yàn)的結(jié)果，因此我們遵循著充分利用集群的計(jì)算能力來(lái)進(jìn)行運(yùn)算。又因?yàn)?，每個(gè)節(jié)點(diǎn)的可用的ducr個(gè)數(shù)都是核的個(gè)數(shù)減1。因此，集群中可用的Mppr和ducr最大個(gè)數(shù)等于集群中可用的核的個(gè)數(shù)減去集群中的機(jī)器的個(gè)數(shù)。在這種情況下，擁有7個(gè)節(jié)點(diǎn)的集p和c2uc個(gè)數(shù)。由idens生成的accides1360M、ccidens2(720Maccides31440Mconect的大小是conect1conec3的大小是conec2ccides系列的數(shù)實(shí)驗(yàn)中我們主要采用加速比(speedup)和規(guī)模增長(zhǎng)性(sizeup)來(lái)評(píng)估PU-Apriori算法的性能。規(guī)模增長(zhǎng)性是指當(dāng)集群中的節(jié)點(diǎn)個(gè)數(shù)固定，改變數(shù)據(jù)3.4具體 如下

Sizeup(data,m)=

其中，data代表原始的數(shù)據(jù)集，而T1代表PU-Apriori算法處理數(shù)據(jù)集data所花的時(shí)間，Tm代表處理m倍的數(shù)據(jù)集所花的時(shí)間。而算法的運(yùn)行總時(shí)間包括通信開(kāi)加速比是指加速的情況，具體Speedup(data,m)=

其中，T1是指在一個(gè)單位(本文中是指4核的計(jì)算能力)的節(jié)點(diǎn)中處理數(shù)據(jù)集data所花的時(shí)間，而Tp是指在p個(gè)單位(本文中是指p4)的節(jié)點(diǎn)上算法所比主要用來(lái)衡量算法的加速情況。下面一小節(jié)分別就PU-Apriori算法在上面的81624核和32核的集且minexpsup設(shè)置的越小的時(shí)候，PU-Apriori算法的加速效果就越好。這是因?yàn)閿?shù)據(jù)集越大，minexpsup設(shè)置的越小，每個(gè)節(jié)點(diǎn)處理的數(shù)據(jù)量就越多，節(jié)點(diǎn)集，minexpsup設(shè)置的越小，加速效果就越好。這是因?yàn)閙inexpsup設(shè)置的越432theorymin432theorymin min min012dataset45432theorymin10minmin12dataset443214321minexpsup=0.6minexpsup=0.7minexpsup=0.808numberof:432min432min min min0 numberof期望支持度來(lái)衡量項(xiàng)集的頻繁性。輸出那些期望支持度大于等于minexpsup的采用優(yōu)化的策略來(lái)檢驗(yàn)候選k項(xiàng)集是否存在當(dāng)前的事務(wù)中,而這個(gè)是影響PU-2:foreachitemsetl1∈Lk foreachitemsetl2∈Lk if(l1[1]=l2[k]) c=l1??

(l1[2]=

··

(l1[k?1]=l2[k?

(l1[k] delete end end end13:end14:return15:Procedure:hasinfrequentsubset(C:candidate(k+1)-itemsets,Lk:frequentk-16:foreachk-subsetsofC ifs/Lk return return end22:end 1:Procedure:Map(key=offset,value=2:3:foreachpair<item,pro>intransaciton 5:end6:7:Procedure:Reduce(key, ble8:9:intsum= sum=sum+12:end13:ifsum≥minexpsup 15:end16:1:Procedure:Gen2FI(OrderedF2:3:foreachitemiinOrderedFrequent1Itemsets foreachitemsjbehindoftheiinOrderedFrequent1Itemsets add<i,j>to end7:end8:1:Procedure:Map(key=offset,value=2:4:foreachckinCk iftransaction.contains(ck) output(ck, end8:end9: ble11:12:intsum= sum=sum+15:end16:ifsum≥minexpsup Output(key,18:end19:1:Procedure:Map(key=offset,value=2:3:String[]4:for(i=0;i≤items.length?2;i++) MP=MP+””+6:end7:output(MP,8:9:Procedure:Reduce(key, ble10:11:setup(Lk);//loadallCkforallReducer13:foreachvalueinvaluesdo14:15:end 17:foreachpairingroupdo18:foreachiteminkeydo Stringsubset=key+””+ if!Lk.contains(subset); end end output(key+””+pair,28:end29: 在上一章中，我們提出了Hdoop平臺(tái)下的基于期望支持度的不確定頻繁項(xiàng)集的挖掘算法。在該算法中我們通過(guò)統(tǒng)計(jì)項(xiàng)集的期望支持度來(lái)確定哪些項(xiàng)集是頻繁的，哪些是不頻繁的。然而，用這種方法得到的頻繁項(xiàng)集并不能表示它在多大數(shù)據(jù)中，項(xiàng)集的支持度是不確定的，因此關(guān)于項(xiàng)集支持度的分布以及項(xiàng)集支持度的置信度信息是非常重要的。當(dāng)用基于期望支持度的P-iori算法來(lái)挖掘頻繁項(xiàng)集的時(shí)候，這種置信度信息將會(huì)丟失。因此基于期望支持度的挖掘算法最大的缺點(diǎn)就是它丟失了項(xiàng)集支持度的不確定信息。200年，Brcr在文章[]中提出了概率頻繁項(xiàng)集(ProbabilisicFrquettemst)的概念，還提出在并行的環(huán)境下提出了用產(chǎn)生式(generatefunction)來(lái)計(jì)算頻繁項(xiàng)集的概下面一節(jié)對(duì)不確定數(shù)據(jù)下的概率頻繁項(xiàng)集以及產(chǎn)生式(generatingfunc- TSe(X)

Ptj j=1其中，X是含有多個(gè)項(xiàng)(x的項(xiàng)集，tj是數(shù)據(jù)集T中的事務(wù)j。也可寫成如下的∑Se(X) P(X? 同樣，t是數(shù)據(jù)集T中的一條事務(wù)，X是含有多個(gè)項(xiàng)x的項(xiàng)集。表4.2.1是一個(gè)不確定數(shù)據(jù)集，從表中我們可以計(jì)算得到{D}的期望支持度為0.5+1.0+0.2+0.8+0.5=3.0，而{G}的期望支持度為0.1+1.0+0.9+1.0=3.0望支持度的算法中，我們認(rèn)為}和G}是同樣頻繁的，因?yàn)樗麄兊钠谕С侄仁窍嗤?。但是，由于他們出現(xiàn)在不確定數(shù)據(jù)中，他們?cè)跀?shù)據(jù)集中的支持度是不確定的，因此他們的頻繁確定程度也是不同的。對(duì)于項(xiàng)集{D}來(lái)說(shuō)，它在事務(wù)中出現(xiàn)的不確定性要高一些，而對(duì)于G}來(lái)說(shuō)它的確定型要高一些，因?yàn)樗谑聞?wù)中出現(xiàn)的概率要么接近要不接近。因此對(duì)于擁有相同期望支持度的{D}和G}來(lái)說(shuō)，他們的頻繁程度是不同的。因此，我們可以肯定的說(shuō)G}是頻繁項(xiàng)集的置信度要高于D200年Brcr提(A,0.8);(B,0.2);(D,0.5);(F,(B,0.1);(C,0.7);(D,1.0);(E,1.0);(G,(A,0.5);(D,0.2);(F,0.5);(G,(D,0.8);(E,0.2);(G,(C,1.0);(D,0.5);(F,0.8);(G,(A,1.0);(B,0.2);(C,4.1概率頻繁項(xiàng)集(frequentnessprobabilityitemset)[8]。給定一個(gè)不確定數(shù)據(jù)集T以及它的可能世界的集合W,T中的任意一個(gè)項(xiàng)集X的支持度概率Pi(X)表示項(xiàng)集X的支持度為i的概率。具體為：∑Pi(X)j(S(X,

W,W是可能世界的集合，任意一個(gè)可能世界w∈T,T數(shù)據(jù)集中的是事務(wù)集，任意一個(gè)t∈IX,項(xiàng)集XI項(xiàng)xS(X,項(xiàng)集X在可能世界w項(xiàng)集X的支持度是i項(xiàng)集X的支持度是大于等于i4.2其中的S(X,wj)是項(xiàng)集X在可能世界wj的支持度。又因?yàn)樵诓淮_定數(shù)據(jù)集中i∈{0,1,···,|T|},所以Pi(X)的分布又叫做支持度的概率分布，因?yàn)槭歉怕省?≤i≤|T

Pi(X)= ∑00123?456由表可知0≤i≤6Pi({D})=0.04+000123?456 004.1:項(xiàng)集D前一章的分析，對(duì)于一個(gè)有|T|條事務(wù)，I個(gè)項(xiàng)集的數(shù)據(jù)集來(lái)說(shuō)，利用可能世界求項(xiàng)集的支持度概率是一個(gè)巨大的。因?yàn)樗目赡苁澜缬蠴(2|T|·|I|)個(gè)之多的概率，如下 Pi(X) P(X?t)) (1?P(X? S?T,|S|=i t∈T其中S?T代表包含了i條事務(wù)的子集，并且這i條事務(wù)都包含有項(xiàng)集X。我們?cè)趍insup條事務(wù)中的概率，我們用P≥iX來(lái)表示項(xiàng)集X的支持度大于等于i的概率，得到P≥i(X)=∑|T Pk(X),當(dāng)用戶指定最小支持度minsup的時(shí)候，k=min們要求的是P≥minsup(X),即為項(xiàng)集X的頻繁概率(frequentnessprobability)，表示項(xiàng)集X的支持度最少為minsup的概率。而P≥minsup(X)=∑|T Pk(X),k=min終可以求得項(xiàng)集X圖4.2展示了表4.2.1中的項(xiàng)集{D}對(duì)于minsup的所有可能值的頻繁概率情況。當(dāng)minsup=3的時(shí)候，{D}的頻繁概率為0.71，當(dāng)minsup=4111 000123456???(min4.2:項(xiàng)集D候{D}的頻繁概率只有0.29。直來(lái)，P≥minsup(X)是用來(lái)衡量X頻繁程度的一個(gè)標(biāo)準(zhǔn)，也就是我們到底有多確定X在數(shù)據(jù)集中是頻繁的。結(jié)合4.5,我們可以得到在不確定數(shù)據(jù)集T中，項(xiàng)集X的支持度最少為minsup概率為：P≥minsup(X)

P(X?t))

(1?P(X? S?T,|S|≥minsup t∈T綜上，當(dāng)用戶指定一個(gè)最小頻繁概率σ，即是要求返回那些P≥minsup(X)≥σ的中，給定最小支持度minsup和最小頻繁概率σ,挖掘出那些支持度在大于等于最小支持度minsup的情況下，頻繁概率大于等于σ的項(xiàng)集。但是,通過(guò)觀察4.6我們發(fā)現(xiàn)要求出一個(gè)項(xiàng)集的頻繁概率必須窮舉出所有的滿足minsup的條件的的來(lái)計(jì)算項(xiàng)集的頻繁概率： P≥minsup(X)=1 P(X?t))·· 1?P(X? t∈T然而這種方法在雖然大大節(jié)約了計(jì)算時(shí)間，尤其是在minsup非常小的情況下。但是它仍然很低效，因?yàn)樗](méi)有解決窮舉S不適于并行化。而單機(jī)平臺(tái)下的一些優(yōu)化措施也使用不了。因此，我們使用了產(chǎn)生式(grigfuio)產(chǎn)生式(generatingfunction)最早是JianLi在2009年的[35]中提出用于概率數(shù)我們的并行化策略不謀而合。又因?yàn)椴淮_定數(shù)據(jù)的復(fù)雜性，傳統(tǒng)的FP-growth算首先，我們來(lái)看這樣的一個(gè)函數(shù)：(x)= (ai+bix),將函數(shù)展開(kāi)得到xk

i:βi=0

i:βi=1bi,其中β=<β1β1···βn>∏t∈{t1,t2,···

(1?P(X∈t)+P(X∈t)·x)j∈{0,1,···

其中，xj的系數(shù)cj是i的展開(kāi)式，代表著項(xiàng)集X在i條事務(wù)中出現(xiàn)j次的概率。在i的展開(kāi)式中包含了i+1個(gè)非零的項(xiàng)。又因?yàn)閕=i?1·(1?P(X∈ti)+P(X∈ti)· 即i可以由i?1在O(i的時(shí)間復(fù)雜度下求出。又因?yàn)?=1x0=1,所以計(jì)算N的復(fù)雜度為O(N2)，這個(gè)復(fù)雜度并不是那么理想的，因此能不能把復(fù)雜度降低到O(N)呢？要計(jì)算項(xiàng)集的頻繁概率只需要計(jì)算那些支持度大于等于最小支持度minsup的項(xiàng)集的概率,即:P(sup(X)≥minsup)。因此，可以得到下面的misup?1P(sup(X)≥minsup)=1?P(sup(X)<minsup)=1 去支持度小于等于最小支持度的概率。由于minsup的值小于項(xiàng)集在事務(wù)中出現(xiàn)的次數(shù)且i展開(kāi)式中的系數(shù)cj與i?1中的任何系數(shù)ck(k>j)都是不相關(guān)的，因此在計(jì)算任意的系數(shù)ci(i<minsup)的時(shí)候是不涉及到ck(k≥minsup)的。因此minsup包含最多minsup個(gè)項(xiàng)數(shù)。而計(jì)算項(xiàng)集的頻繁概率的復(fù)雜度被降低到O(minsup×N)。對(duì)于表4.2.1中的項(xiàng)集{D}，它在事務(wù)中出現(xiàn)的概率分別為{0.51.00.20.80.5}。假設(shè)minsup=3,可以肯定的是{D}在所有的可能世界里至少出現(xiàn)1次，因?yàn)镈1=0·(0.5+0.5x)=0.5x1+2=1·(0.0+1.0x)=0.5x2+3=2·(0.8+0.2x)=0.1x3+0.5x2+0.4x1?0.5x2+4=3·(0.2+0.8x)=0.4x3+0.42x2+0.08x1?0.42x2+5=4·(0.5+0.5x)=0.21x3+0.25x2+0.04x1?0.25x2+因此，P(sup({D})=0)=0,P(sup({D})=1)=0.04,P(sup({D})=2)=0.25。這樣可以求得P(sup({D})≥3)=0.71，與圖4.2中minsup=3時(shí)的值是一樣的。此時(shí)，如果σ小于等于0.71，那么{D}將會(huì)作為概率頻繁項(xiàng)集被返回，否則不返回。等式中等號(hào)上面的”?“表示我們只需要計(jì)算那些指數(shù)小于等于步驟1產(chǎn)生頻繁1項(xiàng)集。并行掃描在HDFS上的數(shù)據(jù)集，以每一項(xiàng)作為key，的支持度大于等于minsup的頻繁概率，輸出那些頻繁概率大于等于用戶指定的σ的項(xiàng)集，結(jié)果在HDFS上。若頻繁1項(xiàng)集不為空則繼續(xù)步驟2，步驟2產(chǎn)生頻繁2項(xiàng)集的候選集。首先對(duì)步驟1輸出的頻繁1項(xiàng)集進(jìn)行排序，將排序后的頻繁1項(xiàng)集兩兩進(jìn)行組合生成頻繁2項(xiàng)集的候選集，結(jié)果同樣步驟3若頻繁k項(xiàng)集候選集為空，則停止迭代；否則在map端的setup函數(shù)中載入以及它對(duì)應(yīng)的概率。在reduce端利用4.10來(lái)求得每個(gè)項(xiàng)集的支持度大于等于minsup頻繁概率，輸出那些頻繁概率大于等于用戶指定的σ的項(xiàng)步驟4由頻繁k成k+1項(xiàng)候選集。map端并行的掃描頻繁k項(xiàng)集，以前k-1項(xiàng)-priori算法和-priori算法相比，主要區(qū)別在于頻繁項(xiàng)集的計(jì)算，主要是步驟1和步驟3中的rduc1和步驟32和步驟4的算法參在步驟1中，mp端一行一行地處理原始的事務(wù)，輸入數(shù)據(jù)的k是行號(hào)，而lu是一條完整的事務(wù)。輸出一個(gè)<y=itmvlue=pro>的鍵值對(duì)，其中itm代表事務(wù)中的項(xiàng)，而pro代表這個(gè)項(xiàng)itm出現(xiàn)在事務(wù)中的概率。在ruc端，rurdc用410計(jì)算出每個(gè)支持度大于等minup的項(xiàng)的頻繁概率。最終輸出那些頻繁概率大于等于給定閾值σ的項(xiàng)集。至此，P-priori完成了概率頻繁1項(xiàng)集的挖掘。具體如算法7。1:Procedure:Map(key=offset,value=2:3:foreachpair<item,pro>intransaciton 5:end6:7:Procedure:Reduce(key, ble8:9:intsum=10:ArrayList 13:end14:ifproList.size()≥minsup p=computeFrequentnessProbability(min16:end17:的存在概率，即<keyck,vluepro>,ck是指包含的候選集，pro是指對(duì)應(yīng)Bernecker的方法根本沒(méi)有辦法處理GB以上的數(shù)據(jù)，而我們的算法雖然也有運(yùn)行時(shí)間過(guò)長(zhǎng)的缺點(diǎn)，可是我們是可以處理GB以上的數(shù)Algorithm Generatek-probabilistic-frequent-1:Procedure:Map(key=offset,value=2:4:foreachckinCk iftransaction.contains(ck) output(ck, end8:end9: ble11:12:intsum=13:ArrayList 16:end17:ifproList.size()≥minsup p=computeFrequentnessProbability(min19:end20:minOur4.3 據(jù)上面一章的分析可知，計(jì)算一個(gè)項(xiàng)集的精確概率的復(fù)雜度為O(N2),即使是采用了產(chǎn)生式模型進(jìn)行優(yōu)化，也只能降低到O(minsupN)。而由實(shí)驗(yàn)結(jié)果可知，即使是在并行的環(huán)境下，挖掘概率頻繁項(xiàng)集的時(shí)間也是難以忍受的，那對(duì)種方法，既能把計(jì)算的時(shí)間復(fù)雜度降低到O(N),又能保證挖掘出的概率頻繁項(xiàng)了基于正態(tài)分布的不確定概率頻繁項(xiàng)集并行挖掘算法和基于分布的不確定概本文對(duì)這兩種方法在時(shí)間上、精確率上、率上以及加速比上進(jìn)行了比在不確定數(shù)據(jù)中，我們知道項(xiàng)集的支持度是一個(gè)服從二項(xiàng)分布的隨機(jī)變量，因此項(xiàng)集的支持度可以用二項(xiàng)分布來(lái)進(jìn)行估計(jì)，而二項(xiàng)分布又可以用分布來(lái)進(jìn)行代替[。而當(dāng)數(shù)據(jù)量比較大的時(shí)候，根據(jù)李雅普諾夫中心極限定理，項(xiàng)集的支持度服從標(biāo)準(zhǔn)正態(tài)分布。因此常用的概率估計(jì)方法有兩種：一種是基于分布的概率估計(jì)方法[4]，一種是基于正態(tài)分布的概率估計(jì)方法[。下面將就這兩種方法分別進(jìn)行介紹。為了更好的理解這部分知TIXi布爾變量，代表項(xiàng)集X出現(xiàn)在事務(wù)ti由一系列的ZXiX,項(xiàng)集XI項(xiàng)x項(xiàng)集X在數(shù)據(jù)集T代表項(xiàng)集XμZXnZX5.1基于分布的概率估計(jì)方在介紹這部分知識(shí)之前，先介紹一個(gè)反單調(diào)性定理：假設(shè)存在兩個(gè)項(xiàng)集SI，并且SI,那么S的頻繁概率大于等于I的頻繁概率，即P(sup(S)≥minsup≥P(sup(I≥minsup)。在上一章的表4.2.1中，項(xiàng)集{D}的支持度概率分布如圖4.1，我們稱之為最大支持度概率函數(shù)(supportprobabilitymassfunction)簡(jiǎn)稱spmf[49]。spmf有一個(gè)項(xiàng)集X,在某條事務(wù)tj中的存在概率為P(X?tj),則：∏P(x∈P(X?tj)

用布爾向量ZX表示項(xiàng)集X出現(xiàn)在事務(wù)tj的情況，若ZX=1則表示項(xiàng)集 j出現(xiàn)在tj中，若ZX=0則表示項(xiàng)集X沒(méi)有出現(xiàn)在tj中。給定一個(gè)數(shù)據(jù)集T，對(duì)于項(xiàng)集X來(lái)說(shuō)它的出現(xiàn)情況可以由這樣一組隨量ZX，ZX，··· j 。因此，ZX=∑|T|ZX服 二項(xiàng)分布。又因?yàn)閆X=i表示項(xiàng)集X 事務(wù)中的支持度為i。因此，結(jié)合上一章中的知識(shí)可以得出如下的P(ZX=i)=P(S(X)=i)= 而P(ZX≥i)=P≥i(X)=1?P<i(X)。因此，給定不確定數(shù)據(jù)集T以及最小支持度minsup，項(xiàng)集的頻繁概率可以由下面的計(jì)算得出：P(S(X)≥minsup)=1?P(S(X)<minsup)=1?P(ZX≤minsup?又因?yàn)樽兞縕X的期望μXμX=Se(X)

T

tP tjj=1而當(dāng)數(shù)據(jù)量足夠大的時(shí)候，二項(xiàng)分布可以用分布來(lái)進(jìn)行估計(jì)。因此項(xiàng)集X的頻繁概率可以用如下的進(jìn)行計(jì)算：P(S(X)≥minsup)=1?F(minsup?1, 其中，F(xiàn)是期望為μX的分布的分布函數(shù)，而F(minsup?1,μX)=1τ(minsup,μX,其中τ(minsup,μX)=∫∞tminsup?1e?tdt。要計(jì)算項(xiàng)集的頻繁概(min 率是隨著μX的遞增而單調(diào)遞增的[49](min 因此，給定最小支持度minsup和最小頻繁概率σ,我們有更簡(jiǎn)便的方法可步驟1找到一個(gè)實(shí)數(shù)μm,使其滿足等式：σ=1?F(minsup,μm)。這個(gè)式子可步驟2用5.4計(jì)算項(xiàng)集的期望支持度，此時(shí)需要掃描數(shù)據(jù)集一次步驟3如果μX≥μm,那么我們認(rèn)為項(xiàng)集X是頻繁的，否則X是不頻繁的。2:Output:AllPFI:F={F1,F2,···,Fm}//Fkissetofk-3:4:μm=MinExpSup(minsup,5:6:k=1;j=7:while|Ck|!=0 foreachX∈Ck X.μ= while(++j)≤nand|Ck|!=0 foreachX∈Ck I.μ+=P(X∈ ifI.μ≥μm end end end end21:returnF;22:endj在基于分布的方法被同時(shí)，ToonCalders提出了用正態(tài)分布來(lái)游戲，要么這條事務(wù)包含項(xiàng)集X,要么不包含。最終項(xiàng)集X的支持度就是硬幣正面朝上的次數(shù)。和上一小節(jié)一樣，我們用布爾向量ZX表示X出現(xiàn)在事務(wù)tjj況，若ZX=1則表示項(xiàng)集X出現(xiàn)在tj中，若ZX=0則表示項(xiàng)集X 事務(wù)tj中。因此，給定一個(gè)數(shù)據(jù)集T，對(duì)于項(xiàng)集X來(lái)說(shuō)它的出現(xiàn)情況可以由這樣一組隨量ZX，ZX，···，ZX表示。因?yàn)檫@|T|個(gè)是相互獨(dú)立的， 此，每個(gè)變量都可以看做是二項(xiàng)分布的一個(gè)。根據(jù)中心極限定理可知，當(dāng)數(shù)據(jù)量足夠大的時(shí)候二項(xiàng)分布收斂于正態(tài)分布。因此，ZX服從正態(tài)分布，它的期望也就是項(xiàng)集的期望支持度μ∑

∑|T|

x∈XP(x∈而方差s2 |T|P(ZX=1)(1?P(ZX=1))。因此當(dāng)|T|也就是事務(wù)的數(shù)量 s ZX?μY|T|= s2

的頻繁概率進(jìn)行估計(jì)。如下：s2 minsup?0.5?Se(X) ≥minsup)=1?P(Z <minsup)=1??( s2其中，?是標(biāo)準(zhǔn)正態(tài)函數(shù)的累積分布函數(shù)，代表著Ixminsup0.5的概率。因此，在不確定數(shù)據(jù)集中，給定最小支持度minsup和最小頻繁概率σ，要后根據(jù)5.7求得項(xiàng)集的頻繁概率。若項(xiàng)集的頻繁概率大于等于σ則輸出，否基于正態(tài)分布的概率頻繁項(xiàng)集挖掘算法如算法上面一小節(jié)分析了基于分布的概率頻繁項(xiàng)集挖掘算法。LiangWang提掘。然而，面對(duì)海量數(shù)據(jù)時(shí)它仍然顯得很無(wú)力，因此我們提出了基于分布的概率頻繁項(xiàng)集并行挖掘算法(parallelApriori-basedPFI簡(jiǎn)稱PAPFI)。由上面的分析可知，在用戶給定的最小支持度minsup和最小頻繁概率σ的情況下必須先計(jì)算出對(duì)應(yīng)的μm。而我們的算法是基于Apriori算法的，因此在給定μm的情步驟1產(chǎn)生頻繁1項(xiàng)集。map端并行掃描在HDFS上的數(shù)據(jù)集，以每一項(xiàng)作為key，以每一項(xiàng)對(duì)應(yīng)的概率作為value，輸出<key=item,value=pro>的這樣一個(gè)鍵值對(duì)。其中item代表出現(xiàn)在事物中的項(xiàng)，pro代表這個(gè)項(xiàng)對(duì)望支持度，輸出其中結(jié)果大于等于μm的頻繁1項(xiàng)集，結(jié)果在HDFS上。2:Output:AllPFI:F={F1,F2,···,Fm}//Fkissetofk-3:4:C1={i|i∈5:k:=6:while|Ck|!=0 foreachck∈Ck ifX?t end end end14:Fk:={X∈Ck|X.freqprob≥σ}15:Ck+1:=generateCandidate(Fk);16:k++;17:end18:returnF;19:步驟2產(chǎn)生頻繁2項(xiàng)集的候選集。將步驟1中輸出的頻繁1項(xiàng)集進(jìn)行排序，將排序后的頻繁1項(xiàng)集兩兩組合生成頻繁2項(xiàng)集的候選集，結(jié)果同樣步驟3若頻繁k項(xiàng)集候選集為空，則停止迭代；否則在map端載入頻繁k項(xiàng)集候輸出那些期望支持度大于等于μm的候選集，即生成長(zhǎng)度為k的頻繁項(xiàng)集，結(jié)果在HDFS上。步驟4由頻繁k成k+1項(xiàng)候選集。map端并行的掃描頻繁k項(xiàng)集的每一行，的k項(xiàng)集，通過(guò)兩兩組合最后一項(xiàng)來(lái)產(chǎn)生k+1項(xiàng)候選集。k++,轉(zhuǎn)到步驟3.繁項(xiàng)集被輸出到HDFS上，而基于分布的概率頻繁項(xiàng)集任務(wù)完成。計(jì)算得到對(duì)應(yīng)的μm,最終挖掘出滿足用戶要求的概率頻繁項(xiàng)集。與第三章中的1:Procedure:Map(key=offset,value=2:3:foreachpair<item,pro>intransaciton 5:end6:7:Procedure:Reduce(key, ble8:9:intsum=10:intcount= sum=sum+ count+14:end15:ifcount≥minsup ifsum≥μm end19:end20:步驟1中，map端掃描事務(wù)集，發(fā)送<key=item,value=pro>這樣的鍵值對(duì)。而在reduce端，key相同的鍵值對(duì)將會(huì)被發(fā)送到同一個(gè)reduce節(jié)點(diǎn)。在reduce端，統(tǒng)計(jì)每個(gè)1項(xiàng)集的支持度和期望支持度，若項(xiàng)集item的支持度大于等于最小支持度minsup,且它的期望支持度大于等于μm,那么我們認(rèn)為這個(gè)1項(xiàng)集item是頻繁的，輸出到HDFS。否則是不頻繁的，予以舍棄。具體參見(jiàn)1:Procedure:Map(key=offset,value=2:4:foreachckinCk iftransaction.contains(ck) output(ck, end8:end9: ble11:12:intsum=13:intcount= sum=sum+ count+17:end18:ifcount≥minsup ifsum≥μm Output(key, end22:end23:出他們?cè)谙鄳?yīng)事物中的存在概率，即輸出一個(gè)<key=Ckvalue=pro>這樣的鍵值對(duì)。其中ck表示候選k項(xiàng)集，pro為ck在相應(yīng)事物中的存在概率。因此，key相同的鍵值對(duì)將會(huì)被發(fā)送到同一個(gè)reduce節(jié)點(diǎn)。在reduce端用和步驟1相同同樣，基于正態(tài)分布的概率頻繁項(xiàng)集并行挖掘算法(parallelAprioriApproxPFI簡(jiǎn)稱PAAPFI)，由分析可知，在給定最小支持度minsup和最小頻繁概率σ度的項(xiàng)集的頻繁概率，最終輸出頻繁概率大于等于σ步驟1產(chǎn)生頻繁1項(xiàng)集。map端并行掃描在HDFS上的數(shù)據(jù)集，以每一項(xiàng)作度，對(duì)于那些支持度大于等于minsup的項(xiàng)集用5.7計(jì)算它們的頻繁概率。輸出其中結(jié)果大于等于σ的頻繁1項(xiàng)集，結(jié)果在HDFS上。若頻步驟2產(chǎn)生頻繁2項(xiàng)集的候選集。對(duì)步驟1中輸出的頻繁1項(xiàng)集進(jìn)行排序，將排序后的頻繁1項(xiàng)集進(jìn)行兩兩組合生成頻繁2項(xiàng)集的候選集，結(jié)果同樣步驟3若頻繁k項(xiàng)集候選集為空，則停止迭代；否則map端的setup函數(shù)載入頻式5.7計(jì)算那些支持度大于等于minsup的項(xiàng)集的頻繁概率，輸出那些頻繁概率大于等于σ的候選集，即生成長(zhǎng)度為k的頻繁項(xiàng)集。步驟4由頻繁k成k+1項(xiàng)候選集。并行的掃描頻繁k項(xiàng)集，以前k-1項(xiàng)與第三章相比，PAAPFI算法大致相同，時(shí)間復(fù)雜度都是O(N)。只是在第于等于σ的項(xiàng)集。與第三章中的算法相比，改進(jìn)了步驟1和步驟3。而步驟2和步步驟1是用來(lái)生成頻繁1項(xiàng)集的。在mp端，發(fā)送當(dāng)前事務(wù)中的每個(gè)項(xiàng)以及這個(gè)項(xiàng)在這條事務(wù)中出現(xiàn)的概率，即鍵值對(duì)<y=itmlue=pro>。其中itm是現(xiàn)在當(dāng)前事務(wù)中的項(xiàng)，而pro是這個(gè)項(xiàng)對(duì)應(yīng)的存在概率。而在rduc端，y相同的鍵值對(duì)將會(huì)被發(fā)送到同一個(gè)rduc節(jié)點(diǎn)。在rduc節(jié)點(diǎn)中，需要計(jì)算三個(gè)變量的值。第一個(gè)是y期望支持度，最后一個(gè)是項(xiàng)集的方差。有了這三個(gè)變量就可以根據(jù)57計(jì)1:Procedure:Map(key=offset,value=2:3:foreachpair<item,pro>intransaciton 5:end6:7:Procedure:Reduce(key, ble8:9:floatmean= 10:floatvar=11:int sum=sum+ var=var+value?(1? n+16:end17:ifn≥minsupthen pro=key.freqProb ifpro≥σthen end22:end23:算出項(xiàng)集的頻繁概率。最后輸出那些頻繁概率大于等于最小頻繁概率σ的項(xiàng)集。若當(dāng)前的事務(wù)中包含ck<key=ck,value=pro>。若不包含ck，則檢查是否包含下一個(gè)候選集。直到檢查完所有的候選集，map函數(shù)結(jié)束。在reduce端，key相同的鍵值對(duì)將會(huì)被發(fā)這一章的實(shí)驗(yàn)環(huán)境仍然和第三章一樣，在擁有17個(gè)節(jié)點(diǎn)的集群上運(yùn)行，數(shù)據(jù)集也采用第三章的數(shù)據(jù)集，主要包括由connect生成的connect1