决策树ID3算法研究

杜威铭　冉羽

【摘 要】用于分类的数据挖掘技术的方法有很多，在这些方法中决策树凭借其易理解、效率高等优点而占有重要地位。ID3 算法是决策树构造方法中最为常用的实现方法，它在数据分类和预测领域得到广泛应用。本文重点总结了决策树方法中的ID3算法的研究现状，在详细介绍ID3算法原理、算法性能的基础上，总结了ID3算法以及给出了ID3算法的改进算法。

【关键词】数据挖掘；ID3算法；ID3优化算法；决策树

中图分类号： TP181 文献标识码： A 文章编号： 2095-2457（2018）11-0145-002

DOI：10.19694/j.cnki.issn2095-2457.2018.11.062

【Abstract】There are many methods used to categorize data mining techniques， in which decision trees play an important role by virtue of their ease of understanding and efficiency. ID3 algorithm is the most commonly used method in decision tree construction method， which is widely used in the field of data classification and prediction. This paper focuses on the research status of ID3 algorithm in decision tree method. Based on the detailed introduction of ID3 algorithm principle， application example and algorithm performance， this paper summarizes the ID3 algorithm and the improved algorithm of ID3 algorithm.

【Key words】Data mining； ID3 algorithm； ID3 optimization algorithm； Decision tree

0 绪论

随着软硬件技术的发展，数据库技术也经历了多次演变，在信息数据量剧增的环境下，对于海量的数据以及数据背后的隐藏信息，我们期望通过更高层次的方法，寻找出模型与规则，帮助我们利用数据进行分析与决策。因此，数据挖掘技术应运而生并越发受人重视，高校、研究所與公司在该方面的研究也做了很大的投入。决策树[1]方法作为数据挖掘中的一种重要的方法，也受到了诸多关注。下面将介绍决策树方法中的ID3[2]（Interactive Dichotomic Version 3）算法。

1 ID3算法研究

1.1 ID3算法简介

J·Ross Quinlan等人在1986年提出ID3算法。其核心是“信息熵”，在创建决策树的过程中，依次查询样本集合中的每个属性，选取出具有最大信息增益值的属性，将该属性作为测试属性与划分标准。通过该标准将原始数据集合划分成多个更纯的子集，并在每个子集中重复这个过程，直到分支子集中的所有样本无法继续分割，即样例属性属于同一类别，此时一棵决策树便创建完成。

1.2 ID3算法原理

ID3算法原理包含了信息论[3]中的信息熵和信息增益。信息熵作为属性类别的不纯性度量，熵值越高属性的纯度越低，反之越高。信息增益通过信息熵相减求得，它反映了该属性特征在总体数据集中的重要程度。信息增益和信息熵分别有以下数学定义[4]：

1.3 ID3算法描述

下面给出ID3算法的伪代码描述：

输入：离散型决策属性集合D和样本集合S。

输出：函数Create_Tree（D ， S）返回一棵决策树。

Function Create_Tree（D ， S）

Begin

（1）创建结点N；

（2）if S都在同一个类C then

（3）return N作为叶子结点，记为类C；

（4）if D=NULL then

（5）return N为叶子结点，记为S中最普通的类；

（6）选择D中拥有最大信息增益的属性A；

（7）标记结点N为A；

（8）for each A中的未知值value

（9）从结点N长出一个条件为A=value的分枝；

（10）设Bvalue是S中A=value的样本子集；

（11）if Bvalue=NULL then

（12）添加一个叶子结点，记为S中最普通的类；

（13）else 添加一个从Create_Tree（Bvalue，D–{A}）返回的结点。

End

1.4 ID3算法应用实例

以表1数据为训练样本集，介绍ID3算法如何生成一棵决策树。

（1）信息熵的计算

用p表示感冒，n表示未感冒，初始训练样本感冒人数为12，未感冒人数为4，因此可求得分类前训练集的信息熵：

H（X）=I（p，n）=-（12/16）log2（12/16）-（4/16）log2（4/16）=0.8113bits

（2）条件熵的计算

选择属性体温作为划分属性，体温的取值集为{正常，高，很高}，其中正常体温人数为5，高体温人数为6，很高体温人数为5，则有：

体温正常：p1=3，n1=2，I（p1，n1）=0.9710bits

体温高：p2=3，n2=2，I（p2，n2）=0.6500bit

体温很高：p3=3，n3=2，I（p3，n3）=0.7219bits

此时可以算出用体温属性划分训练集后熵的期望值为：

