基于关联解释的术语集mups求解方法-崔仙姬.pdf

《基于关联解释的术语集mups求解方法-崔仙姬.pdf》由会员分享，可在线阅读，更多相关《基于关联解释的术语集mups求解方法-崔仙姬.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第54卷 第1期2018年1月南京大学学报(自然科学)JOURNAL OF NANJING UNIVERSITY( NATURAL SCIENCE)Vol. 54, No. 1Jan. , 2018基金项目:国家自然科学基金( 61672261, 61502199, 61402070) ,辽宁省自然科学基金( 2015020023) ,符号计算与知识工程教育部重点实验室开放课题( 93K172016k02) ,大连民族大学自主基金( DC201501060)收稿日期: 2017- 12- 09通讯联系人, E- mail: urchin2012 sina. comDOI: 10. 13232

2、/ j. cnki. jnju. 2018. 01. 007基于关联解释的术语集M UPS求解方法崔仙姬1, 2 ,欧阳丹彤2, 3 ,何加亮1 ,高 健4( 1.大连民族大学信息与通信工程学院,大连, 116600; 2.符号计算与知识工程教育部重点实验室(吉林大学) ,长春, 130012; 3.吉林大学计算机科学与技术学院,长春, 130012; 4.大连海事大学信息科学技术学院,大连, 116026)摘 要:本体调试是人工智能中非标准推理任务之一,主要用于找出本体中导致逻辑冲突的解释并进行修改,对于本体工程具有重要意义.结合语法相关性与关联解释,提出一种术语集的极小不可满足子术语集求解

3、方法.语法相关性用于递归扩展不可满足子术语集,从待测术语集中将与不可满足概念语法相关的公理集合加入到不可满足子术语集,一定程度上减少了不相关公理的加入,可以有效减少待测术语集规模.进一步地,将术语集的极小不可满足保持子术语集( minimal unsatisfiability- preserving sub- TBox, M UPS)的求解过程看作是关键公理的查找过程.提出关联解释的定义,并通过构造术语集的关联解释方式确定关键公理.该过程一定程度上减少了推理机调用次数并简化了每次调用用于找出问题时的推理任务.实验部分将各类优化策略应用于黑盒算法并进行了比较.实验结果表明,该方法能够有效提高术语

4、集M UPS求解效率.关键词:描述逻辑,本体调试,极小不可满足保持子术语集,关联解释中图分类号: TP391 文献标识码: AAssociate interpretation based M USP calculation in terminologiesCui Xianji1, 2 , Ouyang Dantong2, 3 , He Jialiang1 , Gao Jian4( 1. College of Information and Communication Engineering, Dalian M inzu University, Dalian, 116600, China;2.

5、Key Laboratory of Symbol Computation and Knowledge Engineering( Jilin University) ,M inistry of Education, Changchun, 130012, China;3. College of Computer Science and Technology, Jilin University, Changchun, 130012, China;4. College of Information Science and Technology, Dalian M aritime University,

6、 Dalian, 116026, China)Abstract: Ontology debugging is one of the non- standard reasoning tasks in artificial intelligence, which is veryimportant for the ontology engineering. Ontology debugging is mainly used to find out the interpretations which maycause the logical conflicts in ontologies, and f

7、urther revise the ontologies to eliminate these conflicts. Technically, cal-culating minimal unsatisfiability- preserving sub- TBox( M UPS) is the core issue in the ontology debugging. Theexisting work of M UPS calculation investigates two approaches: one based on modifying the internal of a descrip

8、tionlogic reasoner( the “ glass- box” technology) , and other based on using an unmodified external reasoner( the “ black-box” technology) . In our work, one method using syntactic relevance and associate interpretation is proposed tocalculate the M UPS for the unsatisfiable classes and terminologie

9、s. This method is based on the traditional black- box万方数据 第1期崔仙姬等:基于关联解释的术语集M UPS求解方法technology, and further optimizes the expansion and prune procedure in the traditional black- box technology. Firstly,we extend the candidate unsatisfiable sub- TBox by adding the axioms which are structurally relev

