一：思想：決策樹使用樣本的屬性作為結點，決策樹的跟結點一般是信息量最大的,然后遞歸的找到各個分支下子數據集中次大的決定性特征，直至子數據集中所有特征屬于同一類，如何從這么多的特征中選擇出有價值的，并且按照最好的順序由根到葉選擇。完成了這個我們也就可以遞歸構造一個決策樹了。

二：決策樹的學習過程，大致分為三步

???????? 1：特征選擇：指從訓練數據中眾多的特征中選擇一個特征作為當前節點的分裂標準，如何選擇特征有著很多不同量化評估標準標準，從而衍生出不同的決策樹算法。

? ? ? ? 2：決策樹生成： 根據選擇的特征評估標準，從上至下遞歸地生成子節點，直到數據集不可分則停止決策樹停止生長。 樹結構來說，遞歸結構是最容易理解的方式。

??????? 3：剪枝：決策樹容易過擬合，一般來需要剪枝，縮小樹結構規模、緩解過擬合。剪枝技術有預剪枝和后剪枝兩種。

三：基于信息論的三種決策樹算法

劃分數據集就是讓熵變的更小，從而使得數據的無序性減小，如果有8個特征，那每次選取哪一個作為劃分依據呢，因此我們需要采用量化的方法來判斷，量化方法很多，其中有一項就是“信息論度量信息”，基于信息論的決策樹算法有ID3，CART，C4.5等，其中CART，C4.5是從ID3衍生出來的。

四：ID3算法的思想：越是小型的決策樹越是優于大的決策樹，ID3是根據信息論的信息增益評估和特征選擇，每次選擇信息增益最大的模塊作為特征判斷模塊。

ID3算法可用于劃分標稱型數據集，沒有剪枝的過程，為了去除過度數據匹配的問題，可通過裁剪合并相鄰的無法產生大量信息增益的葉子節點（例如設置信息增益閥值）。使用信息增益的話其實是有一個缺點，那就是它偏向于具有大量值的屬性--就是說在訓練集中，某個屬性所取的不同值的個數越多，那么越有可能拿它來作為分裂屬性，而這樣做有時候是沒有意義的，另外ID3不能處理連續分布的數據特征，于是就有了C4.5算法。CART算法也支持連續分布的數據特征。

五：C4.5是ID3的一個改進算法，繼承了ID3算法的優點。C4.5算法用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足在樹構造過程中進行剪枝；能夠完成對連續屬性的離散化處理；能夠對不完整數據進行處理。C4.5算法產生的分類規則易于理解、準確率較高；但效率低，因樹構造過程中，需要對數據集進行多次的順序掃描和排序。也是因為必須多次數據集掃描，C4.5只適合于能夠駐留于內存的數據集。C4.5與ID3都是利用貪心算法進行求解，不同的是分類決策的依據不同。

信息增益比率度量是用ID3算法中的的增益度量Gain(D，X)和分裂信息度量SplitInformation(D，X)來共同定義的。分裂信息度量SplitInformation(D，X）就相當于特征X（取值為x₁，x₂，……，x_n，各自的概率為P₁，P₂，...，P_n，P_k就是樣本空間中特征X取值為x_k的數量除上該樣本空間總數）的熵。

信息熵，條件熵，互信息，信息增益等公式太簡單不寫出來了

SplitInformation(D，X） = -P₁ log₂(P₁)-P₂ log₂(P)-,...,-P_n log₂(P_n)

GainRatio(D,X) = Gain(D,X)/SplitInformation(D,X)

C4.5在處理連續數值特征時的步驟：

1：先把連續屬性轉換為離散屬性再進行處理。

2：對特征的取值進行升序排序

3：兩個特征取值之間的中點作為可能的分裂點，將DS分為兩部分，計算每一個分裂點的信息增益，優化時只計算分類屬性發生改變的

4：選擇修正后的信息增益最大的分裂點作為該特征的最佳分割點

5：計算最佳分裂點的信息增益率（Gain Ratio）作為特征的Gain Ratio。注意，此處需對最佳分裂點的信息增益進行修正：減去log2(N-1)/|D|（N是連續特征的取值個數，D是訓練數據數目，此修正的原因在于：當離散屬性和連續屬性并存時，C4.5算法傾向于選擇連續特征做最佳樹分裂點）

六：剪枝

分析分類回歸樹的遞歸建樹過程，不難發現它實質上存在著一個數據過度擬合問題。在決策樹構造時，由于訓練數據中的噪音或孤立點，許多分枝反映的是訓練數據中的異常，使用這樣的判定樹對類別未知的數據進行分類，分類的準確性不高。因此試圖檢測和減去這樣的分支，檢測和減去這些分支的過程被稱為樹剪枝。樹剪枝方法用于處理過分適應數據問題。通常，這種方法使用統計度量，減去最不可靠的分支，這將導致較快的分類，提高樹獨立于訓練數據正確分類的能力。

決策樹常用的剪枝常用的簡直方法有兩種：預剪枝(Pre-Pruning)和后剪枝(Post-Pruning)。預剪枝是根據一些原則及早的停止樹增長，如樹的深度達到用戶所要的深度、節點中樣本個數少于用戶指定個數、不純度指標下降的最大幅度小于用戶指定的幅度等。預剪枝的核心問題是如何事先指定樹的最大深度，如果設置的最大深度不恰當，那么將會導致過于限制樹的生長，使決策樹的表達式規則趨于一般，不能更好地對新數據集進行分類和預測。除了事先限定決策樹的最大深度之外，還有另外一個方法來實現預剪枝操作，那就是采用檢驗技術對當前結點對應的樣本集合進行檢驗，如果該樣本集合的樣本數量已小于事先指定的最小允許值，那么停止該結點的繼續生長，并將該結點變為葉子結點，否則可以繼續擴展該結點。

后剪枝則是通過在完全生長的樹上剪去分枝實現的，通過刪除節點的分支來剪去樹節點，可以使用的后剪枝方法有多種，比如：代價復雜性剪枝、最小誤差剪枝、悲觀誤差剪枝等等。后剪枝操作是一個邊修剪邊檢驗的過程，一般規則標準是：在決策樹的不斷剪枝操作過程中，將原樣本集合或新數據集合作為測試數據，檢驗決策樹對測試數據的預測精度，并計算出相應的錯誤率，如果剪掉某個子樹后的決策樹對測試數據的預測精度或其他測度不降低，那么剪掉該子樹。

總結

以上是生活随笔為你收集整理的决策树理论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。