不一致本體精確調(diào)試的公理分割方法

張 永 濤

(商丘工學(xué)院信息與電子工程學(xué)院 河南 商丘 476000)

?

不一致本體精確調(diào)試的公理分割方法

張 永 濤

(商丘工學(xué)院信息與電子工程學(xué)院 河南 商丘 476000)

本體調(diào)試是解決本體不一致問(wèn)題的主要手段?，F(xiàn)有的本體調(diào)試方法能夠求解出本體不一致性的一組沖突公理集合，刪除這些公理可使本體恢復(fù)到一致?tīng)顟B(tài)。然而，簡(jiǎn)單地刪除這些沖突公理不可避免地會(huì)造成本體信息的損失。為了解決這個(gè)問(wèn)題，采用公理分割的思想，對(duì)沖突公理集合進(jìn)行分割，基于分割后的公理集再次進(jìn)行調(diào)試。該方法能夠保留與不一致性無(wú)關(guān)的本體信息，從而避免了信息損失的情況發(fā)生。實(shí)驗(yàn)結(jié)果表明，在各種類(lèi)型的實(shí)驗(yàn)本體上，所提出的精確調(diào)試算法在留存度與調(diào)試時(shí)間兩方面都比類(lèi)似相關(guān)的算法取得較好的效果。

本體調(diào)試 不一致本體 不可滿足概念 公理分割 不一致本體精確調(diào)試

0 引 言

在語(yǔ)義網(wǎng)的體系結(jié)構(gòu)中，處于核心地位的是本體層[1]，本體是共享的概念模型的形式化的規(guī)范說(shuō)明，是人機(jī)之間以及機(jī)器之間進(jìn)行交流的知識(shí)基礎(chǔ)[2]，目前本體已被廣泛應(yīng)用于知識(shí)工程和信息檢索等領(lǐng)域[3-4]。在描述本體的眾多語(yǔ)言中，由于描述邏輯具有很強(qiáng)的推理功能和較好的表達(dá)能力，因而成為本體語(yǔ)言普遍適用的邏輯基礎(chǔ)[5]。在本體的相關(guān)應(yīng)用中，本體構(gòu)建是基礎(chǔ)性的工作，然而本體構(gòu)建是一種復(fù)雜且容易出錯(cuò)的過(guò)程[6]。此外，在本體的更新、合并與重用等應(yīng)用中，邏輯矛盾的情況也經(jīng)常發(fā)生。例如，多個(gè)作者構(gòu)建的小本體合并成一個(gè)較大本體時(shí)，由于知識(shí)理解上的差異，容易對(duì)同一個(gè)對(duì)象做出相互矛盾的定義，而產(chǎn)生了邏輯矛盾的概念(稱為不可滿足概念)，這就引起了本體不一致的現(xiàn)象。只有消除了不一致本體中存在的不可滿足概念，才能解決本體的不一致問(wèn)題?，F(xiàn)有的描述邏輯推理機(jī)雖然能判別出本體是否存在不可滿足概念，但是導(dǎo)致概念不可滿足性的原因，推理機(jī)則無(wú)法給出。本體調(diào)試則是目前解決這一問(wèn)題的主要手段[7]。從不一致本體中求解出導(dǎo)致概念不可滿足的一組公理集合，稱為極小不可滿足保持子術(shù)語(yǔ)集(MUPS)[8-9]便是本體調(diào)試的結(jié)果，刪掉這些公理就確保了本體的一致性。Baader等提出了一種求解極小公理集的MinA方法[10]，與MUPS方法類(lèi)似，該方法同樣是獲取滿足調(diào)試條件的一個(gè)極小公理集合。Suntisrivaraporn等[11]與Horridge等[12]所提出的最小本體子集，也是MUPS問(wèn)題的一個(gè)變體，與MUPS只有表現(xiàn)形式的差異，沒(méi)有本質(zhì)上的區(qū)別。除此之外， Kalyanpur等提出了辯解(Justification)的概念[13]，并指出求解一個(gè)不可滿足概念的MUPS問(wèn)題和求解蘊(yùn)涵該不可滿足概念的辯解問(wèn)題是可以相互轉(zhuǎn)化的。與之思路相反的另一種調(diào)試方法是求解極大可滿足保持子術(shù)語(yǔ)集的MSS方法[14]。該方法通過(guò)排除那些錯(cuò)誤的公理而獲得一個(gè)無(wú)邏輯沖突的可滿足本體來(lái)實(shí)現(xiàn)調(diào)試目的。Fleischhacker等從兩個(gè)方面展開(kāi)研究，一方面通過(guò)定義一系列完備規(guī)則對(duì)不可滿足概念進(jìn)行解釋從而求取極小不一致保持子集(MIPS)來(lái)近似解決MUPS問(wèn)題[15]，另一方面采用了本體學(xué)習(xí)的思想，提出了一種基于馬爾科夫鏈網(wǎng)絡(luò)的調(diào)試方法[16]。Fu等[17]提出一種基于圖的方法對(duì)DL-Lite術(shù)語(yǔ)集進(jìn)行調(diào)試，采取的方式是通過(guò)計(jì)算極小不一致保持路徑對(duì)(MIPP)來(lái)近似模擬MUPS。該方法借用了文獻(xiàn)[18]的圖的思想，該思想將本體轉(zhuǎn)換為圖的方式來(lái)簡(jiǎn)化問(wèn)題求解過(guò)程。在本體修復(fù)方面，文獻(xiàn)[19-20]的研究對(duì)象都是DL-Lite本體系列，不同之處在于前者針對(duì)術(shù)語(yǔ)集進(jìn)行修復(fù)，后者則針對(duì)斷言集進(jìn)行修復(fù)。

