（计算机应用技术专业论文）极大布尔关联规则生成算法的研究.pdf

河南大学研究生硕士学位论文第1 页 摘要 数据挖掘( d a t am i n i n g ) 是指从大量结构化和非结构化的数据中提取有用的 信息和知识的过程，数据挖掘的研究已经取得了重大的进展，而且被应用到众多 的领域。关联规则是数据挖掘研究中一个重要的研究课题，它主要用于发现隐藏 在大型数据集中的令人感兴趣的联系。 本文首先介绍了数据挖掘的发展概况和应用前景，然后通过研究关联规则的 挖掘现状发现，大部分关联规则挖掘的研究重点都放在如何提高挖掘频繁项集或 生成关联规则的算法效率上。在实践中，由频繁项集生成的关联规则可能有很多， 这将导致用户无法高效地从关联规则中提取有用的信息。本文重点研究了如何在 不丢失关联规则信息的基础上减少关联规则的生成数量，主要工作包括以下几个 方面： 1 通过研究发现以往的关联规则挖掘算法如g r s e t 算法往往会产生“规则爆 炸”的问题，由某个频繁项集生成的关联规则的数量可以在不丢失任何规则信息的 情况下被减少。在综合借鉴前人研究成果的基础上本文提出的g l m b r 算法深度 优先生成了任一个频繁项集所对应的局部极大布尔关联规则l m b r ，然后分别在 理论和实验两个方面对比分析了用g r s e t 算法和g l m b r 算法生成的同一个频繁 项集对应的关联规则集，通过实验验证了g l m b r 算法的有效性； 2 通过深入研究频繁闭项集、频繁基项集和极大布尔关联规则的性质以及它 们之间的联系，提出了基于以上两种特殊项集的极大布尔关联规则的挖掘算法， 从理论上进行了论证，用实例进行了验证。 关键词：局部极大布尔关联规则；g l m b r 算法；频繁闭项集；频繁基项集；极大 布尔关联规则 a b s t r a c t 1 ，竺掣n g w h 油i st h e p r o c e s s 。f e x 仃a c t j n gt h eu s e f h 】j n f o 肿a t i o na n d 竺? ：k 咄e ? ? m e s t r u c t u r e d a n du n s t m c t u r e dd a t a sh a sg e t t h em a j 。rp r o g r e s sa n ： ! ：竺弩印p ! e d i nm a n y 托i d s a s s 0 c i a n o n n l j ei s 。n e 。ft h ei m p 。r t a n t 二s e 二ha r e ：。：i ： 竺m 1 州n g n s 9 0 a 1 话t 0 d i s c o v e rp r e v i o u s i yu n k n o w n m r e s t i n g r e i a t i o n s 舶m i ： a a t a b a s e s 。 。h r s ：擘掣sp a p e r b m f l y i n t r 。d u c e s t h ed e v e l 叩m e n ta 1 1 dt h ep r o s p e c t so f t h ed a t a 竺1 _ g 冀? 。v e r e a t m a n yr e a s e a r c h e r s 哦nf o c u s 。nh 。wt 。i m p r o v e t h e ：衔c l e n 掣1 h e “9 0 r 油m s 0 f m i n i n g 觎q u e n t i t e m s e t o rt h e 绷c i a t i o nr u l e s ：a c m a l l 二 竺二0 f 出ea ：；s o d a t 伽川e s m a yb eg e 力e r a t e d 疔o m t h e 疗e q u e n ti t e m s e t ，a n dt h j ： ：b l e ：? a y 1 e t h e u s e r sd i d n ，te x 们c tt h eu s e 如ii n f o 啪a t i o n 舶m t h ea s s 。c i a t i 。n 竺要d 明 时n 拇p a p e r f o c u so nh 。wt 0r e d u c et h eq u a n t 时。f t h ea s s o c j ：1 ： w l t h o u t1 0 5 ei n f o 册a t i o n o f a s s o c i a t i o nm i e s n em a i nr e a s e a r c hi sa sf o l l o w s ： 。 。ll ，j 1 1 e 芈o n t h m s s u c ha sg r s e tw h i c hg e n e r a t e t h ea s s o c j a t j o n 1 1 j l e sa r e t h 。r 0 ：】曹1 y s t u d i e da 1 1 d t h e ym a yl e a dt 。t h e “r u l e s e x p i 。s i 。n ”n eq u a n t i 移。ft h e ? ；0 c l a t j ：) n m l e sw h i c h a r e g e t 行。m 仔e q u e n ti t e m s e tm a yb er e d u c e d ，锄d t h e ：n t 。? a n ? 。o f t h ea s s o d a t i o nm l e sw i l ln o t b ei 。s t w r ep r e s e n tt h eg l m b r a l g 。r i b a s e d ! | nt h e ? s e a r c h 0 f 幽ep r e d e c e s s o ra n dt h j sa 培o r i t h mu s et h e d 印t b f i r s t 二e t h 。d 曼n = ：m e 1 0 c a lm a x i m a lb o o l e a na s s o c i a t i o n r u l e 、袖i c hc 。r r e s p 。n d i n gt 0 仔q u e n t ：o s e ! n e m s 专。a n d 能q u e n t k e yj t e m s e t w 色a n a i y z e d t b er e s u l t 。ft 1 1 e g l 聂b r 竺n mm 卸叭hg r 距t a i g 硎岫w h i c h g e n e r a t ea s s 。c a ：t i o nm i es e t 。ft h es 踟e 票 ：竺1 竺m 5 7 她町a n d e x p r j m e n t w h i c ha r eu s e dt 0p r 0 0 f t h ev a j i d i t ) ，。f t h e g l m b r a i g o r i t h m 。1 “ fl w ep r e s e n t aa l g 硎m mo fg e n e 刚n gt h em b r w h i c hb a s e d h e 肌q u e n t 叭：竺n e m s e ：a n d 舶q u e n tk e y “e m s e t 疆e rw ed i s c 。v e r e dt h ep r o p e r t i e s 。ft h e lf c i a n d ? i ? u e m e y “e m s e t ，a n d t h ei m p 。r t 锄tr e l a t i 。nb e 铆e e nt h e m a ) ( i m a lb 。0 1 e a n ：s 0 c l a t i 。：l m l e sa n d t w 0 s p e c i a “t e m s e t s f i n a l l y ，w e p r 0 0 f t h ea 1 9 0 r i t h m ，sv a i i d i t yi n 河南大学研究生硕士学位论文第1 l i 页 k e y w o r d ：l o c a lm a x i m a lb o o l e a na s s i a t i o nn l l e s ；g l m b r ；f i e q u e n tc l o s e di t e m s e t ； f 啊u e n tk e yi t e m s e t ；m a ) ( i i n a lb 0 0 1 e a na s s o c i a t i o n gm l e s 关于学位论文独立完成和内容创新的声明 了蜊蝴= 瑟蜊j 袋一 学位申请嫩麓学位论走盼者弧鍪名：二：翌o ：! 磁一 菇鬻崩瓤黧镳荔多。箩 学位获得者( 学位论文作者) 塞名： 多垂 2 0 堙年月o 曰 学住论文指导教师签名：z 墨当墨亟 2 0 昭年月d 日 河南大学研究生硕士学位论文第1 页 1 。1 数据挖掘概述 第1 章绪论 1 9 8 9 年在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论会上首 次提出了数据挖掘的概念，数据挖掘是一门新兴的、来自不同领域的交叉性学科， 涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、高 性能计算、专家系统等多个领域【l 圳。 目前，国际国内有大批学者对关联规则进行研究。数据挖掘是在大型数据存 储库中自动地发现有用信息的过程，数据挖掘还具有预测未来观测结果的能力， 例如，预测一位新的顾客是否会在一家百货公司消费1 0 0 美元以上【5 j 。数据挖掘是 一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖 掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是 数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和 工程技术人员投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 1 1 1 数据挖掘的起源和涵义 近年来，数据库技术的飞速发展和数据库管理系统的广泛应用使得各种组织 机构存储了海量的数据，但是“数据丰富，信息贫乏”是一个不容忽视的现实问题。 如果没有一个有力的工具，人们很难理解这些数据并从中得到有价值的信息。另 外，计算机硬件稳定的、令人吃惊的进步导致了功能强大的计算机、数据收集设 备和存储介质的大量供应，这些技术大大推动了数据库和信息产业的发展，使得 大量数据库和信息存储用于商品管理、信息检索和数据分析。 在这些海量数据中蕴藏着丰富的有价值的信息。通常由于数据量太大，无法 使用传统的数据分析工具和技术处理它们。有时，即使数据集相对较小，由于数 据本身的非传统特点，也不能使用传统的方法处理。在另外一些情况下，需要回 答的问题不能使用已有的数据分析技术来解决。这样就需要开发新的技术和工具 对海量数据进行分析并从中提取有用的信息。数据挖掘就是这样一种技术，它将 第2 页河南大学研究生硕士学位论文 传统的数据分析方法与处理大量数据的复杂算法相结合。 许多人把数据挖掘看做另一个常用术语数据库中的知识发现( 1 支持度计数的商，一般也可记为p ( 果酱i 面 包) 。若该数据库中事务总数为5 ，项集 面包，果酱) 的支持度计数为2 ，则该规则 的支持度为2 5 = 0 4 ，若共有3 个事务包含面包，则规则的置信度为2 乃= o 6 7 。其 直观意义为：在所有的顾客中有4 0 的顾客同时购买了面包和果酱，而在购买面 包的顾客中有6 7 的顾客也同时购买了果酱。支持度4 0 反映了规则的重要性， 置信度6 7 反映了规则的准确度。 2 2 2 支持度一置信度框架的局限性 现有的关联规则的挖掘算法依赖于支持度和置信度来除去没有意义的模式。 支持度的缺点在于许多潜在的有意义的模式由于包含支持度小的项而被删去。选 择合适的支持度阈值挖掘这样的数据集可能相当棘手。如果阈值太高，则可能遗 漏较低支持度项的有趣模式。在购物篮数据分析中，这种低支持度的项可能对应 那些顾客很少买的昂贵商品( 如珠宝) ，但是它们的模式仍然是零售商十分感兴趣 的。相反，如果支持度阂值太低，挖掘关联模式变得非常困难：首先，由于支持 度阈值太低，已有的关联分析算法所需的计算量和内存需求都将显著增加；其次， 由于支持度阈值太低，提取出的关联模式的数量大幅度增加；第三，可能会提取 出大量的高频率项与低频率项相关联的虚假模式。而置信度的缺陷在于该度量忽 略了规则后件中项集的支持度。 2 2 3 期望置信度 设事务集中有s 的的事务支持物品集 果酱) ，s 称为关联规则 “面包j 果酱”的期望置信度。期望置信度( e x p e c t e dc o n f i d e n c e ) 描述了在没有 任何条件影响下，规则的后件集在所有事务中出现的概率有多大。如果某天共有 1 0 0 0 个顾客到商场购买物品，即共有1 0 0 0 个事务，其中有2 0 0 个顾客购买果酱， 第1 8 页河南大学研究生硕士学位论文 则上述关联规则“面包j 果酱 的期望置信度就是2 0 。 2 2 4 提升度 解决置信度度量缺陷的一种方法是使用称作提升度( l i r ) 的度量，它是置信度 和规则后件中项集的支持度( 即期望置信度) 的比率。提升度描述项集 面包) 的 出现对项集 果酱) 的出现有多大的影响。因为项集 果酱 在所有事务中出现的概 率是期望置信度；而项集 果酱 在有项集 面包 出现的事务中出现的概率是置信 度，通过置信度对期望置信度的比值反映了在加入“项集 面包) 出现”的这个条件 后，项集f 果酱 的出现概率发生了多大的变化。在上例中提升度就是6 7 2 0 = 3 3 。 2 2 5 兴趣度 为了修剪一些无趣的规则，避免生成假的关联规则，引入兴趣度( i n t e r e s t i n g ) 这个度量值。一般一条规则的兴趣度是在基于统计独立性假设下真j f 的强度与期 望的强度之比，然而在许多应用中己发现，只要人们仍把支持度作为最初的频繁 项集产生的主要决定因素，那么，要么把支持度设得足够低以使得不丢失任何有 趣的规则，或者就可能存在一些重要规则丢失的风险；对前一种情况计算效率是 个问题，而后一种则可能丢失信息。 s r i k a i l te ta l ( 1 9 9 5 ) 最初提出兴趣度概念的定义，( r i n t e r e s t i n g ) ，s r i k a n te t a l ( 1 9 9 6 ) 作了进一步的改进。b r i ne ta l ( 1 9 9 6 ) 把事件依赖性的统计定义扩展到兴趣度 上来，s a v a s e r e ( 1 9 9 8 ) 定义了否定关联规则的兴趣度。k l e m e t t i n e ne ta l ( 1 9 9 4 ) 则提出 模版( t e m p i a t e ) 的概念，用户可以利用它来确定哪些规则是有趣的和哪些规则是 用户不关心的。 兴趣度的值介于一1 和1 之间。如果一条规则的兴趣度越大于o ，说明我们对这 条规则越感兴趣j 而一条规则的兴趣度越小于o ，并非这条规则没有意义，相反我 们对它的反面规则越感兴趣( 即反面规则的实际利用价值越大) 。只有那些兴趣度 位于o 附近的关联规则才是没有价值的规则【5 引。 河南大学研究生硕士学位论文第1 9 页 2 3 关联规则挖掘算法 一般说来，关联规则的挖掘可以看做两步的过程【卅： 第一步，找出所有的频繁项集：根据定义，这些项集的每一个出现的频繁性至少 与预定的最小支持度阈值m s 一样 第二步，由频繁项集产生关联规则：根据定义，这些规则必须满足最小置信度 m c o 同时也可以使用附加的兴趣度度量来发现相关联的项之间的相关联系。由于 第二步的开销远低于第一步，所以挖掘关联规则的总体性能由第一步决定。 2 3 1a p r i o r i 算法 a p r i o 一算法是r a 蓼a w a l 和r s r i k 锄t 于1 9 9 4 年提出的为布尔关联规则挖掘 频繁项集的原创算法。算法使用频繁项集的先验原理，利用一种称作逐层搜索迭 代方法，k 项集用于探索( 1 ( + 1 ) 项集。首先，通过扫描数据库，累积每个项的计数， 并收集满足最小支持度的项，找出频繁1 项集的集合，该集合记为l l ，然后l l 找 频繁2 项集l 2 ，l 2 用于找l 3 ，如此下去，直到不能再找到频繁k 项集。 a 研o r i 算法和它相关过程的伪代码如下： 算法：a 州o r i 使用根据候选生成的逐层迭代找出频繁项集 输入：事务数据库d ；最小支持度阈值m s 输出：d 中的频繁项集三 ( 1 ) 三1 2 f i n d 一觚q u e n t _ 1 - i t e m s e t s ( d ) ； ( 2 ) f 1 0 r ( j 砭：2 2 ；三七1 g ；k + + ) ( 3 )q2 a p r i 耐萨n 舡l ，朋瞳j 印) ； ( 4 ) 矗订e a c h 住狮s a c t i o nf d s c a nd f o rc o u n t s ( 5 ) c f - s u b s e t ( g ，f ) ；g e tt h es u b s e t so f ft h a ta r ec 锄d i d a t e s ( 6 ) f 0 re a c hc a n d i d a t ec c f ( 7 ) c c o u n t + + ； ( 8 ) ( 9 )三尸 c q k c o u n t 、独s ) ( 1 0 ) 第2 0 页河南大学研究生硕士学位论文 ( 1 1 ) r e t u m 三= u 止t ； p r o c e d u r ea p r i o r i g e n 盘- l ：仃e n q u e n t ( 忌- 1 ) 一i t e m s e t s ；朋f 船j 印) ( 1 ) f o re a c hi t e m s e t ，l i ( 2 ) f 0 re a c hi t e m s e t 如三b l ( 3 )i f 1 = 易【1 】2 】= 如【2 】八八f l 【足- 2 】- ? 2 【七一2 八f j 【j j 一1 】 如【船1 t h e n ( 4 )c = ，l 冈如；j o i ns t e p ：g e n e r a t ec a n d i d a t e s ( 5 )i f h a s j n f j r e q u e n t s u b s e t ( c ，玩1 ) t h e n ( 6 ) d e l e c tc ；p 九】n es t e p ：r e m o v eu n 6 1 】i t 如lc a n d i d a t e ( 7 ) e l s ea d dct oc i 七； ( 8 ) ( 9 ) r e t u mc t ； p r o c e d u r e h a s 骶q u e n t s u b s e t ( c ：c a n d i d a t e 足一i t e m s e t ；“仔e q u e n t ( 缸1 ) - i t e m s e t ) ( 1 ) f o re a c h ( 缸1 ) - s u b s e tso f c ( 2 )i f j 仨如lt h e n ( 3 ) r e t u mt m e ； ( 4 ) r e t u mf a l s e ； 如上所述，函数a p r i o r i _ g e n 用于在频繁项集的基础上产生新的候选项集， 它的基本思想可以由两个步骤来进行描述： ( 1 ) 连接步：为找厶，通过l 中满足条件的不同元素之间的连接产生候选 缸项集的集合，该候选项集的集合记为g 。设，l 和如是如l 中的项集。记号，f 阴表示 厶的第项( 例如，埘娩】表示，l 的倒数第3 项) 。为方便计，假定事务或项集中的 项按字典次序排序。执行连接川冈k l ，其中“i 的元素是可连续的，如果它们 前( 七2 ) 个项相同。即是，纠的元素z l 和如是可连续的，如果 ( ，l 1 】- 如【l 】八“2 】- 如 2 】八八，l 肛2 】= 如 肛2 】八足一l 】= 如 肛l 】) 条件，l 肛l 】 都是极大频繁项集，因为他们的直接超集都是非频繁的。 极大频繁项集形成了可以导出所有频繁项集的最小的项集的集合。对于可能 产生长频繁项集的数据集，极大频繁项集提供了颇有价值的表示，因为这种数据 集中的频繁项集可能有指数多个。尽管极大频繁项集提供了一种紧凑表示，但是 极大频繁项集却不包含它们子集的支持度的信息。因此，这就需要再扫描一遍数 据集，来确定那些非最大的频繁项集的支持度计数，所以在某些情况下，可能期 待得到保持支持度信息的频繁项集的最小表示。 第2 4 页河南大学研究生硕士学位论文 2 4 2 频繁闭项集 图2 2 搜索空间树 定义2 4 2 【6 】闭项集( c l o s e di t e m s e t ) 项集x 是闭的，如果它的直接超集都不具 有和它相同的支持度计数。 换句话说，如果至少存在一个x 的超集，其支持度计数与x 的相同，x 就不 是闭项集。 定义2 4 3 【6 频繁闭项集：一个项集是频繁闭项集，如果它是闭的，并且它的 支持度大于或等于最小支持度阈值。 频繁闭项集是相应的频繁项集的子集，它完全抓住了频繁项集的所有信息， 它是频繁项集的无失真信息的最小集合，任一个频繁项集都可以由频繁闭项集得 到。 例如：假定事务数据库只有两个事务： ， ) ，设最 小支持度m s = 0 5 。我们发现两个频繁闭项集和它们的支持度，即 c = ：l ， ：2 。只有一个极大频繁项集： m = ：l 。与上面相比，那里确定了2 1 0 0 一1 个频繁项集，数量太大， 根本无法枚举! 频繁闭项集的集合包含了频繁项集的完整信息，不是频繁闭项集的频繁项集 的支持度一定等于它的所有超集中有最大支持度的那个频繁项集的支持度。例如， 我们可以从c 推出( 1 ) ：2 ) ，因为 ) 是 ：2 ) 的子集； 河南大学研究生硕士学位论文第2 5 页 ( 2 ) ：1 不是 ：2 ) 的予集，而是 ：l 的子集。 然而，从极大频繁项集我们只能断言两个项集 和 ) 是频繁的， 但是我们不能断言他们的实际支持度计数。 使用频繁闭项集的支持度可以确定那些非闭的频繁项集的支持度。频繁闭项 集可以显著减少频繁项集挖掘所产生的模式数量，而且保持关于频繁项集的完整 信息。所以，在许多的实践中，更希望挖掘频繁闭项集的集合，而不是所有频繁 项集的集合。 从频繁项集的定义出发，挖掘频繁闭项集的一种朴素方法是首先挖掘频繁项 集的完全集，然后删除这样的频繁项集，即每个与现有的频繁项集有相同支持度 的真子集。但是这种方法开销太大，为得到一个长度为1 0 0 的频繁闭项集，在开 始删除冗余项集之前，这种方法首先必须导出2 1 0 0 1 频繁项集，这样开销太大。一 种推荐的方法是直接在挖掘过程种搜索频繁闭项集，这需要在挖掘过程中，一旦 识别闭项集就尽快对搜索空间进行剪枝。 频繁闭项集挖掘过程中的剪枝策略包括： 1 项合并：如果包含频繁项集x 的每个事务都包含项集y ，但不包含y 的任 何真超集，则x u y 形成一个频繁闭项集，并且不必再搜索包含x 但不包含y 的 任何项集。 2 子项集剪枝：如果频繁项集x 是一个已经发现的频繁闭项集y 的真子集， 并且s u p ( x ) = s u p ( ，则x 和x 在集合枚举树中的除y 及y 分支外的所有后代都 不可能是频繁闭项集，因此可以剪枝。 本章小结 本章首先介绍了关联规则的一些基本概念，然后介绍了关联规则的分类、度 量方法以及布尔关联规则集的结构，分析了布尔关联规则、多层关联规则、多维 关联规则和量化关联规则的特点以及挖掘关联规则的经典算法，最后讨论了频繁 项集、极大频繁项集和频繁闭项集的性质以及挖掘的经典算法和剪枝策略。 第2 6 页河南大学研究生硕士学位论文 第3 章频繁项集对应的局部极大布尔关联规则集的生成算法 频繁模式是在数据集中频繁出现的模式，关联规则是从频繁模式中产生的一 种常见的规则，挖掘频繁模式可导致发现数据中有趣的关联和相关。目前，对关 联规则的挖掘一般都是分两步进行：第一步生成频繁项集( 即项集的支持度大于等 于最小支持度) ；第二步由频繁项集导出其相对应且满足最小置信度的关联规则。 由于关联规则挖掘的总体性能由第一步的挖掘效率决定，所以大多数对关联规则 挖掘的研究热点都放在如何对已有的算法的性能进行改进或提出新的算法以便快 速有效地找出所有的频繁项集，有的也致力于找出频繁项集的紧凑表示，即研究 如何挖掘极大频繁项集和频繁闭项集。而只有少部分才涉及到第二步，研究如何 由频繁项集生成关联规则，其研究重点也大都集中在如何提高生成关联规则算法 的效率上。频繁项集所对应的满足最小置信度的关联规则的数量是有可能减少的， 而且那些被省略的关联规则可以对某些关联规则通过将关联规则中的某些后件移 为前件的方法得到，即生成关联规则的数量虽然减少但却没有丢失任何关联规则 的信息。关联规则数量的减少大大提高了用户分析规则结果的效率，也节省了规 则的存储空间。本章我们将重点研究如何在不丢失关联规则信息的基础上减少频 繁项集对应的关联规则的生成数量，提出了生成某个频繁项集所对应的局部极大 布尔关联规则的算法g l m b r ，并通过理论和实验验证了算法的正确性。 3 1 g r s e t 算法分析和局部极大布尔关联规则 3 1 1g r s e t 算法及其产生的“规则爆炸”问题 g r s e t 算法是一个递归算法，它采用的深度优先的方法来生成关联规则的后 件，首先判定一个关联规则后件的头h 所包含项目的个数n 是否小于频繁项集中包 含的项目个数减1 ，即i 是否小于1 。若小于，则将头h 与差集i - h 中的项目相连 接并进行验证。g r s e t 相对于一般的规则挖掘算法来说具有运行时间少的优点。 例：如表3 1 中的数据库，其中m s = 0 5 ，m c = o 8 。 根据给定的m c 和m s ，6 ( c b h e ) = 9 ，所以项集 c b h e ) 是频繁项集，按照g r s e t 河南大学研究生硕士学位论文第2 7 页 算法的思想，由频繁项集 c b h e ) 生成的所有满足最小置信度的关联规则共有l o 条： r _ e j c b h ，c b j h e ，b h j c e ，e c j b h ，曲c h ，e h j c b ，e c b j h ，e c h b ，e b h j c ， c b h j e ) ；o ( f h e 曲= 8 ，所以 m e g 也是频繁项集，由它生成的满足最小置信度的关联 规则有8 条： f e j h g ，龟j h e ，h g f e ，e g j f h ，f e h j g ，f e g j h ，f 曲j e ，h g e j f ) ， 因为数据库中有很多个频繁项集，所以将导致大量的关联规则生成，这将对用户 分析规则制定决策带来很大的困扰。 表3 1 事务项目 1 a b c d e f 曲 2 b c e f 曲 3c d f 4 a b c d e f 曲 5 a b c e f 曲 6 a c d e 曲 7 b c d f 曲 8a b c e f l l 9 a b c d e f 鲈 1 0 c e f 曲 1 l a b d f 1 2 a b d f 1 3 c d g 1 4 a b c d e f j 曲 1 5 b c d e f j 曲 1 6 b c e f h 3 1 2 频繁项集对应的局部极大布尔关联规则 从上例中我们发现，集合r 的子集r = e c j b h ，e b j c h ，e h j c b ，e c b j h ， e c h b ，e b h c ，c b h j e ) 中的每个关联规则都可由r r = c b j h e ，b h j c e ，e j c b h ) 中的某些关联规则按照后件移为前件的方法推导出，这是因为项集的支持度总是 小于等于它的子集的支持度。例如：在关联规则e j c b h 中，若将规则中的后件c 第2 8 页河南大学研究生硕士学位论文 移为前件，则得到关联规则c e b h ，根据先验原理可知a ( c e ) g ( e ) ，根据关联规则 的置信度计算公式可知规则c e j b h 的置信度一定大于等于规则e j c b h 的置信度， 即它一定是满足最小置信度的；同样若将关联规则e j c b h 的后件c 、h 移为前件， 则可得到新的关联规则c h e j b ，它同样也满足最小置信度。 但是集合r r = c b j h e ，b h j c e ，e j c b h ) 中的任何一个关联规则都不能 再被简化掉，因为只要去除集合r r 中的任何一个关联规则，将导致由频繁项集 c b h e 生成的某些关联规则的相关信息被丢失掉。 例：若将r r = c b j h e ，b h j c e ，e j c b h ) 中的规则e j c b h 去除，那么我 们只能从剩余的规则 c b j h e ，b h j c e 中得到如下的规则 e c b j h ，e b h j c ， c b h j e ，相对于集合r 来说丢失了规则 e c j b h ，e b j c h ，e h j c b ，e c h j b 的信 息。集合r r = c b j h e ，b h j c e ，e c b h ) 中的任何一条规则都不能再被删除， 本章我们将这样的某个频繁项集所对应的不能再被简化的关联规则称为频繁项集 对应的局部极大布尔关联规则l m b r 。上例集合r r = c b j h e ，b h j c e ，e j c b h 中的关联规则就是频繁项集 c b h e 对应的局部极大布尔关联规则。 3 2g l m b r 算法 3 2 1 相关概念和定理 定义3 2 1 集合枚举树是一种层次型的树结构，它的根节点为空集合，称为 第0 层。树中第k 层包含所有可能的k 项集。图3 i 是项目集i = c b h e 的集合枚举 树的例子，根节点( 第o 层) 为空集合g ，第1 层包含所有的1 项集 c 、 b 、 h 、 e ，第2 层包含所有的2 项集，每个可能的项集都出现在集合枚举树中，所 以这种树结构可以将项集的所有搜索空间完全枚举出来。 性质3 2 1 若关联规则c ( 1 c ) 满足m c ，那么所有以包含c 的且是l 的了集的 项目集为前件的关联规则也一定满足m c 。 证明：设c 是d 的真了集，且d 是l 的子集，若c j ( 1 c ) 成立，则关联规则d j ( 1 d ) 一定成立。 因为c ( 1 c ) 成立，所以s u p ( 1 ) s u p ( c ) 一定大于等于m c ，又因为c 是d 的真 子集，s u p ( c ) s u p ( d ) ，可知s u p ( 1 ) s u p ( d ) 也一定大于等于m c ，所以关联规则d j ( 1 d ) 一定成立。 河南大学研究生硕士学位论文第2 9 页 由性质3 2 1 可知，给定一个频繁项集l ，若其某一个真予集c 作为前件可以 使关联规则c j ( 1 c ) 成立，那么所有包含c 且又是l 的子集的项目集d 一定可以作 为前件使关联规则d = ( 1 d ) 成立。 由上述性质我们可知某个关联规则在满足最小置信度的情况下，若将规则中 的某些后件移为前件，那么形成的新的关联规则也一定满足最小置信度。 o ) 歹外_ c ) b ) h ) e ) 7 卜 c b c h ) c e b h b e ) h e ) 卜i c b h ) c b e ) c h e ) b h e ) l c b h e ) 3 2 2g l 船r 算法基本思想 图3 1 集合枚举树 g l m b r 算法基于性质3 2 1 对需搜索的频繁项集的集合枚举树进行剪枝( 即 若以某个项集做前件生成的关联规则满足最小置信度，则就不再深度优先搜索此 项集的超集) ，递归地生成某个频繁项集所对应的局部极大布尔关联规则l m b r 。 算法中初始化一个集合m f s 用来暂时存放l m b r 对应的前件，其中l 表示项集h 包含的项目数，h 【i 】表示h 的最后一个项目，p ( 1 ，h 训h m 表示l 中项目h 川h m 在l 中 的位置， i i m f s | | 表示集合m f s 包含的元素的个数。频繁项集 c b h e ) 的集合枚举树 如图3 1 所示。 算法lg l m b r 输入：频繁项集1 输出：由l 生成的局部极大布尔关联规则l m b r 。 方法： ( 1 ) m = ； ( 2 )m f s = g ： 河南大学研究生硕士学位论文 l m b r = o ： g e t l m b r ( 八，1 ) ； p r o c e d u r eg e t l m b r ( h ，s ) 参数：h ：l 的予串，以h 为前件的关联规则满足m c 。 s ：l 中待连接项目的起始位置，p ( 1 ，h 【】) + l s m ( 1 ) n = | ； ( 2 ) i f n 1 1 2 5 6 ( c b ) 2 1 0 1 1 2 5 g ( c h e ) 5 1 1 2 c b ，c h e ) o ( c e ) = 1 1 1 1 2 5 o ( b h ) = 1 0 l1 2 5m f s = m f su b h ) = c b ，c e ，b h o ( b e ) 2 9 1 1 2 5 g ( h e ) = 1 1 b ，e b h = = c ， e c b = h ，e c h = b ， c b h = e e b h = c ，c b h = e f h e g ) 8 条：4 条： 4 条： f e j h g ，绝j h e ， f e j h g ，f e h j g ，f e g j h ， h g j f e ，e g j f h ，龟j h e ，f i 珈e ，h g e f f e h j g ，f e g j h ，h g j f e ， f i 珈e ，h g e j fe g f h b c e 4 条：2 条：2 条： e = ，b c ，b c = ，e ， e = ，b c b c = e b e = c ，e c = b b e = c ，e c = ，b 河南大学研究生硕士学位论文第3 5 页 第4 章极大布尔关联规则的生成算法 通过对关联规则的覆盖运算的定义分析可知，覆盖运算中包含关联规则中的 某些后件被移丢的情况。g l m b r 算法尽管减少了关联规则的生成数量，但是由于 它没考虑存在后件移为前件时有部分后件被移丢失的情况，所以g l m b r 生成的 所有的频繁项集对应的l m b r 的并集并不是极大布尔关联规则集【4 ”。极大布尔关 联规则就是那些不可能由任何一个满足最小置信度的关联规则通过覆盖运算得到 的规则。若将数据库中的所有的项目集构成一个分层偏序集，那么满足最小置信 度的关联规则构成了该分层偏序集的一个下集，极大布尔关联规则就是这个下集 的极大元。 频繁闭项集是支持度比它的任何超集的支持度都大的频繁项集，频繁基项集 是支持度比它的任何非空真子集的支持度都小的频繁项集，它们与极大布尔关联 规则有着很重要的联系，本章在总结出有关此联系的性质的基础上提出了一种基 于频繁闭项集和频繁基项集的挖掘极大布尔关联规则的有效算法，并初步在理论 上验证了算法的正确性。 4 1 由覆盖运算进一步分析g l m b r 算法 定义4 1 1 【4 6 】关联规则x j y 的个覆盖运算c 为： c ( x = = y ) 2 x u z = ，vj z ，v s y z n v = o ，v o ) 。 即在c ( x j 中每个规则由规则x j y 的一个项目子集组成，通过对x j y 进 行覆盖运算得到的任何规则r 的前件包含x 和y 的子集，而r 的后件是一个y 的 非空子集。 性质4 1 1 【4 6 】若r 是一个关联规则，具有支持度s 和置信度c ，则覆盖c ( r ) 中每 个规则r 的支持度和置信度分别不小于s 和c 。 由以上定义和性质可以得知，已知规则x j y 成立，将此规则的后件y 中的 某个项目z 移位得到新的关联规则共有两种方法，一种方法是将x u z 作为新规则 的前件，同时将y - z 作为新规则的后件，得到同样满足最小置信度的新的关联规 则x u z j y - z ；另一种方法是z 在移动的过程中丢失z 的真子集v ，其中v 可以 第3 6 页河南大学研究生硕士学位论文 为空，得到的关联规则x u ( z v ) j y - z 同样满足最小置信度。 以第3 章的表3 1 、3 2 为例，g l m b r 算法挖掘出的频繁项集 c b h e 对应的 局部极大布尔关联规则为： c b j h e ，b h j c e ，e j c b h ) ，我们知道这3 个规则还 蕴涵了其它7 个前件并后件为项集 c b h e ) 的关联规则： e c j b h ，e b j c h ，e h j c b ， e c b j h ，e c h j b ，e b h j c ，c b h j e ，。根据先验原理可知，频繁项集的予集也是频 繁项集，所以项集 b c e 也是频繁项集，其支持度计数为9 ，频繁项集 b c e 对应 的局部极大布尔关联规则为：fe c b ，c b e ，这2 条规则也蕴涵了2 条前件并 后件为频繁项集 b c e ) 的关联规则 b e c ，e c j b 。若将按g l m b r