机器学习——决策树

决策树基础概念

决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。

每个内部节点（非叶子节点）表示一个属性上的测试条件，每个分支代表一个测试输出结果，每个叶节点代表一种类别

决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。

决策树的构造过程就是找到这些具有决定性作用的特征，根据其决定性程度来构造一个倒立的树–决定性作用最大的那个特征作为根节点，然后递归找到各分支下子数据集中次大的决定性特征，直至子数据集中所有数据都属于同一类。

特征：

有监督的学习
非参数学习算法
自顶向下递归方式构造决策树
在每一步选择中都采取在当前状态下最好\优的选择

决策树生成过程

一棵决策树的生成过程主要分为以下3个部分:

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

基于信息论的三种决策树算法

划分数据集的最大原则是：使无序的数据变的有序。

熵降低的速度越快越好==>树的高度最矮

基于信息论的决策树算法有ID3、CART和C4.5等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。

ID3算法

信息增益作为评估标准，分支节点选择特征X信息增益最大的

可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。使用信息增益的话，其实是有一个缺点，那就是它偏向于具有大量值的属性–就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性

C4.5算法

C4.5是ID3的一个改进算法，继承了ID3算法的优点。

C4.5算法用信息增益率来选择属性，
克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝；
能够完成对连续属性的离散化处理；能够对不完整数据进行处理。

CART算法（Classification And Regression Tree）

**采用的是Gini指数（选Gini指数最小的特征s）**作为分裂标准
同时它也是包含后剪枝操作
ID3和C4.5虽可尽可能挖掘数据信息，但生成的决策树分支较大。CART可以简化决策树的规模，提高生成决策树的效率

决策树优缺点

决策树适用于数值型和标称型（离散型数据，变量的结果只在有限目标集中取值），能够读取数据集合，提取一些列数据中蕴含的规则。在分类问题中使用决策树模型有很多的优点，1.决策树计算复杂度不高、便于使用、而且高效，2.决策树可处理具有不相关特征的数据、3.可很容易地构造出易于理解的规则，而规则通常易于解释和理解。

决策树模型也有一些缺点，比如1.处理缺失数据时的困难、2.过度拟合以及3.忽略数据集中属性之间的相关性等。

ID3数学原理

信息熵(香农熵)：

一种度量不确定性的方式，是用来衡量随机变量不确定性的，熵就是信息的期望值

如果待分类的事物可能划分在多个分类之中，则符号xi的信息定义为 $\mathrm{I}\left(x_{i}\right)=-\log _{2} p\left(x_{i}\right)$ ，其中p(xi)是选择该分类的概率。

有人可能会问，信息为啥这样定义啊？答曰：前辈得出的结论。这就跟1+1等于2一样，记住并且会用即可。上述式中的对数以2为底，也可以e为底(自然对数)。

若随机事件发生的结果记为X，且待分类的事物可能划分在N类中，分别是x1，x2，……，xn，每一种取到的概率分别是P1，P2，……，Pn，那么X的熵就定义为：

$\mathrm{H}=-\sum_{\mathrm{i}=1}^{n} \mathrm{p}\left(x_{i}\right) \log _{2} p\left(x_{i}\right)$

反映了每一个元素在该类别下的不纯度，如{1,2,3,4}跟{1,1,1,2}相比,每个元素1-4的logPi都很大,因此sum的熵就要大很多。

注：有"某个类别的结果"的熵（某个特征有多个值），也有"某事件结果"的熵（该事件有多个特征）。直观来讲，结果种类越多，熵值越大。

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。

经验熵举例：

我们定义贷款申请样本数据表中的数据为训练数据集D，则训练数据集D的经验熵为H(D)。|D|表示其样本容量，即样本个数。设有K个类Ck, = 1,2,3,…,K,|Ck|为属于类Ck的样本个数，因此经验熵公式就可以写为：

