面向需求的應用本體不一致診斷方法研究

宋丹輝

(河南科技大學圖書館，河南 洛陽 471023)

?

·理論探索·

面向需求的應用本體不一致診斷方法研究

宋丹輝

(河南科技大學圖書館，河南 洛陽 471023)

為計算復雜應用本體中非合法蘊含式集合的根本性沖突原因，首先對現有不一致診斷方法進行系統的梳理，然后結合應用本體及其需求特點，分析存在問題與不足，探討將原本相互孤立的、分別應用在不同診斷工具中的反模式探測法、根辨解法、簡潔辨解法之核心算法進行組合、優化的思路與方法。在此基礎上，提出一個綜合性的啟發式簡潔根辨解診斷法，闡述其基本思路與具體步驟，并以相關論文中經常使用的實驗本體為例，驗證方法的有效性。

應用本體；不一致診斷；簡潔辨解；根辨解；反模式探測

語義網的發展強化了用戶對高質量應用本體的需求。但應用本體開發是一個復雜過程，需要綜合使用多種語言構件來描述具體業務約束規則。在描述邏輯復雜性無法改變、開發者素質無法在短時間內提高的前提下，現有開發方法又普遍缺乏對本體評價、尤其是面向需求的功能評價的支持，這使得本體很容易出現各種不一致問題，嚴重影響語義正確性及后續推理服務的質量。

從性質上看，這不一致既可能是與本體邏輯基礎不符的內部錯誤(不可滿足概念UC)，也可能是與背景知識、領域基本假定不符的潛在語義錯誤(錯誤的推論)。且都是經推理才能得到的隱含知識，無法直接刪除。只有先識別其可能的產生原因、逐一修正才能徹底消除，這便是應用本體診斷的核心內容[1]。

不同研究者先后提出多種不一致診斷方法，如反模式探測法[2-5]、根辨解法[6]和簡潔辨解法[7-9]等。這些方法雖然從不同角度不同程度改善了本體診斷的性能，但就復雜應用本體及其多樣化需求而言，仍存在各種局限與不足。目前仍沒有一套完整的、既解決內部不一致、也消除潛在語義錯誤的本體不一致診斷流程或方法，這給實踐造成很多不便。

為彌補上述缺漏，本文首先對現有不一致診斷方法進行系統的梳理，然后結合應用本體及其需求特點，分析存在問題與不足，探討將反模式探測法、根辨解法、簡潔辨解法之核心算法進行優化組合的思路與方法。在此基礎上，提出一個綜合性的啟發式簡潔根辨解診斷法，并以相關論文中經常使用的實驗本體為例，驗證方法的有效性。

1 現有工具存在的問題

本體診斷的首要任務是計算辨解，辨解是導致不一致的最小公理集合[10]，其特點是不可再約簡，刪除其中任何一個公理，推理機便無法推出錯誤結論，本文將這種需推理才發現的錯誤結論稱為非合法蘊含式，簡稱蘊含式。就特定蘊含式而言，辨解可能是一個，也可能是多個。每個辨解代表一個獨立的充分條件。要真正消除蘊含式，就必須從每個辨解中至少刪除或修改一個公理，這種為消除蘊含式必須刪除或修改的最小公理集合就是最小診斷[11]。

辨解可能包含與沖突無關的元素(導致概念不可滿足或非合法蘊含式的往往只是公理的部分，并非整個公理)[12]，也可能被其他辨解所屏蔽(某些潛在的沖突原因被其他辨解所掩蓋，無法識別)[13]，不同辨解間也可能存在依賴關系[14]，這些都會影響后續計算診斷的效率。只有同時保證簡潔性、完備性及不依賴其他辨解的獨立性辨解，才能真正反映根本性沖突。本文稱這種無冗余、無屏蔽及面向全局獨立的辨解為簡潔根辨解。

若用蘊含式描述具體需求，那么判斷本體是否滿足具體需求便可通過檢測本體與蘊含式的一致性來實現。在實際應用中，具體需求往往有多個，用于檢測一致性的蘊含式也就多個，若要依據具體需求來修正本體，計算該蘊含式集的簡潔根辨解就不可避免。然而，理想與現實之間總是存在差距，對應用本體而言，目前還沒有任何本體診斷工具能完成該任務。從診斷過程對推理機的依賴程度和所得辨解質量看，各工具的局限主要表現在：

(1)過度依賴推理，沒有科學利用前人總結出來的建模經驗。現有診斷方法要么完全依賴推理，將效率問題一律推給推理機。產生的后果是：不能在有限時間內給出所有辨解，尤其在UC較多、每個UC含較多MUPS、或不一致本體的復雜情況下，受推理機一致性檢測效率的影響；要么完全放棄推理，只考慮常見錯誤模式，用SPARQL檢索式或圖搜索算法來探測沖突。產生的后果是：無法找到與模式不匹配的沖突原因，不能保證完備性，都不能兼顧效率和完備性。

