（计算机软件与理论专业论文）一种新的频繁子树挖掘算法研究.pdf

独创性声明 y 9 7 4 3 6 1 本人声明所呈交的学位论文是我个人在导师指导下进 行的研究工作及取得的研究成果。尽我所知，除文中已经标 明引用的内容外，本论文不包含任何其他个人或集体已经发 表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：弋付箩 押何年6 月l 口日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文 的规定，即：学校有权保留并向国家有关部门或机构送交论 文的复印件和电子版，允许论文被查阅和借阅。本人授权云 南师范大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文。 学位做储鹤：呼 蒯年月t o 日 指导教师签名：a 乡惕 ， 知一石年占n o 日 摘要 摘要 随着信息的爆炸式增长，人们日益变得在信息垃圾当中不知所措。如何从这些无用的信息中挖 掘出对我们有用的知识是近几十年来数据挖掘的主要研究目的。最初的数据挖掘的对象是结构化的 关系表和事务数据库。到目前为止，该领域已经有了长足的发展。然而，随着数据挖掘应用领域的 不断扩大，如_ 可从半结构化和非结构化数据当中发现知识呢? 这是目前研究人员所面临的技术难题， 因为传统的数据挖掘算法不能有效的应用到这些领域中来。图结构能够模拟几乎所有的事物之间的 联系，它也能应用到上述半结构化和非结构化的数据挖掘中来。基于图的数据挖掘己成为数据挖掘 中的一个新的研究热点。基于图的数据挖掘有广阔的应用空间，如在w e 挖掘、空间数据挖掘、生 物信息学中蛋白质结掏挖掘、药物分子设计及其功能预测等领域都有广泛的应用。树是一种特殊的 图，对频繁子树挖掘算法的研究有着重要的理论意义和应用价值。 本文工作主要包括以下几部分：( 1 ) 在分析当前频繁子树挖掘定义的基础上提出了基于支持度 和频繁度的频繁子树挖掘定义；( 2 ) 为计算模式子树的支持度和频繁度，提出了一种基于树同构的 候选子树支持度与频繁度的计数方法；( 3 ) 提出了森林的二维表表示方法，这提高了对数据库访问 的速度；( 4 ) 提出了一种新的候选子树的生成方法，通过在数据库的基础上生成新的候选子树，从 而减少了为了计算子树的支持度而进行的无效的树匹配问题；( 5 ) 提出了频繁子树挖掘算法 f s u b t r e e m ，它能有效地从自由树数据库中挖掘频繁的导出自由树。 实验研究表明，f s u b t r e e m 能有效地从实验数据库c a r c i n o g e n 中挖掘其中的频繁导出自由子树 结构，并根据频繁结构集提取有趣的关联规则，有一定的理论意义和应用价值。 关键词：频繁子树挖掘同构编码规范化树中心 3 a b s t i t a c t a b s t r a c t w i t ht h ee x p l o s i o no fi n f o l m a t i o n ，w ea r eo v e r w h e l m e di nt h ei n f o r m a t i o ng a r b a g e h o wt od i s c o v e r y t h eu s e f u lk n o w l e d g ef r o ms u c ha ni n f o r m a t i o n a lb i ni st h em a i np u r p o s eo fd m i nt h ep a s td e c a d e s t h e o r i g i n a ld a t at a r g e to fd m i st h es t r u c t u r e dt a b l e so rt r a n s a c t i o nd b s u pt od a t e ，t h et e c h n i q u e si nt h ef i e l d a r ed e v e l o p e dt ot h er e a la p p l i c a t i o n s h o w e v e r ，t h e yc a n tb ea p p l i e dt om a n yo t h e ra p p l i c a t i o n ss u c ha s s e m i - s t r u c t u r e da n dn o n - s t r u c t u r e dd a t aa st h e s et e c h n i q u e sc a n tm o d e lt h ed a t af r o m a t sc o r r e c t l y g r a p h s t r u c t u r ec a nm o d e lt h ec o m p l i c a t e dr e l a t i o n s h i p sb e t w e e ne n t i t i e sa n di ta l s oc a nb eu s e di ns u c hd o m a i n s a s f a r , g r a p hb a s e dd m b e c o m e san o v e lh o tt o p i ci nt h ef i e l do fd m g r a p hb a s e dd mh a sav a r i e t yo f a p p l i c a t i o n ss u c ha sw e bm i n i n g ，s p a t i a ld a t am i n i n g ，s u b s t r u c t u r em i n i n gi nt h eb i o i n f o r m a t i c s ，d r u g m o l e c u l ad e s i g na sw e l la si t sf u n c t i o n a lp r e d i c t i o n ，e t c t r e e sa r ea c y c l i cg r a p h s ，f r e q u e n ts u b t r e em i n i n g h a st h et h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e o u rc o n t r i b u t i o ni nt h i sp a p e ri n c l u d e s ：( 1 ) b a s e do nt h eu s u a lf r e q u e n ts u b t r e ed e f i n i t i o n ，w ep r o p o s e an o v e ld e f i n i t i o no ff r e q u e n ts u b t r e em i n i n g ，( 2 ) p r o p o s eat r e ei s o m o r p h i s mb a s e dm e t h o dt of a c i l i t a t e t h es u p p o r ta n df r e q u e n tc o u n t i n go ft h ec a n d i d a t e s ，( 3 ) i no r d e rt os p e e d - u pt h ev i s i to ft h ed a t a b a s e ，w e p r o p o s eat a b l er e p r e s e n t a t i o no faf o r e s t ，( 4 ) p r o p o s ean o v e lc a n d i d a t eg e n e r a t i o nm e t h o db a s e do nt h e d a t at r e et h a tc a ns i g n i f i c a n t l yr e d u c et h ei n v a l i dt r e em a t c h i n g sd u r i n gt h et r e ec o u n t i n g ，( 5 ) p r o p o s e a l g o r i t h mf s u b t r e e mw h i c he m p l o y st h ea b o v et e c h n i q u e st om i n ef r e q u e n ti n d u c e df r e es u b t r e e sf r o ma f o r e s tc o n s i s t i n go ff r e et r e e s p e r f o r m a n c es t u d yi n d i c a t e st h a tp s u b t r e e mc a ne f f e c t i v e l yd i s c o v e r yt h ef r e q u e n ti n d u c e df r e e s u b t r e e sf r o mt h ed a t a b a s ec a r c i n o g e n ，i ta l s oc a l lf o r ms o m ei n t e r e s t i n ga s s o c i a t i o nr u l e sf r o mt h ef r e q u e n t s u b t r e e sw h i c hh a ss o m et h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e k e y w o r d s ：f r e q u e n ts u b t r e em i n i n g ，i s o m o r p h i s m ，c o d i n g ，c a n o n i c a l i z a t i o n ，t r e ec e n t e r 第一苹。|言 第一章引 j l 一 日 l _ 1 研究背景 在过去的数十年中，我们产生和收集数据的能力已经迅速提高。起作用的因素包括条码在大部 分商业产品中的广泛应用，许多商务、科学和行政事务的计算机化，以及由文本和图像扫描平台到 卫星遥感系统的数据收集工具的进步。此外，作为全球信息系统的万维网的流行，已经将我们淹没 在各类数据的汪洋大海中。存储数据的爆炸性增长业已激起对新技术和自动工具的需求，以便帮助 我们将海量数据转换成信息和知识。因此，我们必须找到有关方法来分析数据、对数据分类、汇总、 发现和描述数据中的趋势、自动地标记异常。数据挖掘技术正是应这些需求而产生的。 近年来，数据挖掘引起了信息产业界的极大关注，其主要原因是存在大量数据可以广泛使用， 并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识可以广泛用于各种应用，包 括商务管理、生产控制、市场分析、工程设计和科学探索等。 自从a r g a w a l 等人于1 9 9 3 年提出数据挖掘以来，频繁项目集和关联规则的挖掘引起了广泛的关 注。在过去的几十年里，有大量的关于提出新的挖掘算法和改善现有算法的研究文献。关联规则挖 掘首先由a g r a w a l ，i m i e l i n s k i 和s w a m i r a g r a w a l ，1 9 9 3 提出。后来a g r a w a l 和s f i k a n t 提出了著名的 a p r i o r i r a g r a w a l ，1 9 9 4 算法。使用类似的剪枝方法的算法变形由m a n n i l a ，t o i v o n e n 和 v e r k a n m o h m a r m i l a ，1 9 9 4 1 分别提出。为提高关联规则的挖掘效率，p a r k ，c h e n 和y u 提出了使用h a s h 表 j s p a r k ，1 9 9 5 1 1 船3 法，还有诸多的基于a p f i o r i 的改进算法。关联规则有许多扩充，包括序列模式 挖掘 r a g r a w a l ，1 9 9 5 ，周期挖掘 r j m i l l e r , 1 9 9 7 ，空间关联规则挖掘【k k 0 p e r s k i ，1 9 9 5 ，挖掘事务 间关联规则【h l u ，1 9 9 8 。频繁闭合项集的挖掘由p a s q u i e r ，b a s t i d e ，t a o u i l 和l a k h a l n p a s q u i e r , 1 9 9 9 提出，而有效的挖掘算法由p e i ，h a r t 和m o j p e i ，2 0 0 0 提出。频繁项集的深度优先产生由a g r a w a l ， a g g a r w a l 和p r a s a d r a g a r w a l ，2 0 0 0 提出。挖掘频繁模式而不产生候选的方法由h a n ，p e i 和y i n j h a n 2 0 0 0 提出。 以上本文提到的文献所处理的数据对象都局限于结构化的关系表和事务数据库。到目前为止， 该领域已经有了长足的发展，并有大量的相关数据挖掘软件得到应用。然而，随着数据挖掘应用领 域的不段扩大，它己延伸到了非传统领域，如科学数据库、空间数据库和关系数据库，而我们不能 将现有的项目集挖掘算法应用到这些领域中来，因为这些问题很难用传统的菜篮子事务的方法来正 确有效地模拟 1 驮a s h iw a s h i o ，2 0 0 3 。 如何从半结构化( 如h t m l 和x m l 文本、符号序列、有序树等) 和非结构化( 如科学数据、 空间数据、分子结构等) 数据当中发现知识呢? 这是目前研究人员所面临的技术难题，因为传统的 数据挖掘算法不能有效的应用剑这些领域中来 a k i h i r oi n o k u c h i 2 0 0 0 。 种新的频繁子柑挖掘算法研究 我们知道，在数学当中最为普遍的图结构能够模拟几乎所有p ：事物之司的联系，它也能应用到 上述半结构化和非结构化的数据挖掘中来。基于图的数据挖掘( g r a p h - b a s e dd a t am i n i n g ，g b d m ) 已成为数据挖掘中的一个新的研究热点 t a k a s h iw a s h i o ，2 0 0 3 1 。传譬为数据挖掘的主要目的是从结构 化数据库中发现有趣的属性模式( a t t r i b u t e sp a t t e r n s ) ，而g b d m 是要提供并的原理和有效算法来挖 掘嵌入在图数据库( g r a p h d a t a b a s e ) 中的子结构模式( s u b s t r u c t u r e s p a t t e r n s ) 。 树是一种特殊的图，频繁子树挖掘在生物信息学 c h r i s t o p hh e l m a ，2 0 0 3 d s h a s h a ，2 0 0 4 h a i y a n h u ，2 0 0 5 】、电信【a b a r i t c h i ，2 0 0 0 】、w e b 挖掘【a d a ms c h e n k e r 2 0 0 3 a a d a ms c h e n k e r , 2 0 0 3 b a r a k h s h a n ，2 0 0 3 1 、半结构化数据挖掘【a r a k h s h a n ，2 0 0 4 j u r y o np a i k 2 0 0 5 a 等领域均有重要的应用价 值。 1 2 研究意义 树结构模式典型地应用在生物信息学、w e b 挖掘、半结构化文档挖掘等领域。 分子结构挖掘化学图长期以来都用来研究分子和高分子譬立- 有机化台物，聚合酸和蛋白质。 一组具有相似生物活性的化合物中的重复出现的子结构可以通过巨来表示这些化合物来识别。这些 重复出现的子结构可以说明这些化合物活性的化学特性。再举一个铡子，r a n 的二层结构( s e c o n d a r y s t r u c t u r e ) 可以用一棵标识树来模拟，树中的每个结点是一个对基r p a i r e db a s e ) ，树中结点间的双亲 兄弟关系由基对键的嵌入来确定。对一个化合物来说，图的顶点荐边分别对应着化合物的原子和原 子之间的键，而顶点标识和边标识则分别代表着原子的名称或信息壬键的类型或信息。 w e b 挖掘在数据库领域，x m l 文档可以看作是树结构的，碧点代表x m l 文档中的元素或属 性，而边则对应了元素子元素对和属性值对之间的关系。我们可以- 寸这些支档的子树结构进行划分。 我们也可以对用户对x m l 文档的查询历史日志来挖掘频繁的历曼查询，对这些查询存储和索引可 以有利于将来的查询应答。在w e b 交通中，访问树可以表示不同慝户的访问模式。我们可以使用这 些访问树来对不同类型的用户进行分类。 l3 研究现状 在g b d m 的先驱是c o o k 和m o t o d a 等人，他们在上个世纪9 0 年代中期就分别提出了 s u b d u e c o o k l h o l d e r , 1 9 9 5 算法来挖掘图数据中的子结构模式= 为了避免图同构检测所带来的高 复杂性，因为这是一个n p 困难问题 s c o t tf o r t i n ，1 9 9 6 1 ，他们采取了贪心接索策略，但这却又导致了 所挖掘的频繁子图的不完全性。d e h a s p e 在1 9 9 8 年提出了可对频繁子图进行完全挖掘的基于i l p 的 w a r m r 【l d e h a s p e ，1 9 9 9 】算法。n i j s s e n 也提出了一个快速曲挖掘算法f a r m e r s i e g f r i e d n i j s s e n ，2 0 0 3 。2 0 0 0 年，i n o k u c h i 等人结合a p r i o r i 算法和数学匡论的知识，提出了a g m a k i h i r o i n o k u c h i 。2 0 0 0 1 算法。从此之后，研究人员提出了大量的基于数学图论的g b d m 算法。2 0 0 1 年， k u r a m o c h i 等人对a g m 进行了修改并引入了一些剪枝策略，提出了f s g k u r a m o c h i ，2 0 0 1 算法。当 第一帚引高 前算法效率最高的是j i a w e i h a n 等人提出的g s p a n x i f e n g y a h ，2 0 0 2 算法，它能有效的挖掘出图数据 库中的频繁连通子图。j p r i n s 和x i f e n gy a h 等人分别提出了s p i n j u nh u a n ，2 0 0 4 b 】和 c l o s e g r a p h x i f e n g y a h ，2 0 0 3 1 来挖掘极大频繁子图模式。在国内，复旦大学的b a i l es h i 等人提出了基 于硬盘的图挖掘算法a d i m i n e c h e n w a n g ，2 0 0 4 a ，它能对大的圈数据库进行挖掘，并在相关领域做 了大量的研究工作 c h e nw a n g ，2 0 0 5 】【m i n g s h e n gh o n g ，2 0 0 3 】【q i n g q i n gy u a n ，2 0 0 2 】 z i j i n gt a n ，2 0 0 5 。 尽管图挖掘算法同样可以应用到频繁子树挖掘当中来，但它们看起来太普遍了，因为它们并没有利 用根的存在以及无圈的特点，因此它们是无效的： 第一个面向树挖掘的工作是w a n g w a n g ，2 0 0 0 。它们的算法是a p r i o r i 算法的在挖掘频繁出现路 径的一个应用，这些路径中的任一条路径都不是其它路径的前缀，因此它们对应树。后来，k a t s a r o 等 d i m i t r i o sk a t s a r o s ，2 0 0 5 1 开发了一个为标识有序树编号模式来提高w a n g 提出来的算法的执行速 度。k a t s a r o k a t s a r o s ，2 0 0 3 提出了d e l t a s s d 算法来对发现的树子结构在数据库更新的情况下进行有 效维护。 与a p r i o r i 不同，z a k i m o h a m m e dj a v e e dz a k i ，2 0 0 2 提出了t r e e m i n e r ，以及a b e ，a s a i 等人 t a t s u y a a s a i ，2 0 0 2 】【k e n j i a b e ，2 0 0 2 】【t a t s u y a a s a i 2 0 0 3 提出了f r e q t 算法。这些树挖掘算法非常相 似，它们都是基于一个有效的枚举技术，它考虑到了频繁树模式集的增量构造以及它们的层次出现。 t r e e m i n e r 以深度优先搜索方式发现频繁子树，并对数据库中的树进行垂直表示以加快支持度计 数。f r e q t 使用了极右扩展的思想，即只在一棵频繁子树的极右路径上添加结点来产生候选树。有 相类似思想的算还有c h i 等 y u n c h i ，2 0 0 3 】 y u n c h i ，2 0 0 4 b 。最后，x i a o ，y a o ，l i 和d u n h a m i x i a o ，2 0 0 3 】 提出了只挖掘极大频繁子树的算法，它使用了一个紧凑的数据结构来表示和发现数据库中的极大频 繁子树。最近，研究人员提出了很多的频繁子村挖掘算法。t r e e m i n e r 是挖掘嵌入有序子树的；f r e q t 是挖掘导出有序子树，f r e e t r e e m i n e r 挖掘导出无序自由树；t r e e f i n d e r 挖掘嵌入无序子树，它是一 个不完全挖掘算法；p a t h j o i n ，u f r e q t ，u n o t ，c m t r e e m i n e r 和h y b r i d t r e e m i n e r 都是挖掘导出无序子 树的。 树挖掘问题涉及到树同构和子树同构问题。树挖掘与这两个研究问题的主要区别在于，树挖掘 算法的关键是发现所有的频繁树子结构，而不仅仅是确定一棵特定的树是否包含于另一棵大树当中。 1 4 本文的主要工作 本文的主要工作包括以f j l , 个方面： ( 1 ) 提出了一种新的候选子树的支持度与频繁度的计数方法，通过对大小相同的树进行同构判 定，而不是传统的采用子树同构的判定方法。由于子树同构判定的复杂性为o ( k 1 5 n l o g n ) r o n s h a m i r , 1 9 9 7 r o ns h a m i r , 1 9 9 9 ，而树的同构判定复杂性仅为d 伽) 【a h o ，h o p c r o f t & u l l m a n ，1 9 7 4 ，从 而降低了计算模式树的支持度与频繁度的时间复杂性； 9 吾新的频繁了树挖蠢算法i i = ：究 ( 2 ) 提出了森林的二维表表示方至，这叠高了药数据库访问的遮度； ( 3 ) 提出了一种新的候选子树的生成方法，通过在数据章的基础上生成新的候选子树，从而减 少了为了计算子树的支持度而进行的乏效的栲互配问题； ( 4 ) 提出了基丁| 支持度和频繁度频繁子树挖捱定义，一定程度上避免了单纯的基于支持度的 频繁子树挖掘带来的挖掘知识的不完全性； ( 5 ) 提出了频繁子树挖掘算法f s u b t r e e m ，它能有效地从自由树数据库中挖掘频繁的导出自由 树，并且它是可以同时支持支持度和薤繁度挖掘的。 1 。5 论文组织结构 1 本文的余下部分是这样组织的。 在下一章节，本文介绍了频繁子样挖掘的基本概念，并提出了子树计数的定理，给出了频繁子 树挖掘的一般过程和要解决的问题及本文处理这些问嚣采用的方法。为解决子树的计数问题，我们 介绍了本文采用的子树字符串编码方法，并提出了森 = 的二维表表示方法。在接下来的第三章中， 我们提出了频繁子树挖掘算法f s u b t r e e m ，给出了算法的复杂性分析，并与同类的挖掘算法进行了 比较。提出了无序树的规范化算法和引入了自由树的亭心化算法，将f s u b t r e e m 应用到无序树和自 由树的挖掘中来。然后，本文将算法f s u b t r e e m 应用到实际的致癌物质化合物数据库的挖掘，并对 实验结果进行了分析。最后，我们对本文进行了总结并提出了下步要研究的内容。 1 0 第二章基本概念 第二章基本概念 2 1 树及其子树 定义1 有根树( r o o t e dt r e e ) k n u t h ，2 0 0 2 】有根树丁是一个或多个结点的集合y 使得： ( 1 ) 集合中y 的一个结点r 指定为这棵树的根结点，记为r o o t ( t ) ；而且 ( 2 ) 结点集v r 被划分为m 0 个不相交集五，正，l ，每个集合又是一棵树。树 五，五，l 称作r o o t ( t ) 的平凡子树( t r i v i a ls u b t r e e ) 。 定义2 根子树( r o o t s u b t r e e ) 树r 中的所有结点的平凡子树及丁本身都是丁的根子树。树丁是 t 的一棵根子树t 我们记为t 5 t 。 我们可以形式地定义树t = ( y ，e ) ，其中v 是该树中结点集，e ； ( 石，y ) j 上，y 矿) 是边集， 对任意z 矿，从r 都有唯一的条路径到达x ，路经的长定义为从r 到x 所经历的边数。如果 x ，y y 而且存在一条从x 到y 的路径，那么x 称为y 的祖先，y 称为x 的后代，记为x s 。y ，其 中p 是从x 到y 的路径长。如果zs 。y ，那么x 是y 的双亲，记为p ( y ) ，y 是z 的孩子。如果x 和 y 共享同一个双亲，那么称z 和y 为兄弟。一个结点的根子树棵树称为它的度( d e g r e e ) ，一个0 度 结点称作叶子结点。树r 中一个结点的深度( d e p t h ) 定义为：r o o t ( t ) 的深度为0 ，t 中的其它结 点的深度比它们的双亲多1 。如果存在一个标识函数f ：矿一l 为结点集到标识集l = ( g l , e 2 ，) 的 一个映射，是一个有限字符集，那么树丁是一棵标识树( l a b e l e dt r e e ) 。一棵具有k 个结点的树 叫作k ( 子) 树。 如果我们要考虑定义1 ( 2 ) 中巧，互，乙的相对顺序的话，我们说这树t 是棵有根有序树 ( r o o t e d o r d e r e d t r e e ) ，有根有序树在一些文献 s h i n - i c h i n a k a n o ，2 0 0 3 、当中也q 平面树( p l a n e t r e e ) 。 五，互，乙的相对顺序不重要的话，我们称这棵树为有根无序树( r o o t e d u n o r d e r e d t r e e ) 。如果树 r 中没有指定一个根结点，我们称丁为一棵自由树( f r e et r e e ) 。 一个森林是0 棵或多棵不相连的树的集合。 黛氛胁 f i g u r e1l a b e l e d t r e e s 圈l 标识村 图1 中是3 棵标识树，其中结点中的字符是对应结点的标识，图l 左边的数字是与其处于同一 水平的结点的深度。若将树i 和疋看作是有根有序标识树的话，那么它们表示的是不同的两棵树i 二整三塑塑鍪三塑丝塑墨堡型壅 若看作是有根无序树的话，那么它们表示拘是匣一棵树：若写、疋和五都是自由树的话，那么它们 表示的是同一棵树。 定义3 嵌入子树( e m b e d d c ds u b t r e e ) m o h a m m e dj a v e e d z a k i ，2 0 0 5 a 】t = ( v ，e ) 是t = ( v ，e ) 的一棵嵌入子树，记为t s 。t ，当且仅当存在一个一对一映射，：v 一y 满足：( 1 ) ( x ，y ) e e i f ff ( x ) s ，厂( y ) ( p 1 ) ，艿且( 2 一啦) = f ( ， ) ) 。 根据嵌入子树的定义本文得到导出子讨的定义。 定义4 导出子树( i n d u c e ds u b t r e e m o h a m m e dj a v e e dz a k i ，2 0 0 5 a 对树t = ，e ) 和 r ：( y ，e ) ，我们说r 是r 的一棵导出子讨，记为t s 。t ，订t s 。t 而且在定义3 ( 1 ) 中p = 1 。 嵌入子树与导出子树妁区别在于：对子( x ，y ) e ，那么i f ( x ) ，f ( y ) ) e e ，即，( 是f ( y ) 的 双亲，而嵌入子树不必满足，它只需满足i ( x ) s 。f ( y ) 即可，也就是说f ( x ) 只要是f ( y ) 的祖先 结点就可以。 p 1p 2p 3 f = t 1 ， r l 1 3 a n d3s u b t r e p i ，p 2a dp 3 f i g u 咒2af o r e n a n ds u b t r e e s 圈2 森林和子树 以上本文给出了当前文献中主要提及的子树的概念。如果s 是f 的一棵子树，那么t 是s 的一 棵超树( s u p e r t r e e ) 。下边给出一个子栲豹例子： 图2 中的森林f 由3 棵标识有根有声树t 1 、t 2 和t 3 组成。p 1 、p 2 和p 3 是子树。其中p 1 是 t 3 的根子树，p 1 和p 2 都是t 2 和t 3 的导出子 雩，p 3 是t 2 和t 3 的嵌入子树。 根据子树的定义，本文得到定理1 。 定理1t = 缈，e ) 是一棵有根有序标识树，那么 ( 1 ) t 有i y l 棵根子树： ( 2 ) t 最多有2 川- 1 + ( 1 v f i ) 操导出子树。 证明：结论( 1 ) 是显而易见的，根据根子树的定义就可以得到，f 面证明结论( 2 ) 。 我们考虑所有结点具有不同标识的情况，其中一个结点为根结点，其它的结点都是根结点的 孩子结点，如图3 所示。具有一个结点的导出子讨有q 1 ，j 棵，具有两个结点的导出子树有哆l 一，棵， 。暑 毋 掩b ，父 哂叁 第二章基本概念 具有3 个结点的导山子树有c ；棵， 等等c 树丁总的导出子树有 s i ( 丁) = 哆i + 哆卜1 + 嘭卜l + - + r m r 一- ，1 = 哆l + 2 m 一嘭卜1 = 2 什1 + ( i v i - 1 ) 棵。若从 z ：，i r i 中取出结点l 来作为f 1 的双亲，得到树墨，那么s ( 互。) = s ( r ) 。若取出两个结点0 和 来，l m 一个作为的双亲，另一个作为的兄弟或_ 的双亲，得到树乏，那么包含的导出3 - 子树的棵数为 睇卜3 + 筇卜3 + 1 ：坐丘掣_ 塑s 睇2 卜1 ( 1 y k3 ) ， 这也是所有的导出3 子树棵树。同理可证导出4 子树棵数嘭i 一，+ 2 1 。+ i 一，c 印h ( i v l 3 ) 。如 炯i t s i ( t 2 ) c 墨( r ) 。同样可以证明其它情况满足s 仃) cs ( r ) 。证毕。 f i g u r e3 al a b e l e dt r e et 图3 标识树t 从以上证明及嵌入子树的定义我们可知，在计算s ( 乏) 时，虽然匕不可以和l l 的孩子结点组合 成导出子树，但是却可以是嵌入予树，因为它们满足祖先后代关系。 根据以上讨论本文可以得到树t 的所有根子树墨( 丁) 、导出子树置( 丁) 以及嵌入子树( 丁) 之 间的一个关系，其中s ( r ) 、s 1 ( r ) 和s 。仃) 分别表示相应的子树集。 推论1 对有根有序标识树r ，s r 仃) s s i 仃) s s e 口) ，且有s 7 ( t ) s 仃) s e 口) 。 2 2 子树同构、支持度和频繁度 有根有序标识树p 一( ，廓，e ，) 和d = ( ，。) ，d 脚= d 1 ，d 2 ，d 。) ，d b 是含 有甩棵有根有序标识树的集合。我们说p 是一棵模式树( p a t t e r n t r e e ) ，d 是一棵数据数( d a t a t r e e ) 。 我们说模式树p 出现在数据树d 中，如果存在一个映射函数f ：一使得，y k 满足以下4 点： ( 1 ) 厂是一对一的，也就是说如果x y ，月i v z , f 0 ) f ( y ) 。 ( 2 ) 厂保持双亲一孩子关系，也就是说( x ，y ) e vi f f ( ，0 ) ，( _ ) ，) ) 。 ( 3 ) f 保持兄弟结点的相对顺序，也就是说x 在y 之前，i f ff ( x ) 在f ( y ) 之前。 ( 4 ) ，保持标识，也就是说， ) = 。( 厂g ) ) 。 那么，f 称作从p 到d 的一个子树同构( s u b t r e e i s o m o r p h i s m ) ，或者p 到d 的一个匹配( m a t c h i n g ) 、 1 3 一种蒂耋勺频繁子树挖据算法研究 p 在d 中a 一个皂含( i n c l u s i o n ) ：我们藏说d 包含p ，或者p 出现在d 中。p 在d 中的一个出 现( o c c u r r e n c 6 ) i 以用它约唯一的匹配标记来确定，匹配标记是p 在d 中匹配的一个结点序列， f ( x ，) ，( x ：) f ( x 爿) ，其= 薯。若厂是满射的，那么我们称f 是p 到d 的一个同构，记为s c 。 让如( p ) 表示嗔式树p 在数据树d 中的出现数。d d 是个指示变量，且 以胪幺篡”。 那么模式树p 在数秀库d b 中的支持数( s u p p o n y ) o ( p ) = d d 口d d ( 暑) ，也就是在数据库中对模 式树p 至少有一冀包含的数据树总数。我们也可以定义模式树p 在数据库d b 中的频繁数 ( f r e q u e n c 3 ；) z ( pj = d d 。如( 尸) ，也就是模式树p - f f ：燃d b 中的所有出现次数。p 在d b 中 的支持度( s u p p o r t ) 定义为s ( p ) = a ( e ) i d b l ，p 在d b 中的频繁度( f r e q u e n t ) f ( p ) = x ( p ) i d b i 。显然，0 s s ( p ) s 1 ，f ( p ) 2 s ( e ) ，值得注意的是f ( p ) 是可以大于1 的。 在图4 中，舌将它”：看作是有序树的话那么模式树p 在数据树d 中共有4 个出现， = 礼2 ，5 ，6 ，4 ，1 0 ) ，2 - ( l 2 ，5 ，6 ，4 ，1 2 ) ，3 = 0 , 2 ，6 ，5 ，4 ，1 0 ) ，