XML文档聚类研究与应用-计算机科学与技术专业论文.docxVIP

承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果。除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 （必威体育官网网址的学位论文在解密后适用本承诺书） 作者签名： 日 期： 南京航空航天大学硕士学位论文 南京航空航天大学硕士学位论文 XML XML 文档聚类研究与应用 I I II II 摘 要 XML(eXtensible Markup Language)是因特网中信息描述、传输和交换的重要标准，而 XML 文档聚类是众多 XML 文档整合和管理技术中关注的焦点，其目标是有效整合 XML 文档使之便 于存储和传输。相似度计算则是 XML 文档聚类的关键步骤，而传统 XML 文档相似度计算方法 中，树编辑距离算法时间复杂度较高，元素比较法丢失文档结构特性，边与路径比较法过于局 限，扩展性差，而向量空间计算法虽计算简便，但多数算法因其特征权重设定导致无法完整保 留文档结构特性。 论文着眼于 XML 文档的特征权重设定，分别从相似度计算和聚类算法选择两方面进行研 究，并取得了如下成果： 1、论文研究了计算 XML 文档相似度的 pq-gram 算法。XML 文档的结点在不同 XML 文档 树中所处层次以及本层次中位置都会有所不同，而这些不同正是 XML 文档结构特性的一种体 现，但 pq-gram 算法在提取 pq-gram 时未考虑这一点。鉴于此，论文提出了一种新的带权 pq-gram 算法，通过全面考虑 XML 文档树中结点的层次及位置，结合其父节点所处的位置，为 XML 文 档结点以及 pq-gram 设计了全新的权重设定方法，并在权重设定的基础上改进了其相似度计算 方法。最后通过聚类算法对三个真实数据集进行聚类，比较聚类精度的优劣以及各聚类簇之间 的相似度。 2、在此基础上，论文进一步研究了常见的 XML 文档特征向量提取方法,发现大多数特征提 取算法只是针对 XML 文档结构特性对特征进行权重设定，未考虑各特征之间是存在偏好关系 的。事实上，XML 聚类不能完全通过结点在 XML 文档中的层次来判定它对于聚类的重要性。 论文在此基础上研究了基于特征偏好的聚类(Clustering with feature order preference, CFP)算法。 论文在带权 pq-gram 算法对 XML 文档进行特征向量提取的基础上，结合 CFP 算法，提出了基 于特征偏好的 XML 文档聚类(CXFP）算法。CXFP 算法可结合 pq-gram 权重以及特征偏好权重 两个方面，并利用 CFP 算法的特点，在聚类过程中动态调整特征偏好权重。实验表明 CXFP 算 法通过加入了特征偏好，可显著提高聚类的精度。 3、分析了当前国内机场噪声现状，并介绍了对其分析研究的必要性，在此基础上，将 CXFP 算法应用于机场噪声数据的聚类中，根据不同的聚类需求为数据特征设定偏好权重，实验结果 表明，CXFP 算法较之其他聚类算法可以取得较优的聚类效果。 关键字：相似度计算，XML 文档聚类，权重，特征偏好，机场噪声 ABSTRACT XML(eXtensible Markup Language) is an important standard for describing, transferring and exchanging information in Internet, and clustering for XML documents is focus of lots of technologies for integrating and managing them. The target of clustering XML documents is to integrate them effectively for convenience store and management. Calculating similarity of XML documents is the pivotal step of clustering, among lots of traditional algorithms of calculating similarity, the Time complexity of tree edit distance algorithm is too high, tag similarity algorithm lost th