本站原创文章，转载请说明来自《老饼讲解-机器学习》www.bbbdata.com
ID3决策树是罗斯.昆兰（J. Ross Quinlan）于1975年提出的一种基于信息增益函数的决策树模型
本文讲解ID3决策树的模型结构、模型思想原理，以及ID3决策树的算法流程
通过本文，可以快速了解ID3决策树模型是什么，以及ID3决策树的相关公式的具体意义
前言
ID3算法是相对较早的算法，现在已经一般都不使用了，而是使用CART决策树
但ID3作为一个经典算法，仍然有独特的、闪光的地方
本文讲解ID3算法是什么，包括它的思想、模型结构以及相关公式
由于一般的软件已经不实现ID3，实际中也很少使用
因此本文不提供代码实现，事实上也不建议大家花太多时间在ID3决策树上面
备注：本文需建立在CART决策树的认识上再进行阅读，阅读时注意ID3与CART的区别
本节讲解ID3决策树模型是什么，并与CART决策树进行对比
ID3决策树模型
ID3是最早的决策树模型算法，由罗斯.昆兰（J. Ross Quinlan）于1979年提出
ID3决策树模型简单而朴素，它模仿人类的决策方式，用于解决模式识别(分类)问题
ID3决策树模型如下：
ID3决策树模型与CART决策树一样，都是一棵树，但它的输入变量必须全是枚举型
它在每个节点都选择一个变量，然后按变量的所有取值可能进行分枝
如图所示，一棵ID3决策树由3部分构成：
1. 节点选择哪个变量分枝
2. 节点是否能成为叶子节点
3. 如果是叶子节点，该叶子节点的属于哪一类
ID3与CART树的比较
下面不妨通过ID3决策树与CART决策树的比较，来进一步加深对ID3决策树的理解
ID3与CART决策树的模型结构差异如下：
1. 变量类型
CART的输入是连续变量，ID3的输入变量是枚举变量
2. 分叉类型
CART决策树是一棵二叉树，即每次只作二分叉
而ID3是全分叉，它对节点变量的枚举值全分叉，变量有多少个枚举值就分多少个叉
所以CART需要指定分裂阈值，而ID3并不需要，因为它是全分裂
3. 层数上限
CART如果在第一层选择了身高变量分叉，那第二层，仍然可以选择身高来分叉
而ID3如果在第一层选择了身高，那第二层只能选择身高以外的变量来分叉，即变量不可重复
因此，CART可能会有很多层，因为它的变量可重复利用，而ID3的层数必定<=变量个数
4. 变量分叉点
CART在确定节点所选择的变量后，还需要确定变量的分割阈值，根据阈值来分叉
而ID3不需要，它直接按变量枚举个数进行全分叉，因此它不需要阈值
一句话总结：相比CART, ID3更原始、简单、粗爆，它就是枚举变量全分叉
本节介绍ID3决策树分叉时使用的评估函数
ID3的分叉评估函数
ID3每次分叉时，需要确定选择哪一个变量，因此需要一个函数来评估分叉质量
在ID3算法中，使用信息增益作为分叉质量评估函数
信息增益(Gain)函数如下：
其中，
：分叉子节点个数
：所有子节点的总样本数（也即父节点的样本数）
：第 i 个子节点上样本个数
：第 i 个子节点上第k类样本的个数
：父节点上第 k 类样本的个数
信息增益的意义是，分叉后比分叉前信息量(不确定性)的减少量
信息增益函数的推导
ID3的信息增益(Gain)函数的意义就是，分叉后比分叉前信息量(不确定性)的减少量
信息增益函数的详细推导如下：
1. 节点分类质量
度量单个节点上的分类质量可以用经验熵公式：
其中
：节点上样本个数
：节点上样本的类别个数
：节点上属于 k 类的样本个数
说明：熵的背景意义是不确定性
所以，H越大，代表该节点越不能确定它是哪一类，越大质量就越差
2. 分叉质量
分叉质量 （信息增益）= 分叉前质量 - 分叉后质量
分叉前质量：分叉前是一个单节点，直接用单节点的经验熵即可
分叉后质量：用各个分叉子节点的经验熵加权和（也称为条件经验熵）即可
其中，
：子节点个数
：所有子节点的总样本数
：第 i 个子节点上样本个数
：第 i 个子节点上第k类样本的个数
两者相减（分叉前质量 - 分叉后质量）就得到了分叉带来的质量提升--信息增益
本节讲解ID3的整体算法流程
ID3决策树-算法流程
算法基本是用贪婪算法，即从根节点，逐个逐个节点向下分裂，
每次只要确定分裂哪个变量，分裂之后节点是否还要继续分裂即可
ID3算法主流程
ID3算法主流程如下：
1. 计算各个变量的信息增益，确定本次由哪个变量分支
2. 对变量分支后,确定哪些节点是叶子节点
哪些需要再分，需要再分的就继续由剩余变量分支
3. 如果所有节点都不需分支,或所有变量已分完,则停止算法
其中，成为叶子节点的条件如下：
(1) 该节点按最优秀的变量去分，收益仍然极小
则该节点不再分，作为叶子节点
(2) 无变量可分
(3) 叶子上的样本全属于同一类
叶子节点的类别如下确定：
叶子节点的样本中，哪个类别的样本最多，则节点就是哪个类别
好了，以上就是ID3决策树的算法流程与相关公式了~
End
评论
