第13章 数据挖掘PPT课件

1、LOGO高级数据库系统及其应用高级数据库系统及其应用2022-5-112第第13章章 数据挖掘数据挖掘数据挖掘综述数据挖掘综述13.1数据关联模式数据关联模式13.2决策树决策树13.3聚类聚类13.4基于序列的相似搜索基于序列的相似搜索13.52022-5-11313.1 数据挖掘（数据挖掘（Data Mining, DM）综述）综述vDM定义定义 是一种需要很少用户定义参数、高度抽象复杂是一种需要很少用户定义参数、高度抽象复杂且无法用常规且无法用常规SQL表达的查询表达的查询。v主要目标主要目标 从大数据集中发现有趣的趋势或模式，以指导未来的决策行为，或引导后续更细致的数据分析研究。 v应

2、用特点应用特点 必须面向非常大数据集处理，针对数据集大小是否具有线性可伸缩性(scalability)，是判断一个DM方法是否有效的重要标准。 2022-5-114DM与知识发现过程与知识发现过程(KDD)的关系的关系 在实际应用中，在实际应用中，DM并不只是应用一两个算法的简单问并不只是应用一两个算法的简单问题，而是通常比这复杂得多，且或多或少会涉及题，而是通常比这复杂得多，且或多或少会涉及KDD的其的其它过程步。它过程步。2022-5-115本章将介绍的本章将介绍的DM知识体系及特点知识体系及特点vDM现已发展成为数据处理技术的一个重要分支现已发展成为数据处理技术的一个重要分支学科，包含丰

3、富的相关知识，有自己独立的体系。学科，包含丰富的相关知识，有自己独立的体系。v而在本章中而在本章中 只限于介绍一些重要的、已在主流RDBMS产品之数据分析扩展套件中实现的DM功能，并侧重考虑如何充分利用DB查询处理技术，来优化某些传统DM算法的性能和可伸缩性。 这显然与其它数据挖掘专著所基于的视角有所不同。 2022-5-11613.2 数据关联模式数据关联模式13.2.1 频繁项集 13.2.2 冰川查询 13.2.3 挖掘关联规则对给定的数据集，通过搜索不同数据项（items）之间的关联性，来寻找频繁且有趣的数据模式。 通过分析顾客购买物品的交易数据记录集（每条记录描述一个顾客的一次购买交

4、易物品项目集），来发现一些顾客经常同时购买的物品类。 这个信息可用于改善商店中物品摆放布局，或改进商店的物品目录板。2022-5-11713.2.1 频繁项集频繁项集v 用于购物篮分析的一用于购物篮分析的一个购买实例个购买实例,图图13.1 (Purchases) 将记录按交易事务(由transid标识)排序分组，同组各元组合在一起，构成了一个购买交易。 该表中有冗余。然而，这种有冗余的临时关系，更便于演示寻找频繁项集的算法思想。 观察记录数据不难发现 “75%的事务同时购买了pen和ink” 2022-5-118计算频繁项集的经典算法计算频繁项集的经典算法 Priori算法算法(1)v算法涉

5、及的几个重要概念算法涉及的几个重要概念 项集项集(itemset) 代表一组物品或一组项目 项集支持度项集支持度(support) 包含该项集的事务占DB中所有事务的比例。 在我们的例子中，项集pen,ink的支持度为75% 频繁项集频繁项集(frequent itemset) 指支持度超过用户指定阈值(minsup)的项集项集 Priori性质性质 每个频繁项集的任何子集必须也是频繁项集每个频繁项集的任何子集必须也是频繁项集 v算法算法13.1 寻找频繁项集的寻找频繁项集的Priori算法算法2022-5-119计算频繁项集的经典算法计算频繁项集的经典算法 Priori算法算法(2)v算法涉

6、及的几个重要概念算法涉及的几个重要概念v算法算法13.1 寻找频繁项集的寻找频繁项集的Priori算法算法该算法可以进一步应用该算法可以进一步应用Priori性质来求精性质来求精 以以 “频繁项集的所有子集也是频繁项集频繁项集的所有子集也是频繁项集”为检为检查标准，可进一步减少候选集数目。从而有助于减查标准，可进一步减少候选集数目。从而有助于减少了扫描少了扫描Purchases关系期间需执行的计算量。关系期间需执行的计算量。 2022-5-111013.2.2 冰川查询冰川查询(1)v 仍考虑图仍考虑图13.1的的Purchases关系实例。假设我们要查找：满足关系实例。假设我们要查找：满足“

