ID3算法
ID3和C4.5都是由澳大利亚计算机科学家Ross Quinlan开发的决策树构建算法,其中C4.5是在ID3上发展而来的。
ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归地构建决策树。具体方法是:从根结点(root node)开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子结点;再对子结点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一棵决策树。ID3相当于用极大似然法进行概率模型的选择。 下面我们给出一个更加正式的ID3算法的描述:
若D中所有实例属于同一类Ck,则T为单结点树,并将类Ck作为该结点的类标记,返回T;
若A=∅,则T为单结点树,并将D中实例数最大的类Ck作为该结点的类标记,返回T;
否则,计算A中各特征对D的信息增益,选择信息增益最大的特征Ag;
(1) 如果Ag的信息增益小于阈值ϵ,则置T为单结点树,并将D中实例数最大的类Ck作为该结点的类标记,返回T;
(2) 否则,对Ag的每一可能值ai,依Ag=ai将D分割为若干非空子集Di,将Di中实例数最大的类作为标记,构建子结点,由结点及其子结点构成树T,返回T;
对第i个子结点,以Di为训练集,以A−{Ag}为特征集,递归地调用步骤(1)~(3),得到子树Ti,返回Ti。
下面我们来看一个具体的例子,我们的任务是根据天气情况计划是否要外出打球:
首先来算一下根节点的熵:
然后再分别计算每一种划分的信息熵,比方说我们选择Outlook这个特征来做划分,那么得到的信息熵为
据此可计算采用Outlook这个特征来做划分时的信息增益为
同理,选用其他划分时所得到之信息增益如下:
取其中具有最大信息增益的特征来作为划分的标准,然后你会发现其中一个分支的熵为零(时间中阈值可以设定来惩罚过拟合),所以把它变成叶子,即得
对于其他熵不为零(或者大于预先设定的阈值)的分支,那么则需要做进一步的划分
根据上述的规则继续递归地执行下去。最终,我们得到了如下一棵决策树。
C4.5算法
C4.5是2006年国际数据挖掘大会票选出来的十大数据挖掘算法之首,可见它应该是非常powerful的!不仅如此,事实上,C4.5的执行也相当的straightforward。
C4.5算法与ID3算法相似,C4.5算法是由ID3算法演进而来的。C4.5在生成的过程中,用信息增益比来选择特征。下面我们给出一个更加正式的C4.5算法的描述:
如果D中所有实例属于同一类Ck,则置T为单结点树,并将Ck作为该结点的类,返回T;
如果A=∅,则置T为单结点树,并将D中实例数最大的类Ck作为该结点的类,返回T;
否则,计算A中各特征对D的信息增益比,选择信息增益比最大的特征Ag;
(1) 如果Ag的信息增益比小于阈值ϵ,则置T为单结点树,并将D中实例数最大的类Ck作为该结点的类,返回T;
(2) 否则,对Ag的每一可能值ai,依Ag=ai将D分割为若干非空子集Di,将Di中实例数最大的类作为标记,构建子结点,由结点及其子结点构成树T,返回T;
对结点i,以Di为训练集,以A−{Ag}为特征集,递归地调用步骤(1)~(3),得到子树Ti,返回Ti。
How to do it in practice?
易见,C4.5跟ID3的执行步骤非常类似,只是在划分时所采用的准则不同。我们这里不再赘述。但是这里可以来看看在实际的数据分析中,该如何操作。我们所使用的数据是如下所示的一个csv文件,文件内容同本文最初给出的Play Ball例子中的数据是完全一致的。
使用Weka进行数据挖掘是非常容易的,你不再需要像R语言或者MATLAB那样编写代码或者调用函数。基于GUI界面,在Weka中你只需要点点鼠标即可!首先我们单击“Explorer”按钮来打开操作的主界面,如下图所示。
然后我们单击“Open File…”,并从相应的目录下选择你要用来进行模型训练的数据文件,如下图所示。
Weka提供了非常易于操作的各种数据预处理功能,你可以自己尝试探索一下。注意到属性Day其实在构建决策树时是不需要的,我选中该属性,并将其移除,如下图所示。
完成数据预处理后,我们就可以开始进行模型训练了。因为我们是要建立决策树,所以选择“Classify”选项卡,然后在“Classifier”中选择J48。你可以能会疑惑我们不是要使用C4.5算法建立决策树吗?为什么要选择J48呢?其实J48是一个开源的C4.5的Java实现版本(J48 is an open source Java implementation of the C4.5 algorithm),所以J48就是C4.5。 数据分析师培训
然后你可以自定义的选择“Test options”中的一些测试选项,这里我们不做过多说明。然后单击“Start”按钮,Weka就为我们建立了一棵决策树,你可以从“Classifier output”栏目中看到模型训练的一些结果。但是对于决策树而言,你可以觉得文字看起来还不够直观。不要紧,Weka还为你提供了可视化的决策树建模呈现。为此,你需要右键单击刚刚训练好的模型,然后从右键菜单中选择“Visualize tree”,如下图所示。
最后我们得到了一棵与前面例子中相一致的决策树,如下图所示。
在后续的决策树系列文章中,我们将继续深入探讨CART算法等相关话题。
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
2025年是智能体(AI Agent)的元年,大模型和智能体的发展比较迅猛。感觉年初的deepseek刚火没多久,这几天Manus又成为媒体头条 ...
2025-03-14以下的文章内容来源于柯家媛老师的专栏,如果您想阅读专栏《小白必备的数据思维课》,点击下方链接 https://edu.cda.cn/goods/sh ...
2025-03-13以下的文章内容来源于刘静老师的专栏,如果您想阅读专栏《10大业务分析模型突破业务瓶颈》,点击下方链接 https://edu.cda.cn/go ...
2025-03-12以下的文章内容来源于柯家媛老师的专栏,如果您想阅读专栏《小白必备的数据思维课》,点击下方链接 https://edu.cda.cn/goods/sh ...
2025-03-11随着数字化转型的加速,企业积累了海量数据,如何从这些数据中挖掘有价值的信息,成为企业提升竞争力的关键。CDA认证考试体系应 ...
2025-03-10推荐学习书籍 《CDA一级教材》在线电子版正式上线CDA网校,为你提供系统、实用、前沿的学习资源,助你轻松迈入数据分析的大门! ...
2025-03-07在数据驱动决策的时代,掌握多样的数据分析方法,就如同拥有了开启宝藏的多把钥匙,能帮助我们从海量数据中挖掘出关键信息,本 ...
2025-03-06在备考 CDA 考试的漫漫征途上,拥有一套契合考试大纲的优质模拟题库,其重要性不言而喻。它恰似黑夜里熠熠生辉的启明星,为每一 ...
2025-03-05“纲举目张,执本末从。”若想在数据分析领域有所收获,一套合适的学习教材至关重要。一套优质且契合需求的学习教材无疑是那关 ...
2025-03-04以下的文章内容来源于刘静老师的专栏,如果您想阅读专栏《10大业务分析模型突破业务瓶颈》,点击下方链接 https://edu.cda.cn/go ...
2025-03-04在现代商业环境中,数据分析师的角色愈发重要。数据分析师通过解读数据,帮助企业做出更明智的决策。因此,考取数据分析师证书成为了许多人提升职业竞争力的选择。本文将详细介绍考取数据分析师证书的过程,包括了解证书种类和 ...
2025-03-03在当今信息化社会,大数据已成为各行各业不可或缺的宝贵资源。大数据专业应运而生,旨在培养具备扎实理论基础和实践能力,能够应 ...
2025-03-03数据分析师认证考试全面升级后,除了考试场次和报名时间,小伙伴们最关心的就是报名费了,报 ...
2025-03-032025年刚开启,知乎上就出现了一个热帖: 2024年突然出现的经济下行,使各行各业都感觉到压力山大。有人说,大环境越来越不好了 ...
2025-03-03大数据分析师培训旨在培养学员掌握大数据分析的基础知识、技术及应用能力,以适应企业对数据分析人才的需求。根据不同的培训需求 ...
2025-03-03小伙伴们,最近被《哪吒2》刷屏了吧!这部电影不仅在国内掀起观影热潮,还在全球范围内引发了关注,成为中国电影崛起的又一里程 ...
2025-03-03以下的文章内容来源于张彦存老师的专栏,如果您想阅读专栏《Python 数据可视化 18 讲(PyEcharts、Matplotlib、Seaborn)》,点 ...
2025-02-28最近,国产AI模型DeepSeek爆火,其创始人梁文峰走进大众视野。《黑神话:悟空》制作人冯骥盛赞DeepSeek为“国运级别的科技成果” ...
2025-02-271.统计学简介 听说你已经被统计学劝退,被Python唬住……先别着急划走,看完这篇再说! 先说结论,大多数情况下的学不会都不是知 ...
2025-02-27“我们的利润率上升了,但销售额却没变,这是为什么?” “某个业务的市场份额在下滑,到底是什么原因?” “公司整体业绩稳定, ...
2025-02-26