一種用于本體排序的內容分析方法

摘 要:針對使用傳統的用于本體排序的方法得到的排序結果不夠準確的問題，提出了一種新的內容分析方法。首先通過構造本體的概念模型提取本體的主題詞集合得到本體的主題相似度;然后通過對關鍵詞所在的本體上下文進行分析，得到本體相對于關鍵詞的上下文相關度;最后結合主題相似度和上下文相關度得到本體相對于關鍵詞的綜合評價值并進行排序。實驗結果表明，該方法可以有效地提高本體排序的準確性。

關鍵詞:本體排序; 主題相似度; 上下文相關度

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2010)06-2127-03

doi:10.3969/j.issn.1001-3695.2010.06.038

Content analysis method used for ontology ranking

XU Dezhi， LIU Yijing

(School of Information Science Engineering， Central South University， Changsha 410083， China)

Abstract:The ontology ranking result was not precise enough using traditional method. Aiming at this problem， this paper proposed a new content analysis method. First， obtained the topic similarity according to the keywords set which was extracted by constructing the ontology conceptual model. Second， got the context relatedness through analyzing the ontology context. Finally， combined the topic similarity and context relatedness to calculate the ranking value which was used to order the related ontologies. The experimental result shows that the method can improve the precision of the ontology ranking result.

Key words:ontology ranking; topic similarity; context relatedness

萬維網中本體數目日益增長，大量表示相同或相似概念的本體相繼出現，而尋找并重用已有的本體并不是一件容易的事情，導致其重用度低并產生了大量的冗余信息，為了幫助用戶尋找并理解相關的本體，本體搜索引擎應運而生，而本體搜索引擎返回的搜索結果的排序直接影響到用戶搜索的效率。為了提高本體搜索結果的準確性，本文提出了一種用于解決本體搜索中排序問題的內容分析方法，通過計算本體的主題相似度和上下文相關度得到本體綜合評價值并進行排序。

1 相關工作

對語義Web中本體進行排序是語義Web眾多排序問題中的一個關鍵問題[1]。隨著本體技術的發展，不同的用于本體排序的評價方法被提出。OntoRank[2]是常用的本體搜索引擎Swoogle所使用的算法，它是一種類似網頁排序的基于鏈接分析的方法，該算法考慮了可能存在于不同本體之間的多種語義關聯，為不同關聯指定相應的權值，再根據類似網頁排序的基于鏈接分析的思想來評價本體的重要性。此外，文獻[3]中提出了AKTiveRank算法，綜合考慮了四種不同標準對本體的重要性進行評價，包括類匹配標準、密度標準、語義相似度標準和中介性標準。文獻[4]中提出的OntoQA算法則是從本體模式和本體實例兩個方面提出不同的標準來評價本體。

然而，OntoRank算法沒有考慮關鍵詞在本體中的重要性對排序結果的影響和本體本身的結構，因此準確率比較低;AKTiveRank和OntoQA算法雖然考慮了本體的結構信息和關鍵詞對結果的影響，但是只考慮了對關鍵詞描述的豐富程度，沒有考慮其差異性，因此得到的結果均不理想。

2 本體的內容分析方法

2.1 主題相似度的計算

根據用戶提供的關鍵詞，本體搜索引擎可能搜索出大量的相關本體。本體對關鍵詞的描述是否恰當與本體和本體所描述的主題是密不可分的。例如，用戶想搜索關于“Person”的本體，關鍵詞“Person”可能會以分類的形式出現在描述“Agent”的本體中，也有可能在描述“Publish”本體中，以與“Publish”概念具有“has Author”的關系出現。根據結構特征分析，這兩個概念具有相似的重要性，但關鍵詞與“Agent”的相似度要明顯高于與“Publish”的相似度，顯然用戶會認為描述“Agent”的本體更加符合需要。因此，本體的內容分析應該考慮關鍵詞與本體主題的相似度。

為了得到關鍵詞與相關本體間的主題相似度，首先要得到本體的主題詞信息。本體元素中，概念在表現本體主題信息方面所起到的作用顯然要遠遠大于屬性、實例等元素，因此本體的主題提取算法主要考慮本體的概念結構信息。本文根據本體的概念模型得到本體主題詞集，本體的概念模型構造算法如算法1所示。

算法1 構造本體概念模型

輸入:本體;輸出:本體概念模型。

a)解析本體，得到本體中所有的概念及概念之間的父子關系、等價關系、組成關系，及以概念作為domain的賓語的屬性數目與概念所具有的onProperty屬性數目之和npd等。

b)將每個概念看做本體概念模型中的一個節點。

c)將具有等價關系的概念節點合并成一個節點。

d)對于任意概念C1，如果C1是概念C2的子概念，或C1是C2的組成部分，則增加一條C1節點指向C2節點的邊。

