數(shù)據(jù)挖掘中決策樹分類算法的研究

李如平

(安徽工商職業(yè)學院電子信息系，安徽合肥231100)

數(shù)據(jù)挖掘中決策樹分類算法的研究

李如平

(安徽工商職業(yè)學院電子信息系，安徽合肥231100)

決策樹方法是數(shù)據(jù)挖掘中一種重要的分類方法，決策樹是一個類似流程圖的樹型結構，其中樹的每個內部結點代表對一個屬性的測試，其分支代表測試的結果，而樹的每個葉結點代表一個類別。通過決策樹模型對一條記錄進行分類，就是通過按照模型中屬性測試結果從根到葉找到一條路徑，最后葉節(jié)點的屬性值就是該記錄的分類結果。

數(shù)據(jù)挖掘，分類，決策樹

近年來，隨著數(shù)據(jù)庫和數(shù)據(jù)倉庫技術的廣泛應用以及計算機技術的快速發(fā)展，人們利用信息技術搜集數(shù)據(jù)的能力大幅度提高，大量數(shù)據(jù)庫被用于商業(yè)管理、政府辦公、科學研究和工程開發(fā)等。面對海量的存儲數(shù)據(jù)，如何從中有效地發(fā)現(xiàn)有價值的信息或知識，是一項非常艱巨的任務。數(shù)據(jù)挖掘就是為了應對這種要求而產(chǎn)生并迅速發(fā)展起來的。數(shù)據(jù)挖掘就是從大型數(shù)據(jù)庫的數(shù)據(jù)中提取人們感興趣的知識，這些知識是隱含的、事先未知的潛在有用的信息，提取的知識表示為概念、規(guī)則、規(guī)律、模式等形式(姜靈敏等，2007)。

分類在數(shù)據(jù)挖掘中是一項非常重要的任務。分類的目的是學會一個分類函數(shù)或分類模型，把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某個類別。分類可用于預測，預測的目的是從歷史數(shù)據(jù)記錄中自動推導出對給定數(shù)據(jù)的趨勢描述，從而能對未來數(shù)據(jù)進行預測(趙翔，2005)。分類算法最知名的是決策樹方法，決策樹是用于分類的一種樹結構。

1 決策樹介紹

決策樹(decision tree)技術是用于分類和預測的主要技術，決策樹學習是一種典型的以實例為基礎的歸納學習算法，它著眼于從一組無次序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則(趙翔，2005)。它采用自頂向下的遞歸方式，在決策樹的內部節(jié)點進行屬性的比較，并根據(jù)不同屬性判斷從該節(jié)點向下的分支，在決策樹的葉節(jié)點得到結論。所以從根到葉節(jié)點就對應著一條合取規(guī)則，整棵樹就對應著一組析取表達式規(guī)則(張桂杰，2005)。

把決策樹當成一個布爾函數(shù)。函數(shù)的輸入為物體或情況的一切屬性(property)，輸出為”是”或“否”的決策值。在決策樹中，每個樹枝節(jié)點對應著一個有關某項屬性的測試，每個樹葉節(jié)點對應著一個布爾函數(shù)值，樹中的每個分支，代表測試屬性其中一個可能的值。

最為典型的決策樹學習系統(tǒng)是ID3，它起源于概念學習系統(tǒng)CLS，最后又演化為能處理連續(xù)屬性的C4.5(C5.0)等。它是一種指導的學習方法，該方法先根據(jù)訓練子集形成決策樹。如果該樹不能對所有給出的訓練子集正確分類，那么選擇一些其它的訓練子集加入到原來的子集中，重復該過程一直到時形成正確的決策集。當經(jīng)過一批訓練實例集的訓練產(chǎn)生一棵決策樹，決策樹可以根據(jù)屬性的取值對一個未知實例集進行分類。使用決策樹對實例進行分類的時候，由樹根開始對該對象的屬性逐漸測試其值，并且順著分支向下走，直至到達某個葉結點，此葉結點代表的類即為該對象所處的類。

