本体演化中基于TFOF的波及效应分析

Analysis for Ripple-Effect Based on TFOF in Ontology Evolution

摘要

通过定量地评估本体中概念或实体的波及效应，本体的所有者和使用者均能够准确、全面地分析本体演化。现有方法初步量化了本体中的波及效应，但是并未考虑本体中语义关系强弱对于波及效应的影响。针对上述问题，本文提出了基于术语频率与本体频率(term frequency and ontology frequency，TFOF)的定量评估方法，并将其应用于本体演化研究。该方法利用本体中语义关系的出现频率计算关系的权重，从而获得本体所对应的语义关系矩阵，最后运用改进的Floyd-warshall算法计算各个概念或实体的波及效应。实验结果表明，基于TFOF波及效应的评估方法能够更精准地度量本体演化过程中概念或实体的波及效应，且该方法对不同版本中共有结点的度量结果更加稳定。

Abstract

By evaluating the ripple-effect of concepts or entities in the ontology, both the owner and the user of the ontology can accurately and comprehensively analyze the ontology evolution. This paper proposes a quantitative evaluation method based on the TFOF (term frequency and ontology frequency) and applies it to ontology evolution research due to the fact that the existing methods do not consider the influence of the semantic relationship between the ontologies. This paper uses the frequency of the semantic relationship in the ontology to calculate the weight of the relationship to obtain the semantic relation matrix corresponding to the ontology. Finally, the improved Floyd-warshall algorithm is used to calculate the ripple-effect of each concept or entity. The experimental results show that the evaluation method based on the TFOF ripple-effect can measure the ripple-effect of concepts or entities in the evolution process of ontologies with higher accuracy, and the results of the common nodes in different versions are more stable.

Graphical abstract

关键词

本体演化 / 波及效应 / 语义关系 / TFOF算法

Key words

ontology evolution / ripple-effect / semantic relationship / TFOF( term frequency and ontology frequency) algorithm

0　 引 言

本体在演化过程中由于其中的概念、约束关系等某部分的改变会导致本体进入到不一致的状态，本体内部的不一致性对基于本体的应用会产生不良影响。随着本体不断增大，维护本体一致性的成本也逐步上升。当一个概念发生变化时，如果能准确判断其波及的范围，在一个小范围内验证本体的一致性将有助于降低本体维护成本，提升本体质量。本体波及效应分析就是借鉴软件工程中软件演化波动性的一种分析方法^[1,2]。

目前，国内外学者对本体演化中的波及效应已进行大量的研究^[3,4]。在本体演化过程中对本体波及效应的度量能够帮助本体使用者对本体进行较细致地分析^[5]。针对本体演化中某个结点的变化对整个本体可能会造成较大影响的问题，Sall等^[6]提出基于断言和本体逆向工程的本体演化模型，用于控制本体演化中的波及效应，并且在其后续的工作^[7]中考虑到了本体中个体的变化对于其他结点的综合影响，通过相应的前置条件、后置条件和定量分析，提出计算本体演化过程中结点综合影响力的算法；文献[8]基于原有分析方法，构建了合适的本体并设置相应变化，提出了用香农熵的概念来度量本体中的结构或语义的每次变化操作对本体的影响程度。以上方法分析了本体演化过程中的波及效应的影响，但是并未对本体演化中的波及效应进行具体地量化。

在国内，众多的学者试图对本体演化的波及效应进行具体地度量。金龙飞等^[9]从定量分析角度给出了本体演化波及效应的分析和具体计算方法，通过建立本体邻接矩阵和可达矩阵，以矩阵变化计算本体元素对本体结构综合影响力。该方法并未考虑到本体元素之间的各种关系，鉴于此刘晨等^[10]分析了服务之间的依赖关系，提出了量化变更影响范围的数学公式；尚晋等^[11]则基于描述逻辑语言定义本体中元素间的依赖关系，建立了本体依赖关系图模型；在更新本体演化传播模型的前提下，刘世卿^[12]提出一种基于最小波及效应的本体演化算法。依赖关系具体该如何度量，以上研究中并没有说明，于是在基本演化模型的基础上，考虑到本体间语义关系对本体演化中波及效应的影响，文献[13]对本体中的语义关系给出了一个级别定义，进而计算本体演化中的波及效应，该方法对于同一个级别的语义关系只设置了相同的语义权重。

