决策树 -- C4.5算法

C4.5是另一个分类决策树算法,是基于ID3算法的改进,改进点如下:
1、分离信息
 决策树 -- C4.5算法
解释:数据集通过条件属性A的分离信息,其实和ID3中的熵;
 
2、信息增益率
 决策树 -- C4.5算法
解释:Gain(A)为获的A的信息增益,C4.5中选择具有最大增益率的属性作为分裂属性;
 
 
3、C4.5中所采用的悲观剪枝法
解释:数据的内容,还没有特别理解,之后补上。
 
 
相较ID3的改进:
1、用信息增益率来选择属性,克服了使用信息增益选择属性时偏向选择取值多的属性的不足;
2、在数构造过程中进行剪枝;
3、能够完成对连续属性的离散化处理;
4、能够对不完整数据进行处理;
 
优点:
产生的分类规则易于理解,准确率较高;
缺点:
在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5只适合于能够驻留于内存的数据集,当训练集大的无法在内存中容纳时程序无法运行;
 
 
相关内容:
决策树的过拟合问题:
      算法生成的决策树详细而庞大,很多错误数据数据也会被吸收和学习,成为决策树中的一部分,这些决策树的部分可能在训练数据中表现很好,但在以后的数据终究不会那么好,甚至错误率要高。
 
剪枝方法:先剪枝和后剪枝
      先剪枝方法中通过提前停止树的构造(比如决定在某个节点不在分裂或划分训练元组的子集)而对树剪枝。一旦停止,这个节点就变成输液,改树叶可能取它持有的子集最频繁的类作为自己的类。先剪枝有很多方法,比如:1、当决策树达到一定的高度就停止决策树的生长;2、到达此节点的实例具有相同的特征向量,而不必一定属于同一类,也可以停止生长;3、到达此节点的实例个数小于某个阈值的时候也可以厅直属的生长,不足之处是不能处理那些数据量比较小的特殊情况;4、计算每次扩展对系统性能的增益,如果小于某个阈值就可以让它停止生长。先剪枝有个缺点就是视野效果问题,也就是说在相同的标准下,也许当前扩展不能满足要求,但更进一步扩展又能满足要求。这样会过早停止决策树的生长。
     后剪枝方法由完全成长的树减去子树而形成。通过删除节点的分支并用树叶来替换它。树叶一般用子树中最频繁的类别来标记。剪枝过程是对拥有同样父节点的一组节点进行检查,判断如果将其合并,熵的增加量是否小于某一阈值。如果确实小,则合并为一个节点。
    后剪枝算法有很多种,Reduced-Error Pruning(REP,错误率降低剪枝)、Pessimistic Error Pruning(PEP,悲观剪枝);
上一篇:02-22 决策树C4.5算法


下一篇:3.决策树ID3算法原理