一种XML文档结构概要间的相似性度量方法

摘要

本发明涉及数据挖掘技术领域，具体涉及一种XML文档结构概要间的相似性度量方法。为了从结构角度在线快速聚类XML数据流，满足这类算法对内存和时间的较高要求，提供一种XML文档的结构概要以及这种结构概要间的相似性度量方法。该算法将XML文档以SAX格式解析后，借助全局名称-代码索引表和进行式栈技术将该文档形式化成一个可增量表示的概要数据结构——元素链(NodeList)，然后通过一个自定义公式计算两元素链间的相似性。本发明使用SAX解析XML文档，并利用了进行式栈技术获取层值，使得建立结构概要的过程中，内存消耗很小。整个内存消耗基本花费在保存元素链式的聚类结果和全局名称-索引表上。

权利要求

1.一种XML文档结构概要间的相似性度量方法，其特征在于步骤如下：

1）为待处理的XML文档流或文档集定义全局元素名称-代码索引表，并将该表置空；

该表中每个节点包括两部分内容：一部分是字符串格式用于存放待处理XML文档流或文档集包含的相异元素的名称；另一部分是整数格式用于存放该元素对应的整数编码；编码规则如下：当XML文档以SAX格式解析时，这个整数表示元素开始事件在全部相异元素开始事件流中第一次出现的顺序；

2）依据SAX格式解析XML文档，获取每个元素的开始事件，查找全局元素名称-代码索引表，如果元素名称已在链表中，则该元素的编码就是元素名称对应的整数；如果元素名称不在链表中，则该元素的编码值等于链表中现有最大整数加一，且该元素名称和对应整数编码作为新节点插入全局元素名称-代码索引表；

3）基于进行式栈技术获取特定元素的层值，具体操作如下：依据SAX格式解析XML文档，文档开始事件激活一个空栈结构，随着XML文档中元素数据元组的动态变化进行入栈和出栈操作，即元素开始事件和结束事件分别对应元素入栈和出栈两种操作，元素的层数值等同于所在栈的指针标记；

4）利用获取到的相异元素整数编码和其层值创建XML文档结构概要成为可增量表示的偏序元素链；

5）元素链以元素的编码整数为索引，具有可组合性，只是组合结果要满足同层同名重复元素只保留一个副本，具体组合过程如下：给定两个元素链a和b，从链表头部开始比较两个元素链中第一个节点的编码，如果a=b，则继续比较第一个节点的层值，如果层值也相等，则将a中第一个节点插入到结果元素链，否则将a和b中第一个节点都插入到结果元素链，继续比较两链表的下一个节点；如果第一个节点编码比较结果为a>b，则将b元素链中第一个节点插入到结果元素链，继续比较a中第一个节点和b中下一个节点；如果第一个节点编码比较结果为a

比较两个偏序元素链获取公有元素及其对应层值，比较过程如下：给定两个元素链a和b，从链表头部开始比较且节点是基本的移动单位，如果a中元素编码小于等于b中元素编码，则a移动到下一个节点，否则b移动到下一个节点，比较过程继续；比较过程中记录相等元素编码及其对应层值用于计算元素链间的相似性；

其中，ComWeight1与ComWeight2分别表示第一个与第二个元素链中包含的公有元素的权重累加和；ObjWeight1和ObjWeight2 分别表示第一个和第二个元素链中包含的所有元素的权重累加和；N1和N2分别表示第一个和第二个元素链的元素个数；M1和M2分别表示第一个和第二个元素链中公有元素的个数； 表示第一个元素链的第i个公有元素层数，表示第二个元素链的第j个公有元素的层数； 和 分别表示第一个和第二个元素链的第k个元素的层数；r是权重的递减因子，其值要大于1。

说明书

一种XML文档结构概要间的相似性度量方法

技术领域

[0001] 本发明涉及数据挖掘技术领域，具体涉及一种适用于对内存和时间有较高要求的XML文档流或集的结构概要间的相似性度量方法。

背景技术