上述方法虽然量化了本体演化的波及效应，但均未考虑语义关系的强弱对波及效应的影响，而一个本体元素的变化会对本体中其他元素产生影响，不同的语义关系为演化带来的影响大小也不尽相同^[10]。本体中出现的某种关系越多，表明该关系在本体中占有越重要的地位，所以本文在本体语义关系图模型的基础上，使用TFOF(term frequency and ontology frequency)算法^[14]对本体演化过程中的语义关系进行了更加精确地量化，分别统计每一个关系在本体中出现的频率，然后计算出该关系的权重，最后通过语义关系矩阵与改进后的Floyd-warshall算法计算本体在演化过程中的波及效应的变化。

1　 本体的语义关系图模型

本文将本体用一个关系图模型表示，通过本体图模型表示本体演化过程中的元素。

本体由类、属性和实例组成。本体中属性主要用于构建不同资源之间的语义关系^[14]，因此可以将属性转化为资源间的语义关系，构建不含属性结点的本体演化图模型。然后在本体演化过程中，将属性的变化作为本体演化时的额外条件，用于更新不同资源之间的语义关系。本文选择果蝇本体（https://github.com/FlyBase/flybase⁃controlled⁃vocabulary/blob/master/releases/2018-01-03/dpo.owl）的最新版本中的部分结点作为实例来介绍本文算法。为了方便理解，在表1中列出结点编号及结点标签，根据结点之间的语义关系，构建出如图1的本体语义关系图模型。

定义1本体语义关系图模型

本体的语义关系图模型是一个带标签的有向图G。G=〈E,R〉,其中，E=\{e_i | i\in1,2,3,…,n,e_i\inO\}，表示本体中的结点集（包含本体中的概念、实例等实体），e_i 是E中某个实体。R=\{r_ij | r_ij\inO\}，表示本体中的语义关系集合，r_ij=r(e_i,e_j ),即本体O中出现的e_i 与e_j 之间的语义关系，e_i 为关系的起点，e_j 为关系r_ij 的终点。

本体语义关系模型在演化过程中的操作主要为增加、删除和编辑。当本体结构发生变化时，首先判断结点是否发生改变，如果结点改变，则删除发生改变的原有结点，增加新结点并完善新结点与原有结点的关系，在更新完本体中元素以及其关系后，完成一次本体的演化。在本体完成一次演化操作之后，原版本的本体就演化为了新版本的本体，在逐步演化的过程中就会形成多个版本的本体，若本体语义关系图模型第一个版本为G(v₁)，在本体一次演化后本体图模型表示为G(v₂)，经过n次演化的本体模型表示为G(v_n+1)。

2　 基于TFOF的波及效应度量

2.1 基于TFOF的语义关系量化

语义关系反映了本体之间的关联强度，不同的关联强度对于本体之间的波动影响强度会有一定影响。本体中语义关系包含的结点越少，关系的复杂度越低，两个类术语之间关系越强。如，上下位关系是术语间直接且强烈的语义关系，存在量化关系是术语间比较弱的语义关系^[11]。

本文将不同级别的关系按照关系等级分别赋予四个等级，并给出初始的关系权重，如表2所示，此处权值按照文献[14]设定为1,1/2,1/3,1/4。

表2中的关系权重是根据关系等级给出的初始权值，本文的目标是精确计算每个关系的权重。在自然语言处理的过程中，通常用文档频率来确定词语在整个数据集中的重要性。但是在本体中，由于术语的广泛性，文档频率不应该作为关系强度评估的惩罚因子，故提出一种基于TFOF的方法计算语义关系的强度。计算过程如下：

1） 计算关系r_ij 相对本体中各个结点中的比重

\mathrm{t}\mathrm{f}(r_{ij},e_i)=\mathrm{1}+\frac{\mathrm{0.5}\times f(r_{ij},e_i)}{\mathrm{m}\mathrm{a}\mathrm{x}\left\{f(r_x,e_i)|r_x\in R(e_i)\right\}},

i=\mathrm{1,2},\cdots ,n,r_{ij}\in R(e_i)(1)

