数据仓库与数据挖掘的决策支持.ppt

《数据仓库与数据挖掘的决策支持.ppt》由会员分享，可在线阅读，更多相关《数据仓库与数据挖掘的决策支持.ppt（135页珍藏版）》请在三一办公上搜索。

1、第5章 数据仓库与数据挖掘 的决策支持,基本原理,知识发现与数据挖掘,数据仓库系统,联机分析处理,数据仓库与数据挖掘的决策支持,数据仓库的支持系统,5.1 数据仓库的基本原理,数据仓库的兴起1.“数据太多，信息不足”的现状2.异构环境的数据源 据美国幸福杂志所列的全球2000家大公司中已有90%将Internet网络和数据仓库这两项技术列入企业计划。数据仓库是1995年开始盛行起来的。,5.1.1 数据仓库的概念,（1）在建立数据仓库一书中，对数据仓库的定义为：数据仓库是面向主题的、集成的、稳定的，不同时间的数据集合，用于支持经营管理中决策制定过程。,1、数据仓库的概念,（2）SAS软件研究所

2、定义：数据仓库是一种管理技术，旨在通过通畅、合理、全面的信息管理，达到有效的决策支持。,1、数据仓库的概念,传统数据库用于事务处理，也叫操作型处理，是指对数据库联机进行日常操作，即对一个或一组记录的查询和修改，主要为企业特定的应用服务的。用户关心的是响应时间，数据的安全性和完整性。数据仓库用于决策支持，也称分析型处理，用于决策分析，它是建立决策支持系统（DSS）的基础。,操作型数据（DB数据）与分析型数据（DW数据）之间的差别为：,2、数据仓库特点,（1）数据仓库是面向主题的 主题是数据归类的标准，每一个主题基本对应一个宏观的分析领域。例如，银行的数据仓库的主题：客户 DW的客户数据来源：从银

3、行储蓄DB、信用卡DB、贷款DB等三个DB中抽取同一客户的数据整理而成。在DW中分析客户数据，可决定是否继续给予贷款。,2、数据仓库特点,（2）数据仓库是集成的 数据进入数据仓库之前，必须经过加工与集成。对不同的数据来源进行统一数据结构和编码。统一原始数据中的所有矛盾之处，如字段的同名异义，异名同义，单位不统一，字长不一致等。将原始数据结构做一个从面向应用到面向主题的大转变。,2、数据仓库特点,（3）数据仓库是稳定的 数据仓库中包括了大量的历史数据。数据经集成进入数据仓库后是极少或根本不更新的。（4）数据仓库是随时间变化的 数据仓库内的数据时限在510年，故数据的键码包含时间项，标明数据的历史

4、时期，这适合DSS进行时间趋势分析。而数据库只包含当前数据，即存取某一时间的正确的有效的数据。,2、数据仓库特点,大型DW是一个TB（1000GB）级数据库问题（一般为10GB级相当于一般数据库100MB的100倍）需要一个巨大的硬件平台 需要一个并行的数据库系统 最好的数据仓库是大的和昂贵的。,面向主题,稳定,随时间变化,集成,特点,数据仓库特点,近期基本数据：是最近时期的业务数据，是数据仓库用户最感兴趣的部分，数据量大。历史基本数据：近期基本数据随时间的推移，由数据仓库的时间控制机制转为历史基本数据。轻度综合数据：是从近期基本数据中提取出的，这层数据是按时间段选取，或者按数据属性（attr

5、ibutes）和内容（contents）进行综合。高度综合数据层：这一层的数据是在轻度综合数据基础上的再一次综合，是一种准决策数据。,5.1.2 数据仓库结构,数据仓库工作范围和成本常常是巨大的。开发数据库是代价很高、时间较长的大项目。提供更紧密集成的数据集市就应运产生。目前，全世界对数据仓库总投资的一半以上均集中在数据集市上。,5.1.3 数据集市（Data Marts）,数据集市（Data Marts）是一种更小、更集中的数据仓库，为公司提供分析商业数据的一条廉价途径。Data Marts是指具有特定应用的数据仓库，主要针对某个应用或者具体部门级的应用，支持用户获得竞争优势或者找到进入新市

