决策树

决策树概述

• 决策树是一种非参数的有监督学习方法，它能够从一系列有特征和标签的数据中总结出决策规则，并用树状图的结构来呈现这些规则，以解决分类和回归问题。

• 决策树模型：树形结构，内部节点表示特征或属性，分支代表一个判断结果的输出，叶节点代表分类结果。

• 决策树的学习：主要包括特征选择、决策树生成、决策树的剪枝三个部分，生成算法有ID3算法、C4.5算法、CART算法。

• 决策树的主要优点：模型具有可读性，分类速度快。

决策树模型

特征选择

• ID3的特征选择准则为信息增益最大化；

• C4.5的特征选择准则为信息增益比最大化；

• CART分类树的特征选择准则为基尼指数最小化；

• CART回归树的特征选择准则为平方误差最小化准则。

信息增益和信息增益比

熵的定义

ID3算法

算法采用自顶向下的贪婪搜索遍历（同C4.5）可能的决策树空间，算法流程为

C4.5算法

悲观剪枝策略

剪枝策略分为预剪枝和后剪枝

预剪枝

利用超参数来控制树的结构，在节点划分前来确定是否继续增长，及早停止增长的主要方法有：

• 是否达到最大深度；

• 节点内数据样本低于某一阈值；

• 所有节点特征都已分裂；

• 节点划分前准确率比划分后准确率高；

• 是否达到最小分裂增益；

预剪枝可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

后剪枝

利用测试集在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。

后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

一般的后剪枝方法：基于误判的剪枝｜REP｜错误率降低修剪

为最简单的方法，利用测试数据集来修改树结构。具体做法：

• 对于完全决策树中的每一个非叶子节点的子树，尝试把它替换成一个叶子节点，该叶子节点的类别用子树所覆盖训练样本中存在最多的那个类来代替，这样就产生了一个简化决策树，然后比较这两个决策树在测试数据集中的表现，如果简化决策树在测试数据集中的错误比较少，并且该子树里面没有包含另外一个具有类似特性的子树（所谓类似的特性，指的就是把子树替换成叶子节点后，其测试数据集误判率降低的特性），那么该子树就可以替换成叶子节点。

• 该算法以自底向上的方式遍历所有的子树，直至没有任何子树可以替换使得测试数据集的表现得以改进时，算法就可以终止。

REP方法的缺点：需要一个额外测试集。为了解决这个问题，提出了悲观剪枝。

C4.5 采用的悲观剪枝方法

悲观剪枝方法

不需要额外测试集去计算误判率，而是直接利用训练数据集去估算每个内部节点所覆盖样本节点的误判率。

1. 利用惩罚因子估算误判率
把一颗子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。
• 叶子节点的误判率：对于一颗叶子节点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的误判率估计为$$\frac{E+0.5}{N}$$，其中的0.5即惩罚因子。
• 子树的误判率：那么一颗子树，它有L个叶子节点，那么该子树的误判率估计为$$\frac{\sum_{i=1}^L E_i+0.5 * L}{\sum_{i=1}^L N_i}$$。这样一来，虽然一颗子树具有多个子节点，但由于加上了惩罚因子，所以子树的误判率计算未必占到便宜。
• 剪枝后子树变为叶子节点的错误率：该叶子节点的误判个数为J，则剪枝后的误判率估计为$$\frac{J+0.5}{N},(N=\sum_{i=1}^L N_i)$$。
• 判断一颗子树是否需要剪枝成叶子节点：即判断$$J+0.5$$是否在$$\sum_{i=1}^L E_i+0.5 * L$$的标准误差内。