10、ant with the axiomsthat contain unsatisfiable classes. By doing this, we can eliminate the irrelevant axioms for the satisfiability to theextent, which may reduce the size of the axioms in terminologies to be checked. Then, the M UPS calculation can beseen as the procedure of seeking the critical ax

11、ioms in the M UPS. In this procedure, we propose the definition of theassociate interpretation, and the associate interpretation is introduced to construct special interpretation which can beused to check the satisfaction of axioms in candidate minimal unsatisfiable sub- TBox. And the number of reas

12、onercall is reduced and further the reasoning problem in each iteration is also simplified. Finally, we realize the algorithmand compare it with the optimizations of the black box algorithm. The experimental results show that the proposedmethod can effectively improve the efficiency of M UPS calcula

13、tion in the terminology.Key words: description logics, ontology debugging, minimal unsatisfiability- preserving sub- TBox ( M UPS ) ,associate interpretation本体作为语义W eb的核心,允许语义W eb中的数据以语义明确的方式进行共享并重用领域知识,在语义W eb应用中起着至关重要的作用 1 .本体构建在语义W eb相关的各个领域具有广泛的应用 2- 3 .而语义W eb技术高度依赖于这些本体的质量与正确性.然而,由于本体构建过程中建模错误

14、及本体融合过程中不可避免的逻辑冲突,需要对本体进行一致性验证 4 .保证本体质量涉及两种关键性策略,第一个是开发越来越复杂且成熟的本体建模工具,第二种是基于逻辑推理,本文关注后者.随着表达能力强的本体语言,如OW L( W eb OntologyLanguage)及其与描述逻辑DL之间的紧密关系,目前最先进的本体推理机即使在非常大的本体上也可以有效监测逻辑不一致性,例如RACER, FaCT等.面对不一致的本体更为实际的问题是: “如果本体被监测为不一致,应该做什么” .有两种方式来处理不一致本体:第一种是“忍受”不一致,应用非标准推理方法在存在不一致的情况下获得有意义的答案;另一种可行的方法

15、是当出现不一致的时候,解决或调试错误.本体调试作为一种非标准推理任务,可以识别并消除本体知识库中出现的逻辑错误 5 .本文关注本体术语集上的调试过程.本文结合语法相关性与关联解释,提出一种术语集的极小不可满足子术语集的求解方法,主要工作如下:( 1)在传统黑盒技术的基础上,通过语法相关性递归扩展与不可满足概念相关的不可满足子术语集,减少了待测子术语集的规模;( 2)通过判断子术语集的关联解释的可满足性来确定极小不可满足保持子术语集( minimal unsatisfiability- preserving sub- TBoxes,M UPS)中的元素,减少了推理机的调用次数,提高了M UPS求

16、解效率;( 3)应用不同数据集的实验结果表明本文提出的M UPS求解方法可以有效提高效率.1 相关工作本体调试主要工作在于找出导致逻辑冲突的解释并进行修改.本体调试任务的主要思想均在于求解极小不可满足子集. Schlobach andCornet 6第一次提出将调试不一致术语集看作是非标准推理服务,并通过M UPS来解释术语集不一致的原因.这种方法主要针对于概念关于术语集的可满足性问题,求解导致一个概念不可满足的解释.这是本体调试中的最基本问题.针对整体术语集的一致性问题,可以求解导致一个术语集不可满足的极小不一致保持子术语集( minimal incoherence preserving s

17、ub-TBox, M IPS) .该调试任务可以通过不可满足概念的M UPS集合覆盖的方式进行求解,也可以通过直接调用术语集一致性验证方法实75万方数据南京大学学报(自然科学)第54卷现 7 .查找本体逻辑蕴涵的理由( Justification)是本体中的另一个关键推理服务,主要用于求解本体蕴涵一个公理集合过程中所涉及的极小公理集合.查找逻辑蕴涵的理由对于调试不可满足概念和冲突也是必要的. Kalyanpuret al 8提出了求解术语集所有理由的几种算法.另一方面,针对较为复杂的公理集合,Baader and Pe aloza 9和Ye et al 10在找出极小不可满足子术语集之后,将解

