決策樹——ID3、C4.5惧浴、CART

本篇開始總結一下以決策樹為基礎的模型实夹，當然本篇的內容就是決策樹了橄浓，決策樹可以用來分類也可以用來回歸，用作分類的應該更多一些亮航，我們也先從分類問題講起荸实。

1 決策樹思想

決策樹的分類思想很好理解，就是很多個if-then規(guī)則的集合缴淋，形成了一個從根結點出發(fā)的樹狀結構的模型准给，每一個if-then都對應著樹上的一個分支，如下圖是一個用來判斷是不是加班的決策樹示例宴猾，樹中的每個內部結點代表一個特征圆存，每個葉子結點代表一個類別：

看到這里我們程序員們可能會想，這個東西也能做成一個算法仇哆？我分分鐘寫100個if-else沦辙。試想，如果有成千上萬個特征呢讹剔，我們怎么知道這些特征判斷的順序怎么樣會比較高效油讯、準確呢详民？哪些特征可能根本沒什么用呢？哪些特征不做判斷更有利于模型的泛化呢陌兑？要解決這些問題沈跨，靠人工是很困難的，還是得用決策樹算法來操作兔综。

要實現(xiàn)上述特征選擇的功能有多種方法饿凛，我們知道，信息越多我們做出分類判斷的不確定性就越小软驰，這顯然是我們追求的目標涧窒，針對這一目標先后出現(xiàn)了多種決策樹算法。

2 決策樹ID3分類算法

決策樹ID3算法的核心是：使用信息增益在各個結點上選擇特征锭亏。
使用信息增益來選擇特征的思想就是：哪個特征的信息增益值最大纠吴，就認為其提供的信息的多，我們就選這個特征進行分支慧瘤。

1）信息增益（information gain）

信息增益表示得知特征 $X$ 的信息而使得類 $Y$ 的信息的不確定性減少的程度戴已。特征 $A$ 對訓練數(shù)據(jù)集 $D$ 的信息增益 $g(D,A)$ 定義為：集合 $D$ 的經(jīng)驗熵（香農(nóng)熵） $H(D)$ 與特征 $A$ 給定條件下 $D$ 的經(jīng)驗條件熵 $H(D|A)$ 之差，即

$g(D,A)=H(D)?H(D|A)$

這個差又稱為互信息锅减。信息增益大的特征具有更強的分類能力糖儡。

信息增益的計算：
輸入：訓練數(shù)據(jù)集 $D$ 和特征 $A$ ；
輸出：特征 $A$ 對訓練數(shù)據(jù)集 $D$ 的信息增益 $g(D,A)$
（1）計算數(shù)據(jù)集 $D$ 的經(jīng)驗熵 $H(D)$ 怔匣， $D$ 有 $K$ 個類別 $C_k$

$H(D)=?\sum_{k=1}^K\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$

def calc_shannon_ent(dataset):
    num_entires = len(dataset)                       #數(shù)據(jù)集總數(shù)
    label_counts = {}                                #保存每個Label（類別）出現(xiàn)次數(shù)
    for row in dataset: 
        current_label = row [-1]                     #提取Label信息
        label_counts[current_label] = label_counts.get(current_label,0)+1    #Label計數(shù)
    shannon_ent = 0.0                                #經(jīng)驗熵(香農(nóng)熵)
    for key in label_counts:    
        prob = float(label_counts[key]) / num_entires #該Label的概率
        shannon_ent -= prob * log(prob, 2)
    return shannon_ent

（2）計算特征 $A$ 對數(shù)據(jù)集 $D$ 的經(jīng)驗條件熵 $H(D|A)$ 休玩， $D_i$ 為特征 $A$ 的取值 $A_i$ 在 $D$ 中對應的子集
$H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)=?\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}$

def calc_cond_ent(dataset, fea_i, fea_i_vals):
    condition_ent = 0.0
    for value in fea_vals:
        sub_dataset = dataset[dataset[columns[fea_i]]==fea_i_vals]  # 假設數(shù)據(jù)集是一個DataFrame
        prob = len(sub_dataset ) / float(len(dataset))  # 極大似然估計概率
        conditionEnt += prob * calc_shannon_ent(sub_dataset )  # 條件熵的計算
    return condition_ent

（3）計算信息增益
$g(D,A)=H(D)?H(D|A)$

