欢迎来到天天文库
浏览记录
ID:39548372
大小:728.50 KB
页数:18页
时间:2019-07-06
《C4.5决策树的生成》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、CHANGSHAUNIVERSITYOFSCIENCE&TECHNOLOGY题目:C4.5决策树的生成学生姓名:曹水根学号:14208050937专业:软件工程年级:2014级指导老师:李平完成时间:2015年7月10号一、介绍决策树(Decisiontree),是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较,并根据不同的属性值从该结点向下分支,叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条
2、合取规则,整个决策树就对应着一组析取表达式规则。1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上,1993年Quinlan又提出了C4.5算法。二、核心思想采用从信息论知识中我们直到,期望信息越小,信息增益越大,从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择,选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。设D为用类别对训练元组进行的划分,则D的熵(entropy)表示为:其中pi表示第i个类别在整个训练元组中出现的概率,可以用属于此类别元素的数量除以
3、训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。现在我们假设将训练元组D按属性A进行划分,则A对D划分的期望信息为:而信息增益即为两者的差值:C4.5算法首先定义了“分裂信息”,其定义可以表示成:其中各符号意义与ID3算法相同,然后,增益率被定义为:算法::二、ID3算法和C4.5的比较 (1)ID3算法ID3算法的核心是:在决策树各级结点上选择属性时,用信息增益(information gain)作为属性的选择标准,以使得在每一个非叶结点进行测试时,能获得关于被测试
4、记录最大的类别信息。其具体方法是:检测所有的属性,选择信息增益最大的属性产生决策树结点,由该属性的不同取值建立分支,再对各分支的子集递归调用该方法建立决策树结点的分支,直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树,它可以用来对新的样本进行分类。 某属性的信息增益按下列方法计算。通过计算每个属性的信息增益,并比较它们的大小,就不难获得具有最大信息增益的属性。 设S是s个数据样本的集合。假定类标号属性具有m个不同值,定义m个不同类Ci(i=1,…,m)。设si是类Ci中的样本数。对一个给定的样本
5、分类所需的期望信息由下式给出: 其中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的概率。在属性
6、A上分枝将获得的信息增益是 Gain(A)=I(s1,s2,…,sm)-E(A) ID3算法的优点是:算法的理论清晰,方法简单,学习能力较强。其缺点是:只对比较小的数据集有效,且对噪声比较敏感,当训练数据集加大时,决策树可能会随之改变。(2)C4.5算法 C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进: 1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足; 2)在树构造过程中进行剪枝; 3)能够完成对连续属性的离散化处理
7、; 4)能够对不完整数据进行处理。 C4.5算法与其它分类算法如统计方法、神经网络等比较起来有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。二、实例C4.5数据集的一个示例如图4.1:图4.1C4.5算法数据集(1)、根节点的计算数据集信息的统计如表4.1:属性OutlookTemperatureHumidityWindy总
8、记录数记录情况属性值得个数3322149个Yes,5个No。表4.1数据集信息数据集详细统计信息如表4.2:属性属性值记录数记录的情况OutlookSunny52个Yes,3个No;Overcast44个Yes;Rain53个Yes,2个No;TemperatureHot42个Yes,2个No;Mild64个Yes,2个No;Cool44个Yes,1个No;HumidityHigh73个Yes,4个No;Norm
此文档下载收益归作者所有