上一章：機器學習03——線性模型
下一章：機器學習05——多分類學習與類別不平衡
機器學習實戰項目：【從 0 到 1 落地】機器學習實操項目目錄：覆蓋入門到進階，大學生就業 / 競賽必備

一、決策樹的基本流程

決策樹是一種基于“分而治之”思想的監督學習模型，通過遞歸劃分樣本構建樹狀結構，每個節點對應一個屬性測試，葉節點對應決策結果。

（一）核心原理

• 決策過程：從根節點開始，對樣本的某個屬性進行測試，根據測試結果進入相應子節點，重復此過程直至葉節點，得到決策結果。從根節點到葉節點的路徑對應一個判定規則序列。
• 終止條件：當滿足以下任一條件時，停止劃分并將當前節點標記為葉節點：
  1. 當前節點的所有樣本屬于同一類別；
  2. 屬性集為空，或所有樣本在剩余屬性上取值相同（此時標記為樣本數最多的類別）；
  3. 當前節點包含的樣本集為空（此時標記為父節點樣本數最多的類別）。
     

（二）生成算法

1. 輸入：訓練集$D=\{(x_1,y_1),...,(x_m,y_m)\}$和屬性集A={a1,...,ad}A=\{a_1,...,a_d\}A={a1?,...,ad?}；
2. 遞歸過程（函數TreeGenerate(D,A)）：
   • 生成當前節點，檢查是否滿足終止條件，若滿足則標記為葉節點并返回；
   • 否則從屬性集A中選擇最優劃分屬性$a^{?}$；
   • 對$a^{?}$的每個取值$a_v^{?}$，生成子節點，將D中取值為$a_v^{?}$的樣本子集$D_v$傳入子節點，遞歸調用TreeGenerate(Dv,A?{a?})(D_v, A-\{a^*\})(Dv?,A?{a?})。

二、劃分選擇（最優屬性的判定）

決策樹學習的關鍵是選擇最優劃分屬性，目標是使劃分后各子節點的樣本純度盡可能高。經典方法包括信息增益、增益率和基尼指數。

（一）信息增益（ID3算法）

• 信息熵：衡量樣本集純度的指標，對于包含$|\mathcal{Y}|$類樣本的集合D，第k類樣本占比為$p_k$，則信息熵為：
  $$Ent(D)=?\sum _{k=1}^{|\mathcal{Y}|}{p}_k{\log }_2{p}_k$$
  Ent(D)值越小，樣本集純度越高（如全為同一類時Ent(D)=0）。
• 信息增益：屬性a對D的劃分所帶來的信息熵減少量，計算公式為：
  $$Gain(D,a)=Ent(D)?\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$
  其中$D^v$是D中在屬性a上取值為$a^v$的樣本子集，V是屬性a的取值數。信息增益越大，說明該屬性劃分后樣本純度提升越明顯。
• 示例：在“好瓜”識別中，屬性“紋理”的信息增益（0.381）高于其他屬性，因此被選為根節點的劃分屬性。
• 局限：對取值數目多的屬性有偏好（如“編號”這類唯一標識屬性，信息增益通常極高，但無泛化意義）。
  

（二）增益率（C4.5算法）

