C4.5

C4.5算法介绍2014/11/10一、概述C4.5算法是在ID3算法的基础上进一步改进形成的，此算法用信息增益率来选择决策属性，继承了ID3算法的优点，并在一些方面进行了改进。二、C4.5优点（1）用信息增益率代替信息增益来选择属性：信息增益率定义为：,GainRatioSAGain为信息增益(S,A)H(S,A)GainH(S,A)为信息熵C4.5采用信息增益率作为对选择分枝属性的分枝准则，表示了由分枝产生的有用信息的比率，值越大，分枝包含有用信息越多。与ID3算法相比，ID3算法选择信息增益最大的属性进行分支，而C4.5算法选择信息增益率最大的属性进行分支，整体上看，分支更明确，获得有用信息更多。(2)能够完成对连续属性的离散化处理：C4.5将连续型属性的值分成不同的区间，具体步骤是：先寻找连续型属性的最小值，赋值给min，最大值赋值给max；然后设置区间[min，max]中的N个等分断点Ci；再计算将（min，Ci）和（Ci，max）作为区间值的信息增益率，并比较；最后选取信息增益率最大的C，作为断点，将属性值设置为[min,A]和[A,max]。离散化处理时，C4.5算法对节点上的每个属性都要计算信息增益率，从中选择出信息增益率最大的属性断点。（3）在决策树构造过程中或者构造完成之后进行剪枝：决策树的修剪的目的是抛弃一个或更多的子树，并用叶代替子树，是决策树简单化。修剪可以避免树的无节制增长，避免过度拟合数据，去掉对未知检验样本的分类精度无帮助的树。（4）能够对不完整的数据进行处理：在一些情况中，数据可能缺失某些属性的值，处理的一种方法是赋给该属性最常见的值，另一种是为其可能值赋予一个概率。（5）C4.5可以用决策树形式形成产生式规则，即if-then形式。C4.5缺点在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，导致算法的低效；C4.5只适合能够驻留在内存的数据集，当数据集大的无法在内存容纳时程序无法运行。C4.5算法如何计算信息增益并选择决策结点？下面以一个例子来说明。上面的训练集有4个属性，即属性集合A={OUTLOOK,TEMPERATURE,HUMIDITY,WINDY}；而类标签有2个，即类标签集合C={Yes,No}，分别表示适合户外运动和不适合户外运动数据集D包含14个训练样本，其中属于类别“Yes”的有9个，属于类别“No”的有5个，则计算其信息熵：Info(D)=-9/14*log2(9/14)-5/14*log2(5/14)=0.940下面对属性集中每个属性分别计算信息熵，如下所示：1.Info(OUTLOOK)=5/14*[-2/5*log2(2/5)–3/5*log2(3/5)]+4/14*[-4/4*log2(4/4)-0/4*log2(0/4)]+5/14*[-3/5*log2(3/5)–2/5*log2(2/5)]=0.6942.Info(TEMPERATURE)=4/14*[-2/4*log2(2/4)–2/4*log2(2/4)]+6/14*[-4/6*log2(4/6)–2/6*log2(2/6)]+4/14*[-3/4*log2(3/4)–1/4*log2(1/4)]=0.9113.Info(HUMIDITY)=7/14*[-3/7*log2(3/7)–4/7*log2(4/7)]+7/14*[-6/7*log2(6/7)-1/7*log2(1/7)]=0.7894.Info(WINDY)=6/14*[-3/6*log2(3/6)–3/6*log2(3/6)]+8/14*[-6/8*log2(6/8)-2/8*log2(2/8)]=0.892根据上面的数据，我们可以计算选择第一个根结点所依赖的信息增益值，计算如下所示：1Gain(OUTLOOK)=Info(D)-Info(OUTLOOK)=0.940-0.694=0.2462Gain(TEMPERATURE)=Info(D)-Info(TEMPERATURE)=0.940-0.911=0.0293Gain(HUMIDITY)=Info(D)-Info(HUMIDITY)=0.940-0.789=0.1514Gain(WINDY)=Info(D)-Info(WINDY)=0.940-0.892=0.048接下来，我们计算分裂信息度量H(V)：OUTLOOK属性属性OUTLOOK有3个取值，其中Sunny有5个样本、Rainy有5个样本、Overcast有4个样本，则H(OUTLOOK)=-5/14*log2(5/14)-5/14*log2(5/14)-4/14*log2(4/14)=1.577406282852345TEMPERATURE属性属性TEMPERATURE有3个取值，其中Hot有4个样本、Mild有6个样本、Cool有4个样本，则H(TEMPERATURE)=-4/14*log2(4/14)-6/14*log2(6/14)-4/14*log2(4/14)=1.5566567074628228HUMIDITY属性属性HUMIDITY有2个取值，其中Normal有7个样本、High有7个样本则H(HUMIDITY)=-7/14*log2(7/14)-7/14*log2(7/14)=1.0WINDY属性属性WINDY有2个取值，其中True有6个样本、False有8个样本，则H(WINDY)=-6/14*log2(6/14)-8/14*log2(8/14)=0.9852281360342516根据上面计算结果，我们可以计算信息增益率，如下所示：1IGR(OUTLOOK)=Info(OUTLOOK)/H(OUTLOOK)=0.246/1.577406282852345=0.155952212612701452IGR(TEMPERATURE)=Info(TEMPERATURE)/H(TEMPERATURE)=0.029/1.5566567074628228=0.0186296695096420943IGR(HUMIDITY)=Info(HUMIDITY)/H(HUMIDITY)=0.151/1.0=0.1514IGR(WINDY)=Info(WINDY)/H(WINDY)=0.048/0.9852281360342516=0.048719680492692784根据计算得到的信息增益率进行选择属性集中的属性作为决策树结点，对该结点进行分裂。