本體中ｉｓ－ａ層次的構(gòu)建與本體集成
2008-12-31 00:00:00張忠平趙海亮何麗榮
計(jì)算機(jī)應(yīng)用研究 2008年11期
(燕山大學(xué) 信息科學(xué)與工程學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，河北 秦皇島 066004)
摘要：首先給出了本體中is-a層次的構(gòu)建方法，并提出了is-a層次中刪除概念的算法；其次，分析了本體集成的原因，給出了本體集成的分類、三種集成方式和四條集成原則；最后，提出一種基于OWL (Web ontology language)的本體集成算法，實(shí)驗(yàn)證明此算法可行。
關(guān)鍵詞：本體； is-a層次； 概念； 構(gòu)建； 集成
中圖分類號：TP311文獻(xiàn)標(biāo)志碼：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
現(xiàn)實(shí)中許多應(yīng)用需要對不同的相關(guān)數(shù)據(jù)源進(jìn)行聯(lián)合操作，而這些數(shù)據(jù)源一般具有半結(jié)構(gòu)化、異構(gòu)性和分布性等特點(diǎn)。本體對于異構(gòu)的、面向計(jì)算機(jī)的海量信息處理起著舉足輕重的作用。本體可以描述概念的含義，又可以描述概念之間的關(guān)系，具有很強(qiáng)的表達(dá)概念語義和獲取知識的能力，能通過邏輯推理獲取概念之間的蘊(yùn)涵關(guān)系。本體在語義層次上描述了領(lǐng)域知識，這不僅使人可以理解，而且機(jī)器也可自動處理。因此，人們很自然地想到利用本體來實(shí)現(xiàn)異構(gòu)數(shù)據(jù)源的互聯(lián)。本體在知識表示、數(shù)據(jù)共享、信息檢索、數(shù)字圖書館、電子商務(wù)等方面有著廣泛的應(yīng)用。所以，對不同領(lǐng)域內(nèi)的知識進(jìn)行抽取和描述，并構(gòu)建出合適的領(lǐng)域本體是本體研究的熱點(diǎn)之一。
隨著應(yīng)用領(lǐng)域的不斷擴(kuò)大和本體描述語言的發(fā)展，本體的數(shù)量和規(guī)模在不斷增大，加上日益增加的對跨專業(yè)、跨領(lǐng)域異構(gòu)信息交換的迫切需要，決定了本體集成研究的必要性。
1本體的概念
Studer等人[1]對上述定義進(jìn)行了深入的研究，他們認(rèn)為本體是共享概念模型的明確的形式化規(guī)范說明，這個定義在業(yè)界得到普遍認(rèn)可。從本體的內(nèi)涵上看，本體是某個領(lǐng)域內(nèi)不同主體之間交流的一種語義基礎(chǔ)，即本體提供一種明確定義的共識。本體的目標(biāo)就是獲取相關(guān)領(lǐng)域知識，提供對該領(lǐng)域知識的共同理解，確定該領(lǐng)域內(nèi)共同認(rèn)可的詞匯，并從不同層次的形式化模式上給出這些詞匯和詞匯之間的相互關(guān)系的明確定義。
本體的形式化定義可以是五元組，也可以是七元組[2]，其形式為O=(C，AC，R，AR，H，I，X)。其中：C是概念的集合；AC是概念屬性的集合；R是關(guān)系的集合；AR是關(guān)系屬性的集合；H表示層次的集合；I是實(shí)例的集合；X是公理的集合。
2本體中的is-a層次
21is-a層次的構(gòu)建
is-a關(guān)系是本體中概念之間的核心關(guān)系，用來組織概念。概念之間有三類關(guān)系，即概念包含、概念相交和概念獨(dú)立[3]。兩個概念之間具有包含關(guān)系，在is-a層次中表現(xiàn)為概念上下層間的父子關(guān)系；兩個概念具有相交關(guān)系，在is-a層次中表現(xiàn)為概念的同層間的兄弟關(guān)系；兩個概念相互獨(dú)立，在is-a層次中無直接聯(lián)系。
文獻(xiàn)[4]研究了從關(guān)系數(shù)據(jù)庫中抽取is-a關(guān)系。本文引入關(guān)系理論中的約束來構(gòu)建is-a層次。關(guān)系理論中有三種約束：a)排斥約束，一個關(guān)系中兩個屬性x和y的排斥約束記為x/ y，表示x和y不可同時出現(xiàn)。b)共存約束，記為xy，表示x出現(xiàn)時，y也出現(xiàn)；反之也成立。c)條件約束，記為x|→y，表示x出現(xiàn)時，y也出現(xiàn)；反之不成立，即x的作用領(lǐng)域包含于y的作用領(lǐng)域中。
從實(shí)例中抽取關(guān)鍵字之間的存在約束，利用關(guān)鍵字間的存在約束來構(gòu)建is-a層次。假設(shè)有四個關(guān)鍵字K1、K2、K3和K4，七個實(shí)例I1、I2、I3、I4、I5、I6和I7，這七個實(shí)例具有的關(guān)鍵字情況為：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。由此可以將這組實(shí)例分成三類。第一類實(shí)例：只有K1和K2作為關(guān)鍵字的實(shí)例I2和I3；第二類實(shí)例：只有K1、K2和K3作為關(guān)鍵字的實(shí)例I1、I5和I6；第三類實(shí)例：只有K1、K2和K4作為關(guān)鍵字的實(shí)例I4 和I7。用布爾代數(shù)表示這三類實(shí)例：
K1K2K3K4+K1K2K3K4+K1K2K3K4=1
解此布爾等式，得K1=1，K2=1，K3K4=0。說明關(guān)鍵字K1和K2是每個實(shí)例的屬性，K1和K2之間存在共存約束，即K1 K2；關(guān)鍵字K3和K4，每個實(shí)例只能具有其一，K3和K4之間存在互斥約束，即K3/ K4；當(dāng)一個實(shí)例具有K3或K4時，一定具有K1和K2，即K3|→K1，K3|→K2，K4|→K1，K4|→K2。令C1表示具有K1和K2關(guān)鍵字的概念(類)，用C2表示具有關(guān)鍵字K3的概念；用C3表示具有關(guān)鍵字K4的概念，則構(gòu)建的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本體集成的原因
本體之所以要進(jìn)行集成，首先是因?yàn)楸倔w之間存在異構(gòu)。這些異構(gòu)包括結(jié)構(gòu)上的異構(gòu)和語義上的異構(gòu)兩部分。本體結(jié)構(gòu)上的異構(gòu)主要是概念異構(gòu)。在進(jìn)行概念化描述時，概念表示的粒度差異和覆蓋度不同，概念的范圍值域不同，概念的建模形式和表示形式也不同。本體間異構(gòu)的另一個方面主要是語義異構(gòu)，造成語義異構(gòu)的原因主要是：a)不同的本體使用多種術(shù)語表示同一概念；b)同一概念在不同本體中表達(dá)不同的含義；c)各種本體使用不同的結(jié)構(gòu)表示相同或相似的信息；d)各本體中的概念之間存在著各種關(guān)聯(lián)，但由于本體的分布自治性，這種關(guān)聯(lián)一般是隱含的；e)不同本體使用不同的開發(fā)語言和系統(tǒng)。
本體集成是因?yàn)樵跇?gòu)建本體時也要用到集成技術(shù)，尤其是大型本體。在構(gòu)建大型本體時通常需要多個人多個團(tuán)體的協(xié)作，其中每個參與者的本體涵蓋領(lǐng)域的各個部分，而滿足需求的本體通常要由這幾個獨(dú)立開發(fā)的本體模塊組合而成，這就需要本體集成技術(shù)。
32本體集成的分類
廣義上所說的本體集成，即本體融合（ontology reconciliation)。它是把多個本體匯集在一起使用，這是一個很大的題目，因?yàn)樗婕暗皆S多不同的情況。Adil等人在文獻(xiàn)[5]中將本體融合技術(shù)分成本體合并、本體串聯(lián)、本體集成三類。文獻(xiàn)[6]中按照本體集成程度的不同，將本體集成分為本體映射(ontology mapping)、本體結(jié)盟(ontology alignment)和本體合并(ontology merging)。這三種形式的集成程度依次增強(qiáng)，體現(xiàn)了從松散集成、封裝集成到緊密集成的過渡。
本文所說的本體集成是狹義上的本體集成，即ontology integrating，它可以有三種形式，如圖3所示。這里，假設(shè)源本體A的a3與源本體B的b3之間有直接聯(lián)系。
a)簡單集成。新生的目標(biāo)本體C包含初始的源本體A和B，初始本體部分或完全保持其內(nèi)部結(jié)構(gòu)，但失去自治性，而且一旦形成目標(biāo)的本體，新的信息源本體很難再添加進(jìn)去，不易擴(kuò)充，每個源本體的修改會影響到目標(biāo)本體。
b)選擇集成。新生成的目標(biāo)本體C包含所需的部分初始本體，初始本體A和B保持其內(nèi)部結(jié)構(gòu)完整性和自治性。優(yōu)點(diǎn)是新的本體容易添加進(jìn)去，每個源本體的修改不會影響彼此，也不會影響目標(biāo)本體；缺點(diǎn)是合適的所需部分很難確定。
c)擴(kuò)展集成。就是要擴(kuò)展初始本體之一A，使其包括所需的其他初始本體B的一部分，A即為目標(biāo)本體，初始本體A部分保持內(nèi)部結(jié)構(gòu)和自治性，本體B完全保持其內(nèi)部結(jié)構(gòu)和自治性。擴(kuò)展集成優(yōu)缺點(diǎn)介于簡單集成和選擇集成之間。
另一種解決本體異構(gòu)的方法是本體映射，即尋求不同本體間的映射規(guī)則，在不同本體的概念和關(guān)系間建立連接。這些連接可以將不同本體間的概念或關(guān)系進(jìn)行對應(yīng)，而各個源本體本身并不改變。本體集成和本體映射之間既有差別又有聯(lián)系。一方面，在本體集成過程中，映射可以看做是集成的子過程，在本體集成的過程中需要分析不同本體間的映射；另一方面，建立映射后的多本體可以看做是一種虛擬的本體集成。
33本體集成的原則
通過對已有的本體集成項(xiàng)目進(jìn)行研究，本體集成應(yīng)該遵循以下四條基本原則：
a)完備性原則。主要指數(shù)據(jù)(語義)完備性和約束(關(guān)聯(lián))完備性，待集成本體中如果有數(shù)據(jù)(語義)符合本體應(yīng)用需求，則該語義一定要在目標(biāo)本體中體現(xiàn)；如果所需求的語義之間有約束(關(guān)聯(lián))，則該約束也一定要出現(xiàn)在目標(biāo)本體中。
b)本體進(jìn)化原則。本體的集成是一個動態(tài)過程，集成后形成的本體一定要具有可復(fù)用性，具備二次開發(fā)的空間和能力。源本體變化后，可能導(dǎo)致整個系統(tǒng)語義上的不一致，功能上發(fā)生錯誤，因此，集成后的本體要能隨著源本體的變化進(jìn)行不斷更新。
c)覆蓋度和粒度兼顧的原則。覆蓋度是指本體對領(lǐng)域的覆蓋程度，粒度是指領(lǐng)域本體對領(lǐng)域知識的細(xì)化程度。本體的集成不但要求廣(覆蓋度)而且要求深(粒度)，要兩者兼顧。
d)實(shí)用性的原則。本體的集成是個異常復(fù)雜的過程，到目前為止，國外所進(jìn)行的一些本體集成的嘗試都需要大量的人工參與。因此，所謂實(shí)用性原則就是一方面要盡量減少人的工作量；另一方面要考慮集成的復(fù)雜程度，如果將多個本體集成比重新構(gòu)建一個新本體還要復(fù)雜，那就無所謂集成了。
34基于OWL DL閉包的本體集成方法
文獻(xiàn)[7]提出一種新的本體集成方法ILIADS(integrated learning in alignment of data and schema)；文獻(xiàn)[8]基于默認(rèn)的分布式描述邏輯，提出了一個本體集成的架構(gòu)；文獻(xiàn)[9]中利用字典技術(shù)對同義詞進(jìn)行識別，并使用啟發(fā)式規(guī)則計(jì)算本體中實(shí)體間的相似度，開發(fā)了一個半自動化的本體集成系統(tǒng)。文獻(xiàn)[10]研究了從多個本體中抽取子本體，此思想也可用于本體集成。
341OWL DL本體圖閉包
通過對OWL DL本體的研究，本文提出了一種基于其圖閉包的本體集成算法OIODC (ontology integration based OWL DL closure)。
定義1OWL DL本體。它表示為五元組O=(C， I， P， A， F)。其中：C表示類(class)的集合；I表示實(shí)例(individual)的集合；P表示屬性(property)的集合，屬性表示實(shí)例與實(shí)例、或?qū)嵗c數(shù)據(jù)值之間的二元關(guān)系；A是公理(axiom)的集合；F是事實(shí)(fact)的集合。公理A和事實(shí)F統(tǒng)稱為本體O的三元組集T(triples)；類C、實(shí)例I和屬性P統(tǒng)稱為本體O的實(shí)體集(entities)；而三元組集包含的三元組數(shù)目，稱為本體O的大小，記為|O|。
定義2OWL DL本體圖閉包。OWL DL本體圖G中所有顯示的和隱含的三元組的集合，稱為OWL DL本體圖G的閉包，記為C(G)。
OWL DL本體圖閉包包含更多的領(lǐng)域知識。OWL DL本體圖閉包的算法：循環(huán)地應(yīng)用OWL DL的推理規(guī)則，如果有聲明滿足這些規(guī)則中的某一條，則生成新的聲明，將新的聲明添加到原有聲明中，直到所有聲明都不滿足推理規(guī)則的觸發(fā)條件，停止循環(huán)。這時所有聲明組成了OWL DL的本體圖閉包。如圖4所示，實(shí)線為原來的OWL DL本體聲明；虛線為新生成的聲明，一起構(gòu)成OWL DL本體的圖閉包。
342算法描述
OIODC算法（算法2）的基本流程如圖5所示。相似度計(jì)算采用編輯距離，同時考慮結(jié)構(gòu)、實(shí)例和屬性。限于篇幅，不再詳述。本體剪枝中，所謂虛擬本體OV是已經(jīng)建立了映射聯(lián)系，但還沒有對源本體中沒有用到的類、實(shí)例、關(guān)系等進(jìn)行刪除操作。
算法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實(shí)驗(yàn)評估
針對本算法進(jìn)行對比實(shí)驗(yàn)。機(jī)器采用P4 3.0 GHz臺式機(jī)，1 GB內(nèi)存，Windows操作系統(tǒng)。從網(wǎng)上的本體庫尋找20對本體，先用人工方式對這些本體進(jìn)行集成，集成的結(jié)果作為評價標(biāo)準(zhǔn)。將本文介紹的本體集成方法OIODC與COMA++[11]和FCA-merge[12]進(jìn)行比較。用A*表示人工集成得到的公理集，用A表示用集成方法生成的公理集，查準(zhǔn)率P(precision)和查全率R(recall)定義為
P=｜A*∩A｜/｜A｜，R=｜A*∩A｜/｜A*｜(1)
三種方法的實(shí)驗(yàn)結(jié)果對比如圖6所示。由于OWL DL本體圖閉包包含更多的領(lǐng)域知識，這樣在圖閉包的基礎(chǔ)上進(jìn)行相似度計(jì)算和推理，減少信息的丟失。可以看出本文介紹的OIODC在查準(zhǔn)率和查全率上優(yōu)于COMA++和FCA-merge。但OIODC在運(yùn)行時間上相對較長，平均集成每對本體用時482 s(不含剪枝時間)，而COMA++和FCA-merge分別為228和251 s(不含人工交互時間)。OIODC時間主要耗費(fèi)在閉包生成上，因此需要進(jìn)一步設(shè)計(jì)好的閉包生成算法。
4結(jié)束語
本文對本體中概念的is-a層次進(jìn)行了研究，提出了is-a層次的建立方法，并提出了is-a層次中概念的刪除算法。如何集成不同團(tuán)體開發(fā)的不同語言和不同組織方式的本體，解決信息異構(gòu)，實(shí)現(xiàn)信息共享，是當(dāng)今的一個研究熱點(diǎn)。本文提出了一種基于OWL DL圖閉包的本體集成算法OIODC，實(shí)驗(yàn)證明此方法可行。但本體集成是一個復(fù)雜的過程，到目前為止，仍沒有一個好的方法。因此，可以研究的空間很大。
將來的研究方向是在本體構(gòu)建方面，集中在is-a層次的其他維護(hù)上，如概念的添加合并、層次的合并刪除等，進(jìn)一步考慮本體中概念的其他關(guān)系，如part-of和kind-of等。在本體集成方面，尋求更好的閉包生成算法和相似度計(jì)算方法，同時研究多個本體的集成。
參考文獻(xiàn)：
［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].情報學(xué)報，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]范莉婭，王愛民，肖田元.本體集成方法評價指標(biāo)體系及其應(yīng)用研究[J].計(jì)算機(jī)集成制造系統(tǒng)，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]魏哲雄， 馮志勇. 基于字典技術(shù)的本體整合系統(tǒng)[J]. 計(jì)算機(jī)應(yīng)用， 2007，27(2):428-430.
[10]劉文斌， 謝強(qiáng)， 張磊. 多本體中子本體抽取的研究[J]. 計(jì)算機(jī)應(yīng)用研究， 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.
