《第5章52ID3.ppt》由会员分享，可在线阅读，更多相关《第5章52ID3.ppt（41页珍藏版）》请在三一办公上搜索。
1、1,第 5 章,机器学习与数据挖掘(2)5.2节,5.2 基于信息论的归纳学习方法,5.2.1 基于互信息的ID3方法5.2.2 基于信息增益率的C4.5方法5.2.3 基于信道容量的IBLE方法,5.2.1 基于互信息的ID3方法,决策树概念最早是1966年由EHunt提出的的CLS决策树学习算法。影响最大的是J.R.Quinlan于1986年提出的改进CLS算法的ID3方法，他提出用信息增益（information gain，即信息论中的互信息）来选择属性作为决策树的结点。由于决策树的建树算法思想简单，识别样本效率高的特点，使ID3方法成为当时机器学习领域中最有影响的方法之一。,1、决策树
2、概念：决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。决策树方法的原理是信息论，信息论是C.E.Shannon为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。,2、ID3算法,当前国际上最有影响的示例学习方法首推J.R.Quinlan的ID3。ID3引进了信息论中的互信息，他将其称为信息增益（information gain），作为特征判别能力的度量，并且将建树的方法嵌在一个迭代的中。,一、ID3 基本思想,某天早晨气候描述为:天气：多云 气温：冷 湿度：正常 风：无风,在一实体世界中，每个实体用多个特征来描
3、述。每个特征限于在一个离散集中取互斥的值。例如，设实体是某天早晨，分类任务是关于气候的类型，特征为:天气 取值为：晴，多云，雨 气温 取值为：冷，适中，热 湿度 取值为：高，正常 风 取值为：有风，无风,它属于哪类气候（能否打高尔夫球）呢?每个实体属于不同的类别，为简单起见，假定仅有两个类别，分别为P，N。在这种两个类别的归纳任务中，P类和N类的实体分别称为概念的正例和反例。将一些已知的正例和反例放在一起便得到训练集。下表给出一个训练集。由ID3算法得出一棵正确分类训练集中每个实体的决策树，见图。,晴,雨,多云,高,正常,有风,无风,P,N,N,P,P,ID3决策树,决策树叶子为类别名，即P
4、或者N。其它结点由实体的特征组成，每个特征的不同取值对应一分枝。若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。,用图来判本节开始处的具体例子，得该实体的类别为P类。ID3方法就是要从表的训练集构造图这样的决策树。实际上，能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。,二、ID3 算法,（一）主算法 1、从训练集中随机选择一个既含正例又含反例的子集（称为窗口）；2、用“建树算法”对当前窗口形成一棵决策树；3、对训练集（窗口除外）中例子用所得决策树进行类别判定
5、，找出错判的例子；4、若存在错判的例子，把它们插入窗口，转2，否则结束。,主算法流程用下图表示。其中PE、NE分别表示正例集和反例集，它们共同组成训练集。PE，PE和NE，NE分别表示正例集和反例集的子集。主算法中每迭代循环一次，生成的决策树将会不相同。,ID3主算法流程,（二）建树算法 1、对当前例子集合，计算各特征的互信息；2、选择互信息最大的特征Ak；3、把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；4、对既含正例又含反例的子集，递归调用建树算法；5、若子集仅含正例或反例，对应分枝标上P或N，返回调用处。,3、ID3方法应用实例,对于气候分类问题进行具体计算有：信息熵的
6、计算信息熵：,类别出现概率：|S|表示例子集S的总数，|ui|表示类别ui的例子数。对9个正例和5个反例有：P（u1）=9/14 P（u2）=5/14H（U）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit,条件熵：,条件熵计算,属性A1取值vj时，类别ui的条件概率：,A1=天气 取值 v1=晴，v2=多云，v3=雨在A1处取值晴的例子5个，取值多云的例子4 个，取值雨的例子5 个，故：P（v1）=5/14 P（v2）=4/14 P（v3）=5/14取值为晴的5 个例子中有2 个正例、3个反例，故：P（u1/v1）=2/5，P（u2/v1）=3/5同理有：P（
7、u1/v2）=4/4，P（u2/v2）=0 P（u1/v3）=2/5，P（u2/v3）=3/5H(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/14)(4/4)log(4/4)+0)+(5/14)(2/5)log(5/2)+(3/5)log(5/3)=0.694bit,互信息计算 对 A1=天气 处有：I（天气）=H（U）-H（U|V）=0.94-0.694=0.246 bit 类似可得：I（气温）=0.029 bit I（湿度）=0.151 bit I（风）=0.048 bit 建决策树的树根和分枝 ID3算法将选择互信息最大的特征天气作为树根，在14个
8、例子中对天气的3个取值进行分枝，3 个分枝对应3 个子集，分别是:F1=1，2，8，9，11，F2=3，7，12，13，F3=4，5，6，10，14 其中F2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用建树算法。,递归建树 分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征）求互信息.（1）F1中的天气全取晴值，则H（U）=H（U|V），有I（U|V）=0，在余下三个特征中求出湿度互信息最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标记N。取值正常的例子全为P类，该分枝标记P。（2）在F3中，对四个特征求互信
9、息，得到风特征互信息最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。这样就得到图的决策树,5.2.2 基于信息增益率的C4.5方法,ID3算法在数据挖掘中占有非常重要的地位。但是，在应用中，ID3算法不能够处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。C4.5是在ID3基础上发展起来的决策树生成算法，由J.R.Quinlan在1993年提出。C4.5克服了ID3在应用中存在的不足。,C4.5的进步（1）用信息增益率来选择属性，它克服了用信息增益选择属性时偏向选择取值多的属性的不足；（2）在树构造过程中或者构造完成之后，进行
10、剪枝；（3）能够完成对连续属性的离散化处理；（4）能够对于不完整数据的处理，例如未知的属性值；（5）C4.5采用的知识表示形式为决策树，并最终可以形成产生式规则。,C4.5构造决策树的算法,Quinlan在ID3中使用信息论中的信息增益（gain）来选择属性，而C4.5采用属性的信息增益率（gain ratio）来选择属性。信息增益率 C4.5对ID3改进是用信息增益率来选择属性。理论和实验表明，采用“信息增益率”（C4.5方法）比采用“信息增益”（ID3方法）更好，主要是克服了ID3方法选择偏向取值多的属性。,5.2.3 基于信道容量的IBLE方法,我们于91年研制的IBLE方法 IBLE方
11、法是利用信息论中信道容量来选择属性，比互信息更好。IBLE方法建决策规则树，每个结点由多个属性取值组成，各特征的正例标准值由译码函数决定。结点中判别正反例的阈值是由实例中权值变化的规律来确定的。,决策规则树,决策规则树结点（1）规则表示形式 决策规则树中非叶结点均为规则。规则表示为：特征：A1，A2，.，.Am 权值：W1，W2，.，.Wm 标准值：V1，V2，.，.Vm 阈值：Sp，Sn,该规则可形式描述为：（1）sum:=0；（2）对i:=1到m作：若（Ai）=Vi，则 sum:=sum+wi；（3）若sumsn，则该例为N类；（4）若sumsp，则该例为P类；（5）若snsumsp，则该
12、例暂不能判，转下一条规则判别。其中sum表示权和，（Ai）表示特征Ai的取值。,（2）举例设问题空间中例子有10个特征（属性），特征编号从1到10。每个特性取值为no,yes，用0,1表示，规则是由重要特征组成的，对每个特征求出权值以表示其重要程度，删除不重要特征得规则如下：特征：1 3 4 6 7 权值：100 90 105 500 40 标准值：1 0 1 1 0 阈值：220，100,现有三个测试例子：例子1：（1，0，0，0，1，0，0，1，1，1）例子2：（0，1，0，0，1，0，0，0，1，0）例子3：（0，1，0，0，1，0，1，0，1，1）例子1的权和sum=230，有sum2
13、20，判定例子1属于u1类。例子2的权和sum=130，有100sum220，认为例子2不能判，例子3有权和sum=90，有sum100，判例子3的类别为u2类。,规则中:A1，A2，.，Am为组成规则的特征 W1，W2，.，Wm为对应的权值 V1，V2，.，Vm为对应特征取正例的标准值 测试例子在该特征处取值与标准值相同，则sum（权和）加上对应权值，否则不加。Sp，Sn是判是、判非、不能判的阈值。测试例子的权和为sum:sumSp时判为是类（u1类）sumSn时判为非类（u2类）SnsumSp时认为不能判,IBLE算法由四部分组成：预处理；建决策树算法；建规则算法；类别判定算法。以上算法见
14、书中说明.,IBLE方法实例 配隐形眼镜问题,（1）患者配隐形眼镜的类别 患者是否应配隐形眼镜有三类：1：患者应配隐形眼 2：患者应配软隐形眼镜 3：患者不适合配隐形眼镜（2）患者眼镜诊断信息(属性)a：患者的年纪(1)年轻；(2)前老光眼；(3)老光眼b：患者的眼睛诊断结果(1)近视；(2)远视c：是否散光(1)是：(2)否d：患者的泪腺(1)不发达；(2)正常,配隐形眼镜患者实例表,利用IBLE算法得出的各类决策规则树和逻辑公式（1）1类的决策规则树 规则 1 a=1 b=1 c=2 d=2 0.21 0.048 0.282 0.282 s1=0.5639 s1 s1 非1类 1类等价规则
15、为：c=2 d=2 a=1 1 c=2 d=2 b=1 1,苯等八类化合物的分类问题,对八类化合物，IBLE的平均预测正确率为93.967%。,IBLE与ID3的比较,预测正确率IBLE比ID3高出近10个百分点。,原因分析,IBLE的预测正确率之所以比ID3高的原因在于：IBLE用信道容量作为特征选择量，而ID3用互信息，信道容量不依赖于正、反例的比例，互信息依赖训练集中正反例的比例。ID3在建树过程中，每次选择一个特征作为结点，不能较好地体现特征间的相关性。IBLE在建树过程中每次循环选择多个特征构成规则，变量间的相关性得到较好的体现。,IBLE决策规则树的特点,IBLE的决策规则树中的规则在表示和内容上与专家知识具有较高的一致性。第一条规则指出在m/e=27，50-52，62-65，74-78，89-92，104-105处应有峰。有关文献中认为含苯化合物的重要系列应是m/e=38-39，50-52，63-65，75-78，91，105，119，113等。比较一下知道，在列出的这16个峰中第一条规则就包含了12个，而且都是权值较大的峰。,IBLE决策规则树的特点,在训练集中，若正、反例数目变化较大，IBLE得到的规则具有较好的稳定性。IBLE得出的各决策规则树中第一条规则，都含有相同的41个特征。在相同的变化下ID3的决策树头两层7个重要质量中，无共同的特征。,