6、场的具体解决方案。,数据集市概念,独立数据集市(Independent Data Mart)从属数据集市(Dependent Data Mart),数据集市的种类,1、规模是小的2、特定的应用3、面向部门4、由业务部门定义，设计和开发5、由业务部门管理和维护6、快速实现7、购买较便宜8、投资快速回收9、工具集的紧密集成10、更详细的、预先存在的数据仓库的摘要子集11、可升级到完整的数据仓库,数据集市的特性,元数据是数据仓库的重要组成部分。元数据描述了数据仓库的数据和环境，即关于数据的数据(meta data)元数据包括四种元数据。,5.1.4 元数据,Himart,元数据,数据仓库使用,数据仓

7、库映射,数据模型,数据源,它是现有的业务系统的数据源的描述信息。这类元数据是是对不同平台上的数据源的物理结构和含义的描述。具体为：（1）数据源中所有物理数据结构，包括所有的数据项及数据类型。（2）所有数据项的业务定义。（3）每个数据项更新的频率，以及由谁或那个过程更新的说明。（4）每个数据项的有效值。,1、关于数据源的元数据,数据仓库的数据模型是星型模型。通常企业数据模型被用作建立仓库数据模型的起始点，再对模型加以修改和变换。,2、关于数据模型的元数据,这类元数据是数据源与数据仓库数据间的映射。当数据源中的一个数据项与数据仓库建立了映射关系，就应该记下这些数据项发生的任何变换或变动。即用元数据

8、反映数据仓库中的数据项是从哪个特定的数据源填充的，经过那些转换，变换和加载过程。,3、关于数据仓库映射的元数据,这类元数据是数据仓库中信息的使用情况描述。数据仓库的用户最关心的是两类元数据：（1）元数据告诉数据仓库中有什么数据，它们从哪里来。即如何按主题查看数据仓库的内容。（2）元数据提供已有的可重复利用的查询语言信息。如果某个查询能够满足他们的需求，或者与他们的愿望相似，他们就可以再次使用那些查询而不必从头开始编程。关于数据仓库使用的元数据能帮助用户到数据仓库查询所需要的信息，用于解决企业问题。,4、关于数据仓库使用的元数据,5.2 数据仓库系统,5.2.1数据仓库系统结构 数据仓库系统由数

9、据仓库（DW）、仓库管理和分析工具三部分组成。,1、数据仓库管理系统,（1）定义部分 用于定义和建立数据仓库系统。它包括：(1)设计和定义数据仓库的数据库(2)定义数据来源(3)确定从源数据向数据仓库复制数据时的清理和增强规则（2）数据获取部分 该部件把数据从源数据中提取出来，依定义部件的规则，抽取、转化和装载数据进入数据仓库。,（3）管理部分 它用于管理数据仓库的工作，包括：（1）对数据仓库中数据的维护（2）把仓库数据送出给分散的仓库服务器或DSS用户（3）对仓库数据的安全、归档、备份、恢复等处理工作,1、数据仓库管理系统,（4）信息目录部件（元数据）数据仓库的目录数据是元数据，由三部分组成

10、：技术目录：由定义部件生成，关于数据源、目标、清理规则、变换规则以及数据源和仓库之间的映象信息。业务目录：由仓库管理员生成，关于仓库数据的来源及当前值；预定义的查询和报表细节；合法性要求等。信息引导器：使用户容易访问仓库数据。利用固定查询或建立新的查询，生成暂时的或永久的仓库数据集合的能力等。,1、数据仓库管理系统,分析工具集分两类工具：（1）查询工具 数据仓库的查询不是指对记录级数据的查询，而是指对分析要求的查询。一般包含：可视化工具：以图形化方式展示数据，可以帮助了解数据的结构，关系以及动态性。,2、数据仓库工具集,多维分析工具（OLAP工具）:通过对信息的多种可能的观察形式进行快速、一致

11、和交互性的存取，这样便利用户对数据进行深入的分析和观察。多维数据的每一维代表对数据的一个特定的观察视角，如时间、地域、业务等。,2、数据仓库工具集,（2）数据挖掘工具 从大量数据中挖掘具有规律性知识，需要利用数据挖掘（Data Mining）工具。,2、数据仓库工具集,3、数据仓库的运行结构,数据仓库应用是一个典型的客户/服务器（C/S）结构形式。数据仓库采用服务器结构，客户端所做的工作有：客户交互、格式化查询、结果显示、报表生成等。服务器端完成各种辅助决策的SQL查询、复杂的计算和各类综合功能等。现在，越来越普通的一种形式是三层C/S结构形式，即在客户与数据仓库服务器之间增加一个多维数据分析

