MapReduce海量數(shù)據(jù)并行處理-數(shù)據(jù)挖掘基礎(chǔ)算法

Ch9.數(shù)據(jù)挖掘基礎(chǔ)算法MapReduce海量數(shù)據(jù)并行處理9.1數(shù)據(jù)挖掘并行算法研究的重要性9.2基于MapReduce的K-Means聚類算法9.3基于MapReduce的分類算法9.4基于MapReduce的頻繁項集挖掘算法Ch9.數(shù)據(jù)挖掘基礎(chǔ)算法數(shù)據(jù)挖掘是通過對大規(guī)模觀測數(shù)據(jù)集的分析，尋找隱藏在這些數(shù)據(jù)集中的有用信息和事實的過程。

數(shù)據(jù)挖掘的特征之一：海量數(shù)據(jù)

Smalldatadoesnotrequiredatamining,largedatacausesproblems

——摘自黎銘的《數(shù)據(jù)挖掘》課件研究發(fā)現(xiàn)大數(shù)據(jù)隱含著更為準(zhǔn)確的事實因此海量數(shù)據(jù)挖掘是并行計算中值得研究的一個領(lǐng)域9.1數(shù)據(jù)挖掘并行算法研究的重要性2001年微軟研究院的BankoandBrill*等研究發(fā)現(xiàn)數(shù)據(jù)越大，機器學(xué)習(xí)的精度越高；當(dāng)數(shù)據(jù)不斷增長時，不同算法的分類精度趨向于相同！*M.BankoandE.Brili(2001).Scalingtoveryverylargecorporafornaturallanguagedisambiguation.ACL2001研究發(fā)現(xiàn)大數(shù)據(jù)隱含著更為準(zhǔn)確的事實數(shù)據(jù)挖掘并行算法研究的重要性研究發(fā)現(xiàn)大數(shù)據(jù)隱含著更為準(zhǔn)確的事實2007年Google公司Brants等基于MapReduce研究了一個2萬億單詞訓(xùn)練數(shù)據(jù)集的語言模型，發(fā)現(xiàn)大數(shù)據(jù)集上的簡單算法能比小數(shù)據(jù)集上的復(fù)雜算法產(chǎn)生更好的結(jié)果*T.Brants,A.C.Popat,etal.LargeLanguageModelsinMachineTranslation.InEMNLP-CoNLL2007-Proceedingsofthe2007JointConferenceonEmpiricalMethodsinNaturalLanguageProcessingandComputationalNaturalLanguageLearning數(shù)據(jù)挖掘并行算法研究的重要性9.1數(shù)據(jù)挖掘并行算法研究的重要性9.2基于MapReduce的K-Means聚類算法9.3基于MapReduce的分類算法9.4基于MapReduce的頻繁項集挖掘算法Ch9.數(shù)據(jù)挖掘基礎(chǔ)算法9.2基于MapReduce的K-Means聚類算法1.K-Means聚類算法介紹2.基于MapReduce的K-Means并行算法設(shè)計3.實驗結(jié)果與小結(jié)4.聚類算法應(yīng)用實例定義：將給定的多個對象分成若干組，組內(nèi)的各個對象是相似的，組間的對象是不相似的。進行劃分的過程就是聚類過程，劃分后的組稱為簇(cluster)。幾種聚類方法：基于劃分的方法；基于層次的方法；基于密度的方法；......1.K-Means聚類算法介紹數(shù)據(jù)點的數(shù)值類型數(shù)據(jù)點的類型可分為：歐氏（Euclidean）非歐這二者在數(shù)據(jù)的表示以及處理上有較大的不同：怎樣來表示cluster？怎樣來計算相似度K-Means聚類算法介紹Cluster的表示歐氏空間：取各個數(shù)據(jù)點的平均值（centroid）非歐空間取某個處于最中間的點取若干個最具代表性的點（clustroid）......K-Means聚類算法介紹相似度(距離)的計算歐氏空間：可以有較為簡單的方法

非歐氏空間：通常不能直接進行簡單的數(shù)字計算Jaccard距離:1-|S∩T|/|S∪T|Cosine距離：兩個向量的夾角大小Edit距離：適合于string類型的數(shù)據(jù)K-Means聚類算法介紹基于劃分(Partitioning)的聚類方法給定N個對象，構(gòu)造K個分組，每個分組就代表一個聚類。K個分組滿足以下條件：每個分組至少包含一個對象；每個對象屬于且僅屬于一個分組；K-Means算法是最常見和典型的基于劃分的聚類方法K-Means聚類算法介紹K-Means算法輸入：待聚類的N個數(shù)據(jù)點，期望生成的聚類的個數(shù)K輸出：K個聚類算法描述:選出K個點作為初始的clustercenter

