资源描述：
《C45算法生成决策树的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、C4.5算法生成决策树1、基础知识当我们需要对一个随机事件的概率分布逬行预测时我们的预测应当满足全部已知的条件，而对未知的情况不要做但可主观假设。在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息嬌最大，所以称之为〃大嬌法”最大爛法在数学形式上很漂亮,但是实现起来比较复杂，但把它运用于金融领域的诱惑也比较大，比如说决定股票涨落的因素可能有几十甚至上百种,而最大嬌方法涪恰能找到一个同时满足成千上万种不同条件的模型。目前，针对分类问题已有了若干不同领域方法的算法，例如统计学、机器学习、神经
2、网络和粗糙集理论等。其中从机器学习中引岀的决策树方法是一种较为通用并被深入硏究的分类方法，由于决策树分类算法是一种直观快速的分类方法，它的分类过程不需要背景知识、并且清晰、易于理解，因此有很大的实用价值。目前已经形成了多种决策树算法。如CLS、ID3、CHAID、CART、FACT、C4.5、Gini、SEES.SLIQ、SPRINT等。在决策树分类算法中，最常用的、最经典的是C4.5算法,它继承了ID3算法的优点并对ID3算法进行了改进和补充。C4.5算法采用信息增益率作为选择分支属性的标准，克服了I
3、D3算法中信息增益选择属性时偏向选择取值多的属性的不足，并能够完成对连续属性离散化的处理,还能够对不完整数据进行处理。根据分割方法的不同，目前决策的算法可以分为两类：基于信息论(InformationTheory)的方法和最小GINI指标(LowestGINIindex)方法。对应前者的算法有ID3、C4.5,后者的有CART、SLIQ和SPRINT。C4.5算法是以信息论为基础，以信息爛和信息增益度为衡量标准,从而实现对数据的归纳分类。2、算法以下图数据为例，介绍用C4.5建立决策树的算法。表1室外温
4、度室内温度室外湿度风力大小机房楼层机房朝向（0：阴，1：阳）机房开启设备总额定功率（千瓦）2317654105002417622214502718603-103002419583203002518522114502618505-115003019452214502818433104502718483-10500291840410500ID3算法最初假定属性都是离散值，但在实际应用中，很多属性值都是连续的。C4.5对ID3不能处理连续型属性的缺点进行了改进。如果存在连续型的描述性属性，首先将连续型属性的值
5、分成不同的区间，即"离散化〃。对上表中将实际耗电量分为10个区间（0—9）（300-320,320-340,340-360,360-380,380-400,400~420,420~440,440~460,460~480,480~500）因为最终是要得到实际的耗电量区间，因此"实际耗电量〃属于"类别属性"。“室外温度"、〃室内温度"、”室外湿度"、〃风力大小"、“机房楼层"、“机房朝向"、〃机房开启设备总额定功率"属于〃非类别属性"。表2室外温度室内温度室外湿度风力大小机房楼层机房朝向（0：阴，1：阳）机
6、房开启设备总额定功率（千瓦）实际耗电量（区间）231765410500524176222145072718603-103000241958320300025185221145052618505-115004301945221450928184331045062718483-1050052918404105007非类别属性类别属性通过表2知，实际耗电量区间的个数为：表3序号区间值个数102241353461572691总计10定义若存在n个相同概率的消息(Massage),则每个消息的概率p是1/n,—个
7、消息传递的信息量为-log2(p)=log2(«)o若有16个事件，则-log2(16)=4,则需4个比特来代表一个消息。例如：表3中，区间为0的信息量为：—Iog2(2/10)=log2(10)=3.322定义2：若给定的概率分布—(]“,•••□)，则由该分布传递的信息量称为P的爛。即^(^)=-(Pixlog2(Pj)+p2xlog2(p2)+...+pnxlog2(pn))注意：概率分布越均匀，其信息量越人)。定义3：若f记录的集合1■根据类别属性的值被分成互相独立的类G，C2，・..q,则识别
8、T的一个元素所属哪个类所需要的信息量是info(T)=I(P)f其中卩是(C19C2,...CA)的概率分布，即P=(ICiI/ITI,IC2I/ITI,...ICJ/ITI,)例如：表3中，得到实际耗电量区间的信息量为(以下单位为比特，下同)：Info(T)=I(P)=-<2/10xlog2(2/10)+l/10xlog2(l/10)+3/10xlog2(3/10)+^J/10xlog2(l/10)+2/10xlog2(2/10)+l/1
