天天看點
傳回

cart算法_決策樹（二）ID3、C4.5算法，CART算法

cart算法_決策樹（二）ID3、C4.5算法，CART算法

Email：[email protected]

原創内容，轉載請标明，本文主要介紹CART的剪枝部分，其他内容比較簡單

參考：《統計學習方法》李航

一. ID3和C4.5算法

ID3算法的核心是在決策樹各個結點上應用資訊增益準則選擇特征

C4.5算法是應用資訊增益比來選擇特征

資訊增益的相關知識可參考我的另一篇文章，不過多闡述

黑夜不再來：決策樹（一）熵、條件熵、資訊增益​zhuanlan.zhihu.com

cart算法_決策樹（二）ID3、C4.5算法，CART算法
二.CART算法

CART生成分為回歸樹的生成和分類樹的生成，對回歸樹用平方誤差最小化準則，對分類樹用基尼指數最小化準則，進行特征選擇，生成二叉樹

  • 回歸樹生成

可參考下面這個部落格

https://blog.csdn.net/weixin_40604987/article/details/79296427​blog.csdn.net

選擇第j個變量x（j）和它取得值s，作為切分變量，将輸入空間切分為兩個區域，分别在兩個區域内求均值

cart算法_決策樹（二）ID3、C4.5算法，CART算法

然後再求平方誤差

cart算法_決策樹（二）ID3、C4.5算法，CART算法

尋找最小平方誤差的變量和切分值即可。

cart算法_決策樹（二）ID3、C4.5算法，CART算法
  • 分類樹生成

CART分類樹生成采用基尼指數選擇最優特征，同時決定該特征的最優二值切分點

cart算法_決策樹（二）ID3、C4.5算法，CART算法
cart算法_決策樹（二）ID3、C4.5算法，CART算法

CART剪枝

先參考《統計學習方法》

CART剪枝算法由兩步組成：首先從生成算法産生的決策樹

cart算法_決策樹（二）ID3、C4.5算法，CART算法

低端開始不斷剪枝，直到

cart算法_決策樹（二）ID3、C4.5算法，CART算法

的根節點，形成一個子樹序列

cart算法_決策樹（二）ID3、C4.5算法，CART算法

；然後通過交叉驗證法在獨立的驗證資料集上對子樹序列進行測試，從中選擇最優子樹。

這裡的關鍵就在于如何剪枝得到合适的子樹序列。

cart算法_決策樹（二）ID3、C4.5算法，CART算法
cart算法_決策樹（二）ID3、C4.5算法，CART算法

這是代價複雜度剪枝的核心思想

我們每次剪枝剪的都是某個内部節點的子節點，也就是将某個内部節點的所有子節點回退到這個内部節點裡，并将這個内部節點作為葉子節點。是以在計算整體的損失函數時，這個内部節點以外的值都沒變，隻有這個内部節點的局部損失函數改變了，是以我們本需要計算全局的損失函數，但現在隻需要計算内部節點剪枝前和剪枝後的損失函數。
cart算法_決策樹（二）ID3、C4.5算法，CART算法
cart算法_決策樹（二）ID3、C4.5算法，CART算法
cart算法_決策樹（二）ID3、C4.5算法，CART算法
cart算法_決策樹（二）ID3、C4.5算法，CART算法

課後習題5.4：

cart算法_決策樹（二）ID3、C4.5算法，CART算法
cart算法_決策樹（二）ID3、C4.5算法，CART算法
cart算法 id3決策樹
上一篇: cart算法_算法思想與硬核推導：決策樹（ID3/C4.5/CART）
下一篇: 資料挖掘算法學習（六）CART算法

繼續閱讀