论文部分内容阅读
近几年来,随着社会信息化进程的不断深入发展,人类对信息的需求和依赖程度越来越高,如何从海量的信息资源中快速有效的获取有用的信息,已经成为研究的热点,这也给信息检索带来了极大的挑战。相似度的计算是文档检索、挖掘和文本聚类的基础,因此对相似度算法进行研究具有非常重要的意义,可以说文档相似度的计算直接影响了最后的检索结果。XML语言具有“自描述”、“树形结构”、“结构嵌套”等特点受到了业界的普遍欢迎和支持,越来越多的应用领域已经将其作为主要的存储格式和传输媒体。因此如何计算XML文档的相似度特别是它的结构相似度是目前研究的主要任务。通过对XML文档的不断深入研究,发现传统的相似度的计算方法已不能满足计算元素的嵌套结构的语义要求。用树的编辑距离来计算文档的相似度时,如果树描述全部结构信息,这样树的结构会非常庞大,并且树编辑距离方法对文档中元素重复和元素可选问题不能有效处理。另一方面,在因特网上通过搜索引擎检索信息时,出来的信息成千上万,而人们通常只关心检索的前20名,如何提高前20项(或前n项)与用户相关项的个数,即提高检索结果的准确性是研究的另外一个难题。为了解决上述问题,本论文,在文档对象树的基础上,提出了一种基于树路径的XML文档描述模型,并给出了相应的相似度算法,将问题有效地简化,从而降低了解决问题的复杂度。这种算法能快速、准确分辨出具有相同结构的XML文档。首先,本文提出了一种基于树路径模型的相似度算法,来实现对XML文档之间相似度的计算。该算法简化了XML文档描述,从而降低了解决问题的复杂度。此算法在文档类别数较少,且不同类别的文档的结构相差较大时,有很好的聚类效果。其次,在此算法的基础上,针对它存在的一些问题如:路径只是包含父/子这种祖先与子孙的关系,忽略了兄弟结点之间关系;没有考虑各路径的权重;并且在比较两路径的相似度时用的是路径的完全匹配等,本文对此一一进行了改进,并提出了改进后的相似度的计算方法。改进后的算法计算出来的相似度更准确,处理了文档中元素重复问题,使得计算结果也更符合人的直观理解。最后本文进行了实验测试,并且在计算文档相似度的基础上对文档进行了聚类,实验结果显示与其它算法相比,本文的方法更显著地提高了识别具有相同结构的XML文档的能力,在此基础上,通过对文档进行聚类,使具有相同特征或相似度值很大的文档归为一类,很好提高检索结果的准确性。