XML文档的聚类研究尹路修

(湖南师范大学数学与计算机科学学院,中国 长沙　410081)



XML文档的聚类研究尹路修

(湖南师范大学数学与计算机科学学院,中国 长沙410081)

摘要随着互联网的迅速发展，XML已经成为互联网中最常用的数据交换与存储语言，如何从大量的XML文档中提取有价值的信息是目前的研究热点之一．本文提出了一种基于SET/BAG模型的改进的相似度计算方法．该方法将XML文档的每个节点转换成一个对象(由对象名、父对象、属性集合以及该对象相对于其父对象的权重组成)，能较完整地表达XML文档的结构信息，并且通过调整重复节点的权重来降低其在相似度计算中的影响．在真实数据集与人工数据集上分别进行实验，仿真实验结果表明，本文提出的基于SET/BAG模型下改进的相似度计算方法能得到很好的聚类结果．

关键词XML；文档聚类；相似度计算

在研究如何从大量的XML文档中提取有价值的信息时，关于XML文档的聚类[1]研究显得非常重要．通过XML文档的聚类，可以将大量的XML文档在未知类别的情况下进行分类整理，使用户可以用更短的时间获得更为完整和有用的信息．XML文档聚类研究主要有两大研究方向．一种是对聚类算法进行改进，使之能更好地结合XML文档的特点以及更好的聚类结果．目前主要的聚类算法[2-3]有基于划分的，基于层次的和基于密度的．另一种是对XML文档的表示模型进行改进，以便得到更有效率的相似度计算方法．目前主要的XML文档的表示模型[4-7]有3种，分别是SET/BAG模型，向量空间模型和树模型．本文着重对SET/BAG模型的相似度计算方法进行改进，提出一种基于SET/BAG模型改进的相似度计算方法．

1SET/BAG模型相似度计算

SET/BAG模型[8]是将XML文档用集合的形式来表示，通过Jaccard相似系数计算公式得到两个文档的相似度．设有2个XML文档集合，x1,x2，Jaccard相似系数计算公式：

(1)

基于SET/BAG模型的相似系数计算公式，再结合XML文档的自身特点，有以下几种相似度计算方法:

(1)节点比较法.节点比较法是将一个XML文档中的所有节点组合成一个集合，这个集合代表这个XML文档．相似度计算是使用Jaccard相似系数计算公式得到相似度．节点比较法只是简单地提取了XML文档中的节点，忽略了XML文档的结构信息，如XML文档结构中的父子关系，同时嵌套节点与重复节点带来的相似度计算的影响也并未得到解决．并且XML文档中层级越高的节点概括的信息量越大，层级越低的节点概括的信息量越小，但是在节点比较法中并未得到表现．

(2)边集比较法.边集比较法与节点比较法类似，只是集合中的节点不是XML文档里的元素，而是用表示父子关系的有向边．相似度计算方式与节点比较法一样，也是计算两个集合之间的交集除以两个集合之间的并集．边集比较法在一定程度上保存了XML文档中的父子关系，但和节点比较法一样也未能解决嵌套元素与重复元素的影响．

2基于SET/BAG模型改进的相似度计算

2.1基于SET/BAG模型改进的相似度计算

2.1.1XML文档的数据预处理XML文档中的一个对象由一个四元组表达，即，O={Name，Parent，AttributeList，Weight}，其中Name:该对象的名字，Parent:该对象的父对象，AttrubuteList:该对象的属性集合，Weight:权重，是该对象相对于其父对象的重要度，如图1所示．在进行对象集合相似度计算之前，需要遍历XML文档中的每个节点并将其转换成一个对象．于是，计算两个XML文档的相似度时，即对这个XML文档的对象集合进行比较．

图1　XML文档示例Fig.1　XML document sample

