浅谈ID3决策树算法与改进算法对比.pdfVIP

浅谈ID3 决策树算法与改进算法对比 摘要：ID3 算法作为最有影响的一种决策树算法应用于各个领域，其优点鲜 明，但缺点也较为突出，很多学者对其进行了改进，达到了一定效果。本文在简 单介绍该算法和其优缺点后，对现今的一些改进算法进行了总结分析，最后提出 继续改进ID3 算法是必要的。 关键字：ID3 算法，C4.5 算法，IBLE 算法，灰色关联度，粗糙集 ID3 Decision Tree Algorithm and Imoroved Algorithm Comparison Abstract:ID3 algorithm is the most significative decision tree algorithm,and it applied to many areas.ID3 algorithm has distinct advantages,but its disadvantages are prominent also.Many scholars improved it and achieved some good results.The article firstly introduced the algorithm and its good and bad points,secondly summarized and analysised some last improved algorithm,finally broght up that it’s necessary to improve ID3 algorithm futher. Key words:ID3 algorithm, C4.5 algorithm,IBLE algorithm,grey relational degeree,rough set 0 引言 决策树分类方法是一种有效的数据挖掘方法，Quinlan 提出的ID3 算法是最 有影响的一种决策树生成算法，它已经广泛的应用于各种领域。该算法将信息论 引入到了决策树算法中，把信息熵作为选择测试属性的标准，对训练实例集进行 分类并构造决策树，其关键是选择何种属性作为依据来对整个实例空间进行划 分。该算法优点多，但是缺点也较为突出。目前针对其各个方面的缺点，学者们 提出了各种改进方法，达到了一定的改进效果，对其进一步应用起到了一定的推 动作用。 1 ID3 决策树算法简介 ID3 算法采用自顶向下的方法来学习。采用信息增益量 （互信息）作为属性 选取的标准。设当前训练样本集： ，有s个样本；A 是训练样本集的一个描述 S 属性，取值为A ，A ，…，A ；C 为决策分类属性，具有m个不同值，定义了 1 2 n j m个不同类C （j 1，2 ，…，m ），c 是 当中类C 的样本数。则信息增益 S j j j （互信息）可表示如下： m 信息增益gainA I EA ，其中信息熵I pC log pC ，条件熵 j 2 j j 1 n n m