知识工程与知识管理第5章5.2节.ppt

《知识工程与知识管理第5章5.2节.ppt》由会员分享，可在线阅读，更多相关《知识工程与知识管理第5章5.2节.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第第 5 章章机器学习与数据挖掘机器学习与数据挖掘(2)5.2节节15.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方法，他提出用信息增益（方法，他提出用信

2、息增益（information gain，即信，即信息论中的互信息）来选择属性作为决策树的结点。息论中的互信息）来选择属性作为决策树的结点。由于决策树的建树算法思想简单，识别样本效率高的特点，使由于决策树的建树算法思想简单，识别样本效率高的特点，使ID3方法成为当时机器学习领域中最有影响的方法之一方法成为当时机器学习领域中最有影响的方法之一。1 1、决策树概念：、决策树概念：决策树是用样本的属性作为结点，用属性的取值作决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。性进行分析和

3、归纳而产生的。决策树方法的原理是信息论决策树方法的原理是信息论，信息论是，信息论是C.E.ShannonC.E.Shannon为解决信息传递（通信）过程问题而建立为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。的理论，也称为统计通信理论。2 2、ID3ID3算法算法n当前国际上最有影响的示例学习方法首推当前国际上最有影响的示例学习方法首推J.R.QuinlanJ.R.Quinlan的的ID3ID3。nID3ID3引进了信息论中的引进了信息论中的互信息互信息，他将其称为，他将其称为信信息增益（息增益（information gaininformation gain），作为特征判别

4、作为特征判别能力的度量，并且将建树的方法嵌在一个迭代能力的度量，并且将建树的方法嵌在一个迭代的中。的中。一、一、ID3 ID3 基本思想基本思想某天早晨气候描述为某天早晨气候描述为:天气天气：多云多云 气温气温：冷冷 湿度湿度：正常正常 风风：无风无风 在一实体世界中，每个实体用多个特征来描述。每在一实体世界中，每个实体用多个特征来描述。每个特征限于在一个离散集中取互斥的值。例如，设实体个特征限于在一个离散集中取互斥的值。例如，设实体是某天早晨，分类任务是关于气候的类型，特征为是某天早晨，分类任务是关于气候的类型，特征为:天气天气 取值为：取值为：晴，多云，雨晴，多云，雨 气温气温 取值为：取

5、值为：冷冷 ，适中，热，适中，热 湿度湿度 取值为：取值为：高高 ，正常，正常 风风 取值为：取值为：有风，有风，无风无风n它属于哪类气候（能否打高尔夫球）呢它属于哪类气候（能否打高尔夫球）呢?n每个实体属于不同的类别，为简单起见，假定仅有两个每个实体属于不同的类别，为简单起见，假定仅有两个类别，分别为类别，分别为P P，N N。在这种两个类别的归纳任务中，在这种两个类别的归纳任务中，P P类和类和N N类的实体分别称为概念的正例和反例。类的实体分别称为概念的正例和反例。n将一些已知的正例和反例放在一起便得到训练集。将一些已知的正例和反例放在一起便得到训练集。n下表给出一个训练集。由下表给出一

6、个训练集。由ID3ID3算法得出一棵正确分类训算法得出一棵正确分类训练集中每个实体的决策树，见图。练集中每个实体的决策树，见图。NO.属性属性类别类别天气天气气温气温湿度湿度风风1晴晴热热高高无无风风N2晴晴热热高高有有风风N3多云多云热热高高无无风风P4雨雨适中适中高高无无风风P5雨雨冷冷正常正常无无风风P6雨雨冷冷正常正常有有风风N7多云多云冷冷正常正常有有风风P8晴晴适中适中高高无无风风N9晴晴冷冷正常正常无无风风P10雨雨适中适中正常正常无无风风P11晴晴适中适中正常正常有有风风P12多云多云适中适中高高有有风风P13多云多云热热正常正常无无风风P14雨雨适中适中高高有有风风N天天 气

7、气湿湿 度度风风晴晴雨雨多云多云高高正常正常有风有风无风无风P PN NN NP PP PID3ID3决策树决策树n决策树叶子为类别名，即决策树叶子为类别名，即P P 或者或者N N。其它结点由实体的特其它结点由实体的特征组成，每个特征的不同取值对应一分枝。征组成，每个特征的不同取值对应一分枝。n若要对一实体分类，从树根开始进行测试，按特征的取若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点，对该结点进行测试，过程一值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类直进行到叶结点，实体被判为属于该叶结点所标记的类别。别。n 用

