决策树算法：三大核心流程解析

        决策树分类树是一种监督学习算法，通过递归地将数据集划分为更纯的子集来构建树形结构。每个内部节点代表一个特征测试，分支代表测试结果，叶节点代表最终的分类结果。常用于解决分类问题，如垃圾邮件识别、决策分类树有三种算法，分别是ID3,C4.5,和CART.

决策树算法具体计算过程

🔍 案例数据集：银行贷款决策

🌳 一. ID3算法计算过程（基于信息熵）

步骤1：计算整体信息熵

• 类别分布：批准(9)，拒绝(6)
• 整体信息熵：

  H(D) = -[P(批准)log₂P(批准) + P(拒绝)log₂P(拒绝)]= -[9/15 * log₂(9/15) + 6/15 * log₂(6/15)]= -[0.6 * log₂(0.6) + 0.4 * log₂(0.4)]= -[0.6*(-0.737) + 0.4*(-1.322)]= -[-0.442 - 0.529]= 0.971

步骤2：计算各特征的信息增益

​​（1）按"年龄"分裂：​​

• 青年(5)：批准(2)，拒绝(3) → H(青年)= -[0.4log₂0.4 + 0.6log₂0.6]=0.971
• 中年(5)：批准(3)，拒绝(2) → H(中年)= -[0.6log₂0.6 + 0.4log₂0.4]=0.971
• 老年(5)：批准(5)，拒绝(0) → H(老年)=0
• 年龄条件熵：

  H(D|年龄) = (5/15)*0.971 + (5/15)*0.971 + (5/15)*0 = 0.647

• 年龄信息增益：

  Gain(年龄) = H(D) - H(D|年龄) = 0.971 - 0.647 = 0.324

​​（2）按"有工作"分裂：​​

• 有工作(5)：批准(5)，拒绝(0) → H(有工作)=0
• 无工作(10)：批准(4)，拒绝(6) → H(无工作)= -[0.4log₂0.4 + 0.6log₂0.6]=0.971
• 有工作条件熵：

  H(D|有工作) = (5/15)*0 + (10/15)*0.971 = 0.647

• 有工作信息增益：

  Gain(有工作) = 0.971 - 0.647 = 0.324

​​（3）按"有房"分裂：​​

• 有房(6)：批准(6)，拒绝(0) → H(有房)=0
• 无房(9)：批准(3)，拒绝(6) → H(无房)= -[1/3 log₂(1/3) + 2/3 log₂(2/3)]=0.918
• 有房条件熵：

  H(D|有房) = (6/15)*0 + (9/15)*0.918 = 0.551

• 有房信息增益：

  Gain(有房) = 0.971 - 0.551 = 0.420

步骤3：选择信息增益最大的特征

✅ ​根节点分裂：选择"有房"特征​

 二 C4.5核心步骤：计算信息增益率

1. 计算整体信息熵（同ID3）

• 批准(9)，拒绝(6)
• H(D) = 0.971（计算过程见ID3部分）

2. 计算各特征的信息增益（同ID3）

• Gain(年龄) = 0.324
• Gain(有工作) = 0.324
• Gain(有房) = 0.420
• Gain(信贷情况) = （待计算）

3. 计算"信贷情况"特征的信息增益

信贷情况有3个取值：一般/好/非常好

• ​一般​(5)：拒绝(4)，批准(1) →
  H(一般) = -[0.2×log₂0.2 + 0.8×log₂0.8] ≈ 0.722

• ​好​(6)：批准(5)，拒绝(1) →
  H(好) = -[5/6×log₂(5/6) + 1/6×log₂(1/6)] ≈ 0.650

• ​非常好​(4)：全部批准(4) → H(非常好) = 0

• 条件熵：

  H(D|信贷) = (5/15)×0.722 + (6/15)×0.650 + (4/15)×0 ≈ 0.472

• 信息增益：

  Gain(信贷) = H(D) - H(D|信贷) = 0.971 - 0.472 = 0.499

4. 计算各特征的分裂信息量（Split Information）

分裂信息量衡量特征取值的分布情况：

IV(A) = -Σ(|D_v|/|D|) × log₂(|D_v|/|D|)

