機器學習筆記（九）——決策樹的生成與剪枝

1、決策樹的生成算法

        基本的決策樹生成算法主要有ID3和C4.5, 它們生成樹的過程大體類似，ID3是採用的信息增益做爲特徵選擇的度量，而C4.5採用信息增益比。構建過程以下：web

1. 從根節點開始，計算全部可能的特徵的信息增益（信息增益比），選擇計算結果最大的特徵。
2. 根據算出的特徵創建子節點，執行第一步，直到全部特徵的信息增益（信息增益比）很小或者沒有特徵能夠選擇爲止。

以上算法只有樹的生成，容易產生過擬合。算法

2、決策樹的剪枝

       決策樹對於訓練數據有很好的分類，可是對於未知測試集的分類並無那麼準確，這就產生過擬合的現象。其實，原理都是同樣，決策樹的構建是直到沒有特徵可選或者信息增益很小，這就致使構建的決策樹模型過於複雜，而複雜的模型是經過在訓練數據集上創建的，因此對於測試集每每形成分類的不許確，這就是過擬合。解決過擬合的方法是控制模型的複雜度，對於決策樹來講就是簡化模型，稱爲剪枝。很形象的就是減掉樹中的一些節點。
        決策樹的剪枝通常經過極小化損失函數或者代價函數來實現。svg

$設樹T的葉節點的個數爲|T|，t是樹T的葉節點，該葉節點上有N_t個樣本點，其中\\k類樣本點有N_{tk}個，k=1,2,\dots,K,H_t(T)爲葉節點t上的經驗熵，\alpha \ge 0 爲\\參數，則決策樹的損失函數能夠定義爲：$
函數

$$C_{\alpha}(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T| (1)$$
其中，經驗熵爲：
$$H_t(T)=-\sum_k\frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}(2)$$
將（1）式的第一項記爲：
$$C(T) = \sum_{t=1}^{|T|}N_tH_t(T) = -\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk} \log \frac{N_{tk}}{N_t}$$
則：
$$C_{\alpha}(T)=C(T)+\alpha|T| (3)$$

$C(T)$表示模型對訓練數據的預測偏差，即擬合度。$|T|$表示模型的複雜度，參數$\alpha \ge 0$控制二者之間的影響。剪枝就是當$\alpha$肯定時，選擇損失函數最小的模型。子樹越大，數據擬合得越好，可是模型的複雜度越高；相反，字數越小，數據擬合較差，模型的複雜度較低。損失函數正好表示對二者的平衡。測試

        從上述分析能夠看出，決策樹的生成算法的模型複雜度很高，很好的地擬合了訓練數據。須要重點提一下的是，（3）式定義的損失函數極小化等價於正則化的極大似然估計。atom