一、模型目标
决策树就像一个流程图，通过一系列“是/否”问题对数据进行分类或预测。例如，医生在判断病人是否感冒时，可以按照以下流程提问：
graph TD
A("发烧吗？") -->|是| B("咳嗽吗？")
A -->|否| C("诊断为健康")
B -->|是| D("诊断为感冒")
B -->|否| E("诊断为流感")
其核心目标是在数据中找出一系列最佳问题（即选择合适的特征和分割点），使得每一步分割后数据的相似度尽可能高，最终达到高准确率或低误差的预测效果。
二、决策树构建的学习步骤
- 选择特征：在当前数据中，挑选一个最能区分类别的特征。例如：在判断感冒或流感时，用“是否有喉咙痛”可能比“年龄”更有区分作用。*
- 数据分割：根据选中的特征及其分割值将样本划分成若干子集。
- 递归建树：对每个子集重复上述步骤，直到所有样本都属于同一类或满足停止条件。
- 剪枝：通过对树结构的调整，降低过拟合的出现概率。
三、分割指标的选择
在决策树中，如何衡量特征对数据分类或回归的“区分能力”显得尤为重要。在讨论如何衡量特征的“区分能力”前，我们首先要介绍一个概念，熵。
3.1 熵
信息论中的熵是描述数据混乱程度的指标，它代表着信息的不确定性。熵由香农提出，用来衡量一个信息源传递信息的平均不确定性或信息量。对于离散信息源，熵定义为： $$ H(D) = -\sum_{k=1}^K p_k \log_2 p_k \quad \text{其中 } p_k = \frac{|C_k|}{|D|} $$
- 当数据集所有样本都属于同一类别时，熵为0，此时不含混乱或不确定性。
- 当数据集中各类别大致相等时，熵达到最大值，表示数据集的不确定性最高。
3.2 信息增益
在选择最佳分割特征时，我们目标是尽可能得让分割后的样本纯度更高，也就是说使得分割后各子集熵的加权平均值比分割前数据集的熵尽可能得低，这里我们可以用一个值来描述两者之间的差值，即信息增益。其计算公式为
$$ Gain(D,A) = H(D) - \sum_{v=1}^V \frac{|D_v|}{|D|}H(D_v) $$
其作用就是衡量特征对熵的减少能力。选择能带来较大信息增益的特征进行分裂，这样能够更有效地减少数据集的不确定性，从而构建出更“纯”的分支。
3.3 信息增益比
信息增益也有其缺陷，他会倾向于选择取值多的特征。为了弥补信息增益对多值属性的偏好，我们可以引入固有值进行标准化，可以得到信息增益比： $$ GainRatio(D,A) = \frac{Gain(D,A)}{H_A(D)} \quad $$
其中 $$ H_A(D) = -\sum_{v=1}^V \frac{|D_v|}{|D|}\log_2\frac{|D_v|}{|D|} $$ 使用信息增益比最大化进行分割特征选择就可以将使得划分标准更合理，避免了多值属性偏好问题。
3.4 基尼指数
由于信息增益比涉及信息熵的计算和后续的归一化处理，在数据集较大时可能会带来更高的计算负担。
计算复杂度更优的不纯度指标基尼指数在大数据计算中具有较高的效率。基尼指数的计算仅涉及基本的乘法和加法运算，不需要计算对数： $$ Gini(D) = 1 - \sum_{k=1}^K p_k^2 $$ 不过当处理类别较多或属性值分布极不平衡的数据时，基尼指数在评估纯度时可能不如经过归一化处理的信息增益比稳定。
四、剪枝
4.1 预剪枝
在构造决策树的过程中，通过设定一定的停止条件来提前终止分裂，从而避免树的过深和过于复杂。这样做可以在树的构建阶段就降低过拟合的风险。
常用方法和条件：
- 最大深度： 限制决策树的最大层数，当达到预设的最大深度时，不再继续分裂。
- 最小样本数： 设置一个节点所需的最小样本数，当某个节点的样本数量少于该阈值时，停止分裂。
- 信息增益/基尼指数阈值： 当选择属性进行分裂时，如果最佳属性所带来的信息增益或基尼指数改善低于某个阈值，则不进行分裂。
- 置信度测试： 利用统计检验（如卡方检验）判断当前节点的分裂是否有足够的统计显著性。
由于在构建过程中就限定了树的复杂度，算法训练速度较快，并且相对容易控制过拟合。但预剪枝可能过早停止分裂，导致模型欠拟合，错过了数据中潜在的有用结构。
4.2 后剪枝
4.2.1 降低误差剪枝
- 将训练数据分为训练集和验证集。
- 从底部往上遍历每个结点，删除该节点的子树，将其转化为叶节点，并使用验证集测试剪枝前后的误差。
- 如果剪枝后验证误差减小或没有增大，则保留剪枝结果，否则还原该结点。
4.2.2 成本复杂度剪枝
- 完整生成决策树后，引入一个代价复杂度参数 $ \alpha $ 用于平衡模型的复杂度和训练误差。
- 定义目标函数 $R_{\alpha}(T) = R(T) + \alpha |T|$。其中，$R(T)$ 为树 T 在训练集上的误差，$|T|$ 为叶节点的数量，$ \alpha $ 控制剪枝过程中对树复杂度的惩罚。
- 通过不断调整 $ \alpha $ 值，生成一系列嵌套的子树，并利用交叉验证或验证集选择最佳的 $ \alpha $，确定最终剪枝后的树。
后剪枝方法通常能更全面地探索树的可能结构，对最终树的结构有更高的灵活性，通常能取得较好的泛化效果。不过由于需要先构造出完整的树，初始阶段可能会耗费较多计算资源，并且剪枝过程依赖于一个独立的验证集或交叉验证，数据划分可能影响结果。
五、缺失值处理
缺失值在实际应用场景中非常常见，如果不妥善处理，会影响模型的性能和预测效果。下面简单介绍一下两种常见的决策树算法 C4.5 和 CART 中的缺失值处理。
5.1. C4.5 算法中的缺失值处理
C4.5 算法对缺失值的处理较为巧妙，其主要策略包括：
- 计算信息增益时的权重分配：当划分某个节点时，如果样本在选定的划分属性上存在缺失值，C4.5 不会简单地删除这些样本，而是根据其他样本在该属性上的分布对它们进行“分散”。例如，如果在属性 A 中，大部分非缺失样本落在某个取值上，那么缺失值样本在计算信息增益时也会按一定概率被视为属于该类别。这种方法确保了缺失样本对分裂评估仍有贡献。
- 后期决策合并：在决策过程中，若遇到缺失值，算法可能将样本按一定的概率分摊到各个子节点，最终合并各子树的预测结果。这种方式提高了决策结果的鲁棒性。
2. CART 算法中的缺失值处理
CART 算法在处理缺失值时通常采用以下策略：
- 代理划分：当主划分属性的值缺失时，CART 会寻找与主属性高度相关的备用属性（代理变量）进行划分。对于缺失值样本，由与主属性划分结果最为接近的其他属性来“代理”其划分，确保这部分样本不会因为缺失值而被丢弃。
- 局部数据重分布：类似 C4.5 的策略，CART 在节点划分时也可以对缺失值样本以权重的方式，分散到各个分支中，进而在决策时综合各分支的预测结果。
六、代码实现
我们讨论了决策树很多复杂的主题，如果全部落实到代码上复杂程度非常高，特别是剪枝和缺失值处理部分。这里我们基于基尼指数来实现一个简单的决策树，也就是一个简化版的 Cart 树：
import numpy as np
class DecisionTree:
def __init__(self, max_depth=None):
self.tree = {}
self.max_depth = max_depth
def _gini(self, y):
_, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return 1 - np.sum(probs ** 2)
def _best_split(self, X, y):
"""寻找最佳分割点（特征及阈值）"""
best_gini = float('inf')
best_feat, best_val = None, None
for feat in range(X.shape[1]):
for val in np.unique(X[:, feat]):
mask = X[:, feat] <= val
if np.sum(mask) == 0 or np.sum(~mask) == 0:
continue
# 加权计算左右分割后的基尼指数
gini_left = self._gini(y[mask])
gini_right = self._gini(y[~mask])
total_gini = (gini_left * np.sum(mask) + gini_right * np.sum(~mask)) / len(y)
if total_gini < best_gini:
best_gini, best_feat, best_val = total_gini, feat, val
return best_feat, best_val
def _build_tree(self, X, y, depth=0):
if depth == self.max_depth or len(np.unique(y)) == 1:
return {'class': np.argmax(np.bincount(y))}
feat, val = self._best_split(X, y)
if feat is None:
return {'class': np.argmax(np.bincount(y))}
mask = X[:, feat] <= val
return {
'feature': feat,
'split': val,
'left': self._build_tree(X[mask], y[mask], depth + 1),
'right': self._build_tree(X[~mask], y[~mask], depth + 1)
}
def fit(self, X, y):
self.tree = self._build_tree(X, y)
def predict(self, X):
return np.array([self._traverse_tree(sample, self.tree) for sample in X])
def _traverse_tree(self, sample, node):
"""根据样本遍历树进行预测"""
while 'class' not in node:
if sample[node['feature']] <= node['split']:
node = node['left']
else:
node = node['right']
return node['class']
# 构造简单数据（2个特征，2个类别）
X = np.array([[0, 1],
[1, 0],
[1, 1],
[0, 0]])
y = np.array([1, 1, 0, 0])
dt = DecisionTree(max_depth=2)
dt.fit(X, y)
print("Predictions:", dt.predict(X)) # 输出：[1 1 0 0]