7、顾客购买顾客购买item最少最少5次次”条件的所有条件的所有对，对，这个请求可用这个请求可用SQL语句表达如下：语句表达如下： SELECT P.custid, P.item, SUM(P.qyt) FROM Purchases P GROUP BY P.custid, P.item HAVING SUM(P.qty) 5 概念赋值策略：对每个概念赋值策略：对每个对，需要检对，需要检查查SUM(P.qyt)是否大于是否大于5。 如果主存可容纳所有这样对的值，则扫描一次Purchases关系即可。否则，需使用额外的排序和散列，查询赋值计划的代价会很大。 这个概念赋值策略没有充分利用查询的一个重要

8、特性：这个概念赋值策略没有充分利用查询的一个重要特性：HAVING条件限制。条件限制。 虽然分组数可能非常大，但满足HAVING条件的分组数缺往往不多就象冰川的顶尖通常总是很小一样。2022-5-111113.2.2 冰川查询冰川查询(2)v 冰川查询的一般形式冰川查询的一般形式 SELECT R.A1, R.A2, R.Ak, aggr(R.B) FROM Relation R GROUP BY R.A1, R.A2, R.Ak HAVING aggr(R.B) constantv 比较冰川查询与找频繁项集问题，有一个惊人的相似性。比较冰川查询与找频繁项集问题，有一个惊人的相似性。 要求组满

9、足SUM(qty)5，可很自然导出要求分组或分组也满足SUM(qty)5。 这相当于一种priori性质变体的情况。 对只考虑已经购买了至少5个的哪些item,及custid值，可通过下面两个查询来产生。反之，由这些满足限制的单项值，构成的组数目肯定会大大减少。SELECT P.custidFROM Purchases PGROUP BY P.custidHAVING SUM(P.qty) 5 SELECT P.itemFROM Purchases PGROUP BY P.itemHAVING SUM(P.qty) 5一个改进的赋值策略一个改进的赋值策略： 首先为custid和item字段计算

10、候选值，并只利用这些候选值组合到原冰川查询赋值中。 这样，冰川查询就与频繁项集类似，都服从自底向上的自底向上的赋值策略赋值策略。 2022-5-111213.2.3 挖掘关联规则挖掘关联规则(association rule) v 关联规则一般具有如下的形式：关联规则一般具有如下的形式： LHS=RHS，这里，LHS和RHS都是项集。 当(LHS,RHS)是频繁项集时，可很自然导出该规则。v 度量关联规则强度的两个量：度量关联规则强度的两个量： 支持度：指的是包含项集中所有项的事务占所有相关事务的比例，即指频繁项集的支持度。 规则LHS=RHS的支持度，等于项集LHS , RHS的支持度。 置

11、信度：规则LHS=RHS的置信度，指同时包含了项集LHS、RHS的事务占只包含LHS事务的比例。 conf(LHS=RHS) = sup(LHSRHS)/ sup(LHS)。 规则置信度是规则强度的一个指示量。v 发现关联规则的两个基本算法发现关联规则的两个基本算法 1) 利用用户指定的minsup，计算所有的频繁项集； 2)利用频繁项集为输入，产生规则集。 2022-5-111313.3 决策树决策树13.3.1 决策树与分类规则 13.3.2 构造决策树算法“如果某人的如果某人的年龄小于等于年龄小于等于25，且驾驶小，且驾驶小轿车，则他轿车，则他(她她)可拥有低保可拥有低保险险”。 202

12、2-5-1114决策树的相关概念决策树的相关概念 v一棵决策树是一组分类规则的图形化表示。一棵决策树是一组分类规则的图形化表示。 树的节点树的节点（根节点和内节点） 带一个特殊的属性标签。这个属性常被称为分裂属性，因为数据在关于该属性的条件上分类。 树节点的出边树节点的出边 每个内部节点的一个出边上标上包含节点分裂属性的谓词（条件），每个进入该节点的数据记录必须且只满足一条出边上标注的谓词条件。 分裂属性和出边上的谓词，合称为节点的分类准则(splitting criterion)。 树的叶节点树的叶节点 指没有出边的节点，其上常标记一个被预测属性值。 2022-5-1115构造决策树的两个基

13、本阶段构造决策树的两个基本阶段增长阶段增长阶段剪枝阶段剪枝阶段 v先构造一棵相对先构造一棵相对较大的、完全树。较大的、完全树。 该树以准确的方式该树以准确的方式表示输入表示输入DB中的中的记录记录 比如，为输入比如，为输入DB的每条不同记录分的每条不同记录分别创建一个叶节点。别创建一个叶节点。v 树结构所表示的规则，树结构所表示的规则，通常会过于细化。通常会过于细化。 v通过减小归纳树结通过减小归纳树结构，产生一个规则构，产生一个规则数目相对较少的、数目相对较少的、更一般的规则树。更一般的规则树。v剪枝后的规则树通剪枝后的规则树通常比大且细化的原常比大且细化的原规则树更有意义。规则树更有意义。

