ID3算法原理及应用

1、ID3算法的应用研究摘要决策树算法是数据挖掘领域的核心分类算法之一，其中ID3算法是最为经典的决 策树算法。ID3算法理论清晰、使用简单、学习能力较强，且构造的决策树平均深 度较小，分类速度较夬特别适合处理大规模的学习问题，目前已得到广泛应用。本 文对ID3算法进行了详细的描述,介绍了其算法的基本原理、开展近况、及其具 体运用。引言分类技术是一种根据输入数据集建立分类模型的系统方法。分类技术一般是用一 种学习算法确定分类模型，该模型可以很好地拟合输入数据中类标号和属性集之 间的联系。依据学习算法可以建立能够准确地预测未知样本类标号的模型。分类 方法的实例包括：决策树分类法、基于规那么的分类法、

2、神经网络、支持向量级、 朴素贝叶斯分类方法等。相对于其他几种算法而言，ID3算法理论清晰，算法简 单，是很有实用价值的实例学习算法，计算时间是例子个数、特征属性个数、节 点个数属性之积的线性函数，总预测准确率较高，针对属性选择问题，是决策树 学习方法中最具影响和最为典型的算法。因此本文将详细介绍该算法。算法基本原理在ID3决策树归纳方法中，通常是使用信息增益方法来帮助确定生成每个节点时 所应采用的合适属性。这样就可以选择具有最高信息增益（燧减少的程度最大） 的属性最为当前节点的测试属性，以便对之后划分的训练样本子集进行分类所需 要的信息最小，也就是说，利用该属性进行当前（节点所含）样本集合划分

3、，将 会使得所产生的样本子集中的“不同类别的混合程度”降为最低。因此，采用这 样一种信息论方法将有效减少对象分来所需要的次数，从而确保所产生的决策树 最为简单。设E = Fl XF2 X-XFn是n维有穷向量空间，其中鸟是有穷离散符号集,E中的元素 = 匕，匕叫做例子,其中匕，j = l,2,，n。设PE和NE是E的F两个例子集，分别叫正例集和反例集。假设向量空间E中的正例集PE和反例集NE的大小分别为p和n ,ID3基于以下 两个假设：（1）在向量空间E上的一棵正确决策树，对任意例子的分类概率同E 中的正、反例的概率一致；（2） 一棵决策树能对一例子做出正确类别判断所需的信息量为：I (p,

4、 n) =-log2log2-p+n p+n p+n如果以属性A作为决策树的根，A具有v个值（匕，%，V，它将E分为v个子 集（片,2,，纥），假设中含有Pi个正例和4个反例，子集用的信息焙为I (Pi, 4),以属性A为根分类后的信息燧为:(%) = Z=1因此，以A为根的信息增益是Gain (A)=I (p, n) - E(A) 。 ID3选择使Gain (A)最大(即E(A)最小)的属性作为根结点。对4的不同的取值对应的E的v个子集耳递归调用上述过程，生成4的子结点，鸟，82,，与。ID3的基本原理是基于两类分类问题，但很容易扩展到多类。设样本集S共 有C类样本，每类样本数为pi , (

5、 i=1 , 2 , 3 ,c)。假设以属性A作为决策树 的根，A具有V个值匕，匕，匕，它将E分成V个子集四,生，纥，假设 片中含有j类样本的个数为4,j = 1,2,c那么，子集与的信息量是1(g)。*log 以A为根分类的信息烯为：选择属性4使E(A)最小,信息增益也将增大。理想的决策树分成3种：(1)叶节点数最小，(2)叶节点深度最小；(3)叶节点 数量最少且叶子结点深度最小。决策树的好坏,不仅影响分类的效率,而且还影响 分类的准确率。人们为了寻求较优的解，不得不寻求各种启发式的方法。有的采 用基于属性相关性的启发式函数;有的对生成的决策树进行剪枝处理;有的那么扩 充决策树,形成决策图。

6、如今普遍采用的是优化算法,基本思想:首先用ID3选择属性F1,建立树T1,左、 右子树的属性分别为F2, F3,再以F2, F3为根,重建树T2, T3;较Tl, T2, T3的结点个 数,选择结点最少的树。对于选择定树的儿子结点采用同样的方法递归建树。尽 管作者用一个实验证明能建立理想的决策树，但算法有较大的弱点：时间开销太 大,因为每选择一个新的属性,算法都需要建立3棵决策树,从中选优。算法的开展近况ID3算法的缺点：可能会收敛于局部最优解而丧失全局最优解，因为它是一种自 顶向下贪心算法，逐个地考虑训练例，而不能使用新例步进式地改进决策树，同 时它是一种单一变量决策树算法，表达复杂概念时非

7、常困难；信息增益的方法往 往偏向于选择取值较多的属性；连续性的字段比拟难预测；当类别太多时，错误 可能就会增加的比拟快；只适合解决属性值为离散变量的问题；抗噪性差，比例 较难控制。后来又出现了 ID3算法的增量版本ID4算法和ID5算法，它们相对于小的数据集 很有效率。ID4学习算法：在每个可能的决策树结点创造一系列表，每个表由全 部未检测属性值和每个值的正例和反例数组构成，当处理一个新例时，每个属性 值的正例和反例递增计量，也就是递增概念归纳。ID4算法优点：选择性的利用 了原有规那么集和决策表，使树结构规那么，搜索和匹配速度很快。但它规那么前件集 中，样本正确识别率低，对不确定性处理能力差

