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

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

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

Smalldatadoesnotrequiredatamining,largedatacausesproblems

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

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

Loop:

對(duì)輸入中的每一個(gè)點(diǎn)p：

｛

計(jì)算p到各個(gè)cluster的距離；

將p歸入最近的cluster;

｝

重新計(jì)算各個(gè)cluster的中心

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

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

Mapper偽代碼classMapper

setup(…){

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

Centers}

map(key,p)//p為一個(gè)數(shù)據(jù)點(diǎn){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è)計(jì)Map階段的處理Combiner偽代碼classCombiner

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

reduce(ClusterID,value=[(pm1,n1),(pm2,n2)…]){pm=0.0；n=0;k=數(shù)據(jù)點(diǎn)列表中數(shù)據(jù)項(xiàng)的總個(gè)數(shù);fori=0tok{pm+=pm[i]*n[i];n+=n[i];}pm=pm/n;//求得所有屬于ClusterID的數(shù)據(jù)點(diǎn)的均值emit(ClusterID,(pm,n));//輸出新的聚類(lèi)中心的數(shù)據(jù)值}基于MapReduce的K-Means并行算法設(shè)計(jì)令k=2，欲生成cluster-0和cluster-1隨機(jī)選取A(1,1)作為cluster-0的中心，C(4,3)作為cluster-1的中心假定將所有數(shù)據(jù)分布到2個(gè)節(jié)點(diǎn)node-0和node-1上,即node-0：A(1,1)和C(4,3)node-1：B(2,1)和D(5,4)基于MapReduce的K-Means并行算法設(shè)計(jì)MapReduceK-Means聚類(lèi)處理示例在開(kāi)始之前，首先創(chuàng)建一個(gè)如前所述的全局文件基于MapReduce的K-Means并行算法設(shè)計(jì)MapReduceK-Means聚類(lèi)處理示例MapReduce階段每個(gè)節(jié)點(diǎn)讀取全局文件，以獲得上一輪迭代生成的clustercenters等信息計(jì)算本節(jié)點(diǎn)上的每一個(gè)點(diǎn)到各個(gè)clustercenter的距離，選擇距離最近的cluster為每一個(gè)數(shù)據(jù)點(diǎn)，emit<clusterassignedto,數(shù)據(jù)點(diǎn)自身>MapReduceK-Means聚類(lèi)處理示例基于MapReduce的K-Means并行算法設(shè)計(jì)MapReduce階段計(jì)算各個(gè)數(shù)據(jù)點(diǎn)到各個(gè)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è)計(jì)MapReduceK-Means聚類(lèi)處理示例Map階段的Combine處理利用combiner合并map階段產(chǎn)生的大量的ClusterID相同的鍵值對(duì)<ClusterID,p>Combiner計(jì)算要emit的所有數(shù)據(jù)點(diǎn)的均值，以及這些數(shù)據(jù)點(diǎn)的個(gè)數(shù)然后，為每一個(gè)cluster發(fā)射新的鍵值對(duì)<ClusterID,(pm,n)>

基于MapReduce的K-Means并行算法設(shè)計(jì)MapReduceK-Means聚類(lèi)處理示例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è)計(jì)MapReduceK-Means聚類(lèi)處理示例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，所以每個(gè)cluster的全部數(shù)據(jù)將被發(fā)送同一個(gè)reducer，包括：該cluster的ID該cluster的數(shù)據(jù)點(diǎn)的均值，及對(duì)應(yīng)于該均值的數(shù)據(jù)點(diǎn)的個(gè)數(shù)然后經(jīng)計(jì)算后輸出當(dāng)前的迭代計(jì)數(shù)ClusterID新的ClusterCenter屬于該ClusterCenter的數(shù)據(jù)點(diǎn)的個(gè)數(shù)基于MapReduce的K-Means并行算法設(shè)計(jì)MapReduceK-Means聚類(lèi)處理示例Reduce階段在上一階段，Combiner的輸出兩個(gè)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è)計(jì)MapReduceK-Means聚類(lèi)處理示例node-0發(fā)射：<cluster-0,[(1,1),1]><cluster-1,[(4,3),1]>node-1發(fā)射：<cluster-1,[(3.5,2.5),2]>計(jì)算可得cluster-0的中心=(1,1)cluster-1的中心=

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

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

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

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

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

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

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

Mapper偽代碼classMapper

setup(…){

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

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

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

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

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

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

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

//key或?yàn)榉诸?lèi)標(biāo)記y，或?yàn)?lt;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)頻度進(jìn)行未標(biāo)記測(cè)試樣本X分類(lèi)預(yù)測(cè)時(shí)，可以從這個(gè)輸出數(shù)據(jù)文件中快速查找相應(yīng)的頻度值并最終計(jì)算出X在各個(gè)Yi中出現(xiàn)的頻度P(X|Yi)P(Yi)，最后取得最大頻度的Yi即為X所屬的分類(lèi)樸素貝葉斯分類(lèi)并行化算法MapReduce并行化算法實(shí)現(xiàn)

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

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

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

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

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

頻繁項(xiàng)集挖掘算法1.頻繁項(xiàng)集挖掘問(wèn)題概述Whatistransactionanditemsets?AtransactioniscomposedofanidandasetofitemsThereare4transactionsinthefigureaboveThefirsttransaction(T100)has3items,{I1,I2,I5}isanitemsetThelengthof{I1,I2,I5}is3,soitiscalleda3-itemsetsAnitemset,whoselengthisk,isreferredasak-itemset頻繁項(xiàng)集挖掘問(wèn)題概述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,....)枚舉計(jì)算的時(shí)間復(fù)雜度是：O(2n*N*t),n是Item的總數(shù)，N是Transaction總數(shù)，t是每個(gè)Transaction平均包含的Item數(shù)頻繁項(xiàng)集挖掘問(wèn)題概述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