一種本體協(xié)同沖突的檢測方法

陳葉旺，李海波，余金山，陳維斌

（華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建 泉州 362021）

一種本體協(xié)同沖突的檢測方法

陳葉旺，李海波，余金山，陳維斌

（華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建 泉州 362021）

針對農(nóng)業(yè)領(lǐng)域分布式的迭代知識協(xié)同建構(gòu)過程中存在的協(xié)同沖突及難于檢測的問題，提出協(xié)同沖突劃分、檢測與消解方法.把協(xié)同沖突與本體一致性問題區(qū)別開來，按本體知識編輯操作的影響范圍、操作類型及啟發(fā)式規(guī)則把協(xié)同沖突劃分為硬沖突、軟沖突.依據(jù)這個劃分，給出一個高效的檢測算法和沖突消解方案.

本體；協(xié)同沖突；硬沖突；軟沖突

本體已經(jīng)為人們廣泛地接受成為知識共享的基礎(chǔ)設(shè)施，但本體建構(gòu)卻是一個令人頭痛的問題［1］.2002年，Denny［2］分別介紹和比較了56種本體編輯工具.借助Protégé2000［3］和 OilEd［4］等本體構(gòu)建工具，可以把精力集中在本體內(nèi)容的組織上，而不必了解本體描述語言的細(xì)節(jié).一些支持協(xié)同開發(fā)［5－7］工具提拱類似于數(shù)據(jù)庫中的同步事務(wù)存儲控制，包括鎖定和回滾.然而，本體與數(shù)據(jù)庫有一點(diǎn)關(guān)鍵不同，本體實(shí)體之間存在著微妙的關(guān)系，改變一個實(shí)體就有可能引起連鎖變化.在本體協(xié)同建構(gòu)中，沖突總是伴隨著開發(fā)過程始終.在傳統(tǒng)的軟件協(xié)同開發(fā)過程中，為了解決沖突問題，在版本管理系統(tǒng)中引入“鎖”和“分枝／合并”技術(shù).這種技術(shù)的前提是以文檔為基本單位，如一個開發(fā)人員在操作某個文檔，而另一個開發(fā)人員也要對該文檔修改，則沖突產(chǎn)生.因此，其解決的辦法有：（1）鎖定需要操作的文檔；（2）由版本管理系統(tǒng)自動合并兩個開發(fā)人員對文檔的修改.然而，在本體開發(fā)過程中，情況則比較復(fù)雜，必然會在在協(xié)同沖突.有些沖突本身不會對本體一致性造成損害，其錯誤的結(jié)果是隱性的，很難輕易地發(fā)現(xiàn)，各種本體推理機(jī)也無法檢測出來，但其結(jié)果卻不是知識操作員所期望的.針對這些問題，本文提出分布式的迭代知識協(xié)同構(gòu)建過程中協(xié)同沖突檢測劃分、檢測與消解方法.

1 協(xié)同沖突劃分與檢測方法

在農(nóng)業(yè)本體知識建構(gòu)系統(tǒng)中，本體知識建構(gòu)的基本單位是本體實(shí)體，包括概念、實(shí)例、關(guān)系、公理等，其粒度遠(yuǎn)小于物理文檔.為實(shí)現(xiàn)這些基本單位的操作，本體知識協(xié)同建構(gòu)系統(tǒng)中定義一些基本的操作命令 .通過這些操作可計(jì)算用戶對本體的編輯操作的影響范圍，并以此為基礎(chǔ)來劃分和檢測協(xié)同沖突.

1.1 OntoCommand

定義1 OntoCommand（OC）：這是一個3元組，記為oc＝〈Name，E，V〉.其中：Name是操作名稱；E是其操作的本實(shí)體集合；V為操作的參數(shù).

表1列出了本體知識協(xié)同建構(gòu)系統(tǒng)中的一些操作命令 .根據(jù)操作的類型，區(qū)分出3類不同的操作：ADD，DEL，MOD，分別表示增加、刪除和修改3大類操作.

1.2 操作影響范圍

本體中存在著豐富的語義關(guān)系，其中有些需要通過推理計(jì)算才能確定.改變一個本體實(shí)體語義，有可能影響到與其邏輯上相關(guān)的其他實(shí)體.這就意味著在本體的協(xié)同開發(fā)過程中，對于用戶的任何一個對本體實(shí)體的操作，都存在一個受影響的實(shí)體集合的定義

表1 命令列表Tab.1 Commands list

定義2 影響范圍（Impact Range，IR）：給定一個命令操作oc，IR（oc），計(jì)算oc的影響范圍.

對于所有的原子命令操作，表2給出了每一個命令的影響計(jì)算值.

