数据挖掘课件(关联分析).ppt

关联分析: 基本概念和算法,第6章 关联分析: 基本概念和算法,定义:关联分析（association analysis）,关联分析用于发现隐藏在大型数据集中的令人感兴趣的联系，所发现的模式通常用关联规则或频繁项集的形式表示。 关联分析可以应用于生物信息学、医疗诊断、网页挖掘、科学数据分析等,Rules Discovered: Diaper Beer,定义: 频繁项集（Frequent Itemset）,项集（Itemset） 包含0个或多个项的集合 例子: Milk, Bread, Diaper k-项集 如果一个项集包含k个项 支持度计数（Support count ）() 包含特定项集的事务个数 例如： (Milk, Bread,Diaper) = 2 支持度（Support） 包含项集的事务数与总事务数的比值 例如： s(Milk, Bread, Diaper) = 2/5 频繁项集（Frequent Itemset） 满足最小支持度阈值（ minsup ）的所有项集,定义: 关联规则（Association Rule）,Example:,关联规则 关联规则是形如 X Y的蕴含表达式, 其中 X 和 Y 是不相交的项集 例子: Milk, Diaper Beer 关联规则的强度 支持度 Support (s) 确定项集的频繁程度 置信度 Confidence (c) 确定Y在包含X的事 务中出现的频繁程度,关联规则挖掘问题,关联规则挖掘问题：给定事务的集合 T, 关联规则发现是指找出支持度大于等于 minsup并且置信度大于等于minconf的所有规则, minsup和minconf是对应的支持度和置信度阈值 挖掘关联规则的一种原始方法是：Brute-force approach: 计算每个可能规则的支持度和置信度 这种方法计算代价过高，因为可以从数据集提取的规则的数量达指数级 从包含d个项的数据集提取的可能规则的总数R=3d-2d+1+1，如果d等于6，则R=602,挖掘关联规则（Mining Association Rules）,大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务: 频繁项集产生（Frequent Itemset Generation） 其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。 规则的产生（Rule Generation） 其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。,频繁项集产生（Frequent Itemset Generation）,格结构（lattice structure）,频繁项集产生（Frequent Itemset Generation）,Brute-force 方法: 把格结构中每个项集作为候选项集 将每个候选项集和每个事务进行比较，确定每个候选项集的支持度计数。 时间复杂度 O(NMw)，这种方法的开销可能非常大。,降低产生频繁项集计算复杂度的方法,减少候选项集的数量 (M) 先验(apriori)原理 减少比较的次数 (NM) 替代将每个候选项集与每个事务相匹配，可以使用更高级的数据结构，或存储候选项集或压缩数据集，来减少比较次数,先验原理（ Apriori principle）,先验原理: 如果一个项集是频繁的，则它的所有子集一定也是频繁的 相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的: 这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝（support-based pruning） 这种剪枝策略依赖于支持度度量的一个关键性质，即一个项集的支持度决不会超过它的子集的支持度。这个性质也称为支持度度量的反单调性（anti-monotone）。,例子,被剪枝的超集,Apriori算法的频繁项集产生,Apriori算法的频繁项集产生,Items (1-itemsets),Pairs (2-itemsets),Triplets (3-itemsets),支持度阈值=60% 最小支持度计数 = 3,枚举所有项集将产生 6C1 + 6C2 + 6C3 = 41个候选 而使用先验原理，将较少为 6 + 6 + 1 = 13,Apriori 算法,Apriori 算法,Apriori算法的频繁项集产生的部分有两个重要的特点： 它是一个逐层算法。即从频繁1-项集到最长的频繁项集，它每次遍历项集格中的一层 它使用产生-测试策略来发现频繁项集。在每次迭代，新的候选项集由前一次迭代发现的频繁项集产生，然后对每个候选的支持度进行计数，并与最小支持度阈值进行比较。 该算法需要的总迭代次数是kmax+1，其中kmax是频繁项集的最大长度,候选的产生与剪枝(构造apriori-gen函数),蛮力方法 蛮力方法把所有的k-项集都看作可能的候选，然后使用候选剪枝除去不必要的候选 第k层产生的候选项集的数目为 虽然候选产生是相当简单的，但是候选剪枝的开销极大，因为必须考察的项集数量太大。 设每一个候选项集所需的计算量为O（k），这种方法 的总复杂度为,候选的产生与剪枝,Items (1-itemsets),Pairs (2-itemsets),Triplets (3-itemsets),支持度阈值=60% 最小支持度计数 = 3,枚举所有项集将产生 6C1 + 6C2 + 6C3 = 41个候选 而使用先验原理，将较少为 6 + 6 + 1 = 13,候选的产生与剪枝,这种方法用其他频繁项来扩展每个频繁（k-1）-项集 这种方法将产生 个候选k-项集，其中|Fj|表示频繁j-项集的个数。这种方法总复杂度是 这种方法是完全的，因为每一个频繁k-项集都是由一个频繁（k-1）-项集和一个频繁1-项集组成的。因此，所有的频繁k-项集是这种方法所产生的候选k-项集的一部分。 然而，这种方法很难避免重复地产生候选项集。 如：面包，尿布，牛奶不仅可以由合并项集面包，尿布和牛奶得到，而且还可以由合并面包，牛奶和尿布得到，或由合并尿布，牛奶和面包得到。,候选的产生与剪枝,候选的产生与剪枝,避免产生重复的候选项集的一种方法是确保每个频繁项集中的项以字典序存储，每个频繁（k-1）-项集X只用字典序比X中所有的项都大的频繁项进行扩展 如：项集面包，尿布可以用项集牛奶扩展，因为“牛奶”（milk）在字典序下比“面包”（Bread）和“尿布”（Diapers）都大。 尽管这种方法比蛮力方法有明显改进，但是仍然产生大量不必要的候选。 例如，通过合并啤酒，尿布和牛奶而得到的候选是不必要的。因为它的子集啤酒，牛奶是非频繁的。,候选的产生与剪枝,这种方法合并一对频繁（k-1）-项集，仅当它们的前k-2个项都相同。 如频繁项集面包，尿布和面包，牛奶合并，形成了候选3-项集面包，尿布，牛奶。算法不会合并项集啤酒，尿布和尿布，牛奶，因为它们的第一个项不相同。 然而，由于每个候选都由一对频繁（k-1）-项集合并而成，因此，需要附加的候选剪枝步骤来确保该候选的其余k-2个子集是频繁的。,候选的产生与剪枝,支持度计数,支持度计数过程确定在apriori-gen函数的候选项剪枝步骤保留下来的每个候选项集出现的频繁程度。计算支持度的主要方法: 一种方法是将每个事务与所有的候选项集进行比较，并且更新包含在事务中的候选项集的支持度计数。这种方法是计算昂贵的，尤其当事务和候选项集的数目都很大时。 另一种方法是枚举每个事务所包含的项集，并且利用它们更新对应的候选项集的支持度。,枚举事务t的所有包含3个项的子集,产生Hash树,Hash函数h(p)=p mod 3 假设有15个候选3-项集: 1 4 5, 1 2 4, 4 5 7, 1 2 5, 4 5 8, 1 5 9, 1 3 6, 2 3 4, 5 6 7, 3 4 5, 3 5 6, 3 5 7, 6 8 9, 3 6 7, 3 6 8,Hash树结构,1,4,7,2,5,8,3,6,9,Hash Function,Candidate Hash Tree,Hash on 1, 4 or 7,Hash树结构,1,4,7,2,5,8,3,6,9,Hash Function,Candidate Hash Tree,Hash on 2, 5 or 8,Hash树结构,1,4,7,2,5,8,3,6,9,Hash Function,Candidate Hash Tree,Hash on 3, 6 or 9,使用Hash树进行支持度计数,transaction,使用Hash树进行支持度计数,1 5 9,1 3 6,3 4 5,transaction,使用Hash树进行支持度计数,1 5 9,1 3 6,3 4 5,transaction,15个项集中的9个与事务进行比较,存放在被访问的叶结点中的候选项集与事务进行比较，如果候选项集是该事务的子集，则增加它的支持度计数。 在该例子中 ，访问了9个叶子结点中的5个。 15个项集中的9个与事务进行比较,计算复杂性,支持度阈值 降低支持度阈值通常将导致更多的项集是频繁的。计算复杂度增加 随着支持度阈值的降低，频繁项集的最大长度将增加，导致算法需要扫描数据集的次数也将增多 项数 随着项数的增加，需要更多的空间来存储项的支持度计数。如果频繁项集的数目也随着数据项数增加而增长，则由于算法产生的候选项集更多，计算量和I/O开销将增加 事务数 由于Apriori算法反复扫描数据集，因此它的运行时间随着事务数增加而增加 事务的平均宽度 频繁项集的最大长度随事务平均宽度增加而增加 随着事务宽度的增加，事务中将包含更多的项集，这将增加支持度计数时Hash树的遍历次数,规则产生,忽略那些前件或后件为空的规则，每个频繁k-项集能够产生多达2k-2个关联规则 关联规则的提取：将一个项集 Y划分成两个非空的子集 X 和Y-X，使得X Y X满足置信度阈值。 如果 A,B,C,D 是频繁项集, 候选项集为: ABC D, ABD C, ACD B, BCD A, A BCD, B ACD, C ABD, D ABC AB CD, AC BD, AD BC, BC AD, BD AC, CD AB, 这样的规则必然已经满足支持度阈值，因为它们是由频繁项集产生的。,规则产生,怎样有效的从频繁项集中产生关联规则? 一般，计算关联规则的置信度并不需要再次扫描事务数据集。规则A,B,C D的置信度为(ABCD)/ (ABC)。 因为这两个项集的支持度计数已经在频繁项集产生时得到，因此不必再扫描整个数据集. 如果规则X Y-X不满足置信度阈值，则形如XY-X的规则一定也不满足置信度阈值，其中X是X的子集。 例如：c(ABC D) c(AB CD) c(A BCD) 因为(AB) (ABC)，则(ABCD)/ (ABC) (ABCD)/ (AB) ，则c(ABC D) c(AB CD),Apriori 算法中规则的产生,低置信度规则,频繁项集的紧凑表示,由事务数据集产生的频繁项集的数量可能非常大。因此，从中识别出可以推导出其他所有的频繁项集的，较小的，具有代表性的项集是有用的。,最大频繁项集（Maximal Frequent Itemset）,频繁项集的边界,不频繁项集,最大频繁项集,最大频繁项集是这样的频繁项集，它的直接超集都不是频繁的,非频繁的,频繁的,最大频繁项集的特点,优点：最大频繁项集有效地提供了频繁项集的紧凑表示。 换句话说，最大频繁项集形成了可以导出所有频繁项集的最小的项集的集合。 从图中，可以看出，所有的频繁项集是最大频繁项集 A,D, A,C,E, B,C,D,E的子集 缺点：尽管最大频繁项集提供了一种紧凑表示，但是它却不包含它们子集的支持度信息。,频繁闭项集（Closed Frequent Itemset）,闭项集（Closed Itemset）：项集X是闭的，如果它的直接超集都不具有和它相同的支持度计数。 换句话说，如果至少存在一个X的直接超集，其支持度计数与X相同，X就不是闭的。 频繁闭项集: 一个项集是频繁闭项集，如果它是闭的，并且它的支持度大于或等于最小支持度阈值。,频繁闭项集,Transaction Ids,Not supported by any transactions,频繁闭项集,minsup = 40%,# Closed Frequent Itemset = 9 # Maximal Frequent itemset = 4,频繁项集、最大频繁项集和频繁闭项集之间的关系,产生频繁项集的其他方法,项集格遍历 一般到特殊 vs 特殊到一般。 一般到特殊：适合于频繁项集的最大长度不是太长的时候。 特殊到一般：适合于处理频繁项集的最大长度较长的时候,产生频繁项集的其他方法,项集格遍历 等价类：将格划分为两个不相交的节点组（或等价类）。频繁项集产生算法依次在每个等价类内搜索频繁项集 Apriori算法采用的逐层策略可以看作根据项集的大小划分格。等价类也可以根据项集的前缀或后缀来定义。,产生频繁项集的其他方法,项集格遍历 宽度优先与深度优先 通常，深度优先搜索方法是用于发现最大频繁项集的算法,产生频繁项集的其他方法,事务数据集的表示 水平数据分布（horizontal data layout） 垂直（vertical data layout）,FP增长算法（FP-growth Algorithm）,该算法采用完全不同的方法来发现频繁项集。 该算法不同于Apriori算法的“产生-测试”范型。而是使用一种称作FP树的紧凑数据结构组织数据，并直接从该结构中提取频繁项集。 FP树是一种输入数据的压缩表示，它通过逐个读入事务，并把每个事务映射到FP树中的一条路径来构造。,构造FP树,扫描一次数据集，确定每个项的支持度计数。丢弃非频繁项，而将频繁项按照支持度的递减排序 算法第二次扫描数据集，构建FP树。读入第一个事务a，b之后，创建标记为a和b的结点。然后形成null-a-b路径，对该事务编码。该路径上的所有结点的频度计数为1. 读入第二个事务b，c，d之后，为项b，c和d创建新的结点集。然后，连接结点null-b-c-d，形成一条代表该事务的路径。该路径上的每个结点的频度计数也等于1.尽管前两个事务具有一个共同项b，但是它们的路径不相交，因为这两个事务没有共同的前缀。,构造FP树,null,A:1,B:1,null,A:1,B:1,B:1,C:1,D:1,读入事务 TID=1后:,读入事务 TID=2后:,第三个事务a，c，d，e与第一个事务共享一个共同的前缀项a，所以第三个事务的路径null-a-c-d-e与第一个事务的路径null-a-b部分重叠。因为它们的路径重叠，所以结点a的频度计数增加为2. 继续该过程，直到每个事务都映射到FP树的一条路径。,构造FP树,D:1,E:1,null,A:1,B:1,B:1,C:1,D:1,读入事务 TID=3后:,C:1,构造FP树,null,A:8,B:5,B:2,C:2,D:1,C:1,D:1,C:3,D:1,D:1,E:1,E:1,D:1,E:1,构造FP树,通常，FP树的大小比未压缩的数据小，因为购物篮数据的事务常常共享一些共同项。如果共同项较少，FP树对存储空间的压缩效果将不明显。 FP树的大小也依赖于项如何排序。一般按照支持度计数递减序可以导致较小的FP树。但也有一些例外。 FP树还包含一个连接具有相同项的结点的指针列表。这些指针有助于方便快捷地访问树中的项。,构造FP树,FP增长（FP-growth）算法,FP增长是一种以自底向上方式探索树，由FP树产生频繁项集的算法。 由于每一个事务都映射到FP树中的一条路径，因而通过仅考察包含特定结点（例如e）的途径，就可以发现以e结尾的频繁项集。使用与结点e相关联的指针，可以快速访问这些路径。,FP增长（FP-growth）算法,FP增长（FP-growth）算法,FP增长（FP-growth）算法,关联模式的评估（Pattern Evaluation）,关联分析算法往往产生大量的规则，而其中很大一部分可能是不感兴趣的。 因此，建立一组广泛接受的评价关联模式质量的标准是非常重要的。 第一组标准可以通过统计论据建立。涉及相互独立的项或覆盖少量事务的模式被认为是不令人感兴趣的，因为它们可能反映数据中的伪联系。 这些令人感兴趣的模式可以使用客观兴趣度度量来排除。,第二组标准可以通过主观论据建立。一个模式被主观认为是无趣的，除非它能够揭示料想不到的信息或提供导致有益的行动的有用信息。 例如：黄油 面包可能不是有趣的，尽管有很高的支持度和置信度，但是它表示的关系显而易见。另一方面，规则尿布 啤酒是有趣的，因为这种联系十分出乎意料，并且可能为零售商提供新的交叉销售机会。 将主观知识加入到模式的评价中是一项困难的任务，因为需要来自领域专家的大量先验信息。下面是一些将主观信息加入到模式发现任务中的方法。,兴趣度客观度量（objective interestingness measure）,客观兴趣度度量使用从数据推导出的统计量来确定模式是否是有趣的。 客观兴趣度度量的例子包括支持度、置信度、相关性。 给定一个规则 X Y, 我们可以构建一个相依表（contingency table）。,Contingency table for X Y,支持度-置信度框架的局限性,现有的关联规则的挖掘算法依赖于支持度和置信度来除去没有意义的模式。 例子：假定希望分析爱喝咖啡和爱喝茶的人之间的关系。收集一组人关于饮料偏爱的信息，并汇总到下表6-8。,支持度-置信度框架的局限性,可以使用表中给出的信息来评估关系规则茶 咖啡。 似乎喜欢喝茶的人也喜欢喝咖啡，因为该规则的支持度（15%）和置信度（75%）都相当高。 但是所有人中，不管他是否喝茶，喝咖啡的人的比例为80%。这意味着，一个人如果喝茶，则他喝咖啡的可能性由80%减到了75%。 置信度的缺点在于该度量忽略了规则后件中项集的支持度。,由于支持度-置信度框架的局限性，各种客观度量已经用来评估关联模式。下面，简略介绍这些度量并解释它们的优点和局限性。 兴趣因子 相关分析 IS度量,兴趣因子,茶和咖啡的例子表明，由于置信度度量忽略了规则后件中出现的项集的支持度，高置信度的规则有时存在误导。 解决这个问题的一种方法是使用称作提升度（lift）的度量： 它计算规则置信度和规则后件中项集的支持度之间的比率 对于二元变量，提升度等价于另一种称作兴趣因子（interest factor）的客观度量，其定义如下：,对于相互独立的两个变量，I(A,B)=1。如果A和B是正相关的,则I(A,B)1。对于表6-8中的例子，I=0.15/(0.2*0.8)=0.9375, 这表明存在负相关。 兴趣因子的局限性 表6-9显示了两个词p,q和r,s出现的频率。p,q和r,s的兴趣因子分别为1.02和4.08. 这表明虽然p和q同时出现在88%的文档中，但是它们的兴趣因子接近于1，表明二者是相互独立的。另一方面，r,s的兴趣因子比p,q的高，尽管r和s很少同时出现在同一个文档中。 这种情况下，置信度可能是一个更好的选择，因为置信度表明p和q之间的关联（94.6%）远远强于r和s之间的关联（28.6%）.,表6-9,相关分析,对于二元变量，相关度可以用以下公式表示。 相关度的值从-1（完全负相关）到+1（完全正相关）。如果变量是统计独立的，则值为0.例如：在表6-8中给出的饮茶者和喝咖啡者之间的相关度为-0.0625。,相关分析的局限性 相关性的缺点通过表6-9所给出词的关联可以看出.虽然p和q同时出现的次数比r和s更多，但是它们的系数是相同的，都等于0.232。 这是因为，这种方法把项在事务中出现和同时不出现视为同等重要。因此，它更适合于分析对称的二元变量。 这种度量的另一个局限性是，当样本大小成比例变化时，它不能够保持不变。,IS度量,IS是另一种度量，用于处理非对称二元变量。该度量定义如下： 表6-9中显示的词对p,q和r,s的IS值分别是0.946和0.286.IS度量暗示p,q之间的关联强于r,s，这与期望的文档中词的关联一致。 可以证明IS数学上等价于二元变量的余弦变量,IS度量也可以表示为从一对二元变量中提取出的关联规则的置信度的几何平均值： IS度量的局限性 一对相互独立的项集A和B的IS值是： 尽管表6-10中所显示的项p和q之间的IS值相当大（0.889），当项统计独立时它仍小于期望值（ISindep=0.9）。,表6-10,其他客观兴趣度度量,不同度量间的比较,客观度量的性质,反演性 客观度量M在反演操作下是不变的，如果交换频度计数f11和f00、f10和f01它的值保持不变.,在反演操作下保持不变的度量有系数、几率、k和集体强度。 这些度量可能不适合于分析非对称的二元数据。 一些非反演不变的度量包括兴趣因子、IS、PS、Jaccard系数。,零加性 客观度量M在零加操作下是不变的，如果增加f00而保持相依表中所有其他的频度不变并不影响M的值. 对文档分析或购物篮分析这样的应用，期望度量多在零加操作下保持不变。满足零加性的度量包括余弦（IS）和Jaccard度量，而不满足该性质的度量包括兴趣因子、PS、几率和系数。 缩放性 客观度量M在行/列缩放操作下是不变的，如果M（T）=M（T），其中T是频度计数为f11,f00,f10,f01的相依表。T是频度计数为k1k3f11, k2k3f10, k1k4f01, k2k4f00的