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

《数据仓库与数据挖掘的决策支持》由会员分享，可在线阅读，更多相关《数据仓库与数据挖掘的决策支持（122页珍藏版）》请在装配图网上搜索。

1、,,,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,第5章,,数据仓库与数据挖掘,,的决策支持,,,5.1 数据仓库的基本原理,5.1.1 数据仓库概念,,5.1.2 数据仓库结构,,5.1.3 数据集市,,5.1.4 元数据,,5.1.1 数据仓库的概念,（1）在《建立数据仓库》一书中，对数据仓库的定义为：,,,数据仓库是面向,主题的,、,集成的,、,稳定的,，,不同时间,的数据集合，用于支持经营管理中,决策制定,过程。,,,1、数据仓库的概念,（2）SAS软件研究所定义：,,,数据仓库是一种,管理技术,，旨在通过,通畅,、,合

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

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

4、间变化的,,数据仓库内的数据时限在,5,~,10,年，故数据的键码包含时间项，标明数据的历史时期，这适合DSS进行,时间趋势分析,。,,,数据库只包含当前数据，即存取某一时间的正确的有效的数据。,,2、数据仓库特点,,(5)数据仓库的数据量大.,,,大型DW是一个TB（1000GB）级数据库问题（一般为10GB级相当于一般数据库100MB的100倍）,,,(6)数据仓库的硬件要求较高,,,需要一个巨大的硬件平台需要一个并行的数据库系统.,,,最好的数据仓库是大的和昂贵的。,,,近期基本数据：,是最近时期的业务数据，是数据仓库用户,最感兴趣,的部分，数据量大。,,,历史基本数据：,近期基本数据,

5、随时间的推移，由数据仓库的,时间控制机制,转为历史基本数据。,,,轻度综合数据：,是从,近期基本数据,中提取出的，这层数据是按时间段选取，或者按数据属性（attributes）和内容（contents）进行综合。,,高度综合数据层：,这一层的数据是在,轻度综合数据,基础上的再一次综合，是一种准决策数据。,5.1.2 数据仓库结构,,,元数据:,整个数据仓库的组织结构由元数据组织,它不包含数据仓库中的,实际数据信息,。,,,作用：,,（1）定位数据仓库的目录内容,,（2）数据从,业务环境,向,数据仓库环境,传递时数据仓库的目录内容,,（3）指导从,当前基本数据,到,轻度综合数据,到,高度综合数

6、据,的综合算法的选择。,,,组成：,,,（1）数据结构,,（2）用于综合的算法,,（3）从业务环境到DW规划,5.1.2 数据仓库结构,,数据仓库结构图,,1.数据集市的产生,,数据仓库工作范围和成本常常是巨大的。开发数据库是,代价很高,、,时间较长,的大项目。提供更紧密集成的数据集市就应运产生。,,目前，全世界对数据仓库,总投资的一半,以上均集中在数据集市上。,5.1.3 数据集市（Data Mart）,,,数据集市（Data Marts）是一种,更小,、,更集中,的数据仓库，为公司提供分析商业数据的一条廉价途径。,,数据集市是指具有,特定应用,的数据仓库，主要针对某个应用或者具体部门级

7、的应用，支持用户获得竞争优势或者找到进入新市场的具体解决方案,2.数据集市概念,,3.数据集市与数据仓库的,关系,数据集市不等于数据仓库，多个数据集市简单合并起来不能成为数据仓库。,,各数据集市之间对详细数据和历史数据的存储,存在大量冗余,。,,同一个问题在不同的数据集市的查询结果,可能不一致，甚至互相矛盾。,,各数据集市之间以及与源数据库系统之间,难以管理,。,,1、规模小,,2、特定的应用,,3、面向部门,,4、由业务部门定义，设计和开发,,5、由业务部门管理和维护,,6、快速实现,,7、购买较便宜,,8、投资快速回收,,9、工具集的紧密集成,,10、更详细的、预先存在的数据仓库的摘要子集

8、,,11、可升级到完整的数据仓库,4.数据集市的特性,,,5.两种数据集市结构,从属数据集市(Dependent Data Mart),,从属：,数据直接来自中央数据库，能够保持数据的一致性。,,关键业务部门建立从属的数据集市，可以很好的查询反应速度。,,,5.两种数据集市结构,独立数据集市(Independent Data Mart),独立：,数据直接来自各生产系统。,,从投资考虑，用来解决各个部门比较迫切的决策问题。,,6.数据集市与数据仓库的,差别,数据仓库是基于,整个企业,的数据模型建立的，它面向企业范围的主题；,,数据集市是按照,某一特定部门,的数据模型建立的，由于每个部门有自己特定

