论文部分内容阅读
XML(eXtensible Markup Language)即可扩展的标记语言,由于具有简单、可扩展、互操作性强、开放性强等特点,正迅速成为一种与技术无关的数据交换的标准和传输格式。与HTML相比,XML具有更大的灵活性。它不仅可以用来标记无结构的文本信息,还可以标记高度结构化的规则数据(如数据库中的数据)。随着Web上XML数据的快速增长,如何帮助用户快速有效地检索大量的XML数据,得到想要的信息,便成为亟待解决的课题。文档聚类是一种帮助人们检索信息的有效手段。为了有效的分析XML文档中的信息,XML文档聚类研究也就成了当前研究的热点。对XML文档聚类的关键点是文档间相似性的度量,由于XML文档是一种半结构化的文本,其信息可以通过文档结构得以描述,所以并不是所有的文本相似性算法都适合于XML文本。目前XML文档相似性计算方法主要有:元素比较法、边集比较法和编辑距离法。元素比较法简单,速度快,但是只是考虑节点的个数但是没有考虑XML文档树的结构复杂性,聚类结果不是很理想。树编辑距离法考虑了XML文档树的结构复杂性和节点相似行,有着良好的聚类结果,但是时间复杂度较高。边集比较法的性能介于二者之间,因此本文对边集比较法进行了扩展,提出带权重的边集比较算法,通过消除XML文档树中的嵌套和重复节点有效的简化了XML标记树,并结合语义信息度量XML文档之间的相似度。得到XML概要树间的相似度后,利用划分聚类法,对XML文档进行聚类。基于经典的边集比较算法,本文做出了以下创新:一、提出了带权重的边集比较法的概念,对XML概要树上每一条边都根据结构复杂性和所处的层次,赋予一定的权重,加强了XML中结构和层次的重要性。二、结合语义信息计算XML概要标记树中有向边的相似性,得到在语义上等价的边的集合,以此确定两个XML概要树之间的相似度,增加了聚类的精确度。实验结果表明,基于语义的带权重的边集比较法有较好的聚类结果。