5挖掘频繁模式、关联和相关

1、挖掘频繁模式、关联和相关,什么是频繁模式分析？,频繁模式是频繁的出现在数据集中的模式 如项集、子序或者子结构 动机：发现数据中蕴含的内在规律 那些产品经常被一起购买？-啤酒和尿布？ 买了PC之后接着都会买些什么？ 哪种DNA对这种新药敏感 我们能够自动的分类WEB文档吗？ 应用 购物篮分析、WEB日志（点击流）分析、捆绑销售、DNA序列分析等,频繁模式挖掘的重要性,揭示数据集的内在的、重要的特性 作为很多重要数据挖掘任务的基础 关联、相关和因果分析 序列、结构（e.g.子图）模式分析 时空、多媒体、时序和流数据中的模式分析 分类：关联分类 聚类分析：基于频繁模式的聚类 数据仓库：冰山方体计算,

2、购物篮分析,如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示（e.g. 0001001100，这种方法丢失了什么信息？） 关联规则的两个兴趣度度量 支持度 置信度 通常，如果关联规则同时满足最小支持度阈值和最小置信度阈值，则此关联规则是有趣的,关联规则：基本概念,给定： 项的集合：I=i1,i2,.,in 任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得 每个事务由事务标识符TID标识； A,B为两个项集，

3、事务T包含A当且仅当 则关联规则是如下蕴涵式： 其中 并且 ，规则 在事务集D中成立，并且具有支持度s和置信度c,规则度量：支持度和置信度,Customer buys diaper,Customer buys both,Customer buys beer,支持度s是指事务集D中包含 的百分比 置信度c是指D中包含A的事务同时也包含B的百分比 假设最小支持度阈值为50%，最小置信度阈值为50%，则有如下关联规则 A C (50%, 66.6%) C A (50%, 100%) 同时满足最小支持度阈值和最小置信度阈值的规则称作强规则,P148 ,基本概念示例,项的集合 I=A,B,C,D,E,F

4、 每个事务T由事务标识符TID标识，它是项的集合 TID(2000)=A,B,C 任务相关数据D是数据库事务的集合,D,频繁项集,基本概念 k项集：包含k个项的集合 牛奶，面包，黄油是个3项集 项集的频率是指包含项集的事务数，简称为项集的频率、支持度计数或计数 项集的支持度有时称为相对支持度，而出现的频率称作绝对支持度。如果项集I的频率大于（最小支持度阈值D中的事务总数），则称该项集I为频繁项集。频繁k项集的集合通常记作Lk。,关联规则挖掘 的两步过程,一般来说，关联规则的挖掘可以看作两步的过程： 找出所有频繁项集 该项集的每一个出现的频繁性 min_sup 由频繁项集产生强关联规则 即满足最

5、小支持度和最小置信度的规则 主要挑战：会产生大量满足min_sup的项集，尤其当min_sup设置得低的时候 E.g. 一个长度为100的频繁项集a1,a2,a100包含的频繁项集的总个数为,闭频繁项集和极大频繁项集,如果不存在真超项集Y使得Y与X在S中有相同的支持度计数，则称项集X在数据集S中是闭的。项集X是数据集S中的闭频繁项集，如果X在S中是闭的和频繁的。项集X是S中的极大频繁项集（或极大项集），如果X是频繁的，并且不存在超项集Y使得 并且Y在S中是频繁的。 设C是数据集S中满足min_sup的闭频繁项集的集合，令M是S中满足min_sup的极大频繁项集的集合。假定我们有C和M中每个项集

6、的支持度计数，则C和他的计数信息可以用来导出频繁项集的完整集合（我们称C包含了关于频繁项集的完整信息）。 E.g. DB中只有两个事务; ，min_sup=1，则 C= :1; :2，M= :1 （显然a1,a2,a100 有个频繁超集a1,a2,a100 ）。,关联规则挖掘分类 (1),根据挖掘的模式的完全性分类：给定min_sup，可以挖掘频繁项集的完全集，闭频繁项集和极大频繁项集。也可以挖掘被约束的频繁项集（即满足用户指定的一组约束的频繁项集）、近似的频繁项集（只推导被挖掘的频繁项集的近似支持度计数）、接近匹配的频繁项集（即与接近或几乎匹配的项集的支持度计数符合的项集）、top-k频繁项

