郑秀月

（福州黎明职业技术学院,福建 福州 350001）

1 C4.5算法介绍

C4.5算法是决策树技术中较为典型的、应用广泛的分类算法，是ID3算法的提出者J.R Quinlan根据ID3算法存在的一些问题提出的一种改进算法[1]。C4.5不仅具备ID3算法的所有优点，还可以处理离散类型、连续类型的属性；在生成决策树时，可以采用边构造树边剪枝或者完整的树生成之后再进行剪枝的策略，也可以采用不同的剪枝技术如删除子树或结点的方法来避免生成不平衡的树[2]。

2 C4.5算法的改进

2.1 C4.5算法的不足

C4.5算法中，在生成决策树的过程中需要花大量的时间进行信息增长率的运算，对决策树的生成效率产生了很大的影响。它与ID3算法一样仍然是基于“贪心”策略的搜索方式，通过找到每棵子树的最优解，然后构造出一棵完整的决策树，这样只能保证子树是最优的，最后生成的决策树未必能达到整体最优。

2.2 C4.5算法的改进

在C4.5算法中，计算分类及测试属性的信息量时，涉及了对数运算，在进行数据挖掘时要反复地调用对数库函数，造成计算复杂度大，时间成本高等问题。这里，针对信息量的计算方法提出了改进措施。

假设在样本数据中，类“YES”的有m个，类“NO”的有n个，则该样本分类属性的信息量计算方法如公式(1-1)所示。

以A为测试属性，假设A有p个不同的取值，则它的信息量计算方法如公式(1-2)所示。

根据高等数学中的泰勒公式、麦克劳林公式和等价无穷小的思想，可以知道当x很小时，ln(1+x)≈x，因此可以得出如下公式(1-3)和公式(1-4)所示。……