用于XML文档分类的语义相似度度量方法

摘要

本发明公开了一种用于XML文档分类的语义相似度度量方法，依次将每个文档分解为结构信息和内容信息；从内容信息中抽取关键字特征，构造关键字特征空间；从结构信息中抽取所有的路径，构造路径字典；统计关键字特征空间中每个关键字特征在每个文档的任意路径中出现的频率，同时包含该关键字特征和路径的文档个数以及包含该关键字特征的文档个数等信息，计算关键字特征空间中每个关键字特征在文档中的权重；根据余弦度量计算任意两个文档之间的相似度。本发明应用于XML文档的分类，可以提高准确率。

权利要求

1.一种用于XML文档分类的语义相似度度量方法，其特征在于：对于给定的XML文档集D，其中的第i个文档表示为di，设D中的文档分属于|C|个类别，C表示所有类别的集合，Ci表示文档集D中所有属于第i个类别的文档组成的集合，则为了计算文档之间的相似度，包括以下步骤：a.解析文档集中所有的XML文档，将每一个XML文档分解为结构信息和内容信息；

b.从内容信息中抽取关键字特征，构造关键字特征空间；

c.从结构信息中抽取所有的路径，构造路径字典；

d.统计关键字特征空间中每个关键字特征tk在每个文档的任意路径pathj中出现的频率tfi(tk，pathj)，同时包含该关键字特征和路径的文档个数df(tk，pathj)以及包含该关键字特征的文档个数df(tk)，并根据df(tk)进行关键字特征筛选；

e.计算路径字典中每条路径pathj的深度pl(pathj)，数据集中包含该路径的文档数df(pathj)及其权重wpathj，其中权重利用信息论中熵和信息增益的概念进行计算；

f.根据第d，e步得到的信息，利用下式计算关键字特征空间中每个关键字特征tk在文档di中的权重wik，然后将文档表示为关键字特征空间中的所有关键字特征组成的向量，其中每个分量表示对应的关键字特征tk在该文档中的权重；

g.根据余弦度量 计算任意两个文档di和dj之间的相似度。

说明书

用于XML文档分类的语义相似度度量方法

技术领域

[0001] 本发明属于数据识别技术领域，尤其是一种用于文档分类的相似度度量方法。

背景技术

[0002] XML作为互联网上数据表示和数据交换的标准，已得到广泛的应用。随着XML文档数量的不断增长，如何对XML数据进行有效的管理在数据库和信息检索领域变得越来越重要。在很多XML数据应用，例如版本控制、半结构化数据集成、XML文档分类/聚类、XML检索等领域，如何度量XML文档之间的相似度成为一个重要的问题，尤其在XML文档分类/聚类应用中，需要根据文档之间的相似度把XML文档归到不同的类别中。

[0003] 根据文献“Tekli J，Chbeir R，Yetongnon K.An overview on XML similarity：Background，current trends and future directions.Computer ScienceReview，2009，
3(3)：151-173.”，度量XML文档之间相似度的方法大体可分成基于编辑距离(ED，Edit Distance)的方法、基于信息检索(IR，Information Retrieval)的方法以及其它一些方法。

[0004] 基于编辑距离的方法一般都忽略了包含在文档中的内容信息，利用结构信息计算文档距离并进行分类，这种方法的缺点在于编辑距离的计算开销很大。文献“DalamagasT，Cheng T，Winel KJ，Sellis T.A methodology for clustering XML documents by structure.Information Systems，2006，31(3)：187-228.”首先对XML文档进行简化，得到文档的Summary Tree，然后计算Summary Tree之间的编辑距离来进行分类。虽然这种方法降低了计算树编辑距离的时间复杂性，但是Summary Tree并不能很好地保持原有文档的结构。文献“Xing G，Guo J，Xia ZH.Classifying XML Documents Based onStructure/Content Similarity.Comparative Evaluation of XML Information RetrievalSystems，2007，4518：444-457.”通过计算XML文档与Schema之间的编辑距离对XML文档进行分类，这种方法假设属于同一个类别的所有XML文档具有共同的Schema，并且该Schema可以得到。事实上属于同一类别的XML文档很多情况下并不具有共同的Schema，而且XML文档的Schema并非总是可以轻易获得，虽然文中提出了一种从XML文档中抽取Schema的方法，但这需要额外的开销。由于基于编辑距离的方法忽略了文档的内容，因而并没有利用关键字的语义信息。

