第7章：数据挖掘的决策支持.pptVIP

数据挖掘的兴起 2、ID3算法 2、ID3算法 2、ID3算法 2、ID3算法 2、ID3算法 7.2 决策树及其应用 1、决策树概念： 决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。 数据挖掘的决策树方法的原理是信息论，信息论是C.E.Shannon为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。 一个传递信息的系统是由发送端（信源）和接收端（信宿）以及连接两者的通道（信道）三者组成。 7.2 决策树及其应用 信息论把通信过程看做是在随机干扰的环境中传递信息的过程。在这个通信模型中，信息源和干扰（噪声）都被理解为某种随机过程或随机序列。 7.2 决策树及其应用 在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。这种情形就称为信宿对于信源状态具有不确定性。而且这种不确定性是存在于通信之前的。因而又叫做先验不确定性。 在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。 如果干扰很小，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。 7.2 决策树及其应用 在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。因此，先验不确定性不能全部被消除，只能部分地消除。 通信结束之后，信宿还仍然具有一定程度的不确定性。这就是后验不确定性。 显然，后验不确定性总要小于先验不确定性，不可能大于先验不确定性。 7.2 决策树及其应用 如果后验不确定性的大小正好等于先验不确定性的大小，这就表示信宿根本没有收到信息。 如果后验不确定性的大小等于零，这就表示信宿收到了全部信息。 可见，信息是用来消除（随机）不确定性的度量。信息量的大小，由所消除的不确定性的大小来计量。 7.2 决策树及其应用 当前国际上最有影响的示例学习方法首推J.R.Quinlan的ID3。 ID3引进了信息论中的互信息，他将其称为信息增益（information gain），作为特征判别能力的度量，并且将建树的方法嵌在一个迭代的中。 某天早晨气候描述为: 天气： 多云 气温： 冷 湿度： 正常 风： 无风 在一实体世界中，每个实体用多个特征来描述。每个特征限于在一个离散集中取互斥的值。例如，设实体是某天早晨，分类任务是关于气候的类型，特征为: 天气 取值为： 晴，多云，雨 气温 取值为： 冷 ，适中，热 湿度 取值为： 高 ，正常 风 取值为： 有风， 无风 它属于哪类气候呢? 每个实体属于不同的类别，为简单起见，假定仅有两个类别，分别为P，N。在这种两个类别的归纳任务中，P类和N类的实体分别称为概念的正例和反例。 将一些已知的正例和反例放在一起便得到训练集。 下表给出一个训练集。由ID3算法得出一棵正确分类训练集中每个实体的决策树，见图。 N 有风 高 适中 雨 14 P 无风 正常 热 多云 13 P 有风 高 适中 多云 12 P 有风 正常 适中 晴 11 P 无风 正常 适中 雨 10 P 无风 正常 冷 晴 9 N 无风 高 适中 晴 8 P 有风 正常 冷 多云 7 N 有风 正常 冷 雨 6 P 无风 正常 冷 雨 5 P 无风 高 适中 雨 4 P 无风 高 热 多云 3 N 有风 高 热 晴 2 N 无风 高 热 晴 1 风 湿度 气温 天气 类别 属性 NO. 天 气 湿 度 风 晴 雨 多云 高 正常 有风 无风 P N N P P ID3决策树 决策树叶子为类别名，即P 或者N。其它结点由实体的特征组成，每个特征的不同取值对应一分枝。 若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。 * * 第7章 数据挖掘的决策支持 7.1 知识发现与数据挖掘 7.2 数据挖掘的决策支持及应用 （1）80年 美国 第一届国际机器学习研讨会； （2）89年 美国 第一届知识发现国际学术会议； （3）95年 加拿大 第一届知识发现和数据挖掘国际学术会议； （4）我国 87年 第一届全国机器学习研讨会。 7.1 知识发现与数据挖掘 7.1.1 知识发现与数据挖掘概念 知识发现（KDD） 从数据中发现有用知识的整个过程。 数据挖掘（DM） KDD过程中的一个特定步骤，它用专门算法从数据中抽取模式。 7.1.1 知识发现与数据挖掘概念 KDD过程定义： 从大量数据中提取出可信的、