混合的本体原子分解方法.docx

该【混合的本体原子分解方法 】是由【科技星球】上传分享，文档一共【18】页，该文档可以免费在线阅读，需要了解更多关于【混合的本体原子分解方法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。混合的本体原子分解方法??王昌龙,冯志勇,王鑫,,,兰州7300701引言基于Web本体语言(WebOntologyLanguage,OWL)及其扩展版本OWL2的本体在语义Web开发中扮演着最重要的角色[1]。同时,OWL本体也广泛应用在生物医学信息系统[2-3]以及其他的应用领域,如农业[4],天文[5],国防[6],地理[7]和交通[8-9]等。本体的广泛应用导致大规模本体逐渐增多,著名的大型本体如SNOMEDCT和FMA,其包含的公理数已经超过1000000条。在生物医药本体库NCBOBioPortal中,很多单个本体的规模已经达到100000,如GO,ChEBI,GALEN等[10]。伴随大规模本体的一个难题是复杂性问题。从推理方面看,用户只需要本体中的小部分知识,而本体中的大部分知识与个别子领域中具体的应用无关,在这种情况下,没有必要把整个本体都装入内存或通过网络传输;从认知方面看,本体工程师很难理解大规模本体的内部结构。本体模块化是处理大规模本体问题的一种方法,它为抽取模块提供了理论基础和工具支持[11-12]。基于语法局部性的模块抽取算法能够在多项式时间内提供模块抽取服务,但该传统的模块抽取方法需要把整个本体装入内存。另外,这种方法需要检查每一个公理与目标模块的相关性[13-14]。最近提出本体原子分解(position)方法[15],克服传统的模块抽取方法的缺点:在原子分解的情况下,本体原子成为模块的基本构造组件,基于原子分解的模块抽取算法的时间复杂度为线性[16],模块抽取具有更高的效率;同时,在以分解的方式管理本体的情况下,可以根据需要部分加载本体[17]。本质上,原子分解是识别本体模块的基本构件的过程——通过识别本体中高度关联的公理团(原子),依据这些原子之间的依赖关系来构造本体模块。原子分解本身仍然是一项计算量较大的工作。在利用原子分解技术实现本体模块化推理的时候,实验发现,对于一些大型的本体,如NCI,其原子分解的时间超过了5个小时[18-19]。文献[20]中的实证研究表明,超过10%的大型本体不可能在12小时内完成原子分解。传统的原子分解方法效率不高,其主要原因在于,该方法简单地将本体视为公理的集合,没有考虑公理的类型,也没有考虑本体的特性。另外,传统的原子分解方法直接依赖于模块抽取,很难实现并行化以充分利用当前流行的多核计算平台。实际应用中的很多本体,其中的绝大部分公理属于EL类型,非EL公理只占极少数。如最新的医药生物本体NCI含有226038条公理,其中,EL类型的公理为225971条,%;蛋白质本体Protain含有46698公理,其中的EL公理数为46682,%[18]。EL本体具有一个重要的属性:EL本体的语法局部性模块抽取问题等价于相应有向超图中的可达性问题[21-23]。本体的有向超图模型为引入标准的图论算法及其并行机制提供了理论基础。文[21]研究表明,对于轻量级EL本体,基于有向超图的原子分解方法比传统的方法具有更高的效率,平均加速比超过100。但是,这种基于有向超图的原子分解方法只局限限于弱表达力的EL本体。鉴于以上两种方法的互补特性,在本文中,联合本体的有向图表示模型和传统的原子分解方法对大型的强表达力本体进行原子分解。具体分为两步:首先,从原本体中分离出EL子本体OEL并表示为有向超图HEL,通过计算强连通分量,形成部分原子分解AEL;然后,利用传统的原子分解方法,将剩余的非EL公理加入部分分解AEL,得到完整的原子分解AO。混合原子分解方法的优点表现两个方面:①可以直接使用现存的优化的原子分解算法;②将本体中的大部分EL公理表示为有向超图模型,方便使用标准的图论算法[24-25],有助于并行化以充分利用方便得到的多核计算平台。从优化的角度看,混合原子方法将大部分工作负载赋予高效的图论算法来处理,只把少部分工作委托给低效率的逻辑模块识别方法。2基础知识OWL以描述逻辑(DescriptionLogic,DL)为逻辑基础[26]。OWL2对应描述逻辑SROIQ,后者是目前表达力最强的可判定描述逻辑[27]。OWL2EL(简称EL)为OWL2的一个子语言,对应描述逻辑EL++,EL只允许使用有限的逻辑运算子,即合取(conjunction)和存在约束(existentialrestriction)[28]。为简单起见,本文使用描述逻辑的形式化描述。描述逻辑采用模型论语义,详细描述可参阅文献[26]。描述逻辑本体的词汇包括概念名、角色名、个体名以及两个特殊的概念:顶概念T表示全域,底概念⊥表示空。公理(集)α包含的词汇记为S(α)。在描述逻辑本体中,通常采用模型保持性扩展(modelconservativeextension)来描述逻辑模块[14]。本体O与其关于种子词汇集∑的模块M(记为M(∑,O))蕴含相同的公理,这些公理由∑中的符号构成。由于最小模块的计算复杂性等同于推理难度,具有多项式计算复杂性的语法局部性模块(SyntacticLocalityModule,SLM)成为最小模块的有效近似。语法局部性模块的类型x包括顶类型(Top)Τ、底类型(Bottom)⊥和星型(Star)Τ⊥*。如果α关于∑不具有x局部性(Locality),则α与∑相关,∑称为α的局部性符号集,公理α包含在模块Mx(∑,O)中。本文采用⊥型模块,直观上,⊥模块的计算方法是,把公理α中不属于种子符号∑的词汇替换为⊥,如果得到的公理为重言式,则α关于∑具有局部性,α不在模块M⊥(∑,O)中,文[14]实现了基于语法局部性的模块抽取算法。本文使用惯用的图论术语。有向超图为二元组H=(V,E),其中V为顶点集,E为超边集。超边e为二元组e=(T(e),H(e)),其中T(e)和H(e)均为V的非空子集,分别表示e的头和尾。从节点v1可到达v2,记为v1→2,满足条件:①v2=v1;或②?e∈E,∈H(e)且?v∈T(e)有v1→v。从顶点v1到vn的路径P径为序列(v1,vn)=v1e1v2e2,…,en-1vn,满足vi∈T(ei),vi+1∈H(ei),(i=1,2,…,n-1)。如果vn∈T(e1),P(v1,vn)称为超环。在有向超图H中,如果节点v2和v1互相可到达,称v2和v1强连通。超图H中互相可到达的顶点集称为强连通分量(ponent,SCC)。3本体的原子分解在模块抽取的过程中,不同的种子词汇可能产生相同的模块。以公理的词汇为种子符号,能够产生相同模块的所有公理构成的集合称为一个本体原子。为了方便理解原子分解算法(算法1)[15],对原子进行如下的形式化定义:定义1(原子)给定本体O,公理集αt={α1,α2,…,αn}?O,如果M⊥(S(α1),O)=M⊥(S(α2),O)=,…,=M⊥(S(αn),O),对于任意的公理β∈O{at},M⊥(S(β),O)≠M⊥(S(αi),O),i=1,2,…,n。称at为O的一个⊥原子1)在原子分解过程中,假设本体不含有全局公理和常言式[15]。。原子表示语义高度关联的公理集,从逻辑模块的角度看,一个原子中的所有公理总是同时出现在某个模块中。原子类型与模块类型相关,用Ax(O)表示O的所有x类型原子的集合,则Ax(O)是O的一个划分,每个公理只出现在一个原子当中[17]。以原子at的词汇为种子符号的模块M(S(at),O)称为真模块2)真模块不能为两个或多个不相交模块的并。,记为Mat。实际上,如果α∈at,Mat与M⊥(S(α),O)一致[17]。根据真模块之间包含关系,原子之间的依赖关系定义如下:定义2(原子依赖关系)a和b为本体O的两个原子,如果Ma?Mb,称原子b依赖a,记为b≥a。由原子以及原子之间的关系构成的二元组(Ax(O),≥)称为本体的原子分解,记为AO。定义1和定义2分别蕴含了原子及其依赖关系的计算过程[17],如算法1所示。该算法的基本思想是,首先利用每一个公理的词汇为种子符号来识别模块,如果多个公理引起的模块相同,则这些公理构成一个原子,然后利用这些原子对应的真模块之间的包含关系建立原子依赖关系。具体地,算法1第3行除去本体中的全局公理,得到需要处理的公理集TodoAxioms,第4行GenAxioms表示所有原子中用来产生真模块的公理的集。余下分为两个独立的部分:第一部分(5~18行)创建所有的本体原子。以每一个公理a的词汇为种子符号抽取模块(第6行),并比较新模块和已经创建的模块,如果该模块已经存在,则公理α加入已有原子(10行);如果不存在以α为种子符号创建的模块,则为α创建新的原子(15行)。第二部分(19~25行)计算原子间的依赖关系:通过比较两个原子对应的真模块之间的包含关系来设置原子的依赖关系:如果原子a中的公理出现在为b原子创建的模块中,则b依赖a:b≥a。如果本体的规模为n,基于语法局部性的模块抽取算法的复杂度为O(n2)[13]。明显地,算法1中创建原子的复杂度为O(n4),如果本体的原子数目为m,则计算原子依赖关系的复杂度为O(m2)。一般地,原子总是包含多个公理,因此,本体原子分解算法中的大部分时间用于原子计算。算法1已经实现在OWLAPI的软件包OWLAPITOOLS中(http://owlapitools./)。:创建原子时根据公理所属模块减少遍历空间;在创建原子的时候同时计算原子依赖关系[29]。该优化算法已实现在描述逻辑推理器FaCT++中(http://code./p/factplusplus/)。在本文的实验中,将与FaCT++进行比较。4本体的有向超图模型如前文所述,判断公理α关于种子词汇∑的⊥语法局部性的依据是,将α中不属于∑的词汇替换为⊥,检查得到的公理是否为重言式。对于大规模本体,该过程繁琐且计算量大。如果本体为轻量级的EL类型,判断公理的⊥语法局部性的过程可以进一步简化——由α的左边词汇S(L(α))或右边词汇S(R(α))与∑的包含关系来确定[22]:命题1设α为EL公理,∑为词汇集,则(1)如果α=(C?D),则α关于∑不具有语法局部性当且仅当S(L(α))?∑。(2)如果α=(C≡D),则α关于∑不具有语法局部性当且仅当S(L(α))?∑或S(R(α))?∑。直观上,如果公理α的形式为C?D,且该公理的左边词汇集S(L(α))为∑的子集,则α关于∑不具有语法局部性,即α与主题“∑”相关,α应该包含在以∑为种子符号的模块中;同样地,如果形如C≡D的公理α的左边词汇集S(L(α))或右边词汇S(R(α))包含在∑中,α必然包含在以∑为种子符号的模块中。因此,EL公理的词汇集之间的包含关系体现公理之间的逻辑关联关系,这种关系可用有向图来表示,称为公理依赖性超图(AxiomDependencyHypergraph,ADH)[21,23]。ADH中的顶点表示本体的公理,ADH的边表示公理词汇集之间的包含关系。根据命题1,ADH的边蕴含了公理之间的依赖关系。用S⊥(α)表示公理α的⊥局部性符号集,如果α的形式为C?D,则S⊥(α)=S(L(α));如果α的形式为C≡D,S⊥(α)={S(L(α)),S(R(α))}。定义3(EL本体的⊥局部性公理依赖超图)[21]。设O为EL本体,O的⊥局部性公理依赖超图(ADH)HO=(V,E),其中V=O;e=(T(e),H(e))∈E,当且仅当下面条件成立:(1)H(e)={β};(2)T(e)?V{β},对于X∈S⊥(β),满足|T(e)|最小且X?S(T(e))。这里,EL本体的公理依赖超图是针对⊥局部性定义的。顶点为本体的公理,边关联尾结点公理集{α1,α2,…,αn}和单个头结点公理β,使得β的⊥局部性符号集包含在α1,α2,…,αn的符号集中。最小性条件表明,为了覆盖β的⊥局部性符号,每个公理αi都是必须的。定义3蕴含了将EL本体O表示为有向图的过程:对于每个头结点公理β∈O,寻找满足S⊥(β)?sig(T(e))的最小尾结点集。如果本体规模为n,将O表示为有向超图的计算复杂度为O(n2)。将本体表示为有向超图之后,可以借助超图的可达性来识别本体中的⊥局部性模块。命题2设O为EL本体,α∈O,则M⊥(S(α),O)={β|α可到达β}EL本体中的原子对应公理依赖性超图中的强连通分量。命题3设O为EL本体,SCCs(HO)表示超图HO中所有的强连通分量集,则A⊥(O)=SCCs(HO)。EL本体中原子间的依赖性对应于超图HO中强连通分量之间的指向关系。对于S1,S2∈SCCs(HO),如果存在超边e=(T(e),H(e))使得H(e)?S1且H(e)?S2,称S1依赖S2,记为S1→S2。显然,→为偏序关系(自反、反对称和传递属性)。命题4设O为EL本体,a1,a2∈A⊥(O),S1,S2∈SCCs(HO),如果a1=S1且a2=S2,则a1≥a2当且仅当S1→S2。根据命题1和定义3,如果有向超边e的头结点β为形如A?C(其中,A为概念名)的EL简单概念包含(PrimitiveConceptConclusion,PCC)公理,则|S⊥(β)|=1,满足定义3的条件(2)的尾结点集T(e)最多包含一个公理,即|T(e)|≤1。更进一步,公理,则其所对应的有向超图HO演化为常见的简单有向图——每一条边关联两个结点。用有向超图表示EL本体之后,可以借助标准图算法来计算超图中的强连通分量及其依赖关系[27]。在创建本体的有向图模型的过程中,每条边的创建过程是独立的,因此,可采用并行算法来进一步优化。5混合的原子分解方法在这一章中,联合传统的原子分解方法和有向超图模型对本体进行原分解。:首先从原本体O中分离出EL子本体OEL,构造OEL对应的有向超图HEL,从而得到该EL子本体的原子分解A⊥(OEL),然后利用递增式原子分解方法[17],将剩余非EL公理添加到部分分解A⊥(OEL)中,得到本体的全部分解A⊥(O)。算法2描述该混合原子分解方法的过程。算法2的第一部分(3行~6行)计算EL子本体的原子分解A⊥(OEL)。第二部分(7行~12行)添加剩余的非EL公理。由于局部性模块抽取过程的单调性,新公理的加入不会导致旧原子的分裂,但是会造成旧原子的合并,同时引起原子间依赖关系的变化[17]。因此,在添加非EL公理α的时候,首先从部分分解A⊥(OEL)中选取因添加公理而受到影响的原子AFF(O,α)(第9行),重新计算这部分原子(11行),然后再把重新分解的结果合并到原分解图中(12行)。算法2使用文献[17]中的两个算法作为子程序(9行、12行)。如果本体规模为n,其中EL公理数目为m,最坏情况下,算法2的计算复杂度为O((n-m)4)。在基于语法局部性的模块抽取过程中,抽取的模块与公理的选择顺序无关[11]。本体原子分解的结果只受原子类型(Τ、⊥、Τ⊥*)影响,与分解原子时公理的选择顺序无关。一旦原子类型确定,本体O的原子分解唯一地对应于一个Hasse有向图[15]。在混合式原子分解方法中,首先选择EL公理创建原子,然后选择剩余的公理创建原子。因此,算法2是正确的。(http://owlapi./),实现了算法2。为了能够直接使用标准的线性复杂度算法来计算强连通分量,公理表示表示为有向超图。因此,对算法2的实现进行细微的修改:OEL只包含形如A?C的公理,Onon-EL包含形如A≡C的EL公理和所有的非EL