9、的需求，因此，对他们对数据集市的期望也不一样，也称作部门级数据仓库,,部门的主题与企业的主题之间可能存在关联，也可能不存在关联。,,数据集市的数据组织一般采用星形模型，大型数据仓库的数据组织采用第三范式。,,,元数据,是数据仓库的重要组成部分。元数据描述了数据仓库的数据和环境，即,关于数据的数据,(meta data)。,元数据,就相当于数据库系统中的,数据字典,,元数据包括四种元数据,,关于,数据源,的元数据,,关于,数据模型,的元数据,,关于,数据仓库映射,的元数据,,关于,数据仓库使用,的元数据,5.1.4 元数据,,它是现有的业务系统的数据源的描述信息。这类元数据是对,不同平台,上的

10、数据源的,物理结构,和,含义,的,描述,。具体为：,,（1）数据源中所有物理数据结构，包括所有的数据项及数据类型。,,（2）所有数据项的业务定义。,,（3）每个数据项更新的频率，以及由谁或哪个过程更新的说明。,,（4）每个数据项的有效值。,1、关于,数据源,的元数据,,,这类元数据描述了数据仓库中有什么数据以及数据之间的关系,它们是用户使用管理数据仓库的基础。这类元数据可以,支持用户,从数据仓库中,获取数据。,,,,数据仓库的数据模型是星型模型。,,通常,企业数据模型,被用作建立仓库数据模型的,起始点,，再对模型加以修改和变换。,,2、关于,数据模型,的元数据,,,这类元数据是数据源与数据仓库

11、数据间的映射。,,,当数据源中的一个数据项与数据仓库建立了映射关系，就应该记下这些数据项发生的任何变换或变动。,即用元数据反映数据仓库中的数据项是从哪个特定的数据源填充的，经过那些转换、变换和加载过程,3、关于,数据仓库映射,的元数据,,3、关于,数据仓库映射,的元数据,一个抽取要经过以下几个步聚,,获取,,过滤,,验证,,融合,,综合,,装载,,存档,从源系统的数据到数据仓库中的目标数据的转移是一项复杂的工作，其工作量占整个数据仓库开发的,70%,,这类元数据是数据仓库中信息的使用情况描述。,,数据仓库的用户最关心的是两类元数据：,,,（1）元数据告诉数据仓库中有什么数据，它们从哪里来。即,

12、如何按主题查看数据仓库的内容,。,,（2）元数据提供,已有的可重复利用的查询语言信息,。如果某个查询能够满足他们的需求，或者与他们的愿望相似，他们就可以再次使用那些查询而不必从头开始编程。,,关于数据仓库使用的元数据能帮助用户到数据仓库查询所需要的信息，用于解决企业问题。,4、关于,数据仓库使用,的元数据,,5.2 数据仓库系统,,5.2.1数据仓库系统结构,,,数据仓库系统由数据仓库（DW）、仓库管理和分析工具三部分组成,,1、数据仓库管理系统,（1）定义部分,,,用于定义和建立数据仓库系统。它包括：,,设计和定义数据仓库的数据库,,定义数据来源,,确定从源数据向数据仓库复制数据时的清理和

13、增强规则,,（,2,）数据获取部分,,,该部件把数据从源数据中提取出来，依定义部件的规则，抽取、转化和装载数据进入数据仓库。,,,,（3）管理部分,,它用于管理数据仓库的工作，包括：,,对数据仓库中数据的维护,,把仓库数据送出给分散的仓库服务器或,DSS,用户,,对仓库数据的安全、归档、备份、恢复等处理工作,,1、数据仓库管理系统,,（4）信息目录部件（元数据）,,,数据仓库的目录数据是元数据，由三部分组成：,,,技术目录：,由定义部件生成，关于数据源、目标、清理规则、变换规则以及数据源和仓库之间的映象信息。,,,业务目录：,由仓库管理员生成，关于仓库数据的来源及当前值；预定义的查询和报表细节

14、；合法性要求等。,,,信息引导器：,使用户容易访问仓库数据。利用固定查询或建立新的查询，生成暂时的或永久的仓库数据集合的能力等。,,（5）DBMS部分,,,DW的存储形式仍为关系型数据库。,1、数据仓库管理系统,,,分析工具集分两类工具：,,（1）查询工具,,数据仓库的查询不是指对记录级数据的查询，而是指对分析要求的查询。,,一般包含：,,,可视化工具：,以图形化方式展示数据，可以帮助了解数据的结构、关系以及动态性。,2、数据仓库,工具集,,,多维分析工具（OLAP工具）:,,通过对信息的多种可能的观察形式进行快速、一致和交互性的存取，这样便利用户对数据进行深入的分析和观察。,,多维数据的每一

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

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

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

