本站原创文章，转载请说明来自《老饼讲解-机器学习》www.bbbdata.com
本文讲解ID3决策树的模型和思想，是决策树模型相关知识的补充。
备注：本文需建立在CART决策树的认识上再进行阅读，注意CART和ID3的区别。
本文背景
常见的决策树算法包括ID3、C4.5和CART三种
CART和【ID3,C4.5】是两条不同的分支，
ID3算法和C4.5算法提出比较早，但目前主流是使用CART算法
在软件算法包里，一般都只看到CART算法了
尽管ID3和C4.5已经是一条在实际使用中逐渐遗弃的算法分支，
但它们仍有独特的闪光的地方
本文讲解ID3,C4.5的思路，但不再对它们落地代码，
也不建议大家花太多时间在上面
本节讲解ID3决策树模型是什么，并通过与CART决策树的差异对比来进一步掌握ID3决策树
ID3决策树-模型结构
ID3决策树模型如下：
ID3决策树模型也是一棵树，输入变量必须全是枚举型
每个节点选择一个变量，按该变量所有可能取值分叉
ID3决策树需要确定的内容
（1）节点选择哪个变量分叉
（2）节点是否能成为叶子节点
（3）如果是叶子节点，该叶子节点的属于哪一类
ID3与CART树结构的差异
（1）变量类型
CART的输入是连续变量，ID3的输入变量是枚举变量
（2）分叉类型
CART是二叉树，每次只作二分叉，
而ID3分叉是选举的变量，有多少个枚举值，就分多少个叉
（3）层数上限
CART如果在第一层选择了身高变量分叉，
那第二层，仍然可以选择身高来分叉
而ID3如果在第一层选择了身高，
那第二层只能选择身高以外的变量来分叉，
所以，ID3的层数<=变量个数
(4) 变量分叉点
CART在确定变量后，还需要确定分割值来作为分叉点，
而ID3不需要，它直接按变量枚举个数分叉
总结：相比CART, ID3更原始，简单，粗爆
本节介绍ID3决策树分叉时使用的评估函数
ID3决策树的评估函数
每次分叉时，需要确定选择哪一个变量，
因此需要一个评估函数来衡量分叉质量。
ID3中用的评估质量的函数用信息增益作为评估函数。
信息增益(Gain)函数：
： 分叉子节点个数
： 所有子节点的总样本数（也即父节点的样本数）
： 第 i 个子节点上样本个数
：第 i 个子节点上第k类样本的个数
：父节点上第 k 类样本的个数
信息增益的意义是，分叉后比分叉前信息量(不确定性)的减少量。
评估函数的推导
（1）节点分类质量
度量单个节点上的分类质量可以用经验熵公式：
：节点上样本个数
: 节点上样本的类别个数
:节点上属于 k 类的样本个数
----------------------------------------------------------------
说明：熵的背景意义是不确定性。
所以，H越大，代表该节点越不能确定它是哪一类。越大，质量越差。
（2）分叉质量
分叉质量 （信息增益）= 分叉前质量 - 分叉后质量
分叉前质量：分叉前是一个单节点，直接用单节点的经验熵即可
分叉后质量：用各个分叉子节点的经验熵加权和（也称为条件经验熵）即可
： 子节点个数
： 所有子节点的总样本数
： 第 i 个子节点上样本个数
：第 i 个子节点上第k类样本的个数
两者相减（分叉前质量 - 分叉后质量）即可得到分叉带来的质量提升---信息增益。
本节讲解ID3的整体算法流程
ID3的算法思想与算法主流程
算法基本是用贪婪算法，即从根节点，逐个逐个节点向下分裂，
每次只要确定分裂哪个变量，分裂之后节点是否还要继续分裂即可
ID3算法主流程
(1) 计算各个变量的信息增益,确定本次由哪个变量分支
(2) 对变量分支后,确定哪些节点是叶子节点，
哪些需要再分，需要再分的就继续由剩余变量分支.
(3) 如果所有节点都不需分支,或所有变量已分完,则停止算法.
细节补充说明
1.成为叶子节点的条件
(1) 该节点按最优秀的变量去分，收益仍然极小，
则该节点不再分，作为叶子节点。
(2) 无变量可分。
(3) 叶子上的样本全属于同一类。
2.如何确定叶节点类别
节点中所属类别最多的类
End
