（计算机应用技术专业论文）嵌入频繁子树挖掘研究.pdf

摘要 随着计算机与信息技术的发展，人们在日常事务处理和科学研 究中积累了大量数据。如何从中提取或“挖掘用户所需要的信息， 是当前信息科学技术领域面临的一大挑战。数据挖掘正是在这样的 背景下发展而来。 目前，数据挖掘及其应用己经渗透到多个学科，并在人工智能、 数据仓库、模式识别、生物信息分析等领域取得了丰硕的成果。频 繁模式挖掘是数据挖掘领域中的一个重要问题，其研究范围包括事 务、序列、树和图。树作为一种特殊的图结构，有其自身的特点和 优势，因此本文选择频繁子树挖掘作为本文的研究方向。论文的主 要内容安排如下： 首先，本文研究了数据挖掘和频繁模式挖掘的基本概念和性质， 并给出了子树模式的相关概念。此外，研究了无序树的结构特点和 规范形式，给出了无序树的规范化方法，综合模式增长的子树挖掘 策略和无序子树的挖掘策略，提出了无序树的模式增长框架。 第二，本文提出用模式增长方法在无序树构成的森林中挖掘嵌 入频繁子树。该算法利用规范化方法将无序树化为唯一的表示形式， 根据待增长模式的拓扑结构确定其增长点并构造相应的投影库，将 挖掘频繁子树模式问题转化为在各投影库中寻找频繁节点的问题。 实验表明其具有较高的效率。 第三，本文研究了加权支持度的基本概念和性质，比较了传统 频繁子树挖掘和加权频繁子树的不同，提出了挖掘加权嵌入频繁子 树的新算法。该算法分别以频繁节点和非频繁节点为基础，利用向 上模式增长和向下模式增长的方法产生加权频繁子树模式。最后， 通过实验对其正确性和有效性进行了验证。 关键词：频繁子树；无序树；嵌入子树；加权子树；加权支持度 a bs t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e ra n di n f o r m a t i o nt e c h n o l o g y ，a g r e a ta m o u n to f d a t ai s a c c u m u l a t e di nd a i l yw o r ka n di n s c i e n t i f i c r e s e a r c h h o wt oe x t r a c tu s e f u li n f o r m a t i o nf r o mt h e s ed a t ai s ag r e a t c h a l l e n g ef o rt o d a y sr e s e a r c h e r si ni n f o r m a t i o ns c i e n c e d a t am i n i n g a p p e a r si nt h i ss i t u a t i o n r e c e n t l y ，d a t am i n i n ga 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 o m a n vd i s c i p l i n e sa n da c h i e v e dp l e n t i f u lf r u i t si nm a n yf i e l d s ，i n c l u d i n g 7 a r t i f i c i a l i n t e l l i g e n c e ，d a t a w a r e h o u s e ，p a t t e r nr e c o g n l t l 仰， b i o i n f o r m a t i c s ，e t c f r e q u e n tp a t t e r nm i n i n gi s a ni m p o r t a n ti s s u ei n d a t am i n i n gd o m a i n i ti n v o l v e sm i n i n gt r a n s a c t i o n s ，s e q u e n c e s ，t r e e s a n dg r a p h s a sak i n do fs p e c i a ls t r u c t u r e ，t r e e sh a v et h e i rf e a t u r ea n d a d v a n t a g e ，s ow et a k ef r e q u e n ts u b t r e em i n i n ga s t h es u b je c to ft h i s p a p e r t h em a i nc o n t e n t so ft h ep a p e ra r ea sf o l l o w s ： f i r s t l y w ei n v e s t i g a t e d a t am i n i n ga n df r e q u e n tp a t t e r nm l n l n g c o n c e p t sa n dp r i n c i p l e sa n df o r m u l a t et h ec o n c e p to fs u b t r e ep a t t e r n w ea i s os t u d yc a n o n i c a lf o r mo fu n o r d e r e dt r e e sa n dp r e s e n tp a t t e r n g r o w t hf r a m e w o r kw h i c hi s b a s e do np a t t e r ng r o w t hm i n i n gs t r a t e g y a n du n o r d e r e ds u b t r e em i n i n gs t r a t e g y s e c o n d l y 。a l le f f i c i e n tp a t t e r ng r o w t ha l g o r i t h m i sp r e s e n t e df o r m i n i n gf r e q u e n te m b e d d e ds u b t r e e si n af o r e s to fr o o t e d ，l a b e l e d ，a n d u n o r d e r e dt r e e s i tu s e sac a n o n i c a lf o r mt or e p r e s e n tu n o r d e r e dt r e e si n au n i q u ew a y i tc r e a t e sap r o je c t i o nd a t a b a s ef o re v e r yg r o w i n gp o i n t o ft h ep a t t e r nt og r o w a n dt h e n t h ep r o b l e mi st r a n s f o r m e df r o m m i n i n gf r e q u e n t t r e e st of i n d i n gf r e q u e n fn o d e s i nt h ep r o j e c t l o n d a t a b a s e e x p e r i m e n t ss h o w e dt h a ti th a sg o o dp e r f o r m a n c e t h i r d l y ，w es t u d yt h ec o n c e p ta n dp r o p e r t y o fw e i g h t e ds u p p o r t d e g r e e a n dt h e n w ep r o p o s ea n o t h e ra l g o r i t h mt o m i n ew e i g h t e d i _ 一 e m b e d d e ds u b t r e e s i tu s e sb o t hg r o w i n g - u pa n dg r o w i n g - d o w nm e t h o d t og e n e r a t ef r e q u e n ts u b t r e ep a t t e r n s f i n a l l y ，w ed i de x p e r i m e n t st o p r o v ec o r r e c t n e s sa n dv a l i d i t yo ft h ea l g o r i t h m k e y w o r d s ：f r e q u e n ts u b t r e e ；u n o r d e r e dt r e e ；e m b e d e ds u b t r e e ； w e i g h t e ds u b t r e e ；w e i g h t e ds u p p o r td e g r e e 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立迸行 研究工作所得的成果。除文中已经注明引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研 究做出贡献的个人和集体，均已在文中作了明确的说明。本人完全 意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： ( 1 ) 本文综合模式增长的子树挖掘策略和无序子树的挖掘策略， 提出了无序树的模式增长框架。 ( 2 ) 本文根据无序树模式增长框架，提出了挖掘无序嵌入频繁子 树的算法u e f t 。 ( 3 ) 本文根据加权频繁子树的特性，提出了挖掘加权嵌入频繁子 树的算法w e f t 。 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权西南交通大学可以将本论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密日，使用本授权书。 ( 请在以上方框内打“4 ) 学位论文作者签名：4 1 1 支 日期： 2 口。5 r i 指导老师签名：彤3 落 日期如舻s f 7 1 1 课题研究背景 第1 章绪论 随着网络和其它信息技术的广泛应用，人们获得数据越来越容 易，积累的数据也越来越多，但分析和利用数据的能力正面临着越 来越严峻的考验。激增的数据背后隐藏着许多重要的信息，人们希 望对其进行更高层次的分析，以便更好地利用这些数据。数据挖掘 ( d a t am i n i n g ，d m ) 正是在这样的背景下发展而来。数据挖掘是从 大量数据中提取隐含的、未知的、非平凡的及有潜在价值的信息或 者模式。 频繁模式挖掘( f p m ，f r e q u e n tp a t t e r nm i n i n g ) 作为数据挖掘 的一个重要方向，近年来取得了许多的研究成果。其研究范围已经 从较为简单的关联规则和序列模式的挖掘发展到较为复杂的半结构 化模式的挖掘，比如树结构和图结构。我们知道，在数学中最为普 遍的图结构能够模拟几乎所有的事物之间的联系，而树作为一种特 殊的图结构，有其自身的特点和优势，其中频繁子树模式的挖掘已 经被广泛应用于生物特征信息分析、w e b 挖掘、半结构化数据挖掘 等各个方面。 本课题在此背景下，结合频繁模式的相关特点，主要对树结构 的频繁模式挖掘进行了研究和探讨。 1 2 课题研究现状 随着对半结构化数据研究与应用的深入，从半结构化数据中自 动抽取有用的信息，特别是相关规则和频繁模式的需求不断增加。 其中，半结构化数据中的频繁模式发现问题是一个重要的研究领域， 并主要被用于以下几个方面： 1 获取数据源的特征信息：当一个用户面对一个新的数据源时， 由于数据量庞大，用户不能轻易发现这个数据源的特征信息。而挖 酉亩奎通太堂亟硒究生堂僮i 金空笙2 夏 掘此数据源的频繁模式有助于用户了解数据源，然后用户可以使用 更加明确的查询来获取数据源的详细情况。 2 分类和聚类：频繁模式可以用于分类和聚类，构造分类或聚 类规则。通过把频繁模式作为数据的特征，就可以在应用中使用标 准的分类或聚类算法。例如，在文献【1 】中，z a k i 等利用频繁子树模 式构造出一个x m l 文档的分类器x r u l e s 。另外，也可以从一个站点 的w e b 日志中挖掘出用户的频繁访问模式，然后把这些模式作为用 户的特征，对用户进行分类。 3 构建索引和视图：为了加速信息的搜索速度，有时需要针对 经常出现、经常被搜索到的内容建立索引。而挖掘出的频繁模式就 可以用来建立包含结构信息的索引和视图。比如可以在无统一规范 的数据层次之上通过频繁模式信息建立一个新层次来帮助用户更快 的进行信息查找。 4 发现有用的模式信息：通过发现w e b 用户的浏览访问模式， 可以帮助我们更好的组织w e b 页面，并吸引更多的用户和商机。每 一次的w e b 会话中网页的链接信息可以被看作一个半结构化文档， 其中的典型结构就蕴涵着用户的兴趣点和访问模式。 为了顺应挖掘对象复杂化的要求，半结构化数据挖掘逐渐成为 了近些年的个研究热点，其中国内外学者提出了许多频繁子树挖 掘算法。 2 0 0 2 年，z a k i 在文献【2 】中提出了在有序树森林中挖掘嵌入频繁 子树的算法t r e e m i n e r ，利用有效的字符串编码和深度优先挖掘算法， 使t r e e m i n e r 成为当时最优的嵌入频繁子树挖掘算法。 2 0 0 2 年，a t e r m i e r 等人在文献【3 】中提出了在x m l 数据中挖掘 频繁嵌入式子树的算法t r e e f i n d e r ，其中将x m l 数据看作有根无序。 树集合。t r e e f i n d e r 在挖掘过程中采用了非精确性匹配的方法，使挖 掘效率有了大幅度提高，但是其并是一个完全的挖掘算法，不能保 证结果的完整性。 2 0 0 2 年，t a s i a 等人在文献【4 】中提出了在有序树中挖掘导出频 繁子树的算法f r e q t 。算法利用最右路径扩展的方法，建立枚举树， 并采用深度优先的挖掘策略。2 0 0 3 年，他们在文献f 5 1 中以f r e q t 一 酉亩奎通太堂亟班究生堂僮i 金塞簋三西 为基础，扩展算法思想，解决了在无序树集中挖掘频繁导出子树的 问题，提出了u n o t 算法。 2 0 0 3 年，s n i j s s e n 等人在文献【6 】中扩展了f r e q t 算法思想， 提出了在无序树集中挖掘频繁导出式子树的算法u f r e o t 。u f r e q t 利用无序树的规范化表达，在枚举频繁子树时效率更高。 2 0 0 3 年，y x i a o 等人在文献【7 】中提出了在有根无序树集中挖掘 最大导出式频繁子树的p a t h j o i n 算法，即利用路径“交”操作生成 侯选集。p a t h j o i n 算法必须满足兄弟节点无相同标号的假设。 2 0 0 3 年，y c h i 等人在文献【8 】中提出了在自由树集中挖掘频繁 导出子树的算法f r e e t r e e m i n e r 。2 0 0 4 年，他们在文献【9 1 中又提出了 在有根无序树和自由树( 无根无序树或无向无环图) 集合中挖掘频繁 导出子树的算法h y b r i d t r e e m i n e r 。h y b r i d t r e e m i n e r 提出了新的树规 范化表达，即宽度优先规范表达。2 0 0 5 年，他们在文献f 1 0 1 中又提 出了挖掘闭合频繁子树和最大频繁子树的算法c m t r e e m i n e r 。 近些年国内也提出了一些频繁子树挖掘算法，如朱永泰等提出 了面向有序树的嵌入式频繁子树挖掘算法e s p m t m ，利用序列匹配， 先同分后同构，不同于以往的工作，把树同构的判断工作放到了算法 的晚期，从而减少了整个挖掘过程的时间开销；王晨等提出了基于 序模式增长的挖掘嵌入频繁子树的算法c h o p p e r t l 2 1 以及其扩展算法 x s p a n n e r t t ：】；杨沛等提出了面向有序树的导出式频繁子树挖掘算法 p f t m i - 3 】，构造投影数据库，采用了侯选节点的递推式更新策略；赵 传申等在e s p m 的基础上提出了面向有序树的嵌入式频繁子树挖掘 算法f t p b t 】；马海兵等先后提出了有序嵌入式频繁子树挖掘算法 t p t t s l 和无序导出式频繁子树挖掘算法u t - g r o w t h t t + ；邹磊等提出了 有序嵌入式频繁子树挖掘算法p r e f i x t r e e s p a n l - 7 l 。 以上列举了一些比较经典的频繁子树挖掘算法，根据挖掘策略 的不同基本可以分为三类：第一类是a p r i o r i 系列算法，其中以 t r e e m i n e r t 2 1 为代表；第二类利用枚举树来产生候选子树，如f r e q t m 以及挖掘最大闭合子树的c m t r e e m i n e r t l 0 j ；第三类算法基于模式增长 原理，与前两类不同，不需要生成候选模式，可以直接生成频繁子 树，如c h o p p e r t l 2 j 、x s p a n n e r t l 2 l 等。 酉亩童通太堂亟班宜生堂僮j 盒室簋垒亟 1 3 本文主要内容 本文的主要工作可分为三大部分：首先对无序树的规范化方法 进行了研究和分析；其次提出了挖掘无序嵌入频繁子树的算法 u e f t ；然后提出了挖掘加权嵌入频繁子树的算法w e f t 。全文共分 为六章。本论文的组织结构如下： 第1 章绪论，主要介绍了课题的背景和意义、国内外研究现状， 最后介绍了论文的主要工作和内容安排。 第2 章相关知识，主要介绍了数据挖掘的概念与原理、频繁模 式的概念和发展趋势、频繁子树挖掘的基本概念和定义。 第3 章无序树规范化，主要介绍了无序树的相关概念，并对无 序树的各种规范化方法进行了分析和研究，并提出了本文的规范化 策略。 第4 章无序嵌入频繁子树挖掘，主要介绍了模式增长的子树挖 掘策略，并结合无序树规范化提出了通过无序树模式增长框架，提 出了无序嵌入频繁子树的挖掘算法u e f t ，并进行了实验比较。 第5 章加权嵌入频繁子树挖掘，主要介绍了加权支持度的特性， 对传统频繁子树和加权频繁子树进行了对比分析，提出了挖掘加权 嵌入频繁子树的算法w e f t ，并进行了实验和结果分析。 论文总结，对全文的研究工作进行了总结，并提出有待进一步 研究的问题。 第2 章相关知识 2 1 数据挖掘 2 1 1 数据挖掘的产生 随着科学技术的发展、信息技术的进步，人们进入了一个全新 的信息时代。计算机网络和存储技术的迅猛发展，使数据的传播和 积累速度在各个领域内不断提高。与此同时，众多领域内各自的数 据库的规模日益扩大，信息量也随之急剧增加，人们意识到隐藏在 这些数据之后的更深层次、更重要的信息能够描述数据的整体特征， 可以预测发展趋势，这些信息在决策生成的过程中具有重要的参考 价值。面对海量的数据库和大量繁杂的信息，如何才能从中提取有 价值的知识，进一步提高信息的利用率，由此引发了一个新的研究 方向：数据挖掘。数据挖掘作为一个新兴的多学科交叉应用领域， 正在各行各业的决策支持活动扮演着越来越重要的角色。 1 9 8 9 年，在第1 1 届国际人工智能联合会议( i n t e r n a t i o n a lj o i n t c o n f e r e n c eo na r t i f i c i a li n t e l l i g e n c e ) 的专题研讨会上，首次提出了基 于数据库的知识发现( k d d ，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 ) 技术。 1 9 9 5 年，在美国计算机年会( a c m ) 上，正式提出了数据挖掘( d a t a m i n i n g ) 的概念。数据挖掘，简单的讲，它是一个从大量数据中抽取 挖掘出未知的、有价值的模式或规律等知识的复杂过程。 2 1 2 数据挖掘的过程 整个知识挖掘( k d d ) 过程是由若干挖掘步骤组成的，而数据 挖掘仅是其中的一个主要步骤。整个知识挖掘的主要步骤有： 1 数据清洗( d a t ac l e a n i n g ) ，其作用就是清除数据噪声和与挖 掘主题明显无关的数据； 2 数据集成( d a t ai n t e g r a t i o n ) ，其作用就是将来自多数据源中 一一 酉亩套通太堂亟班究生兰僮i 金空丝西 的相关数据组合到一起： 3 数据转换( d a t at r a n s f o r m a t i o n ) ，其作用就是将数据转换为 易于进行数据挖掘的数据存储形式； 4 数据挖掘( d a t am i n i n g ) ，它是知识挖掘的一个基本步骤， 其作用就是利用智能方法挖掘数据模式或规律知识； 5 模式评估( p a t t e r ne v a l u a t i o n ) ，其作用就是根据一定评估标 准( i n t e r e s t i n gm e a s u r e s ) 从挖掘结果筛选出有意义的模式知识； 6 知识表示( k n o w l e d g ep r e s e n t a t i o n ) ，其作用就是利用可视 化和知识表达技术，向用户展示所挖掘出的相关知识。 其实数据挖掘仅仅是整个知识挖掘过程中的一个步骤，但由于 其在整个过程中的重要性，目前工业界、研究领域都广义的使用“数 据挖掘”词来表示整个知识挖掘过程，即数据挖掘就是一个从数据 库、数据仓库或其它信息资源库的大量数据中发掘出有趣的知识。 2 1 3 数据挖掘的热点问题 近年来，数据挖掘的热点包括w e b 挖掘、生物信息挖掘、文本 挖掘等。随着w e b 技术的发展，各类电子商务网站风起云涌，产生 了大量的w e b 数据，如何对这些数据进行分析和挖掘，充分了解客 户的喜好、购买模式，增加网站竞争力，已成为一个重要问题；生 物信息挖掘则完全属于另外的一个领域，由于生物信息如基因等的 结构和组合千变万化，需要更为复杂、效率更高的数据挖掘算法来 支持；文本挖掘一直以来都是数据挖掘的一个热点问题，但是随着 数据挖掘应用领域不断扩大，传统的结构化文本挖掘已经逐渐扩展 到半结构化、非结构化的文挡的挖掘。以上简单列举了目前数据挖 掘的三个热点问题，本文主要研究的基于树结构的频繁模式挖掘同 这些研究领域均有着密切的联系。 2 2 频繁模式挖掘 频繁模式挖掘是数据挖掘中的一个重要研究领域，随着研究的 不断深入，频繁模式挖掘对象已经从传统的频繁项集挖掘，发展到 酉亩窑通太堂亟班究生堂僮i 金塞篁z 亟 稍微复杂的序列模式和时间序列模式挖掘，并逐渐延伸到更为复杂 的频繁子树和频繁子图挖掘。 2 2 1 频繁项集挖掘 频繁项集挖掘是数据挖掘领域的传统课题，国内外已经取得了 很多的成果。频繁项集挖掘最初应用于在事务库中发现关联规则的 a p r i o r i 算法，由r a g r a w a l 等人在文献【1 8 】中首先提出来。关联规则 反映了大量数据中项目集之间有一定的关联。识别或发现所有的频 繁项集是关联规则发现算法的关键。 a p r i o r i 算法是最有影响的挖掘频繁项集的算法，其原理是基于 算法使用了频繁项集的先验知识：即频繁项集的所有非空子集必须 也是频繁的。算法使用一种逐层搜索的迭代方法，将频繁k 项集用 于探索频繁( k + l 卜项集。a p r i o r i 算法的一个巨大优势是其挖掘大型事 务库的能力，不需要将事务库全部读入内存就可以进行挖掘工作， 然而该算法需要多次扫描数据库，扫描次数等于发现的最长的频繁 项集的项的个数。 文献【1 9 】中的f p g r o w t h 算法是另一个经典的频繁项集挖掘算 法。其算法思想是通过构造条件模式库直接挖掘频繁项集，其中省 略了候选项集的产生过程。研究表明，f p g r o w t h 算法大约比a p r i o r i 算法快一个数量级。 另外，由于频繁项集的数量巨大，使得挖掘结果仍难以处理， 于是产生了最大频繁项集和闭合频繁项集的挖掘。在不损失或基本 不损失数据信息的基础上，最大频繁项集和闭合频繁项集的数量相 对频繁项集大大减少，提高了挖掘的效率。 2 2 2 序列模式挖掘 序列模式挖掘同样由r a g r a w a l 在文献【2 0 】中首先提出。序列模 式与关联规则之间的区别在于后者描述的是在一次购物中所购买物 品之间的关联关系，即事务内部的关联模式。而前者则描述同一顾 客在多次购物所购物品之间可能存在的某种关联关系，即事务之间 酉亩奎通太堂亟硒究生堂僮i 金室簋垦区 的关联模式。 j p e i 等人在文献【2 1 】中提出了p r e f i x s p a n 算法，利用f p g r o w t h 算法的思想，用模式增长方法挖掘频繁序列模式，其基本思路是基 于前缀子序列，将相关的后缀序列经过投影操作组织成投影库，然 后在相应的投影库内，寻找局部频繁子序列，与前缀结合，增长为 新的频繁序列模式。 2 2 3 频繁子树和频繁子图挖掘 随着i n t e r n e t 日益普及和w e b 挖掘、半结构化文档挖掘等需求， 频繁模式的研究对象也自，然地从最初的事务项集和序列，逐渐扩展 到树和图等复杂结构型数据。如何发现挖掘频繁子树和频繁子图的 高效算法，日益成为一个具有重要理论和实用价值的研究课题。 频繁子图挖掘问题首先由i n o k u c h i 提出，同时给出a g m 算法i z z i 。 a g m 算法使用基于a p r i o r i 的方法挖掘频繁子图模式。挖掘频繁子 图的另一个著名的算法是g s p a n 算法1 2 3 1 。此算法利用深度优先、模 式增长的方法避免了候选模式的生成和测试。因此g s p a n 成为目前 最有效的图挖掘算法之一。 2 3 频繁子树挖掘基本定义 半结构化数据通常可以表示为树型结构，由于树型结构具有清 晰简洁的表达能力，因此它己经成为描述半结构化数据的主要载体。 树的类型有多种，如自由树、有根无序树、有根有序树等，不同类 型的树具有不同的数据表达能力和范畴。树结构是图结构的特例， 因此可以利用图的性质定义各种类型的树。在本小节中，我们将给 出一些必要的子树挖掘背景知识。首先给出关于树结构的一些基本 定义，其中包含不同种类的树结构；其次介绍了不同的子树模式； 最后给出子树模式挖掘问题的基本定义。 2 3 1 树和森林 酉直变通太堂亟研究生兰僮i 金空簋2 西 定义2 1 有根树( r o o t e dt r e e ) 有根树是一种连通有向无环图，可表示为一个五元组t = ( v ，v o ，e ， ，l ) ，其中v 是节点集合；v 0 是树的根节点；e 是树的边集：是 标识集合；l 是从v 到的映射，每个节点都有各自对应的标识， 不同的节点可以有相同的标识符。对于( v 1 ，v 2 ) e ，均有v 1 ，v 2 v ， 称v l 为v 2 的父亲，v 2 为v 1 的孩子。 在树的分类中，除了有根树以外还有一种特殊的树一一自由树 ( 无根树) ，自由树是连通的无向无环图，其中不存在根节点。自由 树不在本文讨论的范畴内，本文仅讨论有根树。 给定一棵树t ，树t 中节点的数量称为树的大小，记为l t i ；在t 中，v o 是根节点，那么节点v 的深度定义为从v o 到v 的路径长度， 树中所有节点的深度的最大值，即是树高；再设x 和y 是树t 中的 两个节点，如果x 出现在v o 到y 的路径上，则x 和y 是祖孙关系， 且x 是y 的祖先，y 是x 的子孙。如果x 出现在v o 到y 的路径上， 且x 与y 之间存在1 条边，则x 和y 是父子关系，且x 是y 的父亲， y 是x 的孩子。如果x 和y 拥有同一个父亲，则x 和y 是兄弟关系。 如果x 和y 具有相同祖先，则x 和y 称为堂兄弟。 定义2 2 有根有序树( r o o t e do r d e r e dt r e e ) 给定一棵有根树t ，设v 是树的任意非叶子节点( 内部节点) ，且 v 具有k 个孩子，给这些孩子节点排序，形成v o v k ，排完序后 形成的树被称为有根有序树。 定义2 3 有根无序树( r o o t e du n o r d e r e dt r e e ) 给定一棵有根树t ，设v 是树的任意非叶子节点( 内部节点) ，且 v 具有k 个孩子，若这k 个孩子间无固定顺序，则此树被称为有根无 序树。 定义2 4 森林( f o r e s t ) 森林是树的集合，数据库d 就是森林。 总的来说，自由树是保持连通的无向无环图；有根无序树是有 向无环图，并且满足以下条件：图中存在1 个节点，它没有出边， 该节点被称为“根”；除此以外的节点仅有一条出边；从“根”到其他节 点仅有1 条路径。有根有序树是有根无序树的特例，它要求树中所 酉亩奎通太堂亟班究生堂僮诠空筮! q 厦 有的兄弟节点之间具备预先定义的序。在本文中涉及到的树结构类 型，仅限于有根有序树和有根无序树的范畴。 2 3 2 子树模式 正如树结构存在不同的分类，子树模式也分为不同的种类，下 面给出三种不同的子树模式的定义。 定义2 5 底部子树( b o t t o m u ps u b t r e e ) 对于树t ( 具有节点集v 、边集e ) ，那么树t ( 具有节点集v 、 边集e ) 就是树t 的一棵底部子树，当且仅当( 1 ) v 包含于v 。( 2 ) ( v l ，v 2 ) e ，在t 中v 1 是v 2 的父亲，当且仅当在t 中v 1 是v 2 的父亲。 ( 3 ) 对于v 1 ，v 2 v ，在t 中p r e o r d e r ( v 1 ) p r e o r d e r ( v 2 ) 且仅当在t 中p r e o r d e r ( v 1 ) p r e o r d e r ( v 2 ) 。( 4 ) 对于v v ，如果v v ，那么 v 在t 所有的后代都在t 中。实际上，可以通过取出t 中任意一个 节点及其所有后代来获得t 的底部子树。 定义2 6 导出子树( i n d u c e ds u b t r e e ) 对于树t ( 具有节点集v 、边集e ) ，那么树t ( 具有节点集v 、 边集e ) 就是树t 的一棵导出子树，当且仅当( 1 ) v 包含于v 。( 2 ) ( v l ，v 2 ) e ，在t 中v 1 是v 2 的父亲，当且仅当在t 中v 1 是v 2 的父亲。 ( 3 ) 对于v 1 ，v 2 v ，在t 中p f e o r d e r ( v 1 ) p r e o r d e r ( v 2 ) 当且仅当在t 中p r e o r d e r ( v 1 ) p r e o r d e r ( v 2 ) 。 定义2 7 嵌入子树( e m b e d e ds u b t r e e ) 对于树t ( 具有节点集v 、边集e ) ，那么树t ( 具有节点集v 、 边集e ) 就是树t 的一棵嵌入子树，当且仅当( 1 ) v 包含于v 。( 2 ) ( v l ，v 2 ) e ，在t 中v 1 是v 2 的父亲，当且仅当在t 中v 1 是v 2 的祖先 ( 包括父亲) 。( 3 ) 对于v 1 ，v 2 v ，在t 中p r e o r d e r ( v 1 ) p r e o r d e r ( v 2 ) 当且仅当在t 中p r e o r d e r ( v t ) p r e o r d e r ( v 2 ) 。 图2 1 给出了三种不同种类的子树模式，其中树t 2 、t 3 、t 4 分 别是树t 1 的三种不同种类的子树模式。 t li z t 3 i 耳 图2 1 不同种类的子树模式 在图2 1 中，对于左边的树t 1 来说，树t 2 是一棵底部子树， 树t 3 是一棵导出子树，而不是底部子树，树t 4 是一棵嵌入子树； 而不是底部子树或者导出子树。由图可以看出，底部子树包含了节 点相应的全部叶子节点，导出子树包含了节点之间的父子继承关系， 而嵌入子树则包含了节点之间所有直接或非直接的继承关系。以下 给出三种子树模式的包含关系：底部子树= 导出子树= 嵌入子树。根 据以上的关系，可以看出嵌入子树数量最多，并且可以反映节点之 间隔代的继承关系，因此对于嵌入子树的挖掘可以反映出更多的结 构信息。 2 3 3 子树模式挖掘问题 定义2 8 支持度 给定数据库d 以及一棵模式树m ，定义支持数d ( m ，t ) ，当且仅 当m t ，d ( m ，t ) = 1 否则d ( m ，t ) = o ，则定义m 在d 中的支持数 f r e q ( m ，d ) = e tedd ( m ，t ) ，定义m 在d 中的支持度s u p ( m ，d ) = e t ed d ( m ，t ) d i 。 给定数据库d 以及一棵模式树m ，定义相对支持数dw ( m ，t ) ， 当且仅当m t ，dw ( m ，t ) = m 在t 中出现的次数，否则dw ( m ，t ) = 0 ， 则定义m 在d 中的加权支持数f r e qw ( m ，d ) = e teddw ( m ，t ) ，定义m 在d 中的加权支持度s u pw ( m ，d ) = teddw ( m ，t ) i d i 。 定义2 9 子树模式挖掘问题 给定数据库d 、最小支持度m i n s u p 以及一棵模式树m ，如果m 在d 中的支持度s u p ( m ，d ) = m i n s u p ，那么m 就称为频繁子树， 则频繁子树挖掘问题定义为在数据库d 中寻找所有满足 s u p ( m ，d ) = m i n 二s u p 的子树模式m 。 酉亩窑通太堂亟班究生堂僮i 盒玄簋呈2 亟 第3 章无序树规范化 3 1 有序树的存储表示 在子树模式挖掘过程中；树结构的存储表示是一个很重要的部 分，很多算法都是同其数据结构息息相关的。传统的树结构的存储 表示方式主要有邻接表、邻接矩阵以及孩子兄弟表示法。 传统的数据结构虽然应用广泛，但是仍然存在一些不足。首先， 传统的数据结构消耗的存储空间较大；其次，在子树模式挖掘的过 程中，并不一定能够很好的适应各算法的特点；另外，很重要的一 点，对于很多树结构，传统的数据结构并不能很好的表示，比如采 用孩子兄弟表示法来表示无序树结构，由于无序树中各个兄弟节点 间不存在固定顺序，那么数据结构中兄弟节点的链接如何确定就成 为一个问题。于是很多的子树模式挖掘算法提出了新的树结构的存 储表示方法。 图3 1 树的示例 例如，在文【2 4 1 介绍到了一个有序树的前序字符串编码的嵌套定 义：( 1 ) 对于只有根节点的标记有序树t ，t 的前序字符串编码为l ，0 ， 其中l ，是根节点的标记；( 2 ) 对有多个节点的有序树t ，设：是t 的根 节点，节点标记是l r ，且按照自左向右的顺序，r 的子节点依次是 r l r k ，那么t 的前序字符串编码为l s ( t r l ) s ( t r k ) o 。根据上述定义， 图3 1 中t 的前序字符串编码为：s ( t ) = a b d o e o f o o c g o o o 。这种前 序编码的好处在于可以很容易的计算出底部子树的前序字符串。比 如，从b 开始扫描s ( t ) ，匹配字符数目与标记0 的数目，得到子串 b d o e o f 0 0 ，则这个结果子串正是以b 为根的底部子树的前序编码。 利用这样的性质，可以将子树匹配问题简化为字符串匹配问题，大 酉亩奎通太堂亟班究生堂僮论空筮! 兰夏 大提高了效率。另外，z a k i 等人也提出了类似的基于深度序的树结 构编码1 2 5 1 。 而在u f r e q t 算法【6 1 中，n i j s s e n 等在深度优先遍历的基础上， 记录每个节点的深度信息和标记。例如，对图3 1 所示的有序树t ， 其字符串编码为s ( t ) = ( ， ， ， ， ， ， ) 。其中每一个 对代表一个节点， 数字代表节点的深度，字符表示节点的标记。 以上两种树结构表示方式在形式上有一定区别，但是实质上都 是基于深度优先遍历，而y c h i 等人在h y b i r d t r e e m i n e r m 中提出了基 于宽度优先遍历的树结构编码。例如，对图3 1 所示的有序树t ，其 字符串编码为s ( t ) = a $ b c $ d e f $ g 撑，其中$ 表示兄弟家族，撑表示字 符串的结束。 以上列举了目前相对流行的一些树结构表示方法，与传统的数 据结构，如邻接表、邻接矩阵、孩子兄弟表示法相比，采用这些字 符串编码表示有序树可以节约存储空间。给定一棵有序树t 有n 个 节点，则采用邻接表表示带有序树需要大小为4 n 2 的存储空间，其 中存储标记和邻接表的头指针需要2 n 的空间，存储每个表节点的 n e x t 指针和标记需要2 n - 2 的空间；采用邻接矩阵则需要n + f * n 的空 间( f 是最大出度) ，其中存储标记需要n 的空间，存储邻接信息需要 f * n 的空间；孩子兄弟表示法则需要3 n 的空间；而上述三种字符串 编码方式只需要2 n 的空间。从存储空间上看，树结构的字符串编码 形式效率较高。另外，这些编码形式对于无序树结构的表示也有良 好的适应性。下面给出本文将采用的有序树存储方式一有序树深度 优先编码。 定义3 1 有序树深度优先编码 定义“1 ”为不同于任何节点标识和边标识的特殊标识，用来表示 先序遍历中的每一次向上回朔。下面给出深度优先编码的递归定义： ( 1 ) 如果树t 只有一个根节点r ，那么树t 的编码s ( t ) 为i t - 1 ，其 中l r 为根节点r 的标识，1 表示向根节点的一次回朔；( 2 ) 如果树t 存在多个节点，假设根节点为r ，r 的孩子依次为r l r k ，那么树t 的编码为l r s ( t 。1 ) s ( t r k ) 1 。根据上述定义，图3 1 中t 的前序字符 酉亩窑遵太堂亟硒宜生堂焦诠室蓥兰垒亟 串编码为：s ( t ) = a b d 1 e 1 f 1 - 1 c g 11 1 。 以上是本文给出的有序树深度优先编码定义，在本文后几章的 算法设计中，对此编码进行了适当的改造，保持节点标识不变，对 回朔标记改造，令新的回朔标记= o 对应节点的深度优先序号。根据 上述改造，图 3 1中t的前序字符串编码为： s ( t ) = a b d 3 e 4 f 5 2 c g 761 ，例如回朔标记3 代表其对应的节点 为第3 个节点d 。 3 2 无序树的存储表示 在子树模式挖掘问题中，树结构的匹配，也就是树的同构问题， 是一个核心问题。如何确定子树模式的匹配，是计算子树模式支持 度的基础。下面我们首先给出树的同构定义以及相关性质。 定义3 2 有序树同构 给定两棵有序树t l 和t 2 ，如果存在一个映射函数f ：v 1 一v 2 ， 使得任取x 、y v l ，满足以下4 个条件： ( d f 是一对一的，也就是说如果x c y ，那么f ( x ) f ( y ) 。 ( 2 ) f 保持父亲一孩子关系，也就是说如果( x ，y ) e 1 ，那么 ( f ( x ) ，f ( y ) ) e 2 。 ( 3 ) f 保持兄弟节点的相对顺序，也就是说如果x 在y 之前，那么 f ( x ) 在f ( y ) 之前。 ( 4 ) f 保持标识，也就是说l 1 ( x ) = l 2 ( f ( x ) ) 。 那么，称t l 和t 2 同构，f 叫做从t 1 到t 2 的一个同构，或者从 t 1 到t 2 的一个匹配。 定理3 1 对于两棵有根有序树t l 和t 2 ，当且仅当有序树深度优 先编码s ( t 1 ) = s ( t 2 ) 时，t l 和t 2 同构。 证明：因为有序树深度优先编码可以唯一的标志一棵有序树， 那么当s ( t 1 ) = s ( t 2 ) 时，t 1 和t 2 是同一棵有序树，所以t 1 和t 2 同构。 定义3 3 无序树同构 给定两棵无序树t l 和t 2 ，如果存在一个映射函数f ：v 1 _ v 2 ，使 得任取x 、y v 1 ，满足以下3 个条件： 酉亩窑通太堂亟班究生堂僮论空簋兰豆 ( 1 ) f 是一对一的，也就是说如果x y ，那么f ( x ) = - f ( y ) 。 ( 2 ) f 保持父亲一孩子关系，也就是说如果( x ，y ) e 1 ，那么 ( f ( x ) ，f ( y ) ) e 2 。 一 ( 3 ) f 保持标识，也就是说l f f x ) = l 2 ( f ( x ) ) 。 那么，称t 1 和t 2 同构，f 叫做从t 1 到t 2 的一个同构，或者从 t 1 到t 2 的一个匹配。 图3 2 给出了一个树的同构示例。 ” t 4 图3 2 树的同构示例 根据上述定义，在图3 2 中，有序树