幾個常用機器學(xué)習(xí)算法 - 決策樹算法

1 決策樹算法（Decision Tree）是從訓(xùn)練數(shù)據(jù)集中歸納出一組分類規(guī)則的過程。
實際操作中，與訓(xùn)練數(shù)據(jù)集不相矛盾的決策樹可能有多個，也可能一個都沒有；理想情況是找到一個與訓(xùn)練數(shù)據(jù)矛盾較小的決策樹，同時也具有良好的泛化能力。
2 決策樹結(jié)構(gòu)：
        有向邊
        節(jié)點
        -內(nèi)部節(jié)點： 數(shù)據(jù)的特征
        -葉節(jié)點：數(shù)據(jù)的類別
    決策樹準則：每個實例都被一條路徑覆蓋，且僅被一條路徑覆蓋
3 決策樹算法過程
    特征選擇
        決策樹生成過程就是劃分數(shù)據(jù)集的過程，合適地選取特征能幫助我們將數(shù)據(jù)集從無序數(shù)據(jù)組織為有序；
        有很多方法可以劃分數(shù)據(jù)集，決策樹算法根據(jù)信息論來度量信息；
        信息論中有很多概念，不同的決策樹生成算法使用不同的信息論概念來進行特征選擇。

    決策樹生成
        有諸如ID3, C4.5, CART等算法用于生成決策樹；

        ID3和CART4.5的差別在于用于特征選擇的度量的不同
        -ID3使用信息增益進行特征選擇
        -C4.5使用信息增益比進行特征選擇
        -以上兩個算法流程：迭代的尋找當前特征中最好的特征進行數(shù)據(jù)劃分，直到所有特征用盡或者劃分后的數(shù)據(jù)的熵足夠小。

            ID3核心思想：信息增益越大說明該特征對于減少樣本的不確定性程度的能力越大，也就代表這個特征越好。

            C4.5核心思想：某些情況（比如按照身份證號、信用卡號、學(xué)號對數(shù)據(jù)進行分類）構(gòu)造的樹層數(shù)太淺而分支又太多，而這樣的情況對數(shù)據(jù)的分類又往往沒有意義，所以引入信息增益比來對分支過多的情況進行適當“懲罰”。具體情景解釋可見這篇博客
        CART我還沒了解過，暫不介紹
4 決策樹生成算法得到的樹對訓(xùn)練數(shù)據(jù)的分類很準確，但對未知數(shù)據(jù)的分類卻沒那么準確，容易過擬合；因為決策樹考慮的特征太多，構(gòu)建得太復(fù)雜。
所以我們需要對決策樹進行剪枝：從已生成的樹上裁掉一些子樹或葉節(jié)點，并將其根節(jié)點或父節(jié)點作為新的葉節(jié)點，以此簡化樹。

剪枝算法很多，這里引入一種簡單的：極小化決策樹整體的損失函數(shù)。

設(shè)樹 T 的葉節(jié)點個數(shù)為 |T|, t 是樹 T 的葉節(jié)點，該葉節(jié)點有Nt
個樣本點，其中 k 類的樣本點有Ntk個， k = 1,2,…,k, Ht(T)是葉節(jié)點 t 上的經(jīng)驗熵，α≥0
為參數(shù)，決策樹的損失函數(shù)可定義如下


而經(jīng)驗熵為

其中，為了簡潔，令

所以，上面的損失函數(shù)可以記為

各個符號定義如下：

    C(T) 表示模型對訓(xùn)練數(shù)據(jù)的預(yù)測誤差，即擬合程度
    |T| 表示模型復(fù)雜度
    α
控制以上兩者之間的平衡
    當α
確定時，樹越大，與訓(xùn)練數(shù)據(jù)的擬合就越好，C(T)越小，但是樹的復(fù)雜度也會上升，|T| 上升；而樹越小，樹的復(fù)雜度就越低，|T| 越小，但往往和訓(xùn)練數(shù)據(jù)的擬合程度不好，C(T) 又會上升
較大的α
使得生成較簡單的樹，較小的α使得生成較復(fù)雜的樹，當α=0
        ，就完全不考慮樹的復(fù)雜度了，相當于不進行剪枝操作
        決策樹生成只考慮提高信息增益來更好擬合訓(xùn)練數(shù)據(jù)，但決策樹剪枝則通過優(yōu)化損失函數(shù)來減少樹的復(fù)雜度；可以說決策樹生成學(xué)習(xí)的是局部模型，而決策樹剪枝學(xué)習(xí)的是整體模型
剪枝算法流程
    計算每個節(jié)點的經(jīng)驗熵
    遞歸地從樹的葉節(jié)點向上回縮：設(shè)一組葉節(jié)點
    回縮到父節(jié)點前后的整體樹分別是TB
和TA，其對應(yīng)的損失函數(shù)值分別是Cα(TB)和Cα(TA)
，如果

那么將父節(jié)點變?yōu)樾碌娜~節(jié)點，即剪枝
重復(fù)執(zhí)行步驟2，直到不能再繼續(xù)為止，得到損失函數(shù)最小的子樹Tα
5
代碼部分，先挖個坑。。。過段時間回來填