12、（OLAP）服务器。,OLAP服务器将加强和规范化决策支持的服务工作，集中和简化了原客户端和数据仓库服务器的部分工作，降低了系统数据传输量。这种结构形式工作效率更高。,三层C/S结构,数据仓库存储采用多维数据模型。维就是相同类数据的集合，商店、时间和产品都是维。各个商店的集合是一维，时间的集合是一维，商品的集合是一维。每一个商店、每一段时间、每一种商品就是某一维的一个成员。每一个销售事实由一个特定的商品、一个特定的时间、一个特定的商品组成。两维表，如通常的电子表格。三维构成立方体，若再增加一维，则图形很难想象，也不容易在屏幕上画出来。,5.2.2 数据仓库的存储,商品,城市,日期,上海,牛奶,

13、存储示意图,数据仓库是以多维表型的“维表事实表”结构形式组织的，共有三种形式：1、星型模型 大多数的数据仓库都采用“星型模型”。星型模型是由“事实表”（大表）以及多个“维表”（小表）所组成。“事实表”中存放大量关于企业的事实数据（数量数据）。例如：多个时期的数据可能会出现在同一个“事实表”中。“维表”中存放描述性数据，维表是围绕事实表建立的较小的表。星型模型数据如下图：,2、雪花模型 雪花模型是对星型模型的扩展，雪花模型对星型模型的维表进一步层次化，原来的各维表可能被扩展为小的事实表，形成一些局部的“层次”区域。它的优点是最大限度地减少数据存储量，以及把较小的维表联合在一起来改善查询性能。在上

14、面星型模型的数据中，对“产品表”“日期表”“地区表”进行扩展形成雪花模型数据见下图。3、星网模型 星网模型是将多个星型模型连接起来形成网状结构。多个星型模型通过相同的维，如时间维，连接多个事实表。,40,联机分析处理（On Line Analytical Processing，OLAP）的概念最早是由关系数据库之父于1993年提出的。在数据仓库系统中，联机分析处理是重要的数据分析工具。OLAP的基本思想是从多方面和多角度以多维的形式来观察企业的状态和了解企业的变化。,5.3 联机分析处理,41,5.3.1 基本概念,OLAP是在OLTP的基础上发展起来的。OLTP是以数据库为基础的，面对的是操

15、作人员和低层管理人员，对基本数据的查询和增、删、改等进行处理。OLAP是以数据仓库为基础的数据分析处理。它有两个特点：一是在线性（On Line），由客户机/服务器这种体系结构来完成的；二是多维分析，这也是OLAP的核心所在。,1、OLAP的定义,联机分析处理是共享多维信息的快速分析。它体现了四个特征：（1）快速性：用户对OLAP的快速反应能力有很高的要求。（2）可分析性：OLAP系统应能处理任何逻辑分析和统计分析。（3）多维性：系统必须提供对数据分析的多维视图和分析。（4）信息性：OLAP系统应能及时获得信息，并且管理大容量的信息。,43,1993年，提出OLAP的12条准则，其主要的准则有

16、：多维数据分析；客户/服务器结构；多用户支持；一致的报表性能等。,2、OLAP准则,44,1.多维概念视图,企业的数据空间本身就是多维的。因此OLAP的概念模型也应是多维的。用户可以对多维数据模型进行切片、切块、旋转坐标或进行多维的联合（概括和聚集）分析。,45,4.稳定的报表性能,报表操作不应随维数增加而削弱，即当数据维数和数据的综合层次增加时，提供的报表能力和响应速度不应该有明显的降低。,46,5客户/服务器体系结构,OLAP是建立在客户/服务器体系结构上的。要求多维数据库服务器能够被不同的应用和工具所访问。,47,8多用户支持 当多个用户要在同一分析模式上并行工作，需要这些功能的支持。1

