英语原文共 41 页，剩余内容已隐藏，支付完成后下载完整资料
XML数据聚类：概述
ALSAYED ALGERGAWY, Magdeburg University
MARCO MESITI, University of Milano
RICHI NAYAK, Queensland University of Technology
GUNTER SAAKE, Magdeburg University
在过去几年中，我们观察到了基于XML文档和模式的结构和内容集群化XML文档和模式的方法。存在如此大量的方法是由于需要聚类XML数据的不同应用程序。这些应用程序需要类似内容，标签，路径，结构和语义形式的数据。在本文中，我们首先概述了聚类有用的应用程序上下文，然后我们调查了迄今为止提出的依赖于数据（实例或模式）的抽象表示，已识别的相似性度量以及聚类算法的方法。在本演示文稿中，我们的目标是绘制一个分类法，可以对当前的方法进行分类和比较。我们的目标是在比较XML数据集群方法，开发新的集群算法以及实现XML集群组件时引入一个有用的集成视图。最后，本文将介绍仍需要面对的未来趋势和研究问题。
Categories and Subject Descriptors: H.2.8 [Database Management]: Database Applications—Data mining; H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval; H.3.5 [Information Storage and Retrieval]: Online Information Services
一般关键词：文档，算法，性能
附加关键词和短语：XML数据，聚类，树相似性，模式匹配，语义相似性，结构相似性，文档
ACM Reference Format:
Algergawy, A., Mesiti, M., Nayak, R., and Saake, G. 2011. XML data clustering: An overview. ACM Comput. Surv. 43, 4, Article 25 (October 2011), 41 pages. DOI = 10.1145/1978802.1978804 http://doi.acm.org/10.1145/1978802.1978804
1.简介
可扩展标记语言（XML）已成为Web和Internet上信息表示和交换的标 [Wilde和Glushko2008]。 因此，大量的信息以XML表示，并且已经开发了几种工具来交付，存储，集成和查询XML数据[Wang 等人2004; Bertino and Ferrari 2001; Florescu和Kossmann 1999]。开发用于有效管理和分析极大量XML数据集的高性能技术变得不可避免。 许多研究人员关注的方法之一是聚类，它根据内容和结构对类似的XML数据进行分组。 XML数据的聚类过程在许多数据应用领域中起着至关重要的作用，例如信息检索，数据集成，文档分类，Web挖掘和查询处理。
通常，聚类是一种有用的技术，用于将共享相似特征的单个组/集群中的数据对象分组，同时将对象放置在不同的不同组中[Jain等人。 1999; Berkhin 2002; Xu and Wunsch 2005]。关于聚类XML数据的具体研究正在获得动力[Lee 等人 2002;Lee等人。 2004; Leung等。 2005; Dalamagas等人。 2006; Nayak和Tran 2007; Aggarwal等人。 2007;Cui等人。 2007; Nayak 2008]用于根据XML文档和XML模式的内容和结构对其进行聚类。已经提出了几种XML模式语言[Lee和Chu 2000]，用于描述XML文档的结构和合法构建块。其中，通常使用XML数据类型定义（DTD）和XML模式定义（XSD）。自文件以来模式中概述的定义适用于该模式的所有文档实例，从模式集群生成的结果能够将具有相似特征的文档组合在一起。但是，实际上，由于使用了选择运算符，一些XML文档没有关联的模式，并且模式实例可能呈现不同的结构。因此，用于聚类XML文档和XML模式的算法引起了研究人员的关注。
集群XML数据是一个复杂的过程，它与平面数据和文本的集群有很大不同。集群XML数据的困难是由于以下原因[Aggarwal等人。 2007年]。首先，聚类算法需要计算不同XML数据集之间的相似性，这本身就是一个困难的研究问题（XML数据的异质性给识别理想的相似性函数带来了许多挑战）。其次，XML数据的结构组织增加了集群算法需要处理的隐式维度，这导致无意义的集群。 XML数据具有多个功能，例如语义，结构和内容，每个功能都包含一组子功能。对XML数据进行聚类，考虑一个特征而忽略其他特征，无法实现准确的聚类结果。例如，图1（a）显示了三个表示DBLP数据库中日记和会议论文的XML模式。数据集具有诸如“作者”和“标题”之类的共同元素。即使D1和D2只有一个不同的元素，它们也应该根据通常的语义分为两个不同的集群，这些语义与期刊和会议中的出版物具有不同的相关性。相反，即使D2和D3只有一个不同的元素，它们也应该在同一个集群中，因为它们都是指会议论文。此外，由于XML数据异构性的增加，根据其内容和结构组织XML文档的需求变得具有挑战性。图1（b）描绘了来自发布域的六个XML文档的片段：（a），（b），（c）和（f）中所示的XML片段共享相似的结构，（d）和（d）中的片段（e）分享类似的结构。可以观察到（a）和（f）中的片段与（b）和（c）中的片段具有相似的结构，然而，这两组片段的含量不同。如果将结构相似性视为聚类的标准，则这些文档将分为两组，分别为“书籍”和“会议文章”。但是，这种分组将无法进一步区分包含多种类型书籍的“书籍”群集中的文档。另一方面，仅基于内容特征相似性的文档聚类将无法区分会议文章和遵循两种不同结构的书籍。为了得到有意义的分组，应该根据它们的结构和内容特征相似性来分析这些片段。通过综合考虑结构和内容特征来聚类XML文档将产生三个集群，即“数据挖掘书籍（DM）”，“生物学书籍（生物学）”和“关于数据挖掘的会议文章”。
为了进行良好的调查并构建用于比较现有XML数据聚类方法的公平基础，提出了用于XML数据聚类的通用框架的高级架构。受数据聚类活动步骤的启发[Jain et al.1999]，图2描述了具有三个基本阶段的XML数据聚类框架。
（1）数据表示。 XML数据使用公共数据模型表示，该模型捕获XML数据中固有的语义和结构信息。该阶段包括两个子阶段：特征选择和特征提取。特征选择从一组候选中选择独特的特征，而特征提取使用规则从原始特征生成有用和新颖的特征。我们在第3节详细介绍了XML数据表示。
（2）相似度计算。确定用于测量数据对对之间的相似性的接近函数。根据提取/选择的特征的相似性对XML数据进行分组。聚类解决方案的性能主要取决于所采用的相似性度量。基于用于表示XML数据的数据模型的类型，已经提出了几种XML相似性度量。我们将在第4节讨论XML相似性度量。
（3）聚类/分组。使用适当的聚类算法，基于邻近函数将类似的XML数据分组在一起。大多数聚类算法隐含地或明确地与所采用的相似性度量相关联。在图2中，“相似性计算”和“聚类/分组”框之间的细箭头表示分组处理可以与相似性计算阶段交织。最后，聚类框架的输出可以表示为一组聚类或嵌套的数据集（层次结构），如图2中的虚线所示。我们对聚类方法和质量评估进行了详细讨论。他们在第5节中的应用。
本文概述了XML数据聚类方法和实现，以便绘制在XML数据管理中使用聚类算法的路线图。 本文从XML数据聚类有用的应用程序上下文开始，然后调查当前的方法，并提供解释其共同特征的分类法。 本文还讨论了XML数据聚类领域带来的挑战和益处。 希望该调查对新方法的开发者和需要从可用方法库中选择方法的用户都有帮助。
本文的其余部分安排如下。第2节调查了利用XML数据聚类输出的不同应用程序域。 第3节，第4节和第5节分别讨论了通用聚类框架的三个阶段。 在第6节中，根据引入的框架提出并比较了现有方法。 第7节介绍了结束语和开放研究方向。
2.应用领域
为了激发集群XML数据的重要性，我们总结了它在多个数据应用领域中的使用。
2.1．XML查询处理
虽然XML主要被视为信息交换的标准媒介，但XML数据的存储，索引和查询仍然是重要的问题，并已成为学术界和工业界的研究热点[Wang 等人2004; Melton和Buxton 2006; Gou和Chirkova 2007]。到目前为止，已经提出了用于存储和查询XML文档的XML本机（例如，Tamino，eXist，TIMBER）和启用（例如，Oracle，IBM DB2，SQL Server）数据库管理系统（DBMS [Bourret 2009]。原生DBMS依赖于专门用于管理XML的数据模型，而已启用的DBMS是已经扩展用于XML处理的关系或对象关系数据模型。启用的XML DBMS比原生的更成熟，因为大型供应商支持并且XML数据与其他公司数据的集成更容易。一些已启用的DBMS支持XML Schema，用于规范XSD与XML文档的内部关系或对象关系表示之间的映射[Florescu和Kossmann 1999; Shanmugasundaram等。 1999年]。
Xpath和XQuery等查询语言已经开发用于以其本机表示形式访问和操作XML文档，并且已经构想了SQL标准的扩展以处理除关系数据之外的XML数据[Melton和Buxton 2006]。到目前为止提出的所有标准都没有涉及数据异质性。为了处理异构查询，已经提出了近似技术来评估树枝模式[Gou和Chirkova 2007]。 Twig模式是XML的简单树结构查询，包括三个基本语言元素，即节点条件，父子边缘和祖先 - 后代边缘。 Twig模式适用于信息检索（IR）以及数据库设置。数据库样式的查询返回所有与查询的内容和结构要求精确匹配的结果，而IR样式的查询允许模糊结果，这些结果基于它们排序查询相关性。
尽管树枝模式匹配已经成为一个重要的研究领域，并且已经开发了几种方法来解决它，但是它存在一些缺点，特别是在大规模XML数据和复杂的树枝模式中，其中与查询相关的数据出现在一小部分中。整个XML文档。因此，如果我们只能访问我们需要的部分数据，则可以更有效地进行查询处理，因为在查询处理期间通过跳过不必要的数据来减少搜索空间。因此，一个好的解决方案是考虑聚类方法，以便根据它们的共同内容，语义和结构对整个XML数据进行分区。[Lian等人。 2004;Choi等人。 2007年]。
2.2．XML数据集成
XML被广泛用作Web应用程序和企业之间的数据交换媒介。因此，分布式XML数据的集成成为一个研究问题。这是由于Web上出现了大量的业务数据;大量面向服务的体系结构正在以Web服务的形式进行调整。 XML数据集成包括构建一组独立开发的XML数据的全局视图[Batini 等人 1986; Le等人。 2006;贝尔蒂诺和法拉利2001]。
由于XML数据是由不同的人设计的，因此它们通常具有不同的结构和术语异质性。异构数据源的集成需要许多工具来组织和使其结构和内容同质。 XML数据集成是一项涉及不同级别协调的复杂活动：（1）在模式级别，协调同一实体或属性的不同表示，以及（2）在实例级别，确定来自不同源的不同对象是否代表相同现实世界的实体。此外，Web数据的集成增加了数据异构性方面的集成过程挑战。这些数据来自不同的资源，很难确定与业务主体的关系。因此，集成XML数据的第一步是找到在语义和结构上相似的XML数据集群[Lee 等人
2002; Viyanon等。 2008]。这允许系统集成商专注于每个集群中的XML数据。我们注意到，协调类似的XML数据比协调结构和语义不同的XML数据更容易，因为后者涉及更多的重组。
在XML数据集成中有两种使用聚类的方向。
（1）确定跨XML数据的相似性矩阵，并将聚类算法应用于计算的相似性矩阵，产生类似XML数据的聚类。然后，整合每个集群中的XML数据[Lee 等2002]。
（2）每个XML数据树都聚集成子树，这大大减少了比较次数。然后测量基于每对子树的数据和结构的相似度。根据匹配子树的相似度的平均值计算数据树相似度。如果数据树相似度大于给定阈值，则可以集成两个XML文档[Viyanon 等人 2008]。
2.3. XML信息检索
传统信息检索（IR）系统[Singhal 2001]依赖布尔模型或向量空间模型来表示文档的平面结构作为一个单词包。已经提出了这些模型的扩展，例如，模糊布尔模型和知识感知模型。但是，所有这些索引模型都忽略了文本的结构组织。 XML文档具有由DTD或XML模式定义的层次结构。虽然这种结构允许文档用层次级别的粒度表示，以便通过聚焦检索实现更好的精度，但它意味着对表示和检索机制的更多要求。使用IR技术检索XML文档称为XML-IR。围绕XML检索的热情越来越高，形成了XML检索评估计划（简称INEX）.1自2002年以来每年组织一次，INEX是一个类似TREC2的论坛，参与的研究人员可以在这里讨论和评估他们的检索技术在相当大的相关性评估测试集合上使用统一评分程序。随着XML聚类技术的日益普及，INEX 2009包括一个聚类轨道，其中聚
全文共33234字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[1893]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