名称父对象属性权重booknulltitle;publisher;year;author;price1titlebooknull0.2publisherbooknull0.2yearbooknull0.2authorbookfirstname;lastname0.2pricebooknull0.2firstnameauthornull0.5lastnameauthornull0.5

2.1.2节点对象的相似度计算在将数据处理成对象集合之后，需要进行对象的相似度计算．对象的相似度取决于对象名和对象的属性集合．两个XML文档的相似度等于两个XML文档的顶层对象的相似度．

设有对象P1和P2，P1的属性集合为{a11,a12，…，a1m}，P2的属性集合为{a21,a22,…,a2n}，对象的相似度计算公式：

(2)

基于SET/BAG模型改进的相似度计算算法采用递归的方式从顶层对象(树模型里的根节点)开始计算，通过动态规划算法的思想，分别求解出两个顶层对象下属性集合的相似度，然后将每个属性与各自对于顶层对象的权重相乘再累加除以2得到两个顶层对象的相似度，也就是XML文档的相似度，有两种情况：

(1)如果对象的属性集合为空，则比较对象名是否一样.当属性名一样时，判定两个属性的语义是否相同，若相同，则similaryValue=1，否则similaryValue=0．

(2)如果对象属性集合不为空，先比较对象名，如果相同，则比较其属性集合．先将两个对象的所有属性进行两两比较，然后分别查找出相似度最大的值作为这两个属性的相似度，若没有匹配上的属性， similaryValue=0．

基于SET/BAG模型改进的相似度计算算法描述如下：

函数：compareObject

输入：O1，O2;// 顶层对象O1，顶层对象O2

输出：similaryValue；//两个对象集合的相似度值

方法:

(1)比较顶层对象名是否相同，如果相同，则跳入(2)；

(2)比较两个对象的属性集合，

If(其中一个对象的属性集合为空，而另一个对象的属性集合不为空){

similaryValue = 0;

返回 similaryValue;

}else if (两个对象的属性集合都为空){

If(o1.name == o2.name){

similaryValue = 1;

}else{

similaryValue = 0;

}

返回similaryValue;

}else{

Repeat

//将两个对象的属性集合进行两两对比，跳入(1);

//将相似度最大的两个属性划分为一组，得到的相似度结果为这两个属性的相似度;

Until

//所有属性比较完毕

//跳入(3)

}

(3)分别乘以这个属性在该对象的权重，得到最终带权重的相似度，代入公式(1)中，得到两个顶层对象的相似度．

基于SET/BAG模型改进后的相似度计算方法结合了语义相似度的比较，并未通过语义词典来得到两个属性的语义相似度．由于目前的语义词典如WordNet存在一些不足的地方如合并词汇与缩写词汇不能计算相似度，例如图3.1中firstname是由first和name合并的，但是在语义词典里面不能被识别．还有语义词典中的词汇不完善，简写词汇和专业术语的单词如VSM是Vector Space Model的简写，但是在语义词典中也不能被识别．因此，改进后的相似度计算方法并未采用语义词典进行相似度的计算．

在嵌套节点与重复节点的处理方面，由于基于SET/BAG模型改进后的相似度计算方法将节点转换成对象处理，而对象包含了名称与属性，所以对于嵌套节点不会影响相似度的计算．而在重复节点的处理上，通过在XML文档的预处理中，降低重复节点的权重，减少重复节点在相似度计算中的影响．

2.2实验结果

为了验证基于SET/BAG模型改进的相似度计算方法的有效性，使用NIGARA数据集(actor, movies, department, club, bib)，分别从actor类中抽取117个文档，moives类中抽取282个文档，department类中抽取19个XML文档，club类中抽取12个文档，bib类中抽取16个文档，总计446个文档进行混合．分别使用SET/BAG模型下的节点比较法、树模型下的树编辑距离和基于SET/BAG模型下改进的相似度计算方法与DBSCAN聚类算法结合对XML文档进行聚类．节点比较法与树编辑距离法是XML文档相似度计算中有代表性的计算方法．并且通过与节点比较法和树编辑距离法进行对比，能很好地表现出基于SET/BAG模型改进的相似度计算方法在XML文档结构特征的存储与对重复节点和嵌套节点的处理上有很大的提升．实验结果如表2所示.

