资源描述:
《决策树算法在实际中的应用》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、决策树算法在实际中的应用吴逍刘启兵汪飞上海海事大学物流工程学院摘要:通过实例详细地说明了数据挖掘中关于决策树算法在实际中的应用,并将ID.3和C4.5两个算法进行比较,表明各个算法的优势。关键词:数据挖掘;决策树;ID3算法;C4.5算法;收稿日期:2017-8-7ApplicationofDecisionTreeAlgorithminPracticeAbstract:Thispaperillustratestheapplicationofdecisiontreealgorithmindataminingthroughanexample,andcomparesthetwoalgorith
2、msofTD.3andC4.5,andshowstheadvantagesofeachalgorithm.Keyword:datamining;decisiontree;ID3algorithm;C4;5algorithm;Received:2017-8-7本文将选取数据挖掘中的基于决策树的分类,体现这一科学在日常生活中的应用,并选取决策树的ID3与C4.5算法完成实例,作比较,分析C4.5相对于ID3的优势。1决策树决策树方法在分类、预测、规则提取等领域有着广泛的应用。20世纪70年代后期和80年代初期,机器学习研究者JROSSQuinlan提出了ID3算法以后,决策树在机器学习、数据
3、挖掘领域得到极大发展。Quinlan后来乂提出了C4.5,成为新的监督学习算法。2ID.3算法ID.3算法是基于信息爛来选择最佳测试属性,选择具有最大信息增益值的属性作为测试展性;样本集的划分则依据测试屈性的取值进行,测试屈性有多少不同取值就将样本划分为多少子样本集,同时决策树上相应于该样本集的节点长岀新的叶子节点。ID.3算法在每个非叶节点选择信息增益最大的属性作为测试属性,这样可以得到当前情况下的最纯拆分,这是因为信息增益值越大,不确定越小,从而得到较小的决策树。对某一数据集D,有d个样本,假定类别属性有n个不同的值:G(1=1,2,3,…n)。设di为G的样木数,对于数据集D,总的
4、信息爛为:对某一属性A而言,有k个不同的值{兀a2,•:aj,对应的最终结果有不同的值,{dbd2,…,djo设此是子集Dj中类别为G的样本数,则关于属性A的信息嫡值为:最后,求属性A的信息增益:依次求出各个属性的信息增益,将所求得的具有最大信息增益的属性作为根节点,以该属性的n个不同值作为分支,下一个非叶节点采取以上的方法继续求解信息增益,以具有最大增益值的属性作为此非叶节点的划分属性,以此循环,直到求出最纯的叶节点,即完成了1D3算法的整个过程,对数据进行了分类。2.1用于实例木文将ID.3算法用于分类一些环境因素对于人们是否进行活动的影响,并且能够以此判断岀哪一因素对于是否进行活动
5、的影响最大。表1显示的是环境因素对于是否进行活动的影响,并给出了结果。本文的思路是用1D.3算法完成一个决策树,对表中的因素对活动的影响进行分类,用前面10组数据进行决策树的构造,并以后4组的数据进行预测,判断TD.3算法构造的决策树是否具有预测功能。2.2ID.3实现将表1中的前10个数据作为训练集,后4个作为预测集。1)根据公式(1),计算总的信息爛。其中总的数据样本为10个,“进行”活动的数据有6个,“取消”活动的有4个。那么:2)根据公式(1)和(2),计算每个属性的信息爛。对于天气属性,有“晴”、“雨”和“阴”3种,它们的数据分别为4、4、2O其中,天气为“晴”时,活动“进行”
6、的数据有1个,活动“取消”的数据有3个;天气为“雨”时,活动“进行”的数据有3个,活动“取消”的数据有1个;天气为“阴”时,活动“进行”的数据有2个,活动“取消”的数据有0个。则:同理,可以计算岀:E(温度)=0.875489E(湿度)二0.846439E(风速)=0.8796733)根据公式(3),计算天气、温度、湿度和风速属性的信息增益值。Gain(天气)=T(6,4)E(天气)=0.321928Gain(温度)=1(6,4)E(温度)=0.095461Gain(湿度)=1(6,4)E(湿度)=0.124511Gain(风速)=1(6,4)E(风速)=0.0912774)由步骤3)的
7、计算结果可知,天气属性的信息增益值最大,所以将天气属性作为第一个分裂属性,向下划分,所以第一次划分的决策树如图1所示。从图1可以得知,当天气“阴”吋的子节点是纯的,而其他两个子节点都不是纯的。然后接下來的划分,应该按照第1)步到第3)的步骤继续对“晴”和“雨”的分支进行划分,针对每一个分支节点继续进行信息增益值的计算,如此循环反复,直到没有新的节点分支,最终构成一棵决策树,如图2所示。图2ID3生成的决策树模型下载原图由1D3算法生