决策树中基于基尼指数的属性分裂方法陈云樱,吴积钦,徐可佳(西南交通大学电气工程学院,四川成都610031)摘要:决策树是数据挖掘中的一个重要算法。文中首先介绍了决策树的生成思想,和生成过程中关于多值属性的分离问题。基尼指数是多值属性分离的一种方法,文中详细介绍了基尼指数作为一种不纯度分裂方法的原理,并通过一个分别用两种方式进行基尼分裂的实例。最后参阅国内外文献将基尼指数与其他一些算法如信息增益、χ2统计作了比较来说明其在多值属性分裂时的一些优点和缺点。中图分类号:TP301.6文献标识码:A文章编号:1005-3751(2004)05-0066-03UsingGini-IndexforAttributeSelectioninDecisionTreesCHENYun2ying,WUJi2qin,XUKe2jiaAbstract:DecisionTreeplaysanimportantroleindatamining.Firstly,introducehowtheDecisionTreegrows,thenpresenthowtousetheGini-Indexformulti-attributeselectioninDecisionTree,andintroducesomeotherattributeselectionmethods.AndgiveatestthoughthetwodifferentwaysofGini-Index.ComparetheGini-IndexwithInformationGainandχ2statisticathomeandabroad.0引言数据挖掘的核心算法主要有统计分析、神经元网络、决策树和遗传算法等,其中作为主要算法之一的决策树算法是当前比较活跃的领域。常用的决策树算法有很多种:ID3,C4.5,CHAID,CART,ASSISTANT等。可以用一棵倒置的树状结构来形象地描述决策树,一棵决策树包含一个根节点、零个或者多个内部节点和一个或者多个叶子节点。它利用树的结构的不同对记录集进行不同的分类,树的每个叶节点就代表某个条件下记录集中的一个子集,根据记录集中属性的不同来进行属性的分裂,建立下层节点,即进行树的分枝,整个过程自顶向下递归构造决策树,这就是决策树生成的思想1。裂,从而建立下层节点,这是决策树建立过程中一个重要问题,人们称之为splitattributes,一些论文中也称之为goodnessfunction。不同的决策树算法使用不同的属性分裂方法,最常见的是基于信息增益(InformationGain)的分裂方法,例如ID3和C4.5;基尼指数(GiniIndex),例如CART算法、SLIQ算法、SPRINT算法和IntelligentMiner(IBM公司的数据挖掘工具)中的决策树算法;χ2统计(Chi-squaredstatisticχ2),例如CHAID算法;相关度(Relevance);G统计(GStatistics)等等。文中详细研究基尼指数作为决策树中属性分裂的方法,并就一些常见的方法进行对比。基尼指数是一种不纯度分裂方法,它能适用于类别、二进制、连续数值等类型的字段,是Breiman等人于19842年在文ClassificationandRegressionTrees中提出的,具体算法思想:假设集合T包含N个类别的纪录,那么其Gini指标为N1分裂属性的方法在一棵树的生成过程中,需要对一个根节点或者内部节点进行依据记录集属性的分裂,选择不同的属性,会使划分出来的记录子集不同,从而决策树生长的快慢和得到的信息规则都会受到有很大的影响。如何找到最优的分Gini(t)=1-6[p(j|t)]2(1)j=1p(j/t)为类别j在t节点处的相对频率,当Gini(t)最小为0时,即在此节点处所有记录都属于同一类别,表示能得到最大的有用信息;当此节点中的所有记录对于收稿日期:2003-08-23作者简介:陈云樱(1979—),女,四川雅安人,硕士研究生,研究方向为计算机实时控制与系统仿真、数据挖掘。用信息。如果集合分成k个部分,那么进行这个分割的Gini就是kn6iGinisplit(T)=nGini(i)(2)i=1k是子节点的个数,ni是在子节点i处的记录数,n是在节点P处的记录数。基尼指数的基本思想就是:对于每个属性都要遍历所有可以的分割方法后,若能提供最小的Ginisplit就被选择作为此节点处分裂的标准。无论对于根节点还是子节点。1.2实例在应用实例中,构造一个包括14条记录的关于天气、温度、湿度和风级的模型,用以分析比赛与上述何种因素有关,属性皆为类别字段。该集合中,天气分为Sunny(阳关充足)、overcast(多云)和rain(下雨),温度分为hot(热)、mild(温度适中)和cool(冷),湿度分为high(强湿度)和normal(一般湿度),风级分为true(是)和false(否),在class(类别)一栏用N表示负例,即“不比赛”,用P表示正例,即“比赛”,如表1所示。3222Gini(rain)=1-(5)-(5)=0.48Gini(overcast)=1-(4)2-(0)2=04所以,根...