8、图来判本节开始处的具体例子，得该实体的类别用图来判本节开始处的具体例子，得该实体的类别为为P P类。类。n ID3ID3方法就是要从表的训练集构造图这样的决策树。方法就是要从表的训练集构造图这样的决策树。n 实际上，能正确分类训练集的决策树不止一棵。实际上，能正确分类训练集的决策树不止一棵。n QuinlanQuinlan的的ID3ID3算法能得出结点最少的决策树。算法能得出结点最少的决策树。二、二、ID3 ID3 算法算法（一）主算法（一）主算法 1 1、从训练集中随机选择一个既含正例又含反例的子从训练集中随机选择一个既含正例又含反例的子集（称为集（称为 窗口窗口）；）；2 2、用用“建树算

9、法建树算法”对当前窗口形成一棵决策树；对当前窗口形成一棵决策树；3 3、对训练集（窗口除外）中例子用所得决策树进行对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；类别判定，找出错判的例子；4 4、若存在错判的例子，把它们插入窗口，转若存在错判的例子，把它们插入窗口，转2 2，否则，否则结束。结束。n主算法流程用下图表示。其中主算法流程用下图表示。其中PEPE、NENE分别表示分别表示正例集和反例集，它们共同组成训练集。正例集和反例集，它们共同组成训练集。nPEPE，PEPE和和NENE，NENE分别表示正例集分别表示正例集和反例集的子集。和反例集的子集。n主算法中每迭代循环

10、一次，生成的决策树将会主算法中每迭代循环一次，生成的决策树将会不相同。不相同。训练集训练集PEPE、NENE取子集取子集建窗口建窗口窗口窗口PEPE、NENE生成生成决策树决策树测试测试PEPE、NENE扩展窗口扩展窗口PE=PE+PENEPE=PE+PENE=NE+NE=NE+NE此决策树为此决策树为最后结果最后结果存在错判的存在错判的PEPE，NENE吗吗是是否否ID3ID3主算法流程主算法流程（二）建树算法（二）建树算法 1 1、对当前例子集合，计算各特征的互信息；对当前例子集合，计算各特征的互信息；2 2、选择互信息最大的特征选择互信息最大的特征AkAk；3 3、把在把在AkAk处取值

11、相同的例子归于同一子集，处取值相同的例子归于同一子集，AkAk取几个取几个值就得几个子集；值就得几个子集；4 4、对既含正例又含反例的子集，递归调用建树算法；对既含正例又含反例的子集，递归调用建树算法；5 5、若子集仅含正例或反例，对应分枝标上若子集仅含正例或反例，对应分枝标上P P或或N N，返回返回调用处。调用处。3 3、ID3ID3方法应用实例方法应用实例 对于气候分类问题进行具体计算有：对于气候分类问题进行具体计算有：信息熵的计算信息熵的计算信息熵：信息熵：类别出现概率：类别出现概率：|S|S|表示例子集表示例子集S S的总数，的总数，|u ui i|表示类别表示类别u ui i的例子

12、数。的例子数。对对9 9个正例和个正例和5 5个反例有：个反例有：P P（u u1 1）=9/14=9/14 P P（u u2 2）=5/14=5/14H H（U U）=（9/149/14）loglog（14/914/9）+（5/145/14）loglog（14/514/5）=0.94bit0.94bit 条件熵：条件熵：条件熵计算条件熵计算属性属性A A1 1取值取值vjvj时，类别时，类别u ui i的条件概率：的条件概率：A A1 1=天气天气 取值取值 v v1 1=晴，晴，v v2 2=多云，多云，v v3 3=雨雨在在A A1 1处处取值晴取值晴的例子的例子5 5个，个，取值多云取

13、值多云的例子的例子4 4 个，个，取值雨取值雨的例子的例子5 5 个，故：个，故：P P（v v1 1）=5/14 P=5/14 P（v v2 2）=4/14 P=4/14 P（v v3 3）=5/14=5/14取值为晴取值为晴的的5 5 个例子中有个例子中有2 2 个正例、个正例、3 3个反例，故：个反例，故：P P（u u1 1/v/v1 1）=2/5=2/5，P P（u u2 2/v/v1 1）=3/5=3/5同理有：同理有：P P（u u1 1/v/v2 2）=4/4=4/4，P P（u u2 2/v/v2 2）=0=0 P P（u u1 1/v/v3 3）=2/5=2/5，P P（u

