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

《智能信息系统》课程论文基于结构与内容相融合的XML文档聚类研究姓名：祝黎学号：2012201040008院系：信息管理学院专业：管理科学与工程年级：12级硕士基于结构与内容相融合的XML文档聚类研究祝黎（武汉大学信息管理学院，湖北武汉430072）摘要本文分析了国内外已有的XML文档聚类技术，对XML聚类技术进行了研究，提出了一种将文档结构和内容相融合的聚类方法——两阶段聚（TPCM：TwoPhaseClusteringMethodofXMLDocuments）。该方法首先采用传统的相似度计算和K-means聚类算法对XML文档结构进行大类的聚类，然后利用改进的数路径模型方法对大类进行更有效、更准确的XML文档分类。关键词xml；文档聚类；两阶段法；K-meansAbstractThispaperanalyzedthedomesticandforeignexistingXMLdocumentclusteringtechnique,theXMLclusteringtechniquesarestudied,thispaperputsforwardadocumentstructureandcontentoftheintegrationofclusteringmethod,TwoPhaseClusteringMethodofXMLDocuments.ThismethodfirstlyusestraditionalsimilaritycalculationandK-meanstoclustertheXMLdocumentstructuretypes,andbyusingtheimprovedmethodofpathmodelnumberofcategoriestogetmoreeffectiveandmoreaccurateclassificationoftheXMLdocument.Keywordsxml;documentclustering;TPCM;K-means1.引言我们正处在一个信息爆炸的时代，随着WEB网上信息的爆炸式增长，从半结构化文档（特别是XML文档）中提取信息变得越来越重要。目前互联网上已经形成了一个巨大的由XML格式数据构成的数据仓库。如何有效存储、索引、挖掘与利用XML数据已成为研究热点。XML是一种元标记语言，它提供描述结构化资料的格式，可用于创建标记语言。它以其良好的数据存储格式、可扩展性、高度结构化、便于网络传输等优点在许多领域应用，便于网页信息组织，不仅能满足不断增长的网络应用需求，而且还能确保在与网络进行交互时，具有良好的可靠性与互操作性。文本聚类是数据挖掘中的一项重要内容，它不但可以提高信息检索系统的查准率和查全率，还可以用来组织搜索引擎返回的结果，自动产生文本的层次簇或类，并利用这些簇或类对新文档进行归类。XML文本聚类的目标和普通的文本聚类一样，就是将XML文档集组成不同的类，使得类内文档之间的相似性尽量大，而类间的相似性尽量小。XML文档是信息与元信息的混合体，其“语义”可以看作是由文档内容和文档结构两部分构成。这里的内容是指元素值和属性值，结构是指由标记名称及标记之间的层次关系描述的元素值（属性值）之间的语义关系。而现有的XML文档聚类算法也根据上面的两种关系分为基于结构相似度和基于语义相似度两大类。但是这两大类其实都只考虑了XML文档的一个部分，在很多场合的应用是不合理的。：两个有截然不同结构的Schema可以有同样内容的文档实例，两个有截然不同内容的XML文档若他们的Schemas相似也可以聚类在一起。文献［1］提出将文本内容中的高频词和文档标记简单合并作为特征向量，引进向量空间法对文档进行聚类。这种方法虽然综合考虑了文档的内容特征和结构特征，但将两类特征看作是正交的，割裂了彼此之间的联系，显然与文档的特点不相符合。文献[3]提出了反映XML文档内容特征和结构特征的构件向量,在数据为中心的文档集中获得了较好的聚类效果。但是该方法在处理开放的、大规模的以文本为中心的XML真实数据时,会产生大量的构件向量,导致算法的执行效率大打折扣。而本文分析了国内外已有的XML文档聚类技术，对XML聚类技术进行了研究，提出了一种将文档结构和内容相融合的聚类方法——两阶段聚（TPCM：TwoPhaseClusteringMethodofXMLDocuments）。该方法首先采用传统的相似度计算和K-means聚类算法对XML文档结构进行大类的聚类，然后利用改进的数路径模型方法对大类进行更有效、更准确的XML文档分类。此方法可用于大量不同领域的文本挖掘和信息检索，提高信息检索的查准率和查全率，或作为查找最相似文档的有效方法。2.文档表示模型XML文档可以被模型化为有序标签树，图1给出了一个XML文档的例子及其树模型。树中有三类节点：○1元素节点(内部节点)，与XML文档中的标记对应，如Book；○2属性节点（内部节点），与标记内的属性对应，如category。○3值节点（叶子节点），与文档中的内容对应，如“HarryPorter”。树中的边表示元素、属性、值之间的关系。图1xml文档及其树模型定义1XML文档树：一棵XML文档树T是一个五元组T=N，E，r，L,S其中N是节点的有限集合r是树T唯一的根节点E⊂N×N是包含T父子关系的有限边集合s是包含XML文档中所有标签的有限集合，L：N→S是节点到标签的函数。定义2节点路径：一棵XML文档树中节点v的路径为从根节点到v节点所经过的标签列表记为path（v）。节点v的路径长度为path（v）中节点标签的个数，记为|path（v）|定义3节点层次:定义根节点的层次为1如果一个节点的父节点层次为n则该节点的层次为n+1文档d中节点v的层次数记为Level(v)。定义4词项权重w(,)表示词项对文档中的第j个标签的贡献程度,权值越大说明该词项对该节点的贡献越大,反之越小。传统的向量空间模型里，词项的权值通常简单地由词频和文档逆频率决定。在本文XML文档的表示模型中，词项是带有结构语义约束信息的。因此，词项权重不仅要考虑频率，还要考虑结构语义约束信息的影响。通过对XML文档表示模型的分析，我们认为有以下结构特征因素影响词项权重。（1）词项的元素频率传统的TFIDF方法中TF代表词项在文档中出现的频率。TF值越大，表示该词项在文档中出现的次数越多，越能够代表文档的主旨思想，从而越重要。在XML文档中，词项出现在不同的标签节点下。相似地，在某一标签下出现的次数越多，说明该词项对该标签片段的贡献程度越大，越能够反映该片段的中心意思，更能够代表该片段的内容。（2）词项的反比元素频率TFIDF方法中的IDF表示词项在整个文档集中的出现情况，用于区分其所在文档与其他文档的能力。通常，IDF值越小，说明该词项出现在很多文档里具有普遍性的含义，对文档的区分度不强。类似地，在XM文档中，如果很多标签节点下面都包含了某一词项，说明该词项很普通，对标签片段的区分贡献不大，无法体现各个片段的差别。相反地，如果某词项只在文档集中很少的标签节点中出现那么利用该词项就能够很好地将包含该词项的几个标签节点片段和文档集中的其他标签片段区分开来。（3）词项隶属元素的标签节点语义权重在XML查询处理中，查询词在文档或片段中出现的次数（频度）往往是很XMl查询处理模型重点考虑的因素。然而，在已有的很多XML查询处理方法中忽略了该关键词出现的位置。也就是说，关键词在XML文档或元素中出现的次数与其所在节点的标签是无关的[13]。从直观的感觉来看，对于相同的查询关键词，如果其所在的XML结点(标签)不同，则对相关度判断的影响也不应相同。例如，在以文本为中心的XML数据上进行查询时，用户给出的CO查询为“XMLretrieval”如果在一个XML文档(或元素)中“XMLretrieval”所在结点标签为“abstract”(摘要)。而在另一个XML文档（或元素）中查询关键词所在结点（标签）为“reference”(参考文献)，在其他统计信息相同的情况下，显然，前者与查询应该更相关。相应地XML文档（或元素）在排序中应该更靠前。因此，XML文档集中不同元素标签名对文档内容的贡献程度是不同的，需要区分对待[12]。(4)词项隶属元素节点的层次分析XML文档的树形结构，出现在不同层次的叶节点中的词项对文档内容的贡献程度不同。通常越靠近根节点层次中的叶节点词项对XML文档越重要，对类别划分的影响也越大，反之越小。例如ss1是sec节点的孩子节点，st节点既在sec标签下出现，又在ss1标签节点下面出现。在sec标签下st代表整个sec段落的标题，是对整个片段进行解释概括，在ss1标签下，st代表ss1片段的标题，对ss1标签下的内容进行概括。显然，文档中一级标题包含的词项对文档主题的贡献要大于二级标题包含的词项对于文档主题的贡献。所以，仅仅考虑元素的语义标签权重是不够的，特别是对同一标签而言，层次高的元素中词项的权重要大于层次低的元素中词项的权重。综合上述分析词项权值计算如公式（1）～（2）所示。W(,)=*(ln(tf(,)+1))*IEF()(1)IEF()=1+log(2)其中,表示文档中第j个标签节点,w(,)表示词项在标签中的权重w()是标签的节点语义权重tf(,)表示词项在标签下出现的频率lEF(是词项的反比元素频率。类似于传统信息检索中的反比文献频率，即包含词项的元素节点在整个数据集中元素节点里所占的比重。N为整个数据集中元素节点的个数,是包含词项tk的元素节点个数。Level()表示标签节点在文档中的层次数。定义5词项的文档权重wtk,di:指某词项tk对文档的贡献程度。词项tk在文档中可能出现在不同的标签节点下,具有不同的词项权值。将该词项的不同权值进行累加,即可得到该词项的文本权重值。=mjw1(,)(3)其中,m表示文档中词项tk出现的叶子节点数目。定义6相似度:两文档之间相似的距离程度计为相似度。文档、相似度定义为向量之间的夹角余弦,XML文档由相互独立的词条组,,…构成,每一个词条(1≤i≤n)出现在文档的不同标签节点下面,具有不同的权重。因此,对词项权重的计算需要考虑结构语义因素。具体公式如下所示:Sim(,)=(4)3.第一阶段XML聚类第一阶段聚类工作从XML文档集中识别出了具有相同结构的XML文档，根据XML文档结构进行聚类，更好地组织和管理了信息。第一阶段聚类算法提出利用XSLT产生XML文档结构的数据框架，将其模型化成树后，通过去除重复路径和任何与结构无关的内容后得到简化结构树；以简化结构树路径作为结构单元，将XML文档中的每个结构单元看作一个向量，整个XML文档则被量化为一组向量，以一个矩阵来表示；最后利用文档结构相似度计算和K-means聚类算法，对XML文档集进行了第一阶段聚类，产生具有基本相似结构的XML文档分类集合。3.1文档结构相似度计算第一阶段聚类算法的XML文档结构相似度计算：1、计算文档和相似度时，对中每条路径记下它被中路径((1≤k≤n，其中n为中的路径数目)匹配的次数，对文档中所有路径的匹配次数初始值设match_count()=1；2、对于中的每条路径,在文档中寻找它的最佳匹配路径(1≤k≤m，其中m为中的路径数目)，计算sim(，)，并且与的匹配次数加1；3、依据公式(5)计算Ti中每一条路径(1≤k≤n)在文档的相似度Lsim()；LSim()=(5)4、文档={，,…}，={,，…)，它们之间相似度计算公式如下所示：Sim(,)=(6)3．2K—means算法k—means算法是一种基于样本间相似性度量的间接聚类方法，属于非监督学习方法。此算法以k为参数，把n个对象分为k个簇，以使簇内具有较高的相似度，而且簇间的相似度较低。相似度的计算根据一个簇中对象的平均值(被看作簇的重心)来进行。此算法首先随机选择k个对象，每个对象代表一个聚类的质心。对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