劉世卿

(中航工業(yè)西安航空計算技術(shù)研究所， 陜西 西安 710119)

基于最小波及效應(yīng)的企業(yè)本體演化方法研究

劉世卿

(中航工業(yè)西安航空計算技術(shù)研究所， 陜西 西安 710119)

本體演化會影響依賴本體的服務(wù)，使其重新修訂和重新部署。面對同一變更需求，不同演化實現(xiàn)方法造成的影響范圍差別很大。提出了一種基于最小波及效應(yīng)(MRE)的本體演化算法?；诒倔w圖模型建立了本體鄰接矩陣和可達矩陣，憑借矩陣變換與運算對本體演化中節(jié)點組級與節(jié)點級的波及效應(yīng)進行了深入的分析和量化。MRE算法將本體演化過程轉(zhuǎn)變?yōu)榍髨D的最短路徑過程，通過搜索一條影響值最小的變更路徑來減小本體演化的影響范圍。通過實際應(yīng)用驗證，MRE算法的時間代價與變更影響范圍大大小于現(xiàn)有算法。

本體演化；波及效應(yīng)；本體變更路徑；強子圖

引 言

近年來，許多應(yīng)用系統(tǒng)都采用本體作為語義支撐來滿足不斷增長的知識交換和知識集成需求。本體(Ontology)是某一領(lǐng)域共享概念模型的明確表示和描述，環(huán)境的變化和業(yè)務(wù)需求的多變性常常會引發(fā)支撐本體的演化[1]，由此產(chǎn)生了本體演化(Ontology Evolution)問題。本體的變化對本體所定義的數(shù)據(jù)、依賴于該本體的其他本體以及使用這些本體和數(shù)據(jù)的應(yīng)用系統(tǒng)都會產(chǎn)生較大的影響[2]。

降低本體演化的影響可以從兩個角度進行：1)降低本體演化的影響范圍，即當本體演化后受到波及的服務(wù)個數(shù)越少越好。2)減輕服務(wù)的受影響程度，即如果某服務(wù)不可避免地受到波及，那么是否可以控制本體演化的過程使其朝著有利于服務(wù)修訂的方向進行，使其變得盡可能的簡單易行。其中需求2的滿足依賴于服務(wù)的具體實現(xiàn)方式，難以提出一個通用的算法，本文主要從滿足需求1的角度出發(fā)來探討如何降低本體演化的影響。

當前本體演化研究的焦點在于保證演化需求的實現(xiàn)以及維護演化前后本體的一致性[3]，對于降低演化的影響關(guān)注甚少。由于本體演化的復(fù)雜性，大多數(shù)研究還停留在框架分析和定性討論層面。而演化影響的降低不但可以顯著減輕依賴本體的應(yīng)用系統(tǒng)的開發(fā)和維護的負擔，還可以大幅提高系統(tǒng)的健壯性和靈活性。當前，流行的本體編輯演化工具如OntoEdit[4]、OilEd[5]、KAON[6]都存在演化策略簡單、依賴人工等問題[7-8]。

據(jù)此，本文基于本體圖模型，憑借矩陣變換與運算對本體演化中的波及效應(yīng)進行了深入的分析和量化界定。同時給出了本體元素影響度及受影響度的計算方法。在強分圖理論的支持下定義了本體強子圖，并分析了子圖內(nèi)聚度、強子圖影響度的計算方法。在此基礎(chǔ)上建立了基于最小波及效應(yīng)(Minimal Ripple-effect, MRE)的本體演化算法，將本體演化過程轉(zhuǎn)變?yōu)榍髨D的最短路徑過程，通過尋找一條影響值最小的變更路徑來減小本體演化的影響范圍。

1 本體圖與本體矩陣

1.1 本體模型

本文所依賴的本體模型被定義一個二元組：

定義1 本體模型：OntModel:=(E,Imp)。

其中，E為本體的實體集合；Imp為導(dǎo)入的其他本體模型。

定義2 本體的實體集合E被定義為一個12元組：

E:=(C,P,I,Hc,Hp,label,domain,range,mincard,maxcard,instconc,instprop)

其中各組成詳見文獻[9]。

