基于结构与内容相融合的XML文档聚类研究(智能信息系统)

1、智能信息系统课程论文基于结构与内容相融合的XML文档聚类研究姓名： 祝 黎 学号： 2012201040008 院系： 信息管理学院 专业： 管理科学与工程 年级： 12级硕士 基于结构与内容相融合的XML文档聚类研究祝黎（武汉大学 信息管理学院，湖北 武汉 430072）摘 要 本文分析了国内外已有的XML文档聚类技术，对XML聚类技术进行了研究，提出了一种将文档结构和内容相融合的聚类方法两阶段聚（TPCM：Two Phase Clustering Method of XML Documents）。该方法首先采用传统的相似度计算和K-means 聚类算法对XML文档结构进行大类的聚类，然后利

2、用改进的数路径模型方法对大类进行更有效、更准确的XML文档分类。关键词 xml；文档聚类；两阶段法；K-meansAbstract This paper analyzed the domestic and foreign existing XML document clustering technique, the XML clustering techniques are studied, this paper puts forward a document structure and content of the integration of clustering method, Two

3、Phase Clustering Method of XML Documents. This method firstly uses traditional similarity calculation and K - means to cluster the XML document structure types, and by using the improved method of path model number of categories to get more effective and more accurate classification of the XML docum

4、ent.Keywords xml; document clustering;TPCM;K-means1.引言我们正处在一个信息爆炸的时代，随着WEB网上信息的爆炸式增长，从半结构化文档（特别是XML文档）中提取信息变得越来越重要。目前互联网上已经形成了一个巨大的由XML格式数据构成的数据仓库。如何有效存储、索引、挖掘与利用XML数据已成为研究热点。XML是一种元标记语言，它提供描述结构化资料的格式，可用于创建标记语言。它以其良好的数据存储格式、可扩展性、高度结构化、便于网络传输等优点在许多领域应用，便于网页信息组织，不仅能满足不断增长的网络应用需求，而且还能确保在与网络进行交互时，具有良好的可

5、靠性与互操作性。文本聚类是数据挖掘中的一项重要内容，它不但可以提高信息检索系统的查准率和查全率，还可以用来组织搜索引擎返回的结果，自动产生文本的层次簇或类，并利用这些簇或类对新文档进行归类。XML文本聚类的目标和普通的文本聚类一样，就是将XML文档集组成不同的类，使得类内文档之间的相似性尽量大，而类间的相似性尽量小。XML文档是信息与元信息的混合体，其“语义”可以看作是由文档内容和文档结构两部分构成。这里的内容是指元素值和属性值，结构是指由标记名称及标记之间的层次关系描述的元素值（属性值）之间的语义关系。而现有的XML文档聚类算法也根据上面的两种关系分为基于结构相似度和基于语义相似度两大类。但

6、是这两大类其实都只考虑了XML文档的一个部分，在很多场合的应用是不合理的。：两个有截然不同结构的Schema可以有同样内容的文档实例，两个有截然不同内容的XML文档若他们的Schemas相似也可以聚类在一起。文献1提出将文本内容中的高频词和文档标记简单合并作为特征向量，引进向量空间法对文档进行聚类。这种方法虽然综合考虑了文档的内容特征和结构特征，但将两类特征看作是正交的，割裂了彼此之间的联系，显然与文档的特点不相符合。文献3提出了反映XML文档内容特征和结构特征的构件向量,在数据为中心的文档集中获得了较好的聚类效果。但是该方法在处理开放的、大规模的以文本为中心的XML真实数据时,会产生大量的构