7、集 不同的应用对挖掘的模式的完全性有不同的要求，我们主要研究挖掘频繁项集的完全集、闭频繁项集和被约束的频繁项集,关联规则挖掘分类 (2),根据规则集所涉及的抽象层 单层关联规则 多层关联规则 （挖掘的规则集由多层关联规则组成） E.g. 下例购买的商品涉及不同的抽象级 根据规则中设计的数据维 单维关联规则 E.g.（仅涉及buys这个维） 多维关联规则,关联规则挖掘分类 (3),根据规则中所处理的值类型 布尔关联规则（规则考虑的关联为项是否出现） 量化关联规则（规则描述量化的项或属性间的关联） 根据所挖掘的规则类型分类 关联规则 相关规则 强梯度联系,关联规则挖掘分类 (4),根据所挖掘的模式

8、类型分类 频繁项集挖掘 从事务或关系数据集中挖掘频繁项集 序列模式挖掘 从序列数据集中搜索频繁子序列 结构模式挖掘 在结构化数据集中搜索频繁子结构,由事务数据库挖掘单维布尔关联规则,最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。,最小支持度 50% 最小置信度 50%,对规则A C，其支持度 =50% 置信度,Apriori算法 (1),Apriori算法是挖掘布尔关联规则频繁项集的算法 Apriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。 先找到频繁1-项集集合L

9、1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。,Apriori算法 (2),Apriori算法利用的是Apriori性质：频繁项集的所有非空子集也必须是频繁的。 模式不可能比A更频繁的出现 Apriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。 Apriori性质通过减少搜索空间，来提高频繁项集逐层产生的效率,Apriori算法步骤,Apriori算法由连接和剪枝两个步骤组成。 连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。 Lk-1中的两个元素

10、L1和L2可以执行连接操作 的条件是 Ck是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk 。 为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。,Apriori算法示例,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,使用Apiori性质由L2产生C3,1 连接： C3=L2 L2= A,C,B,C,B,EC,E A,C,B,C,B

11、,EC,E = A,B,C,A,C,E,B,C,E 2使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选项C3，我们可以删除其子集为非频繁的选项： A,B,C的2项子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以删除这个选项； A,C,E的2项子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以删除这个选项； B,C,E的2项子集是B,C,B,E,C,E，它的所有2项子集都是L2的元素，因此保留这个选项。 3这样，剪枝后得到C3=B,C,E,由频繁项集产生关联规则,同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置

12、信度则可由一下公式计算： 每个关联规则可由如下过程产生： 对于每个频繁项集l，产生l的所有非空子集； 对于每个非空子集s，如果 则输出规则“ ”,提高Apriori算法的有效性(1),Apriori算法主要的挑战 要对数据进行多次扫描； 会产生大量的候选项集； 对候选项集的支持度计算非常繁琐； 解决思路 减少对数据的扫描次数； 缩小产生的候选项集； 改进对候选项集的支持度计算方法 方法1：基于hash表的项集计数 将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。,提高Apriori算法的有效性(2),方法2：事务

13、压缩（压缩进一步迭代的事务数） 不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除。 方法3：划分 挖掘频繁项集只需要两次数据扫描 D中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。 第一次扫描：将数据划分为多个部分并找到局部频繁项集 第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集,提高Apriori算法的有效性(3),方法4：选样（在给定数据的一个子集挖掘） 基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式 通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适

14、当降低最小支持度来减少遗漏的频繁模式 可以通过一次全局扫描来验证从样本中发现的模式 可以通过第二此全局扫描来找到遗漏的模式 方法5：动态项集计数 在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算。,不产生候选频繁项集的算法FP树,Apriori算法的主要开销： 可能要产生大量的候选项集 104个频繁1-项集会导致107个频繁2-项集 对长度为100的频繁模式，会产生2100个候选 重复扫描数据库，通过模式匹配检查一个很大的候选集合 不产生候选频繁项集的算法FP-树频集算法 一种采用divide and c

