决策树算法-ID3

审核： 施天璐 单华 傅佳 编辑：张翔

一 什么是决策树

决策树是机器学习方法中的一种监督学习算法，表示根据特征对样本进行分类的树形结构，可以用于分类和回归。

它的思路大概是这样的：从根节点开始，按照训练数据的每个特征进行计算，根据每个特征的不确定性将训练数据分配到其子节点（分支），沿着该分支可能达到叶子节点或者到达另一个内部节点，然后对剩余的特征递归执行下去，直到抵达一个叶子节点。当都到达叶子节点时，我们便得到了最终的分类结果。把这种决策分支画成图形很像一棵树的枝干，也就是决策树。

假如有一份关于跳槽的调查问卷,整理后发现,工资涨幅，公司性质，加班多少，距离远近4个指标对员工跳槽的影响比较大,从中抽取出14条数据，并且已知每条记录都有是否跳槽的结果。

假如你是IT穷屌丝一枚,有一个跳槽的机会：工资涨幅—高,公司性质—互联网公司,加班—多,距离—远，那么你犹豫是否应该跳呢?这个问题可以通过决策树来实现。

那决策树有哪些特点？决策树在sklearn中如何使用？带着这个问题请继续往下看,决策树怎么帮助我们解决现实生活中的问题的。

二 决策树的学习过程

特征选择

特征选择是指从训练数据的特征中选择一个特征作为当前节点的分裂点，怎么选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。

决策树生成

根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。树结构来说，递归结构是最容易理解的方式。

剪枝

决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有前剪枝和后剪枝两种。

三 基本概念

信息熵

信息熵是度量随机变量的不确定性。

定义：假设随机变量的可能取值有,对于每一个可能的取值，其概率,因此随机变量的熵：

在分类问题中的意义：信息熵表示分类的不确定性。样本集纯度越高，熵越小;反之，成分越复杂，纯度越低，则熵越大。

信息增益(ID3算法)

以某特征划分数据集前后的熵的差值公式：

是划分前的信息熵,是按照特征X下的条件熵：

在决策树中的意义：信息增益作为决策树选择特征（ID3算法）的衡量指标，目的是为了要建立一个能够准确分类而且尽可能矮的树。在建立决策树的过程中，一个特征的信息增益越大，表明特征对样本的熵减少的能力越强，这个特征使得数据由不确定性变成确定性的能力越强。

缺点：信息增益偏向取值较多的特征。

剪枝

决策树很容易过拟合，往往是因为太过“茂盛”，也就是节点过多，分类过细，所以需要裁剪（Prune Tree）枝叶。主要有前置剪枝和后置剪枝两种策略。

前剪枝就是在树的构建过程（只用到训练集），设置一个阈值，使得在当前分裂节点中分裂前和分裂后的误差超过这个阈值则分裂，否则不进行分裂操作。

后剪枝是是在用训练集构建好一颗决策树后，利用测试集进行的操作。

由于剪枝比较复杂，暂时不在此文中具体介绍。

四 ID3算法

决策树有三种比较经典的算法: ID3, C4.5和CART。

由于ID3是这三个算法的基础，而且其他两个算法是ID3的改进，因此本文主要以ID3为例.

输入：m个样本，每个样本有n个离散特征，特征集合为A，样本输出集合为D,采用前剪枝，信息增益的阈值为ϵ

输出：决策树T。

算法的流程图如下：

五 实例理解算法

还记得开篇的例子吗？现在我们怎么使用构建决策树呢？

计算方法如下：

1. 第一次迭代（即根节点的构建）：

分类之前的信息熵：

按距离分类，特征值有两种（远和近），信息熵分别为：

在特征“距离”下的条件熵为：

因此按距离分类，信息增益为：

同理可得，

Gain(S|加班)=0.151

Gain(S|公司性质)= 0.029

Gain(S|工资涨幅)=0.247

经过第一次迭代，Gain(S|工资涨幅)的信息增益是最大的，因此工资涨幅作为根节点。此时树按照工资涨幅分成了三类（低，一般,高）：

2. 接下来按照工资涨幅的每个特征进行再分类：

对于工资涨幅低的，一共有5个样本，首先计算该样本集的信息熵：

计算距离特征的条件熵：

计算出信息增益：

同理可得:

Gain(S|加班)=0.971

Gain(S|公司性质)= 0.771

由此可见，Gain(公司性质)的信息增益是最大的，因此”公司性质”作为特征值”工资低”的子树。

同理对于特征值”工资一般”，Gain(距离)的信息增益是最大的，因此距离作为特征值”工资一般”的子树。

对于工资高，4个样本都属于同一分类（是），停止计算。

3. 第三次迭代，按照特征向量”加班”继续进行分类

对加班的每个特征进行再分类：

但此时”多”都属于同一类（否），”少”都属于同一类（是），停止分类