[0002] XML是一种用于数据交换和共享的自描述语言，于1998年2月成为W3C的推荐标准后，得到了广泛的应用。遵循这一标准的Web应用和服务，在实时数据传输及交换过程中将产生随时间而不断变化的海量流式XML数据。例如医疗机构的各种病历和检查数据，航空机构的各种旅客信息，搜索服务面对的用户请求，网络监控需要处理的各种网络资源等等。为了有效分析这些数据，一个可能的解决办法就是根据文档结构，内容和语义聚类相似数据。

[0003] 现有的XML数据聚类技术只支持静态的XML数据集，其核心思想是：将XML文档看作是数据点，通过选定的XML文档相似性度量方法计算出聚类所需的文档间距离或相异矩阵，利用传统的聚类技术如：k-means或层次方式等完成聚类任务。聚类中所用XML文档相似性度量方法是聚类效果的关键。现有的XML文档相似性度量方法大致可以分为两类：基于树编辑距离的方法和基于文档特征集的方法。

[0004] 基于树编辑距离的方法通常将一个XML文档模型化为一棵树或一个图，两个XML文档间的相似度可以用这两棵树或图间的编辑距离来度量。编辑距离的基本思想是将两棵树间的距离定义为利用编辑操作，比如删除、插入、修剪等，将一棵树转化为另一棵树所需的最小代价。这类方法只考虑了节点不同，并没有区分不同层的节点对相似性的影响也不一样。

[0005] 基于文档特征集的方法更直接，首先提出各种方式用于表示XML文档特征然后通过直接计算这些特征间的距离来度量XML文档间的相似性。具体特征多种多样，涉及用位图索引技术表示XML文档特征，用向量空间模型VSM表示XML文档特征，用时间序列表示XML文档结构，用简化标记树对应的层结构LevelStructure表示文档结构特征等。这类方法主要用于处理静态数据，一般需要多次反复的文档读取和解析，而XML数据流的特点是仅允许1次并按照数据到达的顺序进行存取和解析。

[0006] 最近对XML数据的研究也扩展到了XML数据流方面，但是现有技术对这类数据流的处理大多集中于直接查询领域，例如：Christoph Koch和Stefanie Scherzinger介绍了一种用于XML流查询的语言XML Stream Attribute Grammars(XSAGs)，Koch等人提出了一个优化XQuery引擎的FluXQuery引擎，很少涉及更进一步的知识挖掘比如：在线分类，在线聚类等。

发明内容

[0007] 本发明的目的是为了从结构角度在线快速聚类XML数据流，满足这类算法对内存和时间的较高要求，提供一种XML文档的结构概要以及这种结构概要间的相似性度量方法。该算法将XML文档以SAX格式解析后，借助全局名称-代码索引表和进行式栈技术将该文档形式化成一个可增量表示的概要数据结构——元素链(NodeList)，然后通过一个自定义公式计算两元素链间的相似性。

[0008] 本发明提供的建立XML文档的结构概要技术，具体步骤如下：

[0009] 1)为待处理的XML文档流(或文档集)定义全局元素名称-代码索引表，并将该表置空。该表中每个节点包括两部分内容：一部分是字符串格式用于存放待处理XML文档流(或文档集)包含的相异元素的名称；另一部分是整数格式用于存放该元素对应的整数编码。编码规则如下：当XML文档以SAX格式解析时，这个整数表示该元素开始事件在全部相异元素开始事件流(只记录元素开始事件)中第一次出现的顺序。

[0010] 2)依据SAX格式解析XML文档，获取每个元素的开始事件，查找全局元素名称-代码索引表，如果元素名称已在链表中，则该元素的编码就是元素名称对应的整数；如果元素名称不在链表中，则该元素的编码值等于链表中现有最大整数加一，且该元素名称和对应整数编码作为新节点插入全局元素名称-代码索引表。

[0011] 3)基于进行式栈技术获取特定元素的层值。具体操作如下：依据SAX格式解析XML文档，文档开始事件激活一个空栈结构，随着XML文档中元素数据元组的动态变化进行入栈和出栈操作，即元素开始事件和结束事件分别对应元素入栈和出栈两种操作，元素的层数值等同于所在栈的指针标记，指针从0开始每次递增一。