決策樹是應用非常廣泛的分類方法，目前有多種決策樹方法，如 ID3，C4.5，PUBLIC，CART，CN2，SLIQ，SPRINT等。大多數(shù)已開發(fā)的決策樹是一種核心算法的變體，下面先介紹一下決策樹分類的基本思想決策樹構造與剪枝，然后詳細介紹ID3和C4.5算法及決策樹算法的分析及改進等。

2 決策樹構造與剪枝

決策樹分類算法通常分為兩個步驟，決策樹生成和決策樹剪枝。

2.1 決策樹構造

決策樹構造算法的輸入是一組帶有類別標記的例子，構造的結果是一棵二叉樹或多叉樹。二叉樹的內部結點(非葉子結點)一般表示為一個邏輯判斷，如形式為(ai=vi)的邏輯判斷，其中ai是屬性，vi是該屬性的某個值。樹的邊是邏輯判斷的分支結果。多叉樹的內部結點是屬性，邊是該屬性的所有取值，有幾個屬性值，就有幾條邊。樹的葉子結點都是類別標記。

構造決策樹的方法是采用自上而下的遞歸構造(毛國君等，2007)。以多叉樹為例，它的構造思路是，以代表訓練樣本的單個結點開始建樹，如果樣本都在同一個類，則將其作為葉子結點，節(jié)點內容即是該類別標記。否則，根據(jù)某種策略選擇一個屬性，按照屬性和各個取值，把例子集合劃分為若干子集合，使得每個子集上的所有例子在該屬性上具有同樣的屬性值。然后再依次遞歸處理各個子集。這種思路實際上就是“分而治之”的道理。二叉樹同理，差別僅在于要如何選擇好的邏輯判斷。

構造好的決策樹的關鍵在于如何選擇好的邏輯判斷或屬性。對于同樣的一組例子，可以有很多決策樹符合這組例子(朱明，2008)。研究結果表明，一般情況下，樹越小則樹的預測能力越強。要構造盡可能小的決策樹，關鍵在于選擇合適的產(chǎn)生分支的屬性。屬性選擇依賴于對各種例子子集的不純度(Impurity)度量方法。不純度度量方法包括信息增益(Information Gain)、信息增益比(Gain Ratio)、Gini-index、距離度量、x2統(tǒng)計、證據(jù)權重、最小描述長度等。不同的度量由不同的效果，特別是對于多值屬性，選擇合適的度量方法對于結果的影響是很大的。ID3，C4.5，C5.0算法使用信息增益的概念來構造決策樹，而CART算法x則使用Gini-index，其中每個分類的決定都與前面所選擇的目標分類相關。

2.2 決策樹的剪枝

數(shù)據(jù)挖掘的對象是現(xiàn)實世界的數(shù)據(jù)，這些數(shù)據(jù)一般不可能是完美的，可能某些屬性字段上缺值;可能缺少必須的數(shù)據(jù)而造成數(shù)據(jù)不完整;可能數(shù)據(jù)不準確、含有噪聲甚至是錯誤的，所以要討論噪聲問題?；镜臎Q策樹構造算法沒有考慮噪聲，生成的決策樹完全與訓練例子擬合。有噪聲情況下，完全擬合將導致過分擬合，即對訓練數(shù)據(jù)的完全擬合反而不具有很好的預測性能。剪枝是一種克服噪聲的技術，同時它也能使樹得到簡化而變得更容易理解。

1)兩種基本的剪枝策略。

①前期剪枝(Forward-Pruning)是在樹的生長過程完成前就進行剪枝(馬麗等，2008)。在樹的生長過程中，決定是繼續(xù)對不純的訓練子集進行劃分還是停機。