18、,,在上面星型模型的数据中 ，对“产品表”“日期表”“地区表”进行扩展形成雪花模型数据见下图。,5.2.2 数据仓库的存储,,,3、星网模型,,星网模型是将多个星型模型连接起来形成网状结构。多个星型模型通过相同的维，如时间维，连接多个事实表。,5.2.2 数据仓库的存储,,第（,2）部分,,5.3 联机分析处理（OLAP）,,,,5.4 数据仓库的决策支持,,,5.3 联机分析处理,联机分析处理（On Line Analytical Processing，OLAP）,的概念最早是由关系数据库之父(科德)于1993年提出的。,,在数据仓库系统中，联机分析处理是重要的数据分析工具,。,,OLA

19、P的基本思想是从,多方面,和,多角度,以多维的形式来观察企业的状态和了解企业的变化。,,,5.3.1,基本概念,OLAP,是在,OLTP,(联机事务处理系统 )的基础上发展起来的。,,OLTP,是以数据库为基础的，面对的是操作人员和低层管理人员，对基本数据的查询和增、删、改等进行处理。,,OLAP,是以数据仓库为基础的数据分析处理。它有两个特点：,,一是在线性（On Line），由客户机/服务器这种体系结构来完成的；,,二是多维分析，这也是OLAP的核心所在。,,1、OLAP的定义,联机分析处理是共享多维信息的快速分析。,,它体现了四个特征：,,（1）快速性,：用户对OLAP的快速反应能力有很

20、高的要求。,,（2）可分析性,：OLAP系统应能处理任何逻辑分析和统计分析。,,（3）多维性,：系统必须提供对数据分析的多维视图和分析。,,（4）信息性,：OLAP系统应能及时获得信息，并且管理大容量的信息。,,,2、OLAP准则,,1993年，提出OLAP的12条准则，其主要的准则有：,,,1）多维数据分析；,,2）客户/服务器结构；,,3）多用户支持；,,4）一致的报表性能等。,,,,2、OLAP准则,,多维概念视图,,企业的数据空间本身就是多维的。因此,OLAP,的概念模型也应是多维的。,,用户可以对多维数据模型进行,切片、切块、旋转坐标或进行多维的联合,（概括和聚集）分析。,,,,稳定

21、的报表性能,,报表操作,不应,随维数增加而削弱，即当数据维数和数据的综合层次增加时，,提供的报表能力和响应速度不应该有明显的降低,。,,2、OLAP准则,,,,客户,/,服务器体系结构,,,OLAP,是建立在客户,/,服务器体系结构上的。,,要求多维数据库服务器能够被不同的应用和工具所访问。,2、OLAP准则,,,,多用户支持,,,当多个用户要在同一分析模式上并行工作，需要这些功能的支持。,,灵活的报表生成,,,报表必须,充分反映,数据分析模型的,多维特征,，并可按用户需要的方式来显示它。,,2、OLAP准则,,,3、OLAP的基本概念,OLAP是针对特定问题的联机数据访问和分析。,,,（1）

22、变量,：变量是数据的实际意义，即描述数据“是什么”。,,,（2）维,：维是人们观察数据的特定角度。如产品维、顾客维、时间维等。,,,（3）维的层次,：数据的细节不同程度为维的层次。如日、月、季、年是时间维的层次。,,,（4）维成员,：维的一个取值称为该维的一个维成员。如“某年某月某日”是时间维的一个成员。,,3、OLAP的基本概念,5）多维数组,：一个多维数组可以表示为：,,（维1，维2，……，维n，变量）,,一个5维的结构，即（产品，地区，时间，销售渠道，销售额）。,,（6）数据单元（单元格）,：,,多维数组的取值称为数据单元。,,如：5维数据单元（牙膏，上海，1998年12月，批发，销售额

23、为100000）。,,,,4、OLAP与OLTP的关系与比较,（1）OLTP,(联机事务处理系统 ),,OLTP是低层人员利用计算机网络对数据库中的数据进行查询、增、删、改等操作，以完成事务处理工作。,,OLTP利用数据库快速地处理具体业务。OLTP应用要求多个查询并行。,,,,4、OLAP与OLTP的关系与比较,（2）OLAP,,OLAP是高层人员对数据仓库进行信息分析处理。,,①存取大量的数据,,②包含聚集的数据,,③按层次对比不同时间周期的聚集数据,,④以不同的方式来表现数据,,⑤要包含数据元素之间的复杂的计算,,⑥能够快速的响应用户的查询,,,,4、OLAP与OLTP的关系与比较,（3