15、onquer（分治策略）的方法 在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息； 将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。,从数据库构建一个FP树,min_sup= 3,TIDItems bought (ordered) frequent items 100f, a, c, d, g, i, m, pf, c, a, m, p 200a, b, c, f, l, m, of, c, a, b, m 300 b, f, h, j, of, b 400 b, c, k, s, pc,

16、 b, p 500 a, f, c, e, l, p, m, nf, c, a, m, p,步骤: 扫描一次数据库，导出频繁项的集合（1-项集） 将频繁项按降序排列 再次扫描数据库，构建FP树,FP树的构建（第二次扫描数据库）,创建树的根节点，用null标记； 将每个事务中的项按递减支持度计数排列，并对每个事务创建一个分枝； 比如为第一个事务f, c, a, m, p构建一个分枝 当为一个事务考虑增加分枝时，沿共同前缀上的每个节点的计数加1，为跟随前缀后的项创建节点并连接 比如将第二个事务f, c, a, b, m加到树上时，将为f，c，a各增计数1，然后为b, m创建分枝 创建一个项头表，以

17、方便遍历，每个项通过一个节点链指向它在树中的出现。,FP树结构的好处,完整性 不会打破任何事务数据中的长模式 为频繁模式的挖掘保留了完整的信息 紧凑性 减少了不相关的信息非频繁的项被删除 按频率递减排列使得更频繁的项更容易在树结构中被共享 数据量比原数据库要小,FP树挖掘,FP树的挖掘步骤： 由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”，由FP树中与后缀模式一起出现的前缀路径集组成。 构造该初始后缀模式的条件FP树，并递归的在该树上实现挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。,FP树挖掘从FP树到条件模式基,从项头表开始挖掘，由频率低的节

18、点开始 沿循每个（频繁）项的链接来遍历FP树 通过积累该项的前缀路径来形成一个条件模式基,Conditional pattern bases itemcond. pattern base cf:3 afc:3 bfca:1, f:1, c:1 mfca:2, fcab:1 pfcam:2, cb:1,FP树挖掘构建条件FP树,对每个条件模式基 为基中的每一项累积计数 为模式基中的频繁项构建FP树,m-条件模式基: fca:2, fcab:1,所有关于m的频繁模式： m, fm, cm, am, fcm, fam, cam, fcam,null,f:4,c:1,b:1,p:1,b:1,c:3,a

19、:3,b:1,m:2,p:2,m:1,项头表 Item frequency head f4 c4 a3 b3 m3 p3,多层关联规则 (1),数据项中经常会形成概念分层 底层的数据项，其支持度往往也较低 这意味着挖掘底层数据项之间的关联规则必须定义不同的支持度,All,Computer accessory,software,laptop,financial,mouse,color,printer,computer,desktop,IBM,edu.,Microsoft,b/w,HP,Sony,wrist pad,Logitech,TID,Items,T1,IBM D/C, Sony b/w,T

20、2,Ms. edu. Sw., Ms. fin. Sw.,T3,Logi. mouse, Ergoway wrist pad,T4,IBM D/C, Ms. Fin. Sw.,T5,IBM D/C,Ergoway,多层关联规则 (2),在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的 通常，事务数据库中的数据也是根据维和概念分层来进行储存的 这为从事务数据库中挖掘不同层次的关联规则提供了可能。 在多个抽象层挖掘关联规则，并在不同的抽象层进行转化，是数据挖掘系统应该提供的能力,挖掘多层关联规则的方法,通常，多层关联规则的挖掘还是使用置信度支持度框架，可以采用自顶向下策略 请注意：概念分层

