机器学习： 决策树

machine-learning

---

简介

决策树是一个分而治之的递归过程。

• 开始，构建根节点，将所有训练数据都放在根节点。
• 选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类
• 如果子集未分类完毕，则在子集中选择一个最优特征，继续进行划分，直到所有训练数据子集都被正确分类或没有合适的特征为止。

决策树三步走

• 特征选择： 从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。
• 决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。
• 决策树的修剪：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

算法描述

决策树优缺点

• 优点：

  • 理解和解释起来简单，决策树模型易想象。

  • 相比于其他算法需要大量数据集而已，决策树算法要求的数据集不大。

  • 决策树算法的时间复杂度较小，为用于训练决策树的数据点的对数。

  • 相比于其他算法智能分析一种类型变量，决策树算法可处理数字和数据的类别。

  • 能够处理多输出的问题。

  • 对缺失值不敏感。

  • 可以处理不相关特征数据。

  • 效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。

• 缺点

  • 对连续性的字段比较难预测。

  • 容易出现过拟合。

  • 当类别太多时，错误可能就会增加的比较快。

  • 信息缺失时处理起来比较困难，忽略了数据集中属性之间的相关性。

  • 在处理特征关联性比较强的数据时表现得不是太好。

  • 对于各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。

1. 特征的选择

ID3: 信息增益，C4.5: 信息增益比，CART: 基尼系数

1. 信息增益

思想： 计算所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。

熵

熵是用来度量随机变量的不确定性。

定义： 假设随机变量X的可能取值有$x_{1},x_{2},...,x_{n}$，对于每一个可能的取值$x_{i}$，其概率为$P(X=x_{i})=p_{i},i=1,2...,n$。随机变量的熵为：

$$熵： H(X)=-\sum_{i=1}^{n}p_{i}log_{2}p_{i} \\ 条件熵： H(Y|X) = \sum_{i=1}^n p_i H(Y | X=x_i), p_i = P(X=x_i)$$
熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。

信息增益

定义： 度量以某特征划分数据集前后的熵的差值

假设划分前样本集合D的熵为H(D)。使用某个特征A划分数据集D，计算划分后的数据子集的熵为H(D|A)。

$$信息增益： g(D,A)=H(D)-H(D|A)$$

$$H(D) = - \sum_{k=1}^k \frac{|C_k|}{|D|} log_2 \frac{|C_k|}{|D|} \\ H(D|A) = \sum_{i=1}^n \frac{|D_i|}{|D|} H(D_i) \\ g(D,A)=H(D)-H(D|A)$$
信息增益对数目较多的属性有所偏好，因此有人提出采用信息增益比来划分特征。

2. 信息增益比

信息增益比本质：在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。

$$g_R(D,A) = \frac{g(D,A)}{H(D)}$$
信息增益比对可取值数目较少的属性有所偏好。C4.5 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益比最高的。

3. 基尼系数

$$Gini(D) = 1 - \sum_{k=1}^{|y|} p_k^2$$

2. 决策树的生成

1. ID3 算法

ID3 算法采用信息增益来选择特征。 方法是： 从根节点开始， 对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点特征，然后划分子集。 再对子集递归调用以上方法，构建决策树，直到所有特征的信息增益均很小或没有特征可以选择为止。

2. C4.5 算法

采用信息增益比来选择 特征。

3. 剪枝处理

剪枝的作用

剪枝处理是决策树学习算法用来解决过拟合的一种办法。在决策树算法中，为了尽可能正确分类训练样本， 节点划分过程不断重复， 有时候会造成决策树分支过多，以至于将训练样本集自身特点当作泛化特点， 而导致过拟合。 因此可以采用剪枝处理来去掉一些分支来降低过拟合的风险。

1. 预剪枝

在决策树生成过程中，在每个节点划分前先估计其划分后的泛化性能， 如果不能提升，则停止划分，将当前节点标记为叶结点。

评估方法采用常见的性能评估法即可。

2. 后剪枝

生成决策树以后，再自下而上对非叶结点进行考察， 若将此节点标记为叶结点可以带来泛化性能提升，则修改之。