24、）OLAP与OLTP对比（对比表）,,OLTP,,OLAP,,数据库数据,,数据仓库数据,,细节性数据,,综合性数据,,当前数据,,历史数据,,一次性处理的数据量小,,一次处理的数据量大,,对响应时间要求高,,响应时间合理,,用户数量大,,用户相对较少,,面向应用，事务驱动,,面向分析，分析驱动,,,,5.3.2 OLAP的数据组织,,MOLAP(多维OLAP),和,ROLAP(关系OLAP),是OLAP的两种具体形式：,,ROLAP,是基于,关系数据库,存储方式建立的OLAP。多维数据映射成平面型的关系表。采用星型模型。,,MOLAP,是基于,多维数据库,存储方式建立的OLAP；表现为“超立

25、方”结构，类似于多维数组的结构。,,在分析中，需要“旋转”数据立方体以及“切片” 、“切块”等操作。,,,MOLAP和ROLAP的对比表,MOLAP,ROLAP,,固定维,,可变维,,维交叉计算,,多维视图,,行级计算,,超大型数据库,,读-写应用,,维数据变化速度快,,数据集市,,数据仓库,,,例如，以“产品、城市、时间”三维数据，如图,,5.3.3 OLAP的决策支持：,,OLAP多维数据分析,,1、基本功能：切片和切块,,对三维数据，通过“切片” ，分别从城市和产品等不同的角度观察销售情况：,,,2）钻 取,钻取：例如，1995年各部门销售收入表如下：,,对时间维进行下钻操作，获得新表如

26、下：,钻 取（续）,,旋转前的数据,旋 转,,,旋转后的数据,旋 转（续）,,,旋转后再切片,,,假设有一个5维数据模型，5个维分别为：商店，方案，部门，时间，销售。,,,,1．三维表查询,,在指定“商店=ALL，方案=现有”情况的三维表（行为部门，列为时间和销售量）,、OLAP实例,,,,,1994,,1995,,%,增长率,,销售量,,利润增长,%,,销售量,,利润增长,%,,销售量,,利润增长,,服装,,234,670,,27.2,,381,102,,21.5,,62.4,,(20.0),,家具,,62,548,,33.8,,66,005,,31.1,,5.6,,(8.0),,汽车,,3

27、75,098,,22.4,,325,402,,27.2,,(13.2),,21.4,,所有其它,,202,388,,21.3,,306,677,,21.7,,50.7,,1.9,,指定商店、方案后的三维表,,,,,1994,,1995,,%增长率,,销售,,利润增长%,,销售,,利润增长%,,销售,,利润增长,,汽车,,375,098,,22.4,,325,402,,27.2,,(13.2),,21.4,,维修,,195,051,,14.2,,180,786,,15.0,,(7.3),,5.6,,附件,,116,280,,43.9,,122,545,,47.5,,5.3,,8.2,,音乐,,6

28、3,767,,8.2,,22,071,,14.2,,(63.4),,7.3,,2、向下钻取,,对汽车部门向下钻取出具体项目的销售情况和利润增长情况。,,,,,1995,,Sales,,服装,,381,102,,家具,,66,005,,汽车,,325,402,,所有其它,,306,677,,3、切片表,,切片（Slice）操作是除去一些列或行不显示,,,,,1995,,销售量,,现有,,计划,,差量,,差量%,,服装,,381,102,,350,000,,31,102,,8.9,,家具,,66,005,,69,000,,(2,995),,(4.3),,汽车,,325,402,,300,000,,

29、25,402,,8.5,,所有其它,,306,677,,350,000,,(44,322),,12.7,,4、旋转表,,这次旋转操作得到1995年的交叉表方案为：现有、计划、 差量、差量%。,,5.4.2 数据仓库的决策支持,美国著名的NCR数据仓库公司对数据仓库总结5种决策支持能力。,,,1、报表,,2、随机分析,,3、预测,,4、实时决策,,5、事件触发的自动决策,,,1、报表,数据仓库所面临的,最大挑战是数据集成,。传统的环境经常有上百个数据源，每一数据源都有各自定义的标准和实施技术。,,建立的数据仓库是通过收集各种来源的数据，来,回答预先设置的一些问题，告诉决策者“发生了什么”,。它为

30、以后数据仓库的发展奠定了基础。,,,,2、随机分析,数据仓库应用的第二种决策支持是，,从“发生了什么”转向“为什么会发生”。,分析活动就是了解报表数据的涵义，需要更多更详细的数据进行各种角度的分析。在第二阶段的数据仓库主要用于随机分析。,,,,3、预测,数据仓库的第三种决策支持是帮助决策者来预测未来，,回答“将要发生什么”,。,,数据仓库需要利用历史资料创建预测模型。,,4、实时决策,数据仓库的第4种决策支持是企业需要准确了解,“正在发生什么”,，从而需要建立动态数据仓库（实时数据库），用于支持战术型决策，即实时决策。有效地解决当前的实际问题。,,第1到第3种决策支持的数据仓库都以支持企业,内

