引言
在之前的兩節(jié)博文《混合和裝袋》和《自適應(yīng)提升》中，我們已經(jīng)有現(xiàn)成的一堆假設(shè)g在手中产阱，我們還如何將這些g混合起來江解，得到更好的分類器。
混合方式可以分為三種情況：
- 把g看做是同等地位脐彩，通過投票或者平均的方式將它們合起來碎乃，稱為Bagging
- g是不平等的，有好有壞惠奸，一個可行的做法是把g當成是特征的轉(zhuǎn)換梅誓，然后丟進線性模型訓(xùn)練就可以了，這稱為AdaBoost
- 如果是不同的條件下，使用不同的g梗掰，那么我們?nèi)匀豢梢詫當做是特征轉(zhuǎn)換嵌言，接下來使用一個非線性模型來得到最終的模型參數(shù)，這就是該文要介紹的決策樹算法
1. 決策樹的表達式
決策樹的表示方式可以有兩種形式及穗。
第一種是從路徑的角度（Path View）摧茴，將每個從根到葉子的路徑作為一個假設(shè)g，通過不同的條件組合得到最后的G(X)埂陆。
第二種是從遞歸的角度（Recursive View）苛白，父樹是由子樹遞歸定義的
tree=(root,sub-trees)。
2. CART決策樹算法
這里我們討論的決策樹算法以CART算法為例焚虱。
2.1 基本流程
- 從數(shù)據(jù)中看看如何做分支（branching criteria）
- 根據(jù)分支將數(shù)據(jù)分成幾塊
- 根據(jù)不同的數(shù)據(jù)學(xué)習(xí)子樹
- 得到最終的決策樹
所以购裙，上面進行決策樹學(xué)習(xí)的過程中需要考慮4個方面，分別是：分支的數(shù)量(number of branches)著摔、分支的判斷條件(branching criteria)缓窜、終止的條件(termination criteria)定续、基本的假設(shè)(base hypothesis)谍咆。
2.2 CART算法
分類回歸樹(CART,Classification And Regression Tree)算法采用一種二分遞歸分割的技術(shù)，將當前的樣本集分為兩個子樣本集私股，使得生成的的每個非葉子節(jié)點都有兩個分支摹察。
CART根據(jù)不同的條件，對數(shù)據(jù)進行切分倡鲸，到達葉子節(jié)點時供嚎，根據(jù)剩下的數(shù)據(jù)進行預(yù)測，輸出一個常數(shù)峭状。
2.3 純度
CART算法中每個節(jié)點（看做是一個決策樁decision stump）對數(shù)據(jù)進行切分克滴，如果分出來的數(shù)據(jù)的y都很接近（回歸問題）或者都一樣（分類問題），那么我們說這樣的數(shù)據(jù)是“純的”优床，這樣用標量對數(shù)據(jù)進行預(yù)測可以得到比較小的誤差劝赔。
我們通過上面的公式，來計算對于每一個節(jié)點的決策樁來說胆敞，分出來的兩份數(shù)據(jù)的純度是怎樣的着帽。該公式通過計算數(shù)據(jù)集Di（i=1 or 2）的純度并根據(jù)數(shù)據(jù)集的數(shù)量對其進行加權(quán)，其加權(quán)的意義是如果數(shù)據(jù)集的數(shù)量比較大的話移层，那個純度對其比較重要仍翰，反之，就不那么重要观话。
CART通過分出的兩部分數(shù)據(jù)綜合起來的純度對決策樁進行選擇予借，選擇“最純”的分割方式作為當前的分支。
2.4 計算純度的函數(shù)
我們可以將分割出來的數(shù)據(jù)和回傳的常數(shù)的誤差作為評價純度的方法，利用數(shù)據(jù)的y和回傳的y_ba的均方誤差來評價回歸問題的純度灵迫；利用0/1誤差函數(shù)來評價分類問題的純度喧笔。
如果是分類問題，我們還可以使用一個別的方法龟再。通過基尼不純度來度量分類問題的純度問題书闸。
2.5 終止條件
CART中有兩種被迫終止的情況，分別是：當yn都一樣利凑，這時不純度為0浆劲，于是可以得到gt(x)=yn；另一種情況是xn都一樣哀澈，就沒有繼續(xù)分割的可能了牌借。
CART樹長到被迫停下來的情況，稱為完全長成的樹（fully-grown tree）割按。
下面是CART算法完整流程：
CART剪枝算法
一棵完全長成的樹的訓(xùn)練誤差為0Ein(G)=0膨报，這會有過擬合的危險，在每一個節(jié)點上的數(shù)據(jù)越來越少适荣，導(dǎo)致擬合到這些節(jié)點的數(shù)據(jù)可能是過擬合的现柠。
所以，我們需要一個正則化的機制弛矛，來控制模型復(fù)雜度够吩，讓模型不那么容易出現(xiàn)過擬合現(xiàn)象。
CART剪枝算法從完全生長的決策樹的底端剪去一些子樹丈氓，使決策樹變簡單周循，從而能夠?qū)ξ粗獢?shù)據(jù)有更準確的預(yù)測。
上圖告訴我們使用葉子的數(shù)目作為正則項（regularizer）万俗，最終得到一個正則化的決策樹湾笛。
關(guān)于剪枝的具體做法時：
- 首先得到完全長成的樹作為G(0)；
- 然后試圖摘掉一片葉子闰歪，將所有摘掉一片葉子后的樹計算Ein嚎研，將最小的那棵摘掉一片葉子的數(shù)作為G(1)；
- 如此這般课竣，得到摘掉兩片葉子的最優(yōu)樹G(2)嘉赎，這樣不斷剪枝，直到根結(jié)點于樟，形成一個子樹序列公条；
- 最終對這個子樹序列使用
argmin Ein(G)+λΩ(G)來得到最后的輸出。
參考資料
機器學(xué)習(xí)技法課程迂曲，林軒田靶橱，臺灣大學(xué)
CART: 分類與回歸樹
轉(zhuǎn)載請注明作者Jason Ding及其出處
GitCafe博客主頁(http://jasonding1354.gitcafe.io/)
Github博客主頁(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡書主頁(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354進入我的博客主頁