Loop:

對輸入中的每一個點p：

｛

計算p到各個cluster的距離；

將p歸入最近的cluster;

｝

重新計算各個cluster的中心

如果不滿足停止條件，gotoLoop;否則，停止K-Means聚類算法介紹初始數(shù)據(jù)K=2選擇初始中心----------------------------------------------------------------------------------------------第1次聚類：計算距離++K-Means聚類算法介紹過程示例第1次聚類：歸類各點-----------------------------------------------重新計算聚類中心++K-Means聚類算法介紹過程示例(cont.)第2次聚類：計算距離-----------------------------------------------第2次聚類：歸類各點++++聚類無變化，迭代終止過程示例(Cont.)K-Means聚類算法介紹第i輪迭代：生成新的clusters，并計算clustercenters第i+1輪迭代：根據(jù)第i輪迭代中生成的clusters和計算出的clustercenters，進行新一輪的聚類如此不斷迭代直到滿足終止條件K-Means聚類算法介紹K-Means是個不斷迭代的過程對初始clustercenters的選取會影響到最終的聚類結(jié)果由此帶來的結(jié)果是：能得到局部最優(yōu)解，不保證得到全局最優(yōu)解相似度計算和比較時的計算量較大K-Means聚類算法介紹K-Means算法的局限性如果樣本數(shù)據(jù)有n個，預(yù)期生成k個cluster，則K-Means算法t次迭代過程的時間復(fù)雜度為O(nkt)，需要計算ntk次相似度如果能夠?qū)⒏鱾€點到clustercenter相似度的計算工作分攤到不同的機器上并行地計算，則能夠大幅提高計算速度本課將介紹利用MapReduce來將K-Means聚類過程并行化K-Means聚類算法介紹K-Means計算性能的瓶頸在進行K-Means聚類中，在處理每一個數(shù)據(jù)點時只需要知道各個cluster的中心信息不需要知道關(guān)于其他數(shù)據(jù)點的任何信息所以，如果涉及到全局信息，只需要知道關(guān)于各個clustercenter的信息即可2.基于MapReduce的K-Means并行算法設(shè)計考慮數(shù)據(jù)相關(guān)度將所有的數(shù)據(jù)分布到不同的MapReduce節(jié)點上，每個節(jié)點只對自己的數(shù)據(jù)進行計算每個Map節(jié)點能夠讀取上一次迭代生成的clustercenters，并判斷自己的各個數(shù)據(jù)點應(yīng)該屬于哪一個clusterReduce節(jié)點綜合每個屬于每個cluster的數(shù)據(jù)點，計算出新的clustercenters基于MapReduce的K-Means并行算法設(shè)計MapReduce并行化聚類算法設(shè)計思路需要全局共享的數(shù)據(jù)每一個節(jié)點需要訪問如下的全局文件當(dāng)前的迭代計數(shù)K個表示不同聚類中心的如下的數(shù)據(jù)結(jié)構(gòu)

clusteridclustercenter屬于該clustercenter的數(shù)據(jù)點的個數(shù)這是唯一的全局文件基于MapReduce的K-Means并行算法設(shè)計原始數(shù)據(jù)點數(shù)據(jù)文件Mapper1Mapper2Mapper3聚類中心信息ShuffleandSortReducer1Reducer2基于MapReduce的K-Means并行算法設(shè)計Map階段的處理在Map類的初始化方法setup中讀取全局的聚類中心信息對Map方法收到的每一個數(shù)據(jù)點p，計算p與所有聚類中心間的距離，并選擇一個距離最小的中心作為p所屬的聚類，輸出<ClusterID,p>鍵值對對每個Map節(jié)點上即將傳遞到Reduce節(jié)點的每一個<ClusterID,p>鍵值對，用Combiner進行數(shù)據(jù)優(yōu)化，合并相同ClusterID下的所有數(shù)據(jù)點并求取這些點的均值pm以及數(shù)據(jù)點個數(shù)n基于MapReduce的K-Means并行算法設(shè)計Map階段的處理

Mapper偽代碼classMapper

setup(…){

讀出全局的聚類中心數(shù)據(jù)

Centers}