31、部战略性决策为重点,，帮助企业制定发展战略。,,,第4种决策支持侧重在战术性决策支持。,,动态数据仓库能够逐项产品、逐个店铺、逐秒地作出最佳决策支持。,,,5、事件触发的自动决策,数据仓库的第5种决策支持是由事件触发，利用动态数据库自动决策，,达到“希望发生什么”,。,,例如，电子货架标签技术结合动态数据仓库，可以帮助企业按照自己的意愿实现复杂的价格管理自动化，以便以最低的损耗售出最多的存货。,,,5.5 知识发现与数据挖掘,,,5.6 数据挖掘的决策支持及应用,第（3）部分,,演变阶段,商业问题,支持技术,产品厂家,产品特点,数据搜集（20,,世纪60年代）,数据访问（20,,世纪80年代）

32、,数据仓库决策,,支持（20世纪,,90年代,数据挖掘（正,,在流行）,“过去五年中整个有关,,联锁超市总收入是,,多少？”,“联锁超市第一分部去,,年三月的销售额是,,多少？”,“联锁超市第一分部去,,年三月的销售额是多,,少？第二分部据此可,,得出什么结论？”,“下个月第二分部的,,销售会怎么样？,,为什么？”,计算机、磁带和磁盘,关系数据库,,（RDBMS），,,查询语言（SQL），,,ODBC,OLAP、多维数据库和,,数据仓库,高级算法、多处理器,,计算机和海量数据库,IBM和CDC,Oracle、Sybase,,、Informix、,,IBM和,,Microsoft,Pilot、C

33、omshare,,、Arbor、,,Cognos和,,Microstrategy,Pilot、Lockheed,,、IBM、SGI,,和其他初创公司,提供历史性的静态,,的数据,在记录级提供历史性,,动态数据,在各种层次上提供,,回溯的动态数据,提供预测性信息,表5-1 数据挖掘的演变进程,,产 品,Clementine,Darwin,Data mining Workstation,Data Engine,IBM Intelligent Miner,F-DBMS,IDIS,Information Harvester,Knowledge Seeker,Neural Ware,Priso

34、n,Re Mind,技 术,供应商,规则归纳,神经网络、遗传算法等,神经网络,神经网络、模糊逻辑、信号处理,多种技术,分数维,规则发现,模糊专家系统,规则发现、决策树,神经网络,神经网络,基于实例的推理、归纳逻辑,Ingegral Solutions,Thinking Machines Corp.,HNC Software Inc.,MIT Gmbh,IBM Corp.,Cross/Z International Inc.,Informational Discovery Inc.,Informational Harvesting,Angoss Software Int’1 Ltd..

35、,Neural Ware Inc.,Nestor Inc.,Cognitive Systems,表5-2 一些主要的数据挖掘产品,,数据挖掘的兴起,（1）80年在美国召开了第一届国际机器学习研讨会；,,（2）89年8月于美国底特律市召开的第一届KDD国际学术会议；,,（3）95年在加拿大召开了第一届知识发现和数据挖掘国际学术会议；,,（4）我国于87年召开了第一届全国机器学习研讨会。,,5.5.1 知识发现与数据挖掘概念,知识发现（KDD）：,从数据中发现有用知识的整个过程。,,KDD过程定义：,,,从数据集中提取出可信的、新颖的、潜在有用的,以及最终可理解的,模式,的高级处理过程。,,,“模

36、式”,可以看成是,“知识”,的雏形，经过验证、完善后形成知识。,,数据挖掘（DM）：,KDD过程中的一个特定步骤，它用专门算 法从数据中抽取模式（patterns）。,,,数据源,数据,数据集成,目标数据,预处理后,,数据,转换数据,模式,知识,数据选择,预处理,数据挖掘,数据转换,结果表达和解释,数据准备,数据挖掘,结果表达和解释,KDD过程,,5.5.2 数据挖掘方法和技术,（一）归纳学习方法,,分为两大类：信息论方法（决策树方法）和集合论方法,,,1、信息论方法（决策树方法）,,利用信息论的原理建立决策树或者是决策规则树。,,,（1）ID3方法：,Quiula

