第5章：数据仓库与数据挖掘的决策支持(3).ppt

《第5章：数据仓库与数据挖掘的决策支持(3).ppt》由会员分享，可在线阅读，更多相关《第5章：数据仓库与数据挖掘的决策支持(3).ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、LOGO决策支持系统及其开发主讲教师：唐晶磊主讲教师：唐晶磊E-mail:Tel:87091337(O)2022/12/20信息分析与决策支持 唐晶磊 5.5 5.5 知识发现与数据挖掘知识发现与数据挖掘 5.6 5.6 数据挖掘的决策支持及应用数据挖掘的决策支持及应用2022/12/20信息分析与决策支持 唐晶磊DWDW的兴起的兴起的兴起的兴起（1 1）8080年在美国召开了年在美国召开了第一届国际机器学习第一届国际机器学习研讨会；研讨会；（2 2）8989年年8 8月月,美国底特律市召开的美国底特律市召开的第一届第一届KDDKDD国际学术会议；国际学术会议；（3 3）9595年年,加拿大召

2、开了加拿大召开了第一届第一届KDDKDD和和DMDM国际学术会议；国际学术会议；（4 4）我国于）我国于8787年召开了年召开了第一届全国机器学习第一届全国机器学习研讨会。研讨会。5.5 知识发现与数据挖掘知识发现与数据挖掘2022/12/20信息分析与决策支持 唐晶磊5.5.1 5.5.1 知识发现与数据挖掘概念知识发现与数据挖掘概念知识发现（知识发现（Knowledge discovery in database）：从数据中发现从数据中发现有用知识有用知识的整个过程的整个过程(KDD)。KDD过程过程定义定义:从从数据集数据集中识别出中识别出有效的、新颖的、潜在有用有效的、新颖的、潜在有用

3、的，的，以及最终可理解的以及最终可理解的模式模式的高级处理过程。的高级处理过程。“模式模式”即是即是“知识知识”的雏形，需经过验证、完善的雏形，需经过验证、完善(模式评价模式评价)后后形成知识。形成知识。KDD过程过程概括：概括：数据准备数据准备(data preparation)、数据挖掘数据挖掘(data mining)及及结果的解释和评估结果的解释和评估(interpretation&evaluation)。2022/12/20信息分析与决策支持 唐晶磊5.5.1 5.5.1 知识发现与数据挖掘概念知识发现与数据挖掘概念问题：所有企业都面临企业数据量巨大，而其中真正有价值的问题：所有企业

4、都面临企业数据量巨大，而其中真正有价值的信息却很少。信息却很少。解决方法：对大量的数据进行深层分析，获得有利于商业运作、解决方法：对大量的数据进行深层分析，获得有利于商业运作、提高竞争力的信息。提高竞争力的信息。数据挖掘（数据挖掘（DM）：KDD过程中的一个特定步骤，它用专门算过程中的一个特定步骤，它用专门算 法从数据中抽取模式（法从数据中抽取模式（patterns）。）。数据挖掘是一门交叉学科，涉及数据库技术、人工智能技术、数据挖掘是一门交叉学科，涉及数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面。数理统计、可视化技术、并行计算等方面。2022/12/20信息分析与决策支持

5、唐晶磊5.5.1 5.5.1 知识发现与数据挖掘概念知识发现与数据挖掘概念（1）DM（技术角度）（技术角度）：从大量的、不完全的、有噪声的、：从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、事模糊的、随机的实际应用数据中，提取隐含在其中的、事先不知道的、但又是潜在先不知道的、但又是潜在有用的信息和知识有用的信息和知识的过程。即从的过程。即从数据源数据源发现用户感兴趣的知识，发现用户感兴趣的知识，知识知识要可接受、可以理解要可接受、可以理解和运用；和运用；2022/12/20信息分析与决策支持 唐晶磊5.5.1 5.5.1 知识发现与数据挖掘概念知识发现与数据挖掘概

6、念（2）（）（DM）商业角度）商业角度：是一种新的、商业信息处理技术。：是一种新的、商业信息处理技术。对商业数据库中的大量业务数据进行抽取、转换、分析和其对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。他模型化处理，从中提取辅助商业决策的关键性数据。数据挖掘是一种数据挖掘是一种深层次的数据分析方法。深层次的数据分析方法。2022/12/20信息分析与决策支持 唐晶磊5.5.1 5.5.1 知识发现与数据挖掘概念知识发现与数据挖掘概念（3）(DM)企业角度企业角度：按企业既定业务目标，对大量的企业：按企业既定业务目标，对大量的企业数据进行探索和