map(key,p)//p為一個數(shù)據(jù)點{minDis=Double.MAXVALUE;index=-1;fori=0toCenters.length{dis=ComputeDist(p,Centers[i]);ifdis<minDis{minDis=dis;index=i;}}emit(Centers[i].ClusterID,p);}基于MapReduce的K-Means并行算法設(shè)計Map階段的處理Combiner偽代碼classCombiner

reduce(ClusterID,[p1,p2,…]){pm=0.0；n=數(shù)據(jù)點列表[p1,p2,…]中數(shù)據(jù)點的總個數(shù);fori=0tonpm+=p[i];pm=pm/n;//求得這些數(shù)據(jù)點的平均值emit(ClusterID,(pm,n));}基于MapReduce的K-Means并行算法設(shè)計Reduce階段的處理經(jīng)過Map和Combine后從Map節(jié)點輸出的所有ClusterID相同的中間結(jié)果<ClusterID,[(pm1,n1),(pm2,n3)…]>,計算新的均值pm，輸出<ClusterID,pm>所有輸出的<ClusterID,(pm,n)>形成新的聚類中心，供下一次迭代計算基于MapReduce的K-Means并行算法設(shè)計Reduce階段的處理Reducer偽代碼classReducer

reduce(ClusterID,value=[(pm1,n1),(pm2,n2)…]){pm=0.0；n=0;k=數(shù)據(jù)點列表中數(shù)據(jù)項的總個數(shù);fori=0tok{pm+=pm[i]*n[i];n+=n[i];}pm=pm/n;//求得所有屬于ClusterID的數(shù)據(jù)點的均值emit(ClusterID,(pm,n));//輸出新的聚類中心的數(shù)據(jù)值}基于MapReduce的K-Means并行算法設(shè)計令k=2，欲生成cluster-0和cluster-1隨機選取A(1,1)作為cluster-0的中心，C(4,3)作為cluster-1的中心假定將所有數(shù)據(jù)分布到2個節(jié)點node-0和node-1上,即node-0：A(1,1)和C(4,3)node-1：B(2,1)和D(5,4)基于MapReduce的K-Means并行算法設(shè)計MapReduceK-Means聚類處理示例在開始之前，首先創(chuàng)建一個如前所述的全局文件基于MapReduce的K-Means并行算法設(shè)計MapReduceK-Means聚類處理示例MapReduce階段每個節(jié)點讀取全局文件，以獲得上一輪迭代生成的clustercenters等信息計算本節(jié)點上的每一個點到各個clustercenter的距離，選擇距離最近的cluster為每一個數(shù)據(jù)點，emit<clusterassignedto,數(shù)據(jù)點自身>MapReduceK-Means聚類處理示例基于MapReduce的K-Means并行算法設(shè)計MapReduce階段計算各個數(shù)據(jù)點到各個cluster的距離，假定是如下的結(jié)果

Node-0Node-1node-0輸出：<cluster-0,A(1,1)><cluster-1,C(4,3)>node-1輸出：<cluster-1,B(2,1)><cluster-1,D(5,4)>基于MapReduce的K-Means并行算法設(shè)計MapReduceK-Means聚類處理示例Map階段的Combine處理利用combiner合并map階段產(chǎn)生的大量的ClusterID相同的鍵值對<ClusterID,p>Combiner計算要emit的所有數(shù)據(jù)點的均值，以及這些數(shù)據(jù)點的個數(shù)然后，為每一個cluster發(fā)射新的鍵值對<ClusterID,(pm,n)>

基于MapReduce的K-Means并行算法設(shè)計MapReduceK-Means聚類處理示例Map階段的Combine處理Map的輸出（即Combiner的輸入）：Combiner的輸出key-ClusterIDvalue-<ClusterID,(pm,n)>

node-0發(fā)射：<cluster-0,[(1,1),1]><cluster-1,[(4,3),1]>node-1發(fā)射：<cluster-1,[(3.5,2.5),2]>基于MapReduce的K-Means并行算法設(shè)計MapReduceK-Means聚類處理示例node-0輸出：<cluster-0,A(1,1)><cluster-1,C(4,3)>node-1輸出：<cluster-1,B(2,1)><cluster-1,D(5,4)>Reduce階段由于map階段emit的key是clusterID，所以每個cluster的全部數(shù)據(jù)將被發(fā)送同一個reducer，包括：該cluster的ID該cluster的數(shù)據(jù)點的均值，及對應(yīng)于該均值的數(shù)據(jù)點的個數(shù)然后經(jīng)計算后輸出當(dāng)前的迭代計數(shù)ClusterID新的ClusterCenter屬于該ClusterCenter的數(shù)據(jù)點的個數(shù)基于MapReduce的K-Means并行算法設(shè)計MapReduceK-Means聚類處理示例Reduce階段在上一階段，Combiner的輸出兩個reducer分別收到Reducer-0：<cluster-0,[(1,1),1]>Reducer-1：<cluster-1,[1,(4,3),1]><cluster-1,[(3.5,2.5),2]>基于MapReduce的K-Means并行算法設(shè)計MapReduceK-Means聚類處理示例node-0發(fā)射：<cluster-0,[(1,1),1]><cluster-1,[(4,3),1]>node-1發(fā)射：<cluster-1,[(3.5,2.5),2]>計算可得cluster-0的中心=(1,1)cluster-1的中心=

=(3.67,2.67)基于MapReduce的K-Means并行算法設(shè)計MapReduceK-Means聚類處理示例Reduce階段Reducer-0：<cluster-0,[(1,1),1]>Reducer-1：<cluster-1,[1,(4,3),1]><cluster-1,[(3.5,2.5),2]>Reducer輸出基于MapReduce的K-Means并行算法設(shè)計MapReduceK-Means聚類處理示例在第i次迭代后，已經(jīng)生成了K個聚類。如果滿足了終止條件，即可停止迭代，輸出K個聚類終止條件：設(shè)定迭代次數(shù);均方差的變化（非充分條件）每個點固定地屬于某個聚類其他設(shè)定條件......與具體的應(yīng)用高度相關(guān)基于MapReduce的K-Means并行算法設(shè)計終止迭代3.實驗結(jié)果與小結(jié)ParallelK-meansclusteringbasedonMapReduce

Zhao,Weizhong;Ma,Huifang;He,QingSource:

LectureNotesinComputerScience(includingsubseriesLectureNotesinArtificialIntelligenceandLectureNotesinBioinformatics),v5931LNCS,p674-679,2009,CloudComputing-FirstInternationalConference,CloudCom2009,Proceedings節(jié)點增加時的加速比數(shù)據(jù)增加時的時間開銷利用MapReduce來并行化K-Means聚類過程是可行的每個節(jié)點計算一部分數(shù)據(jù)的歸屬，從而實現(xiàn)并行數(shù)據(jù)間是無關(guān)的，但是數(shù)據(jù)和聚類中心是相關(guān)的，因此需要全局文件，但不構(gòu)成性能瓶頸沒有因為并行而降低了算法的精確度（每一個點均保證與每一個clustercenter進行了比較）算法設(shè)計實現(xiàn)小結(jié)實驗結(jié)果與小結(jié)NetFlix百萬美元大獎賽4.聚類算法應(yīng)用實例美國的一家電影在線租賃公司擁有大量用戶的影評記錄影片推薦系統(tǒng)基于這些影評記錄2009年設(shè)置大獎賽，能夠?qū)⑼扑]正確率提高10%者，將獲得100萬美元的獎勵聚類算法應(yīng)用實例Netflix公司與大獎賽聚類算法應(yīng)用實例Netflix公司與大獎賽上一個的百萬美元大獎的挑戰(zhàn)：為那些提供了50個以上評級的觀眾準(zhǔn)確地預(yù)測他們的口味，已經(jīng)被BellKor’sPragmaticChaos團隊解決。下一個百萬美元大獎的挑戰(zhàn)：為那些不經(jīng)常做影片評級或者根本不做評級的顧客推薦影片，要求使用一些隱藏著觀眾口味的地理數(shù)據(jù)和行為數(shù)據(jù)來進行預(yù)測。訓(xùn)練數(shù)據(jù)集：由N提供的由來自超過480K名隨機選擇的匿名用戶對接近18K部電影的影評（超過100M條）影評的等級范圍：從★到★★★★★測試數(shù)據(jù)集：包含超過2.8M條記錄。每條記錄包含用戶ID、電影ID、日期、影評等級，但是影評信息是空白。測試數(shù)據(jù)集是訓(xùn)練數(shù)據(jù)集的一個子集。聚類算法應(yīng)用實例競賽數(shù)據(jù)有17770個影片的影評文件，每個文件代表一部影片，描述了觀眾對于該影片的評價評價的指數(shù)從★到★★★★★

