- C4.5 算法是 Ross 对 ID3 算法的改进。
用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，而C4.5用的是信息增益率。
在决策树构造过程中进行剪枝。
对非离散数据也能处理。
能够对不完整数据进行处理。
过拟合的原因：
为了尽可能正确分类训练样本，节点的划分过程会不断重复直到不能再分，这样就可能对训练样本学习的“太好”了，把训练样本的一些特点当做所有数据都具有的一般性质，从而导致过拟合。
剪枝的基本策略有“预剪枝”（prepruning）和“后剪枝”（post-pruning）通过剪枝处理去掉一些分支来降低过拟合的风险。
预剪枝（prepruning）
预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。
-
剪枝策略
在节点划分前来确定是否继续增长，及早停止增长
主要方法有：
• 节点内数据样本低于某一阈值；
• 所有节点特征都已分裂；
• 节点划分前准确率比划分后准确率高。
后剪枝
在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情况下，后剪枝的欠拟合风险更小，泛化性能往往优于预剪枝决策树
-
剪枝方法
在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。
C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。
后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。
- 缺点
• 剪枝策略可以再优化；
• C4.5 用的是多叉树，用二叉树效率更高；
• C4.5 只能用于分类；
• C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
• C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。