基于频繁子树挖掘的XML聚类方法研究

摘要

XML数据由于其开放性、通用性、半结构化等特性，已经成为互联网上数据表示和交换的标准。随着XML应用的不断扩展，大量数据源产生出千差万别的XML文档，它们所遵循的文档模式(DTD或XML Schema)也各不相同。对异源XML数据集合进行处理的一个关键技术，是将XML文档根据结构相似性进行分类并提取DTD。基于同一DTD的XML文档间会有较多的相同子结构，对于规模较大的XML文档集而言，表现为频繁子树。本文研究基于频繁子树的XML聚类算法。主要工作包括：
　　 1、概述现有的针对XML文档的聚类方法，指出这些方法的不足之处，提出了新的解决的思路，即基于频繁子树进行聚类，并阐述了理论依据。
　　 2、在经典频繁子树挖掘算法FREQT的基础上，引入了等价类扩展的思想，提出了FROTreeMiner算法，该算法大大减少了产生的候选子树数目，可用于挖掘频繁递归有序子树。
　　 3、基于频繁子树挖掘结果，本文提出两种XML文档相似度计算方法：第一种方法结合了向量空间模型和频繁子树构建频繁结构特征向量，通过特征向量来计算相似度。第二种方法先构建了全局的频繁子树包含关系表，通过该表可以找出文档包含的最大频繁子树和文档间最大的共有频繁子树，并以此为基础定义了XML文档相似度计算公式。在得到文档的相似度后，通过最小生成树来进行XML文档的聚类。
　　 4、实验表明了(1)FROTreeMiner频繁子树挖掘算法效率高于经典算法FREQT。(2)基于频繁子树的聚类算法在应用于XML文档分类时，比传统算法具有更高的准确率和性能。