決策樹 · 機器學習

> 通過本課掌握"決策樹"這種經典算法。 > 本課學習時長評估：6小時。 ## 決策樹定義決策樹是一種基本的分類與回歸方法。 * 是一種根據樣本為基礎的歸納學習，采用的是自頂而下的遞歸方法：開始數據都在根節點，遞歸的進行數據分片 * 通過剪枝的方法，防止過擬合 ## 決策樹使用場景 * 對未知數據進行分類 * 特征逐層向下，直到葉子節點，葉子節點的類型為預測類型 ## 決策樹的構造過程 * 特征選擇 * 樹生成，啟發函數：ID3、C4.5、CART * 剪枝 ## 下面計算過程使用的樣本數據 | 人 | 年齡 | 長相 | 工資 | 寫代碼 | 類別 | | --- | --- | --- | --- | --- | --- | | 小A | 老 | 帥 | 高 | 不會 | 不見 | | 小B | 年輕 | 一般 | 中等 | 會 | 見 | | 小C | 年輕 | 丑 | 高 | 不會 | 不見 | | 小D | 年輕 | 一般 | 高 | 會 | 見 | | 小L | 年輕 | 一般 | 低 | 不會 | 不見 | ## 樹生成過程中的啟發函數 ### 理解熵（entropy）熵（entropy）在統計學中是一個很重要的概念，是衡量信息量的度量單位，用于特征的選擇，衡量結果的不確定性，信息熵越小，結果越簡單。如果信息都是一個類別，那么熵就是0。 **信息熵的計算公式：** `$ H(D) = -\sum_{i=1}^{n}P_i\log_{2}{P_i} $` `$ P_i $`代表，第i份樣本出現的概率，小于1，所以`$ log_{2}{P_i} $`是小于0的，所以`$ \sum $`前面需要有負號。關于熵的更多講解，可以看這個視頻：[視頻鏈接](https://www.bilibili.com/video/BV1Hx411J7pW)。 ### ID3 最大信息增益 **對于樣本集合D，類別為K（不見/見），數據集D的經驗熵如下：** `$ H(D) = -\sum_{k=1}^{K}\frac{|C_k|}{|D|}\log_{2}{\frac{|C_k|}{|D|}} $` **特征A（比如年齡），對于數據集的經驗條件熵如下**： `$ H(D|A) = \sum_{i=1}^{n}H(D_i) $` 實際代表的意義，就是特征A的所有取值分類（比如老、年輕）：計算權重*經驗熵*，然后相加。 #### 第一步：計算經驗熵 `$ H(D) = -\frac{3}{5}\log_{2}{\frac{3}{5}}-\frac{2}{5}\log_{2}{\frac{2}{5}} = 0.971 $` #### 第二步：計算經驗條件熵 `$ H(D|年齡) = \frac{1}{5}H(老) + \frac{4}{5}H(年輕) = \frac{1}{5}(-0) + \frac{4}{5}\left (-\frac{2}{4}\log_{2}{\frac{2}{4}}-\frac{2}{4}\log_{2}{\frac{2}{4}}\right ) = 0.8 $` `$ H(D|長相) = \frac{1}{5}H(帥) + \frac{3}{5}H(一般) + \frac{1}{5}H(丑) = 0 + \frac{3}{5}\left (-\frac{2}{3}\log_{2}{\frac{2}{3}}-\frac{1}{3}\log_{2}{\frac{1}{3}}\right ) + 0 = 0.551 $` `$ H(D|工資) = \frac{3}{5}H(高) + \frac{1}{5}H(中等) + \frac{1}{5}H(低) = \frac{3}{5}\left (-\frac{2}{3}\log_{2}{\frac{2}{3}}-\frac{1}{3}\log_{2}{\frac{1}{3}}\right ) + 0 + 0 = 0.551 $` `$ H(D|寫代碼) = \frac{3}{5}H(不會) + \frac{2}{5}H(會) = \frac{3}{5}(0) + \frac{2}{5}(0) = 0 $` #### 第三步：計算信息增益 ??(??,年齡) = 0.171 ??(??,長相) = 0.42 ??(??,工資) = 0.42 ??(??,寫代碼) = 0.971 #### 第四步：計算結果分析特性"寫代碼"的信息增益最大，所以的樣本根據此特征，可以直接被分到葉節點（見或不見），完成決策樹的生長。當然，實際應用中，不回通過一個特性就完成構建，需要在經驗熵非0的類別中繼續生長，也不會無限生長，需要根據"預剪枝"決定何時停止生長。 #### ID3的缺陷 * 當某一個特征值的取值種類非常多時，對應每一個屬性取值的樣本子集，其分類的信息熵可能會變得很小，極端例子：DNA特性分割，分割后信息熵為0。 * 信息增益對屬性較多的特征有所偏好。以上，帶來的實際是過擬合問題。 ### C4.5 最大信息增益比信息增益比公式對value值多的情況進行的懲罰處理(盡管如此，還是要剪枝)。 **特征A對于數據集D的信息增益比定義為：** `$ g_R(D,A) = \frac{g(D,A)}{H_A(D)} $` **以上，分子是信息增益，分母成為數據集D關于A的取值熵，如下：** `$ H_A(D) = -\sum_{i=1}^{n}\frac{|D_i|}{|D|}\log_{2}{\frac{|D_i|}{|D|}} $` 特征A的取值越多，取值熵越大，也就是分母越大。 #### 第一步：計算取值熵 `$ H_{年齡}(D) = 0.722 $` `$ H_{長相}(D) = 1.371 $` `$ H_{工資}(D) = 1.371 $` `$ H_{寫代碼}(D) = 0.971 $` #### 第二步：計算信息增益比 `$ g_{R}(D,年齡) = 0.236 $` `$ g_{R}(D,長相) = 0.402 $` `$ g_{R}(D,工資) = 0.402 $` `$ g_{R}(D,寫代碼) = 1 $` #### 第三步：計算結果分析特征"年齡"對應的指標上升了，特性"長相"和"工資"有所下降。 ### CART 最大基尼指數(Gini) Gini描述的是數據的純度，與信息熵含義類似。 `$ Gini(D) = 1 - \sum_{k=1}^{n}\left(\frac{{C_k}}{|D|}\right )^{2} $` CART在每一次迭代中選擇Gini最小的"特征及其對應的切分點"進行分類。 CART是一顆二叉樹，每一步按照特征的取值切成兩份，進入**左右子樹**。 **特征A的Gini指數定義如下：** `$ Gini(D|A) = \sum_{i=1}^{n}Gini(D_i) $` 因為二分，以上i實際就兩個取值，分別代表：特征A的取值/非特征A的取值 #### 第一步：計算各個特征的Gini指數 `$ Gini(D|年齡=老) = \frac{1}{5}Gini(老) + \frac{4}{5}Gini(不老) = \frac{1}{5}\left(1-\frac{0}{1}^2 - \frac{1}{1}^2\right) + \frac{4}{5}\left(1-\frac{2}{4}^2 - \frac{2}{4}^2\right) = 0.4 $` `$ Gini(D|年齡=年輕) = 0.4 $` `$ Gini(D|長相=帥) = 0.4 $` `$ Gini(D|長相=丑) = 0.4 $` `$ Gini(D|長相=一般) = 0.27 $` `$ Gini(D|寫代碼=會) = 0 $` `$ Gini(D|寫代碼=不會) = 0 $` `$ Gini(D|工資=高) = 0.47 $` `$ Gini(D|工資=中等) = 0.3 $` `$ Gini(D|工資=低) = 0.4 $` #### 第二步：計算結果分析以上，我們可以發現"寫代碼"的Gini指數最小為0，因此選擇"寫代碼"作為最優特征，"寫代碼=會"為最優切分點。 ## 如何對決策樹進行剪枝一顆完全生長的決策樹會面臨一個很嚴重的問題，即過擬合。因此，需要對決策樹進行剪枝，剪掉一些枝葉，提升模型的泛化能力。通常的剪枝方法：Pre-Pruning、Post-Pruning ### 預剪枝(Pre-Pruning) 在決策樹的生成過程中，提前停止決策樹的生長。 **何時停止決策樹的生長：** * 當樹到達一定的深度時，停止樹的生長 * 當到達當前節點的樣本數量小于某個閾值時，停止樹的生長 * 計算每次分裂對測試集的準確度的提升，當小于某個閾值的時候，不再繼續擴展。 **預剪枝的特點：** * 思想直接、算法簡單、效率高，適合解決大規模問題 * 以上閾值，需要一定的經驗判斷 * 有欠擬合的風險。 ### 后剪枝(Post-Pruning) 在已生成的過擬合的決策樹上進行剪枝，得到簡化版的剪枝決策樹。 **常見的后剪枝方法：** * 錯誤率降低剪枝(Reduced Error Pruning, REP) * 悲觀剪枝(Pessimistic Error Pruning, PEP) * 代價復雜度剪枝(Cost Complexity Pruning, CCP) * 最小誤差剪枝(Minimum Error Pruning, MEP) * CVP(Critical Value Pruning) * OPP(Optimal Pruning) **代價復雜度剪枝(CCP)簡介：** * 從完整決策樹`$ T_0 $`開始，生成一個子樹序列{`$ T_0 $`,`$ T_1 $`...`$ T_n $`}，其中`$ T_{i+1} $`由`$ T_i $`生成，`$ T_n $`為樹的跟節點。 * 在子樹序列中，根據真實誤差選擇最佳的決策樹。 * 誤差增加率計算公式：`$ \alpha = \frac{R_{(t)} - R_{(T_t)}}{|L_{(T_t)}|-1} $`，分子：剪枝后的節點誤差-剪枝前的節點誤差，分母：子樹`$ T_t $`的葉子節點個數-1，每一步都選擇`$ \alpha $`最小的節點進行剪枝。 **后剪枝的特點：** * 通常可以得到泛化能力更強的決策樹 * 時間開銷會更大。 ## 學習資料 * 《百面機器學習》第3章-第3節 * [40分鐘搞懂機器學習算法系列 - 決策樹 /理論/實戰](https://www.bilibili.com/medialist/play/ml969336500)