一、決策樹的生成算法

? ? ? ? 基本的決策樹生成算法主要有ID3和C4.5, 它們生成樹的過程大致相似，ID3是采用的信息增益作為特征選擇的度量，而C4.5采用信息增益比。構建過程如下：

從根節點開始，計算所有可能的特征的信息增益（信息增益比），選擇計算結果最大的特征。

根據算出的特征建立子節點，執行第一步，直到所有特征的信息增益（信息增益比）很小或者沒有特征可以選擇為止。

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

二、決策樹的剪枝

?? ? ? 決策樹對于訓練數據有很好的分類，但是對于未知測試集的分類并沒有那么準確，這就產生過擬合的現象。其實，原理都是一樣，決策樹的構建是直到沒有特征可選或者信息增益很小，這就導致構建的決策樹模型過于復雜，而復雜的模型是通過在訓練數據集上建立的，所以對于測試集往往造成分類的不準確，這就是過擬合。解決過擬合的方法是控制模型的復雜度，對于決策樹來說就是簡化模型，稱為剪枝。很形象的就是減掉樹中的一些節點。
? ? ? ? 決策樹的剪枝一般通過極小化損失函數或者代價函數來實現。

設樹T的葉節點的個數為|T|，t是樹T的葉節點，該葉節點上有Nt個樣本點，其中k類樣本點有Ntk個，k=1,2,…,K,Ht(T)為葉節點t上的經驗熵，α≥0為參數，則決策樹的損失函數可以定義為：

Cα(T)=∑t=1|T|NtHt(T)+α|T|(1)
其中，經驗熵為：
Ht(T)=?∑kNtkNtlogNtkNt(2)
將（1）式的第一項記為：
C(T)=∑t=1|T|NtHt(T)=?∑t=1|T|∑k=1KNtklogNtkNt
則：
Cα(T)=C(T)+α|T|(3)

C(T)表示模型對訓練數據的預測誤差，即擬合度。|T|表示模型的復雜度，參數α≥0控制兩者之間的影響。剪枝就是當α確定時，選擇損失函數最小的模型。子樹越大，數據擬合得越好，但是模型的復雜度越高；相反，字數越小，數據擬合較差，模型的復雜度較低。損失函數正好表示對兩者的平衡。

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

總結

以上是生活随笔為你收集整理的机器学习笔记（九）——决策树的生成与剪枝的全部內容，希望文章能夠幫你解決所遇到的問題。

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