C4.5决策树的生成.doc

CHANGSHA UNIVERSITY OF SCIENCE TECHNOLOGY 题目： C4.5决策树的生成 学生姓名： 曹水根 学 号： 14208050937 专 业： 软件工程 年 级： 2014级 指导老师： 李平 完成时间： 2015年7月10号 一、介绍 决策树（Decision tree），是以实例为基础的归纳学习算法。 它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，并根据不同的属性值从该结点向下分支，叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上，1993年Quinlan又提出了C4.5算法。 核心思想 采用从信息论知识中我们直到，期望信息越小，信息增益越大，从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。 设D为用类别对训练元组进行的划分，则D的熵（entropy）表示为： 其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。 现在我们假设将训练元组D按属性A进行划分，则A对D划分的期望信息为： 而信息增益即为两者的差值： C4.5算法首先定义了“分裂信息”，其定义可以表示成： 其中各符号意义与ID3算法相同，然后，增益率被定义为： 算法：： ID3算法和C4.5的比较 ????(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只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。 实例 C4.5数据集的一个示例如图4.1： 图4.1 C4.5算法数据集 (1)、根节点的计算 数据集信息的统计如表4.1： 属性 Outlook Temperature Humidity Windy 总记录数