17、1灵活的报表生成 报表必须充分反映数据分析模型的多维特征，并可按用户需要的方式来显示它。,OLAP是针对特定问题的联机数据访问和分析。（1）变量：变量是数据的实际意义，即描述数据“是什么”。（2）维：维是人们观察数据的特定角度。如产品维、顾客维、时间维等。（3）维的层次：数据的细节不同程度为维的层次。如日、月、季、年是时间维的层次。（4）维成员：维的一个取值称为该维的一个维成员。如“某年某月某日”是时间维的一个成员。,3、OLAP的基本概念,（5）多维数组：一个多维数组可以表示为：（维1，维2，维n，变量）一个5维的结构，即（产品，地区，时间，销售渠道，销售额）。（6）数据单元（单元格）：多维

18、数组的取值称为数据单元。如：5维数据单元（牙膏，上海，1998年12月，批发，销售额为100000）。,3、OLAP的基本概念,（1）OLTPOLTP是低层人员利用计算机网络对数据库中的数据进行查询、增、删、改等操作，以完成事务处理工作。OLTP利用数据库快速地处理具体业务。OLTP应用要求多个查询并行。,4、OLAP与OLTP的关系与比较,（2）OLAPOLAP是高层人员对数据仓库进行信息分析处理。存取大量的数据 包含聚集的数据 按层次对比不同时间周期的聚集数据 以不同的方式来表现数据 要包含数据元素之间的复杂的计算 能够快速的响应用户的查询,4、OLAP与OLTP的关系与比较,（3）OLA

19、P与OLTP对比（对比表）,53,5.3.2 OLAP的数据组织,MOLAP和ROLAP是OLAP的两种具体形式：ROLAP是基于关系数据库存储方式建立的OLAP。多维数据映射成平面型的关系表。采用星型模型。,54,MOLAP是基于多维数据库存储方式建立的OLAP；表现为“超立方”结构，类似于多维数组的结构。在分析中，需要“旋转”数据立方体以及“切片”、“切块”等操作。,MOLAP和ROLAP的对比表,56,例如，以“产品、城市、时间”三维数据，如图,5.3.3 OLAP的决策支持；OLAP多维数据分析,57,1、基本功能：切片和切块,对三维数据，通过“切片”，分别从城市和产品等不同的角度观察

20、销售情况：,58,钻 取,钻取：例如，1995年各部门销售收入表如下：,59,对时间维进行下钻操作，获得新表如下：,钻 取（续）,60,旋转前的数据,旋 转,61,旋转后的数据,旋 转（续）,62,旋转后再切片,63,2、广义OLAP功能,1、基本代理操作“代理”是一些智能性代理，当系统处于某种特殊状态时提醒分析员。（1）示警报告 定义一些条件，一但条件满足，系统会提醒分析员去做分析。如每日报告完成或月定货完成等通知分析员作分析。（2）异常报告 当超出边界条件时提醒分析员。如销售情况已超出预定义阈值的上限或下限时提醒分析员。,64,2、计算能力 计算引擎用于特定需求的计算或某种复杂计算。3、模

21、型计算 增加模型，如增加系统优化、统计分析、趋势分析等模型，以提高决策分析能力。,2、广义OLAP功能,65,假设有一个5维数据模型，5个维分别为：商店，方案，部门，时间，销售。1三维表查询 在指定“商店=ALL，方案=现有”情况的三维表（行为部门，列为时间和销售量）,、OLAP实例,指定商店、方案后的三维表,2、向下钻取 对汽车部门向下钻取出具体项目的销售情况和利润增长情况。,3、切片表 切片（Slice）操作是除去一些列或行不显示,4、旋转表 这次旋转操作得到1995年的交叉表方案为：现有、计划、差量、差量%。,70,5.4.1 数据仓库的开发 1、数据仓库规划 数据仓库开发的范围怎样?要

22、解决的业务问题是什么？开发的数据仓库的决策支持能力是什么？,5.4 数据仓库的决策支持及实例,71,决策者的需求:对信息的需求 对业务过程的需求 对数据访问的需求,2、定义体系结构,72,确定体系结构,（1）来源：数据应该来自于什么DBMS的源数据？（2）传输：数据通过什么样的网络拓扑结构传送过来？（3）目的地：数据发送到数据仓库的什么硬件环境？（4）元数据：确定存储和访问数据的元数据。（5）变换：编制数据抽取、变换、装载的程序。（6）访问：最终用户怎样才能查询数据？,73,（1）主题域分析 确定所需数据的范围和内容。并建立数据仓库的数据模型：主题域范围 数据仓库的数据模型（2）物理数据库设计

