机器学习算法 决策树

一、决策树的原理

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

决策树算法的本质是一种图结构，我们只需要问一系列问题就可以对数据 进行分类了。比如说，来看看下面这组数据集，这是一系列已知物种以及所属类别的数据：

我们现在的目标是，将动物们分为哺乳类和非哺乳类。那根据已经收集到的数据，决策树算法为我们算出了下面的这 棵决策树：

假如我们现在发现了一种新物种Python，它是冷血动物，体表带鳞片，并且不是胎生，我们就可以通过这棵决策树 来判断它的所属类别。

可以看出，在这个决策过程中，一直在对记录的特征进行提问。最初的问题所在的地方叫做根节点，在得到结论 前的每一个问题都是中间节点，而得到的每一个结论（动物的类别）都叫做叶子节点。

• 根节点：没有进边，有出边。包含样本全集
• 中间节点：既有进边也有出边，进边只有一条，出边可以有很多条。都是针对特征的提问。
• 叶子节点：有进边，没有出边，每个叶子节点都是一个类别标签

使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。从根结点到每个叶结点的路径对应了一个判定的测试序列。决策树学习的目的是产生一棵泛化能力强，即处理未见示例强的决策树。

决策树算法的核心是要解决两个问题：

1. 如何从数据表中找出最佳节点和最佳分枝？
2. 如何让决策树停止生长，防止过拟合？

二、决策树的构建

决策树最终的优化目标是使得叶节点的总不纯度最低，即对应衡量不纯度的指标最低。

为了要将表中的数据转化为一棵树，决策树需要找出最佳节点和最佳的分枝方法，而衡量这个“最佳”的指标叫做“不纯度”。不纯度基于叶子节点来计算的，所以树中的每个节点都会有一个不纯度，并且子节点的不纯度一定是低于父节点的，也就是说，在同一棵决策树上，叶子节点的不纯度一定是最低的。

不纯度：决策树的每个叶子节点中都会包含一组数据，在这组数据中，如果有某一类标签占有较大的比例，我们就说叶子 节点“纯”，分枝分得好。某一类标签占的比例越大，叶子就越纯，不纯度就越低，分枝就越好。如果没有哪一类标签的比例很大，各类标签都相对平均，则说叶子节点”不纯“，分枝不好，不纯度高。

通常来说，不纯度越低，决策树对训练集的拟合越好。现在使用的决策树算法在分枝方法上的核心大多是围绕在对某个不纯度相关指标的最优化上。若我们定义$t$代表决策树的某节点， $Dt$是$t$节点所对应的数据集，设$p(i|t)$表示给定结点$t$中属于类别$i$的样本所占的比例，这个比例越高，则代表叶子越纯。

熵：物理意义是体系混乱程度的度量。

信息熵：表示事物不确定性的度量标准，可以根据数学中的概率计算，出现的概率就大，出现的机会就多，不确定性就小（信息熵小）。
$$Entropy=\sum _{i=0}^{c-1}p(i|t){\log }_{2}p(i|t)$$
其中$c$表示叶子节点上标签类别的个数， $c-1$表示标签的索引。注意在这里，是从第0类标签开始计算，所以最后的标签类别应该是总共$c$个标签，$c-1$为最后一个标签的索引。在计算$Entropy$时设定${\log }_{2}0=0$ 。

信息增益（ID3）：求父节点信息熵和子节点总信息熵之差

一个父节点下可能有多个子节点，而每个子节点又有自己的信息熵，所以父节点信息熵和子节点信息熵之差，应该是父节点的信息熵 - 所有子节点信息熵的加权平均。其中，权重是使用单个叶子节点上所占的样本量比上父节点上的总样本量来确定的一个权重。
$$I(child)=\sum _{j=1}^k\frac{N(v_j)}{N}I(v_j)$$

信息增益公式如下：

$$InformationGain=I(parent)-I(child)$$

信息增益率（C4.5）：在信息增益计算方法的子节点总信息熵的计算方法中添加了随着分类变量水平的惩罚项分支度。而分支度的计算公式仍然是基于熵的算法，只是将信息熵计算公式中的 $p(i|t)$(即某类别样例占总样例数)改成了$P(v_i)$ ，即某子节点的总样本数占父节点总样本数的比例，这其实就是我们加权求和时的”权重“。这样的一个分支度指标，让我们在切分的时候，自动避免那些分类水平太多，信息熵减小过快的特征影响模型，减少过拟合情况。$IV$计算公式如下：
$$InformationValue=-\sum _{i=1}^{k}P(v_i){\log }_{2}P(v_i)$$

