数据挖掘课件

1、第六章 挖掘频繁模式、关联和相关性：基本概念和方法,报告人：唐忠任,数据挖掘概念与技术,哪些模式是有趣的：模式评估方法,哪些模式是有趣的？,本节学习目标,本节首先考察为何关联规则也可能是无趣的并且可能是误导。 然后讨论如何用基于相关分析的附加度量加强支持度置信度框架。,强规则不一定是有趣的,规则是否有趣可以主观或客观地评估。最终，只有用户能够评判一个给定的规则是否是有趣的，并且这种判断是主观的，可能因用户而异。然而，根据数据“背后”的统计量，客观兴趣度度量可以用来清除无趣的规则，而不用用户提供。 “我们如何识别哪些强关联规则是真正有趣的？”让我们考查下面的例子。,一个误导的“强”关联规则,假设

2、我们对分析涉及购买计算机游戏和录像的事务感兴趣。设game表示包含计算机游戏的事务，而video表示包含录像的事务。,在所分析的10000个事务中，数据显示6000个顾客事务包含计算机游戏，7500个事务包含录像，而4000个事务同时包含计算机游戏和录像。假设发现关联规则的数据挖掘程序在该数据上运行，使用最小支持度30%，最小置信度60%。将发现下面的关联规则：,从关联分析到相关分析,正如我们在上面已经看到的，支持度和置信度不足以过滤掉无趣的关联规则。为了处理这个问题，可以使用相关性度量来扩充关联规则的支持度置信度框架。这导致如下形式的相关规则（correlation rule） A=Bsup

3、port, confidence, correlation 也就是说，相关规则不仅用支持度和置信度度量，而且还用项集A和B之间的相关性度量有许多不同的相关性度量可供选择。本节研究各种相关性度量，确定哪些度量适合挖掘大型数据集。,提升度,提升度（lift）是一种简单的相关性度量，定义如下。项集A的出现独立于项集B的出现，如果P(AB)=P(A)P(B);否则，作为事件，项集A和B是依赖的（dependent） 和相关的（correlated）。这个定义容易推广到两个以上的项集。A和B出现之间的提升度可以通过计算正式得到,让我们回到例6.7的计算机游戏和录像数据 例6.8 使用提升度的相关分析 为

4、了帮助过滤掉从例6.7的数据得到的形如A=B的误导“强”关联，需要研究两个项集A和B如何相关的。设 表示例6.7中不包含计算机游戏的事务， 表示不包含录像的事务。这些事务可以汇总在一个相依表（contingency）中。,小结,大量数据之间的关联关系的发现在选择购物、决策分析和商务管理方面是有用的。一个流行的应用领域是购物篮分析，通过搜索经常一块（或依次）购物的商品的集合，研究顾客的购物习惯。关联规则首先找出频繁项集（项的集合，如A和B，满足最小支持度阈值，或相关任务的百分比），然后，由它们产生形如AB的强关联规则。这些规则也满足最小置信度阈值（预定义的在满足A的条件下满足B的概率）。,根据不

5、同的标准，关联规则可以分成若干类型，如：,根据规则所处理的值的类型，关联规则可以分为布尔的和量化的。布尔规则表现离散（分类）对象之间的联系。量化关联规则是多维关联规则，涉及动态离散化的数值属性。它可能涉及分类属性。 根据规则中数据涉及的维，关联规则可以分为单维和多维的。单维关联规则涉及单个谓词或维，如buys；而多维关联规则涉及多个（不同的）谓词或维。单维关联规则涉及的是属性内联系（即同一属性或维内的关联）；多维关联规则展示的是属性间的联系（即属性/维之间的关联）。 根据规则涉及的抽象层，关联规则可以分为单层和多层。在单层关联规则中，项或谓词的挖掘不考虑不同的抽象层；而多层关联规则考虑多个抽象

6、层。 根据对关联挖掘的不同扩充，关联挖掘可以扩充为相关分析和最大频繁模式（“最大模式”）与频繁闭项集挖掘。相关分析指出相关项的存在与否。,2020/7/8,Apriori算法,Apriori算法是一种有效的关联规则挖掘算法，它探查逐级挖掘Aprior性质：频繁项的所有非空子集都必须是频繁的。在第K次（k1），它根据频繁k-项集，形成频繁（k+1）-项集候选，并扫描数据库一次，找出完整的频繁（k+1）-项集L。 涉及散列和事务压缩的变形可以用来使得过程更有效。其他变形涉及划分数据（在每一部分挖掘，然后合并结果）和数据选样（在数据子集上挖掘）。这些变形可以将数据扫描次数减少到两次或一次。,2020

7、/7/8,频繁模式增长（FP-增长）,是一种不产生候选的挖掘频繁项的集方法。它构造一个高度压缩的数据结构（FP-树），压缩原来的数据库。不使用类Apriori方法的产生-测试策略，它聚焦于频繁模式（段）增长，避免了高代价的候选产生，获得更好的效率。,2020/7/8,多层关联规则,多层关联规则可以根据每个抽象层上的最小支持阈值如何定义，使用多种策略挖掘。当在多层使用递减的支持度时，剪枝方法包括层交叉按单项过滤，层交叉按k-项集过滤。冗余的多层（后代）关联规则可以删除，不向用户提供，如果根据其对应得祖先规则，它们的支持度和置信度接近于期望的话。,2020/7/8,多层关联规则,挖掘多维关联规则可以根据对量化属性处理分为若干类。第一，量化属性可以根据预定义的概念分层静态离散化。数据立方体非常适合这种方法，因为数据立方体和量化属性都可以利用概念分层。第二，可以挖掘量化关联规则，其量化属性根据分箱动态离散化，其中”临近的“关联规则可以用聚类组合。第三，可以挖掘基于距离的关联规则，其中区间根据聚类的定义。,2020/7/8,并非所有的强关联规则都是有趣的。对统计相关项，可以挖掘相关规则。 基于约束的挖掘允许用户聚焦，按提供的元规则（即模式模板）和其它挖掘约束搜索规则。这种挖掘促进了