37、n研制的ID3方法是利用信息论中互信息建立决策树。,,,（2）IBLE方法：,我们研制的IBLE方法，是利用信息论中信道容量，寻找数据库中信息量大的多个字段的取值建立决策规则树。,,2、集合论方法,,,（1）粗糙集（Rough Set）方法,,对数据库中的条件属性集与决策属性集建立上下近似关系，对下近似集合建立确定性规则，对上近似集合建立不确定性规则（含可信度）。,,（2）关联规则挖掘,,,在交易事务数据库中，挖掘出不同商品集的关联关系，即发现哪些商品频繁地被顾客同时购买。,5.5.2 数据挖掘方法和技术,,（二）仿生物技术,,仿生物技术典型的方法是神经网络方法和遗传算法。,,,1、神经网络方

38、法：,包括：前馈式网络、反馈式网络、自组织网络等多个神经网络方法。,,,2、遗传算法：,这是模拟生物进化过程的算法。,,它由三个基本算子组成：,,繁殖（选择）、交叉（重组）、变异（突变）,,遗传算法起到产生优良后代的作用，经过若干代的遗传，将得到满足要求的后代（问题的解）。,5.5.2 数据挖掘方法和技术,,（三）公式发现,,,在工程和科学数据库中对若干数据项（变量） 进行一定的数学运算，求得相应的数学公式。,,,,1．物理定律发现系统BACON,,,BACON发现系统完成了物理学中大量定律的重新发现。,,,,2．经验公式发现系统FDD,,,我们研制了FDD发现系统，寻找由数据项的初等函数或复

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

40、 和析取（或,,）组合而成。,,,,结论,为决策字段项（属性）的取值或者类别组成。,,,,2、决策树,,例如：上例的人群数据库，按ID3方法得到的决策树如下：,,数据挖掘的知识表示（二）,,3、知识基（浓缩数据）,,,例如上例的人群数据库，通过计算可以得出,身高,是不重要的字段，删除它后，再合并相同数据元组，得到浓缩数据如下表：,数据挖掘的知识表示（三）,,5、公式,,例如，太阳系行星运动数据中包含行星运动周期（旋转一周所需时间，天），以及它与太阳的距离（围绕太阳旋转的椭圆轨道的长半轴，百万公里），数据如下表：,发现的公式为：d,3,/p,2,=25,数据挖掘的知识表示（五）,,

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

42、据挖掘的决策支持及应用,,5.6.2 决策树及其应用,1、决策树概念：,,,决策树是用样本的,属性,作为结点，用属性的,取值,作为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。,,根结点是所有样本中信息量最大的属性,.,,中间节点是该结点为根据的子树所包含的样本子集中信息量最大的属性,.,每个内部节点表示在一个属性上的测试,,每个分枝代表一个测试输出,,,每个树叶节点是样本的类别值,.,,5.6.2 决策树及其应用,决策树对新样本的分类过程:,,,即通过新样本属性值的测试,,从根结点开始按照样本属性的取值,,,逐渐沿着决策树向下,,,直到树的叶结点,,,该叶结点表示的

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

44、这种不确定性是存在于通信之前的。因而又叫做,先验不确定性,。,,在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。,,如果干扰很小，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。,5.6.2 决策树及其应用,,在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。因此，先验不确定性不能全部被消除，只能部分地消除。,,通信结束之后，信宿还仍然具有一定程度的不确定性。这就是,后验不确定性,。,,显然，后验不确定性总要小于先验不确定性，不可能大于先验不确定性。,5.6.2 决策树及其应用,,如果后验不确定性的大

45、小正好等于先验不确定性的大小，这就表示,信宿,根本没有收到信息。,,如果后验不确定性的大小等于零，这就表示信宿收到了全部信息。,,可见，,信息是用来消除（随机）不确定性的度量。信息量的大小，由所消除的不确定性的大小来计量。,5.6.2 决策树及其应用,,信息论基本概念,,定义,1,：若存在,n,个相同概率的消息，则每个消息的概率,p,是,1/n,，一个消息传递的信息量为,-Log,2,(1/n),,概率越大,,,信息量越小,,,如英语有,26,个字母,,,假如每个字母在文章中出现的次数平均的话,,,每个字母的信息量为,:,,I(e,)=-log,2,1/26=4.7,,如常用汉字有,2500,

46、个,,,假如每个汉字在文章中出现的次数平均的话,,,每个汉字的信息量为,:,,I(e,)=-log,2,1/2500=11.3,,5.6.2 决策树及其应用,,定义,2,：若有,n,个消息，其给定概率分布为,P=(p1,p2…,pn,),，则由该,分布传递的信息量,称为,P,的熵，记为,定义,3,：若一个记录集合,T,根据类别,属性,的值被分成互相独立的类,C1,C2..Ck,，,,则识别,T,的一个元素所属哪个类所需要的信息量为,Info(T,)=,I(p,),，其中,P,为,C1,C2…Ck,的概率分布，即,P=(|C,1,|/|T|,…..|C,k,|/|T|),5.6.2 决策树及其应