7、件向量,导致算法的执行效率大打折扣。而本文分析了国内外已有的XML文档聚类技术，对XML聚类技术进行了研究，提出了一种将文档结构和内容相融合的聚类方法两阶段聚（TPCM：Two Phase Clustering Method of XML Documents）。该方法首先采用传统的相似度计算和K-means 聚类算法对XML文档结构进行大类的聚类，然后利用改进的数路径模型方法对大类进行更有效、更准确的XML文档分类。此方法可用于大量不同领域的文本挖掘和信息检索，提高信息检索的查准率和查全率，或作为查找最相似文档的有效方法。2.文档表示模型XML文档可以被模型化为有序标签树，图1给出了一个XML

8、文档的例子及其树模型。树中有三类节点：元素节点(内部节点)，与XML文档中的标记对应，如Book；属性节点（内部节点），与标记内的属性对应，如category。值节点（叶子节点），与文档中的内容对应，如“Harry Porter”。树中的边表示元素、属性、值之间的关系。图1 xml文档及其树模型定义1 XML文档树： 一棵XML文档树T是一个五元组T=<N，E，r，L ,S > 其中N是节点的有限集合 r是树T唯一的根节点 EN×N是包含T父子关系的有限边集合 s 是包含XML 文档中所有标签的有限集合， L：NS 是节点到标签的函数。定义2 节点路径： 一棵XML文档树

9、中节点v的路径为从根节点到v节点所经过的标签列表 记为path（v）。节点v的路径长度为path（v）中节点标签的个数，记为|path（v）|定义3 节点层次: 定义根节点的层次为1 如果一个节点的父节点层次为n 则该节点的层次为n+1 文档d 中节点v的层次数记为Level(v)。定义4 词项权重w(tk ,ij) 表示词项tk对文档dj中的第j个标签ij的贡献程度, 权值越大 说明该词项对该节点的贡献越大, 反之越小。传统的向量空间模型里，词项的权值通常简单地由词频和文档逆频率决定。在本文XML文档的表示模型中，词项是带有结构语义约束信息的。因此，词项权重不仅要考虑频率，还要考虑结构语义约

10、束信息的影响。通过对XML文档表示模型的分析，我们认为有以下结构特征因素影响词项权重。（1） 词项的元素频率传统的TF*IDF方法中TF代表词项在文档中出现的频率。TF值越大，表示该词项在文档中出现的次数越多，越能够代表文档的主旨思想，从而越重要。在XML文档中，词项出现在不同的标签节点下。相似地，在某一标签下出现的次数越多，说明该词项对该标签片段的贡献程度越大，越能够反映该片段的中心意思，更能够代表该片段的内容。（2） 词项的反比元素频率TF*IDF方法中的IDF表示词项在整个文档集中的出现情况，用于区分其所在文档与其他文档的能力。通常，IDF值越小，说明该词项出现在很多文档里具有普遍性的含

11、义，对文档的区分度不强。类似地，在XM文档中，如果很多标签节点下面都包含了某一词项，说明该词项很普通，对标签片段的区分贡献不大，无法体现各个片段的差别。相反地，如果某词项只在文档集中很少的标签节点中出现那么利用该词项就能够很好地将包含该词项的几个标签节点片段和文档集中的其他标签片段区分开来。（3） 词项隶属元素的标签节点语义权重在XML查询处理中，查询词在文档或片段中出现的次数（频度）往往是很XMl查询处理模型重点考虑的因素。 然而，在已有的很多XML查询处理方法中忽略了该关键词出现的位置。也就是说，关键词在XML文档或元素中出现的次数与其所在节点的标签是无关的 13 。从直观的感觉来看，对于

12、相同的查询关键词，如果其所在的XML结点(标签)不同，则对相关度判断的影响也不应相同。例如，在以文本为中心的XML数据上进行查询时，用户给出的CO查询为“XML retrieval ”如果在一个XML文档( 或元素 )中 “XML retrieval” 所在结点标签 为“abstract”( 摘要)。 而在另一个XML文档（ 或元素）中查询关键词所在结点（标签） 为 “reference”( 参考文献)， 在其他统计信息相同的情况下， 显然， 前者与查询应该更相关。 相应地XML文档（或元素）在排序中应该更靠前。因此，XML文档集中不同元素标签名对文档内容的贡献程度是不同的，需要区分对待 12