，每個影評文件的格式如：第一行：movieID其余每行：userID,rating,date兩個影評文件中的觀眾id可能有相同的，也可能不同聚類算法應(yīng)用實例競賽數(shù)據(jù)對提交算法的要求對于測試數(shù)據(jù)集中的任一個<用戶ID,電影ID>對，算法必須能夠預(yù)測出該用戶對該電影的影評，即給出影評的星級(1-5級)。聚類算法應(yīng)用實例算法的評價標(biāo)準(zhǔn)測試集將被劃分為不交的兩個子集（劃分的方法是保密的），對這兩個子集中的每一個預(yù)測影評，N將計算其與對應(yīng)的真實影評的均方根誤差(RMSE,RootMeanSquaredError)，計算結(jié)果精確到0.0001。δ=這里n是測量次數(shù)，di是一組測量值與平均值的誤差。聚類算法應(yīng)用實例競賽結(jié)果Cinematch影片推薦引擎形成了在前述訓(xùn)練數(shù)據(jù)集上的預(yù)測算法，該預(yù)測算法對測試數(shù)據(jù)集所做的預(yù)測的RMSE為0.9525。要想拿到百萬美金大獎，參賽者至少將預(yù)測的精確度提高10%，所以，算法的預(yù)測結(jié)果的RMSE必須不大于0.8572。BellKor’sPragmaticChaos

