竞争选择分裂属性的决策树分类模型.pdf

计算机技术与发展
第16卷第8期Vol.16No.8
2006年8月COMPUTERTECHNOLOGYANDDEVELOPMENTAug.2006

竞争选择分裂属性的决策树分类模型

房立,黄泽宇
(北京交通大学计算机与信息技术学院,北京100044)

摘要:构建决策树分类器关键是选择分裂属性。通过分析信息增益和增益比率、Gini索引、基于Goodman-Kruskal关联
索引这三种选择分裂属性的标准,提出了一种改进经典决策树分类器C4.5算法的方法(竞争选择分裂属性的决策树分类
模型),它综合三种选择分裂属性的标准,通过竞争机制选择最佳分裂属性。实验结果表明它在大多数情况下,使得不牺牲
分类精确度而获得更小的决策树成为了可能。
关键词:决策树;信息增益;增益比率;Gini索引;Goodman-Kruskal关联索引
中图分类号:TP311113文献标识码:A文章编号:1673-629X(2006)08-0106-04

ADecision-TreeClassifierModelofCompetition
inChoosingSplitAttribute

FANGLi,HUANGZe2yu
(DepartmentofComputerScienceandInformationTechnology,JiaotongUniversity,Beijing100044,China)

Abstract:Theconstructionofdecision-treeiscenteredontheselectionalgorithmofanattributethatgeneratesapartitionofthesubsets
ofthetrainingdatabasethatislocatedinthenodeabouttobesplit.Onthebasisofanalyzingthreetechniquesforchoosingthesplittingat2
tributesincludingtheentropygainandthegainratio,theginiindexandGoodman-Kruskalassociationindex,proposeastrategytoim2
proveonclassicaldecision-treeclassifierC4.5arithmetic(adecision-treeclassifiermodelofcompetitioninchoosingsplitattribute).Ex2
perimentalresultsshowitispossible,inmostcases,toobtainsmallerdecisiontreeswithoutsacrificingaccuracy.
Keywords:decision-tree;entropygain;gainratio;giniindex;Goodman-Kruskalassociationindex

0前言寸大小。
分类在数据挖掘中是一项非常重要的任务。分类的
目的是学会一个分类函数或分类模型(也称分类器),该模1决策树分类模型
型能把数据库中的数据项映射到给定类别中的某一个,以决策树分类可描述为:输入数据即训练集是由一条条
根据历史数据记录对未来数据进行预测[1,2]。记录组成的。每条记录由若干条属性及一个特定的类标
分类器的构造方法有统计方法、机器学习方法、神经
签组成,如(a1,⋯,an,c),其中ai(i=1,⋯,n)表示属
网络方法等等。其中机器学习方法包括决策树法和规则
性,c表示类标。给定训练集D={x1,x2,⋯,xn},目标是
归纳法。这些方法各自在不同的领域中起到了很重要的
确定一个映射函数f:(A1,A2,⋯,An)→C,使得对任意
作用,如:在经济业和安全交易领域中可以建立不同的模
的未知类别的实例xi=(a1,a2,⋯,an)可标以适当的类
型:预测债券价格的变化;决定交易的最佳时刻。航空公标C3。
司可根据历史资料寻找乘客的旅行模式,改进航线的设置。决策树方法利用信息增益寻找示例数据库中具有最
构建决策树分类器最重要的是选择分裂属性。文中
大信息量的属性字段,建立决策树的一个节点,再根据该
仔细地分析了信息增益和增益比率、索引、基于
Gini属性字段的不同取值建立树的分支;在每个分支子集中重
Goodman-Kruskal关联索引这三种选择分裂属性的标
复上述过程,直至节点中所有记录的类别都相同,再通过
准并根据经典决策树分类器算法提出了一种改进
,C4.5剪枝生成最终的决策树。
方法。这种方法综合了上述三种选择分裂属性的标准,通
最典型的决策树学习算法ID3的算法核心是在决策
过竞争机制选择