设O表示某个本体，r_ij 表示本体O中出现的语义关系，e_i 表示本体O中出现的某个结点，f(r_ij,e_i)表示与结点e_i 相关且以e_i 为关系起点的关系r_ij 出现的次数，R(e_i )表示与e_i 相连并且与e_i 为关系起点的关系种类集合，\mathrm{m}\mathrm{a}\mathrm{x}\left\{f(r_x,e_i)|r_x\in R(e_i)\right\}表示与结点e_i 相关且以e_i 为关系起点的关系出现的最多的次数。如图1，与e₁₀相关的关系inverseOf出现次数为1，且与e₁₀结点相关的关系中出现次数最多的关系的次数为1，所以domain的tf(r_ij,e₁₀)=1+0.5×1/1=1.5,即关系inverseOf相对第一个结点的比重为1.5。

2） 计算关系r_ij 在本体O中出现次数的平均比重

\mathrm{t}\mathrm{f}(r_{ij},O)=\frac{\stackrel{n}{\sum _{i=\mathrm{1}}}\mathrm{t}\mathrm{f}(r_{ij},e_i)}{\stackrel{n}{\sum _{i=\mathrm{1}}}f(r_{ij},e_i)},e_i\in O,r_{ij}\in R(e_i)(2)

在图1中，inverseOf出现的次数为2，与e₈和e₁₀相关的出现次数均为1。因此，tf(“inverseOf”,e₈)和tf(“inverseOf”,e₁₀)均为1.5。所以，\stackrel{n}{\sum _{i=\mathrm{1}}}\mathrm{t}\mathrm{f}(r_{ij},e_i)=3，tf(“inverseOf”,O)=(1.5+1.5)/2=1.5，即关系inverseOf在本体O中出现的平均次数为1.5。

3） 计算关系r_ij 在本体O中出现的广泛程度。广泛程度依下式计算

\mathrm{d}\mathrm{f}(r_{ij},O)=\mathrm{1}+\mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{1}+\frac{\stackrel{n}{\sum _{i=\mathrm{1}}}\mathrm{r}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(e_i,r_{ij},O)}{\stackrel{n}{\sum _{i=\mathrm{1}}}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(e_i,O)}),

r_{ij}\in R(e_i)(3)

其中，\stackrel{n}{\sum _{i=\mathrm{1}}}\mathrm{r}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(e_i,r_{ij},O)是以r_ij 为关系起点的结点的数量，\stackrel{n}{\sum _{i=\mathrm{1}}}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(e_i,O)是本体O中结点的数量。图1中，\stackrel{n}{\sum _{i=\mathrm{1}}}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(e_i,O)=10，inverseOf的\stackrel{n}{\sum _{i=\mathrm{1}}}\mathrm{r}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(e_i,r_{ij},O)=2，df(“inverseOf”,O)=1+log(1+2/10)=1.079。

4） 计算关系r_ij 在一个本体中语义上使用的普遍程度。普遍程度计算如下

\mathrm{T}\mathrm{F}\mathrm{O}\mathrm{F}(r_{ij},O)=\mathrm{t}\mathrm{f}(r_{ij},O)\times \mathrm{d}\mathrm{f}(r_{ij},O)(4)

图1的语义关系inverseOf的TFOF的值为1.5×1.079=1.619。

5） 计算关系r_ij 在本体O中的权重

w(r_{ij})=\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{a}\mathrm{l}(r)\times \frac{\mathrm{T}\mathrm{F}\mathrm{O}\mathrm{F}(r,O)}{\mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{T}\mathrm{F}\mathrm{O}\mathrm{F}(r_i,O)\}},

r_i\in R(e_i),e_i\in O,i=\mathrm{1,2},\cdots ,n(5)

(5)式中，initial(r)表示关系r对应的初始权重。通过计算可知图1所使用的关系中TFOF最大值为1.619，所以w(“inverseOf”)=1/3×(1.619/1.619)=1/3。即在实例中，inverseOf的语义关系权重为1/3。

根据以上定义，对图1中的关系进行量化，得到各关系的最终权重结果如表3所示。

2.2 波及效应矩阵

依据上述基于TFOF的语义关系，构建本体的语义关系矩阵。

定义2语义关系矩阵

设本体元素集合为E=\{e₁,e₂,…,e_n\}，则本体语义矩阵 M (R)=[WR _ij ],其阶为n，WR _ij 表示元素e_i 和e_j 之间的语义关系权重，定义如下

