1、在信息時(shí)代的今天，數(shù)據(jù)庫(kù)中蘊(yùn)含著大量有價(jià)值的信息和知識(shí)。這些信息和知識(shí)廣泛適用于大量領(lǐng)域，包括商務(wù)管理、生產(chǎn)控制、市場(chǎng)分析、工程設(shè)計(jì)和科學(xué)探索等，可以為決策者做出正確的選擇提供有效的支持。然而這些潛在的信息和知識(shí)隱藏在數(shù)據(jù)的海洋中，沒(méi)有工具的幫助，人們很難甚至幾乎不可能發(fā)現(xiàn)它們。因此數(shù)據(jù)挖掘越來(lái)越重要。
　　至今，已經(jīng)有多種數(shù)據(jù)挖掘的方法，其中決策樹(shù)是一種重要的分類(lèi)和預(yù)測(cè)手段，它既能處理離散型數(shù)據(jù)，也能處理連續(xù)型數(shù)據(jù)，并且易于理解

2、。預(yù)測(cè)離散屬性值的樹(shù)模型叫做分類(lèi)樹(shù)，而預(yù)測(cè)連續(xù)屬性值的樹(shù)模型叫做回歸樹(shù)。決策樹(shù)方法主要包括樹(shù)的構(gòu)建即歸導(dǎo)和剪枝兩個(gè)方面。其中，樹(shù)的歸導(dǎo)既是重點(diǎn)也是難點(diǎn)所在，本文主要關(guān)注樹(shù)的歸導(dǎo)和并行化方面的問(wèn)題。
　　經(jīng)典的決策樹(shù)算法要求將整個(gè)訓(xùn)練集放入內(nèi)存，數(shù)據(jù)集增大時(shí)，算法便不能運(yùn)行，可規(guī)模性極差，這使得它不能用于現(xiàn)實(shí)世界的數(shù)據(jù)庫(kù)。SLIQ算法強(qiáng)調(diào)算法的可規(guī)模性，將數(shù)據(jù)集分成一個(gè)個(gè)屬性表駐留磁盤(pán)，從一定程度上減少了內(nèi)存的限制，但是它要求類(lèi)表全

3、部駐留內(nèi)存。SPRINT算法繼承了SLIQ的很多優(yōu)點(diǎn)，并且取消了類(lèi)表，完全消除了內(nèi)存的限制。并且SPRINT為并行而設(shè)計(jì)，并行性能也很優(yōu)秀。但SPRINT也有其不足，屬性表占用過(guò)多空間，建立哈希表耗費(fèi)不少的時(shí)間。雨林框架將算法的可擴(kuò)展性與算法的其他部分分離開(kāi)，將訓(xùn)練集壓縮成小得多的AVC-Group，再次提高了可擴(kuò)展性。
　　樹(shù)歸導(dǎo)過(guò)程中最重要也最難的一步是節(jié)點(diǎn)分割，包括尋找最佳分割準(zhǔn)則和根據(jù)此分割準(zhǔn)則劃分?jǐn)?shù)據(jù)集。本文對(duì)樹(shù)模型和樹(shù)

4、歸導(dǎo)進(jìn)行深入研究，對(duì)屬性的候選分割謂詞的選取作出了改進(jìn)，大量減少了需要評(píng)估的分割謂詞，從而節(jié)省了大量的計(jì)算時(shí)間。關(guān)于衡量分割質(zhì)量的指標(biāo)，對(duì)于分類(lèi)樹(shù)本文選擇GINI指數(shù)，對(duì)于回歸樹(shù)選擇計(jì)算方差的減少量。無(wú)論是GINI指數(shù)還是方差，目的都是要使分割前后數(shù)據(jù)集的不純度的減少量達(dá)到最大。
　　采用MapReduce編程框架來(lái)實(shí)現(xiàn)并行化的樹(shù)歸導(dǎo)。使用兩個(gè)隊(duì)列來(lái)存放待分割的節(jié)點(diǎn)，一個(gè)隊(duì)列存放數(shù)據(jù)集過(guò)大不能放入內(nèi)存的節(jié)點(diǎn)，另一個(gè)存放數(shù)據(jù)集能放入