• ​年龄的IV值​：

  IV(年龄) = -[5/15×log₂(5/15) + 5/15×log₂(5/15) + 5/15×log₂(5/15)]= -[0.333×(-1.585) × 3]≈ 1.585

• ​有工作的IV值​：

  IV(有工作) = -[5/15×log₂(5/15) + 10/15×log₂(10/15)]= -[0.333×(-1.585) + 0.667×(-0.585)]≈ 0.918

• ​有房的IV值​：

  IV(有房) = -[6/15×log₂(6/15) + 9/15×log₂(9/15)]= -[0.4×(-1.322) + 0.6×(-0.737)]≈ 0.971

• ​信贷情况的IV值​：

  IV(信贷) = -[5/15×log₂(5/15) + 6/15×log₂(6/15) + 4/15×log₂(4/15)]= -[0.333×(-1.585) + 0.4×(-1.322) + 0.267×(-1.907)]≈ 1.577

5. 计算信息增益率（Gain Ratio）

GainRatio(A) = Gain(A) / IV(A)

• ​年龄的增益率​：

  GainRatio(年龄) = 0.324 / 1.585 ≈ 0.204

• ​有工作的增益率​：

  GainRatio(有工作) = 0.324 / 0.918 ≈ 0.353

• ​有房的增益率​：

  GainRatio(有房) = 0.420 / 0.971 ≈ 0.433

• ​信贷情况的增益率​：

  GainRatio(信贷) = 0.499 / 1.577 ≈ 0.316

6. 选择根节点特征

比较各特征的增益率：

✅ ​根节点分裂：选择增益率最大的特征"有房"​

🌳 三. CART算法计算过程（基于基尼指数）

步骤1：计算整体基尼指数

• 批准概率 P(+) = 9/15 = 0.6
• 拒绝概率 P(-) = 6/15 = 0.4
• 基尼指数：

  Gini(D) = 1 - (0.6² + 0.4²) = 1 - (0.36 + 0.16) = 1 - 0.52 = 0.48

步骤2：计算各特征分裂后的加权基尼指数

​​（1）按"有房"分裂（二分裂）：​​

• 有房子集(6)：全部批准 → Gini(有房)=1-(1²+0²)=0
• 无房子集(9)：批准(3)，拒绝(6) →

  Gini(无房)=1-(1/3)²-(2/3)²=1-1/9-4/9=4/9≈0.444

• 加权基尼指数：

  Gini_{split}(有房) = (6/15)*0 + (9/15)*(4/9) = 0.267

​​（2）按"年龄"分裂（需处理多分类）：​​
CART自动处理多分类转为二叉树：

1. 青年 vs {中年,老年}
2. 中年 vs {青年,老年}
3. 老年 vs {青年,中年}
4. {青年,中年} vs 老年
5. {青年,老年} vs 中年
6. {中年,老年} vs 青年

以{青年} vs {非青年}为例：

• 青年子集(5)：批准(2)，拒绝(3) →

  Gini(青年)=1-((2/5)²+(3/5)²)=1-0.16-0.36=0.48

• 非青年子集(10)：批准(7)，拒绝(3) →

  Gini(非青年)=1-((7/10)²+(3/10)²)=1-0.49-0.09=0.42

• 加权基尼：

  Gini_{split}(年龄) = (5/15)*0.48 + (10/15)*0.42 = 0.44

​​（3）按"有工作"分裂：​​

• 有工作子集(5)：全部批准 → Gini=0
• 无工作子集(10)：批准(4)，拒绝(6) →

  Gini(无工作)=1-((4/10)²+(6/10)²)=1-0.16-0.36=0.48

• 加权基尼：

  Gini_{split}(有工作) = (5/15)*0 + (10/15)*0.48 = 0.32

步骤3：选择最优分裂点

比较各特征的最优二分裂结果：

✅ 有房特征基尼指数最小(0.267)，选为根节点

🌟 关键差异总结

实际应用中：

• ​ID3/C4.5​ 更注重信息理论纯度
• ​CART​ 更注重计算效率和不平衡数据处理

💡 实践建议：现代库（如scikit-learn）默认使用CART+基尼指数组合，因其速度最快且实际效果优秀。