e)將每個概念的npd更新成其子概念中npd的最大值。

f)如果所有的概念節點合并成一個有向圖則完成;否則給定Thing概念作為公共父概念，為每個分圖的根節點添加一條指向Thing概念的邊。

本體的概念模型中包含多個概念節點，各個概念所起到的作用是不同的，并不是所有的概念都能描述本體的主題信息。在一個本體中，各個概念的分類信息分布得并不均勻，有些概念的子概念多一些，有些概念子概念少一些。為了描述本體中概念分類信息的不同，給出了定義1。

定義1 概念的子概念飽和度、寬度飽和度和深度飽和度假設在本體概念模型中，概念Ci的父節點有n個孩子(C1，C2，…，Cn)。其中:Ci(1≤i≤n)的子概念數用s表示，直接子概念數用w來表示，子樹深度用d來表示，那么Ci.SATw=Ci.w/max(Ck.w)，Ci.SATd=Ci.d/max(Ck.d)，Ci.SATs=(Ci.s+Ci.ndp)/max(Ck.s+Ck.ndp)(1≤k≤n)分別叫做概念Ci的寬度飽和度、深度飽和度和子概念飽和度。

在本體的概念模型中，每個概念對于本體主題的貢獻并不相同，因此應為主題詞集中的每個概念分配不同的權值。而本體相對于關鍵詞的重要性不僅要與關鍵詞與相關主題詞之間的相似度有關，還應與相關主題詞在本體主題詞集中的權重有關。一個概念是否能在某種程度上體現本體的主題信息，一方面與該概念的父概念分類的細致程度也就是該概念在兄弟概念中所處的位置有關;另一方面又與該概念本身分類的情況有關。根據以上的描述，本文給出兩條本體主題詞提取規則。

規則1 一個本體概念模型中的任意節點R有n(n≥1)個孩子(記為C1，C2，…，Cn)，如果該本體中對R的孩子Ci(1≤i≤n)的描述遠遠多于對R的其他孩子的描述，那么可以認為節點Ci比R更能表現該本體的主題信息，而R的其他孩子對主題信息的貢獻可以忽略不計。

規則2 假設一個概念有非常細致的分類，即該概念的直接子概念的數目特別地多，那么其中的任何一個直接子概念都不能準確表現主題信息，除非該概念有少量的直接子概念相對于其他直接子概念來說具有非常詳細的描述，那么這少量的直接子概念就能夠代表部分主題的信息。

根據以上分析，本文給出在本體的概念模型中本體主題詞權值的分配算法，如算法2所示。

算法2 本體概念模型中概念處理算法。

輸入:本體概念模型，當前概念。

輸出:當前概念的子概念中可以作為主題詞的概念及其權值分配。

a)如果C2.SATs/C1.SATs<α，則將C1加入到集合topic和集合wait中，C1.f的值置為2，并忽略概念C1的兄弟節點，即C2.f…Cn.f=-1，同時，將current的權值賦給C1，降低current的權值，如式(1)(2)所示，轉到e)。dep(C1)的定義如文獻[5]所示。

C1.weight=current.weight(1)

current.weight=current.weight×(1-1/2dep(C1))(2)

b)如果Cv.SATs<α(1≤v≤n)，則忽略概念Cv…Cn，即將Cv.f…Cn.f的值置為-1。

c)對于每個沒被忽略的current的子概念，則

(a)如果Ci.SATw>β且Ci.SATd<γ，則將Ci加入到集合topic中，忽略Ci，置C1.f值為-1;

(b)如果Ci.SATw<β且Ci.SATd<γ，則通過值m=ni/ki來選擇操作，若m>3，則將Ci加入到集合topic和wait中，置C1.f值為2;否則將Ci加入到集合topic中，忽略Ci;

(c)如果Ci.SATd≥γ，則將Ci加入到集合topic和wait中置值C1.f為2。

d)根據式(3)為current概念的子概念中抽取的主題詞分配權值;

Ci.weight=current.weight×(Ci.SATs/∑v-1j=1Cj.SATs)(3)

e)將概念current從集合wait中移除。

以上給出了本體概念模型中概念處理算法。本體主題詞提取過程如算法3所示。

算法3 本體主題詞集提取算法

輸入:本體概念模型;輸出:本體的帶權主題詞集合。

a)初始化變量;

topic={root}，wait={root}，root.weight=1，current=root

b)獲得當前概念current的直接子概念C1，C2，…，Cn。

c)對每一個概念Ci計算其深度飽和度Ci.SATd、寬度飽和度Ci.SATw和子類飽和度Ci.SATs。

d)根據Ci.SATs將current的子概念進行排序，得到新的C1，C2，…，Cn。

e)根據算法2對current進行處理。

