2009-8-20 高级人工智能 史忠植 1
第九章 知识发现和数据挖掘数据库中知识发现史忠植中科院计算所
2009-8-20 高级人工智能 史忠植 2
知识发现
关联规则
数据仓库
知识发现工具
2009-8-20 高级人工智能 史忠植 3
知识发现知识发现是指从数据集中抽取和精炼新的模式。
范围非常广泛,经济、工业、农业、军事、社会
数据的形态多样化,数字、符号、图形、图像、声音
数据组织各不相同,结构化、半结构化和非结构
发现的知识可以表示成各种形式规则、科学规律、方程或概念网。
2009-8-20 高级人工智能 史忠植 4
数据库知识发现目前,关系型数据库技术成熟、应用广泛。
因此,数据库知识发现 (Knowledge Discovery
in Databases KDD)的研究非常活跃。
该术语于 1989年出现,Fayyad定义为
,KDD是从数据集中识别出有效的、新颖的、
潜在有用的，以及最终可理解的模式的非平凡过程,
2009-8-20 高级人工智能 史忠植 5
不同的术语名称知识发现是一门来自不同领域的研究者关注的交叉性学科，因此导致了很多不同的术语名称。
知识发现,人工智能和机器学习界。
数据挖掘 (data mining):
统计界、数据分析、数据库和管理信息系统界
知识抽取 (information extraction)、
信息发现 (information discovery)、
智能数据分析 (intelligent data analysis)、
探索式数据分析 (exploratory data analysis)
信息收获 (information harvesting)
数据考古 (data archeology)
2009-8-20 高级人工智能 史忠植 6
2009-8-20 高级人工智能 史忠植 7
知识发现的任务 (1)
数据总结：
对数据进行总结与概括。传统的最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值,或者用直方图、饼状图等图形方式表示。
分类：
根据分类模型对数据集合分类。分类属于有导师学习,一般需要有一个训练样本数据集作为输入。
聚类：
根据数据的不同特征，将其划分为不同的类。无导师学习
2009-8-20 高级人工智能 史忠植 8
知识发现的任务 (2)
相关性分析：
发现特征之间或数据之间的相互依赖关系关联规则
偏差分析：
基本思想是寻找观察结果与参照量之间的有意义的差别。通过发现异常,可以引起人们对特殊情况的加倍注意。
建模：
构造描述一种活动或状态的数学模型
2009-8-20 高级人工智能 史忠植 9
知识发现的方法 (1)
统计方法：
传统方法：
回归分析、判别分析、聚类分析、探索性分析
模糊集 (fuzzy set) Zadeh 1965
支持向量机 (Support Vector Machine) Vapnik 90
年代初
粗糙集 (Rough Set) Pawlak 80年代初
2009-8-20 高级人工智能 史忠植 10
知识发现的方法 (2)
机器学习：
规则归纳,AQ算法
决策树,ID3,C4.5
范例推理,CBR
遗传算法,GA
贝叶斯信念网络
2009-8-20 高级人工智能 史忠植 11
知识发现的方法 (3)
神经计算：
神经网络是指一类新的计算模型，它是模仿人脑神经网络的结构和某些工作机制而建立的一种计算模型。常用的模型：
Hopfield网
多层感知机
自组织特征映射
反传网络
可视化：
2009-8-20 高级人工智能 史忠植 12
KDD的技术难点
动态变化的数据
噪声
数据不完整
冗余信息
数据稀疏
超大数据量
2009-8-20 高级人工智能 史忠植 13
关联规则属于知识发现任务中的相关性分析由于条形码技术的发展,零售部门可以利用前端收款机收集存储大量的售货数据 。 因此,如果对这些历史事务数据进行分析,则可对顾客的购买行为提供极有价值的信息 。 例如,可以帮助如何摆放货架上的商品
(如把顾客经常同时买的商品放在一起 ),帮助如何规划市场 (怎样相互搭配进货 )。
2009-8-20 高级人工智能 史忠植 14
关联规则的表示关联规则的形式如,在购买面包顾客中,有 70%的人同时也买了黄油,,可以表示成,面包 → 黄油 。
用于关联规则发现的主要对象是事务型数据库,其中针对的应用则是售货数据,也称货篮数据 。 一个事务一般由如下几个部分组成,事务处理时间,一组顾客购买的物品,有时也有顾客标识号 (如信用卡号 )。
2009-8-20 高级人工智能 史忠植 15
关联规则的相关概念 (1)
设 R={I1,I2…… Im}是一组物品集,W是一组事务集 。 W
中的每个事务 T是一组物品,T?R。
假设有一个物品集 A,一个事务 T,如果 A?T,则称事务 T支持物品集 A。
关联规则是如下形式的一种蕴含,A→B,其中 A,B是两组物品,A?I,B?I,且 A∩B=?。
2009-8-20 高级人工智能 史忠植 16
关联规则的相关概念 (2)
支持度物品集 A的支持度：称物品集 A具有大小为 s的支持度,
如果 D中有 s%的事务支持物品集 X P(A)
1000个顾客购物,其中 200个顾客购买了面包,
支持度就是 20％ （ 200/1000） 。
关联规则 A→B 的支持度：关联规则 A→B 在事务数据库 W中具有大小为 s的支持度,如果物品集 A∪B 的支持度为 s
100个顾客购买了面包和黄油,则面包 → 黄油 10％
2009-8-20 高级人工智能 史忠植 17
关联规则的相关概念 (3)
可信度设 W中支持物品集 A的事务中,有 c％ 的事务同时也支持物品集 B,c％ 称为关联规则 A→B 的可信度 。
P(B|A)
1000个顾客购物,200个顾客购买了面包,其中 140个买了黄油,则可信度是 70％ （ 140/200） 。
2009-8-20 高级人工智能 史忠植 18
关联规则的相关概念 (4)
最小支持度 minsup
用户规定的关联规则必须满足的最小支持度 。
最小可信度 minconf
用户规定的关联规则必须满足的最小可信度 。
大项集 (大项集,大物品集 largeitemset)
支持度不小于最小支持度 minsup的物品集
2009-8-20 高级人工智能 史忠植 19
关联规则发现任务给定一个事务数据库 D,求出所有满足最小支持度和最小可信度的关联规则。该问题可以分解为两个子问题：
1) 求出 D中满足最小支持度的所有大项集；
2) 利用大项集生成满足最小可信度的所有关联规则。对于每个大项集 A,若 B?A,B≠ φ,且
Confidence（ B? (A?B)）?minconf,则构成关联规则 B? (A?B)
2009-8-20 高级人工智能 史忠植 20
关联规则发现的基本思路第 2个子问题比较容易。目前大多数研究集中在第一个子问题上，即如何高效地求出大项集。
首先生成长度为 1的大项集（即单个物品），记为 L[1]；
在 L[k]的基础上生成候选物品集 C[k+1],候选物品集必须保证包括所有的大项集。
用事务数据库 D中的事务对 C[k+1]进行支持度测试以生成长度为 k+1的大项集 L[k+1],计算每个候选物品集的支持度，如果大于 minsup,则加入到 L[k+1]中。
如果 L[k+1]为空集，则结束,L[1]∪L[2]∪ … 即为结果；
否则转 (2)，继续。
2009-8-20 高级人工智能 史忠植 21
思路的正确性
利用了大物品集向下封闭性，即大物品集 X
的任意子集一定是大物品集，反过来说，
如果 X有一子集不是大项集，则 X肯定不是。
是宽度优先算法
2009-8-20 高级人工智能 史忠植 22
经典的 Apriori算法
(1) L[1]={large 1-itemsets};
(2) for (k=2; L[k-1]不为空 ; k++) do begin
(3) C[k]=apriori-gen(L[k-1]); // 新候选物品集
(4) For all transactions t∈ D do begin
(5) C=subset(C[k],t); // t中的候选物品集
(6) For all candidates c∈ C do
(7) c.count++;
(8) end;
(9) L[k]={c∈ C[k]|c.count>=minsup};
(10) end;
(11) Answer = L[1]∪ L[2]∪ …
2009-8-20 高级人工智能 史忠植 23
apriori-gen(L[k-1]) 分成两步：
join算法：从两个 L[k-1]物品集生成候选物品集 C[k]
insert into C[k]
select p.item1,p.item2,...,p.item(k-1),q.item(k-1)
from L[k-1] p,L[k-1] q
where p.item1=q.item1,...,p.item(k-2)=q.item(k-2),
p.item(k-1)<q.item(k-1)?
2009-8-20 高级人工智能 史忠植 24
Prune算法：从 C[k]中除去大小为 k-1且不在
L[k-1]中的子集
(1) For all itemsets c∈ C[k] do
(2) For all (k-1)-subsets s of c do
(3) if (s?L[k-1])
(4) then delete c from C[k]
2009-8-20 高级人工智能 史忠植 25
举例：
L[3]为 {{1,2,3},{1,2,4},{1,3,4},{1,3,5},{2,3,4}}
经过 join后,C[4]={{1,2,3,4},{1,3,4,5}}
由于 {1,3,4,5}有子集 {1,4,5}不在 L[3]中，
所以经过 prune后，得到 L[4]={{1,2,3,4}}
2009-8-20 高级人工智能 史忠植 26
2009-8-20 高级人工智能 史忠植 27
2009-8-20 高级人工智能 史忠植 28
2009-8-20 高级人工智能 史忠植 29
2009-8-20 高级人工智能 史忠植 30
关联规则发现注意的问题
充分理解数据
目标明确
数据准备工作要做好
选取适当的最小的支持度和可信度
很好地理解关联规则
2009-8-20 高级人工智能 史忠植 31
关联规则发现使用步骤
连接数据,做数据准备
给定最小支持度和最小可信度,利用知识发现工具提供的算法发现关联规则
可视化显示,理解,评估关联规则
2009-8-20 高级人工智能 史忠植 32
关联规则在保险业务中的应用
最小支持度 1%,最小可信度为 50%
2009-8-20 高级人工智能 史忠植 33
2009-8-20 高级人工智能 史忠植 34
2009-8-20 高级人工智能 史忠植 35
2009-8-20 高级人工智能 史忠植 36
数据仓库
在过去几十年，数据库技术，特别是 OLTP（ 联机事务处理），主要是为自动化生产、精简工作任务和高速采集数据服务。它是事务驱动的、面向应用的。
20世纪 80年代，人们要利用现有的数据，进行分析和推理，
从而为决策提供依据。这种需求既要求联机服务，又涉及大量用于决策的数据。而传统的数据库系统已无法满足这种需求：
所需历史数据量很大，而传统数据库一般只存储短期数据。
涉及许多部门的数据，而不同系统的数据难以集成。
对大量数据的访问性能明显下降
2009-8-20 高级人工智能 史忠植 37
数据仓库的定义信息处理技术的发展趋势是：从大量的事务型数据库中抽取数据,并将其清理,转换为新的存储格 。 随着此过程的发展和完善,这种九十年代初出现的支持决策的,特殊的数据存储即被称为数据仓库 （ Data Warehouse） 。
Inmon将数据仓库明确定义为：
数据仓库（ Data Warehouse） 是面向主题的，集成的，内容相对稳定的、不同时间的数据集合，用以支持经营管理中的决策制定过程。
2009-8-20 高级人工智能 史忠植 38
数据仓库的特征 (1)
数据仓库中的数据是面向主题的与传统数据库面向应用相对应的。主题是一个在较高层次将数据归类的标准，每一个主题基本对应一个宏观的分析领域
数据仓库中的数据是集成的在数据进入数据仓库之前，必然要经过加工与集成。要统一原始数据中的所有矛盾之处，还要进行数据综合和计算
2009-8-20 高级人工智能 史忠植 39
数据仓库的特征 (2)
数据仓库中的数据是稳定的数据仓库的数据主要供决策分析之用，所涉及的操作主要是数据查询，一般不进行修改操作
数据仓库中的数据又是随时间不断变化的数据仓库的数据不是实时更新的，但并不是永远不变的，也要随着时间的变化不断地更新、增删和重新综合。
更新周期
2009-8-20 高级人工智能 史忠植 40
元数据元数据（ Metadata） 是关于数据的数据，它描述了数据的结构、内容、编码、索引等内容。传统数据库中的数据字典是一种元数据，但在数据仓库中，元数据的内容比数据库中的数据字典更加丰富和复杂。设计一个描述能力强、内容完善的元数据，是有效管理数据仓库的具有决定意义的重要前提
2009-8-20 高级人工智能 史忠植 41
元数据的重要性
数据仓库使用者往往将使用元数据作为分析的第一步。元数据如同数据指示图，指出了数据仓库内各种信息的位置和含义
从操作型数据环境到数据仓库的数据转换是复杂的、
多方面的，是数据仓库建设的关键性步骤，元数据要包含对这种转换的清晰描述，保证这种转换是正确、
适当和合理的，并且是灵活可变的
元数据还管理粒度的划分、索引的建立以及抽取更新的周期等，以便管理好数据仓库中的大规模数据
2009-8-20 高级人工智能 史忠植 42
数据仓库的相关概念
事实表 （ Fact）,存储用户需要查询分析的数据,事实表中一般包含多个维 （ Dimension） 和度量 （ Measurement） 。
维,代表了用户观察数据的特定视角,如：时间维,地区维,
产品维等 。 每一个维可划分为不同的层次来取值,如时间维的值可按年份,季度,月份来划分,描述了不同的查询层次 。
度量：是数据的实际意义,描述数据,是什么,,即一个数值的测量指标,如：人数,单价,销售量等 。
2009-8-20 高级人工智能 史忠植 43
数据仓库的建模模型度量的实际数据存放在事实表中。维的详细信息，
如不同的层次划分和相应数据等在维表中存储，事实表中存放各个维的标识码键。事实表和维表将通过这些键关联起来，构成一种 星型模型对于层次复杂的维,为避免冗余数据占用过大的存储空间,可以使用多个表来描述,这种星型模式的扩展称为 雪花模型
2009-8-20 高级人工智能 史忠植 44
OLAP
数据仓库技术中，多维数据分析（ Multidimensional
Data Analysis） 方法是一种重要的技术，也称作联机分析处理（ On-Line Analytical Processing,简称 OLAP）
或数据立方体（ Data Cube） 方法,主要是指通过各种即席复杂查询，对数据仓库中存储的数据进行各种统计分析的应用数据仓库是面向决策支持的，决策的前提是数据分析。
在数据分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作，这类操作的计算量特别大 。
2009-8-20 高级人工智能 史忠植 45
OLAP的类型
ROLAP,数据保留在原有的关系型结构中，并且将聚合表也存储在关系数据库,在技术成熟及各方面的适应性上较之 MOLAP占有一定的优势，性能较差
MOLAP,数据和聚合都存储在多维结构中,效率较高,便于进行优化操作。维数多数据量大时，存储是难点。
HOALP,数据保留在原有的关系型结构中，聚合存储在多维结构。结合 ROLAP和 MOLAP两者的优点
2009-8-20 高级人工智能 史忠植 46
OLAP的分析操作
OLAP的基本多维分析操作有钻取（ roll up和 drill down）、
切片（ slice） 和切块（ dice）,以及旋转（ pivot)等。
钻取是改变维的层次,变换分析的粒度 。 它包括向上钻取和向下钻取 。 roll up是在某一维上将低层次的细节数据概括到高层次的汇总数据；而 drill down则相反,它从汇总数据深入到细节数据进行观察
切片和切块是在一部分维上选定值后,关心度量数据在剩余维上的分布 。 如果剩余的维只有两个,则是切片,否则是切块
旋转是变换维的方向,即在表格中重新安排维的放置 （ 例如行列互换
2009-8-20 高级人工智能 史忠植 47
数据仓库和知识发现技术的结合 (1)
知识发现成为数据仓库中进行数据深层分析的一种必不可少的手段数据仓库是面向决策分析的，数据仓库从事务型数据抽取并集成得到的分析型数据后，需要各种决策分析工具对这些数据进行分析和挖掘，得到有用的决策信息。而知识发现技术具备从大量数据中发现有用信息的能力。
2009-8-20 高级人工智能 史忠植 48
数据仓库和知识发现技术的结合 (2)
数据仓库为知识发现提供经过良好预处理的数据源知识发现往往依赖于经过良好组织和预处理的数据源，数据的好坏直接影响知识发现的效果。
数据仓库具有从各种数据源中抽取数据，并对数据进行清洗、聚集和转换等各种处理的能力
2009-8-20 高级人工智能 史忠植 49
一、数据挖掘概念 ----发展
1989 IJCAI会议,数据库中的知识发现讨论专题
Knowledge Discovery in Databases (G,Piatetsky-
Shapiro and W,Frawley,1991)
1991-1994 KDD讨论专题
Advances in Knowledge Discovery and Data Mining (U,
Fayyad,G,Piatetsky-Shapiro,P,Smyth,and R,
Uthurusamy,1996)
1995-1998 KDD国际会议 (KDD’95-98)
Journal of Data Mining and Knowledge Discovery
(1997)
1998 ACM SIGKDD,SIGKDD’1999-2002 会议,以及 SIGKDD
Explorations
数据挖掘方面更多的国际会议
PAKDD,PKDD,SIAM-Data Mining,(IEEE) ICDM,
DaWaK,SPIE-DM,etc.
2009-8-20 高级人工智能 史忠植 50
二、数据挖掘软件的发展代 特征 数据挖掘算法 集成 分布计算 模型 数据模型第一代作为一个独立的应用支持一个或者多个算法独立的系统 单个机器 向量数据第二代和数据库以及数据仓库集成多个算法：能够挖掘一次不能放进内存的数据数据管理系统，包括数据库和数据仓库同质、局部区域的计算机群集有些系统支持对象,文本和连续的媒体数据第三代和预言模型系统集成多个算法 数据管理和预言模型系统
intranet/e
xtranet网络计算支持半结构化数据和 web数据第四代和移动数据 /
各种计算设备的数据联合多个算法 数据管理、
预言模型、
移动系统移动和各种计算设备普遍存在的计算模型
Robert Grossman,National Center for Data Mining
University of Illinois at Chicago 的观点
2009-8-20 高级人工智能 史忠植 51
二、数据挖掘软件的发展第一代数据挖掘软件特点
支持一个或少数几个数据挖掘算法
挖掘向量数据（ vector-valued data）
数据一般一次性调进内存进行处理
典型的系统如 Salford Systems公司早期的 CART系统 (www.salford-systems.com)
缺陷
如果数据足够大，并且频繁的变化，这就需要利用数据库或者数据仓库技术进行管理，第一代系统显然不能满足需求。
2009-8-20 高级人工智能 史忠植 52
二、数据挖掘软件的发展第一代数据挖掘软件 CBA
新加坡国立大学。 基于关联规则的分类算法，能从关系数据或者交易数据中挖掘关联规则，使用关联规则进行分类和预测
2009-8-20 高级人工智能 史忠植 53
二、数据挖掘软件的发展第二代数据挖掘软件特点
与数据库管理系统（ DBMS） 集成
支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性
能够挖掘大数据集、以及更复杂的数据集
通过支持数据挖掘模式（ data mining schema） 和数据挖掘查询语言增加系统的灵活性
典型的系统如 DBMiner,能通过 DMQL挖掘语言进行挖掘操作缺陷
只注重模型的生成，如何和预言模型系统集成导致了第三代数据挖掘系统的开发
2009-8-20 高级人工智能 史忠植 54
二、数据挖掘软件的发展第二代数据挖掘软件 DBMiner
2009-8-20 高级人工智能 史忠植 55
二、数据挖掘软件的发展第二代软件 SAS Enterprise
Miner
2009-8-20 高级人工智能 史忠植 56
二、数据挖掘软件的发展第三代数据挖掘软件特点
和预言模型系统之间能够无缝的集成，使得由数据挖掘软件产生的模型的变化能够及时反映到预言模型系统中
由数据挖掘软件产生的预言模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模型相联合提供决策支持的功能
能够挖掘网络环境下（ Internet/Extranet） 的分布式和高度异质的数据，并且能够有效地和操作型系统集成缺陷
不能支持移动环境
2009-8-20 高级人工智能 史忠植 57
二、数据挖掘软件的发展第三代软件 SPSS lementine
以 PMML的格式提供与预言模型系统的接口
2009-8-20 高级人工智能 史忠植 58
二、数据挖掘软件的发展第四代数据挖掘软件特点
目前移动计算越发显得重要，将数据挖掘和移动计算相结合是当前的一个研究领域。
第四代软件能够挖掘嵌入式系统、移动系统、和普遍存在（ ubiquitous） 计算设备产生的各种类型的数据第四代数据挖掘原型或商业系统尚未见报导,PKDD2001
上 Kargupta发表了一篇在移动环境下挖掘决策树的论文，
Kargupta是马里兰巴尔的摩州立大学（ University of
Maryland Baltimore County） 正在研制的 CAREER数据挖掘项目的负责人，该项目研究期限是 2001年 4月到
2006年 4月，目的是开发挖掘分布式和异质数据
（ Ubiquitous设备）的第四代数据挖掘系统。
第九章 知识发现和数据挖掘数据库中知识发现史忠植中科院计算所
2009-8-20 高级人工智能 史忠植 2
知识发现
关联规则
数据仓库
知识发现工具
2009-8-20 高级人工智能 史忠植 3
知识发现知识发现是指从数据集中抽取和精炼新的模式。
范围非常广泛,经济、工业、农业、军事、社会
数据的形态多样化,数字、符号、图形、图像、声音
数据组织各不相同,结构化、半结构化和非结构
发现的知识可以表示成各种形式规则、科学规律、方程或概念网。
2009-8-20 高级人工智能 史忠植 4
数据库知识发现目前,关系型数据库技术成熟、应用广泛。
因此,数据库知识发现 (Knowledge Discovery
in Databases KDD)的研究非常活跃。
该术语于 1989年出现,Fayyad定义为
,KDD是从数据集中识别出有效的、新颖的、
潜在有用的，以及最终可理解的模式的非平凡过程,
2009-8-20 高级人工智能 史忠植 5
不同的术语名称知识发现是一门来自不同领域的研究者关注的交叉性学科，因此导致了很多不同的术语名称。
知识发现,人工智能和机器学习界。
数据挖掘 (data mining):
统计界、数据分析、数据库和管理信息系统界
知识抽取 (information extraction)、
信息发现 (information discovery)、
智能数据分析 (intelligent data analysis)、
探索式数据分析 (exploratory data analysis)
信息收获 (information harvesting)
数据考古 (data archeology)
2009-8-20 高级人工智能 史忠植 6
2009-8-20 高级人工智能 史忠植 7
知识发现的任务 (1)
数据总结：
对数据进行总结与概括。传统的最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值,或者用直方图、饼状图等图形方式表示。
分类：
根据分类模型对数据集合分类。分类属于有导师学习,一般需要有一个训练样本数据集作为输入。
聚类：
根据数据的不同特征，将其划分为不同的类。无导师学习
2009-8-20 高级人工智能 史忠植 8
知识发现的任务 (2)
相关性分析：
发现特征之间或数据之间的相互依赖关系关联规则
偏差分析：
基本思想是寻找观察结果与参照量之间的有意义的差别。通过发现异常,可以引起人们对特殊情况的加倍注意。
建模：
构造描述一种活动或状态的数学模型
2009-8-20 高级人工智能 史忠植 9
知识发现的方法 (1)
统计方法：
传统方法：
回归分析、判别分析、聚类分析、探索性分析
模糊集 (fuzzy set) Zadeh 1965
支持向量机 (Support Vector Machine) Vapnik 90
年代初
粗糙集 (Rough Set) Pawlak 80年代初
2009-8-20 高级人工智能 史忠植 10
知识发现的方法 (2)
机器学习：
规则归纳,AQ算法
决策树,ID3,C4.5
范例推理,CBR
遗传算法,GA
贝叶斯信念网络
2009-8-20 高级人工智能 史忠植 11
知识发现的方法 (3)
神经计算：
神经网络是指一类新的计算模型，它是模仿人脑神经网络的结构和某些工作机制而建立的一种计算模型。常用的模型：
Hopfield网
多层感知机
自组织特征映射
反传网络
可视化：
2009-8-20 高级人工智能 史忠植 12
KDD的技术难点
动态变化的数据
噪声
数据不完整
冗余信息
数据稀疏
超大数据量
2009-8-20 高级人工智能 史忠植 13
关联规则属于知识发现任务中的相关性分析由于条形码技术的发展,零售部门可以利用前端收款机收集存储大量的售货数据 。 因此,如果对这些历史事务数据进行分析,则可对顾客的购买行为提供极有价值的信息 。 例如,可以帮助如何摆放货架上的商品
(如把顾客经常同时买的商品放在一起 ),帮助如何规划市场 (怎样相互搭配进货 )。
2009-8-20 高级人工智能 史忠植 14
关联规则的表示关联规则的形式如,在购买面包顾客中,有 70%的人同时也买了黄油,,可以表示成,面包 → 黄油 。
用于关联规则发现的主要对象是事务型数据库,其中针对的应用则是售货数据,也称货篮数据 。 一个事务一般由如下几个部分组成,事务处理时间,一组顾客购买的物品,有时也有顾客标识号 (如信用卡号 )。
2009-8-20 高级人工智能 史忠植 15
关联规则的相关概念 (1)
设 R={I1,I2…… Im}是一组物品集,W是一组事务集 。 W
中的每个事务 T是一组物品,T?R。
假设有一个物品集 A,一个事务 T,如果 A?T,则称事务 T支持物品集 A。
关联规则是如下形式的一种蕴含,A→B,其中 A,B是两组物品,A?I,B?I,且 A∩B=?。
2009-8-20 高级人工智能 史忠植 16
关联规则的相关概念 (2)
支持度物品集 A的支持度：称物品集 A具有大小为 s的支持度,
如果 D中有 s%的事务支持物品集 X P(A)
1000个顾客购物,其中 200个顾客购买了面包,
支持度就是 20％ （ 200/1000） 。
关联规则 A→B 的支持度：关联规则 A→B 在事务数据库 W中具有大小为 s的支持度,如果物品集 A∪B 的支持度为 s
100个顾客购买了面包和黄油,则面包 → 黄油 10％
2009-8-20 高级人工智能 史忠植 17
关联规则的相关概念 (3)
可信度设 W中支持物品集 A的事务中,有 c％ 的事务同时也支持物品集 B,c％ 称为关联规则 A→B 的可信度 。
P(B|A)
1000个顾客购物,200个顾客购买了面包,其中 140个买了黄油,则可信度是 70％ （ 140/200） 。
2009-8-20 高级人工智能 史忠植 18
关联规则的相关概念 (4)
最小支持度 minsup
用户规定的关联规则必须满足的最小支持度 。
最小可信度 minconf
用户规定的关联规则必须满足的最小可信度 。
大项集 (大项集,大物品集 largeitemset)
支持度不小于最小支持度 minsup的物品集
2009-8-20 高级人工智能 史忠植 19
关联规则发现任务给定一个事务数据库 D,求出所有满足最小支持度和最小可信度的关联规则。该问题可以分解为两个子问题：
1) 求出 D中满足最小支持度的所有大项集；
2) 利用大项集生成满足最小可信度的所有关联规则。对于每个大项集 A,若 B?A,B≠ φ,且
Confidence（ B? (A?B)）?minconf,则构成关联规则 B? (A?B)
2009-8-20 高级人工智能 史忠植 20
关联规则发现的基本思路第 2个子问题比较容易。目前大多数研究集中在第一个子问题上，即如何高效地求出大项集。
首先生成长度为 1的大项集（即单个物品），记为 L[1]；
在 L[k]的基础上生成候选物品集 C[k+1],候选物品集必须保证包括所有的大项集。
用事务数据库 D中的事务对 C[k+1]进行支持度测试以生成长度为 k+1的大项集 L[k+1],计算每个候选物品集的支持度，如果大于 minsup,则加入到 L[k+1]中。
如果 L[k+1]为空集，则结束,L[1]∪L[2]∪ … 即为结果；
否则转 (2)，继续。
2009-8-20 高级人工智能 史忠植 21
思路的正确性
利用了大物品集向下封闭性，即大物品集 X
的任意子集一定是大物品集，反过来说，
如果 X有一子集不是大项集，则 X肯定不是。
是宽度优先算法
2009-8-20 高级人工智能 史忠植 22
经典的 Apriori算法
(1) L[1]={large 1-itemsets};
(2) for (k=2; L[k-1]不为空 ; k++) do begin
(3) C[k]=apriori-gen(L[k-1]); // 新候选物品集
(4) For all transactions t∈ D do begin
(5) C=subset(C[k],t); // t中的候选物品集
(6) For all candidates c∈ C do
(7) c.count++;
(8) end;
(9) L[k]={c∈ C[k]|c.count>=minsup};
(10) end;
(11) Answer = L[1]∪ L[2]∪ …
2009-8-20 高级人工智能 史忠植 23
apriori-gen(L[k-1]) 分成两步：
join算法：从两个 L[k-1]物品集生成候选物品集 C[k]
insert into C[k]
select p.item1,p.item2,...,p.item(k-1),q.item(k-1)
from L[k-1] p,L[k-1] q
where p.item1=q.item1,...,p.item(k-2)=q.item(k-2),
p.item(k-1)<q.item(k-1)?
2009-8-20 高级人工智能 史忠植 24
Prune算法：从 C[k]中除去大小为 k-1且不在
L[k-1]中的子集
(1) For all itemsets c∈ C[k] do
(2) For all (k-1)-subsets s of c do
(3) if (s?L[k-1])
(4) then delete c from C[k]
2009-8-20 高级人工智能 史忠植 25
举例：
L[3]为 {{1,2,3},{1,2,4},{1,3,4},{1,3,5},{2,3,4}}
经过 join后,C[4]={{1,2,3,4},{1,3,4,5}}
由于 {1,3,4,5}有子集 {1,4,5}不在 L[3]中，
所以经过 prune后，得到 L[4]={{1,2,3,4}}
2009-8-20 高级人工智能 史忠植 26
2009-8-20 高级人工智能 史忠植 27
2009-8-20 高级人工智能 史忠植 28
2009-8-20 高级人工智能 史忠植 29
2009-8-20 高级人工智能 史忠植 30
关联规则发现注意的问题
充分理解数据
目标明确
数据准备工作要做好
选取适当的最小的支持度和可信度
很好地理解关联规则
2009-8-20 高级人工智能 史忠植 31
关联规则发现使用步骤
连接数据,做数据准备
给定最小支持度和最小可信度,利用知识发现工具提供的算法发现关联规则
可视化显示,理解,评估关联规则
2009-8-20 高级人工智能 史忠植 32
关联规则在保险业务中的应用
最小支持度 1%,最小可信度为 50%
2009-8-20 高级人工智能 史忠植 33
2009-8-20 高级人工智能 史忠植 34
2009-8-20 高级人工智能 史忠植 35
2009-8-20 高级人工智能 史忠植 36
数据仓库
在过去几十年，数据库技术，特别是 OLTP（ 联机事务处理），主要是为自动化生产、精简工作任务和高速采集数据服务。它是事务驱动的、面向应用的。
20世纪 80年代，人们要利用现有的数据，进行分析和推理，
从而为决策提供依据。这种需求既要求联机服务，又涉及大量用于决策的数据。而传统的数据库系统已无法满足这种需求：
所需历史数据量很大，而传统数据库一般只存储短期数据。
涉及许多部门的数据，而不同系统的数据难以集成。
对大量数据的访问性能明显下降
2009-8-20 高级人工智能 史忠植 37
数据仓库的定义信息处理技术的发展趋势是：从大量的事务型数据库中抽取数据,并将其清理,转换为新的存储格 。 随着此过程的发展和完善,这种九十年代初出现的支持决策的,特殊的数据存储即被称为数据仓库 （ Data Warehouse） 。
Inmon将数据仓库明确定义为：
数据仓库（ Data Warehouse） 是面向主题的，集成的，内容相对稳定的、不同时间的数据集合，用以支持经营管理中的决策制定过程。
2009-8-20 高级人工智能 史忠植 38
数据仓库的特征 (1)
数据仓库中的数据是面向主题的与传统数据库面向应用相对应的。主题是一个在较高层次将数据归类的标准，每一个主题基本对应一个宏观的分析领域
数据仓库中的数据是集成的在数据进入数据仓库之前，必然要经过加工与集成。要统一原始数据中的所有矛盾之处，还要进行数据综合和计算
2009-8-20 高级人工智能 史忠植 39
数据仓库的特征 (2)
数据仓库中的数据是稳定的数据仓库的数据主要供决策分析之用，所涉及的操作主要是数据查询，一般不进行修改操作
数据仓库中的数据又是随时间不断变化的数据仓库的数据不是实时更新的，但并不是永远不变的，也要随着时间的变化不断地更新、增删和重新综合。
更新周期
2009-8-20 高级人工智能 史忠植 40
元数据元数据（ Metadata） 是关于数据的数据，它描述了数据的结构、内容、编码、索引等内容。传统数据库中的数据字典是一种元数据，但在数据仓库中，元数据的内容比数据库中的数据字典更加丰富和复杂。设计一个描述能力强、内容完善的元数据，是有效管理数据仓库的具有决定意义的重要前提
2009-8-20 高级人工智能 史忠植 41
元数据的重要性
数据仓库使用者往往将使用元数据作为分析的第一步。元数据如同数据指示图，指出了数据仓库内各种信息的位置和含义
从操作型数据环境到数据仓库的数据转换是复杂的、
多方面的，是数据仓库建设的关键性步骤，元数据要包含对这种转换的清晰描述，保证这种转换是正确、
适当和合理的，并且是灵活可变的
元数据还管理粒度的划分、索引的建立以及抽取更新的周期等，以便管理好数据仓库中的大规模数据
2009-8-20 高级人工智能 史忠植 42
数据仓库的相关概念
事实表 （ Fact）,存储用户需要查询分析的数据,事实表中一般包含多个维 （ Dimension） 和度量 （ Measurement） 。
维,代表了用户观察数据的特定视角,如：时间维,地区维,
产品维等 。 每一个维可划分为不同的层次来取值,如时间维的值可按年份,季度,月份来划分,描述了不同的查询层次 。
度量：是数据的实际意义,描述数据,是什么,,即一个数值的测量指标,如：人数,单价,销售量等 。
2009-8-20 高级人工智能 史忠植 43
数据仓库的建模模型度量的实际数据存放在事实表中。维的详细信息，
如不同的层次划分和相应数据等在维表中存储，事实表中存放各个维的标识码键。事实表和维表将通过这些键关联起来，构成一种 星型模型对于层次复杂的维,为避免冗余数据占用过大的存储空间,可以使用多个表来描述,这种星型模式的扩展称为 雪花模型
2009-8-20 高级人工智能 史忠植 44
OLAP
数据仓库技术中，多维数据分析（ Multidimensional
Data Analysis） 方法是一种重要的技术，也称作联机分析处理（ On-Line Analytical Processing,简称 OLAP）
或数据立方体（ Data Cube） 方法,主要是指通过各种即席复杂查询，对数据仓库中存储的数据进行各种统计分析的应用数据仓库是面向决策支持的，决策的前提是数据分析。
在数据分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作，这类操作的计算量特别大 。
2009-8-20 高级人工智能 史忠植 45
OLAP的类型
ROLAP,数据保留在原有的关系型结构中，并且将聚合表也存储在关系数据库,在技术成熟及各方面的适应性上较之 MOLAP占有一定的优势，性能较差
MOLAP,数据和聚合都存储在多维结构中,效率较高,便于进行优化操作。维数多数据量大时，存储是难点。
HOALP,数据保留在原有的关系型结构中，聚合存储在多维结构。结合 ROLAP和 MOLAP两者的优点
2009-8-20 高级人工智能 史忠植 46
OLAP的分析操作
OLAP的基本多维分析操作有钻取（ roll up和 drill down）、
切片（ slice） 和切块（ dice）,以及旋转（ pivot)等。
钻取是改变维的层次,变换分析的粒度 。 它包括向上钻取和向下钻取 。 roll up是在某一维上将低层次的细节数据概括到高层次的汇总数据；而 drill down则相反,它从汇总数据深入到细节数据进行观察
切片和切块是在一部分维上选定值后,关心度量数据在剩余维上的分布 。 如果剩余的维只有两个,则是切片,否则是切块
旋转是变换维的方向,即在表格中重新安排维的放置 （ 例如行列互换
2009-8-20 高级人工智能 史忠植 47
数据仓库和知识发现技术的结合 (1)
知识发现成为数据仓库中进行数据深层分析的一种必不可少的手段数据仓库是面向决策分析的，数据仓库从事务型数据抽取并集成得到的分析型数据后，需要各种决策分析工具对这些数据进行分析和挖掘，得到有用的决策信息。而知识发现技术具备从大量数据中发现有用信息的能力。
2009-8-20 高级人工智能 史忠植 48
数据仓库和知识发现技术的结合 (2)
数据仓库为知识发现提供经过良好预处理的数据源知识发现往往依赖于经过良好组织和预处理的数据源，数据的好坏直接影响知识发现的效果。
数据仓库具有从各种数据源中抽取数据，并对数据进行清洗、聚集和转换等各种处理的能力
2009-8-20 高级人工智能 史忠植 49
一、数据挖掘概念 ----发展
1989 IJCAI会议,数据库中的知识发现讨论专题
Knowledge Discovery in Databases (G,Piatetsky-
Shapiro and W,Frawley,1991)
1991-1994 KDD讨论专题
Advances in Knowledge Discovery and Data Mining (U,
Fayyad,G,Piatetsky-Shapiro,P,Smyth,and R,
Uthurusamy,1996)
1995-1998 KDD国际会议 (KDD’95-98)
Journal of Data Mining and Knowledge Discovery
(1997)
1998 ACM SIGKDD,SIGKDD’1999-2002 会议,以及 SIGKDD
Explorations
数据挖掘方面更多的国际会议
PAKDD,PKDD,SIAM-Data Mining,(IEEE) ICDM,
DaWaK,SPIE-DM,etc.
2009-8-20 高级人工智能 史忠植 50
二、数据挖掘软件的发展代 特征 数据挖掘算法 集成 分布计算 模型 数据模型第一代作为一个独立的应用支持一个或者多个算法独立的系统 单个机器 向量数据第二代和数据库以及数据仓库集成多个算法：能够挖掘一次不能放进内存的数据数据管理系统，包括数据库和数据仓库同质、局部区域的计算机群集有些系统支持对象,文本和连续的媒体数据第三代和预言模型系统集成多个算法 数据管理和预言模型系统
intranet/e
xtranet网络计算支持半结构化数据和 web数据第四代和移动数据 /
各种计算设备的数据联合多个算法 数据管理、
预言模型、
移动系统移动和各种计算设备普遍存在的计算模型
Robert Grossman,National Center for Data Mining
University of Illinois at Chicago 的观点
2009-8-20 高级人工智能 史忠植 51
二、数据挖掘软件的发展第一代数据挖掘软件特点
支持一个或少数几个数据挖掘算法
挖掘向量数据（ vector-valued data）
数据一般一次性调进内存进行处理
典型的系统如 Salford Systems公司早期的 CART系统 (www.salford-systems.com)
缺陷
如果数据足够大，并且频繁的变化，这就需要利用数据库或者数据仓库技术进行管理，第一代系统显然不能满足需求。
2009-8-20 高级人工智能 史忠植 52
二、数据挖掘软件的发展第一代数据挖掘软件 CBA
新加坡国立大学。 基于关联规则的分类算法，能从关系数据或者交易数据中挖掘关联规则，使用关联规则进行分类和预测
2009-8-20 高级人工智能 史忠植 53
二、数据挖掘软件的发展第二代数据挖掘软件特点
与数据库管理系统（ DBMS） 集成
支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性
能够挖掘大数据集、以及更复杂的数据集
通过支持数据挖掘模式（ data mining schema） 和数据挖掘查询语言增加系统的灵活性
典型的系统如 DBMiner,能通过 DMQL挖掘语言进行挖掘操作缺陷
只注重模型的生成，如何和预言模型系统集成导致了第三代数据挖掘系统的开发
2009-8-20 高级人工智能 史忠植 54
二、数据挖掘软件的发展第二代数据挖掘软件 DBMiner
2009-8-20 高级人工智能 史忠植 55
二、数据挖掘软件的发展第二代软件 SAS Enterprise
Miner
2009-8-20 高级人工智能 史忠植 56
二、数据挖掘软件的发展第三代数据挖掘软件特点
和预言模型系统之间能够无缝的集成，使得由数据挖掘软件产生的模型的变化能够及时反映到预言模型系统中
由数据挖掘软件产生的预言模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模型相联合提供决策支持的功能
能够挖掘网络环境下（ Internet/Extranet） 的分布式和高度异质的数据，并且能够有效地和操作型系统集成缺陷
不能支持移动环境
2009-8-20 高级人工智能 史忠植 57
二、数据挖掘软件的发展第三代软件 SPSS lementine
以 PMML的格式提供与预言模型系统的接口
2009-8-20 高级人工智能 史忠植 58
二、数据挖掘软件的发展第四代数据挖掘软件特点
目前移动计算越发显得重要，将数据挖掘和移动计算相结合是当前的一个研究领域。
第四代软件能够挖掘嵌入式系统、移动系统、和普遍存在（ ubiquitous） 计算设备产生的各种类型的数据第四代数据挖掘原型或商业系统尚未见报导,PKDD2001
上 Kargupta发表了一篇在移动环境下挖掘决策树的论文，
Kargupta是马里兰巴尔的摩州立大学（ University of
Maryland Baltimore County） 正在研制的 CAREER数据挖掘项目的负责人，该项目研究期限是 2001年 4月到
2006年 4月，目的是开发挖掘分布式和异质数据
（ Ubiquitous设备）的第四代数据挖掘系统。
