結合編輯距離和Google距離的語義標注方法

摘 要:提出了一種在領域本體指導下對網頁進行語義標注的方法。該方法利用編輯距離和Google距離從詞語的語法和語義兩方面綜合度量詞匯與本體概念之間的語義相關度，從而在網頁與本體之間建立映射關系。此外，對網頁進行語義標注后，利用標注結果對本體進行有效擴充，使本體更趨于領域化。實驗結果表明該方法是行之有效的。

關鍵詞:語義網; 本體; 語義標注; 編輯距離; Google距離

中圖分類號:TP391

文獻標志碼:A

文章編號:1001-3695(2010)02-0555-03

doi:10.3969/j.issn.1001-3695.2010.02.042

Approach for semantic annotation based on editdistance and Google distance

ZHANG Yu-fang， AI Dong-mei， HUANG Tao， XIONG Zhong-yang

(College of Computer， Chongqing University， Chongqing 400044， China)

Abstract:This paper presented a methodology for semantic annotation of Web pages with domain-specific ontology. This new approach used the edit distance and the Google distance to measure the relativity between words and ontology concepts in terms of syntax and semantic， so as to link Web pages with ontology concepts. In addition， it enriched the ontology with the results of annotation to make the ontology greatly cover the domain knowledge. The experimental result shows that this method is significantly effective.

Key words:semantic Web; ontology; semantic annotation; edit distance; Google distance

語義網是當前Web的延伸，它提供了一個通用的框架，對現有Web進行擴展。其核心思想是通過增加語義信息，讓計算機參與到自動處理Web信息的過程，改變它在Web中的角色，使其可理解Web上的信息，使Web應用具有一定的智能，從而實現信息的自動化和智能化處理[1]。在語義網上，信息通過本體以及與本體一致的元數據以結構化的形式描述，并定義了良好的語義，使計算機能夠理解網頁內容，從而實現計算機之間的智能交互，讓互聯網真正成為一個全球化的信息共享和智能服務平臺。

語義標注是通過本體描述網頁中的概念或概念實例，為網頁添加語義信息的。它在現有Web的基礎上增加語義，產生語義元數據，輔助計算機從語義層次上處理信息。通過語義標注的作用，可將Web的狀態從機器可讀提高到機器可理解，這是發展和實現語義網的基礎。因此，通過對網頁進行語義標注，為網頁添加語義元數據、提供機器可處理的語義在語義網的發展中起著至關重要的作用。

本文在傳統語義標注的基礎上引入了機器學習中的概念學習思想，并結合編輯距離[2]、Google距離[3]等，提出了一種新的語義標注方法。

1 本體和語義標注簡述

1.1 本體和語義標注

在Berners-Lee等人[1]提出的語義網模型中，本體層是最核心的組成部分。Studer 等人[4]在進行深入研究之后，給出了本體的定義:本體是共享概念模型的明確的形式化規范說明。這包含四層含義，即概念模型(conceptualization)、明確(explicit)、形式化(formal)和共享(share)。這表明本體是一種能在語義和知識層次上描述系統的概念模型，通過獲取某個領域內的共有知識，確定該領域內共同認可的詞匯，從不同層次的形式化模型上給出領域內的概念和概念間相互關系的明確定義，幫助不同主體之間進行知識交換，使各個主體對該領域的概念達成一致的理解，實現知識的共享和重用。

語義網中的信息是結構化的，允許人們將領域內的知識表示成概念、概念屬性以及概念之間存在的各種關系。當信息用本體進行語義標注后，機器才能理解其含義，從而可以自動地完成互聯網上的信息收集和集成。因此，本體不僅是語義網的核心，也是語義標注的基礎。完善本體的構造，進行本體擴充[5]也是語義標注的目的。

語義標注即在領域本體的指導下，為網頁添加語義元數據的過程，也就是網頁中的實體與其語義描述相關聯的過程。語義標注的目的不僅在于讓人更好地理解Web上的信息，更重要的是讓機器解釋和理解信息。通過語義標注，建立起Web資源與元數據之間的橋梁，對Web文檔的內容進行擴充，使Web資源以更加形式化的方式表示出來。

