本體中ｉｓ－ａ層次的構建與本體集成
2008-12-31 00:00:00張忠平趙海亮何麗榮
計算機應用研究 2008年11期
(燕山大學 信息科學與工程學院 計算機科學與技術系，河北 秦皇島 066004)
摘要：首先給出了本體中is-a層次的構建方法，并提出了is-a層次中刪除概念的算法；其次，分析了本體集成的原因，給出了本體集成的分類、三種集成方式和四條集成原則；最后，提出一種基于OWL (Web ontology language)的本體集成算法，實驗證明此算法可行。
關鍵詞：本體； is-a層次； 概念； 構建； 集成
中圖分類號：TP311文獻標志碼：A
文章編號：1001-3695(2008)11-3249-04
Constructing is-a hierarchy for ontology and ontology integration
ZHANG Zhong-ping， ZHAO Hai-liang， HE Li-rong
(Dept. of Computer Science Technology， College of Information Science Engineering， Yanshan University， Qinhuangdao Hebei 066004， China)
Abstract:Firstly， this paper proposed method for constructing the is-a hierarchy， and gave the algorithm for deleting concepts in is-a hierarchy. Secondly， after analyzing the reasons of ontology integration， it gave up the classifications and presented three modes and four rules. At last， based on OWL， presented an algorithm for ontology integration. Experiment shows this method is feasible.
Key words：ontology; is-a hierarchy; concept; construct; integrate
現實中許多應用需要對不同的相關數據源進行聯合操作，而這些數據源一般具有半結構化、異構性和分布性等特點。本體對于異構的、面向計算機的海量信息處理起著舉足輕重的作用。本體可以描述概念的含義，又可以描述概念之間的關系，具有很強的表達概念語義和獲取知識的能力，能通過邏輯推理獲取概念之間的蘊涵關系。本體在語義層次上描述了領域知識，這不僅使人可以理解，而且機器也可自動處理。因此，人們很自然地想到利用本體來實現異構數據源的互聯。本體在知識表示、數據共享、信息檢索、數字圖書館、電子商務等方面有著廣泛的應用。所以，對不同領域內的知識進行抽取和描述，并構建出合適的領域本體是本體研究的熱點之一。
隨著應用領域的不斷擴大和本體描述語言的發展，本體的數量和規模在不斷增大，加上日益增加的對跨專業、跨領域異構信息交換的迫切需要，決定了本體集成研究的必要性。
1本體的概念
Studer等人[1]對上述定義進行了深入的研究，他們認為本體是共享概念模型的明確的形式化規范說明，這個定義在業界得到普遍認可。從本體的內涵上看，本體是某個領域內不同主體之間交流的一種語義基礎，即本體提供一種明確定義的共識。本體的目標就是獲取相關領域知識，提供對該領域知識的共同理解，確定該領域內共同認可的詞匯，并從不同層次的形式化模式上給出這些詞匯和詞匯之間的相互關系的明確定義。
本體的形式化定義可以是五元組，也可以是七元組[2]，其形式為O=(C，AC，R，AR，H，I，X)。其中：C是概念的集合；AC是概念屬性的集合；R是關系的集合；AR是關系屬性的集合；H表示層次的集合；I是實例的集合；X是公理的集合。
2本體中的is-a層次
21is-a層次的構建
is-a關系是本體中概念之間的核心關系，用來組織概念。概念之間有三類關系，即概念包含、概念相交和概念獨立[3]。兩個概念之間具有包含關系，在is-a層次中表現為概念上下層間的父子關系；兩個概念具有相交關系，在is-a層次中表現為概念的同層間的兄弟關系；兩個概念相互獨立，在is-a層次中無直接聯系。
文獻[4]研究了從關系數據庫中抽取is-a關系。本文引入關系理論中的約束來構建is-a層次。關系理論中有三種約束：a)排斥約束，一個關系中兩個屬性x和y的排斥約束記為x/ y，表示x和y不可同時出現。b)共存約束，記為xy，表示x出現時，y也出現；反之也成立。c)條件約束，記為x|→y，表示x出現時，y也出現；反之不成立，即x的作用領域包含于y的作用領域中。
從實例中抽取關鍵字之間的存在約束，利用關鍵字間的存在約束來構建is-a層次。假設有四個關鍵字K1、K2、K3和K4，七個實例I1、I2、I3、I4、I5、I6和I7，這七個實例具有的關鍵字情況為：a)I1具有K1、K2和K3；b)I2具有K1和K2；c)I3具有K1、K2；d)I4具有K1、K2和K4；e)I5具有K1、K2和K3；f)I6具有K1、K2和K3；g)I7具有K1、K2和K4。由此可以將這組實例分成三類。第一類實例：只有K1和K2作為關鍵字的實例I2和I3；第二類實例：只有K1、K2和K3作為關鍵字的實例I1、I5和I6；第三類實例：只有K1、K2和K4作為關鍵字的實例I4 和I7。用布爾代數表示這三類實例：
K1K2K3K4+K1K2K3K4+K1K2K3K4=1
解此布爾等式，得K1=1，K2=1，K3K4=0。說明關鍵字K1和K2是每個實例的屬性，K1和K2之間存在共存約束，即K1 K2；關鍵字K3和K4，每個實例只能具有其一，K3和K4之間存在互斥約束，即K3/ K4；當一個實例具有K3或K4時，一定具有K1和K2，即K3|→K1，K3|→K2，K4|→K1，K4|→K2。令C1表示具有K1和K2關鍵字的概念(類)，用C2表示具有關鍵字K3的概念；用C3表示具有關鍵字K4的概念，則構建的is-a層次如圖1所示。
22is-a層次中概念的刪除
可以刪除本體is-a層次中的概念，考慮兩種策略：a)只刪除要刪的概念本身，其直接子概念(如果有的話)鏈接到此刪除概念的直接父概念上。b)刪除概念和只屬于此概念的所有子孫概念，斷開的鏈接與此刪除概念的直接父概念相連，如圖2所示。算法如算法1所示。
算法1刪除概念算法
輸入：初始概念層次H，初始的概念集C，待刪除的概念集C1
輸出：刪除概念后的層次H′
compute A1，D1; //A1和D1為C1中概念
//直接父概念的集合和所有子概念的集合
if select strategy1 for deleting then
For c∈C1 do
For each direct descendant d of c if exist do
For each direct ascendant a of c if exist do
Create the inheritance link from d to a;
End For
End For
End For
Delete all the concepts of C1;
End if
if select strategy2 for deleting then
C2=C-C1-A1-D1;
compute D2; //D2為C2所有子概念的集合
C1=C1+D1-D2;
For c∈C1 do
For each direct descendant d of c if exist do
For each direct ascendant a of c if exist do
Create the inheritance link from d to a;
End for
End for
End for
Delete all the concepts of C1;
End if
3本體集成
31本體集成的原因
本體之所以要進行集成，首先是因為本體之間存在異構。這些異構包括結構上的異構和語義上的異構兩部分。本體結構上的異構主要是概念異構。在進行概念化描述時，概念表示的粒度差異和覆蓋度不同，概念的范圍值域不同，概念的建模形式和表示形式也不同。本體間異構的另一個方面主要是語義異構，造成語義異構的原因主要是：a)不同的本體使用多種術語表示同一概念；b)同一概念在不同本體中表達不同的含義；c)各種本體使用不同的結構表示相同或相似的信息；d)各本體中的概念之間存在著各種關聯，但由于本體的分布自治性，這種關聯一般是隱含的；e)不同本體使用不同的開發語言和系統。
本體集成是因為在構建本體時也要用到集成技術，尤其是大型本體。在構建大型本體時通常需要多個人多個團體的協作，其中每個參與者的本體涵蓋領域的各個部分，而滿足需求的本體通常要由這幾個獨立開發的本體模塊組合而成，這就需要本體集成技術。
32本體集成的分類
廣義上所說的本體集成，即本體融合（ontology reconciliation)。它是把多個本體匯集在一起使用，這是一個很大的題目，因為它涉及到許多不同的情況。Adil等人在文獻[5]中將本體融合技術分成本體合并、本體串聯、本體集成三類。文獻[6]中按照本體集成程度的不同，將本體集成分為本體映射(ontology mapping)、本體結盟(ontology alignment)和本體合并(ontology merging)。這三種形式的集成程度依次增強，體現了從松散集成、封裝集成到緊密集成的過渡。
本文所說的本體集成是狹義上的本體集成，即ontology integrating，它可以有三種形式，如圖3所示。這里，假設源本體A的a3與源本體B的b3之間有直接聯系。
a)簡單集成。新生的目標本體C包含初始的源本體A和B，初始本體部分或完全保持其內部結構，但失去自治性，而且一旦形成目標的本體，新的信息源本體很難再添加進去，不易擴充，每個源本體的修改會影響到目標本體。
b)選擇集成。新生成的目標本體C包含所需的部分初始本體，初始本體A和B保持其內部結構完整性和自治性。優點是新的本體容易添加進去，每個源本體的修改不會影響彼此，也不會影響目標本體；缺點是合適的所需部分很難確定。
c)擴展集成。就是要擴展初始本體之一A，使其包括所需的其他初始本體B的一部分，A即為目標本體，初始本體A部分保持內部結構和自治性，本體B完全保持其內部結構和自治性。擴展集成優缺點介于簡單集成和選擇集成之間。
另一種解決本體異構的方法是本體映射，即尋求不同本體間的映射規則，在不同本體的概念和關系間建立連接。這些連接可以將不同本體間的概念或關系進行對應，而各個源本體本身并不改變。本體集成和本體映射之間既有差別又有聯系。一方面，在本體集成過程中，映射可以看做是集成的子過程，在本體集成的過程中需要分析不同本體間的映射；另一方面，建立映射后的多本體可以看做是一種虛擬的本體集成。
33本體集成的原則
通過對已有的本體集成項目進行研究，本體集成應該遵循以下四條基本原則：
a)完備性原則。主要指數據(語義)完備性和約束(關聯)完備性，待集成本體中如果有數據(語義)符合本體應用需求，則該語義一定要在目標本體中體現；如果所需求的語義之間有約束(關聯)，則該約束也一定要出現在目標本體中。
b)本體進化原則。本體的集成是一個動態過程，集成后形成的本體一定要具有可復用性，具備二次開發的空間和能力。源本體變化后，可能導致整個系統語義上的不一致，功能上發生錯誤，因此，集成后的本體要能隨著源本體的變化進行不斷更新。
c)覆蓋度和粒度兼顧的原則。覆蓋度是指本體對領域的覆蓋程度，粒度是指領域本體對領域知識的細化程度。本體的集成不但要求廣(覆蓋度)而且要求深(粒度)，要兩者兼顧。
d)實用性的原則。本體的集成是個異常復雜的過程，到目前為止，國外所進行的一些本體集成的嘗試都需要大量的人工參與。因此，所謂實用性原則就是一方面要盡量減少人的工作量；另一方面要考慮集成的復雜程度，如果將多個本體集成比重新構建一個新本體還要復雜，那就無所謂集成了。
34基于OWL DL閉包的本體集成方法
文獻[7]提出一種新的本體集成方法ILIADS(integrated learning in alignment of data and schema)；文獻[8]基于默認的分布式描述邏輯，提出了一個本體集成的架構；文獻[9]中利用字典技術對同義詞進行識別，并使用啟發式規則計算本體中實體間的相似度，開發了一個半自動化的本體集成系統。文獻[10]研究了從多個本體中抽取子本體，此思想也可用于本體集成。
341OWL DL本體圖閉包
通過對OWL DL本體的研究，本文提出了一種基于其圖閉包的本體集成算法OIODC (ontology integration based OWL DL closure)。
定義1OWL DL本體。它表示為五元組O=(C， I， P， A， F)。其中：C表示類(class)的集合；I表示實例(individual)的集合；P表示屬性(property)的集合，屬性表示實例與實例、或實例與數據值之間的二元關系；A是公理(axiom)的集合；F是事實(fact)的集合。公理A和事實F統稱為本體O的三元組集T(triples)；類C、實例I和屬性P統稱為本體O的實體集(entities)；而三元組集包含的三元組數目，稱為本體O的大小，記為|O|。
定義2OWL DL本體圖閉包。OWL DL本體圖G中所有顯示的和隱含的三元組的集合，稱為OWL DL本體圖G的閉包，記為C(G)。
OWL DL本體圖閉包包含更多的領域知識。OWL DL本體圖閉包的算法：循環地應用OWL DL的推理規則，如果有聲明滿足這些規則中的某一條，則生成新的聲明，將新的聲明添加到原有聲明中，直到所有聲明都不滿足推理規則的觸發條件，停止循環。這時所有聲明組成了OWL DL的本體圖閉包。如圖4所示，實線為原來的OWL DL本體聲明；虛線為新生成的聲明，一起構成OWL DL本體的圖閉包。
342算法描述
OIODC算法（算法2）的基本流程如圖5所示。相似度計算采用編輯距離，同時考慮結構、實例和屬性。限于篇幅，不再詳述。本體剪枝中，所謂虛擬本體OV是已經建立了映射聯系，但還沒有對源本體中沒有用到的類、實例、關系等進行刪除操作。
算法2基于OWL DL的本體集成算法(OIODC)
輸入：初始本體O1，O2(僅考慮兩個本體的集成)
輸出：集成后的本體O
C= C1∪C2 ;I= I1∪I2 ;P= P1∪P2 ;A= A1∪A2 ; F=F1∪F2;
Parse O1， O2 to triples: T1 and T2 and filter them;
Compute the closures of O1 and O2;
repeat
Compute each similarity for classes， properties and instances between O1 and O2;
If similarity ≥λ then clustering as C′， P′ or I′;
Endif
until no more candidate
repeat
get (p1 ， p2) form C′， P′ or I′ in parallel;
determine equivalence or subsumption relation between p1 and p2 ， expressing as a axiom Aint(p1，p2);
inference with Aint(p1，p2) in parallel;
If a pair ofx，y ∈I′ with equivalence relation was inferenced
Then {add Aint(p1，p2) to A;
recomputed similarity(p1，p2);}
else If there is an inconsistency was inferenced
then continue; Endif
until no more candidate
Do pruning to O;
return O;
343實驗評估
針對本算法進行對比實驗。機器采用P4 3.0 GHz臺式機，1 GB內存，Windows操作系統。從網上的本體庫尋找20對本體，先用人工方式對這些本體進行集成，集成的結果作為評價標準。將本文介紹的本體集成方法OIODC與COMA++[11]和FCA-merge[12]進行比較。用A*表示人工集成得到的公理集，用A表示用集成方法生成的公理集，查準率P(precision)和查全率R(recall)定義為
P=｜A*∩A｜/｜A｜，R=｜A*∩A｜/｜A*｜(1)
三種方法的實驗結果對比如圖6所示。由于OWL DL本體圖閉包包含更多的領域知識，這樣在圖閉包的基礎上進行相似度計算和推理，減少信息的丟失。可以看出本文介紹的OIODC在查準率和查全率上優于COMA++和FCA-merge。但OIODC在運行時間上相對較長，平均集成每對本體用時482 s(不含剪枝時間)，而COMA++和FCA-merge分別為228和251 s(不含人工交互時間)。OIODC時間主要耗費在閉包生成上，因此需要進一步設計好的閉包生成算法。
4結束語
本文對本體中概念的is-a層次進行了研究，提出了is-a層次的建立方法，并提出了is-a層次中概念的刪除算法。如何集成不同團體開發的不同語言和不同組織方式的本體，解決信息異構，實現信息共享，是當今的一個研究熱點。本文提出了一種基于OWL DL圖閉包的本體集成算法OIODC，實驗證明此方法可行。但本體集成是一個復雜的過程，到目前為止，仍沒有一個好的方法。因此，可以研究的空間很大。
將來的研究方向是在本體構建方面，集中在is-a層次的其他維護上，如概念的添加合并、層次的合并刪除等，進一步考慮本體中概念的其他關系，如part-of和kind-of等。在本體集成方面，尋求更好的閉包生成算法和相似度計算方法，同時研究多個本體的集成。
參考文獻：
［1］STUDER R， BENJAMINS V R， FENSEL D. Knowlegde enginee-ring: principles and methods[J].Data and Knowledge Enginee-ring，1998，25(1-2):161-197.
[2]苗壯，張亞非，陸建江.從多個RDFS本體中抽取子本體[J].情報學報，2007，26(1):71-76.
[3]CHEN Rung-ching， LIANG Jui-yuan， PAN Ren-hao. Using recursive ART network to construction domain ontology based on term frequency and inverse document frequency [J].Expert Systems with Applications: An International Journal， 2008，34(1):488-501.
[4]LAMMARI N. An algorithm to extract is_a inheritance hierarchies from a relational database Paris[C]//Proc of ER’99. 1999:218-232.
[5]ADIL H， ALUN P， DEREK S. Ontology reconciliation[EB/OL].(2007-11-10).http://www.csd.abdn.ac.uk/~sleeman/published-papers/p139.pdf.
[6]范莉婭，王愛民，肖田元.本體集成方法評價指標體系及其應用研究[J].計算機集成制造系統，2007，13(5):912-917.
[7]UDREA O， GETOOR L， MILLER R J. Leveraging data and structure in ontology integration[C]//Proc of ACM SIGMOD2007. Beijing:[s.n.]， 2007:449-460.
[8]MA Ying-long， WEI Jun， JIN Bei-hong，et al. A formal framework for ontology integration based on a default extension to DDL[C]//Proc ofTheoretical Aspects of Computing—ICTAC 2004.Guiyang:[s.n.]， 2004:154-169.
[9]魏哲雄， 馮志勇. 基于字典技術的本體整合系統[J]. 計算機應用， 2007，27(2):428-430.
[10]劉文斌， 謝強， 張磊. 多本體中子本體抽取的研究[J]. 計算機應用研究， 2006，23(3):35-37，40.
[11]AUMUELLER D， DO H H， MASSMANN S， et al. Schema and ontology matching with COMA++ [C]//Proc of ACM SIGMOD2005. Maryland:[s.n.]，2005:906-908.
[12]STUMME G， MAEDCHE A. FCA-merge:bottom-up merging of onto-logies[C]//Proc ofIJCAI2001.Seattle:[s.n.]， 2001:225-230.