2）使用信息增益的決策樹ID3

決策樹ID3算法的過程為：

輸入：訓練數(shù)據(jù)集 $D$ ，每個樣本有 $n$ 個離散特征劫狠，特征集合為 $A$ ；
輸出：決策樹 $T$ 永部。

1 初始化信息增益的閾值 $?$ 独泞；

2 判斷樣本是否為同一類輸出 $C_k$ ，如果是則返回單節(jié)點樹 $T$ 苔埋，標記類別為 $C_k$ 懦砂；

3 判斷特征 $A$ 是否為空，如果是组橄，則返回單節(jié)點樹 $T$ 荞膘，標記類別為樣本中輸出類別 $D$ 中實例數(shù)最多的類別 $C_k$ ；

4 計算 $A$ 中的各個特征對輸出 $D$ 的信息增益（計算方法如上節(jié)所述）玉工，選擇信息增益最大的特征 $A_g$ 羽资；

5 如果 $A_g$ 的信息增益小于閾值 $?$ ，則返回單節(jié)點樹 $T$ 遵班，標記類別為樣本中輸出類別 $D$ 實例數(shù)最多的類別 $C_k$ 屠升；

6 否則，按特征 $A_g$ 的不同取值 $A_{gi}$ 將對應的樣本輸出 $D$ 分成不同的類別 $D_i$ 。每個類別產(chǎn)生一個子節(jié)點偏陪。對應特征值為 $A_{gi}$ 铡恕。返回增加了節(jié)點的數(shù) $T$ ；

7 對于所有的子節(jié)點脏答，令 $D=D_i,A=A?{A_g}$ 遞歸調用2-6步糕殉，得到子樹 $T_i$ 并返回。

在這個過程中殖告，如果達到了終止條件阿蝶，則生成過程結束（這也算是預剪枝了，可以防止過擬合）丛肮，得到最終的決策樹赡磅，其中，終止條件包括：

結點的數(shù)據(jù)樣本小于閾值（提前設定）宝与，因為數(shù)據(jù)量較少時焚廊，再做分裂容易強化噪聲數(shù)據(jù)的作用；二是降低樹生長的復雜性习劫，這樣有利于減少過擬合的風險咆瘟；
每個葉結點的數(shù)據(jù)樣本都只屬于一個分類，數(shù)據(jù)無法再分裂
樹的層數(shù)大于閾值（提前設定）诽里，同樣可以減小決策樹的復雜度袒餐，減少過擬合的風險。
所有特征已經(jīng)使用完畢谤狡，不能再繼續(xù)分裂灸眼；

3）決策樹ID3的缺點

根據(jù)以上過程就可以得到一個決策樹ID3算法模型，不過決策樹ID3算法存在一些不足之處墓懂，其缺點為：

采用信息增益焰宣，在相同條件下，取值多的特征傾向于比取值少的特征信息增益大（并不是一定有這個規(guī)律）捕仔，主要是因為特征的取值越多匕积，相當于對數(shù)據(jù)集的進一步細分，那么自然是消除了更多的數(shù)據(jù)的不確定性榜跌， $\frac{|D_{ik}|}{|D_i|}$ 可能越接近1闪唆，導致 $H(D|A)$ 越小，即信息增益越大钓葫；
只能處理離散型特征悄蕾，不能處理連續(xù)型特征，限制了其適用性础浮；
缺少對缺失值的處理笼吟；
容易產(chǎn)生過擬合库物。

3 決策樹C4.5分類算法

為了解決上述決策樹ID3算法的缺點，使用信息增益比來選擇特征的決策樹C4.5算法出現(xiàn)了贷帮。

1）信息增益比（information gain ratio）

特征 $A$ 對訓練數(shù)據(jù)集 $D$ 的信息增益比 $g_R(D,A)$ 定義為其信息增益 $g(D,A)$ 與訓練數(shù)據(jù)集 $D$ 關于特征 $A$ 的值的熵 $H_A(D)$ 之比戚揭，即

$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$

其中， $H_A(D)=?\sum_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$ 撵枢， $n$ 是特征 $A$ 取值的個數(shù)民晒。