由于語義標注通常是建立在領域本體的基礎上，為文檔中的知識及其在領域中的語義提供精確的描述，使本體實例化，可通過語義標注完善本體，有效地進行本體擴充，使本體盡可能多地涵蓋該領域的概念、屬性和關系。同時，本體的層次結構也可使語義標注模式充分的形式化，有助于約束其結構，減少標注過程中的歧義和錯誤，輔助人們對標注本身所蘊涵的語義達成一致的認識。

1.2 傳統語義標注方法

傳統的語義標注方法主要分為手動標注、半自動標注和自動標注三類。手動標注方法大多集中在建立標注及分享標注的工具上。這方面考慮因素主要有標注的表達、有效分享標注的設計以及對標注的評估等[6]，但是手動標注存在著效率低、標注的一致性難以保證等問題。半自動語義標注是利用詞匯語義分析對網頁進行標注的。利用信息抽取(information extraction，IE)技術抽取Web頁面中的實例，在詞匯抽取和分析技術的基礎上，建立待標注詞匯集合與本體概念類別之間的映射關系[7]。由于當前很少有IE是基于本體實現的，這類基于IE技術的半自動語義標注方法在提取到數據后就采用啟發式方法對抽取結果進行后期處理和映射到本體[8]，而從IE結果到本體這個語義映射過程需要大量人工干預，降低了自動化程度。自動語義標注主要利用機器學習的方法從統計學的角度為網頁建立標注。

在對語義標注系統的研究中，使用得較多的方法是采用半自動技術完成，目前國外已經存在一些標注工具[9]，如KIM、GATE、Onto_mat、MnM、SHOE、Annotea、Annozilla、SMORE、Yawas、Melita、Briefing Associate、Semantic Word、Semantic Markup。現有工具普遍存在以下的不足[10]:多數工具不支持本體詞匯擴充，這與語義標注的應用環境相悖;語義標注過程中本體查詢、輔助推理支持以及元數據產生的自動化程度還不夠。

標注效果的好壞很大程度上取決于標注過程中所使用的方法，不同的標注平臺間可以通過其所使用的方法來進行區分。因此，從這個角度來看，語義標注方法主要有兩大類，即基于模式的方法和基于機器學習的方法。一般情況下，基于機器學習的標注方法效果優于基于模式方法的標注。

2 基于編輯距離和Google距離的語義標注方法

2.1 基于領域本體的標注流程

本文采用的語義標注方法流程如圖1所示。

標注過程主要分為以下三部分:

a)網頁搜集和預處理。其包括網絡爬蟲搜集網頁、網頁存儲到數據庫、GATE(general architecture for text enginee-ring)[11]分句、分詞、詞性標注等處理，詞匯過濾處理，并將預處理結果存儲到數據庫中。

b)本體預處理。其包括本體獲取、本體轉換為三元組(subject， predicate， object)形式，從三元組中提取類、實例、屬性、關系，并存儲到關系數據庫中。

c)語義標注。將待標注詞匯與本體中的概念計算其編輯距離和Google距離，獲得綜合語義相關度，并通過排序和設定閾值進行取舍。再通過人工驗證，將標注結果加入到本體中，對本體的概念、屬性及關系進行擴充;對于舍棄掉的詞匯，填充到詞匯過濾集。

2.2 編輯距離和Google距離

本文主要從編輯距離和Google距離兩方面來計算文檔詞匯與本體概念間的相關度。其中，編輯距離是從詞匯的語法構成上來計算詞匯間的相似程度，而Google距離是從語義的角度反映詞匯間的關聯程度。

2.2.1 編輯距離

編輯距離最早由俄國科學家Levenshtein提出，又稱Levenshtein distance，指兩個字符串之間，由一個轉成另一個所需的最少編輯操作代價。這里的編輯操作包括替換、插入和刪除。

將兩個詞x和y的編輯距離用EDS(x，y)表示，那么EDS(x，y)的取值為[0，∞]。兩個詞語之間的編輯距離常用動態規劃方法來計算，假設詞語x是一個長度為m的字符串x1x2…xm，y是一個長度為n的字符串y1y2…yn，那么詞語x到y的編輯距離即將詞語X轉換為Y的最簡便的轉換序列的代價，可遞歸地表示為[12]