表2 部分操作命令影響范圍表Tab.2 Affect range table in part of operation command

1.3 協(xié)同沖突分析

在本體協(xié)同開發(fā)過程中，不同用戶之間的操作沖突有些很容易判斷；有些不那么明顯，需要經(jīng)過描述邏輯（DL）推理，才能判斷沖突是否存在；還有一些很難得到?jīng)_突是否存在的確定判斷，需要用到啟發(fā)式規(guī)則，計(jì)算沖突是否有發(fā)生的可能性.根據(jù)檢測沖突的容易程度，可以將協(xié)同沖突劃分為硬沖突（hard conflicts）、軟沖突（soft conflicts）.

1.3.1 硬沖突 硬沖突是一種比較容易檢測的沖突，可以根據(jù)操作命令的影響范圍和操作類型來判斷.給定兩個操作命令oc和oc′，OTC（oc，oc′）是沖突檢測函數(shù)，返回真則表示oc有可能與oc′發(fā)生沖突；否則不然 .據(jù)此，判斷兩個操作命令是否有發(fā)生硬沖突的可能.表3為操作命令類型沖突函數(shù)表 .其中：T表示OTC值為真；F表示為假.

從表3可知，OTC值計(jì)算是根據(jù)操作命令類型來判斷的.如兩個操作都為DEL類型，則不視為沖突，即使兩個操作要刪除的本體實(shí)體是同一個 .這是因?yàn)锳RGONT會將相同操作合并.同理，對于同為ADD類型的操作也一樣.如果兩個操作同為MOD類型，則需通過OTC＿M(jìn)OD函數(shù)［8］作進(jìn)一步判斷.

定義3 硬沖突：給定兩個由不同用戶提交的操作命令，若滿足（1）OTC（oc，oc′）為真；（2）DR（oc，co′）〈〉NULL，其中，DR（oc，co′）＝IR（oc）∩IR（co′）兩個條件，則oc＠oc′成立，表示oc與oc′發(fā)生硬沖突.

表3 操作命令類型沖突函數(shù)表Tab.3 Conflict function table of the operation command

1.3.2 軟沖突 有些用戶操作之間的沖突并不像硬沖突那樣比較容易判斷，因?yàn)橛行┎僮鏖g接地影響了某些內(nèi)容的語義，而另一些操作仍舊使用它的原始語義.為了檢測因?yàn)檫@種間接影響而造成的沖突，需要通過描述邏輯推理來完成.

為此，定義一個基于描述邏輯的語義規(guī)則（semantic rules）集合 .以下列出其中幾條，違反任何其中一條規(guī)則即視為軟沖突.

（1）The Same VS Different：檢測是否存在一個本體實(shí)體，使得它與e1，e2中的某一個存在owl：sameAs或owl：Equivalent關(guān)系，而與另一個存在owl：differentFrom關(guān)系.

（2）The Same VS DisjointWith：檢測是否存在一個本體實(shí)體，使得它與e1，e2中的某一個存在owl：sameAs或owl：Equivalent關(guān)系，而與另一個存在owl：disjointWith關(guān)系.

（3）Functional Same VS Different：檢測是否存在一個本體實(shí)體，使得用owl：FunctionalObjecpro－ty關(guān)系可以推導(dǎo)出它與e1，e2中的某一個存在owl：sameAs或owl：Equivalent關(guān)系，而與另一個存在owl：differentFrom 關(guān)系.

（4）Functional Same VSDisjointWith：檢測是否存在一個本體實(shí)體，使得用owl：FunctionalObjecproty關(guān)系可以推導(dǎo)出它與e1，e2中的某一個存在owl：sameAs或owl：Equivalent關(guān)系，而與另一個存在owl：disjointWith關(guān)系.

定義4 語義規(guī)則：給定一個本體實(shí)體e和兩個操作命令oc和oc′，語義規(guī)則函數(shù)SEM（e，oc，oc′）用于計(jì)算是否存在語義不一致.返回值若為真，則表示e1與e2之間存在語義不一致，否則不然.其中：（1）e∈IR（oc）∩IR（oc′）；（2）e1為獨(dú)立執(zhí)行oc后實(shí)體e演化的結(jié)果，即e→e1；（3）e2為獨(dú)立執(zhí)行oc′后實(shí)體e演化的結(jié)果，即e→e2.

定義5 軟沖突：給定分別由不同用戶提交的兩個操作命令oc和oc′.若滿足以下兩個條件：（1）OTC（oc，oc′）為假；（2）?SEM?e∈IR（oc）∩IR（oc′），s.t.SEM（e，oc，oc′）＝0，則oc＃oc′成立，表示oc與oc′之間存在軟沖突.

