第13章数据挖掘

第4部分其它高级主题第13章数据挖掘高级数据库系统及其应用2024/7/92第13章数据挖掘数据挖掘综述13.1数据关联模式13.2决策树13.3聚类13.4基于序列的相似搜索13.52024/7/9313.1数据挖掘（DataMining,DM）综述DM定义是一种需要很少用户定义参数、高度抽象复杂且无法用常规SQL表达的查询。主要目标从大数据集中发现有趣的趋势或模式，以指导未来的决策行为，或引导后续更细致的数据分析研究。应用特点必须面向非常大数据集处理，针对数据集大小是否具有线性可伸缩性(scalability)，是判断一个DM方法是否有效的重要标准。2024/7/94DM与知识发现过程(KDD)的关系在实际应用中，DM并不只是应用一两个算法的简单问题，而是通常比这复杂得多，且或多或少会涉及KDD的其它过程步。2024/7/95本章将介绍的DM知识体系及特点DM现已发展成为数据处理技术的一个重要分支学科，包含丰富的相关知识，有自己独立的体系。而在本章中只限于介绍一些重要的、已在主流RDBMS产品之数据分析扩展套件中实现的DM功能，并侧重考虑如何充分利用DB查询处理技术，来优化某些传统DM算法的性能和可伸缩性。这显然与其它数据挖掘专著所基于的视角有所不同。2024/7/9613.2数据关联模式13.2.1频繁项集13.2.2冰川查询13.2.3挖掘关联规则挖掘数据关联模式对给定的数据集，通过搜索不同数据项（items）之间的关联性，来寻找频繁且有趣的数据模式。典型应用市场购物篮分析通过分析顾客购买物品的交易数据记录集（每条记录描述一个顾客的一次购买交易物品项目集），来发现一些顾客经常同时购买的物品类。这个信息可用于改善商店中物品摆放布局，或改进商店的物品目录板。2024/7/9713.2.1频繁项集用于购物篮分析的一个购买实例,图13.1(Purchases)将记录按交易事务(由transid标识)排序分组，同组各元组合在一起，构成了一个购买交易。该表中有冗余。然而，这种有冗余的临时关系，更便于演示寻找频繁项集的算法思想。观察记录数据不难发现“75%的事务同时购买了pen和ink”

2024/7/98计算频繁项集的经典算法－Priori算法(1)算法涉及的几个重要概念项集(itemset)代表一组物品或一组项目项集支持度(support)包含该项集的事务占DB中所有事务的比例。在我们的例子中，项集{pen,ink}的支持度为75%频繁项集(frequentitemset)

指支持度超过用户指定阈值(minsup)的项集

Priori性质每个频繁项集的任何子集必须也是频繁项集

算法13.1寻找频繁项集的Priori算法2024/7/99计算频繁项集的经典算法－Priori算法(2)算法涉及的几个重要概念算法13.1寻找频繁项集的Priori算法该算法可以进一步应用Priori性质来求精以“频繁项集的所有子集也是频繁项集”为检查标准，可进一步减少候选集数目。从而有助于减少了扫描Purchases关系期间需执行的计算量。

2024/7/91013.2.2冰川查询(1)仍考虑图13.1的Purchases关系实例。假设我们要查找：满足“顾客购买item最少5次”条件的所有<customer,item>对，这个请求可用SQL语句表达如下：SELECTP.custid,P.item,SUM(P.qyt)FROMPurchasesPGROUPBYP.custid,P.itemHAVING

SUM(P.qty)>5概念赋值策略：对每个<customer,item>对，需要检查SUM(P.qyt)是否大于5。如果主存可容纳所有这样对的值，则扫描一次Purchases关系即可。否则，需使用额外的排序和散列，查询赋值计划的代价会很大。这个概念赋值策略没有充分利用查询的一个重要特性：HAVING条件限制。虽然分组数可能非常大，但满足HAVING条件的分组数缺往往不多――就象冰川的顶尖通常总是很小一样。2024/7/91113.2.2冰川查询(2)冰川查询的一般形式SELECT

R.A1,R.A2,…,R.Ak,aggr(R.B)FROMRelationRGROUPBY

R.A1,R.A2,…,R.AkHAVING

aggr(R.B)>constant比较冰川查询与找频繁项集问题，有一个惊人的相似性。要求<customer,item>组满足SUM(qty)>5，可很自然导出要求<item>分组或<customer>分组也满足SUM(qty)>5。这相当于一种priori性质变体的情况。对只考虑已经购买了至少5个的哪些item,及custid值，可通过下面两个查询来产生。反之，由这些满足限制的单项值，构成的组数目肯定会大大减少。SELECTP.custidFROMPurchasesPGROUPBYP.custidHAVINGSUM(P.qty)>5

SELECTP.itemFROMPurchasesPGROUPBYP.itemHAVINGSUM(P.qty)>5一个改进的赋值策略：首先为custid和item字段计算候选值，并只利用这些候选值组合到原冰川查询赋值中。这样，冰川查询就与频繁项集类似，都服从自底向上的赋值策略。

2024/7/91213.2.3挖掘关联规则(associationrule)

关联规则一般具有如下的形式：

