基于最小波及效应的企业本体演化方法研究

刘世卿

(中航工业西安航空计算技术研究所， 陕西 西安 710119)

基于最小波及效应的企业本体演化方法研究

刘世卿

(中航工业西安航空计算技术研究所， 陕西 西安 710119)

本体演化会影响依赖本体的服务，使其重新修订和重新部署。面对同一变更需求，不同演化实现方法造成的影响范围差别很大。提出了一种基于最小波及效应(MRE)的本体演化算法。基于本体图模型建立了本体邻接矩阵和可达矩阵，凭借矩阵变换与运算对本体演化中节点组级与节点级的波及效应进行了深入的分析和量化。MRE算法将本体演化过程转变为求图的最短路径过程，通过搜索一条影响值最小的变更路径来减小本体演化的影响范围。通过实际应用验证，MRE算法的时间代价与变更影响范围大大小于现有算法。

本体演化；波及效应；本体变更路径；强子图

引 言

近年来，许多应用系统都采用本体作为语义支撑来满足不断增长的知识交换和知识集成需求。本体(Ontology)是某一领域共享概念模型的明确表示和描述，环境的变化和业务需求的多变性常常会引发支撑本体的演化[1]，由此产生了本体演化(Ontology Evolution)问题。本体的变化对本体所定义的数据、依赖于该本体的其他本体以及使用这些本体和数据的应用系统都会产生较大的影响[2]。

降低本体演化的影响可以从两个角度进行：1)降低本体演化的影响范围，即当本体演化后受到波及的服务个数越少越好。2)减轻服务的受影响程度，即如果某服务不可避免地受到波及，那么是否可以控制本体演化的过程使其朝着有利于服务修订的方向进行，使其变得尽可能的简单易行。其中需求2的满足依赖于服务的具体实现方式，难以提出一个通用的算法，本文主要从满足需求1的角度出发来探讨如何降低本体演化的影响。

当前本体演化研究的焦点在于保证演化需求的实现以及维护演化前后本体的一致性[3]，对于降低演化的影响关注甚少。由于本体演化的复杂性，大多数研究还停留在框架分析和定性讨论层面。而演化影响的降低不但可以显著减轻依赖本体的应用系统的开发和维护的负担，还可以大幅提高系统的健壮性和灵活性。当前，流行的本体编辑演化工具如OntoEdit[4]、OilEd[5]、KAON[6]都存在演化策略简单、依赖人工等问题[7-8]。

据此，本文基于本体图模型，凭借矩阵变换与运算对本体演化中的波及效应进行了深入的分析和量化界定。同时给出了本体元素影响度及受影响度的计算方法。在强分图理论的支持下定义了本体强子图，并分析了子图内聚度、强子图影响度的计算方法。在此基础上建立了基于最小波及效应(Minimal Ripple-effect, MRE)的本体演化算法，将本体演化过程转变为求图的最短路径过程，通过寻找一条影响值最小的变更路径来减小本体演化的影响范围。

1 本体图与本体矩阵

1.1 本体模型

本文所依赖的本体模型被定义一个二元组：

定义1 本体模型：OntModel:=(E,Imp)。

其中，E为本体的实体集合；Imp为导入的其他本体模型。

定义2 本体的实体集合E被定义为一个12元组：

E:=(C,P,I,Hc,Hp,label,domain,range,mincard,maxcard,instconc,instprop)

其中各组成详见文献[9]。

1.2 本体图与邻接矩阵

定义3(本体图) 一个本体O的图模型是一种有向的类型图G=，其中节点集V的元素对应O中的概念或关系，边集E的元素对应O中的函数、概念层次或关系层次。v∈V，v=，其中节点类型t对应本体概念或关系的ODM类型(如OWLClass)，A是节点的属性集合，a∈A，a=，即属性是名称和值的二元组。e∈E，e=，e的类型对应ODM中的表示关系的类型(如OWLOnProperty)，from∈V，表示边的始点，to∈V，表示边的终点。边的方向表示节点间的语义方向，V称为本体元素，E称为本体关系(不同于本体定义中“关系”的含义)。

基于本体和本体图模型定义可以将本体表示成图的形式，这种图形方式的本体模型清晰地体现出本体的结构性。例如，一个本体用基于ODM的模型表示如图1所示。