\mathrm{W}{\mathrm{R}}_{ij}=\left\{\begin{array}{l}w(r_{ij}),r_{ij}\in R\\ \mathrm{0},r_{ij}\notin R\end{array}\right.(6)

其中i,j=1,2,…,n。

依据该定义，图1的语义关系矩阵表示如下

\mathit{M}(R)=\left[\begin{array}{cccccccccc}\mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0.294}& \mathrm{0}& \mathrm{0}& \mathrm{0.294}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0.333}& \mathrm{0.294}& \mathrm{0}& \mathrm{0.333}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0.334}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0.333}& \mathrm{0.333}& \mathrm{0.333}& \mathrm{0.333}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0.294}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0.367}& \mathrm{0}& \mathrm{0.294}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}.& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0.294}& \mathrm{0}& \mathrm{0.367}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right](7)

在本体关系矩阵中，e_i 和e_j 之间的语义关系权重就是e_i 和e_j 之间的关系强度。由（7）式可知e₁和e₂之间的关系强度为0.294。

在本体的演化中，当一个本体元素变化时，会对其他元素产生影响，此即为波及效应。计算某个结点的波及效应实质上是计算本体语义矩阵中某一结点到其他结点之间权重最大路径。Floyd-warshall算法通过动态规划的方式求得多源最短路径，本文对Floyd-warshall进行修改。将语义关系矩阵作为算法的输入，结点之间权重采用累乘的方式进行传播，在更新路径的时候，比较新的路径权重与原有路径权重，只有新的路径权重大于原有路径权重才更新原有路径权重。这样通过修改的Floyd-warshall算法可计算出基于TFOF的波及效应矩阵RippleEffectMatrix( M (R))。Function RippleEffectMatrix如下

由（7）式可得图1的基于TFOF的波及效应矩阵如下

\mathrm{R}\mathrm{i}\mathrm{p}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{E}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{x}(\mathit{M}(R))=\left[\begin{array}{cccccccccc}\mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0.294}& \mathrm{0}& \mathrm{0}& \mathrm{0.294}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0.333}& \mathrm{0.294}& \mathrm{0}& \mathrm{0.333}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0.113}& \mathrm{0.099}& \mathrm{0.338}& \mathrm{0.113}& \mathrm{0}& \mathrm{0.333}& \mathrm{0.333}& \mathrm{0.333}& \mathrm{0.333}& \mathrm{0.333}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0.294}& \mathrm{0.108}& \mathrm{0}& \mathrm{0.086}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0.367}& \mathrm{0}& \mathrm{0.294}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0.294}& \mathrm{0}& \mathrm{0.367}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right](8)

从波及效应矩阵知，e_i 对e_j 的影响力

\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}(e_i)=\mathrm{R}\mathrm{i}\mathrm{p}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{E}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{x}(\mathrm{M}{\mathrm{R}}_{ij})(9)

从（8）式可知e₁对e₅的影响力为0.113，e₈对e₁₀的影响力为0.294，而e₂对e₁₀没有影响。

不仅某个e_j 会受e_i 影响，其他的结点也会受e_i 影响，定义e_i 的综合影响力如下

\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{A}\mathrm{l}\mathrm{l}(e_i)=\stackrel{n}{\sum _{j=\mathrm{1}}}RippleEffectMatrix(M{R}_{ij})(10)

由(8)式可知e₃的综合影响力为0.333+0.294+0.333=0.960。通过基于TFOF的波及效应矩阵可以计算出每一个结点的综合影响力，如表4所示。

2.3 本体演化中的波及效应

在本体演化过程中，本体会产生多个版本，结点e_i 在本体的第j个版本中的综合影响力就是结点e_i 在版本v_j中的波及效应。

对于某一个本体来说，某个结点的波及效应在本体演化的过程中会发生变化。若结点e_k 在演化过程中其周围新增一些结点，那么本体的综合波及效应会增加；若结点e_k 在本体更新过程中，其周围没有增加或删除对其有影响的结点，那么e_k 在更新后的版本中其波及效应将不会发生变化。在本体演化的各个版本，波及效应变化的结点为本体中重要的结点。对本体中结点的波及效应度量得越精确，就越可以捕获到更多细微的变化。

定义3共有结点