同理距离的每个特征也都属于同一类，”近”属于是，”远”属于否

至此，所有的特征都抵达叶子节点，停止分类，递归结束

此时树结构图如下：

因此文章开头的数据（工资涨幅—高,公司性质—互联网公司,加班—多,距离—远）的数据,当然是去了。这也许是互联网公司为什么加班多、离家远也有很多人想去的原因吧，哈哈。

注：此例子纯属虚构

六 ID3算法的优缺点

优点：

1.决策树易于理解和解释，可以可视化分析。

2.决策树分类器的构造不需要任何领域知识或参数设置，

3.适合高维数据

4.可以同时处理标称型和数值型数据

5.计算复杂度不高

缺点：

1.容易出现过拟合

2.对缺失数据处理比较困难

3.忽略数据集中属性的相关性

4.ID3算法计算信息增益时偏向数值较多的特征

5.不支持增量学习

七 Python怎么实现决策树算法

通过调用sklearn库中的sklearn.tree.DecisionTreeClassifier类来实现决策树算法Python实现如下：

[criterion]:string类型，可选（默认为"gini"），支持的标准有"gini"代表的是Giniimpurity(不纯度)与"entropy"代表的是information gain（信息增益）。

[splitter]:string类型，可选（默认为"best"）一种用来在节点中选择分类的策略。支持的策略有"best"，选择最好的分类，"random"选择最好的随机分类。

[max_features]:int,float,stringor None 可选（默认为None），在进行分类时需要考虑的特征数。如果是int，在每次分类是都要考虑max_features个特征。如果是float,那么max_features是一个百分率并且分类时需要考虑的特征数是int(max_features*n_features,其中n_features是训练完成时发特征数)。

[max_depth]:int or None,可选（默认为"None"）表示树的最大深度。如果是"None",则节点会一直扩展直到所有的叶子都是纯的或者所有的叶子节点都包含少于min_samples_split个样本点。忽视max_leaf_nodes是不是为None。

[min_samples_split]:int,float,可选（默认为2）区分一个内部节点需要的最少的样本数。如果是int，min_samples_split为最小的样本数。如果是float，min_samples_split是一个百分率并且ceil(min_samples_split*n_samples)是每个分类需要的样本数。

[min_samples_leaf]:int,float,可选（默认为1）一个叶节点所需要的最小样本数：如果是int，则其为最小样本数;如果是float，则它是一个百分率并且ceil(min_samples_leaf*n_samples)是每个节点所需的样本数。

[min_weight_fraction_leaf]:float,可选（默认为0）一个叶节点的输入样本所需要的最小的加权分数。

[max_leaf_nodes]:int,None 可选（默认为None）在最优方法中使用max_leaf_nodes构建一个树。最好的节点是在杂质相对减少。如果是None则对叶节点的数目没有限制。如果不是None则不考虑max_depth.

八知识扩展

不知道大家看到信息熵、信息增益那些数学公式的时候是什么感觉,我会有以下几个疑问：

1. 熵是怎么来的？

决策树的数学公式不是平白出现的,而是从概率论推到出来的，公式的推导过程请参考：

不过需要注意的是：信息熵的公式是假设各个特征值是相互独立的，因此如果特征之间相互关联，最好不要选择决策树；如果使用决策树，要选择相互独立的特征值。

注：其实C4.5和CART树也是一样的，都是以各个特征值是相互独立为前提条件的

2. 为什么信息增益偏向取值较多的特征？

信息增益的公式为：

因为H(Y)是固定的(如果不太理解，请参考实例理解算法那一部分)，所以G(Y,X)的增减性要看-H(Y|X)，也就是变化后的信息熵。

想象两个极端情况：假设特征X中有两个特征和，的样本特别不纯(等分为m类)，即不会偏向任何一个特征值，那X的条件熵：

而是单调递增函数，m是样本个数，m的取值为大于1的整数，所以，。

而如果的样本特别纯（都属于同一类），即这个类的特征取值较多，则H(Y|X)=log(1)=0，那么：G(Y,X)=H(Y)。因此信息增益偏向取值较多的特征。

3. 为什么引入C4.5？

当然是解决问题2的缺点了，那么怎么解决呢？

C4.5引入了信息增益率作为特征选择的衡量指标。信息增益率：是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。

公式：

，

其中

其实ID3和C4.5可以对比路程与速度的概念。

比如：甲跑了1000米，用了5分钟；乙跑了200米，用了0.5分钟，问谁跑的快?

ID3的意思就是按路程1000米和200米做比较，当然选择1000了；

而C4.5的意思是求速度：

，

(注：没转换成m/s是为了计算简便)

这时可以看出。

本期的决策树-ID3算法就介绍到这了，欢迎大家批评指正并关注我们的公众号。

参考：

https://www.cnblogs.com/muzixi/p/6566803.html

http://scikit-learn.org/dev/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier