《C45算法的源代码全解》由会员分享，可在线阅读，更多相关《C45算法的源代码全解（14页珍藏版）》请在金锄头文库上搜索。
1、)数据挖掘分类算法之决策树(zzDecisiontree决策树()以实例为基础的归纳学习算法。决策树是30student?creditiating?30Y0qE)exceDeiit它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采并根据不同的用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，该结点向下分支，叶结点是要学习划分的类。从根到叶结点的一条路属性值从径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。1986年又ID3算法的基础上，1993年QuinlanQuinlan提出了著名的ID3算法。在提出了若干改提出了C4.5算法。为了适应处理大规模数据集的
2、需要，后来又SPRINT(scalable进的算法，其中SLIQ(super-visedlearninginquest)和是比较有代表性的两个算法。parallelizableinductionofdecisiontrees)(1)ID3算法算法的核心是：在决策树各级结点上选择属性时，用信息增益ID3)作为属性的选择标准，以使得在每一个非叶结点进行测(informationgain检测所有的属性，其具体方法是：试时，能获得关于被测试记录最大的类别信息。再对由该属性的不同取值建立分支，选择信息增益最大的属性产生决策树结点，直到所有子集仅包含同一各分支的子集递归调用该方法建立决策树结点的分支，类别
3、的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。某属性的信息增益按下列方法计算。通过计算每个属性的信息增益，并比较它们的大小，就不难获得具有最大信息增益的属性。个m个不同值，定义mS设是s个数据样本的集合。假定类标号属性具有中的样本数。对一个给定的样本分类所需si是类Ci不同类Ci(i=1,m)。设的期望信息由下式给出：为底，其原2Ci其中pi=si/s的概率。注意，对数函数以是任意样本属于因是信息用二进制编码。个划分为v可以用属性A将Sv设属性A具有个不同值a1,a2,av。aj上具有相同的值A，其中Sj中的样本在属性子集S1,S2,Sv(j=1,2,v)。设sij是子集Sj中
4、类Ci的样本数。由A划分成子集的熵或信息期望由下式给出：熵值越小，子集划分的纯度越高。对于给定的子集Sj,其信息期望为其中pij=sij/sj是Sj中样本属于Ci的概率。在属性A上分枝将获得的信息增益是Gain(A)=I(s1,s2,sm)-E(A)ID3算法的优点是：算法的理论清晰，方法简单，学习能力较强。其缺点是：决策树可当训练数据集加大时，且对噪声比较敏感，只对比较小的数据集有效，能会随之改变。算法(2)C4.5ID3C4.5算法继承了算法的优点，并在以下几方面对ID3算法进行了改进：用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值1)多的属性的不足；在树构造过程中进行剪枝
5、；2)3)能够完成对连续属性的离散化处理；4)能够对不完整数据进行处理。算法与其它分类算法如统计方法、神经网络等比较起来有如下优点：C4.5产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对只适合因而导致算法的低效。数据集进行多次的顺序扫描和排序，此外，C4.5于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。(3)SLIQ算法在决策树的构造SLIQ算法对C4.5决策树分类算法的实现方法进行了改进，预排序”和“广度优先策略”两种技术。过程中采用了“预排序。对于连续属性在每个内部结点寻找其最优分裂标准时，都需要对1)S口Q训练集按照该属性的取值进行排序，而排
6、序是很浪费时间的操作。为此，采用了预排序技术。所谓预排序，就是针对每个属性的取值，把所有的记算法以消除在决策树的每个结点对数据集进行的排录按照从小到大的顺序进行排序，现时，需要为训练数据集的每个属性创建一个属性列表，为类别属序。具体实性创建一个类别列表。算法中，树的构造是按照深度优先策略完成的，C4.52)广度优先策略。在采需要对每个属性列表在每个结点处都进行一遍扫描，费时很多，为此，SLIQ广度优先策略构造决策树，即在决策树的每一层只需对每个属性列表扫描一用次，就可以为当前决策树中每个叶子结点找到最优分裂标准。大得多的使得该算法能够处理比C4.5SLIQ算法由于采用了上述两种技术，训练集，在
7、一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。然而它仍然存在如下缺点：而类别列表的元组数与训练集的元组数由于需要将类别列表存放于内存,1),这就一定程度上限制了可以处理的数据集的大小。是相同的由于采用了预排序技术，而排序算法的复杂度本身并不是与记录个数成线2)算法不可能达到随记录数目增长的线性可伸缩性。性关系，因此，使得SLIQ算法(4)SPRINT算法进一步改进了决策树算法的数SPRINT为了减少驻留于内存的数据量，SLIQ中需要驻留于内存的类别列表，将它的类别列合并到每去掉了在据结构，个属性列表中。这样，在遍历每个属性列表寻找当前结点的最优分裂标准时，不必参照其他信息，将对结点的
8、分裂表现在对属性列表的分裂，即将每个属性列表分成两个，分别存放属于各个结点的记录。SPRINT算法的优点是在寻找每个结点的最优分裂标准时变得更简单。其缺点是对非分裂属性的属性列表进行分裂变得很困难。解决的办法是对分裂属性进行分裂时用哈希表记录下每个记录属于哪个孩子结点，若内存能够容纳下整个哈希表，其他属性列表的分裂只需参照该哈希表即可。由于哈希表的大小与训练集的大小成正比，当训练集很大时，哈希表可能无法在内存容纳，此时分裂只算法的可伸缩性仍然不是很好。SPRINT能分批执行，这使得.算法C4.5一.背景。当前最有影响的决CLS1966年提出的最早的决策时算法是由Hunt等人于只。ID3于Qui
9、nlan1986年提出的ID3和1993年提出的C4.5策树算法是其目的是进能处理离散型描述属性，它选择信息增益最大的属性划分训练样本，算法的主要缺从而提高算法的运算速度和精确度。ID3行分枝时系统的熵最小，而在某偏向于取值较多的属性，陷是，用信息增益作为选择分枝属性的标准时，算法的改进ID3些情况下，这类属性可能不会提供太多有价值的信息。C4.5是采用了C4.5算法，不仅可以处理离散型描述属性，还能处理连续性描述属性。ID3信息增益比作为选择分枝属性的标准，弥补了算法的不足。)对噪声决策树算法的优点如下：(1)分类精度高；(2)成的模式简单；(3在数据挖数据有很好的健壮性。因而是目前应用最为
10、广泛的归纳推理算法之一，掘中受到研究者的广泛关注。二改进的具体方面C4.5算法存在的缺点1.ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作ID3(1)为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。ID3算法只能对描述属性为离散型属性的数据集构造决策树。)(2C4.5算法做出的改进2.(1) 用信息增益率来选择属性克服了用信息增益来选择属性时偏向选择值多的属性的不足。信息增益率定义为：代ID3算法中的信息增益相同，而分裂信息SplitInfo(S,A)其中Gain(S,A)与的广度和均匀性。分裂样本集S表了按照属性A个样
11、本子集。而形成的c分割是S其中，到Scc个不同值的属性AS30个用例)分成了10个用例和集(含把如按照属性AS20个用例两个集合SplitInfo(S,A)=-1/3*log(1/3)-2/3*log(2/3)则.(2) 可以处理连续数值型属性在选择某节点C4.5既可以处理离散型描述属性，也可以处理连续性描述属性。相同，按照的处理方法与ID3上的分枝属性时，对于离散型描述属性，C4.5，假设在某个结该属性本身的取值个数进行计算；对于某个连续性描述属性AcC4.5将作以下处理。点上的数据集的样本数量为total，将该结点上的所有数据样本按照连续型描述属性的具体数值，由小到大进行lAtotalc。
12、排序，得到属性值的取值序列Ale，A2c,)个分割点的取值(Ovivtotal个分割点。第l在取值序列中生成total-1i它可以将该节点上的数据集划分为两个子c)设置为Vi=(Aic+A/2,(i+1)集。个分割点中选择最佳分割点。对于每一个分割点划分数据集的方total-11从并且从中选择信息增益比最大的分割点来划分式，C4.5计算它的信息增益比，数据集。(3)采用了一种后剪枝方法避免树的高度无节制的增长，避免过度拟合数据，方从而决定是否真正剪枝。该方法使用训练样本集本身来估计剪枝前后的误差，法中使用的公式如下：个实例中分类错E为N(其中其中N是实例的数量，f=E/N为观察到的误差率算法的
13、一个输入参数，默c为置信度(C4.5误的个数)，q为真实的误差率，的设定值通过查cc的标准差，其值可根据认值为z0.25)，为对应于置信度的一个置信度上限，用q正态分布表得到。通过该公式即可计算出真实误差率做一个悲观的估计：此上限为该节点误差率e的大小，从而决定是否需要剪枝。通过判断剪枝前后e(4)对于缺失值的处理在某些情况下，可供使用的数据可能缺少某些属性的值。假如x,c(x)是样本集S中的一个训练实例，但是其属性A的值A(x)未知。处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值；另外一种更复杂的策略是为A的每个可能值赋予一个概率。例如，给定一个布尔属性A,如果结点
14、n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。这些片断样例(fractionalexamples)的目的是计算信息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的就是使用这种方法处理缺少的属性值。C4.5树分支中被进一步细分。.算法的优缺点3.C4.5优点：产生的分类规则易于理解，准确率较高。因而导致需要对数据集进行多次的顺序扫描和排序，缺点：在构造树的过程中，C4.5只适合于能够驻留于内存的数据集，当训练集大得无算法的低效。此外，法在内存容纳时程序无
15、法运行。三.C4.5算法源代码(C+)/C4.5_test.cpp:Definestheentrypointfortheconsoleapplication./椣据畲敤尠瑳慤硦栮#include#include椣据畲敤尠慭汬捯栮#includeconstintMAX=10;int*ilnput;inti=0;/列数intj=0;/行数voidbuild_tree(FILE*fp,int*iSamples,int*iAttribute,intilevel);/输出规则、intchoose_attribute(int*iSamples,int*iAttribute);/通过计算信息增益率选出tes
16、t_attributedoubleinfo(doubledTrue,doubledFalse);/计算期望信息doubleentropy(doubledTrue,doubledFalse,doubledAll);/求熵doublesplitinfo(int*list,doubledAll);intcheck_samples(int*iSamples);/检查samples是否都在同一个类里intcheck_ordinary(int*iSamples);/检查最普通的类intcheck_attribute_null(int*iAttribute);/检查attribute是否为空voidget_attributes(int*iSamples,int*iAttributeValue,intiAttribute);int_tmain(intargc,_TCHAR*ar