18、释进一步定位到公理的内部,简化导致冲突的解释.本体诊断任务作为本体调试的进一步工作,将模型诊断的思想引入到本体调试过程中 11 . Schlobach 12和Friedrich and Shcheko-tykhin 13通过找极小不可满足子术语集的极小碰集构造诊断系统,并根据这些诊断系统研究删除冲突公理的调试策略.进一步的,Shchekotykhin et al 14和Jannach et al 15针对当今的多核计算机提出了并行诊断算法,在碰集树算法中同时求出多个极小不可满足子集.现有求解本体中不可满足概念的M UPS的相关工作分为黑盒技术与白盒技术.白盒技术为表达能力强的描述逻辑给出一个基

19、于表演算的可判定过程.这个过程中需要修改推理机内部,需要对表演算加入一些跟踪技术 16 .而黑盒技术使用推理机作为子程序,通过调用现有推理机进行,其实现过程无需修改推理机内部 17 .本文给出的M UPS求解方法属于黑盒技术.2 M UPS与黑盒技术求解M UPS的方法本节主要介绍术语集中极小不可满足子术语集M UPS及利用黑盒技术求解关于概念C和术语集T的M UPS的方法.定义1 M UPS 7 概念C关于术语集T不可满足,称术语集T T是T中关于概念C的一个极小不可满足保持子术语集,记作mups( T, C) ,如果C关于T不可满足且对于任意的子术语集T T , C关于T可满足.例1 T1

20、 = ax1 , ax2 , ax3 , ax4 , ax5 , ax6 ,ax7 是如下所示的一个不一致术语集,其中A,B, C, A1 , , A7是概念, r和s是角色.概念可满足性检测结果显示 A1 , A3 , A6 , A7 是不可满足概念集合.ax1 : A1 A A 2 A3ax2 : A2 A A 4ax3 : A3 A4 A5ax4 : A4 s. B Cax5 : A5 s. Bax6 : A6 A1 r. ( A3 C A 4 )ax7 : A7 A4 s. B根据M UPS的定义可知, mups( T1 , A1 ) : ax1 , ax2 , ax1 , ax3 ,

21、 ax4 , ax5 , mups( T1 ,A3 ) : ax3 , ax4 , ax5 , mups( T1 , A6 ) : ax1 ,ax2 , ax4 , ax6 , ax1 , ax3 , ax4 , ax5 , ax6 ,mups( T1 , A7 ) : ax4 , ax7 .下面介绍如何使用黑盒技术求解M UPS,其主要思想如下:给出一个关于概念C不可满足的术语集T ,将T中的公理一个个加入到不可满足子术语集T中,直到C关于T不可满足.之后,从T中删除不相关公理,直到T是关于C的一个极小不可满足子术语集.这个算法分为两步: ( 1)扩展T从而得到一个不可满足子术语集; ( 2

22、)收缩T从而找到M UPS.两个阶段都需要调用推理机来进行概念可满足性的检测,因而优化的主要重点就在于如何减少可满足性检测的次数.算法1 利用黑盒技术的M UPS求解算法输入:不可满足概念C,术语集T输出:一个M UPS T1. T 2. while C is satisfiable w. r. t. T3. select a set of axioms S T/ T4. T T S5. for each axiom Ax T6. T T / Ax7. if C is satisfiable w. r. t. T8. T T Ax85万方数据 第1期崔仙姬等:基于关联解释的术语集M UPS求解

23、方法算法1包括两个循环,第一个循环( 2 4行)中算法从一个空的候选术语集T开始,每次循环将T中的公理添加到T中直到概念C关于T不可满足.第二次循环( 5 8行) ,算法在每次循环从T中删除一个公理并检测是否C关于T仍是可满足,若是将这个公理重新加入到T中,直到T中所有的公理都被检测完毕.3 基于关联解释的M UPS求解从上一节算法可以看出使用黑盒技术求M UPS过程分为两步:第一步,通过不断添加公理扩展术语集从而获得不可满足子术语集;第二步,因这个术语集并不能保证是极小的,需要在此基础上进行公理的删减.本节在传统黑盒技术的基础上,结合语法相关性和关联解释的概念,通过构造关联解释求出术语集T中

