C4.5算法的源代码题稿.doc

数据挖掘分类算法之决策树（zz） 决策树（Decision tree） ???决策树是以实例为基础的归纳学习算法。 ??? 它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，并根据不同的属性值从 该结点向下分支，叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。1986年 Quinlan提出了著名的ID3算法。在ID3算法的基础上，1993年Quinlan又提出了C4.5算法。为了适应处理大规模数据集的需要，后来又 提出了若干改进的算法，其中SLIQ(super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)是比较有代表性的两个算法。????(1) ID3算法??? ID3算法的核心是：在决策树各级结点上选择属性时，用信息增益（information?gain）作为属性的选择标准，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。??? 某属性的信息增益按下列方法计算。通过计算每个属性的信息增益，并比较它们的大小，就不难获得具有最大信息增益的属性。??? 设S是s个数据样本的集合。假定类标号属性具有m个不同值，定义m个不同类Ci(i=1,…,m)。设si是类Ci中的样本数。对一个给定的样本分类所需的期望信息由下式给出：??? 其中pi=si/s是任意样本属于Ci的概率。注意，对数函数以2为底，其原因是信息用二进制编码。????设属性A具有v个不同值{a1,a2,……,av}。可以用属性A将S划分为v个子集{S1,S2,……,Sv}，其中Sj中的样本在属性A上具有相同的值aj（j=1,2,……,v）。设sij是子集Sj中类Ci的样本数。由A划分成子集的熵或信息期望由下式给出：????熵值越小，子集划分的纯度越高。对于给定的子集Sj，其信息期望为??? 其中pij=sij/sj 是Sj中样本属于Ci的概率。在属性A上分枝将获得的信息增益是??? Gain(A)= I(s1, s2, …,sm)-E(A)??? ID3算法的优点是：算法的理论清晰，方法简单，学习能力较强。其缺点是：只对比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变。????(2) C4.5算法??? C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：??? 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；??? 2) 在树构造过程中进行剪枝；??? 3) 能够完成对连续属性的离散化处理；??? 4) 能够对不完整数据进行处理。??? C4.5算法与其它分类算法如统计方法、神经网络等比较起来有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集 进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。????(3) SLIQ算法??? SLIQ算法对C4.5决策树分类算法的实现方法进行了改进，在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。??? 1)预排序。对于连续属性在每个内部结点寻找其最优分裂标准时，都需要对训练集按照该属性的取值进行排序，而排序是很浪费时间的操作。为此，SLIQ算法 采用了预排序技术。所谓预排序，就是针对每个属性的取值，把所有的记录按照从小到大的顺序进行排序，以消除在决策树的每个结点对数据集进行的排序。具体实 现时，需要为训练数据集的每个属性创建一个属性列表，为类别属性创建一个类别列表。??? 2)广度优先策略。在C4.5算法中，树的构造是按照深度优先策略完成的，需要对每个属性列表在每个结点处都进行一遍扫描，费时很多，为此，SLIQ采用 广度优先策略构造决策树，即在决策树的每一层只需对每个属性列表扫描一次，就可以为当前决策树中每个叶子结点找到最优分裂标准。??? SLIQ算法由于采用了上述两种技术，使得该算法能够处理比C4.5大得多的训练集，在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。??? 然而它仍然存在如下缺点：??? 1)由于需要将类别列表存放于内存,而类别列表