【十分钟 机器学习 系列课程】 讲义（二十一）：决策树的生成

欢迎回来。上篇讲义【十分钟 机器学习 系列课程】 讲义（二十）：选择最优特征-信息增益我们给大家介绍了如何计算「信息增益」和「信息增益比」来选择最优特征，那么今天我们就要一起用ID3算法生成一棵决策树。

壹 算法解说

最早的决策树算法是由Hunt Earl B提出的CLS(Concept Learning System)，但是没有明确给出采用什么方法选择最优特征。

接着由罗斯昆（J. Ross Quinlan）提出「ID3算法」，并且确定用「信息增益」选择最优特征。

接着罗斯昆（J. Ross Quinlan）对ID3算法又进行了优化，得出「C4.5算法」，用「信息增益比」来选择最优特征，注意哦，其实两个方法的算法思路是一样的，「唯一就是最优特征的选择依据不同」，ID3算法侧重于选择数量较多的某一特征，C4.5算法侧重于某一特征单位数量的选择，并且可以计算离散和连续的变量，当然计算过程会比较麻烦，当数据量很大时，对程序运行的硬件就要求很高啦。Anyway, 在2006年的国际数据挖掘大会，C4.5这个算法就被票选为「十大算法之首」。

今天我们将一起来重点学习ID3算法，因为C4.5算法只是把信息增益变成了信息增益比。

贰 解读ID3算法

「输入」：训练数据集 ，特征集 ，阈值

「输出」：决策树

Step1 判断 是否需要选择特征生成决策树

「Case 1」 若 中所有实例属于「同一类」，则 为「单结点树」，记录实例类别 ，以此作为该结点的类标记，并返回 。

「Case 2」 若 中所有实例「无任何特征」 ( )，则 为「单结点树」，记录 中实例个数最多类别 ，根据多数表决原则，以此作为该结点的类标记，并返回 。

Step2 否则，计算 中各特征的信息增益，并选择信息增益最大的特征

「Case 1」若 的「信息增益小于 」，则 为「单结点树」，记录 中实例个数最多类别 ，以此作为该结点的类标记，并返回 。

「Case 2」否则，按照 的每个可能值 ，将 分为若干非空子集 ，将 中「实例个数最多的类别作为标记」，构建子结点，以结点和其子节点构成 ，并返回 。

Step3 第 个子结点，以 为训练集， 为特征集合，递归地调用以上步骤，得到子树 。

我们一起来看一个流程图你就明白啦。

从这个图中，我们可以知道决策树思想的核心在于当每个迭代出来的训练集计算出的最大信息增益小于阈值时，「生成单结点树才可终止」。

叁 例题讲解

如果上面这个流程图你还没有搞明白，别担心，咱们直接上题。

还是上次的例子，训练集 ，特征集分别是 年龄， 是否有工作， 是否有自己的房子， 信贷情况，类别为 =是， =否。

还记得咱们上篇讲义计算出来的最大信息增益属于哪个特征不？

没错，正是有自己的房子 这个特征。

好啦，下一步，就是最关键的迭代开始，也就是上面那个流程图中的粉色部分，我们把是否有自己的房子进行分类，「可以看出有房子的，都是单一的叶结点，同意贷款」。那没有房子的该怎么办呢？

接着，把没房子的训练集作为新的训练集 ，把剩下的年龄 、是否有工作 、信贷情况 作为新的特征集，再来计算一下这三个特征下的最大信息增益。

对应的表达式写成：

从没有房子的选择中看出，共有 个，其中有 个同意贷款， 个不同意贷款。那么经验熵可以写成：

继续，来看看 ，在 这个特征里面，我们把没有房子的摘出来，然后统计一个表格看看：

代入计算：

「 青年时」

「 中年时」

可以看出对于这个子集都是同意贷款，那么它的经验条件熵就为 。

「 老年时」

那么经验条件熵 为：

好啦，接下来我们要继续计算是否有工作 、信贷情况 的信息增益。小伙伴们最好也自己算一算哦，看看是不是和下面这个表格一样。

这里面对应的最大信息增益就是「是否有工作」啦，那么我们下一个特征就选它。

继续绘制决策树吧！

对于这个例子而言，整棵决策树只用了两个特征，因为他们的子集都是属于一个类别的，对于有房子都是同意贷款，对于没有房子的都是不同意贷款，「因此就满足了一开始流程图里的单一叶结点要求，决策树就生成啦！」

感兴趣的同学还可以自己在计算一下用「信息增益比」来绘制决策树哦。

好啦，关于如何生成决策树方法就介绍到这里，感兴趣的小伙伴可以点击视频链接继续学习哦，我们下期不见不散~