机器学习笔记：决策树

2020-04-25

关键词：ID3、C4.5、CART

决策树

介绍下决策树？

决策树是基于树结构来进行决策的。决策树由节点（node）和有向边（directed edge）组成。节点有两种类型：内部节点（internal node）和叶节点（leaf node）。内部节点表示一个特征或属性，叶节点表示一个类。
- 根节点包含样本全集
- 每个非叶节点表示一个特征属性测试，每个节点包含的样本集合通过属性测试被划分到子节点中
- 每个分支代表这个特征属相在某个值域上的输出
- 每个叶子节点存放一个类别
决策树的构造

决策树的构造是一个递归的过程。
- 构造根节点，将所有训练数据都放在根节点
- 选择一个最优特征，按照该特征将训练数据分割成子集
- 如果这些子集已经能够正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点中去
- 如果这些子集不能被基本正确分类，那么对这些子集选择新的最优特征，继续对其进行分割
决策树学习的常用算法：
- ID3算法
- C4.5算法
- CART算法
决策树特征选择的准则？
- 信息增益
- 信息增益比
- 基尼指数

在介绍上述两个 evaluation 前，先介绍下熵（entropy）。熵表示随机变量不确定性的度量，设 $X$ 是一个取有限个值的离散随机变量，其概率分布为：
$$
P(X = x_i) = p_i, \qquad i = 1,2,\cdots,n
$$
则随机变量 $X$ 的熵定义为：
$$
H(X) = -\sum^n_{i = 1} p_ilogp_i
$$

熵越大，随机变量的不确定性就越大

设有随机变量 $(X, Y)$，其联合概率分布为：
$$
P(X = x_i, Y = y_i) = p_{ij}, \qquad i = 1, 2, \cdots, n; j = 1, 2, \cdots, m
$$
条件熵：随机变量 $X$ 下随机变量 $Y$ 的不确定性：
$$
H(Y|X) = \sum^{n}_{i = 1}p_iH(Y|X = x_i), \qquad p_i = P(X = x_i)
$$
接下来引入信息增益的定义。

直观定义

得知特征 $X$ 的信息而使类 $Y$ 的信息不确定性减少的程度
数学定义

特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D, A)$，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，即
$$
g(D, A) = H(D) - H(D|A)
$$
根据信息增益准则的特征选择方法
对训练数据集（或子集）$D$，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征
信息增益算法
1. 计算数据集 $D$ 的经验熵 $H(D)$，$|C_k|$ 表示 $k$ 类别的数据量
  $$
  H(D) = -\sum^{K}_{k = 1}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}
  $$
2. 计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D|A)$，$|D_i|$ 表示数据集中特征 $A$ 取值为 $i$ 的数量
  $$
  H(D|A) = \sum^{n}{i = 1} \frac{|D_i|}{|D|}H(D_i) = -\sum^{n}{i = 1}\frac{|D_i|}{|D|} \sum^K_{k = 1}\frac{|D_{ik|}}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}
  $$
3. 计算信息增益
  $$
  g(D, A) = H(D) - H(D|A)
  $$
4. 计算每个特征的信息增益，选择信息增益最大的特征
缺点：

信息增益会偏向于选择值较多的特征。例如：如果对于某一个特征，有 $D$ 个取值，样本集D将会被划分为|D|个分支，每个分支只有一个样本，这样划分后的信息熵为零，十分纯净，但是对分类毫无用处

接下来引入信息增益比的定义。

直观定义

在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小，计算得到的信息增益比越小；特征个数较少时，惩罚参数较大。
数学定义

特征 $A$ 对训练数据集 $D$ 的信息增益之比 $g_R(D, A)$ 定义为其信息增益 $g(D, A)$ 与训练数据集 $D$ 关于特征 $A$ 的值的熵 $H_A(D)$ 之比
$$
g_R(D, A) = \frac{g(D, A)}{H_A(D)}
$$
其中，$H_A(D) = -\sum^{n}_{i = 1}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$，其实就是根据特征 $A$ 计算数据集 $D$ 的熵值
缺点：信息增益比偏向取值较少的特征

接下来引入基尼指数的定义。

直观定义

