摘  要： 為提高大規(guī)模數(shù)據(jù)集生成樹的準(zhǔn)確率，提出一種預(yù)生成一棵基于這個數(shù)據(jù)集的決策樹，采用廣度優(yōu)先遍歷將其劃分為滿足預(yù)定義的限制的數(shù)據(jù)集，再對各數(shù)據(jù)集按照一定比例進(jìn)行隨機(jī)采樣，最后將采樣結(jié)果整合為目標(biāo)數(shù)據(jù)集的數(shù)據(jù)采樣方法。通過對一UCI數(shù)據(jù)集進(jìn)行采樣，并用現(xiàn)有決策樹算法實驗證明，該采樣方法優(yōu)于傳統(tǒng)隨機(jī)采樣方法，基于該采樣方法的生成樹準(zhǔn)確率有所提高。
關(guān)鍵詞： 決策樹；樣本選取；廣度優(yōu)先遍歷

    隨著信息爆炸時代的到來，人們常常要面對海量的數(shù)據(jù)分析和處理任務(wù)，而且這些數(shù)據(jù)還在以幾何級數(shù)的速度增加。同時，在現(xiàn)實中這些海量數(shù)據(jù)往往是高維而稀疏的，且存在著大量的冗余。因而能對數(shù)據(jù)進(jìn)行有效地采樣，且保持其準(zhǔn)確率的處理方法成為人工智能、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域的重要研究課題之一。
    決策樹[1]算法由于其易于理解等特點被廣泛應(yīng)用于機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中。然而由于決策樹算法采用的是貪心策略，這就決定了其生成的決策樹只是局部最優(yōu)而非全局最優(yōu)。同時一個決策樹算法的成功在于生成基于給定的數(shù)據(jù)集下最高準(zhǔn)確率的生成樹。但是由于面對的數(shù)據(jù)集是海量的，所以如果簡單地運用決策樹生成算法，不僅需要大量的計算，而且無法保證低錯誤率和低偏差。所以有必要在真正進(jìn)行挖掘前進(jìn)行數(shù)據(jù)采樣，以期有效地提高準(zhǔn)確率。
    本文提出一種結(jié)構(gòu)化的采樣技術(shù)，運用現(xiàn)有決策樹算法對整個數(shù)據(jù)集生成決策樹，然后對生成的決策樹進(jìn)行后加工，再基于生成的多個數(shù)據(jù)集進(jìn)行隨機(jī)取樣，最后，整合取樣后的樣本生成目標(biāo)樣本集。
1 決策樹算法
    決策樹技術(shù)(Decision tree)是用于分類和決策的主要技術(shù)，決策樹學(xué)習(xí)是以實例為基礎(chǔ)的歸納學(xué)習(xí)方法，通過一組無序、無規(guī)則的實例推理出決策樹表示形式的分類規(guī)則。決策樹是運用于分類的一種類似于流程圖的樹結(jié)構(gòu)，其頂層節(jié)點是樹的根節(jié)點，每個分枝代表一個測試輸出，每個非葉子節(jié)點表示一個屬性的測試，每個葉節(jié)點代表一個類或一個類的分布。決策樹進(jìn)行分類主要有兩步：第一步是利用訓(xùn)練集建立一棵決策樹，建立決策樹模型；第二步是利用生成完畢的決策樹模型對未知數(shù)據(jù)進(jìn)行分類。
    由于決策樹算法具有良好的預(yù)測性和易理解性，所以被廣泛研究和應(yīng)用。目前，有許多好的決策樹算法，如ID3、C4.5[2]、CART[3]等。ID3算法采用貪心(即非回溯的)方法，決策樹以自頂向下遞歸的分治方法構(gòu)造。通過對一個訓(xùn)練集進(jìn)行學(xué)習(xí)，生成一棵決策樹，訓(xùn)練集中的每一個例子都組織成屬性-屬性值對的形式，例子的所有屬性都為離散屬性。而C4.5是由ID3演變來的，其核心思想是利用信息熵原理，使用信息增益率(Gain Ratio)的信息增益擴(kuò)充，使用分裂信息(Split Information)值將信息增益規(guī)范化，遞歸地構(gòu)造決策樹分支，完成決策樹。本文的實驗中生成預(yù)決策樹時將用該算法。CART(Classification And Regression Tree)算法采用一種二分遞歸分割的技術(shù)，將當(dāng)前的樣本集分為兩個子樣本集，使得生成的決策樹的每個非葉子節(jié)點都有兩個分支。因此，CART算法生成的決策樹是結(jié)構(gòu)簡潔的二叉樹。同時，CART算法考慮到每個節(jié)點都有成為葉子節(jié)點的可能，對每個節(jié)點都分配類別。分配類別的方法可以用當(dāng)前節(jié)點中出現(xiàn)最多的類別，也可以參考當(dāng)前節(jié)點的分類錯誤或者其他更復(fù)雜的方法。
    當(dāng)然也有一些非常好的針對大數(shù)據(jù)集的決策樹算法，如SPRINT、SLIQ等，然而由于生成的樹過于龐大，給理解它帶來了一定困難。雖然還有一些相關(guān)的剪枝技術(shù)，但其中也伴隨著由于過度剪枝而降低精確度的問題，使得其無法接近最優(yōu)。
