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

摘要

一种新的基于扩展邻接矩阵的XML文档结构及语义相似性计算方法，属于数据挖掘技术领域。该方法具体包括：XML文档树的编码；对于编码后的两个文档首先生成模式文档节点列表和数据源文档节点列表，然后生成模式扩展邻接矩阵和数据源扩展邻接矩阵(P1，P2)；通过cos(P1，P2)计算XML文档相似性。该方法充分考虑了不同层次节点对文档贡献的不同，且在XML文档节点数为n的情况下，此方法的时间复杂度最高为O(n2)，优于编辑距离算法。

主权项

1.基于扩展邻接矩阵的XML文档结构及语义相似性计算方法，其特征在于该方法的具体步骤如下：第1、首先进行XML文档树的编码以及文档的定义XML文档的DOM结构可以看作是该文档的树形结构，其中节点属性看作是此节点的子节点，一个XML文档可以看作是一个自上向下展开的树；对此树进行编码的方式为深度搜索方式，即采用深度搜索方法遍历此树，然后为节点依次编码1，2，3，4......，直到最后一个节点，记作节点编码；树中层的分配采用倒排方式，即树的叶节点所在层记作第一层，然后依次向上推第二层、第三层......，直至根节点；模式文档：指用户所提供的需求文档；数据源文档：从数据源中提取的文档；第2、对于两个编码后的文档，要分别生成它们所对应的邻接矩阵第2.1、生成模式文档节点列表和数据源文档节点列表将模式文档读入以后，采用深度优先搜索方法遍历每个节点；而对于节点的属性，这里将之看作节点的一个子节点；遍历到任何一个节点的时候，抽取每个节点的标签信息、编码信息、层信息、父节点信息组成NodeMessage类，然后依次添加到list列表中，形成模式文档节点列表；对于数据源文档，根据模式文档节点列表的生成方法生成一个临时节点列表，然后用模式文档节点列表中的每个NodeMessage与临时节点列表中的每个NodeMessage相比较，如果找到与模式文档节点列表的NodeMessage相同的节点，将其加入到数据源文档节点列表中去，如果不能找到与模式文档列表的NodeMessage相同的节点，则在数据源文档节点列表中加入空节点；当模式文档节点列表中的每个节点都比较过之后，数据源文档节点列表随之生成；第2.2、生成模式扩展邻接矩阵和数据源扩展邻接矩阵扩展邻接矩阵：G是一个树，V(G)为G的节点集合，E(G)为G的祖先-后代关系；设G中有n个节点v₁，v₂，v₃...v_n；P＝(p_ij)_n*n为G扩展邻接矩阵，其中f_j代表v_j所在的层值，f_i代表v_i所在的层值，θ代表语义相似度；假设模式文档包含n个节点，那么在模式文档节点列表中就会有n条信息，而且这n个节点按照编码顺序1，2，3，4，5......n排列；首先取节点i与节点j比较，i＝1，2，3，4，5......n，j＝1，2，3，4，5......n，这里分两种情况：①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计算相似性数值将生成的扩展邻接矩阵中的每个元素看成是向量的一个维度，然后从第一行开始每行首尾相连，这样就形成了两个n*n维的向量n代表矩阵中每行、每列元素的个数，那么根据向量的性质可得：其中，P₁是模式文档扩展邻接矩阵，P₂是数据源文档扩展邻接矩阵。