1.2 本體圖與鄰接矩陣

定義3(本體圖) 一個本體O的圖模型是一種有向的類型圖G=，其中節(jié)點集V的元素對應(yīng)O中的概念或關(guān)系，邊集E的元素對應(yīng)O中的函數(shù)、概念層次或關(guān)系層次。v∈V，v=，其中節(jié)點類型t對應(yīng)本體概念或關(guān)系的ODM類型(如OWLClass)，A是節(jié)點的屬性集合，a∈A，a=，即屬性是名稱和值的二元組。e∈E，e=，e的類型對應(yīng)ODM中的表示關(guān)系的類型(如OWLOnProperty)，from∈V，表示邊的始點，to∈V，表示邊的終點。邊的方向表示節(jié)點間的語義方向，V稱為本體元素，E稱為本體關(guān)系(不同于本體定義中“關(guān)系”的含義)。

基于本體和本體圖模型定義可以將本體表示成圖的形式，這種圖形方式的本體模型清晰地體現(xiàn)出本體的結(jié)構(gòu)性。例如，一個本體用基于ODM的模型表示如圖1所示。

圖1 本體模型舉例

該本體的圖模型則由10個結(jié)點和11條邊組成，結(jié)點表示本體元素(Φ為空)：

v1=

v2=

v3=

v4=

v5=

v6=

v7=

v8=

v9=

v10=

邊表示本體關(guān)系，邊的方向表示終點對始點的依賴，邊上標簽的含義一般與依賴關(guān)系相反：

e1=

e2=

e3=

e4=

e5=

e6=

e7=

e8=

e9=

e10=

e11=

圖2給出了本體圖模型及其對應(yīng)的鄰接矩陣，現(xiàn)在可以使用圖論方法處理本體。

圖2 本體圖模型及其對應(yīng)的鄰接矩陣

(1)

則圖2對應(yīng)的可達矩陣為

2 本體變更波及效應(yīng)量化

本體演化是在本體元素發(fā)生變更時，通過相應(yīng)其他元素的配套更改而重新達到本體一致的過程。本體演化算法通過順序執(zhí)行相應(yīng)的變更操作來完成變更需求，每一個變更都將帶來一系列元素的更改，最終導(dǎo)致一條變更執(zhí)行路徑的產(chǎn)生。分析本體演化的波及效應(yīng)實質(zhì)上就是分析變更操作及其組成的變更執(zhí)行路徑的波及效應(yīng)。本體元素的變更操作可以分為4類：添加、刪除、重命名和設(shè)置。其中添加、刪除為基本操作，而重命名和設(shè)置可以由基本操作組合而成。雖然兩種基本操作帶來的波及效應(yīng)不同，但只要確定變更所影響的元素，波及效應(yīng)的計算方法是相同的。下面給出本體元素變更的波及效應(yīng)量化方法。

2.1 本體元素量化

將各元素對本體結(jié)構(gòu)的貢獻大小排序，可以清楚地看出元素在本體中的重要性，也可以用于指導(dǎo)用戶制訂本體修改策略。如OR+的各行之和分別為4、5、5、3、3、3、0、3、3、3。因此在變更過程中避免對影響度較大元素的更改是必要的。影響度為零的本體元素為孤立元素。

定義6(本體元素受影響度) 假設(shè)本體圖模型G=中有向邊的距離都為1，節(jié)點vi到vj的最短距離為D(vi,vj)，則vj對應(yīng)的本體元素受vi對應(yīng)本體元素的變化的影響程度(受影響度)

(2)

不同本體元素的變化會對某一本體元素產(chǎn)生不同程度的影響，表現(xiàn)為本體圖模型中到達同一節(jié)點的不同路徑的長度。本體元素對應(yīng)節(jié)點距離變化元素(變化源)對應(yīng)節(jié)點越遠，則該元素的受影響度越小。當多個關(guān)聯(lián)元素發(fā)生變化時，vj的受影響度可以通過式(2)求和得到。

2.2 本體子圖量化

定義7(本體子圖) 針對本體圖模型G=，存在一個本體圖G′=，如果V′?V和E′?E，則G′是G的本體子圖。