47、用,,定义4：若先根据非类别属性X的值将T分成集合T,1,, T,2,, … T,n,，则确定T中一个元素类的信息量可通过确定T,i,的,加权平均值,来得到，即Info(T,i,)的加权平均值为：,,,Info(X, T)= ((|T,i,|/|T|)Info(T,i,)),,5.6.2 决策树及其应用,定义,5,：信息增益度是两个信息量之间的差值，其中一个信息量是需确定,T,的一个元素的信息量，另一个信息量是在已得到的属性,X,的值后需确定的,T,一个元素的信息量，信息增益度公式为：,,,Gain(X,, T)=,Info(T)-Info(X,, T),,2、ID3算法,

48、当前国际上最有影响的示例学习方法首推,的,ID3,。,,,ID3,以信息论为基础,,,以,互信息,(,信息增益,,,Inf,,ormation,gain,）,和信息熵为衡量标准,,,从而实现对数据的归类分类,.,,2、ID3算法,工作过程,:,,首先找出最有判别力,(,信息增益,,information gain),的属性,,,把数据分成多个子集,,,每个子集又选择最有判别力的属性进行划分,,,一直进行到所有子集仅包含同一类型的数据为止,.,,最后得到一棵决策树,,,可用它来对新的实例进行分类,.,,训练集,,PE、NE,取子集建窗口,窗口,,PE`、NE,`,生成,,决策树,测试,,PE、N

49、E,扩展窗口,,PE`=PE`+PE``NE`=NE`+NE``,此决策树为最后结果,存在错判的,,PE``，NE``吗,是,否,ID3主算法流程,（一）主算法,,1、,从训练集中随机选择一个既含,正例,又含,反例,的子集（称为"窗口"）；,,2、,用“建树算法”对当前窗口形成一棵,决策树,；,,3、,对训练集（窗口除外）中例子用所得决策树进行类别判定，找出,错判,的例子；,,4、,若存在错判的例子，把它们插入窗口，转2，否则结束。,主算法中每迭代循环一次，生成的决策树将会不相同。,,（二）建树算法,,,1、,对当前例子集合，计算各特征的,互,信息；,,,2、,选择互信息最大的特征,Ak,；,

50、,,3、,把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；,,,4、,对既含正例又含反例的子集，递归调用建树算法；,,,5、,若子集仅含正例或反例，对应分枝标上P或N，返回调用处。,二、ID3算法,,,在一实体世界中，每个实体用多个特征来描述。每个特征限于在一个离散集中取,互斥,的值。例如，设实体是某天早晨，分类任务是关于气候的类型，特征为:,,,,天气,取值为： 晴，多云，雨,,,气温,取值为： 冷 ，适中，热,,,湿度,取值为： 高 ，正常,,,风,取值为： 有风， 无风,某天早晨气候描述为:,,,天气,： 多云,,,气温,： 冷,,,湿度,： 正常,

51、,,风,： 无风,3、ID3方法应用实例,,它属于哪类气候呢,?,,每个实体属于不同的类别，为简单起见，假定仅有两个类别，分别为,P,，,N,。,在这种两个类别的归纳任务中，,P,类和,N,类的实体分别称为概念的正例和反例,,,将一些已知的正例和反例放在一起便得到训练集。,,,下表给出一个训练集。由,ID3,算法得出一棵正确分类训练集中每个实体的决策树，见图。,3、ID3方法应用实例,,NO.,属性,,,,类别,,天气,气温,湿度,风,,1,晴,热,高,无风,N,2,晴,热,高,有风,N,3,多云,热,高,无风,P,4,雨,适中,高,无风,P,5,雨,冷,正常,无风,P,6,雨,冷,正常,有

52、风,N,7,多云,冷,正常,有风,P,8,晴,适中,高,无风,N,9,晴,冷,正常,无风,P,10,雨,适中,正常,无风,P,11,晴,适中,正常,有风,P,12,多云,适中,高,有风,P,13,多云,热,正常,无风,P,14,雨,适中,高,有风,N,,天 气,湿 度,风,晴,雨,多云,高,正常,有风,无风,P,N,N,P,P,ID3决策树,决策树叶子为类别名，即,P,或者,N,。,其它结点由实体的特征组成，每个特征的不同取值对应一分枝。,,若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。,

53、,能正确分类训练集的决策树不止一棵。,,Quinlan,的,ID3,算法能得出结点最少的决策树。,,3、ID3方法应用实例,,对于气候分类问题进行具体计算有：,,⒈ 信息熵的计算,,信息熵：,,类别出现概率：,,|S|表示例子集,S,的总数，|u,i,|表示类别u,i,的例子数。,,对9个正例和5个反例有：,,P（u,1,）=9/14 P（u,2,）=5/14,,H（U,）=（9/14）log,2,（14/9）+（5/14）log,2,（14/5）,,=0.94bit,3、ID3方法应用实例,,条件熵：,⒉ 条件熵计算,属性A,1,取值v,j,时，类别u,i,的条件概率：,,A,1,=天气

54、 取值 v,1,=晴，v,2,=多云，v,3,=雨,,在A,1,处,取值晴,的例子5个，,取值多云,的例子4个，,取值雨,的例子5个，故,,,P（v,1,）=5/14 P（v,2,）=4/14 P（v,3,）=5/14,,取值为晴,的5个例子中有2个正例、3个反例，故：,,,P（u,1,/v,1,）=2/5， P（u,2,/v,1,）=3/5,,同理有：,P（u,1,/v,2,）=4/4， P（u,2,/v,2,）=0,,,P（u,1,/v,3,）=2/5， P（u,2,/v,3,）=3/5,,H(U/V)=(5/14)(,(2/5)log(5/2)+(3/5)log(5/3)),+,,

55、,(4/14),((4/4)log(4/4)+0,),+,,,(5/14),((2/5)log(5/2)+(3/5)log(5/3)),,= 0.694bit,,⒊ 互信息计算,,,对 A,1,=天气 处有：,,,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，

56、8，9，11}，F2={3，7，12，13}，F3={4，5，6，10，14},,,其中F2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用,建树算法,。,,⒌ 递归建树,,,分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征）求互信息.,,,（1）,F1中的天气全取晴值，则H（U）=H（U|V），有I（U|V）=0，在余下三个特征中求出,湿度,互信息,最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标记N。取值正常的例子全为P类，该分枝标记P。,,,（2）,在F3中，对四个特征求互信息，得到,风,特征,互信息,最

