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

南京师范大学硕士学位论文频繁予静 挖掘及萁在x m l 挖掘中的威潮研究 摘要 频繁模式挖掘是数据挖掘领域中的一个重要问题，其研究范围包括事务、序列、树和 图。频繁子树挖握在生物信息学，w 西挖攮，讫食物结构分析等领域具有+ 分重要黪应用 价值，因此受到研究人员的高度重视。x m l 己经成为i n t e r n e t 上数据描述和交换的标准。 如何从x m l 数据中挖掘有价值的知识是一个具有挑战性的研究课题。本文就频繁子树挖 掘方法、最大频繁e m b e d d e d 子树挖搬、基于可变支持度约束的最大频繁i n d u c e d 与 e m b e d d e d 子树挖握、以及频繁子楗挖撼在x m l 挖掘中鲶应用等方面作了深入的研究。本 文的主要研究工作包括以下几个方面： ( 1 ) 对近些年来提出的频繁子树挖掘算法进行综述与分析。论述了各种频繁子树挖掘 算法的思想，并对典型算法的性能进行了实验分析与比较。 ( 2 ) 提出了一种高效酶最大频繁e m b e d d e d 子树挖掘算法1 m p e t r e e m i n e r ，该算 法采用带节点范覆酶先序遍历序列存德树，著采瘸伪投影技术对频繁予穿列进霉亍投影，对 投影序列中的每个节点编码。在挖掘带编码频繁子序列过程中使用剪枝技术尽早删除最终 不能通过投影编码生成最大频繁e m b e d d e d 子树的带编码频繁子序列，大大降低了搜索空 间，节省了时间与空间的代价。实验结粱表明c m p e t r e e m i n e r 具有较高的效率。 ( 3 ) 提出了快速挖撼可交支持度约寒豹溺合与凌大频繁i n d u c e d 子树算法一一 s c c m t r e e m i n e r ，采用最右扩展技术梭举候选子树，并利用最小有效扩展性质进行剪技， 在变化的支持度约束下求出所有闭合频繁子树以及最大频繁子树。实验结果表明， s c c m t r e e m i n e r 算法不仅能够有效地减少所产生子树的数量，而且在执行时间上也大大少 于使用固定支持度的同类算法。 ( 4 ) 提出了快速挖撅可交支持度约束的闭合与最大频繁e m b e d d e d 子树算法 s c c m e l h e m i n e r ，通过对频繁k 子树的每个增长点构造投影数据库，将投影数据库中的 频繁节点添加到频繁k 予树上直接得到频繁( k + 1 ) 子树，无冗余的构造了e m b e d d e d 予树的 增长空间。并利用最小有效扩展性质进行剪技，得到所有满足约束的闭合频繁予树以及最 大频繁子树。实验结果表明，其不仅执符时闻少，最关键於是，得到了蹋户惑兴趣懿模式。 ( 5 ) 提出了一种基于频繁子树模式的x m l 文档结构聚类算法川c f s 。该算法采 用基于后遐的先序序列表示x m l 文档树，挖掘x m l 文档集合中的闭合与最大频繁i n d u c e d 子树，并将其作为聚类特雒，根据频繁子树的大小赋予不同的权值，采用余弦函数定义相 议度，剩羽k - m e a n s 算法聚类x m l 文档。实验结果表嚷，g c f s 不仅戆够得到维数较小 的聚类特征空间，而且程聚类效率和精度上也高于同类算法。 ( 6 ) 提出了一种改进的x m l 文档结构聚类算法叫c f s * 。该算法通过挖掘x m l 文档集合中的最大频繁i n d u c e d 子树构造聚类特征空间，在频繁子树挖掘过程中自动生成 较好的最小支持度，无需溺户设置；优化聚类特征空阍；并采用c l o p e 算法聚类x m l 文 档，聚类过程中自动生成簇的个数。实验结果表明，g c f s * 不仅取得了较好的聚类效率， 而且其聚类精度较g c f s 高。 关键词：频繁子树挖撵；x m l 挖掘：霹变支持度约寒；最大频繁子树；x m l 频繁模式； x m l 结构聚类 南京师范大学磺学毪论文频繁予树挖掘及其在x m l 挖掘中的应溺研究 a b s t r a c t f r e q u e n tp a r e m sm i n i n gi sa l li m p o r t a n tp r o b l e mi nd 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 g t r a n s a c t i o n s ，s e q u e n c e s ，t r e e sa n dg r a p h s e s p e c i l a l l yf r e q u e n ts u b t r e em i n i n gi sw i d e l yu s e di n d o m a i n ss u c ha sb i o i n f o r m a t i c s ，w e b - m i n i n g , c h e m i c a ld a t as t r u c t u r em i n i n g ，a n ds oo n 。i th a s a t t r a c t e dt r e m e n d o u si n t e r e s ta m o n gr e s e a r c h e r s w i t hr a p i dd e v e l o p m e n to fw e bt e c h n o l o g ya n d a p p l i c a t i o n ，x m lh a sb e c o m et h es t a n d a r d sf o rd a t ar e p r e s e n t a t i o na n de x c h a n g eo v e rt h ei n t e r n e t i ti sag r e a tc h a l l e n g et o p i co fm i n i n gt h eu s e f u ik n o w l e d g ef r o ms e m i - s t r u c t u r e dx m ld a t a t h i s p a p e rs t u d i e so nf r e q u e n ts u b t r e em i n i n ga n df r e q u e n ts u b t r e em i n i n ga p p l i e di nx m lm i n i n g w i t hm a x i m a lf r e q u e n te m b e d d e ds u b t r e em i n i n g , m i n i n gm a x i m a lf r e q u e n ti n d u c e do re m b e d d e d s u b t r e e su s i n gl e n g t h - d e c r e a s i n gs u p p o r tc o n s t r a i n t , x m lf r e q u e n tp a a e mm i n i n ga n dx m l d o c u m e n t sc l u s t e r i n gb ys t r u c t u r e t h em a i nc o n t r i b u t i o n so ft h ep a p e ra r el i s t e da sf o l l o w s ( 1 ) d i s c u s st h ea c t u a l i t i e so ft h er e c e n tr e s e a r c h e so nf r e q u e n ts u b t r e em i n i n g m o r e o v e rt h e r e l a t e da l g o r i t h m su s i n gb o t hs y n t h e t i c sa n dr e a ld a t a s e t sa r ei m p l e m e n t e d , a n dt h ev i r t u ea n d d e f i c i e n c yo f t h e s ea l g o r i t h m sa r ec o m p a r e d ( 2 ) p r o p o s ean o v e la l g o r i t h mc m p e l h e m i n e rf o rd i s c o v e r i n gm a x i m a lf r e q u e n te m b e d d e d s u b t r e e sf r o mo r d e r e dl a b e l e dt r e e s 1 1 l ea t t r i b u t eo fn o d e ss c o p ei sa d d e di nt h ep r e o r d e r s e q u e n c et os t o r et r e e p s e u d o - p r o j e c t i o nt e c h n i q u ei su s e dd u r i n gp r o j e c t i o na n de a c hn o d ei s e n c o d e d m i n i n gt h ee n c o d e df r e q u e n ts u b - s e q u e n c ec a l lb ed i r e c t l yc o r r e s p o n dt oa l le m b e d d e d f r e q u e n ts u b t r e e s e v e r a lt e c h n i q u e sa r ep r o p o s e dt op r u n et h ef r e q u e n ts u b - s e q u e n c et h a td on o t c o r r e s p o n dt oc l o s e do rm a x i m a lf r e q u e n te m b e d d e ds u b t r e eu s i n gc o d ea n ds c o p ei n f o r m a t i o n e x p e r i m e n tr e s u l t ss h o wt h a tc n 口e t r e e m i n e fi se f f i c i e n ta n de f f e c t i v e 3 ) p r o p o s ea na l g o r i t h mc a l l e ds c c m t r e e m i n e r , t h a tf m d sa l lc l o s e da n dm a x i m a lf r e q u e n t i n d u c e ds u b t r e e su s i n gl e n g t h d e c r e a s i n gs u p p o r tc o n s t r a i n t s c c m t r e e m i n e ru s e sr i g h t m o s t e x p a n s i o nt e c h n i q u et os y s t e m a t i c l l ye n u m e r a t ea l lc a n d i d a t es u b t r e e s t w on e wp r u n i n gm e t h o d s a r ep r o p o s e dt oi m p r o v et h ep e r f o r m a n c eo fs c c m t r e e m i n e r d u r i n gt h em i n i n gp r o c e s ss u p p o r t d e c r e a s e sa st h el e n g t ho ft h et r e ei n c r e a s e 。e x p e r i m e n t a lr e s u l t ss h o wt h a ts c c m t r e e m i n e rn o t o n l yg e n e r a t e sm o r ec o n c i s er e s u l ts e t ，b u ta l s or u n sm u c hf a s t e r ( 4 ) p r e s e n ta l g o r i t h ms c c m e t r m i n e rw h i c hc a r lf m da l lc l o s e da n dm a x i m a lf r e q u e n t e m b e d d e ds u b t r e e su s i n gl e n g t h d e c r e a s i n gs u p p o r tc o n s t r a i n t s c c n 饪h y e e m i n e rc o m b i n e st h e r i g h t m o s tp a t he x p a n s i o ns c h e m ea n dp r o j e c t i o nt e c h n i q u et oc o n s t r u c tp a t t e r ng r o w t hs p a c e ，a n d u s e ss e v e r a lt e c h n i q u e st op r u n et h eb r a n c h e so ft h ee n u m e r a t i o nt r e e st h a td on o tc o r r e s p o n dt o c l o s e do rm a x i m a lf r e q u e n ts u b t r e e su n d e rc o n s t r a i n t e x p e r i m e n t a lr e s u l t ss h o wt h a t s c c m e t r e e m i n e ri se f f e c t i v ea n de f f i c i e n t , a n di tg e n e r a t e sm o r ec o n c i s er e s u l ts e t , w h i c hi s i r r e d u n d a n ta n di n t e r e s t i n gt ou s e r s ( 5 ) p r e s e n ta l g o r i t h mg c f sf o rc l u s t e r i n gx m ld o c u m e n ts t r u c t u r eb a s e do nf r e q u e n t s u b t r e ep a t t e r n s i tf i r s t l ym i n e sa l lm a x i m a la n dc l o s e df r e q u e n ti n d u c e ds u b t r e e sf r o mx m l d o c u m e n t s ；t h e nc h o o s e ss o m es u b t r e ep a t t e r n st of o r mt h ec l u s t e r i n gf e a t u r e s ，w e i g h t st h e s e f e a t u r e sa c c o r d i n gb yt h el e n g t ho fs u b t r e ep a t t e r n ，c o m p u t e st h es i m i l a r i t yo ft w ox m l d o c u m e n t sb yc o s i n er u c t i o n , u s e sk m e a n sa l g o r i t h mt oc l u s t e rd o c u m e n t sb yc l u s t e r i n g f e a t u r e s e x p e r i m e n tr e s u l t ss h o wt h a tg c f si s e f f e c f i v ea n de f f i c i e n t , i t sp e r f o r m a n c ei s s u p e r i o rt oo t h e rx m lc l u s t e r i n ga l g o r i t h m s ( 6 ) p r e s e n ta ni m p o v e da l g o r i t h mg c f s f o rc l u s t e r i n gx m ld o c u m e n ts t r u c t u r eb a s e do n l 王 南京师范大学磺学逝论文 频繁子树挖握及其在x m l 挖掘中的应用研究 f r e q u e n ts u b t r e ep a t t e r n s d u r i n gt h em a x i m a lf r e q u e n ts u b t r e em i n i n gp r o c e s si tc a ng e tt h eb e s t m i n i m u ms u p p o r ta u t o m a t i c a l l y ；t h e nc h o o s es o m es u b t r e e p a t t e r nt of o r mt h eo p t i m i s t i c c l u s t e r i n gf e a t u r e s ；u s e sc l o p ea l g o r i t h mt oc l u s t e rd o c u m e n t s 姆c l u s t e r i n gf e a t u r e s , w i t h o u t g i v i n gt h en u m b e ro fc l u s t e r e x p e r i m e n tr e s u l t ss h o wt h a tg c f s * i sm o r ee f f e c t i v ea n de f f i c i e n t t h e ng c f s k e y w o r c l s ：f r e q u e n ts u b t r e em i n i n g ；x m lm i n i n g ；l e n g t h - d e c r e a s i n gs u p p o r tc o n s t r a i n t ； m a x i m a lf r e q u e n ts u b t r e e ；x m lf r e q u e n tp a t t e r n ；x m lc l u s t e r i n gb ys t r u c t u r e 1 1 1 学位论文独创性声明 本人郑重声明： 1 、坚持以搿求实、创新 的科学精耩l 从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作释取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名： 笨题雯 曩期：逖：墨! ! 学位论文使用授权声明 本入完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许 论文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据 库进行检索；有权将学位论文的标题和摘要汇编出版。保密的学位 论文在解密后适用本规定。 作者签名：盔匙雯 日期：迎里：点：! i 南京师范大学硕士学位论文频繁子树挖掘及其在x m l 挖掘中的应用研究 第一章引言 1 1 研究背景及意义 近年来，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们拥有和积累 的数据越来越多。面对庞犬的数据量，人们迫切希望将这些数据转换成有用的信息和知识， 从中找出规律和模式，以便更好地利用这些数据，帮助人们进行决策和研究。传统的以数据 库为中心，进行事务处理、批处理及决策分析等各种类型的数据处理模式，己远远不能满足 用户的需求。数据挖掘( d a t am i n i n g ) 作为新一代的、智能的辅助人类从海量数据中发现 有用知识的技术正是在这种背景下产生并迅速发展起来的。数据挖掘，也称数据库中的知识 发现( 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 ) 【l j ，是指从大型数据库或数据仓库中提取人 们感兴趣的知识，这些知识是隐含的、事先未知的、潜在的有用信息，提取的知识一般可表 示为概念( c o n c e p t s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式【列。用数据库管理系 统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合促 成了数据挖掘技术的产生。数据挖掘是一门交叉性学科，涉及到机器学习、神经网络、模式 识别、归纳推理、统计学、智能数据库、知识获取、数据可视化、高性能计算、专家系统等 多个领域。 频繁模式挖掘是数据挖掘领域的一个基本问题。1 9 9 4 年，为了寻找大量商务事务库中的 项集之间的有趣联系，a g r a w a l 开创性地提出了关联规则挖掘问题，并发表了著名的a p r i o r i 算法p 训，用频繁项集产生关联规则，发现顾客购买的不同商品之间的联系，分析顾客的购 物习惯，帮助零售商制定营销策略。1 9 9 5 年，为描述同一顾客在多次购物所购物品之间可能 存在的某种关联关系，a g r a w a l 又发表了序列模式挖掘算法i5 | 。此后，频繁项集与频繁序列 挖掘算法被广泛应用于许多其他数据挖掘任务中，如相关分析，周期分析，查询，分类，索 引等等。由于问题本身的基础性和内在复杂性，挖掘方法成为许多研究者关注的课题。 随着i n t e m e t e t 益普及和w e b 挖掘，半结构化文档挖掘等需求，频繁模式的研究对象，也 自然的从最初的事务项集和序列，逐渐扩展到树和图等结构型数据。如何发现挖掘频繁子树 ( 图) 的高效算法，日益成为一个具有重要理论和实用价值的研究课题。其重要性可反映在 计算机网络、w e b 挖掘、生物信息学、生物化学、多维数据挖掘、电子图书馆、x m l 文档 挖掘等应用领域。在这些应用中有很多方面都涉及了频繁子树挖掘算法。例如，当一个用户 面对一个新的数据集，他通常并不知道这个数据集的特点。提供这个数据集的子结构可以帮 助用户来理解这个数据集，为用户提供一个如何使用更为精确的查询来了解此数据集的方 法。在网络多播路由中，为所有的群组独立地存储路由表时，并发多播群组的每个路由器需 要大量的空间。一个可能的策略就是将此多播群组划分成多个小组，并为每个小组建立路由 表。这里，不同多播群组的多播路由树中的频繁子树为如何形成一个分组提供依据。在生物 化学中，具有树形结构的分子片断在活性分子中是频繁的，但在惰性分子中却是非频繁的。 这些频繁出现的片断为化学家们对q s a r s ( q u a n t i t a t i v es t r u c t u r e a c t i n gr e l a t i o n s h i p ) 提供了 更深入的了解。在分类和聚类算法中的数据点可以标识成树，通过将频繁子树看成是数据点 的特征，标准的分类和聚类算法是同样可以应用的。从一个网站的网页日志文件我们可以获 得用户的访问模式( 访问树) ，这样我们就可以使用这些访问树来划分不同的用户类型 ( c a s u a l 与s e d o u s 用户，正常访问者和网页爬虫等) 。标识树数据库的频繁子结构可以为我 们提供信息如何有效地为数据库建立索引结构，如何为不同的查询类别设计有效的访问方 南京师范大学硕士学位论文频繁子树挖掘及其在x m l 挖掘中的应用研究 法。譬如，从一个x m l 文档的历史查询日志中挖掘频繁的查询模式。所挖掘的频繁查询可 以存储起来，这样可以为将来有效的查询应答提供索引。 w e b 技术自上个世纪9 0 年代出现以来，极大地改变了人们发布、获取和使用信息的方式， 尤其是近年来，以x m l i 6 l 为基础的新一代w e b 环境的出现，很好地兼容了原有的w e b 应用， 而且可以更好地实现w e b 中的信息共享与交换。其基于文本的方便性和半结构化特征使得 x m l 在信息管理、电子商务、个性化出版、移动通信、网络教育、电子文档交换等诸多领 域得到了广泛应用，而且其应用范围还在不断扩展。x m l 己经开始成为i n t e m e t 上数据描述 和交换的事实标准。对于这些越来越多的采用x m l 文档格式进行存储、交换和表现的数据， 除了已有的信息抽取、w e b 搜索等信息处理方法之外，人们越来越需要获取更进一步的、深 层次的知识，这就需要对其进行数据挖掘。但是，正由于x m l 是一类半结构化的文本数据， 其具有文本文档和半结构化数据的诸多弱点，如解析文档时必须采用顺序读取的方式，访问 效率不高；对信息的组织不规则，或者其结构可能经常变化，甚至可能不完整等。而传统的 数据挖掘技术主要面对的是以结构化数据为主的关系数据库、事务数据库和数据仓库，这样， 我们不能直接将传统的基于关系数据库的挖掘方法，如a p d o d ，应用到半结构化数据挖掘中。 因此，开发出有效的针对x m l 的数据挖掘方法成为数据挖掘领域和x m l 技术领域的一项重 要课题。 目前，国外频繁子树挖掘及x m l 挖掘已经取得了部分研究成果，提出了若干研究算法， 而国内起步较晚。本文根据频繁子树挖掘技术研究的潜在应用背景，结合国家自然科学基金 项目“面向g m l 的空间聚类与异常监测方法研究”( 编号：4 0 7 7 1 1 6 3 ) 及江苏省自然科学 基金项目“基于分布式数据挖掘的分布式入侵检测技术研究( 编号：b k 2 0 0 5 1 3 5 ) 任务开 展研究工作，对频繁子树挖掘算法及其在x m l 挖掘中的应用作较深入的探讨。 1 2 研究现状 数据挖掘是计算机技术，数据库技术，决策管理技术，人工智能技术等综合发展的结果。 数据挖掘起源于从数据库中发现知识( 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 ，k d d ) ，它首次出 现在1 9 8 9 年8 月举行的第十一届国际联合人工智能学术议上。到现在为止，对在关系数据库 或事务数据库中进行数据挖掘的研究已经取得了长足的进步，并且国际上一些著名软件公司 的商用数据挖掘系统己投放市场( 如d b m i n e r t 7 j ) 。如i b md b 2 产品家族的i n t e l l i g e n t m i n e ， 美国b u s i n e s s o b j e c t s 公司b u s i n e s s m i n e r ，m i c r o s o f t 的a n a l y s i ss e r v i c e s2 0 0 0 等。 频繁模式的挖掘作为数据挖掘研究的核心任务之一，被应用于很多领域，如购物篮分析、 消费者行为学习、分类、聚类等。在过去的l o 年中，基于事务数据1 8 - 2 5 1 和序列数据口3 1 的频 繁模式挖掘己被广泛研究。而最近的新兴应用，比如生物信息学、w e b 挖掘、电子商务等提 出了在复杂的结构化数据中挖掘频繁模式的要求。挖掘频繁的子结构成了数据挖掘中的热点 问题。频繁结构挖掘包括频繁子树挖掘1 3 4 - 7 5 1 与频繁子图挖掘【7 6 4 0 i 。在国外，美国伊利诺伊大 学、美国加州大学洛杉矶分校、美国北卡罗来纳大学、澳大利贬南澳大利亚大学、德国慕尼 黑大学、德国弗赖堡大学、德国马格德堡大学、日本九州大学、希腊亚里斯多德大学等许多 大学和研究所都有结构挖掘研究成果的报道。他们的研究目的主要是提高结构挖掘算法的执 行效率，减少用户需要管理和使用的频繁子树( 图) 的数量，使得结构挖掘算法能够应用于 大型结构数据库。与国外相比，国内对数据挖掘和结构挖掘的研究都要稍晚，还没有形成整 体力量。国内频繁子树挖掘的研究还处于起步和探索阶段。 到目前为止，频繁子树挖掘 3 4 - 7 5 i 已取得一些成果，研究工作主要包括： ( 1 ) 频繁b o r o m - u p 子树挖掘算法 2 0 0 1 年，f l u c c i o 等人【37 i 提出了有根树匹配算法，并给出了准线性时间复杂度 2 南京师范大学硕士学位论文 频繁子树挖掘及其在x m l 挖掘中的应用研究 o ( m v d i o g i v d i ) ，其中m 表示有序标号树集中最大树包含的节点数量，l v d l 表示树集中节点 的数量。随后在2 0 0 4 年，他们【3 s 】又提出了在无序标号树集中挖掘b o t t o m u p 子树的算法。 ( 2 ) 频繁i n d u c e d 子树挖掘算法 2 0 0 2 年，t a s i a 等人【3 9 j 提出了在有宁标号树集中挖掘频繁i n d u c e d 子树的算法f r e q t 。 算法采用了最右路径扩展的方法建立枚举树，并深度优先地逐层挖掘。f r e q t 算法时间复 杂度的上界是o ( m l v d i f ) ，其中f 是频繁i n d u c e d 子树的数量，而m 和i v d l 分别表示最大树包 含的节点数量，以及树集中节点的数量。 2 0 0 5 年，s h i d o 等人1 4 0 提出了a m i o t 算法，利用连接技术挖掘了有序标号树集中的 频繁i n d u c e d 子树，与f r e q t 相比，减少了生成的候选子树数量，从而高效可行。 2 0 0 3 年，t a s i a 等人j 在f r e q t 的基础上，扩展算法思想，解决无序标号树集中频繁 i n d u c e d 子树挖掘的问题，提出了同宗同源的u n o t 算法。 2 0 0 3 年，s n i j s s e n 等人1 4 2 l 扩展了f r e q t 算法思想，提出了在无序标号树集中挖掘频 繁i n d u c e d 子树的算法u f r e q t 。与u n o t 算法相似，u f r e q t 利用无序树的正则表示( c a n o n i c a l r e p r e s e n t a t i o n s ) ，在枚举频繁子树时更方便直接，并保证不丢失、不重复。 2 0 0 3 年，y c h i 等人 4 3 j 提出了在自由树( 无根无序树或无向无环图) 集中挖掘频繁 i n d u c e d 子树的算法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 年，他们l 4 4 j 又提出了在无序树和自由树集合中挖掘频繁i n d u c e d 子树的算法 h y b r i d t r e e m i n e r 。算法采用了混合式的搜索遍历方法，并同时使用“交”和“扩展”两种 操作，保证每个候选子树至少被遍历1 次。h y b r i d t r e e m i n e r 提出了新的树的正则表示方法， 即宽度优先正则表示，它按层搜索遍历树。 2 0 0 4 年，u r u c k e a 等人【4 习也提出了一个f r e e t r e e m i n e r 算法，它与y c h i 等人【4 2 l 提出的 f r e e t r e e m i n e r 算法一样，采用了宽度遍历的思想，并利用“交”操作生成侯选项。他们之 间的最大区别在于u r u c k e r t 等人【4 5 】提出的f r e e t r e e m i n e r 算法是在图集中寻找频繁i n d u c e d 自由树。 2 0 0 4 年，s n i j s s e n 等人 4 6 1 又提出了g a s t o n 算法，在自由树集合中挖掘频繁i n d u c e d 子 树。g a s o m 算法吸收了h y b r i d t r e e m i n e r 算法中的混合遍历方法，并将其成功的转变为深度 优先遍历。 ( 3 ) 频繁e m b e d d e d 子树挖掘算法 2 0 0 2 年，m j z a k i 在文献 4 7 1 中给出了两种算法t r e e m i n e r 和p a t t e m m a t c h e r ，挖掘有序 标号树集合中的频繁e m b e d d e d 子树。p a t t e m m a t c h e r 是类a p r i o r i 的宽度优先挖掘算法。算 法将树表示为带有回溯信息的先序序列，引入等价类表示一组具有相同序列前缀的树，并使 用h a s h 表示方法将其组织成一种高效的存储结构。算法通过等价类连接操作生成候选子树， 然后通过子串匹配运算在h a s h 结构上计算支持度。t r e e m i n e r 仍然使用先序表示方法，并保 留了等价类的概念，然而采用深度优先的挖掘策略。算法利用一种树的倒排表示方法， s c o p e 1 i s t ，来重新组织数据库，通过对s c o p e 1 i s t 求交来进行有效的支持度计算。t r e e m i n e r 的效率比p a t t e r n m a t c h e r 高出大约4 2 0 倍。然而，t r e e m i n e r 仍采用候选生成测试策略，在 递归过程中，s c o p e 1 i s t 的求交运算时间复杂度仍显得较高。 2 0 0 3 年，p a n 等人【4 9 】提出了c h o p p e r 算法挖掘有序标号树集合中的频繁e m b e d d e d 子树。 其扩展序列模式挖掘算法p r e f i x s p a n 2 8 】，使用模式增长方法来解决同样的问题，效率有一 定提高。 2 0 0 4 年，w a n g 等人【5 0 j 在c h o p p e r 算法基础上提出x s p a n n e r 算法挖掘有序标号树集合 中的频繁e m b e d d e d 子树。严格地来讲，这两种算法均是序列意义上的模式增长。即先将树 看做是一个用先序表示的序列，然后在序列上应用模式增长方法。然而由于有许多不同拓扑 3 南京师范大学硕士学位论文频繁子树挖掘及其在x m l 挖掘中的应用研究 结构的树可能表示相同的序列，所以算法依然需要使用字串匹配操作完成支持度计算。 2 0 0 4 年，z h u 等人 5 1 】提出e s p m 算法挖掘有序标号树集合中的频繁e m b e d d e d 子树。 该算法提前对树同构进行判断，尽早删去不频繁树结构的频繁序列。减少了c h o p p e r 算法创 建准频繁结构索引的代价。 2 0 0 5 年，m a 等人【5 2 】提出了t g 算法挖掘有序标号树集合中的频繁e m b e d d e d 子树。利 用模式增长的方法直接枚举得到频繁子树。 2 0 0 5 年，h t a n 等人郾j 提出了m b 3 m i n e r 算法挖掘有序标号树集中的频繁e m b e d d e d 子树。采用不同的数据结构存储了有序树。 2 0 0 6 年，z h a o 等人t 5 4 l 提出了f t p b 算法挖掘有序标号树集中的频繁e m b e d d e d 子树。 通过投影分支的概念，减少搜索空间，加快算法运行效率。 2 0 0 6 年，c h e n 等人【5 5 】提出了p e t r e e m i n e r 算法挖掘有序标号树集中的频繁e m b e d d e d 子树。利用投影与编码技术直接生成频繁子树。 2 0 0 6 年，s h i r i s ht a t i k o n d a 等人p 6 j 提出了t r i p s 算法挖掘有序标号树集中的频繁 e m b e d d e d 子树。其在树的存储结构上作了优化，与同类算法相比，其对内存的占用量较低。 2 0 0 6 年，z o u 等人p7 j 提出了p r e f i x t m e e s p a n 算法挖掘有序标号树集中的频繁e m b e d d e d 子树。 2 0 0 5 年，m j z a k i l 5 8 j 提出了挖掘无序标号树集合中的频繁e m b e d d e d 子树算法s l e u t h 。 ( 4 ) 闭合与最大频繁子树挖掘算法 2 0 0 3 年，y x i a o 等人【”j 提出了在无序标号树集中挖掘最大频繁i n d u c e d 子树的p a t h j o i n 算法，它类似于k w a n g 等人i f , 0 1 提出的算法，即利用路径“交”操作生成侯选集。因此，p a t h j o i n 算法也必须满足兄弟节点无相同标号的假设。p a t h j o i n 的特点就是在预处理过程中，找出树 集中所有存在的路径，存放在f s t o f o r e s t 数据结构中，并在随后的递归过程中，利用路径“交” 操作生成侯选项。 2 0 0 5 年，y c h i 等人1 6 1 - 6 2 提出了挖掘闭合频繁i n d u c e d 子树和最大频繁i n d u c e d 子树的算法 c m t r e e m i n e r 。闭合频繁子树与频繁子树的区别在于闭合频繁子树集去掉了那些支持度相 等，且被闭合频繁子树所包含的那些频繁子树。挖掘闭合频繁子树可以减少结果的数量，消 除冗余，并可以通过还原的方法，恢复频繁子树集合，因此它不会丢失任何信息。而最大频 繁子树可以进一步减小结果集，但无法还原其他频繁子树。 ( 5 ) 基于约束的频繁子树挖掘算法 基于约束的频繁子树挖掘的主要目的是发现更有趣、更实用、更特别的子树，这些约束 可以反映用户的兴趣模式。 2 0 0 5 年，j d k n i j ：6 3 l 提出了挖掘满足用户给定选择约束的闭合频繁i n d u c e d 子树挖掘算 法s c t r e e m i n e r 。该选择约束可以是结构或树标号上的约束。 2 0 0 5 年，他们m 】又提出了满足单调约束的频繁子树挖掘算法。 2 0 0 5 年，a t s u y o s h in a k a m u r a 等人 6 5 1 在t r e e m i n e r 算法的基础上提出了 c o n s t r a i n e d t r e e m i n e r 算法，挖掘包含某些固定节点的频繁e m b e d d e d 子树。 2 0 0 6 年，z o u i s s l 等人提出了挖掘满足给定子树约束的频繁i n d u c e d 子树的算法s c f s 。 2 0 0 6 年，h t a n 等人提出了i m b 3 m i n e r 算法【6 7 】与r a z o r 算法【6 8 】挖掘满足层次约束的频 繁e m b e d d e d 子树。 ( 6 ) 其他频繁子树挖掘算法 1 9 9 8 年，k w a n g 等人唧l 在假设“兄弟”节点没有相同标号的前提下，提出了在无序标 号树集中挖掘频繁i n d u c e d 子树的算法。由于任意兄弟节点之间不具有相同标号，因此算法 采用了路径“交”操作的方法，可以方便地生成侯选子树集。 2 0 0 2 年，a t e r m i e r 等人【6 9 】提出了在x m l 数据中挖掘频繁e m b e d d e d 子树的算法 4 南京师范大学硕士学泣论文频繁予树挖掘及其在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 年，d 。s h a s h a 等入扩嘲也提出了一个近似搜索查询算法a t r e e g r e p ，并定义了近似最 近邻搜索问题。算法利用基于近似包含的距离作为树匹配的标准。当距离设为0 时， a t r e e g e r p 就是精确匹配的衡询算法。 2 0 0 4 年，他们1 7 l j 又提出了在无序树集中挖掘“表冠弟对”，这是一种新的尝试，并提出 了薪应用环境下对“表兄弟对”模式熬要求。 ( 7 ) 频繁子树挖掘在x m l 挖掘中的应用 根据x m l 文档的特点，当前x m l 挖掘的研究可以分为结构挖掘和内容挖掘两类。x m l 的内容指的是文档中每个开始标记和结束标记之间的文本部分，对其内容的挖掘其实也就是 对标记值戆挖掘。基前，x m l 酶内容挖掇主要有三种途径：第一种是遗过一些专f l 为x m l 数据或半结构纯数据开发的套询语言，如x m l - q l 、x m l - g l 、x q u e r y 等，利孺其查询功 能，嵌入到其他应用程序中，从而获得数据集进行挖掘。这种方法的优点是能够将x m l 技 术与数据挖掘技术紧密结舍越来，但不足也是显而易见的，比如修改困难、查询开销巨大等。 第二种是将x m l 文档的数据