24、关于概念C的M UPS.下面分两个小节分别介绍M UPS求解过程.3. 1 基于语法相关性的术语集扩展过程 术语集扩展过程关键在于如何选择合适的公理加入到不可满足子术语集T中.不同的公理选择方式会影响推理机的调用次数.例如,求mups( T1 , A3 )时,公理ax3的基础上如果先选择ax4和ax5可直接导致不可满足,而若先选择ax1和ax2 ,则需要再加入ax4和ax5才能导致不可满足.一种比较简单且高效的方式是通过概念之间的语法相关性选择公理.定义2 语法相关 18 称两个公理axi和ax j是语法相关的,如果这两个公理具有相同的概念或角色.基于语法相关性的不可满足术语集扩展具体实现如算

25、法2.从不可满足概念C的包含公理ax : C开始,递归将语法相关的公理集合加入到T ,直到C关于T不可满足,递归次数即为推理机调用次数.每一次循环( 4- 6行)中都将T中所有与当前公理ax语法相关的公理加入到T中.另外,为了便于术语集收缩过程,这里分别用Tlast和Tdebug表示最后一轮递归中加入的公理集合和最后一轮递归前候选术语集.算法2 基于语法相关性的术语集扩展算法输入:不可满足概念C,术语集T;输出:一个不可满足子术语集T .1. initialize T C 2. while C is satisfiable w. r. t. T3. Tdebug T4. for each ax

26、iom ax T5. for each entity curObj Sig( ax)6. T T expandAxioms( curObj , T)7. Tlast T / Tdebug8. T T / C 可以看出,通过算法2可以减少部分不相关公理加入到T中.用cus( T1 , Ai )表示算法2输入术语集T1和概念Ai返回的结果,可以得出, cus( T1 , A1 ) : ax1 , ax2 , ax3 , cus( T1 , A3 ) : ax3 , ax4 , ax5 , cus ( T1 , A6 ) : ax1 , ax2 ,ax3 , ax4 , ax5 , ax6 , cu

27、s( T1 , A7 ) : ax4 , ax7 .3. 2 基于关联解释的子术语集收缩过程 上一小节求出的使概念C不可满足的子术语集T在一定程度上减少了不可满足公理的个数,但不能保证是极小的.比如, cus ( T1 , A6 )中公理ax5虽然也与概念A6语法相关,但去掉该公理之后也能导致A6不可满足,也就是mups( T1 , A6 )与A5是不相关的.下面先给出关键公理及关联解释的定义,再介绍如何利用关联解释获得仅包含关键公理的术语集,即M UPS.定义3 关键公理 C是关于术语集T不可满足概念,称公理Ax T是一个关于T的关键公理,若C关于T/ Ax可满足.命题1 一个不可满足概念C

28、的M UPSM中所有的公理都是C关于M的关键公理.事实上,算法1中给出的收缩过程就是从不可满足子术语集T中删除非关键公理的过程.这种验证方式能保证得到的一定是M UPS.但是需要反复调用推理机,这使得验证效率降低.下面给出关联解释的定义,并根据关联解释给出一种不可满足子术语集收缩过程.其主要思想如下:将M UPS求解过程转化为关95万方数据南京大学学报(自然科学)第54卷键公理的查找过程,根据关键解释的构造方法求直接导致不可满足的关键公理集合,并在此基础上根据语法相关性回溯寻找所有的语法相关公理.定义4 关联解释 称解释I是公理Ax的关联解释,记作SigI ( Ax) ,若I满足如下条件:(

29、1) I包括所有Ax中出现的符号;( 2) I仅由公理Ax中符号构成;( 3) I满足Ax .术语集T中所有公理的关联解释的集合称为术语集T的关联解释,记作SigI ( T) .根据定义,如果公理Ax不可满足,则SigI ( Ax)为空集.而对于任意可满足公理,由于不同实例对应的不同解释,其关联解释并非唯一.为了简化M UPS求解过程,本文以x表示一般化实例并在计算关联解释的过程中将任意限定形式概念转化为存在限定概念的否定形式.根据定义,可以得到术语集T1中各个公理的关联解释:SigI ( ax1 ) = A1 ( x) , A( x) , A2 ( x) , A3 ( x) SigI ( a

30、x2 ) = A2 ( x) , A( x) , A4 ( x) SigI ( ax3 ) = A3 ( x) , A4 ( x) , A5 ( x) SigI ( ax4 ) = A4 ( x) , ( s. B) ( x) , C( x) SigI ( ax5 ) = A5 ( x) , ( s. B) ( x) SigI ( ax6 ) = A6 ( x) , ( A1 r. ( A3 C A 4 ) ) ( x) SigI ( ax7 ) = A7 ( x) , ( s. B) ( x) , A4 ( x) 下面给出一种不可满足子术语集收缩方法,分为关键公理集合求解算法(算法3)和子术