14、2022-5-1116建立分类树的基本算法建立分类树的基本算法 2022-5-111713.4 聚类聚类13.4.1 几种典型的聚类方法 13.4.2 BIRCH聚类算法图图13.4 顾客年龄/薪水数据记录点分布图年轻低收年轻低收入顾客群入顾客群 年长高收年长高收入顾客群入顾客群 年轻高收年轻高收入顾客群入顾客群 2022-5-1118“聚类聚类(clustering)”的几个基本概念的几个基本概念v聚类定义聚类定义 是将一个数据记录集划分为若干组/类（group / cluster）的过程。v聚类分析的基本指导思想聚类分析的基本指导思想 最大程度地实现同类中对象相似度大、不同类间对象相异度。

15、 v在机器学习中，聚类分析属于一种在机器学习中，聚类分析属于一种无监督的学习无监督的学习方法方法。 它不依赖于事先确定的数据类别，不需要标有数据类别的学习训练样本集。 它是一种通过观察来学习的方法。2022-5-1119聚类的算法输出及其描述方法聚类的算法输出及其描述方法v一个聚类分析算法的输出，应包括对所获得每个一个聚类分析算法的输出，应包括对所获得每个聚类的描述。聚类的描述。v这种描述强烈依赖于聚类类型和形状。这种描述强烈依赖于聚类类型和形状。 例如，对近似球状的聚类，可利用中心点和半径来描例如，对近似球状的聚类，可利用中心点和半径来描述。述。 给定一个记录集合给定一个记录集合r1,r2,

16、rn，它们的中心，它们的中心C和半径和半径R可定义如下可定义如下 nnCrRrCniinii11)/( 2022-5-112013.4.1 几种典型的聚类方法几种典型的聚类方法 1. 划分方法划分方法划分数据集到划分数据集到k个组，每个组代表一个聚类，聚类数个组，每个组代表一个聚类，聚类数目目k是用户指定的一个参数值。是用户指定的一个参数值。最常用的划分算法是最常用的划分算法是k-means算法。该算法中各聚算法。该算法中各聚类中心，分别用相应类中数据对象的平均值来表示。类中心，分别用相应类中数据对象的平均值来表示。2. 层次方法层次方法最初将每个数据对象作为一个聚类。最初将每个数据对象作为一

17、个聚类。算法在每一步，合并两个距离最近的聚类，直到最算法在每一步，合并两个距离最近的聚类，直到最终只剩下一个聚类。终只剩下一个聚类。 层次聚类算法最终也将产生一个包含若干聚类的序层次聚类算法最终也将产生一个包含若干聚类的序列。列。3. 密度方法密度方法 2022-5-1121基本基本k-means算法算法 2022-5-112213.4.1 几种典型的聚类方法几种典型的聚类方法 1. 划分方法划分方法2. 层次方法层次方法3. 密度方法密度方法基于数据对象间的距离进行的聚类算法，通常只能基于数据对象间的距离进行的聚类算法，通常只能发现圆形或球形聚类，很难发现任意形状的聚类。发现圆形或球形聚类，

18、很难发现任意形状的聚类。而基于密度概念的聚类方法，则是不断增长所获得而基于密度概念的聚类方法，则是不断增长所获得的每个聚类，直到出现的每个聚类，直到出现“邻近邻近“数据对象密度小于数据对象密度小于指定阈值为止。指定阈值为止。这种方法有利于消除数据中的噪声（异常数据），这种方法有利于消除数据中的噪声（异常数据），以及帮助发现任意形状的聚类。以及帮助发现任意形状的聚类。 2022-5-112313.4.2 BIRCH聚类算法聚类算法 v BIRCH算法，可以处理非常大的数据集且具有良好的可算法，可以处理非常大的数据集且具有良好的可伸缩性。算法处理时不需要将伸缩性。算法处理时不需要将整个输入整个输入

19、DB装入主存。装入主存。 v BIRCH设计采用了下面两个假定：设计采用了下面两个假定： 数据集中潜在的记录数可能非常大，因此，希望只扫数据集中潜在的记录数可能非常大，因此，希望只扫描一次数据集；描一次数据集； 只有有限的可用主存。只有有限的可用主存。v BIRCH算法的两个基本控制参数算法的两个基本控制参数 可用主存量可用主存量 被对应到主存中可维护的被对应到主存中可维护的最大分组数最大分组数k值；值； 聚类的聚类的上限半径阈值上限半径阈值 BIRCH算法总是在主存中维持算法总是在主存中维持k个或更少的聚类描述个或更少的聚类描述 (Ci, Ri)，且算法只设法维持紧凑聚类，且算法只设法维持紧凑聚类。 2022-5-1124BIRCH算法描述算法描述v 顺序从顺序从DB读出数