7、分析，揭示隐藏的、未知的或验证已知的规数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效方法。律性，并进一步将其模型化的先进有效方法。2022/12/20信息分析与决策支持 唐晶磊数据源数据源数据数据数据集成数据集成目标数据目标数据预处理预处理数据数据转换数据转换数据模式模式知识知识数据选择数据选择预处理预处理数据挖掘数据挖掘转换转换结果表达和解释结果表达和解释KDDKDD过程过程数据准备数据准备数据挖掘数据挖掘结果解释和评估结果解释和评估2022/12/20信息分析与决策支持 唐晶磊v数据准备：数据准备：数据选择数据选择(data selection)、数

8、据预处理数据预处理(data preprocessing)和和数据转换数据转换(data transformation)。v数据选择：数据选择：确定操作对象，即目标数据确定操作对象，即目标数据(target data)，是，是根据用户的需要，从原始根据用户的需要，从原始DB中选取的一组数据。中选取的一组数据。v数据预处理：数据预处理：消除噪声、处理缺值数据、消除重复记录等。消除噪声、处理缺值数据、消除重复记录等。v数据转换：数据转换：完成数据完成数据类型转换类型转换，进行，进行属性约简属性约简（从初始属（从初始属性中找出真正有用的属性，删除无用属性，以减少数据挖掘性中找出真正有用的属性，删除无

9、用属性，以减少数据挖掘时要考虑的属性个数）。时要考虑的属性个数）。数据准备数据准备2022/12/20信息分析与决策支持 唐晶磊数据挖掘数据挖掘v数据挖掘数据挖掘（1）首先确定挖掘的任务或目的；）首先确定挖掘的任务或目的；（2）确定使用何种挖掘算法。）确定使用何种挖掘算法。v选择挖掘算法需考虑选择挖掘算法需考虑2个因素：个因素：不同数据具有不同特点，需要用与之相关的算法来挖掘；不同数据具有不同特点，需要用与之相关的算法来挖掘；考虑用户或实际运行系统的要求。如用户可能希望考虑用户或实际运行系统的要求。如用户可能希望获取描获取描述性的、容易理解的知识述性的、容易理解的知识，或者希望获取预测准确度更

10、可，或者希望获取预测准确度更可能高能高预测型知识预测型知识。2022/12/20信息分析与决策支持 唐晶磊结果的解释和评估结果的解释和评估v结果的解释和评估（模式评价）结果的解释和评估（模式评价）（1）经过评估，剔除冗余或无关的模式；）经过评估，剔除冗余或无关的模式；（2）不满足用户要求的模式，需回退到）不满足用户要求的模式，需回退到KDD过程的前面阶段。过程的前面阶段。（3）KDD是面向用户的，一般需对发现的模式进行可视化处是面向用户的，一般需对发现的模式进行可视化处理，或把结果转换为用户易懂的表示形式。理，或把结果转换为用户易懂的表示形式。vDM质量好坏的质量好坏的2个影响因素：个影响因素

11、：（1）所采用的）所采用的DM技术的有效性；技术的有效性；（2）用于挖掘的数据的质量和数量（数据量的大小）。）用于挖掘的数据的质量和数量（数据量的大小）。2022/12/20信息分析与决策支持 唐晶磊数据挖掘任务数据挖掘任务vDM任务有六项：任务有六项：（1）关联分析）关联分析 若两个或多个数据项的取值重复出现，且概率很高时，若两个或多个数据项的取值重复出现，且概率很高时，它就存在某种关联，它就存在某种关联，则可建立起这些数据项的关联规则。则可建立起这些数据项的关联规则。（2）时序模式）时序模式 通过时间序列，搜索出通过时间序列，搜索出重复发生概率较高的模式。重复发生概率较高的模式。（3）聚类

12、（通过聚类建立宏观概念）聚类（通过聚类建立宏观概念）有统计分析方法、机器学习方法、神经网络方法等。有统计分析方法、机器学习方法、神经网络方法等。2022/12/20信息分析与决策支持 唐晶磊数据挖掘任务数据挖掘任务（4）分类：以聚类为基础，对已确定的类找出该类别的概念）分类：以聚类为基础，对已确定的类找出该类别的概念描述。它代表此类数据的整体信息（内涵描述）。描述。它代表此类数据的整体信息（内涵描述）。内涵描述内涵描述分为分为特征描述特征描述和和辨别性描述辨别性描述。判别分类方法的判别分类方法的3个标准：个标准：预测准确度预测准确度、计算复杂度计算复杂度、模式的模式的简洁度简洁度。（5）偏差检

