本站原创文章,转载请说明来自《老饼讲解-机器学习》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中用的评估质量的函数用信息增益作为评估函数。
信息增益(Gain)函数:
: 分叉子节点个数
: 所有子节点的总样本数(也即父节点的样本数)
: 第 i 个子节点上样本个数
:第 i 个子节点上第k类样本的个数
:父节点上第 k 类样本的个数
信息增益的意义是,分叉后比分叉前信息量(不确定性)的减少量。
评估函数的推导
(1)节点分类质量
度量单个节点上的分类质量可以用经验熵公式:
:节点上样本个数
: 节点上样本的类别个数
:节点上属于 k 类的样本个数
----------------------------------------------------------------
说明:熵的背景意义是不确定性。
所以,H越大,代表该节点越不能确定它是哪一类。越大,质量越差。
(2)分叉质量
分叉质量 (信息增益)= 分叉前质量 - 分叉后质量
分叉前质量:分叉前是一个单节点,直接用单节点的经验熵即可
分叉后质量:用各个分叉子节点的经验熵加权和(也称为条件经验熵)即可
: 子节点个数
: 所有子节点的总样本数
: 第 i 个子节点上样本个数
:第 i 个子节点上第k类样本的个数
两者相减(分叉前质量 - 分叉后质量)即可得到分叉带来的质量提升---信息增益。
本节讲解ID3的整体算法流程
ID3的算法思想与算法主流程
算法基本是用贪婪算法,即从根节点,逐个逐个节点向下分裂,
每次只要确定分裂哪个变量,分裂之后节点是否还要继续分裂即可
ID3算法主流程
(1) 计算各个变量的信息增益,确定本次由哪个变量分支
(2) 对变量分支后,确定哪些节点是叶子节点,
哪些需要再分,需要再分的就继续由剩余变量分支.
(3) 如果所有节点都不需分支,或所有变量已分完,则停止算法.
细节补充说明
1.成为叶子节点的条件
(1) 该节点按最优秀的变量去分,收益仍然极小,
则该节点不再分,作为叶子节点。
(2) 无变量可分。
(3) 叶子上的样本全属于同一类。
2.如何确定叶节点类别
节点中所属类别最多的类
End