例如某些有效統(tǒng)計量達到某個預先設定的閾值時，節(jié)點不再繼續(xù)分裂，內部節(jié)點成為一個葉子節(jié)點。葉子節(jié)點取子集中頻率最大的類作為自己的標識，或者可能僅僅存儲這些實例的概率分布函數(shù)。前期剪枝會引起樹在不完全成熟之前停止工作，即樹可能在不應停止的時候而停止擴展，或稱之為horizon效應，而且，選取一個適當?shù)拈撝凳抢щy的。較高的閾值可能導致過分簡化的樹，而較低的閾值可能使樹簡化的太少。即使這樣，預先修剪對大規(guī)模的實際應用還是值得研究的，因為它相當高效。人們有望在未來的算法中解決horizon效應。

②)后期剪枝(Post-Pruning)是當決策樹的生長過程完成之后再進行剪枝(馬麗等，2008)。它是一種擬合-化簡(Fitting-and-simplifying)的兩階段方法(毛國君等，2007)。首先生成與訓練數(shù)據(jù)完全擬合的一棵決策樹，然后由下向上從樹的葉子開始剪枝，逐步向根的方向剪。剪枝時要用到一個測試數(shù)據(jù)集合，如果存在某個葉子剪去后測試集上的準確度或其它測度不降低(不變得更壞)，則剪去該葉子，否則停機。

如果節(jié)點的子樹不應按某種規(guī)則被修剪，則由下向上的評價規(guī)則將使該節(jié)點避免被按同一規(guī)則修剪。與此相對的是自上向下的策略，即從根開始依次修剪節(jié)點，直到無法修剪為止。這樣作的風險在于，按某種規(guī)則剪掉了某個節(jié)點，但其子類是不應按這一規(guī)則被剪掉的。

2)對樹進行修剪優(yōu)化時應遵循的原則。

①最小描述長度原則(MDL)(張桂杰，2005)。它的思想是最簡單的解釋是期望的，做法是對決策樹進行二進位編碼。編碼所需二進位最少的樹即為“最佳剪枝樹”。

②期望錯誤率最小原則(張桂杰，2005)。它的思想是選擇期望錯誤率最小的子樹剪枝，即對樹中的內部節(jié)點計算其剪枝/不剪枝可能出現(xiàn)的期望錯誤率，比較后加以取舍。

③奧卡姆剃刀原則。如無必要，勿增實體(朱明，2008)。即“在與觀察相容的理論中，應當選擇最簡單的一個”，決策樹越小就越容易被理解，其存儲與傳輸?shù)拇鷥r也就越小。

3 ID3算法

ID3算法是1986年Quinlan提出的一個著名決策樹生成方法，是目前引用率很高的一種算法。ID3算法是運用信息熵理論，選擇當前樣本集中最大信息增益的屬性值作為測試屬性;樣本集的劃分則依據(jù)測試屬性值進行，測試屬性有多少不同取值就將樣本集劃分為多少子樣本集，同時，決策樹上相應于該樣本集的節(jié)點長出新的葉子節(jié)點。由于決策樹的結構越簡單越能從本質的層次上概括事物的規(guī)律，期望非葉節(jié)點到達后代節(jié)點的平均路徑總是最短，即生成的決策樹的平均深度最小，這就要求在每個節(jié)點選擇好的劃分。系統(tǒng)的不確定性越小，信息的傳遞就越充分。ID3算法根據(jù)信息理論，采用劃分后樣本集的不確定性作為衡量劃分好壞的標準，用信息增益值度量:信息增益值越大，不確定性越小。因此，算法在每個非葉節(jié)點選擇信息增益最大的屬性作為測試屬性。

ID3算法將對挖掘樣本集分為訓練樣本集和測試樣本集，決策樹的構建是在對訓練樣本集的學習上產(chǎn)生的，決策樹生成之后，再運用測試樣本集對樹進行后剪技，將分類預測準確率不符合條件的葉節(jié)點剪去。

