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

关联分析 基本概念和算法 第6章关联分析 基本概念和算法 定义 关联分析 associationanalysis 关联分析用于发现隐藏在大型数据集中的令人感兴趣的联系 所发现的模式通常用关联规则或频繁项集的形式表示 关联分析可以应用于生物信息学 医疗诊断 网页挖掘 科学数据分析等 RulesDiscovered Diaper Beer 定义 频繁项集 FrequentItemset 项集 Itemset 包含0个或多个项的集合例子 Milk Bread Diaper k 项集如果一个项集包含k个项支持度计数 Supportcount 包含特定项集的事务个数例如 Milk Bread Diaper 2支持度 Support 包含项集的事务数与总事务数的比值例如 s Milk Bread Diaper 2 5频繁项集 FrequentItemset 满足最小支持度阈值 minsup 的所有项集 定义 关联规则 AssociationRule Example 关联规则关联规则是形如X Y的蕴含表达式 其中X和Y是不相交的项集例子 Milk Diaper Beer 关联规则的强度支持度Support s 确定项集的频繁程度置信度Confidence c 确定Y在包含X的事务中出现的频繁程度 关联规则挖掘问题 关联规则挖掘问题 给定事务的集合T 关联规则发现是指找出支持度大于等于minsup并且置信度大于等于minconf的所有规则 minsup和minconf是对应的支持度和置信度阈值挖掘关联规则的一种原始方法是 Brute forceapproach 计算每个可能规则的支持度和置信度这种方法计算代价过高 因为可以从数据集提取的规则的数量达指数级从包含d个项的数据集提取的可能规则的总数R 3d 2d 1 1 如果d等于6 则R 602 挖掘关联规则 MiningAssociationRules 大多数关联规则挖掘算法通常采用的一种策略是 将关联规则挖掘任务分解为如下两个主要的子任务 频繁项集产生 FrequentItemsetGeneration 其目标是发现满足最小支持度阈值的所有项集 这些项集称作频繁项集 规则的产生 RuleGeneration 其目标是从上一步发现的频繁项集中提取所有高置信度的规则 这些规则称作强规则 strongrule 频繁项集产生 FrequentItemsetGeneration 格结构 latticestructure 频繁项集产生 FrequentItemsetGeneration Brute force方法 把格结构中每个项集作为候选项集将每个候选项集和每个事务进行比较 确定每个候选项集的支持度计数 时间复杂度 O NMw 这种方法的开销可能非常大 降低产生频繁项集计算复杂度的方法 减少候选项集的数量 M 先验 apriori 原理减少比较的次数 NM 替代将每个候选项集与每个事务相匹配 可以使用更高级的数据结构 或存储候选项集或压缩数据集 来减少比较次数 先验原理 Aprioriprinciple 先验原理 如果一个项集是频繁的 则它的所有子集一定也是频繁的相反 如果一个项集是非频繁的 则它的所有超集也一定是非频繁的 这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝 support basedpruning 这种剪枝策略依赖于支持度度量的一个关键性质 即一个项集的支持度决不会超过它的子集的支持度 这个性质也称为支持度度量的反单调性 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 pmod3假设有15个候选3 项集 145 124 457 125 458 159 136 234 567 345 356 357 689 367 368 Hash树结构 1 4 7 2 5 8 3 6 9 HashFunction CandidateHashTree Hashon1 4or7 Hash树结构 1 4 7 2 5 8 3 6 9 HashFunction CandidateHashTree Hashon2 5or8 Hash树结构 1 4 7 2 5 8 3 6 9 HashFunction CandidateHashTree Hashon3 6or9 使用Hash树进行支持度计数 transaction 使用Hash树进行支持度计数 159 136 345 transaction 使用Hash树进行支持度计数 159 136 345 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 ABCAB CD AC BD AD BC BC AD BD AC CD AB 这样的规则必然已经满足支持度阈值 因为它们是由频繁项集产生的 规则产生 怎样有效的从频繁项集中产生关联规则 一般 计算关联规则的置信度并不需要再次扫描事务数据集 规则 A B C D 的置信度为 ABCD ABC 因为这两个项集的支持度计数已经在频繁项集产生时得到 因此不必再扫描整个数据集 如果规则X Y X不满足置信度阈值 则形如X Y 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算法中规则的产生 低置信度规则 频繁项集的紧凑表示 由事务数据集产生的频繁项集的数量可能非常大 因此 从中识别出可以推导出其他所有的频繁项集的 较小的 具有代表性的项集是有用的 最大频繁项集 MaximalFrequentItemset 频繁项集的边界 不频繁项集 最大频繁项集 最大频繁项集是这样的频繁项集 它的直接超集都不是频繁的 非频繁的 频繁的 最大频繁项集的特点 优点 最大频繁项集有效地提供了频繁项集的紧凑表示 换句话说 最大频繁项集形成了可以导出所有频繁项集的最小的项集的集合 从图中 可以看出 所有的频繁项集是最大频繁项集 A D A C E B C D E 的子集缺点 尽管最大频繁项集提供了一种紧凑表示 但是它却不包含它们子集的支持度信息 频繁闭项集 ClosedFrequentItemset 闭项集 ClosedItemset 项集X是闭的 如果它的直接超集都不具有和它相同的支持度计数 换句话说 如果至少存在一个X的直接超集 其支持度计数与X相同 X就不是闭的 频繁闭项集 一个项集是频繁闭项集 如果它是闭的 并且它的支持度大于或等于最小支持度阈值 频繁闭项集 TransactionIds Notsupportedbyanytransactions 频繁闭项集 minsup 40 ClosedFrequentItemset 9 MaximalFrequentitemset 4 频繁项集 最大频繁项集和频繁闭项集之间的关系 产生频繁项集的其他方法 项集格遍历一般到特殊vs特殊到一般 一般到特殊 适合于频繁项集的最大长度不是太长的时候 特殊到一般 适合于处理频繁项集的最大长度较长的时候 产生频繁项集的其他方法 项集格遍历等价类 将格划分为两个不相交的节点组 或等价类 频繁项集产生算法依次在每个等价类内搜索频繁项集Apriori算法采用的逐层策略可以看作根据项集的大小划分格 等价类也可以根据项集的前缀或后缀来定义 产生频繁项集的其他方法 项集格遍历宽度优先与深度优先通常 深度优先搜索方法是用于发现最大频繁项集的算法 产生频繁项集的其他方法 事务数据集的表示水平数据分布 horizontaldatalayout 垂直 verticaldatalayout FP增长算法 FP growthAlgorithm 该算法采用完全不同的方法来发现频繁项集 该算法不同于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 算法 关联模式的评估 PatternEvaluation 关联分析算法往往产生大量的规则 而其中很大一部分可能是不感兴趣的 因此 建立一组广泛接受的评价关联模式质量的标准是非常重要的 第一组标准可以通过统计论据建立 涉及相互独立的项或覆盖少量事务的模式被认为是不令人感兴趣的 因为它们可能反映数据中的伪联系 这些令人感兴趣的模式可以使用客观兴趣度度量来排除 第二组标准可以通过主观论据建立 一个模式被主观认为是无趣的 除非它能够揭示料想不到的信息或提供导致有益的行动的有用信息 例如 黄油 面包 可能不是有趣的 尽管有很高的支持度和置信度 但是它表示的关系显而易见 另一方面 规则 尿布 啤酒 是有趣的 因为这种联系十分出乎意料 并且可能为零售商提供新的交叉销售机会 将主观知识加入到模式的评价中是一项困难的任务 因为需要来自领域专家的大量先验信息 下面是一些将主观信息加入到模式发现任务中的方法 兴趣度客观度量 objectiveinterestingnessmeasure 客观兴趣度度量使用从数据推导出的统计量来确定模式是否是有趣的 客观兴趣度度量的例子包括支持度 置信度 相关性 给定一个规则X Y 我们可以构建一个相依表 contingencytable ContingencytableforX Y 支持度 置信度框架的局限性 现有的关联规则的挖掘算法依赖于支持度和置信度来除去没有意义的模式 例子 假定希望分析爱喝咖啡和爱喝茶的人之间的关系 收集一组人关于饮料偏爱的信息 并汇总到下表6 8 支持度 置信度框架的局限性 可以使用表中给出的信息来评估关系规则 茶 咖啡 似乎喜欢喝茶的人也喜欢喝咖啡 因为该规则的支持度 15 和置信度 75 都相当高 但是所有人中 不管他是否喝茶 喝咖啡的人的比例为80 这意味着 一个人如果喝茶 则他喝咖啡的可能性由80 减到了75 置信度的缺点在于该度量忽略了规则后件中项集的支持度 由于支持度 置信度框架的局限性 各种客观度量已经用来评估关联模式 下面 简略介绍这些度量并解释它们的优点和局限性 兴趣因子相关分析IS度量 兴趣因子 茶和咖啡的例子表明 由于置信度度量忽略了规则后件中出现的项集的支持度 高置信度的规则有时存在误导 解决这个问题的一种方法是使用称作提升度 lift 的度量 它计算规则置信度和规则后件中项集的支持度之间的比率对于二元变量 提升度等价于另一种称作兴趣因子 interestfactor 的客观度量 其定义如下 对于相互独立的两个变量 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 的相依表 表6 16显示了1993年和2004年注册某课程的学生的性别和成绩的相依表 多个二元变量的度量 使用多维相依表 可以扩展到多个变量 例如 表6 18显示了a b和c的3维相依表 倾斜支持度分布的影响 许多关联分析算法的性能受输入数据的性质的影响 例如 Apriori算法的计算复杂性依赖于数据中的项数和事务的平均长度等性质 具有倾斜支持度分布的数据集 其中大多数项具有较低或中等频率 但是少数项具有很高的频率 图6 29显示了一个呈现这种分布的实际数据集的例子 该数据取自PUMS人口普查数据 它包含49046条记录和2113个非对称的二元变量 选择合适的支持度阈值较难 如果阈值太高 则可能遗漏涉及G1中较低支持度项的有趣模式 如 在购物篮数据中 顾客很少买的昂贵商品 珠宝等如果支持度阈值太低 提取出的关联模式大幅增加 可能提取出大量的高频率项 如 牛奶 与低频率项 如 鱼子酱 相关联的虚假模式 这样的模式称为交叉支持 cross support 模式 定义6 9交叉支持模式交叉支持模式是一个项集X i1 i2 ik 它的支持度比率小于用户指定的阈值hc假设牛奶的支持度是70 糖的支持度是10 鱼子酱的支持度是0 004 给定hc 0 01 频繁项集 牛奶 糖 鱼子酱 是一个交叉支持模式 因为r 0 00058 0 01 现有的度量 如支持度和置信度 都不足以消除交叉支持模式 例如 图6 30所示 当hc 0 3时 项集 p q p r p q r 是交叉支持模式 虽然它们支持度很高为4 30 13 3 因为它们的支持度比率为0 2 小于阈值0 3 例如 置信度也无法消除交叉支持模式 因为交叉模式 q p 的置信度达到80 图6 30 由于p的大部分事务不包含q 所以由模式 p q 导出的规则 p q 的置信度很低 相反 由 r q 导出的规则 r q 却有很高的置信度 这一观察暗示 可以通过检查由给定项集提取的最低置信度规则来检测交叉支持模式 所以 当我们保证h置信度值超过hc时 就可以消除交叉支持模式 除可以消除交叉支持模式外 h置信度还具有反单调性的特点 所以可以直接并入挖掘算法 此外 h置信度能够确保项集中的项之间是强关联的 即超团模式 hypercliquepattern 挖掘关联模式的研究问题