ID3算法原理及应用

ID3算法的应用研究摘要决策树算法是数据挖掘领域的核心分类算法之一,其中ID3算法是最为经典的决策树算法。ID3算法理论清晰、使用简单、学习能力较强,且构造的决策树平均深度较小,分类速度较快,特别适合处理大规模的学习问题,目前已得到广泛应用。本文对ID3算法进行了详细的描述,介绍了其算法的基本原理、发展近况、及其具体运用。引言分类技术是一种根据输入数据集建立分类模型的系统方法。分类技术一般是用一种学习算法确定分类模型，该模型可以很好地拟合输入数据中类标号和属性集之间的联系。依据学习算法可以建立能够准确地预测未知样本类标号的模型。分类方法的实例包括：决策树分类法、基于规则的分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。相对于其他几种算法而言，ID3算法理论清晰，算法简单，是很有实用价值的实例学习算法，计算时间是例子个数、特征属性个数、节点个数属性之积的线性函数，总预测准确率较高，针对属性选择问题，是决策树学习方法中最具影响和最为典型的算法。因此本文将详细介绍该算法。算法基本原理在ID3决策树归纳方法中，通常是使用信息增益方法来帮助确定生成每个节点时所应采用的合适属性。这样就可以选择具有最高信息增益（熵减少的程度最大）的属性最为当前节点的测试属性，以便对之后划分的训练样本子集进行分类所需要的信息最小，也就是说，利用该属性进行当前（节点所含）样本集合划分，将会使得所产生的样本子集中的“不同类别的混合程度”降为最低。因此，采用这样一种信息论方法将有效减少对象分来所需要的次数，从而确保所产生的决策树最为简单。设E=F1×F2×…×Fn是n维有穷向量空间,其中jF是有穷离散符号集,E中的元素e=1V,2V,…,nV叫做例子,其中jV∈jF,j=1,2,…,n。设PE和NE是E的F两个例子集,分别叫正例集和反例集。假设向量空间E中的正例集PE和反例集NE的大小分别为p和n,ID3基于下列两个假设:(1)在向量空间E上的一棵正确决策树,对任意例子的分类概率同E中的正、反例的概率一致;(2)一棵决策树能对一例子做出正确类别判断所需的信息量为:I（p,n）=log2log2ppnpnpnpn如果以属性A作为决策树的根,A具有v个值(1V,2V,…,nV),它将E分为v个子集(1E,2E,…,vE),假设iE中含有Pi个正例和in个反例,子集iE的信息熵为I(Pi,in),以属性A为根分类后的信息熵为：1()()viiiiipnEAIpnpn因此,以A为根的信息增益是Gain(A)=I(p,n)-E(A)。ID3选择使Gain(A)最大(即E(A)最小)的属性作为根结点。对的不同的取值对应的E的v个子集iE递归调用上述过程,生成的子结点,12,,BB…，VB。ID3的基本原理是基于两类分类问题,但很容易扩展到多类。设样本集S共有C类样本,每类样本数为pi,(i=1,2,3,…c)。若以属性A作为决策树的根,A具有V个值1V,2V,…,nV,它将E分成V个子集[1E,2E,…,vE],假设iE中含有j类样本的个数为ijp,j=1,2,…,c那么,子集jE的信息量是I(iE)。1()*log||||cijvijiiPPIEEE以A为根分类的信息熵为:1||()*()||viiiEEAIEE选择属性使E(A)最小,信息增益也将增大。理想的决策树分成3种:(1)叶节点数最小,(2)叶节点深度最小;(3)叶节点数量最少且叶子结点深度最小。决策树的好坏,不仅影响分类的效率,而且还影响分类的准确率。人们为了寻求较优的解,不得不寻求各种启发式的方法。有的采用基于属性相关性的启发式函数;有的对生成的决策树进行剪枝处理;有的则扩充决策树,形成决策图。如今普遍采用的是优化算法,基本思想:首先用ID3选择属性F1,建立树T1,左、右子树的属性分别为F2,F3,再以F2,F3为根,重建树T2，T3;较T1,T2,T3的结点个数,选择结点最少的树。对于选择定树的儿子结点采用同样的方法递归建树。尽管作者用一个实验证明能建立理想的决策树,但算法有较大的弱点:时间开销太大,因为每选择一个新的属性,算法都需要建立3棵决策树,从中选优。算法的发展近况ID3算法的缺点：可能会收敛于局部最优解而丢失全局最优解，因为它是一种自顶向下贪心算法，逐个地考虑训练例，而不能使用新例步进式地改进决策树，同时它是一种单一变量决策树算法，表达复杂概念时非常困难；信息增益的方法往往偏向于选择取值较多的属性；连续性的字段比较难预测；当类别太多时，错误可能就会增加的比较快；只适合解决属性值为离散变量的问题；抗噪性差，比例较难控制。后来又出现了ID3算法的增量版本ID4算法和ID5算法，它们相对于小的数据集很有效率。ID4学习算法：在每个可能的决策树结点创造一系列表，每个表由全部未检测属性值和每个值的正例和反例数组构成，当处理一个新例时，每个属性值的正例和反例递增计量，也就是递增概念归纳。ID4算法优点：选择性的利用了原有规则集和决策表，使树结构规则，搜索和匹配速度很快。但它规则前件集中，样本正确识别率低，对不确定性处理能力差。ID5算法抛弃了旧的检测属性下面的子树，从下面选出检测属性形成树。它具有学习能力强，保证生成和ID3相同的判定树，使用树结构、搜索匹配速度快；但上拉复杂度高，判定生成树代价高，规则前件集中，样本识别率低，对不确定性记录处理能力差。由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法以及后来的C5.0算法，严格上说C4.5只能是ID3的一个改进算法。C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。但C4.5在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。此外，很多计算机的爱好者也对ID3算法和C4.5算法提出了各种各样的改进方法，在此本文就不一一列举了。算法的具体应用实例由于ID3算法的简洁和强大之处，它已经广泛的应用在数据挖掘和人工智能中，在这里本文就通过考察某校学生的学习状况为例,来展示ID3算法的一个实际应用。此例假定要按某校学生学习成绩好坏这个概念对一个集合进行分类,该集合中用来描述学生的属性有性格、父母教育程度和性别。性格的取值为外向、内向。父母教育程度取值为良好、中等和差。性别的取值为男生、女生。例子集中共有12名学生,如表2所示。在类别一栏,将正例即“学习成绩好”的学生用“好”标出,反例即“学生成绩差”的学生用“差”标出。表2某学校学生的例子集性格父母教育程度性别类别内向外向外向内向外向内向外向外向外向内向内向内向良良中差中良差差良中中差女生男生女生女生男生男生女生男生女生女生男生男生好好差差好好好差好差差差这些例子一开始全部包含在根结点中,为了找出当前的最佳划分属性,先须根据信息论中的公式计算训练实例集Es的熵值。则根节点的熵值为:6666()log2log212661266EntropyEs=1下面分别计算例子集中各个属性的信息赢取值。对属性“性格”来说,分外向和内向两个分支。当v=“外向”时,有4名“外向”小学生是“学习成绩好”的,有2名“外向”小学生是“学习成绩差”的。因此,4422()log2log20.9183624624sEntropyE性格,外向当v=“内向”时,有2名“内向”小学生是“学习成绩好”的,有4名“内向”小学生是“学习成绩差”的。因此,4422()log2log20.9183624624sEntropyE性格,内向所以根据“性格”属性来进行例子集分类的信息赢取值为:Gain(Es,性格)=Entropy(Es)-Entropy(Esv,格)=111-(*0.9183+*0.9183)=0.081722同理,对“父母教育程度”来说:Gain(Es,父母教育程度)=0.4591;对“性别”来说:Gain(Es,性别)=0。因为Gain(Es,性别)Gain(Es,性格)Gain(Es,父母教育程度)可以看出以“父母教育程度”这个属性进行例子集分类的信息赢取值最大,于是“父母教育程度”就被选为用于划分的属性,得到如下图所示的决策树。父母教育程度良差中内向，良，女生：好外向，良，男生：好内向，良，男生：好外向，良，女生：好内向，中，女生：差外向，中，男生：好内向，中，男生：差外向，中，女生：差内向，差，女生：差外向，差，女生：好内向，差，男生：差外向，差，男生：差按“父母教育程度”划分后的决策树现在必须根据所提供的信息进一步分析“父母教育程度”为“中”或“差”的小学生的“学习成绩好坏”,因此必须对“中”和“差”两个分支的实例组成的例子集(共8个例子)重复上述计算过程。这里简化计算过程,算出:Gain(Es,性格)=0.3113和Gain(Es,性别)=0.2045。因为Gain(Es,性别)Gain(Es,性格),所以用属性“性格”作第二步划分,于是得到如下图所示的决策树。父母教育程度良差中内向，良，女生：好外向，良，男生：好内向，良，男生：好外向，良，女生：好内向，中，女生：差内向，中，男生：差内向，差，女生：差内向，差，男生：差性格内向外向外向，中，男生：好外向，中，女生：差性格内向外向外向，差，女生：好外向，差，男生：差按“性格”作第二次划分后的决策树现在只有“父母教育程度”为“中”和“差”的“外向”小学生还没有明确类别,它们要用属性“性别”来进一步划分。最终得到的决策树如下图所示。父母教育程度良差中内向，良，女生：好外向，良，男生：好内向，良，男生：好外向，良，女生：好内向，中，女生：差内向，中，男生：差内向，差，女生：差内向，差，男生：差性格内向外向{外向，中，女生：差}性格内向外向{外向，差，男生：差}性别女生男生{外向，中，男生：好}{外向，差，女生：好}性别男生女生最终得到的决策树IF父母教育程度=“良”THEN学习成绩=“好”IF父母教育程度=“中”AND性格=“内向”THEN学习成绩=“差”IF父母教育程度=“差”AND性格=“内向”THEN学习成绩=“差”IF父母教育程度=“中”AND性格=“外向”AND性别=“女生”THEN学习成绩=“差”IF父母教育程度=“中”AND性格=“外向”AND性别=“男生”THEN学习成绩=“好”IF父母教育程度=“差”AND性格=“外向”AND性别=“女生”THEN学习成绩=“好”IF父母教育程度=“差”AND性格=“外向”AND性别=“男生”THEN学习成绩=“差”参考文献邹良颖，《浅析ID3算法原理及应用》，华南金融电脑2008年12月10日第12期张亚磊，《决策树算法的研究与该进》，海南大学2005级计算机科学与技术论文