基于MapReduce的ID3決策樹(shù)分類(lèi)算法研究

1、計(jì) 算 機(jī) 與 現(xiàn) 代 化jisuanji yu xiandaihua2012 年第 2 期總第 198 期文章編號(hào): 1006-2475( 2012) 02-0026-05mapreduceid3基于的決策樹(shù)分類(lèi)算法研究錢(qián)網(wǎng)偉( 同濟(jì)大學(xué)電子與信息工程學(xué)院，上海 201804)摘要: 決策樹(shù)算法是經(jīng)典的分類(lèi)挖掘算法之一，具有廣泛的實(shí)際應(yīng)用價(jià)值。經(jīng)典的 id3 決策樹(shù)算法是內(nèi)存駐留算法，只能處理小數(shù)據(jù)集，在面對(duì)海量數(shù)據(jù)集時(shí)顯得無(wú)能為力。為此，對(duì)經(jīng)典 id3 決策樹(shù)生成算法的可并行性進(jìn)行了深入分析和 研究，利用云計(jì)算的 mapreduce 編程技術(shù)，提出并實(shí)現(xiàn)面向海量數(shù)據(jù)的 id3 決策樹(shù)并行分

2、類(lèi)算法。實(shí)驗(yàn)結(jié)果表明該算法 是有效可行的。關(guān)鍵詞: 云計(jì)算; 數(shù)據(jù)挖掘; 決策樹(shù);id3; mapreduce中圖分類(lèi)號(hào): tp301 6文獻(xiàn)標(biāo)識(shí)碼: adoi: 10 3969 / j issn 1006-2475 2012 02 008research on id3 decision tree classification algorithm based on mapreduceqian wang-wei( school of electronics and information engineering，tongji university，shanghai 201804，china)ab

3、stract: decision tree is widely used in data mining which is one of the typical classification algorithms traditional id3 treelearning algorithms require training data to reside in memory on a single machine，so they cannot deal with massive datasets to solve this problem，this paper analyzes the para

4、llel algorithm of id3 decision tree based on mapreduce model，then proposes a parallel and distributed algorithm for id3 decision tree learning the experimental results demonstrate the algorithm can scale well and efficiently process large-scale datasets on commodity computerskey words: cloud computi

5、ng; data mining; decision tree; id3;mapreducempi 的并行分布式 sprint5決策樹(shù)算法。該算法通過(guò)每個(gè)節(jié)點(diǎn)保存相應(yīng)的屬性表以及維護(hù)屬性表的 hash 表來(lái)實(shí)現(xiàn)并行運(yùn)算，這將導(dǎo)致數(shù)據(jù)過(guò)度冗余，從 而影響超大規(guī)模數(shù)據(jù)處理效率，這就需要一種新的計(jì) 算模型。云計(jì)算( cloud computing) 是一種新近提出的計(jì)算模式，是分布式計(jì)算( distributed computing) 、并行0引言分類(lèi)是數(shù)據(jù)挖掘的主要任務(wù)，其中決策樹(shù)分類(lèi)是分類(lèi)挖掘的常用模型，是經(jīng)典的機(jī)器學(xué)習(xí)算法之一。 它能夠通過(guò)訓(xùn)練數(shù)據(jù)集的學(xué)習(xí)來(lái)產(chǎn)生相應(yīng)的決策規(guī) 則樹(shù)，目前已成功地應(yīng)

6、用于 web 智能、金融分析、天 文學(xué)和分子生物學(xué)等領(lǐng)域1。c4 5 決策樹(shù)算法更是 被 icdm 評(píng)為十大經(jīng)典的數(shù)據(jù)挖掘算法之一并位居榜首2。傳統(tǒng)的決策樹(shù)算法有 id33、c4 54等。但是， 隨著信息量爆發(fā)性地增長(zhǎng)，傳統(tǒng)內(nèi)存駐留的決策樹(shù)算 法在處理海量數(shù)據(jù)時(shí)性能問(wèn)題日益突出，大規(guī)模海量 數(shù)據(jù)與處理任務(wù)不可能由一般的計(jì)算機(jī)在規(guī)定的時(shí) 間內(nèi)完成。為了解決算法內(nèi)存駐留問(wèn)題，通過(guò)引入高 效的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)調(diào)度策略等來(lái)改造決策樹(shù)學(xué)習(xí) 過(guò)程的算法相繼提出，如 john shafer 等提出了基于計(jì)算( parallel computing) 和網(wǎng)格計(jì)算( gridcompu-mapre-6。ting)

