8.4 决策树算法：ID3、C4.5、CART与剪枝策略
8.4 决策树算法：ID3、C4.5、CART与剪枝策略
决策树是一种基于树形结构进行决策的机器学习模型，它模拟人类在面临选择时的分步判断过程，因其模型直观、可解释性强、对数据预处理要求低而被广泛应用。决策树的学习本质上是通过递归地选择最优特征对数据进行划分，旨在构建一棵能将样本尽可能正确分类或预测的树。本节将系统阐述决策树的核心框架与构建要素，并深入剖析三种经典算法——ID3、C4.5和CART的原理与区别，最后讨论为防止过拟合所必需的剪枝策略。
8.4.1 决策树的基本框架与核心概念
一棵决策树由内部节点、分支和叶子节点构成。每个内部节点对应一个特征属性的测试，每个分支代表该特征的一个输出（或取值范围），每个叶子节点则存储一个类别标签（分类树）或一个具体的数值（回归树）。
构建决策树的核心是解决两个递归问题：
- 特征选择：在当前节点的数据子集上，如何从所有可用特征中选择一个最优的特征进行分裂？
- 停止条件：何时停止分裂，将当前节点标记为叶子节点？
决策树的生长过程遵循分而治之的策略，其目标是随着树的生长，使每个子节点中样本的“纯度”越来越高，即同类样本尽可能聚集在一起。
8.4.2 经典决策树算法原理
8.4.2.1 ID3算法：基于信息增益
ID3算法由Quinlan于1986年提出，是决策树学习的里程碑[1]。它使用信息增益作为特征选择准则，适用于离散特征和分类任务。
其核心概念源于信息论：
- 信息熵：度量样本集合D DD纯度的指标。设样本属于k kk个类别，第i ii类样本所占比例为p i p_ipi，则D DD的熵定义为：
Ent ( D ) = − ∑ i = 1 k p i log 2 p i \text{Ent}(D) = -\sum_{i=1}^{k} p_i \log_2 p_iEnt(D)=−i=1∑kpilog2pi
Ent ( D ) \text{Ent}(D)Ent(D)越小，则D DD的纯度越高。 - 条件熵与信息增益：以离散特征A AA对D DD进行划分，假设有V VV个可能的取值，则划分后各子集D v D^vDv的熵的加权和称为条件熵。特征A AA对数据集D DD的信息增益定义为：
Gain ( D , A ) = Ent ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Ent ( D v ) \text{Gain}(D, A) = \text{Ent}(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} \text{Ent}(D^v)Gain(D,A)=Ent(D