一種用于大規模數據集的決策樹采樣策略

趙國強，王會進

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

隨著信息爆炸時代的到來，人們常常要面對海量的數據分析和處理任務，而且這些數據還在以幾何級數的速度增加。同時，在現實中這些海量數據往往是高維而稀疏的，且存在著大量的冗余。因而能對數據進行有效地采樣，且保持其準確率的處理方法成為人工智能、機器學習、數據挖掘等領域的重要研究課題之一。

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

本文提出一種結構化的采樣技術，運用現有決策樹算法對整個數據集生成決策樹，然后對生成的決策樹進行后加工，再基于生成的多個數據集進行隨機取樣，最后，整合取樣后的樣本生成目標樣本集。

1 決策樹算法

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

由于決策樹算法具有良好的預測性和易理解性，所以被廣泛研究和應用。目前，有許多好的決策樹算法，如ID3、C4.5[2]、CART[3]等。 ID3 算法 采用 貪心(即 非 回 溯 的)方法，決策樹以自頂向下遞歸的分治方法構造。通過對一個訓練集進行學習，生成一棵決策樹，訓練集中的每一個例子都組織成屬性-屬性值對的形式，例子的所有屬性都為離散屬性。而C4.5是由ID3演變來的，其核心思想是利用信息熵原理，使用信息增益率(Gain Ratio)的信息增益擴充，使用分裂信息(Split Information)值將信息增益規范化，遞歸地構造決策樹分支，完成決策樹。本文的實驗中生成預決策樹時將用該算法。CART(Classification And Regression Tree)算法采用一種二分遞歸分割的技術，將當前的樣本集分為兩個子樣本集，使得生成的決策樹的每個非葉子節點都有兩個分支。因此，CART算法生成的決策樹是結構簡潔的二叉樹。同時，CART算法考慮到每個節點都有成為葉子節點的可能，對每個節點都分配類別。分配類別的方法可以用當前節點中出現最多的類別，也可以參考當前節點的分類錯誤或者其他更復雜的方法。

當然也有一些非常好的針對大數據集的決策樹算法，如SPRINT、SLIQ等，然而由于生成的樹過于龐大，給理解它帶來了一定困難。雖然還有一些相關的剪枝技術，但其中也伴隨著由于過度剪枝而降低精確度的問題，使得其無法接近最優。

2 采樣方法

本文提出一種基于預生成決策樹的機構化的采樣方法。首先通過現有的任意一種快速的決策樹生成算法生成一棵決策樹；之后對生成的決策樹進行后加工，再基于生成的數據集進行隨機取樣；最后，整合取樣后的樣本集生成目標樣本。

具體算法是：首先對整個數據集采用一種快速的決策樹生成算法生成決策樹。然后采用廣度優先遍歷該生成樹，當遍歷的節點所包含的樣本量等于預定義的限制時終止，將遍歷過的節點所包含的樣本存于數據集Si(i=1～n)。如此反復，直到遍歷過所有節點為止。由此便產生了n個數據集，然后再隨機地從這n個數據集中隨機取樣本，其中每個集內所取樣本的數量K由以下公式決定：K=M×|Si|/|∑iSi|。其中 M表示目標樣本大小，|Si|表示數據集 Si中樣本的個數，|∑iSi|表示樣本總個數。最后再將隨機取得的所有樣本整合為目標樣本集。該算法采樣的過程如下所示：

(1)用現有決策樹算法對整個數據集建立決策樹。

(2)Do

Do

廣度優先算法遍歷生成樹；

從左到右整合兄弟節點；

While節點包含樣本的個數＜預定義限制；

將整合好的樣本存于集合Si；

i++；

While遍歷完所有節點；

(3)對每一個集合Si(i=1～n)進行大小為K的隨機采樣，其中 K=M×|Si|/|∑iSi|；

(4)整合(3)中采集得到的所有樣本生成目標樣本集。

3 實驗

選取UCI數據集[4]中的大型數據集“census-income”作為實驗對象。該數據集包括199 523個樣本，共包括41個屬性，其中8個是連續性的。同時對于連續屬性的樣本先做了離散化，以節省計算時間。

選用C4.5算法作為預先生成樹的算法，產生的樹共有1 821個節點，其中葉子節點為1 661個，錯誤率為0.042 8。其中在進行樹的廣度優先遍歷時的預定義的集合大小為30 000。得到的生成樹如下：

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

表1 隨機取樣10 000個的結果

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

隨機采樣的方法是在對較大規模的數據庫進行數據挖掘時常用的方法，然而由于決策樹生成算法是貪婪算法，其只能找出局部最優解，所以簡單的隨機采樣方法不能對準確率的提高起到作用。本文提供的新的采樣方法通過用現有決策樹快速生成預決策樹的方法，有效利用已生成的知識結構，再對預決策樹進行更加具有平衡性的采樣進而形成目標數據集。實驗證明，該采樣方法與隨機采樣方法相比，準確率有一定提高。

[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.