（计算机应用技术专业论文）条件独立性在关联规则挖掘中的研究和应用.pdf

摘要 随着信息技术的应用普及，数据爆炸和知识贫乏之间的矛盾越来越大，使数 据挖掘的深入研究和广泛应用势在必行。在数据挖掘的各分支中，关联规则挖掘 的研究最为深入和广泛。对关联规则挖掘的研究又主要集中在频繁集的生成优化 和事物集的扫描次数两个方面，并且主要基于支持度可信度框架，由于这种框 架的自身缺陷，使挖掘的关联规则中用户感兴趣的却不多，因此如何使用户对挖 掘的关联规则更感兴趣又成为一项新研究任务，不少学者不采用支持度可信度 框架，尝试采用新方法来进行关联规则挖掘，以提高用户的满意度和兴趣度。本 文正是在这种背景下，研究基于条件独立性的关联规则挖掘的算法框架；研究如 何在传统关联规则挖掘的基础上，利用条件独立性进行后处理，提高关联规则的 有趣性。 本文的主要内容如下： 1 探讨了传统关联规则挖掘的主要思想和技术，分析了各种频繁集裁剪技术 和兴趣度度量。 2 给出了一种利用马尔可夫覆盖进行关联规则挖掘的算法框架，并研究了算 法中的各个组成部分。 3 提出了多项集的马尔可夫覆盖的生成方法，证明了其正确性，然后探讨了 多变量马尔可夫覆盖的贝叶斯网络表示形式。 4 面向教育评估系统中的具体应用，本文提出了对原有系统中采用的a p f i o f i 算法挖掘的关联规则进行后处理的方法：采用条件独立性和传统支持度可信度 框架相结合的方法进行关联规则的过滤，并从中发现存在的条件独立性限制。 关键词：条件独立性；马尔可夫覆盖；关联规则挖掘；贝叶斯网络；后处理 a b s t r a c t b e c a u s eo fb r o a d l yu s i n go fi n f o r m a t i o nt e c h n o l o g i e s ，t h ec o n f l i c tb e t w e e n e x p l o s i o no f d a t aa n dp o o m e s so fk n o w l e d g eh a sb e e nm o r ea n dm o r ea c u t e ，a n dt h e n e c e s s i t yo f d a t am i n i n gb e c o m e sm o r ea n dm o r eu r g e n tt o o a m o n ga l lb r a n c h e so f d a t am i n i n g ，t h er e s e a r c ho fa s s o c i a t i o nr u l em i n i n gw a st h ed e e p e s to n ea n dt h e a p p l i c a t i o no fa s s o c i a t i o nr o l em i n i n gw a st h em o s tw i d e l yu s e do n e r e s e a r c ho f a s s o c i a t i o nr o l e m i n i n g a l m o s tc o n c e n t r a t e do nt h e o p t i m a l i t y o ff r e q u e n ts e t s g e n e r a t i o na n dt h er e d u c t i o no fs c a n n i n gt i m e so f t r a n s a c t i o ns e t s m o s to ft h e mw e r e b a s e do ns u p p o r t c o n f i d e n c ef r a m e w o r k f o rt h ei n s t i n c ts h o r t c o m i n go ft h ef l a m e ， f e wa s s o c i a t i o nr u l e sw e r ei n t e r e s t i n g s ot h ee x p l o r a t i o no fh o wt o i m p r o v et h e i n t e r e s to fa s s o c i a t i o nr u l e sb e c a m ean o v e la n dp o p u l a rt a s ki nt h er e s e a r c ho f a s s o c i a t i o nr u l e m i n i n g s e v e r a le x p e l se m p l o y e dn e wm e a s u r e s t o i m p r o v et h e c o n t e n t n e s sa n di n t e r e s to fa s s o c i a t i o nr u l e sw i t h o u ta d o p t i n gs u p p o r t c o n f i d e n c e f r a m e w o r ki na s s o c i a t i o nr u l em i n i n g u n d e rs u c hb a c k g r o u n d s ，t h i sp a p e rm a k e sa s t u d yo f t h ea l g o r i t h m i cf r a m e w o r ko fa s s o c i a t i o nr u l em i n i n gb a s e do nc o n d i t i o n a l i n d e p e n d e n c e s ；e x p l o r e sh o wt op e r f o r mp o s t p r o c e s s i n g a n dh o wt o i m p r o v et h e i n t e r e s to fa s s o c i a t i o nr u l e sw i t l lc o n s t r a i n t so fc o n d i t i o n a li n d e p e n d e n c e sa f t e rt h e p r o c e s s i n go f t r a d i t i o n a la s s o c i a t i o nr u l em i n i n g f i r s t l y , t h i sp a p e re x p l o r e sm a i ni d e a sa n dp o p u l a ra l g o r i t h m s o ft r a d i t i o n a l a s s o c i a t i o nr u l em i n i n g ，a n da n a l y z e sd i f f e r e n tp r i m i n gt e c h n o l o g i e so f f r e q u e n ts e t s a n dd i f f e r e n tm e a s u r e so f i n t e r e s t s e c o n d l y , t h i sp a p e rp u t sf o r w a r dt h ea l g o r i t h m i c f r a m e w o r ko fa s s o c i a t i o nr u l em i n i n g u s i n gm a r k o vb l a n k e t ，a n da l s oe x p l o r e se a c h c o m p o n e n t so fa l g o r i t h m i cf r a m w o r k t h i r d l y , t h i sp a p e rg i v e s o u tam e t h o do f d i s c o v e r i n gm a r k o vb l a n k e to f m u l t i s e t sr a t h e rs i n g l e t o n ，a n dp r o v e s t h ec o r r e c t n e s s o ft h em e t h o d ，a f t e r w a r d st h i sp a p e re x p r e s s e si t u s i n gb a y e sn e t w o r kt o o f i n a l l y , a i m e da tt h e a p p l i c a t i o n o fe d u c a t i o n a l e v a l u a t i o n ，t h i sp a p e rp e r f o r m s p o s t p r o c e s s i n ga tt h o s er u l e sm i n e db ya p r i o r ia l g o r i t h m a n df i l t e r st h o s er u l e sw i m t h ec o n s t r a i n t so fc o n d i t i o n a li n d e p e n d e n c e s ，a n dr e a d so u tc o n d i t i o n a li n d e p e n d e n c e s f r o mr u 】e s k e y w o r d s ：c o n d i t i o n a li n d e p e n d e n c e s ；m a r k o vb l a n k e t ；a s s o c i a t i o nr u l em i n i n g ； b a y e s i a nn e t w o r k s ；p o s t - p r o c e s s i n g 条件独立性在关联规则挖掘中的研究和应用 第一章绪论 1 1 研究背景 第一章绪论 在当今信息社会的年代，数据采集和存储技术的进步导致巨型数据库不断增 多，并且其涉及到社会生活的各个方面，使数据量异常丰富，但是数据的用途仅 仅是供操作和作简单分析，对于数据中蕴含的“知识”却不太清楚，随着人们探 求数据中隐含的“知识”的愿望的日益强烈和能力的日益提高，数据挖掘( 也称 知识发现) 的研究越来越深入，应用场合也越来越广。 根据挖掘任务数据挖掘可分为：分类、聚类分析、关联规则、序列模式发现、 回归分析等等( 文献 7 ) ，它们又可以归结为两类：第一类，描述性的数据挖掘， 包括关联规则、聚类分析；第二类，预测性的数据挖掘，包括分类和回归分析 3 】。 序列模式由于挖掘内容的连续性这个特征，使其也可以进行描述性数据挖掘，也 可以进行预测性数据挖掘。但是这些分类并不是绝对的，它们之间也是相互交融 的，可以结合使用。在这些数据挖掘任务中，关联规则挖掘是其中的最为流行、 研究尤为深入和广泛的一种应用之一。 关联规则挖掘最早由a g r a w a l ( 文献 4 9 ) 等人在1 9 9 3 年提出，以后研究人员 对关联规则进行了大量的研究工作，包括对原有的算法提出优化和改进，提高算 法挖掘关联规则的效率；包括引入统计方法、并行思想等等方法设计新算法；包 括对关联规则挖掘进行推广，应用到可以应用的各个领域( 文献 1 ) 。 本文也是对关联规则挖掘在教育领域的一个应用，在高校智能评估系统中有 大量的关于现在和过去学生的资料，包含学习成绩、思想道德表现、行为表现、 奖惩情况等等，在数据比较完备的前提下，原有系统( 文献 1 0 ) 主要通过a p r i o r i 算法( 文献 2 ，5 0 ) 实现关联规则数据挖掘，挖出的关联规则比较多，有很多重复 和冗余的规则，掺杂在其中影响了挖掘的效果，使挖掘的效果不够明确和简洁。 本文正是在这样的问题驱动下，探求采用统计学习的方法，研究关联规则挖掘的 算法，并对挖掘的关联规则进行后处理，谋求挖掘效果更为简单明了。 1 2 关联规则挖掘的发展和研究现状 1 2 1 起源 由于条形码技术在零售业的广泛使用，使得人们有可能记录顾客购物的明细 记录，关联规则最早就是对于顾客的购物篮进行相似性分析，分析购物篮有哪些 河海大学硕士学位论文 条件独立性在关联规则挖掘中的研究和应用 商品是相关联的，从而进一步改进商场的商品布置，促进商场的销售。 比如说，顾客购物篮中的物品种类非常多，可能有上千种，但是顾客购买的 物品品种却不是很多，关联规则挖掘就是发现其中经常一起购买的物品种类，比 如“牛奶”和“面包”，那么超市就可以将“牛奶”和“面包”放在靠近的地方， 以方便顾客选购。这就是关联规则的一种形式：顾客一起购买“牛奶”和“面包”。 还有一种关联规则的形式，就是i fat h e nb 的启发式规则，例如如果顾客购买 了“牛奶”，那么他会买“面包”，说明购买牛奶对于购买面包具有促进作用，提 高牛奶的购买量会提高面包的销量，可以将二者捆绑销售。 1 2 2 关联规则挖掘算法的研究发展 1 9 9 3 年，i b m a l m a d m r e s e a r c h c e n t e r 的a g r a w a l 等人( 文献 4 9 ) 提出了关 联规则这一重要课题，并展开了深入的研究，首先提出了a i s 算法( 文献 4 9 ) ， 对销售的事务数据集进行挖掘，并给出了形式化的关联规则描述，提出了支持度 可信度框架生成频繁集和规则的算法。 1 9 9 4 年，a g r a w a l 等人有对a i s 算法( 文献 4 9 ) 进行了改进，提出了a p r i o r i 算法( 文献 5 0 ) ，这是关联规则挖掘的发展过程中一个具有里程碑意义的算法， 它基于一个先验规则：如果一个k + l 项集是频繁的，那么其k + 1 个k 项子集也必 定是频繁的。a p n o n 算法采用逐层迭代的方法，自底向上，发现全部的频繁集， 在很大程度上提高了关联规则挖掘的效率和时空开销。其后很多的算法都是在 a p r i o r i 算法基础上进行改进，谋求性能和效率的提高。例如a p r i o r i t i d ( 文献 5 0 ) 等算法，通过存储项集的支持事务集，这样两个项集做连接时只要求其支持事务 集的交集就可以得到支持度，而不需要再一次遍历全部事务集，但是其需要很大 的空间来存储其支持事务集。 1 9 9 5 年，p a r k 等人提出了d h p ( 动态哈希裁剪) 算法( 文献 4 0 ) ，对事务 集通过哈希裁剪，将由于项数比较小的事务从哈希树上剪掉( 或加标志) ，从而 减少了以后需要遍历的事务数。s a v a s e r e ( 文献 1 5 ) 等人提出了分区的算法，将 超大事务集分块，每一块采用以前的算法进行局部频繁集生成，然后在进行处理 产生全局频繁集。 1 9 9 7 年z a k i 为首等人研究快速关联规则挖掘的新算法( 文献 4 3 ) ，提出了 e c l a t 、m a x e e l a t 、c l i q u e 、m a x c l i q u e 四种算法，其主要采用了项集聚类、格遍 历和事务聚类等技术。 2 0 0 0 年j i a w e ih a n 提出了不采用候选项集的f p t r e e 算法( 文献 2 ，3 7 ) ， 通过f p t r e e 存储事务集，最大程度的压缩数据并保证数据的完整性，通过对 f p t r 的一次遍历生成全部的频繁集。 2 0 0 1 年r o b e r tc a s t e l o 等人提出了通过隐马尔可夫链的模拟，发现最大后验 2 条件独立性在关联规则挖掘中的研究和应用 第一章绪论 可能的马尔可夫覆盖挖掘关联规则的m a m b o 算法( 文献 5 1 ，5 2 ) 。其首先求得 所有属性的n 个最大马尔可夫覆盖，然后由马尔可夫覆盖生成关联规则，然后对 所有生成的关联规则进行过滤，过滤掉对超规则没有提高改进的子规则。其主要 涉及统计分析的一些理论和方法。 2 0 0 2 年q i n g h u az o u 等人提出模式分解的关联规则挖掘算法( 文献 4 7 ) ， 以往的关联规则挖掘算法都只记录频繁集，舍弃非频繁集，模式分解算法中不但 记录频繁集，也记录非频繁集，并且将记录的非频繁集的元素用于事务的模式分 解中，这样事务中就不存在非频繁集，很大程度上提高了挖掘的速度。 2 0 0 3 年z a k i 等人提出了采用异项集的垂直挖掘算法( 文献 4 4 ) ，主要适用 于稠密事务集，对于稀疏事务集就不适合了，其原理主要采用类似a p r i o r i t i d 算 法( 文献 5 0 ) 的t i d 集，但存储的是集合之间的相异事务集d i f f s e t ( 文献 4 4 ) 。 欧阳为民在1 9 9 9 年也提出了基于垂直数据分布的关联规则的高效发现算法( 文 献 6 ) 。2 0 0 2 年( 文献 2 3 ) 则提出了基于垂直挖掘的列分区的关联规则挖掘算 法。 总之关联规则的研究的延伸幅度非常广，这里只能抛砖引玉，简单回顾关联 规则挖掘的各方面的进展。 1 2 3 关联规则挖掘分类 根据分类原则的不同，关联规则挖掘可以有多种不同的分类方法( 文献【l 】) 。 根据数据属性是布尔型还是多值型( 数量型、类别型) 分为布尔关联规则挖 掘和多值关联规则挖掘。根据数据的概念层次划分为单层关联规则挖掘和多层关 联规则挖掘，例如前面提到的一起购买牛奶和面包就是单层关联规则，如果对牛 奶加上层次：光明牌牛奶、卫岗牌牛奶等等品牌特征，挖掘出如果购买光明牛奶 就会购买面包的多层关联规则。这就需要领域知识的帮助，比如牛奶的品牌。根 据关联规则是否具有约束分为无约束和约束性关联规则。根据关联规则的主观尺 度分类可以分为：兴趣度、支持度一可信度、条件独立性等等。 1 3 相关研究工作 1 3 1 复杂性分析 尽管在实际应用中关联规则有着很广泛的应用，对于关联规则挖掘的算法的 复杂性的彻底分析还没有定论，因为其复杂性对数据集的依赖性非常大，比如稀 疏数据和稠密数据，同一算法的性能和效率会截然不同；同样规模的数据，由于 内容的不同也会造成效率的不同。对于关联规则挖掘的算法复杂性目前研究只能 河海大学硕士学位论文 条件独立性在关联规则挖掘中的研究和应用 使用一些最常用的定量特征来对计算的复杂性进行理解，这些特征包括：可信度 s u p 、支持度c o n f 、0 - g a i n 和 一却，口c g ( 文献 3 1 ) 。 假设，是一个属性集，丁是一个在属性集上的数据库，k 是一个自然数，且 l k 的复杂性是一个n p 一 完全问题；当p h - l a p l a c e ，o - g a i n ) 时，( ，t ，p ，k ，j ) 的复杂性时一个n p 一完全 问题( 文献 3 1 ) 。 1 3 2 商_ k 产品介绍 商业产品一般都是一个数据挖掘软件包，包含关联规则发现、分类、聚类、 序列分析、回归分析等各种数据挖掘分支，其只能采用一种成熟的算法，而数据 挖掘算法是和数据集、变量集等密切相关的，所以这些数据挖掘软件包只能针对 一些它所适用的数据集。目前主要的商用产品有s p s s 公司的c l e m e n f i n e ，m 公司的i n t e l l i g e n tm i n e r ，s a s 公司的e n t e r p r i s em i n e r ，j i a w e ih a n 等开发的 d b m i n e r 等等。 1 3 3 其它应用 关联规则除了单纯为了挖掘关联规则之外，还有不少其它应用，比如w y n n e h s u 、b i n gl i u 等人( 文献 1 9 ，2 0 ，2 1 ，2 2 ) ，尝试使用将关联规则挖掘和分类结合 在一起，应用关联规则挖掘的规则作为分类的标准，构建判决树，进行分类，并 且取得不错的分类效果，有成熟的产品c b a ( c l a s s i f i c a t i o nb a s e do n a s s o c i a t i o n ) 面世：w e n m i nl i 、j i a w e ih a n 等人也在这方面做了类似的工作( 文 献 5 7 ，5 8 ) 。 s e r g e yb r i n 等人对购物篮数据的关联规则挖掘的规则进行概化，形成相关 性，通过差方测试测量关联规则的显著性，这样就形成一种在项集格中的向上的 封闭的方法，将挖掘问题降解到在格中搜索相关的和不相关的项集的边界( 文献 5 3 ，5 4 ) 。 c 叫o n 眩和c c a r s o n 等人( 文献 2 6 ，2 5 ) 还将关联规则挖掘应用到图象处 理，发现二维彩色图像内容上的关联规则。其通过特征提取、对象标志、辅助图 4 条件独立性在关联规则挖掘中的研究和应用 第一章绪论 像创建以及目标挖掘等四步，对包含地理形状的综合图像进行关联规则挖掘，发 现基于图像内容进行图像挖掘时有希望的。j t e i 6 等人( 文献 3 6 ) 使用感知关联 规则挖掘图像数据集。q i nd i n g 等人( 文献 4 8 ) 采用p - t r e e s 对遥感图像进行关 联规则挖掘。 1 4 本文主要工作 本文的主要工作如下： ( 1 ) 探讨了基于支持度可信度框架的关联规则挖掘的主要思想和技术，分 析了各种频繁集裁剪技术和兴趣度度量。 ( 2 ) 给出了一种利用马尔可夫覆盖进行关联规则挖掘的算法框架：通过遍历 构建的贝叶斯网络( 文献 2 ，1 4 ，1 6 ，2 0 ，3 0 ，3 8 ，4 5 ，4 6 ) 或者根据直接产生马尔可 夫覆盖的算法( 文献 2 4 ，2 7 ，3 0 ，3 3 ，3 4 ，3 5 ，4 2 ) 发现马尔可夫覆盖，根据马尔可夫 覆盖产生关联规则，再对关联规则集进行后处理，并对该算法框架的各个组成部 分进行了研究。 ( 3 ) 提出了多项集马尔可夫覆盖相应的生成方法，并证明其正确性。 本文针对以往马尔可夫覆盖发现算法仅能发现单项集的马尔可夫覆盖这一 点进行进行扩展，提出了多项集马尔可夫覆盖的生成方法，并且对这种方法进行 了证明，使实现关联规则的结果部分是多项集成为可能，并用贝叶斯网络进行表 刁a ( 4 ) 研究了传统关联规则挖掘的结果进行后处理的方法提出了一种采用条件 独立性和支持度、可信度、提升、兴趣度等传统度量相结合的关联规则后处理方 法，既过滤了超规则和子规则，又发现了其中隐含的条件独立性限制。 1 5 本文组织结构 本文共由5 个章节所组成： 第一章绪论部分。这一章介绍了本文的研究背景，分析了关联规则挖掘的 发展现状和关联规则挖掘的相关性工作，阐述了本文的主要研究成果和组织结 构。 第二章相关理论及技术基础。给出了关联规则挖掘的形式化的问题描述， 剖析了关联规则挖掘算法采用的重要技术和思想，讨论了关联规则的各种裁剪方 法；引出了条件独立性的概率和性质，分析了蕴含条件独立性限制的图模型的含 义，并介绍了采用信息论的表示条件独立性的方法。 第三章应用条件独立性进行关联规则挖掘的算法。在这一章里主要论述了 马尔可夫覆盖的含义，给出了一种通过直接发现马尔可夫覆盖或者遍历构建的贝 河海大学硕士学位论文条件独立性在关联规则挖掘中的研究和应用 叶斯网络后发现马尔可夫覆盖的关联规则挖掘算法框架，提出和证明了多项集马 尔可夫覆盖的生成方法，并给出了多变量马尔可夫覆盖的贝叶斯网络表示。 第四章关联规则挖掘后处理。首先分析了原有关联规则挖掘a p r i o r i 算法 的缺陷，提出了对a p r i o r i 算法挖掘的关联规则使用条件独立性方法从中发现条 件独立性限制并过滤超规则和子规则的后处理方法，并使用贝叶斯网络来表示条 件独立性和关联规则。 第五章总结和展望。对本文的工作进行了总结，并对利用条件独立性发现 关联规则中一些不足展望了下一步的工作。 6 条件独、z 眭在关联规则挖掘中的研究和应用 第二章相关理论及技术基础 第二章相关理论及技术基础 2 1 传统关联规则挖掘理论 2 1 l 问题形式化描述 设，= m i n c o n f i d e n c e ，我 们称x j y 是一条强规则，否则就是一条弱规则( 文献 1 ，3 9 ，4 9 ，5 0 ) 。 定义2 5 ：关联规则的提升 + 此处绝对值号不做绝对值使用，是衡量集合元素数目的范数，以下集合加绝对值号含义相同。 7 河海大学硕士学位论文条件独立性在关联规则挖掘中的研究和应用 关联规则的显著程度或提升1 i r ( x _ y ) ；丛! ；表连蔷型( 文献 1 0 ，1 4 ) a 给定一个事务集d ，关联规则挖掘问题就是产生支持度和可信度分别大于给 定的最小支持度和最小可信度的强关联规则。如果关联规则xjy 的提升大于 1 ，表示关联规则中前件x 对后件y 有促进作用；如果关联规则x j y 的提升 小于1 表示前件x 对后件y 没有促进作用，反而有一定的抑制作用。 2 1 2 理论基础 2 1 - 2 1 先验规则 定理2 1 ：任何频繁集的子集都必须是频繁集( 文献 2 ，4 9 ，5 0 】) 。 证明：( 反证法) 假设任意频繁集l ，其存在非频繁集的子集。设m 是l 的 非空子集，且i t i 是非频繁集，则m l 且s u p p ( m ) m i n s u p p o r t 。根据定义， s u p p ( m ) = l 卅r g d a n d r e g r i i d i 。m 三l 。 ，l r da n d l 丁 列r da n d m _ c t j f i r d a n d l t f 蚓 r i r d a n d m t l s u p p ( l ) s u p p ( m ) r a i n s u p p o r t 这与l 是频繁集矛盾，l 所以不存在非频繁集的子集，得证。 2 1 2 2 搜索空间的遍历方法 在前面问题描述中引入最小支持度和最小可信度，主要是因为在实际应用 中，对j r 的每个子集都遍历一次是非常耗时的，因为j 的子集数是2 ”1 ，所以其 遍历，的每个子集的复杂性是以指数表示的，所以需要采用这些指标来过滤掉一 些子集。 下面我们以扣 a ，b ，c ，d 为例，用格来表示i 的搜索空间( 文献 3 2 ，3 9 ) 。 条件独立- | 生在关联规则挖掘中的研究和应用 第二章相关理论及技术基础 图2 1i 的搜索空间格 在粗线下的都是频繁集，根据前面的定理椭圆形项集都是非频繁集。连接矩 形项集和椭圆形项集的弧表示从频繁集到非频繁集的转换。 定义2 6 ：最大频繁集( 文献 1 3 ，1 4 ) 最大频繁集是那些不是其他任意频繁集的子集的频繁集。如在图2 1 中的 a ，b ，c ) 、 b ，d ) 、 c ，d ) 。 定义2 7 ：闭频繁集( 文献【1 3 ，1 4 】) 一个项集是闭的，当且仅当对的每一个真超集y ，t i d ( 工) 是t i d ( 】，) 的真超集，其中t i d ( 舶是所有支持x 的事务集。项集x 是闭频繁集，当且仅 当它既是频繁集又是闭集。三者之间的关系是： 最大频繁集j 闭频繁集j 频繁集。 2 1 3 重要技术和思想 自从a g r a w a l 等人提出关联规则这个概念以来( 文献 4 9 1 ) ，许多人对关联规 则挖掘算法进行优化，提高挖掘效率，下面对其中主要使用的技术思想进行分析。 2 1 3 1 格的遍历方法 在发现频繁集时，一个最大化的频繁集就对应j r 的搜索空间一格的一个子集， 即子格，我们遍历格的方法对于频繁集的产生效率和速度也是切切相关的。 对于j 的遍历有以下三种方法( 文献 3 2 ，3 9 】) ： ( 1 ) 自底向上 自底向上的格遍历在生成所有的频繁集时，采取广度优先的策略，在生成 9 河海大学硕士学位论文条件独立性在关联规则挖掘中的研究和应用 k + 1 频繁集之前，必先生成所有的k 一频繁集。 f 2 1 自顶向下 自顶向下的遍历，首先对，全集进行支持度的计数，如果是频繁集，则其所 有的子集都是频繁集。如果不是则对其i ，1 个( | j1 1 ) 项子集进行计数，如果有频繁 集，则必为最大化频繁集，否则在此对其( i jj 一2 ) 项子集进行计数。 ( 3 ) 混合方式 自底向上方式在生成频繁集的同时，必然会产生许多假候选集，这是由先验 规则是必要条件决定的，项集所有的子集都是频繁的，并不保证项集是频繁的。 在f 文献 4 3 1 ) 0 0 提到采用一种混合白底向上自顶向下的方法，其基本思想是 从单元素开始进行项集聚类( 文献 4 3 】) ，对聚类的元素按照支持度降序排列，然 后用一个或多个元素对其进行扩展，直到产生一个非频繁集，这采用自顶向下方 法。在自底向上阶段，剩下的元素和第一个集合连接生成所有的附加的频繁集。 这种方法基于这样的直觉：支持度越大的项集越可能是一个更大的项集的一部 分。 2 1 3 2 动态哈希裁剪( d h p ) d h p 算法和a p r i o r i 算法略有不同，它们的区别主要在于( 文献 2 ，1 1 ，4 0 ，5 0 d ： ( i ) d h p 算法在每次扫描事务集d 之前，使用一个哈希表筛选c k 。由于在初 期减少了候选集的数量，例如c z 的规模f 乒i ，筛选c ：，会折陕形成l ：的效率， 从而提高了算法的执行效率。 ( 2 ) 在扫描事务集d 的过程中，同时对d 进行修剪，减少事务集d 的事务数 量。 2 ，1 3 3 动态项集计数( d i c ) 在一般的关联规则挖掘算法中，项集计数和候选生成是相互独立和分离的， 动态项集计数就是使二者结合，减少二者之间的分离程度。当候选集达到最小支 持度时，即使还没有遍历完整个事务集d ，d i c 开始工作，由其生成附加的候选 集。具体的技术介绍见( 文献 5 5 9 ，其主要思想是在同一次事务集遍历中，对k 值不同的候选k 一项集计数。d i c 将事务集d 分成n 个大小相等的几段d ；进行搜 索a 首先搜索d 1 ，计算1 一项集的支持度，所得本地1 频繁集用来产生2 项集的 候选集。然后搜索d 2 ，获取1 项集和候选2 项目集，即当前所有的候选项集， 计算它们的支持度，所得2 一频繁集用于产生3 频繁集的候选集。重复这一过程， 直到d 。完成。在对事务集的第一次搜索中，当搜索到仇时，d i c 就开始计算候 1 0 条件独立陆在关联规则挖掘中的研究和应用 第二章相关理论及技术基础 选k 一项集的支持数。所有分块都处理完之后，开始第二次搜索。当算法回到d t 进行搜索时，就能得出k 项集的全局支持度。每一次搜索完成后，开始新的一次， 直到当前d 。没有新的候选集产生，且所有的候选集都已经计算完成，d i c 终止。 2 1 3 4 分区方法 分区方法( 文献 1 5 ) 就是将事务集划分为若7 = d , n g - 集，使小事务集的大小 能够装入主存，这样就避免不断的在主存和磁盘之间交换数据，这样在各小事务 集上发现相应的频繁集，将各小事务集上的局部频繁集在事务全集上检查是否是 全局频繁集，如果是就是频繁集。分区的方法非常适合和并行方法结合，进行并 行关联规则挖掘。 2 1 3 5t i d 方法 在项集计数方法中，生成k - - 频繁集需要遍历k 次事务集，这也是算法性能 上的一个重要瓶颈。t i d 方法只需要遍历一次事务集，但是其需要从单项集开始 存储支持事务集的事务t i d 。对二项候选集的支持度计算，只需将二者的t i e ) 集 进行交运算，然后计算结果集合的元素个数，即得支持度( 文献【5 0 ) 。 2 1 3 6 模式分解方法 自从a p r i o r i 算法f 文献 5 0 9 1 9 9 4 年问世以来，大家提出了很多方法来提高 算法的性能，但是基本上都是采用候选集生成和测试方法，有些算法不生成所有 的频繁集，使其不能产生所有的关联规则。q i n h u az o u 等人提出模式分解方法( 文 献1 4 7 1 ) ，在每一次扫描事务集时显著减小事务集的大小，使其能对大事务集更有 效地发现所有的频繁模式，并且避免了非常昂贵的候选集生成过程，减少事务集 大小也为算法节省了时间开销。 在模式分解方法中，利用发现频繁集的同时筛选掉的非频繁集l k 将事务 中的长模式规约为仅包含k 一频繁集的短模式，从而消除了在形成l 针l 时生成候 选集的需要，只要在d k 中简单对所有k + 1 项集进行计数即获得支持度，产生k + l 频繁集l k + l 和k + l 非频繁集l h l 。在图2 2 中给出了对事务集d 进行模式分解 的实例。 2 1 4 7 垂直挖掘方法 垂直挖掘方法( 文献 6 ，2 3 ，4 4 ) 的优点是通过事务t i d 集的交操作实现快速频 率计数和自动的不相关数据的裁剪，缺点是垂直挖掘的中间t i d 集太大( 相对 河海大学硕士学位论文 条件独立性在关联规则挖掘中的研究和应用 d 1 d ，d 1 i d 4 l ：a bcde 1 f 1 ：a bcde ：1 1 ：a b e d ，b c d e ：1_ l ：bcde ：2 2 ：abcg ：1 2 ：abc ：22 ：abc ：2 3 ：abdh ：l g 3 ：a bd ：13 ：a bd ：1 1 r 4 ：bcdek ：l 4 ：bcde ：l4 ：bcde ：1d ；= o 5 ：a bc ：l i s l i ：l 【 l l l ：i t s 3 翁罐 a b 4 a e ) 1 l l l a e 3 l 3一l 3 1 s o c cl 蘸q c 露 a d 2 l 黔。l o 雠 # 臻濑辨蕊! f a 4 d1 b e 4 a b e t 3 a c d 1 b 5f g ) 1 b d 3 a b d 2 c ) 4f h 1 b e 2 b e d 2 d ) 3 k ) 1 c d 2 b e e 2 l 4 卜l 4 e l3 e e 2 b d e 2 i gi 鬻陋弑 d e ，2 c d e 2 b c d e 2 l 图2 2 模式分解实例 大小而言) ，影响算法的可放缩性。z a k i 等人提出一种新方法，只跟踪候选模式 和生成的频繁模式的相异之处，称之为d i f f s e t s ( 文献 4 4 ) ，从而戏剧性地降低了 存放中间结果所需内存大小。 a p r i o r i 系列的算法在稀疏事务集上能够获得较好的性能，比如购物篮数据， 挖掘的频繁集也是比较小的( 项数较少) ，对于密度较大的事务集如电信数据和 普查数据等而言，就会产生很多的大频繁集( 项数很多) ，是算法的性能大幅度 降低，并且由于产生关联规则的复杂度也是和频繁集的项数成指数关系，所以大 频繁集产生关联规则的复杂性也急剧提高。 2 1 4 8 并行方法 关联规则挖掘的问题描述虽然简单，但它的计算量是很大的。假设项集i 含 m 个项目，就有2 “个子集可能是频繁子集，可以证明要找出某一频繁集是一个 n p 问题。当m 较大时，要穷尽搜索每一个子集几乎是不可能的，另一方面，处 理数据库中存储的大量记录要求繁重的磁盘i o 操作。因此，随着数据库规模的 不断增大，数据属性向高维发展，传统的顺序挖掘算法很难适应大规模、可扩展 ( s c a l a b i l i t y ) 的挖掘需要，发展高性能的并行算法是解决这一问题的关键。 a g r a w a l 和s h a f e r 等人提出了三种基于a p r i o r i 的并行算法：c o u n t d i s t r i b u t i o n 算法，d a t ad i s t r i b u t i o n 算法和c a n d i d a t ed i s t r i b u t e 算法。这些算法 1 2 条件独立性在关联规则挖掘中的研究和应用 第二章相关理论及技术基础 的前提是处理器有专用内存和磁盘，而结构上没有任何共享。处理器用通信网络 连接，靠传递消息进行通信。数据平均分配到每个处理器的专用磁盘上。基于 d h p 的思想，p a r k 等人提出了p d m 算法，由并行生成候选项目集和并行确定大 项集两部分构成。p d m 算法有些局限性：首先，为构成完整的候选项目集各 节点都要进行广播通信，通信的开销可能会抵消掉并行生成候选项目集的优势。 其次，和d i - i - p 一样，p d m 对非大项集的项目和事务的物理剪枝要涉及大量磁盘 i o 操作。还有很多其他的并行关联规则挖掘算法，这里就不一一介绍。 这些挖掘关联规则的并行算法，基本方法都是进行数据库分配，使并行系统 中每一个处理器分配到数据库的一个子集，让处理器独立地在这个子集上进行计 算。所有并行算法都要求一定量的通信来协调各独立的处理器。 2 i 3 9 小结 这些技术的使用都有一定约束的，都有其使用的特定要求。其中动态哈希裁 剪、动态项集计数以及模式分解都是对频繁集的产生进行优化，使形成各阶频繁 集的同时，降低数据集的大小及数据集中记录的大小。t d 方法的使用可以减少 对数据集的访问次数，但是需要大量的空间来存放事务t i d 集合。垂直关联规 则挖掘主要适用于稠密数据集，例如普查数据、电信数据等稠密事务集。分区方 法主要针对大型事务集，往往和并行关联规则方法结合使用，在多处理机环境中 进行关联规则挖掘。 2 1 4 其它裁剪方法 除了用支持度可信度框架来裁剪频繁集，过滤弱关联规则之外，还有其 它方法来进行关联规则的裁剪。 2 1 4 1 兴趣度 定义2 8 ：规则的兴趣度 规则的兴趣度是在基于统计独立性下真正的强度和期望的强度之比f 文献 【9 ) 。文中介绍了b r i n 等应用差异思想发现关联规则r ：雪jh 的兴趣度定义为： i n t e r e s t ( r ) = ( c r - s r h ) m a x ( c r ，西们 其中c r 为规则r 的可信度，s r h 为原始记录中支持规则右部h 的比例， s r h = 1 日l 俐。i n t e r e s t ( r ) 可能大于0 ，也可能小于0 ，m a x ( c r ，s r h ) 为标准化 因子，确保i n t e r e s t ( r ) 值范围在 一1 ，+ 1 】之间( 文献 9 ，5 3 】) 。 1 3 河海大学硕士学位论文 条件独立性在关联规则挖掘中的研究和应用 根据定义2 8 ，当规则的兴趣度越大于0 ，说明可信度c r 越大，当兴趣度充 分接近于+ 1 时，表示不管关联规则后件的支持度的大小，可信度都很多，这条 规则很可信：反之，兴趣度越小于0 ，说明这条规则的负规则兴趣度越大，负规 则的可信度c r 越大，当兴趣度充分接近于一1 时，说明关联规则的可信度可以 忽略，关联规则后件几乎是必然发生的。 2 1 4 2 最大频繁集、闭频繁集 这两个概念在2 1 2 2 小节中已经介绍过了，所有的闭频繁集和最大频繁集 都是频繁集，所以是频繁集的压缩版本。由于闭频繁集和最大频繁集的个数相对 于频繁集而言数量少多了，使生成的关联规则也比较少。 ( 1 ) 最大频繁集 一个项集i 是最大频繁集，当且仅当( 文献 1 3 ，1 4 ) ： i 是频繁的； i 的真超集都是非频繁的。 从定义和图2 1 可知，每一个频繁集都至少是一个虽大频繁集的子集。因此 可以从所有的频繁集中进行过滤出最大频繁集。最简单的方法就是根据定义( 文 献 1 3 ，1 4 ) ： f o r 石f d o i f 现f ：工c 五t h e n f ：频繁集的集合 f = f 一 采用这种方法既需要发现所有的频繁集，又需要遍历所有的频繁集，筛选掉有真 超频繁集的频繁集，剩下的就是最大频繁集。 前面介绍的自顶向下方法就可以发现最大频繁集。从最大项集i 开始，看i 是否是频繁集，如是则i 是最大频繁集，否则向下遍历其下一层所有的子集，如 果是频繁的，则一定是最大频繁集，其子集就不要再下钻判断，否则再对下一层 重复这个步骤。 ( 2 ) 闭频繁集 闭频繁集是在所有频繁集中具有闭属性的频繁集，所以在所有频繁集中进行 闭属性的过滤就可以得到闭频繁集。由2 1 _ 2 2 小节闭属性定义， c j ： t i d u ) = t i d ( o = s u p p ( j ) s u p p ( i ) 所以发现闭频繁集就是在所有的频繁集中，对任意频繁集i ，判别其真超集j 的支持度是否小于i 的支持度( 文献 1 3 ，1 4 】) 。 1 4 条件独证性在关联规则挖掘中的研究和应用 第二章相关理论及技术基础 f r e q u e n t c l o s e di t e m s e