决策树

1. 决策树基本原理

决策树通过递归分裂特征空间，构建树形决策结构，每个内部节点表示一个特征判断，叶节点表示预测结果。

1.1 树结构

              根节点
             /       \
        特征A≤3?    特征A>3
         /    \       /    \
    特征B≤5?  叶:0  特征C≤2? 叶:1
     /  \           /   \
   叶:0  叶:1     叶:1   叶:0

1.2 学习过程

决策树学习本质是递归选择最优特征和分裂点：

BuildTree(D, features):
    if D中所有样本同类:
        return 叶节点(该类)
    if features为空 or D样本数 < 阈值:
        return 叶节点(多数类)
    选择最优特征 f* 和分裂点 t*
    D_left = {D | f* ≤ t*}
    D_right = {D | f* > t*}
    return Node(f*, t*, BuildTree(D_left), BuildTree(D_right))

2. 特征选择准则

2.1 信息增益（ID3）

信息熵度量数据集的纯度：

$H(D)=-{\sum }_{k=1}^K{p}_k{\log }_2{p}_k$

其中 $p_k$ 为第 $k$ 类的比例。熵越大，数据越不纯。

信息增益：按特征 $A$ 分裂后的熵减少量：

$\text{Gain}(D,A)=H(D)-{\sum }_{v=1}^V\frac{|D^v|}{|D|}H(D^v)$

选择信息增益最大的特征进行分裂。

缺点：偏向选择取值多的特征。

2.2 信息增益率（C4.5）

固有值（Intrinsic Value）：

$\text{IV}(A)=-{\sum }_{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$

信息增益率：

$\text{GainRatio}(D,A)=\frac{\text{Gain}(D,A)}{\text{IV}(A)}$

C4.5 选择信息增益率最大的特征，惩罚取值多的特征。

2.3 基尼指数（CART）

基尼指数度量数据集的不纯度：

$\text{Gini}(D)=1-{\sum }_{k=1}^K{p}_k^2$

按特征 $A$ 的某个取值 $a$ 二分后的基尼指数：

$\text{Gini}(D,A=a)=\frac{|D_1|}{|D|}\text{Gini}(D_1)+\frac{|D_2|}{|D|}\text{Gini}(D_2)$

CART 选择使基尼指数最小的特征和分裂点。

2.4 三种准则对比

基尼指数 vs 熵：

$\text{Gini}(D)\approx \frac{1}{2}H(D)\cdot \ln 2$

基尼指数计算不需要对数运算，效率更高。

3. 剪枝策略

3.1 预剪枝

在构建过程中提前停止树的生长：

3.2 后剪枝

先生成完整树，再从底部开始剪枝：

代价复杂度剪枝（CART）：

$R_{\alpha }(T)=R(T)+\alpha |T|$

其中 $R(T)$ 为训练误差，$|T|$ 为叶节点数，$\alpha$ 为复杂度参数。

• $\alpha =0$：不剪枝
• $\alpha \to \infty$：只保留根节点
• 通过交叉验证选择最优 $\alpha$

悲观剪枝（C4.5）：

$R^{\prime }(T)=R(T)+\frac{|T|\cdot e}{2}$

使用连续性修正估计泛化误差。

3.3 剪枝对比

4. CART回归树

CART 回归树使用平方误差最小化准则：

${\min }_{j,s}\left[{\min }_{c_1}{\sum }_{{\mathbf{x}}_i\in R_1(j,s)}(y_i-c_1{)}^2+{\min }_{c_2}{\sum }_{{\mathbf{x}}_i\in R_2(j,s)}(y_i-c_2{)}^2\right]$

其中 $R_1$ 和 $R_2$ 为按特征 $j$ 的分裂点 $s$ 划分的两个区域。

最优输出为区域内的均值：

$c_m=\frac{1}{|R_m|}{\sum }_{{\mathbf{x}}_i\in R_m}{y}_i$

5. 决策树优缺点

5.1 优点

• 可解释性强：决策逻辑直观可视
• 无需特征缩放：对量纲不敏感
• 处理混合类型：数值和类别特征
• 处理缺失值：部分算法内置缺失值处理
• 训练速度快：时间复杂度 $O(n\cdot d\cdot \log n)$

5.2 缺点

• 过拟合风险高：树太深容易记住噪声
• 不稳定：数据微小变化可能导致完全不同的树
• 贪心算法：局部最优不保证全局最优
• 偏向多值特征：ID3的信息增益偏好
• XOR问题：线性不可分问题需要很深的树

5.3 改进方向