[0012] 4)利用获取到的相异元素整数编码和其对应层值创建XML文档结构概要成为可增量表示的偏序元素链。

[0013] 5)元素链以元素的编码整数为索引，具有可组合性，只是组合结果要满足同层同名重复元素只保留一个副本。具体组合过程如下：给定两个元素链a和b，从链表头部开始比较两个元素链中第一个节点的编码，如果a＝b，则继续比较第一个节点的层值，如果层值也相等，则将a中第一个节点插入到结果元素链，否则将a和b中第一个节点都插入到结果元素链，继续比较两链表的下一个节点；如果第一个节点编码比较结果为a＞b，则将b元素链中第一个节点插入到结果元素链，继续比较a中第一个节点和b中下一个节点；如果第一个节点编码比较结果为a＜b，则将a元素链中第一个节点插入到结果元素链，继续比较b中第一个节点和a中下一个节点。

[0014] 6)比较两个偏序元素链获取公有元素及其对应层值，比较过程如下：给定两个元素链a和b，从链表头部开始比较且节点是基本的移动单位，如果a中元素编码小于等于b中元素编码，则a移动到下一个节点；否则b移动到下一个节点，比较过程继续。比较过程中记录相等元素编码及其对应层值用于计算元素链间的相似性。

[0015] 本发明自定义的加权公式用于计算两元素链间相似性(NodeSim)：

[0016]

[0017]

[0018] 其中，ComWeight1与ComWeight2分别表示第一个与第二个元素链中包含的公有元素的权重累加和；ObjWeight1和ObjWeight2分别表示第一个和第二个元素链中包含的所有元素的权重累加和；N1和N2分别表示第一个和第二个元素链的元素个数；M1和M2分别表示第一个和第二个元素链中公有元素的个数；表示第一个元素链的第i个公有元素层数，表示第二个元素链的第j个公有元素的层数；和 分别表示第一个和第二个元素链的第k个元素的层数；r是不同层中元素权重的递减因子，设计成用户自定义参数，其值要大于1，根据实验结果，r通常可取值2、4。

[0019] 本发明使用SAX解析XML文档，并利用了进行式栈技术获取层值，使得建立结构概要的过程中，内存消耗很小。整个内存消耗基本花费在保存元素链式的聚类结果和全局名称-索引表上。

附图说明

[0020] 图1-(a)XML文档的SAX解析格式示例

[0021] 图1-(b)通过进行式栈获取层值的示例图

[0022] 图1-(c)全局元素名称-代码索引表

[0023] 图1-(d)XML文档对应的元素链

[0024] 图2组合两元素链的示例图

[0025] 图3比较两元素链获取共有元素的示例图

[0026] 图4比较后得到的共有元素

[0027] 图5-(a)内存消耗随文档个数的变化情况

[0028] 图5-(b)时间花费随文档个数的变化情况

具体实施方式

[0029] 下面将结合附图和具体实施例对本发明进行详细说明。以下实施例中的XML文档可以是在线XML文档流中的具体个体样本。并且假设整个过程是从待处理的第一文档开始。建立XML文档对应元素链并比较获取共有元素的具体处理流程如下：

[0030] 1)为待处理的XML文档流(或文档集)定义全局元素名称-代码索引表，并将该表置空。

[0031] 如图1-(a)所示一个XML文档片段根据SAX格式解析后得到的是一个标记流，各个相异元素的开始事件在元素开始事件流中的次序用对应整数标记。例如：第一个元素名称“W4F-DOC”开始事件是第一个出现，因此标记为整数“1”。

[0032] 2)根据解析格式，为每个元素的开始事件获取整数编码，图1-(c)是处理过四个相异元素后处理第五个元素时的状态，首先利用元素名称“LastName”查找全局名称-代码索引表，此时元素名称不在链表中，则该元素的编码值等于链表中现有最大整数“4”加一，且该元素名称和对应整数编码作为新节点插入全局元素名称-代码索引表。