為本次競賽的領(lǐng)先團隊，他們所提交的算法的RMSE為0.8567。聚類算法應(yīng)用實例目的：根據(jù)觀眾的評價對這17770部影片進行數(shù)據(jù)挖掘，輸出約400個聚類，使得每個聚類中的影片是相似的考慮：1.怎樣定義及計算這類聚類問題中的相似度2.怎樣表示一個聚類（或聚類中心）3.對于高維數(shù)據(jù)怎樣預(yù)處理4.怎樣減少高維數(shù)據(jù)的計算量Netflix中的聚類問題聚類算法應(yīng)用實例9.1數(shù)據(jù)挖掘并行算法研究的重要性9.2基于MapReduce的K-Means聚類算法9.3基于MapReduce的分類算法9.4基于MapReduce的頻繁項集挖掘算法Ch9.數(shù)據(jù)挖掘基礎(chǔ)算法9.3基于MapReduce的分類并行算法1.分類問題的基本描述2.K-最近鄰分類并行化算法3.樸素貝葉斯分類并行化算法4.決策樹分類并行化算法分類(Classification)是機器學(xué)習(xí)和數(shù)據(jù)挖掘中最重要、最頻繁使用的算法。分類算法的基本作用是：從一組已經(jīng)帶有分類標(biāo)記的訓(xùn)練樣本數(shù)據(jù)集來預(yù)測一個測試樣本的分類結(jié)果。分類算法的基本描述是：一個訓(xùn)練數(shù)據(jù)集TR={tr1，tr2,tr3,…}每個訓(xùn)練樣本tri是一個三元組（tid，A，y）

其中tid是每個訓(xùn)練樣本的標(biāo)識符，A是一組特征屬性值：A={a1，a2，a3,…}，而y是訓(xùn)練樣本已知的分類標(biāo)記。