图1 本体模型举例

该本体的图模型则由10个结点和11条边组成，结点表示本体元素(Φ为空)：

v1=

v2=

v3=

v4=

v5=

v6=

v7=

v8=

v9=

v10=

边表示本体关系，边的方向表示终点对始点的依赖，边上标签的含义一般与依赖关系相反：

e1=

e2=

e3=

e4=

e5=

e6=

e7=

e8=

e9=

e10=

e11=

图2给出了本体图模型及其对应的邻接矩阵，现在可以使用图论方法处理本体。

图2 本体图模型及其对应的邻接矩阵

(1)

则图2对应的可达矩阵为

2 本体变更波及效应量化

本体演化是在本体元素发生变更时，通过相应其他元素的配套更改而重新达到本体一致的过程。本体演化算法通过顺序执行相应的变更操作来完成变更需求，每一个变更都将带来一系列元素的更改，最终导致一条变更执行路径的产生。分析本体演化的波及效应实质上就是分析变更操作及其组成的变更执行路径的波及效应。本体元素的变更操作可以分为4类：添加、删除、重命名和设置。其中添加、删除为基本操作，而重命名和设置可以由基本操作组合而成。虽然两种基本操作带来的波及效应不同，但只要确定变更所影响的元素，波及效应的计算方法是相同的。下面给出本体元素变更的波及效应量化方法。

2.1 本体元素量化

将各元素对本体结构的贡献大小排序，可以清楚地看出元素在本体中的重要性，也可以用于指导用户制订本体修改策略。如OR+的各行之和分别为4、5、5、3、3、3、0、3、3、3。因此在变更过程中避免对影响度较大元素的更改是必要的。影响度为零的本体元素为孤立元素。

定义6(本体元素受影响度) 假设本体图模型G=中有向边的距离都为1，节点vi到vj的最短距离为D(vi,vj)，则vj对应的本体元素受vi对应本体元素的变化的影响程度(受影响度)

(2)

不同本体元素的变化会对某一本体元素产生不同程度的影响，表现为本体图模型中到达同一节点的不同路径的长度。本体元素对应节点距离变化元素(变化源)对应节点越远，则该元素的受影响度越小。当多个关联元素发生变化时，vj的受影响度可以通过式(2)求和得到。

2.2 本体子图量化

定义7(本体子图) 针对本体图模型G=，存在一个本体图G′=，如果V′⊆V和E′⊆E，则G′是G的本体子图。

定义9(本体强子图) 内聚度为1的子图称为本体强子图。

3 MRE算法

文献[10]通过公式推导将本体演化带来的服务变更的减小问题转化为本体演化波及效应减小问题。这里直接针对本体演化波及效应的最小化展开讨论。根据上一节的分析，本体演化最小波及效应的问题可以归结为寻找一条变更执行路径，使得演化后的本体满足一致性约束且所改变的本体元素个数最小。MRE算法将最小演化代价问题转化为针对本体图的最短路径问题。其中，图的节点是本体元素，按照之前的讨论，节点赋值为该本体元素的影响度。

3.1 算法设计

算法寻找路径的过程为从变更元素的出边开始，到达所有可达孤立元素的过程。此时经历的路径称为搜索路径。依据算法的设计目标，MRE算法被描述为如下过程：在图的搜索过程中计算已搜索路径的变更影响值，如果该值大于已经搜索到的最小值就不再继续搜索。搜索过程中，已搜索路径的影响值小于原先搜索到的最小值，那么将作为一个新的备选解。MRE算法以一个待演化本体邻接矩阵以及一个变更元素为输入，以一条最小变更执行路径和最小影响值为输出。MRE算法描述如下：

输入：变更节点ChgNod，ChgNod与其可达的所有节点构造的邻接矩阵Q(可以通过待演化本体邻接矩阵构造)，Q的秩为N，infect为Q中节点的影响度。

输出：已经搜索到的最小影响值minValue和最小变更执行路径minPath。

算法：