13、。(4) 词项隶属元素节点的层次分析XML文档的树形结构，出现在不同层次的叶节点中的词项对文档内容的贡献程度不同。通常越靠近根节点层次中的叶节点词项对XML文档越重要，对类别划分的影响也越大， 反之越小。例如ss1 是sec节点的孩子节点，st节点既在sec标签下出现，又在ss1 标签节点下面出现。在sec标签下st代表整个sec段落的标题，是对整个片段进行解释概括，在ss1 标签下，st代表ss1 片段的标题，对ss1标签下的内容进行概括。显然，文档中一级标题包含的词项对文档主题的贡献要大于二级标题包含的词项对于文档主题的贡献。所以，仅仅考虑元素的语义标签权重是不够的，特别是对同一标签而言，

14、层次高的元素中词项的权重要大于层次低的元素中词项的权重。综合上述分析 词项权值计算如公式（1）（2）所示。W(tk , ij) =w(ij)Level(ij)2 * (ln( tf (tk ,ij) + 1) * IEF(tk) (1)IEF(tk) = 1+ logNNk (2)其中, ij表示文档di中第j个标签节点, w(tk , ij)表示词项tk在标签ij中的权重 w( ij)是标签ij的节点语义权重tf(tk ,ij) 表示词项tk在标签ij下出现的频率 lEF( tk)是词项tk的反比元素频率。类似于传统信息检索中的反比文献频率，即包含词项tk的元素节点在整个数据集中元素节点里所

15、占的比重。N为整个数据集中元素节点的个数,Nk是包含词项tk的元素节点个数。Level(ij) 表示标签节点ij在文档di中的层次数。定义5 词项的文档权重w<tk , di> :指某词项tk对文档di的贡献程度。词项tk在文档di中可能出现在不同的标签节点下,具有不同的词项权值。将该词项的不同权值进行累加,即可得到该词项的文本权重值。Wik =(tk , ij) (3)其中, m表示文档di中词项tk出现的叶子节点数目。定义6 相似度: 两文档之间相似的距离程度计为相似度。 文档di、dj相似度定义为向量之间的夹角余弦,XML文档由相互独立的词条组< t1,t2 ,tn&g

16、t; 构成,每一个词条ti(1 i n)出现在文档的不同标签节点下面,具有不同的权重。因此,对词项权重的计算需要考虑结构语义因素。 具体公式如下所示: Sim(di , dj)=cos didj|di|*|dj|=k=1nwik*wjkk=1nwik2 *k=1nwjk2 (4)3.第一阶段XML聚类第一阶段聚类工作从XML文档集中识别出了具有相同结构的XML文档，根据XML文档结构进行聚类，更好地组织和管理了信息。第一阶段聚类算法提出利用XSLT产生XML文档结构的数据框架，将其模型化成树后，通过去除重复路径和任何与结构无关的内容后得到简化结构树；以简化结构树路径作为结构单元，将XML文档中

17、的每个结构单元看作一个向量，整个XML文档则被量化为一组向量，以一个矩阵来表示；最后利用文档结构相似度计算和K-means聚类算法，对XML文档集进行了第一阶段聚类，产生具有基本相似结构的XML文档分类集合。3.1文档结构相似度计算第一阶段聚类算法的XML文档结构相似度计算：1、计算文档Ti和Tj相似度时，对Ti中每条路径记下它被Ti中路径Lik(1kn，其中n为Ti中的路径数目)匹配的次数，对文档Ti中所有路径的匹配次数初始值设match _count(Lik)=1；2、对于Ti中的每条路径Lik ,在文档Tj中寻找它的最佳匹配路径Lik (1km，其中m为Tj中的路径数目)，计算sim(L

18、ik，Ljl)，并且与Lik的匹配次数加1；3、依据公式(5)计算Ti中每一条路径Lik(1kn)在文档Tj的相似度LsimTj (Lik)；LSimTj (Lik)=depth(LCATiTj(LikLjl)maxdepthLik, depthLjl×ln(e+matchLik-1) (5)4、文档Ti=Li1，Li2 , Lim，Tj=Lj1,Lj2，Ljm)，它们之间相似度计算公式如下所示：Sim(Ti, Tj)=k=1nLSimTj Lik×weight(Lik)k=1nweight(Lik) (6)32 Kmeans算法kmeans算法是一种基于样本间相似性度量的

19、间接聚类方法，属于非监督学习方法。此算法以k为参数，把n个对象分为k个簇，以使簇内具有较高的相似度，而且簇间的相似度较低。相似度的计算根据一个簇中对象的平均值(被看作簇的重心)来进行。此算法首先随机选择k个对象，每个对象代表一个聚类的质心。对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚类中。然后，计算每个聚类的新质心。重复上述过程，直到准则函数会聚。K-means算法是一种较典型的逐点修改迭代的动态聚类算法，其要点是以误差平方和为准则函数。逐点修改类中心：一个象元样本按某一原则，归属于某一组类后，就要重新计算这个组类的均值，并且以新的均值作为凝聚中心点进行下一

20、次象元素聚类；逐批修改类中,G-在全部象元样本按某一组的类中心分类之后，再计算修改各类的均值，作为下一次分类的凝聚中心点。这个算法重复的部分，从最近的质心对每个映射元素开始一个嵌套循环，一个映射元素成为最近的质心簇的成员。簇被形成后，新的质心被计算。这些新的质心在下一个反复中表现簇。k-mems聚类算法的复杂度是O(C·I·|ME|)，而c是形成簇的数目，I是反复的数目ME是在知识库schema中的所有映射元素的集。33第一阶段聚类中Kmeans算法实现第一阶段聚类实现步骤：输入：聚类个数k，以及包含n个数据对象的数据库。输出：满足方差最小标准的k个聚类。处理流程：1、给定

21、文档集和它们对应的对象代表，从n个数据对象任意选择k个对象作为初始聚类中心；2、循环(3)到(4)直到每个聚类不再发生变化为止3、根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；两个聚类中心(C1，C2)之间的相似度：Cos（C1，C2）=（C1 ，C2）C1|C2| (7)4、重新计算每个(有变化)聚类的均值(中心对象)第一阶段聚类算法把XML文档之间结构的相似度值看成一个对象，接受输入量k；在满足同一聚类中的对象相似度较高而不同聚类中的对象相似度较小的条件下，将n个数据对象划分为k个聚类。利用各聚类中对象的均值获得一个“中心对象”

22、，利用文档结构相似度值与聚类中心之间的相似度值来进行聚类。第一阶段聚类完成后，k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。在数据量较小时，具有较好的聚类效果，当处理大规模数据时，时间复杂度也是O(n)，聚类效果较差，计算量会增加。4.第二阶段XML聚类在第一阶段聚类产生的文档集合中，按照第二阶段聚类算法产生DOM树路径，提取特征库计算权重值，利用文档结构相似度计算公式计算相似度，使用聚类算法实现XML文档集的第二阶段聚类。本文所采用的两阶段聚类法如图2所示：图2 XML两阶段聚类模型5.实验过程与结果分析本实验选用英文的ACMSIGMOD数据集进行试验分析。ACMS

23、IGMOD数据集是由数百篇XML格式的ACMSIGMOD论文组成，其文档结构如图3所示：图3 ACMSIGMOD的XML文档的DOM树51实验步骤1、读入XML文档集，按照图33的处理过程，使用结构分析器分析XML文档，利用XSLT样式表产生XML文档的结构，产生与源XML文档相关联的数据元素的框架，同时简化结构框架树；2、在步骤1基于改进的结构向量空间模型的基础上，对各结构单元进行向量赋值，并进行文档结构相似度计算；3、利用Kmeans聚类算法聚类文档，把相似文档放入同一文件夹中；4、在第一阶段聚类的基础上，对聚类的结果再一次按照第二阶段聚类的方法进行聚类分析，读入同一文件夹下的XML文档集

24、；5、对读入的XML文档解析成DOM树，生成树路径和其权重；6、对两文档中的两条路径进行相似度计算，再进行两文档之间的相似度计算；7、利用Kmeans算法进行文档聚类，输出结果，进行对比，计算准确率。52 测试结果衡量指标衡量信息检索性能的召回率和精度是衡量分类算法效果的常用指标，然而聚类过程中并不能像分类一样直接以精度和召回率作为评价标准。而本测试的聚类准确性是通过计算严格按照XML文档的类别数目进行聚类后的正确的XML文档数目除以总的XML文档数得出准确率。定义为：P=ID×100 (8)其中，I表示聚类后分类正确的XML文档数目，D表示XML文档集合所有XML文档数目。另外，设

25、M为聚类错误的XML文档数目，T为进行XML文档聚类的时间代价。表1 聚类准确性测试对比XML文档集合K值树路径改进后的树路径方法本文TPCM方法K错（M）精准率（P）错（M）精准率（P）错（M）精准率（P）第一组5599.5%0100%799.3%第二组637805%696.8%796.3%第三组76965.5%4080%398.5%第四组84379.5%3981.4%498.1%第五组95872.9%5474.7%2090.7%实验结果表明采用两阶段法对XML文档进行聚类错误率更低，精准率更高。6.总结XML已经被证实在互联网上传输和共享数据的过程中是有效的，而且许多公司想利用其优势来分析

26、数据。当XML文档资料太多时，由于它们的不同种类和不规则的结构使得从XML资源中获取知识的能力降低。通过新的研究工作的发展，在挖掘过程中应用XML数据已经成为可能。在国内外相关技术的发展下，XML文档的挖掘技术方面存在广泛的成就，本文在研究以上技术的基础上，提出两阶段聚类的思想，先采用简化XML文档结构，基于结构的向量空间模型来聚类文档，在形成的第一阶段聚类文档集合的基础上，再在小的集合中采用改进的树路径模型的方法第二阶段聚类文档。以达到提高识别具有相同结构文档的能力，使其能快速、准确分辨出具有相同结构的文档，同时简化文档描述，以降低解决问题的复杂度，使文档的聚类效果更佳。在基于文档结构向量空

27、间模型方法上进行了改进，在基于树路径模型的方法上对其方法存在的一些不足进行了创新和改进，有效地考虑了兄弟节点之间关系和树路径相似度计算时的路径重复匹配问题，提高了聚类精确度。参考文献：1 郝晓丽，冯志勇. XML结构聚类天津大学.2005.2 潘有能文档自动聚类研究情报学报，2006.3 谌志群,王小华,王荣波.一种结构与内容相结合的文档聚类方法,2009.054 朱春磊. 基于结构向量空间和树路径模型的XML文档聚类技术研究, 2008,5 余宏，万常选. 基于XML的检索结果聚类方法，2010 6 钟敏娟基于内容与结构语义相融合的XML检索结果聚类，2012.05.7 郑仕辉，周傲英，张龙

28、7ABC 文档的相似测度和结构索引研究7 计算机学报，2003,26(9):1116-11228 杨建武，陈晓鸥基于核矩阵学习的XML文档相似度量方法叨软件学报，2006，179 Guo Yongming, Chen dehua and Le JIajinClustering XML Documents by Combining Content and Structure.200810 Sergio Greco , Francesco Gullo, Giovanni Ponti, Andrea Tagarelli. Collaborative clustering of XML documents.2012 .11 Sigmod xml 数据集. Available at: http:/ww