基于Hadoop的決策樹分類算法的并行化研究.pdf

1、隨著計算機(jī)和網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，數(shù)據(jù)呈爆炸式增長。大數(shù)據(jù)的有效存儲和處理成為各大企業(yè)當(dāng)前面臨的最艱巨的任務(wù)之一。如何高效、低成本的從海量數(shù)據(jù)中挖掘出潛在、有用的信息是數(shù)據(jù)挖掘技術(shù)當(dāng)前面臨的一大難題。
　　在數(shù)據(jù)挖掘算法中決策樹分類算法占有重要地位，決策樹分類算法被視為是一種重要的分類和預(yù)測手段。但傳統(tǒng)的決策樹分類算法為內(nèi)存駐留算法，在單機(jī)環(huán)境下，由于內(nèi)存的限制，只能處理小規(guī)模的數(shù)據(jù);其次，決策樹分類算法最耗時的階段為分割指標(biāo)的計算

2、階段;再者，決策樹的生成過程是一個遞歸過程，時間復(fù)雜度高。因此本文旨在解決傳統(tǒng)決策樹算法不能處理大規(guī)模數(shù)據(jù)的問題，以及如何高效的處理大規(guī)模數(shù)據(jù)的問題。
　　近來，云計算的出現(xiàn)，為數(shù)據(jù)挖掘技術(shù)的進(jìn)一步發(fā)展帶來了新的前景。因為云計算不僅具有海量存儲的能力，而且還提供并行處理的能力;其次，云計算系統(tǒng)可以構(gòu)建在普通的、廉價的PC機(jī)上，代替高性能計算機(jī)，大大降低了成本。因此，云計算的出現(xiàn)，使數(shù)據(jù)挖掘技術(shù)進(jìn)入了云挖掘的時代。
　　Had

3、oop是Apache基金會開發(fā)的一個分布式系統(tǒng)基礎(chǔ)框架，其中，HDFS分布式存儲文件系統(tǒng)和MapReduce分布式計算框架是Hadoop最重要的設(shè)計。其次，Hadoop使得用戶在進(jìn)行分布式程序開發(fā)的時候可以不用了解分布式的底層細(xì)節(jié)，并提供了一種高效、低成本、可擴(kuò)展的計算模式。本文通過分析算法本身的特點(diǎn)，結(jié)合MapReduce編程模式，將決策樹分類算法移植到Hadoop平臺上，從而實現(xiàn)了高效、低成本的數(shù)據(jù)挖掘工作。
　　本文的主要工

4、作如下:
　　(1)針對傳統(tǒng)的ID3決策樹分類算法不能處理大規(guī)模數(shù)據(jù)的問題，通過引入云計算的并行化思想，提出了一種基于Hadoop平臺的并行決策樹分類算法H_ ID3
　　H_ID3算法利用MapReduce編程模型，實現(xiàn)了數(shù)據(jù)集縱向劃分的并行化、橫向劃分的并行化以及決策樹同一層所有節(jié)點(diǎn)最佳分裂屬性選擇的并行化。通過算法的實現(xiàn)及相關(guān)實驗，驗證了算法的可行性，其次還可以得到如下結(jié)論:H_ID3算法能夠處理大規(guī)模的數(shù)據(jù)集，且具有

5、良好的可擴(kuò)展性和高加速比;其次，在處理的數(shù)據(jù)集規(guī)模較大時，H_ID3算法的效率明顯高于ID3算法。（第3章）
　　(2)針對傳統(tǒng)C4.5決策樹分類算法不能處理大規(guī)模數(shù)據(jù)的問題，提出了一種基于Hadoop平臺的決策樹分類算法H_C4.5
　　H_ C4.5算法和H_ID3算法的并行化思想大致相同，只是最佳分裂屬性的選擇標(biāo)準(zhǔn)不同。同樣，通過算法的實現(xiàn)及相關(guān)實驗，驗證了算法的可行性，以及H_C4.5算法具有的高效性、高擴(kuò)展性和高加

6、速比。（第4章）
　　(3)針對傳統(tǒng)CART決策樹分類算法不能處理大規(guī)模數(shù)據(jù)的問題，提出了一種基于Hadoop平臺的決策樹分類算法H_CART
　　H_ CART算法利用MapReduce模型，實現(xiàn)了對數(shù)據(jù)集的并行劃分，以及利用MapReduce本身具有的排序功能，實現(xiàn)對連續(xù)屬性值的并行化排序;其次，同樣也實現(xiàn)了決策樹同一層所有節(jié)點(diǎn)最佳分裂屬性的并行化計算，大大提高了算法效率。通過算法的實現(xiàn)和相關(guān)實驗，驗證了算法的可行性和H