决策树算法分析与改进

张永昭　岳晟　刘晓楠

摘 要 ID3、C4.5、CART是三种已经研究发展很多年的经典算法，是从事数据挖掘研究工作基础模板。三种决策树模型应用广泛，原理简明，各有所长，但缺点同样明显。经过深入的学习研究，团队对三种算法的特点及改进进行了汇总，为进一步的研究做了总结性分析；并运用分析成果对ID3算法进行了改进。

关键词 数据挖掘；决策树算法；特点；改进；汇总

引言：

近年来，决策树方法在机器学习、知识发现等领域得到了广泛应用。数据挖掘作为一种发现大量数据中潜在信息的数据分析方法和技术，已经成为各界关注的热点。其中，决策树以其出色的数据分析效率、直观易懂等特点，倍受青睐。构造决策树有多种算法，国际上最早的、具有影响力的决策树是由Quinlan于1986年提出的ID3算法[1]，是基于信息熵的决策树分类算法。ID3算法采用信息熵作为属性选择标准，可这个标准易偏向于取值较多的候选属性。

一、ID3算法优化

1.改进思路

针对ID3算法的缺点④，即信息增益的计算依赖于特征数目较多的特征，而属性取值最多的属性并不一定最优，这会导致结果与实际误差较大。基于上述对ID3算法改进方案的分析，本文提出以下改进思路：

（1）提出子属性信息熵的概念。假设所有属性集合为{A1，A2，…，An}，对于属性Ai有子属性{Ai1，Ai2， …， Aim}。定义Aij的子属性信息熵为。

（2）引入属性优先[18]的概念。不同的属性对决策的影响程度不同，这种影响程度可以在辅助知识的的基础上事先加以假设，给每个属性赋予一个权值{w1，w2，…，wn}，通过权值，弱化非重要属性，强化重要属性。……