14、 u2 2/v/v3 3）=3/5=3/5H(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/14)H(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)(4/4)log(4/4)+0)+(5/14)(2/5)log(5/2)+(3/5)log(5/3)=0.694bit)=0.694bit 互信息计算互信息计算 对对 A A1 1=天气天气 处有：处有：I I（天气）天气）=H H（U U）-H-H（U|VU|V）=0

15、.94-0.694=0.246 bit=0.94-0.694=0.246 bit 类似可得：类似可得：I I（气温）气温）=0.029=0.029 bitbit I I（湿度）湿度）=0.151=0.151 bitbit I I（风）风）=0.048=0.048 bitbit 建决策树的树根和分枝建决策树的树根和分枝 ID3ID3算法将选择互信息最大的特征天气作为树根，在算法将选择互信息最大的特征天气作为树根，在1414个例子中对个例子中对天气的天气的3 3个取值进行分枝，个取值进行分枝，3 3 个分枝对应个分枝对应3 3 个子集，分别是个子集，分别是:F1=1F1=1，2 2，8 8，9 9

16、，1111，F2=3F2=3，7 7，1212，1313，F3=4F3=4，5 5，6 6，1010，1414 其中其中F2F2中的例子全属于中的例子全属于P P类，因此对应分枝标记为类，因此对应分枝标记为P P，其余两个子其余两个子集既含有正例又含有反例，将递归调用建树算法。集既含有正例又含有反例，将递归调用建树算法。递归建树递归建树 分别对分别对F1F1和和F3F3子集利用子集利用ID3ID3算法，在每个子集中对各特算法，在每个子集中对各特征（仍为四个特征）求互信息征（仍为四个特征）求互信息.（1 1）F1F1中的天气全取晴值，则中的天气全取晴值，则H H（U U）=H=H（U|VU|V）

17、，），有有I I（U|VU|V）=0=0，在余下三个特征中求出湿度互信息最大，以它在余下三个特征中求出湿度互信息最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为为该分枝的根结点，再向下分枝。湿度取高的例子全为N N类，类，该分枝标记该分枝标记N N。取值正常的例子全为取值正常的例子全为P P类，该分枝标记类，该分枝标记P P。（2 2）在在F3F3中，对四个特征求互信息，得到风特征互中，对四个特征求互信息，得到风特征互信息最大，则以它为该分枝根结点。再向下分枝，风取有风信息最大，则以它为该分枝根结点。再向下分枝，风取有风时全为时全为N N类，该分枝标记类，该分枝标记N N。取无风时全

18、为取无风时全为P P类，该分枝标记类，该分枝标记P P。这样就得到图的决策树这样就得到图的决策树 5.2.2 5.2.2 基于信息增益率的基于信息增益率的C4.5C4.5方法方法 ID3ID3算法在数据挖掘中占有非常重要的地位。但是，算法在数据挖掘中占有非常重要的地位。但是，在应用中，在应用中，ID3ID3算法不能够处理连续属性、计算信息增益算法不能够处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。时偏向于选择取值较多的属性等不足。C4.5 C4.5是在是在ID3ID3基础上发展起来的决策树生成算法，由基础上发展起来的决策树生成算法，由J.R.QuinlanJ.R.Quinlan在

19、在19931993年提出。年提出。C4.5C4.5克服了克服了ID3ID3在应用中存在在应用中存在的不足。的不足。C4.5C4.5的进步的进步 （1 1）用信息增益率来选择属性，它克服了用信息增益用信息增益率来选择属性，它克服了用信息增益选择属性时偏向选择取值多的属性的不足；选择属性时偏向选择取值多的属性的不足；（2 2）在树构造过程中或者构造完成之后，进行剪枝；在树构造过程中或者构造完成之后，进行剪枝；（3 3）能够完成对连续属性的离散化处理；能够完成对连续属性的离散化处理；（4 4）能够对于不完整数据的处理，例如未知的属性值；能够对于不完整数据的处理，例如未知的属性值；（5 5）C4.5C

20、4.5采用的知识表示形式为决策树，并最终可以采用的知识表示形式为决策树，并最终可以形成产生式规则。形成产生式规则。C4.5C4.5构造决策树的算法构造决策树的算法 QuinlanQuinlan在在ID3ID3中中使使用用信信息息论论中中的的信信息息增增益益（gaingain）来来选选择择属属性性，而而C4.5C4.5采采用用属属性性的的信信息息增增益益率率（gain gain ratioratio）来选择属性。来选择属性。信息增益率信息增益率 C4.5C4.5对对ID3ID3改进是用信息增益率来选择属性。改进是用信息增益率来选择属性。理论和实验表明，采用理论和实验表明，采用“信息增益率信息增益

