基于扩展邻接矩阵的XML文档结构及语义相似性计算方法

摘要

一种新的基于扩展邻接矩阵的XML文档结构及语义相似性计算方法，属于数据挖掘技术领域。该方法具体包括：XML文档树的编码；对于编码后的两个文档首先生成模式文档节点列表和数据源文档节点列表，然后生成模式扩展邻接矩阵和数据源扩展邻接矩阵(P

说明书

【技术领域】

本发明属于数据挖掘技术领域，具体涉及一种合理有效的XML文档相似性计算方法。

【背景技术】

XML作为一种标示语言，已经在互联网上成为一种数据表达和数据交换的相关标准，尤其在电子商务等方面起着举足轻重的作用。在现今网络数据不断膨胀的条件下，作为网络数据标准之一的XML数据也在急速增长，在这些海量的XML数据中如何能找到我们需要的数据甚至如何从中挖掘出一些我们不曾了解的隐藏信息成为数据挖掘的一个重要研究方向。在这个研究方向中，如何能量化两个XML文档的相似性是一个关键。

XML不仅可以描述结构化数据，还具有描述半结构化数据的能力。目前，网络上的XML数据大多是半结构化的，半结构化数据的结构类似于图或树，通常称为有向标记图，可以用邻接矩阵来描述。根据这个特点，本发明通过改进的邻接矩阵来描述XML文档的结构及语义，进而量化文档间的相似性。

近些年，国内外许多学者在XML文档相似测度问题的研究方面做了大量的工作。其中，研究最早也是研究最多的方法是把XML文档之间的相似性用树之间的编辑距离(EditDistance)来度量。两棵树之间的编辑距离指的是通过修改(update)、删除(delete)、插入(insert)等操作使原始树到达目标树所经过的步骤。Tai最早使用编辑距离来计算两棵树间的相似度。其基本思想是将两棵树间的距离定义为利用编辑操作将一棵树转化为另一棵所需的代价。这种方法的优点是可以很好的表示出不同文档之间有多少节点不相同，但是没有考虑不同层节点对文档的贡献的不同，而且时间复杂度过高，为O(n³)。

【发明内容】

本发明目的是如何在海量的XML数据中找到我们需要的数据或如何从中挖掘出一些我们不曾了解的隐藏信息的问题，提供一种新的基于扩展邻接矩阵的XML文档结构及语义相似性计算方法，该方法通过两个扩展邻接矩阵来表示两个XML文档的结构及语义信息，然后计算两个矩阵的相似性。

该方法充分考虑了不同层次节点对文档贡献的不同，且在XML文档节点数为n的情况下，此方法的时间复杂度最高为O(n²)，优于编辑距离算法。

本发明提供的基于扩展邻接矩阵的XML文档结构及语义相似性计算方法的具体步骤如下：

第1、首先进行XML文档树的编码

XML文档的DOM结构可以看作是该文档的树形结构，其中节点属性看作是此节点的子节点，一个XML文档可以看作是一个自上向下展开的树；如图1为一棵XML文档树，对此树进行编码的方式为深度搜索方式，即采用深度搜索方法遍历此树，然后为节点依次编码1，2，3，4......，直到最后一个节点，记作节点编码；树中层的分配采用倒排方式，即树的叶节点所在层记作第一层，然后依次向上推第二层、第三层......，直至根节点；

第2、对于两个编码后的文档，要分别生成它们所对应的邻接矩阵

第2.1、生成模式文档节点列表和数据源文档节点列表

将模式文档读入以后，采用深度优先搜索方法遍历每个节点；而对于节点的属性，这里将之看作节点的一个子节点；遍历到任何一个节点的时候，抽取每个节点的标签信息、编码信息、层信息、父节点信息组成NodeMessage类，然后依次添加到list列表中，形成模式文档节点列表；

对于数据源文档，根据模式文档节点列表的生成方法生成一个临时节点列表，然后用模式文档节点列表中的每个NodeMessage与临时节点列表中的NodeMessage相比较，如果找到与模式文档节点列表的NodeMessage相同的节点，将其加入到数据源文档节点列表中去，如果不能找到与模式文档列表的NodeMessage相同的节点，则在数据源文档节点列表中加入空节点；当模式文档节点列表中的每个节点都比较过之后，数据源文档节点列表随之生成；

第2.2、生成模式扩展邻接矩阵和数据源扩展邻接矩阵

假设模式文档包含n个节点，那么在模式文档节点列表中就会有n条信息，而且这n个节点按照编码顺序1，2，3，4，5............排列；首先取节点i(i＝1，2，3，4，5......)与节点j(j＝1，2，3，4，5......)比较，这里分两种情况：

①i＝j，当i＝j的时候，模式文档扩展邻接矩阵的P[i][j]＝1；对于数据源文档的扩展邻接矩阵，如果节点为空节点，则P[i][j]＝0，如果节点不为空节点，则P[i][j]＝1；

②i≠j，分为四种情况：1)如果节点i的编码大于节点j的编码，那么P[i][j]＝0；2)如果节点i的编码小于节点j的编码，但是节点i或节点j为空节点，那么P[i][j]＝0；3)如果节点i的编码小于节点j的编码，而且节点i与节点j不为空节点，但是节点i不是节点j的父节点或祖先节点，那么P[i][j]＝0；4)如果节点i的编码小于节点j的编码，而且节点i与节点j中不包含空节点，且节点i是节点j的父节点或祖先节点，P[i][j]＝节点j所在层值除以节点i所在层值；待所有节点全部相互比较之后，扩展邻接矩阵随之生成；