定義9(本體強子圖) 內(nèi)聚度為1的子圖稱為本體強子圖。

3 MRE算法

文獻[10]通過公式推導(dǎo)將本體演化帶來的服務(wù)變更的減小問題轉(zhuǎn)化為本體演化波及效應(yīng)減小問題。這里直接針對本體演化波及效應(yīng)的最小化展開討論。根據(jù)上一節(jié)的分析，本體演化最小波及效應(yīng)的問題可以歸結(jié)為尋找一條變更執(zhí)行路徑，使得演化后的本體滿足一致性約束且所改變的本體元素個數(shù)最小。MRE算法將最小演化代價問題轉(zhuǎn)化為針對本體圖的最短路徑問題。其中，圖的節(jié)點是本體元素，按照之前的討論，節(jié)點賦值為該本體元素的影響度。

3.1 算法設(shè)計

算法尋找路徑的過程為從變更元素的出邊開始，到達所有可達孤立元素的過程。此時經(jīng)歷的路徑稱為搜索路徑。依據(jù)算法的設(shè)計目標，MRE算法被描述為如下過程：在圖的搜索過程中計算已搜索路徑的變更影響值，如果該值大于已經(jīng)搜索到的最小值就不再繼續(xù)搜索。搜索過程中，已搜索路徑的影響值小于原先搜索到的最小值，那么將作為一個新的備選解。MRE算法以一個待演化本體鄰接矩陣以及一個變更元素為輸入，以一條最小變更執(zhí)行路徑和最小影響值為輸出。MRE算法描述如下：

輸入：變更節(jié)點ChgNod，ChgNod與其可達的所有節(jié)點構(gòu)造的鄰接矩陣Q(可以通過待演化本體鄰接矩陣構(gòu)造)，Q的秩為N，infect為Q中節(jié)點的影響度。

輸出：已經(jīng)搜索到的最小影響值minValue和最小變更執(zhí)行路徑minPath。

算法：

Function MRE(Q, ChgNod){

//初始化，得到賦權(quán)鄰接矩陣

minPath置空;

S置空; //已求出最短路徑的頂點集合

S = S+ChgNod;

P[N][N] set false; //是否為最短路徑上節(jié)點的標志位

O[N][N] set 0; //賦權(quán)鄰接矩陣

for i∈[0, N-1] do

for j∈[0, N-1] do

if Q[i][j] equals 1

O[i][j]=infect[i];

P[i][j]=true;

end

end

end

D=O[0]; //記錄最短路徑值的數(shù)組

//尋找從ChgNod到所有可達孤立元素的最短路徑

for i∈[0, N-1] do

minValue=0;

找出不在S中的離ChgNod最近的節(jié)點Vtemp;

S+=Vtemp;

minValue=D[Vtemp];

for j∈[0, N-1] do

if j?S ∧ minValue+Q[Vtemp][j]

D[j]=minValue+Q[Vtemp][j];

P[j]=P[Vtemp];

P[i][j]=true;

end

end

end

//通過并操作，找到最小變更路徑

for i∈[0, N-1] do

for j∈[0, N-1] do

if infect[i] equals 0 ∧ P[i][j] equals true

minPath=minPath∪j;

minValue+=D[j];

end

end

end

}

3.2 復(fù)雜度分析與改進

MRE算法的主體是求圖頂點到各節(jié)點最短路徑的過程，無論采用何種圖存儲方法其算法復(fù)雜度都為O(N2)，當本體規(guī)模增加時，算法執(zhí)行時間的增加也很可觀。根據(jù)2.2節(jié)對強子圖的分析不難發(fā)現(xiàn)，當本體圖中包含強子圖時，MRE算法的搜索路徑只要包含強子圖的任意節(jié)點，算法的計算結(jié)果都是一樣的，我們引入強子圖節(jié)點化方法對算法進行簡化。

定義10(強子圖節(jié)點化) 由于對強子圖任意元素的更改造成的波及效應(yīng)等同于對整個強子圖的更改造成的波及效應(yīng)，為了分析方便我們將本體圖的強子圖轉(zhuǎn)化為節(jié)點，該節(jié)點的先行后續(xù)關(guān)系為強子圖所有節(jié)點對外關(guān)系的并集。這個過程稱為強子圖節(jié)點化，轉(zhuǎn)化后的節(jié)點稱為強節(jié)點。