$\mathrm{H}(\mathrm{D})=-\sum_{k=1}^{K} \frac{\left|c_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$ ，即 $p(C_k)=\frac{\left|C_{k}\right|}{|D|}$ 由样本数据出来的结果。

根据此公式计算经验熵H(D)，分析贷款申请样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知，在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷。所以数据集D的经验熵H(D)为：

$\mathrm{H}(\mathrm{D})=-\frac{9}{15} \log _{2} \frac{9}{15}-\frac{6}{15} \log _{2} \frac{6}{15}=0.971$

经过计算可知，数据集D的经验熵H(D)的值为0.971。

▲熵值越高，则数据混合的种类越高，其蕴含的含义是一个变量可能的变化越多（反而跟变量具体的取值没有任何关系，只和值的种类多少以及发生概率有关）

条件熵

表示在已知随机变量X的条件下随机变量Y的不确定性，其定义为X在给定条件下Y的条件概率分布的熵对X的数学期望:

$H(Y | X)=\sum_{i=1}^{n} p_{i} H\left(Y | X=x_{i}\right)$ ,其中 $p_{i}=P\left(X=x_{i}\right), i=1,2, \cdots, \mathrm{n}$

经验条件熵举例：

设特征A有n个不同的取值{a1,a2,···,an}，根据特征A的取值将D划分为n个子集{D1,D2，···,Dn}，|Di|为Di的样本个数。记子集Di中属于Ck的样本的集合为Dik，即Dik = Di ∩ Ck，|Dik|为Dik的样本个数

$\begin{align*}\mathrm{H}(\mathrm{D} | \mathrm{A}) & =\sum_{i=1}^{\mathrm{n}} \frac{\left|D_{i}\right|}{|D|} \mathrm{H}\left(D_{i}\right) \\ & =-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}\end{align*}$

信息增益

信息增益(information gain)表示得知特征X的信息后，而使得Y的不确定性减少的程度。定义为集合D的经验熵H(D)与给定特征A条件下D的经验条件熵H(D|A)之差:

$g(D, A)=H(D)-H(D| A)$

一般地，熵H(D)与条件熵H(D|A)之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

举例：以贷款申请样本数据表为例进行说明。看下年龄这一列的数据，也就是特征A1，一共有三个类别，分别是：青年、中年和老年。我们只看年龄是青年的数据，年龄是青年的数据一共有5个，所以年龄是青年的数据在训练数据集出现的概率是5\15，也就是1\3。同理，年龄是中年和老年的数据在训练数据集出现的概率也都是1\3。现在我们只看年龄是青年的数据的最终得到贷款的概率为2\5，因为在五个数据中，只有两个数据显示拿到了最终的贷款，同理，年龄是中年和老年的数据最终得到贷款的概率分别为3\5、4\5。所以计算年龄的信息增益，过程如下：

$\begin{aligned} \mathrm{g}\left(\mathrm{D}, A_{1}\right) &=H(D)-H\left(D | A_{1}\right) \\ &=H(D)-\sum_{i=1}^{\mathrm{n}} \frac{\left|D_{i}\right|}{|D|} \mathrm{H}\left(D_{i}\right) \\ &=H(D)-\left[\frac{\left|D_{1}\right|}{|D|}H\left(\mathrm{D}_{1}\right)+\frac{\left|D_{2}\right|}{|D|} H\left(D_{2}\right)+\frac{\left|D_{3}\right|}{|D|} H\left(D_{3}\right)\right] \\ &=H(D)- \frac{\left|D_{i}\right|}{|D|} \sum_{i=1}^{3} p_{i} * \log _{2} p_{i} \\ &=0.971-\left[\frac{5}{15}\left(-\frac{2}{5} \log _{2} \frac{2}{5}-\frac{3}{5} \log _{2} \frac{3}{5}\right)+\frac{5}{15}\left(-\frac{3}{5} \log _{2} \frac{3}{5}-\frac{2}{5} \log _{2} \frac{2}{5}\right)\right.\\ &\left.+\frac{5}{15}\left(-\frac{4}{5} \log _{2} \frac{4}{5}-\frac{1}{5} \log _{2} \frac{1}{5}\right)\right] \\ &=0.971-0.888=0.083 \end{aligned}$

其中|Di|为特征该类别的数量，Pi为该类别下为true（事件发生）的概率

C4.5数学原理

以信息增益进行分类决策时，存在偏向于取值较多的特征的问题。于是有了基于信息增益比的分类决策方法C4.5。C4.5与ID3都是利用贪心算法进行求解，不同的是分类决策的依据不同。

信息增益比率度量:信息增益比率度量Gain(D，X) \ 分裂信息度量SplitInformation(D，X)

