（计算机软件与理论专业论文）基于连接和合并的子树挖掘算法研究.pdf

兰州大学硕士研究生毕业论文 摘要 近年来，数据挖掘作为一门正处于蓬勃发展期的学科，其应用己经渗透到了 许多领域并且在人工智能与机器学习、数据库、模式识别、生物信息学、神经计 算等方向上取得了丰硕的成果。 子树挖掘作为一种半结构化的数据挖掘问题是数据挖掘领域中一个较新的 分支，它在生物学、w e b 数据分析和化合物结构分析等许多领域都有广泛的应用 前景。本文对子树挖掘的基本概念、研究现状和一些典型算法进行了较为深入的 讨论和研究，在此基础上提出了一种新的基于合并和连接的频繁子树挖掘机制和 相应的算法。 首先提出了子树挖掘算法c c t r e e m i n e r ( c o m b i n a t i o na n dc o n n e c t i o n t r e e m i n e r ) 。与基于最右路径和前缀等价类等模式扩展方法不同，算法主要通过 合并具有相同根结点的子树和连接频繁二项树的叶结点与频繁子树的根结点来 生成不确定大小的候选超模式，同时提出了相应的剪枝策略。通过分析证明了 c c t r e e m i n e r 挖掘结果的完整性和正确性。 其次，提出了用于挖掘封闭式子树模式的c t m i n e r ( c l o s e dt r e e m i n e r ) 算法。 该算法是对c c t r e e m i n e r 的扩展，在合并和连接中加入了更有效的剪枝策略和 检测机制来提高算法的效率。同时本文对c t m i n e r 算法的实验结果进行了分析 并提出了下一步工作的内容。 以上两种算法只需对数据库进行一次扫描，并且保证所有被扩展的候选模式 至少在数据库中有一次出现。 关键词：子树挖掘，频繁子树，连接，合并，封闭子树，剪枝 兰州大学硕士研究生毕业论文 a b s t r a c t i nr e c e n ty e a r s ，d a t am i n i n g ( d m ) h a sg r o w nv i g o r o u s l ya n di t sa p p l i c a t i o n s h a v ea l r e a d yc o m ei n t om a n ya r e a sa n da c h i e v e dp l e n t i f u lf r u i t s i nv a r i e df i e l d s i n c l u d i n ga r t i f i c i a li n t e l l i g e n c ea n dm a c h i n el e a r n i n g , d a t a b a s e ，b i o i n f o r m a t i c s ， p a t t e r nr e c o g n i t i o n ，n e u r a lc o m p u t i n ga n do t h e rf i e l d s b e i n gas e m i s t r u c t u r e dd a t am i n i n gp r o b l e m ，s u b t r e em i n i n gi sar e l a t i v e l yn e w b r a n c hy e th a sm a n ya p p l i c a t i o n si nd o m a i n ss u c ha sb i o l o g y , w e bd a t aa n a l y s i sa n d c o m p o u n de l e m e n t a r ya n a l y s i sa n ds oo n t h i st h e s i sd i s c u s s e st h eb a s i cc o n c e p t sa n d s u m m a r i z e st h ec u r r e n tr e s e a r c hs t a t u so fs u b t r e em i n i n ga n dt h e ni n t r o d u c e san o v e l m e c h a n i s ma n di t s c o r r e s p o n d i n ga l g o r i t h m sf o rf r e q u e n t t r e ep a t t e r nd i s c o v e r i e s w h i c hi sb a s e do nc o n n e c t i o na n dc o m b i n a t i o n f i r s t ，an o v e la l g o r i t h mn a m e l yc c t r e e - m i n e r ( c o m b i n a t i o na n dc o n n e c t i o n t r e e m i n e r ) i sp r e s e n t e d i n s t e a do ft r a d i t i o n a lp a t t e r ng r o w t hm e t h o d ss u c ha st h o s e b a s e do np r e - s t r i n ge q u i v a l e n c ec l a s so rr i g h tm o s tp a t he x t e n s i o n ，c c t r e e - m i n e r c o n n e c t sb e t w e e nt h el e a fo ff r e q u e n t - 2s u b t r e ea n dt h er o o to ff r e q u e n ts u b t r e eo r c o m b i n e st h er o o t so ff r e q u e n ts u b t r e e st op r o d u c es u p e r - c a n d i d a t ep a t t e r no fa r b i t r a r y s i z e t h es t r a t e g yo fs e a r c hs p a c ep r u n i n gi st h e nd i s c u s s e da n dt h ei n t e g r i t yo f m i n i n gr e s u l t si sa l s op r o v e d s e c o n d l y , a na l g o r i t h mc t m i n e r ( c l o s e dt r e e m i n e r ) f o rm i n i n gc l o s e ds u b t r e e p a t t e r n si sp r e s e n t e dw h i c hi sa na l t e r a t i o no fc c t r e e m i n e r , t ow h i c h ，m o r ep o w e r f u l p r u n i n gt e c h n i q u e sa r ea d d e df o rh i g h e re f f i c i e n c y w ea n a l y s i st h ee x p e r i m e n t a l r e s u l t so fc t m i n e ra n db r i n gf o r w a r dt h ef u t u r ew o r k t h e r ea r et w om a i na d v a n t a g e so ft h ea l g o r i t h m si n t r o d u c e di nt h i st h e s i s ：f i r s t ， t h ed a t a b a s et ob em i n e di ss c a n n e do n c ea n do n c eo n l y ；s e c o n d l y , w ec a nm a k es u r e t h a te v e r yc a n d i d a t et r e ep a t t e r ne x t e n d e dh a sa tl e a s to n ea p p e a r a n c ei nt h ed a t a b a s e k e yw o r d s ：s u b t r e em i n i n g , f r e q u e n ts u b t r e e ，c o n n e c t ，c o m b i n e ，c l o s e ds u b t r e e ， p r u n i n g 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内 容外，不包含任何其他个人或集体己经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式 标明。 本声明的法律责任由本人承担。 论文作者签名：么孽垂坠 日期： 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产 权归属兰州大学。本人完全了解兰州大学有关保存、使用学位论 文的规定，同意学校保存或向国家有关部门或机构送交论文的纸 质版和电子版，允许论文被查阅和借阅；本人授权兰州大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以 采用任何复制手段保存和汇编本学位论文。本人离校后发表、使 用学位论文或与该论文直接相关的学术论文或成果时，第一署名 单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：艘导师签名：壹：l 蠡 日期：蔓立：盘茎 兰州大学硕一卜研究生毕业论文 第一章绪论弟一早三百下匕 1 1 数据挖掘研究工作背景 我们现在已经生活在一个网络化信息化的时代，通信、计算机和网络技术正 改变着整个人类社会，信息化给各国的社会经济发展带来了新的机遇和挑战并将 对未来的社会发展产生深远的影响。 随着信息技术特别是数据库技术的迅猛发展，数据采集、生成和传播等技术 获得了极大的提高，在技术上实现了全球的信息共享。但随之而来的问题是当人 们积累的数据越来越多，激增的数据背后隐藏着许多重要的信息，人们希望能够 对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高 效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则， 无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手 段，导致了“数据爆炸但知识贫乏”的现象。 数据库知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 技术正是在上述 的应用要求下产生的。事实上，知识的发现不仅仅局限于数据库，发现的目标也 可以是数据集、数据仓库或者是其他信息的集合。由于知识发现是一门受到来自 各种不同领域的研究者关注的交叉性学科，因此导致了很多不同术语的出现，如： “数据挖掘”( d a t am i n i n g ，d m ) 、“知识抽取”( i n f o r m a t i o ne x t r a c t i o n ) ，“信息发现” ( i n f o r m a t i o nd i s c o v e r y ) 和“数据考古”( d a t aa r c h e o l o g y ) 等。目前最常用的术语 是“数据挖掘”和“知识发现”。“数据挖掘”一词是在1 9 8 9 年于美国底特律市召开 的第1 1 界国际联合人工智能学术会议上首次提出的。许多人把数据挖掘视为 k d d 的同义词，而另一些人只是把数据挖掘视为k d d 的一个基本步骤。通常， 人们并不严格区分以上的这些术语而常常将它们混用。 1 9 9 5 年，第一届知识发现和数据挖掘国际学术会议在加拿大蒙特利尔召开。 从此，每年主办一次k d d 国际学术会议更是将数据挖掘和知识发现方面的研究 推向了高潮，其规模也由原先的专题讨论会发展到国际学术大会。k n o w l e d g ea n d d a t ae n g i n e e r i n g 会刊于1 9 9 3 年出版了k d d 技术专刊，而很多相关领域的国际 学会和学刊也把数据挖掘和知识发现列为专题和专刊来讨论，研究重点也渐渐转 向实际应用。此外，因特网上也出现了很多相关出版物，其中k n o w l e d g ed i s c o v e r y 兰州大学硕七研究生毕业论文 n u g g e t s ( h t t p ：w w w k d n u g g e t s c o m ) 较有影响力。在应用方面，国际上比较有 影响的典型数据挖掘系统有c o v e rs t o r y 、e x p l o r a 、k n o w l e d g ed i s c o v e r y w o r k b e n c h 、d bm i n e r 、q u e s t 等。此外网站h t t p ：w w w d a t a m i n i n g l a b r c o m 提供 了很多数据挖掘系统和工具的性能测试报告。 1 2 数据挖掘技术概述 1 2 1 数据挖掘的定义 数据挖掘是指从大量的、可能不完全、不一致或者有噪声的、模糊的数据集 中提取出事先未知且存在潜在有趣价值的信息、知识和规律的非平凡过程。 对象数据集可能是不完全或者不一致的，比如某些感兴趣的属性缺少属性值 或存在不一致等；噪声是指测量变量中随机出现的偏差。实现数据的完整性、消 除不一致和噪声属于挖掘前的数据清理工作( 详见文献【1 ，2 】) ，本文不做讨论。兴 趣度是数据挖掘概念中的一个重要参数，对它的选取在很大程度上决定了数据挖 掘结果的有效性。通常每个兴趣度都关联一个可由用户定义的阈值，比如在聚类 过程中，若耦合度超过某个阈值则可认为是有趣的；而频繁模式挖掘中，兴趣度 可定义为模式至少要出现的次数。非平凡是指数据挖掘的过程要具有一定程度的 智能性、自动性( 仅仅给出所有数据的总和不能算作是一个发现过程) 。 数据挖掘作为知识发现过程中一个特定的步骤，是一系列技术及其应用，或 者说是对大容量数据及数据之间的关系进行考察和建模的方法集。它的目标是将 大容量数据转化为有用的知识和信息。目前，数据挖掘技术已经在许多行业得到 应用并取得了一定的实效。它不但可以帮助人们从数据库，特别是从数据仓库的 相关数据中提取出感兴趣的知识、规律或其他更高层次的信息，而且也可以帮助 人们从不同程度上去分析它们，从而更有效地利用数据库或数据仓库中的数据。 数据挖掘不仅可以用于描述过去数据的发展过程，而且还能进一步预测未来的发 展趋势，它是人们长期对信息技术尤其是数据库技术研究和开发的自然演化结 果。通过数据挖掘，有价值的知识、规则或高层次的信息能够从数据库的相关数 据集合中被抽取出来，并以不同的角度显示给拥有不同需求的用户，从而使大型 数据库作为一个丰富、可靠的资源为知识的提取服务。 2 兰州大学顾：t 研究生毕业论文 数据挖掘技术是数据库技术快速发展和广泛应用的结果。数据库技术经历了 数据搜集、数据访问、数据仓库与决策支持、数据挖掘等几个发展阶段阶段。从 上个世纪6 0 年代以来，数据库处理已经从原始的文件处理演化为对复杂且功能 强大的数据库系统的处理。到7 0 年代，数据库技术日益成熟，已经能够存放大 规模的数据集合。8 0 年代数据库进入了标准化的发展阶段，出现了结构化查询 语言( s t r u c t u r e dq u e r yl a n g u a g e s q l ) 标准、开放式数据库接口( o p e nd a t a b a s e c o n n e c t i v i t y o d b c ) 等。与此同时产生了面向对象、对象关系模型、演义 模型等先进的数据模型，出现了时间、空间、分布式、多媒体、主动和科学计算 数据库，知识库等多种面向应用领域的数据库系统。9 0 年代以来，数据库技术 进入了一个崭新的发展阶段，出现了联机分析处理( o n l i n ea n a l y t i c a l p r o c e s s i n g o l a p ) 、多维数据库( m u l t id i m e n s i o n a ld a t a b a s e m d d ) 、数据仓 库( d a t aw a r e h o u s e d w ) 和基于w e b 的数据库系统等新技术。 1 2 2 数据挖掘的步骤 数据挖掘过程包含如下几个步骤：选择提取、预处理、转换、挖掘、表达和 分析评价【3 ，4 j 。 1 数据选择抽取( s e l e c t i o n ) ：数据挖掘所使用的原始数据规模庞大，具有 多源和异构的特性，数据选择抽取就是从各种数据库、数据集，数据文件等来源 提取出所需要的原始数据。 2 数据预处理( p r e p r o c e s s i n g ) 从各种来源抽取的数据可能存在不正确、 不一致、缺失等问题，数据类型和度量单位也可能不一致，而数据预处理可以很 好的解决这些问题。 3 数据转换( t r a n s f o r m a t i o n ) ：为了方便数据挖掘，数据转换将预处理后的 数据进行编码、约简、汇总、聚集等，转换为统一的数据格式。 4 数据挖掘( d a t am i n i n g ) ：根据数据挖掘任务的不同，采取不同的挖掘算 法。提取数据模式或模型。 5 知识表达和分析评价( i n t e r p r e t a t i o n e v a l u a t i o n ) ：将挖掘的知识、规则以 用户易于理解的方式提供给用户以满足用户交互式挖掘的要求，一般涉及到可视 化图形界面( g u i ) 。 3 兰州大学硕上研究生毕业论文 1 3 数据挖掘任务的分类 数据挖掘的两个基本目标是预测和描述。预测涉及到使用数据集中的一些变 量或属性来预测其他我们关心的未知值；描述关注的则是找出可由人们解释的数 据模式。因此，数据挖掘任务一般可以分为“预测性数据挖掘和“描述性数据 挖掘”两大类。预测型数据挖掘主要是找出已知的数据集所蕴含的系统模型并进 行推断和预测；描述型数据挖掘主要用于刻画数据集中数据的一般特性，并在此 基础上生成新的未知信息。根据数据挖掘的基本功能大致可以归纳为6 种l l j ： 1 概念描述( c o n c e p td e 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 ) ：关联分析主要是挖掘大量数据集合中 项集之间有趣的关联规则或联系。关联分析的结果一般有两种：关联规则和序列 模式。它是无指导机器学习系统中挖掘本地模式的最普通型式，利用该过程可以 获取数据集合中事先并不了解或并不肯定的有价值信息。 3 分类和预测( c l a s s i f i c a t i o na n dp r e d i c a t i o n ) ：分类是找出描述并区分数据 类和概念的规律或模型以便能够预测未知的信息。大量的数据对象可以根据其表 象特征区分为不同的类，它们之间具有内在的本质差别，如何通过这些不同的表 象挖掘出它们内在性质上的不同是分类方法的主要工作。在分类的基础上进一步 推演以实现推测数据对象的类标记和部分数据值的过程称为预测。分类常用的方 法有：决策树方法、粗集方法、贝叶斯( b a y e s ) 方法、人工神经网络方法和遗 传算法等。 4 聚类分析( c l u s t e r i n ga n a l y s i s ) ：聚类分析是将物理或抽象的数据对象集 合划分为表象特征相近的多个类，在同类中的数据具有表象的相似性，而类间的 数据具有表象的相异性。聚类分析是一种普遍的描述性任务，它与分类不同，主 要分析数据对象而不考虑预先定义的类和已知的类标记。聚类主要采用基于距离 的距离分析。常用方法有：遗传算法、划分法、层次法、基于密度的方法、基于 网格的方法和基于模型的方法。 5 异类分析( o u t l i e ra n a l y s i s ) ：在系统中存在一些数据，它们不符合数据 的一般模型，与其他数据对象不一致，这样的数据对象称为孤立点。孤立点可能 是度量或者操作错误造成的，也可能是固有的数据变异结果。在大多数情况下要 4 兰州大学硕上研究生毕业论文 求孤立点的影响最小化或清除它们，但在一些特殊的应用中，如欺诈行为检测中， 孤立点本可能非常重要。因此，孤立点检测和分析是一种非常有价值的数据挖掘 任务。孤立点分析的主要方法有：基于统计的孤立点检测、基于距离的孤立点检 测和基于偏离的孤立点检测。 6 演化分析( e v o l u t i o na n a l y s i s ) ：演化分析是通过数据分析描述行为随时 间变化的规律或特征，并对其建模。主要的演变分析方法包括：时间序列数据分 析、序列或周期模式匹配和基于类似性的数据分析。 近年来，数据挖掘研究已经成为数据库乃至计算机技术研究、开发和应用领 域中最活跃和最受关注的分支之一，有大批学者和研究机构从事相关的研究工作 并产生了很多有价值的研究成果。 1 4 频繁模式挖掘介绍 通过数据挖掘过程推导出来的关系通常为模型( m o d e l ) 或者模式( p a t t e r n ) ： 模型通常为对象的全局性描述，它对整个测量空间做出描述；而模式结构仅对变 量变化空间的一个有限区域做出描述，比如线性方程、规则、聚类、树结构、图 结构和循环结构等。 频繁模式挖掘是数据挖掘领域中的一个基本问题，本文所关注的子树挖掘属 于局部模式结构的挖掘，而项集和序列属于结构上较为简单的模式。 项集简单来说就是数据项的集合。1 9 9 4 年r a g r a w a l 等【5 j 开创性地提出了 a p r i o r i 性质，用频繁项集产生关联规则以发现顾客所购买的不同商品之间的关 系，分析顾客的购买习惯并帮助零售商制定相应的营销策略。a p r i o r i 性质为以 后的许多数据挖掘方法起到了重要的指导作用。 序列定义为一个有序的项集集合。1 9 9 5 年r a g r a w a l 又在文献【6 】中发表了 序列模式挖掘算法，算法描述了同一顾客在多次购物时所购买商品之问可能存在 的某种关联关系。此后，频繁项集和频繁序列挖掘算法被广泛应用于许多数据挖 掘任务中，比如相关性分析、周期分析、最大模式挖掘、封闭模式挖掘、查询、 分类，索引掣7 。刚。2 0 0 0 年，j i a w e ih a n 提出了f p g r o w t h i l l l 算法，并成为序列 挖掘领域中的一个罩程碑。 早期的研究主要集中在无结构数据的挖掘，随着领域研究的不断深入，具有 5 兰州大学硕七研究生毕业论文 较复杂结构的数据类型如树和图等也逐渐成为人们关注的焦点。本文将对树形结 构的挖掘方法进行较深入的讨论。 1 5 本文研究内容和创新 本文研究的内容和创新之处有以下几点： 1 对子树挖掘领域的经典算法进行了较为详细的讨论，重点分析研究了不 同子树中具有代表性的挖掘算法。 2 提出了一种新的子树模式增长机制。在目前已有的子树模式增长机制中， 新生成的候选模式其长度增加值为1 ，而c c t r e e m i n e r 中采用了对具有相同根 结点的频繁子树进行根合并的方式来生成新的候选模式，而新生成候选模式的大 小取决于参与合并的两棵子树的结点数相加。算法只对数据库进行一次扫描；同 时算法保证每个被扩展的候选模式在数据库中至少有一次出现。 3 对c c t r e e m i n e r 算法进行改进，提出了用于挖掘封闭式子树模式的 c t m i n e r 算法，提出了子树封闭的充分条件并应用于c t m i n e r 算法。c t m i n e r 算法同样可以保证每个新生成的候选模式在数据库中至少有一次出现。 1 6 本文组织结构 第一章：介绍了数据挖掘工作的研究背景和相关概念，阐述了本文的主要研 究内容和创新之处。 第二章：介绍了子树挖掘研究现状及相关概念并给出了相关术语和定义。探 讨了子树挖掘问题的定义，分析研究了几种典型的子树挖掘算法，比较了它们各 自的优缺点。 第三章：提出了用于挖掘诱导式( i n d u c e ds u b t r e e ) 子树模式的c c t r e e m i n e r 算法，给出了算法所涉及到的相关定义、数据结构以及实现机制等，对算法的完 整性和正确性给出了证明，提出了剪枝策略并进行了证明。 第四章：介绍了封闭式子树的概念和意义，提出了用于挖掘封闭式子树模式 的c t m i n e r 算法以及判定子树封闭的充分条件并给出了证明。对算法的实验结 果进行了分析，证实了算法具有较高的挖掘效率。 第五章：总结和下一步研究工作展望。主要对本文的研究工作进行总结，并 6 兰州人学硕士研究生毕业论文 对下一步的工作进行展望。 7 兰州大学硕十研究生毕业论文 第二章子树挖掘的研究现状及基本概念 客观世界中的事物总是具有各种各样的联系，用计算机来模拟现实世界就必 然需要选择合适的数据结构来对各种事物和它们之间的联系进行抽象。在数据的 基本逻辑结构中，线性结构通常用来表示时序或前后等关系，相对简单易处理， 但是作为一种半结构化的存在形式，其表达能力不足，因而它的应用会受到很多 限制。而树形和图形结构具有更强的表达能力和广泛的应用基础。 随着网络和数据库等技术的快速发展，以及计算机在不同领域中应用的不断 深入，人们不得不在很多领域罩去面对大量的且结构复杂的数据。比如生物学数 据、w e b 数据、x m l 数据以及化合物结构分析等领域 1 2 - 1 7 】。与这些领域相关 的数据通常可以用树来表示，因此，如何从树型数据库中提取有价值的信息已经 成为数据挖掘研究的热点。 2 1 子树挖掘相关概念 树形结构是一种非线性结构，它为具有层次关系或分支关系的数据提供了一 种自然的表示方法。在介绍树之前首先介绍图( g r a p h ) 的概念。图是由非空的 结点( v e r t i c e s ) 集合和一个描述结点间关系，即边( e d g e ) 的有限集合组成的 一种数据结构，下面给出图的定义。 【定义2 1 】图表示为g = ( k ，s ，厶) ，其中v 是结点集；e 是边集；三是有限 字符集；标记函数l ：y u q 将s 中的字符映射到y 和e 。如果g 中表示边的 结点对是有序的，则称g 为有向图( d i g r a p h ) ，反之称g 为无向图( u n d i g r a p h ) ； 如果任意两结点v 2 ev 之间都存在一条路径连接n 与v 2 ，称g 为连通图 ( c o n n e c t e dg r a p h ) ，反之g 为非连通图。 【定义2 2 】如果一个图无向无环路且连通，则称该图为自由树。 【定义2 3 】无序根树：一个无序根树r 是一个有根结点的有向无环图，可表示 为一个五元组贮( ke ，s ，lv 0 ) 。其中v o 称为根，是树中惟一没有入度的结点( r 非空) ，树中其余结点的入度均为1 ；v 代表结点集；e 为边集，如果似，l ，) e ， 我们称u 是v 的父结点或v 是u 的子结点；s 为字符集：标记函数：yue _ s 将s 中的字符映射到y 和e 。我们将根树简称为树。 【定义2 4 】从根结点到任意结点v 存在一条惟一的通路称为从根到y 的路径。 8 兰州大学硕上研究生毕业论文 【定义2 5 】对于w e ”v e v 且w = = v ，如果w 是从根结点到 ，的路径上的结点， 则称w 为v 的祖先结点，称y 为w 的子孙结点。 【定义2 6 】路径上边的个数称为结点v 的层数。 【定义2 7 】树的深度定义为树中最长路经的长度，即路径上边的个数。 【定义2 8 】树t 的大小是指树中结点的个数，表示为l 引。 【定义2 9 】我们将大小为k 的树称k 项树或k 模式树。 【定义2 1 0 树中没有孩子的结点称为叶结点。 【定义2 1 1 】具有同一父结点的子结点互相称为兄弟结点。 【定义2 1 2 1 女i 果无序树r 的兄弟结点集合间存在一个预先定义的从左到右的顺 序，则称z 为有序树。 【定义2 1 3 树的集合称为森林。 树与其子树之间是一种包含与被包含的关系，根据约束条件的强弱不同，目 前在子树挖掘领域中主要有三种不同的子树定义形式，即完全子树( b o t t o m u p s u b t r e e ) 、诱导式子树( i n d u c e ds u b t r e e ) 和嵌入式子树( e m b e d d e ds u b t r e e ) ， 以下是它们的定义。 【定义2 1 4 1 完全子树【1 8 1 对于两棵树r 和t ( t 和丁均为无序树或均为有序树) ，假设它们的字符 集和边集分别为k 和e ，e ，则丁为丁的完全子树当且仅当( 1 ) v 坎( 2 ) e e ；( 3 ) v 和e 在z 中的标记符在r 中被保持；( 4 ) 对于任意结点v 形如 果v e v ，则v 的全部子孙结点也属于v ；( 5 ) 如果丁有序，则丁中兄弟结点集 合的顺序在r 中被保持。 【定义2 1 5 1 诱导式子树1 1 9 】 对于两棵树丁和丁，假设它们的字符集和边集分别为kv 和e ，e ，则r 为r 的诱导式子树当且仅当( 1 ) 比( 2 ) e e ；( 3 ) v 和e 在z 中的标 记符在丁中被保持；( 4 ) 如果丁有序，则丁中兄弟结点集合的序列为丁中兄弟 结点集合的子序列，及兄弟结点间的相对位置被保持。 根据概念，我们可以按照一定次序依次删除丁中度为1 的结点来获得丁的任 意诱导式子树丁。 【定义2 1 6 嵌入式子树【2 0 l 对于两棵树r ( 无序树) 和t ，假设它们的字符集和边集分别为k 和e ，e ， 9 兰州大学硕士研究生毕业论文 则丁为丁的嵌入式子树当且仅当( 1 ) y 圯( 2 ) v 中的结点在树t 中的标记 在丁中被保留；( 3 ) 如果( y t ，忱) e e ，则 ，- 必需是忱在r 中的祖先结点；如 果r 和丁是有序树，还应该满足( 4 ) 若 ，- ，v 2 ，则在r 中v - 的前序序号小于 v ：的前序序号当且仅当在丁中 ，的前序序号小于 ，z 的前序序号。子树丁不能破 坏丁中结点的祖先子孙关系。 根据定义，我们可以得出三种子树集合之间的关系：完全子树诱导式子树 嵌入式子树。 【定义2 1 7 t 是丁的子树表示为t 5 t ，称丁是r 的超树( s u p e r t r e e ) 。 【定义2 1 8 1 如果两棵树互和l 的结点之间具有一一对应的双射关系，并且在映 射中互的结点、边以及邻接关系均在乏中被保留，则称夏和瓦之间具有同构关 系。 【定义2 1 9 自同构是指一棵树到其自身的同构。 2 2 子树挖掘问题的定义 给定一个关于树的类c 以及一个由用户定义的阈值m i n s u p p o r t ；给定一个树 的有限集合d c _ c ；d 即为所要挖掘的数据库。 则频繁子树挖掘问题就是发现d 中所有的子树集合f ，使得，中不存在同 构关系( 不包括自同构) 且对所有se f ：砌厂 ，d = s u p ( s ，d ) = m i n s u p p 。r t ， 称s 为频繁子树；其中厂为一个反单调函数：对所有t c ：如果s 5 s ，则， ， d = 厂 ，乃。我们将t e d 称为数据树，将se f 称为模式树。对，简单的定义 如下【2 1 】： rl s5 t f ( s ，刀2 l0 其它 根据以上所述，一个模式树s 在数据库d 中的支持度被定义为d 中支持s 的数据树的个数，用f r e q ( s ，d ) 表示；称这样定义的支持度为出现支持度 ( o v e r l a y s u p p o r t ) ，简称支持度；支持度大于等于m i n s u p p o r t 的子树模式被称为 频繁子树模式或简称为频繁子树。此外还有根据s 在d 中不同位置所出现的总 次数来定义支持度的方法，称为加权支持度( w e i g h t e d s u p p o r t ) 。 1 0 兰州大学顾：l 研究生毕业论文 一个出现是指对应模式在数据库中的一次呈现。如果模式大小为k ，我们称 其出现为k 出现；如果模式频繁则称其出现为频繁出现。 2 3 子树挖掘研究现状 目前已出现很多有关频繁子树的挖掘算法，其中主要有： 2 0 0 2 年，m j z a k i 提出了挖掘嵌入式有序子树的m e 肘跏e r l 2 0 1 算法，该算法 采用深度加宽度的方式，通过对最右路径的扩展来挖掘频繁子树；使用作用域链 表( s c o p el i s t s ) 来记录频繁模式的每个出现进而完成支持度的计算。 2 0 0 2 年，a s a i 等提出了用于挖掘诱导式有序子树的f r e q t l 2 2 】算法，该算法 同样采用在最右路径上的深度优先扩展方式，并通过出现列表( o c c u r r e n c el i s t ) 来计算支持度。 2 0 0 3 年，a s a i 等又提出了用于挖掘诱导式无序子树的u n o t l 2 3 l 算法，该算法 为f r e q t 算法的扩展。同年s n i j s s e n 等提出了与u n o t 基本相似的u f r e q t l 2 4 j 算 法。两者都采用了标准深度序和扩展最右路径的方式来生成具有标准深度序的候 选模式。以上两种算法的不同主要在于支持度的计算方法。 2 0 0 3 年由潘锦等提出的c h o p p e r 算法【2 5 】利用了这样一个性质：即在子树挖 掘的过程中首先将子树表示为序列，如果子树模式频繁则它所对应的序列也必须 频繁，即提出了先挖掘频繁序列再挖掘频繁结构的思想。c h o p p e r 算法先获得所 有的频繁序列，然后为每一个频繁序列寻找对应的子树，最后进行子树的支持度 计算。 2 0 0 4 年朱永泰等提出了c h o p p e r 算法的改进e s p m 算法【矧。e s p m 算法并 不一次性的获得所有频繁序列，而是每得到一个频繁序列就判断对应的树是否频 繁。如果频繁，则继续挖掘以该序列为前缀的序列，如果不频繁则对解空间进行 剪枝，因而e s p m 比c h o p p e r 生成了更少的候选模式。 2 0 0 4 年，y c h i 等提出了用于挖掘无序子树的h y b r i d t r e e m i n e r l 2 7 1 算法。算 法采用深度加宽度的方式遍历搜索空间并生产候选模式。此外，算法还提出了树 的宽度优先规范形式。 2 0 0 5 年，y c h i 又提出了挖掘封闭( c l o s e df r e q u e n ts u b t r e e ) 和最大频繁子 树( m a x i m a lf r e q u e n ts u b t r e e ) 的c m t r e e m i n e r 2 8 】算法。其中封闭式子树模式排 兰州大学硕上研究生毕业论文 除了那些支持度相等并且是某封闭树的子树的频繁模式，使得挖掘的结果更精简 和易理解。 2 0 0 5 年杨沛等提出了p f i m 算法【2 9 1 。该算法在挖掘诱导式子树的过程中采 用了投影的思想，在最右路径扩展的基础上，利用递推式的候选结点集更新技术 来压缩候选结点集，进而压缩搜索空间，以达挖掘频繁子树完全集的目的。 可以看出，以上这些算法由于问题定义的不同，在数据结构、扩展方式以及 实现细节上存在各种类似和差别。根据挖掘对象可以归纳如下： 挖掘有序子树的算法有：t r e e m i n e r , f r e q t , e s p m ，c h o p p e r ，p f r m 。 挖掘无序子树的算法有：t r e e f i n d e r , u n o t ，u f r e q t ，h y b r i d t r e e m i n e r , c m t r e e m i n e r 等。 挖掘嵌入式子树的算法有：t r e e m i n e r 。 挖掘诱导式子树的算法有：f r e q t ，u n o t ，u f r e q t ，h y b r i d t r e e m i n e r ，e s p m ， c h o p p e r ，p f t m 。 挖掘最大频繁子树和封闭频繁子树的算法有：c m t r e e m i n e r 。 2 4 经典算法简介 本节主要介绍两种具有较大影响力的频繁子树的挖掘算法。 2 4 1t r e e m i n e r 算法 z a k i 等在文献 2 0 1 q h 提出了t r e e m i n e r 算法用于挖掘嵌入式有序频繁子树。 t r e e m i n e r 算法基于子树前序字符串编码( 见3 1 1 ) 的一个特殊性质：即对于有 序根树丁来说，删除其前序字符串编码中最后两个结点中的任意一个，所得到的 子串为r 的一棵有效的嵌入式子树的字符串编码。根据这一性质，对于一棵k + l 项候选子树丁，通过删除其前序字符串编码中的最后一个和倒数第二个结点，可 以分别确定丁的两棵k 项子树的前序字符串编码，而这两个字符串编码的前k 一1 项完全相同。将具有相同“1 项前缀的k 项频繁子树归结为一个等价类 ( e q u i v a l e n c ec l a s s ) ，称为缸1 项前缀等价类。反之，通过结合属于同一前缀等价 类的两棵频繁k 1 项树就可以确定一个候选k 项树。根据以上讨论，算法能够采 用一种深度加宽度的枚举空间遍历策略来完成模式的增长。对于支持度计算，算 1 2 兰州大学硕士研究生毕业论文 法提出了子树出现的一种三元组链表的表示形式( f ，m ，s ) ：其中t 为子树出现 所在数据树的标识符；m 为出现的前序字符串：s 为子树出现最右叶 ，结点的作 用域，用两个整数来表示，第一个整数为v 在对应数据树中的前序序号，第二个 整数为l ，所在数据树中以 ，为根结点的最大子树的最右叶结点的前序序号。用上 述三元组来表示模式p 的每一次出现，这种表示方式称为p 的s c o p e l i s t 表示， 显然，p 的支持度就是s c o p e l i s t 中元素的个数。以下举例介绍t r e e m i n e r 的具 体实现方式。 假设两棵k 子树x 和y 的先序序列中的前缸1 个结点相同，则x , y 属于 1 ) 等价类。假设前限1 ) 个结点构成的子树为p ，用p k - 表示所有以p 为前缀的k 项树的集合。集合中的元素用其第k 个结点( 最右叶结点) 和该结点父结点的前 序序号来表示，如 p k - 1 中的元素( x ，i ) 表示在p 的前序序号为f 的结点上添加标号 为x 的结点所得到的子树，称该子树为p 的x ，i ) 扩展子树。设( x ，i ) 和( y ，j ) 是前缀 子树为p 的等价类【p 】中的成员，p x 是p 经过( x ，i ) 扩展得到的子树，限】是以r 为前缀子树的等价类，【p x 】是由【p 】中成员之间经过连接操作( j o i n ，标记为o ) 后得 到的，( x ，i ) o ( y ，j ) 的具体步骤如下。如果i - j ，那么：( 1 ) p ：g ：0 ，把( y ，j ) 和( y ，j + 1 ) 添加到类p 叫中；( 2 肛l z i ，把( y j + 1 ) 添加到类口q ；如果i j ，那么把( y ，j ) 添加到 类【p x 】；如果i 的叶结点，其序号为5 ；而f d a 中的出现 1 ，3 ，( 5 ，6 ) 的根结点也 是5 ，因此找到一个候选模式。我们沿对应模式( a a t 和a b t ) 的链表向上遍历， 可以确定出现 2 ，0 ，( o ，5 ) ) 和出现 2 ，1 ，( 5 ，6 ) ) 也可以进行叶根连接，从而判定模式 a a b t t 为频繁模式。调用最终返回尼( 见图5 ) 。 1 9 兰州大学硕= t 研究生毕业论文 算法调用c o n n e c t ( n d 姆i 1 脚) 后可以将，删除，因为后续循环中 不必再次考虑，中的出现，同时根据下述性质对枚举空间进行剪枝。 【性质3 1 】在第f 次连接之后，对任意频繁模式，如果将该模式处在第d e p f 层 的出现，即属于，中的出现删除后，其剩余出现不满足支持度阈值， 则该模式不可能被再次扩展而生成更大的频繁模式。 证明：首先，根据定理3 1 ( 见3 3 1 ) ，对于任意频繁模式p ，p 在第d e p i 层以 下层的所有频繁超模式已经被全部生成，因此，在第f 次连接之后，如果 存在p 的超树p 且p 未被生成，则p 一定处于第d e p f 层以上，即p 在第 d e p i 层及其以下层的所有出现对p 的支持度贡献为o ；假设删除p 在第 d e p f 层及其以下层的出现后p 的支持度为_ ，则_ m i n s u p p o r t ，根据a p r i o r i 性质，非频繁模式的所有超集非频繁，即对任意超模式p 来说，设其支持 度为j ，则j = + 0 m i n s u p p o r t ，因此任意增长模式p 非频繁。证毕。 根据性质3 1 ，算法将不满足支持度的模式标记为“轳，在后续循