设本体O有n个版本\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_n\},各个版本所对应语义关系图模型为\{G(v₁)=〈E₂,R₁〉, G(v₂)=〈E₂,R₂〉,…, G(v_n )=〈E_n,R_n 〉\}，则O的共有结点A(O)=\{E_{\mathrm{1}}\wedge E_{\mathrm{2}}\wedge \dots \wedge E_n\}。

共有结点作为本体所有版本内都保留的结点，在分析本体演化趋势的时候其数据更具有参考意义。通常而言，本体演化过程中重要结点的波及效应缓步上升，而不应该在版本迭代的过程出现较大幅度起伏，即在本体演化中，本体的波及效应度量值的变化越稳定越符合本体演化的趋势。

在研究本体演化过程中结点的波及效应变化时，为了避免非共有结点造成实验结果的不准确性，本文只计算共有结点的波及效应变化，即AffectAll(e_k,v₁), AffectAll(e_k,v₂ ),\cdots ,AffectAll(e_k,v_n ),e_k\inA(O)。

3　 实验与评估

3.1 数据集

本文使用三个本体进行实验，分别为：Ontology of Biological and Clinical Statistics(obc), obc是关于生物学和临床统计学的本体; Drosophila Phenotype Ontology(dpo),dpo本体中是关于果蝇表型的各项数据;FlyBase Controlled Vocabulary(fbcv),fbcv是一个由FlyBase发布的结构化受控词汇表本体，包括果蝇表型本体。本体下载网址以及相关的参数已在表5中列出。

3.2 实验分析

将本文方法与文献[5,9]中方法作对比。文献[5]将本体演化过程转化为可达矩阵的计算，所以将该方法称为RPA方法，文献[9]在波及效应的计算过程中添加了语义关系的初步度量，所以将文献[9]的方法称为G-RPA；本文提出的方法命名为TFOF-RPA方法。

3.2.1 本体演化中的波及效应变化

为了验证上述分析的准确性，本文将从分析本体演化过程中结点波及效应的变化来评估本文中基于TFOF的方法与文献[5,9]方法的优劣。

本文记录每个本体在三种方法下每个结点随版本的变化而产生的波及效应变化，然后计算每个结点在所有版本中波及效应的波动范围。假定本体O有n个版本，拥有结点数量为m，对于特定的结点k，定义e_k 的波及效应在所有版本中的变化幅度为

\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(e_k)=\mathrm{m}\mathrm{a}\mathrm{x}(\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{A}\mathrm{l}\mathrm{l}(e_k,v_j))-\mathrm{m}\mathrm{i}\mathrm{n}(\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{A}\mathrm{l}\mathrm{l}(e_k,v_j)),j\in \{\mathrm{1},\mathrm{2},\cdots ,n\}(11)

为了让结果对比更加准确，将所有的结果进行标准化得到

\mathrm{S}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(e_k)=\frac{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(e_k)-\mathrm{m}\mathrm{i}\mathrm{n}\{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(e_{{}_i})\}}{\mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(e_i)\}-\mathrm{m}\mathrm{i}\mathrm{n}\{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(e_i)\}}

i=\mathrm{1,2},\cdots ,m(12)

计算本体中每个结点的Srange（e_k ），然后统计其值在不同范围内个数的占比，如obc中总结点数目为719，其中Srange（e_k ）值为0的个数为583，所以该本体波及效应变化为0的结点个数占比为81.08%。统计三个本体在各方法下Srange（e_k ）的值所在范围占比，得到如表6所示的数据。从表6中可以看出各方法捕获细微波及效应变化的能力，以评估各方法量化本体演化过程中结点波及效应变化的精准度。

在RPA与G-RPA方法中，对于本体的具体语义关系没有给出一个精确的度量。在演化过程中，如果结点e_k 周围的的结点发生了变化，从波及效应值的角度来看，RPA与G-RPA方法捕获不到这些语义关系上的变化对于本体的影响。在波动范围为0的结点数占比中，RPA和G-RPA方法得到的结点数占比都大于TFOF-RPA方法，表明RPA和G-RPA方法捕获不到更多变化的结点；在(0,0.1]区间中，TFOF-RPA方法可以捕获到更多的结点。由于TFOF-RPA方法考虑到了本体中语义关系的权重，相比于RPA和G-RPA方法度量出的波及效应，它具有更高的精准度，能够捕获本体演化中概念和实体的细微变化。

