资源描述：
《ID3算法原理及应用.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ID3算法的应用研究摘要决策树算法是数据挖掘领域的核心分类算法之一,其中ID3算法是最为经典的决策树算法。ID3算法理论清晰、使用简单、学习能力较强,且构造的决策树平均深度较小,分类速度较快,特别适合处理大规模的学习问题,目前已得到广泛应用。本文对ID3算法进行了详细的描述,介绍了其算法的基本原理、发展近况、及其具体运用。引言分类技术是一种根据输入数据集建立分类模型的系统方法。分类技术一般是用一种学习算法确定分类模型，该模型可以很好地拟合输入数据中类标号和属性集之间的联系。依据学习算法可以建立能够准确地预测未知样本类标号的模型。分类方法的实例包括：决策树分类法、基于规则的
2、分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。相对于其他几种算法而言，ID3算法理论清晰，算法简单，是很有实用价值的实例学习算法，计算时间是例子个数、特征属性个数、节点个数属性之积的线性函数，总预测准确率较高，针对属性选择问题，是决策树学习方法中最具影响和最为典型的算法。因此本文将详细介绍该算法。算法基本原理在ID3决策树归纳方法中，通常是使用信息增益方法来帮助确定生成每个节点时所应采用的合适属性。这样就可以选择具有最高信息增益（熵减少的程度最大）的属性最为当前节点的测试属性，以便对之后划分的训练样本子集进行分类所需要的信息最小，也就是说，利用该属性进行当前（节点所
3、含）样本集合划分，将会使得所产生的样本子集中的“不同类别的混合程度”降为最低。因此，采用这样一种信息论方法将有效减少对象分来所需要的次数，从而确保所产生的决策树最为简单。设E=F1×F2×…×Fn是n维有穷向量空间,其中是有穷离散符号集,E中的元素e=<,,…,>叫做例子,其中∈,j=1,2,…,n。设PE和NE是E的F两个例子集,分别叫正例集和反例集。假设向量空间E中的正例集PE和反例集NE的大小分别为p和n,ID3基于下列两个假设:(1)在向量空间E上的一棵正确决策树,对任意例子的分类概率同E中的正、反例的概率一致;(2)一棵决策树能对一例子做出正确类别判断所需的信息
4、量为:I（p,n）=如果以属性A作为决策树的根,A具有v个值(,,…,),它将E分为v个子集(,,…,),假设中含有Pi个正例和个反例,子集的信息熵为I(Pi,),以属性A为根分类后的信息熵为：因此,以A为根的信息增益是Gain(A)=I(p,n)-E(A)。ID3选择使Gain(A)最大(即E(A)最小)的属性作为根结点。对的不同的取值对应的E的v个子集递归调用上述过程,生成的子结点,…，。ID3的基本原理是基于两类分类问题,但很容易扩展到多类。设样本集S共有C类样本,每类样本数为pi,(i=1,2,3,…c)。若以属性A作为决策树的根,A具有V个值,,…,,它将E分成
5、V个子集[,,…,],假设中含有j类样本的个数为,j=1,2,…,c那么,子集的信息量是I()。 以A为根分类的信息熵为: 选择属性使E(A)最小,信息增益也将增大。理想的决策树分成3种:(1)叶节点数最小,(2)叶节点深度最小;(3)叶节点数量最少且叶子结点深度最小。决策树的好坏,不仅影响分类的效率,而且还影响分类的准确率。人们为了寻求较优的解,不得不寻求各种启发式的方法。有的采用基于属性相关性的启发式函数;有的对生成的决策树进行剪枝处理;有的则扩充决策树,形成决策图。如今普遍采用的是优化算法,基本思想:首先用ID3选择属性F1,建立树T1,左、右子树的属性分别为F
6、2,F3,再以F2,F3为根,重建树T2，T3;较T1,T2,T3的结点个数,选择结点最少的树。对于选择定树的儿子结点采用同样的方法递归建树。尽管作者用一个实验证明能建立理想的决策树,但算法有较大的弱点:时间开销太大,因为每选择一个新的属性,算法都需要建立3棵决策树,从中选优。算法的发展近况 ID3算法的缺点：可能会收敛于局部最优解而丢失全局最优解，因为它是一种自顶向下贪心算法，逐个地考虑训练例，而不能使用新例步进式地改进决策树，同时它是一种单一变量决策树算法，表达复杂概念时非常困难；信息增益的方法往往偏向于选择取值较多的属性；连续性的字段比较难预测；当类别太多时，错误可
7、能就会增加的比较快；只适合解决属性值为离散变量的问题；抗噪性差，比例较难控制。后来又出现了ID3算法的增量版本ID4算法和ID5算法，它们相对于小的数据集很有效率。ID4学习算法：在每个可能的决策树结点创造一系列表，每个表由全部未检测属性值和每个值的正例和反例数组构成，当处理一个新例时，每个属性值的正例和反例递增计量，也就是递增概念归纳。ID4算法优点：选择性的利用了原有规则集和决策表，使树结构规则，搜索和匹配速度很快。但它规则前件集中，样本正确识别率低，对不确定性处理能力差。ID5算法抛弃了旧的检测属性下面的子树，从下面选出