ED(x，y)=ED(Xm，Yn)=

minED(Xm-1，Yn-1)+Cs(Xm，Yn)ED(Xm-1，Yn)+Cd(Xm，ε)ED(Xm，Yn-1)+Ci(ε，Yn)(1)

其中:ED(Xm-1，Yn-1)表示編輯(替換或刪除或插入)x的前m-1個字符，y的前n-1個字符的最小代價;Cs(Xm，Yn)表示將x的第m個字符替換為Y的第n個字符的代價;Cd(Xm，ε)表示將x的第m個字符刪除的代價;Ci(ε，Yn)表示在x的第m個字符后插入y的第n個字符的代價。

將上面的編輯距離歸一化處理后，得到的歸一化編輯距離(normalized edit distance):

NED(x，y)=ED(x，y)max{m，n}(2)

顯然，當x和y完全相同時，NED=0;當x與y完全不相同時，NED=1，即NED(x，y)∈[0，1]。

歸一化編輯距離反映了兩個詞間靠近或相似的程度。距離越大的兩個詞被認為越不相似，反之則越靠近。將歸一化編輯距離轉換為詞語間的語法相似度，可用下式表示:

sim(x，y)=1-NED(x，y)(3)

2.2.2 Google距離

在Google中輸入詞匯進行查詢，利用Google返回的匹配記錄數來計算兩個概念間的語義距離，稱為Google距離，用NGD(normalized Google distance)表示，它是從語義上分析兩個詞語的相似性的。任意兩個詞x和y的Google距離NGD(x，y)可表示為

NGD(x，y)=G(x，y)-min(G(x)，G(y))max(G(x)，G(y))=

max{log f(x)，log f(y)}-log f(x，y)log N-min{log f(x)，log f(y)}(4)

其中:f(x)表示在Google中搜索x時返回的匹配記錄數;f(y)表示在Google中搜索y時返回的匹配記錄數;f(x，y)表示在Google中搜索詞組(x，y)時返回的匹配記錄數;N表示Google索引的Web頁面數。NGD(x，y)是詞條x和y共現的對稱的條件概率:假設給定一個頁面含有x(或y)，那么NGD(x，y)就表示這個頁面同時含有y(或x)的概率。Google距離有以下幾個性質:

a)NGD的取值范圍為[0，∞]。如果x=y或x≠y，而f(x)=f(y)=f(x，y)>0，那么NGD(x，y)=0。這說明詞匯x和y在Google中的語義是相同的。如果f(x)=0，那么對于任何搜索詞條y都有f(x，y)=0，即NGD(x，y)=∞∞。

b)通常情況，NGD為非負數且對任意x有NGD(x，x)=0。對任意x，y有NGD(x，y)=NGD(y，x)，它們是相互對稱的。

c)概念間的語義距離越大，則相似度越小，表明這兩個概念的相關度越小。

由Google距離可知，詞語與其本身的距離為0;語義距離為0時，相似度為1;語義距離為無窮大時，相似度為0。

對于詞語x和y，語義距離為NGD(x，y)，Google相關度(Google relevancy)記為GR(x，y)，那么可定義一個滿足以上條件的轉換關系:

GR(x，y)=λNGD(x，y)+λ(5)

其中:λ是一個可調節的參數，且λ∈(0，1)。

本文將歸一化編輯距離和Google相關度結合起來衡量兩個詞匯間的相關程度，表示如下:

weight(x，y)=α×sim(x，y)+β×GR(x，y)(6)

其中:α+β=1。

3 實驗

3.1 數據集

3.1.1 領域本體

本實驗采用http://www.w3.org提供的wine本體，這是一個OWL DL(Web ontology language description logic)本體，涵蓋了wine領域內定義的類、屬性、實例以及實例間關系。由于本體是對共享概念模型的明確的形式化規范說明，對概念和屬性的定義用語都是精確化和概念化的，且大多采用名詞形式進行表述。