7、的 發(fā) 展 云 計(jì) 算 的 興 起，尤 其 是7-8duce框架( 如圖 1 ) 的提出，使得大規(guī)模數(shù)據(jù)集可以在普通機(jī)器集群上實(shí)現(xiàn)并行運(yùn)算，通過(guò) map 和 re-duce 兩 個(gè) 階 段 實(shí) 現(xiàn) 大 規(guī) 模 數(shù) 據(jù) 的 映 射 和 化 簡(jiǎn)。9作為分布式文件系統(tǒng)也是云計(jì)算的關(guān)鍵技術(shù)，gfs它是 google 云計(jì)算海量的數(shù)據(jù)存儲(chǔ)的有力平臺(tái)，并采用數(shù)據(jù)冗余等技術(shù)提供了一套完善的容錯(cuò)機(jī)制。10是云計(jì)算的開(kāi)源系統(tǒng)并實(shí)現(xiàn)了 google 云計(jì)hadoop算的主要技術(shù)( mapreduce、gfs 等) ，是 apache 開(kāi)源組織的一個(gè)并行分布式計(jì)算框架，它具有較高的可靠收稿日期: 2011-10-2

8、1作者簡(jiǎn)介: 錢(qián)網(wǎng)偉( 1986-) ，男，江蘇鎮(zhèn)江人，同濟(jì)大學(xué)電子與信息工程學(xué)院碩士研究生，研究方向: 數(shù)據(jù)挖掘，云計(jì)算。性和擴(kuò)展性。近年來(lái)云計(jì)算技術(shù)發(fā)展迅猛，并且運(yùn)用于機(jī)器學(xué)習(xí)領(lǐng)域11-12，其中 mapreduce 已經(jīng)廣泛應(yīng) 用于 amazon、google、baidu、阿里巴巴等國(guó)內(nèi)外知名 企業(yè)的云計(jì)算系統(tǒng)，具有強(qiáng)大的生命力。dm ) 。遞歸劃分步驟僅當(dāng)下列條件之一成立時(shí)停止: ( 1) 集合 d 所有元組屬于同一類(lèi);( 2) 沒(méi)有剩余屬性可以進(jìn)一步劃分元組，那么就使用多數(shù)類(lèi)表決;( 3) 給定的分支中沒(méi)有元組( 即 di 為空) ，此時(shí)用父節(jié)點(diǎn)中的多數(shù)類(lèi)標(biāo)記。1 2 屬性度量選擇不

9、同的決策樹(shù)算法之間的一個(gè)重要區(qū)別就在于 決策屬性選取標(biāo)準(zhǔn)的不同。生成決策樹(shù)時(shí)，常用屬性 度量 標(biāo) 準(zhǔn) 有 以 下 幾 種: 信 息 增 益、增 益 率、gini 指標(biāo)1。信息增益是 id3 使用的屬性選擇度量，在節(jié)點(diǎn) n存放的 d 的元組，選擇最高信息增益的屬性作為 n 的分裂屬性。該屬性使結(jié)果劃分中的元組分類(lèi)所需 的信息量最小，并反映這些劃分中的最小隨機(jī)性或“不純性”。對(duì)于 d 元組分類(lèi)所需的期望信息:m圖 1 mapreduce 的工作模式本文深入研究 mapreduce 編程框架，對(duì)經(jīng)典決 策樹(shù)算法進(jìn)行了深入的研究和剖析，利用決策樹(shù)度量 屬性重要性是基于屬性間的相互獨(dú)立性的原則，提出 了

