《统计学习方法》读书笔记5：决策树

决策树像是 if-then 的规则集合。

决策树很可能发生过拟合现象，这时需要自下而上的剪枝。决策树的生成只考虑局部最优，而剪枝考虑全局最优。

特征选择时需要选取具有分类能力的特征，如果利用一个特征进行分类与随机分类的结果没有区别，则称这个特征没有分类能力。通常特征选择的标准是信息增益或信息增益比。

信息增益

1. 熵（entropy）表示的是一个随机变量不确定的程度。设 $X$ 是一个取有限值的离散随机变量，它的熵定义为：

   $$H(X) = -\sum_{i=1}^{N} p_i \log p_i$$

   如果与 $X$ 取值无关，只与其分布有关，还可以记作 $H(p)$。对数以 2 为底时，熵的单位为比特（bit）；以 $e$ 为底时，单位为奈特（nat）。

2. 条件熵 $H(Y \mid X)$ 表示已知 $X$ 的条件下，随机变量 $Y$ 的不确定程度：

   $$H(Y \mid X) = \sum_{i=1}^{N} p_i H(Y \mid X = x_i)$$

3. 信息增益：指给定特征 $A$ 的情况下，训练数据集 $D$ 的不确定性的减少量：

   $$g(D, A) = H(D) - H(D \mid A)$$

   在信息论中称为互信息。$H(D)$ 是由训练集的经验概率得到的，所以称为经验熵。

4. 在实际选取过程中，根据信息增益大小选择特征。

5. 为了解决偏向于选择取值较多的特征的问题，可以用信息增益比：

   $$g_R(D, A) = \frac{g(D, A)}{H_A(D)}$$

   其中，

   $$H_A(D) = -\sum_{i=1}^{n} \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}$$

决策树的生成

1. ID3 算法：每次挑选信息增益最大的特征分裂数据集，直到信息增益小于某一阈值。
2. C4.5 算法：改进了 ID3 算法，使用信息增益比。

决策树的剪枝

1. 决策树的剪枝通过极小化决策树的损失函数完成。

2. 决策树的损失函数定义为：

   $$C_\alpha(T) = \sum_{t=1}^{|T|} N_t H_t(T) + \alpha |T|$$

   其中，经验熵为：

   $$H_t(T) = -\sum_{k} \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}$$

   通常，记：

   $$C(T) = \sum_{t=1}^{|T|} N_t H_t(T) = -\sum_{t=1}^{|T|} \sum_{k=1}^{K} N_{tk} \log \frac{N_{tk}}{N_t}$$

   这时有：

   $$C_\alpha(T) = C(T) + \alpha |T|$$

3. 设一组节点回缩到其父节点之前与之后的整体树分别为 $T_B$ 与 $T_A$，其对应的损失函数分别为 $C_\alpha(T_B)$ 与 $C_\alpha(T_A)$，如果：

   $$C_\alpha(T_A) \leq C_\alpha(T_B)$$

   则进行剪枝，即将父节点变为新的叶节点。重复这一过程，直至不能进行为止。

CART 算法

1. CART（classification and regression tree）
2. 回归树：$X$ 和 $Y$ 分别为输入变量与输出变量，且 $Y$ 为连续变量。
3. 分类树：
   1. 基尼系数。
   2. 根据基尼系数生成分类树。