31、语集收缩算法(算法4) .需要考虑如下几个方面:( 1 )候选子术语集Tc及其关联解释Sig I ( Tc)的构造(算法3中2 3和6 7行) .算法2中每一次递归都会加入语法相关公理集合,但只有最后一轮公理集合加进去时才会出现不可满足的情况出现.这里,将不可满足子术语集分为两个子集T = Tdebug Tlast,因概念C关于T debug是可满足的,直接将Tdebug加入到候选子术语集Tc并根据其公理元素的关联解释求Sig I ( Tc) .另一方面,在找出关键公理之前,加入的公理Axi仍然使C关于Tc可满足,说明Axi的加入并没有影响到可满足性,将Axi也加入到Tc中作为候选公理.( 2

32、)求关联公理(算法3中4 5和8 10行) .若加入Axi之后的Tc使C不可满足,说明Axi一定是关键公理.需要考虑两种情况:第一种是Axi本身不可满足,也就是Axi没有模型, SigI ( Axi )为空;另一种情况是关键公理Axi与Tc中的某一条公理Ax放到一起导致不可满足,也就是SigI ( Tc)不满足Axi ,这时Ax即为与Ax i直接冲突的公理,同时也是关键公理.( 3)求M UPS(算法4) .找出直接导致冲突的公理集合之后,通过回溯的方式寻找导致概念C不可满足的所有相关公理.这部分可通过回溯语法相关性扩展完成.根据语法相关性求同时包含M中公理左侧概念的公理,并结合语法相关性回溯

33、方式递归扩展M t,直到M t中出现包含概念C的公理,这些公理均是关键公理.进一步地,为进一步确认M中包含所有关键公理,需要判断M的可满足性,并将相关关键公理加入到M .算法3 基于关联解释的关键公理求解算法输入:不可满足概念C,不可满足子术语集T ;输出:关键公理集合M t.1. Tc , lastAxiom , relatedAxiom ;2. for each axiom Axi Tdebug3. add SigI ( Axi ) into SigI ( Tc) , add Axi into Tc;4. for each axiom Axi Tlast5. if SigI ( Axi )

34、 is null6. then lastAxiom= Axi a nd break;7. if Sig( Tc) Sig( Axi ) is null8. then add SigI ( Axi ) into SigI ( Tc) , add Axi intoTc, continue;9. for each axiom Ax Tc10. if SigI ( Ax) does not satisfies Axi and SigI( Ax) SigI ( Axi ) is not null11. then lastAxiom= Axi , relatedAxiom= Ax,break;12. M

35、t lastAxiom relatedAxiom06万方数据 第1期崔仙姬等:基于关联解释的术语集M UPS求解方法算法4 基于关联解释的子术语集收缩算法输入:不可满足概念C,候选子术语集Tc,关键公理集合M t;输出: M UPS M .1. M t getRefAxioms( M t, Tc) / 根据语法相关性求同时包含M中公理左侧概念的公理 /2. while( Sig( M t) contain C)3. for each axiom Axj M t4. M t expandRefAxioms( left( Axj ) , Tc )5. M M M t6. if M does not

