决策树算法分析与改进

张永昭　岳晟　刘晓楠

摘 要 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}，通过权值，弱化非重要属性，强化重要属性。

（3）引入属性修正信息熵的概念，目的是弱化非重要多值属性对信息增益的影响。假设所有属性集合为{A1，A2，…，An}，每个属性发生概率分别是{P1，P2，…，Pn}，对于属性Ai每个子属性发生的概率为{Pi1，Pi2，…，Pim}。定义属性Ai的属性修正信息熵为。

而entropy（Ai）采用ID3中的算法计算。

2.算法步骤

（1）对当前例子集合，计算各个属性的修正信息熵。

（2）选择修正信息熵最小的属性Ai作为根节点。

（3）把在Ai处取值相同的例子归于同一子集，Ai取几个值就得几个子集。

（4）依次对每种取值情况下的子集，递归调用建树算法，即返回（1）。

（5）若子集只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处。

二、实例分析

针对表1中的数据，用ID3算法求解得图1所示决策树。

由表一，对于该例子集合的属性集合为{天气，温度，湿度，风} 。对于“天气”属性有子属性{多云，雨，晴}，对于“温度”属性有子属性{高，低，适中}，对于“湿度”属性有子属性{正常，大}，对于“风”属性有子属性{无风，中风，大风}。

由经验我们假定“天气”的优先权值为0.95，“风”的优先权值为0.35，湿度和温度的优先权值为0。

计算“天气”的子属性的子属性信息熵：

由ID3算法可知：

由5.1中属性修正信息熵的定义可得：

同理，，。所以选取“湿度”为根节点。接下来将例子集分成两个子集：

接下来重复上面步骤，可得决策树如图2所示。

通过比较，可以得到以下结论：

（1）优化算法所生成是二叉树，而ID3算法所生成的是多叉树，简化了决策问题处理的复杂度。

（2）引入子属性信息熵、优先权、属性修正信息熵的概念，从本例来看，根节点选择了湿度而没有选择属性值最多的天气，所以本优化算法确实能克服传统ID3算法的多值偏向性。

三、结束语

数据挖掘技术是当前数据库和人工智能领域研究的热点课题，分类是数据挖掘的一种非常重要的任务。决而策树算法是一种非常重要的数据挖掘分类算法。本文主要对三种算法的特点及改进进行了汇总。对于ID3算法，目前的改进方向主要集中在解决ID3偏向于选择取值较多的属性的不足、解决不能处理连续值的属性、解决易受噪声干扰和优化储存这四个方面。

本文对这三种决策树算法当前研究情况进行了总结分析，并运用分析结果对经典ID3算法提出了改进方法。通过进行实例分析，了解和熟悉实际应用上的差别，为对决策树算法进一步的研究作准备。