ID3算法的改进

摘要：ID3算法是决策树学习里面很重要的算法之一。ID3算法采用自顶向下贪婪搜索遍历可能的决策树空间[1]54，由于该算法存在两个大的缺点：一、属性取值偏向；二、抛弃较小数据。针对这两个缺点本文给出了两个改进方法：一、增加属性权值；二：增加信息增益度。通过实验结果表明使用这两种方法的综合应用的结果比没有使用这两种方法的效果更好。

关键词：决策树 ID3 算法 属性权值 信息增益

1 引言

决策树学习是应用最广的归纳推理算法之一。决策树的结果是实例属性值的合取的析取式的结果。合取是从每条树根到树叶的属性测试的结果，对所有合取进行析取的结果就是整个决策树的结果。因为在决策树学习中ID3算法很有用，所以很多人都进行了研究和探索。决策树学习起源于概念学习系统，最早是由Quinlan[2]81提出来的， 通过应用分治策略，对一个训练集进行学习最后生成一棵决策树。当训练数据集变大的时候ID3算法由于之前的决策树已经确定，所以再次加入其它样本的时候就要重新进行树的构建，就会花费较多的时间，这会使算法的效率变得很低。由于ID3算法以最高信息增益作为选择属性的标准[1]54，这就会导致最后的结果偏向于选取属性取值更多的那个属性。针对这两个问题本文采取了从两个方面进行改进：一、属性权值；二、信息增益度。从这两个方面进行改进的好处就是可以提高决策树的准确性和决策树的实时性，减少了决策树依赖于取值较多的属性，通过实验验证这种改进的方法比以前的方法更有效率。

2 ID3 算法的原理

ID3 是基于信息熵的决策树分类算法，其核心思想是在决策树中各层分枝节点上选择属性， 用信息增益作为属性选择标准，使得在每一非叶子节点进行测试时，能获得关于被测试例子最大的类别信息，使用该属性将样本集划分成子集后，系统的信息熵值最小[3]3073。

2.1 ID3算法思想

现假设一个训练集仅有两种分类：正例和反例，并且所有的属性都是离散型数据[4]63。在生成决策树的过程中，通过计算每个结点的信息增益来确定它们的位置，根据信息增益的高低来对每个属性进行排列，树的每个结点的确定都是从信息增益的从高到低的顺序来进行排列。

2.2 ID3算法的理论基础如下

1948 年，香农提出了信息论[5]57。其中对信息量和熵的定义[5]57为：

（1）

（2）

2.2.1 数据集S划分前的熵

设数据集S有 ， C共有n + l个属性。其中分类属性C有m个不同的离散属性值 。即数据集S中的记录要分成m个类别。设数据集S中全部的记录数为s，分类属性值为 的记录数分别为 。那么划分之前，数据集S的总熵为：

（2.1） 其中Pi是任意一个记录属于类别的概率，用Si/S估计。

2.2.2 数据集S划分后的熵

一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低[11]。其中，属性A有v个值，并且把S分割成了v个不同的子集 。设子集Sj中全部的记录数为Sj，其中分类属性值为C1，C2，…Cm的记录数分别为S1j，S2j，…Svj。子集Sij的熵为：

（2.2）

其中Pij是Sj中任意一个记录属于类别Ci的概率，用Sij/Sj估计。S的总熵是v个子集的熵的加权平均。数据集S划分后的熵为：

2.2.3 数据集S划分前与划分后的熵差

信息增益：表示系统由于分类获得的信息量。由系统熵的减少值定量描述。数据集S用属性A划分后的信息增益为数据集S划分前后的熵差：

（2. 4）

在结点划分方面，选择属性应该具有最高信息增益。熵刻画了任意样例集的纯度，就可以使用熵减少量最大的作为划分方案中最好的那张方法，所以就把信息增益最大的属性作为当前结点。

3 ID3算法改进

3.1属性加权

从上面的算法我们可以看出ID3算法存在两个大的缺点：一、属性取值偏向；二、只对较小数据有效。针对以上两个缺点本文进行了下面的改进。通过对2.2.3中的公式（2. 4）中的属性进行加权，以此来增加属性的权值，减小不重要的属性的权值，通过增加权值的方法使得最后生成的决策树的结点的时候数量少的数据元组也会得到重视，而属性值较多但是并不重要的属性就会得不到重视，这样的结果就会使得决策树不会对取值较多的属性存在依赖，从根本上减少由于数据多而属性并不重要但是得到重视，数据少而属性重要的属性得不到重视的情况。经过加权，原式（2. 4）将修改为下式：

其中 是属性j的加权后的值，从上面的公式我们可以看出重要性高的属性，他的权值参数的取值就会越大，但是不管他有多大最终都要满足 。

3.2信息增益度

在公式（3. 1）改进的基础之上，增加信息增益度的概念。将（3. 1）变为下式：

其中，N为属性A的取值个数，这样计算之后就原来的信息增益度就会被替换掉。理论上来说，这种方法通过引入分支数N，在ID3算法的取值存在偏向缺陷的基础上得到了克服。

4 实例验证

下表给出了测试数据样本集，其中属于Y的实例有9个，属于N的实例有6个。

此时可以看出湿度的信息增益最大，而风的信息增益最小。所以在构建决策树的时候，湿度就会作为第一个节点，风最为最后一个结点，最后的决策树形如图1所示。

图 1改进前决策树

现假设各属性的取值的重要程度依次为：温度、风、湿度，那么对他们的权值的赋值为为0. 2、0. 4、0. 4，结合公式（3. 1）与公式（3. 2） ，得到新的决策树如图2所示。

图 2改进后决策树

通过图1和图2的比较，可以发现图1的决策树分支比图2多了很多，而且结构很稀疏，在进行树的搜索的时候扫描次数也更多，所以图2的决策树的算法相对于图1的算法来说更实用， 用200个样本进行测试发现，没有改进之前的ID3算法的错误率为9.3%，改进后的ID3算法的错误率为5.7%，由此我们可以看出在ID3算法的基础上给通过增加属性权值和改变信息增益这两个方面的改进能使得决策树更加符合实际情况，同时也达到了我们的预期目标。

5 结束语

通过对ID3算法中所存在的属性取值偏向和抛弃较小数据的缺点进行改进，即在ID3算法的原有的基础上增加属性权值和信息增益度，一定程度上克服了上面的两个缺点，这样在可以加快决策树的生长的同时，还可以使树的结构性更好，这就提高了ID3算法的效率，并且结果表明，改进后的算法比传统算法更好，更加实用。

参考文献：

[1]张保华.改进的ID3算法[J].中国校外教育，2009（8）：49-54.

[2]J.R.QUINLAN.Induction of Decision Trees[J].Kluwer Academic Publishers，1986，1（1）：81-106.

[3]王小巍，蒋玉明.决策树ID3算法的分析与改进[J].计算机工程与设计，2011（9）：3069-3072+3076.

[4]段玉春，朱晓艳，孙玉强.一种改进的ID3算法[J].南阳师范学院学报（社会科学版），2006（9）：63-65.

[5]王勇.香农信息定义分析与改进[J].情报杂志，2008（8）：57-60.