第5章52ID3.ppt

1 第第 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 1、决策树概念：、决策树概念：决策树是用样本的属性作为结点，用属性的取值作决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。性进行分析和归纳而产生的。决策树方法的原理是信息论决策树方法的原理是信息论，信息论是，信息论是C.E.ShannonC.E.Shannon为解决信息传递（通信）过程问题而建立为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。的理论，也称为统计通信理论。n当前国际上最有影响的示例学习方法首推当前国际上最有影响的示例学习方法首推J.R.QuinlanJ.R.Quinlan的的ID3ID3。nID3ID3引进了信息论中的引进了信息论中的互信息互信息，他将其称为，他将其称为信信息增益（息增益（information gaininformation gain），作为特征判别作为特征判别能力的度量，并且将建树的方法嵌在一个迭代能力的度量，并且将建树的方法嵌在一个迭代的中。的中。某天早晨气候描述为某天早晨气候描述为:天气天气：多云多云 气温气温：冷冷 湿度湿度：正常正常 风风：无风无风 在一实体世界中，每个实体用多个特征来描述。每在一实体世界中，每个实体用多个特征来描述。每个特征限于在一个离散集中取互斥的值。例如，设实体个特征限于在一个离散集中取互斥的值。例如，设实体是某天早晨，分类任务是关于气候的类型，特征为是某天早晨，分类任务是关于气候的类型，特征为:天气天气 取值为：取值为：晴，多云，雨晴，多云，雨 气温气温 取值为：取值为：冷冷 ，适中，热，适中，热 湿度湿度 取值为：取值为：高高 ，正常，正常 风风 取值为：取值为：有风，有风，无风无风n它属于哪类气候（能否打高尔夫球）呢它属于哪类气候（能否打高尔夫球）呢?n每个实体属于不同的类别，为简单起见，假定仅有两个每个实体属于不同的类别，为简单起见，假定仅有两个类别，分别为类别，分别为P P，N N。在这种两个类别的归纳任务中，在这种两个类别的归纳任务中，P P类和类和N N类的实体分别称为概念的正例和反例。类的实体分别称为概念的正例和反例。n将一些已知的正例和反例放在一起便得到训练集。将一些已知的正例和反例放在一起便得到训练集。n下表给出一个训练集。由下表给出一个训练集。由ID3ID3算法得出一棵正确分类训算法得出一棵正确分类训练集中每个实体的决策树，见图。练集中每个实体的决策树，见图。NO.属性属性类别类别天气天气气温气温湿度湿度风风1晴晴热热高高无风无风N2晴晴热热高高有风有风N3多云多云热热高高无风无风P4雨雨适中适中高高无风无风P5雨雨冷冷正常正常无风无风P6雨雨冷冷正常正常有风有风N7多云多云冷冷正常正常有风有风P8晴晴适中适中高高无风无风N9晴晴冷冷正常正常无风无风P10雨雨适中适中正常正常无风无风P11晴晴适中适中正常正常有风有风P12多云多云适中适中高高有风有风P13多云多云热热正常正常无风无风P14雨雨适中适中高高有风有风N天天 气气湿湿 度度风风晴晴雨雨多云多云高高正常正常有风有风无风无风P PN NN NP PP PID3ID3决策树决策树n决策树叶子为类别名，即决策树叶子为类别名，即P P 或者或者N N。其它结点由实体的其它结点由实体的特征组成，每个特征的不同取值对应一分枝。特征组成，每个特征的不同取值对应一分枝。n若要对一实体分类，从树根开始进行测试，按特征的取若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点，对该结点进行测试，过程一值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类直进行到叶结点，实体被判为属于该叶结点所标记的类别。别。n 用图来判本节开始处的具体例子，得该实体的类别用图来判本节开始处的具体例子，得该实体的类别为为P P类。类。n ID3ID3方法就是要从表的训练集构造图这样的决策树。方法就是要从表的训练集构造图这样的决策树。n 实际上，能正确分类训练集的决策树不止一棵。实际上，能正确分类训练集的决策树不止一棵。n QuinlanQuinlan的的ID3ID3算法能得出结点最少的决策树。算法能得出结点最少的决策树。（一）主算法（一）主算法 1 1、从训练集中随机选择一个既含正例又含反例的子从训练集中随机选择一个既含正例又含反例的子集（称为集（称为 窗口窗口）；）；2 2、用用“建树算法建树算法”对当前窗口形成一棵决策树；对当前窗口形成一棵决策树；3 3、对训练集（窗口除外）中例子用所得决策树进行对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；类别判定，找出错判的例子；4 4、若存在错判的例子，把它们插入窗口，转若存在错判的例子，把它们插入窗口，转2 2，否则，否则结束。结束。n主算法流程用下图表示。其中主算法流程用下图表示。其中PEPE、NENE分别表示分别表示正例集和反例集，它们共同组成训练集。正例集和反例集，它们共同组成训练集。nPEPE，PEPE和和NENE，NENE分别表示正例集和反例集分别表示正例集和反例集的子集。的子集。n主算法中每迭代循环一次，生成的决策树将会主算法中每迭代循环一次，生成的决策树将会不相同。不相同。训练集训练集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处取值相同的例子归于同一子集，处取值相同的例子归于同一子集，AkAk取几个取几个值就得几个子集；值就得几个子集；4 4、对既含正例又含反例的子集，递归调用建树算法；对既含正例又含反例的子集，递归调用建树算法；5 5、若子集仅含正例或反例，对应分枝标上若子集仅含正例或反例，对应分枝标上P P或或N N，返回返回调用处。调用处。)logP(ulogP(u)P(uP(uH(U)H(U)i ii ii i|S S|u u|)P(uP(ui ii i 对于气候分类问题进行具体计算有：对于气候分类问题进行具体计算有：信息熵的计算信息熵的计算信息熵：信息熵：类别出现概率：类别出现概率：|S|S|表示例子集表示例子集S S的总数，的总数，|u ui i|表示类别表示类别u ui i的例子数。的例子数。对对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.94bit=0.94bitjjiijijvuPvuPvPVUH)/(log)/()()/(|)/(jijivuvuP 条件熵：条件熵：属性属性A A1 1取值取值vjvj时，类别时，类别u ui i的条件概率：的条件概率：A A1 1=天气天气 取值取值 v v1 1=晴，晴，v v2 2=多云，多云，v v3 3=雨雨在在A A1 1处处取值晴取值晴的例子的例子5 5个，个，取值多云取值多云的例子的例子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 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.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，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），），有有I I（U|VU|V）=0=0，在余下三个特征中求出湿度互信息最大，以它在余下三个特征中求出湿度互信息最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为为该分枝的根结点，再向下分枝。湿度取高的例子全为N N类，类，该分枝标记该分枝标记N N。取值正常的例子全为取值正常的例子全为P P类，该分枝标记类，该分枝标记P P。（2 2）在在F3F3中，对四个特征求互信息，得到风特征互中，对四个特征求互信息，得