圖1 STRU＿CON＿SET數(shù)據(jù)結(jié)構(gòu)Fig.1 Data structure of STRU＿CON＿SET

1.4 協(xié)同沖突檢測算法

為了能高效、快速地進(jìn)行沖突檢測，定義一個數(shù)據(jù)結(jié)構(gòu)STRU＿CON＿SET，如圖1所示.其中，所有的STRU＿CON＿SET對象都存放在一個排序的SortedList v中.每一個STRU＿CON＿SET對象，包括一個本體實(shí)體e，一個操作命令集合IRSet，?oc∈IRSet∶e∈IR（oc）.即IRSet包含的所有操作命令的影響范圍中都包含了e.

那么，給定一個STRU＿CON＿SET對象，根據(jù)定義硬沖突、軟沖突定義，則有

（1）?oc，oc′∈scs.IRSet，如果 OTC（oc，oc′）成立，則oc＠oc′；

（2）?oc，oc′∈scs.IRSet，如果?SEM，s.t.SEM（scs.e，oc，oc′）成立，且 OTC（oc，oc′）不成立，則oc＃oc′.

依據(jù)上述定義好的STRU＿CON＿SET結(jié)構(gòu)和3個定理，設(shè)計(jì)一個高效的協(xié)同沖突檢測算法（Collaborative Conflicts Detector Algorithm）.輸入的數(shù)據(jù)為所有用戶及所有操作命令，初始化值均為空，即hardConflicSet＝｛｝，softConflictSet＝｛｝，結(jié)果為產(chǎn)生兩類沖突集合 .其偽代碼：

該算法只對所得操作命令掃描一遍，就可以進(jìn)行硬沖突、軟沖突兩重檢測，但需要維護(hù)一個排序SortedList v.所有的沖突結(jié)果同樣分別放入hardConflicSet，softConflictSet和latentConflictSet中.算法主要步驟的復(fù)雜度分析：

（1）第3步，二叉排序算法復(fù)雜度為log n；

（2）第5步O（OTC）為常量，即O（C）；

生長在“酒糟透之人”這樣的原生家庭里，即使不變得尖酸刻薄，也難免會被生活染上一層風(fēng)霜，斷不可能有眼前的淡定從容之態(tài)。

（3）第7步，因?yàn)镺（SEM）＝O（C），所以這一步復(fù)雜度也為常量，即O（C）；

（4）第9步，因?yàn)镺（OntoSIM）＝O（C），所以這一步復(fù)雜度也為常量，即O（C）；

（5）第6～7步循環(huán)，系統(tǒng)定義的Semantic－Rules－Set中SEM個數(shù)有限，所以這個循環(huán)復(fù)雜度為常量，即O（C）；

（6）第3～10步循環(huán)，對于一個STRU＿CON＿SET對象scs的IRSet而言，其所包含的操作命令個數(shù)遠(yuǎn)遠(yuǎn)小于n，而根據(jù)實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果，極少有超過100，故這一步復(fù)雜度為常量，即O（C）；

（7）第2～12步循環(huán)，對于一個操作命令oc而言，其影響范圍IR值有限，因而交集S也是個有限集，這一步復(fù)雜度為常量，即O（C）；

（8）第1～13步循環(huán)，操作命令數(shù)為n個，因而復(fù)雜度為O（n）.

2 案例分析與實(shí)驗(yàn)

為進(jìn)行有效測試，組織了多個懂得一些農(nóng)業(yè)領(lǐng)域知識的人員，各自可以使用幾個不同的帳號獨(dú)立的完成一系列編輯操作.測試開始只有少數(shù)幾人進(jìn)行操作，慢慢地所有人逐步加入其中.在這個過程中沒有任何交流，所有操作也均逐一記錄下來.服務(wù)端配置為Intel Centrino Duo T2400 1.83GHz PC＋2 GB內(nèi)存＋WindowsXP SP2，本體知識數(shù)據(jù)來源于自國際糧農(nóng)組織（Food and Agriculture Organization）.表4為測試的本體數(shù)據(jù).

表4 測試本體數(shù)據(jù)Tab.4 Body test data

每隔一段時(shí)間，對所有操作做兩次分析.第1次是根據(jù)操作記錄做人工鑒定，找出認(rèn)為真正的沖突（R）；另一次根據(jù)的自動檢測算法識別出來的沖突P.將兩者對比，可確認(rèn)經(jīng)算法檢測出來的結(jié)果中真沖突的個數(shù)為I，偽沖突為F＝P－I.

通過硬沖突和軟沖突檢測結(jié)果及比較，評判算法檢測是否能有效檢測硬沖突與軟沖突.把所做操作中的硬沖突與軟沖突檢測結(jié)果做比較，兩類沖突查準(zhǔn)率（ηP）和查全率（ηR），如圖2所示.

