本站原创文章，转载请说明来自《老饼讲解-机器学习》www.bbbdata.com
ID3是较早的决策树模型，它采用基于信息熵的信息增益函数来对节点进行分枝
本文讲解ID3决策树的模型和思想，是决策树模型相关知识的补充
通过本文，可以了解ID3决策树模型是什么，以及ID3的相关公式的具体意义
备注：本文需建立在CART决策树的认识上再进行阅读，阅读时注意ID3与CART的区别
前言
常见的决策树算法包括ID3、C4.5和CART三种，
其中，ID3算法和C4.5算法提出得比较早，但现在一般已经很少使用了
目前主流是使用CART算法，一般的软件算法包里，都只有CART算法
尽管ID3和C4.5已经在实际使用中逐渐遗弃，但它们仍有独特的、闪光的地方
本文讲解ID3的思路，但不再对它落地代码，也不建议大家花太多时间在上面
本节讲解ID3决策树模型是什么，并与CART决策树进行对比
ID3决策树模型
ID3决策树模型如下：
ID3决策树模型也是一棵树，它的输入变量必须全是枚举型
它的每个节点都选择一个变量，然后按该变量所有取值可能进行分枝
ID3决策树需要确定的内容如下：
1. 节点选择哪个变量分枝
2. 节点是否能成为叶子节点
3. 如果是叶子节点，该叶子节点的属于哪一类
ID3与CART的树结构差异
ID3与CART决策树的模型结构差异如下：
1. 变量类型
CART的输入是连续变量，ID3的输入变量是枚举变量
2. 分叉类型
CART是二叉树，每次只作二分叉
而ID3分叉是选举的变量，有多少个枚举值，就分多少个叉
3. 层数上限
CART如果在第一层选择了身高变量分叉，那第二层，仍然可以选择身高来分叉
而ID3如果在第一层选择了身高，那第二层只能选择身高以外的变量来分叉
所以，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