LHS=>RHS，这里，LHS和RHS都是项集。当(LHS,RHS)是频繁项集时，可很自然导出该规则。度量关联规则强度的两个量：支持度：指的是包含项集中所有项的事务占所有相关事务的比例，即指频繁项集的支持度。规则LHS=>RHS的支持度，等于项集{LHS,RHS}的支持度。置信度：规则LHS=>RHS的置信度，指同时包含了项集{LHS}、{RHS}的事务占只包含{LHS}事务的比例。conf(LHS=>RHS)=sup(LHS⋃RHS)/sup(LHS)。规则置信度是规则强度的一个指示量。发现关联规则的两个基本算法1)利用用户指定的minsup，计算所有的频繁项集；2)利用频繁项集为输入，产生规则集。2024/7/91313.3决策树13.3.1决策树与分类规则13.3.2构造决策树算法“如果某人的年龄小于等于25，且驾驶小轿车，则他(她)可拥有低保险”。

2024/7/914决策树的相关概念一棵决策树是一组分类规则的图形化表示。树的节点（根节点和内节点）带一个特殊的属性标签。这个属性常被称为分裂属性，因为数据在关于该属性的条件上分类。树节点的出边每个内部节点的一个出边上标上包含节点分裂属性的谓词（条件），每个进入该节点的数据记录必须且只满足一条出边上标注的谓词条件。分裂属性和出边上的谓词，合称为节点的分类准则(splittingcriterion)。树的叶节点指没有出边的节点，其上常标记一个被预测属性值。2024/7/915构造决策树的两个基本阶段增长阶段剪枝阶段

先构造一棵相对较大的、完全树。该树以准确的方式表示输入DB中的记录比如，为输入DB的每条不同记录分别创建一个叶节点。树结构所表示的规则，通常会过于细化。

通过减小归纳树结构，产生一个规则数目相对较少的、更一般的规则树。剪枝后的规则树通常比大且细化的原规则树更有意义。2024/7/916建立分类树的基本算法2024/7/91713.4聚类13.4.1几种典型的聚类方法13.4.2BIRCH聚类算法图13.4

顾客年龄/薪水数据记录点分布图年轻低收入顾客群

年长高收入顾客群

年轻高收入顾客群

2024/7/918“聚类(clustering)”的几个基本概念聚类定义是将一个数据记录集划分为若干组/类（group/cluster）的过程。聚类分析的基本指导思想最大程度地实现同类中对象相似度大、不同类间对象相异度。在机器学习中，聚类分析属于一种无监督的学习方法。它不依赖于事先确定的数据类别，不需要标有数据类别的学习训练样本集。它是一种通过观察来学习的方法。2024/7/919聚类的算法输出及其描述方法一个聚类分析算法的输出，应包括对所获得每个聚类的描述。这种描述强烈依赖于聚类类型和形状。例如，对近似球状的聚类，可利用中心点和半径来描述。给定一个记录集合r1,r2,…,rn，它们的中心C和半径R可定义如下2024/7/92013.4.1几种典型的聚类方法1.划分方法划分数据集到k个组，每个组代表一个聚类，聚类数目k是用户指定的一个参数值。最常用的划分算法是k-means算法。该算法中各聚类中心，分别用相应类中数据对象的平均值来表示。2.层次方法最初将每个数据对象作为一个聚类。算法在每一步，合并两个距离最近的聚类，直到最终只剩下一个聚类。

层次聚类算法最终也将产生一个包含若干聚类的序列。3.密度方法2024/7/921基本k-means算法2024/7/92213.4.1几种典型的聚类方法1.划分方法2.层次方法3.密度方法基于数据对象间的距离进行的聚类算法，通常只能发现圆形或球形聚类，很难发现任意形状的聚类。而基于密度概念的聚类方法，则是不断增长所获得的每个聚类，直到出现“邻近“数据对象密度小于指定阈值为止。这种方法有利于消除数据中的噪声（异常数据），以及帮助发现任意形状的聚类。

2024/7/92313.4.2BIRCH聚类算法BIRCH算法，可以处理非常大的数据集且具有良好的可伸缩性。算法处理时不需要将整个输入DB装入主存。BIRCH设计采用了下面两个假定：数据集中潜在的记录数可能非常大，因此，希望只扫描一次数据集；只有有限的可用主存。BIRCH算法的两个基本控制参数可用主存量被对应到主存中可维护的最大分组数k值；聚类的上限半径阈值εBIRCH算法总是在主存中维持k个或更少的聚类描述(Ci,Ri)，且算法只设法维持紧凑聚类。2024/7/924BIRCH算法描述顺序从DB读出数据记录，并按如下步骤处理每个记录r：计算记录r与每个已有聚类中心的距离。令i是与r有最小距离那个Ci对应的索引。将r插入第i个聚类，然后计算第i个聚类的新Ri’。IFRi’<=εTHEN//第i个聚类仍能保持紧凑；将r真正插入第i个聚类中，并更新Ri为Ri’。ELSEIFRi’>εTHEN//插入r第i个聚类将不再紧凑添加一个只包含r的新聚类，这时，分组数k

k＋1;ENDIFIFk>=kmaxTHEN通过增加半径的域值ε来进行调整处理;/*用某种启发形方法确定ε增量值，以合并已有的聚类。增加ε有两个影响：1)聚类可容纳更多的记录；2）可能合并已有的聚类，使结果聚类仍是紧凑的。这样，增加ε通常减少了聚类的数目。*/ENDIF

2024/7/92513.5基于序列的相似搜索13.5.1数据序列及其相似度定义13.5.2一种发现相似序列的算法本部分简要讨论一类在序列型数据集上进行相似搜索问题。基本查询模型由用户指定了一个查询序列（数据的模板序列），在DB中检索与模板序列相似的所有