f)如果wait=， 轉到g)，否則若集合wait中不存在概念C滿足C.f=1，則對集合wait中的每一個概念C.f--，再在wait中選擇概念C滿足C.f=1賦給current，轉到b)。

g)如果Thing∈topic，那么將概念Thing從topic中移除。

h)輸出topic集合中的元素及其權值。

在算法2和3中，ni為概念Ci的子概念的數目，ki為Ci的直接子概念數目;Ci.f為標志位，Ci.f=1表示Ci與當前正在處理的概念為兄弟概念，即等待處理的概念;Ci.f=2表示概念Ci為當前處理概念的下一級的概念，只有當Ci.f=1的概念全部處理完之后才會考慮這一級的概念;Ci.f=-1表示概念Ci已經處理完畢或者不需要進一步處理。α、β、γ為選擇因子。其中，α的取值不能太大也不能太小，取值過大會導致某些主題信息被丟棄，取值太小會誤將不能表示主題信息的概念加入到主題信息中，一般情況下取α=0.25;β和γ主要用來區分概念分類的深度與廣度的不同對處理方式的影響，文中取β=0.4，γ=0.3。

根據上述算法得到了本體的帶權主題詞集合。根據關鍵詞與本體主題詞的匹配關系，可以將對本體的主題相似度relt計算分為兩種情況。當關鍵詞與本體主題詞集中元素完全匹配時，主題相似度即為主題詞的權值;否則根據文獻[6]中所給的方法，計算關鍵詞與本體中權值最大的主題詞之間的相似度來得到關鍵詞與本體的主題相似度，如式(4)所示。

relt(k，O)=weight(C)關鍵詞與主題詞C完全匹配

sim(k，max(C))不存在與關鍵詞完全匹配的主題詞(4)

其中:k代表用戶輸入的關鍵詞;max(C)代表主題詞集中權值最大的主題詞。

2.2 上下文相關度計算

上下文相關度用來描述對本體中某個概念描述的認可程度，文中用向量來表示本體的上下文描述信息。首先根據所有本體對相關詞的描述信息構造標準向量;然后分別對每個本體構造上下文描述向量;最后通過本體的描述向量與標準向量之間的相關度來表示本體的上下文相關度。

文中對上下文相關度的計算主要基于以下兩個規則:

規則3 本體中對關鍵詞上下文的描述信息在越多的本體中出現，則該描述信息與關鍵詞的相關度越大。

規則4 如果一個描述信息只在極少數本體中出現，不能單純地認為該信息與本體的相關度小。

根據上述思想，用戶給出的關鍵詞的上下文相關度的計算可以描述為算法4。

算法4 本體上下文相關度計算

輸入:相關本體，查詢關鍵詞;

輸出:本體對查詢關鍵詞的上下文相關度。

a)依次遍歷各個相關本體(Oi)，得到各個本體中與關鍵詞相對應的概念的描述信息集合(Dpti)。其中，Dpti包括Oi中與關鍵詞相對應的概念的子概念、屬性等。

b)求所有本體對關鍵詞描述信息集合的并集Dpt，構造標準描述向量D(d1…dn)。其中:di∈Dpt∧i≠j，di≠dj，建立關鍵詞描述矩陣A。矩陣的A中的元素定義如下:

aij=0 djDpti

1 dj∈Dpti

c)統計各個描述信息在相關本體中出現的總次數，并計算各個描述信息在所有相關本體的流行度p。

cntj=∑ni=1aijpj=cntj/N

其中:N為候選本體的個數。

d)設定流行度閾值pt(0

setp={dj|pj≥pt，1≤j≤n}，seti={dj|pj

e)分別計算每個描述的相關度，對于流行度大于閾值的描述，其相關度值即為流行度值;對于流行度小于閾值的描述，相關度則需要由計算得到。

trj=pjdj∈setp

rel(k，dj)dj∈seti

其中:rel(k，dj)的值可以根據文獻[6]中的方法計算。

f)構建關鍵詞描述相關度向量T=(t1，t2，…，tj，…，tn)，向量中的元素tj=trj。

g)計算每個本體的上下文相關度:relc(Oi)=sim(Ai，T)。其中:sim(Ai，T)為Ai與T的余弦相似度。

2.3 本體綜合評價值的計算

根據上文所提出的用于本體排序的評價方法，本體的內容分析方法可由本體的主題相似度、上下文相關度來表示。對本體的綜合評價值計算為

ranking(Oi)=w1×relt(k，Oi)+w2×relc(Oi)(5)

其中:w1和w2分別為主題相似度與上下文相關度的權值，可以對w1和w2進行調整，使其能夠滿足最終要求。

3 實驗結果與分析