第3、根据cos(P₁，P₂)计算相似性数值

将生成的扩展邻接矩阵中的每个元素看成是向量的一个维度，然后从第一行开始每行首尾相连，这样就形成了两个n*n维的向量，n代表矩阵中每行、每列元素的个数，那么根据向量的性质可得：

$\cos (P_1,P_2)=\frac{\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{P}_{1\mathrm{ij}}{P}_{2\mathrm{ij}}}{\sqrt{\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{P_{1\mathrm{ij}}}^2}\sqrt{\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{P_{2\mathrm{ij}}}^2}}.$

与本发明有关的概念和定义

1.XML文档

本发明所述的XML文档可以看作是由节点(Nodes)，边(Edges)，层(Floors)组成，一个文档Doc可以定义成：Doc＝T(N，E，F)，其中，N代表文档中元素、属性、值的集合；E代表文档中边的集合，即节点间包含关系的集合；F代表文档中层的集合。

2.邻接矩阵

邻接矩阵用一个二维数组来表示图中顶点间的相邻关系，无需列出顶点和弧，为图的描述提供了一种便利。G是一个图，V(G)为G的顶点集，E(G)为G的边集。设G中有n个顶点v₁，v₂，v₃...v_n；A＝(a_ij)_n*n为G的邻接距阵，其中

$a_{\mathrm{ij}}=\left(\begin{array}{cc}1& v_i{v}_j\in E\left(G\right)\\ 0& v_i{v}_j\notin E\left(G\right)\end{array},,i,j=\mathrm{1,2},···,n\right)$

3.节点表示信息(见图1)

①.节点标签信息。即节点的语义，是节点的标志，亦是节点最重要的信息。

②.节点层信息。即节点在文档模型中处于哪一个层。

③.节点编码信息。节点索引的唯一标识，在某个文档模型中不会有重复。

④.父节点信息。连接节点与节点间关系的信息，我们可以根据该信息方便的找到每个节点的父节点及其祖先。

4.模式文档和数据源文档

模式文档：用户所提供的需求文档，在相似性比较中需要所有的其他文档与之相比较。

数据源文档：从数据源中提取的文档，在相似性比较中需要与模式文档相比较。

5.扩展邻接矩阵

G是一个树，V(G)为G的节点集合，E(G)为G的祖先-后代关系。设G中有n个节点v₁，v₂，v₃...v_n；P＝(p_ij)_n*n为G扩展邻接距阵，其中

$p_{\mathrm{ij}}=\left(\begin{array}{cc}{f}_j÷f_i& v_i{v}_j\in E\left(G\right),i\ne j\\ 0& v_i{v}_j\notin E\left(G\right),i\ne j\\ \theta & v_i{v}_j\notin E\left(G\right),i=j\end{array}\right),i,j=\mathrm{1,2},···,n$