為修正信息增益的偏好，引入增益率，定義為：
$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$
其中$IV(a)=?{\sum }_{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$為屬性a的“固有值”，取值越多的屬性，IV(a)越大，從而抑制高取值屬性的優勢。

• 啟發式策略：C4.5算法先篩選出信息增益高于平均水平的屬性，再從中選擇增益率最高的，平衡偏好問題。

（三）基尼指數（CART算法）

基尼指數衡量從樣本集中隨機抽取兩個樣本，其類別標記不同的概率，計算公式為：
$$Gini(D)=\sum _{k=1}^{|\mathcal{Y}|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}=1?\sum _{k=1}^{|\mathcal{Y}|}{p}_k^2$$
Gini(D)越小，樣本集純度越高。屬性a的基尼指數為劃分后各子節點基尼指數的加權和，選擇基尼指數最小的屬性作為劃分屬性。

三、剪枝處理（避免過擬合）

剪枝是決策樹對抗過擬合的核心手段，通過移除冗余分支，提升模型泛化能力。分為預剪枝和后剪枝。

（一）預剪枝

• 策略：在決策樹生成過程中，對每個節點先判斷劃分是否能提升泛化性能（通過驗證集精度評估），若不能則停止劃分，將當前節點標記為葉節點。
• 示例：對“好瓜”數據集的根節點，若不劃分（標記為“好瓜”），驗證集精度為42.9%；若用“臍部”劃分，精度提升至71.4%，則進行劃分；后續子節點若劃分不能提升精度，則停止。
• 優缺點：
  • 優點：減少訓練和測試時間開銷；
  • 缺點：可能因“貪心”策略錯過后續有效劃分，導致欠擬合。

（二）后剪枝

• 策略：先生成完整決策樹，再自底向上考察非葉節點，若將其子樹替換為葉節點能提升泛化性能，則剪枝。
• 示例：對完整決策樹的子節點，若替換為葉節點后驗證集精度從42.9%提升至更高，則剪枝；最終保留更多有效分支。
• 優缺點：
  • 優點：泛化性能通常優于預剪枝，保留更多有效分支；
  • 缺點：需生成完整樹后逐一考察，計算開銷大。

四、連續值與缺失值的處理

實際數據中常包含連續屬性（如“密度”“含糖率”）或缺失值，需特殊處理。

（一）連續值處理（二分法）

1. 候選劃分點：將連續屬性a的取值從小到大排序為$a^1,...,a^n$，取相鄰值的中位點作為候選劃分點：
   $$T_a=\left\{\frac{a^i+a^{i+1}}{2}\mid 1\le i\le n?1\right\}$$
2. 最優劃分點：計算每個候選點的信息增益，選擇增益最大的點作為劃分點，將樣本分為“≤t”和“>t”兩類。

• 示例：屬性“密度”的候選劃分點包括0.244、0.294等，通過計算信息增益選擇最優劃分點。
  

（二）缺失值處理

需解決兩個問題：如何選擇劃分屬性，以及如何劃分含缺失值的樣本。

1. 劃分屬性選擇：

   • 定義無缺失值樣本子集$\tilde{D}$，計算其占總樣本的比例$\rho$、各類別占比${\tilde{p}}_k$、屬性a各取值占比${\tilde{r}}_v$；
   • 信息增益修正為：$Gain(D,a)=\rho \times [Ent(\tilde{D})?{\sum }_{v=1}^V{\tilde{r}}_{v}Ent({\tilde{D}}^v)]$，其中$Ent(\tilde{D})=?{\sum }_k{\tilde{p}}_k{\log }_2{\tilde{p}}_k$。

2. 樣本劃分：

   • 若樣本在屬性a上取值已知，劃入對應子節點，權重不變；
   • 若取值缺失，按${\tilde{r}}_v$（屬性a取值$a^v$的比例）將樣本權重分配到各子節點（即$w_x\times {\tilde{r}}_v$）。

五、多變量決策樹

傳統決策樹（單變量）的非葉節點僅測試單個屬性，分類邊界與坐標軸平行；多變量決策樹的非葉節點是多個屬性的線性組合，分類邊界更靈活。

（一）核心特點

• 每個非葉節點對應一個線性分類器：${\sum }_{i=1}^d{w}_i{a}_i=t$，其中$w_i$是屬性$a_i$的權重，t是閾值，兩者通過樣本集學習得到。
• 優勢：能擬合復雜的分類邊界，減少決策樹深度，提升泛化能力。
• 示例：通過“-0.800×密度 -0.044×含糖量 < -0.313”這樣的線性組合劃分樣本，比單屬性劃分更精準。
  

六、經典決策樹算法與工具

• 算法：ID3（信息增益）、C4.5（增益率，支持連續值和缺失值）、C5.0（C4.5的改進版，效率更高）、CART（基尼指數，可用于分類和回歸）；
• 工具：J48（WEKA中C4.5的實現）等。

上一章：機器學習03——線性模型
下一章：機器學習05——多分類學習與類別不平衡
機器學習實戰項目：【從 0 到 1 落地】機器學習實操項目目錄：覆蓋入門到進階，大學生就業 / 競賽必備