13、测：寻找观察结果与）偏差检测：寻找观察结果与DB中参照数据之间的差别。中参照数据之间的差别。（6）预测：利用历史数据找出变化规律，建立模型，并用此）预测：利用历史数据找出变化规律，建立模型，并用此模型来预测未来数据的种类、特征等。模型来预测未来数据的种类、特征等。2022/12/20信息分析与决策支持 唐晶磊属性约简属性约简v属性约简常用于分类问题属性约简常用于分类问题原则：原则：保持数据库中分类关系不变。保持数据库中分类关系不变。一般采用一般采用粗糙集粗糙集(rough set)方法，也可采用方法，也可采用信息论信息论方法。方法。v在在DB的分类问题中，属性分为条件属性的分类问题中，属性分为

14、条件属性(C)和决策属性和决策属性(D)。条件属性分为条件属性分为可省略属性可省略属性和不可省略属性。和不可省略属性。v属性约简是在属性约简是在条件属性条件属性中，删除不影响中，删除不影响对决策属性进行分类对决策属性进行分类的多余的条件属性。的多余的条件属性。v不可省略属性，实质上是对决策属性进行分类的核心属性。不可省略属性，实质上是对决策属性进行分类的核心属性。2022/12/20信息分析与决策支持 唐晶磊补充：数据挖掘与传统分析方法的区别补充：数据挖掘与传统分析方法的区别v传统的数据分析方法：查询、报表和联机分析等。传统的数据分析方法：查询、报表和联机分析等。v采用完全不同的工具，基于的技

15、术差别也很大。采用完全不同的工具，基于的技术差别也很大。（1）查询和报表，告诉决策者数据库中都有什么。）查询和报表，告诉决策者数据库中都有什么。（2）OLAP会进一步告诉决策者，下一步会怎么样，会进一步告诉决策者，下一步会怎么样，（假设假设）如果我采用这样的措施，又会怎么样。）如果我采用这样的措施，又会怎么样。OLAP通通过建立一系列的假设，来证实或推翻这些假设，以得到合过建立一系列的假设，来证实或推翻这些假设，以得到合理的结论。因此，理的结论。因此，OLAP本质上是本质上是演绎推理过程。演绎推理过程。2022/12/20信息分析与决策支持 唐晶磊补充：数据挖掘与联机分析处理的区别补充：数据挖

16、掘与联机分析处理的区别vDM在没有明确假设的前提下去挖掘信息、发现知识。在没有明确假设的前提下去挖掘信息、发现知识。vDM所得到的信息是所得到的信息是先前未知、先前未知、有效的和可实用的。有效的和可实用的。v数据挖掘不用于验证某个假定的模式，而是在数据库中自己数据挖掘不用于验证某个假定的模式，而是在数据库中自己寻找模型。本质是一个归纳的过程。寻找模型。本质是一个归纳的过程。vDM和和OLAP具有一定的互补性。具有一定的互补性。v在利用在利用DM出来的结论采取行动之前，利用出来的结论采取行动之前，利用OLAP验证一下，验证一下，如果采取这样的行动，将会给公司带来什么样的影响。如果采取这样的行动，

17、将会给公司带来什么样的影响。2022/12/20信息分析与决策支持 唐晶磊5.5.2 5.5.2 数据挖掘方法和技术数据挖掘方法和技术vDM方法由人工智能、机器学习的方法发展而来。结方法由人工智能、机器学习的方法发展而来。结合传统的统计分析方法、模糊数学方法以及计算科合传统的统计分析方法、模糊数学方法以及计算科学可视化技术，以数据库为研究对象，形成了数据学可视化技术，以数据库为研究对象，形成了数据挖掘方法和技术。挖掘方法和技术。v数据挖掘方法和技术可以分为六大类。数据挖掘方法和技术可以分为六大类。2022/12/20信息分析与决策支持 唐晶磊5.5.2 5.5.2 数据挖掘方法和技术数据挖掘方

18、法和技术（一）归纳学习方法（一）归纳学习方法按采用的技术可分为信息论方法（决策树方法）和集合论方法。按采用的技术可分为信息论方法（决策树方法）和集合论方法。1 1、信息论方法（决策树方法）、信息论方法（决策树方法）利用信息论的原理建立决策树或者决策规则树。利用信息论的原理建立决策树或者决策规则树。较有特色的方法有：较有特色的方法有：（1）ID3等方法（决策树方法）等方法（决策树方法）（2）IBLE（决策规则树）方法。（决策规则树）方法。2022/12/20信息分析与决策支持 唐晶磊2 2、集合论方法、集合论方法 （1 1）粗糙集（）粗糙集（Rough SetRough Set）方法方法对对数数