10、面向海量數(shù)據(jù)的云計(jì)算環(huán)境下決策樹(shù)生成算法，并 利用 hadoop 開(kāi)源平臺(tái)實(shí)現(xiàn)了該算法。實(shí)驗(yàn)結(jié)果表明 該算法不僅具有高效性，而且能夠處理海量數(shù)據(jù)。1經(jīng)典決策樹(shù)算法hong j r 已經(jīng)證明決策樹(shù)生成算法是一個(gè) np-info( d)= pi log2 ( pi )( 1)i = 1其中，pi 是 d 中 任 意 元 組 屬 于 類(lèi) ci 的 概 率，并 用| ci，d | / | d | 估計(jì)?；诎磳傩?a( v 個(gè)不同值) 劃分對(duì) d 的元組分 類(lèi)所需要的期望信息:hard 問(wèn)題13，所以經(jīng)典決策樹(shù)一般采用貪心、分治的思想，由頂向下的遞歸方式生成。它通過(guò)在決策樹(shù)內(nèi)部節(jié)點(diǎn)上進(jìn)行評(píng)估來(lái)選擇最佳

11、決策屬性，并根據(jù)該 屬性的不同屬性值對(duì)該節(jié)點(diǎn)進(jìn)行分支，最終在決策樹(shù) 的葉子節(jié)點(diǎn)上得到分類(lèi)結(jié)論。決策樹(shù)從根節(jié)點(diǎn)開(kāi)始的每一條路徑均對(duì)應(yīng)著一條分類(lèi)規(guī)則，整棵決策樹(shù)則對(duì)應(yīng)了一組決策規(guī)則集。vinfoa ( d) = × info( dj )( 2)j = 1信息增益為原來(lái)的信息需求與新的需 求 之 間的差:gain( a) = info( d) info ( d)( 3)a1 1經(jīng)典 id3 算法經(jīng)典的深度優(yōu)先生成決策樹(shù) id3 算法如下:本文采用 c4 5 的增益率度量標(biāo)準(zhǔn)。增益率在選取屬性時(shí)避免了信息增益中對(duì)大量值屬性的偏倚，算法 1decision tree( r，c，d) 。從而提高

12、了決策樹(shù)的分類(lèi)準(zhǔn)確率。它定義了一個(gè)分裂信息:輸入: 屬性集 r，類(lèi)別屬性集 c，訓(xùn)練集 d。輸出: 決策樹(shù)。vsplitinfoa ( d)= j = 1× log2( 4)( 1)( 2)記 n;( 3)創(chuàng)建節(jié)點(diǎn) n;由公式( 3) 、( 4) 進(jìn)一步得到增益率，并選取具有最大增益率的屬性作為分裂屬性:ifd 為空 then 返回父節(jié)點(diǎn)中的多數(shù)類(lèi)標(biāo)gain( a)else if d 中屬于同一個(gè)類(lèi)別 c then 以類(lèi) cgainratio( a) =( 5)splitinfo( a)標(biāo)記 n 為葉節(jié)點(diǎn);( 4) else if記 n;r 為 空then返 回 d 中 多 數(shù) 類(lèi)