基尼指数反映的是从样本集 $D$ 中随机抽取两个样本，其类别标记不一致的概率，因此 $Gini(D)$ 越小越好
数学定义
$$
GiDi(D) = \sum^{|y|}{k = 1}\sum{k’ \neq k}p_kp_k’ = \sum^{|y|}{k = 1}p_k(1 - p_k) = 1 - \sum^{|y|}{k = 1}p_k^2
$$
计算数据集 $D$ 的基尼指数
$$
Gini(D) = 1 - \sum^K_{k = 1}(\frac{|C_k|}{|D|})^2
$$
其中，$C_k$ 是 $D$ 中属于第 $k$ 类的样本数量，$K$ 是样本个数。
计算数据集 $D$ 在特征 $A$ 的条件下的基尼指数，根据特征 $A$ 是否取某一可能值 $a$ 将数据集分割为 $D_1$ 和 $D_2$ 两部分
$$
Gini(D, A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)
$$

ID3算法

计算各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A$。

节点停止分裂的几种条件：
- 如果该节点所有实例均属于同一个类
- 特征集为空
- 信息增益小于阈值
否则，对特征 $A$ 的每一个可能值 $a_i$，依 $A = a_i$ 将 $D$ 分割为若干非空子集 $D_i$，再对每一个子节点重复上述步骤
C4.5算法

计算各特征对 $D$ 的信息增益比，选择信息增益比最大的特征 $A$。

其他步骤与ID3算法相同
ID3算法和C4.5算法的缺点
- 只适用于特征值为离散性的数据
- 每次选取当前最佳的特征来分割数据。一旦按某特征切分后，该特征在之后的算法执行过程中将不会再其作用
CART算法
1. 设节点的训练数据集为 $D$，对每一个特征 $A$，对其可能取的每个值 $a$，根据样本点对 $A = a$ 的测试为 “是”或“否”将 $D$ 分割成 $D_1$ 和 $D_2$两部分，并计算 $Gini(D, A)$
2. 在所有可能的特征 $A$ 以及其所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依次从现节点生成两个子节点，将训练数据集依特征分配到两个子节点中去。
3. 对两个子节点递归地调用 1 和 2，直至满足停止条件
停止条件：
- 节点中的样本个数小于预定阈值
- 样本集的基尼指数小于预定阈值
决策树的剪枝处理

解决决策树的过拟合问题。剪枝策略有两种：
- 预剪枝：在构造过程中先评估，再考虑是否分支。例如，在构造决策树的过程中，对一个节点考虑是否分支时，首先计算决策树不分支时在测试集上的性能，再计算分支之后的性能，若分支对性能没有提升，则选择不分支（即剪枝）。
- 后剪枝：在构造好一棵完整的决策树后，自底向上，评估分支的必要性。例如，在构造好一颗完整的决策树后，从最下面的节点开始，考虑该节点分支对模型的性能是否有提升，若无则剪枝，即将该节点标记为叶子节点，类别标记为其包含样本最多的类别。
- 预剪枝 vs 后剪枝
  
  预剪枝处理使得决策树的很多分支被剪掉，因此大大降低了训练时间开销，同时降低了过拟合的风险，但另一方面由于剪枝同时剪掉了当前节点后续子节点的分支，因此预剪枝“贪心”的本质阻止了分支的展开，在一定程度上带来了欠拟合的风险。而后剪枝则通常保留了更多的分支，因此采用后剪枝策略的决策树性能往往优于预剪枝，但其自底向上遍历了所有节点，并计算性能，训练时间开销相比预剪枝大大提升。
一种后剪枝策略：
- 损失函数的定义
  
  设树 $T$ 的叶节点个数为 $|T|$, $t$ 是树 $T$ 的叶节点，该节点有 $N_t$个样本点，其中 $k$ 类的样本点有 $N_{tk}$个， $k = 1, 2, \cdots, K, H_t(T)$为叶结点 $t$上的经验熵，$\alpha \ge 0$为参数，较大的 $\alpha$ 促使选择较简单的模型，较小的 $\alpha$ 促使选择较复杂的模型，则决策树学习的损失函数可以定义为
  $$
  G_{\alpha}(T) = \sum_{t = 1}^{|T|}N_tH_t(T) + \alpha|T|
  $$
  其中经验熵为：
  $$
  H_t(T) = -\sum_{k}\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}
  $$
- 剪枝过程
  1. 计算每个节点的经验熵
  2. 递归地从树的叶节点向上回缩，设一组叶节点回缩到其父节点之前与之后的整体树分别为 $T_B$ 与 $T_A$，其对应的损失函数值分别是 $C_{\alpha}(T_B)$ 与 $C_{\alpha}(T_A)$，如果
    $$
    C_{\alpha} (T_A) <= C_{\alpha} (T_B)
    $$
    则进行剪枝，即将父节点变成新的叶节点
  3. 返回（2），直至不能继续为止，得到损失函数最小的子树 $T_{\alpha}$
