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

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

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

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

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

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

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