第5章：数据仓库与数据挖掘的决策支持(1)ppt课件

第5章数据仓库与数据挖掘的决策支持,.,5.1数据仓库的基本原理,5.1.1数据仓库概念5.1.2数据仓库结构5.1.3数据集市5.1.4元数据,.,5.1.1数据仓库的概念,（1）W.H.Inmon在建立数据仓库一书中，对数据仓库的定义为：数据仓库是面向主题的、集成的、稳定的，不同时间的数据集合，用于支持经营管理中决策制定过程。,.,1、数据仓库的概念,（2）SAS软件研究所定义：数据仓库是一种管理技术，旨在通过通畅、合理、全面的信息管理，达到有效的决策支持。,.,1、数据仓库的概念,传统数据库用于事务处理，也叫操作型处理，是指对数据库联机进行日常操作，即对一个或一组记录的查询和修改，主要为企业特定的应用服务的。用户关心的是响应时间，数据的安全性和完整性。数据仓库用于决策支持，也称分析型处理，用于决策分析，它是建立决策支持系统（DSS）的基础。,操作型数据（DB数据）与分析型数据（DW数据）之间的差别为：,.,2、数据仓库特点,（1）数据仓库是面向主题的主题是数据归类的标准，每一个主题基本对应一个宏观的分析领域。例如，银行的数据仓库的主题：客户DW的客户数据来源：从银行储蓄DB、信用卡DB、贷款DB等三个DB中抽取同一客户的数据整理而成。在DW中分析客户数据，可决定是否继续给予贷款,.,2、数据仓库特点,（2）数据仓库是集成的数据进入数据仓库之前，必须经过加工与集成对不同的数据来源进行统一数据结构和编码统一原始数据中的所有矛盾之处，如字段的同名异义，异名同义，单位不统一，字长不一致等。总之,将原始数据结构做一个从面向应用到面向主题的大转变。,.,2、数据仓库特点,（3）数据仓库是稳定的数据仓库中包括了大量的历史数据。数据经集成进入数据仓库后是极少或根本不更新的。（4）数据仓库是随时间变化的数据仓库内的数据时限在510年，故数据的键码包含时间项，标明数据的历史时期，这适合DSS进行时间趋势分析。数据库只包含当前数据，即存取某一时间的正确的有效的数据。,.,2、数据仓库特点,(5)数据仓库的数据量大.大型DW是一个TB（1000GB）级数据库问题（一般为10GB级相当于一般数据库100MB的100倍）(6)数据仓库的硬件要求较高需要一个巨大的硬件平台需要一个并行的数据库系统.最好的数据仓库是大的和昂贵的。,.,近期基本数据：是最近时期的业务数据，是数据仓库用户最感兴趣的部分，数据量大。历史基本数据：近期基本数据随时间的推移，由数据仓库的时间控制机制转为历史基本数据。轻度综合数据：是从近期基本数据中提取出的，这层数据是按时间段选取，或者按数据属性（attributes）和内容（contents）进行综合。高度综合数据层：这一层的数据是在轻度综合数据基础上的再一次综合，是一种准决策数据。,5.1.2数据仓库结构,.,元数据:整个数据仓库的组织结构由元数据组织,它不包含数据仓库中的实际数据信息。作用：（1）定位数据仓库的目录内容（2）数据从业务环境向数据仓库环境传递时数据仓库的目录内容（3）指导从当前基本数据到轻度综合数据到高度综合数据的综合算法的选择。组成：（1）数据结构（2）用于综合的算法（3）从业务环境到DW规划,5.1.2数据仓库结构,数据仓库结构图,.,1.数据集市的产生数据仓库工作范围和成本常常是巨大的。开发数据库是代价很高、时间较长的大项目。提供更紧密集成的数据集市就应运产生。目前，全世界对数据仓库总投资的一半以上均集中在数据集市上。,5.1.3数据集市（DataMart）,.,数据集市（DataMarts）是一种更小、更集中的数据仓库，为公司提供分析商业数据的一条廉价途径。数据集市是指具有特定应用的数据仓库，主要针对某个应用或者具体部门级的应用，支持用户获得竞争优势或者找到进入新市场的具体解决方案,2.数据集市概念,.,3.数据集市与数据仓库的关系,数据集市不等于数据仓库，多个数据集市简单合并起来不能成为数据仓库。各数据集市之间对详细数据和历史数据的存储存在大量冗余。同一个问题在不同的数据集市的查询结果可能不一致，甚至互相矛盾。各数据集市之间以及与源数据库系统之间难以管理。,1、规模小2、特定的应用3、面向部门4、由业务部门定义，设计和开发5、由业务部门管理和维护6、快速实现7、购买较便宜8、投资快速回收9、工具集的紧密集成10、更详细的、预先存在的数据仓库的摘要子集11、可升级到完整的数据仓库,4.数据集市的特性,5.两种数据集市结构,从属数据集市(DependentDataMart),从属：数据直接来自中央数据库，能够保持数据的一致性。关键业务部门建立从属的数据集市，可以很好的查询反应速度。,.,5.两种数据集市结构,独立数据集市(IndependentDataMart),独立：数据直接来自各生产系统。从投资考虑，用来解决各个部门比较迫切的决策问题。,.,6.数据集市与数据仓库的差别,数据仓库是基于整个企业的数据模型建立的，它面向企业范围的主题；数据集市是按照某一特定部门的数据模型建立的，由于每个部门有自己特定的需求，因此，对他们对数据集市的期望也不一样，也称作部门级数据仓库部门的主题与企业的主题之间可能存在关联，也可能不存在关联。数据集市的数据组织一般采用星形模型，大型数据仓库的数据组织采用第三范式。,.,元数据是数据仓库的重要组成部分。元数据描述了数据仓库的数据和环境，即关于数据的数据(metadata)。元数据就相当于数据库系统中的数据字典元数据包括四种元数据关于数据源的元数据关于数据模型的元数据关于数据仓库映射的元数据关于数据仓库使用的元数据,5.1.4元数据,.,它是现有的业务系统的数据源的描述信息。这类元数据是对不同平台上的数据源的物理结构和含义的描述。具体为：（1）数据源中所有物理数据结构，包括所有的数据项及数据类型。（2）所有数据项的业务定义。（3）每个数据项更新的频率，以及由谁或哪个过程更新的说明。（4）每个数据项的有效值。,1、关于数据源的元数据,.,这类元数据描述了数据仓库中有什么数据以及数据之间的关系,它们是用户使用管理数据仓库的基础。这类元数据可以支持用户从数据仓库中获取数据。数据仓库的数据模型是星型模型。通常企业数据模型被用作建立仓库数据模型的起始点，再对模型加以修改和变换。,2、关于数据模型的元数据,.,这类元数据是数据源与数据仓库数据间的映射。当数据源中的一个数据项与数据仓库建立了映射关系，就应该记下这些数据项发生的任何变换或变动。即用元数据反映数据仓库中的数据项是从哪个特定的数据源填充的，经过那些转换、变换和加载过程,3、关于数据仓库映射的元数据,.,3、关于数据仓库映射的元数据,一个抽取要经过以下几个步聚获取过滤验证融合综合装载存档,从源系统的数据到数据仓库中的目标数据的转移是一项复杂的工作，其工作量占整个数据仓库开发的70%,.,这类元数据是数据仓库中信息的使用情况描述。数据仓库的用户最关心的是两类元数据：（1）元数据告诉数据仓库中有什么数据，它们从哪里来。即如何按主题查看数据仓库的内容。（2）元数据提供已有的可重复利用的查询语言信息。如果某个查询能够满足他们的需求，或者与他们的愿望相似，他们就可以再次使用那些查询而不必从头开始编程。关于数据仓库使用的元数据能帮助用户到数据仓库查询所需要的信息，用于解决企业问题。,4、关于数据仓库使用的元数据,5.2数据仓库系统,5.2.1数据仓库系统结构数据仓库系统由数据仓库（DW）、仓库管理和分析工具三部分组成,.,1、数据仓库管理系统,（1）定义部分用于定义和建立数据仓库系统。它包括：设计和定义数据仓库的数据库定义数据来源确定从源数据向数据仓库复制数据时的清理和增强规则（2）数据获取部分该部件把数据从源数据中提取出来，依定义部件的规则，抽取、转化和装载数据进入数据仓库。,.,（3）管理部分它用于管理数据仓库的工作，包括：对数据仓库中数据的维护把仓库数据送出给分散的仓库服务器或DSS用户对仓库数据的安全、归档、备份、恢复等处理工作,1、数据仓库管理系统,.,（4）信息目录部件（元数据）数据仓库的目录数据是元数据，由三部分组成：技术目录：由定义部件生成，关于数据源、目标、清理规则、变换规则以及数据源和仓库之间的映象信息。业务目录：由仓库管理员生成，关于仓库数据的来源及当前值；预定义的查询和报表细节；合法性要求等。信息引导器：使用户容易访问仓库数据。利用固定查询或建立新的查询，生成暂时的或永久的仓库数据集合的能力等。（5）DBMS部分DW的存储形式仍为关系型数据库。,1、数据仓库管理系统,.,分析工具集分两类工具：（1）查询工具数据仓库的查询不是指对记录级数据的查询，而是指对分析要求的查询。一般包含：可视化工具：以图形化方式展示数据，可以帮助了解数据的结构、关系以及动态性。,2、数据仓库工具集,.,多维分析工具（OLAP工具）:通过对信息的多种可能的观察形式进行快速、一致和交互性的存取，这样便利用户对数据进行深入的分析和观察。多维数据的每一维代表对数据的一个特定的观察视角，如时间、地域、业务等。,2、数据仓库工具集,.,（2）数据挖掘工具从大量数据中挖掘具有规律性知识，需要利用数据挖掘（DataMining）工具。,2、数据仓库工具集,.,3、数据仓库的运行结构,数据仓库应用是一个典型的客户/服务器（C/S）结构形式数据仓库采用服务器结构，客户端所做的工作有：客户交互、格式化查询、结果显示、报表生成等。服务器端完成各种辅助决策的SQL查询、复杂的计算和各类综合功能等。现在，越来越普通的一种形式是三层C/S结构形式，即在客户与数据仓库服务器之间增加一个多维数据分析（OLAP）服务器。,OLAP服务器将加强和规范化决策支持的服务工作，集中和简化了原客户端和数据仓库服务器的部分工作，降低了系统数据传输量。这种结构形式工作效率更高。,三层C/S结构,.,5.2.2数据仓库的存储,数据仓库存储采用多维数据模型。维就是相同类数据的集合，商店、时间和产品都是维各个商店的集合是一维，时间的集合是一维，商品的集合是一维。每一个商店、每一段时间、每一种商品就是某一维的一个成员。每一个销售事实由一个特定的商品、一个特定的时间、一个特定的商品组成。两维表，如通常的电子表格。三维构成立方体，若再增加一维，则图形很难想象，也不容易在屏幕上画出来。,.,数据仓库是以多维表型的“维表事实表”结构形式组织的，共有三种形式：1、星型模型大多数的数据仓库都采用“星型模型”。星型模型是由“事实表”（大表）以及多个“维表”（小表）所组成。“事实表”中存放大量关于企业的事实数据（数量数据）。例如：多个时期的数据可能会出现在同一个“事实表”中。“维表”中存放描述性数据，维表是围绕事实表建立的较小的表,5.2.2数据仓库的存储,.,2、雪花模型雪花模型是对星型模型的扩展，雪花模型对星型模型的维表进一步层次化，原来的各维表可能被扩展为小的事实表，形成一些局部的“层次”区域。它的优点是最大限度地减少数据存储量，以及把较小的维表联合在一起来改善查询性能。在上面星型模型的数据中，对“产品表”“日期表”“地区表”进行扩展形成雪花模型数据见下图。,5.2.2数据仓库的存储,.,.,3、星网模型星网模型是将多个星型模型连接起来形成网状结构。多个星型模型通过相同的维，如时间维，连接多个事实表。,5.2.2数据仓库的存储,.,第（2）部分,5.3联机分析处理（OLAP）5.4数据仓库的决策支持,.,5.3联机分析处理,联机分析处理（OnLineAnalyticalProcessing，OLAP）的概念最早是由关系数据库之父E.F.Codd(科德)于1993年提出的。在数据仓库系统中，联机分析处理是重要的数据分析工具。OLAP的基本思想是从多方面和多角度以多维的形式来观察企业的状态和了解企业的变化。,.,5.3.1基本概念,OLAP是在OLTP(联机事务处理系统)的基础上发展起来的。OLTP是以数据库为基础的，面对的是操作人员和低层管理人员，对基本数据的查询和增、删、改等进行处理。OLAP是以数据仓库为基础的数据分析处理。它有两个特点：一是在线性（OnLine），由客户机/服务器这种体系结构来完成的；二是多维分析，这也是OLAP的核心所在。,.,1、OLAP的定义,联机分析处理是共享多维信息的快速分析。它体现了四个特征：（1）快速性：用户对OLAP的快速反应能力有很高的要求。（2）可分析性：OLAP系统应能处理任何逻辑分析和统计分析。（3）多维性：系统必须提供对数据分析的多维视图和分析。（4）信息性：OLAP系统应能及时获得信息，并且管理大容量的信息。,.,2、OLAP准则,1993年，E.F.Codd提出OLAP的12条准则，其主要的准则有：1）多维数据分析；2）客户/服务器结构；3）多用户支持；4）一致的报表性能等。,.,2、OLAP准则,多维概念视图企业的数据空间本身就是多维的。因此OLAP的概念模型也应是多维的。用户可以对多维数据模型进行切片、切块、旋转坐标或进行多维的联合（概括和聚集）分析。,.,稳定的报表性能报表操作不应随维数增加而削弱，即当数据维数和数据的综合层次增加时，提供的报表能力和响应速度不应该有明显的降低。,2、OLAP准则,.,客户/服务器体系结构OLAP是建立在客户/服务器体系结构上的。要求多维数据库服务器能够被不同的应用和工具所访问。,2、OLAP准则,.,多用户支持当多个用户要在同一分析模式上并行工作，需要这些功能的支持。灵活的报表生成报表必须充分反映数据分析模型的多维特征，并可按用户需要的方式来显示它。,2、OLAP准则,.,3、OLAP的基本概念,OLAP是针对特定问题的联机数据访问和分析。（1）变量：变量是数据的实际意义，即描述数据“是什么”。（2）维：维是人们观察数据的特定角度。如产品维、顾客维、时间维等。（3）维的层次：数据的细节不同程度为维的层次。如日、月、季、年是时间维的层次。（4）维成员：维的一个取值称为该维的一个维成员。如“某年某月某日”是时间维的一个成员。,.,3、OLAP的基本概念,5）多维数组：一个多维数组可以表示为：（维1，维2，维n，变量）一个5维的结构，即（产品，地区，时间，销售渠道，销售额）。（6）数据单元（单元格）：多维数组的取值称为数据单元。如：5维数据单元（牙膏，上海，1998年12月，批发，销售额为100000）。,.,4、OLAP与OLTP的关系与比较,（1）OLTP(联机事务处理系统)OLTP是低层人员利用计算机网络对数据库中的数据进行查询、增、删、改等操作，以完成事务处理工作。OLTP利用数据库快速地处理具体业务。OLTP应用要求多个查询并行。,.,4、OLAP与OLTP的关系与比较,（2）OLAPOLAP是高层人员对数据仓库进行信息分析处理。存取大量的数据包含聚集的数据按层次对比不同时间周期的聚集数据以不同的方式来表现数据要包含数据元素之间的复杂的计算能够快速的响应用户的查询,.,4、OLAP与OLTP的关系与比较,（3）OLAP与OLTP对比（对比表）,.,5.3.2OLAP的数据组织,MOLAP(多维OLAP)和ROLAP(关系OLAP)是OLAP的两种具体形式：ROLAP是基于关系数据库存储方式建立的OLAP。多维数据映射成平面型的关系表。采用星型模型。MOLAP是基于多维数据库存储方式建立的OLAP；表现为“超立方”结构，类似于多维数组的结构。在分析中，需要“旋转”数据立方体以及“切片”、“切块”等操作。,.,MOLAP和ROLAP的对比表,.,例如，以“产品、城市、时间”三维数据，如图,5.3.3OLAP的决策支持：OLAP多维数据分析,.,1、基本功能：切片和切块,对三维数据，通过“切片”，分别从城市和产品等不同的角度观察销售情况：,.,2）钻取,钻取：例如，1995年各部门销售收入表如下：,.,对时间维进行下钻操作，获得新表如下：,钻取（续）,.,旋转前的数据,旋转,.,旋转后的数据,旋转（续）,.,旋转后再切片,.,假设有一个5维数据模型，5个维分别为：商店，方案，部门，时间，销售。1三维表查询在指定“商店=ALL，方案=现有”情况的三维表（行为部门，列为时间和销售量）,5.3.4、OLAP实例,.,指定商店、方案后的三维表,.,2、向下钻取对汽车部门向下钻取出具体项目的销售情况和利润增长情况。,.,3、切片表切片（Slice）操作是除去一些列或行不显示,.,4、旋转表这次旋转操作得到1995年的交叉表方案为：现有、计划、差量、差量%。,.,5.4.2数据仓库的决策支持,美国著名的NCR数据仓库公司对数据仓库总结5种决策支持能力。1、报表2、随机分析3、预测4、实时决策5、事件触发的自动决策,.,1、报表,数据仓库所面临的最大挑战是数据集成。传统的环境经常有上百个数据源，每一数据源都有各自定义的标准和实施技术。建立的数据仓库是通过收集各种来源的数据，来回答预先设置的一些问题，告诉决策者“发生了什么”。它为以后数据仓库的发展奠定了基础。,.,2、随机分析,数据仓库应用的第二种决策支持是，从“发生了什么”转向“为什么会发生”。分析活动就是了解报表数据的涵义，需要更多更详细的数据进行各种角度的分析。在第二阶段的数据仓库主要用于随机分析。,.,3、预测,数据仓库的第三种决策支持是帮助决策者来预测未来，回答“将要发生什么”。数据仓库需要利用历史资料创建预测模型。,.,4、实时决策,数据仓库的第4种决策支持是企业需要准确了解“正在发生什么”，从而需要建立动态数据仓库（实时数据库），用于支持战术型决策，即实时决策。有效地解决当前的实际问题。第1到第3种决策支持的数据仓库都以支持企业内部战略性决策为重点，帮助企业制定发展战略。第4种决策支持侧重在战术性决策支持。动态数据仓库能够逐项产品、逐个店铺、逐秒地作出最佳决策支持。,.,5、事件触发的自动决策,数据仓库的第5种决策支持是由事件触发，利用动态数据库自动决策，达到“希望发生什么”。例如，电子货架标签技术结合动态数据仓库，可以帮助企业按照自己的意愿实现复杂的价格管理自动化，以便以最低的损耗售出最多的存货。,.,5.5知识发现与数据挖掘5.6数据挖掘的决策支持及应用,第（3）部分,.,演变阶段,商业问题,支持技术,产品厂家,产品特点,数据搜集（20世纪60年代）,数据访问（20世纪80年代）,数据仓库决策支持（20世纪90年代,数据挖掘（正在流行）,“过去五年中整个有关联锁超市总收入是多少？”,“联锁超市第一分部去年三月的销售额是多少？”,“联锁超市第一分部去年三月的销售额是多少？第二分部据此可得出什么结论？”,“下个月第二分部的销售会怎么样？为什么？”,计算机、磁带和磁盘,关系数据库（RDBMS），查询语言（SQL），ODBC,OLAP、多维数据库和数据仓库,高级算法、多处理器计算机和海量数据库,IBM和CDC,Oracle、Sybase、Informix、IBM和Microsoft,Pilot、Comshare、Arbor、Cognos和Microstrategy,Pilot、Lockheed、IBM、SGI和其他初创公司,提供历史性的静态的数据,在记录级提供历史性动态数据,在各种层次上提供回溯的动态数据,提供预测性信息,表5-1数据挖掘的演变进程,.,产品,Clementine,Darwin,DataminingWorkstation,DataEngine,IBMIntelligentMiner,F-DBMS,IDIS,InformationHarvester,KnowledgeSeeker,NeuralWare,Prison,ReMind,技术,供应商,规则归纳,神经网络、遗传算法等,神经网络,神经网络、模糊逻辑、信号处理,多种技术,分数维,规则发现,模糊专家系统,规则发现、决策树,神经网络,神经网络,基于实例的推理、归纳逻辑,IngegralSolutions,ThinkingMachinesCorp.,HNCSoftwareInc.,MITGmbh,IBMCorp.,Cross/ZInternationalInc.,InformationalDiscoveryInc.,InformationalHarvesting,AngossSoftwareInt1Ltd.,NeuralWareInc.,NestorInc.,CognitiveSystems,表5-2一些主要的数据挖掘产品,.,数据挖掘的兴起,（1）80年在美国召开了第一届国际机器学习研讨会；（2）89年8月于美国底特律市召开的第一届KDD国际学术会议；（3）95年在加拿大召开了第一届知识发现和数据挖掘国际学术会议；（4）我国于87年召开了第一届全国机器学习研讨会。,.,5.5.1知识发现与数据挖掘概念,知识发现（KDD）：从数据中发现有用知识的整个过程。KDD过程定义：从数据集中提取出可信的、新颖的、潜在有用的,以及最终可理解的模式的高级处理过程。“模式”可以看成是“知识”的雏形，经过验证、完善后形成知识。数据挖掘（DM）：KDD过程中的一个特定步骤，它用专门算法从数据中抽取模式（patterns）。,.,KDD过程,.,5.5.2数据挖掘方法和技术,（一）归纳学习方法分为两大类：信息论方法（决策树方法）和集合论方法1、信息论方法（决策树方法）利用信息论的原理建立决策树或者是决策规则树。（1）ID3方法：Quiulan研制的ID3方法是利用信息论中互信息建立决策树。（2）IBLE方法：我们研制的IBLE方法，是利用信息论中信道容量，寻找数据库中信息量大的多个字段的取值建立决策规则树。,.,2、集合论方法（1）粗糙集（RoughSet）方法对数据库中的条件属性集与决策属性集建立上下近似关系，对下近似集合建立确定性规则，对上近似集合建立不确定性规则（含可信度）。（2）关联规则挖掘在交易事务数据库中，挖掘出不同商品集的关联关系，即发现哪些商品频繁地被顾客同时购买。,5.5.2数据挖掘方法和技术,.,（二）仿生物技术仿生物技术典型的方法是神经网络方法和遗传算法。1、神经网络方法：包括：前馈式网络、反馈式网络、自组织网络等多个神经网络方法。2、遗传算法：这是模拟生物进化过程的算法。它由三个基本算子组成：繁殖（选择）、交叉（重组）、变异（突变）遗传算法起到产生优良后代的作用，经过若干代的遗传，将得到满足要求的后代（问题的解）。,5.5.2数据挖掘方法和技术,.,（三）公式发现在工程和科学数据库中对若干数据项（变量）进行一定的数学运算，求得相应的数学公式。1物理定律发现系统BACONBACON发现系统完成了物理学中大量定律的重新发现。2经验公式发现系统FDD我们研制了FDD发现系统，寻找由数据项的初等函数或复合函数组合成的经验公式。,5.5.2数据挖掘方法和技术,.,（四）统计分析方法利用统计学原理通过对总体中的样本数据进行分析得出描述和推断该总体信息和知识的方法。（五）模糊数学方法利用模糊集合理论进行数据挖掘，如模糊聚类、模糊分类等。（六）可视化技术利用可视化技术分析数据库，找到潜在的有用信息。,5.5.2数据挖掘方法和技术,.,5.5.3数据挖掘的知识表示（一）,主要有四种：规则、决策树、浓缩数据、公式。1、规则规则知识由前提条件和结论两部分组成前提条件由字段项（属性）的取值的合取（与）和析取（或）组合而成。结论为决策字段项（属性）的取值或者类别组成。,.,.,2、决策树例如：上例的人群数据库，按ID3方法得到的决策树如下：,数据挖掘的知识表示（二）,.,3、知识基（浓缩数据）例如上例的人群数据库，通过计算可以得出身高是不重要的字段，删除它后，再合并相同数据元组，得到浓缩数据如下表：,数据挖掘的知识表示（三）,.,5、公式例如，太阳系行星运动数据中包含行星运动周期（旋转一周所需时间，天），以及它与太阳的距离（围绕太阳旋转的椭圆轨道的长半轴，百万公里），数据如下表：,发现的公式为：d3/p2=25,数据挖掘的知识表示（五）,.,5.6数据挖掘的决策支持及应用,5.6.1数据挖掘的决策支持分类有：关联分析、时序模式、聚类、分类、偏差检测、预测。1、关联分析若两个或多个数据项的取值之间重复出现且概率很高时，它就存在某种关联，可以建立起这些数据项的关联规则。2、时序模式通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列的影响。,.,3、聚类：在数据库中找出一系列有意义的子集，即类。4、分类：对数据库中的类，找出该类别的概念描述规则。5、偏差检测：在数据库中找出异常数据。6、预测：利用历史数据找出变化规律的模型，并用此模型预测未来。,5.6数据挖掘的决策支持及应用,.,5.6.2决策树及其应用,1、决策树概念：决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。根结点是所有样本中信息量最大的属性.中间节点是该结点为根据的子树所包含的样本子集中信息量最大的属性.每个内部节点表示在一个属性上的测试每个分枝代表一个测试输出,每个树叶节点是样本的类别值.,.,5.6.2决策树及其应用,决策树对新样本的分类过程:即通过新样本属性值的测试从根结点开始按照样本属性的取值,逐渐沿着决策树向下,直到树的叶结点,该叶结点表示的类别就是新样本的类别.,.,数据挖掘的决策树方法的原理是信息论，信息论是C.E.Shannon为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。一个传递信息的系统是由发送端（信源）和接收端（信宿）以及连接两者的通道（信道）三者组成。信息论把通信过程看做是在随机干扰的环境中传递信息的过程。在这个通信模型中，信息源和干扰（噪声）都被理解为某种随机过程或随机序列。,5.6.2决策树及其应用,.,在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。这种情形就称为信宿对于信源状态具有不确定性。而且这种不确定性是存在于通信之前的。因而又叫做先验不确定性。在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。如果干扰很小，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。,5.6.2决策树及其应用,.,在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。因此，先验不确定性不能全部被消除，只能部分地消除。通信结束之后，信宿还仍然具有一定程度的不确定性。这就是后验不确定性。显然，后验不确定性总要小于先验不确定性，不可能大于先验不确定性。,5.6.2决策树及其应用,.,如果后验不确定性的大小正好等于先验不确定性的大小，这就表示信宿根本没有收到信息。如果后验不确定性的大小等于零，这就表示信宿收到了全部信息。可见，信息是用来消除（随机）不确定性的度量。信息量的大小，由所消除的不确定性的大小来计量。,5.6.2决策树及其应用,.,信息论基本概念定义1：若存在n个相同概率的消息，则每个消息的概率p是1/n，一个消息传递的信息量为-Log2(1/n),概率越大,信息量越小如英语有26个字母,假如每个字母在文章中出现的次数平均的话,每个字母的信息量为:I(e)=-log21/26=4.7如常用汉字有2500个,假如每个汉字在文章中出现的次数平均的话,每个汉字的信息量为:I(e)=-log21/2500=11.3,5.6.2决策树及其应用,.,定义2：若有n个消息，其给定概率分布为P=(p1,p2pn)，则由该分布传递的信息量称为P的熵，记为,定义3：若一个记录集合T根据类别属性的值被分成互相独立的类C1,C2.Ck，则识别T的一个元素所属哪个类所需要的信息量为Info(T)=I(p)，其中P为C1,C2Ck的概率分布，即P=(|C1|/|T|,.|Ck|/|T|),5.6.2决策树及其应用,.,定义4：若先根据非类别属性X的值将T分成集合T1,T2,Tn，则确定T中一个元素类的信息量可通过确定Ti的加权平均值来得到，即Info(Ti)的加权平均值为：Info(X,T)=(|Ti|/|T|)Info(Ti),5.6.2决策树及其应用,定义5：信息增益度是两个信息量之间的差值，其中一个信息量是需确定T的一个元素的信息量，另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量，信息增益度公式为：Gain(X,T)=Info(T)-Info(X,T),.,2、ID3算法,当前国际上最有影响的示例学习方法首推J.R.Quinlan的ID3。ID3以信息论为基础,以互信息(信息增益,Informationgain）和信息熵为衡量标准,从而实现对数据的归类分类.,.,2、ID3算法,工作过程:首先找出最有判别力(信息增益,informationgain)的属性,把数据分成多个子集,每个子集又选择最有判别力的属性进行划分,一直进行到所有子集仅包含同一类型的数据为止.最后得到一棵决策树,可用它来对新的实例进行分类.,.,ID3主算法流程,（一）主算法1、从训练集中随机选择一个既含正例又含反例的子集（称为窗口）；2、用“建树算法”对当前窗口形成一棵决策树；3、对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；4、若存在错判的例子，把它们插入窗口，转2，否则结束。,主算法中每迭代循环一次，生成的决策树将会不相同。,.,（二）建树算法1、对当前例子集合，计算各特征的互信息；2、选择互信息最大的特征Ak；3、把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；4、对既含正例又含反例的子集，递归调用建树算法；5、若子集仅含正例或反例，对应分枝标上P或N，返回调用处。,二、ID3算法,.,在一实体世界中，每个实体用多个特征来描述。每个特征限于在一个离散集中取互斥的值。例如，设实体是某天早晨，分类任务是关于气候的类型，特征为:天气取值为：晴，多云，雨气温取值为：冷，适中，热湿度取值为：高，正常风取值为：有风，无风,某天早晨气候描述为:天气：多云气温：冷湿度：正常风：无风,3、ID3方法应用实例,.,它属于哪类气候呢?每个实体属于不同的类别，为简单起见，假定仅有两个类别，分别为P，N。在这种两个类别的归纳任务中，P类和N类的实体分别称为概念的正例和反例将一些已知的正例和反例放在一起便得到训练集。下表给出一个训练集。由ID3算法得出一棵正确分类训练集中每个实体的决策树，见图。,3、ID3方法应用实例,.,.,决策树叶子为类别名，即P或者N。其它结点由实体的特征组成，每个特征的不同取值对应一分枝。若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。,.,3、ID3方法应用实例,对于气候分类问题进行具体计算有：信息熵的计算信息熵：,.,类别出现概率：|S|表示例子集S的总数，|ui|表示类别ui的例子数。对9个正例和5个反例有：P（u1）=9/14P（u2）=5/14H（U）=（9/14）log2（14/9）+（5/14）log2（14/5）=0.94bit,3、ID3方法应用实例,.,条件熵：,条件熵计算,属性A1取值vj时，类别ui的条件概率：,.,A1=天气取值v1=晴，v2=多云，v3=雨在A1处取值晴的例子5个，取值多云的例子4个，取值雨的例子5个，故P（v1）=5/14P（v2）=4/14P（v3）=5/14取值为晴的5个例子中有2个正例、3个反例，故：P（u1/v1）=2/5，P（u2/v1）=3/5同理有：P（u1/v2）=4/4，P（u2/v2）=0P（u1/v3）=2/5，P（u2/v3）=3/5H(U/V)=(5/14)(2/