19、据据库库中中的的条条件件属属性性集集与与决决策策属属性性集集建建立立上上下下近近似似关关系系，对对下下近近似似集集合合建建立立确确定定性性规规则则，对对上上近近似似集集合合建建立立不不确确定定性性规规则则（含含可可信信度）。度）。（2 2）关联规则挖掘）关联规则挖掘在在交交易易事事务务数数据据库库中中，挖挖掘掘出出不不同同商商品品集集的的关关联联关关系系，即即发发现现哪哪些些商品频繁地被顾客同时购买。商品频繁地被顾客同时购买。（3 3）覆盖正例排斥反例方法）覆盖正例排斥反例方法它是利用它是利用覆盖所有正例覆盖所有正例，排斥所有反例排斥所有反例的思想来寻找规则。较典型的思想来寻找规则。较典型的有

20、的有AQ11AQ11方法、方法、AQ15AQ15方法及方法及AE5AE5方法。方法。2022/12/20信息分析与决策支持 唐晶磊 （二）仿生物技术（二）仿生物技术 典型的仿生物技术方法是神经网络方法和遗传算法。典型的仿生物技术方法是神经网络方法和遗传算法。1 1、神经网络方法：、神经网络方法：包括：前馈式网络、反馈式网络、自包括：前馈式网络、反馈式网络、自组织网络等多个神经网络方法。组织网络等多个神经网络方法。2 2、遗传算法：、遗传算法：模拟生物进化过程的算法。它由三个基本模拟生物进化过程的算法。它由三个基本算子组成：算子组成：繁殖（选择）、交叉（重组）、变异（突变）繁殖（选择）、交叉（重

21、组）、变异（突变）遗传算法起到产生优良后代的作用，经过若干代的遗传，遗传算法起到产生优良后代的作用，经过若干代的遗传，将得到满足要求的后代（问题的解）。将得到满足要求的后代（问题的解）。2022/12/20信息分析与决策支持 唐晶磊（三）公式发现（三）公式发现 在工程和科学数据库中对若干数据项（变量）在工程和科学数据库中对若干数据项（变量）进行一定进行一定的数学运算，求得相应的数学公式。的数学运算，求得相应的数学公式。1 1物理定律发现系统物理定律发现系统BACONBACON BACONBACON发现系统完成了物理学中大量定律的重新发现。发现系统完成了物理学中大量定律的重新发现。2 2经验公式

22、发现系统经验公式发现系统FDDFDD 寻找由数据项的初等函数或复合函数组合成的经验公式。寻找由数据项的初等函数或复合函数组合成的经验公式。2022/12/20信息分析与决策支持 唐晶磊（四）统计分析方法（四）统计分析方法 利用统计学原理对总体中的样本数据进行分析，得出描利用统计学原理对总体中的样本数据进行分析，得出描述和推断该总体信息和知识的方法。述和推断该总体信息和知识的方法。（五）模糊数学方法（五）模糊数学方法 利用模糊集合理论进行数据挖掘，如模糊聚类、模糊分利用模糊集合理论进行数据挖掘，如模糊聚类、模糊分类等。类等。（六）可视化技术（六）可视化技术 利用可视化技术分析数据库，找到潜在的有

23、用信息。利用可视化技术分析数据库，找到潜在的有用信息。2022/12/20信息分析与决策支持 唐晶磊5.5.3 5.5.3 数据挖掘的知识表示（一）数据挖掘的知识表示（一）DM获取知识表示形式主要有六种：获取知识表示形式主要有六种：规则、决策树、浓缩数据、网络权值、公式和案例。规则、决策树、浓缩数据、网络权值、公式和案例。1、规则、规则 规则知识由规则知识由前提条件前提条件和和结论结论两部分组成两部分组成 前前 提提 条条 件件 由由 字字 段段 项项（属属 性性）的的 取取 值值 的的 合合 取取（与与 ）和析取（或和析取（或）组合而成。）组合而成。结论结论为决策字段项（属性）的取值或者类别

