决策树算法.docVIP

《数据仓库与数据挖掘》 决策树算法C4.5 本组成员：维光 郑辰倩 琛 一．背景 最早的决策时算法是由Hunt等人于1966年提出的CLS。当前最有影响的决策树算法是Quinlan于1986年提出的ID3和1993年提出的C4.5。ID3只能处理离散型描述属性，它选择信息增益最大的属性划分训练样本，其目的是进行分枝时系统的熵最小，从而提高算法的运算速度和精确度。ID3算法的主要缺陷是，用信息增益作为选择分枝属性的标准时，偏向于取值较多的属性，而在某些情况下，这类属性可能不会提供太多有价值的信息。C4.5是ID3算法的改进算法，不仅可以处理离散型描述属性，还能处理连续性描述属性。C4.5采用了信息增益比作为选择分枝属性的标准，弥补了ID3算法的不足。 决策树算法的优点如下：（1）分类精度高；（2）成的模式简单；（3）对噪声数据有很好的健壮性。因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。用信息增益率来选择属性克服了用信息增益来选择属性时偏向选择值多的属性的不足。信息增益率定义为： 其中Gain(S,A)与ID3算法中的信息增益相同，而分裂信息SplitInfo(S,A)代表了按照属性A分裂样本集S的广度和均匀性。 其中，S1到Sc是c个不同值的属性A分割S而形成的c个样本子集。 如按照属性A把S集（含30个用例）分成了10个用例和20个用例两个集合 则SplitInfo(S,A)=-1/3*log(1/3)-2/3*log(2/3) 可以处理连续数值型属性 ……Atotalc}。 在取值序列中生成total-1个分割点。第i（0itotal）个分割点的取值设置为Vi=（Aic+A（i+1）c）/2,它可以将该节点上的数据集划分为两个子集。 从total-1个分割点中选择最佳分割点。对于每一个分割点划分数据集的方式，C4.5计算它的信息增益比，并且从中选择信息增益比最大的分割点来划分数据集。 (3)采用了一种后剪枝方法避免树的高度无节制的增长，避免过度拟合数据， 该方法使用训练样本集本身来估计剪枝前后的误差，从而决定是否真正剪枝。方法中使用的公式如下： 其中N是实例的数量，f=E/N为观察到的误差率（其中E为N个实例中分类错误的个数），q为真实的误差率，c为置信度（C4.5算法的一个输入参数，默认值为0.25），z为对应于置信度c的标准差，其值可根据c的设定值通过查正态分布表得到。通过该公式即可计算出真实误差率q的一个置信度上限，用此上限为该节点误差率e做一个悲观的估计： 通过判断剪枝前后e的大小，从而决定是否需要剪枝。 对于缺失值的处理 在某些情况下，可供使用的数据可能缺少某些属性的值。假如〈x，c(x)〉是样本集S中的一个训练实例，但是其属性A的值A(x)未知。处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值；另外一种更复杂的策略是为A的每个可能值赋予一个概率。例如，给定一个布尔属性A，如果结点n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。这些片断样例（fractional examples）的目的是计算信息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。C4.5就是使用这种方法处理缺少的属性值。 　C4.5算法优点产生的分类规则易于理解，准确率较高。缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。/ C4.5_test.cpp : Defines the entry point for the console application.// #include stdafx.h#include stdio.h#include math.h#include malloc.h#include stdlib.h const int MAX = 10; int** iInput;int i = 0;//列数int j = 0;//行数 void build_tree(FILE *fp, int* iSamples, int* iAttribute,int ilevel);//输出规则int choose_attribute(int* iSamples, int* iAttribute);//通过计算信息增益率选出test_attributedouble info(double dTrue,do