Max Blog

树模型第一节，决策树基本介绍

1 背景

本篇笔记为树模型笔记第一篇，主要对决策树做一个简单的总结。后续会再针对集成学习包括xgb等模型做相关总结。

2 基本信息

以树的形式，对数据进行回归或分类。

基本流程：

从根节点开始，选择特征属性进行划分，输出到分支，直到到达叶子节点。

决策树的构造就是不断的进行属性选择，其中有三种情况会导致递归返回：

• 1.当前节点包含的样本完全属于同一种类别，无需划分
• 2.当前属性为空或所有样本在所有属性上取值相同，无需划分
• 3.当前节点包含的样本集合为空，不能划分。

针对第二种情况，把当前结点标记为叶子结点，并将其类别设定为该节点所含样本最多的类别。

针对第三种情况，把当前节点标记为叶子节点，但是类别设为父节点所含样本最多的类别。

3 常见模型

3.1 ID3 决策树

3.1.1 基本信息

**任务：**分类

特征选择依据：信息增益

随机变量X的熵：

$H(X) = -\sum_{i=1}^{n}p_{i}logp_{i}$

随机变量X与关于特征A的条件熵：

$H(X|A) = \sum_{j=1}^{n}p(a_j)H(X|a_j)$

A对于X的信息增益：

$I(X,A) = H(X)-H(X|A)$

3.1.2 缺点

• 不能处理连续特征
• 基于信息增益会优先选择特征取值多的特征作为特征
• 没有对缺失值做考虑
• 没有考虑过拟合

3.2 C4.5 决策树

3.2.1 优化内容

主要针对ID3的4个问题进行了优化

• 不能处理连续特征

  解决方案：连续特征离散化。将特征值进行排序，取相邻像个样本值的平均值，作为划分点。

  连续属性的节点后面还可以继续参与子节点的选择。

• 优先选择特征取值多的特征作为特征

  解决方案：使用信息增益比。信息增益与特征熵的比值。

  $I_{R}(D，A)=\frac{I(A,D)}{H_{A}(D)}$

  特征熵的公式为：

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

  其中，$$|D|$$为样本个数。

  特征取值越多的特征，对应的特征熵就越大，可以校正之前偏向取此类特征的问题。

• 无法处理缺失值

  • 样本在某些特征缺失的情况

    将样本划分为有缺失和无缺失两部分样本。计算无缺失部分的信息增益比，再乘以无缺失样本占总样本的占比。作为该特征的信息增益比。

  • 选定了划分属性，对于该属性上特征缺失的样本处理

    将缺失同时划分入所有的子节点。该样本的权重是按各子节点的样本数量来分配。

• 没有考虑过拟合

  引入正则化系数进行剪枝

3.2.2 缺点

• 剪枝方法有优化空间
• 生产的是多叉树。如果是二叉树，效率更高
• 只能用于分类
• 熵模型用到大量的对数运算，连续值涉及排序运算。有优化空间。

3.3 CART树

3.3.1 特征选择方法

使用基尼系数为特征选择方法

假设K个类别，第k个类的概率为$pk$

$Gini(p)=\sum_{k=1}^{K}p_{k}(1-p_{k})=1-\sum_{k=1}^{K}p_{k}^2$

二分类问题对应的基尼系数表达式

$Gini(p)=2p(1-p)$

对于样本D，根据特征A的某个值a,把D分成$$D_1$$$$D_2$$两部分，基尼系数表达式如下

$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$

基尼系数可以看成熵模型的近似替代，同时二次运算比对数运算要简单。

同时，建立的是二叉树，不是多叉树，可以进一步简化运算。

3.3.2 连续值和离散值的处理

• 连续值

  连续特征离散化。与C4.5的区别是选取的度量方式不同。C4.5选用的是信息增益比，CART树使用的是基尼系数。

• 离散值

  思路：不停的二分离散特征。

  比如有A1,A2,A3三个值。CART会计算{A1}{A2,A3}和{A2}{A1,A3}和{A3}{A1,A2}三个组合各自的基尼系数。找到最小基尼系数作为划分节点。

  离散特征可能会参与多次节点的建立(ID3,C4.5只会一次)。

3.3.3 CART分类树

算法输入：训练集D，基尼系数阈值，样本个数阈值

输出：决策树T

从根节点开始，递归的建立CART树

• (1)对于当前节点数据集D，如果样本个数小于阈值或者没有特征，返回决策树，当前节点停止递归
• (2)计算样本集D的基尼系数，如果基尼系数小于阈值，返回决策树子树，当前节点停止递归
• (3)计算当前节点现有各个特征的各个值对数据集D的基尼系数(缺失值离散值连续值各自处理方法见前面内容)
• (4)选择基尼系数最小的特征A和对应的值a，把数据分成$$D_1$$和$$D_2$$
• (5)对左右子节点递归调用1~4步，生产决策树

使用生成的决策树做预测时，假如测试集里的样本A落到了某叶子节点，而节点里有多个训练样本，样本A的类别预测采用的是这个叶子节点里概率最大的类别。

3.3.4 CART回归树

与分类树的区别

回归树与分类树的区别在于样本输出：

• 样本输出离散值：分类树
• 样本输出连续值：回归树

CART回归树与分类树在建立和预测主要有以下两个区别：

• (1)连续值处理方式不同
• (2)预测方式不同

连续值处理方式

连续值的处理方式：

使用均方差的度量方式替换基尼系数。

划分点a把数据分成$$D_1$$和$$D_2$$,使得各自数据集合的均方差最小同时两者均方差之和最小。

预测方法

用最终叶子的均值或者中位数来预测输出结果

3.3.5 剪枝

CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。

CART树的剪枝算法可以概括为两步，第一步是从原始决策树生成各种剪枝效果的决策树，第二部是用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的数作为最终的CART树。

大致思路为，自下而上，计算损失。如果剪掉子树和不剪子树的损失差小于阈值，则剪去子树，最终选择最优子树。

3.2.6 缺点

• 1.分类决策时依据一个特征决定，没有使用多变量同时决策
• 2.样本发生改动就会导致树结构剧烈改变

4 决策树总结

算法	支持模型	树结构	特征选择	连续值处理	缺失值处理	剪枝
ID3	分类	多叉树	信息增益	不支持	不支持	不支持
C4.5	分类	多叉树	信息增益比	支持	支持	支持
CART	分类、回归	二叉树	基尼系数,均方差	支持	支持	支持

优点

1）简单直观，生成的决策树很直观。

2）基本不需要预处理，不需要提前归一化，处理缺失值。

3）使用决策树预测的代价是𝑂(𝑙𝑜𝑔2𝑚)。 m为样本数。

4）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。

5）可以处理多维度输出的分类问题。

6）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释

7）可以交叉验证的剪枝来选择模型，从而提高泛化能力。

8） 对于异常点的容错能力好，健壮性高。

缺点

1）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。

2）决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。

3）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。

4）有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。

5）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。