顯然，信息增益比比信息增益多了一個 $H_A(D)$ 锄禽，特征的取值越多潜必， $H_A(D)$ 越大，這個規(guī)律與 $g(D,A)$ 相反沃但，所以信息增益比相當于抵消了信息增益對取值多特征的傾向性磁滚，也就優(yōu)化了ID3的缺點1。

2）使用信息增益比的決策樹C4.5

決策樹C4.5算法的過程為：

輸入：訓練數(shù)據(jù)集 $D$ 宵晚，每個樣本有 $n$ 個離散特征垂攘，特征集合為 $A$ ；
輸出：決策樹 $T$ 淤刃。

1 初始化信息增益的閾值 $?$ 晒他；

2 判斷樣本是否為同一類輸出 $C_k$ ，如果是則返回單節(jié)點樹 $T$ 逸贾，標記類別為 $C_k$ 陨仅；

3 判斷特征 $A$ 是否為空，如果是铝侵，則返回單節(jié)點樹 $T$ 灼伤，標記類別為樣本中輸出類別 $D$ 中實例數(shù)最多的類別 $C_k$ ；

4 計算 $A$ 中的各個特征對輸出 $D$ 的信息增益比（計算方法如上節(jié)所述）咪鲜，選擇信息增益比最大的特征 $A_g$ 饺蔑；

5 如果 $A_g$ 的信息增益小于閾值 $?$ ，則返回單節(jié)點樹 $T$ 嗜诀，標記類別為樣本中輸出類別 $D$ 實例數(shù)最多的類別 $C_k$ ；

6 否則孔祸，按特征 $A_g$ 的不同取值 $A_{gi}$ 將對應的樣本輸出 $D$ 分成不同的類別 $D_i$ 隆敢。每個類別產(chǎn)生一個子節(jié)點。對應特征值為 $A_{gi}$ 崔慧。返回增加了節(jié)點的數(shù) $T$ 拂蝎；

7 對于所有的子節(jié)點，令 $D=D_i,A=A?{A_g}$ 遞歸調用2-6步惶室，得到子樹 $T_i$ 并返回温自。

根據(jù)以上過程就可以得到一個決策樹C4.5算法模型玄货，看起來跟ID3的區(qū)別僅僅在于信息增益比，實際上還有一些對ID3缺點的特殊處理悼泌。

3）決策樹C4.5對連續(xù)特征松捉、缺失值的處理

（1）針對ID3缺點2不能處理連續(xù)型特征

C4.5使用二分法進行連續(xù)特征離散化，其特點在于離散化中的分類點不是隨便給的馆里，要選擇信息增益最大的點作為該連續(xù)特征的二元離散分類點隘世，比如在一系列連續(xù)值 $\left\{a_1,a_2,...,a_n\right\}$ 中取到的增益最大的點為 $a^*=\frac{a_4+a_5}{2}$ （取排序后的相鄰兩樣本值的平均數(shù)作為分類點），則小于 $a^*$ 的值為類別1鸠踪，大于 $a^*$ 的值為類別2丙者；

（2）針對缺點3缺少對缺失值的處理

C4.5從兩個方面對其進行處理：

訓練數(shù)據(jù)的特征值有缺失的情況下，如何選擇進行分裂的特征：C4.5的方案是對該有缺失值的特征营密，只使用其非缺失值的樣本子集進行判斷械媒，比如10個樣本 $D$ ，特征 $A$ 存在兩個缺失值评汰，那么就把這兩個樣本剔除纷捞，其他8個樣本組成樣本子集 $D'$ ，在 $D'$ 上按正常方法計算 $A$ 的信息增益键俱，乘0.8（無缺失值樣本所占比例）得到 $A$ 的信息增益 $Gain(D,A)=r\times Gain(D',A)$ 兰绣。
已確定了分裂特征 $A$ ， $A$ 存在缺失值编振，這些缺失值樣本分到哪個分支：C4.5的方案是將缺失值的樣本劃分到所有分支子結點中缀辩，然后為該樣本在不同的子結點中賦予不同的權重，這個權重大概就是概率的意思踪央，子結點中樣本數(shù)多的權重就大臀玄，例如 $A$ 有三個取值 $a_1,a_2,a_3$ ，樣本量分別為1,2,3畅蹂，則一個缺失值在這三個子結點中的權值分別為：1/6健无，2/6，3/6液斜。

4）決策樹C4.5的剪枝

針對缺點4容易產(chǎn)生過擬合問題累贤，C4.5引入了正則化系數(shù)進行初步的剪枝，控制樹的復雜度少漆。剪枝即把決策樹的分支剪掉來簡化模型臼膏，剪枝通過最小化決策樹的整體損失函數(shù)來實現(xiàn)，設決策樹 $T$ 的葉子結點數(shù)量為 $|T|$ 示损，決策樹的整體損失函數(shù)為：

$C_{\alpha}(T) = C(T) + \alpha |T|$

$C(T)$ 表示模型對訓練數(shù)據(jù)的預測誤差渗磅， $\alpha |T|$ 表示決策樹的復雜度（葉子結點越多越復雜）， $\alpha$ 用來控制二者的關系， $\alpha$ 越大始鱼，樹越簡單仔掸。

剪枝算法：

輸入：已經(jīng)生成的決策樹 $T$ ，參數(shù) $\alpha$
輸出：剪枝后的決策樹 $T_{\alpha}$

計算每個結點的經(jīng)驗熵医清；

遞歸的從樹的葉結點向上回縮起暮，如果回縮后的決策樹損失函數(shù)值變小，則進行剪枝——將父結點變?yōu)樽咏Y點状勤；