13、標(biāo)2云計(jì)算下決策樹(shù)算法中并行化思想云計(jì)算技術(shù)傳統(tǒng)的決策樹(shù)算法是內(nèi)存駐留算法，整個(gè)生成決2 1( 5) else 計(jì)算并選出 r 中增益率最大的屬性 s并用 s 標(biāo)記節(jié)點(diǎn) n;( 6) 根據(jù)屬性 s 的取值 si | i = 1，2，m 將訓(xùn) 練集合 d 分割為 di | i = 1，2，m ;策樹(shù)過(guò)程的所有數(shù)據(jù)計(jì)算必須同時(shí)在內(nèi)存中進(jìn)行，并且它只能在單機(jī)上運(yùn)行，這就大大地影響了算法的伸( 7)遞歸執(zhí)行 decisiontree ( r-s，c，d1 ) ，deci-縮性，因此它不能處理大規(guī)模數(shù)據(jù)。云計(jì)算的出現(xiàn)，sion tree ( r-s，c，d2 ) ， decision tree ( r-

14、s，c，為解決這一問(wèn)題提供了強(qiáng)有力的工具，使得用傳統(tǒng)經(jīng)djddjddjd28計(jì) 算 機(jī)與現(xiàn) 代 化2012 年第 2 期典的數(shù)據(jù)挖掘算法處理大規(guī)模數(shù)據(jù)成為可能。mapreduce 是一種處理海量數(shù)據(jù)的并行編程模 式。用戶將實(shí)際應(yīng)用問(wèn)題分解成若干可并行操作的 子問(wèn)題，設(shè)計(jì)相應(yīng)的 map 和 reduce 兩個(gè)函數(shù)，就能 將自己的應(yīng)用程序運(yùn)行在云計(jì)算環(huán)境中。map 函數(shù) 是接收一組輸入鍵值對(duì) in-key，in-value ，然后通 過(guò)某種計(jì)算，產(chǎn)生中間結(jié)果鍵值對(duì)，而 reduce 函數(shù)接 收一個(gè)中間結(jié)果 key 和對(duì)應(yīng)此 key 的一組 value 值，value-sum 進(jìn)行 hash 映射。

15、根據(jù)計(jì)算增益率所需的參數(shù)建立若干個(gè) hash 表。然后，能通過(guò) hash 查詢從 而快速地批處理地計(jì)算同一層次的各個(gè)訓(xùn)練集 di 的 每個(gè)屬性的增益率，并選取 di 中最大增益率的屬性 作為分裂屬性。3基于 mapreduce 的決策樹(shù)算法實(shí)現(xiàn)本算法通過(guò)一個(gè)劃分條件集隊(duì)列 q，來(lái)實(shí)現(xiàn)基于然后 通 過(guò) 歸 并 處 理，最 終 形 成value 。 final-key，final-層次切分?jǐn)?shù)據(jù)和同一層次各個(gè)訓(xùn)練集分裂屬性的選取。利用隊(duì)列先進(jìn)先出原則，從隊(duì)頭到隊(duì)尾依次對(duì) q中每個(gè)對(duì)象( 即劃分條件) 進(jìn)行標(biāo)記臨時(shí) nid 號(hào)( 1，2，| q | ) 。根 據(jù) 上 一 節(jié) 描 述 的 設(shè) 計(jì) 思 想

16、，結(jié) 合 al- lelectronic 顧客數(shù)據(jù)訓(xùn)練集( 見(jiàn)表 1) 以及該數(shù)據(jù)訓(xùn)練2 2決策樹(shù)的并行化通過(guò)分析發(fā)現(xiàn)，屬性選擇度量在決策樹(shù)生成階段是最為關(guān)鍵的任務(wù)，選取最佳分裂屬性的階段是整個(gè)決策樹(shù)生成中占用計(jì)算資源最大的階段。利用云計(jì) 算的 mapreduce 對(duì)這個(gè)階段進(jìn)行最大化的并行計(jì)算 是決策樹(shù)算法并行化的突破口。由于信息增益率計(jì)算是基于屬性間相互獨(dú)立的，所以可以利用 mapreduce 并行地統(tǒng)計(jì)出計(jì)算增益率 所需要的各個(gè)屬性的相關(guān)信息。最后，在主程序中可 以快速地計(jì)算增益率，并選取最佳分裂屬性。具體設(shè) 計(jì)思想如下:1集產(chǎn)生的決策樹(shù)( 如圖 2)，簡(jiǎn)述 3 個(gè)關(guān)鍵函數(shù)的算法實(shí)現(xiàn):表

17、 1 allelectronic 顧客數(shù)據(jù)訓(xùn)練集2 2 1map 階段設(shè)計(jì)思想map 階段主要是對(duì)大規(guī)模數(shù)據(jù)按照劃分條件進(jìn)行切分，劃分條件就是該節(jié)點(diǎn)在決策樹(shù)中的路徑。通 過(guò)實(shí)驗(yàn)證明，切分?jǐn)?shù)據(jù)的時(shí)間幾乎覆蓋了整個(gè)程序運(yùn) 行的時(shí)間。為此，本文提出的是基于層次切分?jǐn)?shù)據(jù)的 廣度優(yōu)先生成多叉樹(shù)算法。假設(shè)對(duì)訓(xùn)練集 d，劃分在決策樹(shù)的同一層的 n 個(gè)節(jié)點(diǎn): d1 ，d2 ，dn ，必定滿足:d d' = d1 d2 dn其中，d'為已生成葉節(jié)點(diǎn)的子訓(xùn)練集，且滿足:d1 d2 dn = 那么，map 函數(shù)的主要任務(wù)就是以單個(gè)元組的形式分解數(shù)據(jù)，并以 key，value 的形式輸出 d1 ，d2

