决策支持系统课程报告课件.ppt

1、 JRQuinlan的ID3（interative dicremiser version3）的工作过程是，首选找出最有判别力（信息增益，-information gain）的属性，把数据分成多个子集，每个子集又选择最有判别力的属性进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树，可以用它来对新的实例进行分类。在一实体世界中，每个实体用多个属性来描述。每个属性限于在一个离散集中取互斥的值。例如，设实体是某天早晨，分类任务是关于气候的类型，属性如下。天气，取值为：晴，多云，雨。天气，取值为：晴，多云，雨。气温，取值为：冷，适中，热。气温，取值为：冷，适中，热。湿度，取值为：

2、高，正常。湿度，取值为：高，正常。风，取值为：有风，无风。风，取值为：有风，无风。某天早晨气候描述为：天气多云；气温冷；某天早晨气候描述为：天气多云；气温冷；某天早晨气候描述为：天气多云；气温冷；某天早晨气候描述为：天气多云；气温冷；湿度正常；风无风。湿度正常；风无风。湿度正常；风无风。湿度正常；风无风。它属于哪类气候呢？它属于哪类气候呢？它属于哪类气候呢？它属于哪类气候呢？要解决这个问题，需要用某要解决这个问题，需要用某要解决这个问题，需要用某要解决这个问题，需要用某个原则来判定，这个原则来自于大量的实际例子，个原则来判定，这个原则来自于大量的实际例子，个原则来判定，这个原则来自于大量的实际

3、例子，个原则来判定，这个原则来自于大量的实际例子，从例子中总结出原则，有了原则就可以判定任何从例子中总结出原则，有了原则就可以判定任何从例子中总结出原则，有了原则就可以判定任何从例子中总结出原则，有了原则就可以判定任何一天的气候了。一天的气候了。一天的气候了。一天的气候了。每个实体在世界中属于不同的类别，为简单起见，每个实体在世界中属于不同的类别，为简单起见，每个实体在世界中属于不同的类别，为简单起见，每个实体在世界中属于不同的类别，为简单起见，假定仅有两个类别，分别为假定仅有两个类别，分别为假定仅有两个类别，分别为假定仅有两个类别，分别为P P P P、N N N N。在这种两个类。在这种两

4、个类。在这种两个类。在这种两个类别的归纳任务中，别的归纳任务中，别的归纳任务中，别的归纳任务中，P P P P类和类和类和类和N N N N类的实体类的实体类的实体类的实体分别称为概念分别称为概念分别称为概念分别称为概念的的的的正例和反例正例和反例正例和反例正例和反例。将一些已知正例和反例放在一起。将一些已知正例和反例放在一起。将一些已知正例和反例放在一起。将一些已知正例和反例放在一起便得到便得到便得到便得到训练集训练集训练集训练集。表表表表1 1 1 1给给给给出出出出一一一一个个个个训训训训练练练练集集集集表表表表1 1气候训练集气候训练集气候训练集气候训练集 由由由由ID3ID3ID3I

5、D3算算算算法法法法得得得得出出出出一一一一棵棵棵棵正正正正确确确确分分分分类类类类训训训训练练练练集集集集中中中中每每每每个个个个实实实实体体体体的的的的决决决决策策策策树，如图树，如图树，如图树，如图1 1 1 1所示所示所示所示晴晴多云多云雨雨P高高正常正常PNNP有风有风无风无风湿度湿度风风天气天气图图1 ID3决策树决策树 得到决策树叶子为类别名，即得到决策树叶子为类别名，即P P或者或者N N。其他结点由实体的属性组成，每个属性的其他结点由实体的属性组成，每个属性的不同取值对应一分支。若要对一实体分类，不同取值对应一分支。若要对一实体分类，从树根开始进行测试，按属性的取值分支从树根

6、开始进行测试，按属性的取值分支向下进入下层结点，对该结点进行测试，向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。现用该叶结点所标记的类别。现用图图1 1来判断本来判断本例，得到该实体的类别为例，得到该实体的类别为P P类。类。ID3ID3就是要就是要从从表表1 1的训练集构造出如的训练集构造出如图图1 1所示的决策树。所示的决策树。晴晴多云多云雨雨P高高正常正常PNNP有风有风无风无风湿度湿度风风天气天气图图1实际上，能正确分类训练集的决策树不止一棵。实际上，能正确分类训练集的决策树不止一棵。Quinlan的的

