（计算机软件与理论专业论文）基于序列编码频繁子树挖掘算法研究.pdf

：啕_ 叶虫害 基于序列编码频繁子树挖掘算法研究 兰州大学硕士学位论文 摘要 频繁模式挖掘是数据挖掘领域的一个基本问题，其研究范围包括事务、序 列、树和图。其方法被广泛应用于许多其它数据挖掘任务中，如相关性分析。 周期分析，最大模式，闭合模式，查询，分类，索引等等。 随着网络的快速发展，频繁模式的挖掘已经推广到诸如图和树这类复杂模式 的挖掘上，并广泛的应用于生物信息学、w e b 挖掘、化合物结构分析等领域。 本文对大量频繁子树挖掘算法，特别是基于模式增长的子树挖掘方法进行了深入 的研究与分析，主要分析了基于模式增长策略下各种挖掘算法的实现方法与技 巧，针对模式挖掘过程中侯选模式集的生成和支持度计算复杂的特点，以及重复 运行挖掘算法而产生的时空消耗，提出一个简单高效的挖掘算法。 本文提出了利用树的序列编码，按照模式增长方法来挖掘频繁予树的算法 算法弓l 入基于数组结构的序列编码来表示树和森林：用最左路径扩展方法构造完 整的模式增长机制；能够系统的根据树的拓扑结构，在频繁子树模式的各个增长 点上构造相应扩展模式，把侯选模式生成巧妙地转化成有效扩展点的查找，这种 方式不但保证了侯选模式生成完全无冗余，而且使支持度计算变得更加的简单可 行，在此基础上，设计并实现了频繁子树挖掘改进算法t m g 。本算法与基于a p r i o r i 的e m i n e r 算法的比较，t m g 算法具有更优的性能。适用范围更广，进行简单 的变换后，可以对不同类型的树进行挖掘。 关键词：树挖掘，频繁模式，p r u f e rs e q u e n c e s ，嵌入链表 蔺- ，：寥 基于序列编码频繁子树挖掘算法研究兰州大学硕士学位论文 a b s t r a c t f r e q u e n tp a t e mm i n i n gi sab a s i cp r o b l e mo f d a t am i n i n g ，i n c l u d i n gm i n i n g t r d i i g a c t i o n s ，s e q u e n c e s ，扭sa n dg r a p h s t h ea l g o r i t h mf o ri th a sb e e np r e v a l e n t l y u s e di nm a n yo t h e rd a t am i n i n gt a s k , s u c ha sa s s o c i a t i o na n a l y s i s , p e r i o d sa n a l y s i s , m a x i m a la n dc l o s e dp a t e m s ，q u e r y ，c l a s s i f i c a t i o na n di n d e x t e c l m o l o g yc t c w 汕t h er a p i dd e v e l o p m e n to fi n t e m e t f r e q u e n tp a t t e r nm i n i n gg e n e r a l i z e st o m o r ec o m p l e xp a t t e r n sl i k et r e em i n i n ga n dg r a p hm i n i n g m e t h o d sf o rm i n i n g 船q u e n tt r e e sa l ew d i e l yu s e di nb i o i n f o r m a t i c s , w e b m i n i n g c h e m i c a ld a t as t n k ：t i 髓 m 试i n g ，a n d s oo n i nt h i s p a p e r , t h ef r e q u e n tl a r g e - t r e ea l g o r i t h m f o rm i n i n g ， p a r t i c u l a r l yt h o s eb a s e do nt h eg r o w t hp a t t e r n so ft r e e - m i n i n gm e t h o dc o n d u c t e d i n - a e p t l lr e s e a r c ha n da n a l y s i s , b a s e do nt h ea n a l y s i so ft h em a i nm o d eo fg r o w t h s t r a t e g yu n d e rv a r i o u sm i n i n ga l g o r i t h mm e t h o dw i t ht h es k i l l s m i n i n ga g a i n s t c a n d i d a t e sp r o c e s sm o d e la n dt h eg e n e r a t i n gs u p p o r tc o m p u t a t i o n a lc o m p l e x i t y c h a r a c t e r i s t i c s ，r e p e a to p e r a t i o n sa n dm i n i n ga l g o r i t h ma n dt h et i m ec o n s u m p t i o n , w e p r o p o s eas i m p l ea n de f f i c i e n ta l g o r i t h mf o rm i n i n g t h i sp a p e rp r o p o s e st h eu s eo f t h et r e ec o d i n gs e q u e n c e ，i na c c o r d a n c ew i t ht h e m o d eo f g r o w t h 印p f o 卸ht om i n i n gf r e q u e n t - t r e ea l g o r i t h m a l g o r i t h m sb a s e do i lt h e i n t r o d u c t i o no fa na r r a yo fs e q u c n c oc o d i n gt oi n d i c a t et r e e sa n df o r e s t s ；m o s tl e f t w i t ht h ee x p a n s i o np a t hc o n s m u c t e di n t e g r i t yo ft h eg r o w t hm o d e ；a c c o r d i n gt ot h e t r e e t o p o l o g y , i n t h e t r e e - f r e q u 锄tp a t t e r no fv a t i o mg r o w t hp o i n t s s 打l 1 c l l l r e c o r r e s p o n d i n ge x p a n s i o nm o d ep u tc a n d i d a t e sg e n e r a t i n gm a r v e l o u s l y e f f e c t i v e e x p a n s i o ni n t ot h es e a r c hp o i n t t h i sa p p r o a c hn o to n l ye n s u r e st h a tt h ec a n d i d a t e g e n e r a t i n gc o m p l e t e l yn o n - r e d u n d a n lb u ta l s os u p p o r tt h ec a l c u l a t i o nb e c o m e sm o r e s i m p l ea n df e a s i b l e , o nt h i sb a s i s ，d e s i g na n dr e a l i z a t i o no ft h ef r e q u e n tm i n i n g s u b - t r e ea l g o r i t h mt r e e m i n e r - gi m p r o v e d b a s e do nt h ea l g o r i t h ma n dt h et r e e m i n e r a p r i o r ia l g o r i t h m ，t r e e m i n e r - ga l g o r i t h mh a sf o u n db e t t e rp e r f o r m a n c e ab r o a d e r s c o p e ，as i m p l et r a n s f o r m a t i o n , w ec a l lf o rd i f f e r e n tt y p e so ft r e e st oc a r r yo u t e x c a v a t i o n s k e yw o r d s ：t r e em i n i n g ，f r e q u e n tp a t e r n s ，p r u f e rs e q u e n c e s ，e m b e d d i n gl i s t s - 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发 表的成果、数据、观点等，均已明确注明出处。除文中已经注明 引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以 明确方式标明。 本声明的法律责任由本人承担。 论文作者签名： 日期：垄立：兰! ! 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：逸! 垒自导师签名：畦! 鱼兰 日期：之竺王j - 膨 ：畸r 土亭基于序列编码频繁子树挖掘算法研究兰抖l 大学硕士学位论丈 1 1 研究背景 第一章绪论 频繁模式挖掘是数据挖掘领域的一个基本问题。1 9 9 4 年，为了寻找大量商务 事务库中的项集之间的有趣联系，a g r a w a i 开创性地提出了关联规则挖掘问题， 并发表了著名的 p r i o r i 算法n 1 嘲，用频繁项集产生关联规则，发现顾客购买的不 同商品之间的联系，分析顾客的购物习惯，帮助零售商制定营销策略。1 9 9 5 年， 为描述同一顾客在多次购物所购物品之间可能存在的某种关联关系，a g r a w a l 又 发表了序列模式挖掘算法捌。此后，频繁项集与频繁序列挖掘算法被广泛应用于 许多其它数据挖掘任务中，如相关性分析，周期分析，最大模式，闭合模式，查 询，分类，索引等等。川”眦”本世纪初，研究者已发表数百篇论文，或提出新 的算法，或改进己有的算法，来更有效的解决这个问题。咖咖删o 。 最近几年，i n t e r n e te l 益普及，万维网成为一个庞大的，分布广泛的全球性 信息服务中心。h t m - 和x m l 文档是其最重要的载体，也为数据挖掘提供了新的丰 富资源。w e b 挖掘是数据挖掘领域中一个发展迅速，更具挑战性的课题。其内容 包括w e b 链接结构，w e b 内容及w e b 访问模式挖掘等。由于h t m l 和x m l 文档本身及页 面之间的链接信息都可以用树或图结构来建模，因此，频繁模式的研究对象，也 自然的从最初的事务项集和序列，逐渐扩展到树和图等结构型数据o ”“小例“”。如 何发现挖掘频繁子树和频繁子图的高效算法，日益成为一个具有重要理论和实用 价值的研究课题。 经过十几年的研究，已经奠定了较成熟的频繁模式挖掘方法的理论基础。根 据不同的挖掘策略，方法可分为两大类：一类是宽度优先，逐层挖掘的算法，一 类是深度优先，模式增长的算法。通过限制挖掘出的模式彼此之间的关系，又可 分为完全频繁模式挖掘，最大频繁模式挖掘和频繁闭合模式挖掘。丽根据挖掘对 象的不同，方法可分为频繁项集挖掘，频繁序列挖掘，频繁予树挖掘和频繁子图 挖掘等。 本文围绕频繁子树挖掘技术展开研究。重点研究利用模式增长方法在有序树 构成的森林中挖掘嵌入式频繁子树；在无序树构成的森林中挖掘直接频繁子树： 萄t ，：掌 基于序列编码频繁子树挖掘算法研究 兰州大学颐士学位论文 及相关的实现技术等系列关键问题。 1 2 本文研究的内容和创新之处 根据前文对频繁模式挖掘研究现状的分析，对现有的大多数频繁模式挖掘 算法进行研究，针对算法中存在多次扫描数据库产生和筛选候选模式集、时空效 率低，动态维护复杂，不利于更新，特别是对于海量数据、长模式的挖掘和维护 效率低等问题。开展本文的研究工作，主要围绕三个主题展开：一是待挖掘的半 结构化数据在内存中的管理与组织；二是基于序列的模式增长频繁子树挖掘算法 的设计与实现；三是高效内存管理程序的设计。本文的研究主要成果和创新之处 包括以下几个方面： l 、基于树的编码序列，在原来算法的基础上改进了频繁子树挖掘算法t m g 。 实验结果表明，改进后的算法与原算法相比性能更优。适用泛围更广，可以对 不同类型的树进行挖掘。 2 、提出了一种新侯选子树生成机制，这种侯选子树的生成是建立在对树进 行序列编码的基础上，利用最左扩展的方法，把侯选模式生成巧妙地转化成有效 扩展点的查找，实践证明这种产生的侯选子树的方法是简单、有效的，并且所产 生的侯选集是完全的、无冗余的。 3 、在程序实现中，对内存空间的频繁申请与释放将会耗费大量的时间，为 了节约这些开销，本文提出的序列编码和嵌入链表数据结构，使内存管理利用更 加的容易高效，从而实现了申请到的内存空间的高效利用，这样就可以避免每次 节点空间的申请与释放都要通过操作系统与硬件通讯，使程序的效率有了很大的 提高。 实验结果表明本文提出的p r u f e r 序列( p r 诵c rs e q u e n c e s ) “”和嵌入子链表 ( e m b e d d i n gl i s t s ) 是两种非常有效的数据结构，使算法具有高性能缓存记忆 ( h i g h l y c a c h e c o n s c i o u s h c c ) 功能，h c c 起到了高效内存管理利用的作用， t m o 算法是高效的、用途广泛的频繁子树挖掘算法。 1 3 本文的组织结构 第1 章：首先介绍了本文的研究工作的背景，接着阐述了本文的主要研究内 - 2 - 萄，? ：亨 基于序列编码频繁子树挖掘算法研究兰州文学硕士学位论文 容、研究成果和创新之处。 第2 章：频繁子树挖掘问题研究。首先简单介绍了频繁模式挖掘的相关研究 和工作进展；其次，认真分析了结构化数据挖掘问题和基本过程；在此基础上， 详细研究了基于模式增长频繁子树挖掘问题，给出了相关术语的定义，认真研究 了t r e e m i n e r 和t r e e c ，r o w t h 算法对子树挖掘的策略和实现方式，深入探讨了基 于模式增长的频繁子树挖掘算法。 第3 章：t m g 算法的设计与实现。对大量频繁子树挖掘算法进行研究，详 细分析了不同算法之间事务数据库在内存中的存储形式，特别对多种利用模式增 长策略子树挖掘算法进行了比较，分析了模式增长过程中不同的方法及特点。在 比较分析的基础上，吸取已有数据结构的优点，找到了两种新的数据结构p l 1 f c r s e q u e n c e s 和e m b e d d i n gl i s t s ，在两种结构的基础上，提出了新的高效的频繁子 树挖掘算法1 m g 算法。然后给出算法描述、实现与性能分析。 第4 章：总结和下一步研究工作展望。主要对本论文的研究工作进行总结， 并对下一步的工作进行展望。 ；啕- ，虫害 基于序列编码频繁子树挖掘算法研究 兰州大学硬士学位论文 第二章频繁子树挖掘问题研究 2 1 频繁模式挖掘相关研究 本节介绍频繁模式挖掘领域相关研究动态。首先介绍传统的频繁项集和频繁 序列模式挖掘的研究概况，接着介绍时间序列模式挖掘的常用方法，然后介绍已 有的频繁最大模式和频繁闭合模式的主要方法，最后介绍频繁子图的研究动态。 2 1 1 频繁项集挖掘 频繁项集挖掘一直是数据挖掘领域的重点课题，所做的工作与取得的成果也 比较多。频繁项集挖掘最初应用于在事务库中发现关联规则的a p r i o r i 算法。由 r a g r a w a l 等人首先提出来。关联规则反映了大量数据中项目集之间有趣的关联 或相关联系。识别或发现事务库中所有的频繁项集是关联规则发现算法的核心和 关键。 a p r i o r i 算法是最有影响的挖掘频繁项集的算法。其核心思想基于频繁项集 的先验知识：即频繁项集的所有非空子集必须也是频繁的。算法使用一种逐层搜 索的迭代方法，将频繁k 一项集用于探索频繁( k + 1 ) 一项集。算法首先找出频繁i 一 项集的集合，记做l l 。l 。用于寻找频繁2 项集合l ：，然后l z 用于找l 。，如此下去， 直到不再产生频繁k 项集。找每个l 需要扫描一遍数据库。 p r i o r i 算法的一个巨大优势是其挖掘大型事务库的能力。不需要将事务库 读入内存就可以完成挖掘工作。然而该算法需要多次扫描数据库，扫描次数等于 发现的最长的频繁项集的项的个数。鉴于a p r i o r i 算法处理的数据库的量非常大， 算法的效率显得十分重要。许多研究人员对算法的连接和剪枝过程进行各种优 化，产生了很多变体。他们通常针对如下几个目标中的一个或多个进行改进优化： 最小化扫描数据的次数；最小化候选集数量；最小化计算每个候选集频率所需的 时间。 与a p r i o r i 算法所不同的是，f p - g r 6 w t h 算法和t r e e p r o j e c t i o n 算法采用深度 优先的策略挖掘频繁项集。f p - g r o w t h 算法思想是：先统计出频繁l 项集( 集合中的 元素称为频繁项) ，将其压缩到内存中的一棵频繁模式树( f p - - 树) ，同时保留项 蔺- - j 天害 基于序列编码频繁子树挖掘算法研究兰州大学硕士学位论文 间关联信息；然后，通过关联信息，将压缩后的数据库分成一组条件模式库。每 一个条件模式库与一个频繁项关联。之后使用称为f p - g r o w t h 的方法从频度最小 的频繁项开始自底向上，在条件模式库上进行频繁项集挖掘。研究表明f p - g r o w t h 算法大约比a p r i o r i 算法快一个数量级，同时也优于t r e e p r o j e c t i o n 算法。 f p - g r 钾t h 方法不足在于：当存在许多长面复杂的模式时，f p - g r o w t h 算法需要递 归构造的条件树数量巨大，时空代价较高。 2 1 2 序列模式挖掘 序列模式挖掘同样由r a g r a w a t 首先提出，之后引起了大家的重视。序列模 式与关联规则之间的区别在于后者描述的是在一次购物中所购买物品之间的关 联关系，即事务内部的关联模式。而前者则描述同一顾客在多次购物所购物品之 间可能存在的某种关联关系，即事务之间的关联模式。显然，所有频繁序列的集 合是所有频繁项目集的超集。 a g r a w ai 在a p rio ri 算法的基础上提出了三个序列模式挖掘算法 p r i o r i a i i p r i o r i s o m e 和d y n 硼i c s o m e 。这些算法也继承了 p r i o r i 算法固有的 弱点，需要多遍扫描数据库，需要代价较高的候选模式产生与测试操作等。文献 o “提出了s p a d e 算法，以深度优先的策略挖掘模式。其将序列数据库组织成新颖 的倒排格式，将支持度计算操作转化为事务i d 和项i d 2 _ 间的求交运算，算法仅需 要三次扫描数据库，性能与类如r i o r i 算法相比有了很大提高。 2 1 3 时间序列模式挖掘 随着数据挖掘研究领域的拓展，针对时间序列数据的数据挖掘研究e l 益受到 人们的关注。所谓时间序列类型数据就是按照时间先后顺序排列各个观测记录的 数据集。h e i k k im a n n i l a 等将事物数据库中关联模式和序列模式的算法思想引入 到事件序列中，提出了从事件序列中发现频繁情节的算法“”。 c l a u d i ob e t t i n i 等对时间序列中静态结构的发现问题进行了研究，与 h e i k k im a n n i l a 不同的是，b e t t i n i 允许用户指定感兴趣的事件结构，并在其算 法中增加了对多时间粒度关系的支持。为实现多粒度挖掘，b e t t i n i 定义了带时 间粒度的静态约束和带时间粒度的事件结构，在计时自动机基础上提出了一种称 蔺- r ) ：寥基于序列编码频繁子树挖掘算法研究兰州大学硕士学位论文 为带时间粒度的计时自动机搜索算法，实现了多粒度复杂结构的发现。 g a u t a md a s 等对从时间序列中发现关联规则进行了研究倥叼，这里的规则是指 对时间序列中不同模式问关系的一种描述，文献嘲的主要贡献在于给出了个将 原始时间序列转换成一个由各个模式标示符组成的符号序列的一般性方案，该方 案由三部分组成，即分割，聚类和符号替换。然后采用序列模式发现算法实现了 符号序列中规则的发现。 文献皿1 首次提出了在一种基于互关联后继树模型的时序特征模式挖掘方 法。该方法在序列分段上，采用了一种新颖的、基于重要点的时问序列线段化算 法；在符号化过程中，采用基于相对斜率的局部符号化方法。既减少计算复杂度， 又避免了噪声的影响。在挖掘算法实现上，根据序列特征模式的有序性和重复性， 提出了一种无须生成大量的候选模式集的互关联后继树挖掘算法。 而针对更有分析价值的多序列关联模式，文献嘲进一步提出一种新颖的关联 模式挖掘方法。该方法利用a l l e n 区间逻辑关系来描述时闻序列模式的关联关系， 避免了传统方法在关联关系描述上的非同步性；然后通过时间观测窗口，构造出 一种包含并行模式和串行模式特殊形式的模式序列。最后，在此基础上构造一种 广义的互关联后继树模型，实现多序列关联模式的挖掘。 2 1 4 最大项集和闭合项集模式挖掘 由于完全频繁项集数量众多，因此，降低候选项目集的数量是减小开销的最 好手段。由于最大频繁项目集中己经隐含了所有频繁项目集，所以可把发现频繁 项目集的问题转化为发现最大频繁项目集的问题。所谓最大频繁模式m 。即，不 存在一个m 的超集m ，使得m 也是频繁的。某些数据挖掘应用仅需发现最大频 繁项目集，而不必发现完全频繁项目集，因而发现最大频繁项目集对数据挖掘具 有一定意义。 目前已经提出的可用于发现最大频繁项目集的算法有m a x - h l i n e r 伽， p i n c e r s e a r c h m l ，d m f i 以及m a f i a 1 等。 m a p m i n e r 突破了传统的自底向上的搜索策略，尽可能早地对项目集进行修 剪。但其未利用自顶向下的信息进行修剪，且未对最大频繁项候选集( m f c s ) 进行 适当的排序，产生了多余的最大频繁候选项目集。 蔺村，：害 基于序列编码频繁子树挖掘算法研究兰州大学硕士学位论文 p i n c e r s e a r c h 采用了自底向上和自顶向下的双向搜索策略，不过其第k 次的 m f c s 是由k - 1 次的m f c s 中的非频繁项目集去掉一个元素来生成的，因此产生了过 多的无用候选项目集。 d m f i 有效地把自底向上和自顶向下的搜索策略进行了合并，该算法为海量数 据库中发现最大频繁项目集和仅需要发现最大频繁项目集的数据挖掘应用提供 了一种有效而快速的算法。 m a f i a 使用位图表示法，将原始数据库重新组织成项一事务列表这样一种倒排 结构，通过对位图求交来计算支持度，是一种很新颖的挖掘方法。不过，为节约 空间，要混合使不同长度的位图，增加了算法的复杂性，并且，位图表示法是节 约空间仍有待探讨 最大频繁模式丢失了支持度信息。在某些应用中，挖掘频繁闭合模式更有意 义嘲。简单的说，所谓频繁闭合模式c ，即，不存在一个p 的超集c ，使得c 与c 的支持度相同。频繁闭合模式包含有完全频繁模式的所有信息，但数量却可 能比完全频繁模式少几个数量级。 以a p r i o r i 算法为基础，p a s q u i e r m l 提出t a - c l o s e 算法，采用自底向上、宽 度优先的搜索策略，通过构造“生成子”集合，逐层枚举所有的频繁闭合模式。 通过引入剪裁技术减小搜索范围。 p e i 以f p - g r o w t h 方法为基础，提出c l o s e t 算法在f p - 树上挖掘频繁闭合项 集。然而由于采用动态构建条件f p - 树，其数目同模式长度成正比，在稠密数据 上，动态树生成与维护开销较大。 z a k i 等人提出t c h a r m 算法侧，将事务库中的项用事务列表这种倒排格式表 示，将支持度计算操作转化为集合交运算，并引入d i f s e t 技术减少存储开销和提 高求交运算的效率。 所有这些方法，都必须将己经发现的频繁闭合项集缓存起来，以备对新发现 的频繁项进行闭包测试，但仍缺乏有效的组织方法。 2 1 5 频繁子图挖掘 完全频繁子图挖掘问题首先由i n o k u c h i 提出，同时给出了a g m 算法1 。a g m 算法使用基于a p r i o r i 的方法挖掘频繁子图模式。 ；鹭村：掌 基于序列编码频繁子树挖掘算法研究兰州大学硕士学位论文 k u r a m p c h i 和k a r y p i s 贝f 提出了一个更有效的f s g 算法汹1 来解决同样的问题。 其主要思路是：利用一种有效的稀疏图表示方法来减小图的存储和计算开销。利 用每次增长一条边的方法增大子图的尺寸，使其能够有效地产生候选模式。 利用规范化编码方法，将图的邻接链表或邻接矩阵表示转化为序列表示，并 且保障两个同构子图的序列表示相同，从而避免了有关同构予图判定的复杂计 算。f s g 算法亦采取宽度优先搜索策略。实验表明，f s g 算法效率较a g m 舅j ：法有较 大提高。 挖掘频繁子图的另一个著名的算法是g s p a n 算法。此算法坚持了深度优先， 模式增长方法优于宽度优先，候选模式产生与测试方法的基本观点。其基本思想 是：首先，在图与图的表示之间建立起一种严格的字典式顺序。其次，将每个图 映射到最小d f s ( d e p t hf i r s ts e a r c h ) 编码。此编码方法能够唯一地表示一个子 图。然后，从频繁一l 模式( 只有一条边的频繁子图) 出发，采用深度优先，模式增 长的策略，搜索所有可能模式的最d 、d f s 编码。对于己发现的频繁子图，在其最 j j 、d f s 编码的末尾附加一条新的边，就可以探索可由其增长得到的频繁模式，直 到其不可能再增长为尺寸更大的频繁子图。最后，利用模式增长的方法完成整个 搜索空间挖掘工作。最小化d f s 编码方法避免了同构子图的复杂计算。深度优先， 模式增长的方法避免了候选模式的生成和测试。因此g s p a n 成为目前最有效的图 挖掘算法之一。实验表明，其效率是f s g 算法的1 5 3 0 0 倍，是判定频繁子图挖掘 效率的一个标志性算法。 a d i 算法嘶1 改进t g s p a n 算法，其将有效的两层索引结构引入g s p a n , 既扩展了 其挖掘大型图库的能力，又提高了算法的计算性能。y a r 避- 步提出了挖掘频繁 闭合子图的算法c l o s e g - r a p h 0 ，并探讨了将频繁予图应用于索引和查询的技术。 2 2 频繁子树挖掘问题综述 数据挖掘关注从庞大数据集中寻找有用的模式和关系。然而当今的大部分数 据挖掘算法仅仅能够处理具有固定结构的数据。这类数据中数据模式往往己经事 先定义，称为结构化数据。 在w e b 数据库和生物信息学数据库中，数据往往缺乏某种固定的结构。常常 称这种数据为半结构化数据。在结构化数据库中，由于所有的数据项具有相同的 蔺孵虫害 基于序列编码频繁子树挖掘算法研究 兰州大学硕士学位论文 结构，因此结构信息在标准的数据挖掘中并不重要。对于半结构化数据，数据项 的结构在其语义中却起着至关重要的作用。 频繁子树结构往往能够给出半结构化数据库的概要信息。这类信息可以用来 构成查询，也可以引导索引的生成，还可以作为对数据库进行分类或聚类的基础。 不过，频繁子树挖掘并不像频繁项集挖掘那样直观明了。因为有许多的因素会对 算法产生重大影响，比如： 树的类型如何定义? 树的孩子节点之间是否有序? 某棵树是另一棵树的“子树”的标准是什么? 这类问题的答案与实际应用背景有关。简单的说，孩子节点之间存在前后关 系的树称为有序树；子树的父子节点保持父树的祖先一后代关系时称为嵌入式子 树；子树父子节点保持父树的父子关系时称为直接子树。不同回答，不仅挖掘的 结构大不一样，而且搜索空间和删枝策略也大不相同。 2 3 频繁子树挖掘算法介绍 频繁子树模式挖掘直到最近才引起大家的重视，相关的研究文献也不太多。 文献呻1 用麴p r i o r i 算法来解决这个问题。一个被称为a p r i o r i 的性质用来减少候 选频繁模式的生成：每个频繁模式的子模式也一定是频繁的。不过，正如文献嘲 在频繁项集挖掘问题中指出的，当存在大量复杂模式时，候选模式产生一测试策 略的性能会严重退化。 z a k i 和a s a i 几乎同时提出了有效挖掘频繁子树的方法汹3 嘲，他们采用一种非 常有用的最右路径扩展机制来产生候选树模式。在文献中，z a k i 给出了两种算 法，t r e e m i n e r 和p a t e r n m a t c h e r ，用来挖掘嵌入式频繁子树。 p a t e r n m a t c h e r 是类a p r i o r i 的宽度优先挖掘算法。而t r e e m i n e r 贝l j 采用深度优 先的挖掘策略。其利用一种树的倒排表示方法，也即用s c o p e l i s t 结构，来重新 组织数据库，通过对s c o p e - l i s t 求交来进行有效的支持度计算。t r e e m i n e r 的效 率比p a t e r r i m a t c h e r 高出大约4 - 2 0 倍，是迄今所发表的算法中最高效的挖掘嵌入 式频繁子树的方法之一。然而，尽管其非常有效，t r e e m i n e r 仍采用的是代价较 高的候选模式产生一测试策略。对s c o p e - l i s t 的求交运算也是这个算法的一个瓶 颈。 篙- r 幺雾 基于序列编码频繁子树挖掘算法研究 兰州大学硕士学位论文 研究表明，利用静态投影技术，在静态i s + - 树上挖掘频繁模式，可以取得比 在动态构建的f p 树上挖掘频繁模式更好的效果。那么，用模式增长的方法和静 态投影技术挖掘树模式，是否更加有效? w a n g 首先尝试用模式增长方法来解决这个问题，在p r e f i x s p a n 序列模式挖 掘算法基础之上，提d j c h o p p e r 和x s p a n e r 两种算法嘲。然而严格地来讲，这两种 算法是序列意义上的模式增长。即，先将树看作是一个用先序表示的序列，然后 在序列上应用模式增长方法。由于有许多不同拓扑结构的树可能表示相同的序 列，所以算法依然需要使用字串匹配操作完成支持度计算，这极大的影响了算法 的效率，因此并不是真正的模式增长算法。 用模式增长方法挖掘树模式，所面临的主要困难在于： 怎样表示树和树的集合，才有利于模式增长方法和投影技术的利用7 如何既无冗余，又完全地构造频繁模式生成空间7 使用怎样的策略将频繁k 一树模式( 包含k 个节点) ，增长为频繁( k + 1 ) 一树模 式。 最后一点最困难也最重要。在频繁项集挖掘中，由于每个事务中不存在重复 的项，因此，模式每增加一项，必然生成唯一的一个新模式。然而，树的不同节 点可以有相同的标识符。且树的拓扑结构使得其可能有许多个“增长点”，相同 标识符节点附加在不同的增长点上便会生成一个不同的模式。因此，用模式增长 方法挖掘树模式，无论从算法复杂度，还是从算法本身的复杂性，都比挖掘频繁 项集大得多。 2 3 1 相关问题定义 树表示为三元组t ( r ，n ，b ，其中( 1 ) n 是带标识符节点集。标志符取自集合l ， 不同节点可以有相同标识符；( 2 ) r n 是唯一的根节点：( 3 ) b 是树中分枝的集 合，且对每个分枝b = ( u i ，u ：) b ，都有u - ，u ：en 。称u 为u ：的父亲，u 2 为u 1 的孩子，若孩子之间有序，则称之为有序树。为简洁起见，用t ( r ) 或t 表示以r 为根的树。树中节点个数称为树的大小，表示为。树的集合称为森林。数据 库d 就是森林。当r 不唯一时称为自由子树。 ；莺- f 虫害 基于序列编码频繁子树挖掘算法研究兰州大学硕士学位论文 路径p 是树t ( r ) 的相连分技的集合，记为( u 。，u 。，u j ，且( u 。，r e + 1 ) eb 。节 点v 的层次定义为从r 到v 的路径的长度，记为k 。称从r 到v 的路径上的任意节点u 为v 的祖先，v 为u 的后代。称先序遍历有序树时节点对应的遍历次序为节点序。 着t ( r ) 的最后节点为w ，称从r 到w 的路径为t ( r ) 的最右路径。节点u 的辖域区问定 义为一段区间 l ，r ，其中，l 是u 本身在节点序中位置，r 是u 的最后一个后代的 位置。节点u 辖域内的节点包含了u 的所有后代。最右路径和辖域区间的概念在构 造拓扑投影的过程中起着非常重要的作用。 有序树给定1 棵树，设u 是树的非叶子节点( 内部节点) ，且u 具有k 个孩子， 给这些孩子节点排序，形成u h u t ，排完序后形成的树被称为有序树。 标号树给定1 棵树t ( v o ) ，标号集l ，顶点集n ，t ( v o ) 是标号树当且仅当存在 映射n 哼l , v vn ，坟垆l l ，记作t ( v 口) = ( l ( n ) ，b ) ) 有序标号树给定1 棵树t ( v 0 ，v ，l ，e ) ，t 是有序标号树当且仅当t 是标号树 且t 是有序树。给出如下形式化定义，t ( v 0 ，v ，l ，e ) 是有序标号树当且仅当满 足以下条件： ( 1 ) v o 仨v ，是树的根节点；( 2 ) v 是树的节点集；( 3 ) l 是节点的标号集， v u v ，l ( u ) 是节点u 的标号；( 4 ) e 是树的边集。 给定树t ( r ，n ，b ) ，树s ( r 。，n 。，b i ) 称为树t 的嵌入子树，表示为s t ，如果 ( 1 ) n scn ；( 2 ) 对任意分枝( u ，v ) bs ，在树t 中一定存在路径 ，即 u 是v 的祖先。称t 包含s 。若u ，v 在t 中仍需保持父子关系，则称s 为t 的直接子树。 直接子树是嵌入式子树的一种特殊情况。称大4 , k 的子树为一棵k 一子树。通常，s 是待挖掘的子树模式，而t 是d 内的一棵树对s 中任意节点uen s ，t 中必有一 映射节点u en 与之对应。称t 中s 的所有映射节点为s 在t 中次呈现。 图2 一l 所示，( a ) 代表一棵有序标号树，( b ) 是( a ) 的一棵直接予树，( c ) 是 ( a ) 的一棵嵌入式子树。根据以上定义可以得出，如果t 是t 的导出式子树，n t 必然是t 的嵌入式子树。反之则不成立。 ：菊，乞搴 基于序列编码顿繁子树挖掘算法研究兰州大学硕士学位论文 ( a )( c ) 图2 1 定义2 1 ( 频繁子树) 给定数据库d ，树s t h 支持度指o f 包含s 的树的个数。即， s u p ( s ) - - i t i t d ，s j ) 时：则将( y ，j ) 加入p ，。 3 ) ( i j ) 时：在此种情况没有候选子树产生。 所有由p 衍生的( k + 1 ) 一子树都可以由对p 的元素列表中的每对元素上旖加求交 算子得到。 爨一 、 、禹一 暂- rj ，：搴 基于序列编码频繁子辩挖掘算法研究兰州大学硕士学位论文 该引理不仅保证仅仅在棵树的最右路径的各个节点上添加新节点，而且能 够保证列举空间的完整和无冗余。 图2 - 3 中所示的是通过等价类扩展候选进行候选生成的过程。对照求 交算予所定义的各种情况：x f r ，的自交得到t 。和t 。，对t ，和t 2 求交得到t 5 ，t 。和l 求交对应没有候选子树产生的情况，对t 。的自交得到t 。和t ，。等价类扩展之后， t 3t r 和t 6t ，各自形成新的等价类。 妙凸 t 4 t 图2 - 3 候选子树计数 t r e e m i n e r 使用一种新颖的称为s c o p e - l i s t 的树表示方法，高效的支持候选子 树计数。 定义2 4 ( 树的s c o p e l i s t 表示) 令x 表示一棵k 一子树，令x k 表示x 的最后节点。 用链表l ( x ) 表示x 的s c o p e - l i s t ，其中的每个元素是一个三元组( t ，s ，m ) 。t 是 树i d 号，表示x 呈现此树中，s 是x 。的辖域，m 是x 的前( k 1 ) 个节点在此树中的呈 现。 图2 4 中显示的是包含三棵树的数据库d 。图2 5 左部为起始时由单独项构成的 单节点树创建s c o p e l i s t 。基于以上概念，给出t r e e m i n e r 算法的总体框架。 裔 &上暑 ；啕- r 幺薯 基于序列编码频繁子树挖掘算法研究 兰州大学硕士学位论文 1 1 2 ，【2 ，3 】n l ，【l n 3 ，【3 捌 1 1 2 ，体2 】n 3 ，d ，3 】 前缀串= m o ，【o ，3 】o f l ，i o ，【2 ，3 】o ，f 3 ，3 】 l ，【1 ，3 】 1 ，【o ，5 1 ，【5 ，5 】 l ， 3 , 3 1 2 ，【o ，7 】 l ，【2 ，2 2 ，【1 ，2 】 2 ，【4 ，7 】 l ，【4 ，4 2 ，【6 ，7 】 2 ，【7 ，7 】 2 ，【2 ，2 2 ，f 5 ，5 图2 4 ，【5 ，5 1 0 , 0 ，【l ，1 】 0 , 0 ，【3 ，3 】 l , l ，【2 ，2 】 1 , 1 ，【3 ，3 】 2 , 0 ，【2 捌2 , 0 ，【7 ，7 1 2 , 0 ，【5 ，5 】 2 ，7 ，【7 ，7 2 , 4 ， 5 ，5 】 图2 5 前缀串= l2 算法挖掘嵌入式子树的t r e e m i n e r 算法 输入：数据库o ：最小支持度： 输出：d 中所有频繁子树： i p o - - ( 所有的频繁一l 予树 用 p 。表示，其共享前缀串长度为x 2 e n u m e r a t e f r e q u e n t s u b t r e e s ( p 】o ) ： 函数e n u m e r a t e - f r e q u e n t s u b t r e e s ( p ) i f o r p 中的每个元素( x ，i ) d o 2 【p 1 = o ：p i 表示从元素( x ，i ) 衍生的等价类 3 f o r p 中的每个元素( y ，j ) e p d o 4 r ： ( x 。i ) 0 ( y ，j ) ； 5 。l ( r ) = l ( x ) nl ( y ) ： 6 i fr 中的任意元素r r 是频繁的，则 p 。 = p 。 u ( r 7 e n d q 暑 串 缀 前6 萄- r 气辜基于序列编码频繁子树挖掘算法研究兰州大学硕士学位论文 8 e n u m e r a t e f r e q u e n t s u b t r e e s ( i f ， ) 9 e n d 算法中，用r 表示对等价类中任意两个元素扩展，用l ( r ) 表示它们各自的 s c o p e l i s t 。当前层的频繁子树递归的构成了等待进一步扩展的新的等价类。可 见，对s c o p e l i s t 的求交运算在t r e e m i n e r q b 起着至关重要的作用。 s c o p e - l i s t 求交运算 怎样对等价类 p 中的两棵予树进行s c o p e l i s t 求交运算? 当计算 ( x ，i ) o ( y ，j ) 时，只可能有两种结果：y 成为x 的孩子节点，或者，y 成为x 的兄弟节 点。然后，将结果加入新生成的等价类 p 。 。前者称这之为i n - s c o p e 测试，后者 称之为。o u t s c o p e 测试。令( t y ，s y ，m ，) l ( y ) ，( b ，s 。，m 。) l ( x ) ，新生成的树为t 。 对于i n s c o p