C4.5算法
一、算法作用
概括的讲，C4.5算法是由Ross Quinlan开发的用于产生决策树的算法。决策树是一种类似流程图的树结构，其中每个内部节点（非树叶节点）表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点存放一个类标号。一旦建立好了决策树，对于一个未给定类标号的元组，跟踪一条有根节点到叶节点的路径，该叶节点就存放着该元组的预测。C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习：给定一个数据集，其中的每一个元组都能用一组属性值来描述，每一个元组属于一个互斥的类别中的某一类。
二、算法流程
决策树分类模型的建立通常分为两个步骤：决策树生成和决策树修剪。
决策树的生成：
第一步，对数据源进行数据预处理，将连续型的属性变量进行离散化处理形成决策树的训练集(如果没有连续取值的属性则忽略)。
第二步，计算每个属性的信息增益和信息增益率。
第三步，根节点属性每一个可能的取值对应一个子集，对样本子集递归地执行以上第二步过程，直到划分的每个子集中的观测数据在分类属性上取值都相同，生成决策树。
第四步，根据构造的决策树提取分类规则，对新的数据集进行分类
决策树的修剪：
剪枝过程实际上并不是一个剔除的过程，而是一个合并的过程
第一步，选择适当的叶子节点（一般选择深度较高，或不纯的叶子节点）
第二步，将同一级的叶子节点向上合并，属性则显示数量最多的一个
第三步，注意剪枝操作不能一直进行下去，否则会导致决策树过于简单，必须在误差拐点处停止。
三、算法优缺点：
优点：
1、通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥 有多个属性值的属性作为分裂属性的不足。
2、通过将连续型的属性进行离散化处理，克服ID3算法不能处理连续型数据缺陷，C4．5算法能够处理离散型和连续型的2种属性类型。
3、构造决策树之后进行剪枝（PEP）操作（ID3算法中没有），解决ID3算法中可能会出现的过拟合问题。
4、能够处理具有缺失属性值的训练数据。
5、产生的分类规则易于理解且准确率较高。
缺点：
1、在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法 的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内 存容纳时程序无法运行。针对含有连续属性值的训练样本时，算法计算效率较低
四、算法改进措施：
可以改进了 C4.5算法的分枝策略和属性选取的标准。把分类效果较差的分枝合并到分类效果较好的分枝中。引进一个平衡度系数,系数大小由决策者依靠先验知识或领域知识确定。
五、算法应用：
上面的训练集有4个属性，即属性集合A={OUTLOOK, TEMPERATURE, HUMIDITY, WINDY}；而类标签有2个，即类标签集合C={Yes, No}，分别表示适合户外运动和不适合户外运动，其实是一个二分类问题。
我们已经计算过信息增益，这里直接列出来，如下所示：
数据集D包含14个训练样本，其中属于类别“Yes”的有9个，属于类别“No”的有5个，则计算其信息熵
根据计算得到的信息增益率进行选择属性集中的属性作为决策树结点，对该结点进行分裂。
Q.E.D.
