基于粗糙集形式化模型的资源描述框架空节点近似表示模型

王凯,杨枢，2

(1. 蚌埠医学院 卫生管理系，安徽 蚌埠 23303；2. 合肥工业大学 信息与计算机学院，安徽 合肥 23300)

0 引言

基于资源描述框架(RDF)的软件版本控制算法通过文本行的比较，基于逻辑谓词、排序重组、关联关系再造等方法，获取版本语句间的增量信息[1].但此类方法在计算结构化或半结构化文档时，由于无法充分挖掘不同版本间的语义信息，数据映射整体效率不高.语义资源描述框架的文档版本利用RDF资源语句的基本数据模型，通过三元组定义语句资源、属性以及数值.RDF三元组涉及与对象关联的二进制关系(逻辑谓词)，通过有向图表示RDF文档或数据集.语义Web环境中的软件版本处理，由于资源通常无序表示，文本关系映射不仅需要基于线性关系的序列化处理模型，还需要通过排序等序列重组，实现RDF数据集的关联知识推理[2].

获取RDF数据集不同版本之间的增量数据，需要建立版本间的节点映射关系.然而，映射关系计算需要解决以下两类问题：RDF图中空节点的遍历最优化搜索问题以及大量空节点的语义关系映射问题.由于空节点通常是局部变量，互相之间一般不直接相连，在两个版本中找到空节点之间的映射往往十分困难，一般情况下最优映射是NP难题.RDF图中空节点没有统一资源标识符(URI)或文字标识资源，不同版本的空节点之间的映射计算准确性不高.

Noy等[3]通过比较本体版本的结构属性，结合不同的启发式匹配器映射RDF图，提出一种支持版本控制和RDF知识库进化的映射框架，更改空节点语句.Guo 等[4]在模型数据集中添加唯一标识符，提供结构和语义版本控制信息.空节点在所有版本中都被赋予唯一标识符，利用URI作为反向功能属性附加到空节点集合中.Khilwani等[5]提出了RDF存储库的版本控制模型，构造一个协作注释工具，开发和共享Web上的注释信息，关系数据库模型优化了RDF存储库中的版本控制程序，但未讨论映射空节点的语义方法 .Dimitris等[6]提出双重多项式时间算法，映射两个知识库之间的空节点，使用Hammoud方法[7]寻求具有时间复杂度O(n3)的最优解.该方法在知识库间不存在互连节点的条件下，获得最佳增量.由于RAM的二次空间要求，该方法无法应用于较大的知识库.熊政[8]对上述模型加以改进，根据空节点的直接邻域生成一个字符串作为标签.在映射阶段同步生成字符串，按字典顺序排序，以允许二进制搜索.潘晓君等[9]提出了一种基于树形存储的二进制搜索算法.减少时隙内数据通信量,提高数据识别的服务效率,.吴菲等[10]设计出一种基于机会感知的情境识别系统，采用优化的知识存储结构，提升系统的综合识别能力.

1 相关理论与方法

1.1 基于RDF模型的映射理论

基于RDF的知识库模型由一组RDF三元组表示.若两个图的节点集合之间存在双映射关系，则两个RDF图G1和G2是等价关系.M函数将空节点映射到空节点集bnodes(即对每个b∈B1，都有M(b)∈B2).若三元组(s，p，o)在G1中，则(M(s)，p，M(o))在G2中.图G1和G2之间的等价表示为G1≡MG2.

随着RDF版本数量的增多，非等价知识库之间的版本信息分析，需要找到两个知识库中空节点之间的映射关系，减少相关的计算规模.将空节点关系映射转化为映射关系描述函数的优化问题.给定n1=|B1|，n2=|B2|，令n=min(n1，n2)，M包含映射知识库的所有URI描述定义，假设n = n1

定义1(双射M的计算成本)

(1)

定义2 (改进的等价关系)

G1≡MG2⟹Esti-cost(argMmin(Esti-cost(M)))=0

(2)

1.2 实验方法：

粗糙集理论(Rough Set Theory)通过不确定性知识表示，解决数据的近似表示问题.近似空间由有序对A =(U，R)表示，设U是一个有限非空对象集合，在集合U中使用等价关系表示R上的不确定性关系，关系R是U中对象的分类关系，即x，y∈U.A中X的近似区域边界，由属于U的上近似集合构成.区域内基于A的等价类元素的隶属关系X是不确定的，表示为公式3所示.

duv(X)=Asup(X)-Ainf(X)

(3)

正向区域涵盖属于X的所有元素，负向区域包括不属于X的所有元素.近似区域包括U中无法完全确定的元素集合，区域元素表示为图1所示.

通过定义精度和判别指标，空间A =(U，R)表示集合X∈U的近似程度.为便于构建映射模型，结合形式概念分析理论[11]给出以下度量概念，定义如公式4-7所示.

