ID3算法_C4.5算法的例子

ID3算法假设有一个信息系统19，关于的是几种天气的不同变化对是否进行比赛的影响根据这些信息，给定一个决策表如下：表 2-1 决策表NO.OutlookTemperatureWindyHumidityPlay?1sunnyhotfalsehighNo2sunnyhottruehighNo3overcasthotfalsehighYes4rainmildfalsehighYes5raincoolfalsenormalYes6raincooltruenormalNo7overcastcooltruenormalYes8sunnymildfalsehighNo9sunnycoolfalsenormalYes10rainmildfalsenormalYes11sunnymildtruenormalYes12overcastmildtruehighYes13overcasthotfalsenormalYes14rainmildtruehighNo以下将通过上述表详细介绍ID3和C4.5两种算法2.2.1 ID3算法下面将介绍如何计算属性的信息增益首先给出信息熵的定义：例：（1）计算属性“Outlook”的信息熵 注：本来没有意义，但在这里我们令的值为0属性的预期信息为：（2）计算属性“Outlook”的信息增益信息增益=分裂前的信息分裂后的信息表2-1中其它属性的信息增益类似可以计算出来，如下：“Outlook”的信息增益最大，可知应该选择“Outlook”作为分裂点接下来，继续上述过程比如选择“Outlook=sunny”这个分支现在要考虑计算剩下的三个属性对应的信息增益如图2-1所示outlookoutlookoutlooktemperaturehumiditywindyyesnoyesyesnonoyesnonononoyesyessunnysunnyhotmildcoolfalsetruehighnormalnono图 2-1 剩下的三个属性对应的信息增益NO.TemperatureWindyHumidityPlay?1hotfalsehighNo2hottruehighNo8mildfalsehighNo9coolfalsenormalYes11mildtruenormalYes由于，所以，属性“Humidity”的信息增益最大在“Outlook=sunny”这个分支下应该选择属性“Humidity”作为分裂点类似进行下去，最终的决策树如下：outlookyeshumiditywindynoyesyesnosunnyovercastrainyhighnormalfalsetrue图 2-2 最终的决策树NO.TemperatureWindyHumidityPlay?4mildfalsehighYes5coolfalsenormalYes6cooltruenormalNo10mildfalsenormalYes14mildtruehighNo注意：某些情况下，相同的实例（即那些对象具有相同的属性值）可能被划分成不同的类里当数据不能被分裂为止，分裂过程就停止2.2.2 C4.5算法C4.5算法是利用信息增益率函数来作为分类标准，其定义如下：其中，其中 ，以表2-1中“Outlook”为例其他的三个属性可以类似地得出它们的信息增益率，如下表所示：表 2-2 各属性相应的信息值OutlookTemperatureInfo:0.693Info:0.911Gain: 0.940-0.6930.247Gain: 0.940-0.9110.029Spilt info: info(5,4,5)1.577Spilt info: info(4,6,4)1.362Gain ratio: 0.247/1.5770.156Gain ratio: 0.029/1.3620.021HumidityWindyInfo:0.788Info:0.892Gain: 0.940-0.7880.152Gain: 0.940-0.8920.048Spilt info: info(7,7)1.000Spilt info: info(8,6)0.985Gain ratio: 0.152/10.152Gain ratio: 0.048/0.9850.049选取各属性中信息增益率最大的属性作为分裂点，以后的做法与ID3的相同，唯一的不同之处是判断标准由信息增益变成了信息增益率表 2-3是ID3和C4.5算法的简单比较表 2-3 ID3和C4.5算法的简单比较特点算法决策树的结构测试属性技术连续属性处理是否需独立测试样本集可伸缩性可并行性ID3算法多叉树信息增益离散化是差差C4.5算法多叉树信息增益率预排序否差差信息增益函数对于那些可能产生多分支输出的测试倾向于产生大的函数值，但是输出分支多并不表示该测试对未知的对象具有更好的预测效果信息增益率函数可以弥补这个缺陷然而，信息增益率函数也有它的缺陷如果划分的信息熵值非常小，信息增益率将会不稳定因此，C4.5系统中引入一个限制来解决这个问题：待选测试的信息增益值不能小于所有的检测过的测试的平均信息增益值然而这个限制有其负面的影响如果属性集中存在无关属性，即便该属性没有被选为测试属性，都将影响信息增益率的效果因为引进的无关属性会降低测试的信息