1、数据库与数据挖掘,多媒体制作;E 2m ai:l hn l dhah to m .co m 。近年来,决策树方法在机器学习、知识发现等领域得到了广泛应用。数据挖掘作为一种发现大量数据中潜在信息的数据分析方法和技术,已经成为各界关注的热点。其中,决策树以其出色的数据分析效率、直观易懂等特点,倍受青睐。构造决策树有多种算法,国际上最早的、具有影响力的决策树是由Qu i n lan 于1986年提出的I D 3算法1,是基于信息熵的决策树分类算法。I D3算法采用信息熵作为属性选择标准,可这个标准易偏向于取值较多的候选属性。Qu i n lan 于1993年又提出了I D3的改进版本C4.5算法2,
2、C4.5算法用信息增益率来选择决策属性,它继承了I D 3算法的全部优点,在I D3的基础上还增加了对连续属性的离散化、对未知属性的处理和产生规则等功能。在决策树算法中,决策树的复杂度和分类精度是需要考虑的两个最重要的因素。常用的评价指标有:预测准确性,描述分类模型准确预测新的或未知的数据类的能力。描述的简洁性,模型描述越简洁,也就越易于理解。计算复杂性,模型强健性,处理规模性。1 C4.5决策树算法1.1 C4.5决策树算法C4.5决策树算法的核心思想是利用信息熵原理,选择信息增益率最大的属性作为分类属性,递归地构造决策树的分枝,完成决策树的构造3。假设向量空间中的正例集PE 和反例集NE
3、的大小分别为p 和n,I D3基于两个假设:（1在向量空间H 上的一棵正确决策树对任意例子的分类概率同H 中正反例的概率一致;（2一棵决策树能对一例子做出正确类别判断所需的信息量为I（p,n=-pp +n lg 2p p +n -n p +n lg 2n p +n（1如果以属性A 作为决策树的根,A 具有V 个值（v 1,v 2,v v ,它将H 分为v 个子集（H 1,H 2,H v ,假设H i 中含有P i 个正例和N i 个反例,子集H i 的信息熵E （H i E （H i =-P i P i +N i l g 2P i P i +N i -N i P i +N i l g 2N i
4、P i +N i（2以属性A 为根分类的信息熵为E （A :E （A=Evi=1P i +n iP +NE （H i （3因此,以A 为根的信息增益是G（A:G （A =I（p,n -E （A（4信息增益率等于信息增益对分割信息量的比值。对样本集T ,假设A 有s 个不同取值的离散属性,划分为s 1,s 2,s n 共n 个子集,用A 分割样本集所得的信息增益的算法I D 3相同,分割信息量由以下公式给出S（s ,A=-ns i s lg 2s is（5信息增益率由下式给出G -R （s ,A=G（s ,A S（s ,A（6C4.5算法选择G -R（A最大的属性A 作为分支属性,较好地解决了I
5、 D3算法的多值属性偏向问题。1.2 C4.5算法代码假设用T 代表当前样本集,当前候选属性集用T .a ttribute list 表示,则C4.5算法C4.5f or m tree（T ,T .a ttribute list的伪代码如下5算法:Gen erate_d ec i s ion_tree 由给定的训练数据产生一棵决策树输入:训练样本sa m p l es ;候选属性的集合attributelist 输出:一棵决策树 （1创建根节点N ;（2 IF T 都属于同一类C ,则返回N 为叶节点,标记为类C ; （3IF attribute list 为空OR T 中所剩的样本数少于某给
6、定值则返回N 为叶节点,标记N 为T 中出现最多的类:（4 FOR each attri bu telis t 中的属性计算信息增益率infor m ati on gai n rati o ; （5 N 的测试属性test .attri bu te =attribute list 具有最高信息增益率的属性;（6 IF 测试属性为连续型则找到该属性的分割阈值; （7 For each 由节点N 一个新的叶子节点 If 该叶子节点对应的样本子集T .为空则分裂此叶子节点生成新叶节点,将其标记为T 中出现最多的类E l se在该叶子节点上执行C4.5for m tree（T .,T .attr i
7、bu telist,继续对它分裂;（8计算每个节点的分类错误,进行树剪枝。2 C4.5决策树算法改进2.1 C4.5算法改进的原理根据上述信息量计算公式的特点,提出针对信息量计算的改进方法,用以简化信息量计算的复杂度。由式（3和式（4可知,C4.5算法是对节点上的每个属性都要计算其信息增益率,然后从中选择信息增益率最大的属性作为该节点的属性。由于在信息增益率计算过程中涉及到对数函数的计算,在计算程序中就得调用库函数,这样就增加了计算量时间。如果能找到一种选择属性的新标准,使计算量减少,就可加快算法生成树的速度。设在n 个反例、p 个正例属性的信息量为信息熵为E （A =Ep i +n ip +
8、nI （n i ,p i 。其中I （n i ,p i =-n i p i +n i lg 2n in i +p i-p i n i +p i l g 2p iE （A=1（n +pln2E ni=1-p i ln p i n i +p i -n i ln n i（7由于1（n +p ln2为一常量且每步都要计算,可省略。E （A可变为:-p i lnp i n i +p i -n i lnn i（8用式（8作为选择节点属性熵的依据。根据数学上的等价无穷小的理论,如果X 很小,则ln （1+X U X,可得:l n p i n i +p i =l n 1-n iU -n i n i +p i
9、（9l nn i n i +p i =l n 1-p iU -p i n i +p i （10将式（9、式（10代入式（8得E c （A =U 351期黄爱辉:2En i p i n i +p i（11S c （s ,A=-n i p i +n i lg 2n i-p i n i +p i lg 2p iU Ep i n i +p i（12G -R .（s ,A=I（S ,A-E c （AS c （s ,A（13因此可以用式（11、式（12和式13替换C4.5算法中的E （A、S（s ,A和信息增益率,用来从中选择/信息增益率0最小的属性作为节点。利用这种计算方法仅仅是加、乘、除的运算,在计算
10、机上实现很快。,这样C4.5算法的计算量大大减少,提高了C4.5算法的效率。2.2 C4.5决策树算法及改进算法做比较2.2.1 C4.5算法构造决策树以UCI 数据集中经典实例/天气表0中的24条记录为例（根据天气条件的记录来决定是否适合打高尔夫球,用C4.5决策树算法和改进的C4.5决策树算法构造的决策树相同,如图1图1 C4.5算法和改进后的C4.5构造的决策树2.3 改进的C4.5决策树算法应用将数据挖掘分类技术应用于对高职院校教学的成绩信息挖掘无疑是非常有益的,它可以全面地分析考试成绩与各种因素之间隐藏的内在联系。比如,经过对学校学生成绩相关数据库中数据的分析,数据挖掘工具可以回答诸
11、如/哪些因素对学生的学习成绩可能有影响0等类似的问题,这是传统评价分析方法无法具备的。通过数据挖掘分析,其评价结果能给教学带来前所未有的收获和惊喜。提出采用数据挖掘中的改进后的C4.5决策树算法,将大量的成绩数据转化为分类规则,从而更好地分析这些数据。以表1/学生成绩分析基本数据集0为例,对影响学生学习成绩的因素进行分析。由于学生信息表中的属性字段很多,在建立成绩是否优良决策树模型时,以2005级计算机应用技术专业的5网页制作6课程成绩为例,选择了与成绩属性相关性较大的课后上机时间、课前对课程的了解程度、课堂学习情况、平时作业情况属性字段,是否优良属性作为类别属性,得到表1的数据。表1 成绩是
12、否优良的数据集每周上机时间课前对知识的了解程度课堂学习情况平时成绩是否优良2基本了解差较差否2-4基本了解基本掌握较好是2-4基本了解基本掌握中否4了解一些基本掌握中否2-4不了解基本掌握较好是2-4了解一些一般较好否2-4了解一些基本掌握较好是2了解一些基本掌握较差否2了解一些差中是,表中共有125条记录（学生,其中正例为41个,反例为84个。用改进后的决策树C4.5对表中的数据进行处理,分别计算每个属性的信息增益率。平时成绩的信息增益率最大,因此作为决策树的根节点,平时成绩有3个值,有三个分支,分别计算平时成绩为/较好0、/中0、/差0的信息增益率,得到如图2所示的决策树。图2 成绩是否优
13、良决策树（下转第42页R esea rch of App lica tion ofW eb Service i n G r i dCHEN W en2j u n,Q I X in,GAO Yuan2tao（A cade m i c Adm i n i strati on,Ch i na Un i versity of Petrol eum,Q i ngdao266555,P.R.Ch i naAb stra ctA ne w k i n d of technology is i n troduced f or gridthe integration ofWeb Service and Grid
14、.The pe2 culiarity ofWeb Service is app lied into the grid technology,and t h en experi m ents are made of under the grid envi2 ronmen.t The resu lts sho w that t h e Web Service provi d es stable f oundati o n f or the deve l o pment of Grid.K ey word sgrid co mputati o n W eb Service state WSDL S
15、OAP（上接第36页3结论从上述用天气表中数据生成决策树的形态得到的结果,可以得出如下结论:C4.5改进算法构造的决策树与C4.5算法构造的决策树有大致相同的分类准确率,在相同规模的数据集中,C4.5改进算法构造决策树所用的计算时间比C4.5算法构造决策树所用的计算时间少,充分说明C4.5改进算法提高了决策树构造的效率。将C4.5算法应用到成绩分析中,通过决策树模型,找出影响成绩的因素,以便于教学。参考文献1H an J i a we,i M i ch eli ne K.数据挖掘:概念与技术TP274.范明孟小峰,译.北京:机械工业出版社,2001:702182Qu i n lan J R.C
16、4.5:P rogra m s f or m ach i ne l earn i ng.M organ K auff2 m an.19933李强,创建决策树算法的比较研究2I D3,C4.5,C5.0算法的比较.甘肃科学学报,2006;（12:84874马秀红.数据挖掘中决策树的探讨.计算机工程与应用,2004;（1:1855h tt p:/ftp.i cs.u c.i edu/pub/m ach i n e2learn i ng2databas eC4.5A lgor ith m of Decisi on T ree I m prove m en t and App licationHUAN
17、G A i2hui（E lectron i c i n for m ation engi n eeri ng,Vocational and T echn i calColl ege of Loud,i Loud i417000,P.R.Ch i naAb stractA ccordi n g to C4.5algorithm i n t h e rate of i n f or mation gai n characteristics of the princi p le of usi n g mathe matical equ iva lent of the infinitesi m a l
18、 nature of a ne w a l g orit h m to i m prove the C4.5,reduce the ra te of inf or2 mati o n gai n ca lculati o n,thus i m pr ovi n g C4.5algorith m Inf or m ati o n ga i n ca lculati o n of the rate of ef ficiency.I m2 proved C4.5algorith m co mpared w ith the ori g ina lC4.5algorith m,dec ision tree structure,w it h the sa m e accuracy rate and a higher speed,w ill i m prove af ter the C4.5a l g orit h m applied to the ana l y sis of resu lts.K ey word sdecision tree C4.5algor ithm i n f o r m ation ga i n2ratio equ i v a lent i n fi n itesi m al