36、 satifiable w. r. t. C7. for each axiom Ax Tc/ M8. if SigI ( M ) satisfies Ax9. add Ax into Tc10. else add Ax into M定理1 算法4返回的集合M是关于输入概念C和术语集T的M UPS.证 明 首先证明算法4返回的集合M中所有元素关于M都是关键公理. M中的元素包括三类: lastAxiom、 relatedAxiom (若lastAxiom本身不可满足,则无这项)以及从概念C到lastAxiom( relatedAxiom)涉及的公理集合.显然, lastAxiom是关键公理,因候

37、选子术语集Tc本身不可满足,而Tc/ lastAxiom可满足.若lastAxiom本身是不可满足的,也就是SigI ( lastAxiom)本身带有冲突从而设置为空,reatedAxiom为空.否则, lastAxiom relatedAxiom包含冲突, relatedAxiom也是关键公理.由于算法4中采用的公理查找方式采用的是算法2中术语集扩展的回溯, M t返回的公理集合仅包含候选子术语集Tc中从不可满足概念C到关键公理集合M t查找过程中涉及的公理集合,因此也是关于M的关键公理.另一方面, M是不可满足的,所以M是M UPS.下面以概念A6为例,考虑基于关联解释的子术语集收缩过程.

38、 Tdebug = ax1 , ax3 , ax4 ,ax6 , Tlast = ax2 , ax5 , Tdebug加入ax5会导致A6不可满足,所以ax5是关键公理.由于SigI ( ax4 )不满足ax5 , ax4也是关键公理.getRefAxioms( M , To )依次返回公理ax3 , ax1 ,及ax6 ,因此, mups( T1 , A6 )为 ax1 , ax3 , ax4 ,ax5 , ax6 .若Tdebug先加入ax2 ,同样会导致A6不可满足.类似地可得到ax1 , ax2 , ax6是关键公理.但由于ax6包含析取式,使得A6关于M t= ax1 , ax2 ,

39、 ax6 仍可满足.进一步从Tc/M t中查找不满足Sig I ( M t)的公理集合 ax4 加入到M中,得到mups ( T1 , A6 ) : ax1 , ax2 ,ax4 , ax6 .4 实验与分析本文实验数据采用的是本体调试中的标准测试集.表1给出了数据集的相关信息,包括本体中概念、角色、实例的个数、不可满足概念的个数以及M UPS中元素个数的平均值.表1 待测本体描述Table 1 The Description of ontologiesOntology Concepts Roles Individuals UnsConcept M UPSEconomy 339 46 482

40、51 3. 6M adCow 54 16 13 1 4Chemical 48 9 0 37 7. 6Transportation 445 89 183 62 4. 4Koala 21 4 6 3 4使用黑盒技术求解术语集M UPS过程中,提高M UPS求解效率的关键在于减少推理机的调用次数.主要从以下三个方面进行优化:( 1)不可满足子术语集扩展阶段,通过语法相关16万方数据南京大学学报(自然科学)第54卷性仅将与不可满足概念C结构相关的公理集合加入到不可满足子术语集T中.这种扩展方式可以减少部分不相关公理加入到T中,大大降低待测术语集的规模. ( 2)不可满足子术语集收缩阶段,通过判断关键解

41、释是否满足公理来确定关键公理.该方法通过公理可满足性获得关键公理,相对于传统方法通过调用推理机判定概念可满足性效率高.进一步地,由于收缩过程中只需对最后一轮迭代产生的公理进行判定,公理可满足性检测次数也比传统方法推理机调用次数少,提高了M UPS求解效率. ( 3)前两个阶段之间使用滑动窗口技术可以优化公理收缩过程.每次删除n个公理,若删除之后C关于T可满足,删除的n个公理中至少有一个公理是导致不可满足的原因,重新将这n个公理加入到T中.若仍不可满足,则可以认定这n个公理都是不相关的,直接从T中删除.该方法适用于待测术语集规模较大的情况,一般用于收缩过程之前减少待测本体的规模.本文实现了分别将