1)信息理論(Informaiton theory)和熵(Entropy)。信息論是C.E Shannon為解決信息傳遞(通信)過程問題而建立的理論，一個傳遞信息的系統(tǒng)是由發(fā)送端和接收端以及連接兩者的通道三者組成。熵是對事件對應的屬性的不確定性的度量。一個屬性的熵值越小、子集劃分的純度越高，熵值熵越大，它蘊含的不確定信息越大，約有利于數(shù)據(jù)的分類(張桂杰，2005)。

2)信息增益(Informmation Gain)。信息增益基于信息論中熵(Entropy)的概念，是指期望信息或者信息熵的有效減少量(通常用“字節(jié)”衡量)，根據(jù)它能夠確定在什么樣的層次上選擇什么樣的變量來分類(毛國君等，2007;朱明，2008)。ID3總是選擇具有最高信息增益(或最大熵)的屬性作為當前結點的測試屬性。該屬性使得對結果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機性或“不純性”。信息增益計算如下:

設S是s個訓練樣本數(shù)據(jù)集，S中類標識屬性具有m個不同值，定義m個不同類Ci(i=1，2，3…，m)。設si是類Ci中的樣本數(shù)。對一個給定的樣本分類所需的期望信息由下式得出:

其中pi是任意樣本屬于Ci的概率，一般可用si/s來估計。

設屬性A具有n 個不同值{a1，a2，…，an}，可以用屬性A將S劃分為n個子集{S1，S2，…，Sn}，其中Sj包含S中這樣一些樣本，它們在A上具有值aj。如果A作為測試屬性，則這些子集對應于由包含集合S的結點生長出來的分支。

設sij是子集Sj中類Ci的樣本數(shù)。根據(jù)由A劃分成子集的熵由下式給出:

根據(jù)上面的期望信息計算公式，對于給定的子集Sj，其期望信息由下式計算:

對屬性A作為決策分類屬性的度量值即信息增益可以由下面的公式得到:

3)ID3算法的分析。ID3通過不斷的循環(huán)處理，逐步求精決策樹，直至找到一個完全正確的決策樹。ID3算法構造的決策樹是從頂向下歸納形成了一組類似If…Then的規(guī)則。其最原始的程序只是用來區(qū)分象棋中的走步，所以區(qū)分的類別只有兩種，即真或假，其屬性值也是一些離散有限的值，頁今ID3算法已發(fā)展到允許多于兩個類別，而其屬性值可以是整數(shù)或實數(shù)。其優(yōu)缺點總結如下:

①優(yōu)點。ID3在選擇重要特征時利用了信息增益的概念，算法的基礎理論清晰，使得算法較簡單，該算法的計算時間是例子個數(shù)、特征個數(shù)、結點個數(shù)之積的線性函數(shù)。而且搜索空間是完全假設空間，目標函數(shù)必在搜索空間中，不存在無解的危險。全盤使用訓練數(shù)據(jù)，而不像候選剪除算法一個一個地考慮訓練例。這樣做的優(yōu)點是可以利用全部訓練例的統(tǒng)計性質進行決策，從而抵抗噪音。

②缺點。信息增益的計算依賴于特征值數(shù)目較多的特征，這樣不太合理，一個簡單的辦法對特征進行分解，可以把特征值統(tǒng)統(tǒng)化為二值特征。ID3對噪聲較為敏感。Quinlan定義訓練例子中的錯誤就是噪聲。它包括兩個方面，一是特征值取錯，二是類別給錯。當訓練集增加時，ID3的決策樹也會隨之變化。在建樹過程中各特征的信息增益隨例子的增加而變化，這對漸近學習不夠方便。

4 C4.5 算法

C4.5(Classsification 4.5)算法是 Quinlan 在1993年提出的，它既是ID3算法的后繼，也成為以后諸多算法的基礎。除了擁有ID3算法的功能外，C4.5算法引用了新的方法并增加了新的功能。在應用于單機的決策樹算法中，C4.5算法不僅分類準確率高而且速度快。