7、ID3算法能得出结点最少的决策树。算法能得出结点最少的决策树。ID3算法分为两种：主算法和建树算法。1主算法主算法的操作步骤如下：（1）从训练集中随机选择一个既含正例又含反例的子集（称为“窗口”）。（2）用“建树算法”对当前窗口形成一棵决策树。（3）对训练集（窗口除外）中的例子用所得决策树进行类别判定，找出错判的例子。（4）若存在错判的例子，把它们插入窗口，转2，否则结束。PN多云 (12)雨 (14)风有风(2,6,7,11,12,14)温度高 (2,12,14)正常 (6,7,11)气温气温N热 (2)适中 (12,14)天气P适中 (11)冷 (6,7)NP多云 (6)雨 (7)天气高

8、(1,3,4,8)无风(1,3,4,5,8,9,10,13)正常 (5,9,10,13)适中 (4,8)P热 (1,3)PNPN晴 (1)多云 (3)晴 (8)雨 (4)温度气温天气天气图图2决策树决策树2建树算法建树算法的操作步骤如下：（1）对当前例子集合，计算各属性的互信息。（2）选择互信息最大的属性Ak（3）把在Ak处取值相同的例子归同一子集，取几个值就得几个子集。（4）对既含正例又含反例的子集，递归调用建树算法。（5）若子集仅含正例或反例，对应分支标上P或N，返回调用处。对于气候分类问题进行以下具体计算。对于气候分类问题进行以下具体计算。对于气候分类问题进行以下具体计算。对于气候分类问

9、题进行以下具体计算。1 1 1 1、信息熵计算、信息熵计算、信息熵计算、信息熵计算：类别类别类别类别u u u ui i i i出现概率出现概率出现概率出现概率：|S|S|S|S|表示例子集表示例子集表示例子集表示例子集S S S S的总数，的总数，的总数，的总数，|u|u|u|ui i i i|表示类别表示类别表示类别表示类别 u u u ui i i i的例子数。的例子数。的例子数。的例子数。对对对对9 9 9 9个正例个正例个正例个正例u1u1u1u1和和和和5 5 5 5个反例个反例个反例个反例u2u2u2u2有：有：有：有：2 2 2 2条件熵计算条件熵计算条件熵计算条件熵计算条件熵

10、：条件熵：条件熵：条件熵：属性属性属性属性A A A A1 1 1 1取值取值取值取值v v v vj j j j时，类别时，类别时，类别时，类别u u u ui i i i的条件概率：的条件概率：的条件概率：的条件概率：A A A A1 1 1 1天气的取值：天气的取值：天气的取值：天气的取值：v v v v1 1 1 1晴，晴，晴，晴，v v v v2 2 2 2多云，多云，多云，多云，v v v v3 3 3 3雨雨雨雨在在在在A1A1A1A1处取值处取值处取值处取值“晴晴晴晴”的例子的例子的例子的例子5 5 5 5个，取值个，取值个，取值个，取值“多云多云多云多云”的例的例的例的例子子

11、子子4 4 4 4个，取值个，取值个，取值个，取值“雨雨雨雨”的例子的例子的例子的例子5 5 5 5个，故：个，故：个，故：个，故：取值为晴的取值为晴的取值为晴的取值为晴的5 5 5 5个例子中有两个正例、个例子中有两个正例、个例子中有两个正例、个例子中有两个正例、3 3 3 3个反例，个反例，个反例，个反例，故：故：故：故：同理有：同理有：同理有：同理有：3 3 3 3互信息计算互信息计算互信息计算互信息计算对对对对A1A1A1A1天气，有：天气，有：天气，有：天气，有：类似可得：类似可得：类似可得：类似可得：I I I I（气温）（气温）（气温）（气温）0.029bit0.029bit0.

12、029bit0.029bitI I I I（湿度）（湿度）（湿度）（湿度）0.151bit0.151bit0.151bit0.151bitI I I I（风）（风）（风）（风）0.048bit0.048bit0.048bit0.048bit4 4 4 4建决策树的树根和分支建决策树的树根和分支建决策树的树根和分支建决策树的树根和分支ID3ID3ID3ID3算法将选择互信息最大的属性算法将选择互信息最大的属性算法将选择互信息最大的属性算法将选择互信息最大的属性“天气天气天气天气”作为树作为树作为树作为树根，在根，在根，在根，在14141414个例子中对个例子中对个例子中对个例子中对“天气天气天气

