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

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

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

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

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

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

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

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

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

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

1.1 OntoCommand

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

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

1.2 操作影響范圍

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

表1 命令列表Tab.1 Commands list

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

對(duì)于所有的原子命令操作，表2給出了每一個(gè)命令的影響計(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ù)檢測(cè)沖突的容易程度，可以將協(xié)同沖突劃分為硬沖突（hard conflicts）、軟沖突（soft conflicts）.

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

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

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

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

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

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

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

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

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

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

定義4 語義規(guī)則：給定一個(gè)本體實(shí)體e和兩個(gè)操作命令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 軟沖突：給定分別由不同用戶提交的兩個(gè)操作命令oc和oc′.若滿足以下兩個(gè)條件：（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é)同沖突檢測(cè)算法

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

那么，給定一個(gè)STRU＿CON＿SET對(duì)象，根據(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個(gè)定理，設(shè)計(jì)一個(gè)高效的協(xié)同沖突檢測(cè)算法（Collaborative Conflicts Detector Algorithm）.輸入的數(shù)據(jù)為所有用戶及所有操作命令，初始化值均為空，即hardConflicSet＝｛｝，softConflictSet＝｛｝，結(jié)果為產(chǎn)生兩類沖突集合 .其偽代碼：

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

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

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

生長(zhǎng)在“酒糟透之人”這樣的原生家庭里，即使不變得尖酸刻薄，也難免會(huì)被生活染上一層風(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個(gè)數(shù)有限，所以這個(gè)循環(huán)復(fù)雜度為常量，即O（C）；

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

文中提出協(xié)同沖突劃分、檢測(cè)與消解方法，將協(xié)同沖突與本體一致性問題區(qū)別開來，按本體知識(shí)編輯操作的影響范圍、操作類型及啟發(fā)式規(guī)則把協(xié)同沖突劃分為硬沖突、軟沖突 .依據(jù)這個(gè)劃分，給出一個(gè)高效的檢測(cè)算法和沖突消解方案 .然而，所提出的協(xié)同沖突劃分、檢測(cè)與消解方法仍然是在一個(gè)比較大的尺度上來劃分沖突，造成有些沖突劃分不明甚至錯(cuò)誤.下一步的工作是逐步細(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］陳葉旺.國(guó)家農(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é)任編輯：陳志賢 英文審校：吳逢鐵）