24、组成。为决策字段项（属性）的取值或者类别组成。2022/12/20信息分析与决策支持 唐晶磊5.5.3 5.5.3 数据挖掘的知识表示（一）数据挖掘的知识表示（一）2022/12/20信息分析与决策支持 唐晶磊2、决策树、决策树例如：上例的人群数据库，按例如：上例的人群数据库，按ID3ID3方法得到的决策树如下：方法得到的决策树如下：数据挖掘的知识表示（二）数据挖掘的知识表示（二）2022/12/20信息分析与决策支持 唐晶磊 3、知识基（浓缩数据）、知识基（浓缩数据）例如上例的人群数据库，通过计算可得出例如上例的人群数据库，通过计算可得出身高身高是不重要的字段，是不重要的字段，删除它后，再删

25、除它后，再合并相同数据元组合并相同数据元组，得到浓缩数据如下表：，得到浓缩数据如下表：数据挖掘的知识表示（三）数据挖掘的知识表示（三）2022/12/20信息分析与决策支持 唐晶磊 4、网络权值、网络权值 神经网络方法经过对神经网络方法经过对训练样本训练样本的学习后，的学习后，所得到的知所得到的知识识是网络是网络连接权值连接权值和和结点的阈值结点的阈值。数据挖掘的知识表示（四）数据挖掘的知识表示（四）Zy2x1 x2 1y1 T1 T2 w12 w21w11 w22 2 ,=0.52022/12/20信息分析与决策支持 唐晶磊 5、公式、公式 例如，太阳系行星运动数据中包含行星运动周期（旋转一

26、周例如，太阳系行星运动数据中包含行星运动周期（旋转一周所需时间，天），以及它与太阳的距离（围绕太阳旋转的椭圆轨所需时间，天），以及它与太阳的距离（围绕太阳旋转的椭圆轨道的长半轴，百万公里），数据如下表：道的长半轴，百万公里），数据如下表：通过物理定律发现系统通过物理定律发现系统BACON和经验公式发现系统和经验公式发现系统FDD，都，都可得到开普勒第三定律：可得到开普勒第三定律：d3/p2=25数据挖掘的知识表示（五）数据挖掘的知识表示（五）2022/12/20信息分析与决策支持 唐晶磊5.6 5.6 数据挖掘的决策支持及应用数据挖掘的决策支持及应用5.6.5.6.1 1 决策树及其应用决策树

27、及其应用1 1、决策树概念：、决策树概念：用样本的用样本的属性属性作为结点，用属性的作为结点，用属性的取值取值作为分支的树结作为分支的树结构。利用构。利用信息论原理信息论原理对大量样本的属性进行分析和归纳。对大量样本的属性进行分析和归纳。决策树的决策树的根结点根结点是所有样本中信息量最大的是所有样本中信息量最大的属性。属性。中间结点中间结点是以该结点为根的子树，所包含的是以该结点为根的子树，所包含的样本子集样本子集中中信息量最大的信息量最大的属性。属性。叶结点叶结点是样本的是样本的类别值类别值。2022/12/20信息分析与决策支持 唐晶磊5.6 5.6 数据挖掘的决策支持及应用数据挖掘的决策

28、支持及应用决策树用于对新样本的分类：通过决策树对新样本决策树用于对新样本的分类：通过决策树对新样本属性属性值值的测试，从树的根结点开始，按照的测试，从树的根结点开始，按照样本属性的取值样本属性的取值，逐渐沿着决策树向下，直到树的叶结点，逐渐沿着决策树向下，直到树的叶结点，该叶结点表示该叶结点表示的类别就是新样本的类别。的类别就是新样本的类别。2022/12/20信息分析与决策支持 唐晶磊nDMDM的的决策树方法的原理是决策树方法的原理是信息论信息论。信息论是信息论是C.E.ShannonC.E.Shannon为解决信息传递（通信）过程问题而建立的理论，也称为解决信息传递（通信）过程问题而建立的

29、理论，也称为为统计通信理论统计通信理论。n传递信息的系统是由传递信息的系统是由发送端（信源）发送端（信源）和和接收端（信宿）接收端（信宿）以以及连接两者的及连接两者的通道（信道）通道（信道）三者组成。三者组成。n信息论把通信过程看做在信息论把通信过程看做在随机干扰的环境中传递信息的过随机干扰的环境中传递信息的过程。程。在这个通信模型中，信息源和干扰（噪声）都被理在这个通信模型中，信息源和干扰（噪声）都被理解为某种解为某种随机过程或随机序列。随机过程或随机序列。补充内容补充内容2022/12/20信息分析与决策支持 唐晶磊n在进行实际在进行实际通信之前通信之前，收信者（信宿）不可能确切了解，收信

