（计算机应用技术专业论文）频繁子树挖掘及其相关技术的研究.pdf

郭鑫：频繁子树挖掘及其相关技术的研究 摘要 随着计算机与信息技术的发展，人们在日常事务处理和科学研究中积 累了大量数据。如何从中提取或“挖掘 用户所需要的信息，是当前信息 科学技术领域面临的一大挑战。数据挖掘正是在这样的背景下发展而来。 目前，数据挖掘及其应用己经渗透到多个学科，并在人工智能与机器 学习、数据库、模式识别、生物信息学、神经网络等领域取得了丰硕的成 果。频繁模式挖掘是数据挖掘领域的一个基本问题，其研究范围包括事务、 序列、树和图。其方法被广泛应用于许多其它数据挖掘任务中，如相关性 分析，周期分析，最大模式，闭合模式，查询，分类，索引等等。 在现实积累的大量数据中有一类诸如树、图等结构化的数据，它们具 备很强的层次表达能力，几乎能够模拟所有的事物之间的联系，因此基于 树的数据挖掘有着广阔的应用空间，如w e b 挖掘、空间数据挖掘、生物信 息学中蛋白质结构挖掘、药物分子设计及其功能预测等等。如何发现挖掘 频繁子树的高效算法，已日益成为数据挖掘中的一个新的研究热点，对频 繁子树挖掘算法的研究将成为个具有重要的理论意义和应用价值的研 究课题。 本文主要研究工作包括： ( 1 ) 提出了一种基于子树向量的快速导出子树挖掘算法i t m s v ( i n d u c e ds u b t r e e sm i n i n gb a s e do ns u b t r e ev e c t o r ) 。算法基于子树 向量和哈希表构建一个多层的数据结构，在挖掘过程中能够减少树同构的 判别时间，并且只需要进行一次数据库的扫描操作，减少了扫描次数，提 高了算法的运行效率。 2扬州大学硕士论文 ( 2 ) 提出了一种可以在大型树数据库中高效挖掘无序树的算法 _ i i t m i n e r ( u n o r d e r e dt r e e sm i n e r ) ，由于所挖掘的树具有无序的特性， 因此为了避免挖掘出相同子树的情况，本文提出了一种高效的无序树的标 准化方法，将无序树转化为标准化子树，再利用本文提出的快速有序树挖 掘算法得到所有的标准化子树。 ( 3 ) 提出一种基于最小闭树特征集的聚类与分类方法，有效地解决了 在实际应用中因数据量大而无法聚类与分类的问题。其基本思想为：提出 以最小闭树特征集作为候选聚类与分类特征，并采用动态阈值按相似度聚 类方法，使得树聚类快速而精确，提出树分类规则等级概念，并应用于树 分类方法中，能迅速预测未知的树结构。 关键字：数据挖掘，频繁子树，闭树模式，导出子树，内含子树，无 序树，自由树，树聚类，树分类，网络日志，频繁子图，子图同构 郭鑫：频繁子树挖掘及其相关技术的研究 3 a b s 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 ，ag r e a t a m o u n to fd a t ai sa c c u m u l a t e di nd a i l yw o r da n di ns c i e n t i n cr e s e a r c h h o wt o e 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 e d a t ai sag r e a tc h a l l e n g ef o rt o d a y s r e s e a r c h e r si ni n f b r m a t i o ns c i e n c e i ) a t am i n i n ga 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 sh a v ea l r e a d yc o m ei n t om a n y d 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 nd i v e r s i n e df i e l d s ，i n c l u d i n ga r t i n c i a l i 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 ，p a t t e r nr e c o g n i t i o n ，b i o i n f 6 r m a t i c s ， n e u r a lc o m p u t i n g ，a n ds oo n f r e q u e n tp a t t e r nm i n i n gi sab a s i cp r o b l e mo fd a t a m i n i n g ，i n c l u d i n gm 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 s sa n dg r a p h s t h e a l g o r i t h mf b ri th a sb e e np r e v a l e n t l yu 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 h a 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 t e r n 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 xt e c h n o l o g ye t c i nl a r g ea m o u n t so fd a t aa c c u m u l a t e di nr e a l i t y ，e x i s tm a n ys t r u c t u r e dd a t a ， s u c ha st r e e so rg r a p h s t h e yh a v eag r e a ta b i l i t yt oe x p r e s sh i e r a r c h i e sa n d s i i n u l a t ea l m o s ta 1 1p a t t e r n so fl i n k s s ot h et r e e - b a s e dd a t am i n i n gc a nb e a p p l i e dw i d e l yi na r e a ss u c h a sw e bm i n i n g ， s p a t i a ld a t am i n i n g ，p r o t e i n s t r u c t u r em i n i n go fb i o i n f l o r m a t i c s ，d r u gd e s i g na n di t sf u n c t i o np r e d i c t i o na n d s oo n t of i n dt h ee m c i e n ta l g o r i t h mo ff r e q u e n ts u b t r e em i n i n gb e c o m ean e w h o t s p o ti nt h ed a t am i n i n gn e l d r e s e a r c h i n gt h ef r e q u e n ts u b t r e em i n i n g a l g o r i t h mw i l lb eas t u d yo fg r e a tt h e o r e t i c a ls i g n i f i c a n c ea n da p p l i c a t i o nv a l u e m m l n g 4扬州大学硕士论文 t h em a i nb o d yo ft h i st h e s i si n c l u d e s ： ( 1 ) a na l g o r i t h mi t m s v ( i n d u c e ds u b t r e e sm i n i n gb a s e do ns u b t r e ev e c t o r ) i s p r e s e n t e dt od i s c o v e rf r e q u e n ti n d u c e ds u b t r e e sq u i c k l yb yt a k i n g f u l l a d v a n t a g e so ft h ef e a t u r e so fs u b t r e ev e c t o ra n dc o m b i n i n gw i t ht h eh a s ht a b l e t h ea l g o r i t h m ，a sar e s u l to fc o n s t r u c t i n gam u l t i - l a y e r e dd a t as t r u c t u r e ，c a n l e s s e nt h et i m eo fd i s t i n g u i s h i n gi s o m o r p h i s md u r i n gm i n i n g ，a n dn e e ds c a n d a t a b a s eo n l yo n c es ot h a ti ti n d u c e st i m e so fs c a n n i n ga n di m p r o v e st h e e f j f i c i e n c yo fa l g o r i t h m ( 2 ) i nt h i sp a p e r ，i tp r e s e n t sa na l g o r i t h mu t m i n e r ( u n o r d e r e d t r e e sm i n e r ) t h a tc a nq u i c k l yd i s c o v e rf r e q u e n tu n o r d e r e dt r e e si nl a r g ef 6 r e s t w ep r o p o s e s t a n d a r d i z e dm e t h o d o l o g yt h a tc a nq u i c k l yc o n v e r tu n o r d e r e ds u b t r e e si n t o s t a n d a r ds u b t r e e sa n du s ea l g o r i t h mo fo r d e r e dt r e e st om i n ea l lo fs t a n d a r d s u b t r e e s ( 3 ) at r e ec l u s t e ra n dc l a s s i n c a t i o na l g o r i t h mw a sp r o p o s e db a s e do nl e a s t c l o s e dt r e e ，w h i c he f f e c t i v e l ys o l v e dp r o b l e m si nl a r g ea m o u n to fd a t ai n p r a c t i c a la p p l i c a t i o n t h eb a s i cm e t h o di sb r i n g i n gf o r w a r dl e a s tc l o s e dt r e ea s t h ec a n d i d a t ec l u s t e ra n dc l a s s i n c a t i o nf e a t u r e ，u s i n gd y n a m i ct h r e s h o l db y s i m i l a r i t yc l u s t e rt om a k et r e ec l u s t e ro p e r a t i o nb em o r eq u i c ka n da c c u r a t e ， m e a n w h i l et h ec o n c e p to ft r e ec l a s s i f i c a t i o nr u l eg r a d ep r o p o s e di su s e di nt r e e c l a s s i f i c a t i o na l g o r i t h m ，s ot h a tt h eu n k n o w nt r e es t r u c t u r ec o u l db ep r e d i c t e d p r o m p t l y k e y w o r d s ：d a t am i n i n g ，f r e q u e n ts u b t r e e ， c l o s e dt r e e p a t t e r n ， i n d u c e d s u b t r e e ，i s o m o r p h i cs u b t r e e ， u n o r d e r e dt r e e s ，f r e et r e e ，t r e ec l u s t e r ， t r e e c l a s s i f i c a t i o n ，w e bl o g ，f r e q u e n ts u b g r a p h ，s u b g r a p hi s o m o r p h i s m 郭鑫：频繁子树挖掘及其相关技术的研究 9 9 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含其他个人或 集体已经发表的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 学位论文作者签名： 签字日期： 却么 l 砂吾7 年 | 6 月乙日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保 留并向国家有关部门或机构送交学位论文的复印件和电子文档，允许论文 被查阅和借阅。本人授权扬州大学可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编 学位论文。同时授权中国科学技术信息研究所将本学位论文收录到 中国 学位论文全文数据库，并通过网络向社会公众提供信息服务。 呻 学位论文作者签名：却绥 导师签名： 簟弓 f i 签字日期：7 年钥日签字日期：9 7 年月日。 f l ( 本页为学位论文末页。如论文为密件可不授权，但论文原创必须声明。) 郭鑫：频繁子树挖掘及其相关技术的研究 5 第一章绪论弟一早珀下匕 1 1 论文研究背景及意义 随着信息处理的高速发展，数据挖掘已经引起了人们的极大关注，数 据挖掘及其应用已经渗透到多个学科，并在人工智能与机器学习、数据库、 模式识别、生物信息学、神经计算等领域取得了丰硕的成果。尽管目前的 数据库系统可以高效地实现数据的录入、查询、统计等功能，但由于数据 量庞大以及数据库系统中分析方法的严重缺乏，使得它无法发现数据中隐 藏的相互联系，更无法根据当前的数据去预测未来的发展趋势。因此，迫 切需要一种从大量数据中提取出隐藏在其中的有用信息，正是为了这种满 足，将机器学习应用于大型数据库中的数据挖掘技术( d a t am i n i n g ) 得到 了长足的发展。数据挖掘又称为数据库中的知识发现( k n o w l e d g e d i s c o v e r i n gd a t a b a s e ，简称k d d ) ：指从大型数据库或者数据仓库中提取 隐含的、未知的、非凡的及有潜在有应用价值的信息或者模式。例如大型 超市可以根据日积月累的销售数据发现内在的规律以供预测未来趋势和 提供更好的服务。数据挖掘其实是一种决策支持的过程，它融合了数据库、 人工智能、数理统计等多个领域的理论和技术，高度自动化的分析企业原 始数据，做出归纳性的推理，从中挖掘出潜在的规律，帮助企业做出正确 的决策。 频繁模式挖掘是数据挖掘领域的一个基本问题。1 9 9 4 年，为了寻找大 量商务事务库中的项集之间的有趣联系，a g r a w a l 开创性地提出了关联规 则挖掘问题，并发表了著名的a p r i o r i 心1 算法，用频繁项集产生关联规则， 6扬州大学硕士论文 发现顾客购买的不同商品之间的联系，分析顾客的购物习惯，帮助零售商 制定营销策略。1 9 9 5 年，为描述同一顾客在多次购物所购物品之间可能存 在的某种关联关系，a g r a w a l 又发表了序列模式挖掘算法。此后，频繁项 集与频繁序列挖掘算法被广泛应用于许多其它数据挖掘任务中，如相关性 分析，周期分析，最大模式，闭合模式，查询，分类，索引等等。到现在， 研究者已发表数篇论文，或提出新的算法，或改进己有的算法，来更有效 的解决这个问题。 随着研究的深入，越来越多的问题呈现出来，也提出了更高的要求。 如a p r i o r i 2 1 和f p g r o w t h 提出时，主要是针对非结构化数据挖掘的研究， 算法能提高挖掘的效率和性能。目前，复杂类型数据的挖掘需求上升，越 来越多的专家学者开始关注这方面的新应用和理论研究，并试图利用以往 在无结构化数据挖掘方面的经验和方法论来解决新问题。非结构化数据 ( 集合) 表达了事物间的松散关系，序列则主要是前后关系，树和图则具备 了结构关系等。集合显得简单易处理，但表达能力不够，应用范围会受到 限制。序列具有一些结构化数据的特性，有一定的表达关系的能力，如前 后关系，同时也简单易用。而树和图则具备了很强的表达能力，它们可以 刻画物质世界内大多数的关系，因此具备了广泛的应用基础。 最近几年，i n t e r n e t 日益普及，万维网成为一个庞大的，分布广泛的 全球性信息服务中心。h t m l 和x m l 文档是其最重要的载体，也为数据挖掘 提供了新的丰富资源。w e b 挖掘是数据挖掘领域中一个发展迅速，更具挑 战性的课题。其内容包括w e b 链接结构，w e b 内容及w e b 访问模式挖掘等。 由于h t m l 和x m l 文档本身及页面之间的链接信息都可以用树或图结构来 建模，因此，频繁模式的研究对象，也自然的从最初的事务项集和序列， 逐渐扩展到树和图等结构化数据。如何发现挖掘频繁子树和频繁子图的高 郭鑫：频繁子树挖掘及其相关技术的研究 7 效算法，日益成为一个具有重要理论和实用价值的研究课题。 目前，结构化数据挖掘已经成为数据挖掘中研究的一个重要的课题， 主要包括树挖掘和图挖掘h 5 6 ， 。而且应用广泛，特别是在生物信息，w e b 结构，x m l 数据等领域中具有很高的应用价值。例如印1 在生物中核糖核酸 ( r n a ) 分子结构可以表示成树结构，研究人员为了得到一种新的r n a 的相 关信息，就必须用已知的r n a 结构与之比较，寻找与之相同的拓扑结构， 从而得到这个新r n a 的功能信息。另外可以把用户访问某个网站的网页集 合表示成一个树结构，所有用户的访问历史就构成了一个树数据库，此时 就可以找出用户们在该网站的最频繁的访问模式，便于网站设计人员调整 网站构架，优化网站结构。 本文旨在借鉴国内外在结构化数据的挖掘技术方面已有的成果，设计 优化结构化数据挖掘算法，解决大多数算法在求频繁项集需要进行大量的 树同构或图同构等瓶颈问题，以进一步提高结构化数据挖掘的速度与效 率。对其中的有序树、无序树、自由树等的挖掘与查找进行研究，提出自 己见解或者解决方案，为结构化数据的挖掘提供实际可行的办法，同时也 可以将结构化数据挖掘的算法应用到概念格h 4 4 5 4 吼4 7 8 1 领域当中，拓展应用 范围。 1 2 国内外研究现状 自从社会进入信息的高速发展的时代以来，尤其是2 0 世纪9 0 年代提 出数据挖掘概念以后，社会对少量数据的挖掘能力和对历史数据的学习能 力的要求也越来越高。到9 0 年代末期，在关联规则阳1 钆1 1 1 和频繁模式 n 5 ，1 6 j 7 1 8 1 的研究领域，学术界开始拓展新的方向，而不仅仅局限于简单的 关系数据m j 7 j 8 1 和序列数据n9 2 啪1 2 2 ，列的挖掘，如购物篮交易数据等。他们 8 扬州大学硕士论文 希望未来有能力处理更贴近现实世界的数据模型。结构数据是能够精确地 刻画物质世界内部存在的各种联系。因此，结构化数据挖掘问题也随之而 来。结构化是良好地、简便地表达物质世界的一种载体，它即可以较清晰 的描述对象性，又具有一定的通用性，树型数据就是一种典型的结构化数 据。 图1 1 与图1 2 表示某r n a 分子结构图和将转换成树结构的示意图。 3 一 k c 舟、广 “譬 户，、 b 一 o 图1 1r n a 结构图 图1 2 转换过程图 为了顺应挖掘对象复杂化的要求，树结构的频繁模式挖掘的研究随之 一 一 c g 一 一 c g 一 _ g e 一 一c 一 一0 c 矿l 声 l r 郭鑫：频繁子树挖掘及其相关技术的研究 9 被提出，这已经成为最近几年数据挖掘领域的一个热点，这方面的成果很 多，主要有： 1 9 9 8 年，k w a n g 4 3 等人在假设“兄弟 节点没有相同标号的前提下， 提出了在有根无序树集合中挖掘频繁的算法。任意兄弟节点之间不具有具 有相同标号，因此算法采用了路径“交 操作的方法，可以入座于生成候 选子树集。 2 0 0 1 年，f l u c c i o 心钉等人提出了有根树匹配算法，并给出了准线性时 间复杂度o ( mv 。ll o gv 。) ，其中m 表示树集中最大树包含的节点数量，lv 。1 表示树集中节点的数量。随后在2 0 0 4 年，他们6 1 又提出了在无序树标号 树集中挖掘“自下至上”子树的算法。 2 0 0 2 年，m j z a k i 抽3 提出了在有序标号树集中挖掘嵌入式的算法，分 别采用了深度和广度遍历搜索的方法，并提出了有效的字符串编码帮助算 法有效遍历。其中，深度优先挖掘算法t r e e m i n e r 具有很高的性能，也当 时最优的嵌入式挖掘算法。 2 0 0 2 年，a t e r m ie r 1 等人提出了在x m l 数据中挖掘频繁嵌入式子树 的算法t r e e f i n d e r ，其中x m l 数据就可以看作为有根无序树集合。 f r e e f i n d e r 不能保证结果的完整性，在数据处理过程中采用非精确性匹配 的方法。 2 0 0 2 年，d s h a s h a 乜8 1 等人也提出了一个近似挖搜索查询算法 a t r e e g r e p ，并定义了近似最近邻搜索问题。算法利用基于近似包含的 距离作为树匹配的标准。当距离设为o 时，a t r e e g r e p 就是精确匹配的查 询算法。2 0 0 4 年，他们乜们又提出了在有根无序树挖掘“表兄弟对 ，这是 一种新的深度，并提出了新应用环境下对“表兄弟对模式的要求。 2 0 0 2 年，t a s i a 们等人提出了在有序标号树中挖掘导出式的算法 1 0扬州大学硕士论文 f r e q t 。算法采用了最右路径扩展的方法，建立枚举树，并深度优先地逐 层挖掘。f r e q t 算法时间复杂度的上界是o ( mv 。lf ) ，其中f 是频繁导出子 树的数量，而m 和lv 。1 分别表示最大树包含的节点数量，以及树集中节点 的数量。2 0 0 3 年他们在此算法的基础上，扩展算法思想，解决无序标号 树集中频繁导出子树挖掘的问题，提出了同宗同源的u n o t 算法。 2 0 0 3 年，s n i j s s e n n 2 1 等人扩展了f r e q t 算法思想，提出了在无序标 号树集中挖掘频繁导出式的算法u f r e q t 。与u n o t 算法相似，该算法利用 无序树的规范化表达，在枚举频繁时更方便直接，并保证不丢失，不重复。 2 0 0 4 年又提出了g a s t o n 口3 3 算法，在自由树集合中挖掘频繁的导出子树。 g a s t o n 算法吸收了h y b r i d t r e e m i n e r 算法中的混合方法，并将其成功的转 变为深度优先遍历。 2 0 0 3 年，y x i a o 口引等人提出了在有根无序树集中挖掘最大频繁的 p a t h j o i n 算法，它类似于k w a n g 乜4 1 等人提出的算法，即利用路径“交” 操作生成候选集。因此，p a t h j o i n 算法也必须满足兄弟节点无相同标号的 假设。p a t h j o i n 算法的特点就是在预处理过程中，找出子树集中所有存在 的路径，存放在f s t f o r e s t 数据结构中，并在随后的递归过程中，利用 路径“交操作等生成候选项。 2 0 0 3 年，y c h i 钉等人提出了在自由树集中挖掘频繁导出式的算法 f r e e t r e e m i n e r ，算法采用了宽度遍历的思想，通过“交”操作生成候选 项。f r e e t r e e m i n e r 可分为2 部分，候选项生成阶段和支持度计数阶段。 2 0 0 4 明年，他们又提出了有根无序树和自由树集合中挖掘频繁导出式的算 法h y b r i d t r e e m i n e r 。算法采用了混合式的搜索遍历方法，并同时使用“交 和“扩展”两种操作，保证每个候选至少被遍历到一次，该算法提出了新 树规范化表达，即宽度优先规范表达，它是按层搜索遍历的。2 0 0 5 口7 3 明年 郭鑫：频繁子树挖掘及其相关技术的研究 11 他们又提出挖掘闭合频繁子树和最大频繁频繁的算法c m t r e e m i n e r 。闭合 频繁子树与频繁子树的区别在于闭合频繁子树去掉了那些支持度相等，且 被闭合频繁子树所包含的那些频繁子树。挖掘闭合频繁子树可以减少结果 的数量，消除冗余，并可以通过还原的方法恢复频繁子树集合，因此它不 会丢失任何翻译片。而最大频繁子树可以进一步减少结果集，但无法还原 其他频繁子树。 2 0 0 4 年，u r u c k e r t 3 9 3 等人也提出了一个f r e e t r e e m i n e r 算法，它与 y c h i 等人提出的算法一样，采用了宽度遍历的思想，并利用“交 操 作生成候选项，他们之间的最大区别在于前者是在图集中寻找频繁自由 树。 2 0 0 4 年，朱永泰等人提出了e s p m h 们算法，利用序列算法挖掘频繁子 树。该算法提出了投影数据库的概念，在投影数据库的基础上挖掘，算法 效率有所提高。 2 0 0 5 年，m j z a k i 4 1 1 在t r e e m i n e r 算法的基础上进行了改进，使算法 能够很好地支持无序树的挖掘。 2 0 0 6 年，赵传申等人在e s p m 算法的基础上提出了f t p b h 2 1 算法，都是 利用序列挖掘算法来提高算法效率。两个算法的最大优点在于将树挖掘转 化为序列挖掘，从而利用已有的序列挖掘算法来解决树挖掘中的问题。 2 0 0 7 年，m j z a k i 4 3 1 提出了x p r o j 算法，该算法将x m l 数据看作为有 根有序树，在树结构的基础上提出了一个结构化的方法对x m l 数据进行聚 类。 2 0 0 8 年，v i n e e tc h a o j i 【4 9 3 提出了0 r i g a m i 算法，该算法在树挖掘算 法的基础上提出挖掘有代表性的子图模式算法，该算法较以往图挖掘算法 有较好的运行效率。 1 2 扬州大学硕士论文 1 3 本文的主要工作 ( 1 )有序树挖掘研究 研究有序树的挖掘技术。基于深度优先和最右扩展生成候选子树，并 利用哈希表和提出的子树向量等数据结构建立一套有序树挖掘体系结构， 在挖掘过程中能够减少树同构的判别时间，并且只需要进行一次数据库的 扫描操作，能够有效地提高了算法的运行效率，并结合树的结构化特性， 提出剪枝阈值概念进一步减少了算法的运行时间。 ( 2 )无序树挖掘研究 研究无序树挖掘技术。采取对无序树先进行标准化生成有序树，然后 利用现有的有序树挖掘算法来挖掘无序树的思路，对深度优先和宽度优先 进行标准化进行深入的研究，结合无序树和有序树的结构化的特点来对无 序树相关算法进行研究。 ( 3 )树聚类与分类研究 研究树聚类与分类算法，提出最小闭树集挖掘算法。可以将标号树看 作为数据点，频繁子树作为数据点的特征，来进行聚类与分类分析。例如 从一个网站得到该网站的w e b 日志，这样利用日志来挖掘频繁子树可以将 不同类型的用户区分开来。 1 4 论文的内容组织 本文主要研究工作是频繁子树挖掘及相关技术的应用研究，论文共分 为六章，具体组织结构如下： 第一章绪论简要介绍了本文研究的背景、意义、研究现状，并对主要 的研究工作做了一个大概介绍。 郭鑫：频繁子树挖掘及其相关技术的研究 1 3 第二章分析和介绍了目前的挖掘频繁子树的方法。首先介绍频繁子树 基本概念与子树的分类，以及子树同构知识。然后介绍了几种不同的频繁 子树挖掘算法，以及序列模式挖掘算法，最后对树的聚类与分类相关知识 与算法进行了介绍。 第三章提出了子树向量和剪枝阈值两个概念，并充分利用子树向量的 特点，结合哈希表结构，提出了一种基于子树向量的快速导出子树挖掘算 法i t m s v 。算法基于子树向量和哈希表构建一个多层的数据结构，在挖 掘过程中能够减少树同构的判别时间，并且只需要进行一次数据库的扫描 操作，减少了扫描次数，能有效提高算法的运行效率。实验表明，此算法 有效可行且同其它同类算法相比具有较高的运行效率。 第四章提出了一种可以在大型树数据库中高效挖掘无序树的算法 - i i t m i n e r ，由于所挖掘的树具有无序的特性，因此为了避免挖掘出相同 子树的情况，本文提出了一种高效的无序树的标准化方法，将无序树转化 为标准化子树，再利用本文提出的快速有序树挖掘算法得到所有的标准化 子树。实验表明，此算法有效可行且同其它同类算法相比具有较高的运行 效率。 第五章在有序树挖掘算法基础上，提出了一种最小闭树特征集挖掘算 法一一e a s t c l o s e d t r e e m i n e ，并在提出树聚类算法_ t r e e c l u s t e r 与分 类算法_ t r e e c l a s s i f i c a t i o n ，有效地解决了在实际应用中因数据量大 而无法聚类与分类的问题。提出以最小闭树特征集作为候选聚类与分类特 征，并采用动态阈值按相似度聚类方法，使得树聚类快速而精确，提出树 分类规则等级概念，并应用于树分类方法中，能迅速预测未知的树结构。 实验结果表明，在树结点数较多或数据量大时，方法有效可行且较同类其 它方法相比效率有显著提高。 1 4扬州大学硕士论文 第六章结束语，总结了本文的主要内容，并给出了进一步的研究工作 和展望。 郭鑫：频繁子树挖掘及其相关技术的研究 1 5 第二章频繁子树挖掘基础 随着科学技术的发展、信息技术的进步，人们进入了一个全新的信息 时代。计算机网络和存储技术的迅猛发展，使数据的传播和积累速度在各 个领域内不断提高。与此同时，众多领域内各自的数据库的规模日益扩大， 信息量也随之急剧增加，人们意识到隐藏在这些数据之后的更深层次、更 重要的信息能够描述数据的整体特征，可以预测发展趋势，这些信息在决 策生成的过程中具有重要的参考价值。面对海量的数据库和大量繁杂的信 息，如何才能从中提取有价值的知识，进一步提高信息的利用率，由此引 发了一个新的研究方向：数据挖掘。数据挖掘作为一个新兴的多学科交叉 应用领域，正在各行各业的决策支持活动扮演着越来越重要的角色。 频繁模式挖掘作为数据挖掘研究的重要内容之一，被应用于很多领 域，如购物篮分析、消费者行为学习、分类、聚类等。在过去的1 0 年中， 基于事务数据和序列数据陆0 5 1 5 2 1 的频繁模式挖掘已深入研究。而最近的新 兴应用，比如生物信息学、数字图书馆、电子商务等提出了在复杂的结构 化数据中挖掘频繁模式的要求。挖掘频繁子树成了又一个重要的研究课 题。 2 1 频繁子树概念与理论 2 1 1 树与子树概念 结构化数据通常可以表示为树型结构。在计算机科学领域中，相比于 序列数据无结构化特性拍3 j 引，由于树型结构具有清晰简洁的表达能力，因 1 6扬州大学硕士论文 此它己经成为刻画半结构化数据的主要载体。树的类型有多种，如无根无 序树( 或称为自由树) 、有根无序树、有根有序树等，不同类型的树具有不 同的数据表达能力和范畴。树结构是图结构的特化，因此可以利用图的性 质定义各种类型的树。自由树是保持连通的无向无环图。有根无序树是有 向无环图，并且满足以下条件：图中存在1 个节点，它没有出边，该节点 被称为“根；除此以外的节点仅有一条出边；从“根 到其他节点仅有1 条路径。有根有序树是有根无序树的特例，它要求树中所有的兄弟节点之 间具备预先定义的序。在本文中涉及到的树结构类型，仅限于有根有序树 的范畴。 下面将给出有关树的一些基本定义。 定义2 1 树的大小给定1 棵树丁( v 。) ，树丁中的数量称为树的大小， 记为。 定义2 2 树高给定1 棵树丁( v 。) ，其中v 。是根。节点1 ，的深度定义为 从v 。到v 的路径长度。树中的所有节点的深度的最大值，即是树高。 定义2 3 有序标号树一棵有序标号树丁= ( y ，e ) 是一个具有标号和 根结点的有向无环图，其中y 表示树中的结点集合，e = ( x ，少) ix ，y y ) 表示 树中的边集合，用三= ，厶) 表示一个标号集，结点矿与三存在一个对 应关系，：y 专三，t 称为结点标号。有序是指对于树中每个结点，其所有 子结点按照从左到右的顺序形成兄弟关系。图2 1 为有序树结构图。 图2 1 有序树 郭鑫：频繁子树挖掘及其相关技术的研究 1 7 定义2 4 无序标号树一棵无序标号树丁= ( 矿，e ) 是一个具有标号和 根结点的有向无环图，其中y 表示树中的结点集合，e = ( x ，y ) ix ，y y 表示 树中的边集合，用三= f 0 ，厶，厶 表示一个标号集，结点y 与三存在一个对 应关系，：y 专三，t 称为结点标号。无序是指对于树中每个结点，其所有 子结点不存在左右顺序关系。无序树表示如图2 所示，图中四棵树都是相 同的。图2 2 中四棵树为无序树，都表示同一棵树结构。 图2 2 无序树 定义2 5树结点的关系给定一根结点是的树r ，考虑任意从 开始的路径：如果u 在y 的前面，那么u 就是y 的祖先，y 是u 的子孙， 如果u ，y 之间只有一条边，那么u 是矿的父亲，y 是u 的孩子。这条边叫 做树枝，记做6 = ( 甜，d 。如果一些结点拥有同一个父亲，那么这些结点是兄 弟。 定义2 6 导出子树( i n d u c e ds u b t r e e ) 对于树s = ( 圪，巨) 和树 r = ( y ，e ) ，如果存在一对一的对应关系：圪寸形对任意( x ，j ，) e ，有 ( x ) ，( j ，) ) e ，z ( x ) = z ( ( x ) ，则称s 为导出子树。 定义2 7 内含子树( is o m o r p h ics u b t r e e ) 对于树s = ( k ，e ) 和树 丁= ( y ，d ，如果存在一对一的对应关系：圪专k 对任意( x ，y ) e ，有 ( x ) ，( y ) ) e ，( x ) = z ( ( x ) ，则称s 为内含子树。也称之为嵌入式子树。 导出子树与内含子树结构如图2 3 所示： 1 8扬州大学硕士论文 l 2 l 辜翻麓瑚擎l i i c 爨潮l e 是 h “甄砧6 噍s u 撒 & 图2 3 导出子树与内含子树 如图2 4 所示，( a ) 代表l 棵有序标号树，( b ) 是( a ) 的l 棵导出子树， ( c ) 则是( a ) 的l 棵嵌入式子树。根据以上定义可以得出，如果t 是t 的 导出子树，则t 必然是t 的嵌入式子树。反之则不成立。 ( b )( e ) 图2 4 示例图 定义2 8 森林森林是有序标号树的集合，表示为( 仍，丁) ，其中仍是 森林中树的编号，r 则是代表这棵树的规范化字符串编码。 2 1 2 树的类别与表示形式 频繁子树挖掘中研究的树是连通有向无环图，是图的一种特例，与传 统数据结构中定义的树不同，这里的树不一定有唯一的根结点，根据这一 性质又可以将频繁子树挖掘中研究的树分为有根树( 根树) ( r o o t e d t r e e ) 和自由树( f r e e t r e e ) 。 郭鑫：频繁子树挖掘及其相关技术的研究 1 9 根树是有唯一的根结点的有向无环图，根树又可以进一步分为有序根 树( o r d e r e dr o o t e d t r e e ) 和无序根树( u n o r d e r e dr o o t e d t r e e ) 。如果将 根树中同一层中的结点看作从左至右有序( 即结点位置不能交换) ，则称这 种根树为有序根树，否则称为无序根树。因此，有序根树中存在左兄弟、 右兄弟、最左孩子和最右孩子等概念，而无序根树中不存在，无序根树的 同构问题在有序树中并不存在。 自由树没有固定的根结点，如图2 5 所示。自由树的结构比根树复杂， 为了简化挖掘过程，可通过以下步骤将自由树分成两类：把一个自由树的 叶子结点逐个去掉，直到只剩下一个或两个结点为止。只剩下一个结点的 自由树称为中心自由树( c e n t e r e df r e e t r e e ) ，并称所剩下的结点为中心 点，如图2 5 所示；剩下两个结点的自由树称为双向自由树( b ic e n t e r e d f r e e t r e e ) ，把剩下的两个结点称为双向中心点，如图2 5 所示。 弘，彩彩 m 由r 褂 润醐国卿0 囝 b b ( 蠛心辩 标准化 图2 5 自由树及标准化过程 在频繁子树挖掘中，子树也存在不同的类型，大致可以分为以下三种。 2 0扬州大学硕士论文 ( 1 ) 自底向上子树( b o t t o m u ps u b t r e e ) ( 2 ) 内含子树 ( 3 ) 导出子树 图2 6 给出了不同类型的子树，其中( b ) 是( a ) 的自底向上子树，( c ) 是 ( a ) 的归纳子树，( d ) 是( a ) 的嵌入子树。 掂 掂 ( a ) 掀树( b ) 自底向上予瓣 ( c ) 蛭l 纳乎树( d ) 嵌入树 图2 6 不同类型子树 树的表示形式是频繁子树挖掘算法的关键所在。树的表示形式与树的 存储结构密切相关，正确的选择树的表示形式使得同构树的判断、比较及 子树的列举更为高效，对整个树挖掘算法有着深远的影响。 由于数据库中的树和算法执行过程中产生的子树的数目可能很大，使 用传统的数据结构诸如临界矩阵、邻接表等存储结构往往会造成空间的浪 费，因此，需要使用比传统数据结构更加紧凑的方法来存储以节省空间； 另外，一些树( 如自由树和无序根树) 用传统的数据结构表示形式不唯一， 这就需要定义一个规范的表示形式。 下面简要的介绍两种常见的树的存储方法。 ( 1 ) 先序字符串( p r e o r d e rs t r i n g ) 递归定义如下： 一棵只含有一个结点，的有序根树，它的先序字符串品= ，o ，其中z ，是 厂的标号；一棵结点数大于1 的有序根树丁，假设其根为，标号为z ，且，的 孩子从左至右依次是吒，屹，那么丁的先序字符串是品= ，s 什1 s m ，其中 - 分别是丁的以，l ，为根的自底向上子树的先序字符串。 郭鑫：频繁子树挖掘及其相关技术的研究 2 1 如图2 6 ( a ) ，图中树的先序字符串可以表示为s r = 么肋0 e o f o o c g 0 0 0 。 用先序字符串存储树的优点在于，能够很容易的从一棵树的先序字符串中 识别出该树的任何一棵自底向上子树。例如从图2 6 ( a ) 中s r 的结点召开始 扫描，直到扫描的结点个数与。的个数相等，这时得到的子序列( 肋o e o f 0 0 ) ， 就是以b 为根结点的自底向上子树的先序字符串。 ( 2 ) 深度标号序列对于有序根树，按照先序顺序遍历的结点构成一个 序列，序列中每个结点由其标号和深度构成，这样的序列就构成了这棵树 的深度一标号序列( d e p t h l a b e ls e q u e n c e ) 。 图2 6 ( a ) 所示的有根树结构的深度标号序列就可表示成为 s r = ( ( o ，么) ，( 1 ，b ) ，( 2 ，d l ( 2 ，e ) ，( 2 ，f l ( 1 ，c ) ，( 2 ，g ) ) ，每一个结点由深度和标号的组 合构成，前面的数字是结点的深度，后面的字母是结点的标号。 无序根树存在同构问题，即存在一棵无序根树能够对应几棵有序根树 的情况，那么，一棵无序树就能够有相应的几种表示形式，因此，需要选 择定义同构的规范表示( c a n o n i c a l