23、 数据的实际存储设计,3、数据仓库设计,74,（1）确定源数据、检查其完整性，进行评价。（2）完成源数据变换到目标数据仓库中去。,4、源系统分析与数据变换设计,75,完成数据加载；评审；元数据加载；系统测试,5、建立数据仓库,76,提供给用户访问的形式：（1）使用现有的特定工具；（2）开发一个最终用户访问程序。,6、用户访问方法的设计和开发,77,5.4.2 数据仓库的决策支持,美国著名的NCR数据仓库公司对数据仓库总结5种决策支持能力。1、报表 2、随机分析 3、预测 4、实时决策 5、事件触发的自动决策,78,1、报表,数据仓库所面临的最大挑战是数据集成。传统的环境经常有上百个数据源，每一

24、数据源都有各自定义的标准和实施技术。建立的数据仓库是通过收集各种来源的数据，来回答预先设置的一些问题，告诉决策者“发生了什么”。它为以后数据仓库的发展奠定了基础。,79,2、随机分析,数据仓库应用的第二种决策支持是，从“发生了什么”转向“为什么会发生”。分析活动就是了解报表数据的涵义，需要更多更详细的数据进行各种角度的分析。在第二阶段的数据仓库主要用于随机分析。,80,3、预测,数据仓库的第三种决策支持是帮助决策者来预测未来，回答“将要发生什么”。数据仓库需要利用历史资料创建预测模型。,81,4、实时决策,数据仓库的第4种决策支持是企业需要准确了解“正在发生什么”，从而需要建立动态数据仓库（实

25、时数据库），用于支持战术型决策，即实时决策。有效地解决当前的实际问题。第1到第3种决策支持的数据仓库都以支持企业内部战略性决策为重点，帮助企业制定发展战略。第4种决策支持侧重在战术性决策支持。动态数据仓库能够逐项产品、逐个店铺、逐秒地作出最佳决策支持。,82,5、事件触发的自动决策,数据仓库的第5种决策支持是由事件触发，利用动态数据库自动决策，达到“希望发生什么”。例如，电子货架标签技术结合动态数据仓库，可以帮助企业按照自己的意愿实现复杂的价格管理自动化，以便以最低的损耗售出最多的存货。,83,5.4.3 数据仓库应用实例,NCR公司成功地开发了很多实际数据仓库系统，在此介绍一例典型的数据仓库

26、系统。实例：金融业数据仓库解决方案 数据仓库是金融银行机构实现客户关系管理（Customer Relationship Management）的核心技术，也是金融银行业竞争优势的来源，主要的应用业务部门为信用卡部、信贷部、市场部和零售业务部等，应用领域是以客户为中心的的分销渠道管理、客户利润分析、客户关系优化、风险评估和管理。,84,银行只有通过以客户为中心（Customer Centric）的数据仓库决策支持系统，才能使用科学的方法实现个性化服务。数据仓库系统存放每一位客户同银行往来的详细的历史交易明细数据，对客户有统一的视图。能帮助银行业务用户以科学的手段快速地分析、模拟和预测客户的个性化

27、需求，进而设计符合客户需求的产品或服务。通过客户喜好的渠道完成交易，是增强商业银行竞争能力最有效的手段。,85,什么是个性化服务呢？可以从客户和银行的观点来看。客户认为个性化服务是：银行知道我（Who）在什么时间（When）、需要什么产品或服务（What）、以我可以接受的价格（How Much）、经由我喜好的分销渠道（Where），对我提供销售。,86,银行的定义是：以有竞争性的产品或服务（What）、在适当的时间（When）、通过适当的分销渠道（Where）、对信用好风险低的客户（Who）、以合理的价格（How Much）和利润（Profitable）完成销售。两者都是在精打细算的前提下，以

28、达成各自的需求和目标。,87,1、分销渠道的分析和管理,银行通过分析知道客户、渠道、产品或服务三者之间的关系；了解客户的购买行为；客户或渠道对业务收入的贡献；哪些客户比较喜好经由什么渠道在何时和银行打交道；目前的分销渠道的服务能力如何；需要增加哪些分销渠道才能达到预期的服务水平。,88,2、利润评价模型,建立所有客户的每一个帐号的利润评价模型，以便了解每一位客户对银行的总利润贡献度。银行可以依客户的利润贡献度安排合适的分销渠道提供服务和销售，知道哪些有利润的客户需要留住，采用什么方法留住客户，交叉销售改善客户的利润贡献度，那些客户应该争取。另外，银行可以模拟和预测，新产品对银行利润的贡献度，或