如果本體圖包含m個強子圖，所有強子圖總元素個數(shù)為n，那么結(jié)點化后本體圖的節(jié)點數(shù)為N-n+m，算法復(fù)雜度降為O((N-n+m)2)。在本體圖的構(gòu)造過程中，原本的關(guān)聯(lián)關(guān)系有包含、繼承等多種，而圖構(gòu)造時都統(tǒng)一為連接線，這樣本體圖中很容易出現(xiàn)強子圖；當本體圖中元素個數(shù)很多時，不同元素間的關(guān)系錯綜復(fù)雜，也很容易出現(xiàn)強子圖。因此在實際的演化路徑生成過程中，強子圖節(jié)點化在大多數(shù)情況下都可簡化演化過程。

3.3 應(yīng)用評價

某生產(chǎn)部門要打造中央級的產(chǎn)品資源集成門戶，允許各級生產(chǎn)單元自主加入總體資源中。其本體片段如圖3所示。在該集成門戶的打造中，本體的構(gòu)建是一個核心任務(wù)。各級生產(chǎn)單元依賴本體以統(tǒng)一的方式接入，由于事先不能確定加入共享資源的生產(chǎn)單元，因此無法事先構(gòu)建出一個能滿足所有需求的全局本體。另外，隨著產(chǎn)品升級換代必然帶來本體結(jié)構(gòu)的變化。也就是說生產(chǎn)部門本體會隨著生產(chǎn)單元的加入與產(chǎn)品升級換代而不斷演化。但是，本體演化會對已構(gòu)建的平臺服務(wù)帶來極大影響，每一次本體演化都可能引起平臺服務(wù)的重新修訂和重新部署[11]。因此，如何減輕本體演化對平臺服務(wù)的影響就成為實現(xiàn)產(chǎn)品集成門戶的關(guān)鍵。

圖3 某產(chǎn)品本體演化示例

下面以圖3所示的產(chǎn)品本體中的產(chǎn)品A片段為實驗數(shù)據(jù)，驗證不同變更算法的效率。該片段共涉及9種產(chǎn)品資源以及與這些資源相關(guān)的搜索、統(tǒng)計等共計60多個服務(wù)。為了方便比較不同變更算法的效率，我們使用元素變更率的概念，即：

變更率=演化后需要改變的元素個數(shù)/元素總數(shù)

(3)

采用Protégé、KAON變更執(zhí)行算法和MRE算法分別對該本體執(zhí)行演化后得到元素的變更率。以刪除操作為例，實驗內(nèi)容和結(jié)果如表1所示。顯然，MRE算法對元素的平均變更程度明顯小于其他兩種算法。

表1 實驗內(nèi)容及結(jié)果

表1反映出MRE算法的有效性主要體現(xiàn)在非葉節(jié)點的改變上，這是因為非葉節(jié)點與其可達所有節(jié)點構(gòu)造的圖中節(jié)點數(shù)較多。非葉節(jié)點在系統(tǒng)中的層次越高，其子節(jié)點和屬性越多，與之關(guān)聯(lián)的可達節(jié)點也越多，MRE算法有效性也越明顯。對于葉節(jié)點的改變，3種算法所引起的服務(wù)變更率基本持平。這是因為當關(guān)聯(lián)元素很少時，最短路徑與一般路徑的差別不是很大。從平均效果來看，Protégé和KAON算法的服務(wù)變更率基本持平。MRE算法的服務(wù)變更率則明顯低于這兩個算法，僅為其65%左右。該實驗結(jié)果可以充分說明本文所提出算法能夠有效減小本體變更的影響范圍。

通過實驗結(jié)果還可以發(fā)現(xiàn)MRE算法相比其他算法的特性。在整個本體圖中，子部件2與非回轉(zhuǎn)類零件的本體元素圖中存在強子圖，而子部件2中還存在一個影響度很大的節(jié)點。Protégé與KAON采用的演化算法之所以變更率較大還因為他們沒有在變更路徑中避開這些節(jié)點，而MRE算法通過最短路徑的搜尋有效避開了這些節(jié)點，因而取得了較好的效果。因此在實際應(yīng)用中，可以考慮以避開影響度大的節(jié)點尤其是強子圖中的節(jié)點為先驗知識的高速演化路徑生成算法，在較小的時間復(fù)雜度下獲得與MRE算法近似的次優(yōu)解。