f_j代表v_j所在的层值，f_i代表v_i所在的层值，θ代表语义相似度。

6.模式扩展邻接矩阵和数据源扩展邻接矩阵

模式扩展邻接矩阵：用来表示模式文档结构及语义信息的扩展邻接矩阵。

数据源扩展邻接矩阵：用来表示数据源文档结构及语义信息的扩展邻接矩阵。

与本发明有关的性质

性质1：邻接矩阵分为有向图邻接矩阵和无向图邻接矩阵，无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n²个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上(下)三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+...+(n-1)＝n(n-1)/2个单元。邻接矩阵中只有0和1两个值。两个顶点之间有边相连则结构信息为1，无边相连则结构信息为0。

性质2：扩展邻接矩阵具有如下特点：

1.模式文档矩阵大小为n*n，其中n为模式文档中节点数量，数据源文档矩阵大小根据模式文档矩阵大小确定。

2.用来表示结构信息有上(下)三角阵中剔除了左上右下对角线上的元素后剩余的元素，即1+2+...+(n-1)＝n(n-1)/2个元素。

3.用来表示语义信息的有上(下)三角阵中左上至右下对角线上的元素。

4.用来表示结构信息的元素的取值遵循如下规则：

①如果两个节点具有父--子关系或祖先--子孙关系，则元素取值E_ij为E_ij＝子结点或子孙节点所在的层值除以父节点或祖先节点所在的层值。

②如果两个节点不具备以上的关系则元素值取为0.

③如果两个节点中有任意一个节点为空节点，则元素取值为0.

5.模式邻接矩阵中的语义信息元素取值全为1，数据源邻接矩阵中语义信息元素取值可根据模式列表和比较列表中对应元素的相似程度取相应的值，取值范围在0-1之间。

性质3：向量的余弦值

设有n维向量x＝(x₁，x₂，…，x_n)，y＝(y₁，y₂，…，y_n)，那么向量x，y的夹角<x，y>的余弦值为：

cos<x，y>＝[x，y]/(|x||y|)

其中[x，y]代表向量x与向量y的内积，

[x，y]＝x₁y₁+x₂y₂+…+x_ny_n

|x|，|y|分别代表向量x和向量y的模，

$\left|x\right|=\sqrt{[x,x]}=\sqrt{{x_1}^2+{x_2}^2+···+{x_n}^2}$

$\left|y\right|=\sqrt{[y,y]}=\sqrt{{y_1}^2+{y_2}^2+···+{y_n}^2}$

所以，向量的余弦值可以表示为：

$\cos (x,y)=[x,y]/\left(\right|x\left|\right|y\left|\right)=\frac{x_1{y}_1+x_2{y}_2+···+x_n{y}_n}{\sqrt{{x_1}^2+{x_2}^2+···+{x_n}^2}\sqrt{{y_1}^2+{y_2}^2+···+{y_n}^2}}.$

本发明的优点在于，不仅充分考虑不同文档间不同节点的数量，而且对于每个节点对文档的贡献作了区分，同时节点对于文档整体性的贡献也被考虑进来。此方法的时间复杂度最高为O(n²)，优于编辑距离算法。

【附图说明】

图1是XML文档树编码示例图。

图2a是算法流程图，图2b是P1生成步骤，图2c是P2生成步骤。

图3是XML文档树图。

图4a是模式文档显示图  图4b是数据源文档显示图

图4c是模式文档列表    图4d是数据源文档列表

【具体实施方式】

实施例

模式文档和数据源文档的编码、读取与显示。

根据发明内容中第1的编码方法对两个文档分别编码，区别出每个节点的编码信息和层信息，并将层信息储存在数组中。以图3为例，模式文档和数据源文档都根据深度搜索进行了节点编码并区分出不同的层。

XML文档的读取采用深度优先搜索方法，首先读取XML文档的根节点，然后从根节点开始通过add_treeview_nodes()方法递归搜索每个节点，递归过程中，先判断节点是否有子节点，如果没有子节点，那么说明此节点为叶节点，然后返回上一层；如果有子节点，那么循环遍历所有子节点，遍历到每个节点的时候再用add_treeview_nodes()递归，最后实现所有节点的遍历。

