决策树相关算法研究（精选8篇）
决策树相关算法研究 篇1
在遥感技术的研究中, 通过遥感图像判读识别各种目标是遥感技术发展的一个重要环节, 无论是专业信息获取、动态变化预测, 还是专题地图制作和遥感数据库的建立都离不开分类。目前, 遥感图像自动分类主要利用统计模式方法, 可分为非监督和监督两类。由于遥感图像往往存在异物同谱和同物异谱的现象, 用传统的统计模式方法分类的效果不甚理想, 因而人们不断研究新的分类方法。例如模拟人脑思维方式提出的人工神经网络分类;针对地物特征和模糊性提出的模糊聚类分类;模式识别与人工智能技术相结合的专家系统分类;计算混合像元内各典型地物所占面积比例的混合像元分解法;按照一定的知识规则, 采用分层思想的树分类等技术。
一、决策树算法的图像分类研究
1. 常用的决策树算法简介
决策树是一个类似流程图的树型结构, 其中树的每个内部节点代表对一个属性的测试, 其分支代表测试的每个结果, 而树的每个叶子节点代表一个类别, 树的最高层节点就是根节点, 是整个决策树的开始。这类算法无须相关领域知识, 且相对于基于模糊理论的分类方法, 具有更高的分类准确率和更快的处理速度。在很多领域特别是数据挖掘中, 决策树是一种经常要用到的技术, 它可以用于分析数据, 也可以用来作预测, 常用的算法有ID3, CART, C4.5等。
(1) ID3算法是最有影响和最早的决策树算法之一, 其建立在推理系统和概念学习系统的基础上, 但它是非递增学习算法。每当一个或数个新例子进来, 就必须重新执行一次该算法, 把新来的例子和以前旧的全部例子集合变成决策树, 因此效率非常低。而且它是基于单变量的, 难以表达复杂概念, 抗噪性差。
(2) C4.5是ID3的改进版本。它主要在以下几个方面对ID3作了改进:缺省值的预测属性仍可用, 提出了修剪思想, 可以进行规则推导。
(3) CART (ClassificationandRegressio nTree, 分类回归树) 是一种数据勘测和预测算法。它用一种非常简单的方法来选择问题, 即将每个问题均试一次, 然后挑出最好的一个, 用它把数据分成更有序的两个分割, 再对新的分割分别提出所有可能的问题。因此该算法得到的决策树每个节点有两个分支, 即二叉树。
2. 改进决策树生成算法
为了更好地将决策树算法应用于遥感图像分类中, 本文在CART算法的基础上作了以下改进。
(1) 常用的决策树算法均由用户提供训练样本集, 计算机执行算法生成决策树, 整个过程由计算机自动完成, 不需要任何人工干预。由于遥感图像训练集的属性取值太多, 而有些取值是用不到的, 需要把这些用不到的取值过滤掉, 否则会影响整颗树的质量。因此本文在决策树的生成过程中引入人机交互技术, 将用户的先验知识用于决策树的生成过程中, 使得生成的决策树更加合理可信。基于人机交互的决策树方法由用户与计算机相互交互, 共同完成, 故要求计算机提供可视化环境和工具, 友好的界面方便用户输入先验知识。
(2) 建立一棵树首先需要选择一个属性作为根节点, 然后将该属性的每一个可能值作为一个分支;再在每个分支所剩余的属性中找出一个属性作为该分支的下一个节点, 如此循环到所有属性均被选用为止。常用的决策树算法均采用信息熵作为选择标准。由于遥感图像中的噪音比较多, 而基于信息熵属性选择标准往往抗干扰能力不强且以对数计算为累加计算的计算量较大, 故本文采用了一种新型的属性选择标准:属性重要性来提高属性选择的效率。该方法是用训练值的变化而引起输出变化的累加值作为衡量属性重要性的标准, 即对于某个属性, 如果训练值的变化而引起的输出变化越大, 说明该属性就越重要。可用式 (1) 表示为C (K) =∑x (i, k) -x (j, k) ×signy (i) -y (j) (i≠j) (1) 式中:C (K) 表示第k个属性的输入/输出关联值;x (i, k) , x (j, k) 表示第i, j个样本的第k个条件属性值;y (i) , y (j) 表示第i, j个样本的决策属性值;sign (x) 表示符号函数。
3. 一种自定义的数据结构
数据结构的设计在程序设计中很关键, 一个好的数据结构可以让算法更加精练, 大大提高开发效率。本文采用的算法是在CART算法的基础上改进过来的, 因此生成的也是一棵二叉树。但由于在生成算法中要频繁地查找和调整决策树 (添加或者删除子树) , 传统的二叉树结构在速度上不能满足算法的需求, 故笔者在设计系统时创新了一种类二叉树的结构。在树的每一层都设置了一个头节点, 且树的每个节点只有指向父节点和左右兄弟节点的指针。
4. 系统实现
图3为系统架构图。其中D是训练集合, A为分类属性集合。另有测试数据集合T用来评估生成决策树的误差ε。整个过程分为两个部分进行: (1) 决策树构造, 也称学习过程, 主要工作是输入训练集, 采用改进的决策树生成算法生成决策树, 并作好分类前的预备工作, 即提取分类规则; (2) 决策树预测, 也称分类过程, 主要工作是应用分类规则进行分类, 并根据测试集, 计算出分类误差, 误差较大的对决策树作裁剪算法。误差较小的就输出其分类结果, 分类结果有两种: (1) 将分类结果写入新的遥感图像文件 (如MIG文件) 中; (2) 可视化的树结构, 在树的叶子节点保存着每一类的属性。
二、结语
通过本文研究发现:决策树算法对于输入数据的空间特征和分类标志具有更好的弹性和坚韧性, 它用于遥感数据分类的优势主要在于对数字图像数据特征空间的分割上, 其分类结构简单明了, 尤其是二叉树结构的单一决策树结构十分容易解释。因此, 当遥感图像数据特征的空间分布很复杂, 或者源数据各维具有不同的统计分布和尺度时, 基于决策树算法的分类方法能够获得较为理想的分类结果。
参考文献
[1]李宁, 等.决策树算法及其常见问题的解决[J].计算机与数字工程, 2010, 3 (33) :60264.
[2]孙雪莲.数据挖掘中分类算法研究[D].吉林大学硕士学位论文, 2010.
决策树相关算法研究 篇2
数据挖掘就是从大量的不完全的有噪声的模糊的随机的实际应用数据中，抽取隐含在其中的、事先并不知道的、但又是潜在有用的信息和知识的过程。
决策树算法作为常用的数据挖掘技术之一，其基本思想是将实例库中记录的大量有限的具体事实数据进行归纳和分类并建立树型结构，以发现并形成隐含在大量实例中的若干形式化的分类判别规则，典型的决策树算法方法有ID3方法和IBLE（Information—based Learning from Example）方法。
利用决策树评估教材质量的基本思想
笔者以高校教学质量建设中的重头戏——教材建设为例来阐释决策树算法在教育统计中的应用。
从教材的教学水平，科学水平等两大要素来对教材的质量进行合理分类，探索出科学合理的决策树的模型，使之成为学校教材建设管理的理论方法，并在今后的教材管理中起着一定的指导作用。
教学水平：教材符合人才培养目标及本课程教学的要求：取材合适、深度适宜、份量恰当；符合认知规律；富有启发性；便于学习。
科学水平：能反映本学科国内外科学研究和教学研究的先进成果；能完整地表达本课程应包含的知识；反映其相互联系及发展规律；结构严谨。
构建决策树模型
即利用训练集（教材建设数据库）建立并精化一棵决策树。该过程可分为建树和剪枝两阶段。其中，建树是用每一个属性将训练集划分成一个或多个子集，递归地调用该过程，直到每个子集中的记录都属于同一类，最终得到决策树。剪枝是为提高树的精度及分类效率，而去掉因训练数据中的噪声和孤立点等引起的不可靠或可能是噪声的一些枝条。
利用决策树研究影响教材质量的因素
首先，将学生问卷调查数据库和教学管理部门所掌握的资料结合起来，分类整理，同时进行规范化的数据清洗，得到创建决策树模型的训练集，如表1所示。
根据评估预期的要求，将所有教材的评估结果分为两类：
Class p：综合评价=“优秀”
Class n：综合评价=“一般”
从上表显示的数据可知，综合评价为“一般”的教材有9种， 综合评价为“优秀”的教材有6种，从而可以计算出样本分类的期望信息：
—∑Pi log2（pi）=
I（p，n）=I（9，6）= —[（9/15）×log2（9/15）+6/15×log2=（6/15）]
=—（—0.444—0.53）=0.974
下面以综合评价是否为“优秀”作为衡量标准分别计算由各个属性划分子集的信息熵，以及各自的信息增益度。
计算“教学水平”的信息增加益度
从而算出信息熵E（教学水平）=
I（3，1）+I（3，2）+I（0，3）+I（0，3）=0.43
再计算出其信息增益度
GainI（p，n）—E（教学水平）=0.974—0.507=0.467
计算“科学水平”的信息增益度
计算信息熵E（科学水平）=I（2，1）+I（3，2）+I（1，6）+I（0，0）—0.783再计算出其信息增益度GainI（科学水平）=I（p，n）—E（科学水平）=0.974—0.783=0.191
计算“教材编者职称”的信息增益度
从而算出信息熵E（教材编者职称）=I（4，1）+I（2，1）+I（0，4）+I（0，3）=0.424再计算出其信息增益度GainI（教材编者职称）—I（p，n）—E（教材编者职称）=0.974—0.424=0.55
计算“教材编者学历”的信息增益度
计算信息熵E（教材编者学历）=I（3，1）+I（3，3）+I（0，5）=0.667再计算出其信息增益度GainI（教材编者学历）=（p，n）—（教材编者学历）=0.974—0.667=0.307
由此可以得知“教材编者职称”的信息增益度最大，它是最能区别训练集实例中教材质量的属性，应作为决策树的根节点。根据各个属性的信息增益度的大小，可以构建该训练集实例的决策树如下图1所示：
由该决策树可以得出诸如以下结论：
教材编者职称的高低程度（也可以说是教学经验的丰富程度）很大程度上影响着教材的质量，教材的教学水平的优劣程度对教材质量的影响程度次之，教材编者的学历和教材的科学水平也在相当程度上影响教材的质量。
一种改进的决策树算法研究 篇3
决策树分类算法中的ID3算法是Quilan在1986年提出来的,也是决策树构造中的经典算法[1]。ID3算法是以信息论为基础,它使用信息熵和信息增益两个指标为衡量标准,选择信息增益最大的属性划分训练样本,从而生成决策树。
定义1、按类标签对训练集D的属m性集A进行划分,信息熵为:
Pi为训练集D中属于第i类的概率。
定义2、按属性集A中每个属性进行划分,得到一组信息熵:
Dj为属性集中每个属性的出现的次数,D为所有属性的总次数。
定义3、信息增益为:
ID3算法对每个节点中选择Gain(A)中最大的属性A作为选择分支的属性。这种算法的缺点是:倾向于选择取值较多的属性[2],在有些情况下这类属性可能不会提供什么有意义的信息,ID3学习简单逻辑表达式的能力差[3]。此外,ID3将注意力集中在属性的选择方面,而属性的选择对决策树的影响如何, 仍无定论[4]。
2 改进的ID3算法
1)调整信息增益
针对ID3算法偏向于选择取值较多但实际中并不总是最优的属性作为测试属性的缺点,调整信息增益。Gain’(A)=Gain(A) /X,其中X的取值大于等于1,主要由属性A的取值个数和使用者根据经验及领域知识来确定,一般取值个数越多则X越大。改进的ID3算法通过调整每个属性的信息增益,使生成决策树时数量少但又很重要的属性不会被淹没,最终使决策树克服了对取值多的属性的偏爱,因为属性取值越多,调整后的信息增益就越小,这个属性当然就很难被选中为判断属性了。
2)剪枝
剪枝方法主要是考虑在决策树的哪个位置产生叶子合适 [5]。剪枝算法分前剪枝和后剪枝。前剪枝是在决策树构造过程中选取某个预定义的阀值,使得某些节点不再继续分裂,限制树的生长。后剪枝是将已生成的决策树做去分支处理[6]。前剪枝由于很难选取一个合适的阀值,应用困难。后剪枝的时间复杂度高,但生成的决策树准确度高,但主要应用的几种后剪枝算法都存在过剪枝或欠剪枝现象。由于各种剪枝算法都有缺点,所以本文提出采用灵活的剪枝方法进行剪枝。
剪枝方法为:首先,根据具体需要设定生成决策树的高度、精确度等信息,设定主要依据经验和领域知识来确定。然后, 针对决策树节点a来说,对a进行剪枝,则产生的错误分配样本数为:
未剪枝的子树错误分配样本数为:
未剪枝的子树误差为:
其中,e(a)为a节点的错误分配样本数,Ti(i=1,2,…,n)是Ta节点的子节点,Ca是Ta节点的子节点数。如果叶子节点的成立,那么Ta可以剪枝。
3实验测试结果
实验所用数据为UCI数据库中的Iris数据集(样本数209个,属性7个)、Breast数据集(样本数817个,属性11个)和Seg-mentation数据集(样本数2932个,属性26个)。对这三个数据集所有连续值的属性使用DBChi2算法对数据进行离散,随机抽取每个数据集中的2/3用于训练样本集,其余的1/3用作测试样本集,然后分别用传统的ID3算法和改进的ID3算法构建决策树,最后通过测试样本集测试准确度。上述构造决策树的方法反复进行十次,得出的结果如表1。
从表1中能明显的得出,改进的ID3算法平均的分类准确度更高,生成决策树的平均叶子数也高过传统的ID3算法,具有更低的复杂性。从实验还得出改进的ID3算法通过不断的学习调整信息增益,从而克服了传统ID3算法倾向于选择取值较多的属性的缺点,但是改进的ID3算法通过实验得出在时间复杂度上和传统ID3几乎一致。
4 结束语
改进的ID3算法调整了传统的ID3算法的信息增益计算方法,又加入了灵活的剪枝策略。它可以依靠经验或领域知识人工增强重要属性在分类决策中调整信息增益,从而减少非重要属性的信息量,特别是它可以减少ID3算法对取值较多的属性的依赖性,从而改善分类规则和结果。
摘要：决策树算法是数据挖掘中的一个常用算法,它通过构造决策树来发现数据中蕴含的分类规则,如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树算法中常用的一种是ID3算法,该文针对传统ID3算法的缺点,提出一种改进的ID3算法,通过实验证实,改进的ID3算法在生成的决策树的规模和精度方面都比传统的ID3算法好,使用这种改进的ID3算法可以提高性能。
一种基于粗糙集的决策树算法研究 篇4
粗糙集理论Rough Sets[3]是由波兰学者Z.Pawlak教授提出的,它从新的角度认识知识,把知识和分类[4]紧密联系起来,为处理不精确、不完全数据的分类问题提供了一种更符合人类认知的数学工具。Pawlak粗糙集模型的一个局限性就是它所处理的分类必须是完全正确的或肯定的,因为它是严格按照等价类来分“包含”或者“属于”。Pawlak粗糙集模型的另一个局限性是它所处理的对象是已知的且从模型中得到的所有结论仅仅适用于这些对象集。但在实际应用中,往往需要将一些小规模的对象集中得到的结论应用到大规模的对象集中去。变精度粗糙集模型是Ziarko W[5]提出的一种对粗糙集模型的扩充,在基本粗糙集模型的基础上引入错误分类率β(0≤β<0.5),允许一定程度上的错误分类存在,主要解决实际应用中属性间无函数或不确定关系的数据分类问题。文献[6]和[7]分别提出用变精度明确区域和变精度近似分类质量作为属性选择标准构造决策树,有效地减小了树的规模,提高了树的泛化能力。以变精度粗糙集模型为基础,对近似分类精度[8]属性选择方法加以改进,提出了以变精度加权平均粗糙度及其后继节点变精度加权平均粗糙度和值作为属性选择标准,对后继节点变精度加权平均粗糙度和值小的作为确定划分属性来构造决策树[9]。
1 相关概念
定义1:信息系统S=(U,A,V,F)。其中U={X1,X2,…Xn}是论域,A是属性集合,V是属性值集合,F是U×A→V的映射。若A=C∪D,C∩D=Φ,其中C是条件属性,D是决策属性,则该信息系统也称为决策表。IND(C)的等价类称为条件类,IND(D)的等价类称为决策类[10]。
定义2:多数包含关系[11](0≤β<0.5)
定义5:变精度加权平均粗糙度[13]
其中μβRi(Xj)=|RiβXj|/|RiβXj|,ω=|Xj|/|U|,Ri表示第i个条件属性,j表示决策属性的第j个等价类,m是决策树属性等价类的个数;Xj表示决策属性的第j个等价类集合,U表示非空有限集合(论域)。γβRi的取值范围是[0,1],γβRi越小则反映第i个属性包含的近似确定性越大。
2 改进的决策树构造算法
输入决策表和精度β,即可输出一棵决策树。
算法步骤如下:
步骤1:计算决策表中每一个条件属性的变精度加权平均粗糙度;
步骤2:计算分别以某一条件属性r作为决策划分属性时,其后继节点的变精度加权平均粗糙度之和,选择后继节点的变精度加权平均粗糙度的和值最小的属性r作为划分属性;
步骤3:用选择的属性r去划分训练集,相应于该属性的每一个取值产生一个分支(子表);
步骤4:若子表中属于某一类别实例个数占表中总实例个数大于等于(1-β)或表中没有可选的属性,则以该子表中占多数的实例类别标识该节点,并作为叶子结点;否则,将子表中的条件属性去掉已选划分属性r,重复上述过程;
步骤5:返回。
本算法与基于近似分类精度构造决策树方法的区别在于选择属性的标准不同,下面通过实例对两个算法进行比较。
3 实例分析
以表1为例构造决策树,比较用近似分类精度构造决策树和提出的改进算法生成的决策树。其中条件属性为:A、B、C、D,决策属性为E。
根据各条件属性及决策属性可以得到如下等价类:
在本例中设定β=0.29,计算各条件属性的变精度加权平均粗糙度,结果为:γAβ=0.9652,γBβ=0.7569,γβC=0.6597,γβD=0.6597。计算分别以属性A、B、C、D为根结点时其后继节点的变精度加权平均粗糙度的和值,属性C的和值最小,所以最终确定选择属性C作为根节点,并由它产生两个分支。每个分支对应着决策表中的一个子表,在每个子集上重复以上操作,直到分支子表某一类的数据个数占子表总数据个数比例不小于71%或表中没有可选的属性,以该类别名标识此节点作为叶子节点。图1就是本文提出的方法构造的决策树,图2是以近似精度为标准构造的决策树。
比较图1和图2,可以看出用改进算法构造的决策树可以使树的复杂度大大降低。本算法同时也允许叶子节点中有小于29%的误分数据,能够避免了分类过于细化,造成对训练集过度拟合,泛化能力不强等问题,更符合实际应用中经常存在噪声数据的情形。
结束语:提出以后继节点变精度加权平均粗糙度和值最小作为构造决策树的属性选择标准,通过一个具体的实例,可以看出用本文提出的改进方法构造决策树,可以有效弱化少数噪声数据对决策树造成的不良影响,虽然有时决策中可能存在一些误差,但决策树总体效果是比较好的,最终生成的决策树也比较简洁,并且大大提高了决策树的泛化能力。
摘要：决策树是一种有效的数据分类方法。粗糙集理论把知识和分类紧密联系起来,为处理不精确、不完全数据的分类问题提供了一种更符合人类认知的数学工具。提出了把后继节点的变精度加权平均粗糙度和值作为属性选择标准构造决策树的改进新算法。新算法用变精度代替近似精度,能有效地克服噪声数据在构造决策树过程中对刻画精度的影响,使生成的决策树复杂性降低,泛化能力更强。
决策树相关算法研究 篇5
简单地说, 决策树算法就是通过将大量数据有目的地分类, 从中找到一些潜在的、对决策有价值的信息[2]。它包括两个步骤:第一步是利用训练样本集来建立并精化出一棵决策树, 建立决策树模型。这个过程实际上是一个从数据中获取知识, 进行机器学习的过程。第二步是利用建好的决策树对新的数据进行分类。
2 几种常用的决策树算法
2.1 CLS算法
CLS (Concept Learning System) 学习算法是Hunt.E.B等人在1966年提出的。它第一次提出用决策树进行概念学习, 后来的许多决策树学习算法都可以看作是CLS算法的改进与更新。CLS的主要思想是从一个空的决策树出发, 通过添加新的判定结点来改善原来的决策树, 直到该决策树能够正确地将训练实例分类为止。它对决策树的构造过程也就是假设特化的过程, 所以CLS可以看作是只带一个操作符的学习算法, 此操作符可以表示为:通过添加一个新的判定条件 (新的判定结点) 特化当前假设。CLS算法递归调用这个操作符作用在每个叶结点来构造决策树。
2.2 CART算法
CART (Classification And Regression Trees) 分类算法是由Breiman.L、Friedman.J.H和Olshen.R.A等人在1984年提出的。这种算法选择具有最小基尼指数值的属性作为测试属性, 并采用一种二分递归分割的技术, 将当前样本集分为两个子样本集, 使得生成的决策树的每一个非叶节点都有两个分枝, 最后生成的决策树是结构简洁的二叉树。CART算法使用后剪枝法。剪枝算法使用独立于训练样本集的测试样本集对子树的分类错误进行计算, 找出分类错误最小的子树作为最终的分类模型。有些样本集, 由于样本数太少而不能分出独立的测试样本集, CART算法采用一种称为交叉确定 (cross validation) 的剪枝方法。该方法解决了在小样本集上挖掘决策树由于没有独立测试样本集而造成的过度拟合问题。
2.3 ID3算法
相比于前两种算法, ID3算法在国际上更具影响力[3]。
ID3 (Iterative Dichotomizer 3) 算法是Quinlan在1986年提出的。它是在CLS的基础上发展而来的。Quinlan的首创性工作主要是在决策树的学习算法中第一次引入了信息论中的互信息 (称之为信息增益) , 以之作为属性选择的标准, 并且将建树的方法嵌入在其中。ID3是一个典型的决策树学习系统, 其核心是在决策树的各级节点上选择属性, 用信息增益作为属性选择标准, 使得在每个非叶节点上进行测试时, 能获得关于被测试例子最大的类别信息。使用该属性将实例集分成子集后, 系统的嫡值最小, 期望该非叶节点到达各后代叶节点的平均路径最短, 使生成的决策树平均深度较小, 提高分类速度和准确率。ID3算法的基本算法是贪婪算法, 采用自顶向下的递归方式构造决策树。其原理是对大量的数据进行归纳、概括、提炼出带有普遍性、概括性的描述 (即事物的属性规律) , 并将这些规律以决策树的方式表示出来, 以下举例说明。
设训练实例集X, 学习目的是将训练实例分为n类, 记为C={X1, X2...Xn}, 设第i类的训练实例个数是|Xi|=Ci, X中总的训练实例个数为|X|。记一个实例属于第i类概率为P (Xi) , 则有 此时决策树划分C的不确定程度为H (X, C) , 简记为H (X) :
决策树学习过程就是使得决策树对划分的不确定程度逐渐减小的过程。选择测试属性A进行测试, 设属性A具有性质ai, a2, a3...at, 在A=aj情况下属于第i类的实例个数为 即P (Xi/A=aj) 为测试属性A的取值为aj时, 它属于第i类的概率。记Yi为A=aj时的实例集, 此时决策树对分类的不确定程度就是训练实例集对属性A的条件嫡:
当选择测试属性A后伸出的每个A=aj叶结点Xj对于分类信息的信息嫡为:
属性A对分类提供的信息量, 即属性A的信息增益 (Information Gain) 为I (X/A) =H (X) -H (X/A) , 显然H (X/A) 越小, I (X/A) 的值越大, 说明选择测试属性A对于分类提供的信息越大, 选择A之后对分类的不确定程度越小, ID3算法即采用I (X/A) 作为测试属性的选择标准分割训练实例集最终生成决策树。
给定一个测试属性Cl, C2...Cn。的集合、类别属性C及记录的训练集T之后, 构造决策树的ID3算法如图1所示。
ID3通过不断的循环处理, 逐步求精决策树, 直至找到一个完全正确的决策树, 并从顶向下归纳形成了一组类似IF-THEN的规则。其区分的类别只有两种:T (正例) 或F (反例) , 其属性值也是一些离散有限的值, 而今ID3算法已发展到允许多于两个类别, 而其属性值可以是整数或实数。
ID3算法有许多优点:首先搜索空间是完全的假设空间, 目标函数必在搜索空间中, 不存在无解的危险;其次全部使用训练数据, 而不是像候选剪除算法一个一个地考虑训练例, 这样做可以利用全部训练例的统计性质进行决策, 从而抵抗噪音。当然ID3算法也有很多缺点:这种基于互信息的计算方法偏向于属性取值数目较多的特征, 而属性值较多的属性并不总是最优的属性。
总的来说, ID3算法由于其理论清晰、方法简单、学习能力较强, 适于处理大规模的学习问题, 是数据挖掘和机器学习领域中的一个极好范例, 也不失为一种知识获取的有用工具。
3 几种算法比较
决策树的优点在于它的直观和易理解性。以上介绍的几种算法的特点比较如表1所示[5]:
参考文献
[1]Jiawei Han Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社, 2001.
[2]迟庆云.决策树分类算法及其应用[J].枣庄学院学报, 2005 (9) .
[3]乔向杰, 陈功平.数据挖掘中分类算法的可扩展性研究[J].信阳师范学院学报, 2006 (8) .
[4]何箭.决策树优化算法研究[D].合肥工业大学硕士学位论文, 2004.
决策树相关算法研究 篇6
分类是数据挖掘和机器学习中的一个重要研究课题。它的目标是构造一个分类器, 对由属性集描述的实例指定适合的类标签。许多分类方法和技术用于构造分类模型, 例如决策树、贝叶斯方法以及支持向量机等。而决策树首先选择最大信息量的属性, 建立决策树的根结点, 然后再根据该属性的不同取值建立树的分枝结点。国际上最有影响和最早的决策树方法是ID3, 在此方法的基础上, 后人又发展了现在非常流行的C4.5、CART算法等, 本文将从一个新的思路对基于最小Gini指标的决策树分类算法进行进行设计与研究。
1 CART算法设计
CART是Classification and Regression Trees的简称。CART模型最早由Breiman等人提出并已在统计学领域普遍应用。它选择具有最小Gini系数值的属性作为测试属性, 当Gini值越小, 样本的纯净度越高, 划分效果也就越好。
假设S是用来划分的样本集合, 选择的划分方法必须使S的子集比它本身更“纯”, 可以用一个不纯函数x来评估各种划分方法的好坏。
如果用x (t) 表示任意叶节点t的不纯度, 那么x (t) 可以表示为:
其中, p (cit) 表示类ci在数据集t中的概率。
根据这个定义, 分支方案s的好坏度可以用不纯度的减小量△xs (t) 来定义。如果测试s将样本集合t分为n个子集t1, t2, …, tn, 那么分支好坏度可以定义为:
如果用Gini指标, 那么函数的定义为:
这时, 在测试s下Gini (s) 可以用不纯度的减小量△xs (t) 表示为:
如果某个测试s使Gini (s) 最大, 那么表示在s测试下不纯度的减小量最大, 则s就是最优的分支方案。
2 SLIQ和SPRINT算法设计
SLIQ分类器是一个基于决策树分类器算法的分类器, 它能够处理数值属性和分类属性, 同普通的决策树分类器不同的是, SLIQ不仅能对内存数据进行分类, 还能够将驻留在磁盘上的数据集分类, 也就是说它是可扩展的。同时, SLIQ还通过采用一定的算法, 改进决策树生成速度, 并且产生结构紧凑而精确的决策树。
在SLIQ算法中, 在树的构建阶段之前还有一个预处理阶段, 通过预处理, 对数值属性进行排序, 这样可以减少根据数值属性计算分支方案时的代价。这种预排序同构建阶段的宽度优先增长策略结合起来, 使SLIQ分类器能够分类驻留在磁盘上的数据集。在根据分类属性计算分支选择的时候, SLIQ使用了一种快速分割子集算法以确定分类属性的分支。在树的修剪阶段, SLIQ采用基于最小描述长度原理的修剪算法。这些技术的组合使得SLIQ能够扩展到大数据集上, 对有很多类、属性和样本的数据集, 具有很强的分类能力。
SLIQ算法不要求所有的训练数据都驻留在内存, 这对因为属性数目非常多而不能常驻内存的训练集非常有效。但是, SLIQ算法在运行过程中要频繁地访问和更新类表, 为了提高效率, 必须使类表驻留在内存中。类表的规模随着训练样本的个数的增加而线性增长, 这就限制了SLIQ的扩展能力:当没有足够的内存保存类表时, SLIQ就失效了。
而SPRINT算法是对SLIQ算法的改进, 它与SLIQ有很多相同的地方, 比如对数值属性的预排序, 选用gini指标作分支指标, 采用基于MDL原理的修剪算法等。但SPRINT消除了所有的内存限制, 即理论上它可以处理任何规模的训练数据集, 并且易于并行化, 即允许多处理器并行工作, 构造同一个模型。为了达到这个目的, SPRINT采用了与SLIQ不同的数据结构, 相应地, 在根据分支方案划分属性表的时候也使用了不同于SLIQ的策略。
3 SLIQ算法时间复杂性分析
SLIQ算法使用的改善程序运行效率策略, 主要有树的宽度优先增长策略和与之结合的数值属性的预排序技术, 以及使用贪心法计算分类属性的最优分割集。决策树算法的时间复杂性主要体现在树的构建阶段。不需要对数值属性进行重排序, 这是因为SLIQ采用的特殊的数据结构使得预排序成为可能, 而不需要在每个叶节点处对样本进行重排序。另外SLIQ并不考察分类属性的全部取值构成的集合S的所有子集, 而是采用一种贪心算法来计算分割子集S`, 贪心算法并不保证最终得到的子集是最优的, 但是经验证明它所得到的结果往往与最优结果相差无几。
将数据分解为属性表和类表、并对数值属性表进行排序的时间复杂性为O (nlogn) , 初始化根节点时的时间复杂性为O (1) 。
根据贪心算法, 可以得出计算最优分支方案时的时间复杂性Te (n) 在O (n) 。
构建SLIQ的决策树算法的时间复杂性T (n) 为:
4 SLIQ和SPRINT内存管理分析与性能比较
SLIQ分类器所采用的技术解决了对磁盘驻留大数据集的分类, 它可以使用其它的决策树分类算法来处理训练数据, 而精确度与所使用的算法相同, 但执行速度更快而且生成的树也更小。另外, SLIQ也不限制训练数据的数量及属性的数量。因此, 通过对其他分类方法处理不了的大数据集的分类, SLIQ实际上提高了分类精度。
SLIQ分类算法对建立一个快速的可扩展分类其存在的问题作了有益的探讨, 很好地解决了磁盘驻留数据太大以至于无法被内存容纳带来的问题。它没有采纳利用抽样或划分来获得可容纳与内存的小数据的处理方法, 而是直接在整个数据集上建立一棵决策树。然而, SLIQ仍要求每条记录的某些子段必须长期驻留于内存中。由于内存驻留数据的大小会随着输入记录数线形正比增大, 这显然限制了SLIQ分类训练的数据量。
而SPRINT作为一种可扩展的、可并行的归纳决策树, 它完全不受内存的限制, 而且处理速度很快, 且可扩展。该算法在设计中兼顾了并行处理, 允许多个处理器相互合作生成一致的模型。所给出的并行算法同样显示了极好的可扩展性。所有这些优点都使得该算法成为数据挖掘处理的理想工具。
我们以列表的方式简单地分析两种非常相似的决策树分类算法SPRINT与SLIQ的异同。
因为SLIQ和SPRINT的分支方案计算策略以及修剪算法完全相同, 所以二者的分类精度是完全一样的。实验表明, 在串行情况下, SLIQ算法的时间性能略优于SPRINT, 因为SLIQ不需要为新的属性表创建文件, 也不需要生成rid的散列表;在并行情况下, SPRINT算法要明显优于SLIQ的两种并行算法。
摘要：从一个新的思路对基于最小Gini指标的决策树分类算法进行了讨论。简单介绍了CART算法和Gini指标的定义, 并且对SLIQ和SPRINT决策树分类技术进行深入的分析。同时对SLIQ算法的时间复杂性和这两种算法的内存管理和性能方面进行了比较和分析。
关键词：分类,决策树,GINI指标
参考文献
[1]TOM M, MITCHELL.机器学习[M].北京:机械工业出版社, 2003.
[2]IAN H.WITTEN, EIBE FRANK.数据挖掘实用机器学习技术[M].北京:机械工业出版社, 2005.
[3]田盛丰, 黄厚宽.人工智能与知识工程[M].北京:中国铁道出版社, 1999.
[4]梁循.数据挖掘算法与应用[M].北京:北京大学出版社, 2006.
[5]MARY CAMPIONE et al.Java语言导学[M].北京:机械工业出版社, 2003.
[6]HAN J, KAMBER M.Data mining concepts and techniques[M].San Francisco:Morgan Kaufmann Publishers, 2001:185-219.
[7]USAMA M FAYYAD, GREGORY PIATETSDY-SHAPIRO et al.Advances in knowledge discovery and data mining[J].California:AAAI/MIT Press, 1996.
[8]FRIDMAN N, GEIGER D, GOLDSZMIDT M.Bayesian network classifiers[J].Machine Learning, 1997, 29 (2) :131-163.
[9]QUINLAN JR.Induction of decision trees.Machine Learning, 1986 (1) :81-106.
决策树相关算法研究 篇7
税收是国家财政收入的主要来源,也是国家调节经济发展的重要手段。税收信用是社会信用体系的重要组成部分,诚信纳税在一定程度上反映了社会信用状况。税务机关通过对纳税人依法纳税情况的评估,评定纳税人的纳税信用等级(A、B、C三类,D类一般不评),实现纳税信用等级管理,有助于加强税收监控,提供税收风险预警能力,促进纳税人依法诚信纳税,提高纳税遵从度。目前,我国的税收信用体系的建设还处于创立阶段,纳税信用等级评定还处在手工或计算机模拟手工评定阶段。随着税收信用体系的逐步建立和运行,对纳税人纳税信用等级评定方法在不断完善和创新,本文就是在采集纳税人大量税收信息基础上应用C4.5[1]算法,构造纳税信用等级评定规则决策树,对纳税人的纳税信用等级进行判定。
利用决策树对纳税人的纳税信用等级进行判定,首先通过采集、分析和处理已经确定了纳税信用等级的纳税人的相关数据来得到生成决策树的训练数据,然后通过训练数据生成决策树,并对未评定等级的纳税人实施计算机自动等级评定。实验数据采集对象是我省某市地税局所管辖的部分纳税人,共采集了A、B、C三类纳税人在过去二年的涉税数据,在实验过程中通过增加和减少生成决策树的属性个数来获取最佳效果。利用生成的决策树获取相关规则,对未评定纳税信用等级的纳税人进行纳税信用等级判决,取得了理想的效果。
2 应用决策树算法构造纳税信用等级评定决策树
决策树学习是以实例为基础的归纳学习算法,它从一组无序、无规则的事例中推理出决策树表示的分类规则。构造决策树的目的是找出属性和类别间的关系,用它来预测将来未知类别的记录类别。当前决策树分类算法主要有CLS、ID3、C4.5、CART、SLIQ、SPRINT等,本文选取的C4.5算法是用于构造决策树的经典算法之一。
2.1 C4.5算法
C4.5算法是Quinlan于1993年提出的,是在ID3[2]算法基础上发展起来的决策树生成算法。较之于ID3算法,C4.5算法克服了它在应用中的不足,主要体现在以下几个方面:
1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;
2)在树构造过程中或者构造完之后进行剪枝;
3)能够完成对连续属性的离散化处理;
4)能够对不完整数据进行处理;
5)能够生成类规则;
6)提高了预测正确率、速度和鲁棒性等等。
C4.5算法主要内容[1,3]:
设S是s个数据样本的集合。假定类标号属性具有m个不同值,定义m个不同类Ci(i=1,…,m)。设si是类Ci中的样本数。对一个给定的样本分类所需要的期望信息由下式给出:
其中pi是任意样本属于Ci的概率,并用si/s估计。对数函数以2为底,因为信息用二进位编码。
设属性A具有v个不同值{a1,a2,...,av}。可以用属性A将S划分为v个子集{S1,S2,...,Sv};其中,Sj包含S中这样一些样本,它们在A上具有值aj。如果A选作测试属性(即最好的分裂属性),则这些子集对应于由包含集合S的节点生长出来的分枝。设sij是子集S中类Ci的样本数。根据由A划分成子集的熵[4](entropy)或期望信息由下式给出:
项(S1j+...+Smj)/S充当第j个子集的权,并且等于子集(即A值为aj)中的样本个数除以S中的样本总数。熵值越小,子集划分的纯度越高。对于给定的子集Sj,
其中,Pij=Sij/|Sj|是Sj中的样本属于类Ci的概率。
在A上分枝将获得的编码信息是:
信息增益率函数:
算法计算每个属性的信息增益率。具有高信息增益率的属性选作集合S的测试属性。创建一个节点,并以该属性标记,对属性的每个值创建分枝,并以此划分样本。
2.2 纳税信用等级评定属性选择及决策树生成
2.2.1 属性选择
本文采集的训练数据为已经过手工评定,确定了纳税信用等级纳税人的涉税数据。根据手工评定过程中所涉及的内容、税务专家经验和属性相关性原则[5],选取了包括申报率、入库税额、欠缴税额、稽查补缴税额、违法违章、重点户标识、注册资金、从业人数等属性,决策树生成属性如表1所示。
类别C的集合是{A,B,C},属性S的集合是{申报率、入库税额、欠缴税额、稽查补缴税额、违法违章、重点户标识、注册资金、从业人数}。本文的方法还可以根据应用加入需要的属性,例如纳税人行业、经济类型等。申报率是纳税人每月已申报税种(目)数/应申报税种(目)数*100%;稽查补缴税额是通过税务稽查结果,要求纳税人应少缴而补缴的税额;违法违章为该纳税人在过去一年内有无违法违章记录。
2.2.2 数据准备和预处理
抽样训练数据必须全面客观的反映纳税人的实际涉税情况,这样生成的决策树才能够比较准确对那些采集的纳税人涉税数据进行判决,确定最终纳税信用等级。本次采集的训练样本数据是从地税核心业务系统-税收征管数据库中抽取的纳税人数据,通过编写数据库存储过程完成数据抽取工作,按照A、B、C三类的实际比率共抽取了约一万户纳税人的相关属性资料。抽取的训练样本数据如表2所示。
表2中的注册资金、从业人数两个属性由于税务机关在基础资料采集时不完整,很多数据缺失或采集失真。虽然C4.5算法可以允许训练样本集中出现属性空缺,但由于数据失真和空缺量过大,直接影响到决策树生成的准确性,因此我们在决策树生成过程中选择了忽略以上两个属性。另外,抽样数据中欠缴税额、稽查补缴税额两个属性值绝大部分为零,只有少部分纳税人有欠税和稽查补缴税款,因此为便于挖掘,直接将其离散化为false、true(大于0的为true,小于等于零的为false)。
2.2.3 生成决策树
应用C4.5算法对以上完成数据准备的数据进行决策树规则挖掘,纳税信用等级评定决策树生成步骤如图1所示。
按照图1的流程和C4.5算法步骤,用VC++平台加以实现,对抽样训练数据进行数据挖掘,得到的决策树共15个节点。
2.2.4 剪枝
决策树的剪枝分为先剪枝和后剪枝两种。先剪枝就是在完全正确分类训练集之前较早地停止决策树的生长,有多种不同的方法[6]。本文采用的是后剪枝方法。对每个叶子结点,分类错误率为该结点中不属于该结点所表示类别的样本的权值之和;对于非叶结点,分类错误率为它的各个孩子结点的分类错误率之和。如果计算出某结点N的分类错误率超过了将结点N所代表的样本集S中的所有样本分配为S中出现最多的类别所得的分类错误,则将结点N的所有子枝剪去,使N成为叶结点,将S中出现最多的类别分配给它。对以上生成的决策树进行剪枝得到最终的决策树共11个节点,如图2所示。
注:表1中continuous表示该属性值为连续的数值,省略号表示属性可以根据需要来进行添加。
2.3 规则知识描述
为了更清楚的理解决策树的知识表示,可以把图2的决策树转化成规则,形式如下:
IF(入库税额<=33430元)AND(申报率>85%)THEN(B类纳税人);
IF(入库税额<=33430元)AND(申报率<=85%)AND(欠税税额=true)THEN(C类纳税人);
IF(入库税额<=33430元)AND(申报率<=85%)AND(欠税税额=false)THEN(B类纳税人);
IF(入库税额>33430元)AND(重点户标识=true)THEN(A类纳税人);
IF(入库税额>274512元)AND(重点户标识=false)THEN(A类纳税人);
IF(274512>=入库税额>33430元)AND(重点户标识=false)THEN(B类纳税人);
由以上规则可以看出,纳税人的纳税信用等级与年入库税额关系最大。年入库税额在3万元以下主要为B、C两类,其申报率和欠税是判定其为B、C的主要依据;年入库税额在27万元以上的基本都为A类;年入库税3万到27万元之间的纳税人主要确定属性是重点户标识,是重点户的为A类,非重点户为B类。这些规则的发现对税务机关的纳税信用等级评定工作来说具有重要意义。
生成规则后即可使用决策树对尚未评定等级的纳税人进行纳税信用等级评定,应用决策树进行纳税信用等级判决的流程:待确定等级纳税人涉税数据输入→决策树判决计算→输出纳税信用等级评定结果。
2.4 决策树验证
应用生成的决策树进行纳税信用等级评定是本文主要研究目的,我们抽取了待评定等级的513户纳税人的有关数据,应用决策树进行判决,判决结果A类32户、B类382户、C类99户,税收专家经过对这些纳税人相关资料的分析研究,认为判决结果要比手工评定的合理。另外,我们还直接应用抽样数据对决策树规则进行了验证,错误率为17.2%。这足可以说明利用C4.5算法生成的决策树是有效的。
3 结束语
决策树在市场划分、金融风险、产品开发以及故障诊断中已经得到了比较广泛的应用。C4.5算法是决策树的一个经典算法,文中把C4.5算法应用到纳税信用等级评定中,通过对样本数据的学习训练生成决策树,根据生成的决策树来对纳税人进行纳税信用等级评定,为改变了纳税信用等级手工评定的现状提供的重要手段,实现了纳税信用等级评定的自动化和智能化,对于建立公平、公正的纳税信用体系具有重要意义。
摘要：纳税信用等级评定的实现是需要对大量税收数据进行分析和判定的结果,决策树是进行数据挖掘和分类的常用工具,其中以C4.5算法最为流行。如何应用数据挖掘技术改变纳税信用等级手工评定的现状是当前税务系统税收信息化工作难点之一。文章主要讨论如何应用C4.5算法构造纳税信用等级评定决策树,通过对纳税人涉税数据的采集、预处理、属性选择、决策树生成和剪枝等一系列过程最终生成纳税信用等级评定决策树,并根据生成的决策树实现对纳税人纳税信用等级的判决。
关键词：决策树,C4.5算法,纳税信用等级评定
参考文献
[1]QuinlanJ R.C4.5Programs for Machine Learning[M].San Mateo:Morgan Kaufmann Publishers,Inc,1993:202-207.
[2]Quinlan J R.Induction of decision tree[J].Machine learning,1986(1):81-106.
[3]HAN Jia-wei,Kamber M.Data Mining Concepts and Techniques[M].机械工业出版社,2001:08.
[4]何劲松,郑浩然,王煦法.从熵均值决策到样本分布决策[J].软件学报,2003,14(3):479-483.
[5]范洁,常晓航,杨岳湘,基于属性相关性的决策树规则生成算法[J].计算机仿真,2006,23(12):90-92.
决策树相关算法研究 篇8
随着数据库技术的广泛应用和数据库管理系统的普及, 现在各行业使用的信息系统尤其是国内金融部门使用的大多数业务处理系统都是基于数据库的, 能够实现业务数据的录入、查询、更新、统计等功能, 并将与业务相关的数据存储在数据库中。数据库存储中的这些大量数据往往隐含着重要信息, 如果对其进行深入的分析, 挖掘数据背后隐藏的信息, 发现大量客户数据中潜在的关联和规则, 以此对未来的发展趋势做出预测, 从而在企业的管理和决策中发挥重要作用。数据挖掘就是从大量的数据中提取出隐藏在其中的, 有应用价值的信息和规则的过程。
客户关系管理 (Customer Relationship Management, CRM) 是一种以客户为核心的经营理念, 通过不断完善客户的服务来实现企业利润的增长。即通过客户信息的分析处理, 不断改进客户业务流程, 满足客户需求, 为客户提供所需要的服务等手段来实现客户和企业利润的增加, 提高对客户的营销能力, 从而实现客户和企业的相互的利益满足。客户分类是CRM中一个重要方面, 而决策树方法是分类分析的常用工具。
决策树是数据挖掘技术中常用的分类方法, 将挖掘的结果以树形结构的图形方式体现出来, 具有结构简单, 易于理解, 效率高等优点。决策树分类挖掘技术广泛应用于各行业的客户关系管理系统中, 通过对客户相关信息的分析, 对客户所属的类别进行预测, 从而采取相应的措施和服务策略, 提高服务水平和工作效率, 从而得到较大的收益。
1 决策树C4.5算法
1.1 C4.5算法
决策树在数据挖掘领域因其分类预测的准确率较高、直观易于理解等特点, 广泛应用在各领域。决策树算法比较多, 不同算法创建的决策树的性能也各有所不同, ID3和C4.5算法是决策树方法中最有影响力的算法, 主要进行数据分类划分的处理。C4.5算法是ID3算法的改进和扩充。ID3算法只能对连续型属性数据进行处理, 而C4.5算法既可以处理离散型属性数据, 也能够对连续性属性数据进行处理。
C4.5算法构造决策树时选择分支节点属性的依据是信息增益率。ID3算法中节点属性的选择标准是信息增益的大小, 因为有较多取值的属性具有较大的信息增益的特点, ID3算法节点属性的选择侧重于取值较多的属性[1]。而C4.5算法以信息增益率为属性节点的选择依据, 克服了ID3算法的倾向于选择取值较多的属性的不足。
1.2 C4.5算法的处理过程
C4.5算法的详细步骤如下:
步骤1:若数据集中的有连续型属性, 需要离散化处理。进行离散化数据预处理后, 进行根节点属性的选择。计算数据集中所有属性的信息增益率, 选择其中的最大值的属性作为根节点属性。
1) 计算数据集分类的信息期望I。设S为有n个实例的数据集合, 依据实例所属的类别, 集合S有m种划分{S1, S2, …, Si, …Sm}, 每种划分的实例数目为ni, pi=ni/n是Si类出现的概率。将集合S划分为m个类别的信息熵或信息期望[2]为:
2) 计算非类别属性A的信息期望I (A=aj) , j=1, 2, …, v, 即属性A有v个取值, 将S划分为v个子集{D1, D2, …, Dv}, Dj为A=aj时的子集, Dj的实例数为dj, Dj子集中属于Si类的实例数为dij, 属于第i类的概率为pij, pij=dij/dj, 信息期望I (A=aj) 为:
当A=aj时的概率为pj=dj/n, 利用属性A的取值进行划分子集的期望信息, 即A的熵为:
属性A在进行分类划分时提供的信息量, 称作属性A的信息增益, 记为Gain (A) :
3) 属性A的信息增益率:
其中I (A) 为属性A的取值划分集合S的信息期望的比值
步骤2:确定节点属性后, 根据节点属性不同取值建立不同的分支, 而属性值的不同取值对应不同的数据子集。依此类推, 对各数据子集, 仍然以信息增益率最大值的属性作为作为子节点属性的选择标准[3], 直到各子集的实例都属于同一类别为止, 由此就能构造一棵决策树。
步骤3:提取决策规则。生成决策树后, 就可以依据各分支上属性的取值获取决策规则, 新数据集就可以根据决策规则进行分类预测。
1.3 C4.5算法对连续属性的处理
C4.5算法既能处理离散型属性数据, 也能够对连续性属性数据进行处理[4]。若数据集中有连续型属性时, 需要对连续属性的值进行离散化处理, 选择分支节点属性以信息增益率作为标准。
如果某节点中数据集合T的实例中有连续型属性A, C4.5算法需进行离散化处理[5]。首先可对连续属性值进行排序, 确定连续属性的最大值和最小值, 采用一定的算法将整个区间划分成多个相等的子区间或以排序后的连续型属性的相邻值的均值设定子区间, 然后计算该属性的信息增益率, 以信息增益率的最大值为标准找到连续属性的分割点, 对连续型属性的实际取值进行顺序查找确定实际的分割点[6]。具体步骤如下:
1) 对节点对应的T集合上的所有实例中连续型描述属性的取值, 按从小到大的顺序进行排列, 得到属性A的取值的顺序排列{a1, a2, …, av}。
2) 计算信息增益率。属性A的取值ai, 其中1≤i≤v-1, 按值a= (ai+ai+1) /2将集合T划分为两个子集:T1={ai|ai≤a}和T2={aj|aj>a}, 然后计算属性A按照a值划分的信息增益率。a值用区间[a1, ai], [ai, ai+1]来描述属性A的取值。
3) 确定连续属性的分割点。属性A的每个v-1种划分, ai和ai+1都可看作该连续属性的2个离散取值的情况进行处理, 计算每种a值划分的信息增益率, 选择v-1种划分中具有信息增益率最大值的a作为连续属性的分割点。
4) 确定实际分割点。在属性A的取值序列{a1, a2, …, av}中找出最接近分割点a, 但又不超过它的属性A的取值ai, 将ai作为属性A的实际分割点, 完成对连续型属性A的离散化处理。
2 连续属性处理过程的改进
将数据集合T以属性A的值按照升序排序后, 在离散化的处理过程中进行信息增益率的计算时, 可将通过比较得到的信息增益率最大值和对应的分割点的序列值分别保存到变量Gain Max和Index M ax中, 变量的初值可设为零。当计算完所有的v-1个区间的信息增益率值时, 就得到了Gain Max和Index Max值, 这样能够提高效率, 节省运算时间, 也省略了多次顺序查找, 因为如果在计算出的v-1个信息增益率中找出最大的信息增益率, 又在连续型属性取值中查找最接近但又不超过属性分割点的属性A的取值ai, 多次的查找会使算法的执行效率降低。
当数据集较大且连续属性值比较多时, 在离散化处理时, 对所有划分计算信息增益率会占用较多的时间, 如何快速找到最佳划分点, 即属性分割点成为解决问题的关键。根据Fayyad的研究, 无论数据集类别有多少种, 连续型属性所属类别分布如何, 最佳划分点总是在类别边界点处, 实际的分割点总是出现在边界处, 因此对离散化方法可做进一步优化。具体步骤如下:
1) 将该节点上的数据集合按照连续型属性的取值从小到大进行顺序排列, 即A属性的取值的顺序序列{a1, a2, …, av}。
2) 计算信息增益率。假设数据集合T分成两个类别, 以A属性ai为边界处, 即分割点, 其中1≤i≤v-1, 得到两个子集:T 1={aj|1≤j≤i}和T2={aj|i
3) 确定连续属性的分割点。假设数据集合T分成多个类别, 通过类别边界处找到分割点。这里分割点可选为相邻不同类别的两个属性值中较小的一个。例如, 当排序后的实例属性值为 (a1, a2, …, a8) , 其中前2个属于类别1, 中间3个属于类别2, 最后3个属于类别3, a2与a3分别属于类别1与类别2, 边界点在a2与a3之间, 选择属性值较小的a2为分割点, 因此只需考察两个分割点a2与a5而无需检查其余6个分割点。
4) 确定实际分割点。计算按照属性分割点的值划分得到的信息增益率, 选择信息增益率最大的属性值作为最佳分割点。
3 改进的处理过程与原处理过程的分析比较
在处理连续属性的离散化时, 需要将数据集合T以连续属性A的值从小到大排序, 减少了后续处理过程中排序和查找的次数, 提高了确定分割点的效率。在原C4.5算法中数据集合T中属性A的值为ai (1≤i≤v-1) , 按值a= (ai+ai+1) /2将T划分为两个子样本集, 改进的C4.5算法中直接用ai将T划分为两个子样本集, 由于{a1, a1, …, av}是有序序列, 用ai将T划分为两个子样本集与用a划分的效果相同。同样在计算信息增益率的过程中得到最大信息增益率和分割点序号, 节省了两次顺序查找的时间, 因此改进后的C4.5算法并没有改变原C4.5算法构造的决策树性质。
改进的分割点选择方法可以有效地减少信息增益率的计算次数, 从而提高效率, 当属性的取值越多, 而所属的类别越少, 性能会有明显的提高。当属性的每个取值都属于一种类别这种极端的情况出现时, 改进算法与未改进算法运行次数相同, 运行效率也不会降低。在未改进的算法中, 需要计算所有划分的信息增益率, 而在改进后的算法中, 只计算边界点处的属性值的信息增益率, 降低了计算复杂度。当连续型属性所属的类别较少时如只有2种类别时, 改进后的算法计算效率有明显提高。当遇到极端情况时, 每个属性值分别属于不同类别, 改进算法的与C4.5的计算复杂度相同。
4 实验分析对比
选取U C I机器学习库中的有1 4条记录的weather数据集创建决策树, 根据天气的情况判断是否适合打球 (yes为适合, no为不适合) , 使用C4.5算法和改进的C4.5算法构造的决策树相同 (如图1) , 由此可知, 改进的C4.5算法与原算法有大致相同的准确率。
在UCI机器学习库中选取4个数据集, 这4个数据集中都有连续型属性值, 通过数据集的测试将改进前后的算法在运算时间上进行分析比较。其中各数据集如表1所示。
C4.5算法与改进的C4.5算法运算时间的对比如图2所示。
使用数据集构造决策树所用时间, 与数据集的大小及连续型属性值的多少有关。通过上述4个数据集进行测试的结果可以看出, 使用改进的C4.5算法构造决策树所用的时间比未改进的算法要快, 尤其在数据量较大时较为明显, 对相同规模的数据集, 改进的C4.5算法构造决策树所用的时间较少。
5 结束语
本文详细的分析了决策树分类算法C4.5, 针对C4.5算法的连续属性离散化处理过程中需要处理所有划分情况的特点, 根据Fayyad边界点判别定理, 提出了尽快找到最佳划分的改进方法, 算法运算速度得到了提高, 改进的C4.5算法与原算法相比, 在构造决策树时具有相同的准确率和较高的计算速度。
参考文献
[1]姚亚夫, 邢留涛.决策树C 4.5连续属性分割阈值算法改进及其应用[J].中南大学学报 (自然科学版) , 2011, 42 (12) :3772-3776.
[2]黄文.决策树的经典算法:ID3与C4.5[J].四川文理学院学报 (自然科学) , 2007, 17 (5) :16-18.
[3]刘耀男.C 4.5算法的分析及应用[J].东莞理工学院学报, 2012, 19 (5) :47-52.
[4]冯帆, 徐俊刚.C 4.5决策树改进算法研究[J].电子技术, 2012, 39 (6) :1-4.
[5]乔曾伟, 孙卫祥.C4.5算法的两点改进[J].江苏工业学院学报, 2008, 20 (4) :56-59.