42、滑动窗口优化技术( Fast- Prune) 、基于语法相关性的术语集扩展方法( Synt- Expand) 、结合前两种优化方法( Synt+Fast)以及结合语法相关性和关联解释的求解方法( Synt+ AssoIn)应用于传统黑盒技术时的M UPS求解算法.表2中给出了在标准测试集上分别使用这四种算法的运行结果比较,黑色加粗的字体表示最优的结果.表2中size与call分别表示针对求解同一个M UPS的收缩阶段之前得到的待测术语集公理个数( # )与推理机调用次数( # ) , time表示求解全部M UPS的运行时间,单位为毫秒( ms) .其中,由于有些本体( Economy和Tra

43、nsportation)规模较大且复杂, Fast- Prune仅列出求解部分M UPS的时间.另一方面,由于传统的黑盒技术在不可满足子术语集扩展以及收缩阶段选择的公理集合随机性较高,无法确定待测数据集中的元素个数,使其推理机调用次数远远超过其他四类方法,这里不做比较.从表2可以看出,本文给出的结合语法相关性与关联解释的M UPS求解方法优于其他三类方法,而且针对规模较大且复杂的本体,其效率更为明显.( 1)语法相关性引入到术语集扩展阶段可以大大减少收缩阶段待测术语集的规模:比较表2中第2, 5, 8, 11列可知, Fast- Prune方法未使用该优化策略,其待测术语集中公理个数远远大于其

44、他三种方法.( 2)使用滑动窗口技术可以适当减少收缩阶段推理机的调用次数,从而减少M UPS求解时间:比较表2中第6, 9和7, 10列可知,减少了推理机的调用次数,且大多数情况下其运行时间会优于未使用该技术的方法.( 3)收缩阶段使用关联解释的方法可以一方面减少推理机的调用次数,另一方面推理机调用主要用于判断关联解释是否满足公理,其推理任务较概念可满足性判断任务简单.比较表2中第9, 12和10, 13列可知,从推理机用次数和M UPS求解运行时间方面本文方法都优于其他方法.表2 各类M UPS求解方法比较Table 2 The Comparison of M UPS algorithmsO

45、ntologyFast- Prunesize call timeSynt- Expandsize call timeSynt+ Fastsize call timeSynt+ AssoInsize call timeEconomy 551 52 46980/ 18 14 13 812 14 6 766 14 3 594M adCow 66 15 527 10 9 401 10 8 409 10 5 395Chemical 135 92 2222 83 82 6123 83 20 2207 83 11 871Transportation 217 85 51890/ 22 81 77 2287 8

46、1 13 1371 81 7 716Koala 27 14 498 11 10 457 11 8 409 11 4 36826万方数据 第1期崔仙姬等:基于关联解释的术语集M UPS求解方法5 总 结本文提出了一种结合语法相关性和关联解释的M UPS求解优化方法.基于语法相关性的不可满足子术语集扩展方法仅添加与不可满足概念语法相关的公理集合,大大降低了待测本体的规模.而基于关联解释的关键公理求解方法采用公理可满足检测且仅对扩展递归中最后一轮公理进行可满足性检测,不仅减少了推理机调用次数,也降低了每次调用的检测时间.实验结果表明,本文给出的M UPS求解优化方法在保证正确性的基础上提高了求解效率

47、.参考文献 1 Staab S, Studer R. Handbook on ontologies.Springer Berlin Heidelberg, 2009, 811. 2 Doms A, Schroeder M . GoPubM ed: ExploringPubM ed with the gene ontology. Nucleic AcidsResearch, 2005, 33( S2) : W 783- W 786. 3 Cornet R, De Keizer N. Forty years of SNOM ED:A literature review. BM C M edical

48、 Informaticsand Decision M aking, 2008, 8( S1) : S2. 4 Baader F, Calvanese D, M cGuinness D L, et al .The description logic handbook: Theory, imple-mentation, and applications. The 2nd Edition. NewYork, NY, USA: Cambridge University Press,2007, 573. 5 Kalyanpur A, Parsia B, Sirin E, et al . Debuggingunsatisfiable classes in OW L ontologies. W eb Se-mantics: Science, Services and Agents on theW orld W ide W eb, 2005, 3( 4) : 268- 293. 6 Schlobach S, Cornet R. No