不协调本体调试与修复的冲突路径优化策略-张瑜 , 欧阳丹彤 , 叶育鑫.pdf
免费下载
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2018,29(10):29482965 [doi: 10.13328/j.cnki.jos.005550] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
不协调本体调试与修复的冲突路径优化策略
张
瑜
1,2
,
欧阳丹彤
1,2
,
叶育鑫
1,2
1
(吉林大学 计算机科学与技术学院,吉林 长春 130012)
2
(符号计算与知识工程教育部重点实验室(吉林大学),吉林 长春 130012)
通讯作者: 叶育鑫, E-mail: yeyx@jlu.edu.cn
摘 要: 以基于黑盒法的不协调本体调试与修复技术为研究对象,分析了黑盒法及其优化方法在调试过程中所存
在的问题.针对这一问题,提出了一种基于冲突路径的调试与修复策略,证明了该策略能够正确构造出与基本冲突模
式相对应的冲突路径.将黑盒法调试目标限定在与该冲突路径相关的冲突集上,以此降低调试目标的规模从而提高
调试的效率.进而根据构造出的冲突路径,获得不可满足依赖路径并基于该路径制定出不可满足概念的修复策略.理
论证明与实验结果均证实了所提出的调试与修复策略的正确性与有效性.
关键词: 不协调本体;本体调试;本体修复;冲突路径;不可满足依赖路径
中图法分类号: TP18
中文引用格式: 张瑜,欧阳丹彤,叶育鑫.不协调本体调试与修复的冲突路径优化策略.软件学报,2018,29(10):29482965.
http//www.jos.org.cn/1000-9825/5550.htm
英文引用格式: Zhang Y, Ouyang DT, Ye YX. Debugging and repairing incoherent ontologies based on the clash path. Ruan Jian
Xue Bao/Journal of Software, 2018,29(10):29482965 (in Chinese). http.//www.jos.org.cn/1000-9825/5550.htm
Debugging and Re pairing Incoherent Ontologies Ba sed on the Cla sh Path
ZHANG Yu
1,2
, OUYANG Dan-Tong
1,2
, YE Yu-Xin
1,2
1
(College of Computer Science and Technology, Jilin University, Changchun 130012, China)
2
(Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education (Jilin University), Changchun 130012,
China)
Abstra ct : This study focuses on the debugging and repairing techniques for incoherent ontology based on the black-box method and
discusses the limitations of the existing black-box methods and their optimizations. To solve this problem, the study proposes a new
strategy called clash path for debugging and repairing incoherent ontology. This strategy can construct the clash path related to the basis
clash models and then identify the clash set based on the clash path. In this case, deubgging can be rapidly performed based on the clash
set because the clash set is smaller than the original ontology. In addition, the unsatisfiable dependent path can be identified from the clash
path and the repair set can be easily obtained on the basis of the unsatisfiable dependent path. The theoretic proofs and experimental
evaluation demonstrate that the presented debugging and repairing strategies are correct and efficiency.
Key words: incoherent ontology; ontology debugging; ontology repairing; clash path; unsatisfiable dependent path
描述逻辑(description logics,简称 DLs)是知识表示的常用形式化语言,用描述逻辑表示的本体知识库由术
语集(TBox)和断言集(ABox)两部分组成
[1]
.本体一般由领域专家手工构建或计算机程序半自动构建,建成的本
基金项目: 国家自然科学基金(61672261, 61502199)
Foundation item: National Natural Science Foundation of China (61672261, 61502199)
本文由“本体工程与知识图谱”专题特约编辑漆桂林教授推荐.
收稿时间: 2017-07-20; 修改时间: 2017-11-08; 采用时间: 2018-01-24; jos 在线出版时间: 2018-02-08
CNKI 网络优先出版: 2018-02-08 11:55:43, http://kns.cnki.net/kcms/detail/11.2560.TP.20180208.1155.006.html
张瑜 等:不协调本体调试与修复的冲突路径优化策略
2949
体被广泛应用于本体工程的各个方面
[24]
.若术语集中概念的定义出现了逻辑冲突,则称该概念是不可满足的,
该术语集是不协调的(incoherent)
[5]
.本体调试的大多数工作都集中在如何解决本体术语集部分的不协调问题
上
[6]
,研究目标是期望提供有效的方法辅助本体建模人员实现逻辑冲突的快速定位和冲突解决方案的自动生
成
[7]
.
不协调本体调试的方法包括基于 Tableau 扩展策略的白盒法
[811]
与基于“扩张-收缩”策略的黑盒法
[1216]
两
种.Schlobach 等人首先提出了极小不可满足保持子术语集(minimal unsatisfiability-preserving sub-TBoxes,简称
MUPS)
[8]
并提供了白盒求解方法,接着又在文献[5]中将其扩展到黑盒求解方法.Baader 等人
[9]
则提出了类似
MUPS 的极小公理集合 MinA,并提供了求解 MinA 的白盒方法.Kalyanpur
[12]
提出了一个适用于解释任何逻辑蕴
涵式的最小公理集合——辨解(justification),并提供了黑盒求解方法,而且证明了在不协调问题中,不可满足概
念的 MUPS 与不可满足概念的辨解是相同的并可以相互转化.欧阳丹彤等人
[7]
提出的基于有序标签演算的概
念 R- MUPS 白盒法能够有效确定不可满足概念的 MUPS 之间的覆盖特征,从而加快 MUPS 的求解.
白盒法虽然效率较高,但受制于本体语言类型并需要修改推理机内部的推理机制,不具有可移植性,因而缺
乏通用性.黑盒法则独立于具体的推理机与本体语言类型,可移植并易于实施,因而应用比较广泛
[12]
.但黑盒法
需要多次调用推理机进行可满足性检测,当本体规模较大或不可满足概念较多时,效率较低.因此,针对黑盒法
的“扩张”与“收缩”两个阶段,一系列优化工作相继展开.在扩张阶段,选择函数法
[5,13,15]
与模块化方法
[14,1618]
用
于选择一个与不可满足概念有直接或间接语法相关的一个候选子集.Ji 等人
[15]
提出了类似于选择函数的定向
相关的方法求解辩解,并在文献[19]中提出了基于基本冲突模式的本体调试方法.Grau 等人
[14]
定义了一种局部
模块用来获取与蕴涵有关的公理子集,Suntisrivaraporn 等人
[16]
证明了该模块能够涵盖所有的辨解.在收缩阶段,
滑动窗口
[12,20]
与分治法
[13,20]
用于提高精确定位较小不可满足子集的效率.Horridge
[19]
采用组合优化的方式,同
时将模块化方法与分治法用于辩解求解问题.Shchekotykhin 等人
[21]
经过对比实验,认为分治法比滑动窗口方法
更具有优势.此外,Ji 在文献[22]中将现有的本体调试工具进行了测试.
本体调试的结果能够提供导致本体不协调的极小冲突集,删除或者修改冲突集中的部分公理就能使得不
可满足概念变得可满足.那么,选择哪部分公理进行修复,以及采取何种策略确定修复的优先级,则是本体修复
工作的主要研究目标.本体修复代表性的工作是 Kalyanpur
[12]
提出的根不可满足概念以及采取的公理分割的细
粒度方法,细粒度方法修复的主要目的是为了尽可能地保留有用信息.类似地,Lam 等人
[23]
和 Du 等人
[24]
提出的
细粒度的公理定位方法,也都是将调试问题深入到公理内部,从而能够定位导致概念不可满足的真正原因,为本
体修复提供精确目标.
关于轻量级的描述逻辑 DL-Lite 本体的调试和修复两方面的工作,漆桂林小组
[2529]
做出了较多较为重要的
贡献,该小组利用 DL-Lite 本体的特殊结构特征,构造肯定与否定逻辑闭包形成图结构,基于 DL-Lite 逻辑闭包
图,不但能够较快地完成本体调试,而且可以高效地实现本体修复.
1 基础理论与研究动机
1.1 描述逻辑AL CO I
描述逻辑提供了一系列构造算子用于构建复杂的概念表达式.描述逻辑 ALCOI 由
(全集)、(空集)、A(原
子概念)、A(原子否定概念)、(概念合取)、(概念析取)、{o
1
,o
2
,…}(枚举概念)、r.A(存在限定)、r. A(全
称限定)构成.其中,r 是原子角色或逆角色.ALCOI 复杂概念按如下方式构成.
C,D
||A|A|r.A|r. A|{o
1
,o
2
,…}|CD|CD|.
ALCOI 术语集由概念包含公理(CD)或概念等价公理(CD)组成,其中,C 和 D 都是 ALCOI 概念.
描述逻辑本体的语义是通过解释 I 体现的,I 是一个二元组(
I
,●
I
),其中,
I
是一个非空集合,代表该领域所有
个体,称为论域.映射●
I
将每个概念 A 映射为
I
的一个子集 A
I
I
,将每个角色 r 映射为
I
上的二元关系 A
I
I
I
.
例如,(
)
I
=
I
,()
I
=,(CD)
I
=C
I
D
I
,(CD)
I
=(C
I
=D
I
).
根据描述逻辑解释,不可满足概念和不协调(incoherent)术语集的形式化定义如下
[5]
.
of 18
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论