21、率”（C4.5C4.5方法）方法）比采用比采用“信息增益信息增益”（ID3ID3方法）更好，主要是克服了方法）更好，主要是克服了ID3ID3方法选择偏向取值多的属性。方法选择偏向取值多的属性。5.2.3 5.2.3 基于信道容量的基于信道容量的IBLEIBLE方法方法 我们于我们于9191年研制的年研制的IBLEIBLE方法方法 IBLEIBLE方法是利用信息论中信道容量来选择属性，比互方法是利用信息论中信道容量来选择属性，比互信息更好。信息更好。IBLE IBLE方法建决策规则树，方法建决策规则树，每个结点由多个属性取值组每个结点由多个属性取值组成，成，各特征的正例标准值由译码函数决定。结点

22、中判别各特征的正例标准值由译码函数决定。结点中判别正反例的阈值是由实例中权值变化的规律来确定的正反例的阈值是由实例中权值变化的规律来确定的。决策规则树决策规则树 规则1规则2规则n u1 u1 u1u2 u2 u2 决策规则树结点决策规则树结点（1）规则表示形式）规则表示形式 决策规则树中非叶结点均为规则。规则表示为：决策规则树中非叶结点均为规则。规则表示为：特征：特征：A1，A2，.，.Am 权值：权值：W1，W2，.，.Wm 标准值：标准值：V1，V2，.，.Vm 阈值：阈值：Sp，Sn该规则可形式描述为：该规则可形式描述为：（1）sum:=0；（2）对）对i:=1到到m作：若（作：若（A

23、i）=Vi，则，则 sum:=sum+wi；（3）若）若sum sn，则该例为，则该例为N类；类；（4）若）若sum sp，则该例为，则该例为P类；类；（5）若）若snsum220，判定例子，判定例子1属于属于u1类。类。例子例子2的权和的权和sum=130，有，有100sum220，认为例子，认为例子2不能判，不能判，例子例子3有权和有权和sum=90，有，有sum100，判例子，判例子3的类别的类别为为u2类。类。规则中规则中:A1，A2，.，Am为组成规则的特征为组成规则的特征 W1，W2，.，Wm为对应的权值为对应的权值 V1，V2，.，Vm为对应特征取正例的标准值为对应特征取正例的标

24、准值 测试例子在该特征处取值与标准值相同，则测试例子在该特征处取值与标准值相同，则sum（权和）加上对应权值，否则不加。（权和）加上对应权值，否则不加。Sp，Sn是判是、判非、不能判的阈值。是判是、判非、不能判的阈值。测试例子的权和为测试例子的权和为sum:sumSp时判为是类（时判为是类（u1类）类）sum Sn时判为非类（时判为非类（u2类）类）Snsums1 n 非非1类类 1类类n等价规则为：等价规则为：c=2 d=2 a=1 1n c=2 d=2 b=1 1苯等八类化合物的分类问题苯等八类化合物的分类问题类类正正例例认认对对认认错错正确正确百分百分比比反反例例认认对对认认错错正确正确

25、百分百分比比总总正确正确百分比百分比RQRT60TJ类一类二类三类四类五1022050552419515345524175160000093137756810010010010010015510050999999999999999136844899799799999999919162220008777484969989981001001009043979582999999100100100对八类化合物，对八类化合物，IBLE的平均预测正确率为的平均预测正确率为93.967%。IBLE与与ID3的比较的比较类类IBLE%ID3%RT60TJ类类二二81 77976 78698 33472 203

26、70 64389 322预测正确率预测正确率IBLE比比ID3高出近高出近10个百分点。个百分点。原因分析原因分析IBLE的预测正确率之所以比的预测正确率之所以比ID3高的原因在于：高的原因在于：IBLE用用信道容量作为特征选择量信道容量作为特征选择量，而，而ID3用互信用互信息，息，信道容量不依赖于正、反例的比例，互信息信道容量不依赖于正、反例的比例，互信息依赖训练集中正反例的比例。依赖训练集中正反例的比例。ID3在建树过程中，每次选择一个特征作为结点，在建树过程中，每次选择一个特征作为结点，不能较好地体现特征间的相关性。不能较好地体现特征间的相关性。IBLE在建树过程中每次循环在建树过程中

27、每次循环选择多个特征构成选择多个特征构成规则，变量间的相关性得到较好的体现规则，变量间的相关性得到较好的体现。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个重要质量个重要质量中，无共同的特征。中，无共同的特征。习题习题 11，12，13，14，16