2种启发式算法抗噪能力的对比研究

第３１卷　第１期２０１１年　１月

河北大学学报（自然科学版）

）ＪｏｕｒｎａｌｏｆＨｅｂｅｉＵｎｉｖｅｒｓｉｔＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ　　　　　ｙ（

Ｖｏｌ．３１Ｎｏ．１

Ｊａｎ．２０１１

２种启发式算法抗噪能力的对比研究

周宁１，谢博鋆２，王涛２

（）河北大学校长办公室，河北保定　０河北大学数学与计算机学院，河北保定　０１．７１００２；２．７１００２

决策树抵抗噪声的能力是启发式算法设计中的关键因素．对ＩＤ３和ＤｏＩ２种启发式算法在抵抗　　摘　要：　

噪声的能力上做了对比研究．通过实验比较得出由ＤｏＩ算法构建出的决策树在抵抗噪声的干扰方面与根据ＩＤ３算法构建出的决策树相比具有一定优势．

关键词：启发式算法；重要度；噪声ＩＤ３；

（）中图分类号：ＴＰ３９　　　文献标志码：Ａ　　　文章编号：１０００－１５６５２０１１０１－０１０３－０４　

ＡＣｏｍａｒａｔｉｖｅｏｎＮｏｉｓｅＲｅｓｉｓｔａｎｃｅｆｏｒＴｗｏ　　　　　　ｐ

ＨｅｕｒｉｓｔｉｃＡｌｏｒｉｔｈｍｓｉｎＤｅｃｉｓｉｏｎＴｒｅｅＧｅｎｅｒａｔｉｏｎ　　　　　ｇ

１２２

，ＷＡＺＨＯＵＮｉｎＸＩＥＢｏｕｎＮＧＴａｏ　　－　ｇ，ｊ

（，Ｈ，；１．ＰｒｅｓｉｄｅｎｔＯｆｆｉｃｅｅｂｅｉＵｎｉｖｅｒｓｉｔＢａｏｄｉｎ０７１００２，Ｃｈｉｎａ　　ｙｇ　

，Ｈ，）２．ＤｅａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｕｔｅｒＳｃｉｅｎｃｅｅｂｅｉＵｎｉｖｅｒｓｉｔＢａｏｄｉｎ０７１００２，Ｃｈｉｎａ　　　　　　ｐｐｙｇ　

：ＡｂｓｔｒａｃｔＴｈｅｃａａｂｉｌｉｔｏｆｎｏｉｓｅｃａｎｃｅｌｌｉｎｉｎｄｅｃｉｓｉｏｎｔｒｅｅｉｓｔｈｅｃｒｉｔｉｃａｌｆａｃｔｏｒｉｎｈｅｕｒｉｓｔｉｃａｌｏｒｉｔｈｍｓ　　　　　　　　　　　　ｐｙｇｇ　　

，ｄｅｓｉｎ．ＴｈｅｃｏｍａｒｉｓｏｎｂｅｔｗｅｅｎＩＤ３ａｎｄＤｏＩｔｈｅｔｗｏｈｅｕｒｉｓｔｉｃａｌｏｒｉｔｈｍｓｆｏｒｔｈｅｃａａｃｉｔｏｆｒｅｓｉｓｔｉｎ　　　　　　　　　　　ｇｐｇｐｙｇ　ｎｏｉｓｅｗａｓｉｎｖｅｓｔｉａｔｅｄ．Ｔｈｅｉｎｖｅｓｔｉａｔｉｏｎｗａｓａｉｍｉｎａｔｓｏｍｅｅｘｅｒｉｍｅｎｔａｌｌｃｏｍａｒａｔｉｖｅａｄｖａｎｔａｉｖｉｎ　　　　　　　　－ｇｇｇｐｙｐｇｇ　　　ｅｓｏｎｔｈｅｒｏｂｕｓｔｎｅｓｓｆｏｒｔｈｅｔｗｏｈｅｕｒｉｓｔｉｃｓ．　　　　　　　ｇ

：；Ｋｅｗｏｒｄｓｈｅｕｒｉｓｔｉｃａｌｏｒｉｔｈｍ；ｄｅｒｅｅｏｆｉｍｏｒｔａｎｃｅＩＤ３；ｎｏｉｓｅｄａｔａ　　　　ｇｇｐｙ　

决策树算法是机器学习领域中的一种解决分类问题的有效算法，被广泛地应用于自动知识获取领域．它通过对已知事例进行归纳学习，将学习结果以决策树的形式描述．该算法使用启发式推理算法，从中抽取出分类规则，达到学习的目的，启发式推理算法不同则分类结果也不相同．目前，已经有多种决策树的启发式算

［］

法，其中以１这是一种基于信息增益的启发式算法，其主要特征是９８６年Ｑｕｉｎｌａｎ提出的ＩＤ３算法１为代表，

在树的结点上使用具有最大信息增益的候选属性作为扩展属性来构建决策树，然后将树中从根结点到叶结点的每一条路径转化为一条规则，从中获得所需的分类知识．

然而，在现有的决策树构造算法中所使用的事例集一般都没有考虑到噪声的因素．现实世界中，数据不可能是完美的，存在很多缺陷，如某些属性字段上含缺失值，数据不完整，数据不准确，含有噪声等．因此，找到一种启发式策略，使根据这种启发式策略构造的决策树具有较好的健壮性来抵抗噪声的干扰具有重要的意义．

２０１０－０５－３０　收稿日期：

）科技部国际科技合作项目（２００８ＤＦＲ１０５３０　基金项目：

，周宁（男，河北保定人，河北大学讲师，主要从事机器学习与人工智能方向研究．１９８０－）　第一作者：

：Ｅ－ｍａｉｌｚｈｏｕｎｉｎｂｕ．ｅｄｕ．ｃｎ＠ｈｇ