(2)只偏重辨解的某方面特性，不能同時保證辨解的簡潔性、完備性和全局獨立性。只有不遺漏任何辨解，且找到辨解都無冗余、不依賴任何其他辨解的方法才是真正有助于用戶理解沖突原因并找到最佳解決方案的理想方法。簡潔辨解法雖然能識別屏蔽、排除與沖突無關的元素，但一次只能處理一個不可滿足概念。當不可滿足概念較多時，需要多輪迭代、構建多顆HStree并將結果組合才可找到所有辨解，其繁瑣和復雜程度非普通用戶所能容忍；根辨解法雖然能基于多個需求識別必須要消除的關鍵性沖突原因，保證辨解全局獨立性，但卻以原本體中公理為對象，會牽連沖突無關元素，也可能有屏蔽，準確性有問題。

總而言之，就復雜應用本體的多個需求而言，目前還沒有能同時保證辨解簡潔性、完備性和全局獨立性的方法。

2 啟發式簡潔根辨解法

應用本體都是為滿足特定需求或任務而建的，公理相對復雜，否定、存在或全稱約束多，需求數量多、種類也多，更容易出現公理與需求不符的異常情況，潛藏語義錯誤。

簡潔辨解法與根辨解法偏重于不同方面，有結合可能，若能將二者有機結合，在保證簡潔性和完備性的基礎上計算根辨解，便可優勢互補，鎖定主要矛盾的主要方面。此外，計算根辨解不僅需要對測試用例集進行一致性檢測，還需要構建HStree，二者都需要頻繁的一致性檢測。而一致性檢測的效率與本體語言復雜度及本體規模有很大關系，本文研究對象是復雜應用本體，規模小但復雜度高。為保證效率，就需要盡量減少調用推理機的次數。

2.1 基本思路

為排除冗余、識別屏蔽，本文添加預處理過程，先對本體進行π(Osplit)結構轉化[12]，按規則解析所有被嵌套或隱含的語義，并用原子公理表達后，再執行后續診斷流程。π(Osplit)的本質就是在不添加新概念的前提下，根據概念在不同類公理或表達式中的位置，設置不同的轉化規則，并用公理索引號記錄轉化后公理與原公理的對應關系。轉化后，任何復雜公理或表達式都可以按語義弱化為語義最約簡的原子公理的集合，保證辨解的簡潔性和完備性。

為減少調用推理機的次數，本文以不可滿足概念為起點、通過啟發式規則來探測反模式，并篩選其中不依賴任何其他沖突的根本性沖突作為下一步處理對象。其依據是導致概念不可滿足的原因有兩類：約束條件之間不兼容(如表1)；約束條件自身不可滿足，且不可滿足性會隨著子類關系和存在約束傳播(如表2，所有不可滿足概念的下位類都是不可滿足的；只要存在約束的filler不可滿足，那么被約束概念一定也是不可滿足的。表中規則都是參考這種演化機制制定的)[3]。需要說明的是，本步驟雖然只能找到部分辨解，但有助于開發者理解錯誤產原因，進而由此及彼分析其他可能錯誤。

表1 約束條件之間不兼容造成的不可滿足及其判定依據

表2 約束條件自身不可滿足的判定依據

為保證辨解面向多需求的全局獨立性，本文以結構轉化后的本體O′為基礎，以模式匹配探測到的反模式pdcs為初始化最小沖突集Conf，以代表需求的B∪P∪

N(B代表肯定正確的、不能出現在診斷中的背景理論，P代表必須被目標本體所蘊含的句子集合，N代表一定不能被目標本體所蘊含的句子集合)為判定條件，以quickXplain算法(其性能比滑動窗口法更優)及批量一致性檢測來計算與需求不符的根本性最小沖突集(也就是阻礙需求得以滿足的非合法蘊含式集合的單個根辨解)，應用路徑提前封閉和節點重用技術，寬度優先構建并擴展HStree，真正實現在一顆HStree中找到所有簡潔根辨解[15-16]。

考慮到反模式探測也需要原子公理，故先將O進行π(Osplit)結構轉化，再用啟發式規則探測反模式。反模式探測結果pdcs用于初始化HStree的最小沖突集Conf。需要注意的是，探測結果并非都是根本性的，為確保辨解的全局獨立性，本文添加過濾環節，只篩選不依賴任何其他沖突的根本性沖突存入pdcs作為下一步的處理對象。凡不可滿足概念UC與兩個沖突概念間路徑有交集、或者是其他沖突真超集的沖突都非最簡，直接被舍棄。