29、是新政策对银行会产生什么样的财务影响，或是客户流失或留住对银行的整体利润的影响。,89,3、客户关系优化,客户在每一笔交易中都能主动地告诉银行需要什么产品和服务，如定期存款是希望退休养老使用等；银行利用客户购买倾向模型、渠道喜好模型等主动地和客户沟通，达到留住客户和增加利润的目标。,90,4、风险评估和管理,风险评估和管理主要利用各种数学模型进行分析，模拟风险和利润间的关系。银行实现了以客户为中心的个性化服务数据仓库决策支持系统，就可以在满足高利润低风险客户需求的前提下，达成银行收益的极大化。,数据挖掘的兴起,（1）80年在美国召开了第一届国际机器学习研讨会；（2）89年8月于美国底特律市召开

30、的第一届KDD国际学术会议；（3）95年在加拿大召开了第一届知识发现和数据挖掘国际学术会议；（4）我国于87年召开了第一届全国机器学习研讨会。,5.5.1 知识发现与数据挖掘概念,知识发现（KDD）：从数据中发现有用知识的整个过程。数据挖掘（DM）：KDD过程中的一个特定步骤，它用专门算 法从数据中抽取模式（patterns）。KDD过程定义：从大量数据中提取出可信的、新颖的、有用的并能被人理解的模式的高级处理过程。“模式”可以看成是“知识”的雏形，经过验证、完善后形成知识。,KDD过程,5.5.2 数据挖掘方法和技术,（一）归纳学习方法 分为两大类：信息论方法（决策树方法）和集合论方法。1、

31、信息论方法（决策树方法）利用信息论的原理建立决策树或者是决策规则树。（1）ID3方法：Quiulan研制的ID3方法是利用信息论中互信息建立决策树。（2）IBLE方法：我们研制的IBLE方法，是利用信息论中信道容量，寻找数据库中信息量大的多个字段的取值建立决策规则树。,2、集合论方法（1）粗糙集（Rough Set）方法 对数据库中的条件属性集与决策属性集建立上下近似关系，对下近似集合建立确定性规则，对上近似集合建立不确定性规则（含可信度）。（2）关联规则挖掘 在交易事务数据库中，挖掘出不同商品集的关联关系，即发现哪些商品频繁地被顾客同时购买。（3）覆盖正例排斥反例方法 它是利用覆盖所有正例，

32、排斥所有反例的思想来寻找规则。比较典型的有AQ11方法，AQ15方法以及AE5方法。,（二）仿生物技术 仿生物技术典型的方法是神经网络方法和遗传算法。1、神经网络方法：包括：前馈式网络、反馈式网络、自组织网络等多个神经网络方法。2、遗传算法：这是模拟生物进化过程的算法。它由三个基本算子组成：繁殖（选择）、交叉（重组）、变异（突变）遗传算法起到产生优良后代的作用，经过若干代的遗传，将得到满足要求的后代（问题的解）。,（三）公式发现 在工程和科学数据库中对若干数据项（变量）进行一定的数学运算，求得相应的数学公式。1物理定律发现系统BACON BACON发现系统完成了物理学中大量定律的重新发现。2经

33、验公式发现系统FDD 我们研制了FDD发现系统，寻找由数据项的初等函数或复合函数组合成的经验公式。,（四）统计分析方法 利用统计学原理通过对总体中的样本数据进行分析得出描述和推断该总体信息和知识的方法。（五）模糊数学方法 利用模糊集合理论进行数据挖掘，如模糊聚类、模糊分类等。（六）可视化技术 利用可视化技术分析数据库，找到潜在的有用信息。,5.5.3 数据挖掘的知识表示（一）,主要有四种：规则、决策树、浓缩数据、公式。1、规则 规则知识由前提条件和结论两部分组成 前提条件由字段项（属性）的取值的合取（与）和析取（或）组合而成。结论为决策字段项（属性）的取值或者类别组成。,2、决策树例如：上例的