然而，在很多情況下，本體的不一致或概念的不可滿足是由MUPS中的公理的一部分而不是整個(gè)公理所導(dǎo)致的。如果刪除整個(gè)公理，則會(huì)丟失一些有用的信息。這個(gè)問(wèn)題產(chǎn)生的原因是本體調(diào)試算法未能深入公理內(nèi)部去探查不可滿足性的緣由，不清楚究竟是公理的哪一個(gè)部分才是造成不可滿足性的真正原因。為了解決這個(gè)問(wèn)題，本文提出了基于公理分割的本體精確調(diào)試的方法。該方法先采用一般的本體調(diào)試算法求出MUPS，然后對(duì)MUPS求解結(jié)果進(jìn)行公理分割，基于分割后的公理集獲得一個(gè)精確(Precise)的MUPS解(PMUPS)。

1 本體調(diào)試及其局限

描述邏輯所表示的知識(shí)庫(kù)包括術(shù)語(yǔ)集(TBox，表示為T(mén))和斷言集(ABox，表示為A)兩部分，TBox定義了領(lǐng)域知識(shí)的概念、角色以及概念之間或角色之間的關(guān)系，它們是通過(guò)公理這種形式體現(xiàn)出的。ABox表示的是領(lǐng)域內(nèi)的個(gè)體，是概念或角色的實(shí)例化。在實(shí)際應(yīng)用中，很多本體只定義了某個(gè)領(lǐng)域內(nèi)的基本知識(shí)，而沒(méi)有涉及具體的實(shí)例，即這類(lèi)本體只包括術(shù)語(yǔ)集而沒(méi)有斷言集，通常將這類(lèi)術(shù)語(yǔ)集也稱為本體。

1.1 本體調(diào)試?yán)碚?/p>

描述邏輯語(yǔ)言的語(yǔ)法與語(yǔ)義列于表1，其中A、B是原子概念，R、S是原子角色，C、D是概念描述。描述邏輯語(yǔ)義將概念解釋為論域Δ的上的子集，角色為其上的二元關(guān)系。形式上，解釋I=(ΔI,·I)是知識(shí)庫(kù)的模型，它由論域ΔI和解釋函數(shù)·I組成。

表1 描述邏輯語(yǔ)言的語(yǔ)法與語(yǔ)義

從邏輯表達(dá)能力的角度劃分，ALC是最基本的描述邏輯語(yǔ)言，它包括Τ、⊥、、?、?、∩、∪這些構(gòu)造算子。在ALC基礎(chǔ)之上加入角色包含就得到ALCH，再加入數(shù)量限制得到ALCHN，進(jìn)一步加入逆角色則為ALCHIN，再加入枚舉算子即為ALCHION。一般將傳遞角色加入ALC后得到的語(yǔ)言表示為S，按照上述同樣的方式，隨著新的算子的加入可以依次得到SHN、SHIN、SHION。倘若包括有數(shù)值、時(shí)間等數(shù)據(jù)類(lèi)型，則添上后綴(D)。

