（计算机软件与理论专业论文）关联规则的精简方法研究.pdf

关联规则的精简方法研究 摘要 数据挖掘是指从大量数据中提取或“挖掘”知识。关联规则是数据 挖掘当前研究的主要模式之一，用于确定数据集中不同域或属性之间的 联系，找出有价值的多个域之间的依赖关系。发现频繁项集是关联规则 挖掘中最基本、最重要的问题，自从a g r a w a l 的开创性工作以来，有关 研究从未停止过。当支持度阈值较低或数据集中存在长模式时，频繁项 集挖掘可能产生大量频繁模式集，这将给人们的理解和从中发现有趣的 模式造成一定的困难。为压缩庞大的频繁模式集，压缩的频繁项集挖掘 是最近研究的一个热点问题，其中包括最大频繁项集挖掘和频繁闭项集 挖掘。 现有最大频繁项集挖掘算法，大多需要维护大量侯选项集并进行超 集检测。当已有最大频繁项集数目较大时，超集检测将成为算法的瓶颈。 本文首先提出了一种基于标记域f p t r e e 的快速挖掘最大频繁项集算法 b f - d m f i ，该算法为f p t r e e 中每个节点增加一个标记域，利用该域对节 点进行有效的标记，从而减少了最大侯选频繁项集的数量，节约了超集 检测时间，在一定程度上提高了算法的性能。 按照搜索空问树的遍历策略，最大频繁项集挖掘算法分为宽度优先 算法和深度优先算法。宽度优先算法大多需要维护大量候选项集并多次 重复扫描数据库或搜索f p - t r e e ；而深度优先算法则需要递归构造频繁 项的条件模式树并进行相应挖掘，这将加大算法的执行时间和所占用的 内存空间。提出了一种基于f p t r e e 的非递归深度优先挖掘算法 d f - d m f i 。该算法通过构造每个频繁节点的频繁子孙集和频繁前缀，连 接生成最大频繁项集，利用m f i - t r e e 进行超集检测，并对f p t r e e 进 行有效的剪枝，从而保证了算法的执行效率。 现有最大频繁项集和频繁闭项集挖掘算法，大多从事务数据库中直 接挖掘，具有较高的时间和空间复杂度。提出了基于频繁项集的最大频 繁项集( b f i d m f i ) 和频繁闭项集挖掘算法( b f i d c f i ) 。在b f i d m f i 算 法中，通过逐个检测频繁项集在其集合中是否存在超集来判断该项集是 不是最大频繁项集；在b f i d c f i 算法中，通过挖掘所有支持度相等的 频繁项集中的最大频繁项集，组合生成频繁闭项集。利用此方法挖掘最 大频繁项集和频繁闭项集在一定程度上降低了算法的时间和空间复杂 度。 在上述研究的基础上，本文最后设计并实现了一个关联规则挖掘工 具原型。该原型可以挖掘出基于频繁项集、频繁闭项集和最大频繁项集 的关联规则，并可根据用户自定义的规则进行约束挖掘，以进步精简 关联规则结果集。 关键词：数据挖掘，关联规则，频繁项集，最大频繁项集，频繁闭项集 l i r e s e a r c ho nt h em e t h o do fc o n d e n s i n g a s s o c i a t i o nr u l e s a b s t r a c t d a t am i n i n gr e f e r st oe x t r a c t i n go r “m i n i n g k n o w l e d g ef r o ml a r g e a m o u n t so fd a t a a so n eo ft h em a i np a t t e r n si nt h ef i e l do fd a t am i n i n g ， a s s o c i a t i o nr u l e sa r eu s e dt od e t e r m i n et h er e l a t i o n s h i p sa m o n gt h ea t t r i b u t e s o ro b j e c t s ，t of i n do u tv a l u a b l ed e p e n d e n c i e sa m o n gt h ef i e l d s d i s c o v e r yo f f r e q u e n ti t e m s e t si st h em o s tf u n d a m e n t a la n di m p o r t a n tp r o b l e m i nm i n i n g a s s o c i a t i o nr u l e s s i n c et h ep i o n e e r i n gw o r ko fa g r a w a l ，t h e r eh a sb e e na n i n c r e a s eo fr e s e a r c h i n go nt h i sp r o b l e m w h e nt h em i n i m u ms u p p o r ti s l o w e ro rt h e r ea r et o om a n yl o n gp a t t e r n s ，f r e q u e n ti t e m s e t sm i n i n gm a y p r o d u c eal a r g eq u a n t i t yo ff r e q u e n tp a t t e r n s i ti sd i f f i c u l tt ou n d e r s t a n dt h e m e a n i n go ft h e s ep a t t e m sa n dd i s c o v e ri n t e m s t i n gp a t t e r n sf r o mt h e m t o r e d u c et h es e to ff r e q u e n tp a t t e m sg e n e r a t e di nd a t am i n i n g ，r e c e n ts t u d i e s h a v eb e e nw o r k i n go nm i n m gc o m p r e s s e ds e to ff r e q u e n tp a t t e m s ，w h i c h i n c l u d em a x i m a lp a t t e r n sa n dc l o s e dp a t t e r n s m o s to fc u = e n ta l g o r i t h m so f m i n i n gm a x i m u mf r e q u e n ti t e m s e t sn e e d t op r o t e c tl o t so fc o n d i t i o n a li t e m s e t sa n dm a k es u p e r s e tc h e c k i n g w h i l et h e a m o u n to ft h ee x i s t i n gm a x i m u mf r e q u e n ti t e m s e t si st o ol a r g e ，s u p e r s e t c h e c k i n gw i l lb e c o m eb o t t l e n e c ko ft h ea l g o r i t h m i nt h i sp a p e r , an e w i l l a l g o r i t h mb f - d m f i i sp r o p o s e d ，w h i c hm a k e su s eo f a d d i n gam a r ko f e a c h n o d ea n ds i g n i n gt h en o d ee f f i c i e n t l yt or e d u c et h en u m b e ro fm a x i m u m c o n d i t i o n a lf r e q u e n ti t e m s e t sa n dt h ec o s to fs u p e r s e tc h e c k i n g c o m p a r i n g w i t ht h ec u r r e n ta l g o r i t h m s ，t h ep e r f o r m a n c eo ft h i sa l g o r i t h mi si m p r o v e d i ns o m ed e g r e e w i d t h f i r s ta l g o r i t h ma n dd e p t h f i r s ta l g o r i t h ma r et w ok i n d so f a l g o r i t h mf o rm i n i n gm a x i m u mf r e q u e n ti t e m s e t s m o s to ft h ew i d t h - f i r s t a l g o r i t h m sn e e dt op r o t e c tl o t so f c o n d i t i o n a li t e m s e t sa n ds c a nt h ed a t a b a s e o rs e a r c hf p t r e em a n yt i m e s a n dm o s to ft h ed e p t h f i r s ta l g o r i t h m sn e e d t oc o n s t r u c tc o n d i t i o np a t t e r nt r e ea n dm i n em a x i m u mf r e q u e n ti t e m s e t s r e c u r s i v e l y , w h i c hw i l lc o n s u m e sm o r ee x e c u t i o nt i m ea n dm e m o r ys p a c e i nt h i sp a p e r , an e wd e p t h - f i r s ta l g o r i t h mb f - d m f ii sp u tf o r w a r d ，w h i c hi s a l s ob a s e do nf p 。t r e e ，b u tt h er e c u r s i o ni sn o ti n c l u d e d w ec a nm a k eu s eo f c o n s t r u c t i n gf r e q u e n ts o n s e t sa n dp r e q u e n tp r e f i x - s e t s o fe a c hf r e q u e n t n o d ea n dl i n k i n gt o g h e rt og e n e r a t em a x i m u mf r e q u e n ti t e m s e t s m a k i n g u s eo fm f i t r e ew ec a nm a k es u p e r s e tc h e c k i n ga n dp r u n et h ef p t r e e e f f e c t i v e l y , s ot h ef u n c t i o no f t h i sa l g o t i t h mi si m p r o v e d m o s to fc u r r e n ta l g o r i t h m so fm i n i n gm a x i m u m 矗e q u e n ti t e m s e t sa n d f r e q u e n tc l o s e di t e m s e t sh a v eh i g ht i m ea n ds p a c ec o m p l e x i t y , b e c a u s et h e y m i n em a x i m u mf r e q u e n ti t e m s e t sa n df r e q u e n tc l o s e di t e m s e t sf r o m t r a n s a c t i o n a ld a t a b a s e d i r e c t l y i td e s i g n s an e wk i n do fa l g o r i t h m s i v b f i - d m f ia n db f i - d c f ii nt h i sp a p e r w ec a nd e t e r m i n ew h e t h e ra f r e q u e n ti t e m s e t si sm a x i m a lf r e q u e n ti t e m s e t st h r o u g hd e t e c t i n gw h e t h e r e x i t i n gt h e i rs u p e r s e ti t e m s e t si nf r e q u e n ti t e m s e t s a l s ow ec a nm a k eu s i n g o fm i n i n gm a x i m u mf r e q u e n ti t e m s e t sf r o mf r e q u e n ti t e m s e t sw h i c hh a v e e q u a ls u p p o r ti n o r d e rt og e n e r a t ef r e q u e n tc l o s e di t e m s e t s t h e ym a k e b e t t e rp e r f o r m a n c et h a nt h ec u r r e n ta l g o r i t h m s o nt h ef o u n d a t i o no fa b o v e m e n t i o n e dr e s e a r c h ，at o o lm o d e lo f m i n i n ga s s o c i a t i o nr u l e si sd e s i g n e da tt h ee n do ft h i sp a p e r t h et o o lc a n m i n ea s s o c i a t i o nr u l e sb a s e do nf r e q u e n ti t e m s e t s ，c l o s e df r e q u e n ti t e m s e t s a n dm a x i m a lf r e q u e n ti t e m s e t s i no r d e rt oc o n d e n s et h er e s u l ts e to f m i n g i n gr u l e s ，i ta l s oc a nm i n ec o n s r a i n t - b a s e da s s o c i a t i o nr u l e s ，w h i c ha r e d i f i n e db yu s e r s k e yw o r d s ：d a t am i n i n g ，a s s o c i a t i o nr u l e s ，f r e q u e n t i t e m s e t s ， m a x i m a lf r e q u e n ti t e m s e t s ，c l o s e df r e q u e n ti t e m s e v 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已经 发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作 了明确的声明并表示了谢意。 研究生签名：蚤睑日期：五，7 j 夏、j 岁 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影印、缩印或扫 描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方式在不同媒体上发 表、传播论文的全部或部分内容。保密的学位论文在解密后遵守此协议。 研究生签名：姜日含 导师签名：贸碉 日期：矽7 ，哆 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理条 例。我的学位论文中凡引用他人已经发表或未发表的成果、数据、 观点等，均已明确注明并详细列出有关文献的名称、作者、年份、 刊物名称和出版文献的出版机构、出版地和版次等内容。论文中未 注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ：萎i l 含 指 导教师：智力q 1 1 数据挖掘概述 1 1 1 数据挖掘的兴起 第一章绪论 在过去的3 0 年中，计算机硬件技术稳步的、令人吃惊的进步导致了功能强 大且价格可以承受的计算机、数据收集设备和存储介质的大量供应。这些技术大 大推动了数据库和信息产业的发展，使得大量数据库和信息存储库用于事务管 理、信息检索和数据分析；另一方面，激增的数据背后隐藏着许多重要的信息， 人们希望能够对其进行更高层次的分析，以便更好地利用这些数据，然而理解它 们已经远远超出了人的能力。结果，收集在大型数据库中的数据变成了“数据坟 墓”，人们不得不面临“数据丰富，知识匾乏”的尴尬处境【堆】。从海量的数据存 储中抽取模式、我出数据变化的规律和数据之间的相互关系，充分发挥数据的潜 力，以指导决策和科学发现等各项工作成为一种越来越迫切的需求。数据挖掘技 术的产生迎合了人们的需求，自产生以来一直受到信息产业界和整个社会的极大 关注。获取的信息和知识可以广泛应用在信息管理、过程控制、科学研究、决策 支持等领域。 1 9 5 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论 会上首次提出k d d 这个术语【4 l 。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行了 k d d 专题讨论会，这些会议汇集了来自各个领域的研究人员和应用开发者，集 中讨论数据统计、海量数据分析算法、知识表示、知识运用等问题。随着参与人 员的不断增多，k d d 国际会议发展成为年会。1 9 9 8 年在美国纽约举行的第四届 知识发现与数据挖掘国际学术会议不仅进行了学术讨论，而且还有3 0 多家软件 公司展示了他们的数据挖掘软件产品口i 。与国外相比，国内专家学者对数据挖掘 的研究起步稍晚。1 9 9 3 年国家自然科学基金首次对该领域的研究项目予以支持。 目前，国内的许多科研单位和高等院校( 如北京大学、中国人民大学、哈尔滨工 业大学、复旦大学) 竞相开展对数据挖掘的基础理论及其应用研究 6 - - 9 1 。据专家 预测，随着数据量的日益累积和计算机的广泛应用，数据挖掘将在中国形成一个 产业【1 0 1 。 1 1 2 数据挖掘的定义 数据挖掘的概念有广义和狭义之分。目前比较公认的是g p i a t e t s k ys h a p r i o 等人1 提出的广义的数据挖掘概念，其定义如下： 浙江师范大学硕士学位论文 定义1 1 数据挖掘又称数据库中的知识发现，是指从大量数据中发现有效 的、新颖的、具有潜在作用的、能被用户理解的模式的处理过程。 狭义的数据挖掘定义认为，数据挖掘只是数据库中知识发现的一个特定的、 关键的步骤，是指应用特定算法从数据中提取模式。 知识发现过程由以下步骤的迭代序列组成l l 习： ( 1 ) 数据清理( 消除噪声和不一致数据) ( 2 ) 数据集成( 将多种数据源组合在一起) ( 3 ) 数据选择( 从数据库中提取与分析任务相关的数据) ( 4 ) 数据变换( 将数据变换或统一成适合挖掘的形式) ( 5 ) 数据挖掘( 使用智能方法提取数据模式) ( 6 ) 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) ( 7 ) 知识表示( 使用可视化的知识表示技术，向用户提供挖掘的知识) 步骤l 4 是数据预处理的不同形式，为挖掘准备数据。数据挖掘步骤可能与 用户或知识库交互，将有趣的模式提供给用户，或作为新的知识存放在知识库中。 根据这种观点，数据挖掘只是整个知识发现过程的一个步骤。事实上，在现今文 献中的大多数场合，这两个术语的使用是不加区别的，本文也将不加区分地使用 两者。 1 1 3 数据挖掘面临的重要挑战 数据挖掘技术的快速发展，使数据挖掘技术的应用范围也得到了一定程度的 拓展。但是，目前的应用情况与人们的预期还有一定的差距，真正使数据挖掘更 广泛的应用于各个行业、解决研发与实际应用相结合的问题，还面临着巨大的挑 战 i o , 12 ，”】，主要有以下几个方面： 1 数据类型的多样性：随着数据库技术的发展，许多数据库系统包含了更 复杂的数据类型，如：文本数据、多媒体数据、空间数据和时态数据等。数据挖 掘系统对这些数据库的操作能力是至关重要的。由于数据类型的多样性和数据挖 掘目标的不同，希望一个系统能够挖掘所有类型的数据是不现实的。为挖掘特定 类型的数据，应当构造特定的数据挖掘系统。 2 算法的效率和可伸缩性：数据挖掘是直接面向海量数据库系统的，这类 数据库通常有上百个属性和数百万条记录，并且数据表之间也包含了复杂的关 系，这必然导致数据挖掘过程中搜索维数和搜索空间的激增。为有效地从数据库 中发现信息，数据挖掘算法必须是有效的和可度量的。因此提高算法的效率和规 模伸缩性是数据挖掘在实际应用中晤临的巨大挑战。 3 数据挖掘系统的交互性；数批挖掘是一个复杂的过程，数据挖掘过程中 第一章绪论 操作者的适当参与是必不可少的。由于生成结果的多样性和挖掘结果集过于庞 大，给用户的理解和从中发现有趣的模式造成一定的困难，因此，友好的用户界 面准确直观地描述挖掘的结果一直是数据挖掘面临的巨大挑战。 4 数据的私有性和安全性：数据挖掘系统能从不同的角度、不同的抽象层 上看待数据，这会潜在地影响到数据的私有性和安全胜。研究数据挖掘可能导致 的非法数据入侵，同样是实际应用过程中亟待解决的问题。 1 2 论文的研究内容和组织结构 1 2 1 论文的研究内容 数据挖掘的目标是采用有效的算法，从大量现有的数据集合中发现用户感兴 趣的知识，并用简明的方式表示出来。而能否更好的达到数据挖掘的目标与数据 挖掘系统所采用的挖掘算法息息相关，因此，数据挖掘算法在数据挖掘中起着至 关重要的作用。 论文的选题源于浙江省自然科学基金项目“基于数据挖掘技术的语义表示方 法及应用研究”( 编号：y 1 0 6 2 5 9 ) 。本文的研究内容是该项目的一部分，主要集 中在关联规则挖掘部分，而关联规则的精简方法更是论文研究的重中之重。本文 首先对数据挖掘技术的产生和面临的主要挑战做了概括性的阐述，介绍了数据挖 掘的定义和挖掘的主要步骤：接着对关联规则的挖掘做了详细的描述，介绍了关 联规则挖掘的步骤、关联规则挖掘的经典算法和关联规则常用的压缩方法；然后， 提出了三种关联规则的精简算法，其中包括基于标记域f p ，t r e e 快速挖掘最大频 繁项集、基于f p t r e e 挖掘最大频繁项集的非递归深度优先算法和基于频繁项集 的最大频繁项集和频繁闭项集挖掘算法：最后，本文设计并实现了一个关联规则 挖掘工具原型。 1 2 2 论文的组织结构 本文主要分为7 章： 第1 章介绍了数据挖掘的由来，给出了数据挖掘的定义，并简要分析了数 据挖掘面临的主要挑战。 第2 章介绍了与本文研究工作相关的知识。首先给出了关联规则挖掘的基 本概念和经典的挖掘算法，然后简单介绍了从关联规则到相关分析的内容，最后 给出了目前常用的一些关联规则精简方法。 第3 章提出了一种基于标记域f p t r e e 的最大频繁项集挖掘算法。首先分 浙江师范大学硕士学位论文 析了现有最大频繁项集挖掘算法的不足之处，接着介绍了深度优先搜索策略、 f p t r e e 结构等基础知识，然后给出了一个改进的数据结构一一带标记域的 f p 。t r e e ，并详细介绍了一种基于该数据结构的最大频繁项集挖掘算法，最后给 出了算法分析以及与其它算法的性能比较。 第4 章提出了一种基于f p t r e e 挖掘最大频繁项集的非递归深度优先算法。 首先分析了现有深度优先算法的不足之处，接着介绍了m f i t r e e 结构等基础知 识，然后详细介绍了一种基于f p t r e e 挖掘最大频繁项集的非递归深度优先算法， 最后给出了算法分析以及与其它算法的性能比较。 第5 章提出了一种基于频繁项集的最大频繁项集和频繁闭项集挖掘算法。 首先简要分析了现有最大频繁项集和频繁闭项集挖掘算法的局限性，接着介绍了 频繁项集、最大频繁项集和频繁闭项集的一些性质，并在该性质的基础上提出了 基于频繁项集的最大频繁项集和频繁闭项集挖掘算法，最后给出了算法分析以及 与其它算法的性能比较。 第6 章设计并实现了一个关联规则挖掘工具原型。首先给出了该工具原型 的实现环境，然后详细介绍了工具原型的主要功能模块和实现方法，最后总结了 该工具原型的特点。 第7 章对论文进行总结并对下一步的工作进行展望。 4 第二章关联规则挖掘概述 关联规则挖掘是数据挖掘的主要任务之二，而频繁项集挖掘则是关联规则挖 掘的关键步骤。本章首先介绍关联规则挖掘技术的一些基本发展情况，包括关联 规则的基本概念、挖掘步骤和研究现状等，然后介绍了从关联规则到相关分析， 最后重点介绍了关联规则主要的精简方法，这将为后续章节提供基础。 2 1 关联规则挖掘 关联规则挖掘问题是r a g a w a l 等人【j 4 】于1 9 9 3 年首先提出来的，是当前数 据挖掘研究的主要模式之一，用于发现大规模数据库中不同域或属性之间的联 系，找出有趣的多个域之间的关联关系。关联规贝i j 挖掘的目标是从数库中找出形 如“由于某些事件的发生而引起另外一些事件的发生”之类的规则。这种规则提 供的信息可以用作商品目录设计、商场货架的布置、生产安排、具有针对性的市 场营销等。 2 1 1 关联规则挖掘的基本概念 设i = 1 1 ，1 2 ，i m 是m 个不同项的集合，任务相关的数据d 是数据库事务 的集合，其中每个事务t 是项的集合，使得t - - - i 。每一个事务有一个标识符， 称作 l i d 。设a 是一个项集，事务t 包含a 当且仅当a - t 。 基于上述基本假设，关联规则及相关定义如下【m ”l ： 定义2 1 关联规则 给定数据集i ，关联规则是形如x 等y 的表达式，其中x i ，y c - i ，x n y = ( 3 。 衡量关联规则是否有意义的标准有两个：一个是支持度( s u p p o r t ) ，另一个是 置信度( c o n f i d e n c e ) 。 定义2 2 关联规则的支持度 给定数据集d 和关联规则x 寻y ，令： s u p ( x j y ) - p ( ) ( u y ) ( 2 1 ) 称s u p ( x jy ) 为关联规则x jy 在数据集d 上的支持度。 定义2 3 关联规则的置信度 给定数据集d 和关联规则x j y ，令： c o n f ( x = p ( x i y )( 2 2 ) 称c o n f ( x 等为关联规则x j y 在数据集d 上的置信度。 定义2 4 强关联规则、最小支持度阂值、最小置信度阈值 浙江师范大学硕士学位论文 给定d 和关联规则r ，并给定r a i n s u p ( o ，1 ) 和r a i n c o n f ( 0 , 1 ) ，当 s u p ( xy 伊m i n s u p 且c o n f ( x ) = m i n - c o n f 时，称关联规则r 为数据集d 上的 强关联规则，简称强关联规哭；j 。其中，r a i n s u p 称为最小支持度阊值，m i n - e o n f 称为最小置信度阈值。 例2 1 设卜 牛奶，面包，啤酒 ，在有1 0 0 0 条原始记录的数据集d 中共有 3 0 0 条记录显示购买了面包，而在这3 0 0 条记录中又有2 0 0 条显示购买了牛奶， 那么关联规则“牛奶j 面包”在数据集d 上的支持度就是s u p = 2 0 0 1 0 0 0 = - 2 0 ， 置信度就是c o n f = 2 0 0 3 0 0 = 6 7 。如果设定最小支持度阈值为2 0 ，最小置信度 阈值为6 0 ，那么： 牛奶令面包 ( s u p = 2 0 ，c o n f = 6 7 ) 就是数据集d 中的一条强关联规则。 定义2 5 完全频繁项集 给定数据库d 和项集x ，设最小支持度阙僮为r a i n - s u p ，项集x 的支持度表 示为s u p ( x ) ，当s u p ( x ) - - m i n - s u p 时，称项集x 为d 上的完全频繁项集，简称 频繁项集。d 中所有频繁项集的集合记为：f l s = x l s u p ( x ) = m i n - s u p 。 简单的说，频繁项集就是在d 上的支持度不小于最小支持度阈值的项集。 此外，在数据集d 上不是频繁项集的项集称为d 上的非频繁项集。定义2 ，5 里 面的最小支持度阈值也就是强关联规则定义里面的最小支持度阈值，是由用户自 定义的闽值。 由完全频繁项集的定义，可以得出完全频繁顼集具有以下性质： 性质2 1 数据集d 上频繁项集的非空子集一定是d 上的频繁项集。 对于给定的数据集d 、最小支持度闽值r a i n s u p 以及项集x 和y ，如果满足 s u p ( x ) = r a i n - s u p 并且y c x ，则有s u p f f ) = m i n - s u p 。 证明；因为y - x ，所以d 中包含x 的事务定包含y ，不包含x 的事务 也有可能包含y ，故d 中包含y 的事务数一定大于等于包含x 的事务数，所以 s u p ( y ) = m i n s u p 性质2 1 是频繁项集的一条基本性质，许多挖掘算法都是利用性质2 1 来进 行剪枝的。由性质2 1 可以得到： 性质2 2 数据集d 上非频繁项集的超集一定不是d 上的频繁项集 2 1 2 关联规则挖掘的步骤 一般来说，关联规则的挖掘由以下两步组成妇i ： ( 1 ) 找出所有频繁项集：这些项集的支持度必须大于等于用户定义的最小 6 第二章关联规则挖掘概述 支持度闽值： ( 2 ) 由频繁项集产生强关联规则：这些频繁项集除了满足最小支持度阀值 的要求外，还必须满足最小置信度阈值的要求，即这些频繁项集的置信度必须大 于等于最小置信度阈值，由这样的频繁项集产生的关联规则才是强关联规则。 由于第二步的开销远低于第一步，因此关联规则挖掘的总体性能由第一步决 定。 2 1 3 频繁项集挖掘 a g r a w a l 等1 4 】在1 9 9 3 年提出的a p f i o f i 算法是挖掘频繁项集中最核心、最具 有影响力的算法，它是一种宽度优先搜索算法，它的基础就是频繁项集的向上闭 包性质，即频繁项集的非空子集一定是频繁项集。 a p r i o d 算法具体步骤如算法2 1 所示： 算法2 1a p d o r i 算法。使用逐层迭代找出频繁项集 输入：事物数据库d ，最小支持度闽值m i m s u p 输出：d 中的频繁项集l ( 1 ) l i - - f l n df r e q u e n tii t e m s e t s ( d ) ； ( 2 ) f o r ( k = 2 ；l k - l a ；k h ) ( 3 ) c k = a p r i o r ig e n ( l k bm i n - s u p ) ； ( 4 ) f o re a c ht r a n c t i o nt ed s c a ndf o rc o u n t s ( 5 )c t = s u b s e t ( c k ，t ) ； g e tt h es u b s e t so f tt h a ta _ ec a n d i d a t e s ( 6 ) f o re a c hc a n d i d a t ec ec t ( 7 ) c c o u n t + + ； ( 8 )l ( 9 ) k c c k l c c o u n t - m i n - s u p ； ( 1 0 ) ( 1 1 ) m t u ml = uk k p r o c e d u r ea p r i o f i _ g e n ( l ：f r e q u e n t ( k - 1 ) - i t e m s e t s ) ( 1 ) f o re a c hi t e m s e t1 i h i ( 2 ) f o r e a c hi t e m s e t s1 2 l ( 3 ) i f ( 1 l 【q = 1 2 1 l f oi 【2 】- 1 2 【2 】) 。 ( 1 i k - 2 = 1 2 ( k - 2 ) ( 1 l 【k - 1 】 1 2 【k 1 】) t h e n ( 4 ) c 1 1 ll i n k1 2 ； ( 5 ) i f h a s _ i n f i e q u e n ts u b s e t ( c ，l k 1 ) t h e n ( 6 ) d e l e t ec ： ，p r u n es t e p ：r e m o v eu n f i u i t f u lc a n d i d a t e ( 7 ) e l s ea d dc t o c 7 浙江师范大学硕士学位论文 ( 8 ) ( 9 ) r e t u r nc k p r o c e d u r eh a s j n f r e q u e n t _ s u b s e t ( e ：c a n d i d a t e k - i t e m s e t ；k ) ：f r e q u e n t ( k - 1 ) 一i t e m s e t ) ( 1 ) f o re a c h ( k - d - s u b s e tso f e ( 2 ) i f ( s 岳l ) t h e n ( 3 )r e t u mt r u e ； ( 4 ) r e t u r nf a l s e ； 该算法中有两个关键步骤：连接步和剪枝步 ( 1 ) 连接步：通过k 1 与自身连接产生候选l c - 项集c k ，其中，l k i 中的元素 是可连接的。 ( 2 ) 剪枝步：c k 是l k 的超集，即它的成员可以是也可以不是频繁的，但所 有的频繁k 项集都包含在c k 中。扫描数据库，确定c k 中每一个候选的计数，从 而确定l k ( 计数值不小于最小支持度计数的所有候选是频繁的，从而属于l d 。然 而，c k 可能很大，这样所涉及的计算量就很大。为压缩c k ，使用a p r i o r i 性质： 任何非频繁的( k 1 ) 项集都不可能是频繁k 项集的子集。因此，如果一个候选b 项集的( k 。1 ) 项集不在l k - l 中，则该候选项也不可能是频繁的，从而可以从c k 中 删除。 a p r i o r i 算法的特点是：扫描数据库的次数与最长的频繁项集的长度相等； 需要保存生成的候选项集。在最小支持度阈值较低的时候，如果出现了比较 “长”的频繁项集，a p r i o r i 算法代价很高。这是因为它需要多遍扫描数据集， 并产生大量的候选项集，容易引起组合爆炸。因此，人们陆续提出一些改进技术， 试图控制候选项集的规模和减少扫描数据库的次数，主要有以下几种方法：基于 散列的技术【1 6 1 、基于划分的方法【m 、抽样方法嗍和动态项集计数方裂州等。 尽管以上算法对a p r i o f i 算法起到了一定的改进作用，但它们仍然需要产生 候选项集，并多遍扫描数据库。于是，人们提出了另外的一些算法。它们的主导 思想不再是经过多次遍历数据库来发现频繁项集，而是将原始数据库中的相关重 要信息压缩保存在一个新的数据结构中，基于新的数据结构进行频繁项集挖掘， 其中以f p g r o w t h 算法【2 0 1 最为典型。 f p g r o v n h 算法由h a r t 等人提出的。它的基本思路是将数据库中的信息压缩 保存在_ 个称为频繁模式树( f p t r e e ) 的数据结构中，然后基于f p - t r e e 挖掘数据 库中所有的频繁项集。该算法对所有频繁项集的挖掘分为以下两步：构造频繁 模式树f p t r e e 。在f p t r e e 中，每个节点有4 个域组成：节点名称i t e m n a m e 、 节点计数n o d e c o u n t 、节点链n o d e - l i n k 及父节点指针n o d e - p a r e n t 。另外，为方便 第二章关联规则挖掘概述 树遍历，创建一个频繁项头表h e a d e r ，它由两个域组成：项目名称i t e m 和节点 链头，其中节点链头指向f p - t r e e 中与之名称相同的第一个节点；调用 f p g r o w t h 挖掘出所有频繁项集，具体算法描述如下： 算法2 2f p - t r e e 构造算法b u i l d f p t r e e ( d ，r a i n - s u p ) 输入：d 为原始数据库，m i n s u p 为最小支持度阈值： 输出：f p t r ( 1 ) 扫描d 一次，产生频繁项集合f 及其支持度计数。按其支持度计数降序 排列f ，生成f p t r e e 头表h e a d e r ； ( 2 ) 创建f p t r e e 的根节点，标号为“n u l l ”。对于d 中的每个事务( 或者条 件模式基) t 作如下处理；按h e a d e r 中的次序排列t 中的频繁项目，设排列后 的结果为【p i p 】，其中p 是第一个项目，而p 是剩余项目的列表，调用 i n s e r t t r e e ( d 问，t r e e ) ： ( 3 ) r e t u m t r e e ； 算法b u i l d f p t r e e 中使用的过程i n s e r t - t r e e 的流程如下； 过程i n s e r t - t r e e ( l o l p 。t r e e ) ( 1 ) 如果t 有子女n 使德n i t e m - n a m e = p 。i t e m - n a m e ，则n 的计数增加1 ； ( 2 ) - 否则创建一个新节点n ，将其名称i t e m n a m e 、计数c o u n t 分别设置为 p ，l ，由父节点指针p a r e n t 链接到它的父节点t ，并通过节点链n o d e - l i n k 将其链接 到具有相同i t e m - n a m e 的节点； ( 3 ) 如果p 非空，递归调用i n s e r t - t r e e ( p , n ) 。 算法2 3 基于f p t r e e 的频繁项集挖掘算法f p - g r o w t h ( f p t r e e 口, r n i n - s u p ) 输入：t r e e 为由算法2 2 生成的f p t r e e 或条件f p 子树，o r 是当前项集， r a i n - s u p 为最小支持度阈值 输出：频繁项集的集合 ( 1 ) i f t r e e 是单分支树p ( 2 )f o r e a c h 路径p 中节点的每个组合( 记作口) d o ( 3 ) 产生频繁项目集声u 口，其支持度s u p p o r t 等于中节点的最小支持度计数； ( 4 ) 。e l s e f o r e a c h a i 在t r e e 头部d o b e g i n ( 5 ) 产生模式口= 籼u 口，其支持度计数s u p p o r t = a is u p p o r t ： ( 6 ) 构造p 的条件模式基，然后构造声的条件模式数? 托： ( 7 ) i f ( t r e e 8 a ) t h e n ( 8 ) 递归调用f p g r o w t h ( t r e e ，p ，r a i n s u p ) ； ( 9 ) e n d 算法f p g r o w t h 将频繁项集的挖掘问题转换成递归挖掘一些短频繁项集，然 浙江师范大学硕士学位论文 后连接后缀。它使用最不频繁的项作后缀，提供了好的选择性。对f p 增长方法 的性能研究表明：对于挖掘长的和短的频繁模式，它都是有效的和可规模化的， 并且大约比a p r i o r i 算法快一个数量级。但当数据库很大时，构造基于内存的 f p t r e e 有时是不现实的。一种可选的方案是首先将数据库划分为投影数据库的 集合，然后在每个投影数据库中构造f p - t r e e 并挖掘它。如果投影数据库的 f p t r e e 还不能放进内存，该过程可以递归地用于投影数据库“”。 2 2 由关联规则到相关分析 大部分关联规则挖掘算法都使用支持度一置信度框架。尽管最小支持度和置 信度阈值能够排除大量无趣的规则，但是仍然会产生一些用户不感兴趣甚至是误 导的关联规则。当使用低支持度闽值或挖掘长模式时，这种情况更为严重。