回到第二步鞋怀，繼續(xù)剪枝至得到損失最小的決策樹 $T_{\alpha}$ 。

5）決策樹C4.5的缺點

決策樹C4.5對ID3的缺點做了一定的改進持搜，不過其仍然存在一些不足：

只能用于分類密似，不能處理回歸問題；
C4.5生成的是多叉樹葫盼，計算效率不夠高残腌；
C4.5生成過程中有很多對數(shù)計算，計算效率不夠高贫导。

3 分類抛猫、回歸都行的決策樹CART

CART（Classification And Regression Tree），分類與回歸樹孩灯，顧名思義闺金，其既可以分類又可以回歸，好神奇呦峰档，它是最常用的決策樹算法败匹，CART同樣由特征選擇、樹的生成及剪枝組成讥巡，為了優(yōu)化C4.5的缺點掀亩，在分類問題中，CART使用基于基尼系數(shù)的特征選擇欢顷，并使用二叉樹的結構來簡化計算槽棍。

3.1 分類樹

1）基尼系數(shù)

基尼系數(shù)代表了數(shù)據(jù)集的不純度，特征分類后的數(shù)據(jù)集基尼系數(shù)越小抬驴，則不純度越低炼七，該特征分類效果越好。在分類問題中布持，假設數(shù)據(jù)集有 $K$ 個類別豌拙，第 $k$ 個類別的概率為 $p_k$ , 則基尼系數(shù)的表達式為：

$Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2$

可以通過下圖來理解基尼系數(shù)隨類別個數(shù)變化的關系，各個類別概率之和為1鳖链，每個類別的概率 $p_k$ 的平方相當于邊長為 $p_k$ 的正方形面積，類別越多，邊長為 $p_k$ 的正方形越多芙委，如下左圖所示逞敷，藍色區(qū)域面積越小，表示數(shù)據(jù)的不純度越高灌侣，當只有一個類別時藍色面積達到最大值1推捐，此時基尼系數(shù)為0，表示數(shù)據(jù)的不純度最低：

為了簡化問題侧啼，我們將決策樹的結構設定為二叉樹牛柒，即對任意特征來說，都只根據(jù)其取值將樣本劃分為兩個類別痊乾，對于樣本D皮壁，如果根據(jù)特征A的某個值a，把D分成D1和D2兩部分哪审，則在特征A的條件下蛾魄，D的基尼系數(shù)表達式為：

$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$

用基尼系數(shù)來判斷特征分裂能力的好壞，如果D1和D2兩部分都包含的類別數(shù)變少湿滓，即純度增加滴须，則基尼系數(shù)變小，所以 $Gini(D,A)$ 越小的特征越好叽奥，這其實跟使用信息熵是差不多的扔水，下圖可以發(fā)現(xiàn)，在二分類的計算中朝氓，基尼系數(shù)和熵之半的曲線非常接近（對熵進行一階泰勒展開可以發(fā)現(xiàn)二者的相似之處）魔市，基尼系數(shù)可以做為熵模型的一個近似替代：

