1.写在前面

前面写了关于决策树针对特征离散值和连续值，如何选择问题个数进行了探讨（https://blog.****.net/Suyebiubiu/article/details/102492274），下面我们将用一部分时间讨论“哪一个特征应该作为根节点，哪一些特征应该放在前面”，这样的选择问题，我们将其称为划分选择问题。

2.纯度和非纯度的概念

一般而言，随着划分过程不断执行，我们希望决策树的分支节点所包含的样本尽可能属于同一个类别，这样我们说这个节点的纯度越来越高，与之相反，若一个节点下面的样本有很多不属于这个类别，那么该节点就是“不纯的”，我们说他的非纯度很大。纯度和纯度可以用来度量我们类别划分的如何。我们接下来使用非纯度（IM）作为考量标准，当然了，我们希望非纯度越小越好（纯度对应着最大）。

3.非纯度的熵度量+非纯度的基尼度量

我们知道了非纯度可以用来描述我们的节点的划分是否优秀，非纯度越小越好，说明该节点下面的杂质越少。我们说一半用熵度量和基尼度量来度量非纯度大小。

3.1 信息熵是度量样本集合纯度的一个常用指标

假定当前样本集合D中第K类样本所占的比例为Pk，则D的信息熵定义为

Ent(D)的值越小，则D的纯度就越高。非纯度就越小。所以我们是希望熵值越小越好的。

3.2 基尼度量

其实我们仔细看两个式子，我们可以看到熵度量是Pi*logPi ，而基尼度量是Pi*Pi，也就是说累加和反应的情况实际上是一致的，log函数也是单调递增函数，Pi也是单调递增函数。

4.划分目标

我们在选择节点的时候（也就是选择特征的时候），我们选择最大可以减少非纯度的一个节点，非纯度（杂质）的减少量越大越好。

4.1 基于非纯度变化量的三个指标

4.2 信息增益（熵度量）

一般而言，信息增益越大，表示我们使用这个节点时候，获得的纯度越大，杂质越少，非纯度越小。著名的ID3算法就是以信息增益作为划分的依据。

举例说明：

我们还是以这个数据集为例子，我们可以看到这个数据集中包含了17个训练样例，根据6个特征判断一个瓜是不是好瓜，显然，这个最后分类是两种情况，好瓜+坏瓜。在决策树开始的时候，好瓜比例是P1=8/17，坏瓜比例P2=9/17，于是我们可以计算出根节点的信息熵为

于是，我们根据信息增益的公式可以计算特征“色泽”对应的信息增益为：

这就相当于我们选出来的根节点一样，我们在选出根节点纹理之后，我们还要对接下的特征进行进一步划分，我们以第一个分支清晰为例子，该节点中包含了样例有9个，纹理被选完之后，便不再作为候选划分属性。我们可以使用的属性特征为{色泽，根蒂，脐部，触感}剩下的五种特征，我们基于第一个分支计算出各个特征的信息增益：

通过计算，我们发现根蒂，脐部，触感这三个特征均取得了最大信息增益，我们可以任意选择一个座位划分属性。类似的我们接下来就一个个的计算，就会实现整个决策树的划分。

4.3  增益率（信息增益与数据集D关于问题α的熵值之比）

在上面的介绍中，我们忽略了编号那一列，不将其作为样本特征。但是我们考虑一下，若是考虑这一栏，我们根据信息增益公式可以计算出编号的信息增益为0.998，远大于其他特征，我们说了信息增益越大越好，那么肯定会选择编号作为根节点，那么编号将产生17个分支，每个分支仅仅包含一个样本，这样的决策树节点纯度肯定是最大的，但是这样的决策树并没有泛化能力，不利于对新样本的预测。

实际上，我们同时可以看出，信息增益对于分支数目多的特征有所偏好，为减少这种情况发生，著名的C4.5决策树算法不直接使用信息增益，而是使用了增益率，增益率的定义为：

我们需要注意的是，增益率对分支数目少的特征有所偏好，会优先选择，因此C4.5也并不是直接使用了增益率最大的特征，而是使用了一个启发式。从候选特征中找到信息增益高于平均水平的特征，再从中选择增益率最高的。

4.4 基尼指数

CART决策树使用了基尼指数作为选择标准。数据集D的纯度可以用基尼值来度量

5. 决策树生成过程

5.1 ID3决策树

5.2 C4.5决策树

5.3 CART决策树

 

撒花✿✿ヽ(°▽°)ノ✿.....................