[0033] 3)图1-(b)是基于进行式栈技术获取特定元素层值的示例图。正如图所示，第四个元素的开始事件将整数编码“4”入栈，此时对应的栈指针是3，因此该元素层值为“3”，当该元素结束事件出现时，该整数编码被出栈。

[0034] 4)根据步骤2)和3)，为各个相异元素获取到对应的整数编码和其层值，创建了图1-(a)中XML文档结构概要对应的偏序元素链如图1-(d)所示。

[0035] 5)元素链以元素的编码整数为索引，具有可组合性，只是组合结果要满足同层同名重复元素只保留一个副本。图2是两个元素链a，b的具体组合过程。正如图中所示，a，b中第一个节点的编码和层值都相等，因此只将a中第一个节点插入到结果元素链；第三个节点的编码相等，而层值不等，所以将a和b中的第三个节点都插入到结果元素链。

[0036] 6)为了计算两个元素链的相似性值(NodeSim)，需要比较两个偏序元素链获取公有元素及其对应层值。图3是给定两个元素链a和c，具体比较过程的示例。从链表头部开始比较，第一个节点编码相等，则a移动到下一个节点，如图中第一次比较结束后a移动到第二个节点，继续和b的第一个节点编码比较；a中第二个节点编码大于b中第一个节点编码，则b移动到第二个节点，比较过程继续。通过这样比较后，得到了图4中粗线标示出的两元素链的共有元素。

[0037] 获得共有元素后，可以利用本发明自定义的加权公式计算两元素链间相似性，假定权重的递减因子设定r＝2，则(1/r)＝0.5，从图4可知元素链a中元素个数N1＝8，元素链c中元素个数N2＝9；元素链a、c中共有元素个数相等M1＝M2＝8；表示元素链a中第i个公有元素的层数， 表示元素链c中第j个公有元素的层数；和 分别表示元素链a和元素链c中第k个元素的层数；则图4中的两个元素链间的相似性计算过程如下：

[0038]

[0039]

[0040]

[0041]

[0042] 为了评测我们发明的这种XML文档的结构概要间的相似性度量方法在时间和内存方面的效果，通过该方法度量相似性然后采用传统的划分方法进行了一系列聚类实验，并在相同条件下与最新的通过层结构LevelStructure评估相似性，然后使用划分方法进行聚类的XCLS算法进行了对比，实验设计过程和最终结果陈述如下。

[0043] 实验条件：Pentium IV的PC，2.4G内存，JAVA语言实现程序，用户定义参数的设置也相同，具体是权重的递减因子设定r＝2，则1/r＝0.5，最小相似性阈值为0.8，最大聚类个数为130。

[0044] 实验数据：实验使用了一个10419个文档模拟数据集，该数据是使用传统行业，比如民航，网络应用等，中成熟的XML Schema通过XML工具oXygen XML编辑器随机产生的。文档大小从几k到几百k。

[0045] 实验结果：图5是一组对比实验的实验结果，尽管两种聚类方法都使用了一种特定的XML文档结构概要及对应的相似性度量方法，从结果中可以看到，本发明在时间花费和内存消耗方面明显优于XCLS算法。通过分析两种度量方法的具体操作过程，可以将本发明在时间花费和内存消耗方面的优势总结如下：

[0046] (1)本发明的结构概要是以有序整数为索引的，因此在比较获取共有元素的过程中，时间复杂度最差情况下是O(max{N1，N2})，而通过层结构LevelStructure评估相似性获取共有元素的过程，时间复杂度最差情况是O{N1×N2)。

[0047] (2)内存消耗方面，本发明使用SAX解析XML文档，并利用了进行式栈技术获取层值，使得建立结构概要的过程中，内存消耗很小。整个内存消耗基本花费在保存元素链式的聚类结果和全局名称-索引表上。而XCLS算法中使用的层结构是基于精简标记树的，该树可以看作是DOM树的简化格式，因此建立概要结构的过程中需要为文档建立对应的标记树，当文档很大时，这个工作的内存消耗很大。尽管保存层结构形式的聚类结果花费的内存和保存元素链式的聚类结果消耗内存基本相当，但是因为建立过程中内存消耗差别很大，最终的结果差别也很显著。