實驗先對本體進行預處理，將本體從OWL形式轉換為形為(subject， predicate， object)的三元組形式。再將三元組按照概念、實例、關系進行分解，并存儲到數據庫中，以提高語義標注和本體擴充的效率。

3.1.2 待標注頁面

待標注頁面來源于互聯網，用爬蟲工具下載與wine相關的英文網頁，共300篇。由于網頁內包含了很多導航欄、廣告、圖像等噪聲信息，需要在下載網頁后進行網頁預處理，主要包括去除HTML標簽、文本編碼轉換、噪聲信息剔除、使用GATE的Splitter、Tokeniser、POSTagger模塊進行分句、分詞、詞性標注預處理。從預處理結果中提取名詞，經詞匯過濾表篩選后形成待標注詞匯列表，并存儲到數據庫中。

3.2 實驗方法

在本實驗中，將從抓取的頁面中隨機抽取30篇作為訓練集，15篇作為測試集。先利用編輯距離和Google距離的綜合權重進行預標注，并根據設定的閾值和人工判斷的方式進行取舍，其標注結果擴充到領域本體中，其余的作為反例添加到文檔詞匯過濾表中。在本體擴充前后分別對測試集中的15篇網頁進行測試，并給出了不同條件下的標注結果。

3.3 實驗結果及分析

表1給出了不同實驗條件下的結果，分為以下幾種情況:只用編輯距離與本體概念計算權重進行標注;只用Google距離與本體概念計算權重進行標注;結合編輯距離和Google距離與本體概念計算綜合權重進行標注。

對于語義標注，傳統的評價標準是通過人工判斷標注準確率P、召回率R和F1值進行測評，其定義如下:

P=標注正確的詞匯數已標注的總詞匯數×100%，R=標注正確的詞匯數待標注的總詞匯數×100%

F1=2×P×RP+R×100%

表1 本體擴充前后的標注性能比較

標注方法PRF1

擴充前基于編輯距離標注基于Google距離標注編輯距離+Google距離標注0.360 70.272 70.378 30.372 70.281 80.390 90.366 60.277 20.384 5

擴充后基于編輯距離標注基于Google距離標注編輯距離+Google距離標注0.668 60.513 20.686 20.690 90.530 30.709 00.679 60.521 60.697 5

由以上結果分析可知:

a)利用編輯距離和Google距離與擴充后的本體概念計算綜合權重進行語義標注的方法整體性能上最優，其F1平均值最高，為69.75%，準確率也最高，達到68.62%，這與預期效果是一致的。

b)對于僅用編輯距離或Google距離來確定詞匯與本體概念的相關度方法，都具有各自的優勢和不足。編輯距離僅能從詞匯的語法構成上來獲得與本體相關的概念和實例，執行效率較高，而通過Google距離計算詞匯相關度的標注方法具備一定的語義分析和暗示能力。

從表1中的數據可以看到，單獨用Google距離標注的方法的各測評指標值都最低。經過分析發現，這主要是由于用Google距離計算語義相關度的基礎是整個互聯網，而信息量龐大的互聯網上存在太多的不相干信息，對計算兩個詞語之間的語義相關度存在干擾影響。所以，將編輯距離和Google距離有機結合，從詞語的語法構成和語義兩方面綜合度量詞語間的語義相關度來進行標注，能取得更好的效果。

c)從實驗結果可知，將編輯距離與Google距離相結合后，與領域本體越相關的詞匯，語義權重越大。而對本體進行有效擴充，增加反饋的過程，使本體盡可能多地包含本領域的概念、屬性和關系，不但可使本體更具有領域性，更廣泛地涵蓋該領域的知識，而且可使標注的準確率、召回率和F1值都明顯提高，標注效率也得到改善，與語義標注就是本體擴充過程的實質也更加貼切。

4 結束語

本文給出了在領域本體下，利用編輯距離和Google距離計算語義相關度以進行語義標注的方法。通過對實驗結果的分析表明，該標注方法是切實有效的。網頁進行語義標注后得到的數據結構和語義可輔助Web發揮其巨大的潛能，不僅將隱含的語義信息顯式地表達出來，有助于機器理解和處理，而且也反映了網頁內容與領域相關類別的關聯情況，是實現智能檢