整個流程如圖1所示，先結構轉化、再用啟發式規則探測反模式，最后構建HStree。前兩個任務只受轉化規則和啟發式探測規則的制約，與需求無關，不管測試用例如何變化，其結果都是不變的，后者允許添加測試用例，結果會隨著測試用例的變化而變化。

圖1 啟發式簡潔根辨解法的基本思路

2.2 核心步驟

上述流程的重點是第三步，其基本流程如圖2。對于根節點，用pdcs初始化最小沖突集Conf。若存在這樣的沖突集Conf，則從Conf中任取一個cs作為根節點標識符，針對其中每個公理，擴展新分支，生成新路徑(根據辨解定義，刪除cs中的任一公理都可以消除該沖突，因此要遍歷每個公理，并且都進行擴展)。若pdcs為空，不存在任何反模式，最小沖突集Conf為空，則直接用quickXplain計算與需求不符的最小沖突集srj做為根節點。

圖2 構建HStree的基本流程

判斷新生成path是否需要提前封閉的規則是：

(1)若存在達到一致的路徑H(n)?H(n′)或者H(n)=H(n′)，則封閉n′。換句話說，若H(n′)是HS中某個已有最小擊中集H(n)的真超集或者與某條已生成路徑H(n)相同，則提前封閉該路徑；

(2)若不存在這樣的路徑H(n)，則以當前路徑為參數，考察是否存在可重用的節點標識。

判斷是否有可重用節點標識的規則是：

(1)若存在標引其他節點的CS(n)，滿足CS(n)∩H(n′)=⊥，則重用該CS(n)標引n′。換句話說，若存在某節點的標識符或最小沖突集cs與當前路徑無交集，則用其標引當前新節點；

(2)若沒有可重用的節點標識CS(n)，則調用推理機，用quickXplain算法結合B∪P∪

N重新生成新的CS(n′)；

(3)若沒有滿足上述條件的CS(n′)，則表明沖突已消除，無需再擴展，用√來結束該分支。該節點到根節點的路徑H(n)可作為新的最小擊中集存入HS。

擴展新節點的基本規則是：對于新節點，遍歷其公理，擴展新分支，生成新路徑。重復上述兩個判定過程，直到出現規定數量的葉節點或者所有根辨解和最小擊中集為止。

綜上，該步驟的本質就是將初始最小沖突集Conf、計算單個根辨解方法quickXplain與HG路徑擴展法相結合，先遍歷當前最小沖突集cs中公理、依次擴展出新的邊，然后針對每條邊構建新的路徑path′，并參考已有最小擊中集和最小沖突集，判斷path′是否有真子集、是否有相同路徑、是否有不相交節點標識符可重用，若有則重用、若沒有則基于path′重新計算新的最小沖突集cs′的循環過程。

所得最小診斷的最小性是最小沖突集、路徑提前封閉、節點重用和寬度優先搜索策略共同作用的結果。先生成最小診斷的基數一定是最小的。后續得到最小診斷則會隨著HStree的層數而增長。所得最小診斷的正確性和完備性則取決于HStree算法、quickXplain、一致性檢測的正確性與完備性。

2.3 效率分析

從效率上看，提高效率的關鍵點主要有兩個：一個是用pdcs初始化HStree的最小沖突集，減少調用推理機的次數；一個是在擴展同一分支過程中，用遞減式策略處理P中的需求e+。而降低效率的關鍵點也有兩個：一是預處理中的π(Osplit)結構轉化；二是反模式探測。

在quickXplain算法中，要計算節點n的最小沖突集，就需要檢測是否存在使需求e+∈P不可滿足的非合法蘊含式η，使得(O-path)∪B∪e+∪

N不一致。若存在，則計算其根辨解。對于n的后繼節點n′而言，任何已被父節點滿足的需求，也就是(O-path)∪B∪e+∪

N一致的e+都無需再考慮。這是因為，子節點路徑是父節點路徑的真超集(path?path′)，那么子節點本體一定是父節點本體的真子集(O-path′?O-path)，已在父本體中消除的非合法蘊含式在子本體中一定也不存在，換句話說，在父本體中可滿足的需求在子本體中一定也是可滿足的。若用集合CE(n)為每個節點n存儲所有的與O-path∪B∪e+∪

N一致的e+，那么就新生成節點n′而言，只需檢測P-∪m∈predecessor(n′)CE(m)中是否存在與(O-path′)∪B∪e+∪

N不一致的e+便可。該策略可進一步提高算法的性能[17]。

3 實證研究