二分類中基尼指數(shù)、熵之半膀篮、分類誤差率之間的關系

2）使用基尼系數(shù)的決策樹CART

決策樹CART的生成過程：

輸入：訓練集D嘹狞，終止條件（如基尼系數(shù)的閾值，樣本個數(shù)閾值）
輸出：CART決策樹 $T$

從根節(jié)點開始誓竿，用訓練集遞歸的建立CART樹磅网；

對于當前節(jié)點的數(shù)據(jù)集為 $D$ ，如果樣本個數(shù)小于閾值或者沒有特征筷屡，則返回決策子樹涧偷，當前節(jié)點停止遞歸；

計算樣本集 $D$ 的基尼系數(shù)毙死，如果基尼系數(shù)小于閾值燎潮，則返回決策樹子樹，當前節(jié)點停止遞歸扼倘；

計算當前節(jié)點現(xiàn)有的各個特征的各個特征值對數(shù)據(jù)集 $D$ 的基尼系數(shù)确封，對于離散值和連續(xù)值的處理方法和基尼系數(shù)的計算見第二節(jié)除呵。缺失值的處理方法和上篇的C4.5算法里描述的相同；

在計算出來的各個特征的各個特征值（與ID3爪喘、C4.5不同颜曾，他們不需要找最佳特征值）對數(shù)據(jù)集 $D$ 的基尼系數(shù)中，選擇基尼系數(shù)最小的特征 $A$ 和對應的特征值 $a$ 秉剑。根據(jù)這個最優(yōu)特征和最優(yōu)特征值泛豪，把數(shù)據(jù)集劃分成兩部分 $D1$ 和 $D2$ ，同時建立當前節(jié)點的左右節(jié)點侦鹏，做節(jié)點的數(shù)據(jù)子集為 $D1$ 诡曙，右節(jié)點的數(shù)據(jù)子集為 $D2$ ；

對左右的子節(jié)點遞歸的調用1-4步略水，生成決策樹价卤。

CART樹的生成效率高，一是因為選擇基尼系數(shù)作為分類標準聚请，主要是乘法荠雕，沒有對數(shù)運算，提高了計算效率驶赏；二是因為CART是二叉樹炸卑，簡化了決策樹結構。

還有一點區(qū)別是CART樹中的一特征可以在多處重復使用來分裂煤傍，而ID3和C4.5的離散特征只能使用一次盖文，C4.5的連續(xù)型特征可能使用多次，本質上來說這也不算什么區(qū)別蚯姆，只不過是樹的結構變成了二叉樹的結果五续，因為一個特征包含多種取值，在ID3和C4.5中因為是多叉樹龄恋，所以一次使用就已經(jīng)窮盡了這個特征的所有分類信息疙驾，即該特征已經(jīng)信息耗盡，如果再重復用他去分類是已經(jīng)沒有意義的了郭毕，而二叉樹的CART不同它碎，一次使用并不一定能將一個特征的信息用完，所以以后還可以重復使用显押，同理可以知道為什么C4.5的連續(xù)型特征可能使用多次扳肛，因為連續(xù)型特征在離散化的時候實際上是用的二分法，沒有將其信息用盡乘碑，所以以后還可以用挖息，所以是不是很好理解，并不是什么特別的設計兽肤。

3）決策樹CART的剪枝

我們已經(jīng)知道決策樹的整體損失函數(shù)：

$C_{\alpha}(T) = C(T) + \alpha |T|$

$\alpha$ 用來平衡經(jīng)驗損失和樹的復雜度套腹， $\alpha$ 越大绪抛，被剪掉的分支就越多，樹越簡單电禀，C4.5中我們把 $\alpha$ 當做參數(shù)來人工輸入睦疫，這顯然是還可以繼續(xù)優(yōu)化的，所以CART的剪枝過程有兩個問題需要解決：1鞭呕、怎么確定 $\alpha$ 來使得復雜度和擬合度達到最好的平衡？2宛官、把哪些分支剪掉葫松？

