（计算机软件与理论专业论文）嵌入式与导出式频繁子树挖掘算法研究.pdf

中文摘要 树结构数据以其表达事物清晰、完整等优势，在计算机网络、w e b 挖掘、生物信 息分析、x m l 文档挖掘等领域有着日趋重要的应用。本文针对有序标号树，以最右 路径扩展技术为基础，从改进投影库的构造方法、减小投影库的规模和提高投影库 中节点的计数效率等方面，对频繁嵌入式与导出式子树挖掘算法进行了研究。主要 研究工作如下： ( 1 ) 给出一种基于离散区间的嵌入式频繁子树挖掘算法d i f t m 。首先，采用了 最右路径扩展的方法，由频繁k 子树可直接扩展成为频繁( k + 1 ) 子树，避免了候选生 成；其次，利用离散区间构造最右路径投影库，消除了部分冗余投影，有效地减小 了投影库的规模；再次，对投影库中的节点计数时，先找离散区间，再在离散区间 上计数频繁节点，避免了对重复投影的重复扫描；最后，采用c s l o g s 数据集，实 验验证了算法的正确性和有效性。 ( 2 ) 给出一种基于编码的导出式频繁子树挖掘算法e f i t m 。首先，通过树的宽度 优先编码表示原始数据库，使得最右路径投影中不存在冗余节点，减小了投影库中 每个投影的编码长度；其次，用带编码的区间表示最右路径上各节点的投影库，消 除了冗余投影，减小了整个投影库的规模；最后，理论分析和实验结果表明，该算 法是正确的和高效的。 关键词：数据挖掘；频繁嵌入式子树：频繁导出式子树；离散区间；投影库；冗余 投影；编码 a b s t r a c t t r e e s t r u c t u r ed a t a ，w i t hc h a r a c t e r i s t i c so fe x p r e s s i n gt h i n g sd i s t i n c t l v a n d p e r f e c t l y , i si n c r e a s i n g l ya p p l i e di nm a n yi m p o r t a n ta r e a ss h c ha s c o m p u t e rn e t w o r k s ，w e bm i n i n g ，b i o i n f o r m a t i c s ，x m ld o c u m e n tm i n i n g ， a n ds oo n t oi m p r o v et h em e t h o do n c o n s t r u c t i n gp r o je c td a t a b a s e d e c r e a s e t h es i z eo f p r o je c t d a t a b a s ea n di n c r e a s e n o d e c o u n t i n ge f f e c t i v e l v a l g o r i t h m so ff r e q u e n te m b e d d e da n di n d u c e ds u b t r e e sm i n i n ga r er e s e a r c h e d b a s e do nt h et e c h n i q u eo fr i g h t m o s te x p a n d i n gf o rt h eo r d e r e dt r e e s t h e m a i nr e s e a r c hw o r k sa r ea sf o l l o w s ： ( 1 ) ad i f t ma l g o r i t h mo ff r e q u e n te m b e d d e ds u b t r e em i n i n gb a s e do n d i s c r e t ei n t e r v a li s p r e s e n t e d f i r s t ，b ym a k i n gu s eo ft h er i g h t m o s tp a t h e x p a n d i n g ， f r e q u e n t k s u b t r e e s a r e d i r e c t l ye x p a n d e d t o f r e q u e n t ( k + 1 ) 。s u b t r e e sw i t h o u tg e n e r a t i n gc a n d i d a t es u b t r e e s e c o n d ，c o n s t m c t i n g t h er i g h t m o s tp a t hp r o j e c td a t a b a s ee l i m i n a t e ss o m er e d u n d a n tp r o j e c t i o n s b ym a k i n gu s eo ft h ed i s c r e t ei n t e r v a l ，s ot h a tt h es i z eo ft h ep r o je c td a t a b a s e i s e f f e c t i v e l yr e d u c e d f u r t h e r m o r e ，d i s c r e t ei n t e r v a li sf i r s t l ys e a r c h e df o r a n d 厅e q u e n tn o d e sa r ec o u n t e do nt h e m ，s ot h a ts c a n i n gs o m eo fp r o je c t i o n r e p e a t e d l yi sa v o i d e d i nt h ee n d ，e x p e r i m e n t a lr e s u l t so nc s l o g sd a t a c o n f i r mt h a tt h ed i f t m a l g o r i t h mi sc o r r e c ta n de f f i c i e n t ( 2 ) a ne f i t ma l g o r i t h mo ff r e q u e n ti n d u c e ds u b t r e em i n i n gi sp r o p o s e d b a s e do ne n c o d i n g f i r s t l y , w i d t h - f i r s te n c o d i n gi su s e dt oe x p r e s st h ei n i t i a l d a t a b a s ea n dm a k er e d u n d a n tn o d e si nt h er i g h t m o s tp a t hp r o j e c tn oe x i s t ， w h i c hg r e a t l yd i m i n i s h st h ee n c o d i n gs i z eo f e v e r ys i n g l ep r o je c t i o ni nt h e p r o je c td a t a b a s e s e c o n d l y ，i n t e r v a l sw i t he n c o d i n ga r eu s e dt od e n o t et h e p r o j e c td a t a b a s eo ft h en o d e so nt h er i g h t m o s tp a t ho fs u b t r e e s ，a n da l lt h e r e d u n d a n tp r o je c t i o n sa r ee l i m i n a t e da n dt h es i z eo ft h ep r o j e c td a t a b a s ei s d e c r e a s e d f i n a l l y , t h e o r ya n a l y s i s a n d e x p e r i m e n tr e s u l t ss h o wt h e c o r r e c t n e s sa n dt h ev a l i d i t yo ft h ee f i t m a l g o r i t h m i i i k e yw o r d s ：d a t am i n i n g ；f r e q u e n te m b e d d e ds u b t r e e ；f r e q u e n ti n d u c e d s u b t r e e ；d i s c r e t ei n t e r v a l ；p r o j e c td a t a b a s e ；r e d u n d a n tp r o j e c t i o n ；e n c o d i n g i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：未塑竺丝i l 笙l 一日期：至与乙l 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名：趔丝 日期：兰誓：! 导师繇粤一嗍j 耳一 第一章引言 第一章引言 1 1 数据挖掘概述 1 1 1 数据挖掘的产生、定义及挖掘对象 由于计算机应用的普及，数据库技术和数据仓库技术的不断发展及应用，在各 个领域产生了大量的数据，如天体光谱数据，银行每天的巨额交易数据等。在这些 数据中隐藏着丰富的信息，如何处理这些数据得到有用的信息，人们进行了有益的 探索。计算机技术的迅速发展使得处理数据成为可能，这推动了数据库技术的极大 发展，但是面对不断增加的数据，人们不再满足于数据库的查询、统计等功能，提 出了深层次问题：能不能从数据中提取信息或者知识为决策服务。就数据库技术而 言已经无能为力了，传统的统计技术也面临了极大的挑战，这就急需有新的方法来 处理这些海量数据。于是，人们结合统计学、数据库、机器学习等技术，提出数据 挖掘来解决这一难题。数据挖掘的概念自从在1 9 8 9 年8 月举行的第1 1 届国际联合人工 智能学术会议【l 】上首次提出后，就一直是数据库和人工智能领域研究的热点课题。 数据挖掘( d a t am i n i n g ) 是从大量的、不完全的、有噪声的、模糊的、随机的 数据中提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过 程。包括四个层次的含义：( 1 ) 数据源必须是大量的、真实的、有噪声的； ( 2 ) 发现的是用户感兴趣的知识；( 3 ) 发现的知识要可接受、可理解、可运用，而且能 用自然语言表达发现的知识；( 4 ) 所发现的知识是相对的，是带有特定前提和约束 条件的、面向特定领域的知识。 数据挖掘的对象【2 】主要有：关系型数据库、面向对象数据库、事务数据库、演绎 数据库、时态数据库、多媒体数据库、空间数据库、遗留数据库、异质数据库、文 本型、i n t e r n e t 信息库以及数据仓库( d a t aw a r e h o u s e ) 等。 1 1 2 数据挖掘的步骤【3 j 数据挖掘是一个多步骤的处理过程，般分为： ( 1 ) 问题定义，了解相关领域的有关情况，熟悉背景知识，弄清用户的需求。 ( 2 ) 数据提取，根据实际要求从数据库中提取相关的数据。 ( 3 ) 数据预处理，对前一阶段产生的数据进行再加工，检查数据的完整性及数 据的一致性，对其中的噪音数据进行处理，对丢失的数据进行填补，把数据变换成 适于挖掘的形式。 ( 4 ) 知识提取，运用适当的知识发现算法，从数据中提取用户所需要的知识， 嵌入式与导出式频繁子树挖掘算法研究 并使用一些常用的方法表示这些知识或用特定的方式表示。 ( 5 ) 知识评估，将发现的知识以用户能理解的方式呈现，如某种规则等，再根 据实际情况对知识发现过程中的具体处理阶段进行优化，直到满足用户要求。 1 1 3 数据挖掘的方法【3 4 】 根据挖掘任务、挖掘对象的不同数据挖掘方法可以有不同的分类。目前常用的 数据挖掘方法包括： ( 1 ) 粗糙集( r o u g hs e t ) 粗集理论是用于研究不精确、不确定性知识的学习、表达、归纳的方法。它通 过引入不可分辨关系、等价类、上近似、下近似等概念考察知识表达中不同属性的 重要性，来确定哪些属性是冗余的，哪些属性是必不可少的。删除冗余属性进而简 化知识表达空间，最终能从数据中挖掘出规则。 ( 2 ) 聚类( c l u s t e r i n g ) 聚类算法是通过对变量的比较，把具有相似特征的数据归于一类。通过聚类以 后，数据集就转化为不同的类集，使得在同一类中的数据具有最大的相似性，不同 类之间的数据不具有相似性。区分不同的类是数据挖掘过程的一部分，这些类不是 事先定义好的，而是通过聚类算法采用全自动方式获得。 ( 3 ) 关联规则( a s s o c i a t i o nr u l e ) 关联规则反映一个事物与其它事物之间的相互依赖性或相关联性。如果两个或 多个事物之间存在关联，那么，其中一个事物就能从其它已知事物中预测得到。关 联规则是指数据集中支持度和信任度分别满足给定阈值的规则。 ( 4 ) 决策树( d i c i s i o nt r e e ) 决策树是一个类似树形结构的流程图，利用信息论中的信息增益寻找数据库中 具有最大信息增益的属性，建立决策树的一个结点，再根据属性的不同取值建立树 的分支；在每个分支子集中，重复建立树的下层结点和分支，即可建立决策树。最 著名的决策树归纳算法是i d 3 方法，它对越大的数据库效果越好。对同一组训练实例 会产生许多与之相符的决策树，一般而言，树的规模越小，它的预测能力就越强。 ( 5 ) 模糊集( f u z z ys e t ) 模糊集合论是用隶属程度来描述差异的中介过渡，是一种用精确的数学语言对 具有模糊性和不确定性问题进行描述的方法。模糊集方法可用于聚类、分类等许多 领域，如模糊聚类方法可对对象的不分明的类属性进行很好的表达和处理。 ( 6 ) 神经网络( n e u r a ln e t w o r k ) 2 第一章引言 神经网络是由简单计算单元组成的广泛并行的网络，它模拟生物神经系统，以 m p 模型和h e b b 学习规则为基础，建立了三大类多种神经网络模型：前向神经网络、 反馈神经网络和自组织特征映射神经网络。它是通过训练来学习的非线性预测模型， 可以完成分类、聚类、特征挖掘等多种数据挖掘任务。 ( 7 ) 可视化技术( v i s u a l i z a t i o n ) 可视化技术是一种图形显示技术，将数据或结果转化为可视化形式，如图形、图 像等，使用户对数据的剖析更清楚。 另外还有统计分析方法、最邻近技术、遗传算法、b a y e s i a n 网络等方法。 1 1 4 数据挖掘的功钳2 】 数据挖掘通过预测未来趋势及行为，做出前瞻的、基于知识的决策。数据挖掘 的目标是从数据中发现隐含的、有意义的知识。具体的功能有：概念描述、关联分 析、分类和预测、聚类分析、孤立点分析、演变分析等。 ( 1 ) 概念描述( c o n c e p td i s c r i p t i o n ) 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。具体 的描述分为特征性描述和区别性描述。其中，特征性描述用于描述某类对象的共同 特征，区别性描述用于描述不同类对象之间的区别。概念描述可以通过数据特征化、 数据区分、数据特征化和比较等方法得到。 ( 2 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 关联分析发现关联规则，即在数据库中寻找数据对象间的关联模式，例如“在 购买个人电脑的顾客中，9 0 也购买了打印机 就是一种关联模式。关联模式发现主 要用于零售业交易数据分析，以进行物品更合理的摆放，最终提高销售量，也称为 “货篮分析”。现在己应用到欺诈发现、电信呼叫分析、客户保持等方面。 ( 3 ) 分类和预测( c l a s s i f i c a t i o na n dp r e d i c t i o n ) 分类就是依照所分析对象的属性分门别类、加以定义、建立类组。分类的关键 是确定对数据按照什么标准或什么规则进行分类。因此，分类时首先根据属性特征， 为每一种类别找到一个合理的描述或模型，即确定分类规则；再根据规则对数据进 行分类。预测就是利用历史数据建立模型，再运用最新数据作为输入值，获得未来 变化的趋势或者评估给定样本可能具有的属性值或值的范围。 ( 4 ) 聚类分析( c l u s t e r i n ga n a l y s i s ) 聚类分析又称为无指导的学习，其目的在于客观地按被处理对象的特征分类， 根据最大化类内的相似性、最小化类间的相似性的原则进行分组，由于在数据挖掘 3 嵌入式与导出式频繁子树挖掘算法研究 之前，数据类划分的数量与类型均是未知的，因此在数据挖掘后需要对数据挖掘结 果进行合理的分析与解释。 ( 5 ) 孤立点分析( o u t l i e ra n a l y s i s ) 孤立点是指数据库中包含的一些与数据的一般行为或模型不一致的数据。大部 分的数据挖掘方法将孤立点视为噪声或异常丢弃，而对某些应用，如欺骗检测等， 孤立点数据可能更有价值。 ( 6 ) 演变分析( e v o l u t i o na n a l y s i s ) 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。 1 2 关联规则 1 2 1 基本概念 关联规则是数据挖掘的重要研究领域之一，由r a g r a w a l 于1 9 9 3 年提出，它在商 业领域的成功应用，使它成为数据挖掘中最成熟、最重要、最活跃的研究内容。关 联规则是基于客户交易数据库，用来解决项集之间关联问题的。关联规则是形如 “a b ”的蕴含式，反映一个事物与其他事物之间的相互依存性和关联性。如果两 个事物或多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他 事物预测到。关联规则挖掘就是要找出隐藏在数据间的相互关系，发现大量数据中 项目集之间满足一些基本要求( 如最小支持度和最小置信度) 的所有有趣的关联或 相关性。 根据不同的标准，关联规则可以分成不同的类型。根据规则所处理的值的类型， 关联规则可以分为布尔的和量化的。根据规则中数据涉及的抽象层，关联规则可以 分为单维的和多维的。根据规则涉及的抽象层，关联规则可以分为单层的和多层的。 1 2 2 关联规则挖掘方法 关联规则挖掘主要分为两步：一是找出所有频繁模式集；二是由频繁模式集产 生关联规则。由于第二步容易实现，因此关联规则挖掘的性能主要取决于频繁模式 挖掘。 由事务数据库挖掘单维布尔关联规则有两种基本算法：基于广度优先的算法和 基于深度优先的算法，分别以a p r i o r i 算法【5 1 和f p g r o w t h 算法【6 】为代表。为提高挖 掘效率，人们提出许多优化策略，比如划分原数据，采用并行算法等。由事务数据 库挖掘多层关联规则可以在不同层使用一致的最小支持度，但由于较低层次抽象的 项不大可能像较高层次抽象的项出现得那么频繁，因此设置合适的最小支持度比较 4 第一章引言 困难；也可以在较低层使用递减的最小支持度使挖掘出的关联规则更符合决策要求。 在关系数据库和数据仓库中挖掘多维关联规则的技术，根据量化属性的的处理可分 为三种基本方法：使用量化属性的静态离散化挖掘多维关联规则；使用分箱技术的 动态离散化挖掘量化关联规则；在动态离散化过程中考虑数据点之间的距离，可以 挖掘基于距离的关联规则。 数据挖掘过程可能产生大量的规则，基于约束的挖掘可在用户提供的各种约束 条件下进行，挖掘用户感兴趣的规则。如最大频繁模式7 - 9 1 挖掘和闭合频繁模式【l o 1 3 】 挖掘等为人们所关注。 1 3 频繁模式挖掘 随着信息技术的发展，各种复杂数据如生物信息数据，w e b 数据，化合物结构 等数据出现，如何从这些数据中找出频繁出现的模式，支持相关领域的研究工作， 成为人们研究的新课题。经过十几年的研究，频繁模式挖掘的理论基础已相对成熟， 根据不同的挖掘策略，挖掘方法可分为两大类：一类是宽度优先的逐层挖掘算法， 一类是深度优先的模式增长算法。根据挖掘对象的不同，可分为频繁项集挖掘，序 列频繁模式挖掘，频繁子树挖掘和频繁子图挖掘等。 1 3 1 频繁项集 自a p r i o r i 算法提出以来，频繁项集挖掘作为关联规则挖掘中的核心和关键，得 到许多学者的研究，其方法主要分为两类。 - 一类以a p f i o f i 算法【5 】为代表，a p n o d 算法使用了频繁项集的先验知识：频繁项 集的所有非空子集都必须也是频繁的( 也称a p f i o n 性质) 。该算法的优势是其挖掘 大型事务库的能力，不需要将事务库读入内存就可以完成挖掘工作。然而该算法需 要多次扫描数据库，扫描次数等于发现的最长的频繁项集的项的个数。许多学者对 算法的连接和剪枝过程进行各种优化，如压缩搜索空间；减小候选模式数量；减小 数据库扫描次数等，提出了改进的算法。典型的算法有a p r i o r i t i d 算法【1 4 1 、a p d o r i p r o 算法15 1 、a p r i o d h y b d d 算、法【1 6 】等，但它们本质上没有什么变化，都要在挖掘过程中 生成大量的候选模式。 另一类以f p g r o w t h 算法1 6 l 为代表，该算法采用分治策略，将所有频繁1 项集压 缩到一棵频繁模式树( f p 树) ，同时保留项集关联信息；然后将这种压缩后的数据 库分成一组条件数据库，每个关联一个频繁项，并分别挖掘每个数据库。研究表明： f p g r o w t h 方法对于挖掘长的和短的频繁模式都是有效的和可伸缩的，并且大约比 嵌入式与导出式频繁子树挖掘算法研究 a p r i o r i 算法快一个数量级。f p g r o w t h 方法的不足在于，当存在许多长而复杂的模 式时，需要递归构造的条件树数量巨大，时空代价较高。典型的改进算法有：h m i n e 算法【1 刀，h y b r i d p r o j e c t i o n 算法【1 8 1 等。 1 3 2 序列频繁模式 序列模式的概念最早是f l ：l a g r a w a lr 和s r i k a n tr 【1 9 2 0 1 提出的。序列模式挖掘是指 给定一个由不同序列组成的集合，其中每个序列由不同的元素按顺序有序排列，每 个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘 就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的 最小支持度阈值。 序列频繁模式挖掘应用广泛，包括顾客购买行为的分析、网络访问模式分析、 科学计算的分析、疾病治疗的早期诊断、自然灾害的预测、d n a 序列模式的分析等。 目前序列模式挖掘算法可以分为3 类：( 1 ) 基于a p d o r i 的候选生成测试的方法， 代表性算法有：a p r i o r i a l l 算法【1 9 1 、g s p 算法【2 0 】； ( 2 ) 基于垂直格式的候选码生成 测试的方法，代表性算法有：s p a d e 算法【2 1 】；( 3 ) 基于投影的模式增长方法，无候 选产生，效率较高，代表性算法有：f r e e s p a n 算、法t 2 2 1 、p r e f i x s p a n 算法吲等。p r e f i x s p a n 是目前序列模式挖掘中效率最高的算法之一。此外，还有一些其它的扩展研究，如 基于规则表达式约束的序列模式挖掘，序列模式闭项挖掘，并行挖掘，分布式挖掘， 多维度序列模式挖掘和近似序列模式挖掘等。 1 3 3 频繁子树 树挖掘( t r e e m i n i n g ) 在计算机网络、w e b 挖掘、生物信息、多关系数据挖掘、x m l 文档挖掘等很多领域都具有重要的应用价值。传统的数据挖掘技术在这些领域中无 法奏效，因为这些领域中的数据对象不是简单的集合关系，而是具有结构层次等各 种各样的关系。传统的关系数据库作为二维表关系结构数据的载体，虽然非常的简 单且易于处理，但是不能刻画这类数据对象之间的内在关系。而树和图则具备了很 强的表达能力，可以刻画物质世界中大多数对象的特征和相互关系，尤其是树结构， 不但能够表达复杂的关系，而且相比图挖掘的算法具有较高的效率。当前很多领域 的数据都可以模型化为树结构，对这些模型化为树结构的数据进行挖掘具备了广泛 的应用基础。1 4 节将详细介绍频繁子树挖掘研究现状。 1 3 4 频繁子图 图结构是最通用的数据结构类型，它可以描述世界万物之间错综复杂的联系。 频繁子图挖掘首先由i n o k u c h i 等人提出，由图论作为理论基础，频繁子图挖掘得到 6 第一章引言 很快发展，并广泛应用到生物信息、机器学习、计算机网络等许多领域中，如在生 物信息中，通过频繁子图预测化合物的癌变；通过对网站浏览日志的挖掘，分析出 用户最频繁的浏览模式，改善网站拓扑结构等。 频繁子图挖掘算法主要分为两类：( 1 ) 基于a p f i o r i 思想的算法，典型的算法有： a g m 算法【2 4 j 、f s g 算法【2 5 】、a m g m 算法【2 6 1 等。( 2 ) 基于f p g r o w t h 思想的算法， 典型的算法有：g s p a n 算法【2 7 1 、c l o s e g r a p h 算法【2 8 1 、a d e s a p 算法【2 9 1 、s f p 算法【2 6 】 等。根据频繁子图的类型，频繁子图挖掘可分为一般子图、导出子图、连通子图等。 如a g m 算法挖掘导出子图，a c g m 算法及f s g 算法等挖掘连通子图。 频繁模式挖掘经常会产生大量的模式和规则，不但降低了算法的执行效率，同 时也使用户从频繁模式产生有用的规则变得很困难。针对这个问题，最近的研究主 要集中于两点：一种方法是允许用户通过加以约束来引导挖掘的过程，通过把约束 条件下推到挖掘的底层来缩小模式搜索的空间，提高性能；另一种方法是挖掘闭合 及最大频繁模式( 包括闭合及最大频繁项集、子树、子图等) ，在保持信息的完整 性的前提下，很大程度地减少结果集的大小，从这个精简的结果集中，可以很直接 地产生所有的频繁模式。 1 4 频繁子树挖掘研究现状 树结构和图结构作为表达半结构化数据的一种载体，可以清晰的描述对象的特 征，具有一定的通用性，相对图结构数据来说，树结构数据更简单易用，树是连通 有向无环图，是图的一种特例。 频繁子树挖掘可分为不同类型。根据应用的对象范围不同，频繁子树挖掘算法 包括有序标号树频繁子树挖掘、有根无序树频繁子树挖掘和自由树中频繁子树挖掘 三个主要的方向。根据子树类型的不同，频繁子树挖掘算法主要包括：频繁嵌入式 及导出式子树挖掘、闭合及最大频繁子树挖掘、挖掘频繁子树精简基以及在数据流 中挖掘频繁子树等。 1 4 1 频繁嵌入式及导出式子树 这两种类型的频繁子树挖掘算法都是挖掘频繁子树完全集，是其它类型的树挖 掘算法( 如闭合及最大频繁子树挖掘) 的基础。主要的研究成果有：2 0 0 2 年，z a k i 等人提出p a t t e m m a t c h e r 及t r e e m i n e r 算法【3 0 1 在有序标号树集中挖掘频繁嵌入式子树， 前者采用类a p f i o f i 的宽度优先搜索策略，后者采用深度优先遍历搜索的方法。 t r e e m i n e r 算法的效率l l , p a t t e r n m a t c h e r 算法高出大约4 2 0 倍，成为当时最优的频繁嵌 7 嵌入式与导出式频繁子树挖掘算法研究 入式子树挖掘算法。2 0 0 4 年，他们又提出s l e u t h 算法【3 1 】，在无序树中挖掘频繁嵌 入式子树，采用一种新的等价类扩展框架生成所有的候选子树，扩展s c o p e 1 i s t 连接操 作计数候选子树的支持度。2 0 0 2 年，a t e r m i e r 等人提出在x m l 数据中挖掘频繁子树 的t r e e f i n d e r 算法【3 2 】，x m l 数据可以看成有根无序树集合，该算法在数据处理过程中 采用非精确匹配的方法，不能保证结果的完整性。同年，a s m 等人提出在有序标号树 集中挖掘频繁导出式子树的f r e q t ：算、法【3 3 1 ，采用最右扩展技术建立枚举树，并深度 优先地逐层挖掘，算法采用了“候选生成测试”的方法，当树规模较大或支持度较 小时，候选模式树集合非常大，算法性能会急剧下降，甚至无法完成挖掘任务。2 0 0 3 年，他们扩展f r e q t ：算法思想，提出u n o t 算法【3 4 】在无序标号树集中挖掘频繁导出式 子树。2 0 0 3 年，s n i j s s e n 等人扩展f r e q t 算法思想，提出无序标号树集中挖掘频繁 导出式子树的u f r e q t 算法【3 5 】，利用无序树的规范表达，在枚举频繁子树时更方便直 接，并保证不丢失、不重复。2 0 0 4 年，他们又提g a s t o n 算法【36 1 。在自由树集合中 挖掘频繁导出式子树，采用混合式的深度优先遍历方法。2 0 0 3 年，潘瑾等人提出 c h o p p e r 3 v j 算法挖掘频繁嵌入式子树，利用了序列挖掘的方法，提出“先频繁序列， 再频繁结构”的思想，逐步求精，极大地压缩搜索空间。2 0 0 3 年，y c h i 等人提出在 自由树集中挖掘频繁导出式子树i 拘f r e e t r e e m i n e r 算法【3 引，采用了宽度遍历思想，通 过“交”操作生成候选项。2 0 0 4 年，他们又提出在有根无序树和自由树集合中挖掘 频繁导出式子树的h y b r i d t r e e m i n e r 算法【3 9 1 ，采用混合式的搜索遍历方法，同时使用 “交 和“扩展”两种操作，保证每个候选子树至少被遍历到一次，并提出了一种 新的树规范表达方法。2 0 0 4 年，王晨提出x s p 锄e r 算法1 4 0 】，对c h o p p 算法改进，发 现频繁序列后立即重构子树，避免了不可能重构出频繁子树结构的频繁序列在算法 中继续扩展。2 0 0 5 年，他又提出了e s m 血e r 算法2 乏i s m i n e r 算法【4 0 j 分别挖掘频繁嵌入 式及导出式子树，基于最右路径模式增长的思想，利用前缀子树模式的最右路径， 有效地分隔投影库，使最右路径上节点的分投影库尽可能小，从而提高搜索频繁候 选节点的效率。i s m m e r - 算法采用同样的策略只关心最右路径上节点的直接孩子节点 来挖掘频繁导出式子树。2 0 0 4 年，朱永泰等人提出e s p m 【4 l 】算法，避免t c h o p p e r l 算 法把挖掘过程分为两个阶段的缺点，及时删减了不频繁的异构体，提高了算法效率， 但在投影库中搜索到的频繁节点中，仍然存在许多不能生成频繁子树的无用节点， 需要再次扫描数据库确定哪些节点能够生成频繁子树。2 0 0 5 年，s h o h e ih i d o 等人提 出a m i o t 【4 2 】算法，采用“候选生成测试的方法挖掘频繁导出式子树，利用连接技 术产生候选子树，比f r e q t 算法生成的候选子树较少，提高了效率。2 0 0 5 年，杨沛 8 第一章引言 等人提出p f t m t 4 3 】算法挖掘频繁导出式子树，利用递推式的候选节点集更新技术来压 缩搜索空间，避免 f r e q t 算法多次扫描子树最右路径上节点的子节点集的缺点； 用c 矩阵来计数候选节点支持度，p f t m 算法不需要产生候选子树，i ：匕f r e q t 算法效 率平均高出4 0 左右。2 0 0 6 年，赵传申等人提, f l u , f t p b 删算法，利用最右路径扩展的 模式增长方法挖掘频繁嵌入式子树，引入投影分支来构造投影库，在计算投影分支 的同时解决树同构的判断问题，由当前频繁子树直接生成新的频繁子树，减少了数 据库扫描次数。2 0 0 6 年，陈子军等人提出p e t r e e m i n e r t 4 5 】算法，利用序列挖掘的前缀 投影技术来挖掘频繁嵌入式子树，在树的先序遍历序列中加人结点的范围属性，使 得序列中包含树结点之间关系的信息。在投影过程中利用结点的范围属性对结点进 行编码，得到带有编码的序列，因此，所得到的频繁子序列也包含树结点之间关系 的信息，使得挖掘到的频繁子序列与一棵频繁子树一一对应。2 0 0 6 年，马海兵提出 在无序树构成的森林中挖掘频繁导出式子树的u t - g r o w t h 算法1 4 6 j ，该算法用规范化方 法唯一表示无序树，用最右路径扩展方法构造完整的模式增长空间，取得比 h y b r i d t r e e m i n e r 算法更高的效率。2 0 0 6 年，l e iz o u 等人提出p r e f i x t r e e e s p a n 【4 7 】算法 挖掘频繁嵌入式子树，采用分而治之的策略，在前缀树投影数据库中递归挖掘长度 为1 的频繁子树，直到挖掘出所有频繁子树。2 0 0 7 年，李伟提p e i t m t 4 8 】算法，采用 与p e t r e e m i n e r 算法相同的模式，在编码过程中只对当前节点的直接孩子节点及右兄 弟节点进行编码，达到挖掘频繁导出式子树的目的。 1 4 2 闭合与最大频繁子树 以上各种算法都是挖掘频繁子树完全集，结果集会随着树结构数据库的增大而 呈爆炸式增长，这将导致两个问题，首先，终端用户无法对大量的频繁子树进行分 析并从其中获取有用的信息，限制了其应用；另一方面，由于频繁子树的数量过于 庞大，挖掘算法会变得难以处理而导致算法效率低下。为了压缩频繁子树集合，提 出挖掘最大频繁子树及闭合频繁子树。 目前，闭合及最大频繁子树挖掘的主要研究成果有：2 0 0 3 年，y x i a o 等人提出在 有根无序树中挖掘最大频繁子树p a t h j o i n 算法【4 9 1 ，用f s t - f o r e s t 结构存放所有路径， 先找最大频繁路径，再连接频繁路径找最大频繁子树，非最大频繁子树被剪掉。同 年，y c h i 等人提出t c m t r e e m i n e r 算法【5 0 】，通过遍历枚举树在无序树集中挖掘闭合 与最大频繁子树，采用基于剪枝和启发式技术减小搜索空间。2 0 0 4 年，吴共庆等人 提出f p f m 算法【”l ，采用最右扩展枚举方法实现了无重复枚举所有候选模式，利用频 繁模式扩展森林实现高效剪枝扩展和挖掘频繁叶模式，通过计算频繁叶模式间的包 9 嵌入式与导出式频繁子树挖掘算法研究 含关系挖掘最大频繁子树。2 0 0 7 年，朱颖雯等到人提出挖掘可变支持度约束的闭合 与最大频繁导出式子树的算法s c c m t r e e m i n e r l 5 2 1 ，采用最右扩展技术枚举候选子树， 挖掘过程中最小支持度随着树中节点数的增加而减小，有利于挖掘长子树。同年， 他们又提出【5 3 j 算法挖掘最大频繁嵌入式子树，该算法先序遍历存储树，并加入节点 的范围属性，采用伪投影技术对频繁子序列进行投影，并对第个节点编码。在挖掘 带编码的频繁子序列的过程中，高效剪枝。2 0 0 8 年，杨沛等人提出m f t m 算法【5 4 1 ， 在有序标号树集中挖掘极大频繁子树，基于最右路径扩展技术，在搜索过程中，采 用覆盖定理进行裁剪，压缩搜索空间，加快算法的收敛速度。 1 4 3 频繁子树精简基 频繁模式精简基【55 】的提出是基于这样一个事实：许多应用中并不需要频繁模式 的特别精确的支持度。用户可能对支持度的一个好的近似( 支持度计数在一定的误 差范围内) 更感兴趣。如某个模式的支持度计数为1 0 0 0 0 1 ，1 即为允许的最大 误差，称为误差边界。由频繁模式精简基可以推导出任何频繁模式的满足一定精度 要求的支持度。 王涛等人把频繁模式精简基理论运用到频繁子树挖掘中1 5 6 】，由相对于一系列支 持度阈值的最大频繁子树组成频繁子树精简基，用来估计任一频繁子树的支持度， 并能将误差控制在确定范围内。这样大大减小了频繁子树结果集的大小，且算法性 能比挖掘全集的算法要高。 由于网络技术和w e b 技术的发展，流数据大量出现，如服务器上的用户访问信 息等，从这些半结构化的数据流中挖掘频繁子树阳也是近期研究的一个重要方向。 另外，基于约束的频繁子树挖掘也得到广泛研究，通过设定约束条件5 o l ，可以挖 掘用户感兴趣的频繁子树。 1 5 本文的主要研究内容及论文的组织结构 1 5 1 论文的主要研究内容 频繁子树挖掘是一种重要的数据挖掘任务，在w e b 挖掘、生物信息处理等领域 具有广泛的应用。本文采用最右路径扩展技术，针对当前提出的频繁子树挖掘算法 中存在的一些问题，提出了一些改进的措施。主要从改进投影库的构造策略、减小 投影库的规模、提高投影库中节点的计数效率等方面进行了研究。 针对频繁嵌入式子树挖掘算法，利用离散区间来构造投影库，给出一种基于离 散区间的频繁嵌入式子树挖掘算法d i f t m 。该算法通过离散区间消除冗余投影，有 1 0 第一章引言 效地压缩投影库的规模，同时提高了子树节点计数效率，减低了算法的时空复杂性。 针对频繁导出式子树，给出种基于编码的频繁导出式子树挖掘算法e f i t m 。该算 法通过宽度优先编码来表示原始数据库，使每个投影的规模最小，通过对投影库中 各投影编码降低了投影库规模，从而有效地提高了频繁导出式子树的挖掘效率。实 验验证了这两个算法具有较高的挖掘效率。 1 5 2 论文的组织结构 论文共分为五章，具体组织如下： 第一章介绍了数据挖掘的相关知识、关联规则、频繁模式挖掘的研究内容以及 频繁子树挖掘的国内外研究现状。 第二章介绍了频繁子树的相关概念、规范表达、以及频繁子树挖掘的基本方法。 第三章主要研究了种基于离散区间的频繁嵌入式子树挖掘算法。 第四章主要研究了一种基于编码的频繁导出式子树挖掘算法。 第五章是对本文研究内容的总结以及对进一步研究工作的展望。 第二章频繁子树 第二章频繁子树 2 1 基本概念 树型结构具有表达数据清晰、简洁等特点，因此它成为刻画半结构化数据的主 要载体。树的类型有多种，如无根无序树( 也称自由树) 、有根无序树、有根有序树等， 不同类型的树具有不同的数据表达能力和范畴。本文中涉及到的树结构类型仅限于 有根有序标号树。参照文献 3 0 ，3 3 ，4 0 】，下面给出有关树的一些基本定义。 定义2 1 ( 树的大小) 给定一棵树t ( v o ) ，v o 是根节点。树t 中节点的数量称为 树的大小，记为l t l 。 定义2 2 ( 树高) 给定一棵树t ( v o ) ，v o 是根节点。节点v 的深度定义为从v o 到 v