18、 ，dn 。其中 key 由子訓(xùn)練集的臨時(shí) nid ( 記為 i，則di 表示同一層次的第 i 個(gè)子訓(xùn)練集) ，決策表的某個(gè)屬性 s，該元組對(duì)應(yīng)屬性 s 的值 s 以及該元組的所屬?zèng)Q策類(lèi) c 組成的; value 值為 1 即可。2 2 2 reduce 階段設(shè)計(jì)思想reduce 階段的任務(wù)相對(duì)單一，即完成對(duì) map 輸出的 key，value 進(jìn)行以相同 key 值的 value 值累 加得到 value-sum。同時(shí)，輸出 key，value-sum 到 分布式文件系統(tǒng) hdfs 中。對(duì)上述決策表有決策樹(shù)模型:圖 2 allelectronic 顧客數(shù)據(jù)訓(xùn)練集產(chǎn)生的決策樹(shù)算法 2map(

19、dataitem，q) 。輸入: 訓(xùn)練數(shù)據(jù)集 d，條件集隊(duì)列 q( map 以元組dataitem 的形式分解訓(xùn)練集 d) 。輸出: key，value 組。( 1)( 2) ( 3)value = 1;if q 為空 thenfor 所有屬性 dokey = 1 #屬性號(hào)，對(duì)應(yīng)屬性值，所屬類(lèi) ，( 4) else if條件 thenq 非空且 dataitem 滿足 q 中第 i 個(gè)( 5) for 所有候選屬性 do( 6)key = i#候選屬性號(hào)，對(duì)應(yīng)屬性值，所屬類(lèi)2 2 3 ，value = 1;主程序的設(shè)計(jì)思想該階 段 首 先 對(duì) mapreduce 的 最 終 輸 出 key，(

20、 7)輸出 key，value ridageincomestucreditbuy1youthhighnofairno2youthhighnoexcellentno3middlehighnofairyes4seniormediumnofairyes5seniorlowyesfairyes對(duì)于表 1 中數(shù)據(jù)，生成在決策樹(shù)( 圖 2 ) 第 3 層節(jié)( 4 )hash 表; ( 5)( 6)mapreduce讀 取輸 出 結(jié) 果 并 映 射 若 干點(diǎn)的 條 件 集 隊(duì) 列 q 為 ( 1，youth ) ( 3，no ) ，( 1，ifq 為空 then i = 1 并跳至步驟( 7) ;youth

21、) ( 3，yes) ，( 1，senior) ( 4，fair) ，( 1，senior) ( 4，excellent) ，該隊(duì)列 q 對(duì)應(yīng)的樹(shù)模型如圖 3 的虛框內(nèi):for i from 1 to | q |do / for 循環(huán)對(duì) 1 至 | q |號(hào)節(jié)點(diǎn)進(jìn)行了最佳分裂屬性的選取和類(lèi)的決策。( i代表同一層次自左向右的第 i 節(jié)點(diǎn)，以下操作皆為對(duì)每個(gè) hash 表中 nid 號(hào)為 i 的數(shù)據(jù)進(jìn)行處理)( 7)if 劃分?jǐn)?shù)據(jù)為空then將劃分條件 + 父節(jié)點(diǎn)多數(shù)類(lèi)放入決策規(guī)則集 r;( 8) elseif 所有類(lèi)同為類(lèi) c then 將劃分條件 +類(lèi) c 放入決策規(guī)則集 r;( 9) el