為驗證方法的有效性，本節分別以相關論文中經常使用的兩個實驗本體為例，闡述啟發式簡潔根辨解法在計算與需求不符的最小沖突集以及可能解決方案中的具體步驟和方法。

圖3 實驗本體O1和O2的縮略圖

3.1 實驗過程

先初始化O，B，P，N，檢測B∪P∪N的一致性。實驗本體的相關參數見表3。

表3 實驗本體及其在不一致診斷過程中的相關參數

步驟1：將O按照π(Osplit)轉化規則進行結構轉化。基于轉化后本體O′探測反模式，獲取不依賴其他沖突的根本性沖突集pdcs。

O1和O2都有反模式：同一概念同一屬性上??沖突，且都隨著分類關系進一步衍化。

就O1而言，其具體表現是〈A3

A4，A4

?s.F，A3

A5，A5

?s.

F〉，這是造成A3?⊥的原因。換句話說，以A3為起點，得出相互矛盾的結論{A3

?s.F，A3

?s.

F}。A1是A3的子類，受A3影響，A1也是不可滿足的，但造成A1?⊥的真正原因有2個：〈A1

A3，A3

A4，A4

?s.F，A3

A5，A5

?s.

F〉和〈A1

A2，A2

A4，A4

?s.F，A1

A3，A3

A5，A5

?s.

F〉。前者是A3?⊥辨解的真超集(或者說A1到沖突概念對F和

F的路徑有交集A1

A3)，只要解決A3?⊥，該辨解自然就不存在。不是根本性原因，因而直接被排除；后者改變A1到F的路徑，不是從A3

A4再到F，而是從A2

A4再到F，這是經結構轉化后才能發現的被屏蔽辨解。在原本體中，其對應的公理集合是〈ax1，ax2，ax3，ax4，ax5〉，被A3?⊥的常規辨解〈ax3，ax4，ax5〉所歸并。經結構轉化、排除無關元素后，該沖突與A3?⊥的簡潔辨解〈A3

A4，A4

?s.F，A3

A5，A5

?s.

F〉已不存在包含關系，因而不會被歸并(如刪除A3

A4后，A3?⊥消失，但該沖突仍然存在)，作為新發現根本性沖突加入pdcs。綜上，實驗本體O1的UC有2個，造成其不可滿足的根本原因有2個，最終存入pdcs的結果有2個。

就O2而言，其具體表現是〈A2

?s.M3，A2

?s.M2，M2

C，C?M3〉，這是造成A2?⊥的根本原因。A1是A2的子類，受A1影響，A1也是不可滿足的，造成A1?⊥的原因有1個〈A1

A2，A2

?s.M3，A2

?s.M2，M2

C，C?M3〉，是A2?⊥辨解的真超集。只要解決A2?⊥，A1?⊥自然就不存在。不是根本性原因，因而直接被排除。需要注意的是，A1到M3還有另外2條路徑，如先到M2然后由M2經C到M3，或者先到M1然后由M1經B到M3，但這2條路徑在性質上不同于先到A2然后由A2經M2和C到M3，前者建立的是子類關系A1

M3，后者建立的是屬性約束A1

?s.M3，只有屬性約束才能與反模式匹配。添加背景知識后，這種差別將被實例斷言掩蓋。不管是子類關系還是屬性關系，只要使得沖突斷言對{M3(w)，

M3(w)}同時存在，便是與需求不符的最小沖突集。因此只有在添加實例斷言的條件下，這2條路徑才能作為根本性原因加入簡潔根辨解中，詳情請看步驟3。綜上，實驗本體O2的不可滿足概念有2個，但造成其不可滿足的根本原因卻只有1個，因此最終只返回1個結果〈A2

?s.M3，A2

?s.M2，M2

C，C?M3〉存入pdcs。

步驟2：得到O′和pdcs后，預處理過程結束。需求是動態添加的，與需求不符的沖突相對復雜，沒有固定的模式，因而不能用啟發式規則，必須調用推理機、用quickXplain算法來計算。具體來說，就是以O′為處理對象，以B∪P∪

N為判定條件，用pdcs初始化最小沖突集Conf，用quickXplain計算單個根辨解，應用路徑提前封閉和節點重用技術，構建并擴展HStree，獲取簡潔根辨解CS及最小診斷D。

O1、O2在結構轉化、反模式探測及調用HStree方法計算簡潔根辨解步驟中的結果見表4：

表4 實驗本體在結構轉化、反模式探測及計算簡潔根辨解步驟中的計算結果

