划分数据集的最大原则是：使无序的数据变的有序。如果一个训练数据中有20个特征，那么选取哪个做划分依据?这就必须采用量化的方法来判断，量化划分方法有多重，其中一项就是“信息论度量信息分类”。基于信息论的决策树算法有ID3、CART和C4.5等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。

决策树的生成算法由很多变形，这里简单说一下几种经典的实现算法：ID3算法，C4.5算法和CART算法。这些算法的主要区别在于分类结点熵特征选择的选取标准不同，下面了解一下算法的具体实现过程。

一：ID3算法

ID3算法所采用的度量标准就是我们前面提到的“信息增益”。当属性a的信息增益最大时，则意味着用a属性划分，其所获得的“纯度”提升最大，我们所要做的，就是找到信息增益最大的属性。

ID3算法的核心是在决策树的各个节点上应用信息增益准则进行特征选择，具体的做法是：

从根节点上开始，对结点计算所有可能特征的信息增益，选择信息增益最大的特征作为结点的特征，并由该特征的不同取值构建子节点;

对于子节点递归的调用以上方法，构建决策树;

直到所有特征的信息增益均很小或者没有特征可选择的时候为止。

ID3算法具体的算法过程如下：

输入的是m个样本，样本输出集合为D，每个样本有n个离散特征，特征集合为A，输出为决策树T。

1，初始化信息增益的阈值€

2，判断样本是否为同一类输出Di，如果是则返回单节点树T，标记类别为Di

3，判断特征是否为空，如果是则返回单节点树T，标记类别为样本值红输出类别D实例数最多的类别

4，计算A中的各个特征(一共n个)对输出D的信息增益，选择信息增益最大的特征Ag

5，如果Ag的信息增益小于阈值€，则返回单节点树T，标记类别为样本中输出类别D实例树最多的类别

6，否则，按特征Ag的不同取值Agi将对应的样本输出D分成不同的类别Di，每个类别产生一个子节点。对应特征为Agi，返回增加了节点的数T

7，对于所有的子节点，令D=Di，A=A-{Ag}递归调用2~6步，得到子树Ti并返回

ID3算法存在的缺点：

1.ID3算法在选择根节点和内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多是属性，在有些情况下这类属性可能不会提供太多有价值的信息。

2.ID3算法只能对描述属性为离散型属性的数据集构造决策树。

3.ID3算法对于缺失值的情况没做考虑。

4.没有考虑过拟合的问题。

以上内容为大家介绍了Python决策树的生成算法介绍，希望对大家有所帮助，如果想要了解更多Python相关知识，请关注IT培训机构:千锋教育。

上一篇

Python之特殊方法与多范式

下一篇

Python 内嵌函数和闭包