一種用于大規(guī)模數(shù)據(jù)集的決策樹采樣策略

趙國(guó)強(qiáng)，王會(huì)進(jìn)

(暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院，廣東 廣州 510632)

隨著信息爆炸時(shí)代的到來，人們常常要面對(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)域的重要研究課題之一。

決策樹[1]算法由于其易于理解等特點(diǎn)被廣泛應(yīng)用于機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中。然而由于決策樹算法采用的是貪心策略，這就決定了其生成的決策樹只是局部最優(yōu)而非全局最優(yōu)。同時(shí)一個(gè)決策樹算法的成功在于生成基于給定的數(shù)據(jù)集下最高準(zhǔn)確率的生成樹。但是由于面對(duì)的數(shù)據(jù)集是海量的，所以如果簡(jiǎn)單地運(yùn)用決策樹生成算法，不僅需要大量的計(jì)算，而且無法保證低錯(cuò)誤率和低偏差。所以有必要在真正進(jìn)行挖掘前進(jìn)行數(shù)據(jù)采樣，以期有效地提高準(zhǔn)確率。

本文提出一種結(jié)構(gòu)化的采樣技術(shù)，運(yùn)用現(xiàn)有決策樹算法對(duì)整個(gè)數(shù)據(jù)集生成決策樹，然后對(duì)生成的決策樹進(jìn)行后加工，再基于生成的多個(gè)數(shù)據(jù)集進(jìn)行隨機(jī)取樣，最后，整合取樣后的樣本生成目標(biāo)樣本集。

1 決策樹算法

決策樹技術(shù)(Decision tree)是用于分類和決策的主要技術(shù)，決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)方法，通過一組無序、無規(guī)則的實(shí)例推理出決策樹表示形式的分類規(guī)則。決策樹是運(yùn)用于分類的一種類似于流程圖的樹結(jié)構(gòu)，其頂層節(jié)點(diǎn)是樹的根節(jié)點(diǎn)，每個(gè)分枝代表一個(gè)測(cè)試輸出，每個(gè)非葉子節(jié)點(diǎn)表示一個(gè)屬性的測(cè)試，每個(gè)葉節(jié)點(diǎn)代表一個(gè)類或一個(gè)類的分布。決策樹進(jìn)行分類主要有兩步：第一步是利用訓(xùn)練集建立一棵決策樹，建立決策樹模型；第二步是利用生成完畢的決策樹模型對(duì)未知數(shù)據(jù)進(jìn)行分類。

由于決策樹算法具有良好的預(yù)測(cè)性和易理解性，所以被廣泛研究和應(yīng)用。目前，有許多好的決策樹算法，如ID3、C4.5[2]、CART[3]等。 ID3 算法 采用 貪心(即 非 回 溯 的)方法，決策樹以自頂向下遞歸的分治方法構(gòu)造。通過對(duì)一個(gè)訓(xùn)練集進(jìn)行學(xué)習(xí)，生成一棵決策樹，訓(xùn)練集中的每一個(gè)例子都組織成屬性-屬性值對(duì)的形式，例子的所有屬性都為離散屬性。而C4.5是由ID3演變來的，其核心思想是利用信息熵原理，使用信息增益率(Gain Ratio)的信息增益擴(kuò)充，使用分裂信息(Split Information)值將信息增益規(guī)范化，遞歸地構(gòu)造決策樹分支，完成決策樹。本文的實(shí)驗(yàn)中生成預(yù)決策樹時(shí)將用該算法。CART(Classification And Regression Tree)算法采用一種二分遞歸分割的技術(shù)，將當(dāng)前的樣本集分為兩個(gè)子樣本集，使得生成的決策樹的每個(gè)非葉子節(jié)點(diǎn)都有兩個(gè)分支。因此，CART算法生成的決策樹是結(jié)構(gòu)簡(jiǎn)潔的二叉樹。同時(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ù)集的決策樹算法，如SPRINT、SLIQ等，然而由于生成的樹過于龐大，給理解它帶來了一定困難。雖然還有一些相關(guān)的剪枝技術(shù)，但其中也伴隨著由于過度剪枝而降低精確度的問題，使得其無法接近最優(yōu)。

2 采樣方法

本文提出一種基于預(yù)生成決策樹的機(jī)構(gòu)化的采樣方法。首先通過現(xiàn)有的任意一種快速的決策樹生成算法生成一棵決策樹；之后對(duì)生成的決策樹進(jìn)行后加工，再基于生成的數(shù)據(jù)集進(jìn)行隨機(jī)取樣；最后，整合取樣后的樣本集生成目標(biāo)樣本。

具體算法是：首先對(duì)整個(gè)數(shù)據(jù)集采用一種快速的決策樹生成算法生成決策樹。然后采用廣度優(yōu)先遍歷該生成樹，當(dāng)遍歷的節(jié)點(diǎn)所包含的樣本量等于預(yù)定義的限制時(shí)終止，將遍歷過的節(jié)點(diǎn)所包含的樣本存于數(shù)據(jù)集Si(i=1～n)。如此反復(fù)，直到遍歷過所有節(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)樣本集。該算法采樣的過程如下所示：

(1)用現(xiàn)有決策樹算法對(duì)整個(gè)數(shù)據(jù)集建立決策樹。

(2)Do

Do

廣度優(yōu)先算法遍歷生成樹；

從左到右整合兄弟節(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ù)先生成樹的算法，產(chǎn)生的樹共有1 821個(gè)節(jié)點(diǎn)，其中葉子節(jié)點(diǎn)為1 661個(gè)，錯(cuò)誤率為0.042 8。其中在進(jìn)行樹的廣度優(yōu)先遍歷時(shí)的預(yù)定義的集合大小為30 000。得到的生成樹如下：

采用常用的隨機(jī)采樣方法對(duì)數(shù)據(jù)集“census-income”進(jìn)行大小為10 000的采樣5次，之后采用經(jīng)典的決策樹算法C4.5、CART進(jìn)行決策樹的生成，其樹的規(guī)模及準(zhǔn)確率如表1所示。同時(shí)對(duì)該數(shù)據(jù)集合采用文中所提出的采樣方法進(jìn)行大小為10 000的采樣5次，并用決策樹算法C4.5、CART進(jìn)行決策樹的生成，其樹的規(guī)模及準(zhǔn)確率如表2所示。

表1 隨機(jī)取樣10 000個(gè)的結(jié)果

由表1、表2比較可知，新的采樣方法在生成樹的準(zhǔn)確率方面比C4.5算法和CART算法都有所提高，特別是對(duì)CART算法有較大的提高。

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