就O1而言，添加背景知識B={A1(u)，A6(w)，s(u，w)}后，調用HStree方法計算與需求不符的最小沖突集，也就是非合法蘊含式{A1?⊥，A3?⊥，C(w)，F(v)}的簡潔根辨解。結果共4個，其中{A3?⊥}的1個、C(w)的1個、F(v)的2個。需要注意的是，反模式探測結果原本有2個，但其中之一{A1?⊥}的簡潔辨解〈A1

A2，A2

A4，A4

?s.F，A1

A3，A3

A5，A5

?s.F〉被F(v)的簡潔根辨解〈A1

A2，A2

A4，A4

?s.F〉所歸并。在路徑提前封閉和節點重用技術的幫助下，用這4個最小沖突集共生成6個最小診斷。除表中列出的2個外，還有另外4個{〈ax1.2，ax3.1〉，〈ax2.2，ax3.1〉，〈ax1.2，ax1.3〉，〈ax2.2，ax1.3〉}。

就O2而言，添加背景知識B={A1(u)，A1(w)，s(u，w)}后，調用HStree方法計算與需求不符的最小沖突集，也就是非合法蘊含式{A1?⊥，A2?⊥，{A(w)，

A(w)}，{M3(w)，

M3(w)}}的簡潔根辨解。結果共4個，其中{A2?⊥}的1個，{A(w)，

A(w)}的1個、{M3(w)，

M3(w)}的2個。造成{M3(w)，

M3(w)}的原因原本有3個：其中1個是〈A1

A2，A2

?s.M3，A2

?s.M2，M2

C，C?M3〉，另2個是〈A1

A2，A2

?s.M3，A2

?s.M2，M2

C，C?M3〉和〈A1

A2，A2

?s.M3，A1

M1，M1

B，B?M3〉。前者被A2?⊥的簡潔辨解歸并；后兩種改變A1到M3的路徑，不是先由A1

A2得A2(u)、然后從A2

?s.M2得M2(w)、再由M2經C推出M3(w)，而是先由A1

M2得M2(w)、再由M2經C推出M3(w)；或者從由A1

M1得M1(w)、再由M1經B推出M3(w)，A1到沖突概念對M3(w)和

M3(w)的路徑無交集，不依賴任何其他沖突，都是根本性原因，因而都加入最終結果。

需注意的是，〈A1

A2，A2

A4，A4

?s.F，A1

A3，A3

A5，A5

?s.

F3〉是經結構轉化后才發現的辨解。在原本體中，其對應的常規辨解是〈ax1，ax2，ax4，ax5〉，不僅與A1?⊥的常規辨解完全相同，還會被A2?⊥的常規辨解〈ax2，ax4，ax5〉所歸并，因此{M3(w)，

M3(w)}的根辨解只有1個。經結構轉化、排除無關元素后，該沖突與〈ax2，ax4，ax5〉所對應的簡潔根辨解〈A2

?s.M3，A2

?s.M2，M2

C，C

M3〉已不存在包含關系，因而不會被歸并(如刪除A2

?s.M2后，前一個沖突消失，但該沖突仍然存在)，{M3(w)，

M3(w)}的根辨解數由1變為2。在路徑提前封閉和節點重用技術的支持下，用這4個最小沖突集共生成30個最小診斷。

表5 實驗本體中各類辨解及最小診斷的構成

參考表5，實驗本體O1中各類辨解的分布情況以及簡潔根辨解示意圖如圖4所示：A1?⊥有2個不簡潔辨解，但都被A3?⊥歸并，有1個也可以被F(v)的辨解歸并，因此根辨解和簡潔根辨解都變為0；A3?⊥和C(w)各有1個不簡潔根辨解。結構轉化后，各生成1個簡潔根辨解；F(v)有2個不簡潔根辨解。結構轉化后，生成2個簡潔根辨解。

參考表5，實驗本體O2中各類辨解的分布情況以及簡潔根辨解示意圖如下圖所示：A1?⊥有1個不簡潔辨解，但被A2?⊥歸并，因此根辨解和簡潔根辨解都變為0；A2?⊥和{A(w)，

A(w)}各有1個不簡潔根辨解。結構轉化后，各生成1個簡潔根辨解；{M3(w)，

M3(w)}有2個常規辨解，其中1個被A2?⊥歸并，只剩下1個根辨解。結構轉化后，生成3個簡潔辨解，真正能被A2?⊥簡潔根辨解歸并的只有1個，因此最終簡潔根辨解數為2。

圖4 實驗本體O1中各類辨解的分布情況以及簡潔根辨解示意圖

圖5 實驗本體O2中各類辨解的分布情況以及簡潔根辨解示意圖

需要注意的是，在{M3(w)，

M3(w)}的2個常規辨解中，被A2?⊥歸并的恰恰也是A1?⊥的常規辨解，因此常規辨解總數是4，并不是5；同理，在{M3(w)，

M3(w)}的3個簡潔辨解中，被A2?⊥歸并的恰恰也是A1?⊥的簡潔辨解，因此簡潔辨解總數是5，并不是6。