tidagesexcmKg發(fā)育12M8014良好23M8212不良32F6812良好………………1.分類問題基本描述對于一個測試樣本數(shù)據(jù)集TS={ts1，ts2,ts3,…}每個測試樣本ts也是一個三元組（tid，A，y’)，其中y’未知需要解決的問題是：根據(jù)訓(xùn)練數(shù)據(jù)集來預(yù)測出每個ts的未知的分類標(biāo)記y’訓(xùn)練數(shù)據(jù)集越大，對測試樣本分類標(biāo)記的預(yù)測越準(zhǔn)確tidagesexcmKg發(fā)育12M8014良好23M8212不良32F6812良好42F7517肥胖………………tidagesexcmKg發(fā)育12F7015？22M8212？33F6812？42M7517？………………訓(xùn)練樣本數(shù)據(jù)測試樣本數(shù)據(jù)分類問題基本描述基本算法設(shè)計思想K-最近鄰是分類器算法中最通俗易懂的一種，計算測試樣本到各訓(xùn)練樣本的距離，取其中距離最小的K個，并根據(jù)這K個訓(xùn)練樣本的標(biāo)記進行投票得到測試樣本的標(biāo)記。加權(quán)K-最近鄰分類算法的思路是，在根據(jù)測試樣本的標(biāo)記進行投票表決時，將根據(jù)測試樣本與每個訓(xùn)練樣本間距離（或相似度）的大小決定訓(xùn)練樣本標(biāo)記的作用大小，基本原則是：距離越近的訓(xùn)練樣本其標(biāo)記的作用權(quán)重越大，反之則越小。據(jù)此，可以建立一個帶加權(quán)的投票表決計算模型(比如y’=∑Si*yi/∑Si,k=[0,k-1],Si為取值0-1的相似度數(shù)值，yi為選取出的最鄰近訓(xùn)練樣本的分類標(biāo)記值)決定以最終的測試樣本的分類標(biāo)記。算法的思路清晰簡單，然而對于海量數(shù)據(jù)計算量很大，耗費時間較長。2.K-最近鄰(KNN)分類并行化算法K-最近鄰(KNN)分類并行化算法MapReduce并行化算法設(shè)計思路基本處理思路是：將測試樣本數(shù)據(jù)分塊后分布在不同的節(jié)點上進行處理，將訓(xùn)練樣本數(shù)據(jù)文件放在DistributedCache中共每個節(jié)點共享訪問Map階段對每個讀出的測試樣本數(shù)據(jù)ts(trid,A’,y’）計算其與每個訓(xùn)練樣本數(shù)據(jù)tr(trid,A,y)之間的相似度S=Sim(A’,A）（1：相似度最大，0：相似度最?。z查S是否比目前的k個S值中最小的大，若是則將(S,y)計入k個最大者根據(jù)所保留的k個S值最大的(S,y)，根據(jù)模型y’=∑Si*yi/∑Si計算出ts的分類標(biāo)記值y’，發(fā)射出(tsid,y’)Reduce階段直接輸出(tsid,y’)K-最近鄰(KNN)分類并行化算法MapReduce并行化算法實現(xiàn)

Mapper偽代碼classMapper

setup(…){

讀取全局訓(xùn)練樣本數(shù)據(jù)文件，轉(zhuǎn)入本地內(nèi)存的數(shù)據(jù)表TR中}

map(key,ts)//ts為一個測試樣本{Φ

MaxS(k)tstsid,A,yfori=0toTR.lenghth){TR[i]tr,A’S=Sim(A,A’);

若S屬于k個最大者，(S,y)MaxS;}

根據(jù)MaxS和帶加權(quán)投票表決模型計算出y’

emit(tsid,y’)}基本問題描述和算法設(shè)計思想設(shè)每個數(shù)據(jù)樣本用一個n維特征向量來描述n個屬性的值，即：X={x1，x2，…，xn}，假定有m個類，分別用Y1,Y2,…，Ym表示給定一個未分類的數(shù)據(jù)樣本X，若樸素貝葉斯分類將未知的樣本X分配給類Yi，則一定有P(Yi|X)>P(Yj|X),1≤j≤m，j≠i根據(jù)貝葉斯定理，由于P(X)對于所有類為常數(shù)，概率P(Yi|X)可轉(zhuǎn)化為概率P(X|Yi)P(Yi)。如果訓(xùn)練數(shù)據(jù)集中有很多具有相關(guān)性的屬性，計算P(X|Yi)將非常復(fù)雜，為此，通常假設(shè)各屬性是互相獨立的，這樣P(X|Yi)的計算可簡化為求P(x1|Yi)，P(x2|Yi)，…，P(xn|Yi)之積；而每個P(xj|Yi)可以從訓(xùn)練數(shù)據(jù)集求得。據(jù)此，對一個未知類別的樣本X，可以先分別計算出X屬于每一個類別Yi的概率P(X|Yi)P(Yi)，然后選擇其中概率最大的Yi作為其類別。3.樸素貝葉斯分類并行化算法樸素貝葉斯分類并行化算法MapReduce并行化算法設(shè)計思路根據(jù)前述的思路，判斷一個未標(biāo)記的測試樣本屬于哪個類Yi的核心任務(wù)成為：根據(jù)訓(xùn)練數(shù)據(jù)集計算Yi出現(xiàn)的頻度和所有屬性值xj在Yi中出現(xiàn)的頻度。據(jù)此，并行化算法設(shè)計的基本思路是：用MapReduce掃描訓(xùn)練數(shù)據(jù)集，計算每個分類Yi出現(xiàn)的頻度FYi(即P(Yi))、以及每個屬性值出現(xiàn)在Yi中的頻度Fxij(即P(xj|Yi))而在MapReduce中對訓(xùn)練數(shù)據(jù)集進行以上的頻度計算時，實際上就是簡單地統(tǒng)計Yi和每個xj出現(xiàn)的頻度在進行分類預(yù)測時，對一個未標(biāo)記的測試樣本，根據(jù)其包含的每個具體屬性值xj，根據(jù)從訓(xùn)練數(shù)據(jù)集計算出的Fxij進行求積得到FXi(即P(X|Yi))，再乘以FYi即可得到X在各個Yi中出現(xiàn)的頻度P(X|Yi)P(Yi)，取得最大頻度的Yi即為X所屬的分類。樸素貝葉斯分類并行化算法MapReduce并行化算法實現(xiàn)