3.2.2 共有结点的波及效应分析

本节计算本体演化中共有结点的波及效应的方差，比较在不同版本中方差的变化，判断共有结点在本体演化过程中波及效应变化稳定性。由于各个方法的计算结果范围的差异较大，本文对于共有结点的波及效应先进行标准化然后再进行相关计算。

假设在本体O中拥有n个版本，共有结点数目p个，使用(12)式对各结点的波及效应进行标准化：

\mathrm{S}\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{A}\mathrm{l}\mathrm{l}(e_k,v_i)=

\frac{\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{A}\mathrm{l}\mathrm{l}(e_k,v_i)-\mathrm{m}\mathrm{i}\mathrm{n}\{\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{A}\mathrm{l}\mathrm{l}(e_j,v_i)\}}{\mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{A}\mathrm{l}\mathrm{l}(e_j,v_i)\}-\mathrm{m}\mathrm{i}\mathrm{n}\{\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{A}\mathrm{l}\mathrm{l}(e_j,v_i)\}}

i=\mathrm{1},\mathrm{2},\cdots ,n;j=\mathrm{1},\mathrm{2},\cdots ,p(13)

由共有结点的波及效应标准差，可以得到每一个版本中的方差

\mathrm{v}\mathrm{a}\mathrm{r}(v_i)=

\frac{\stackrel{p}{\sum _{j=\mathrm{1}}}(\mathrm{S}\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{A}\mathrm{l}\mathrm{l}(e_j,v_i{)-\frac{\stackrel{p}{\sum _{j=\mathrm{1}}}\mathrm{S}\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{A}\mathrm{l}\mathrm{l}(e_j,v_i)}{p})}^{\mathrm{2}}}{p}

i=\mathrm{1},\mathrm{2},\cdots ,n(14)

图2中分别是obc、dpo和fbcv本体在三种方法下的共有结点的波及效应的方差对比图。由图中可以发现，所有方法计算的方差整体的趋势都是随着版本的变化而越来越小，验证了本体在演化过程中的稳定性。对于obc本体，在第三个版本中方差变化较大。通过比较原始数据集，发现对于obc本体，随着版本更新，其原始owl文件的大小分别为919 kb，936 kb，1 110 kb，1 126 kb，1 150 kb，1 152 kb，在第三个版本中，本体数据发生了一个较大的版本变化，故在第三个版本中方差也发生了一个较大的变化。对比三种方法，本文中提出的TFOF-RPA方法的方差值均小于G-RPA和RPA方法，因为TFOF-RPA方法考虑到影响本体中波及效应的语义关系的变化因素，相比于G-RPA和RPA方法具有更高的稳定性。

综合本体演化过程的波及效应变化以及共有本体的波及效应，可以看出本文所提出的TFOF-RPA方法能够较精准地度量本体演化过程中概念或实体的波及效应，同时在本体共有结点方差值的对比中，TFOF-RPA的波及效应度量值波动相对稳定。

4　 结 语

本文基于现有的本体演化波及效应度量方法，提出TFOF-RPA算法，通过计算本体中的语义关系权重，对本体中语义关系进行更精确地度量，进而对本体演化过程中结点波及效应的变化有更精确的度量，可以更清楚地观察在本体的演化过程中本体各个结点随着版本的变化其波及效应的变化，同时对于重要结点的定位有一定的参考意义，能够帮助本体的所有者和使用者准确、全面地分析本体的构建及其演化，并为本体后续的更新提供了依据。

本文中波及效应的计算是基于Floyd-warshall算法的，方法的时间复杂度相对较高，对于较大数据集，会导致计算速度受到一定影响。对于如何改善本体演化波及效应中的计算方式，提升计算速度，需要继续研究。

参考文献

[1] KATIFORI A, VASSILAKIS C, LEPOURAS G, et al. Effectiveness of visualization for information retrieval through ontologies with entity evolution: The impact of ontology modeling[J]. International Journal of Information Retrieval Research, 2017, 5(2):66-91. DOI: 10.4018/IJIRR.2015040104 .

[2] KONDYLAKIS H, DESPOINA M, GLYKOKOKALOS G, et al. EvoRDF: A Framework for Exploring Ontology Evolution[DB/OL]. [2019-09-10].

