知识框架
决策树把分类或回归过程表示为一组层次化规则。重点包括递归生成流程、信息熵、信息增益、增益率、基尼指数、ID3、C4.5、CART、连续属性处理、缺失值处理、剪枝和回归树。
基本流程
决策树通常自顶向下递归生成：
- 若当前结点样本全属同一类，设为叶结点。
- 若属性集为空或样本在剩余属性上取值相同，设为叶结点，类别取多数类。
- 否则选择最优划分属性，根据属性取值生成分支。
- 对每个分支递归处理子数据集。
这种生成过程是贪心的，每一步只选择当前看来最优的划分。
信息熵与信息增益
数据集 $D$ 中第 $k$ 类比例为 $p_k$，信息熵为
\[
\operatorname{Ent}(D)=-\sum_{k=1}^{K}p_k\log_2 p_k.
\]
属性 $a$ 有 $V$ 个取值，划分后的条件熵为
\[
\sum_{v=1}^{V}\frac{|D^v|}{|D|}\operatorname{Ent}(D^v).
\]
信息增益：
\[
\operatorname{Gain}(D,a)=
\operatorname{Ent}(D)-
\sum_{v=1}^{V}\frac{|D^v|}{|D|}\operatorname{Ent}(D^v).
\]
ID3 选择信息增益最大的属性。
C4.5 与增益率
信息增益偏好取值数多的属性。C4.5 使用增益率：
\[
\operatorname{Gain\_ratio}(D,a)=
\frac{\operatorname{Gain}(D,a)}{\operatorname{IV}(a)},
\]
\[
\operatorname{IV}(a)=
-\sum_{v=1}^{V}\frac{|D^v|}{|D|}
\log_2\frac{|D^v|}{|D|}.
\]
CART 与基尼指数
基尼值：
\[
\operatorname{Gini}(D)=1-\sum_{k=1}^{K}p_k^2.
\]
按属性 $a$ 划分后的基尼指数：
\[
\operatorname{Gini\_index}(D,a)=
\sum_{v=1}^{V}\frac{|D^v|}{|D|}\operatorname{Gini}(D^v).
\]
CART 选择基尼指数最小的划分，并通常生成二叉树。
连续属性与缺失值
连续属性常将相邻排序取值的中点作为候选划分点：
\[
T_a=\left\{\frac{a^{(i)}+a^{(i+1)}}{2}\right\}.
\]
对每个候选阈值 $t$，把样本分为 $a\le t$ 和 $a>t$ 两支，选择指标最优者。缺失值可用样本权重、按已知样本比例分配或用替代划分处理。
剪枝
- 预剪枝
- 在划分前估计继续划分是否能提升验证集性能，若不能则停止。
- 后剪枝
- 先生成完整树，再自底向上考察把子树替换为叶结点是否更好。
代价复杂度剪枝可写为
\[
C_\alpha(T)=C(T)+\alpha |T|,
\]
其中 $C(T)$ 是经验误差或损失，$|T|$ 表示叶结点数，$\alpha$ 控制复杂度惩罚。
回归树
回归树叶结点输出连续值，常取该叶结点样本均值。对特征 $j$ 和切分点 $s$，选择使平方误差最小的划分：
\[
\min_{j,s}\left[
\sum_{\mathbf{x}_i\in R_1(j,s)}(y_i-c_1)^2+
\sum_{\mathbf{x}_i\in R_2(j,s)}(y_i-c_2)^2
\right],
\]
其中 $c_1,c_2$ 是两个区域内的均值。
常见问法
- 给离散数据表，计算 $H(D)$、$H(D\mid a)$、信息增益并选择根结点。
- 用基尼指数重新计算划分，比较与信息增益是否一致。
- 用文字层次结构画出决策树。
- 解释决策树为什么容易过拟合，并说明预剪枝和后剪枝。
- 给连续特征，列出候选划分点并选择最优阈值。
- 给回归数据，按平方误差选择切分点和叶结点输出。