（计算机软件与理论专业论文）基于集群环境的并行频繁子图挖掘算法pgminer研究.pdf

兰州大学硕士学位论文基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 摘要 从大型数据库中挖掘频繁模式是数据挖掘研究的一类基本问题，也是该领域 最具挑战性的一个研究热点。其中频繁子图挖掘旨在解决结构化模式挖掘问题， 诸如化学，生物学，w w w 应用等领域的关联性问题。由于实际应用中具有数据规 模大，抽象出的图结构复杂等特性使得高性能的子图挖掘算法一直是该领域研究 中的一个难点。本文首先提出了并行频繁项集挖掘算法h p f p m i n e r ，并以此为 基础，提出一个高效的并行频繁子图挖掘算法p g m i n e r 。论文主要内容包括： 1 、并行频繁项集挖掘算法h p f p - m i n e r h p f p m i n e r 为了能够在并行处理中生成完备且不冗余的结果集提出了两个 数据结构h p f p 树和h p f p f o r e s t 来压缩存储频繁项集信息，与f p 树的根为 “n u t t 不同的是，每一颗h p f p 树都独立完整的表述了当前数据库中以其根节 点为前缀的模式，h p f p 树中反向表示父节点到子节点的指针。同时，所有h p f p 树通过指针链接形成h p f p - f o r e s t ，到执行时再由主节点根据从节点的多少向各 处理节点分发h p f p 树，这使得算法具有更高的可扩展性，并且进一步也容易控 制各处理节点的负载。 2 、并行频繁子图算法p g m i n e r 设计与实现 在这部分，我们提出一种新的并行频繁子图挖掘算法p g m i n e r 。该算法以尽 可能大的并行粒度将频繁子图挖掘算法中时间复杂度最高的子图同构判断过程 分发到多台处理器上并行处理，使得算法的执行时间随着处理节点的线性增加而 线性减少。该算法的主要策略是，首先将整个挖掘过程分成两部分，由主处理节 点来生成频繁子树集，接着将生成的子树集分发到从处理节点。其次，将频繁子 图边扩展及同构判断这部分频繁子图挖掘算法中时间复杂度最高的部分并行处 理。经过算法分析得出，本文提出的算法时间复杂度为o ( 2 n n z k ) ，其中n 是图 集中的频繁边数，k 是用于并行计算的从节点个数( 总节点个数为k + 1 ) 。本文分 析了该算法的时间复杂度，并在不同的真实和模拟数据集上验证了算法的可行 性。 关键词：数据挖掘，关联规则挖掘，频繁子图挖掘，并行关联规则挖掘 兰州大学硕士学位论文基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 a b s t r a c t t h es t u d yo fm i n i n gf r e q u e n tp a t t e r n si nl a r g ed a t a b a s eh a sb e e nf o c u s e da l l a l o n gi nd a t am i n i n gf i e l d s a n df r e q u e n ts u b g r a p hm i n i n ga i m sa tr e s o l v i n gt h e s 仃u 曲珊lp a t t e r nm i n i n gi s s u e s ，s u c ha sc h e m i s t r y , b i o l o g y , w w wa p p l i c a t i o n sa n d o t h e rr e l a t e dp r o b l e m s b e c a u s eo ft h el a r g es c a l ea n dc o m p l e xf e a t u r e so ft h eg r a p h a b s t r a c t e df r o mp r a c t i c a la p p l i c a t i o n s ，t h er e s e a r c h e sf o rh i g h p e r f o r m a n c ef r e q u e n t s u b g r a p hm i n i n ga l g o r i t h m sh a v eb e e nar e s e a r c hi s s u e t h em a i nc o n t e n to ft h i s t h e s i si sp r o p o s e dap a r a l l e lf r e q u e n ti t e m s e t sm i n i n ga l g o r i t h m ：h p f p m i n e r , t h e n d e s c r i b e sap a r a l l e l f r e q u e n ts u b g r a p h sm i n i n ga l g o r i t h m ：p g - m i n e r t h em a i n c o n t e n t sc a nb es t a t e da sf o l l o w 1 p a r a l l e lf r e q u e n ti t e m s e t sm i n i n ga l g o r i t h m ：h p f p - m i n e r i nt h i ss e c t i o nw ep r e s e n t e dt h eh p f p - m i n e ra l g o r i t h m i no r d e rt og e n e r a t e c o m p l e t ea n dn o n r e d u n d a n tr e s u l ts e t s ，i nt h i sa l g o r i t h mw ep r o p o s e dt w op a r a l l e l e n v i r o n m e n t b a s e dd a t as t r u c t u r e sh p f p t r e e sa n dh p f p f o r e s tw h i c hw e r eu s e dt o c o m p r e s sa n ds t o r et h ei n f o r m a t i o no ft h ef r e q u e n ti t e m s e t s i nc o n t r a s tt of pt r e e ，t h e r o o to fh p f pt r e ei sn o ta “n u l l ”b u ta l li t e mt oi d e n t i f yt h es p e c i f i ct r e e ，a n dh p f p t r e e si n d e x e sa r ef r o mc h i l d r e nt op a r e n t w el i n k e da l lo ft h eh p f pt r e e sw i t ha p o i n t e rl i s tt oc o n s t i t u t eah p f p f o r e s t b yd o i n gs o ，t h em a s t e rn o d ec a nd i s p a t c h e d h p f pt r e et od i s t r i b u t e dp r o c e s s i n gn o d e sd u r i n ge x e c u t i o np h a s e ，w h i c hm a k et h e a l g o r i t h mm o r ef l e x i b l ea n de a s i e rt oc o n t r o lt h el o a db a l a n c eo fa l lp r o c e s s i n gn o d e s 2 p a r a l l e lf r e x l u c n ts u b g r a p h sm i n i n ga l g o r i t h m ：p g m i n e r i nt h i ss e c t i o n ，w ep r o p o s e dan e w p a r a l l e lf r e q u e n ts u b g r a p h sm i n i n ga l g o r i t h m p g m i n e r t h ea l g o r i t h md i s p a t c ht h em o s tc o m p l e x i t yo fs u b - g r a p hi s o m o r p h i s mt o d i f f e r e n tp r o c e s s i n gn o d e s ，w h i c hm a d et h ea l g o r i t h m se x e c u t i o nt i m ed e c r e a s e c o n s i d e r a b l y t h em a i ns t r a t e g yo ft h ea l g o r i t h mc o n t a i n s t w os t e p s f i r s t l y , w e d i v i d e dt h em i n i n gp r o c e s si n t ot w op a r t s o n ep a r ti sg e n e r a t et h ef r e q u e n ts u b t r e e s e t sb yt h em a s t e rn o d e ，a n o t h e rp a r td i s p a t c h e ss u b t r e es e t st od i f f e r e n tp r o c e s s i n g 兰州大学硕士学位论文 基于集群环境的并行频繁子图挖掘算法p g - m i n e r 研究 n o d e s s e c o n d l y , w ep r o c e s s e d t h e e d g ee x p a n s i o na n df r e q u e n ts u b - g r a p h i s o m o r p h i s mw h i c ha r et h em o s tc o m p l e x i t yp a r t so ff r e q u e n ts u b g r a p h sm i n i n gi n p a r a l l e l a f t e ra l g o r i t h ma n a l y s i s ，w ec o n c l u d e dt h a to u ra l g o r i t h m st i m ec o m p l e x i t y i s o ( 2 n 掌n 2 k ) ，w h e r en i st h en u m b e ro ff r e q u e n te d g e si ng r a p hs e t s ，a n dki st h e p a r a l l e l e dp r o c e s s i n gn o d en u m b e r ( t o t a ln u m b e ro fn o d e si sk + 1 ) f i n a l l y , w e v a l i d a t e dt h ef e a s i b i l i t yo ft h ea l g o r i t h mi nd i f f e r e n tr e a la n ds y n t h e t i cd a t as e t s k e y w 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 sm i n i n g ，f r e q u e n ts u b g r a p h sm i n i n g , p a r a l l e la s s o c i a t i o nr u l e sm i n i n g 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下 独立进行研究所取得的成果。学位论文中凡引用他人已经发表 或未发表的成果、数据、观点等，均已明确注明出处。除文中 已经注明引用的内容外，不包含任何其他个人或集体已经发表或 撰写过的科研成果。对本文的研究成果做出重要贡献的个人和集 体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：靼避虹 日期：尘0 7 0 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产 权归属兰州大学。本人完全了解兰州大学有关保存、使用学位论 文的规定，同意学校保存或向国家有关部门或机构送交论文的纸 质版和电子版，允许论文被查阅和借阅；本人授权兰州大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以 采用任何复制手段保存和汇编本学位论文。本人离校后发表、使 用学位论文或与该论文直接相关的学术论文或成果时，第一署名 单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：弋& 避狃l 导师签名： 日期：型叫 兰州大学硕士学位论文基于集群环境的并行频繁子图挖掘算法p g - m i n e r 研究 第一章绪论 本章首先介绍了研究工作的背景，以“信息爆炸”为线索，突出了数据挖掘 这一学科的重要意义，接着介绍了数据挖掘的任务：分类、聚类、频繁模式与序 列模式的发现、预测和离群点的检测。在1 2 节中重点介绍了频繁子图挖掘的发 展、现状及该领域所面临的挑战。面对这样的挑战与问题，1 3 节阐述了本文研 究工作的内容与意义。1 4 节对本论文的组织结构做了一个简单的介绍。 1 1 研究工作的背景及意义 2 1 世纪是一个信息时代，计算机已经广泛应用于各行各业乃至各家各户。 而通常人们对计算机的应用都以获取数据和保存数据为目的，用于数据处理的并 不多。这样不断积累的信息量产生了“信息爆炸 ，人们面对着网络上庞大的信 息不知所措一- - - 2 1 世纪信息综合症。 随着计算机对数据的生成、收集、存储和处理能力的大大提高，数据量与日 俱增，数据库的容量将变得无比庞大，但是庞大的数据库里的信息只有一小部分 有用，大部分毫无价值，传统的数据分析工具对海量数据的处理能力远远不能满 足人们的实际需求，所以如何从庞大的数据库中提取有用信息，便是信息时代必 须需要解决的问题。在这种情况下数据挖掘( d a t am i n i n g ) 技术应运而生，数 据挖掘就是为了解决拥有大量数据却贫乏有用知识，进而从中提取有价值的信息 而提出的个学科。我们可以把数据挖掘定义为，从数据库中大量的数据中提取 未知的、潜在的、有价值的数据以及数据与数据之间潜在的关联。 数据挖掘技术及数据挖掘算法研究是目前国际上数据库和信息决策领域当 中最前沿的研究方向之一。该技术不但作为一种学术科研主题，更重要的是作为 一种商业决策技术被广泛应用于各种商业行为中。数据挖掘的主要任务有：( 1 ) 分类，为了方便描述对象，按照对象的属性和特征把对象分成不同的类。例如学 校根据以前教学成果数据把学生分成不同的成绩段从而确定一个最佳的教学方 案。( 2 ) 聚类，通过分析对象内在的抽象的联系，从而利用这些联系把对象分成 不同的簇，最终使簇内的对象相似度尽量最高，簇间对象相似度尽量最小。( 3 ) 兰州大学硕士学位论文基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 频繁模式与序列模式的发现，通过对其中频繁模式的发现从而确定事务之间的关 联程度。如在零售业中购买香烟的人，其中有多少人同时会去购买打火机，这个 规则的关联程度是通过支持度与置信度去分析来得出的。而序列模式的挖掘是挖 掘频繁出现的有序事件或子序列，与关联规则不同之处是序列是一种纵向的联 系。( 4 ) 预测，分析对象的发展规律，对未来发展的趋势进行预见。例如技术预 测是依据当前科技水平和各种影响因素对未来科学技术发展做出估计与分析，从 而确定科学发展的方向。( 5 ) 偏差检测( 离群点检测) ，通过对离群点的检测可 以发现庞大数据集中与数据的一般行为或模型不一致的数据，从而揭示产生这种 现象的原因。例如：对银行的5 0 万笔交易统计中有2 0 例的欺诈行为，这2 0 例 的交易相对于正常的交易来说就可以当成是离群点。银行可以通过对这2 0 例交 易产生的因素进行分析从而减少风险。 频繁模式挖掘作为数据挖掘的重要任务之一，被广泛应用在相关性分析 1 、 序列模式 2 、关联规则 3 4 5 6 、最长模式 7 、多维模式 8 9 、显露模 式 1 0 1 1 、因果关系 1 2 、局部周期性 1 3 以及频繁子图挖掘等领域的研究当 中，而且它的应用势必会越来越广泛。 传统的基于属性一一值的数据挖掘方法对于现实世界中普遍存在的关系数 据库和复杂的结构化对象而言，存在明显的缺陷。因此，各种数据的多关系数据 挖掘研究具有重大的理论意义与应用价值。在实际生活中，我们可以把许多领域 的数据抽象为图，如在化学中一个物质的化学结构就可以被抽象为无向标号图， 其中图的节点对应着分子而边则可以表示原子间的化合键。我们知道图的拓扑结 构是数学中最根本的结构，它与逻辑语言有非常紧密的联系，预计图的挖掘将对 数据挖掘和机器学习的新发展做出更多的贡献。此外，图的挖掘有很深的实际应 用潜力，因为基于图结构的数据广泛存在于各种实际领域中，如w e b 数据挖掘、 生物信息学、药物研制、化学、材料学、通信网络、集成电路的布局布线、国防、 计算机视觉、文本检索等领域都大量使用到了图形数据，图作为描述它们的数据 结构，将会在这些应用领域的建模中起到至关重要的作用。 图挖掘可以粗略地分为频繁子图挖掘、图聚类与图分类。无论是在图聚类 还是图分类中，对频繁子图的分析都是必不可少的。 频繁子图( 频繁子结构) 就是为了进一步对具有图数据结构的图集合进行区 2 兰州大学硕士学位论文基于集群环境的并行频繁子图挖掘算法p g - m i n e r 研究 分、特征提取、分类和聚类分析从而发现这些图结构中基本的子结构而提出的。 通过对这些频繁子结构的分析就可以知道这些图集合之间的联系与区别，甚至我 们可以通过对挖掘出的频繁子结构的研究去发现一些未知的，有趣的与已知图结 构相关的一些潜藏在其它模型里面的频繁出现的图结构。如通过对已有的生物分 子结构与未知的生物结构的研究，来确定未知生物分子与已知生物分子之间的联 系与区别。例如在p ，r e ( p r e d i c t i v et o x i c o l o g ye v a l u a t i o nc h a l l e n g e ) 项目中 找到频繁出现的而且与已有的有毒物质具有相同子结构的物质，这样就可以发现 新的对人体有害的物质。因此，对基于图的频繁子图挖掘的算法研究是非常必要 的，而且具有很好的实际应用价值。 1 2 频繁子图挖掘的发展现状及遇到的挑战 1 2 1 频繁子图挖掘的发展现状 频繁子图挖掘的研究工作始于1 9 9 4 年，l b c o o k 等人 1 4 提出了著名的采 用最小描述长度压缩原始图，并利用启发式的搜索策略挖掘频繁子图的子图挖掘 算法s u b d u e ，但是该算法不能完全保证结果集的完整性。同时该算法使用了模 糊计算的方法，从而使挖掘效率得以提高，但是该算法的局限性是其目标主要针 对生物应用领域的特殊问题。后来s u b d u e 还扩展成为图分类算法，称为 s u b d u e c l 1 5 ，在s u b d u e c l 中不再采用最小描述长度，而是采用基于子图置信度 的启发式方法。2 0 0 5 年，l d e s h p a n d e 等人 1 6 同样提出了化学化合物分类中挖 掘频繁子图的算法。1 9 9 4 年，k y o s h i d a 等人 1 7 提出了一个类似s u b d u e 算法 的子图挖掘算法，g b i 算法，但该算法采用了不同的启发式搜索策略。此后，又 有各种不同的频繁子图挖掘算法被提出来，比较有影响的有m k u r a m o c h i 等人 2 2 提出一个频繁子图挖掘算法f s g 算法，该算法同样是采用了a p r i o r i 思想， 但是不同之处是该算法通过增量方式逐层挖掘频繁子图，在算法性能与效率上 f s g 要优于a c g m 算法。w e r n i c k e 等 2 3 提出的e s u 算法，也是挖掘频繁子图 的。2 0 0 5 年，m k u r a m o c h i 等 2 4 又提出了一个新的子图挖掘问题，即在1 个 稀疏的超大规模的图中挖掘不相关的子图模式，针对这个问题又提出了两个分别 采用宽度优先遍历与深度优先遍历方法挖掘子图的算法h s i g r a m 和v s i g r a m 。其 兰州大学硕士学位论文 基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 中一个重要的成果是x y a n 等人 2 5 提出了一个新颖的深度优先搜索图空间的 挖掘频繁子图方法，同时在该算法的基础上提出了频繁子图挖掘算法g s p a n 。 2 0 0 3 年，x y a n 等人 2 6 又在g s p a n 算法的基础上，进步提出了挖掘频繁闭合 子图的算法c l o s e g r a p h ，频繁闭合子图集是频繁子图集的压缩表达方式。2 0 0 3 上，j h u a n 等人 2 7 提出了一个新的子图扩展策略，在这个算法的基础上形成 了频繁子图挖掘算法f f s m ，该算法是基于f p - g r o w t h 思想的算法，使得频繁子 图挖掘算法得到进一步的发展；后来对f f s m 算法进行改进，得到针对最大频繁 子图挖掘的s p i n 2 8 算法。2 0 0 4 年之后，s w e r n i c k e 等入对挖掘子图的挖掘也 做了大量的研究工作 2 9 3 0 。 除了上述这些子图模式挖掘的通用算法外，研究人员还提出了大量运用于实 际问题的、带有约束的子图模式挖掘算法 3 1 - 3 3 。 1 2 2 频繁子图挖掘的挑战 频繁予图挖掘与技术相对比较成熟的频繁模式挖掘相比( 例如文本型频繁模 式挖掘) ，图结构数据所包含的信息比一般的数据类型的数据量更大，其数据结构 比线性表和树更为复杂。在图形结构中，结点之间的关系是任意的，任意两个数 据元素之间都可能相关。尽管其结构很复杂，但是由于基于图的应用越来越广泛， 其已经渗入到诸如语言学、逻辑学、物理、化学、计算机科学及数学的这些分支 学科中。例如，目前复杂网络的研究都只是考虑了节点等的分布形式，并提出了 b a 模型来研究节点如何加入网络中的演化过程，而这些对网络分析来说是远远 不够的，如果将频繁子图挖掘算法和复杂网络分析结合起来，通过对频繁子图进 行简化定义，比如只考虑全连通子图( c l i q u e ) ，n c l i q u e ，n c l a n s ，k - p l e x e s ， n - c o r e s 等，并结合复杂网络分析的方法来研究网络从而对网络进行分析，一定 会挖掘出很多有意义的结果。 随着大量结构化数据分析与处理需求的不断增长，现存的频繁子图挖掘算 法对大数据量的应用来说，大部分速度都太慢，因此，应用不是很广泛，但是频 繁子图挖掘是数据挖掘中最具有前途的研究方向之一。所以尽管在研究的过程 中有许多困难，我们也必须克服种种困难对频繁子图的挖掘进行研究。对原始的 图数据进行频繁子图挖掘难度较大，同时通过边或节点添加生成的候选子图集中 4 兰州大学硕士学位论文基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 往往存在大量的冗余，子图同构已被证明是n p 问题等都增加了候选子图支持度 计算的复杂性，因此一般的文本数据挖掘方法不再适用于频繁子图挖掘，必须结 合图数据格式的特点寻求新的挖掘算法。 在一般意义下，由于没有利用任何先验信息，频繁子图的搜索工作量很大。 现存的频繁子图挖掘算法对大数据量的挖掘任务来说，大部分速度都太慢，而且 效率低下，因此，应用不是很广泛。研究出算法效率高，执行速度快的频繁子图 挖掘算法是目前炙手可热的一个话题而且其任务相当艰巨。 1 3 本文的研究内容及意义 本文研究内容以如何设计并行频繁子图挖掘算法p g m i n e r 为主，围绕两个 关键字并行和频繁子图挖掘展开研究，首先介绍了并行计算理论和并行频繁项集 挖掘算法h p f p - m i n e r ，其后以此为基础，提出并详细阐述了并行频繁子图挖掘 算法p g - m i n e r ： 1 、并行计算理论及并行频繁项集挖掘算法h p f p - m i n e r 在这部分我们首先介绍了并行计算的概念，随后介绍了如何在普通p c 上搭 建m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 集群环境，为后文的实验环境做准备。之 后对m p i 编程的通信模式和最常用到的函数接口做了简单介绍。后半部分介绍了 并行频繁项集挖掘算法h p f p m i n e r ，该算法中我们提出了两个适用于并行环境 的数据结构h p f p 树和h p f p f o r e s t ，与f p 树不同，h p f p 树的根不是“n u l l ， 而是一个用来标识这一棵树的具体的项。为了方便并行处理，每一颗h p f p 树都 独立完整的表述当前数据库中以其根节点为前缀的模式。所有h p f p 树通过指针 链接就形成了h p f p f o r e s t ，在执行过程中由主节点根据从节点的多少向各处理 节点分发h p f p 树，这使得算法具有更高的可扩展性，并且进一步也容易控制各 处理节点的负载。 2 、并行频繁子图算法p g m i n e r 设计与实现 在这部分，我们在论文前半部分的基础上提出一种新的应用于频繁子图的并 行挖掘算法p g - m i n e r 。该算法延续了h p f p - m i n e r 的并行策略，以尽可能大的并 行粒度将频繁子图挖掘算法中时间复杂度最高的子图同构判断过程分发到多台 处理器上并行处理，使得算法的执行时阳j 随处理节点的线性增加而线性减少。该 5 兰州大学硕士学位论文基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 算法将整个挖掘过程分成两部分，第一部分由主处理节点来生成频繁予树集，然 后将生成的子树集分发到别的从处理节点。第二部分将频繁子图边扩展及同构判 断这部分频繁子图挖掘算法中时间复杂度最高的部分并行处理。经过算法分析得 出，本文提出的算法时间复杂度为o ( 2 n * n 2 k ) ，其中n 是图集中的频繁边数，k 是用于并行计算的从节点个数( 总节点个数为k + 1 ) 。论文在最后分析并验证了 该算法的可行性。 1 4 本文的组织结构 第一章绪论。这部分介绍了论文的研究背景及意义，频繁子图挖掘的发展 现状及在研究的过程中遇到的问题。最后介绍了本文重点研究的内容及意义。 第二章关联规则挖掘理论及算法策略。主要阐述了关联规则挖掘的理论知 识及几个重要的算法策略。在关联规则挖掘理论方面先由购物篮的例子引出了频 繁项集及关联规则的生成。在算法策略方面重要介绍了基于a p r i o r i 的频繁子图 挖掘算法和基于模式增长的频繁子图挖掘算法。 第三章并行计算概论、集群环境搭建及并行关联规则挖掘研究现状。并行 计算概论部分讲述了并行体系结构和并行算法设计的一些准则等基本理论知识； 并行编程模型部分写了数据并行、共享变量及消息传递三种模型并对其进行比 较；m p i 并行集群环境搭建主要介绍了集群环境在普通p c 上是如何实现的。最 后介绍频繁子图挖掘在并行化方面研究的进展情况，重点介绍了i d m 实验室及本 文作者之前在基于f p - g r o w t h 挖掘算法方面的研究成果及在并行关联规则挖掘 方面取得的进展。 第四章并行频繁子图挖掘算法p g - m i n e r 。在深入研究f p g r o w t h 模式及并 行计算之后，结合在这些方面取得的成果提出并行频繁子图挖掘算法p g - m i n e r ， 在本章详细介绍了p g - m i n e r 的并行策略并分析了该算法的时间效率复杂度，最 后选取数据挖掘研究网站公认的测试数据对该算法进行实验验证。 第五章总结及下一步展望。总结了本文的工作，给出了通过并行p g m i n e r 算法对频繁子图挖掘所得出的结论。最后对下一步需要做的工作做了展望。 6 兰州大学硕士学位论文 基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 第二章关联规则挖掘理论及算法策略 本章主要内容是关联规则挖掘的一些理论知识以及频繁子图挖掘的一些经 典算法。2 1 节首先介绍了相关的频繁子图挖掘的基础知识和相关的概念，如置 信度、支持度、强关联规则、频繁项集。2 2 节描述了关联规则生成的两个过程： 频繁项集的生成与关联规则的生成。在频繁项集生成这一部分着重讲了基于 a p r i o r i 思想的产生候选的频繁项集生成算法与基于模式增长的不产生候选的 印g r o w t h 算法。2 3 节首先对频繁子图的概念做了解释，再重点阐述了两种基 于a p r i o r i 和基于模式增长的频繁子图的挖掘算法。 2 1 关联规则挖掘的基本概念 2 1 1 购物篮分析 当今社会中购物可以看成是一种经济和休闲活动，各种各样的人都在参与 这一项活动。为此零售商就会绞尽脑汁地为自己的商场设计一个很好的商品位置 布局或一个很好的营销策略，从而激发消费者尽可能多地购买本商场的商品。比 如，零售商在一段时间里可以对顾客所购买的商品进行统计，经过一段时间后， 零售商可能会发现购买牛奶的顾客当中有绝大一部分人购买面包，购买钢笔的顾 客当中绝大部分人购买墨水。这样零售商就会根据顾客放入“购物篮 的 商品之间的关联程度去摆放商品的位置或者确定营销策略。 通常有以下策略：一是将顾客经常同时购买的商品放置在比较靠近的位置， 形成一种类似打包销售的策略，从而促进消费者对有关联商品的购买，如将牛奶 与面包放在相临的位置。二是将顾客经常购买的商品摆放在距离比较远的地方， 这样顾客在寻找商品的过程中，可以激发对其他商品的购买兴趣。比如将钢笔和 墨水放在商场的两端，这样顾客购买了钢笔在寻找墨水的过程中可能还会购买其 它的商品，如记录本等。三是降低经常同时购买商品中的某些商品的价格，进一 步提高顾客购买相关商品的兴趣，促进消费。这样零售商就可以从中得到更多的 利润。四是将时间纬度也加入考虑，根据“购物篮分析的结果，进行主动有目 7 兰州大学硕士学位论文基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 的的推销活动，比如对买电脑的顾客在一段时间后推销杀毒软件，对买自行车的 顾客在一个月后推销打气筒等。 我们对以上的问题用以下的数学思维来表达： 假如有一个集合a = 弘1 ，a 2 ，a 3 ，a n ) ，其中a i ( j = n ) 表示商场里有商品，则a 就是商品的集合，每种商品我们可以用一个布尔变量表示，1 表示购物篮中有该 商品，0 表示购物篮中没有该商品。这样一个购物篮就可以用商品相对应的布尔 向量表示。如有一个商品序列( p 1 ，p 2 ，p 3 ，p 4 ) ，其对应的布尔向量为( 11 0 0 ) ， 则表明该购物篮中有商品p 1 和p 2 ，而没有p 3 和p 4 。通过对购物篮的分析我们 就可以获取顾客购买商品的习惯与模式。这种模式我们可以用一个关联规则来表 示。如果购买牛奶的同时也可能购买面包可以用以下的关联规则表示： m i t k jb r e a d 【s u p p o r t = 4 ，c o n f i d e n c e = 7 0 】( 2 - 1 ) 其中s u p p o r t 和c o n f i d e n c e 表示支持度与置信度，它是关联规则兴趣度的 两个度量值，在接下来的内容中我们会介绍支持度与置信度的概念。( 2 1 ) 式表 示在所有购买的事务中同时购买牛奶和面包的概率是4 ，而7 0 则表示在购买 牛奶的所有事务中，同时购买面包的占7 0 。如果支持度与置信度均大于或等于 最小支持度阈值与最小置信度阈值时( 最小支持度阈值与最小置信度阈值是由该 领域的专家或者使用该系统的用户根据以往经验及已有理论规定的) ，则这些关 联是有用的信息。 2 1 2 频繁项集及相关概念 1 置信度( c o n f i d e n c e ) 设集合a = a l ，a ：，a 。，a 。) 1 1 之1 n n ) 是项的集合，该项集里有n 个 项称为n 项集，事务集t = t 。，t ：，l ) ( m 2 n ) ，其中t j 是a 集合的一个子集， 称为项集，当且仅当t j a ，t j 都有一个标识符，称作t i d 。对于一个关联规则 t m 曹t n ，其中t m n t n = 仍，c o n f i d e n c e ( t i n j t n ) 定义如下： c o n f i d e r l c e ( t i n 号t n ) ；篙嚣o 裂t ( 2 划 l l e 鲳ccn e 越n im ，i 其中l l e a s tc o n t a i n ( t i n , t n ) i 表示至少包含事务t m 与t n 中项的事务的个 8 兰州大学硕士学位论文基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 数，l l e a s tc o n t a i n ( t i n ) l 表示至少包含事务t m 中项的事务的个数。 2 支持度( s u p p o r t ) 设集合a = a 。，a ：，a 。，a n n l n n ) 是项的集合，事务集 t = t ，t 。，t m ( m 2 n ) ，其中t j 是a 集合的一个子集，当且仅当w j a ，t i 都有一个标识符，称作t i d 。对于一个关联规则t m 专t n ，其中t mnt n = 茹，s u p p o r t ( t m 净t n ) 定义如下： 5 u p p 。r t ( t m = 寺t n ) = 些坐篙垫型 ( 2 _ 3 ) 其中l t l 表示事务的总个数。 3 支持度与置信度的关系 由概率论的相关知识我们易知，支持度与置信度的关系如下： c o n f i d e n c e ( t i njt n ) - - - - p ( t n t m ) = 篇篙薏罴揣( 2 - 4 ) 通常我们把式( 2 - 2 ) 与式( 2 - 3 ) 叫做相对置信度与相对支持度。当然我们 可以用该规则出现的频率表示支持度我们称之为绝对支持度( 支持度计数) 。这样 ( 2 4 ) 式也可以用以下公式计算： c 。n f i d e n c e ( t i n 每t n ) = 篙s u d 煮p o 篇c o u n 装琏l e a 嚣s t0 粼 ( 2 - 5 ) r tc 舶棚l l t l m ，j 4 强关联规则( s t r o n ga s s o ci a ti o nr u l e ) 如果一个规则的支持度与置信度同时满足最小支持度阈值与最小置信度阈 值时，我们就称这个规则为强关联规则。 5 频繁项集( f r e q u e n c yi t e m s ) 如果一个项集满足预定义的最小支持度阈值( 或者该项集的支持度计数大于 或等于最小支持度计数阈值) 则称该项集为频繁项集，如果该项集有n 个项，就 称为频繁n 项集，记作l n 。 2 2 关联规则生成 关联规则的生成一般可以分成两个步骤：( 1 ) 频繁项集的生成，这些项集必 须满足最小支持度阈值；( 2 ) 由频繁项集生成关联规则，生成的关联规则必须满 9 兰州大学硕士学位论文基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 足最小支持度阈值的同时也满足最小置信度阈值。下面对这两个步骤进行描述。 1 频繁项集的生成 频繁项集生成的算法主要有产生候选项集的a p r i o r i 算法和不产生候选项集 的基于模式增长的f p 8 r o w t h 算法。 ( 1 ) a p r f o r i 算法 a p r i o r i 算法是为布尔关联规则挖掘频繁项集而提出的原创性算法，是使用 一种称作逐层搜索的迭代方法，由k 项集探索k + l 项集。其思想是先通过扫描整 个数据库，求出每个项的计数，并收集满足最小支持计数的频繁1 项集的集合， 该集合记作l 1 。然后通过l 1 找出满足最小支持度计数的频繁2 项集的集合l 2 ， 如此下去直到不能找出频繁k 项集为止。该算法的缺点是每找一个频繁项集都需 要对整个数据库扫描一次，这样的运算量非常庞大。为了提高该算法的执行效率， 我们可以利用a p r i o r i 性质降低搜索空间。该性质如下： a p r i o r i 性质：如果b = t 1t z ，t 3 ，t k ) 是频繁项集，则对于任意0 瓦 i = l ( 1 j s k ) 是频繁项集。 a p r i o r i 算法主要由两步来完成。第一步称为连接步。在该步骤中，为了求 得频繁k 项集l i k ，首先求出频繁k 一1 项集k - ，然后通过k 1 项集执行自身连接 产生候选k 项集，记作c k ，其中c k 中的有些项可能不满足最小支持度阈值。第 二步称剪枝步。在该步骤中，根据a p r i o r i 性质，如果在c k 中的某些项集的子集 不包含在l l 中，那么该项集就是非频繁的，此时我们就把该项集从c k 中删除。 循环操作第一步与第二步，这样在第一步中连接产生所有的候选，在第二步中使 用a p r i o r i 性质删除非频繁子集的候选，如此进行，直到生成的频繁项集为空时 算法终止。 ( 2 ) 基于模式增长的f p g r o w t h 算法 由于基于a p r i o r i 思想的频繁模式挖掘算法在计算机中有两大开销，一是该 算法可能产生大量候选项集，当数据量很大时，生成庞大的不足以存储在计算机 内存中的候选项集时，这些候选项集的存储开销对于计算机硬件和程序的执行效 率来说都是一个巨大的考验；二是该算法在没有找到所有频繁项集之前需要不断 重复地扫描数据库。为了克服以上问题，就提出了一种不产生候选项集的挖掘频 繁项集的算法- 基于频繁模式增长( f r e q u e n t - p a t t e r ng r o w t h ) ，简称f p 增长 1 0 兰州大学硕士学位论文基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 算法。该算法采用了分治的算法策略。其主要思想就是，首先将提供频繁项的数 据库压缩到一棵频繁模式树( f p 树) ，该压缩过程保持数据库中数据的关联信息 不变。然后将压缩后的数据库划分成一组条件数据库，每个条件数据库对应一个 频繁项或“模式段 ，并分别挖掘每个条件数据库。其挖掘频繁模式的过程如下： 先以长度为1 的频繁模式( 初始后缀模式) 开始的，然后构造它的条件f p 树， 并递归地对该树进行挖掘。模式增长通过后缀模式与条件f p 树产生的频繁模式 连接实现。增长的方法是将发现长频繁模式的问题转换成递归搜索一些比较短的 模式，然后连接后缀。该算法是使用最不频繁的项作后缀，提供了好的选择性， 所以该算法大大降低了搜索的开销。 该算法相对于a p r i o r i 算法的优点是，对于同时挖掘长的和短的频繁模式，该 算法的执行效率大约比a p r f o r i 算法快一个数量级，因为长频繁模式或短频繁模 式都是有效的和可规模化的。 2 由频繁项集生成强关联规则 第一步我们挖掘出一个数据库中事务的频繁项集后，可以直接由这些频繁项 集产生强关联规则，强关联规是满足最小支持度阈值和最小置信度阈值的。由式 2 - 4 和式2 5 我们可知，我们可以通过事务的支持度计数求出置信度。由于频繁 项集中的任一非空子集都是频繁的，所以由频繁项集中的事务构成的规贝均满足 最小支持度阈值与最小置信度阈值，所以这些规则是强关联规则。 2 3 频繁子图挖掘算法 频繁项集挖掘是在项集中挖掘出满足最小支持度阂值与最小置信度阈值的 频繁项集。而在频繁子图挖掘中，相当于把频繁项集挖掘中的项集变为图集。从 而从这一图集中挖掘出满足最小支持度阈值的频繁子图。但是在频繁子图挖掘过 程中，计算子图频繁度时，必须解决子图同构问题【3 4 】，而且子图同构已经被证 明是一个n p 问题 3 5 】。故在子图挖掘过程中的一个难点就是子图同构的检测， 而且子图同构检测的计算复杂度是指数难度高的。如下图所示虽然图2 1 中的a 图与b 图表示形式不一样，但这两个图中仍然存在同构子图c 。 兰州大学硕士学位论文 基于集群环境的并行频繁子图挖掘算法p g m i n e r 研究 1 酬 a 图2 - 1 子图同构示例 因此频繁子图挖掘比频繁项集挖掘的算法的效率要求更高。 2 3 1 频繁子图的相关概念 1 频繁子图( f r e q u e n c yg r a p h s ) 将事务集t 换成图集g ，将事务t m 换成图g m 即可将频繁项集的相关置信 度和支持度扩展到频繁子图上。唯一不同是在频繁项集中项集出现的频度在频繁 子图由子图同构来定义，在这里，有必要先给出图的相关定义。 2 标号图 一个标号图是一个五元组，g = e ，e ，v l j 。其中，v 代表图中顶点的集 合，e v v 代表图中边的集合。v ，e 分别代表节点标号的集合与边标号 的集