21、中，一个节点的支持度肯定不小于该节点的任何子节点的支持度 由概念层1开始向下，到较低的更特定的概念层，对每个概念层的频繁项计算累加计数 每一层的关联规则挖掘可以使用Apriori等多种方法 例如： 先找高层的关联规则：computer - printer 20%, 60% 再找较低层的关联规则：laptop - color printer 10%, 50%,多层关联一致支持度,一致支持度：对所有层都使用一致的最小支持度 优点：搜索时容易采用优化策略，即一个项如果不满足最小支持度，它的所有子项都可以不用搜索 缺点：最小支持度值设置困难 太高：将丢掉出现在较低抽象层中有意义的关联规则 太低：会在较

22、高层产生太多的无兴趣的规则,多层关联递减支持度,使用递减支持度，可以解决使用一致支持度时在最小支持度值上设定的困难 递减支持度：在较低层使用递减的最小支持度 每一层都有自己的一个独立的最小支持度 抽象层越低，对应的最小支持度越小,min_sup = 5%,min_sup = 5%,min_sup = 3%,多层关联基于分组的支持度,用户和专家清楚哪些分组比其他分组更加重要，在挖掘多层关联规则时，使用用户指定的基于项或者基于分组的最小支持度阈值 E.g. 对laptop_computer或者flash_drives设置特别低的支持度阈值，以便特别关注这类商品的管理模式,检查冗余的多层关联规则,挖

23、掘多层关联规则时，由于项间的“祖先”关系，有些发现的规则将是冗余的 例如： desktop computer = b/w printer sup=8%, con=70% (1) IBM desktop computer = b/w printer sup=2%, con=72% (2) 上例中，我们说第一个规则是第二个规则的“祖先” 如果规则(2)中的项用它在概念分层中的“祖先”代替，能得到(1)，而且(1)的支持度和置信度都接近“期望”值，则(1)是冗余的。,多维关联规则概念,单维关联规则： buys(X, “milk”) buys(X, “bread”) 多维关联规则：涉及两个或多个维或谓

24、词的关联规则 维间关联规则：不包含重复的谓词 age(X,”19-25”) occupation(X,“student”) = buys(X,“coke”) 混合维关联规则：包含某些谓词的多次出现 age(X,”19-25”) buys(X, “popcorn”) = buys(X, “coke”) 在多维关联规则挖掘中，我们搜索的不是频繁项集，而是频繁谓词集。k-谓词集是包含k个合取谓词的集合。 例如：age, occupation, buys是一个3-谓词集,挖掘多维关联规则的技术,数据属性可以分为分类属性和量化属性 分类属性 具有有限个不同值，值之间无序 量化属性 数值类型的值，并且值之

25、间有一个隐含的序 挖掘多维关联规则的技术可以根据量化属性的处理分为两种种基本方法： 1. 量化属性的静态离散化 使用预定义的概念分层对量化属性进行静态地离散化 2. 量化关联规则 根据数据的分布，将量化属性离散化到“箱”,多维关联规则挖掘使用量化属性的静态离散化,量化属性使用预定义的概念分层，在挖掘前进行离散化 数值属性的值用区间代替 如果任务相关数据存在关系数据库中，则找出所有频繁的k-谓词集将需要k或k+1次表扫描 数据立方体技术非常适合挖掘多维关联规则 n-维方体的单元用于存放对应n-谓词集的计数或支持度，0-D方体用于存放任务相关数据的事务总数 如果包含感兴趣的维的数据立方体已经存在并

26、物化，挖掘将会很快，同时可以利用Apriori性质：频繁谓词集的每个子集也必须是频繁的,多维关联规则挖掘挖掘量化关联规则 (1),量化关联规则中，数值属性将根据某种挖掘标准，进行动态的离散化 例如：最大化挖掘规则的置信度和紧凑性 为了简化量化关联规则挖掘的讨论，我们将聚焦于类似以下形式的2-维量化关联规则：Aquan1 Aquan2 Acat （两个量化属性和一个分类属性间的关联） 例如： age(X,”30-39”) income(X,”42K - 48K”) buys(X,”high resolution TV”),多维关联规则挖掘挖掘量化关联规则 (2),找出这类2-维量化关联规则的方法