圖2 硬沖突與軟沖突檢測結(jié)果Fig.2 Test results of hard conflicts and soft conflicts

由圖2可知：由于查準(zhǔn)率和查全率都比較高，故算法對軟沖突檢測比較有效 .相對而言，對硬沖突檢測不如軟沖突檢測，很難接近100%.究其原因，可能是對每一個命令的IR定義不夠完備，造成查準(zhǔn)率不能達(dá)到理想要求，但當(dāng)擴(kuò)充操作命令I(lǐng)R定義，使查準(zhǔn)率接近100%時(shí)，查全率卻急速下跌.

對于硬沖突檢測結(jié)果，在X軸起始處，查準(zhǔn)率查全率變化比較大.可以認(rèn)為這是因?yàn)閿?shù)據(jù)量還不夠，不能真正反映有效結(jié)果 .因此，隨著數(shù)據(jù)量的增大，其值也日趨平穩(wěn)，查準(zhǔn)率趨近于95%，查全率也趨近于93%.

3 結(jié)束語

文中提出協(xié)同沖突劃分、檢測與消解方法，將協(xié)同沖突與本體一致性問題區(qū)別開來，按本體知識編輯操作的影響范圍、操作類型及啟發(fā)式規(guī)則把協(xié)同沖突劃分為硬沖突、軟沖突 .依據(jù)這個劃分，給出一個高效的檢測算法和沖突消解方案 .然而，所提出的協(xié)同沖突劃分、檢測與消解方法仍然是在一個比較大的尺度上來劃分沖突，造成有些沖突劃分不明甚至錯誤.下一步的工作是逐步細(xì)劃編輯操作的影響范圍，進(jìn)而更詳細(xì)劃分沖突類別，以提高沖突消解效率.

［1］NOY N F，CHUGH A，ALANI H.The CKC challenge：Exploring tools for collaborative knowledge construction［J］.IEEE Intelligent Systems，2008，23（1）：64－68.

［2］DENNY M.Ontology building：A survey of editing tools［EB／OL］.［2002－11－06］http：／／www.xml.com／pub／a／2002／11／06／ontologies.html.

［3］NOY N F，SINTEK M，DECKER S，et al.Creating semantic Web contents with protege－2000［J］.IEEE Intelligent Systems，2001，16（2）：60－71.

［4］BECHHOFER S，HORROCKS I，GOBLEN C，et al.OilEd：A reason－able ontology editor for the semantic Web［C］∥Joint German／Austrian Conference on Artificial Intelligence（KI′01）.Berlin：Springer，2001：396－408.

［5］BOZSAK E，ETC M.KAON－towards a large scale semantic Web［C］∥The Third International Conference on ECWeb Aix－en－Provence.France：Springer，2002：304－313.

［6］DOMINGUE J.Tadzebao and webonto：Discussing，browsing and editing ontologies on the Web［C］∥Proceedings of the Eleventh Knowledge Acquisition Workshop.Banff：［s.n.］，1998.

［7］TEMPICH C，PINTO H S，SURE Y，et al.An argumentation ontology for distributed［C］∥Loosely Controlled and Evolving Engineering Processes of Ontologies.Crete：［s.n.］，2005.

［8］陳葉旺.國家農(nóng)業(yè)本體協(xié)同建構(gòu)與語義檢索若干技術(shù)研究［D］.上海：復(fù)旦大學(xué)，2009.

A Collaborative Conflicts Detection Method for Ontology Building

CHEN Ye－wang，LI Hai－bo，YU Jin－shan，CHEN Wei－bin

（College of Computer Science and Technology，Huaqiao University，Quanzhou 362021，China）

There exists conflicts in the process of iterative constructing agricultural ontology collaboritvelly，and they are difficult to detect.In this paper，based on the operation range，operation type and heuristic rulses，the collaborative conflicts was divided to hard conflicts and soft conflicts.We propose a method to classify，detect and digest collaborative conflicts，which differentiate the collaborative conficts from ontology consistency，finally we give a efficient solution to resolve conflits when they are detected.

ontology；collaborative conflicts；hard conflicts；soft conflicts

TP 301

A

1000－5013（2011）06－0641－05

2011－04－18

陳葉旺（1978－），男，講師，主要從事語義檢索與數(shù)據(jù)挖掘的研究.E－mail：ywchen＠hqu.edu.cn.

福建省自然科學(xué)基金資助項(xiàng)目（A0810013）；福建省農(nóng)業(yè)科技重大項(xiàng)目（2010N5008）；華僑大學(xué)科研基金資助項(xiàng)目（09BS619）

（責(zé)任編輯：陳志賢 英文審校：吳逢鐵）