Function MRE(Q, ChgNod){

//初始化，得到赋权邻接矩阵

minPath置空;

S置空; //已求出最短路径的顶点集合

S = S+ChgNod;

P[N][N] set false; //是否为最短路径上节点的标志位

O[N][N] set 0; //赋权邻接矩阵

for i∈[0, N-1] do

for j∈[0, N-1] do

if Q[i][j] equals 1

O[i][j]=infect[i];

P[i][j]=true;

end

end

end

D=O[0]; //记录最短路径值的数组

//寻找从ChgNod到所有可达孤立元素的最短路径

for i∈[0, N-1] do

minValue=0;

找出不在S中的离ChgNod最近的节点Vtemp;

S+=Vtemp;

minValue=D[Vtemp];

for j∈[0, N-1] do

if j∉S ∧ minValue+Q[Vtemp][j]

D[j]=minValue+Q[Vtemp][j];

P[j]=P[Vtemp];

P[i][j]=true;

end

end

end

//通过并操作，找到最小变更路径

for i∈[0, N-1] do

for j∈[0, N-1] do

if infect[i] equals 0 ∧ P[i][j] equals true

minPath=minPath∪j;

minValue+=D[j];

end

end

end

}

3.2 复杂度分析与改进

MRE算法的主体是求图顶点到各节点最短路径的过程，无论采用何种图存储方法其算法复杂度都为O(N2)，当本体规模增加时，算法执行时间的增加也很可观。根据2.2节对强子图的分析不难发现，当本体图中包含强子图时，MRE算法的搜索路径只要包含强子图的任意节点，算法的计算结果都是一样的，我们引入强子图节点化方法对算法进行简化。

定义10(强子图节点化) 由于对强子图任意元素的更改造成的波及效应等同于对整个强子图的更改造成的波及效应，为了分析方便我们将本体图的强子图转化为节点，该节点的先行后续关系为强子图所有节点对外关系的并集。这个过程称为强子图节点化，转化后的节点称为强节点。

如果本体图包含m个强子图，所有强子图总元素个数为n，那么结点化后本体图的节点数为N-n+m，算法复杂度降为O((N-n+m)2)。在本体图的构造过程中，原本的关联关系有包含、继承等多种，而图构造时都统一为连接线，这样本体图中很容易出现强子图；当本体图中元素个数很多时，不同元素间的关系错综复杂，也很容易出现强子图。因此在实际的演化路径生成过程中，强子图节点化在大多数情况下都可简化演化过程。

3.3 应用评价

某生产部门要打造中央级的产品资源集成门户，允许各级生产单元自主加入总体资源中。其本体片段如图3所示。在该集成门户的打造中，本体的构建是一个核心任务。各级生产单元依赖本体以统一的方式接入，由于事先不能确定加入共享资源的生产单元，因此无法事先构建出一个能满足所有需求的全局本体。另外，随着产品升级换代必然带来本体结构的变化。也就是说生产部门本体会随着生产单元的加入与产品升级换代而不断演化。但是，本体演化会对已构建的平台服务带来极大影响，每一次本体演化都可能引起平台服务的重新修订和重新部署[11]。因此，如何减轻本体演化对平台服务的影响就成为实现产品集成门户的关键。

图3 某产品本体演化示例

下面以图3所示的产品本体中的产品A片段为实验数据，验证不同变更算法的效率。该片段共涉及9种产品资源以及与这些资源相关的搜索、统计等共计60多个服务。为了方便比较不同变更算法的效率，我们使用元素变更率的概念，即：

变更率=演化后需要改变的元素个数/元素总数

(3)

采用Protégé、KAON变更执行算法和MRE算法分别对该本体执行演化后得到元素的变更率。以删除操作为例，实验内容和结果如表1所示。显然，MRE算法对元素的平均变更程度明显小于其他两种算法。

表1 实验内容及结果

表1反映出MRE算法的有效性主要体现在非叶节点的改变上，这是因为非叶节点与其可达所有节点构造的图中节点数较多。非叶节点在系统中的层次越高，其子节点和属性越多，与之关联的可达节点也越多，MRE算法有效性也越明显。对于叶节点的改变，3种算法所引起的服务变更率基本持平。这是因为当关联元素很少时，最短路径与一般路径的差别不是很大。从平均效果来看，Protégé和KAON算法的服务变更率基本持平。MRE算法的服务变更率则明显低于这两个算法，仅为其65%左右。该实验结果可以充分说明本文所提出算法能够有效减小本体变更的影响范围。