大量對語義Web中本體排序問題的研究只是停留在研究水平，并沒有成熟的評價標準。本文采用文獻[7]中的評價方法，使用Swoogle的排序結果做對比實驗來評價本文的算法。以“Person”作為輸入關鍵詞，可得Swoogle的排序結果如下所示(去掉失效鏈接后的結果):

a. http://xmlns.com/foaf/0.1/index.rdf

b. http://rdfs.org/sioc/ns

c. http://inferenceweb.stanford.edu/2004/07/iw.owl

d. http://swrc.ontoware.org/ontology

e. http://morpheus.cs.umbc.edu/aks1/ontosem.owl

f. http://swrc.ontoware.org/ontology/portal

g. http://inferenceweb.org/2.0/pmlprovenance.owl

h. http://www.aktors.org/ontology/portal

i. http://ebiquity.umbc.edu/ontology/publication.owl

j. http://ebiquity.umbc.edu/ontology/person.owl

k. http://lsdis.cs.uga.edu/projects/semdis/opus

l. http://swrc.ontoware.org/ontology/ontoware

m.http://ebiquity.umbc.edu/ontology/event.owl

以Swoogle所得到的結果作為輸入，可得使用本文算法的排序結果以及人類主觀排序結果，如表1所示。本文選取Swoogle中符合人類主觀排序結果的前10個進行分析，并對本文中算法取w1=0.7，w2=0.3;w1=0.8，w2=0.2;w1=0.85，w2=0.15三組數據進行比較。

表1 排序結果的比較

主觀結果Swoogle結果w1=0.8w2=0.2w1=0.7w2=0.3w1=0.85w2=0.15主觀結果Swoogle結果w1=0.8w2=0.2w1=0.7w2=0.3w1=0.85w2=0.15

1134368232

937678910109

34424210111

566761011888

779910412555

使用皮爾森相關系數，分別對表1中Swoogle和本文排序結果與人類主觀排序結果之間的關系進行評價，得出皮爾森相關系數如表2所示。皮爾森相關系數越接近于1，說明所得到的結果與主觀排序結果之間越符合線性關系。

表2 不同排序方法的皮爾森相關系數比較

方法Swooglew1=0.8w2=0.2w1=0.7w2=0.3w1=0.85w2=0.15

皮爾森相關系數0.2700.7580.7210.745

根據表2所示，使用本文方法所得的結果與人類主觀排序結果比較的皮爾森相關系數的絕對值要明顯大于用Swoogle所得的結果，用本文方法所得的皮爾森相關系數更接近1，因此本文提出的方法與主觀的方法得到的結果更相近。根據表2結果所示，當取權值為w1=0.8，w2=0.2時，所得的結果要略優于其他取值，因此一般選取w1=0.8，w2=0.2。

4 結束語

排序問題是語義Web中的一個重要的研究課題，對搜索引擎而言具有很高的研究價值。對語義Web中的本體進行排序，有助于提高本體的重用度并節省了開發的消耗。本體的內容分析方法不局限于本體之間的鏈接關系，還為不同的本體主題詞和不同的描述信息提供了不同的權值，使得排序結果能夠更加符合人類的主觀結果，提高本體排序的準確度。

筆者未來的工作主要包括:對本體的結構和內容信息進行更進一步的研究，得出多關鍵詞搜索對本體評價值的影響;對本體的主題詞集抽取算法進行進一步的完善，得到一種能夠幫助用戶快速理解本體的新方法。

參考文獻:

[1]張祥，瞿裕忠. 語義網中的排序問題[J].計算機科學，2008，35(2):196-200.

[2]FININ T， SACHS J， PARR C. Finding data， knowledge， and answers on the semantic Web[C]//Proc of the 20th International FLAIRS Conference. [S.l.]: AAAI Press，2007: 2-7.

[3]ALANI H， BREWSTER C， SHADBOLT N. Ranking ontologies with AKTiveRank[C]//Proc of the 5th International Semantic Web Conference. Berlin: Springer，2006: 5-9.

[4]TARTIR S， ARPINAR I B. Ontology evaluation and ranking using OntoQA[C]//Proc of the 1st IEEE International Conference on Semantic Computing. Washington DC: IEEE Computer Society， 2007: 185-192.

[5]徐德智，鄭春卉，PASSI K. 基于SUMO的概念語義相似度研究[J].計算機應用，2006，26(1):180-183.

[6]WU Zhibiao， PALMER M. Verbs semantics and lexical selection[C]//Proc of the 32nd Conference on Association for Computational Linguistics. Morristown: Association for Computational Linguistics， 1994: 133-138.

[7]RAJAPAKSHA S K， KODAGODA N. Internal structure and semantic Web link structure based ontology ranking[C]//Proc of the 4th International Conference on Information and Automation for Sustainability.2008: 86-90.