22、seif 劃分條件長(zhǎng)度 = 閾值 then 將劃分條件 + 該節(jié)點(diǎn)的多數(shù)類(lèi)放入決策規(guī)則集 r;( 10) else 計(jì)算各屬性的增益率，取最大的作為 分裂屬性，分別將劃分條件 + 該屬性的每個(gè)屬性值依 次放入數(shù)據(jù)劃分條件隊(duì)列 q;( 11) end for;圖 3 map 函數(shù)處理第三層數(shù)據(jù)map 函數(shù)利用虛框中條件集 q 分解整個(gè)訓(xùn)練集 d，對(duì)于 rid = 9 的元組: 因?yàn)樵撛M滿足 q 中第 2 個(gè) 元素( 1，youth) ( 3，yes) ，所以把其歸入 nid = 2 的節(jié) 點(diǎn)中，那么該元組的 key，value 組為 ( 2 #2，low， yes) ，1 ， ( 2 #4，f

23、air，yes) ，1 ; 其它所有元組的 key，value 組依此類(lèi)推得到。( 12) while( q 非空) 根據(jù) allelectronic 顧客數(shù)據(jù)訓(xùn)練集，本算法通過(guò)實(shí)驗(yàn)輸出的規(guī)則集 r 為: ( 1，middle: yes) ，( 1，youth 3，no: no) ，( 1，youth 3，yes: yes) ，( 1，senior 4，fair: yes) ，( 1，senior 4，excellent: no) 。算法 3reduce( key，value) 。4實(shí)驗(yàn)輸入: map 輸出的 key，value 組。輸出: key，value-sum 組。( 1) for 所

24、有相同 key 則 value-sum + = value;( 2) 輸出 key，value-sum / key = ( nid #屬性 號(hào)，屬性值，類(lèi)名) ; value-sum = 相同 key 的總數(shù)。根據(jù)之前 map 的輸出得到，nid = 1 節(jié)點(diǎn)的 3 條數(shù)據(jù)對(duì)應(yīng)的 map 輸出的 key，value 組為 ( 1 #2， high，no) ，1 ， ( 1 #4，fair，no) ，1 ， ( 1 #2，high， no) ，1 ， ( 1 #4，excellent，no ) ，1 ， ( 1 #2，medi- um，no) ，1 ， ( 1 #4，fair，no) ，1 ;

25、那么 reduce 輸 出的 key，value-sum 組為 ( 1 #2，high，no) ，2 ， ( 1#4，fair，no) ，2 ， ( 1 #4，excellent，no) ，1 ，( 1#2，medium，no) ，1 。其它所有節(jié)點(diǎn)的 key，val- ue 組依此類(lèi)推得到。基于層次切分?jǐn)?shù)據(jù)的廣度優(yōu)先生成多叉樹(shù)算法:因?yàn)楸舅惴ㄊ菍?duì)傳統(tǒng)算法實(shí)現(xiàn)并行化，算法對(duì)allelectronic 顧客數(shù)據(jù)集分類(lèi)輸出的決策規(guī)則集與傳 統(tǒng)算法產(chǎn)生的決策樹(shù)是一致的，并未改變傳統(tǒng)決策樹(shù) 算法的分類(lèi)精確度，所以實(shí)驗(yàn)僅對(duì)算法的高效性和可 擴(kuò)展性進(jìn)行論證。軟件環(huán)境: hadoop-0 20 2，ubun

26、tulinux 9 04，jdk6 0。硬件環(huán)境: 7 臺(tái) pc 機(jī)，其中 1 臺(tái) master 和 6臺(tái) slave。每臺(tái)的機(jī)器配置為: cpu p4，內(nèi)存 512m，網(wǎng)卡 100m。實(shí)驗(yàn)數(shù)據(jù)來(lái)自 uci，具體描述如表 2 所示。表 2 nursery 數(shù)據(jù)集描述算法 4generating-decisiontree( d) 。為產(chǎn)生大規(guī)模數(shù)據(jù)，本實(shí)驗(yàn)采用了 nursery 數(shù)據(jù)輸入: 大規(guī)模數(shù)據(jù)訓(xùn)練集 d。輸出: 決策規(guī)則集 r。集復(fù)制的手段分別產(chǎn)生了 100m、300m、500m、800m、1g 的數(shù)據(jù)集，并分別在 1、2、4、6 臺(tái)機(jī)器組成的集群運(yùn)行，得到如圖 4 的運(yùn)行時(shí)間圖。( 1

27、)( 2) ( 3)模數(shù)據(jù)創(chuàng)建條件隊(duì)列 q;do執(zhí)行 mapreduce( d，q) ;/ 并行處理大規(guī)數(shù)據(jù)集特征:多變量元組數(shù):12960領(lǐng)域:社會(huì)屬性類(lèi)型:離散屬性個(gè)數(shù):8捐獻(xiàn)日期:1997-06-01缺失值:不包含web 點(diǎn)擊量:2258930計(jì) 算 機(jī)與現(xiàn)代 化2012 年第 2 期圖 6 不同機(jī)器數(shù)的加速比圖 4 不同數(shù)據(jù)量的運(yùn)行時(shí)間由于切分?jǐn)?shù)據(jù)的 map 函數(shù)覆蓋了程序運(yùn)行的絕 大多數(shù)時(shí)間，其中決策樹(shù)一層的節(jié)點(diǎn)越多切分?jǐn)?shù)據(jù)的 時(shí)間就越長(zhǎng)，圖 5 是 1g 數(shù)據(jù)( 即 1 × 107 條數(shù)據(jù)) 在不 同層次的運(yùn)行時(shí)間。在圖 5 中，筆者發(fā)現(xiàn)在第 7 層的時(shí)候運(yùn)行時(shí)間達(dá) 到最