3.2 結果分析

從歸并和屏蔽的關系看，屏蔽就是錯誤的歸并。兩辨解的公理雖然相同或存在包含關系，但真正用于推理的元素卻不同。若基于原本體中復雜公理直接求根辨解，這種差異就會被掩蓋，原本不能被歸并的辨解就會錯誤的被歸并(如實驗本體O1中A1的辨解)；歸并就是有意的屏蔽，根據依賴關系，把本質上相同的辨解都歸結為一個關鍵性沖突，減少處理問題的數量，以提高效率、集中力量解決主要矛盾(如結構轉化后，上述A1的辨解雖然不再錯誤的被A2屏蔽，但最終又被F(v)的辨解所歸并)。

結構轉化可以識別被屏蔽辨解。同一個蘊含式的不同辨解間可能有屏蔽，不同蘊含式的辨解間也可能有屏蔽。公理間的關聯關系是錯綜復雜的，與蘊含式的作用關系也是復雜的，只有通過結構轉化，把相關的復雜公理都分解為原子公理，把所有的嵌套的語義都解析出來，才能明確這種相互作用關系，避免任何可能的屏蔽。

結構轉化是否會影響歸并辨解數并不清晰，有待進一步研究。但可以肯定，這7類辨解的數量關系應滿足表6。

表6 7類辨解的數量關系表

將上述實驗結果匯總，將簡潔根辨解數分別與其他辨解數對比，可得組圖6。由圖中數量變化關系可以看出，實驗結果與上表完全吻合，這間接表明啟發式簡潔根辨解法在揭示根本性沖突上的準確性。

綜上，簡潔根辨解不同于簡潔辨解，也不同于根辨解，更不同于常規辨解。大部分情況下，簡潔根辨解數都小于常規辨解數。僅在每個不可滿足概念都有獨立辨解、或存在被屏蔽辨解時，簡潔根辨解數才會大于常規辨解數。只要常規辨解數與簡潔辨解數不等(通常是小于)，就說明有屏蔽，存在其他被掩蓋的沖突原因；只要常規辨解數與根辨解數不等(通常是大于)，就說明辨解間有依賴關系，真正需要處理的沖突原因要少一些。而簡潔根辨解數則是找出屏蔽、歸并衍生性沖突之后的結果，大部分情況下都小于常規辨解數。僅在有不能被歸并的屏蔽辨解時，簡潔根辨解數才可能大于常規辨解數。

圖6 實驗對象各類辨解對比圖

3.3 與其他工具的對比

為驗證方法在準確性上的優勢，下文以實驗本體O1為例，分別用SWOOP(常規辨解法)[18]、Protege and Debugger(根辨解法)[19]、ORE(簡潔辨解法)[20]、啟發式簡潔根辨解法對其進行診斷，并對比分析其結果。

常規辨解法：以N={A1

⊥，A3

⊥，C(w)，F(v)}為非合法蘊含式集合，用傳統方法計算辨解及診斷的過程較復雜，具體過程如下：先識別根不可滿足概念A3，計算一個MUPS作為根節點構建HStree，計算其他最小沖突集CS1(如〈ax3，ax4，ax5〉)和最小診斷D1(如{〈ax3〉，〈ax4〉，〈ax5〉})。然后分別刪除不同的d1，得到連貫本體集Ot1。將Ot1與需求2合并，識別沖突，構建HStree，計算最小沖突集CS2(如{〈ax4〉，〈ax6〉})和最小診斷D2(如〈ax4〉或〈ax6〉，〈ax4〉也是第一棵樹的診斷，刪除〈ax4〉后需求2是滿足的，此時不會增加新的診斷。但刪除其他兩個診斷〈ax3〉或〈ax5〉后需求2不滿足，算法會重新計算出〈ax6〉和〈ax4〉)。然后分別刪除不同的d2，得到滿足前兩個需求的候選本體集Ot2。依次類推，最后得到與需求3不符的最小沖突集CS3(如〈ax1，ax2，ax4〉，〈ax1，ax3，ax4〉)和消除沖突所需的最小診斷D3(如〈ax1〉，〈ax4〉或〈ax2，ax3〉)。將D1，D2，D3組合，才能得到最終的4個診斷。總的來說，傳統方法一次只能選擇1個RUC計算其辨解。當RUC較多時，前后需要構建多棵HStree才能計算出所有辨解。將這些辨解按照包含關系歸并，才能得到N的根辨解，但并不保證簡潔性。計算最小診斷隨著計算辨解而完成，且是逐步累積的，需要分別將每顆樹中的最小診斷組合才能得到一次消除所有N的最小診斷。這個最小診斷并非并非最小，還可能包含與沖突無關的元素。傳統診斷法并不一定能求出簡潔根辨解。

