决策树算法流程图 决策树经典算法ID3-我的第一篇博客

介绍

	决策树是机器学习中一种常见的分类算法，属于有监督学习算法(至于什么是有监督学习，什么是无监督学习读者可以自行百度)。决策树算法有多种，ID3算法是其中一种经典的决策树算法，这种算法的核心是信息熵（至于什么是信息熵，后面会进行详细介绍）。现在已经商用的决策树算法C45，C50等都是在ID3的基础上进行改进优化而来。

一些条款

1、分类特点

例如，一个数据集有五个属性（或五个字段）A、B、C、D、E。这五个属性不是相互独立的，而是有某种联系的。基于这个连接，可以

一个或多个其他属性的值可以由某些属性的值来确定。例如，E的值可以由属性A、B、C、D的值来确定。决策树算法就是用来对这些属性之间的关系进行建模并确定这种关系。这时，就有了新的记录A1、B1、C1、D1。对于属性E1的位置，可以使用该模型来确定关系。预测E1的值。这听起来是不是很像回归分析的思想呢？事实上，回归分析主要用于处理连续数据，而经典的ID3算法只能用于处理离散值。基于改进的ID3算法的C45和C50可用于处理连续值。

说了这么多，什么是分类特征呢？上述用于构建决策树的属性A、B、C、D是分类特征，属性E的值就是我们想要确定的类别。

2.信息熵

我第一次接触熵的概念是在高中学习化学的时候。似乎是用来分析化学反应的能量方向的。我记不清具体是怎么用的了。事实上，化学中的熵源自信息论中的熵——信息熵，由“信息论之父”香农提出。

信息熵是数据混乱程度的度量，其值范围为0到1。信息熵越大，数据越混乱和不规则，越不利于建模和分类。信息熵的计算公式如下：

下面通过具体例子来说明信息熵的计算方法：

以上是一组关于是否购买电脑的问卷记录。根据这组数据构建决策树，研究是否购买电脑与年龄、收入水平、单身状况、信用评级这四个属性之间的关系。该组数据的信息熵计算方法如下：

购买电脑的记录有 9 条，概率为 p1=9/14，不购买电脑的记录有 5 条，概率为 5/14。因此，信息熵H=-9/14log2(9/14)-5/14log2(5/14)=0.94028。计算出的信息熵接近1，说明数据集非常混乱。如果不经过任何处理，直接根据这个数据集来判断一个人是否购买电脑，极有可能会出错。

3、信息增益

信息熵用来描述一组数据的混乱程度，而信息增益则恰恰相反。信息增益是衡量一组数据从状态0转变到状态1的确定性增加程度的指标。信息增益越大，数据的确定性增加得越多。

构建决策树的过程就是对一组数据不断分类和细化的过程。在对是否购买电脑的数据集进行分类时，可以考虑年龄、收入水平、是否单身、信用评级这四个分类特征。但是，利用这四种分类特征进行分类时应该有一个顺序。首先使用年龄。是使用参考进行分类决策树算法流程图，还是先使用其他三个分类特征之一进行分类，判断的依据是信息熵。

假设以年龄作为分类特征，则上述这组数据可以分为以下三类：

4少年：这组数据的信息熵H1=-3/5log2(3/5)-2/5log2(2/5)=0.97095

4中年人：这组数据的信息熵H2=-1log2(1)-0log2(0)=0

5位老人：这组数据的信息熵H3=-3/5log2(3/5)-2/5log2(2/5)=0.97095

综合上述计算结果可以看出，以年龄作为当前分类特征时，信息熵为H_age=5/14H1+4/14H2+5/14*H3=0.69496。从前面的计算可以看出，在不考虑任何分类特征的情况下，整体信息熵H_total=0.94028。由此可以得出，使用年龄作为当前分类特征后，数据集的信息熵变化值ΔH=H_total-H_age=0.24532，信息熵变小，数据的混乱程度降低，确定性增加，确定性的测量值增加 信息增益等于信息熵的变化值ΔH，即年龄属性的信息增益等于ΔH=0.24532。

4. 最佳分类特征

根据上述信息增益的计算方法，分别计算年龄、收入水平、信用等级、是否单身的信息增益。信息增益最大的属性对数据集的确定性增加最多，对当前的分类最有利。应该作为当前优先的特征，该属性是当前最好的分类特征。

决策树构建过程

决策树的构建是一个递归调用过程，其流程图如下：

注意事项

1、终止条件的选择

如上所述，决策树的构建是一个递归调用的过程。既然是递归，就必须有递归终止条件。常用的递归终止条件如下：

2. 不完美训练样本的处理

对于这一点，通过具体例进行说明。以下是根据示例中的数据构建的决策树：

在构建决策树的过程中，可能会出现一种情况：用于构建决策树的数据集，即训练样本数据不完整。例如，对于属性信用评级，训练样本中只有两个值：良好和平均。使用测试样本对构建的决策树进行测试时，可能存在信用评级属性为优秀或较差的记录。由于构建的决策树根本没有这两个分支，因此在测试样本验证中会造成死循环或者验证。错误（其实我一开始并没有考虑这种情况，是在算法验证过程中程序报错，出现死循环，排查了很久才发现的）。针对这种情况，我的解决方案是在构建决策树的过程中对每个节点（子数据集）进行投票，即不考虑继续向下细分，该节点最终属于类别。在算法验证过程中，如果一条记录找不到继续向下的子树，但未达到递归终止条件，则将该节点投票所属的类别作为该记录的最终类别。

3. 决策树的表示

我用来实现算法的编程语言是python，我用一个列表来保存最终的决策树。结构如下？ dt=[父边，根节点，投票类别，[子树1]，[子树2]，[子树3]，…………]。仍然以例子中的数据为例，最终的决策树结构如下：

[None, '年龄', '买', ['青少年', '是否单身', '不买', ['否', '不买', '不买', [], []], ['是', '买', '买', [], []]], ['中年', '买', '买', [], []], ['老年', '信用等级', '买', ['一般', '买', '买', [], []], ['良好', '不买', '不买', [], []]]]

算法验证

我使用交叉验证策略来验证所实现的算法。数据集为car_evaluation，包括购买-购买价格、维护-保养价格、门数-车门数量、人数-乘客数量、行李箱-后备箱-后备箱容积、安全性-安全性的六个属性，通过这些属性来评估汽车的性价比可以判断一辆车。

具体来说，将样本随机分为10份，其中9份样本作为训练集构建决策树，剩余1份样本作为测试集进行测试，不断循环，直到每个样本都被用作决策树。一个测试集。测试，输出每个测试集的准确率以及最终10个样本的综合准确率。最终结果如下：

从上面的验证结果可以看出，构建的决策树的预测精度是比较高的，但有时并不总是越高越好。预测精度太高意味着可能存在过拟合。

总结

（如果我太懒的话我就发图）

代码和数据：

百度云：（提取码：bdmp

CSDN：

胡说八道

第一篇博客从我决定写它到完成它花了将近一天的时间。之前在CSDN上看过很多人的博客，想过有一天在上面写点东西，但总是一拖再拖：一是因为我很懒，写的很烂，又怕别人看不下去如果我写的话。我明白，浪费自己的时间和大家的时间决策树算法流程图，实在是一种罪过。第二，我是个菜鸟，没什么有用的东西可写，所以最好不要创造有营养的学术垃圾。后来我发现我写的食物只是食物。应该算是一点学习经验吧。再加上我寒假有时间，所以就诞生了这个博客。可能会是最后一篇了（写博客就像做笔记一样，对于懒人来说太痛苦了）。