決策樹CART以及剪枝
上一篇文章寫了C4.5和ID3，這一篇介紹另一種經常使用的決策樹CART，CART是後續學習GBDT，Xgboost須要用到的。函數
參考資料：學習
決策樹剪枝：https://blog.csdn.net/wjc1182511338/article/details/76793164?locationNum=6&fps=1spa
《統計學習方法》.net
決策樹學習資料：http://www.noobyard.com/article/p-wzskcvza-np.htmlcode
CART（classfication and regression tree）分類迴歸樹，既能夠用於分類也能夠用於迴歸，blog
CART假設決策樹是二叉樹（二叉樹，每一個結點至多有兩個子結點），左邊是「是」，右邊是「否」，這樣的決策樹至關於遞歸的二分每個特徵。遞歸
CART樹包括兩部分呢：樹的生成和樹的剪枝get
1.首先介紹樹的生成
CART用於分類用基尼係數最小化準則，用於迴歸是平方偏差最小化io
1.1迴歸樹的生成：
解釋一下：（1）中的切分變量j即特徵，選擇哪一個特徵進行切分，切分點s即切分的閾值，好比我選擇切分變量是個數（特徵），切分點是3（s），那麼大於3的是在區域，小於等於3的在一個區域，進行最小化選擇最優學習資料
1.2.分類樹：
首先介紹下基尼係數：
注意：注意看CART的中止條件
2 CART剪枝
CART剪枝包括兩部分，剪枝得到子樹序列，對子樹序列進行交叉驗證，選擇最優子樹。
在看CART剪枝前，其實你須要理解的是CART剪枝和ID3以及C4.5不一樣，CART剪枝是不知道α的
對於（3）是的理解，在計算總體的損失函數時，這個內部節點之外的值都沒變，只有這個內部節點的局部損失函數改變了，所以咱們本須要計算全局的損失函數，但如今只須要計算內部節點剪枝前和剪枝後的損失函數。換句話說由於剪枝的時候，對於剪枝那個結點，外部的偏差是不會變的，因此剪枝的時候僅僅考慮剪枝結點的子樹，若剪枝，那麼就剩下該結點爲根結點（對於的t），若是不剪枝（即Tt）
能夠看看以下公式理解一下
對於α，只要α 大於這個值時，必定有Cα(t)<Cα(Tt) ，也就是剪掉這個節點後都比不剪要更優。因此每一個最優子樹對應的是一個區間，在這個區間內都是最優的。
- 關於（3）中公式的理解，博主Mrtriste寫的很好，咱們能夠這麼理解，分母是葉子結點較少的數量，分子是偏差減少的數量，比值是偏差減少率，若是偏差減少率很小，那麼還不如不剪枝呢。
- 關於（3）中公式爲何剪去g(t)最小的Tt
g(t)表明每一個葉子節點帶來的偏差減少量，若是g(t)越小，也就是增長葉子帶來的偏差減少量越小，也就是增長這個葉子節點的做用越小，花那麼大的功夫增長葉子節點，偏差才減少那麼一點點，還不如不要，所以優先剪去g(t)最小的t
後面應該都比較好理解，關鍵是明白：在計算總體的損失函數時，這個內部節點之外的值都沒變，只有這個內部節點的局部損失函數改變了，所以咱們本須要計算全局的損失函數，但如今只須要計算內部節點剪枝前和剪枝後的損失函數。
在計算α時，結點t是常量。