30、者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。处于什么样的状态。n此情形称为此情形称为信宿对于信源状态具有不确定性。这种信宿对于信源状态具有不确定性。这种不确不确定性存在通信之前的，又叫做定性存在通信之前的，又叫做先验不确定性先验不确定性。n通信之后，信宿收到了信源发来的信息，这种通信之后，信宿收到了信源发来的信息，这种先验不确先验不确定性才会被消除或者被减少定性才会被消除或者被减少。n如果如果干扰很小干扰很小，信源发出的信息能够被信宿全部收到。，信源发出的信息能够被信宿全部收到。此种情况下，信宿的先验

31、不确定性就会被此种情况下，信宿的先验不确定性就会被完全消除。完全消除。补充内容补充内容2022/12/20信息分析与决策支持 唐晶磊n一般情况下，干扰总会对信源发出的信息造成某种破坏，一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。因此，使信宿收到的信息不完全。因此，先验不确定性不能全先验不确定性不能全部被消除，只能部分地消除。部被消除，只能部分地消除。n通信结束之后，信宿还仍然具有一定程度的不确定性。通信结束之后，信宿还仍然具有一定程度的不确定性。这就是这就是后验不确定性后验不确定性。n显然，后验不确定性总要小于先验不确定性，不可能大显然，后验不确定性总要小于先验不

32、确定性，不可能大于先验不确定性。于先验不确定性。补充内容补充内容2022/12/20信息分析与决策支持 唐晶磊n如果如果后验不确定性的大小后验不确定性的大小正好正好等于等于先验不确定性的大小，先验不确定性的大小，表示信宿根本没有收到信息。表示信宿根本没有收到信息。n如果后验不确定性的大小等于零，表示信宿收到了全部如果后验不确定性的大小等于零，表示信宿收到了全部信息。信息。n因此，因此，信息是用来信息是用来消除（随机）不确定性消除（随机）不确定性的度量。的度量。信息信息量的大小，由所消除的不确定性的大小来计量。量的大小，由所消除的不确定性的大小来计量。2022/12/20信息分析与决策支持 唐晶

