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

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

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

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

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

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

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