27、：关联规则聚类系统(ARCS) 一种源于图像处理的技术，该技术将量化属性对映射到满足给定分类属性条件的2-D栅格上，然后通过搜索栅格点的聚类而产生关联规则,关联规则聚类系统(ARCS) (1),ARCS过程中的步骤包括 1. 分箱（根据不同分箱方法创建一个2-D数组），本步骤的目的在于减少量化属性相对应的巨大的值个数，使得2-D栅格的大小可控 等宽分箱 等深分箱 基于同质的分箱（每个箱中元组一致分布） 2. 找出频繁谓词集 扫描分箱后形成的2-D数组，找出满足最小支持度和置信度的频繁谓词集,关联规则聚类系统(ARCS) (2),3. 关联规则聚类 将上一步得到的强关联规则映射到2-D栅格上，使

28、用聚类算法，扫描栅格，搜索规则的矩形聚类,ARCS的局限性,所挖掘的关联规则左手边只能是量化属性 规则的左手边只能有两个量化属性（2-D栅格的限制） 一种不基于栅格的，可以发现更一般关联规则的技术，其中任意个数的量化属性和分类属性可以出现在规则的两端 等深分箱动态划分 根据部分完全性的度量进行聚类,关联规则的兴趣度度量,客观度量 两个流行的度量指标 支持度 置信度 主观度量 最终，只有用户才能确定一个规则是否有趣的，而且这种判断是主观的，因不同的用户而异；通常认为一个规则（模式）是有趣的，如果： 它是出人意料的 可行动的（用户可以使用该规则做某些事情） 挖掘了关联规则后，哪些规则是用户感兴趣的

29、？强关联规则是否就是有趣的？,对强关联规则的批评（1）,例1：(Aggarwal & Yu, PODS98) 在5000个学生中 3000个打篮球 3750个喝麦片粥 2000个学生既打篮球又喝麦片粥 然而，打篮球 = 喝麦片粥 40%, 66.7%是错误的，因为全部学生中喝麦片粥的比率是75%，比打篮球学生的66.7%要高 打篮球 = 不喝麦片粥 20%, 33.3%这个规则远比上面那个要精确，尽管支持度和置信度都要低的多,对强关联规则的批评（2）,例1：(书P168) 上述数据可以得出 buys(X, “computer games”) = buys(X, “videos”) 40%, 6

30、0% 但其实全部人中购买录像带的人数是75%，比60%多；事实上录像带和游戏是负相关的。 由此可见A = B的置信度有欺骗性，它只是给出A,B条件概率的估计，而不度量A,B间蕴涵的实际强度。,由关联分析到相关分析,可以使用相关度量来扩充关联规则的支持度-置信度框架 我们需要一种度量事件间的相关性或者是依赖性的指标 当项集A的出现独立于项集B的出现时，P(AB)=P(A)P(B)，即lift(A,B)1，表明A与B无关， lift(A,B) 1表明A与B正相关， lift(A,B) 1表明A与B负相关 将相关性指标用于前面的例子，可以得出录像带和游戏将的相关性为： P(game, video)/

31、(P(game)P(video)=0.4/(0.750.6)=0.89 结论：录像带和游戏之间存在负相关,基于约束的关联挖掘,如何对海量数据进行交互性的，解释性的挖掘？ 充分的利用各种约束条件 知识类型约束 数据约束 维/层约束 兴趣度约束 规则约束 指定要挖掘的规则形式，可以用元规则来表示，说明规则的前件和后件中谓词的最大和最小个数，或属性、属性值和/或聚集之间的联系,关联规则的元规则制导挖掘（1）,元规则使得用户可以说明他们感兴趣的规则的语法形式 例：在AllElectronics数据库中挖掘时使用一个元规则表达顾客的特点和他购买的商品之间的关联（具有哪两种特点的顾客会买office software?） P1(X,Y)P2(X,W) = buys(X, “office software) Y,W分别取赋给谓词变量P1, P