E（体温）=（5/16）I（p1，n1）+（6/16）I（p2，n2）+（5/16）I（p3，n3）=0.7728bits

（3）信息增益的计算

Gain（体温）=0.8113-E（体温）=0.0385bits，同理可求得：

Gain（流鼻涕）=0.5117bits

Gain（肌肉疼）=0.0038bits

Gain（头疼）=0.0359bits

选择具有最大信息增益的流鼻涕属性作为根节点进行决策树的创建，引生出流鼻涕和不流鼻涕两个分枝，在流鼻涕分枝，求得新划分的信息增益：

Gain（流鼻涕，体温）=0.1992bits

Gain（流鼻涕，肌肉疼）=0.0924bits

Gain（流鼻涕，头疼）=0.1379bits

选体温作为流鼻涕分枝的结点，在不流鼻涕分枝，求得新划分的信息增益：

Gain（不流鼻涕，体温）=0.0157bits

Gain（不流鼻涕，肌肉疼）=0.0157bits

Gain（不流鼻涕，头疼）=0.0032bits

我们发现存在相同的信息增益，则选择分枝少的属性作为不流鼻涕分枝的结点，即肌肉疼属性。之后重复上诉步骤，完成下图1决策树的创建。

1.5 ID3算法优缺点

通过ID3算法的伪代码描述与实际使用，我们可以发现ID3算法是一种采用自顶向下、贪婪策略的算法。其优势主要有以下3点：①自顶向下的搜索方式降低了搜索次数，提升了分类速度。②ID3算法原理清晰，算法思路简单易懂，易于实现。③由于决策树在创建的过程中都使用目前的训练样本，而不是根据独立的训练样本递增的做出判断，在很大程度上降低了对个别训练样本错误的敏感性[5]。ID3算法不足主要有以下四点：①ID3算法对噪声数据相对敏感。②ID3算法循环调用过程中会产生大量的对数运算，随着样本集合、属性以及属性取值个数的增加，对数运算次数将会大大增加，从而降低了ID3算法的运算效率，产生了极大的时间开销。③ID3算法在建树过程中不进行回溯导致生成的决策树节点只是局部最优的，相对于全局，往往不是我们所期待的结果，即如多值偏向所得结果并不总是最优结果。④ID3只能分类离散型数据，对于非离散型数据需要经过预处理才能使用。

2 ID3改进算法

由于ID3算法的不足与局限性，J·Ross Quinlan于1993年对原算法进行了改进并提出了C4.5算法。该算法将信息增益率作为划分标准，解决了ID3算法无法处理连续特征属性的问题，同时降低了计算的复杂度，提升了分类效率。研究者还提出了如下改进算法：基于分类矩阵的ID3算法改进、基于粗糙集的ID3算法改进、基于粒计算的ID3算法改进等、基于相关系数的决策树优化算法、基于神经网络的分类改进算法、基于朴素贝叶斯与ID3算法的决策树分类、粗糙模糊决策树归纳算法等[6]。

3 总结与展望

随着决策树分类法再次受到人们重视，并被广泛的研究和使用。作为决策树中经典算法，ID3 算法使用信息增益作为分割标准，凭借其分类速度快、实现方式简单等优点，成为了具有适用与研究价值的示例学习算法与知识获取的有效工具。目前，ID3应用领域广，如医学中的病症分类预测和基因与高分子序列分析、商业活动中的市场分析和人力资源管理、教育行业中的成绩分析、高校管理等。同时，研究者们也在不断对ID3算法进行优化与改进，提升了分类效率，获得了更好的分类结果。在当前大数据技术背景下，会有更多ID3改进算法被提出，ID3算法也会在更多的领域得到应用。

【参考文献】

[1]Jiawei Han，Micheline Kamber. Datamining Concepts and Techniques 范明，孟小峰，譯.数据挖掘概念与技术，机械工业出版社，2001.

[2]Quinlan J R. Induction of decision trees" Machine Learning[J]. in Data：Goals and General Description of the IN L.EN System." in， 1986：257--264.

[3]陈文伟.数据仓库与数据挖掘教程.清华大学出版社， 2006-8.

[4]杨洋.决策树ID3算法及其改进[J].软件导刊，2016，15（08）：46-48.

[5]李华.基于决策树ID3算法的改进研究[D].电子科技大学，2009.

[6]杨霖，周军，梅红岩，杜晶鑫.ID3改进算法研究[J].软件导刊，2017，16（08）：21-24.