決策樹算法

來自站酷網的圖片

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

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

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

簡介

決策樹(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算法產生的分類規則易於理解，準確率較高。不過在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，在實際應用中因而會導致算法的低效。