首先我們來思考一下 $\alpha$ 對樹的影響，舉個例子底洗，假設有個決策樹共4個葉子結點腋么，樹上有個分支包含兩個葉子結點，這個分支沒剪掉之前 $C(T)=0$ 亥揖，如果剪掉這個分支珊擂，經(jīng)驗損失升高 $C(T)=0.5$ ，現(xiàn)在我們從0開始來增大 $\alpha$ 费变，當 $\alpha=0.5$ 時摧扇，決策樹的整體損失 $C_{\alpha}(T)=0+0.5*4=2$ ，如果在此時減去這個分支得到子樹 $T_1$ 挚歧，決策樹的整體損失變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=C_%7B%5Calpha%7D(T_1)%3D0.5%2B0.5*3%3D2" alt="C_{\alpha}(T_1)=0.5+0.5*3=2" mathimg="1">扛稽，即剪枝前后整體損失相等，此時就是剪枝的臨界點滑负，如果不剪枝整體損失就大于剪枝的子樹了在张，當然，剪枝之后經(jīng)驗損失（誤差）也增大了矮慕， $\alpha$ 反映了誤差增大的大小帮匾，因此 $\alpha$ 被稱作“誤差增益”。如果繼續(xù)增大 $\alpha$ 痴鳄，發(fā)現(xiàn)到 $\alpha=1$ 時又需要剪枝了瘟斜，顯然 $T_1$ 是在 $\alpha$ 的區(qū)間 $[0.5,1)$ 中的最優(yōu)子樹，每個 $\alpha$ 可以通過下式計算：

$臨界點時：C_{\alpha}(T) = C(T) + \alpha |T|=C(T_1) + \alpha( |T|-1)$

$誤差增益：\alpha = \frac{C(T_1)-C(T)}{|T|-1}$

隨著 $\alpha$ 的不斷增大夏跷，我們會得到子樹序列 $T_0,T_1,T_2,...,T_n$ 哼转，每個 $T_{i}$ 剪去一個分支變成 $T_{i+1}$ ，如果我們從樹的角度來想的話槽华，就是每一個分支結點壹蔓，都對應著一個 $\alpha$ ，這個 $\alpha$ 就是將它剪去的劊子手猫态，所以我們實際操作中是根據(jù)每個結點計算 $\alpha$ 佣蓉，而不是真的通過增大 $\alpha$ 來得到子樹披摄，因為 $\alpha$ 作為連續(xù)數(shù)值要遍歷的話是不可能的。

在我們得到所有的子樹 $T_0,T_1,T_2,...,T_n$ 后勇凭，對每棵樹進行交叉驗證（即用測試集驗證）疚膊，結果最好的即為泛化能力最好的決策樹∠罕辏總結CART決策樹剪枝的過程：

輸入：CART算法生成的決策樹 $T_0$ 寓盗；
輸出：剪枝后的最優(yōu)決策樹 $T_{\alpha}$ 。

（1）設 $k=0,T=T_0$ 璧函；
（2）設 $\alpha=+\infty$ 傀蚌；
（3）自下而上對各內部結點 $t$ 計算 $C(T_t),|T_t|$ 以及

$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$

$\alpha=min(g(t),\alpha)$

式中， $T_t$ 表示已 $t$ 為根結點的子樹蘸吓， $C(T_t)$ 是其對訓練數(shù)據(jù)的預測誤差善炫， $|T_t|$ 是葉子結點個數(shù)；
（4）對 $g(t)=\alpha$ 的內部結點 $t$ 進行剪枝库继，并對葉結點 $t$ 用多數(shù)表決法確定其類別箩艺，得到樹 $T$ ；
（5）設 $k=k+1,\alpha_k=\alpha,T_k=T$ 宪萄；
（6）如果 $T_k$ 不是由根結點和兩個葉子結點構成的樹艺谆，則回到步驟（2）；否則令 $T_k=T_n$ 拜英。
（7）采用交叉驗證法在子樹序列 $T_0,T_1,T_2,...,T_n$ 中選取最優(yōu)子樹 $T_{\alpha}$ 擂涛。

分析一下這個過程，一開始設置 $\alpha$ 為無窮大聊记，然后計算所有內部節(jié)點的 $\alpha$ 撒妈，然后取一個最小的值，最小的 $\alpha$ 應該對應著最少的剪枝排监，保存剪枝后的樹 $T_0$ 狰右；剪枝后，全部結點的 $\alpha$ 都會變化舆床，此時重新計算所有的 $\alpha$ 棋蚌，重復上面的操作，這一次得到的最小的 $\alpha$ 會比之前的大挨队，一直重復這一套操作直到根節(jié)點結束谷暮。

