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

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

　由表1、表2比較可知，新的采樣方法在生成樹(shù)的準(zhǔn)確率方面比C4.5算法和CART算法都有所提高，特別是對(duì)CART算法有較大的提高。
    隨機(jī)采樣的方法是在對(duì)較大規(guī)模的數(shù)據(jù)庫(kù)進(jìn)行數(shù)據(jù)挖掘時(shí)常用的方法，然而由于決策樹(shù)生成算法是貪婪算法，其只能找出局部最優(yōu)解，所以簡(jiǎn)單的隨機(jī)采樣方法不能對(duì)準(zhǔn)確率的提高起到作用。本文提供的新的采樣方法通過(guò)用現(xiàn)有決策樹(shù)快速生成預(yù)決策樹(shù)的方法，有效利用已生成的知識(shí)結(jié)構(gòu)，再對(duì)預(yù)決策樹(shù)進(jìn)行更加具有平衡性的采樣進(jìn)而形成目標(biāo)數(shù)據(jù)集。實(shí)驗(yàn)證明，該采樣方法與隨機(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.