33、磊2 2、ID3ID3算法算法n当前国际上最有影响的示例学习方法首推当前国际上最有影响的示例学习方法首推ID3ID3。nID3ID3引进了信息论中的引进了信息论中的互信息互信息(信息增益信息增益 information information gaingain），），作为特征作为特征(属性属性)判别能力的度量，且将判别能力的度量，且将建树的建树的方法方法嵌在一个迭代的外壳之中。嵌在一个迭代的外壳之中。2022/12/20信息分析与决策支持 唐晶磊ID3ID3基本思想基本思想每个实体用每个实体用多个特征多个特征来描述，每个特征限于在一个来描述，每个特征限于在一个离散离散集集中取中取互斥的值互斥的

34、值。例如，设实体是某天早晨，分类任务。例如，设实体是某天早晨，分类任务是关于是关于气候的类型，有气候的类型，有4 4各各特征（属性）为特征（属性）为:天气天气 取值为：取值为：晴，多云，雨晴，多云，雨 气温气温 取值为：取值为：冷冷 ，适中，热，适中，热 湿度湿度 取值为：取值为：高高 ，正常，正常 风风 取值为：取值为：有风，有风，无风无风某天早晨（实体）气候描述为某天早晨（实体）气候描述为:天气天气：多云多云 气温气温：冷冷 湿度湿度：正常正常 风风：无风无风2022/12/20信息分析与决策支持 唐晶磊n判断此实体属于哪类气候类别判断此实体属于哪类气候类别?n假定仅有两个类别，分别为假定

35、仅有两个类别，分别为P P，N N。两个类别的归纳任务两个类别的归纳任务中，中，P P类和类和N N类的实体分别称为类的实体分别称为概念的正例和反例。概念的正例和反例。n将一些已知的正例和反例放在一起便得到将一些已知的正例和反例放在一起便得到训练集。训练集。n下表给出一个训练集，由下表给出一个训练集，由ID3ID3算法得出一棵算法得出一棵正确分类正确分类训训练集练集中中每个实体每个实体的决策树。的决策树。2022/12/20信息分析与决策支持 唐晶磊NO.属性属性类别类别天气天气气温气温湿度湿度风风1晴晴热热高高无风无风N2晴晴热热高高有风有风N3多云多云热热高高无风无风P4雨雨适中适中高高无

36、风无风P5雨雨冷冷正常正常无风无风P6雨雨冷冷正常正常有风有风N7多云多云冷冷正常正常有风有风P8晴晴适中适中高高无风无风N9晴晴冷冷正常正常无风无风P10雨雨适中适中正常正常无风无风P11晴晴适中适中正常正常有风有风P12多云多云适中适中高高有风有风P13多云多云热热正常正常无风无风P14雨雨适中适中高高有风有风N2022/12/20信息分析与决策支持 唐晶磊天天 气气湿湿 度度风风晴晴雨雨多云多云高高正常正常有风有风无风无风P PN NN NP PP PID3ID3决策树决策树2022/12/20信息分析与决策支持 唐晶磊n决策树决策树叶子结点叶子结点为类别名，即为类别名，即P P或者或者

37、N N。n其它结点由其它结点由实体的特征实体的特征组成，每个特征的不同取值对应组成，每个特征的不同取值对应一分枝。一分枝。n若要对一个实体分类，从树根开始进行测试。若要对一个实体分类，从树根开始进行测试。n按特征的取值按特征的取值分枝向下进入下层结点，对该结点进行测分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。所标记的类别。2022/12/20信息分析与决策支持 唐晶磊ID3ID3算法算法（一）主算法（一）主算法 1 1、从训练集中随机选择一个既含正例又含反例的子从训练集中随机选择一个既含正例又

38、含反例的子集（称为集（称为 窗口窗口）；）；2 2、用用“建树算法建树算法”对当前窗口形成一棵决策树；对当前窗口形成一棵决策树；3 3、对训练集（窗口除外）中例子用所得决策树进行类对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；别判定，找出错判的例子；4 4、若存在错判的例子，把它们插入窗口，转若存在错判的例子，把它们插入窗口，转2 2，否则，否则结束。结束。主算法流程用下图表示。主算法流程用下图表示。2022/12/20信息分析与决策支持 唐晶磊训练集训练集PEPE、NENE取子集取子集建窗口建窗口窗口窗口PEPE、NENE生成生成决策树决策树测试测试PEPE、NENE扩

39、展窗口扩展窗口PE=PE+PENEPE=PE+PENE=NE+NE=NE+NE此决策树为此决策树为最后结果最后结果存在错判的存在错判的PEPE，NENE吗吗是是否否ID3ID3主算法流程主算法流程2022/12/20信息分析与决策支持 唐晶磊nPEPE、NENE分别为正例集和反例集，共同组成训练集。分别为正例集和反例集，共同组成训练集。nPEPE，PEPE和和NENE，NENE分别表示正例集和反例集分别表示正例集和反例集的子集。的子集。n主算法中每迭代循环一次，生成的决策树将会不相同。主算法中每迭代循环一次，生成的决策树将会不相同。2022/12/20信息分析与决策支持 唐晶磊（二）建树算法（

40、二）建树算法 1 1、计算计算当前例子当前例子集合集合各特征的各特征的互信息互信息；2 2、选择选择互信息互信息最大的特征最大的特征AkAk，作为树（子树）的根结点；，作为树（子树）的根结点；3 3、把在把在AkAk处取值相同的例子归于同一子集（分支），处取值相同的例子归于同一子集（分支），AkAk取取几个值就得几个子集（分支）；几个值就得几个子集（分支）；4 4、对既含正例又含反例的子集，递归调用建树算法；对既含正例又含反例的子集，递归调用建树算法；5 5、若子集仅含正例或反例，对应分枝标上若子集仅含正例或反例，对应分枝标上P P或或N N，返回调用返回调用处。处。2022/12/20信息分

41、析与决策支持 唐晶磊3 3、ID3ID3方法应用实例方法应用实例 气候分类问题具体计算有：气候分类问题具体计算有：信息熵信息熵的计算的计算信息熵：信息熵：类别类别ui出现的概率：出现的概率：类别正例类别正例oror反例反例|S|表示例子集表示例子集S的总数，的总数，|ui|表示类别表示类别ui的例子数。的例子数。2022/12/20信息分析与决策支持 唐晶磊对对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）loglog2 2（14/914/9）+（5/145/14）lo

42、glog2 2（14/514/5）=0.94b=0.94b2022/12/20信息分析与决策支持 唐晶磊 条件熵条件熵：计算条件熵计算条件熵属性属性A A1 1取值取值vjvj时，类别时，类别u ui i的条件概率：的条件概率：2022/12/20信息分析与决策支持 唐晶磊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

43、 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/5条件熵为：条件熵为：H(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/14)H(U

44、/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.694bit0.694bit2022/12/20信息分析与决策支持 唐晶磊计算互信息计算互信息 对对 A A1 1=天气天气 处有：处有：I I（天气）天气）=信息熵条件熵信息熵条件熵H H（U U）-H-H（U|VU|V）=0.94-0.694=0.246 bit0.94-0.694=0.246 bit

45、 类似可得：类似可得：I I（气温）气温）=0.029=0.029 bitbit I I（湿度）湿度）=0.151=0.151 bitbit I I（风）风）=0.048=0.048 bitbit2022/12/20信息分析与决策支持 唐晶磊 建决策树的树根和分枝建决策树的树根和分枝 ID3ID3算法将选择算法将选择互信息最大的特征互信息最大的特征天气天气作为树根，在作为树根，在1414个例子中个例子中,对天气的对天气的3 3个取值进行分枝，个取值进行分枝，3 3 个分枝对应个分枝对应3 3个个子集，分别是子集，分别是:F1=1F1=1，2 2，8 8，9 9，1111，F2=3F2=3，7

46、7，1212，1313，F3=4F3=4，5 5，6 6，1010，1414 其中其中F2F2中的例子中的例子全属于全属于P P类类，因此对应分枝标记为，因此对应分枝标记为P P，其余两个子集既有正例又有反例，将其余两个子集既有正例又有反例，将递归调用递归调用建树算法。建树算法。2022/12/20信息分析与决策支持 唐晶磊对对F1F1和和F3F3子集分别利用子集分别利用ID3ID3算法，在每个子集中对各特征算法，在每个子集中对各特征（仍为四个特征）求互信息。（仍为四个特征）求互信息。（1 1）F1F1中的天气中的天气全取晴值全取晴值，则，则信息熵信息熵H H（U U）=条件熵条件熵H H（U

47、|VU|V），），有互信息有互信息I I（U|VU|V）=0=0。在余下三个特征中求出在余下三个特征中求出湿度互信息最大湿度互信息最大，以它为该分枝，以它为该分枝的根结点，再向下分枝。的根结点，再向下分枝。湿度取高的例子全为湿度取高的例子全为N N类，该分枝标记类，该分枝标记N N。取值正常的例取值正常的例子全为子全为P P类，该分枝标记类，该分枝标记P P。递归建树递归建树2022/12/20信息分析与决策支持 唐晶磊（2 2）在在F3F3中，对四个特征求互信息。中，对四个特征求互信息。得到得到风特征风特征互信息最大，则以它为该分枝根结点。再互信息最大，则以它为该分枝根结点。再向下分枝，取有

48、风时全为向下分枝，取有风时全为N N类，该分枝标记类，该分枝标记N N。取无风。取无风时全为时全为P P类，该分枝标记类，该分枝标记P P。这样就得到图的决策树。这样就得到图的决策树。递归建树递归建树2022/12/20信息分析与决策支持 唐晶磊4 4、C4.5C4.5算法算法ID3ID3算法在算法在DMDM中占有非常重要的地位。中占有非常重要的地位。缺点：缺点：ID3ID3算法不能够处理算法不能够处理连续属性连续属性、计算信息增益时偏、计算信息增益时偏向于向于选择取值较多的属性选择取值较多的属性等不足（等不足（P257P257）。）。C4.5C4.5是在是在ID3ID3基础上发展起来的决策树

49、生成算法，由基础上发展起来的决策树生成算法，由J.R.QuinlanJ.R.Quinlan在在19931993年提出。年提出。C4.5C4.5克服了克服了ID3ID3在应用中存在在应用中存在的不足。的不足。2022/12/20信息分析与决策支持 唐晶磊（1 1）用用信息增益信息增益率率来选择属性，它克服了用来选择属性，它克服了用信息增益信息增益选择选择属性时，偏向选择取值多的属性的不足；属性时，偏向选择取值多的属性的不足；（2 2）在树构造过程中或者构造完成之后，进行在树构造过程中或者构造完成之后，进行剪枝剪枝；（3 3）能够完成对能够完成对连续属性的离散化处理连续属性的离散化处理；（4 4）

50、能够对于不完整数据的处理，例如未知的属性值；能够对于不完整数据的处理，例如未知的属性值；（5 5）C4.5C4.5采用的采用的知识表示形式为决策树知识表示形式为决策树，并最终可以形成，并最终可以形成产生式规则产生式规则。C4.5的进步的进步2022/12/20信息分析与决策支持 唐晶磊C4.5C4.5构造决策树的算法构造决策树的算法（1 1）ID3ID3中中使使用用信信息息论论中中的的信信息息增增益益（gaingain）来来选选择择属属性性；（2 2）C4.5C4.5采用属性的采用属性的信息增益率信息增益率（gain ratiogain ratio）来选择属性。来选择属性。信息增益率信息增益率