C4.5算法在ID3的基礎上增加了信息增益比例的概念和連續(xù)型屬性，屬性值空缺情況的處理，對樹剪枝也有了較成熟的方法，通過使用不同的修剪技術以避免樹的過度擬合，它克服了ID3在應用中的不足。首先用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向于選擇取值多的屬性的不足。其次，能夠完成對連續(xù)屬性的離散化處理，還能夠對不完整的數(shù)據(jù)進行處理。C4.5算法采用的知識表示形式為決策機構樹，并最終可以形成產(chǎn)生式規(guī)則。

1)信息增益比例的概念。信息增益比例是在信息增益概念基礎上發(fā)展起來的，一個屬性的信息增益比例用下面的公式給出:

這里設屬性A具有v個不同值{a1，a2，…，av}?？梢杂脤傩訟將S劃分為v個子集{S1，S2，S3}，其中Sj包含S中這樣一些樣本，它們在A上具有值aj。假如我們以屬性 A的值為基準對樣本進行分割，SplitI(A)就是前面熵的概念(毛國君等，2007;朱明，2008)。

2)合并具有連續(xù)值的屬性。ID3算法最初假定屬性離散值，但在實際應用中，很多屬性值是連續(xù)的。針對連續(xù)屬性值，C4.5首先根據(jù)屬性的值，對數(shù)據(jù)集排序，用不同的閾值將數(shù)據(jù)集動態(tài)地進行劃分，當輸入改變時，取兩個實際值中的中點作為一個閾值，取兩個劃分，所有樣本都在這兩個劃分中，得到所有可能的閾值、增益及增益比，在每一個屬性會變?yōu)閭z個取值，即小于閾值或大于等于閾值。

針對屬性有連續(xù)數(shù)值的情況，比如說A有連續(xù)的屬性值，則在訓練集中可以按升序方式排列a1，a2，…，am。如果 A共有 n種取值，則對每個取值vj(j=1，2，…，n)將所有的記錄進行劃分。這些記錄被劃分成為兩個部分:一部分在vj的范圍內，而另一部分則大于vj。針對每個劃分分別計算增益比率，選擇增益最大的劃分來對相應的屬性進行離散化。

3)規(guī)則的產(chǎn)生。一旦樹被建立，就可把樹轉化成If-Then規(guī)則。規(guī)則存儲于一個二維數(shù)組中，每一行代表樹中的一個規(guī)則，即從根到葉之間的一個路徑，表中的每列存放著樹中的結點。

5 決策樹分類算法的分析

基于決策樹的分類算法自提出至今，種類不下幾十種。各種算法在執(zhí)行速度、可擴展性、輸出結果的可理解性及分類預測的準確性等方面各有千秋。決策樹分類算法的發(fā)展可分為這樣幾個階段:首先，最早出現(xiàn)的ID3算法采用信息熵原理選擇測試屬性分割樣本集，只能處理具有離散型屬性和屬性值齊全的樣本，生成形如多叉樹的決策樹。后來出現(xiàn)的C4.5算法經(jīng)過改進，能夠直接處理連續(xù)型屬性，能夠處理屬性值空缺的訓練樣本。ID3系列算法和C4.5系列算法在對訓練樣本集的學習中盡可能多地挖掘信息，但其生成決策樹分枝較多，規(guī)模較大。為了簡化決策樹算法，提高生成的決策樹的效率，又出現(xiàn)了一些其它決策樹算法。

決策樹分類算法的優(yōu)點主要是能生成可以理解的規(guī)則，計算量相對來說不是很大，可以處理多種數(shù)據(jù)類型，決策樹可以清晰的顯示哪些屬性比較重要。與此同時它也存在一些缺點如對連續(xù)性的字段比較難預測，對有時間順序的數(shù)據(jù)，需要很多預處理的工作，當類別太多時，錯誤可能就會增加的比較快。

6 決策樹分類算法的改進

針對決策樹分類算法的缺點，下面將從屬性的選擇，如何對連續(xù)性屬性進行離散化等算法改進方面進行介紹。

