（计算机软件与理论专业论文）xml查询模式挖掘的研究.pdf

摘要 摘要 数据挖掘作为一个新兴的技术是支持企业决策、处理大量信息的关键 步骤之一。i n t e m e t 的飞速发展，出现了大量的x m l 数据，高效地处理 x m l 数据成为数据挖掘研究重要方向之一。本文在对国内外研究现状进行 综合分析的基础上，对x m l 频繁查询模式的挖掘问题进行了研究。 本文主要研究了挖掘x m l 频繁查询模式涉及的技术、方法，所做的 主要工作如下： 首先，讨论挖掘x m l 查询模式相：是的x m l 、x q u e r y 、关联规则和聚 类技术；分析和比较以关联规则为基础，挖掘x m l 频繁查询模式的各种 算法的特点，总结它们的优缺点。 其次，对目前性能最好f a s t x m i n e r 算法深入的研究，并实现了该算法。 然后，提出一种基于网格和密度的聚类算法。将x m l 数据有效的划 分，根据密度的闽值和d t d 引导寻找子空间，利用图的连通算法将单元 格有效的连通，高密度的连通空间就是频繁查询模式。算法的优点是避免 f a s t x m i n e r 算法对候选有根子树的树的包含测试需要的时间开销。 最后，提出在线挖掘频繁查询模式算法的框架。针对x m l 流查询是 连续的，查询处理所使用的内存远远小于数据流本身，查询处理过程中数 据仅仅能够被扫描一遍等特点，挖掘频繁出现的共享路径并将其综合到一 个结构中，从而避免重复操作。该算法能确保高速缓存在线挖掘的高效性， 同时确定当前“热点”的查询模式，并且能捕捉查询流的更新趋势和模式 达到提高查询效率的目的。 关键词数据挖掘；x m l 查询；关联规则；聚类；频繁查询模式 燕山大学二l 学硕士学位论文 a b s t r a c t d a t am i n i n gi san e w t e c h n i q u ew h i c hc a nb eu s e df o rd e c i s i o n - m a k i n g ， a n di ti sa ni m p o r t a n tm e t h o do f d e a i i n gw i t hm a g n a n i m o u si n f o r m a t i o n a s i n t e r a c t r a p i d l yd e v e l o p e d ，t h e r e i sag r e a t q u a n t i t y x m ld a t a o n eo f s i g n i f i c a n tr e s e a r c hd i r e c t i o n si sh a n d l ex m l d a t ae f f i c i e n t l y o nt h eb a s i so f a n a l y z i n ga n ds y n t h e s i z i n gt h ea c t u a l i t yi ni n t e r n a la n de x t e r n a l ，t h i sp a p e r r e s e a r c h e dt h e p r o b l e m so f m i n i n g i nt h ex m l q u e r y f i r s t l y ，i nt h i sp a p e rm i n i n gx m lq u e r yp a t t e r na s s i s t a n tt e c h n i q u e sw e r e d i s c u s s e d ，s u c h a s x m l ，x m lq u e r y , a s s i s t a n tr u l e ra n dc l u s t e r m i n i n g f r e q u e n tq u e r yp a t t e r n sb a s e do na s s i s t a n tr u l e rw e r ec o m p a r e da n da n a l y z e d ， t h e i rr e s p e c t i v ea d v a n t a g e sa n d d i s a d v a n t a g e sw e r ep r e s e n t e d s e c o n d l y , t h e f i n e s t a l g o r i t h m f a s t x m i n e r w a sr e s e a r c h e d d e e p l y a t p r e s e n t t h ea l g o r i t h mw a sa c h i e v e di nt h i sp a p e r t h i r d l y , ac l u s t e r i n ga l g o r i t h mb a s e do ng r i da n dd e n s ew a sg i v e n x m l d a t a p l o t e d o u t e f f i c i e n t l y , f o u n ds u b s p a c e s b a s e do nd t da n dm i n d e n s e c o n n e c t e dg r i d sb yg r a p hc o n n e c ta l g o r i t h m f r e q u e n tq u e r yp a t t e r n s w e r eh i g h - d e s e r t s s u b s p a c e s i t sa d v a n t a g e sw e r er e d u c e dt h et i m ec o s t e d t r e e c o n t a i n m e n ta l g o r i t h mi nf a s t x m i n e r f i n a l l y , t h ea l g o r i t h mf r a m e w o r k f o r m i n i n gf r e q u e n tq u e r yp a t t e r n s o n l i n ew a s p r o v i d e d i tc o u l dm i n e t h ef r e q u e n tm o d e sa n d c o m p o s et h e m t oa c o n s t r u c t i o nt oa v o i d r e p e a t i n go p e r a t e s s i n c et h e q u e r y s t r e a m sh a dt h e c h a r a c t e r i s t i c st h em e m o r yf o o t p r i n tq u e r yp r o c e s su s e dw a sf a rs m a l l e rt h a n t h ed a t as t r e a m s ；t h e nt h ed a t ac o u l db es c a n e d o n l yo n c e t oe n s u r eac a c h i n g s y s t e mr e m a i n e de f f e c t i v e ，i tw a sc r i t i c a lt od e t e r m i n et h ec u r r e n t h o t ，q u e r v p a t t e r n s ，t oc a p t u r eu p t o d a t et r e n d sa n dp a t t e r n si nt h eq u e r ys t r e a m k e y w o r d sd a t am i n i n g ；x m lq u e r y ；a s s i s t a n tr u l e r ；c l u s t e r i n g ；f r e q u e n t q u e r y p a t t e r n 第1 章绪论 1 1 研究背景 第1 章绪论 在信息急剧膨胀的今天，如何从大量数据中发现有用的知识已经成为 一个重要的问题。数据挖掘( d a t am i n i n g ，d m ) 就是一种从大型数据库或数 据仓库中提取隐藏的预测性信息的新技术，它能挖掘出数据问潜在的模式， 找出最有价值的信息，指导商业行为或辅助科学研究。简单的说，数据挖 掘是从数据库或者数据仓库中发现潜在的、有用的、未知的知识的过程。 通过数据挖掘工具预测未来的趋势及行为，支持决策和分析。在典型的决 策支持系统中，数据挖掘可自动提供未来情况的分析结果，这远远的超出 传统工具所提供的历史情况分析。由于计算机和网络应用的普及，产生了 大量的电子数据。银行、保险、制造、通讯等行业都有大量数据，从中发 现知识以提供决策支持已经成为当务之急。所以，数据挖掘的研究具有广 泛的应用背景。 数据挖掘是一个新兴的边沿学科，它涉及多学科技术的集成，包括数 据库技术、人工智能、统计学、机器学习、高性能计算、模式识别、神经 网络、数据可视化、信息检索等等，而发现的知识可以应用于决策分析、 过程控制、信息管理等多个领域。多学科的相互交融和相互促进，使得数 据挖掘这一新兴学科得以蓬勃发展，而且己经初具规模。它把人们对数据 的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。 在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工 智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人 员，投身到数据挖掘这一新兴的研究领：喊，形成新的技术热点。因此，数 据挖掘被信息产业界认为是数据库系统最重要的前沿之一，是信息产业最 有前途的交叉学科。 对数据挖掘有广义的和狭义的两种理解： 广义的理解认为数据挖掘即数据库中的知识发现( k n o w l e d g e 燕山大学工学硕士学位论文 d i s c o v e r y i nd a t a b a s e ，k d d ) ”。即从大规模的数据库中抽取非平凡的、隐 含的、未知的、有潜在使用价值的信息的过程 2 1 。一个典型的数据挖掘系 统具有的主要成分如图1 - 1 所示。 数据清 图1 - 1典型的数据挖掘系统结构 f i g u r e1 - 1a a r c h i t e c t u r eo f at y p i c a ld a t am i n i n gs y s t e m 【1 】 数据库、数据仓库或其他信息库：这是一个或一组数据库。数据仓库、 电子表格或其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据 仓库服务器负责提取相关数据。 知识库：这是领域知识。用于指导搜索或评估结果模式的兴趣度。这 种知识可能包括概念分层，用于将属性或属性值组织成不同的抽象层。用 户确信方面的知识也可以包含在内。可以根据非期望性评估模式的兴趣度， 使用这种知识。 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成， 用于特征化、关联、分类、聚类分析以及演变和偏差分析。 2 第1 章绪论 模式评估模块：通常，此成分使用兴趣度衡量，并与数据挖掘模块交 互，以便将搜索聚焦在有趣的模式上。模式评估模块可能使用兴趣度阈值 过滤发现的模式，也可以与挖掘模块集成在一起，这依赖于所用的数据挖 掘方法的实现。对于有效的数据挖掘，建议尽可能深地将模式评估推进到 数据挖掘过程之中，以便将搜索限制在有兴趣的模式上。 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户与 系统交互，指定数据挖掘查询或任务，提供信息、帮助搜索聚集，根据数 据挖掘的中间结果进行探索式数据挖掘。另外，此成分还运行用户浏览数 据库和数据仓库模式或数据结构，评估挖掘的模式，以不同的形式对模式 进行可视化。 狭义的理解认为数据挖掘是k d d 的一个重要步骤，它使用智能方法 提取数据模式，发现隐藏信息。而知识发现是从数据中识别正确的、新颖 的、有潜在使用价值的、最终可理解的模式的非平凡的过程。它包括数据 选取、数据预处理和数据清洗、数据挖掘、知识评估等多个步骤。数据挖 掘是其中对经过预处理的数据进行处理，抽取知识的过程。 无论哪种理解，对于以下几方面的认识是相同的： ( 1 ) 数据挖掘的对象是大规模的数据，这些数据可能来自于数据库、数 据仓库或者其它数据源： ( 2 ) 数据挖掘的结果是准确的、有用的、未知的、可解释的“知识”， 知识可能以各种形式存在：概念、规则、模式、约束等： ( 3 ) 数据挖掘的目的是支持决策分析，由于决策分析往往是时间紧迫 的，所以数据挖掘过程必须高效。 由此可知，数据挖掘是深层次的数据信息分析方法，它抓住了从大量 的、未加工的材料中发现少量的有用的知识的特点【3 。 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 数据作为一种数据表现和交换的格 式1 4 , 5 ，具有灵活性、自描述性、可扩展性等特点使得越来越多的领域开始 采用它作为主要的存储格式和传输媒介，特别是在w w w 上被广泛接受和 采用，因而产生了大量的x m l 数据，为了更有效地利用这些数据，人们 希望通过数据挖掘发现蕴涵在数据中的有效知识，这为数据挖掘提出了一 燕山大学工学硕士学位论文 个新的挑战。同时，x m l 可以看作一种半结构化数据模型，很容易地将 x m l 文档描述与关系数据库中的属性对应起来，实施精确地查询与模 式的抽取。因而将数据挖掘技术应用于发现频繁的x m l 模式无疑是非常 有益的。 1 2 国内外研究现状 x m l 表述的数据特点比较复杂，没有特定的模型可以描述，它通过将 数据内容和能够表达这些内容的语义标签结合在一起，实现数据层次的自 描述，即在x m l 数据中，结构和数据的区分是模糊的。而目前数据挖掘 必须具有固定的数据模型，可以根据模型具体地描述特定的数据，数据和 结构是分离的。因此，研究x m l 数据挖掘首先是找到合适的数据模型， 在模型基础上研究挖掘方法，进而发现有效的信息。 尽管x m l 数据表现形式灵活，但是本质仍然是树状的模型，可以利 用数据挖掘与树遍历结合的方法，有效的挖掘x m l 查询。在x m l 查询的 挖掘过程中，希望得到频繁结构。频繁结构的挖掘是指在大型x m l 数据 库中，从复杂的相互作用的实体之间抽取模式。这种挖掘方法不仅围绕着 关联规则【6 1 和序列模式【7 j 挖掘技术，而且与树结构的相似性和树模式匹配 有着紧密的联系。挖掘频繁模式最初是对r n a d n a 8 的研究，也就是在 多个r n a 图中找出相似的子结构；研究从标签图中找出频繁的致癌化合 物的子结构 9 l ；随后在w w w 中在w e b 文档中找出频繁子结构1 0 “4 i 。这 些方法都是从结构相似的数据对象或文件中找出频繁出现的子结构。由于 良构的x m l 文档是一个树型结构，查询语言如x p a t h 或x q u e r y 是用正则 路径表达式和树模式在树结构关系上进行查询的，因此将此工作转化为频 繁模式树的挖掘。 典型算法分析如下： ( 1 ) p a t t e r n m a t c h e r 算法文献 1 0 提出将x m l 查询数据转化为树，并 对树的节点用标签进行编码，每一个节点标签l = o ，1 2 ，m 1 允许不同的 节点具有相同的标签。每个树的编码以水平模式存储在x m l 数据库中， 4 第1 章绪论 挖掘的算法a p r i o r i 采用宽度优先搜索策略寻找频繁子树。利用边界把非频 繁的子树从频繁的子树中分离出来，重要的步骤是查寻每一个树中的候选 者。为了这个目的，介绍了一种叫哈希树的结构作为索引，哈希树中每一 树的项目都是下降的，不管什么时候到达它的叶子，将发现有一批候选者 己经包含在树中，接着在树中寻找这些候选者，如果成功的话，候选者的 计数增加。这种算法在挖掘短模式非常有效，但是在挖掘长模式时显得力 不从心。 ( 2 ) t r e e m i n e r 算法 为了解决p a t t e r n m a t c h e r 算法的不足，m j z a k i 在 文献【1 1 仲提出t r e e m i n e r 算法。这个算法是在前一算法的基础上，树中的 节点用一个范围列表来表示，树表示为垂直模式的节点范围表，范围列表 用( t ，m ，s ) 表示节点信息，t 指树的i d 号，m 是 1 ) 长度的前缀的标签，s 是 范围的最后一个项集。通过连接子树的节点范围表为频繁子树快速的计数， 产生无冗余的候选子树。算法的核心仍然是a p r i o r i 采用深度优先搜索频繁 子树的方法。联接范围列表之前进行有效的剪枝，确保子树是频繁的。当 前层发现的频繁予树形成下一层的元素对，直到递归地找到所有的频繁子 树为止。频繁子树由范围列表的所有元素对联接( 包括自然联接) 产生频繁 子树。算法的不足在于因为没有模式信息来引导计数，发现频繁子树时， 所有可能的节点扩展都要进行树蕴含的检测。这种方法对挖掘长模式较有 效。 ( 3 ) 树表示( t r e e e x p r e s s i n g ) 法文献d 2 提出树表示法，认为多个描述 同类信息的多个文档的多个不规则结构之间包含着一些相同的结构信息， 在多个文档中寻找“典型”结构，即相似结构。 算法如下： 第一步：计算频繁1 树。 第二步：由频繁k 一1 树生成频繁k 树。在生成频繁k 树的过程中，采 用经典a p r i o r i 算法的性质，任何频繁k 树p h p k 是由两个频繁k 一1 树 p 】p k - z p k 1 和p l p k 2 p k 组成。整个算法以此性质为依据。从频繁1 - 树开始， 按照从4 , n 大的顺序生成频繁k 树。但是实际处理过程中有很大的不同， 首先路径表示序列之间不能用简单的包含与否确定是否是子集关系；其次， 燕山大学工学硕士学位论文 因为它是一个序列，不同的排列表示不同的子树。正是这些不同使算法比 a p r i o r i 算法要复杂的多。在树表示法中，对于形如p l p k 一2 p k 1 和p 1 p k 2 p k 的匹配路径组合生成p 1 p k 时，假定两个匹配路径组合的叶子节点分别是 l 和l ，采用l 扩展l 的方法，相当于将l 的兄弟结点作为它的子结点进行 扩展。然后计算候选k 树表示的支持度。 第三步：剪枝。提出“非自然”和“超非自然”两种树表示概念。如 果一个树表示中所有非叶子结点具有相同标记的k 个分支上的上标，遵循 从左到右从1 到k 的顺序，那么这个树表示就是自然的，否则就是非自然 的。超非自然是指分支上的上标是无序的。在剪枝步将所有的非自然和超 非自然的候选树表示全部删除。 第四步：最大化。树表示方法主要用于发现多个描述同类信息的多个 文档的相同的结构信息，因此在算法的最后它将所有可以包含在其它频繁 树表示中的一些小的频繁树表示删除。 另外，树表示引入了通配符。x m l 数据虽然包含一定的结构，但是结 构非常不规则，也不确定，发现完全一样的结构比较少，引入通配符可以 替代任何标记，尽量多地发现相同的结构。但通配符的引入导致算法的更 高的复杂程度。g a oc o n g ”】等对通配符问题进行改进。 ( 4 ) t r e e f i n d e r 算法文献 1 4 】也采用树表示方法，首先把树表示为标签 对，代表祖先关系的传递闭包。使用标准的a p r i o r i 算法来挖掘频繁标签对 集，对于每个有一系列频繁标签对集，用树包含来近似树蕴含达到可伸缩 性，这个算法的目的是构造最大公共子树。其主要局限是它只能发现实际 频繁子树集的子集。 ( 5 ) f r e q t 算法t a s i a 等在文献 1 3 1 提出的这种增量算法目的是从半 结构的文档中查找频繁子树，改进了当x m l 文档较大时，树表示法直接 生成检验效率不高的缺陷。 算法的关键是最右边扩展，一种在树的最右分支上增加新结点生成新 树的技巧，这种方法保证了新树不破坏旧树的先序遍历，即新增加的结点 永远是最右边叶子结点。同时由于采用增量算法，另一个关键的技术是通 过频繁k 1 模式的出现次数计算候选k 模式的出现次数，只要根据频繁k 1 6 第1 章绪论 模式的最右边叶子结点的出现频率，就可以得到候选k 模式的出现次数， 因此这种方法还有很大的存储优势，只要保存频繁模式的最右边出现频率 就可以有效地实现增量频繁度的计算。 算法过程如下： 第一步：计算频繁1 模式，遍历树获得并保存每个模式的出现次数。 第二步：在频繁k 1 模式的基础上进行所有可能的扩展，为了保证新 树不破坏旧树的先序遍历，只进行最右边扩展，即只在频繁k 一1 模式的最 右边分支上增加新结点，生成候选k 模式。 第三步：计算候选k 模式的支持度，产生频繁k 模式、由于算法是增 量算法，不需要重新计算候选k 模式中所有结点的匹配情况，借助频繁k 一1 模式的匹配记忆，只考虑新增加的结点即可，因此一个关键就是如何保存 频繁k 1 模式的匹配情况。借助最右边扩展的技巧，文献 7 】证明不需要保 存树中所有的结点的匹配情况，只要保存树的最右边结点的出现次数计算 候选k 模式的最右边结点出现次数，最后根据候选k 模式的最右边结点的 出现次数计算候选k 模式的支持度，进而产生频繁k 模式。 第四步：继续上述步骤，直到生成所有的频繁模式。 另外，文献 1 6 ，1 7 提出从半结构w e b 文档挖掘频繁子结构的算法。 引用“? ”树的匹配算法。缺点：不能获得精确的语义递归。 以上方法存在问题是：产生大量的无关的候选；存在连接子树时，大 量树的匹配问题。为了减少候选子树，解决树的匹配提出频繁模式树性质 和a p r i o r i 算法结合的算法。 ( 6 ) x q p m i n e r 算法l h y a n g 等人提出以树表示算法和增量算法结合 的x q p m i n e r 算法1 1 8 ，首先构造一个全局查询模式树( g l o b a lq u e r y p a t t e r n t r e e 简记g q p t ) ，并用先序遍历计数表示节点。查询模式树用这种编码 模式计数，简化查询模式树，减少操作时对内存的需要。使用前缀树索引 频繁的有根子树。 算法分为两个阶段： 第一阶段：产生候选有根子树。利用g q p t 模式引导最右边扩展计数 的方法，对已产生的频繁k 边有根予树进行最右边扩展，得到k + 1 边有根 7 燕山人学工学硕士学位论文 子树，由于有模式引导，有效的减少不必要的候选，如图卜2 ( b ) 所示；没 有模式引导时，将产生一些根本不存在的候选子树，加大算法的负担。利 用a p r i o r i 算法反单调性对候选有根子树进行剪枝，获得频繁的有根子树， 对得到的候选有根子树进行计数修剪掉低于最小支持度的候选有根子树， 为第二阶段减少匹配的数量。 ( a )全局查询模式树 ( a ) g l o b a lq u e r yp a t t e r nt r e e 99b 。- b o 姗o k g 篙 p _ d r 虻e t - t i t l e 蕊一瑟一瑟 一一一一一了6 一磊丽博一一一一一一 ( b ) s c h e m a - g u i d e de n u m e r a t i o n i 如如j l 一盔一鑫一- j 缸) 非模式引导 ( c ) n o n s c h e m a - g u i d e de n u m e r a t i o n 图卜2 模式引导和无模式引导产生有根子树的对比 f i g u r e1 - 2s c h e m av e r s u sn o n - s c h e m ag u i d e de n u m e r a t i o no f r s t s 第二阶段：对每一候选有根子树与数据库中的查询模式进行匹配、计 数，大于最小支持度的候选有根子树即为频繁查询模式树。这种算法避免 了传统a p r i o r i 算法通过联接产生大量的候选，比前几种算法有较好的有效 性和伸缩性，但仍然存在大量树的匹配的缺点。 ( 7 ) f a s t x m i n e r 算法在x q p m i n e r 算法的基础上提出引入x m l 查询 的事务的i d ( 廿d ) ，就是f a s t x m i n e r 【19 】。对前一算法进行很大的改进。该算 法指出只有最右边扩展单枝需要与数据库中的查询模式进行匹配，而多分 枝不需要匹配的定理，这样就大大缓解了x q p m i n e r 树匹配的压力。 第一阶段用候选生成算法生成候选的有根子树与x q p m i n e r 不同之处 在于：产生的候选有根子树根据是否为单枝有根子树，若是则进入下一阶 段的匹配操作，否则进行有根子树的剪枝，有效地减少匹配的数量。 第l 章绪论 第二阶段由于引入事务的1 d s ，则只有由最右边的叶子节点( 单枝) 产 生的候选频繁有根子树需要进行匹配。而沿着最右分支扩展的非叶子节点 ( 多分枝) 产生的频繁有根子树，因为它们含有相同的前缀所以不用匹配。 从而得到频繁查询模式树。算法的另一改进是对最右边扩展分为两部分， 一部分为深层右边扩展：另一部分为同层进行联接操作。前一部分采用单 枝匹配而对多枝统计剪枝；后一部分根据t i d 列表进行计数和剪枝。这种 算法与x q p m i n e r 相比具有更好的有效性和伸缩性。同时减少了树匹配的 数量。 算法的缺点：虽然避免了产生不存在和无关的大量候选，但仍然需要 维护由于候选产生测试的一部分候选项集。 1 3 本文研究内容 x m l 作为国际数据转换的标准，已经贯穿于i n t e m e t 应用的各个领域， 从而带来了大量的x m l 格式的数据，如何存储和查询x m l 数据成为一个 重要的课题。 由于x m l 数据的嵌套结构和模式信息不全的特点，使其结构非常复 杂，对它的查询处理也比较困难。而用户在x m l 查询时关心的是响应时 间。而对查询响应时问来说网络以及服务器的速度都是很重要的硬件原因。 从软件角度来说，提高响应时间主要集中在索引路径1 2 0 2 2 1 和优化x m l 查 询 2 3 2 4 。 因此，如何利用已有的查询和结果，减少查询次数，这是x m l 查询 频繁模式挖掘的研究重点。x m l 查询挖掘是在已有的x m l 查询中挖掘频 繁查询模式，并将其放入缓存中，从而提高x m l 管理系统的操作效率。 作者对这方面的文献资料进行了广泛的阅读、消化理解，进一步研究发现， 通过关联规则的方法挖掘出频繁查询模式存在不足之处，从而提出新的方 法解决频繁模式的挖掘，并通过实验验l 正该方法的可行性和有效性。具体 的研究如下： ( 1 ) 对于利用关联规则的x m l 查询频繁模式挖掘算法，进行归纳和总 9 燕山大学工学硕士学位论文 结，分析各种算法的缺陷和不足。 ( 2 ) 讨论目前x m l 查询频繁模式的关联规则最优算法，并实现该算法。 f 3 ) 讨论各种聚类方法的优缺点，提出一种适用于x m l 查询模式的基 于网格和密度的聚类算法，将数据放入单元格中，寻找高密度的单元格， 通过单元格的连通构建高密度的聚类子空间，聚类子空间就是所寻找的频 繁模式区域。 ( 4 ) 根据作者提出的聚类方法以v c + + 6 0 为实验平台，采用文献 1 9 】中 使用的数据集，对x m l 查询进行聚类分析，进而发现x m l 查询频繁模式。 对比作者提出的聚类算法和文献【1 9 】提出的关联规则算法挖掘x m l 查询 频繁模式，对比两个算法的有效性和伸缩性的不同，而得出聚类算法具有 较好的有效性和伸缩性的结论。 f 5 ) 最后，根据查询是连续的，查询处理所使用的内存远远小于数据流 本身，查询处理过程中数据仅仅能够被扫描一遍等特点，将查询流分组， 提出建立动态全局查询模式树和等价类树结构，利用这两种简化结构和关 联规则实时挖掘“热点”查询模式，并给出挖掘算法框架。挖掘频繁出现 的共享路径并将其综合到一个结构中，从而避免重复操作。 1 4 研究的理论和实际意义 在x m l 查询的历史数据库中，离线挖掘用户频繁查询模式，并将结 果放入c a c h i n g 中避免重复查询和相似查询以提高查询的响应时间。用户 提出查询，首先在缓存中检查是否存在已有频繁的查询模式，若有则返回 给用户结果，若没有到数据库中查找。而在线挖掘挖掘出动态的频繁查询 模式，从而确保高速缓存的高效性，确定当前“热点”的查询模式，并且 能够及时的捕捉更新趋势和模式，实时的更新频繁查询模式，更能体现出 模式变化的特点。无论是哪一种挖掘都为优化查询提供有力的条件，因此， 挖掘x m l 频繁查询模式在c s 系统、分布式系统、x m l 系统 2 5 , 2 6 和w e b 信息系统上个性化服务口7 3 0 1 以及搜索引擎f 3 】碰1 的优化等都有广阔应用前 景。 1 0 第1 章绪论 1 5 本文结构 第1 章为绪论，介绍了论文研究的目的、意义、现状和研究的内容。 第2 章对x m l 和x m l 查询进行简要介绍以后，概述了挖掘x m l 查 询模式相关的技术方法以及作者所做的工作展开。 第3 章讨论了f a s t x m i n e r 算法及算法的实现。 第4 章介绍数据挖掘的一个新的应用_ x m l 查询模式的聚类，作者对 用聚类技术挖掘x m l 查询模式进行了研究。提出一个聚类算法。 第5 章对查询流中的“热点”查询提出一个有效的挖掘算法的框架。 虽后，作者对本文进行了总结，并在此基础上提出对x m l 查询频繁模式 将来的工作的展望以及个人粗浅的看法。 燕山大学工学硕二e 学位论文 第2 章挖掘x m l 查询模式相关技术 x m l 是一种极为通用的数据格式，它可以用来描述很多不同种类的数 据，随着x m l 的不断普及，x m l 数据的管理和查询问题也越来越引起人 们的重视1 3 “”。 目前，针对x m l 提出了大量的查询语言。其中对树状数据查询提出 的主要有x p a t h 42 1 、x q u e r y 4 3 1 等。尽管这些语言各具特点，但它们的共同 点是将路径表达式作为重要的组成部分。下面讨论x m l 、x q u e r y 以及挖 掘查询频繁模式相关的概念和技术。 2 1x m l 简介 x m l 是w 3 c ( w o r l d w i d ew e bc o n s o r t i u m ) 在1 9 9 8 年提出的新的文档 数据表示规范。x m l 作为数据表示规范，和h t m l 相比，具有表达功能 强大、表达形式灵活的特点。随着一系列与x m l 相关的规范的提出，以 及越来越多的软件产品、w e b 服务提供商开始支持x m l ，以x m l 为主导 的这一系列规范开始成为新一代的w e b 标准。 x m l 是一种界定文本数据的简便而标准的方法。它曾经被人们称作 “w e b 上的a s c i i 码”。就好像程序员可以用自己喜欢的编程语言来创建 任何一种数据结构，然后同其他人在其他计算平台上使用的其他语言来共 享一样。x m l 的标记用来说明所描述的概念，而属性则用来控制它们的结 构，因此人们可以定义自己所设计出的语法与他人共享。x m l 数据描述机 制意味着它将成为一种在i n t e r n e t 上共享信息的强大途径。 x m l 是s g m l 的一个简化而严格的子集，是特别为w e b 应用而设计 的。它去掉了s g m l 中很少使用而且处理起来很麻烦的特征，但继承了 s g m l 具有的可扩展性、结构性及可检验性。x m l 具有简单、开放、中立、 可扩充、国际化、高效、易管理、无二义等特点，与h t m l 相比，区别主 1 2 第2 章挖掘x m l 查询模式相关技术 要在以下几个方面： ( 1 ) 可扩展性h t m l 不允许用户自行定义他们自己的标示或属性，而 在x m l 中，用户能够根据需要，通过d t d t a 4 j 来定义文档结构，使其他信 息系统自动了解文档的内容自行定义新的标识及属性名，以便更好地从语 义上修饰数据。 ( 2 ) 结构性h t m l 不支持深层的结构描述，x m l 的文件结构嵌套可 以复杂到任意程度，能表示面向对象的等级层次。 ( 3 ) 可检验性h t m l 没有提供规范文件以支持应用软件对h t m l 文 件进行结构检验。而x m l 文件可以包括个语法描述，使应用程序可以 对此文件进行结构检验。 ( 4 ) 自描述性这个特性使差异性可以存在，使计算机可以在没有人为 干涉的情况下，理解数据的含义。 ( 5 ) 多样的样式表支持x m l 把数据内容与他们的表现形式分开，这 样既可以只关心数据的逻辑结构，也可以通过样式表来格式化数据的表现， 你甚至可以定义自己的个人样式表来显示各种不同的x m l 数据p 5 1 。 首先x m l 本质上是一种标注语言( m a r k u pl a n g u a g e ) 。x m l 是基于标 签的，与h t m l 的标签不同，x m l 的标签不需要预先指定含义，相反， 它只是用来标记数据。 所谓的“x m l 基本语法”，依据x m l l 0 规格，大致可以整理如下： ( 1 ) x m l 声明必须以小写“x m l ”声明，并设置v e r s i o n 属性，而且是 出现在第一行； ( 2 ) 一定要有一个根( r o o t ) 结点，也只能有一个根结点( 根结点也就是根 标记1 ： ( 3 ) 所有标记必须以树状排列； ( 4 ) 除了内容为空的标记外，所有的标记都必须以开始标记、结束标记 成对出现； ( 5 ) 内容为空的标记结尾必须加上“”，这种标记称为“空标记”； ( 6 ) 标记名称与属性必须合法，且大、小写被视为不同； ( 7 ) 属性值的指定前后必须被双引号所包含： 燕山大学工学硕：上学位论文 f 8 ) 特殊字符必须依照规定编写。 符合上述8 个条件的x m l 文档称为良构的( w e l l f o r m e dx m l ) 文档。 元素是x m l 文档的基本结构，元素和元素之间可以嵌套。一个满足 标注封闭和标注嵌套的x m l 文档被称为( w e l l f o r m e d ) 。每个元素可以附带 属性( a t t r i b u t e ) 。属性可以具有有限的几种类型，其中包含i d 、i d s 、i d r e f 、 i d r e f s 。这几种类型被用来表示元素之间的引用关系。标注所允许的嵌套 关系以及元素可能具有的属性可以使用d t d ( 文档类型定义，d o c u m e n t t y p ed e f i n i t i o n ) 来声明。一个x m l 文档最多只能有一个d t d ，但是一个 d t d 可以是多个x m l 文档的类型说明。一个元素和属性符合相应d t d 定义的x m l 文档称为是有效的( v a l i d ) 。d t d 并不是x m l 文档的严格模式 定义。它仅仅提供了标注和属性的可能出现的形式。同时，类型的说明是 灵活并粗略的：标注可能以“或”( “n 的关系出现，也可能以“连续”( “p 、 “”) 的形式出现。所以，d t d 只提供了简单的模式信息。 从另一个侧面看，d t d 一般是文档的作者编写或选择的，或者是某一 个领域的标准。于是，d t d 中标注和属性所使用词以及标注之间可能出现 的嵌套结构可以认为是相应x m l 文档的提纲。即：d t d 反映了对应x m l 文档的内容和结构信息。 x m l 的应用可分为四类： ( 1 ) 应用于客户需要与不同的数据源进行交互数据可能来自不同的 数据库，他们都有各自不同的复杂格式。但客户与这些数据库只通过一种 标准语言进行交互，那就是x m l 。与其他的数据传递标准不同的是，x m l 并没有定义数据文件中数据出现的具体规范，而是在数据中附加t a g 来表 达数据的逻辑结构和含义，这使得x m l 成为一种程序能自动理解的规范。 ( 2 ) 应用于将大量运算负荷分布在客户端客户可根据自己的需求选 择和制作不同的应用程序以处理数据，而服务器只须发出同一个x m l 文 件。x m l 的自描述性使客户端在收到数据的同时也理解数据的逻辑结构与 含义，从而使广泛、通用的分布式计算成为可能。 ( 3 ) 应用于将同一数据以不同的面貌展现给不同的用户这一应用为 网络用户界面个性化、风格化的发展铺平道路，同时为网络用户提供了一 1 4 第2 章挖掘x m l 查询模式相关技术 个更好的应用空间。 f 4 1 应用于网络代理对所取得的信息进行编辑、增减以适应个人用户 的需要。有些客户取得数据并不是为了直接使用而是为了根据需要组织自 己的数据库。同一个x m l 文件便可变成多个文件传送到不同的用户手中。 从x m l 的这些应用我们可以看出，x m l 已经日益地成为w e b 上数 据表示和数据交换的一个主要标准。 2 2 x q u e r y 概述 x m l 文档可以表示几乎所有的东西，x m l 数据查询语言的用户希望 能够对他们储存在x m l 当中的任何数据进行有效的查询。无论存储在 x m l 当中的数据有多么复杂，x m l 的结构本身是简单的。x m l 文档本质 上讲就是一个以顺序和层次为主要结构单元的轮廓。x q u e r y 正是基于 x m l 的这种结构的，它使用这种结构来为同样范围内的x m l 存储的数据 提供查询能力。更为精确地说，x q u e r y 是以x q u e r y1 0 以及x p a t h2 0 数 据模型的形式定义的 x q d m ，并将x m l 文档的分析结构描述为有序的， 做上标记的树，树上的每一个结点都有一个不同的身份并可能具有简单的 或者复杂的类型。 x q u e r y 能够被用于对没有任何模式( s c h e m a ) 的x m l 数据进行查询， 也可以对由x m l 模式或者由文件类型定义( d t d ) 来管理的数据进行查询。 x q u e r y 是可适用于任何类型的x m l 数据源的查询语言，它是一种将查询 表示为表达式的功能语言，它的各种表达式之间可以相互嵌套；它又是一个 强类型化的语言，所有的操作、表达式和函数都必须有一定的类型；和x m l 一样，它也是大小写敏感，所有的关键字都必须小写。需要注意的是x q u e r y 所使用的数据模型与古典的关系模型截然不同，在x q u e r y 没有层的概念， 顺序在这里也不是很重要，并且不支持身份( i d e n t i t y ) 。x q u e r y 是一种功能 性的语言一与程序设计语言那样执行命令不同的是，每一个查询都是一个 待求值的表达式，并且表达式之间可以进行非常灵活的组合来创建一个新 的表达式。 燕山大学工学硕士学位论文 2 2 1 相关概念 序列( s e q u e n c e ) ：0 个或多个数据项的有序集合；表达式的结果总是一 个序列；只包含一个数据项的序列称为s i n g l e t o n 序列；不包含数据项的序 列e m p t y 序列。 数据项( i t e m l ：一个简单值或节点。 简单值( s i m p l ev a l u e ) ：x m ls c h e m a 中定义的基本数据类型，或引用。 名域( n a m e s p a c e ) ：名字的集合，用u r i 表示，它与元素和函数名构成 一个( 名域，非正规名) 对，可以区分来自不同名域具有相同非正规名的元 素和函数。 节点( n o d e ) ：包括d o c u m e n t ，e l e m e n t ，a t t r i b u t e ，t e x t ，n a m e s p a c e ，p r o c e s s i n g i n s t r u c t i o n 和c o m m e n t 。 名字( n a m e ) ：由名域和非正规名( 即字符串) 构成。 x q u e r y 基本表达式包括变量，文字，元素与函数名，通配符，k i n d t e s t 和括号表达式。变量用“$ ”加上名字表示，立n $ b o o k ；元素和函数名都必 须是正规的名字；文字包括字符串和数值；通配符可以代替整个名字，也 可以代替其中的名域或非正规名：k i n d t e s t 用于获得相应节点的值。 由于x m l 数据具有树状结构，因此在x q u e r y 查询中，路径表达式起 着关键的作用。x q u e r y 的路径表达式的表达能力非常强，从以下几个表达 式中就可以看出： ( 1 ) d o c u m e n t ( “b i b x m l ”) c h i l d ：b i b d e s c e n d a n t o r s e l f ：a u t h o r ； ( 2 ) d o c u m e n t ( “b i b x m l ) b i b a u t h o r ； ( 3 ) $ b i b a u t h o r n a m e ； ( 4 ) $ b i b a u t h o r a g e ； ( 5 ) b i b a u t h o r ! + 。 在路径表达式中最为常用的操作就是通过识别他们在树的层的位置来 查找节点。路径表达式由一步或者多步组成，由一个反斜杠“”或者双反 斜杠“”隔开。每一步求一序列结点的值。 首先式( 1 ) 和式( 2 ) 的结构类似，实际它们的含义相同，都表示b i b x m l 1 6 第2 章挖掘x m