树形结构为什么不需要归一化？

因为数值缩放不影响分裂点位置，每一个特征值的排列顺序不变，那么所属的分支以及分裂点就不会不同。而且，树模型是不能进行梯度下降的，因为构建树模型（回归树）寻找最优点时是通过寻找最优分裂点完成的，因此树模型是阶跃的，阶跃点是不可导的，也就不需要归一化

而对于线性模型来说，特征值差别很大时，运用梯度下降时，损失等高线是椭圆形，需要进行多次迭代才能到达最优点。如果进行了归一化，那么等高线是圆形的，促使 SGD 往原点迭代，因而需要迭代次数较少
决策树怎么处理连续值？

CART回归树是假设树为二叉树，通过不断将特征进行分裂。比如当前树结点是基于第 $j$ 个特征值进行分裂的，设该特征值小于 $s$ 的样本划分为左子树，大于 $s$ 的样本划分为右子树。CART回归树实质上就是在该特征维度对样本空间进行划分，而这种空间划分的优化是一种NP难问题，因此，在决策树模型中是使用启发式方法解决。典型CART回归树（在《统计学习方法》中称为最小二乘回归树）产生的目标函数为：
$$
\sum_{x_i \in R_m}(y_i - f(x_i))^2
$$
因此，可以转换为求解以下目标函数：
$$
min_{j, s}[min_{c_1} \sum_{x_i \in R_1(j, s)} (y_i - c_1)^2 + min_{c_2} \sum_{x_i \in R_2(j,s) }(y_i - c_2)^2]
$$
其中，$R_1(j, s) = {x | x_j <= s}$，$R_2(j, s) = {x | x_j > s}$，$c_m = \frac{1}{N} \sum_{x_i \in R_m(j, s)}y_i (m = 1, 2)$

ID3分类树和C4.5分类树基于信息增益和信息增益比处理连续值，遍历每一个特征值 $s$，将特征小于 $s$ 的样本划分为左子树，大于 $s$ 的样本划分为右子树，计算取不同 $s$ 时的信息增益，选取最大信息增益对应的特征值作为划分点。
分类树和回归树的区别？
- 回归树的每个节点都会得到一个预测值，例如第 10 点中提到的 $f(x_i)$，$c_1$ 和 $c_2$。（回归问题）
- 分类树的每一个节点的类别取多数样本的类别（分类问题）
- 回归树使用最小均方差划分节点
- 分类树使用信息增益或增益比率来划分节点
决策树如何处理缺失值？

具体可参考缺失值处理
- 如何在训练样本属性缺失的情况下进行划分属性的选择？
  
  计算在该属性上没有缺失的样本集 $D’$ 的信息增益或其他指标，再乘以样本子集占样本集的比重。
- 若样本在该属性上的值是缺失的，那么该如何对这个样本进行划分？
  
  将该样本划分到所有分支中，进入到每个分支后权重会被调整（每个样本的初始权重值为 1），更新后的权重值为 |子节点| / |父节点|
- 测试样本中属性有缺失值？
  
  同时探查（计算）所有分支，然后算每个类别的概率，取概率最大的类别赋值给该样本
决策树和逻辑回归的区别？
- 决策树可以处理缺失值，而逻辑回归需要挖掘人员预先对缺失数据进行处理
- 逻辑回归对数据整体结构的分析优于决策树，而决策树对局部结构的分析优于逻辑回归；（决策树由于采用分割的方法，所以能够深入数据内部，但同时失去了对全局的把握。一个分层一旦形成，它和别的层面或节点的关系就被切断了，以后的挖掘只能在局部中进行。同时由于切分，样本数量不断萎缩，所以无法支持对多变量的同时检验。而逻辑回归，始终着眼整个数据的拟合，所以对全局把握较好。但无法兼顾局部数据，或者说缺乏探查局部结构的内在机制。）
- 逻辑回归擅长分析线性关系，而决策树对线性关系的把握较差。
- 逻辑回归对极值比较敏感，容易受极端值的影响，而决策树在这方面表现较好。
- 应用上的区别：决策树的结果和逻辑回归相比略显粗糙。逻辑回归原则上可以提供数据中每个观察点的概率，而决策树只能把挖掘对象分为有限的概率组群。
- 执行速度：当数据量很大的时候，逻辑回归的执行速度非常慢，而决策树的运行速度明显快于逻辑回归。