[0005] 传统的基于信息检索的方法将文档表示为一个向量，向量的每个分量为该文档中所包含的关键字在该文档中的权重，然后任意两个文档之间的相似度可以转换为计算两个向量的距离。关键为如何计算关键字的权重，使用最多的方法是tf-idf公式，这种方法仅仅利用文档中的内容信息，并未考虑到XML文档中的结构信息，因此不完全适用于XML文档的相似度计算。针对XML文档，也有方法对tf-idf方法进行扩展，同时利用XML文档中的结构和内容信息，例如文献“袁家政，须德，鲍泓.基于结构与文本关键词相关度的xml网页分类研究.计算机研究与发展，2006，43(8)：1361-1367.”在计算关键字的权重时考虑了关键字出现在不同树节点的位置以及位置的权重，但仅仅考虑关键字在不同树节点的位置和位置权重还未能完全利用包含在其中的语义信息，比如还可以考虑包含关键字的路径的层次，包含路径的文档数以及同时包含路径和关键字的文档数等信息。

[0006] 文献“Zaki MJ，Aggarwal CC.XRules：an effective structural classifier for XML data.In：Getoor L，Senator TE，domingos P，Faloutsos C，eds.Proc.of the ninth ACM SIGKDDinternational conference on Knowledge discovery and data mining.Washington，D.C.：ACM，2003.316-325.”提出了一种基于规则的分类方法，首先从XML文档中挖掘频繁子树，然后利用这些频繁子树生成规则进行分类。这种方法假设属于同一类别的文档具有相同的子结构，事实上在很多情况下这个假设并不成立。文献“Theobald M，Schenkel R，Weikum Gerhard.Exploiting Structure，Annotation，and OntologicalKnowledge for Automatic Classification of XML Data.In：Christophides V，Freire J，eds.Proc.ofthe WebDB Workshop.San Diego，California：ACM，2003.1-6.”除了使用关键字作为特征外，还使用小枝(Twigs)和标签路径(Tag Paths)作为结构特征来构造特征空间，然后利用本体论和互信息来确定与某一个类别最相关的m个特征，然后根据这些类相关的特征来构造分类器。由于这种方法预先限制结构特征中只包含两层结构，在一定程度上破坏了XML的多层结构。文献“Wu JW，Tang J.A bottom-up approach for XMLdocuments classification.In：Desai BC，ed.Proc.of the 12th International DatabaseEngineering and Applications Symposium.Coimbra，Portugal：ACM，2008.131-137.”利用支持度和互信息的概念从文档中抽取与某一个特定类别相关的关键字，称为KeyTerm，然后找到包含这些Key Term的路径，称为Key Path，该类别的所有Key Path就构成了该类别的一个分类Model，然后通过计算XML文档与各个类别的Model之间的距离来对文档进行分类。作者同样利用了一个假设，即属于同一类别的XML文档的Schema是相似的，虽然并不要求Schema一定能够得到，但这个假设仍然在一定程度上限制了其应用的灵活性。

发明内容

[0007] 为了克服现有技术未充分考虑XML文档中关键字语义信息或者依赖于文档Schema的不足，本发明提供一种基于关键字语义信息的XML文档相似度度量方法，将XML文档表示为由关键字权重组成的向量，XML文档之间的相似度计算就可以转换为计算两个向量之间的距离问题，计算过程中不需要得到XML文档的Schema。本发明同时利用了XML文档中包含的结构信息和内容信息，较为充分地考虑包含在文档中的关键字的语义信息，比如关键字在不同路径中出现的次数，路径的深度，路径本身的分类能力，包含路径的文档个数，同时包含某一路径和关键字的文档个数等计算关键字的权重，并据此度量文档之间的相似度。如果将利用这种方法度量的文档之间相似度用于XML文档的分类时，可以提高分类的准确率。

[0008] 对于给定的XML文档集D，其中的第i个文档表示为di，设D中的文档分属于|C|个类别，C表示所有类别的集合，Ci表示文档集D中所有属于第i个类别的文档组成的集合。则为了计算文档之间的相似度，本发明解决其技术问题所采用的技术方案包括以下步骤：

[0009] 1.解析文档集中所有的XML文档，将每一个XML文档分解为结构信息和内容信息。