其中，$i$表示父节点的第$i$个子节点，$v_i$表示第$i$个子节点样例数，$P(v_i)$表示第$i$个子节点拥有样例数占父节点总样例数的比例。很明显，IV可作为惩罚项带入子节点的信息熵计算中。可以简单计算得出，当取ID字段作为切分字段时，IV值为 ${\log }_{2}k$。所以IV值会随着叶子节点上样本量的变小而逐渐变大，这就是说一个特征中如果标签分类太多，每个叶子上的IV值就会非常大。在C4.5中，使用之前的信息增益除以分支度作为选取切分字段的参考指标，该指标被称作Gain Ratio（获利比例，或增益率），计算公式如下：
$$GainRatio=\frac{InformationGain}{InformationValue}$$

Gini（基尼）指数：主要用于CART树的纯度判定中：
$$Gini=1-\sum _{i=0}^{c-1}[p(i|t){]}^2$$

2.1 ID3算法构建决策树

ID3采用信息熵来衡量不纯度，此处就先以信息熵为例进行讨论。ID3最优条件是叶节点的总信息熵最小，因此ID3决策树在决定是否对某节点进行切分的时候，会尽可能选取使得该节点对应的子节点信息熵最小的特征进行切分。换而言之，就是要求父节点信息熵和子节点总信息熵之差要最大。对于ID3而言，二者之差就是信息增益，即Information gain

但这里需要注意，一个父节点下可能有多个子节点，而每个子节点又有自己的信息熵，所以父节点信息熵和子节点信息熵之差，应该是父节点的信息熵 - 所有子节点信息熵的加权平均。

局限性

• 分支度越高（分类水平越多）的离散变量往往子节点的总信息熵会更小，ID3是按照某一列进行切分，有一些列的分类可能不会对我需要的结果有足够好的指示。极限情况下取ID作为切分字段，每个分类的纯度都是100%，因此这样的分类方式是没有效益的
• 不能直接处理连续型变量，若要使用ID3处理连续型变量，则首先需要对连续变量进行离散化
• 对缺失值较为敏感，使用ID3之前需要提前对缺失值进行处理
• 没有剪枝的设置，容易导致过拟合，即在训练集上表现很好，测试集上表现很差

2.2 C4.5 算法树的构建

在C4.5中，使用信息增益率作为特征选择的依据，并首先通过引入分支度（IV：Information Value）的概念，来对信息增益的计算方法进行修正。增益比例是我们决定对哪一列进行分枝的标准，我们分枝的是数字最大的那一列，本质是信息增益最大，分支度又较小的列（也就是纯度提升很快，但又不是靠着把类别分特别细来提升的那些特征）。IV越大，即某一列的分类水平越多，Gain ratio实现的惩罚比例越大。当然，我们还是希望GR越大越好。

连续变量处理手段：

在C4.5中，还增加了针对连续变量的处理手段。算法首先会对这一列数进行从小到大的排序，然后 选取相邻的两个数的中间数作为切分数据集的备选点，若一个连续变量有N个值，则在C4.5的处理过程中将产生N-1个备选切分点，并且每个切分点都代表着一种二叉树的切分方案

2.3 CART 树的创建

CART决策树使用“基尼指数”来选择划分属性。数据集D的纯度可用基尼值来度量，Gini(D)越小，则数据集的纯度越高。CART生成的是二叉树，计算量相对来说不是很大，可以处理连续和离散变量，能够对缺失值进行处理。

三、决策树的优缺点

优点：

• 速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。
• 准确性高：挖掘出的分类规则准确性高，便于理解，决策树可以清晰的显示哪些字段比较重要。
• 非参数学习，不需要设置参数。

缺点：

• 决策树很容易过拟合，很多时候即使进行后剪枝也无法避免过拟合的问题，因此可以通过设置树深或者叶节点中的样本个数来进行预剪枝控制；
• 决策树属于样本敏感型，即使样本发生一点点改动，也会导致整个树结构的变化，可以通过集成算法来解决；