34、人群数据库，按ID3方法得到的决策树如下：,数据挖掘的知识表示（二）,3、知识基（浓缩数据）例如上例的人群数据库，通过计算可以得出身高是不重要的字段，删除它后，再合并相同数据元组，得到浓缩数据如下表：,数据挖掘的知识表示（三）,4、网络权值 神经网络方法经过对训练样本的学习后，所得到的知识是网络连接权值和结点的阈值。,数据挖掘的知识表示（四）,=0.5,5、公式 例如，太阳系行星运动数据中包含行星运动周期（旋转一周所需时间，天），以及它与太阳的距离（围绕太阳旋转的椭圆轨道的长半轴，百万公里），数据如下表：,发现的公式为：d3/p2=25,数据挖掘的知识表示（五）,5.6 数据挖掘的决策支持及应

35、用,5.6.1 数据挖掘的决策支持分类有：关联分析、时序模式、聚类、分类、偏差检测、预测。1、关联分析 若两个或多个数据项的取值之间重复出现且概率很高时，它就存在某种关联，可以建立起这些数据项的关联规则。2、时序模式 通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列的影响。,3、聚类：在数据库中找出一系列有意义的子集，即类。4、分类：对数据库中的类，找出该类别的概念描述规则。5、偏差检测：在数据库中找出异常数据。6、预测：利用历史数据找出变化规律的模型，并用此模型预测未来。,5.6.2 决策树及其应用,1、决策树概念：决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利

36、用信息论原理对大量样本的属性进行分析和归纳而产生的。,数据挖掘的决策树方法的原理是信息论，信息论是为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。一个传递信息的系统是由发送端（信源）和接收端（信宿）以及连接两者的通道（信道）三者组成。信息论把通信过程看做是在随机干扰的环境中传递信息的过程。在这个通信模型中，信息源和干扰（噪声）都被理解为某种随机过程或随机序列。,在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。这种情形就称为信宿对于信源状态具有不确定性。而且这种不确定性是存在于通信之前的。因而又叫做先验不确定性。

37、在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。如果干扰很小，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。,在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。因此，先验不确定性不能全部被消除，只能部分地消除。通信结束之后，信宿还仍然具有一定程度的不确定性。这就是后验不确定性。显然，后验不确定性总要小于先验不确定性，不可能大于先验不确定性。,如果后验不确定性的大小正好等于先验不确定性的大小，这就表示信宿根本没有收到信息。如果后验不确定性的大小等于零，这就表示信宿收到了全部信息。可见，信息是用来消除（

38、随机）不确定性的度量。信息量的大小，由所消除的不确定性的大小来计量。,2、ID3算法,当前国际上最有影响的示例学习方法首推的ID3。ID3引进了信息论中的互信息，他将其称为信息增益（information gain），作为特征判别能力的度量，并且将建树的方法嵌在一个迭代的中。,一、ID3基本思想,某天早晨气候描述为:天气：多云 气温：冷 湿度：正常 风：无风,在一实体世界中，每个实体用多个特征来描述。每个特征限于在一个离散集中取互斥的值。例如，设实体是某天早晨，分类任务是关于气候的类型，特征为:天气 取值为：晴，多云，雨 气温 取值为：冷，适中，热 湿度 取值为：高，正常 风 取值为：有风，无

39、风,它属于哪类气候呢?每个实体属于不同的类别，为简单起见，假定仅有两个类别，分别为P，N。在这种两个类别的归纳任务中，P类和N类的实体分别称为概念的正例和反例。将一些已知的正例和反例放在一起便得到训练集。下表给出一个训练集。由ID3算法得出一棵正确分类训练集中每个实体的决策树，见图。,晴,雨,多云,高,正常,有风,无风,P,N,N,P,P,ID3决策树,决策树叶子为类别名，即P 或者N。其它结点由实体的特征组成，每个特征的不同取值对应一分枝。若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。,用图

40、来判本节开始处的具体例子，得该实体的类别为P类。ID3方法就是要从表的训练集构造图这样的决策树。实际上，能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。,二、ID3算法,（一）主算法 1、从训练集中随机选择一个既含正例又含反例的子集（称为窗口）；2、用“建树算法”对当前窗口形成一棵决策树；3、对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；4、若存在错判的例子，把它们插入窗口，转2，否则结束。,主算法流程用下图表示。其中PE、NE分别表示正例集和反例集，它们共同组成训练集。PE，PE和NE，NE分别表示正例集和反例集的子集。主算法中每迭代