[0010] 2.从内容信息中抽取关键字特征，构造关键字特征空间。

[0011] 3.从结构信息中抽取所有的路径，构造路径字典。

[0012] 4.统计关键字特征空间中每个关键字特征tk在每个文档的任意路径pathj中出现的频率tfi(tk，pathj)，同时包含该关键字特征和路径的文档个数df(tk，pathj)以及包含该关键字特征的文档个数df(tk)，并根据df(tk)进行关键字特征筛选。

[0013] 5.计算路径字典中每条路径pathj的深度pl(pathj)，数据集中包含该路径的文档数df(pathj)及其权重wpathj，其中权重利用信息论中信息增益的概念进行计算。

[0014] 6.根据第4，5步得到的信息，利用下式计算关键字特征空间中每个关键字特征tk在文档di中的权重wik，然后将文档表示为由关键字特征权重组成的向量。

[0015]

[0016] 7.根据余弦度量计算任意两个文档(向量)di和dj之间的相似度。

[0017] 本发明的有益效果是：本发明较为全面地考虑了包含在XML文档中的关键字特征的语义信息，例如关键字出现在不同路径中的语义，路径的深度不同时的语义等等来计算XML文档之间的相似度，同时相似度的计算不依赖于XML文档的Schema，如果将这种方法应用于XML文档的分类，可以提高准确率。

[0018] 下面结合附图和实施例对本发明进一步说明。

附图说明

[0019] 图1为XML文档样例1及其树形表示；

[0020] 图2为XML文档样例2及其树形表示；

[0021] 图3为图1和图2中的XML文档样例经过解析之后得到的路径字典和关键字特征空间示例。(由于样例个数所限，图中关键字特征空间并未进行关键字特征筛选)；

[0022] 图4为XML文档语义相似度度量方法流程示意图。

具体实施方式

[0023] 1.与本发明有关的概念。

[0024] XML文档可以看作一颗无序标签树T：{V，E，R}，其中V是文档中所有标签元素节点和标签的属性构成的集合，E是所有从父节点到子节点的边构成的集合，R为根节点。如图1(a)中的XML文档就可以表示为(b)中的树。

[0025] 2.与本发明有关的一些性质。

[0026] 性质1.某一个关键字在文档的某一个路径中出现的次数越多，越能说明该文档的类别，权重越大。

[0027] 例如在图1的XML文档中，假设在路径articles/article/abstract中出现了5个关键字“XML”，而在另外一个文档的同样路径中，关键字“XML”仅出现了1次，则我们说第一个文档的类别更有可能是XML。

[0028] 性质2.出现在同一个文档中的关键字，其出现位置越靠近点，越能说明该文档所属的类别，权重越大。

[0029] 例如：假设某个文档的路径articles/article/title中包含关键字“XML”，而在另外的一个文档中，只有路径articles/article/content/chapter1中包含关键字“XML”，则我们认为第一个文档更有可能属于XML类别。

[0030] 性质3.一个文档中包含同一个关键字的路径越多，则这个关键字越能说明该文档所属的类别，权重越大。

[0031] 例如：假设在某个文档中，在路径articles/article/title和articles/article/abstract中都包含了关键字“XML”，而在另外一个文档中只有路径articles/article/abstract包含了关键字“XML”，则很明显第一个文档的类别更有可能是XML。

[0032] 针对给定的一个XML文档集D，本发明计算任意两个文档之间的相似度的具体流程如图4所示包括如下步骤：

[0033] 1.解析文档集中所有的XML文档，从每一个文档中分别抽取结构信息和内容信息。

[0034] 参照图1和图2，每个XML文档都可以表示为一个树形结构。树形结构中，所有叶子结点所包含的文本即为文档的内容信息。从根节点到每个叶子节点的父节点构成了一个路径(path)，所有的路径就构成了该文档的结构信息。通过该步骤，任意一个XML文档都可以表示为由多个路径组成的集合(结构信息)和由多段文本组成的集合(内容信息)，同时保留路径和文本的包含关系信息，以便在后边的步骤中进行统计。

[0035] 2.从内容信息中抽取关键字特征，构成关键字特征空间。

