专题讲座-ID3算法简介

1、ID3 ID3 算法简介算法简介郭向丹 谢宗汛LOGOLOGO 随着信息技术的飞速发展, 数据量也以惊人的速度增长, 如何从这些大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的有用信息呢? 数据挖掘技术数据挖掘技术便应运而生。 数据挖掘是指从大量结构化和非结构的数据中提取有用的信息和知识的过程, 是知识发现的有效手段。 数据分类是数据挖掘中的一个重要问题，指的是通过分析训练集中的数据，对类建立分类模型，利用分类模型预测类标记未知的对象类。数据分类技术主要有：决策树决策树归纳、贝叶斯分类和贝叶斯网络、神经网络算法、遗传算法等。 ID3ID3算法算法是决策树构造中的经典算法。LOG

2、OLOGO1、ID3算法基本思想2、相关定义3、ID3应用举例4、ID3算法缺陷和改进LOGOLOGO 算法核心思想是：检测所有的属性，选择信息增益最大的属性作为决策树节点，由该属性的不同取值建立分支，再对各分支的子集递归地调用该方法建立决策树节点的分支，直到所有子集仅包含同一类别的数据位置。最后得出属性和类别间的关系，得到一棵决策树，用来对新样本进行分类。ID3算法基本思想LOGOLOGOID3算法基本思想 在一实体世界中，每个实体用多个属性来描述。每个属性限于在在一实体世界中，每个实体用多个属性来描述。每个属性限于在一个离散集中取互斥的值。例如，设实体是某天早晨，分类任务一个离散集中取互斥

3、的值。例如，设实体是某天早晨，分类任务是关于气候的类型，属性如下。是关于气候的类型，属性如下。 某天早晨气候描述为：天气多云；气温冷；湿度正常；风无风某天早晨气候描述为：天气多云；气温冷；湿度正常；风无风 需要用某个原则来判定，这个原则来自于大量的实际例子，从例需要用某个原则来判定，这个原则来自于大量的实际例子，从例子中总结出原则。子中总结出原则。 每个实体在世界中属于不同的类别，为简单起见，假定仅有每个实体在世界中属于不同的类别，为简单起见，假定仅有两个两个类别，分别为类别，分别为P P、N N。在这种两个类别的归纳任务中，。在这种两个类别的归纳任务中，P P类和类和N N类的类的实体分别称

4、为概念的实体分别称为概念的正例正例和和反例反例。将一些已知正例和反例放在一。将一些已知正例和反例放在一起便得到起便得到训练集训练集。LOGOLOGOID3算法基本思想LOGOLOGOID3算法基本思想晴晴多云多云雨雨P P高高正常正常P PN NN NP P有风有风湿度湿度风风天气天气ID3ID3决策树决策树LOGOLOGO相关定义1、类别属性的信息熵：设S 是s个训练数据样本的集合。假定类标号属性具有m个不同值, 定义m 个不同类Ci,i=1,m,si是类Ci中的样本数。一个给定的样本分类所需的期望信息:2、期望熵：设属性A 具有v个不同值a1, a2,av, 可以用属性A 将S 划分为v个

5、子集S1, S2,Sv。Sj 中的样本在属性A上具有相同的值aj,j =1,2,v,sij 是子集Sj中类Ci的样本数，由A划分成子集的期望信息:LOGOLOGO3、信息增益：由前面的定义得出的信息熵为：4、属性A上分支将获得信息增益为： ID3算法对每个节点中选择信息增益最大的属性A作为测试属性。信息增益越大，说明选择测试属性A实德队结果划分的样本分类所需信息量最小，对分类提供的信息越多，并确保得到一颗简单的树。相关定义LOGOLOGOID3应用举例 一个预测贷款申请者是否会按时还贷款的实例。表1给出影响按时还款的几个相关指标的数据集合,它有4个属性:拥有车辆情况、婚姻情况、父母收入情况、申

6、请者收入情况, 这4个属性被分为是(正例)和否(反例)两类LOGOLOGOID3应用举例 假设从样本数据集中取100个样本,其中类“是”有45个样本,类“否”有55个样本。依据公式 计算出开始时熵值为:0.9928。 依据公式 得出拥有车辆情况、婚姻情况、父母收入情况、申请者收入情况4个属性的信息熵分别为:0.866、0.5392、0.878、0.8328。LOGOLOGOID3应用举例 由于婚姻情况属性具有最小信息熵, 再依据公式 可知它具有最大的信息增益,因此它被作为测试属性,创建节点婚姻情况,并对每个属性值引出一个分支,样本数据据此划分。每一个分支按照以上方法递归计算,最后得出的决策树如图所示。LOGOLOGOID3应用举例LOGOLOGOID3算法缺陷和改进ID3算法缺陷: 1、不能增量地接受训练例,使得每增加一次实例都必须废除原有决策树,重新计算信息增益并构造新的决策树,造成极大的开销; 2、只能处理离散属性,对于连续型的属性,在分类前需要对其进行离散化的处理;在建树时每个结点仅含一个特征，是一种单变元算法,特征间的相关性强调不够; 3、对噪声较为敏感,数据质量差将直接导致生成的决策树过于庞大或决策树中很多分支的信息量很小; 4、在建树的过程中选择一个新属性时,算法只考虑该属性带来的信