$SplitInformation(D，X） = -\sum_{i=1}^{n}{P_{x_i} }*log_2{P_{x_i} }$

$GainRatio(D,X) = Gain(D,X) \div SplitInformation(D,X)$

CART数学原理

基尼指数GINI

1、是一种不等性度量，表示一个随机选中的样本在子集中被分错的可能性；
2、通常用来度量收入不平衡，可以用来度量任何不均匀分布；
3、是介于0~1之间的数，0-完全相等，1-完全不相等；
4、总体内包含的类别越杂乱，GINI指数就越大（跟熵的概念很相似）

Gini系数的计算方式如下 $Gini(p)=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2}$

上面式子表述的意思就是，加入特征X以后，数据不纯度减小的程度.

如果D为样本数据集， $Gini(D)=1-\sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2}$ 其中Ck是D中属于第k类的样本子集，K是类的个数。

如果D被特征A划分为D1、D2两部分，这个时候就是统计均值，样本数据集D的基尼系数：

$Gini(D, A)=\frac{\left|D_{1}\right|}{|D|} Gini\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} Gini\left(D_{2}\right)$

[统计学习方法：CART算法](https:\www.cnblogs.com\xingshansi\p\6847334.html)

最小二乘回归树

一个回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为M个单元R1,R2,…Rm，并且在每个单元Rm上有一个固定的输出值Cm，于是回归树模型可表示为：

$f(x)=\sum_{m=1}^{M} c_{m} I\left(x \in R_{m}\right)$

模型输出值与实际值的误差： $\sum_{x_{i} \in R_{m}}\left(y_{i}-f\left(x_{i}\right)\right)^{2}$

我们希望每个单元上的Cm，可以是的这个平方误差最小化。易知，当Cm为相应单元的所有实际值的均值时，可以到最优：

$\hat{c}_{m}=ave\left(y_{i} | x_{i} \in R_{m}\right)$

假设，我们选择变量 xj 为切分变量，它的取值 s 为切分点，那么就会得到两个区域：

$\mathrm{R}_{1}(j, s)=\left\{x | x^{(j)} \leq s\right\}, \mathrm{R}_{2}(j, s)=\left\{x | x^{(j)}>s\right\}$

当j和s固定时，我们要找到两个区域的代表值c1，c2使各自区间上的平方差最小：

$\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]$

前面已经知道c1，c2为区间上的平均：

$\hat{c}_{1}=ave\left(y_{i} | x_{i} \epsilon R_{1}(j, s)\right), \hat{c}_{2}=ave\left(y_{i} | x_{i} \epsilon R_{1}(j, s)\right)$

那么对固定的 j 只需要找到最优的s，然后通过遍历所有的变量，我们可以找到最优的j，这样我们就可以得到最优对（j，s）,（特征j，特征分类值s），并s得到两个区间。

这样的回归树通常称为最小二乘回归树（least squares regression tree）。

上述过程表示的算法步骤为:

处理连续数值型特征

C4.5和CART既可以处理离散型属性，也可以处理连续性属性。对于离散型描述属性，处理方法与ID3相同。对于连续分布的特征，其处理方法是：

以C4.5为例子，在C4.5中，对连续属性的处理如下：

1、对特征的取值进行升序排序

2、两个特征取值之间的中点作为可能的分裂点，从分裂点将数据集分成两部分，计算每个可能的分裂点的信息增益（InforGain）。优化算法就是只计算分类属性发生改变的那些特征取值。

3、选择修正后信息增益(InforGain)最大的分裂点作为该特征的最佳分裂点

4、计算最佳分裂点的信息增益率（Gain Ratio）作为特征的Gain Ratio。注意，此处需对最佳分裂点的信息增益进行修正：减去log2(N-1)|D|（N是连续特征的取值个数，D是训练数据数目，此修正的原因在于：当离散属性和连续属性并存时，C4.5算法倾向于选择连续特征做最佳树分裂点）

Q：为什么这边是使用的信息增益率？

A：经证明，在决定连续特征的分界点时采用增益这个指标（因为若采用增益率，splittedinfo影响分裂点信息度量准确性，若某分界点恰好将连续特征分成数目相等的两部分时其抑制作用最大），而选择属性的时候才使用增益率这个指标能选择出最佳分类特征。