◆A中X的内涵度量

(4)

◆A中X的外延度量

(5)

◆A中X下近似绝对量

(6)

◆A中X上近似绝对量

(7)

A中X的内涵度量是A中完全属于X的元素数，而外延度量表示可能属于X的元素数.A中X下近似绝对量和上近似绝对量用于度量上述数值在元素总数中的占比.

图1 对象的近似分类关系表示

2 面向RDF数据集的空节点映射模型

如果所有元素都处于负向区域，将空节点划分成不同的类，使用符号≠Aij表示两节点不在同一个类Aij中，即(bi≠Aijbj)⟺(Asup(Xi)∩Asup(Xj)=Ø)，此时若区域是空集，则所有与该节点的通路的交集是全集，即Asup(Xi)∩Asup(Xj)= Uij.评估以上区域内的空节点的近似集，需要综合考虑集合内交集的近似集.为便于分析Aij内Xi和Xj之间的近似值，定义如下内容：

定义 5

空节点下近似量 - 空节点区域内部近似区域发生变化的区域绝对量

(8)

空节点上近似量 - 空节点区域外部近似区域发生变化的区域绝对量

(9)

定义6根据定义5中给出的计算方法，重新定义两个空节点 bi和bj之间的近似关系，其中γAinf(Xi，Xj)综合考虑具有相同谓词的节点映射关系，而γAsup(Xi，Xj)计算具有相似谓词关系的节点映射关系.

定义6

(bi≡Aijbj)⟺(γAsup(Xi,Xj)=1)

(bi≈Aijbj)⟺(0<γAsup(Xi,Xj)<1)

(10)

(bi≠Aijbj)⟺(γAsup(Xi,Xj)=0)

启发式方法通过比较不同版本之间的增量，减少空节点之间的对比计算量，主要采用以下策略：

1)近似度量策略 - 如果候选对(Xi，Xj)的空节点下近似量取值相同，则使用其上近似量度量.由于具有更多的共同谓词，空节点上近似量具有更高的相似性，具有相似谓词的映射有助于减小运算规模.

2)空节点分级策略- 考虑直接相连空节点之间的层次结构，将其分为四个不相交子集：根节点、叶节点、中间体节点以及无交节点；根据与其他节点之间连接的节点数，重新组合空节点集，允许访问具有特定数量的空节点集合.

3)未映射的相邻空节点映射策略 - 在相邻空节点未发生映射连接的情况下，URI和节点属性在区分空节点边界时具有重要参考价值.如果映射的邻居节点在最终映射中不同，合并具有相同邻居的节点数据.考虑到在计算增量时不同邻居可能产生的影响，综合考虑相邻空节点的上层映射关系，在候选对之间找到更大的近似.

4)自下而上近似空节点映射策略 - 根据上层映射的不同分类级别，实行差异化映射管理，优先处理较高级别的空节点映射.

3 空节点映射算法

在获取最大近似空节点后，执行节点映射时，通过增加NodeEquivalents(m)函数，映射TabG1[m]和TabG2[m]中具有等价连通的空节点，即与空节点具有完全相同标注谓词的节点(近似映射值等于1.0).采用启发式策略集中自下向上的近似策略，迭代映射剩余空节点，分级策略算法伪代码表示如下所示.

Algorithm ApproximationNode (x1, x2)

Input: x1, x2,approx

Output:approx,

1 NodeEquivalents(1);

2 NodeEquivalents(2);

3 While(approx>0)do;

4 min←approx[x2];

5 SearchApproximation(1,2,min);

6 SearchApproximation(1,3, min);

7 SearchApproximation(1,4, min);

8 t←approx;

9 While(t >min)do;

10 t←approx[x1];

11 SearchApproximation(1,1, approx);

12 NodeApproximation(1, approx);

13 EndWhile;

14 SearchApproximation(2,3, approx);

15 SearchApproximation(2,4, approx);

16 SearchApproximation(2,1, approx);

17 t←approx;

18 While(t >min)do;

19 t←approx[x1];

20 SearchApproximation(2,2, approx);

21 NodeApproximation(2, approx);

22 EndWhile;

23 NodeEquivalents(3);

24 SearchApproximation(3,4, approx);

25 SearchApproximation(3,3, approx);

26 SearchApproximation(3,2, approx);

27 t←approx;

28 While(t >min)do;

29 t←approx[x1];

30 SearchApproximation(3,3, approx);

31 NodeApproximation(3, approx);

32 EndWhile;

33 NodeEquivalents(4);

34 SearchApproximation(4,3, approx);

35 SearchApproximation(4,2, approx);

36 SearchApproximation(4,1, approx)

37 t←approx;

38 While(t >min)do;

39 t←approx[x1];

40 SearchApproximation(4,4, approx);