定義1(不可滿足概念)[9]若C是本體術(shù)語(yǔ)集T中的某個(gè)概念，如果對(duì)于T的任意解釋I，都有C=?，則C是T中的不可滿足概念。

定義2(不一致本體)[9]如果本體中存在一個(gè)不可滿足概念，則T是不一致本體。

上例中的T就是不一致本體，因?yàn)樗嬖谝粋€(gè)不可滿足概念people。

定義3(MUPS)[9]設(shè)概念C是TBoxT中的不可滿足概念，某個(gè)子集T′?T是C的極小不可滿足保持子術(shù)語(yǔ)集MUPS(minimal unsatisfiable preserving sub-TBox)，如果C在T′中是不可滿足的，而對(duì)于任意T″?T′，C在T″都是可滿足的。

T中不可滿足概念C的MUPS的集合記作MUPS(T,C)，在T確定的情形下一般簡(jiǎn)寫(xiě)為MUPS(C)。前面例子中的不可滿足概念people的MUPS集合為MUPS(people)={{α1,α2}}。

1.2 本體調(diào)試的局限

2 基于公理分割的精確調(diào)試方法

本文的研究目標(biāo)是精確獲取導(dǎo)致概念不可滿足性的公理中的某一片段(或部分)，基于這一目標(biāo)所提出的解決方案是對(duì)公理進(jìn)行分割。特別需要指出的是：公理分割所要遵循的原則是分割之后形成的多個(gè)小公理必須在邏輯上等價(jià)于原公理，或者說(shuō)，分割之后的公理不得改變?cè)淼恼Z(yǔ)義。

2.1 公理分割思想

本文的公理分割方案首先將待分割的公理通過(guò)轉(zhuǎn)換公式[21]：

(1)

(2)

這里將概念劃分為兩類(lèi)：簡(jiǎn)單概念是形如原子概念A(yù),原子否定A,數(shù)量限制概念≥nR,≤nR與枚舉概念{a}；復(fù)合概念則是基于多個(gè)簡(jiǎn)單概念運(yùn)用合取∩、析取∪、全稱量詞?與存在量詞?聯(lián)結(jié)而形成的復(fù)雜概念。算法1給出了公理分割的實(shí)現(xiàn)過(guò)程。該算法的基本思想是將MUPS中的每個(gè)公理分割成多個(gè)子公理，并且確保分割之前的公理與分割之后得到的子公理集具有語(yǔ)義上的等價(jià)性。

算法1公理分割算法。

輸入：待分割的公理集合M

輸出：分割集Ω

1. Σ=Tran(M)

2. for each C in S

3. if (C是簡(jiǎn)單概念), then

4. Seg(C)={C}

5. end if

6. else (C是復(fù)合概念)

7. (a) if (C形如C1∩C2), then

8. Seg(C)= Seg(C1)∪ Seg(C2)

9. (b) if (C形如C1∪C2) , then

11. (c) if (C形如?R.D) , then

12. Seg(C)=∪D′∈Seg(D)?R.D′

13. (d) if (C形如?R.D)，then

14. (i) 若D形如D1∩D2，則Seg(C)={?R.X}∪

15. (ii)否則，Seg(C)=∪D′∈Seg(D)?R.D′

16. end for

17. Seg*(C)=Tran*[Seg(C)]

18. Ω=Ω∪Seg(C)。

19. end for

20. return Ω