4 結(jié)束語

本文提出的MRE算法，以較小的時間代價使平均變更影響范圍大大小于現(xiàn)有的本體演化算法。為了抽象出問題的本質(zhì)，本文的分析沒有考慮不同變更操作影響度的不同以及本體描述語言因素，進一步的研究工作包括針對具體本體語言的本體演化波及效應(yīng)精確分析、本體演化算法等。

[1] LIU C, CHEN W H, HAN Y B. DODO: A mechanism helping to dynamically construct domain ontologies for services integration[C]//Proceedings of the International Workshop on Service-oriented Software Engineering, 2006: 13-18.

[2] MAEDCHE A, MOTIK B, STOJANOVIC L. Managing multiple and distributed ontologies on the semantic web[J]. The International Journal on Very Large Data Bases, 2003, 12(4): 286-302.

[3] HAASE P, SURE Y. State-of-the-art on ontology evolution[R]. Karlsruhe: University of Karlsruhe, 2004.

[4] SURE Y, ANGELE J, STAAB S. OntoEdit: Multifaceted inferencing for ontology engineering[J]. Journal on Data semantics, 2003(1): 128-152.

[5] BECHHOFER S, HORROCKS I, GOBLE C, et al. OilEd: A reasonable ontology editor for the semantic web[C]//Proceedings of the Joint German/Austrian Conference on Artificial Intelligence, 2001: 396-408.

[6] STOJANOVIC L, MAEDCHE A, MOTIK B, et al. User-driven ontology evolution management[C]//Proceedings of the 13th International Conference on Knowledge Engineering and Knowledge Management, 2002: 285-300.

[7] STOJANOVIC L, MOTIK B. Ontology evolution within ontology editors[C]//Proceedings of the OntoWeb-SIG3 Workshop at the 13th International Conference on Knowledge Engineering and Knowledge Management, 2002: 53-62.

[8] STOJANOVIC L, MAEDCHE A, MOTIK B, et al. Ontology evolution as reconfiguration-design problem solving[C]//Proceedings of the 2nd International Conference on Knowledge Capture, 2003: 162-171.

[9] STOJANOVIC L. Methods and tools for ontology evolution[D]. Karlsruhe: University of Karlsruhe, 2004.

[10] NOY N F, KUNNATUR S, KLEIN M, et al. Tracking changes during ontology evolution[C]//Proceedings of the 3rd International Semantic Web Conference, 2004: 259-273.

[11] BORST W N. Construction of engineering ontologies for kn- owledge sharing and reuse[D]. Enschede: University of Twente, 1997.

劉世卿(1983-)，女，碩士，主要研究方向為計算機輔助制造，電子設(shè)備結(jié)構(gòu)設(shè)計。

Study on Enterprise Ontology Evolution Method Based on Minimal Ripple-effect

LIU Shi-qing

(AVICXi′anInstituteofAviationComputingTechnology，Xi′an710119,China)

Ontology evolution has an effect on services relying on ontology, and makes them revised and redeployed. Facing the same change demands, different evolution implementation methods have greatly different influence scope. This article provides an ontology evolution algorithm based on minimal ripple-effect (MRE). Ontology adjacency matrix and reachability matrix based on ontology graph model are established. In-depth analysisand quantification for the ripple-effects at node-group level and node level in ontology evolution are carried out by matrix transformation and operation. The MRE algorithm transforms ontology evolution process into the process of calculating shortest graph path. It searches a change path with smallest effect-value to decrease the influence scope of ontology evolution. The actual application and demonstration indicate that the MRE algorithm costs a much smaller graph searching time and has a much smaller change influence scope than current algorithm.

ontology evolution; ripple-effect; ontology change path; strong sub-graph

2013-10-23

TP391

A

1008-5300(2014)02-0051-06