2 采樣方法
   本文提出一種基于預(yù)生成決策樹的機(jī)構(gòu)化的采樣方法。首先通過現(xiàn)有的任意一種快速的決策樹生成算法生成一棵決策樹；之后對生成的決策樹進(jìn)行后加工，再基于生成的數(shù)據(jù)集進(jìn)行隨機(jī)取樣；最后，整合取樣后的樣本集生成目標(biāo)樣本。
    具體算法是：首先對整個數(shù)據(jù)集采用一種快速的決策樹生成算法生成決策樹。然后采用廣度優(yōu)先遍歷該生成樹，當(dāng)遍歷的節(jié)點所包含的樣本量等于預(yù)定義的限制時終止，將遍歷過的節(jié)點所包含的樣本存于數(shù)據(jù)集Si(i=1~n)。如此反復(fù)，直到遍歷過所有節(jié)點為止。由此便產(chǎn)生了n個數(shù)據(jù)集，然后再隨機(jī)地從這n個數(shù)據(jù)集中隨機(jī)取樣本，其中每個集內(nèi)所取樣本的數(shù)量K由以下公式?jīng)Q定：K=M×|Si|/|∑iSi|。其中M表示目標(biāo)樣本大小，|Si|表示數(shù)據(jù)集Si中樣本的個數(shù)，|∑iSi|表示樣本總個數(shù)。最后再將隨機(jī)取得的所有樣本整合為目標(biāo)樣本集。該算法采樣的過程如下所示：
    (1)用現(xiàn)有決策樹算法對整個數(shù)據(jù)集建立決策樹。
    (2)Do
         Do
         廣度優(yōu)先算法遍歷生成樹；
         從左到右整合兄弟節(jié)點；
         While節(jié)點包含樣本的個數(shù)<預(yù)定義限制；
    將整合好的樣本存于集合Si；
       i++；
       While遍歷完所有節(jié)點；
    (3)對每一個集合Si(i=1~n)進(jìn)行大小為K的隨機(jī)采樣，其中K=M×|Si|/|∑iSi|；
    (4)整合(3)中采集得到的所有樣本生成目標(biāo)樣本集。
3 實驗
    選取UCI數(shù)據(jù)集[4]中的大型數(shù)據(jù)集“census-income”作為實驗對象。該數(shù)據(jù)集包括199 523個樣本，共包括41個屬性，其中8個是連續(xù)性的。同時對于連續(xù)屬性的樣本先做了離散化，以節(jié)省計算時間。
選用C4.5算法作為預(yù)先生成樹的算法，產(chǎn)生的樹共有1 821個節(jié)點，其中葉子節(jié)點為1 661個，錯誤率為0.042 8。其中在進(jìn)行樹的廣度優(yōu)先遍歷時的預(yù)定義的集合大小為30 000。得到的生成樹如下：
    capital_gains=’(-∞~57 ]’
    |dividends_from_stocks=’(-∞~0.5 ]’
    | | weeks_worked_in_year=’(-∞~0.5 ]’：
    | | weeks_worked_in_year=’(0.5~51.5 ]’：
    | | weeks_worked_in_year=’(50.5~+∞ ]’
    | | | capital_losses=’(-∞~1881.5 ]’
    | | | | sex=Female：
    | | | | sex=Male：
    | | | capital_losses=’(1881.5~+∞ ]’
    | dividends_from_stocks=’(0.5~+∞ ]’
    capital_gains=’(57~+∞ ]’：
    采用常用的隨機(jī)采樣方法對數(shù)據(jù)集“census-income”進(jìn)行大小為10 000的采樣5次，之后采用經(jīng)典的決策樹算法C4.5、CART進(jìn)行決策樹的生成，其樹的規(guī)模及準(zhǔn)確率如表1所示。同時對該數(shù)據(jù)集合采用文中所提出的采樣方法進(jìn)行大小為10 000的采樣5次，并用決策樹算法C4.5、CART進(jìn)行決策樹的生成，其樹的規(guī)模及準(zhǔn)確率如表2所示。

　由表1、表2比較可知，新的采樣方法在生成樹的準(zhǔn)確率方面比C4.5算法和CART算法都有所提高，特別是對CART算法有較大的提高。
    隨機(jī)采樣的方法是在對較大規(guī)模的數(shù)據(jù)庫進(jìn)行數(shù)據(jù)挖掘時常用的方法，然而由于決策樹生成算法是貪婪算法，其只能找出局部最優(yōu)解，所以簡單的隨機(jī)采樣方法不能對準(zhǔn)確率的提高起到作用。本文提供的新的采樣方法通過用現(xiàn)有決策樹快速生成預(yù)決策樹的方法，有效利用已生成的知識結(jié)構(gòu)，再對預(yù)決策樹進(jìn)行更加具有平衡性的采樣進(jìn)而形成目標(biāo)數(shù)據(jù)集。實驗證明，該采樣方法與隨機(jī)采樣方法相比，準(zhǔn)確率有一定提高。
參考文獻(xiàn)
[1] QUINLAN， J R. Induction of decision tree[J]. Machine Learning， 1986，1(1)：81-106.
[2] QUINLAN， J R. C4.5： Programs for machine learning[R].Morgan Kaufmann Publishers， Inc.， 1993.
[3] MACHOVA， K. BARCAK， F. BEDNAR， P. A bagging method using decision trees in the role of base classifiers [J]. Acta Polytechnica Hungarica， 2006，3（2）： 121-132.
[4] NEWMAN D. UCI KDD Archive. [http：//kdd. ics. uci. edu]. Irvine， CA： University of California， Department of Information and Computer Science， 2005.