2. 根据分布模型估算误判次数
有了子树的误判率$$e_1=\frac{\sum_{i=1}^L E_i+0.5 * L}{\sum_{i=1}^L N_i}$$，再根据经验把它估计成各种各样的分布模型，比如正态分布、伯努利分布等。假设子树的误判次数服从伯努利分布，则可以估计出该子树的误判次数的均值和标准差：
$$\begin{aligned}E(subtree\_err\_count)&=N*e_1\\var(subtree\_err\_count)&=\sqrt{N*e_1*(1-e_1)}\end{aligned}$$
把子树替换成叶子节点后，该叶子的误判次数也是一个伯努利分布，其概率误判率$$e_2=\frac{J+0.5}{N},(N=\sum_{i=1}^L N_i)$$，因此叶子节点的误判次数均值为
$$E(leaf\_err\_count)=N*e_2$$
这里我们采用一种保守的分裂方案，即有足够大的置信度保证分裂后准确率比不分裂时的准确率高时才分裂，否则就不分裂（即剪枝）。如果要分裂（即不剪枝）至少要保证分裂后的误判数E(subtree_err_count)要小于不分裂的误判数E(leaf_err_count)，而且为了保证足够高的置信度，甚至要
$$E(subtree\_err\_count)+var(subtree\_err\_count)<E(leaf\_err\_count)$$
这里加了一个标准差可以有95%的置信度。反之，就是要进行剪枝。

 

处理连续特征

C4.5先把连续属性转换为离散属性，使用二分法进行处理。

具体做法：假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点$$v_j(j=1,\ldots,m)$$，$$\leq v_j$$的分到左子树，$$\geq v_j$$的分到右子树，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点。

（对于离散的特征只需做一次信息增益的计算，对于连续的特征需要做m-1次信息增益的计算）

更近一步减少计算量的方法

对于连续属性先进行排序，只有在决策属性发生改变的地方才需要切开。

另外在决定分界点时应该采用信息增益，原因如下：

分界点将样本分成两个部分，这两个部分的样本个数之比也会影响信息增益率。根据增益率公式，我们可以发现，当分界点能够把样本分成数量相等的两个子集时（称此时的分界点为等分分界点），增益率的抑制会被最大化，因此等分分界点被过分抑制了。子集样本个数能够影响分界点，显然不合理。因此在决定分界点是还是采用信息增益这个指标，而选择属性的时候才使用信息增益率这个指标。这个改进能够很好得抑制连续值属性的倾向。

处理缺失值

CART算法

CART 树分为分类树和回归树

CART分类树利用基尼指数最小化准则进行二分

基尼指数

• 数据集D的纯度用基尼值度量为
$$\begin{gathered}\operatorname{Gini}(D)=\sum_{k=1}^{K} \sum_{k^{\prime} \neq k} p_k p_{k^{\prime}} =1-\sum_{k=1}^{K} p_k^2=1-\sum_{k=1}^{K} \frac{|C_k|^2}{|D|^2}\end{gathered}$$
直观来说，Gini(D)反映了从数据集D中随机选取两个样本，其类别标记不一致的概率，因此Gini(D)越小，则数据集D的纯度越高。

• 在特征A下数据集D的条件基尼指数为
$$\operatorname{Gini}(D|A)=\sum_{i=1}^n \frac{\left|D_i\right|}{|D|} \operatorname{Gini}\left(D_i\right)$$
基尼指数偏向于特征值较多的特征，类似信息增益。

CART分类树生成算法

输入：训练数据集D，停止计算的条件；

输出：CART决策树

根据训练数据集，从根节点开始，递归地对每个结点进行以下操作，构建二叉决策树：

1. 设结点的训练数据集为D，计算现有特征对该数据集的基尼指数，此时，对每一个特征A，对其可能取的每一个值a,根据样本点A=a的测试为“是”或“否”将D分割成D1和D2两部分，然后计算Gini(D,A)。

2. 在所有可能的特征A以及他们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最佳切分点。依最优特征与最优切分点，从现结点生成两个子节点，将训练数据集依特征分配到两个子节点中去。

3. 对两个子节点递归调用1，2，直至满足停止条件。

4. 生成CART决策树。