XML文档的显示采用treeview控件，在递归遍历XML每个节点的时候，读取每个节点的文本值，然后将文本值赋给treeview控件相应的位置，形成一个树形结构的XML文档。以图3为例，显示结果图4a、图4b。

1.模式文档节点列表和数据源文档节点列表的生成。

首先生成模式文档节点列表。根据发明内容中第2.1中的方法，将模式文档读入以后，可以采用深度优先搜索方法遍历每个节点。而对于节点的属性，这里将之看作节点的一个子节点。遍历到任何一个节点的时候，抽取每个节点的标签信息、编码信息、层信息、父节点信息组成NodeMessage类，然后依次添加到list列表中，形成模式文档节点列表。以图3为例，生成的模式文档列表如图4c。

其次生成数据源文档节点列表。先根据模式文档节点列表的生成方法生成一个临时节点列表，然后用模式文档节点列表中的每个NodeMessage与临时节点列表中的Nodemessage相比较，如果找到与模式文档节点列表的NodeMessage相同的节点，将其加入到数据源文档节点列表中去，如果不能找到与模式文档列表的NodeMessage相同的节点，则在数据源文档节点列表中加入空节点。当模式文档节点列表中的每个节点都比较过之后，数据源文档节点列表随之生成。以图3为例，生成的数据源文档列表如图4d。

2.模式文档扩展邻接矩阵和数据源文档扩展邻接矩阵的生成。

具体实施方法1提到的节点列表中，包含节点标签信息、编码信息、层信息、父节点信息，根据这些信息分别生成每个列表对应的扩展邻接矩阵P。以图3为例，模式文档包含6个节点，那么在模式文档节点列表和数据源文档列表中就会有6条信息，所以形成的矩阵为6*6方阵。为了说明的方便、清晰，首先采用表格的形式表示矩阵，见表格1(模式文档)和表格2(数据源文档)，其中第一列代表模式文档中的节点，表格1中第一行亦代表模式文档中的节点，表格2中的第一行代表数据源文档中的节点，其他有数值(包括0)的单元格代表交叉点所对应的行和列中节点的关系(对角线上面的单元格代表语义信息关系，其他的单元格代表结构信息关系)。首先取节点i(i＝1，2，3，4，5，6)与节点j(j＝1，2，3，4，5，6)比较，这里分两种情况：①i＝j。当i＝j的时候，就是列表中的每个元素和自身相比较，模式文档扩展邻接矩阵的P[i][j]＝1，即表格1中对角线的值均为1；对于数据源文档的扩展邻接矩阵，如果节点为空节点，则P[i][j]＝0，如果节点不为空节点，则P[i][j]＝1，即表格2中对角线的值前4个为1，后2个为0。②i≠j。分为四种情况：1)如果节点i的编码大于节点j的编码，那么P[i][j]＝0；2)如果节点i的编码小于节点j的编码，但是节点i或节点j为空节点，那么P[i][j]＝0；3)如果节点i的编码小于节点j的编码，而且节点i与节点j不为空节点，但是节点i不是节点j的祖先(包括父节点)那么P[i][j]＝0；4)如果节点i的编码小于节点j的编码，而且节点i与节点j不为空节点，且节点i是节点j的祖先(包括父节点)，P[i][j]＝节点j所在层值除以节点i所在层值。以表格1第一行第二列的单元格为例，此单元格代表了根节点“INVENTORY”和节点“BOOK”之间的结构关系，因为根节点“INVENTORY”所在层为第三层，而节点“BOOK”所在的层为第二层，所以此单元格的结构信息值E₁₂为

类似于E₁₂的计算方法并结合上述四种情况，将表格1和表格2中的所有单元格填满数值后，模式文档扩展邻接矩阵和数据源文档扩展邻接矩阵也随之生成，如下所示：

表格1(模式文档)：

  INVENTORY   ID   BOOK   TITLE   AUTHOR   TELE  INVENTORY  1   2/3   2/3   1/3   1/3   2/3  ID    1   0   0   0   0  BOOK     1   1/2   1/2   0  TITLE      1   0   0  AUTHOR       1   0  TELE        1

模式文档扩展邻接矩阵如下：

