決策樹的生成與剪枝

介紹決策樹的生成過程及算法。算法

關於決策樹的結點的特徵選擇依據：決策樹中結點的特徵選擇方法函數

1、ID三、C4.5決策樹生成算法測試

關鍵點：ID3依據結點上信息增益進行特徵選擇，C4.5依據結點上的信息增益比進行特徵選擇spa

算法：.net

輸入：訓練數據集D，特徵集A，閾值blog

輸出：ID三、C4.5算法決策樹 T遞歸

步驟：get

（先檢驗兩種極端狀況）博客

1.檢查D中全部數據標籤是否爲同一類，是同一類，T直接爲單節點樹，並將此類標記爲該結點的類標記並返回T。基礎

2.若,則T爲單結點樹，並將D中實例數最大的類做爲該結點的標記，返回T。

3.不然，按照特徵選擇方法中的信息增益(信息增益比)方法計算A中各特徵的信息增益(信息增益比)，選擇信息增益(比)最大的特徵，並檢測其增益(比)是否大於閾值。

4.對大於閾值的信息增益(比)特徵，對其每個可能的值將數據集D進行分割爲若干非空子集並構建子結點。

5.重複分割步驟，分割特徵不包括以前已經分割過的特徵，當分割後的信息增益(比)不大於閾值時，將此結點下的實例數最多的類做爲此結點的標記，構成一個葉結點。

2、ID三、C4.5決策樹剪枝算法

    直接生成的決策樹結構可能過於複雜(和閾值的大小也有關係)，此時可能出現過擬合的現象，解決這個問題的方法是對決策樹進行剪枝，對決策樹進行簡化。

    決策樹的剪枝每每經過極小化決策樹總體的損失函數或代價函數來實現。

    引入模型的複雜度懲罰項(相似於線性迴歸的正則化項)，損失函數能夠定義爲：

    加號前半部分表明模型對訓練數據的預測偏差，即模型與訓練數據的擬合程度H(T)爲結點上的經驗熵，經驗熵爲（所以剪枝是利用正則化的極大似然估計進行模型選擇），|T|表示模型複雜度，參數大小控制但願樹結構複雜程度。參數較大，樹相對簡單，參數較小，樹相對複雜。

    剪枝步驟：1.先將生成的決策樹上的每一個結點進行計算經驗熵

                        2.遞歸地從樹的葉節點向上回縮，回縮到父結點以前與以後的總體樹分別爲和，其對應的損失函數值爲：和，若是前者比後者小，則進行剪枝，將父結點變爲新的葉節點。

                           3.返回2，直至不能繼續爲止，獲得損失函數最小的子樹。

3、CART決策樹的生成算法

    關鍵點：CART決策樹能夠是分類樹也能夠是迴歸樹，而且CART樹是二叉樹，內部結點特徵取值爲是或否。CART迴歸樹特徵選擇時使用的是平方偏差最小化，CART分類決策樹特徵選擇時使用的是Gini指數最小化，關於Gini指數也在上面那篇博客中。

    迴歸樹的生成：

    輸入：訓練數據集D

    輸出：迴歸樹

    步驟：1.找尋最優切分變量j和掃描切分點s，找出(s,j)對使得下式最小:  對於c是分爲兩個子節點分別對應的全部子數據的標籤平均值，R一、R2分別對應兩結點上的數據集。

              2.用選定的(j,s)對劃分區域並決定相應的輸出值：

              3.繼續對兩個子區域調用步驟一、2，直至知足中止條件。

              4.最終將輸入空間劃分爲多個子空間，生成決策樹。

    分類樹的生成:

    輸入：訓練數據集D,中止計算的條件

    輸出：CART分類樹

    步驟：1.計算所有數據集的Gini指數：。此時，對每個特徵A，對其每一個可能的取值a，根據樣本點對A=a的測試是「是」或 「否」將D分爲和兩部分，並計算此時的基尼指數。

              2.在全部可能的特徵A以及全部可能的切分點a中，選擇基尼指數最小的特徵及其對應的切分點做爲最優特徵與最優切分點，並將數據集進行分配。

              3.對兩個子結點遞歸地調用一、2，直至知足中止條件。

              4.生成CART決策樹。

4、CART決策樹的剪枝

    在初始決策樹任意內部結點t，以t爲單結點樹的損失函數是 ,以t爲根節點的子樹的損失函數是： ,前面的損失函數表明的是把t下面的子樹均裁剪並把這個結點取出來當作只有一個結點的樹的損失函數，後面的損失函數表明的是在此結點沒剪枝時，把這個結點當作根節點的一個樹的損失函數。

    輸入：CART算法生成的決策樹T

    輸出：最優決策樹

    步驟：1.設k=0，

           2.自下而上地對各內部結點t計算以及(g(t)表明的是一個臨界的值，是當時的值，此時剪枝和不剪枝的損失函數大小相同)和。

                3.對的內部結點t進行剪枝，並對葉節點t以多數表決決定其類，獲得樹T.

                4.設

                5.若是不是由根節點及兩個葉節點構成的樹，則回到步驟2，不然

                6.採用交叉驗證法在子樹序列中選擇最優子樹。

注：在剪枝過程當中，實質上是不斷地增大值，產生新的區間。

對總體過程更爲直觀的理解，注意上面的幾個關鍵地方：

1.對樹的更新是建立一個新的子樹，並非對更新了的子樹賦值給樹帶回到步驟2，而回到步驟2的仍是完整的沒有任何剪枝樹。

2.由於是逐漸增大，因此開始爲0時，不會剪枝，由於太小，樹的結構複雜也對損失函數形成不了什麼影響，隨着的增大，會到達某一個臨界點，這個臨界點就是全部內部結點算出的g(t)中的最小的g(t)，咱們稱爲g(t0)，此時剪枝不剪枝損失相同，但爲告終構更加簡單(奧卡姆剃刀原理)，進行剪枝。

而後剪枝完了，獲得一顆子樹，並保存下來。以後恢復完整沒剪枝的樹回到步驟2裏面，而且由於是自下而上的，因此對上面剛剛剪枝的臨界值即g(t0)的基礎上增大,第二次剪枝的時候就完全不考慮g(t0)了，由於以前第一次剪枝的是全部裏面最小的，因此後面的確定比第一次的臨界大，所以知足了書中的不斷增長值。

而後再找一個g(t0)大的g(t1)，而且g(t1)比除了g(t0)的g(t)都小，因而這就是第二個剪枝的臨界點，找到g(t1)對應的結點，並在此進行剪枝，又獲得一棵子樹，而後再找比g(t0) g(t1)大但比其餘g(t)小的g(t2)，重複以前的過程，直到增大到剛好等於只剩初始完整樹的根節點加倆葉節點時的g(tn)，中止，並返回這個樹，增大也就結束了，也獲得了一系列樹。