訓(xùn)練數(shù)據(jù)集頻度統(tǒng)計Mapper偽代碼classMappermap(key,tr)//tr為一個訓(xùn)練樣本{trtrid,A,yemit(y,1)fori=0toA.lenghth){A[i]屬性名an和屬性值avemit(<y,an,av>,1)}}樸素貝葉斯分類并行化算法MapReduce并行化算法實現(xiàn)訓(xùn)練數(shù)據(jù)集頻度統(tǒng)計Reducer偽代碼classReducerreduce(key,value_list)

//key或為分類標(biāo)記y，或為<y,an,av>

{sum=0while(value_list.hasNext())sum+=value_list.next().get();emit(key,sum)}輸出結(jié)果為所有Yi的出現(xiàn)頻度FYi,以及所有屬性值xj在Yi中的出現(xiàn)頻度進行未標(biāo)記測試樣本X分類預(yù)測時，可以從這個輸出數(shù)據(jù)文件中快速查找相應(yīng)的頻度值并最終計算出X在各個Yi中出現(xiàn)的頻度P(X|Yi)P(Yi)，最后取得最大頻度的Yi即為X所屬的分類樸素貝葉斯分類并行化算法MapReduce并行化算法實現(xiàn)

測試樣本分類預(yù)測Mapper偽代碼classMappersetup(…){讀取從訓(xùn)練數(shù)據(jù)集得到的頻度數(shù)據(jù)

分類頻度表FY={(Yi,每個Yi的頻度FYi)}

屬性頻度表Fx={(<Yi,an,av>,出現(xiàn)頻度Fxij)}}map(key,ts)//ts為一個測試樣本{tstsid,AMaxF=MIN_VALUE;idx=-1;for(i=0toFY.length){FX=1.0；Yi=FY[i].Yi;FYi=FY[i].FYifor(j=0toA.length){an=A[j].an;av=A[j].av