13、天气”的的的的3 3 3 3个取值进行分支，个取值进行分支，个取值进行分支，个取值进行分支，3 3 3 3个分支对应个分支对应个分支对应个分支对应3 3 3 3个子集，分别是：个子集，分别是：个子集，分别是：个子集，分别是：F1F1F1F11 1 1 1，2 2 2 2，8 8 8 8，9 9 9 9，11111111，F2F2F2F23 3 3 3，7 7 7 7，12121212，13131313，F3F3F3F34 4 4 4，5 5 5 5，6 6 6 6，10101010，14141414其中，其中，其中，其中，F2F2F2F2中的例子全属于中的例子全属于中的例子全属于中的例子全属于

14、P P P P类，因此对应分支标记类，因此对应分支标记类，因此对应分支标记类，因此对应分支标记为为为为P P P P，其余两个子集既含有正例其余两个子集既含有正例其余两个子集既含有正例其余两个子集既含有正例P P P P又含有反例，将又含有反例，将又含有反例，将又含有反例，将递归调用建树算法。递归调用建树算法。递归调用建树算法。递归调用建树算法。5 5 5 5递归建树递归建树递归建树递归建树分别对分别对分别对分别对F1F1F1F1和和和和F3F3F3F3子集利用子集利用子集利用子集利用ID3ID3ID3ID3算法，在每个子集中对算法，在每个子集中对算法，在每个子集中对算法，在每个子集中对各属性

15、（仍为各属性（仍为各属性（仍为各属性（仍为4 4 4 4个属性）求互信息。个属性）求互信息。个属性）求互信息。个属性）求互信息。（1 1 1 1）F1F1F1F1中的天气全取中的天气全取中的天气全取中的天气全取“晴晴晴晴”值，则值，则值，则值，则H H H H（U U U U）H H H H（U U U UV V V V），有），有），有），有I I I I（U U U UV V V V）0 0 0 0，在余下在余下在余下在余下3 3 3 3个属性中求出个属性中求出个属性中求出个属性中求出“湿度湿度湿度湿度”互信息最大，以它互信息最大，以它互信息最大，以它互信息最大，以它为该分支的根结点。再向

16、下分支，为该分支的根结点。再向下分支，为该分支的根结点。再向下分支，为该分支的根结点。再向下分支，“湿度湿度湿度湿度”取取取取“高高高高”的例子全为的例子全为的例子全为的例子全为N N N N类，该分支标记类，该分支标记类，该分支标记类，该分支标记N N N N；取值；取值；取值；取值“正常正常正常正常”的例子全为的例子全为的例子全为的例子全为P P P P类，该分支标记类，该分支标记类，该分支标记类，该分支标记P P P P。晴晴多云多云雨雨P高高正常正常PNNP有有风风无无风风湿度湿度风风天气天气图图1（2 2 2 2）在在在在F3F3F3F3中，对中，对中，对中，对4 4 4 4个属性求

17、互信息，得到个属性求互信息，得到个属性求互信息，得到个属性求互信息，得到“风风风风”属性互信息最大，则以它为该分支的根结点。再属性互信息最大，则以它为该分支的根结点。再属性互信息最大，则以它为该分支的根结点。再属性互信息最大，则以它为该分支的根结点。再向下分支，向下分支，向下分支，向下分支，“风风风风”取取取取“有风有风有风有风”时全为时全为时全为时全为N N N N类，该分支类，该分支类，该分支类，该分支标记标记标记标记N N N N；取；取；取；取“无风无风无风无风”时全为时全为时全为时全为P P P P类，该分支标记类，该分支标记类，该分支标记类，该分支标记P P P P。这样就得到如这样就得到如这样就得到如这样就得到如图图1所示的决策树。所示的决策树。所示的决策树。所示的决策树。ID3算法的缺点：1只适合属性值为离散的；2决策树层次较多时，决策质量低；3倾向于选择取值较多的属性；H(V)1.00.501.0P