算法停止计算的条件是结点中的样本个数小于预定的阈值，或样本集的基尼指数小于预定的阈值（样本基本属于同一类），或者没有更多特征。

 

CART回归树利用平方误差最小化准则进行二分

回归树的关键是如何选择切分点、如何利用切分点划分数据集、如何预测 y 的取值。

CART回归树模型

给定训练数据集$$D=\{(x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N)\}$$，其中x为输入变量，y为输出变量（且y为连续变量）。

假设已将输入空间划分成M个单元$$R_1,R_2,\ldots,R_M$$，并且在每个$$R_m$$上有一个输出$$c_m$$.

回归树模型可以表示为

$$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$$

平方误差最小准则

当输入空间的划分确定时，可以用平方误差来表示回归树对于训练数据的预测误差：

$$\sum_{x_i\in R_m}(y_i-f(x_i))^2$$

用平方误差最小的准则求得每个单元上的最优输出值$$\hat{c}_m$$即Rm上所有实例对应的输出值的平均值：

$$\hat{c}_m=ave(y_i|x_i\in R_m)$$

采用启发式的算法选择切分点

选择切分变量$$x^{(j)}$$和切分点s，定义两个区域$$R_1(j,s)=\{x|x^{(j)}\leq s\}$$和$$R_2(j,s)=\{x|x^{(j)}> s\}$$，求解

$$\min _{j, s}\left[\min _{c_1} \sum_{x_i \in R_1(j, s)}\left(y_i-c_1\right)^2+\min _{c_2} \sum_{x_i \in R_2(j, s)}\left(y_i-c_2\right)^2\right]$$

由上知，当j和s固定时，$$\hat{c}_1=ave(y_i|x_i\in R_1(j,s)),\hat{c}_2=ave(y_i|x_i\in R_2(j,s))$$;

固定j，遍历变量$$x^{(j)}$$所有可能的取值作为切分点，计算不同切分点对应的平方误差，取平方误差最小的取值作为变量变量$$x^{(j)}$$对应的切分点$$s_j$$，由此构成了一个$$(j,s_j)$$对。

遍历j，记录不同j值对应的$$(j,s_j)$$以及其平方误差，选择平方误差最小的$$(j,s_j)$$作为最优切分变量和切分点。

由此可以确定一个节点选择的特征和切分点，以此将区域划分为两个子区域。之后对两个新的子空间递归地进行上述的计算，直到满足停止条件，从而得到整个CART回归树。

CART剪枝

从生成算法产生的决策树$$T_0$$底端开始不断剪枝，直到$$T_0$$的根节点，形成一个子树序列$$\{T_0,T_1,\ldots,T_n\}$$;

从完整树$$T_0$$开始剪枝，其任意内部结点为t，以t为单结点树（即仅t一个结点）的损失函数和以t为根结点的子树Tt的损失函数分别是：

$$\begin{aligned}& C_\alpha(t)=C(t)+\alpha \\& C_\alpha\left(T_t\right)=C\left(T_t\right)+\alpha\left|T_t\right|\end{aligned}$$

• 当$$\alpha=\frac{C(t)-C\left(T_t\right)}{\left|T_t\right|-1}$$时，$$C_\alpha\left(T_t\right)=C_\alpha\left(t\right)$$，即剪枝前后的损失函数相同，当剪枝的节点数更小，故剪枝；

• 当$$\alpha$$比该值小时，$$C_\alpha\left(T_t\right)<C_\alpha\left(t\right)$$，不剪枝；

• 当$$\alpha$$比该值大时，$$C_\alpha\left(T_t\right)>C_\alpha\left(t\right)$$，剪枝。

对于不同的内节点t而言，它们都存在一个对应的α值，使剪枝前后两者的损失相同。此时为了节点更少，应该选择剪枝。但参数α应该怎么设置呢，即用哪个α值使得模型的整体损失更小呢？

