Decision tree(決策樹)
決策樹可以分為回歸樹或分類樹，決策樹容易overfitting。
常決策樹主要有三種實現，分別是ID3算法，CART算法和C4.5算法。
這邊我們用data science from scratch的例子來講講決策樹，首先我們有一組數據，這是來應徵者的應徵資料(feature特徵)及面試後是否被錄用(label標籤)。
我們想從過往數據經由特徵將它正確分類到各種標籤，未來依據特徵判斷是否錄用，在決策樹中我們會建立決策路徑來表示樹的結構。
我們如何建立決策路徑呢?首先會先決定一個問題，例如""它們的應徵職等是甚麼，那就是分成3種Junior、Mid、Senior""，然後將資料依問題劃分成不同群組，如果問完問題還沒不同群組中如果還有不同類別(錄用、不錄用)混再一起則再決定一個問題進行切分，直到所有群組都能各自被分為標籤(錄用、不錄用)為止。
樹中每個問題叫做決策節點(decision node)、被已分類的標籤叫做葉節點(leaf node)。
CART算法
CART決策樹的生成就是遞歸地構建二叉決策樹的過程，對回歸樹用平方誤差最小化準則，對分類樹用基尼指數最小化準則，進行特徵選擇，生成二叉樹。
CART是一種二分遞歸分割技術，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子結點都有兩個分支，因此CART算法生成的決策樹是結構簡潔的二叉樹。
由於CART構成的是一個二叉樹，它在每一步的決策時只能是「是」或者「否」，把數據分為兩部分。
在CART算法中主要分為兩個步驟：
- 將樣本遞歸劃分進行建樹
- 用驗證數據進行剪枝
- 離散型變量如何進行遞歸建立二叉樹？
選一個自變量，再選取的一個值，把維空間劃分為兩部分，對非連續變量來說屬性值的取值只有兩個，即等於該值或不等於該值。
ps. 如果特徵有多類別將割成多份各自分為"是某類"與"不是某類"。貪婪演算法會選擇不純度或亂度最小的劃分
首先我們要知道如何衡量劃分好壞，我們可以使用entropy(熵)或Gini(不純度)，不純度或亂度越低越好。
Gini(不純度)：假設我們有K個類，樣本點屬於第k個類的概率為
計算資料的不純度，=第k類在所有樣本中的總數(
) ／ 所有樣本數 (
)。
資料(D)樣本數切分後為()樣本數與(
)樣本數，A表示某切分法(例如以職等切分)，我們將切分後資料各自計算不純度後再各自乘以他們資料在總資料的比例，最後加總起來的值就為切分不純度。
而我們就是要找到切分後不純度為最小的A(切分方法)。
我們用phd(是否為博士)做切分來計算，先算D1(phd=yes)、D2(phd=no)
- 遞歸處理，將上面得到的兩部分按步驟(1)(2)重新選取一個屬性繼續劃分，直到把整個空間都劃分完。
- 連續型變量如何進行遞歸建立二叉樹？
我們希望劃分後的數據集盡的值可能是集中的，接近訓練樣本的y值(標籤)，所以我們對切分後的兩個集合做的y與切分數據的平均y值(c)做MSE，加總起來求最小值，平均值越集中loss越低。
- 遍歷變量
(特徵的中的一個連續值變量，例如身高)，對固定的切分變量
，選擇使式子最小的(
)。
是被劃分的後輸入空間(劃分後的資料集合)
是
中對應標籤的平均值。
- 用選定的對(
CART回歸樹的生成是一個貪心選擇最優分割點的過程，這種貪心策略在一定程度上使得最開始生成的CART樹具有很多缺點，這表現在樹容易將噪聲也擬合進去，出現過擬合，以及訓練容易陷入局部最優等。為此，需要在樹生成後進行一定的處理，這就是剪枝的目的。
剪枝
實際使用CART樹時，常常將訓練數據分為訓練集和剪枝的數據集
- 預剪枝(Pre-Pruning):
通過調整樹停止生長的策略，如提前終止樹生長（通過調整均方誤差下降的最小值實現）等可實現。 - 後剪枝(Post-Pruning):
將數據根據訓練好的樹模型將數據集遞歸地分割到葉子結點，然後考慮減去葉子和不剪去葉子兩種情況下數據集的均方誤差值，如果剪枝使得該值變小，則剪之，否則放棄。遍歷所有結點，剪去所有冗餘的枝條，就實現了後剪枝。