剪枝

预剪枝(Pre-pruning)

在构建决策树的过程时，提前停止。

根据一些原则及早的停止树增长，如树的深度达到用户所要的深度、节点中样本个数少于用户指定个数、不纯度指标下降的最大幅度小于用户指定的幅度等
采用检验技术对当前结点对应的样本集合进行检验，如果该样本集合的样本数量已小于事先指定的最小允许值，那么停止该结点的继续生长，并将该结点变为叶子结点，否则可以继续扩展该结点。
▲核心问题是如何事先指定树的最大深度，如果设置的最大深度不恰当，那么将会导致过于限制树的生长，使决策树的表达式规则趋于一般，不能更好地对新数据集进行分类和预测

后剪枝(Post-pruning)

决策树构建好后，然后才开始裁剪。

代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等
是一个边修剪边检验的过程。
- 在决策树的不断剪枝操作过程中，将原样本集合或新数据集合作为测试数据，检验决策树对测试数据的预测精度，并计算出相应的错误率，如果剪掉某个子树后的决策树对测试数据的预测精度或其他测度不降低，那么剪掉该子树。
- ▲关键就是用独立的验证数据集对训练集生长的树进行剪枝

CART剪枝

先来看看剪枝用到的准则函数： $C_{\alpha}(T)=C(T)+\alpha|T_{leaf}|$

C（T）是叶节点特性的度量，C4.3里它是熵的均值，CART决策树里它是基尼系数的概率均值，原理类似。多一个正则项，就是稀疏性约束。 $T_{leaf}$ 为叶子节点个数，越多，损失越大

ID3、C4.5算法中的剪枝原理是给定α，事实上很难一次给出理想的α。CART剪枝不再给定一个α，然后选择最优决策树，而是通过设定不同的α，通过交叉验证选择最优CART树，也就是：

训练集：得到不同的子树;

测试集：交叉验证选择最优树.

从有限个子树 $\left\{T_{0}, T_{1}, \ldots, T_{n}\right\}$ 中计算最优子树，最优子树由验证集得出的测试误差决定，哪个最小就是哪个。

这里就引出了一个问题，每次剪哪一个节点呢？如何让 $T_{leaf}$ 到达一个合适的点呢？先看分析剪枝的两个极端情况：

1）完全没剪：

$C_{\alpha}\left(T_{t}\right)=C\left(T_{t}\right)+\alpha\left|T_{t}\right|$

2）只剩根节点：

$C_{\alpha}(t)=C(t)+\alpha$

在α较小或者为0时，有：

$C_{\alpha}\left(T_{t}\right)<C_{\alpha}(t)$

在α取+∞大时，有：

$C_{\alpha}\left(T_{t}\right)>C_{\alpha}(t)$

α是连续变量，因此总有临界点：

$C_{\alpha}\left(T_{t}\right)=C_{\alpha}(t)$

为了不混淆变量，重新定义：

$g(t)=\frac{C(t)-C\left(T_{t}\right)}{\left|T_{t}\right|-1}$

α大于g(t)就是该剪。简而言之：

对于同一棵树的结点，α都是一样的，当α从0开始缓慢增大（或者从+∞慢慢减小），总会有某棵子树该剪，其他子树不该剪的情况，即α超过了某个结点的g(t)，但还没有超过其他结点的g(t)。这样随着alpha不断增大，不断地剪枝，就得到了n+1棵子树，接下来只要用独立数据集测试这n+1棵子树，试试哪棵子树的误差最小就知道那棵是最好的方案了。

CART剪枝的算法过程

CART剪枝

代码编写注意点

递归的结束条件：

一.到达叶节点

1.当某集合的值全是同一类时，那么该子集直接可作为叶子节点，为一个类别，此时不再下探。

2.在决策树构造过程中可能会出现这种情况：所有特征都作为分裂特征用光了，但子集还不是纯净集（集合内的元素不属于同一类别）。在这种情况下，由于没有更多信息可以使用了，一般对这些子集进行“多数表决”，即使用此子集中出现次数最多的类别作为此节点类别，然后将此节点作为叶子节点，此时不再下探

二.预剪枝条件

1.树的深度达到用户所要的深度

2.节点中样本个数少于用户指定个数

附录

借鉴：