通过实验结果还可以发现MRE算法相比其他算法的特性。在整个本体图中，子部件2与非回转类零件的本体元素图中存在强子图，而子部件2中还存在一个影响度很大的节点。Protégé与KAON采用的演化算法之所以变更率较大还因为他们没有在变更路径中避开这些节点，而MRE算法通过最短路径的搜寻有效避开了这些节点，因而取得了较好的效果。因此在实际应用中，可以考虑以避开影响度大的节点尤其是强子图中的节点为先验知识的高速演化路径生成算法，在较小的时间复杂度下获得与MRE算法近似的次优解。

4 结束语

本文提出的MRE算法，以较小的时间代价使平均变更影响范围大大小于现有的本体演化算法。为了抽象出问题的本质，本文的分析没有考虑不同变更操作影响度的不同以及本体描述语言因素，进一步的研究工作包括针对具体本体语言的本体演化波及效应精确分析、本体演化算法等。

[1] LIU C, CHEN W H, HAN Y B. DODO: A mechanism helping to dynamically construct domain ontologies for services integration[C]//Proceedings of the International Workshop on Service-oriented Software Engineering, 2006: 13-18.

[2] MAEDCHE A, MOTIK B, STOJANOVIC L. Managing multiple and distributed ontologies on the semantic web[J]. The International Journal on Very Large Data Bases, 2003, 12(4): 286-302.

[3] HAASE P, SURE Y. State-of-the-art on ontology evolution[R]. Karlsruhe: University of Karlsruhe, 2004.

[4] SURE Y, ANGELE J, STAAB S. OntoEdit: Multifaceted inferencing for ontology engineering[J]. Journal on Data semantics, 2003(1): 128-152.

[5] BECHHOFER S, HORROCKS I, GOBLE C, et al. OilEd: A reasonable ontology editor for the semantic web[C]//Proceedings of the Joint German/Austrian Conference on Artificial Intelligence, 2001: 396-408.

[6] STOJANOVIC L, MAEDCHE A, MOTIK B, et al. User-driven ontology evolution management[C]//Proceedings of the 13th International Conference on Knowledge Engineering and Knowledge Management, 2002: 285-300.

[7] STOJANOVIC L, MOTIK B. Ontology evolution within ontology editors[C]//Proceedings of the OntoWeb-SIG3 Workshop at the 13th International Conference on Knowledge Engineering and Knowledge Management, 2002: 53-62.

[8] STOJANOVIC L, MAEDCHE A, MOTIK B, et al. Ontology evolution as reconfiguration-design problem solving[C]//Proceedings of the 2nd International Conference on Knowledge Capture, 2003: 162-171.

[9] STOJANOVIC L. Methods and tools for ontology evolution[D]. Karlsruhe: University of Karlsruhe, 2004.

[10] NOY N F, KUNNATUR S, KLEIN M, et al. Tracking changes during ontology evolution[C]//Proceedings of the 3rd International Semantic Web Conference, 2004: 259-273.

[11] BORST W N. Construction of engineering ontologies for kn- owledge sharing and reuse[D]. Enschede: University of Twente, 1997.

刘世卿(1983-)，女，硕士，主要研究方向为计算机辅助制造，电子设备结构设计。

Study on Enterprise Ontology Evolution Method Based on Minimal Ripple-effect

LIU Shi-qing

(AVICXi′anInstituteofAviationComputingTechnology，Xi′an710119,China)

Ontology evolution has an effect on services relying on ontology, and makes them revised and redeployed. Facing the same change demands, different evolution implementation methods have greatly different influence scope. This article provides an ontology evolution algorithm based on minimal ripple-effect (MRE). Ontology adjacency matrix and reachability matrix based on ontology graph model are established. In-depth analysisand quantification for the ripple-effects at node-group level and node level in ontology evolution are carried out by matrix transformation and operation. The MRE algorithm transforms ontology evolution process into the process of calculating shortest graph path. It searches a change path with smallest effect-value to decrease the influence scope of ontology evolution. The actual application and demonstration indicate that the MRE algorithm costs a much smaller graph searching time and has a much smaller change influence scope than current algorithm.

ontology evolution; ripple-effect; ontology change path; strong sub-graph

2013-10-23

TP391

A

1008-5300(2014)02-0051-06