（计算机应用技术专业论文）一种改进的并行关联规则挖掘算法.pdf

哈尔滨工程大学硕士学位论文 摘要 关联规则是数据挖掘的主要技术之一，这缘于关联规则数据挖掘在商业 等领域的成功应用，故而使它成为数据挖掘领域中最成熟、最重要、最活跃 的研究内容。 挖掘关联规则问题的核心是发现频繁项集。现今已有多种发现频繁项集 的算法，如a p r i o r i ，p a r t i t i o n 等算法。为了提高挖掘频繁项集的效率，引入 了并行化技术。c d 算法是对a p r i o r i 算法的简单并行化，其目的是减少通信 量，获得较好的任务分布性。 本文针对c d 算法存在的i o 量较重、数据结构重复、不能有效利用整 个内存等问题，提出一种改进的并行关联规则挖掘算法该算法在遵循c d 算法思想的基础上，采用动态数据集划分技术对数据库中的数据先进行划分， 然后再由控制处理器分配至各个处理器，以此来减少f o 操作量；提出通过 由一个控制处理器来控制其它处理器的方法，实现挖掘部分的并行化；在此 基础上，提出在各个处理器上应用p - t r e e 结构来存储数据，以达到优化各个 处理器中所存储数据的结构、有效利用内存的目的，从而快速找出频繁项集， 实现对事务数据库中数据的有效挖掘。最后对两种算法进行了实验验证，结 果表明本文提出的改进算法能够更加有效地提高对频繁项集的挖掘效率，达 到了预期的初步并行化效果。 关键词：并行关联规则；频繁项集；p - t r e e ；动态数据集划分 哈尔滨工程大学硕士学位论文 a b s t r a c t a s s o c i a f i o nn i l e sa r et h e 嘶r t a n tt e c h n i q u ehd a t am i n i n g ，b e c a u s et h e s u c c a s s f u la p p l i c 撕。璐s u c h 舔t m s i n e s sm a d ei tb e c o m ef i l em o s tm a t u r e ， 岍r t a n t a n da c t i v er e s e a r c h t h ec o 他o fm i n i n ga s s o c i a t i o nn l l e si sf l n d m gf r e q u e n ti t e m s e t s n o w a d a y s t h e 托a 托m a n ya l g o d t h m s 证f 幽n gf t e q u e n ti t e m s e t ss u c h 勰t h ea 1 9 0 a p d o f i ，p a r t i f i o 血p a r a l l e l i z a t i t e c h n i q u ei si n t r o d u c e di n l p r o v et h ee f f i c i c y o f m i n i n gf t e q u e n ti t e m s e t s 舢g o f i t h mc d i sas i m ：p l ep a r a l l e l i z a t i o n a l g o f i t h m a p r i o da n da i m s 砒d e c r e a s i n gt h eu a f 丘ca n dg a i n i n gp m f e r a b l ed i s b 嘶o f t h e t a s l a ni m p r o v e dp a r a l l e la 1 9 0 f i t h mo fn m n ga s s o c i a t i o nm l 嚣i 3p r e s e n t e di n 也i sp a p e ra g a i n s tt h ep r o b l e m s 商s t i n gi na l g o f i t h mc d s u c h 勰t h ew e i g h t y o p e r a t i o mo fv o ，t h er e p e t i t i o no fd a t a 啦m c t 岛t h eu s e l e s su s i n gm e m o r y h p a r t i t i o n st h ed a t a b a s eb yu s i n gt h et e 幽l o g yo fd y n a m i cd a t a s e t sp a r t i 廿o n b a s e d a l g o r i t h mc d ，t h 既d i s t r i b u t e st h ed a t at oe a c hp r o c e s s o rb yf i l ec o n t r o l p r o c e s s o rt or e d u c et h ew c i g h t yo p e r a t i o n so fi o nu s e sac o n t r o lp r o c e s s o rt o m a n a g et h e 渤p r o c e s s o r si no r d e rt o h i e v et h ep a r a l l e l i z a t i 蛆j nm i n i n g t h e nt h ed a t aa r es t o r e d c hp r o c e s s o rb yu s i n gp - t r e es t r u c t u r ei no r d e rl o o p t i m i z ed a t as t r u c t t 腿a n du s em e m o r yp o t e n o y , s oi t 啪f i n do u tf r e q u e n t i t e m s e t sq l l i c h ya n di m p l e m e n tp o t e n tn m n s md a t a b a s e a th s t - t h et w o a l g o f i t h m sa r ev a l i d a t e db y 懿p e r i m e n ta n dt h er e s u l t ss h o wt h a tt h ei m p f o v e d 如f i t h mc a ni m p r o v et h ee f l c i c ym o l ep o t e n ta n da c h j e v e st h ep r i m a r y p u r p o 辩o f p a r a l l e l i z a t i 蝴o r d s ：p a r a l l e l 鹪s o c i a t i o nm l c s ：f r e q u e n ti t e m s e t s ；p - t r e e ；d y n a m i cd a t a s e t s p a r t i 6 0 n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：盈隘 e t 期：加7 年月j 日 哈尔滨工程大学硕士学位论文 1 1 国内外研究现状 第1 章绪论 在事务数据库中挖掘关联规则是数据挖掘领域中一个非常重要的研究课 题。a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规 则问题，其核心方法是基于频集理论的递推方法m 。以后诸多的研究人员从各 个角度对关联规则的挖掘问题进行了大量的研究。总体来说算法可以归纳为 两类，一类是产生频集候选项的算法，另一类是不产生频集候选项的算法。 在a p r i o r i 算法的基础上，研究人员提出了许多关于频集算法的优化方 法。p a r k 等于1 9 9 5 年提出了采用h a s h 散列技术的d h p 算法，该算法在对数 据库进行第一次扫描时，由于要构建h a s h 表，所以速度会比a p r i 砥算法慢； 但在后期的计算中由于所占用的内存较少，所以速度与a p r i o r i 相比要快m ， 故而从总体来看h a s h 散列技术的应用使算法提速很多a g r a w a l 等提出 a p r i o r i t i d 和a p r i o f i i - i y b r i d 算法m ，因为不包含任何k 项集的事务，所以不可 能包含任何( “1 ) 项集，故而可对这些事务加上删除标志，扫描数据库时不 再考虑s e t m 算法在某种程度上是一种类似于a p r i o r i t i d 的算法，它可以 直接使用s q l 语句“，b r i n 等人给出动态项集计数的算法，该算法动态地评 估所有需要计算支持度的项集，若一个项集的所有子集已经被确定为是频繁 的，则添加它作为新的候选“1 。s a v a s c r e 等人提出了p a r t i t i o n 算法m 以上算 法中较为有效和有影响的算法为a p r i o r i 、p a r t i t i o n 和d h p 算法。针对a p r i o r i 算法的固有缺陷，h a n 等提出了不产生候选频繁项集的f p g r o w t h 算法，实 验表明f p - g r o w t h 算法对不同长度的规则都有很好的适应性，同时在效率上 较之a p r i o r i 算法有巨大的提高n - 。e c l a t 算法是将深度优先搜索( d f s ) 与标 志符集合( 西d l i s t ) 交叉组合运用的一种改进算法，由于该算法采用d f s 方 法，故而可以不必像p a r t i t i o n 算法那样将数据库进行拆分w 尽管关联规则的描述很简单，但是它却是一个计算和f o 量集中的任务， 哈尔滨工程大学硕士学位论文 假设给定，个项目集，那么存在2 。个子集可能是频集。处理这样指数级的数 据需要大量的磁盘f o 操作，显然串行算法无法适应如此巨大的计算量，必 须引入高性能的并行计算以有效地完成挖掘任务z a i a n e 等人提出了基于 f p - g r o w t h 的m l f p t ( m u l t i p l el o c a lf r e q u e n tp a t t e r nt r e e ) 算法，该算法仅 需对数据库进行二次扫描，避免生成大量候选项集，并且通过在数据挖掘的 不同阶段所采用的划分策略实现最佳的负载平衡m 。a g r a w a l 等人提出了c d ( c o u n td i s t r i b u t i o n ) 、d d ( d a t ad i s t r i b u t i o n ) 和c a d ( c a n d i d a t ed i s t r i b u t i o n ) 算法u m 。p a r k 等人提出了p d m 算法“- 。其中的c d 算法具有速度较快、易于 实现且对于各计算机间同步次数要求较少等优点，但仍存在通信量大和产生 大量候选项集等问题。但c d 算法的执行效果要高于d d 、c a d 和p d m 算法。 d m a 算法虽然是基于分布式数据库的挖掘算法，但也可用于并行数据挖掘 w 。虽然d m a 算法克服了c d 所存在的一些弱点，但其对于各计算机问同步 次数的要求仍然较多。本文第2 章、第3 章对以上几种关联规则算法有相关 介绍 过去的几年中，一些针对特殊任务的关联规则算法也取得了长足的发展。 首先，出现了针对提高关联规则自身的方法，诸如量化关联规则m ，、普通关 联规则n ”和序列模式“，还有出现了对于关联规则问题的概括性研究t 蝴。其次， 关于挖掘规则集合子集( 这些子集是根据特殊项目或是属性测量来定义的) 的算法也得到了相应的发展，如普通约束n ”、有效规则一、最大频繁项目集m 和频繁封闭项目集。 1 2 论文的研究内容及意义 关联规则是数据挖掘的主要技术之一，也是在无指导学习系统中挖掘本 地模式的最普通形式。这缘于关联规则数据挖掘在商业等领域的成功应用， 使它成为数据挖掘领域中最成熟、最重要、最活跃的研究内容 关联规则挖掘就是发现具有用户指定的最小置信度( m i n c o n f i d e n c e ) 和 最小支持度( m i n s u p p o r t ) 的关联规则。置信度太低说明规则的可信程度差； 支持度太低，说明规则不具有一般性。对于这类规则，数据挖掘将其称为“不 感兴趣的”，关联规则挖掘的目的在于找出那些可信的并且有代表性的规则 2 哈尔滨工程大学硕士学位论文 在进行关联规则挖掘时需要主要解决以下两个问题： ( 1 ) 算法的复杂性。现阶段的关联规则挖掘算法都是针对这个问题而提 出的。关联规则的算法主要从两方面来进行考虑： 减少i o 操作。关联规则挖掘的数据集有的可达g b 甚至t b 的数量级， 频繁的i o 操作必将影响关联规则的挖掘效率，减少i o 操作的方法主要是 减少扫描数据集的次数来提高效率； 降低需要计算支持度的候选项目集的数量，使其与频繁项目集的数量 接近。候选项目集的降低可以节省为处理部分候选项目集所需的计算时间和 存储空间 ( 2 ) 必须从产生的规则集中选择出用户所感兴趣的、有用的规则。最小 支持度和最小置信度并不能保证所挖掘出的关联规则一定是用户所感兴趣 的，其中可能包含一些冗余的、无意义的关联规则。而且支持度和置信度较 高的关联规则可能是常识性的规则，不能被称为信息。因而制定适当的关联 规则兴趣度计算标准可以使得挖掘出的关联规则更能满足用户的需求m ，+ 尽管目前对关联规则数据挖掘的研究取得了许多显著的成功，但仍然还 有许多问题值得进一步的研究与探讨关联规则数据挖掘的研究与发展方向 主要体现在以下方面c 2 t - 。l ： ( 1 ) 针对关联规则挖掘算法进行效率与可伸缩性的研究。在实际应用中 需要从海量数据库中抽取出有效信息，故而关联规则挖掘算法的效率显得极 为重要基于受限的关联规则挖掘方法在加强结合领域知识、提取与挖掘任 务有关的数据、有效减少问题的复杂度、提高算法效率方面有着广阔的发展 前景。 ( 2 ) 发展更为合理有效的规则评价标准。在实际应用中，若仅凭支持度 和置信度这两个评价关联规则的标准，可能会发现大量冗余、虚假或非感兴 趣的规则，故而需要针对具体情况而研制一些新的评价标准。鉴于此，关联 规则中引入了兴趣度的概念以剔除那些不感兴趣的规则。 ， ( 3 ) 开展并行关联规则挖掘的研究。目前在并行关联规则数据挖掘中仍 存在许多尚待解决的问题，如数据量的不断增长、维数的不断增加、动态负 载的平衡、数据的不对称性、并行的数据库管理系统与文件系统等。由于挖 掘系统自身的原因，并行挖掘不可能随着大规模并行计算而在数据挖掘中实 3 哈尔滨工程大学硕士学位论文 现任意程度的并行。 ( 4 ) 开展对不同类型数据的挖掘研究。目前大部分的挖掘算法都是对关 系型数据库的挖掘。由于应用领域的不同，所挖掘的数据的类型也不同。有 关的研究有李颖基等人提出的基于w e b 拓朴概率模型和有趣关联规则的i a r 算法一；s uf 等提出采用空间分布式数据的关联规则算法对生态关联规则进 行挖掘，对中国黄海区域的鱼群分布进行了实例分析w 此外，还可以对结 构化数据、多维数据、超文本数据、面向对象的数据等展开研究w 。 ( 5 ) 可视化技术在关联规则挖掘中的应用。由于产生的规则最终是要面 向应用的，所以关联规则挖掘的可视化可以通过可视化技术的直观性来弥补 数据挖掘算法复杂性的缺陷，方便用户与挖掘系统进行有效的交互，同时也 加强与领域专家的合作在这方面的研究有l , ：o p a n a k i si 等人提出了并行的 柱状图系统“，；k t m a n is 等人提出了v i d a m i n e 系统w ( 6 ) 开展针对数据挖掘过程中隐私保护及数据安全性问题的研究。在数 据挖掘过程中，可以从不同角度及不同抽象层对数据进行查看，这样做有时 会严重威胁那些受保护数据的安全和禁止侵犯隐私的目标。知识发现何时可 能导致侵犯隐私及为了保护敏感信息而开发何种安全措篪，这些研究工作都 是非常重要的。 此外，关联规则挖掘技术还可以提供决策支持，可以应用到其它数据挖 掘技术中，如应用于决策树归纳、时间序列的数据分析和分类等数据挖掘技 术中。 。 本文从关联规则挖掘的核心问题产生频繁项集着手，在分析研究关 联规则挖掘算法基础上，提出一种改进的并行关联规则挖掘算法 1 3 本文工作及组织结构 目前，关联规则挖掘是信息领域研究的热门课题之一，本文针对关联规 则进行了研究，所做工作如下： ( 1 ) 在将动态数据集划分技术引入到c d 算法的基础上，采用p - t r e e 结 构对c d 算法加以改进，提出一种改进的并行关联规则挖掘算法。 ( 2 ) 通过实验验证改进后的算法较c d 算法能够更加有效地提高对频繁 4 哈尔滨工程大学硕士学位论文 项集的挖掘效率，达到初步的并行化效果 本文组织结构如下： 第l 章介绍了关联规则的国内外研究现状、研究内容和意义，以及本文 的组织结构和主要内容。 第2 章主要介绍关联规则挖掘的思想及算法。详细介绍a p r i o r i 算法和 f p g r o w t h 算法及算法性能，然后介绍了其它几种典型算法的思想并对其优缺 点进行分析，最后讨论了关联规则的价值衡量问题。 第3 章阐述了并行关联规则挖掘的策略及算法首先提出并行关联规则 挖掘的问题描述，然后介绍并行挖掘策略，对几种典型的并行关联规则挖掘 算法及其优缺点加以介绍，最后介绍了并行化数据挖掘的研究与发展方向。 第4 章首先介绍p - t r e e 结构及其性能描述，然后对c d 算法及其性能加 以介绍。随后针对c d 算法存在的i o 量较重、数据结构重复、不能有效利 用整个内存等问题，提出一种改进的并行关联规则挖掘算法最后通过实验 验证这种改进算法与c d 算法相比，能够更有效地提高对频繁项集的挖掘效 率，达到初步的并行化效果。 哈尔滨工程大学硕士学位论文 第2 章关联规则挖掘概述 最近几年里，数据挖掘技术已经引起了数据库研究人员的广泛关注，关 联规则挖掘是数据挖掘中一个重要的研究领域。关联规则是寻找同一个事件 中出现的不同项之间的相关性，即找出事件中频繁发生的项或属性的所有子 集，以及它们之间的相互关联性关联规则最早用于发现顾客交易数据库中 不同商品间的联系，之后研究人员在此基础上对关联规则的挖掘问题进行扩 展性研究。本章中将对关联规则挖掘相关概念、算法及算法性能加以介绍 2 1 关联规则问题描述 关联规则最一般的实例表现形式为“8 0 购买面包的顾客同时也会购买 牛奶”a g r a w a l 等于1 9 9 3 年首先提出了关联规则的数据挖掘命题，并且给 出了解决该问题的算法一a p r i 砸算法。a p r i o r i 算法利用了一个集合的先验 性质，即：任何一个频繁项集的非空子集也是频繁的n ，。在关联规则的数据挖 掘中，凡是利用该性质以减少搜索空间的算法都称之为a p l i o r i 系列算法。 a p r i o r i 算法是关联规则中应用最为广泛的算法。关联规则挖掘是在分析零售 业事务数据库时提出的，现在的发展已经大大超过了原先的应用范围，其深 度和广度都有了较大提高。但关联规则的形式化描述还是有其通用意义的， 本文即采用了这种形式化的描述。 定义2 1 关联规则挖掘的数据集记为d ( 一般事务数据库) ，口 “，t z ， t k ，埘，轳 西，易，0 ，拼，t k ( k = - l ，2 ，糟) 称为事务( t r a n s a c t i o n s ) ， k ( 肝= 1 ，2 ，p ) 称为项目( i t e m ) 定义2 2 设卢 f j ，屯， 是d 中全体项目组成的集合，的任何 子集石称为d 中的项目集( i t e m s e t ) ，因称为集合工为知项目集( k - l t e m s e t ) 。 设“和x 分别为d 中的事务项目集，如果x c 矗，称事务如包含项目集兄 每个事务都有一个惟一的标识符，称为t i d 。 ， 定义2 3 数据集d 中包含项目集x 的事务数称为项目集x 的支持数， 6 哈尔滨工程大学硕士学位论文 记为仃，项目集x 的支持度记为s u p p o r t ( 聊： s u p p o r t ( x ) = 衙x l o o ( 或) s u 删幻= 街 ( 2 - 1 ) 其中| d | 是数据集d 的事务数，若s u p p o r t ( x ) 不小于用户指定的 n l i 璐u p p o r t ，则称x 为频繁项目集，简称频集( 或大项目集) ，否则称石为非 频繁项目集，简称非频繁集( 或小项目集) 定理2 1 设五y 是数据集d 中的项目集： ( 1 ) 若x y ，则s u p p o r t ( 舯 一s u l ；p o r t ( y ) ； ( 2 ) 若z j ，若工是非频集，则j ，也是非频集； ( 3 ) 若z e l ，若r 是频集，则名也是频集； 定义2 4 若瓜y 为项目集，且x n y = ，蕴涵式x ；y 称为关联规 则，瓜】，分别称为关联规则x j r 的前提和结论。项目集j u y 的支持度称 为关联规则x j y 的支持度，记作：s u p p o r t ( x n ， s u p p o r t ( x jy ) = s u p p o r t ( x u y ) ( 2 - 2 ) 关联规则xjy 的置信度记作：c o n f i d e n c e ( xjn ， c o n f i d e n c e ( x j ，) ：婴婴嘤婴x 1 0 0 ( 2 - 3 ) s u p p o r t ( aj 一般的，将用户根据挖掘需要而指定的最小置信度记为m i n c o n f i d e n c e 支持度和置信度是描述关联规则的两个重要概念支持度用于衡量关联 规则在整个数据集中的统计重要性，置信度用于衡量关联规则的可信程度。 一般来说，只有支持度和置信度均较高的关联规则才可能是用户感兴趣、有 用的关联规则m ， +； 定义2 5 若s u p p o r t ( x y ) 7 m i n s u p p o r t ，且c o n f i d e n c e ( x ；y ) m i n c o n f i d e n c e ，称关联规则x j y 为强规则，否则称关联规则x j y 为弱 规则。 。 关联规则的挖掘任务就是挖掘出d 中所有的强规则强规则z jy 对应 的项目集( z u d 必定是频集( 由定义2 5 和式( 2 2 ) ) ，由定理2 1 和式( 2 - 3 ) 可知，频集( x u n 导出的关联规则x y 的置信度可由频集j 和( x u y ) 的 支持度计算。因此，可以把关联规则挖掘划分为以下两个子问题1 2 0 1 ： ( 1 ) 报据最小支持度找出数据集d 中的所有频集； 哈尔滨工程大学硕士学位论文 ( 2 ) 根据频繁项目集和最小置信度产生关联规则 第一个子问题的任务是迅速高效地找出d 中全部频集，是关联规则挖掘 的中心问题，也是衡量关联规则挖掘算法的标准。目前有很多产生频繁项目 集的算法，这些算法产生频繁矗项目集时，扫描数据库的每个事务用以统计 这些候选b 项目集的支持度，并按照事务确定的最小支持度在第七次迭代时 找出所有频繁七项目集；然而，由于数据库的规模通常是非常大的，所以在 每次迭代时产生候选项目集以统计其支持度是非常耗时的。因此寻求频繁项 目集的有效产生算法是问题的关键，也是本论文研究的重点问题 第二个子问题由式( 2 1 ) 和式( 2 - 3 ) 可知其求解过程是比较容易、直 接的，目前所有的关联规则挖掘算法都是针对第一个子问题而提出的，关联 规则挖掘的基本模型如图2 1 所示图2 1 中的d 为数据集，a l g o r i t h m - 1 为 频繁项目集的搜索算法，a l g o d t h r a - 2 为关联规则的产生算法，置为挖掘出的 关联规则集合。用户通过指定m i n s u p p o t t 、m i n c o n f i d e n c e 分别与算法 a l g o r i t h m - 1 、a l g o r i t h m - 2 交互，通过与足的交互对挖掘结果进行解释和评价。 图2 1 关联规则挖掘的基本模型 关联规则挖掘算法主要考虑的问题有如下两个： ( 1 ) 减少 d 操作。有时关联规则挖掘的数据集可达g b 甚至t b 数量 级，过于频繁的i o 操作可能会直接影响到关联规则的挖掘效率，而减少f o 操作的主要方法就是减少扫描数据集d 的次数； ( 2 ) 降低需要计算支持度的候选项目集的数量，使其与频繁项目集的数 量接近。候选项目数量的降低可以节省为要处理的部分候选项目集所需的计 算时间和存储空间w 。 哈尔滨工程大学硕士学位论文 2 2 关联规则挖掘相关算法及描述 2 2 1 经典a p r i o r i 算法 a p r i o r i 算法的主要工作是利用几次迭代来计算数据库中的频繁项集m 。 第f 次迭代计算出所有频繁j 项集。每一次迭代中有两个步骤：产生候选集， 计算和选择候选项集。即先通过计算得出所有候选1 项集的集合c i ，找出所 有频繁1 一项集厶。然后根据频繁1 项集厶确定候选2 项集的集合c 2 从c 2 中找出所有的频繁2 项集厶再根据频繁2 颂集上2 来确定候选3 项集的集 合o 。从c 3 中找出所有频繁3 项集3 。如此下去直到不再有候选项集m 。 算法a p r i o r i 描述如下： ( 1 ) 厶= 大项目集1 项目集 ； f o r ( 脱；k i 中；d o b c g i n c k - - a p r i o r i _ g e n ( l k i ) ； f o r 所有事务t e d d o b e g i n 锦u 慨t ( g ，班 f o r 所有候选c c t d o c c o u n t + + ； 砒 l k = c eg ic c o u n t 一m i n s u p p o r t e n d ； 鹏f 的候选集 ，f 中所包含的候选集 ( i i ) a n s w e x = u l i ； k - i a p r i o r ig e n 是a p r i o r i 的候选产生函数，其参数为k l ，即所有最大矗l 维项目集的集合，结果返回含有七个项目的候选项目集g ，实际上c t 是k 维频繁项目集的超集( s u p c r s e t ) ，通过算法可以计算项目的支持度，然后生 成厶首先，在j o i n ( 连接) 步骤，把k j 和“，相连接以获得候选的最终 集合的一个超集q ： 9 )o q o “6 o 哈尔滨工程大学硕士学位论文 ( 1 ) i n s e r t i n t o c k ( 2 ) s e l e 虻t p 1 ，【2 】，p 陋l 】，g 【七- l j ( 3 ) f r o m 工i p , 如旧 ( 4 ) w h 饿p q = q q ，p k - 2 - - - q k - 2 ，p 【七1 q k - 1 】 其次，在p r u n e ( 修剪) 步骤，如果c 的一些矗j 维子集不在玩l 中，则 删除所有的项目集c e q 。为了说明这个产生过程为什么能保持完全性，要 注意对于厶中的任何有最小支持度的项目集，任何大小为矗1 的子集也必须 有最小支持度。因此，如果用所有可能的项目来扩充k 1 中的每个项目集， 然后删除所有k - i 维子集不在“i 中的项目集，就可得到厶项目集中的一个 超集，即候选项目集q ， 以上的合并运算相当于用数据库中的所有项目来扩充上i i ，如果删除扩 展项目集的第k - 1 个项目后得到的七- l 项目集不在上纠中，则删除该扩展项目 集。条件p k - q q k - l 】保证不会出现相同的扩展项。故经合并运算之后， & 量厶类似的，在删除运算中，删除q 中其矗l 维子项目集不在“l 中的 项目集，同样没有删除包含在k 中的项目集 ( 1 ) f o r 所有项目集c g d o ( 2 )f o r 所有c 的七1 维子集j d o ( 3 ) i f o 薯厶1 1 t h e n ( 4 )从q 中删除a 如表2 1 所示的数据库d ，其中有4 个事务记录，假设最小支持度 m i n s u p p o r t = 2 ，候选项集中满足最小支持度要求的项集组合成最大的1 项集， 为了生成最大的2 - 项集，使用了a p r i o r l g 函数中的j o i n 步骤，即l l j o i n l i ， 并通过p r u n e 步骤删除那些c 2 的子集不在厶中的项集，生成了候选项集c 2 ， 搜索d 中的4 个事务，统计c 2 中每个候选项集的支持度，然后和最小支持 度n l i n s u p p o r t 进行比较，生成历。候选项集c 3 是由上2 生成的，要求自连接 的两个最大2 项集中第个项目相同，在厶中满足该条件有 b ，c ， b ， e ，这两个集合经过j o i n 步骤后，产生集合 b ，c ，e ) ，在p r u n e 步骤中， 测试 b ，c ，e ) 的子集 c ，e ) ， b ，c ， b ，e 是否在如中，由厶可知 c ， e ，毋，c ， b ，e 本身就是最大2 项，即 b ，c ，e 的子集都是最大项 目集，那么 b ，c ，e 为候选3 项集。然后搜索数据库中所有事务记录，生 。 1 0 哈尔滨工程大学硕士学位论文 成3 - 项集厶，此时，从局中不能再生成候选4 项集，a p r i o r i 算法结束，执 行过程如表2 2 、表2 3 和表2 4 所示 表2 1 一个简单事务数据库的模型 币d项 la c d 2b c e 3 ，a b c e 0 0 4b e 从a p f i o r i 算法的执行过程可以发现算法存在如下的缺点：在每一次生成 候选项目集时均需要扫描数据库d ，但由于通常用于关联规则挖掘的数据库 的规模都是非常大的，这样就增加了额外的开销，影响算法的效率“ 表2 2a p r i o r i 算法针对数据库d 的第一次迭代 1 项集c 1 1 项集计数 s 【1大l - 项集l l计数 s 【吲 a a ) 25 0 a 2 5 0 b t b ) 37 5 b 3 7 5 c c l2 5 c 37 5 d ( d 37 5 e e 37 5 e ) 37 5 生成阶段计算阶段选择阶段 表2 3 a p r i o r i 算法针对数据库d 的第二次迭代 2 项集c 2 2 - 项集计数 s 【1 大2 项集l 口 计数 s 【1 a ，b a ，b l2 5 a ，c a ，c 25 0 a ，c 25 0 a ，e a ，e ) l2 5 b ，c b ，c 25 0 b ，c 2 5 0 b ，e b 。e 37 5 b ，e 37 5 c ，e ) c ，e 2 5 0 c ，e l 2 5 0 生成阶段 计算阶段选择阶段 哈尔滨工程大学硕士学位论文 表2 4a p r i o r i 算法针对数据库d 的第三次迭代 3 项集c 33 项集计数 s 惭】大3 项集b 计数 s 【】 b ，c ，e b ，c ，e ) 25 0 b ，c ，e 2 5 0 生成阶段计算阶段选择阶段 2 2 2f p - g r o w t h 算法 在对深度优先数据挖掘算法的研究工作中，h a l l 等人提出了f p - g r o w t h 即频繁模式增长的算法m 该算法通过扫描数据库得到频繁项的集合f 以及 各项的支持度，并按支持度大小降序捧列构成频繁项目的列表工创建f p - t r e e 的根节点并标识为n u l l ，对数据库d 中的每一个事务t k ，按工中的次序对“ 中的频繁项捧序，设珏中捧序后的频繁项列表为驴旧，这里p 是第一个元素， p 是保留列表。接着调用函数i n s e r t _ t r e e ( p i 用，r ) ，如果树r 有一个子节点 且n i t e mn a 加e = p i t e mn 锄c ，就将节点计数加l ；否则就创建一个新节 点，设计数为1 ，它的父节点连接到l 节点连接到同名的节点连接结构上 如果p 是非空的，就递归调用i n s e r tt r e e ( ，) 由于将数据库内容进行了 压缩，并且将频繁项写入f p - t m e 结构时保留了项集问的相联信息，故可将求 解频繁项集的问题，转化为递归地找出最短频繁模式并连接其后缀构成长频 繁模式的问题。下面给出f p - g r o w t h 算法盯m ： p f o c e d u r ef p - g r o w t h ( 1 慨，q ) ( 1 )i f t r e e 包含一个单一路径pt h e e ( 2 )f o r e a c h 路径p 中节点组合( 记为b ) ( 3 )生成模式buo ，拥有支持度为b 节点中的最小支持度 ( 4 )e l s ef o re a c h 树的头列表节点a i ( 5 )生成模式b = oi ub 且s u p p o r t = oi s i 呻o n ( 6 )构成8 的条件模式基和6 的条件f p - t r e et r e eb ( 7 ) i f t r e e # 西t b e n ( 8 ) c a l lf p - g r o w t h ( t r e e8 ，b ) 将长度为l 的频繁模式称为初始后缀模式。条件模式基是一个子数据集， 哈尔滨工程大学硕士学位论文 由f p - t r e e 中与后缀模式一起出现的前缀路径集组成从初始后缀模式开始， 构造它的条件模式基。然后构造f p - t r e e ，并递归地在该树上进行挖掘。通过 后缀模式与由f p - t r e e 生成的频繁模式连接实现模式增长。为便于对树的遍历 可以创建一个项头表，使每个项通过一个节点链指向它在树中的出现位置。 挖掘f p - t r e e 的主要步骤： ( 1 ) 为f p - t r e e 中的每个节点生成条件模式基； ( 2 ) 用条件模式基构造对应的f p - l r e e ； ( 3 ) 递归构造f p - u 呛e ，同时增长其包含的频繁项集。如果条件f p - t r e e 只包含一个路径，则直接生成所包含的频繁项集。 下面以表2 5 所示事务数据库d 为例来介绍f p g r o w t h 算法的执行过程， 规定其最小支持度m m s u p p o f t 为3 。 表2 5 事务数据库d 耵d 项集 o l f ，a c ，d ，g ，i ，m ，p 0 2 a ，b ，c ，f i 。m ，o ， 0 3 b ，f th ，j ，o 0 4 b ，c tk ，s ，p 0 5 a ，f ，c ，e ，i ，p ，m ，1 1 第一步，扫描一次数据库d ，得到频繁项( 在数据库d 中出现3 次或3 次以上) 的列表工这些频繁项集其支持度分别为： 扣 ( f 4 ) ，( c ，4 ) ，c a ，3 ) ，( b ，3 ) ，( m ，3 ) ，( p ，3 ) 频繁项集按支持度计数的递减顺序进行捧序。这样的捧序顺序很重要， 因为f i - t r e e 中的每一个路径也是依照这样的顺序。 、 第二步，创建树的根( r ) c ) t ) ，第二次扫描数据库d 。对第一个事务的 扫描得到树的第一个分枝： ( f ，1 ) ，( c ，1 ) ，c a ，1 ) ， m ，1 ) ，( p ，1 ) 。 只有那些在频繁项集三列表中的项才会被选中分枝中节点的计数( 都是1 ) 代表了树中该节点项所出现的次数，所以在第一个分枝后所有的节点计数都 为1 节点的排列顺序和样本中的并不一样，而是按照频繁项集工的顺序进 r o o t i广、 ， 一 i 2 。人。i c。 “l 3h 1 ，b i 1 c ，z+ l 羔2了入r 1 4 ， i上! r 一，、 i，。 m ti b ，i i “： ij r 6 专一。7 1 | 哈尔滨工程大学硕士学位论文 2 ) ，( p ，2 ) 和 ( c ，1 ) ，( b ，1 ) ，( p ，1 ) ，其中包括p 的样本为 ( f 2 ) ， ( c ，2 ) ，( a ，2 ) ，( m ，2 ) ，( p ，2 ) ) 和 ( c ，1 ) ，( b ，i ) ，( p ，1 ) 。给定 的阙值( 3 ) 只适用于 ( c ，3 ) ，( p ，3 ) ，或者简写为 c ，p 。所有包含p 的其它项集的支持度都小于阈值。 频繁项集的下一个子集为那些包含m 但不包含p 的项集。f p - t r e e 识别的 路径有： ( f ，4 ) ，( c 3 ) ，( a ，3 ) ，( m ，2 ) 和 ( f ，4 ) ，( c ，3 ) ，( a ，3 ) ， ( b ，1 ) ，( m ，1 ) ，或者相应的样本为 ( f ，2 ) ，( c ，2 ) ，( a ，2 ) ，( m ，2 ) 和 ( f 1 ) ，( c ，1 ) ，( a ，i ) ，( b ，1 ) ，( m ，1 ) 。分析样本，可以得到满 足阀值的频繁项集为 ( f ，3 ) ，( c ：3 ) ，( a ，3 ) ，( m ，3 ) ，或者简写为 f ， c ，a ，m l 。 用同样的方法得到第3 到第6 个子集，另外再挖掘出满足阈值的频繁项 集。这些项集为 f ，c ，a 和 f ，c ) ，但它们已经是频繁项集 f c ，a ，m 的 子集。因此，f p - g r o w t h 算法的最后一步得到频繁项集的集合，在本例中就是 “c ，p ， f ，c ，a ，m 。 实验表明f p g r o w t h 算法要l 七a p r i o r i 算法大约快一个数量级。f p - g r o w t h 算法还增加了一些优化技术，并且在约束条件下挖掘捧序和模式时还存在其 它版本的算法。 2 2 3 几种关联规则挖掘算法 虽然a p r i o r i 算法自身已经进行了一定的优化，但是在实际的应用中，还 是存在不令人满意的地方，于是相继出现了一些优化算法在本节中将介绍 几种在关联规则挖掘中常用的算法。 1 i s 算法 早期的a 1 s 算法利用了数据库的多趟扫描，扫描的次数是最长大项集的 长度。候选大项集是在数据库扫描时产生并同时计数的读入一个事务，然 后找出该事务所包含的所有在上一次扫描中得出的大项集，利用该事务中其 它项扩展这些大项集得到候选项集。该算法的缺点是产生的候选项集太大“- 2 距w 算法 s e t m 算法也是较旱提出的关联规则挖掘算法w 。执行算法时，首先对数 5 哈尔滨工程大学硕士学位论文 据库进行扫描，生成候选集并计数。读取一个事务来判定上次扫描找到的频 繁集中有哪些包含在此事务中。通过用此事务中的其它项目来扩展这些频繁 集，从而得到新的候选项集。 3 p r i o r i t i d 算法和 p r i o r i h y b r i d 算法 a p f i o r i t i d 是a p r i o r i 算法的一种改进算法。a p r i o f i h y b r i d 算法是a p r i o d 和a p r i o r i t i d 算法的结合，当候选事务数据库d 不能完全容纳于内存时用 a p r i o d 算法，当内存能够完全容纳候选事务数据库d 时，则用a p r i o r i t i d 算 法i ”。 4 d r i p 算法 d h p 算法由p a r k 等人在1 9 9 5 年提出m 由于寻找频繁项集的主要计算 是在生成频繁2 项集三2 上，p a r k 引入散列技术改进了产生频繁项集的方法。 其基本思想是：首先扫描事务数据库，对k 维的高频数据项集厶中的数据项 进行计数，同时自己连接生成每个事务的所有h l 维的数据项集，根据构造 的散列函数把它散列到相应的散列表中，并计数。这样，相同的抖l 维数据 项被散列函数散列到同一个存储空间当中去为避免冲突，与每个存储空间 对应着的计数器只需简单加l 即可。h a s h 散列技术在第一遍扫描数据库时， 因为要构造h a s h 表，所以速度会比a p r i o r i 慢，但是以后的计算由于占用少 得多的内存，速度就比a p r i o r i 快了总体来说h a s h 散列技术的应用使算法 提速很多。 5 p a r t i t i o n 算法 p a r t i t i o n 算法是由s a v a s e r e 等提出的一种基于划分的算法。这种算法