首先將MUPS中的所有公理(即待分割的公理集合M)借助轉(zhuǎn)換公式(式(1)、式(2))轉(zhuǎn)化為其等價(jià)的概念析取形式得到概念析取集S(第1行)。對(duì)于S中的每個(gè)概念析取式C，如果C是簡(jiǎn)單概念，則不做分割處理(第3～5行)。否則考慮四種形式下的分割操作，當(dāng)C是兩個(gè)概念C1、C2之間的交集形式時(shí)，分別對(duì)C1與C2執(zhí)行分割操作(第7～8行)。當(dāng)C是兩個(gè)概念C1、C2之間的并集形式時(shí)，將C1與C2分割后的各個(gè)部分分別組合成并集形式(第9～10行)。當(dāng)C是全稱量詞限定形式時(shí)，對(duì)全稱限定的值域部分進(jìn)行分割并將分割結(jié)果作為新的全稱限定的值域部分(第11～12行)。當(dāng)C是存在量詞限定形式時(shí)，如果存在限定的值域部分是概念的交集形式，根據(jù)語(yǔ)義等價(jià)的原則，生成四個(gè)新的概念析取式，否則僅對(duì)存在限定的值域部分進(jìn)行分割并將分割結(jié)果作為新的存在限定的值域部分(第14～15行)。每次分割操作結(jié)束，都需要執(zhí)行一次逆向轉(zhuǎn)換，將概念析取式還原成公理的形式(第17行)。并將其放入分割集Ω中(第18行)。

需要強(qiáng)調(diào)的是：這種分割必須是無(wú)失真的分割，即分割之前的公理與分割之后的公理集合必須確保在邏輯上的等價(jià)性。定理1保證了分割操作的正確性。

定理1C是由公理集M中的某一公理轉(zhuǎn)換得到的復(fù)合概念，設(shè)I是C在M中的任意一個(gè)解釋，Seg(C)是算法1得到的分割結(jié)果，則CΙ=SegΙ(C)。

證明：

(1) 若C是簡(jiǎn)單概念，則SegΙ(C)={C}Ι。

(4) 若C形如?R.D，則CΙ=(?R.D)Ι={a∈ΔΙ|?b。(a,b)∈RΙ→b∈DΙ}。由Seg(C) = ∪D′∈Seg(D)?R.D′，得SegΙ(C)=∪D′∈Seg(D){a∈ΔΙ|?b.(a,b)∈(a,b)∈RΙ→b∈D′Ι}={a∈ΔΙ|?b.(a,b)∈RΙ→b∈DΙ}。因此CΙ=SegΙ(C)。

