決策樹算法

決策樹算法是一種逼近離散函式值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。

決策樹方法最早產生於上世紀60年代，到70年代末。由J Ross Quinlan提出了ID3算法，此算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5算法在ID3算法的基礎上進行了改進，對於預測變數的缺值處理、剪枝技術、派生規則等方面作了較大改進，既適合於分類問題，又適合於回歸問題。

決策樹算法構造決策樹來發現數據中蘊涵的分類規則．如何構造精度高、規模小的決策樹是決策樹算法的核心內容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用於數據分析處理的數據集。第二步，決策樹的剪枝：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預衡準確性的分枝剪除。

基本介紹

• 中文名：決策樹算法
• 釋義：一種典型的分類方法
• 典型算法：ID3，C4.5，CART
• 基本思想：樹以代表訓練樣本的單個結點開始

簡介

決策樹(decision tree)是一種基本的分類與回歸方法。決策樹模型呈樹形結構，在分類問題中，表示基於特徵對實例進行分類的過程。它可以認為是if-then規則的集合，也可以認為是定義在特徵空間與類空間上的條件機率分布。

其主要優點是模型具有可讀性，分類速度快。學習時，利用訓練數據，根據損失函式最小化的原則建立決策樹模型。預測時，對新的數據，利用決策樹模型進行分類。

決策樹學習通常包括3個步驟：特徵選擇、決策樹的生成和決策樹的修剪。

決策樹學習

目標：根據給定的訓練數據集構建一個決策樹模型，使它能夠對實例進行正確的分類。決策樹學習本質上是從訓練數據集中歸納出一組分類規則。能對訓練數據進行正確分類的決策樹可能有多個，可能沒有。在選擇決策樹時，應選擇一個與訓練數據矛盾較小的決策樹，同時具有很好的泛化能力；而且選擇的條件機率模型應該不僅對訓練數據有很好的擬合，而且對未知數據有很好的預測。

損失函式：通常是正則化的極大似然函式

策略：是以損失函式為目標函式的最小化

因為從所有可能的決策樹中選取最優決策樹是NP完全問題，所以現實中決策樹學習通常採用啟發式方法，近似求解這一最最佳化問題，得到的決策樹是次最優(sub-optimal)的。

決策樹學習的算法通常是一個遞歸地選擇最優特徵，並根據該特徵對訓練數據進行分割，使得對各個子數據集有一個最好的分類的過程。包含特徵選擇、決策樹的生成和決策樹的剪枝過程。

剪枝：

目的：將樹變得更簡單，從而使它具有更好的泛化能力。

步驟：去掉過於細分的葉結點，使其回退到父結點，甚至更高的結點，然後將父結點或更高的結點改為新的葉結點。

決策樹的生成對應模型的局部選擇，決策樹的剪枝對應於模型的全局選擇。決策樹的生成只考慮局部最優，決策樹的剪枝則考慮全局最優。

特徵選擇：

如果特徵數量很多，在決策樹學習開始時對特徵進行選擇，只留下對訓練數據有足夠分類能力的特徵。（例如把名字不作為一個特徵進行選擇）

典型算法

決策樹的典型算法有ID3，C4.5，CART等。

國際權威的學術組織，數據挖掘國際會議ICDM （the IEEE International Conference on Data Mining）在2006年12月評選出了數據挖掘領域的十大經典算法中，C4.5算法排名第一。C4.5算法是機器學習算法中的一種分類決策樹算法,其核心算法是ID3算法。C4.5算法產生的分類規則易於理解，準確率較高。不過在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，在實際套用中因而會導致算法的低效。

決策樹算法的優點如下：

（1）分類精度高；

（2）生成的模式簡單；

（3）對噪聲數據有很好的健壯性。

因而是目前套用最為廣泛的歸納推理算法之一，在數據挖掘中受到研究者的廣泛關注。

基本思想

1）樹以代表訓練樣本的單個結點開始。

2）如果樣本都在同一個類．則該結點成為樹葉，並用該類標記。

3）否則，算法選擇最有分類能力的屬性作為決策樹的當前結點．

4）根據當前決策結點屬性取值的不同，將訓練樣本數據集tlI分為若干子集，每個取值形成一個分枝，有幾個取值形成幾個分枝。勻針對上一步得到的一個子集，重複進行先前步驟，遞4'I形成每個劃分樣本上的決策樹。一旦一個屬性出現在一個結點上，就不必在該結點的任何後代考慮它。

5）遞歸劃分步驟僅當下列條件之一成立時停止：

①給定結點的所有樣本屬於同一類。

②沒有剩餘屬性可以用來進一步劃分樣本．在這種情況下．使用多數表決，將給定的結點轉換成樹葉，並以樣本中元組個數最多的類別作為類別標記，同時也可以存放該結點樣本的類別分布，

③如果某一分枝tc，沒有滿足該分支中已有分類的樣本，則以樣本的多數類創建一個樹葉。

構造方法

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

由於數據表示不當、有噪聲或者由於決策樹生成時產生重複的子樹等原因，都會造成產生的決策樹過大。因此，簡化決策樹是一個不可缺少的環節。尋找一棵最優決策樹，主要應解決以下3個最最佳化問題：①生成最少數目的葉子節點；②生成的每個葉子節點的深度最小；③生成的決策樹葉子節點最少且每個葉子節點的深度最小。

分類與回歸樹模型

同樣由特徵選擇、樹的生成及剪枝組成，既可以用於分類也可以用於回歸。

CART算法由以下兩步組成

（1）決策樹生成：基於訓練數據集生成決策樹，生成的決策樹要儘量大；

（2）決策樹剪枝：用驗證數據集對己生成的樹進行剪枝並選擇最優子樹，這時用損失函式最小作為剪枝的標準。