8、。ID5算法抛弃了旧的检测属性 下面的子树，从下面选出检测属性形成树。它具有学习能力强，保证生成和ID3 相同的判定树，使用树结构、搜索匹配速度快；但上拉复杂度高，判定生成树代 价高，规那么前件集中，样本识别率低，对不确定性记录处理能力差。由于ID3算 法在实际应用中存在一些问题，于是Quilan提出了 C4.5算法以及后来的C5.0算 法，严格上说C4.5只能是ID3的一个改进算法。C4.5算法继承了 ID3算法的优点, 并在以下几方面对ID3算法进行了改进：用信息增益率来选择属性，克服了用信 息增益选择属性时偏向选择取值多的属性的缺乏；在树构造过程中进行剪枝；能 够完成对连续属性的离散化处

9、理；能够对不完整数据进行处理。但C4.5在构造 树的过程中，需要对数据集进行屡次的顺序扫描和排序，因而导致算法的低效。 此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时 程序无法运行。此外，很多计算机的爱好者也对ID3算法和C4.5算法提出了各种各样的改进方 法，在此本文就不一一列举了。算法的具体应用实例由于ID3算法的简洁和强大之处，它已经广泛的应用在数据挖掘和人工智能 中，在这里本文就通过考察某校学生的学习状况为例，来展示ID3算法的一个实 际应用。此例假定要按某校学生学习成绩好坏这个概念对一个集合进行分类,该 集合中用来描述学生的属性有性格、父母教育程度和性别。

10、性格的取值为外向、 内向。父母教育程度取值为良好、中等和差。性别的取值为男生、女生。例子集 中共有12名学生,如表2所示。在类别一栏,将正例即“学习成绩好”的学生用“好” 标出，反例即“学生成绩差”的学生用“差”标出。表2某学校学生的例子集这些例子一开始全部包含在根结点中，为了找出当前的最正确划分属性,先须 根据信息论中的公式计算训练实例集Es的皤值。那么根节点的燧值为：性格父母教育程度性别类别l/l、61c661c61Entropy(Es) = - - log 2 - - - log 2 = l下面分别计算例子集中各个属性的信息赢取值。对属性“性格”来说，分外 向和内向两个分支。当V = “

11、外向”时，有4名“外向”小学生是“学习成绩好” 的，有2名“外向”小学生是“学习成绩差”的。因此， TOC o 1-5 h z 4422Entropy IE,性格,外向）二7 log 2 - 不 log 2 = 0.9183当v = 内向时，有2名“内向”小学生是“学习成绩好”的，有4名“内 向”小学生是“学习成绩差”的。因此，4422Entropy（EM 内向）=一7log2 -log2 - = 0.9183o2+4 o2+4所以根据“性格”属性来进行例子集分类的信息赢取值为：Gain （Es,性格）=Entropy （Es） -Entropy （Esv,格）二1-（,*0.9183+,*0

12、.9183 户 0.0817同理，对“父母教育程度”来说来ain（Es,父母教育程度）=0.4591 ;对“性别”来说:Gain（ Es,性别）=0。因为Gain （ Es，性别） Gain （ Es，性格） Gain （ Es ,父母教育程度） 可以看出以“父母教育程度”这个属性进行例子集分类的信息赢取值最大，于是 “父母教育程度”就被选为用于划分的属性,得到如以下图所示的决策树。父母教育程度良良良 , , , 向向向向向向向 / 外内一 良 / Y L/好好修 女男男女fE tE 匕 IE4- W2 4- 4-女男男女 fa1 匚 , , , , 中中中中差,好 差 差J外向，差, 内向，

13、差, Q外向，差,女女男男按“父母教育程度”划分后的决策树现在必须根据所提供的信息进一步分析“父母教育程度”为“中”或“差” 的小学生的“学习成绩好坏”，因此必须对“中”和“差”两个分支的实例组成 的例子集（共8个例子）重复上述计算过程。这里简化计算过程,算出:Gain（Es, 性格）=0.3113 和Gain（Es,性别）=0.2045。因为Gain （ Es，性别） Gain （ Es，性格），所以用属性“性格”作第二 步划分,于是得到如以下图所示的决策树。父母教育程度好 差好 差中中中请 - 内 N女男男女差生生 女男向向Lr k 夕夕良良良良中中向向按“性格”作第二次划分后的决策树现在只有“父母教育程度”为“中”和“差”的“外向”小学生还没有明确 类别，它们要用属性“性别”来进一步划分。最终得到的决策树如以下图所示。, , , , 向向向向 丙外内困良良良良女男男女中中生生 女男父母教育程度向性别一男生号一男生鳍外向，中，男生：好外向，中，女生：差物卜向，差，男生：差外向，差，女生：好最终得到的决策树IF父母教育程度=“良”THEN学习成绩=“好”IF父母教育程度=中AND性格二“内向THEN学习成绩=“差”IF父母教育程度=“差” AND性格二“内向THEN学习成绩=“差”IF父母教育程度二“中 AND性格二“外向 AND性别=“女生”THEN学习