不知道大家有沒有這個疑問，直接遍歷各種剪枝的可能不行嗎盛垦，這里計算并保存 $\alpha$ 有什么用呢湿弦？難道這樣按 $\alpha$ 從小到大剪枝會比遍歷的運算效率高嗎，搞不懂腾夯，我猜可能是最小的 $\alpha$ 沒準對應的不一定是第一層颊埃，可能是第二層第三層蔬充，如果這樣的話，那確實一下剪掉就提高了效率班利，純屬猜測饥漫，哪天有空了可以設計個決策樹試試看。罗标。庸队。

3.2 回歸樹

所謂回歸樹，就是其輸出不再是離散型的類別數(shù)據(jù)闯割，而是連續(xù)型的數(shù)值皿哨，回歸樹與分類樹的區(qū)別的根源也就在此，分類樹中的label是離散型的類別纽谒，所以我們使用信息熵啊、基尼系數(shù)啊來衡量被分開的兩波數(shù)據(jù)中類別數(shù)是不是變得更少如输，也就是所謂的數(shù)據(jù)更純粹鼓黔、信息更多；回歸樹的label是各種數(shù)值不见，這樣肯定就行不通啦澳化，我們需要衡量的是被分開的兩波數(shù)據(jù)是不是數(shù)值更相近了，也就是方差稳吮，所以回歸樹與分類樹的區(qū)別就是：1缎谷、數(shù)據(jù)分裂的評價指標不同；2灶似、最終預測結果的獲取方式不同（要把輸出歸一到一個數(shù)值上）列林。

數(shù)據(jù)分裂選擇特征的指標：特征 $A$ 中取值點 $s$ 將數(shù)據(jù)集劃分成數(shù)據(jù)子集 $D_1$ 和 $D_2$ ，使 $D_1$ 和 $D_2$ 的均方差分別最小酪惭，同時使 $D_1$ 和 $D_2$ 的均方差之和最小希痴，那么 $A$ 為分裂特征， $s$ 為分裂點春感，表達式為：

$\min_{A,s}[\min_{c_1}\sum\limits_{x_i \in D_1}(y_i - c_1)^2 + \min_{c_2}\sum\limits_{x_i \in D_2}(y_i - c_2)^2]$

其中砌创， $c_1$ 為 $D_1$ 數(shù)據(jù)集的樣本輸出均值， $c_2$ 為 $D_2$ 數(shù)據(jù)集的樣本輸出均值鲫懒。

預測結果的獲取方式：葉子結點中數(shù)據(jù)label的均值或者中位數(shù)嫩实。

除此之外，回歸樹的生成方式與分類樹一致窥岩。

4 決策樹總結

之前我們已經(jīng)知道了邏輯回歸甲献、SVM等多種分類算法，相比之下：

決策樹的思路簡單易懂颂翼，淺層的樹可解釋性很好竟纳，并且易于可視化撵溃，這種特點使得其頗受一些傳統(tǒng)行業(yè)的青睞；
同時锥累，決策樹對數(shù)據(jù)分布沒有假設缘挑，且可以處理離散型數(shù)據(jù)和連續(xù)型數(shù)據(jù)，而之前那幾種分類器顯然對連續(xù)型數(shù)據(jù)更友善桶略；
決策樹可以直接實現(xiàn)多分類语淘；
對批量數(shù)據(jù)預測速度比較快，因為CART二叉樹的結果际歼，其預測的時間復雜度為 $O(log_2N)$ 惶翻，其中 $N$ 為數(shù)據(jù)量。

決策樹還是有其局限性及缺點的鹅心，包括：

決策樹每次用一個特征分裂吕粗，容易忽略特征間的相互關聯(lián)，這個問題可以通過多變量決策樹來優(yōu)化旭愧；
決策樹容易發(fā)生過擬合颅筋，需要花很大功夫來調整其結構如剪枝等來控制；
決策樹容易因為樣本的小的變化而過分改變其結構输枯，使模型穩(wěn)定性和抗震蕩性差议泵，這個問題可使用集成模型來優(yōu)化；
對缺失值的處理不夠好等桃熄。

決策樹——ID3、C4.5尸折、CART

決策樹——ID3啰脚、C4.5、CART