$\left(\begin{array}{cccccc}1& 2/3& 2/3& 1/3& 1/3& 2/3\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 1/2& 1/2& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

表格2(数据源文档)：

  INVENTORY   ID   BOOK   TITLE   AUTHOR   DATE  INVENTORY  1   2/3   2/3   1/3   0   0  ID    1   0   0   0   0  BOOK     1   1/2   0   0  TITLE      1   0   0  AUTHOR       0   0  TELE        0

数据源文档扩展邻接矩阵如下：

$\left(\begin{array}{cccccc}1& 2/3& 2/3& 1/3& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 1/2& 0& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right)$

3.相似性计算。

将生成的扩展邻接矩阵中的每个元素看成是向量的一个维度，然后从第一行开始每行首尾相连，这样就形成了两个n*n维(n代表矩阵中每行、每列元素的个数)的向量P₁、P₂，两个文档的相似性可以表示成两个向量的余弦值cos(P₁，P₂)，根据向量的性质可知，cos(P₁，P₂)＝向量P₁P₂的内积除以(向量P₁的模乘以向量P₂的模)。以图3为例，根据具体实施方式2中的模式文档扩展邻接矩阵和数据源文档邻接矩阵计算出cos(P₁，P₂)＝0.8073，即为文档一和文档二的相似性值。

附图2a算法流程图中：

1.输入模式文档D1和数据源文档D2。

2.根据模式文档D1生成模式文档列表List1[n]，根据数据源文档D2和模式文档列表List1[n]生成数据源文档列表List2[n]。

3.List1[i]与List1[j]相比较生成P1[i][j](其中i，j＝1，2，3，4，5......，n)。

4.List2[i]与List2[j]相比较生成P2[i][j](其中i，j＝1，2，3，4，5......，n)。

5.根据P1[i][j]和P2[i][j]计算余弦值，得到相似性结果。

6.结束。

附图2b算法流程图中：

List1[i]与List1[j]相比较生成P1[i][j](其中i，j＝1，2，3，4，5......，n)

1.i＝0。

2.j＝0。

3.如果i＝j，则P1[i][j]＝1；如果i≠j，分为四步：

①IF N[i]＜N[j]，THEN P1[i][j]＝0；

②IF N[i]＞N[j]AND(Node[i]＝null OR Node[j]＝null)，THEN P1[i][j]＝0；

③IF N[i]＞N[j]AND Node[i]！＝null AND Node[j]！＝null AND Node[i]不为Node[j]的祖先，THEN P1[i][j]＝0；

④IF N[i]＞N[j]AND Node[i]！＝null AND Node[j]！＝null AND Node[i]为Node[j]的祖先，THEN P1[i][j]＝节点j所在层值除以节点i所在层值。

4.判断i，j是否循环到最大值n，分三种情况：

①IF i＜n，j＜n，THENj++；返回第3步

②IF i＜n，j＞n，THENi++；返回第2步

③IF i＞n，THEN P1[i][j]生成；

附图2c算法流程图中：

List2[i]与List2[j]相比较生成P2[i][j](其中i，j＝1，2，3，4，5......，n)

1.i＝0。

2.j＝0。

3.如果i＝j，分两步：

①IF Label2[i]！＝null，THEN P2[i][j]＝1；

②IF Label2[i]＝null，THEN P2[i][j]＝0.

如果i≠j，分为四步：

①IF N[i]＜N[j]，THEN P2[i][j]＝0；

②IF N[i]＞N[j]AND(Node[i]＝null OR Node[j]＝null)，THEN P2[i][j]＝0；

③IF N[i]＞N[j]AND Node[i]！＝null AND Node[j]！＝null AND Node[i]不为Node[j]的祖先，THEN P2[i][j]＝0；

④IF N[i]＞N[j] AND Node[i]！＝null AND Node[j]！＝null AND Node[i]为Node[j]的祖先，THEN P2[i][j]＝节点j所在层值除以节点i所在层值。

4.判断i，j是否循环到最大值n，分三种情况：

①IF i＜n，j＜n，THEN j++；返回第3步

②IF i＜n，j＞n，THEN i++；返回第2步

③IF i＞n，THEN P2[i][j]生成。