(5) 若C形如?R.D，且D形如D1∩D2，則有CΙ=(?R.D)Ι=(?R.(D1∩D2))Ι。由于Seg(C)={?R.X,X}∪Seg((X∪D1)∪Seg((X∪D2)∪Seg((D1∪D2∪X)，根據(jù)轉(zhuǎn)換式(2),可將X∪D1，X∪D2與D1∪D2∪X分別轉(zhuǎn)換為即根據(jù)轉(zhuǎn)換式(1)，進(jìn)一步得到X≡D1∩D2，則XΙ=(D1∩D2)Ι，那么SegΙ(C)=(?R.XΙ)=(?R.(D1∩D2)Ι=(?R.(D1∩D2))Ι。因此CΙ=SegΙ(C)。

(6) 若C形如(R.D，且D為非合取概念，則CΙ=(?R.D)Ι={a∈ΔΙ|(b.(a,b)∈RΙ(b∈DΙ}。由Seg(C)=∪D′∈Seg(D)?R.D′可知：SegΙ(C)=∪D′∈Seg(D){a∈ΔΙ|?b.(a,b)∈RΙ∧b∈D′Ι}={a∈ΔΙ|?b.(a,b)∈RΙ∧b∈DΙ}。因此CΙ=SegΙ(C)。

對(duì)于C在M中的任意一個(gè)解釋?duì)?，定?保證了滿足C的解釋CΙ也滿足分割之后的C的解釋SegΙ(C)。因此，雖然在語(yǔ)法層面上分割前后的公理結(jié)構(gòu)出現(xiàn)了變化，但在語(yǔ)義層面上卻能夠保證分割前后的不變性。

對(duì)于一個(gè)復(fù)合概念，經(jīng)過(guò)不斷的分割操作，最終會(huì)得到一系列簡(jiǎn)單概念。待所有的復(fù)合概念都分割為簡(jiǎn)單概念，則分割操作結(jié)束。

定理2設(shè)C是由公理集M中的某一公理轉(zhuǎn)換得到的復(fù)合概念，Seg(C)是算法1得到的分割結(jié)果，令C′∈Seg(C),則C′為簡(jiǎn)單概念。

證明：

(1) 若C是簡(jiǎn)單概念，算法執(zhí)行結(jié)果為其本身。

(2) 若C是復(fù)合概念，算法遍歷執(zhí)行如下過(guò)程：

① 若C形如C1∩C2，算法生成兩個(gè)新的概念C1與C2，若C1或C2是簡(jiǎn)單概念，則轉(zhuǎn)向(1)。否則轉(zhuǎn)向(2)。

② 若C形如C1∪C2，若C1或C2是簡(jiǎn)單概念，則轉(zhuǎn)向(1)。否則轉(zhuǎn)向(2)。

③ 若C形如?R.D，若D是簡(jiǎn)單概念，則轉(zhuǎn)向(1)。否則轉(zhuǎn)向(2)。

④ 若C形如?R.D，且D為合取情形，算法生成四個(gè)新的復(fù)合概念?R.X、X∪D1、X∪D2、D1∪D2∪X。對(duì)于每一個(gè)復(fù)合概念中的X、D1與D2，若是簡(jiǎn)單概念，則轉(zhuǎn)向(1)。否則轉(zhuǎn)向(2)。

⑤ 若C形如?R.D，且D為非合取情形，若D是簡(jiǎn)單概念，則轉(zhuǎn)向(1)。否則轉(zhuǎn)向(2)。

在對(duì)嵌套的復(fù)合概念進(jìn)行分割過(guò)程中，每一次分割，都會(huì)使得復(fù)合概念更進(jìn)一步接近簡(jiǎn)單概念，直至全部的分割結(jié)果均為簡(jiǎn)單概念為止，此時(shí)，結(jié)果為該概念自身。因此分割結(jié)果集合Seg(C)中的每一個(gè)概念C′均為簡(jiǎn)單概念。

λα的取值范圍為[0,1)，當(dāng)SSeg(α)=1時(shí)，λα=0，這時(shí)分割前后的公理集合是相同的，這表明分割算法在該MUPS上失效。

上例中，已求得λα1=λα2=66.7%，則λ=66.7%。

2.2 精確調(diào)試求解算法

由公理分割算法1，可以得到一個(gè)細(xì)粒度的公理分割集合。基于該集合，進(jìn)一步求解出更精確的MUPS結(jié)果(PMUPS)，將那些與概念不可滿足性(或本體不一致性)無(wú)關(guān)的部分概念篩選出去從而得以保留下來(lái)。算法2給出了PMUP的求解方案。

算法2PMUPS精確調(diào)試算法。

輸入：不一致本體T

輸出：PMUPS

1. U =Reasoning(T)

2. for each u in U

3. calculate the MUPS(T, u)

4. for each M in MUPS(T, u)

5. Ω=Segmentation(M)

6. MΩ=calculate the MUPS(Ω, u)

7. PMUPS.add(MΩ)

8. end for

9. end for

10. return PMUPS

算法2首先調(diào)用推理機(jī)求出不一致本體里面的所有不可滿足概念(第1行)。針對(duì)每個(gè)不可滿足概念，首先調(diào)用本體調(diào)試算法求取其MUPS(第3行)，針對(duì)MUPS中的每一個(gè)集合，依次進(jìn)行公理分割操作，基于分割集合進(jìn)一步求出其PMUPS(第4～7行)。例如：有一個(gè)不一致術(shù)語(yǔ)集T包括如下四條公理：

(1) 調(diào)用推理機(jī)可以求得不可滿足概念集合U={C4}。

(2) 對(duì)于U中的每個(gè)元素，求出它的MUPS(T,C4)={{α1,α2,α4}}。

(3) 對(duì)于MUPS(T,C4)中的每個(gè)元素M={α1,α2,α4}，調(diào)用算法1執(zhí)行公理分割操作，得到分割集Ω：

定理3PMUPS精確調(diào)試算法具有多項(xiàng)式時(shí)間復(fù)雜度。

證明：

(1) 令不一致本體T中不可滿足概念的個(gè)數(shù)為n=|U|，n∈(0, |TC|]，|TC|為T(mén)中概念的總個(gè)數(shù)；令任意一個(gè)MUPS(u)的元素(形式上為一個(gè)集合)M的個(gè)數(shù)為m，則有m∈[1, |TA|]，|TA|為T(mén)中公理的個(gè)數(shù)。

(2) 對(duì)于任意一個(gè)待分割的M集合，由公理分割算法可知，只有在以下兩種合取情形下才發(fā)生分割操作生成新的概念：一是待分割復(fù)合概念形如C1∩C2，算法生成兩個(gè)新的概念；二是待分割復(fù)合概念形如?R.D，且D為D1∩D2情形下，算法生成四個(gè)新的概念。令T中合取算子的個(gè)數(shù)為k，則分割操作最多執(zhí)行次數(shù)為4k，為線性時(shí)間復(fù)雜度。

綜上，PMUPS精確調(diào)試算法最多執(zhí)行次數(shù)為4nmk，為多項(xiàng)式時(shí)間復(fù)雜度。

η的取值范圍為[0,1)，當(dāng)SSeg(M)=SPM時(shí)，η=0，這表明對(duì)MUPS分割之后得到的公理都出現(xiàn)在PMUPS集合中。

留存度的提出是為了對(duì)精確調(diào)試方案進(jìn)行定量分析，留存度越高，表示本體信息的損失就越少。以此來(lái)確保專家在基于調(diào)試結(jié)果的后續(xù)修復(fù)階段避免有效信息的丟失。

3 實(shí)驗(yàn)及分析

實(shí)驗(yàn)是在PC機(jī)Windows 10操作系統(tǒng)(Intel(R) Core(TM) CPU 3.40 GHz, 4.00 GB RAM)下進(jìn)行的，使用OWLAPI3.4.3進(jìn)行本體的導(dǎo)入和操作，使用Pellet2.3.1進(jìn)行推理。訪問(wèn)網(wǎng)址http://www.zhyweb.cn/ontodebugging/pmups/index.php可以下載測(cè)試本體集以及本文算法的源程序。

實(shí)驗(yàn)的測(cè)試本體囊括了不同表達(dá)層級(jí)不同領(lǐng)域的本體，對(duì)于每一個(gè)不一致術(shù)語(yǔ)集TBox，表2列出了其表達(dá)層級(jí)、概念數(shù)量|CS|、不可滿足概念個(gè)數(shù)|CU|以及公理總數(shù)|NA|。

表2 不一致本體術(shù)語(yǔ)集屬性統(tǒng)計(jì)

3.1 分割率與留存度實(shí)驗(yàn)

表3列出了對(duì)MUPS執(zhí)行分割操作前后所得到的調(diào)試結(jié)果。其中SM表示分割之前的MUPS的各元素中包括的公理數(shù)量總和，SSeg(M)表示對(duì)MUPS進(jìn)行分割之后得到的公理數(shù)量總和，SPM表示基于分割集Seg(M)所求得的PMUPS的各元素中包括的公理數(shù)量總和，NM表示MUPS中所有公理所包含的概念符號(hào)最大數(shù)目，NPM表示PMUPS中所有公理所包含的概念符號(hào)最大數(shù)目。λ表示MUPS分割率，η表示留存度。

表3 MUPS分割前后調(diào)試結(jié)果

續(xù)表3

3.2 留存度與調(diào)試時(shí)間對(duì)比實(shí)驗(yàn)

PMUPS算法通過(guò)公理分割的方法獲得精確的MUPS調(diào)試結(jié)果，以此確保盡可能高的留存度，從而實(shí)現(xiàn)修復(fù)環(huán)節(jié)減少本體信息損失這一目標(biāo)。文獻(xiàn)[21]為了達(dá)到這一目標(biāo)，采取的是細(xì)粒度的調(diào)試方案(FGDebugger)，而文獻(xiàn)[22]則從本體修復(fù)這一角度，提出了細(xì)粒度的修復(fù)方案(FGRepair)。圖1將本文算法與上述兩種算法從留存度方面進(jìn)行對(duì)比實(shí)驗(yàn)。

圖1 留存度對(duì)比實(shí)驗(yàn)結(jié)果

留存度對(duì)比實(shí)驗(yàn)結(jié)果顯示：(1) Economy本體(T4)與Proton本體(T9)的MUPS求解結(jié)果的公理集里面不存在與本體不一致無(wú)關(guān)的部分公理，因而在后續(xù)修復(fù)階段，這些公理都需要整個(gè)刪除，所以三種算法得到的留存度都為0，這是由本體的MUPS結(jié)構(gòu)決定的。(2) PMUPS算法所獲得到的留存度普遍高于FGDebugger。(3) 除T2與T5本體之外，PMUPS算法的結(jié)果都優(yōu)于FGRepair，在這兩個(gè)本體上，PMPUS與FGRepair所得到的留存度是相等的，但它們均優(yōu)于FGDebugger。

圖2將本文算法與FGDebugger和FGRepair兩種算法從調(diào)試時(shí)間方面進(jìn)行對(duì)比實(shí)驗(yàn)。結(jié)果顯示：(1) PMUPS算法的MUPS求解時(shí)間在全部測(cè)試本體上都要少于FGDebugger，因而算法性能優(yōu)于FGDebugger。(2) 除了T5本體上PMUPS算法與FGRepair算法性能一樣，其他本體上PMUPS算法都要優(yōu)于FGepair算法。但在T7、T8兩個(gè)本體上，兩者求解時(shí)間相當(dāng)接近。

圖2 調(diào)試時(shí)間對(duì)比結(jié)果圖

4 結(jié) 語(yǔ)

本體調(diào)試是解決本體不一致問(wèn)題的主要手段，現(xiàn)有的各種本體調(diào)試算法能夠給出導(dǎo)致概念不可滿足的一組公理集合，刪除這些公理即可解決不一致問(wèn)題。然而，刪除公理會(huì)伴隨著出現(xiàn)本體信息丟失的情況。為了避免本體調(diào)試中的信息丟失，提出了不一致本體精確調(diào)試的思路。該思路采取公理分割的方案，目的是篩選出真正導(dǎo)致概念不可滿足性的公理的某一部分，刪除公理的這一部分而不是全部的公理來(lái)解決信息丟失的問(wèn)題。為了驗(yàn)證所提出方法的有效性，采用了不同表達(dá)層級(jí)不同結(jié)構(gòu)形式不同領(lǐng)域的不一致本體，進(jìn)行了留存度與調(diào)試時(shí)間兩個(gè)方面的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果顯示，所提出的精確調(diào)試算法在留存度與調(diào)試時(shí)間兩方面都比類(lèi)似相關(guān)的算法取得較好的效果。

下一步的研究目標(biāo)是在精確調(diào)試的基礎(chǔ)上進(jìn)一步對(duì)沖突公理集的每條公理對(duì)不一致性的影響程度進(jìn)行量化，為每條公理設(shè)定權(quán)重值，在后續(xù)修復(fù)過(guò)程中以權(quán)重值高低作為修復(fù)的先后順序。

[1] 李冬梅.本體不一致問(wèn)題研究[D].北京:北京交通大學(xué),2014.

[2] 周麗平.DL-Lite本體的不一致處理方法研究[D].北京:北京交通大學(xué),2010.

[3] 劉杰,李宏偉,沈立煒,等.分布式本體的構(gòu)建與一致性維護(hù)方法[J].計(jì)算機(jī)應(yīng)用與軟件,2015(10):15-20.

[4] 吳潔明,劉雁昆,段建勇.基于維基百科的領(lǐng)域本體自動(dòng)構(gòu)建方法研究[J].計(jì)算機(jī)應(yīng)用與軟件,2016,33(7):72-75.

[5] Baader F,Calvanese D,Mcguinness D L,et al.The description logic handbook: theory,implementation, and applications[J].Kybernetes,2003,32(9/10).

[6] 韓道軍,甘甜,葉曼曼,等.基于形式概念分析的本體構(gòu)建方法研究[J].計(jì)算機(jī)工程,2016,42(2):300-306.

[7] 雷景佩.基于概念包含推理的本體調(diào)試[D].長(zhǎng)春:吉林大學(xué),2015.

[8] Schlobach S.Diagnosing Terminologies[C]//The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference,July 9-13,2005,Pittsburgh,Pennsylvania,Usa.DBLP,2005:670-675.

[9] Schlobach S,Huang Z,Cornet R,et al.Debugging Incoherent Terminologies[J].Journal of Automated Reasoning,2007,39(3):317-349.

[11] Suntisrivaraporn B,Qi G,Ji Q,et al.A Modularization-Based Approach to Finding All Justifications for OWL DL Entailments[C]//Asian Semantic Web Conference on the Semantic Web.Springer-Verlag,2008:1-15.

[12] Horridge M,Parsia B,Sattler U.Explaining Inconsistencies in OWL Ontologies[C]//Scalable Uncertainty Management,Third International Conference,SUM 2009,Washington,DC,USA,September 28-30,2009.Proceedings.DBLP,2009:124-137.

[13] Kalyanpur A,Parsia B,Horridge M,et al.Finding All Justifications of OWL DL Entailments[C]//International the Semantic Web and,Asian Conference on Asian Semantic Web Conference.Springer-Verlag,2007:267-280.

[14] Meyer T,Lee K,Booth R,et al.Finding maximally satisfiable terminologies for the description logic ALC[C]//National Conference on Artificial Intelligence.AAAI Press,2006:269-274.

[15] Fleischhacker D,Meilicke C,V?lker J,et al.Computing Incoherence Explanations for Learned Ontologies[C]//International Conference on Web Reasoning and Rule Systems.Springer-Verlag,2013:80-94.

[16] Fleischhacker D.Repairing Learned Ontologies[C]//ESWC 2014:proceedings of the 11th Extended Semantic Web Conference,May 26,2014.CEUR-WS,c2014.

[17] Fu X,Qi G,Zhang Y,et al.Graph-based approaches to debugging and revision of terminologies in DL-Lite[J].Knowledge-Based Systems,2016,100:1-12.

[18] Lembo D,Santarelli V,Savo D F.Graph-Based Ontology Classification in OWL 2 QL[C]//Proceeding of ESWC 2013-the Semantic Web:Semantics and Big Data,International Conference,2013:320-334.

[19] Zhuang Z,Wang Z,Wang K,et al.Contraction and revision over DL-Lite Tboxes[C]//AAAI 2014:proceedings of the 28th AAAI Conference on Artificial Intelligence,July 27-31,2014.AI Access Foundation,c2014.

[20] Qi G,Wang Z,Wang K,et al.Approximating model-based ABox revision in DL-Lite[C]//Theory and practice:AAAI 2015:proceedings of the 29th AAAI Conference on Artificial Intelligence,June 1,2015.AI Access Foundation,c2015.

[21] Lam J S C,Sleeman D,Pan J Z,et al.A fine-grained approach to resolving unsatisfiable ontologies[C]//IEEE/WIC/ACM International Conference on Web Intelligence.Springer-Verlag,2008:62-95.

[22] Du J,Qi G,Fu X.A Practical Fine-grained Approach to Resolving Incoherent OWL 2 DL Terminologies[C]//CIKM 2014 :proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management.ACM,Shanghai,November 3-7,2014.Association for Computing Machinery,Inc,c2014.

ANAXIOMSEGMENTATIONAPPROACHFORPRECISELYDEBUGGINGTHEINCOHERENTONTOLOGY

Zhang Yongtao
(CollegeofInformationEngineering,ShangqiuInstituteofTechnology,Shangqiu476000,Henan,China)

Ontology debugging is the main means to resolve the incoherence of ontology. The existing debugging methods can provide a set of error axioms responsible for the incoherence of the ontology, and removing the set of problematic axioms can resolve the inconsistence. However, removing these problematic axioms can cause several information of the ontology to be lost. In order to avoid the loss of information, this paper presents a debugging approach based on the axiom segmentation method. This approach performs the debugging on the subsets of axioms obtained by the axiom segmentation. In this way, the loss of ontology information can be avoided. The experiment results demonstrate that the proposed approach performs better than the existing debugging algorithms both in reservation rate and debugging time over the most types of incoherent ontologies.

Ontology debugging Incoherent ontology Unsatisfiable concept Axiom segmentation Precise debugging for incoherent ontology

2016-11-02。張永濤，講師，主研領(lǐng)域：語(yǔ)義網(wǎng)，本體調(diào)試。

TP3

A

10.3969/j.issn.1000-386x.2017.08.011