根辨解法：如圖7所示，以N={A1?⊥，A3?⊥，C(w)，F(v)}為非合法蘊含式集合，用根辨解法只需一棵HStree樹便可計算4個最小沖突集和4個最小診斷。雖然考慮多個需求，效率相對較高，但不考慮辨解和最小診斷的簡潔性，會誤刪與沖突無關的元素。比如，就診斷〈ax1，ax3，ax6〉而言，刪除〈ax1.2，ax3.1，ax6.1〉就可以達到滿足所有需求的目的，〈ax1.3，ax3.2，ax6.2〉都是可以保留的，這便是簡潔根辨解法相對于根辨解法的優勢所在。

簡潔辨解法：以N={A1

⊥，A3

⊥，C(w)，F(v)}為非合法蘊含式集合，與傳統方法類似，雖然能排除冗余、避免屏蔽，但一次只處理一個需求，需要分別針對每個非合法

圖7 用根辨解法處理實驗本體O1示意圖

蘊含式計算其所有簡潔辨解，然后將這些辨解按照包含關系歸并，才能最終得到N的簡潔根辨解。計算最小診斷隨著計算辨解而完成，需要構建多顆HStree并將中間結果組合，才能得到能一次消除所有N的最小診斷。其繁瑣和復雜程度非普通用戶所能容忍。

簡潔根辨解法：如圖8所示，以N={A1

⊥，A3

⊥，C(w)，F(v)}為非合法蘊含式集合，用簡潔根辨解法，先探測到一個根本性反模式實例〈ax3.1，ax3.2，ax4.1，ax5〉，以其為根節點構建并擴展HStee，得到其它3個最小沖突集和14個最小診斷，其中最小基數診斷有2個。傳統方法和根辨解法都只能得出〈ax4〉1個最小基數診斷，但簡潔根辨解法可以得到2個，多出一種診斷方案來，用戶可根據自身要求決定留4.2(A4?C)還是6.2(A6?D)。最小診斷數量雖然較多，但都是細簡潔性的，不牽連與沖突無關的元素。

圖8 用簡潔根辨解法處理實驗本體O1示意圖

將上述實驗結果匯總，可得表7。由表中對比可以看出，就復雜本體的非合法蘊含式集合S而言，常規辨解法和根辨解法并不一定能求出其簡潔根辨解，簡潔辨解法雖然能最終求出簡潔根辨解、但需多輪迭代并將中間結果組合，過程太過繁瑣，不具有可行性，只有本文提出啟發式簡潔根辨解法能求出所有的簡潔根辨解。

表7 不同診斷方法特點及其在處理實驗本體O1中的表現

表7(續)

4 結 論

為計算復雜應用本體中的非合法蘊含式集合的根本性沖突原因，本文將原本相互孤立、分別用于反模式法、根辨解法和簡潔辨解法的核心技術：啟發式規則、批量一致性檢測、結構轉化有機組合，提出簡潔根辨解的概念(與根本性沖突原因存在一一對應關系)以及能計算該類辨解的啟發式簡潔根辨解法，闡述其基本思路與流程，探討其實現方法。在此基礎上，用相關文獻中經常使用的本體為例驗證方法的可行性與有效性，分析簡潔根辨解與其他類辨解間的區別與聯系，并將啟發式簡潔根辨解法與其他診斷方法進行對比，分析結果的準確性，分析其對最小診斷數的影響。實踐證明，這種在組合原有方法基礎上得到的啟發式簡潔根辨解法可以完成任務一，不管本體自身是否簡潔、不管需求有幾類，都可以找到根本性最小沖突集，同時保證辨解的完備性、簡潔性和準確性，為后續篩選目標診斷奠定良好基礎。

[1]SchlobachS,Huang Z.Inconsistent ontology diagnosis:Framework and prototype[J].Deliverable D3.6.1,SEKT，2005:15-25.

[2]Ji Q,Gao Z,Huang Z,et al.An efficient approach to debugging ontologies based on patterns[M].The Semantic Web.Springer Berlin Heidelberg,2012:425-433.

[3]Wang H.,Horridge M.,Rector A.L.,etal.Debugging OWL-DL Ontologies:A Heuristic Approach[M].In:Gil Y.,Motta E.,BenjaminsV.R.,et al.ISWC 2005,LNCS 3729,Springer,Heidelberg,2005:745-757.