根據(jù)<Yi,an,av>掃描Fx表,取得FxijFX=FX*Fx[i][j];}if(FX*FYi>MaxF){MaxF=FX*FYi;idx=i;}}emit(tsid,FY[idx].Yi)}決策樹分類并行化算法的基本處理思路決策樹的最關(guān)鍵技術(shù)是如何遞歸地在決策樹的節(jié)點上選取最好的分支屬性，而屬性通常用信息增益(informationgain）進行度量。信息增益的計算通常需要求取與前述樸素貝葉斯分類方法中的分類標(biāo)記頻度或“分類標(biāo)記-屬性名-屬性值”的出現(xiàn)頻度。因此，決策樹分類算法中信息增益的計算方法與前述樸素貝葉斯分類算法的處理過程類似。在一層屬性選擇完成后，訓(xùn)練數(shù)據(jù)將被分為數(shù)個數(shù)據(jù)數(shù)據(jù)子集，然后再用MapReduce過程對每一個子集遞歸地進行下一層屬性的選取。在以上屬性選取過程中，逐步形成決策規(guī)則對測試樣本進行分類預(yù)測時，將利用所產(chǎn)生的決策規(guī)則來進行匹配處理，最終得出測試樣本的分類標(biāo)記。4.決策樹分類并行化算法9.1數(shù)據(jù)挖掘并行算法研究的重要性9.2基于MapReduce的K-Means聚類算法9.3基于MapReduce的分類算法9.4基于MapReduce的頻繁項集挖掘算法Ch9.數(shù)據(jù)挖掘基礎(chǔ)算法9.4基于MapReduce的頻繁項集挖掘算法1.頻繁項集挖掘問題概述2.現(xiàn)有算法概述3.PSON：基于MapReduce的并行化算法4.并行化算法實驗結(jié)果本研究組進行了基于MapReduce的頻繁項集挖掘算法研究PSON:AParallelizedSONAlgorithmwithMapReduceforMiningFrequentSets

TaoXiao,ShuaiWang,ChunfengYuan,YihuaHuangTheFourthInternationalSymposiumonParallelArchitectures,AlgorithmsandProgramming(PAAP2011)，Tianjin，Dec.9-11,2011基本設(shè)計實現(xiàn)思路是：

根據(jù)基本的Apriori算法和SON算法，研究實現(xiàn)并行化的

頻繁項集挖掘算法1.頻繁項集挖掘問題概述Whatistransactionanditemsets?AtransactioniscomposedofanidandasetofitemsThereare4transactionsinthefigureaboveThefirsttransaction(T100)has3items,{I1,I2,I5}isanitemsetThelengthof{I1,I2,I5}is3,soitiscalleda3-itemsetsAnitemset,whoselengthisk,isreferredasak-itemset頻繁項集挖掘問題概述Whatistransactionanditemsets?SupposeIisanitemsetconsistingofitemsfromthetransactiondatabaseDLetNbethenumberoftransactionsDLetMbethenumberoftransactionsthatcontainalltheitemsofIM/NisreferredtoasthesupportofIinD

ExampleHere,N=4,letI={I1,I2},thanM=2becauseI={I1,I2}iscontainedintransactionsT100andT400sothesupportofIis0.5(2/4=0.5)Ifsup(I)isnolessthatanuser-definedthreshold,thenIisreferredtoasafrequentitemsetGoaloffrequentsetsminingTofindallfrequentk-itemsetsfromatransactiondatabase(k=1,2,3,....)枚舉計算的時間復(fù)雜度是：O(2n*N*t),n是Item的總數(shù)，N是Transaction總數(shù)，t是每個Transaction平均包含的Item數(shù)頻繁項集挖掘問題概述BasicIdeaAclassicfrequentsetsminingalgorithmNeedsmultiplepassesoverthedatabaseInthefirstpass,allfrequent1-itemsetsarediscoveredIneachsubsequentpass,frequent(k+1)-itemsetsarediscovered,withthefrequentk-itemsetsfoundinthepreviouspassastheseed(referredtoascandidate

itemsets)Repeatuntilnomorefrequentitemsetscanbefound*R.Agrawal,R.Srikant,“Fastalgorithmsforminingassociationrules,”inproceedingsofthe20thInternationalConferenceonVeryLargeDataBases,Santiago,Chile,August29-September1,19942.現(xiàn)有算法概述Apriori算法BasicideaDividethewholedatabaseintoseveralnon-overlappingpartitionsForeachpartition,discoverallthefrequentitemsets(referredtoaslocalfrequentitemsets)Mergeallthelocalfrequentitemsetsfromallthepartitions(referredtoasglobalcandidateitemsets)Removethosethatarenotactuallyfrequentinthewholedatabase,generating

globalfrequentitemsetsLemmaAnitemsetthatisnotlocalfrequentinanyofthepartitionscannotbeglobalfrequentAglobalfrequentitemsetmustappearaslocalfrequentinatleastoneofthepartitions*A.Savasere,E.Omiecinski,andS.Navathe,“Anefficientalgorithmforminingassociationrulesinlargedatabases,”inproceedingsofthe21stVLDBConferenceZurich,Swizerland,1995SON算法現(xiàn)有算法概述MotivationtoParallelizeSONBasedonMapReduceProcessingonepartitiondoesn’tneedanyinformationfromanyotherpartitionEachpartitioncanbeprocessedconcurrentlySONisnaturallysuitableforparallelizationPreparingdataStorethetransactiondatabaseintoDFSThewholedatabasewillbeautomaticallydividedintoseveralnon-overlappingchunksChunkscorrespondtothepartitionsinSONMaptasksEachchunkisprocessedbyonemappernodetofindlocalfrequentitemsetsforthatchunkReducetasksLocalfrequentitemsetsofthesamelengthareprocessedbyonereducenodeEachnodecountsforeachglobalcandidateitemsetitreceivesThendecideswhichareglobalfrequentitemsetsRuntwoMapReducejobstogenerateallfrequentitemsets1stjob:generateallglobalca