xml非完全结构查询处理中若干关键技术的研究

《xml非完全结构查询处理中若干关键技术的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、东北大学博士学位论文XML非完全结构查询处理中若干关键技术的研究姓名：李晓光申请学位级别：博士专业：计算机软件与理论指导教师：于戈20060101东北大学博士学位论文摘要摘要随着Internet的发展和异构信息源集成技术以及存储技术的进步，网络中涌现出大量半结构化数据资源。XML由于其所具有的自描述性、灵活的数据结构以及丰富的数据表示能力等特点，逐渐成为数据表示、存储和交换标准之一。近年来，XML非完全结构查询处理技术作为有效管理XML文档的关键技术之一，引起越来越多研究人员的关注。XML非完全结构查询(Non—fullyStructu

2、redQuery,NFSQuery)是指满足用户在缺乏完整的XML文档结构信息情况下的查询需求。NFS查询是近两年出现的XML查询技术，其主要面向缺少完整的结构信息说明以及异构环境下的查询需求。在实际中，特别是在Intemet和Intranet上，大部分XML文档缺少结构说明或存在异构现象，这使得NFS查询有着广泛的应用前景。本文就XML非完全结构查询处理技术中的有意义的NFS查询结果判断技术和基于内容的查询结果聚类技术进行了深入研究。有意义的NFS查询结果判断是NFS查询处理中非常重要的一环，现有的判断方法，如XSEarch中的Int

3、erconnectionRelationship和Timber中MLCA，都是从一个特定的角度来设计判断标准，缺乏一个准确和全面的定义，这使得它们只能适用于特定的XML文档。另外，现有方法无法适应于大规模XML文档，如XSEarch的索引建立时间和Timber的查询时间在大规模XML文档下远远超出用户的容忍程度。本文提出了一种基于模式和实体概念的有意义的NFS查询结果判断模型一PE模型。PE模型从系统角度出发定义了一种用户普遍接受的判断方法，与具体的等价模式和等价查询项的判断方法无关，具有可扩展性。基于PE判断模型，提出一种具体的基于结

4、构相似性的等价模式判断方法，并给出了一个判断规则。为了提高NFS查询的执行效率，设计了模式索引PE和增强的倒排索引12P，提出一种高效的NFS查询算法，它们不仅可以支持高效的路径查询和关键字查询，而且可以有效地支持本文提出PE模型，并有效地利用了现有XML数据库系统中的索引资源，适用于大部分XML编码方案。实验表明，本文方法的效率和准确率要远远高于XSEarch和Timber系统，适用于大规模XML文档。NFS查询为非精确查询，在XML文档规模较大的情况下，NFS查询往往返回大量结果。而以文档为中心的XML文档节点包含了大量的文本信息，

5、为了方便用户快速定位所需信息，通常需要对结果按照内容进行聚类。文档聚类是实现这一目的的有效技术之一。基于概率模型的聚类方法具有高维数据适用性和簇可东北大学博士学位论文摘要解释性特点，被广泛用于文档聚类。但当数据特征超过100维时，基于模型的聚类极容易产生聚类偏斜。目前的研究主要通过设定平衡约束条件，并将聚类问题看作约束优化问题来防止聚类偏斜。这种解决方法的局限性是：它们均假设数据分布是均衡的，并且通过直接设定各个簇在数据集合中的比例来改进分配阶段的数据分配策略，仅适用于可以事先获得平衡约束条件的应用中。在实际应用中，这种假设在大多数情况

6、下是无法成立的，而且很难事先设定约束条件。本文认为聚类偏斜产生原因主要有以下三点：簇模型的初始值选择、簇模型对文档特性的拟合性以及估计样本分散化与簇模型估计泛化的互作用。基于此分析，提出一种克服聚类偏斜的文档聚类方法MMPC]ust，它采用基于内容特性的混合模型作为簇模型，以期更准确地反映各簇基于内容的分布特征，提高分配阶段的准确率，防止分配阶段样本分散化。在模型重估计阶段，MMPCIust自动选取模型估计样本，降低估计样本的分散化，有效地防止在估计阶段的模型泛化。同基于约束的方法相比，MMPCIusi不需要事先设定各个簇所占的比例作为

7、约束条件，因而具有更好的应用性。另外，为了适应不同的应用环境，本文提出了两种具体的聚类算法MMPCIust—I和MMPCIust—Ii，MMPclust—I算法着重于聚类质量，而MMPCIust．II算法是MMPCIust—I算法的简化，其聚类质量略有降低，但聚类效率大大高于前者。实验结果显示，MMPCIust在很大程度上抑制了聚类偏斜的产生，其Macro—F1评价指标优于现有的模型聚类算法。基于概念的文档特征降维是有效提高文档聚类质量的手段之一。然而现有的基于概念的特征降维技术没有全面地反映词、概念、文档与主题之间的关系，并存在如何选

8、取概念的问题。通过潜在概念变量和主题变量的引入，以及词、潜在概念、文档和主题之间关系的概率表示，本文的模型更全面地反映了词与潜在概念、文档与主题和潜在概念与主题之间的模糊关系。根据信息论中熵压缩编码理论，定