1)屬性選擇。為了避免噪聲和干擾屬性對數(shù)據(jù)分類的影響，在建立決策樹之前先進行對屬性重要性排序，再用神經(jīng)網(wǎng)絡技術對其中最重要的若干屬性進行訓練并檢驗其預測精度，然后屬性重要性次序向兩端分別加減一個鄰近的屬性再進行訓練及檢驗并和原檢驗結果比較，這樣反復多次直到找到分類效果最佳的n個屬性為止，這樣得到n個分類效果最好的屬性。

2)連續(xù)屬性離散化。離散化是分類過程中處理連續(xù)性的一種有效方法。離散化的效率和有效性直接影響到后續(xù)機器學習算法的效率和性能。很多分類規(guī)則只能處理離散屬性，如ID3算法，對連續(xù)屬性進行離散化是一個必要的步驟。C4.5雖能夠處理連續(xù)屬性，但離散化也是系統(tǒng)集成的一個重要步驟。離散化不僅可以縮短推導分類器的時間，而且有助于提高數(shù)據(jù)的可理解性，得到解精度更高的分類規(guī)則。

從優(yōu)化的角度可以將離散化方法分為兩類:局部方法和全局方法。局部方法每次只對一個屬性進行離散，而全局方法同時對所有屬性進行離散。局部離散方法相對簡單，全局方法因為考慮了屬性間的相互作用往往可以得到比局部化方法更好的結果，但全局方法計算代價很高。

7 結束語

通過以上研究和分析，可以得出構造好的決策樹關鍵在于如何選擇好的邏輯判斷和屬性。隨著數(shù)據(jù)庫和數(shù)據(jù)倉庫技術的廣泛應用，數(shù)據(jù)的海量增加，決策樹技術的效率有待提高，針對實際問題時，需要對決策樹數(shù)據(jù)挖掘方法在適應性、容噪性等方面進行適當?shù)母倪M。

但小容，陳軒恕，劉飛，柳德偉.2009.數(shù)據(jù)挖掘中決策樹分類算法的研究與改進［J］.軟件導刊，8(2):41-43.

董賀，榮光怡.2008.數(shù)據(jù)挖掘中數(shù)據(jù)分類算法的比較分析［J］.吉林師范大學學報(自然科學版)，4:107-108.

姜靈敏，馬于濤.2007.信息資源聚合與數(shù)據(jù)挖掘［M］.廣州:華南理工大學出版社，12-18.

馬麗，陳桂芬.2008.基于數(shù)據(jù)挖掘的決策樹算法應用研究［J］.農(nóng)業(yè)網(wǎng)絡信息，11:45-47.

毛國君，段立娟，王實，石云.2007.數(shù)據(jù)挖掘原理與算法(第二版)［M］.北京:清華大學出版社，120-131.

張桂杰.2005.數(shù)據(jù)挖掘決策樹分類算法的研究與應用［D］.長春:長春理工大學.

趙翔.2005.數(shù)據(jù)挖掘中決策樹分類算法的研究［D］.鎮(zhèn)江:江蘇科技大學.

朱明.2008.數(shù)據(jù)挖掘(第2版)［M］.合肥:中國科學技術大學出版社，63-102.

Research of Decision Tree Classification Algorithm in Data Mining

LI Ru-ping
(Anhui Business Vocational College，Department of Electronic and Information，Hefei，AH 231100，China)

Decision tree algorithm is one of the most important classification measures in data mining.Decision tree classifier as one type of classifier is a flow-chart like tree structure，where each intenal node denotes a test on an attribute，each branch represents an outcome of the test，and each leaf node represents a class.The method that a decision tree model is used to classify a record is to find a path that from root to leaf by measuring the attributes test，and the attribute on the leaf is classification result.

data mining;classification;decision tree

TP311.13

A

1674-3504(2010)02-192-05

10.3969/j.issn.1674-3504.2010.02.015

2010-02-28

李如平(1973—)，男，安徽肥東人，講師，碩士，主要研究方向:計算機應用技術、信息管理。