[3] TANG H, MUNGALL C J, MI H, et al. GOTaxon: Representing the Evolution of Biological Functions in the Gene Ontology[DB/OL]. [2019-09-10].

[4] NADAL S, ROMERO O, ABELLÓ A, et al. An integration-oriented ontology to govern evolution in big data ecosystems[J].Information Systems,2019，79:3-19. DOI：10.1016/j.is.2018.01.006.:S0306437917304660 .

[5] GUZZI P H, AGAPITO G, MILANO M, et al. The Impact of Gene Ontology Evolution on Go-term Information Content [DB/OL]. [2019-09-12].

[6] SALL O, THIAM M, LO M, et al. A model for ripple effects of ontology evolution based on assertions and ontology reverse engineering[J]. Communications in Computer & Informationence, 2011, 240:155-162. DOI: 10.1007/978-3-642-24731-6_15 .

[7] SALL O, THIAM M, LO M, et al. A model for ripple effects analysis of cascading problems in ontology evolution[J]. International Journal of Metadata Semantics & Ontologies, 2012, 7(3):171-184.DOI：10.1007/978-3-642-24731-6_15 .

[8] BOUSSO M, SALL O, THIAM M, et al. Ontology Change Estimation Based on Axiomatic Semantic and Entropy Measure[DB/OL]. [2019-09-10].

[9] 金龙飞, 刘磊. 一种本体演化波及效应分析方法[J]. 电子学报, 2006, 34(8):1469-1474. DOI: 10.13413/j.cnki.jdxblxb.2012.01.004 .

[10] JIN L F, LIU L. Ripple-effect analysis method for ontology evolution[J]. Acta Electronica Sinica, 2006, 34(8):1469-1474. DOI: 10.13413/j.cnki.jdxblxb.2012.01.004（Ch).

[11] 刘晨, 韩燕波, 陈旺虎, 等. MINI——一种可减小变更影响范围的本体演化算法[J]. 计算机学报, 2008, 31(5):711-720. DOI: CNKI:SUN:JSJX.0.2008-05-002 .

[12] LIU C, HAN Y B, CHEN W H, et al. MINI: An ontology evolution algorithm for reducing impact ranges [J]. Chinese Journal of Computers, 2008, 31(5):711-720. DOI: CNKI:SUN:JSJX.0.2008-05-002（Ch).

[13] 尚晋, 张睿, 吕帅, 等. 基于依赖关系图模型的本体演化影响分析[J]. 吉林大学学报(理学版), 2012, 50(1):89-94.DOI：10.13413/j.cnki.jdxblxb.2012.01.004 .

[14] SHANG J， ZHANG R， LÜ S, et al. Impact analysis of ontology evolution based on dependency graph model[J]. Journal of Jilin University(Science Edition), 2012, 50(1):89-94.DOI：10.13413/j.cnki.jdxblxb.2012.01.004（Ch).

[15] 刘世卿. 基于最小波及效应的企业本体演化方法研究[J]. 电子机械工程, 2014, 30(2):51-56.DOI: 10.19659/j.issn.1008-5300.2014.02.016 .

[16] LIU S Q. Study on enterprise ontology evolution method based on minimal ripple-effect[J]. Electro⁃Mechanical Engineering, 2014, 30(2):51-56.DOI: 10.19659/j.issn.1008-5300.2014.02.016（Ch).

[17] LÜ Q Y, ZHANG Y P, GU J H. The analysis for ripple-effect of ontology evolution based on graph[C]// International Conference on Computational Science and Its Applications. Cham:Springer International Publishing, 2016:261-276.DOI: 10.1007/978-3-319-42089-9_19 .

[18] 张祥, 李星, 温韵清,等. 语义网虚拟本体构建[J]. 东南大学学报(自然科学版), 2015, 45(4):652-656.DOI: 10.3969/j.issn.1001-0505.2015.04.007 .

[19] ZHANG X, LI X, WEN Y Q, et al. Building virtual ontologies in semantic web[J]. Journal of Southeast University, 2015, 45(4):652-656. DOI: 10.3969/j.issn.1001-0505.2015.04.007(Ch).

基金资助

国家自然科学基金(61673304)

国家社会科学基金重大计划(11&ZD189)