C45算法生成决策树的研究

1/6C4.5算法生成决策树1、基础知识当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以称之为“大熵法”最大熵法在数学形式上很漂亮，但是实现起来比较复杂，但把它运用于金融领域的诱惑也比较大，比如说决定股票涨落的因素可能有几十甚至上百种，而最大熵方法恰恰能找到一个同时满足成千上万种不同条件的模型。目前，针对分类问题已有了若干不同领域方法的算法，例如统计学、机器学习、神经网络和粗糙集理论等。其中从机器学习中引出的决策树方法是一种较为通用并被深入研究的分类方法，由于决策树分类算法是一种直观快速的分类方法，它的分类过程不需要背景知识、并且清晰、易于理解，因此有很大的实用价值。目前已经形成了多种决策树算法。如CLS、ID3、CHAID、CART、FACT、C4.5、Gini、SEE5、SLIQ、SPRINT等。在决策树分类算法中，最常用的、最经典的是C4.5算法，它继承了ID3算法的优点并对ID3算法进行了改进和补充。C4.5算法采用信息增益率作为选择分支属性的标准，克服了ID3算法中信息增益选择属性时偏向选择取值多的属性的不足，并能够完成对连续属性离散化的处理，还能够对不完整数据进行处理。根据分割方法的不同，目前决策的算法可以分为两类：基于信息论（InformationTheory）的方法和最小GINI指标（LowestGINIindex）方法。对应前者的算法有ID3、C4.5，后者的有CART、SLIQ和SPRINT。C4.5算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。2/62、算法以下图数据为例，介绍用C4.5建立决策树的算法。表1ID3算法最初假定属性都是离散值，但在实际应用中，很多属性值都是连续的。C4.5对ID3不能处理连续型属性的缺点进行了改进。如果存在连续型的描述性属性，首先将连续型属性的值分成不同的区间，即“离散化”。对上表中将实际耗电量分为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：阳）机房开启设备总额定功率（千瓦）2317654105002417622214502718603-103002419583203002518522114502618505-115003019452214502818433104502718483-10500291840410500室外温度室内温度室外湿度风力大小机房楼层机房朝向（0：阴，1：阳）机房开启设备总额定功率（千瓦）实际耗电量（区间）231765410500524176222145072718603-103000241958320300025185221145052618505-1150043/6通过表2知，实际耗电量区间的个数为：表3序号区间值个数102241353461572691总计10定义1：若存在n个相同概率的消息(Massage)，则每个消息的概率p是1/n，一个消息传递的信息量为22log()log()pn。若有16个事件，则2log(16)4，则需4个比特来代表一个消息。例如：表3中，区间为0的信息量为：22log2/10log10=3.322定义2：若给定的概率分布12,,npppp，则由该分布传递的信息量称为P的熵。即1212222log()log()log()nnIPpppppp注意：概率分布越均匀，其信息量越大）。定义3：若一个记录的集合T根据类别属性的值被分成互相独立的类12,,,kCCC则识别T的一个元素所属哪个类所需要的信息量是infoTIP，其中P是12,,kCCC的概率分布，即12||/||,||/||,||/||,KPCTCTCT例如：表3中，得到实际耗电量区间的信息量为（以下单位为比特，下同）：2222222/10log(2/10)1/10log(1/10)3/10log(3/10)()1/10log(1/10)2/10log(2/10)1/10log(1/10)InfoTIP=2.446301945221450928184331045062718483-1050052918404105007非类别属性类别属性4/6定义4：若我们先根据非类别属性X的值将T分成集合12,,nTTT，则确定T中一个元素类的信息量可通过确定iT的加权平均值来得到，即Info(iT)的加权平均值为：1,||/||niiiInfoXTTTINFOT例如：属性“室内温度”的值有“17、18、19”，分类见下表：表4序号室内温度个数所属的区间（个数11725(1)7(1)21860(1)4(1)5(2)6(1)7(1)31920(1)9(1)总计10P（17）=（1/2，1/2）P（18）=（1/6，1/6，2/6，1/6，1/6）P（19）=（1/2，1/2）则每个温度的信息量为：22(17)171/2*log(1/2)1/2*log(1/2)InfoIP=1.000222221/6*log(1/6)1/6*log(1/6)2/6*log(2/6)(18)181/6*log(1/6)1/6*log(1/6)InfoIP=2.25222(19)191/2*log(1/2)1/2*log(1/2)InfoIP=1.0002/10(17)6/10(18)2/10(19)(,)InfoInfoInInffooT室内温度=1.751定义5：将增益Gain（X，T）定义为：。所谓增益，就是指在应用了某一测试之后，其对应的可能性丰富程度下降，不确定性减小，这个减小的幅度就是增益，其实质上对应着分类带来的好处）。上式的增益值为：,,GainXTInfoTInfoT室内温度=2.446-1.751=0.6955/6以上是ID3计算信息增益的方法，C4.5算法对此进行了改进。C4.5算法采用信息增益率作为选择分支属性的标准，克服了ID3算法中信息增益选择属性时偏向选择取值多的属性的不足。若我们一个属性D，据其取值将T分成集合T1、T2……Tn，当每一个集合中所有记录得出的结果相同，即同时取值为“是”或“否”时，Info(D，T)为0，此时增益Gain（D,T）取最大值。因此用增益比值来代替，即：(,)(,)(,)GainDTGainRatioDTSplitInfoDT由于T是以类型属性D的值为基准进行的分割，故SplitInfo（D，T）是信息量。举例：根据表4，得到：222,2/10*log(2/10)6/10*log(6/10)2/10*log(2/10)SplitInfoT室内温度=1.371，则(,)GainRatioDT0.695/1.371=0.507可利用函数Gain的定义将属性进行排列，并可构造一棵决策树，其中每一个节点都是属性中具有最大增益的属性，从而不必考虑来自于根的路径。3、选择连续变量的阈值（测试条件）到连续数据的分支的阈值点如何确定呢？很简单，把需要处理的样本（对应根节点）或样本子集（对应子树）按照连续变量的大小从小到大进行排序，假设该属性对应的不同的属性值一共有N个，那么总共有N-1个可能的候选分割阈值点，每个候选的分割阈值点的值为上述排序后的属性值链表中两两前后连续元素的中点，那么我们的任务就是从这个N-1个候选分割阈值点中选出一个，使得前面提到的信息论标准最大。在EXCEL中，对室外温度（第二步）详细介绍了如何分割阈值点并进行计算。4、树的终止树的建立实际上是一个递归过程，那么这个递归什么时候到达终止条件退出递归呢？有两种方式，第一种方式是如果某一节点的分支所覆盖的样本都属于同一类的时候，那么递归6/6就可以终止，该分支就会产生一个叶子节点。还有一种方式就是，如果某一分支覆盖的样本的个数如果小于一个阈值，那么也可产生叶子节点，从而终止建立树。我们只考虑二叉分割的情况，因为这样生成的树的准确度更高。5、树的修剪树一旦生成后，便进入第二阶段——修剪阶段。决策树为什么要剪枝？原因就是避免决策树“过拟合”样本。前面的算法生成的决策树非常的详细而庞大，每个属性都被详细地加以考虑，决策树的树叶节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进行分类的话，你会发现对于训练样本而言，这个树表现堪称完美，它可以100%完美正确得对训练样本集中的样本进行分类（因为决策树本身就是100%完美拟合训练样本的产物）。但是，这会带来一个问题，如果训练样本中包含了一些错误，按照前面的算法，这些错误也会100%一点不留得被决策树学习了，这就是“过拟合”。C4.5的缔造者昆兰教授很早就发现了这个问题，他做过一个试验，在某一个数据集中，过拟合的决策树的错误率比一个经过简化了的决策树的错误率要高。目前决策树的修剪的策略有三种：基于代价复杂度的修剪（Cost-ComplexityPruning）、悲观修剪（PessimisticPruning）和MDL（MinimumDescriptionLength）修剪。基于代价复杂度的修剪使用了独立的样本集用于修剪，即与用于树的构建过程中使用的样本集不同，称为修剪样本。在很多情况下，特别是当训练集很小时，更期望将所有的样本既用于树的构建也用于树的修剪。悲观修剪是Quinlan在1987年提出的，将所有的训练样本都用于树的构建与修剪，经验表明，该方法产生的树太大并且有时精确度不高。在实际使用中用的较多并且效果较好的是MDL修剪。对于树的修剪，相对树的生成要简单一些，后续再做讨论。