[4]Lam S C J,Sleeman D,Vasconcelos W.Graph-Based Ontology Checking.In Proceedings KCAP05 workshop on Ontology Management: Searching,Selection,Ranking and Segmentation,Banff,Canada,2005:33-40.

[5]Roussey C,Corcho O,Vilches-Blázquez L M.A catalogue of OWL ontology antipatterns[C].∥Proceedings of the fifth international conference on Knowledge capture.ACM,2009:205-206.

[6]Meyer T,Moodley K,Varzinczak I.First steps in the computation of root justifications[C].∥Proceedings of ARCOE 2010.

[7]Lam S C,Pan J Z,Sleeman D,et al.A fine-grained approach to resolving unsatisfiable ontologies[C].∥Proceedings of Web Intelligence,2006.WI 2006.IEEE/WIC/ACM International Conference on.IEEE,2006:428-434.

[8]HorridgeM,ParsiaB,SattlerU.Laconic and precise justifications in OWL[C].∥Proceedings of the 7th International Semantic Web Conference(ISWC-2008),LNCS,Springer-Verlag,2008，(5318):323-338.

[9]HorridgeM.Justification based explanation in ontologies[D].the University of Manchester,2011:140-193．

[10]Kalyanpur A,Parsia B,Grau B C,et al.Justifications for entailments in expressive description logics[R].Technical report,University of Maryland Institute for Advanced Computer Studies(UMIACS),2006.

[11]SchlobachS,Cornet R.Non-standard reasoning services for the debugging of description logic terminologies[C].∥Proceedings of the 18th International Joint Conference on Artificial Intelligence(IJCAI-2003),2003:355-360.

[12]Horridge M,Parsia B,Sattler U.Explaining inconsistencies in OWL ontologies[M].Scalable Uncertainty Management.Springer Berlin Heidelberg,2009:124-137．

[3]Horridge M,Parsia B,Sattler U.Justification Masking in Ontologies[C].∥Proceedings of Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning，2012.

[14]Kalyanpur A,Parsia B,Sirin E,et al.Debugging unsatisfiable classes in OWL ontologies[J].Web Semantics:Science,Services and Agents on the World Wide Web,2005,3(4):268-293.

[5]Junker U.QUICKXPLAIN:preferred explanations and relaxations for over-constrained problems[C].∥Proceedings of the National Conference on Artificial Intelligence.Menlo Park,CA;Cambridge,MA;London;AAAI Press;MIT Press;1999,2004:167-172.

[16]Shchekotykhin K,Friedrich G,Jannach D.On computing minimal conflicts for ontology debugging[J].Model-Based Systems,2008，(7):7-12.

[17]Shchekotykhin K.,Friedrich G.,Fleiss P.,et al.Interactive ontology debugging:two query strategies for efficient fault localization[J].Web Semantics:Science,Services and Agents on the World Wide Web,2012，(12-13):88-103.

[18]KalyanpurA,ParsiaB,SirinE,etal.Swoop:A web ontology editing browser[J].Web Semantics:Science,Services and Agents on the World Wide Web,2006,4(2):144-153.Springer,Heidelberg,2005:745-757.

[19]ProtegeAndDebugger[EB/OL].http:∥code.google.com/p/rmbd/，2012-12-20.

[20]Lehmann J,Bühmann L.ORE-a tool for repairing and enriching knowledge bases[M].The Semantic Web-ISWC 2010.Springer Berlin Heidelberg,2010:177-193.

(本文責任編輯：孫國雷)

The Research on Requirements-oriented Ontology Inconsistent Diagnosis Method

Song Danhui

(Library，Henan University of Science and Technology，Luoyang 471003，China)

Firstly,the article teased out the existing Inconsistent Diagnosis methods systematically,and then analyzed the existing problems and inadequacies,combining with the characteristics of application ontology and its requirements,and explored new research idea and method to combine and optimize the core algorithms of anti-pattern detection,root justifications,laconic justifications algorithms respectively,which were isolated Originally and applied in different diagnostic tools respectively.Based on this,the paper not only put forward a comprehensive diagnosis method which is called heuristic Laconic Root Justifications,but also pointed out the basic ideas and concrete steps,and put two frequently used experimental ontologies in related study as examples,in order to validate the effectiveness of the method.

application ontology;inconsistent diagnosis;laconic justifications;root justifications;anti-pattern detection

2015-10-20

2013年國家社會科學基金青年項目“數字圖書館用戶數據資源化管理研究”(項目編號：13CTQ012)研究成果之一。

宋丹輝(1983-)，女，館員，研究方向：知識組織，數字圖書館理論與實踐。

10．3969/j．issn．1008-0821．2016．03．005

G254.29

A

1008-0821(2016)03-0027-11