57、大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。,天 气,湿 度,风,晴,雨,多云,高,正常,有风,无风,P,N,N,P,P,ID3决策树,,4、C4.5算法,,ID3算法在数据挖掘中占有非常重要的地位。但是，在应用中，ID3算法不能够处理,连续属性,、计算信息增益时偏向于选择取值,较多的属性,等不足。,,C4.5是在ID3基础上发展起来的决策树生成算法，由在1993年提出。C4.5克服了ID3在应用中存在的不足。,,,C4.5的进步,,,（1）,用,信息增益率,来选择属性，它克服了用信息增益选择属性时偏向选择,取值多,的属性的不足；

58、,,,（2）,在树构造过程中或者构造完成之后，进行,剪枝,；,,,（3）,能够完成对,连续属性,的离散化处理；,,,（4）,能够对,不完整,数据的处理，例如未知的属性值；,,,（5）,C4.5采用的知识表示形式为决策树，并最终可以形成产生式规则。,4、C4.5算法,,C4.5构造决策树的算法,Quinlan在ID3中使用信息论中的信息增益（gain）来选择属性，而C4.5采用属性的信息增益率（gain ratio）来选择属性。,,信息增益率,,,理论和实验表明，采用“信息增益率”（C4.5方法）比采用“信息增益”（ID3方法）更好，,主要是克服了ID3方法选择偏向取值多的属性。,,5.6.3

59、决策规则树及应用,IBLE方法：,,IBLE方法是利用信息论中,信道容量,来选择属性，比互信息更好。IBLE方法建决策规则树，每个结点由,多个属性,取值组成，提高了属性组合的识别效果。,,属性的选取通过计算各属性信道容量进行,.,,各属性的正例标准值由译码函数决定,.,,结点中判别正反例的阈值,(,wn,wp,),是由实例中权值变化的规律来确定的,.,,IBLE,比,ID3,识别率提高了,10,个百分点。,,5.6.4 数据挖掘的决策支持应用领域,1、金融,,（1）“数据清理”、金融市场分析和预测,,（2）帐户分类、银行担保和信用评估。,,,2、医疗保健,,任务是进行数据清理，预测医疗保健费用。,,,3、市场业,,,进行市场定位和消费者分析，辅助制定市场策略。,,5.6.4 数据挖掘的决策支持应用领域,4、零售业,,目前主要应用于销售预测、库存需求、零售点选择和价格分析。,,,5、制造业,,进行零部件故障诊断、资源优化、生产过程分析等。,,,6、司法,,应用在案件调查、诈骗监测、洗钱认证、犯罪组织分析等工作。,,