id3算法的改进和简化

《id3算法的改进和简化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第44卷第7期上海交通大学学报Vol.44No.72010年7月JOURNALOFSHANGHAIJIAOTONGUNIVERSITYJul.2010文章编号:100622467(2010)0720883204+0891ID3算法的改进和简化1,2,3朱颢东(1.郑州轻工业学院计算机与通信工程学院,郑州450002;2.中国科学院成都计算机应用研究所,成都610041;3.中国科学院研究生院,北京100039)摘要:针对ID3算法倾向于选择取值较多的属性的缺点,引进属性重要性来改进ID3算法,并根据改进的ID3算法中信息增益的计算特点,利用

2、凸函数的性质来简化该算法.实验表明,优化的ID3算法与原ID3算法相比,在构造决策树时具有较高的准确率和更快的计算速度,并且构造的决策树还具有较少的平均叶子数.关键词:决策树;ID3算法;属性重要性;信息增益;凸函数中图分类号:TP301文献标志码:AResearchonImprovementandSimplificationofID3Algorithm1,2,3ZHUHao2dong(1.SchoolofComputerandCommunicationEngineering,ZhengzhouUniversityofLightIndust

3、ry,Zhengzhou450002,China;2.ChengduInstituteofComputerApplication,ChineseAcademyofSciences,Chengdu610041,China;3.TheGraduateSchooloftheChineseAcademyofSciences,Beijing100039,China)Abstract:FortheshortcomingthatID3algorithmtendstochooseattributewhichhasmanyvalues,attrib2utei

4、mportancewasintroducedtoimproveID3algorithm.Next,accordingtothecharacterofinformationgain,theimprovedID3algorithmwassimplifiedtoreducethecomplexityofcomputinginformationgainbytheconvexfunction.Throughexperimenttesting,theoptimizedID3algorithmcanspendmuchlesstimetoconstruct

5、thehighaccuratedecisiontreeandthisdecisiontreehaslessaverageleaves.Keywords:decisiontree;ID3algorithm;attributeimportance;informationgain;convexfunction[2210]决策树分类是一种十分重要的数据挖掘方法,研究表明:式(1)倾向于选择分支值较多的[1]在众多决策树构造方法中,ID3算法最具影响力,属性作为分支节点,而分支值较多的属性却并不总[2210]人们对其进行了深入研究.在此基础上,本文从

6、是最好的属性.例如:Bratko研究小组在研究判断解决ID3算法倾向于选择取值较多的属性的缺点以病情的各种因素时,用ID3确定“病人的年龄(有9及简化ID3算法的角度进行了研究.种值)”为应该首先选择的属性,但在实际情况中,医学专家却认为这个属性在判断病情时没那么重1ID3算法的不足及其改进[3]要.文献[327]中在ID3算法里引入一个用户兴趣[1]ID3算法的核心计算公式为度,取值为[0,1],具体由用户根据经验给出,虽然能Gain(A)=I(s1,s2,⋯,sm)-E(A)(1)在一定程度上克服该算法的缺点,但在使用用户兴收稿日期:2

7、009209224基金项目:四川省科技计划项目(2008GZ0003);四川省科技厅科技攻关项目(07GG0062019)作者简介:朱颢东(19802),男,河南虞城人,博士生,主要研究方向为软件过程技术与方法、文本挖掘、智能信息处理.884上海交通大学学报第44卷趣度时需注意:显然有0≤γ(R,D)≤1,γ(R,D)给出了决策属(1)对用户感兴趣的属性,可根据先验知识或领性D与属性集R之间相依性的一种测度.它反映了域知识进行测试,选择符合实际情况的用户兴趣度.属性集R对于决策D的重要程度.在已知R的前提(2)当大多数属性数据量较大、个别属

8、性数据下,一个属性a∈R对于决策D的重要性定义为量较小,且人们对这些属性重要性认识不足时,选择SGF(a)=γ(R,D)-γ(R-{a},D)(4)这些属性的用户兴趣度,使其不会