41 NodeApproximation(4, approx);

42 t←approx;

43 EndWhile;

44 approx←min;

45 EndWhile;

分级策略算法首先映射TabGk[1]和TabGk[2]中的等效空节点.采用自下而上映射，定义循环体.对每次迭代循环，min值随变量x2递减，将TabG1分区中的空节点映射到TabG2中.在搜索最大节点近似值时，while外循环提供了在不同图之间进行空节点映射的分区表，而内部循环负责在内部分区中执行映射操作，并返回最大近似映射节点.

4 实验与分析

本文使用RDF爬虫LDSpider构建RDF数据集，随机选择的链接数据集，包括Dbpedia、DBPL以及FOAF配置文件，采用宽度优先和负载平衡优先的双重抓取策略[12].考虑到算法的计算成本，在不影响测试效果的前提下，URI的最大数量将被限制.采用Wang等人定义的RDF空节点评价指标[14]进行实验分析：bdensity以及blen.令N和B分别表示图G的节点集和空节点集合，其中BN.令conn(b)定义G中直接与节点b相连的节点集合，其中b∈N，blen是指平均最大路径长度.上述评价指标定义如下.

实验采用宽度优先策略，采用宽度优先策略的空节点映射实例信息，表1给出使用的网爬数据集的基本信息.列| B | 和| G | 分别表示文件中的空节点数和三元组的平均数，列bdensity表示平均空节点密度，列blen是指平均最大路径长度.

表1 基于负载平衡策略的网爬数据集实例信息

考虑到所示算法的映射时间的差异，与ApproximationNode相比，算法映射时间显著增加，执行时间显著降低. 由于变量参数x1和x2存在显著差异，采用混合策略的空节点映射，采用宽度优先平衡策略，有效降低节点的迭代比较次数，提高映射的效率.

5 总结

本文针对空节点的标准化映射问题，通过优化存储版本控制程序，提升版本中空节点的语义映射质量与效率，基于粗糙集形式化模型近似表示方法，构建立近似映射模型，优化数据结构，降低节点之间的映射错误率.后续研究主要讨论RDF中空节点的遍历搜索效率问题，分析动态阈值参数在映射模型中的权值设定模型，优化系统的自适应能力，提高映射算法的准确性.

[1] Zeginis D, Tzitzikas Y, Christophides V. On computing deltas of RDFs knowledge bases[J]. ACM Trans Web, 2014, 5(3): 425-436.

[2]Lee S C, Jung J H, Lee J H. Characteristic Evaluation of RDF for the Combined Drying Produced by Weight Mixing Ratio Use Chemical Wastewater Sludge and Anthracite Coal[J]. 2016, 25(3):417-424.

[3] Noy NF, Kunnatur H, Klein M, et al. Tracking changes during ontology evolution[C]. ISWC2004, Proceeding of the 3rd International Semantic Web Conference, Hiroshima, Japan. 2004: 259-273.

[4] Guo Y, Pan Z, Heflin J. a benchmark for owl knowledge base systems. Web Semantic, 2014,14(6):158-182.

[5] Khilwani N, Harding J A. Managing corporate memory on the semantic web[J]. Journal of Intelligent Manufacturing, 2016, 27(1):101-118.

[6] Dimitris Zeginis, Yannis Tzitzikas, Vassilis Christophides. On Computing Deltas of RDF/S Knowledge Bases[J]. ACM Transactions on the Web (TWEB), 2011, 5(3):1-36.

[7] Hammoud M, Rabbou D A, Nouri R, et al. DREAM: distributed RDF engine with adaptive query planner and minimal communication[J]. Proceedings of the Vldb Endowment, 2015, 8(6):654-665.

[8]熊政, 王金明, 郑海雁,等. 一种基于可排序视图的RDF模式匹配算法[J]. 计算机工程与应用, 2016, 52(08):62-69.

[9]潘晓君,李如平. 基于RFID的二进制树形存储搜索算法的应用研究[J]. 枣庄学院学报,2017,34(02):123-127. [2017-09-21].

[10]吴菲,王欣. 移动学习领域基于机会感知的情境识别系统设计方法[J]. 枣庄学院学报,2016,33(02):109-111.

[11]Nwagwu H C. Visualising Inconsistency and Incompleteness in RDF Gene Expression Data using FCA[J]. International Journal of Conceptual Structures & Smart Applications, 2014, 2(1):68-82.

[12]章登义, 吴文李, 欧阳黜霏. 基于语义度量的RDF图近似查询[J]. 电子学报, 2015, 43(7):1320-1328.

[13]Wang X, Wang J, Zhang X. Efficient Distributed Regular Path Queries on RDF Graphs Using Partial Evaluation[C]// ACM International on Conference on Information and Knowledge Management. ACM, 2016:1933-1936.