[0036] 针对文档集中所有的文档，通过第1步的解析之后，可以得到每个XML文档的内容信息。对于内容信息中的每个单词(word)，进行过滤停用词(stop word filtering)和词干化(stemming)处理后，即可得到一个由若干单词构成的集合，集合中的每个单词称之为关键字特征(term)，所有关键字特征就构成了关键字特征空间(term space)，图1和图2中的XML文档样例经过处理后得到的关键字特征空间如图3所示。

[0037] 3.从结构信息中抽取所有的路径，构成路径字典。

[0038] 针对文档集中所有的文档，通过第1步的解析之后，可以得到每个XML文档的结构信息，即每个XML文档所包含的所有路径。所有文档包含的所有路径构成的集合，称之为该文档集上的路径字典(path dictionary)，图1和图2中的XML文档样例经过处理后得到的路径字典如图3所示。

[0039] 4.统计关键字特征空间中每个关键字特征在每个文档的不同路径中出现的频率，包含该关键字特征的文档个数等信息，并根据这些信息进行关键字特征筛选。

[0040] 对于第2步中得到的关键字特征空间中的每个关键字特征tk，扫描在第1步解析之后得到的文档集的结构信息和路径信息，统计以下3个信息：

[0041] 1)该关键字特征在文档集的每个文档di的任意路径pathj中出现的频率，记为tfi(tk，pathj)；

[0042] 2)文档集中有多少个文档同时包含该关键字特征tk和路径pathj，记为df(tk，pathj)；

[0043] 3)文档集中包含关键字特征tk的文档数，记为df(tk)；

[0044] 根据df(tk)对关键字特征空间进行筛选，如果df(tk)不满足以下条件，则将从关键字特征空间中删除。

[0045] α*Arg min1≤i≤|C||Ci|≤df(tk)≤β*|C|*Arg max1≤j≤|C||Cj|[0046] 其中，α和β是两个参数，满足以下条件：

[0047] 0＜α≤0.5，0.5≤β＜1

[0048] 实际试验中，我们取α和β的值为0.33和0.67。

[0049] 关键字特征筛选的目的就是剔除那些出现过于频繁和过于稀少的关键字特征，因为这些关键字特征对文档所属类别的影响很小，可以忽略。经过特征筛选后，关键字特征空间的大小大大减小，可以加快后边相似度的计算，而不影响准确性。

[0050] 5.计算路径字典中每条路径的相关信息。

[0051] 对于第3步中得到的路径字典中的每条路径pathj，扫描在第1步解析之后得到的文档的结构信息，统计并计算路径的以下3个信息：

[0052] 1)路径的深度，记为pl(pathj)；

[0053] 2)数据集中包含路径的文档数，记为df(pathj)；

[0054] 3)路径pathj的权重，记为wpathj；

[0055] 路径权重表示了该路径在文档集中区别不同类别的能力，我们根据整个数据集的文档中是否包含路径pathj，然后利用信息论中熵(entropy)和信息增益(InformationGain)的概念来计算其权重。

[0056] 对于给定的文档集D，它的熵定义为：

[0057]

[0058] 其中pi表示文档集D中任意一个文档属于类别Ci的概率，可以由下式来计算：

[0059]

[0060] 为了计算路径pathj的信息增益，我们把文档集D中的文档按照是否包含路径pathj分为两个集合D1和D2，则我们定义文档集D被路径pathj划分后的熵为：

[0061]

[0062] 从而路径pathj的信息增益为：

[0063]

[0064] 根据信息论理论，路径pathj的信息增益在一定程度上反映了其对于区分文档集D当中文档所属的类别的能力，所以路径pathj的信息增益在一定程度上可以代表它的权重wpathj。为了消除信息增益为0时导致的影响，我们对其取对数，即：

[0065]

[0066] 6.将文档集中的每个文档表示为向量。

[0067] 文档集D中的任意一个文档di均可以表示为由关键字特征空间中的所有关键字特征组成的向量，其中每个分量表示对应的关键字特征tk在该文档中的权重。设经过第4步的关键字特征筛选后，关键字特征空间中有m个关键字特征，则文档di可以表示为：

[0068] di＝＜wi0，wi1，…，wim>

[0069] 下面的公式表示了关键字特征tk在文档di中的权重计算方法，其中用到了第4，5步中统计得到的信息。

[0070]

[0071] 7.根据余弦度量计算任意两个文档(向量)di和dj之间的相似度。余弦度量的计算公式如下：

[0072]

[0073] 其中，表示向量di的转置，表示向量di的欧几里得范数。