28、大，是因?yàn)榇藭r(shí)的節(jié)點(diǎn)數(shù)是最多的。從第一層開(kāi) 始每層的節(jié)點(diǎn)數(shù)分別為: 1、3、10、31、74、100、160、16、4。在圖 5 中可以看到隨著 slave 數(shù)的增加，各節(jié)點(diǎn)尤 其是第 7 層切分?jǐn)?shù)據(jù)的時(shí)間得到大幅度下降。所以 隨著屬性值個(gè)數(shù)的增加引起同一層次節(jié)點(diǎn)數(shù)的增加，可以通過(guò)動(dòng)態(tài)添加 slave 來(lái)提高算法的效率。因此本算法具有較高的可擴(kuò)展性。5結(jié)束語(yǔ)傳統(tǒng)的決策樹(shù)算法是內(nèi)存駐留算法，不能對(duì)海量數(shù)據(jù)進(jìn)行決策分類(lèi)。本文提出一種基于 mapreduce的大規(guī)模數(shù)據(jù)集決策樹(shù)生成的算法，并將其運(yùn)行在 hadoop 的云計(jì)算平臺(tái)上，通過(guò)實(shí)驗(yàn)和分析發(fā)現(xiàn)，該算 法對(duì)大規(guī)模數(shù)據(jù)分類(lèi)是高效可行的，具有較好的

29、擴(kuò)展 性，是可以處理大規(guī)模海量數(shù)據(jù)的。參考文獻(xiàn):1韓家煒，坎伯 數(shù)據(jù)挖掘概念與技術(shù)( 第 2 版) m 范明，孟小峰譯 北京: 機(jī)械工業(yè)出版社，2007kumar v the top ten algorithms in data miningj knowl- edge and information systems，2008，14( 1) : 1-37quinlan j r induction of decision treej machine learn- ing，1986，1( 1) : 81-106quinlan j r c45: programs for machine learnin

30、gm morgan kaufmann publisher，1993: 27-48shafer j，agrawal r，mehta m sprint: a scalable parallel classifier for data miningr research report ibm alma- den research center，san jose，california，1996: 544-555劉鵬 云計(jì)算m 北京: 電子工業(yè)出版社，2010 陳康，鄭緯民 云計(jì)算: 系統(tǒng)實(shí)例與研究現(xiàn)狀j 軟件 學(xué)報(bào)，2009，20( 5) : 1337-1348jeffrey d，sanjay g mapreduce: simplied data processing onlarge clustersc/ proceedings of the 6th sympesium on op- erating system design and implementation 2004: 137-150 ghemawat s，gobioff h，leun