1. 为此对$$T_0$$的每个内结点都进行上述的计算，此时α是t的函数，我们用g(t)表示，即$$g(t)=\frac{C(t)-C\left(T_t\right)}{\left|T_t\right|-1}$$，该式表示剪枝后整体损失函数减少的程度。

2. 在$$T_0$$中剪去g(t)最小的$$T_t$$，将得到的子树作为$$T_1$$，同时将最小的g(t)设为$$\alpha_1$$，则T1为区间最小[α1,α2)的最优子树。如此剪枝下去，直至得到根节点，在这一过程中不断增加α的值，产生新的区间。

3. 将剪枝后的所有子树$$\{T_0,T_1,\ldots,T_n\}$$保存起来，得到子树序列。

Breiman 证明：将$$\alpha$$从小增大，$$0=\alpha_0<\alpha_1<\cdots<\alpha_n<\infty$$ ，在每个区间$$[\alpha_i,\alpha_{i+1})$$中，子树$$T_i$$是这个区间里最优的。

CART剪枝算法

CART对缺失值的处理

CART可以处理类别不平衡的问题

CART 使用了一种先验机制，其作用相当于对类别进行加权。这种先验机制嵌入于 CART 算法判断分裂优劣的运算里，在 CART 默认的分类模式中，总是要计算每个节点关于根节点的类别频率的比值，这就相当于对数据自动加权，对类别进行均衡。

对于一个二分类问题，节点 node 被分成类别 1 当且仅当：$$\frac{N_1(\text { node })}{N_1(\text { root })}>\frac{N_0(\text { node })}{N_0(\text { root })}$$

比如二分类，根节点属于 1 类和 0 类的分别有 20 和 80 个。在子节点上有 30 个样本，其中属于 1 类和 0 类的分别是 10 和 20 个。如果 10/20>20/80，该节点就属于 1 类。通过这种计算方式就无需管理数据真实的类别分布。假设有 K 个目标类别，就可以确保根节点中每个类别的概率都是 1/K。这种默认的模式被称为“先验相等”。

先验设置和加权不同之处在于先验不影响每个节点中的各类别样本的数量或者份额。先验影响的是每个节点的类别赋值和树生长过程中分裂的选择。

 

 

 

 

参考链接：

“机器学习”系列之决策树 - 飞桨AI Studio星河社区

“机器学习”系列之决策树，详细讲述基于信息熵、信息增益的ID3，基于信息增益率的C4.5，基于gini指数的CART算法原理，并通过代码进行实现ID3。 - 飞桨AI Studio星河社区

https://aistudio.baidu.com/projectdetail/1700924?ad-from=1636

悲观剪枝

C4.5决策树 - 张朝阳 - 博客园

C4.5决策树在ID3决策树的基础之上稍作改进，请先阅读ID3决策树。 C4.5克服了ID3的2个缺点： 1.用信息增益选择属性时偏向于选择分枝比较多的属性值，即取值多的属性 2.不能处理连贯属性 Outlook和Windy取离散值，Temperature和Humidity则取连续值。 对于离散属性

https://www.cnblogs.com/zhangchaoyang/articles/2842490.html

C4.5缺失值的处理

机器学习笔记（7）——C4.5决策树中的缺失值处理_c4.5方法处理缺失值-CSDN博客

文章浏览阅读1.8w次，点赞60次，收藏147次。缺失值处理是C4.5决策树算法中的又一个重要部分，前面已经讨论过连续值和剪枝的处理方法：机器学习笔记（5）——C4.5决策树中的连续值处理和Python实现机器学习笔记（6）——C4.5决策树中的剪枝处理和Python实现现实任务中，通常会遇到大量不完整的样本，如果直接放弃不完整样本，对数据是极大的浪费，例如下面这个有缺失值的西瓜样本集，只有4个完整样本。在构造决策树时，处理含..._c4.5方法处理缺失值

https://blog.csdn.net/leaf_zizi/article/details/83503167