41、循环一次，生成的决策树将会不相同。,ID3主算法流程,（二）建树算法 1、对当前例子集合，计算各特征的互信息；2、选择互信息最大的特征Ak；3、把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；4、对既含正例又含反例的子集，递归调用建树算法；5、若子集仅含正例或反例，对应分枝标上P或N，返回调用处。,3、ID3方法应用实例,对于气候分类问题进行具体计算有：信息熵的计算信息熵：,类别出现概率：|S|表示例子集S的总数，|ui|表示类别ui的例子数。对9个正例和5个反例有：P（u1）=9/14 P（u2）=5/14H（U）=（9/14）log（14/9）+（5/14）log（14/5

42、）=0.94bit,条件熵：,条件熵计算,属性A1取值vj时，类别ui的条件概率：,A1=天气 取值 v1=晴，v2=多云，v3=雨在A1处取值晴的例子5个，取值多云的例子4 个，取值雨的例子5 个，故：P（v1）=5/14 P（v2）=4/14 P（v3）=5/14取值为晴的5 个例子中有2 个正例、3个反例，故：P（u1/v1）=2/5，P（u2/v1）=3/5同理有：P（u1/v2）=4/4，P（u2/v2）=0 P（u1/v3）=2/5，P（u2/v3）=3/5H(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/14)(4/4)log(4/4)+0)

43、+(5/14)(2/5)log(5/2)+(3/5)log(5/3)=0.694bit,互信息计算 对 A1=天气 处有：I（天气）=H（U）-H（U|V）=0.94-0.694=0.246 bit 类似可得：I（气温）=0.029 bit I（湿度）=0.151 bit I（风）=0.048 bit 建决策树的树根和分枝 ID3算法将选择互信息最大的特征天气作为树根，在14个例子中对天气的3个取值进行分枝，3 个分枝对应3 个子集，分别是:F1=1，2，8，9，11，F2=3，7，12，13，F3=4，5，6，10，14 其中F2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正

44、例又含有反例，将递归调用建树算法。,递归建树 分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征）求互信息.（1）F1中的天气全取晴值，则H（U）=H（U|V），有I（U|V）=0，在余下三个特征中求出湿度互信息最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标记N。取值正常的例子全为P类，该分枝标记P。（2）在F3中，对四个特征求互信息，得到风特征互信息最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。这样就得到图的决策树,4、C4.5算法,ID3算法在数据挖掘中占有非常重要的地位。但是，在应用

45、中，ID3算法不能够处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。C4.5是在ID3基础上发展起来的决策树生成算法，由在1993年提出。C4.5克服了ID3在应用中存在的不足。,C4.5的进步（1）用信息增益率来选择属性，它克服了用信息增益选择属性时偏向选择取值多的属性的不足；（2）在树构造过程中或者构造完成之后，进行剪枝；（3）能够完成对连续属性的离散化处理；（4）能够对于不完整数据的处理，例如未知的属性值；（5）C4.5采用的知识表示形式为决策树，并最终可以形成产生式规则。,C4.5构造决策树的算法,Quinlan在ID3中使用信息论中的信息增益（gain）来选择属性，而C4

46、.5采用属性的信息增益率（gain ratio）来选择属性。信息增益率 C4.5对ID3改进是用信息增益率来选择属性。理论和实验表明，采用“信息增益率”（C4.5方法）比采用“信息增益”（ID3方法）更好，主要是克服了ID3方法选择偏向取值多的属性。,5.6.3 决策规则树及应用,IBLE方法：IBLE方法是利用信息论中信道容量来选择属性，比互信息更好。IBLE方法建决策规则树，每个结点由多个属性取值组成，提高了属性组合的识别效果。IBLE比ID3识别率提高了10个百分点。,5.6.4 数据挖掘的决策支持应用领域,1、金融（1）“数据清理”、金融市场分析和预测（2）帐户分类、银行担保和信用评估。2、医疗保健 任务是进行数据清理，预测医疗保健费用。3、市场业 进行市场定位和消费者分析，辅助制定市场策略。,5.6.4 数据挖掘的决策支持应用领域,4、零售业 目前主要应用于销售预测、库存需求、零售点选择和价格分析。5、制造业 进行零部件故障诊断、资源优化、生产过程分析等。6、司法 应用在案件调查、诈骗监测、洗钱认证、犯罪组织分析等工作。,第 5 章 结 束,