表2　NIGARA数据集的聚类结果

由于NIGARA数据集中的部分类别重复节点较多，对树编辑距离的影响较为严重，节点比较法其次．并且因为club,department和bib类别的XML文档较少而重复节点在这些类别中有些文档出现次数较多，有些文档次数较少，导致基于树编辑距离的DBSCAN算法将这些类别中的XML文档计算成孤立点并排除在外，所以树编辑距离的聚类结果不理想．而改进后的SET/BAG模型相似度计算方法由于将重复节点的权重进行调整，能很好地消除重复节点的影响．

为了防止单一数据集带来的偶然性，本文使用XML Generator人工生成XML文档数据集，此人工数据集分为3类，分别通过play.dtd，dblp.dtd和SigmodRecord.dtd生成150个XML文档，其中play.dtd有45个文档， dblp.dtd有65个文档， SigmodRecord.dtd有40个文档．实验结果如表3所示.

表3　人工数据集的聚类结果

人工生成的数据集由于重复节点较少，因此，节点比较法和树编辑距离的表现比在NIGARA数据集要好，但是仍然不能将所有数据集放入正确的簇集中．而基于SET/BAG改进的相似度计算方法始终能够得到很好的聚类结果．

参考文献：

[1]ALSAYED A, MARCO M, RICHI N,etal. XML data clustering:an overview[J]. ACM Comput Surv, 2011,43(4):25.

[2]ANAND R, JEFFREY D U. Mining of Massive Datasets[M].Cambridge: Cambridge University Press， 2011.

[3]周水庚，周傲英.一种基于密度的快速聚类算法[J].计算机研究与发展， 2000，37(11)：1287-1292.

[4]BERTINO E, GUERRINI G, MESITI M. Measuring the structural similarity among XML documents and DTDS[EB/CD].Technical Report DISI-TR-02-02,Department of Computer Science, University of Genova, 2002.

[5]FLESCA S, MANEO G, MASCIARI E,etal. Detecting structural similarities between XML documents[C]// Proceedings of the 5th International Workshop on the Web and Databases, Madison, Wisconsin, 2002:55-60.

[6]SALTON G, WONG A, YANG C S. A vector space model for automatic indexing[J]. Comm ACM, 1975，18(11):613-620.

[7]LEE J W, LEE K, KIM W. Preparations for semantics-based XML mining[C]//Proceedings of the 2001 IEEE International Conference on Data Mining, San Jose, 2001:345-352.

[8]ANDREA T, SERGIO G. Semantic clustering of XML documents[J]. ACM Trans Inform Syst, 2010，28(1):1-56.

(编辑胡文杰)

Clustering Research on XML Document

YINLu-xiu*

(College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China)

AbstractWith the rapid development of Internet, XML has become the most commonly used language for the Internet data exchange and storage. How to extract valuable information from a large number of XML document is one of the hottest research topics currently. This paper proposes a model based on the SET/BAG improved similarity calculation method, which converts each node of the XML document to an object (the object name, object, attribute set, and the weight of the object relative to the parent object) and can fully express the structure of an XML document information, by adjusting the repeated node weights to reduce its influence in similarity calculation. Based on real data sets and artificial datasets experiments respectively, the simulation experimental results show that the proposed method in this paper based on the SET/BAG model improved similarity calculation can get good clustering results.

Key wordsXML; document clustering; similarity computation

中图分类号TP391.1

文献标识码A

文章编号1000-2537(2015)05-0091-04

通讯作者*,E-mail：55749691@qq.com

收稿日期：2015-02-17

DOI:10.7612/j.issn.1000-2537.2015.05.015