[發明專利]基于整數線性規劃的本體邏輯矛盾處理方法

在審

• 申請號: 201910280411.3
• 申請日: 2019-04-09
• 公開（公告）號: CN110069747A
• 公開（公告）日: 2019-07-30
• 發明（設計）人: 季秋;漆桂林;依曼
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F17/15
• 分類號: G06F17/15;G06F16/36
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 董建林

本發明公開一種基于整數線性規劃(Integer Linear Programming,ILP)解決本體中邏輯矛盾的方法，給出了解決邏輯矛盾的ILP模型，即通過將給定的沖突集合轉變為ILP表示，進而使用傳統的ILP求解器獲取最佳解決方案。每個方案對應一個公理集合，從本體中移除一個這樣的集合，便可解決給定的沖突。本發明首次提出一個計算基數最小解決方案的算法，使得刪除的公理盡可能少，還提出保留盡可能多權重信息的算法。本發明提出的基于ILP解決沖突的方法是一個通用的邏輯矛盾處理方法，不僅可以用于修復單個本體和本體映射，還可以用于做本體修正或本體演化。本發明通過豐富的實驗，說明了提出的算法具有非常高的效率，并且刪除的公理具有基數最小或權重和最小的性質。

技術領域

本發明屬于語義網中本體邏輯不一致處理技術領域，涉及一種從給定沖突集合中移除盡可能少公理的方法，具體為一種基于整數線性規劃的本體邏輯矛盾處理方法。

背景技術

在語義網(Semantic Web)中，本體(ontologies)作為形式化的知識表示扮演著重要的角色。由于構建本體是一個非常容易出錯的任務，并且本體總是不停地變化著，因此在本體構建、本體修正(ontology revision)、本體映射(ontology mapping)和本體演化(ontology evolution)等許多應用場景中不可避免地出現邏輯矛盾(logicalcontradictions)。一般來說，邏輯矛盾分為不一致(inconsistency)和不協調(incoherence)。如果一個本體沒有任何模型，則這個本體是不一致的；如果一個本體中存在一個解釋為空集的概念，則該本體被稱為不協調本體，該概念被稱為不可滿足概念(unsatisfiable concept)。通常情況下，不協調往往出現在本體的術語中，而給一個不協調本體添加概念或關系的實例容易導致本體變得不一致。由于對于不一致本體進行標準推理可以推導出任何結論，從而使得這些結論失去了意義，所以解決邏輯矛盾是一項既有意義又重要的任務。

在解決邏輯矛盾時，人們總是期望移除最少的公理，即解決方案應該滿足最小變化原則。為此，大部分已有方法使用Reiter的碰集樹(Hitting Set Tree，HST)算法。Schlobach等和Du等研究人員提出在最小不可滿足保持子集上應用HST算法，找出一個最小的公理集刪除，恢復本體的協調性；Du等又提出在最小不一致子集上應用HST算法來處理本體的不一致性；Kalyanpur等修改了HST算法，在碰集樹的每條邊上添加權重，以此來計算刪除代價最小的公理集。雖然這些算法可以找到用于刪除的最小公理集或權重最小的公理集，但是當碰集樹中分支較多時，基于HST的算法仍然非常耗時。

為了提高基于HST解決邏輯矛盾的方法的效率，研究者們提出一些既能減小搜索空間又能滿足某種最小變化定義的算法。例如，Qi等提出先從每個沖突中抽取一個子集，然后將HST算法應用到這些子集上，這樣大大地提高了效率。抽取子集的方法有兩種，一種是根據打分函數為沖突集中每個公理進行打分，然后從每個沖突中挑出那些打分最高的公理；另一種是根據公理的權重，從每個沖突中挑選權重最低的公理。然而，當挑選出的子集也包含較多公理時，這類方法的效率仍然是個問題，且不能保證找到的公理集對于整個本體是最小的。

為了進一步提高邏輯矛盾處理的效率，人們又提出了啟發式的方法，徹底放棄最小變化的原則。Schlobach等提出按照公理分數進行刪除，先從所有沖突集中刪除分數最高的那個公理，然后從剩下的未移除任何公理的沖突集中再刪除當前分數最高的公理，如此循環下去，直到所有沖突集中都有公理被移除。還有一些在本體學習中處理邏輯矛盾的工作，特別是迭代地學習本體，最常用的處理邏輯矛盾的方法是：對于每個新學到的公理，如果添加該公理使得原來的本體變得不一致或不協調，則直接放棄該公理。