基本流程
决策树的生成过程是一个 分治递归 算法
- 递归：在当前结点找到 最优属性 进行划分/展开，划分得到的各部分生成子结点
- 递归边界：
- 当前结点均为同一类别：将当前结点标记为该类别
- 当前结点样本所有属性的取值均相同：将当前结点标记为样本数最多的类别
- 当前结点样本为空：将当前结点标记为其父结点中样本数最多的类别
划分选择
信息增益
假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k$ （$k=1,2,…,\vert y \vert$），则 $D$ 的 信息熵 为
假设属性 $a$ 有 $V$ 个可能的取值 $\{a^1, a^2,…, a^V\}$，则给定属性 $a$ 后的 条件熵 为
则，使用属性 $a$ 对样本集 $D$ 进行划分得到的 信息增益 为
可以证明，信息增益 一定大于等于 0。
ID3 决策树学习算法
最优属性 的选择使得 信息增益 最大化，即
C4.5 决策树学习算法
最优属性 的选择使得 信息增益率 最大化，其中 信息增益率 为 $\frac{Gain(D,a)}{Ent(a)}$，其中 $Ent(a)$ 是把属性 $a$ 当作数据集 $D$ 上的目标变量后计算的信息熵。
CART 决策树学习算法
基尼系数
剪枝处理
采用 留出法 预先保留一部分作为验证集，评估模型 泛化性能
- 预剪枝：展开每个结点时，评估泛化性能是否提升；若不提升则停止展开。因此，模型存在欠拟合风险。
- 后剪枝：将树完全展开后，依次评估每个结点剪枝后泛化性能是否提升；若提升则进行剪枝。训练时间一般较长。
连续值处理：二分法
假设连续属性 $a$ 在数据集 $D$ 上出现的取值从小到大排序为 $\{a^1, a^2,…, a^n\}$，则存在 $n-1$ 个潜在划分点 $t_i = \frac{a^i+a^{i+1}}{2}, \, 1 \leq i \leq n-1$。
此时，可以将 $a$ 作为 $n-1$ 个离散属性 $(a, t_i)$ 考虑并计算信息增益 $Gain(D, a, t_i)$ ，则 $a$ 的信息增益为
即选出信息增益最大的那个划分点。
缺失值处理
如何选择最优属性？
假设在当前结点中样本 $x$ 的权重为 $w_x$。令 $\tilde{D}$ 代表 $D$ 中属性 $a$ 没有缺失的样本，则
如何进行样本划分？
若样本 $x$ 的属性 $a$ 缺失，则 分别同时 划入所有子结点，权重调整为
回归树
CART 算法
对属性 $a$ 的切分点 $t$，求解
其中，$R_1(a, t)$ 与 $R_2(a, t)$ 是 $(a, t)$ 划分得到的两个子集。显然，$c_1$ 和 $c_2$ 分别是这两个子集上 $y_i$ 的均值，即