基于維基百科的語義相關(guān)度算法研究綜述

景雪芹，徐建良

（中國海洋大學(xué) 信息科學(xué)與工程學(xué)院，山東 青島 266100）

0 引言

相關(guān)度是指事物之間相關(guān)聯(lián)的程度，而語義相關(guān)度是指概念之間相關(guān)聯(lián)的程度。計(jì)算語義相關(guān)度是非常復(fù)雜的，因?yàn)樗枰玫截S富的語義知識，也要對不同的關(guān)系給出不同的權(quán)重值。在語義信息處理的相關(guān)研究中，很多研究者利用語料庫的相關(guān)統(tǒng)計(jì)信息獲取語義相關(guān)度信息，也有研究者利用WordNet等語義網(wǎng)絡(luò)來衡量詞或者概念之間的語義相關(guān)度。近年來，很多研究都證明維基百科是計(jì)算語義相關(guān)度的一個好資源。

最先利用維基百科進(jìn)行語義相關(guān)度研究的是STRUBLE M和 PONZETTO S P[1]，他們把應(yīng)用在 Word-Net上效果比較好的一些經(jīng)典算法應(yīng)用到維基百科中，實(shí)驗(yàn)結(jié)果表明，在大數(shù)據(jù)集上，在維基百科的效果要好于在 WordNet的效果。隨后，ZESCH J和 GUREVYC I[2]對維基百科的分類圖和文檔圖進(jìn)行了圖論分析并與GermaNet進(jìn)行了比較，同樣證明了維基百科可以作為一種語義知識資源代替一些傳統(tǒng)的語義網(wǎng)絡(luò)，將自然語言處理的一些經(jīng)典算法應(yīng)用到維基百科中是可行的。

本文對維基百科進(jìn)行了研究，對利用維基百科計(jì)算語義相關(guān)度的算法進(jìn)行了調(diào)研，最后總結(jié)了幾種典型算法的特點(diǎn)并進(jìn)行了分類。

1 維基百科

維基百科于2001年被發(fā)起，現(xiàn)在，它涵蓋了藝術(shù)、地理、歷史、自然科學(xué)等領(lǐng)域，包括了200多種語言的版本，注冊用戶達(dá)5000多萬。它作為互聯(lián)網(wǎng)上最大的最廣泛使用的免費(fèi)的百科全書，擁有超過百萬的解釋頁面，更新速度快。本文從以下兩方面對維基百科進(jìn)行系統(tǒng)的介紹。

1.1 維基百科中的條目

條目，即頁面，是維基百科基本的組成單位。為了提高一致性，條目的編輯需遵循一系列的編輯規(guī)則，其主要的規(guī)則有以下6條[3]：

（1）一個條目只描述一個概念，一個概念只有一個條目與之對應(yīng)；

（2）條目的標(biāo)題是簡潔的短語，類似于傳統(tǒng)敘詞表中敘詞；

（3）同義詞通過重定向鏈接連接；

（4）消歧義條目為用戶提供可選擇的多種語義；

（5）條目的開始是對主題的簡單介紹，第一句定義了概念及其類型；

（6）條目中有超鏈接，這些超鏈接表示了該條目與其他條目之間的關(guān)系。

根據(jù)這些編輯規(guī)則，將維基百科中的條目分為：分類條目、重定向條目、消歧義條目以及解釋條目。其中分類條目是維基百科中的分類索引，重定向條目和消歧義條目對應(yīng)規(guī)則（3）和（4），解釋條目對應(yīng)編輯規(guī)則（1）。

1.2 維基百科中的超鏈接

普通的語料庫和網(wǎng)絡(luò)語料最大的不同點(diǎn)就是網(wǎng)絡(luò)語料庫具有超鏈接，而超鏈接提供了一個頁面跳轉(zhuǎn)到另一個頁面的功能。維基百科就是典型的網(wǎng)絡(luò)語料庫。維基百科鏈接結(jié)構(gòu)密集，平均每個條目擁有20個超鏈接，而且超鏈接還蘊(yùn)含了豐富的語義信息。一般按照超鏈接的方向把超鏈接分為兩大類：一類是前向鏈接，另一類是后向鏈接。如圖1所示，前向鏈接是指源頁面連接另外一個頁面的鏈接，后向鏈接是指一個頁面連接源頁面的鏈接。

圖1 前向鏈接和后向鏈接

除此之外，也可以根據(jù)超鏈接所連接的頁面類型進(jìn)行分類，分別為語言間的鏈接（Interlanguage Links）、分類與子類之間的鏈接（Category to Subcategory）、分類與解釋頁面之間的鏈接（Category to Article）、重定向頁面（Redirect to Article）與解釋頁面之間的鏈接 （Article to Article）。根據(jù)這種分類可以初步判斷錨文本之間的關(guān)系（錨文本是超鏈接的文本部分，用戶通過點(diǎn)擊這個文本就可到達(dá)目標(biāo)頁面）。

2 基于維基百科的語義相關(guān)度算法

2.1 基于統(tǒng)計(jì)學(xué)的語義相關(guān)度算法

2.1.1 詞匯共現(xiàn)法

詞匯共現(xiàn)法是基于統(tǒng)計(jì)學(xué)的方法來計(jì)算語義相關(guān)度的經(jīng)典方法。由于詞匯共現(xiàn)在敘詞表構(gòu)建的研究中已經(jīng)被廣泛地證明是有效的，因此把它應(yīng)用到維基百科中可能也是可行的。兩個詞匯的詞匯同現(xiàn)率可以用下面的公式進(jìn)行粗略的定義：

其中，Dt1是包含t1的文檔的集合。為了度量兩個詞的相關(guān)度，該方法使用了包含這兩個詞的文檔數(shù)。具體的比較經(jīng)典的方法有共現(xiàn)文檔數(shù)方法 （SD）[4]、文字覆蓋法（TO）。

共現(xiàn)文檔數(shù)就是在一個較大的語料庫中利用詞出現(xiàn)的文檔數(shù)，如Jaccard公式：

其中，dc（i）、dc（j）分別表示包含鏈接 i、j的文檔數(shù)，dc（i&j）表示既包含 i也包含 j的文檔數(shù)。

文字覆蓋法就是通過在2個詞各自的定義文本中共同出現(xiàn)的文本來計(jì)算相關(guān)度。比較經(jīng)典的算法有Lesk算法[5]。在維基百科中，可以尋找在解釋文檔中的共現(xiàn)詞并利用式（3）來計(jì)算：

其中，n表示文檔ta和 tb中都出現(xiàn)的文本片段 （可能是一個詞或連續(xù)的多個詞），mn表示每個片段的詞數(shù)，length（ta）和 length（tb）表示兩個文檔的總詞數(shù)。

2.1.2 鏈接共現(xiàn)法

盡管上文中的詞匯共現(xiàn)法已被證明是有效的，但是由于語義分析的復(fù)雜性，自然語言處理仍然存在很多準(zhǔn)確性的問題。所以有人提出了鏈接共現(xiàn)的方法，這種方法只使用語義網(wǎng)絡(luò)中的鏈接來避免自然語言處理中的準(zhǔn)確率的問題。因?yàn)檎Z義網(wǎng)絡(luò)是一個概念與鏈接的集合，所以使用鏈接同現(xiàn)法是有意義的。具體的公式和詞匯共現(xiàn)的公式的道理是一樣的，不同點(diǎn)只是使用文檔的鏈接代替詞匯。

比較經(jīng)典的鏈接共現(xiàn)的方法是GABRILOVICH E[6]提出的TF-IDF的方法。TF-IDF使用了兩個度量值：TF（Term Frequency）詞匯頻率和IDF （InverseDocument Frequency）后向文檔頻率。這種方法是通過計(jì)算維基百科頁面中鏈接的權(quán)值得到相應(yīng)概念的向量，然后通過比較概念向量來計(jì)算兩個概念的相關(guān)度。一個文檔中鏈接的權(quán)值的計(jì)算公式如下：

其中，tf（l，d）表示在文檔 d 中鏈接 l出現(xiàn)的次數(shù)，N 表示維基百科中文檔的數(shù)量，df（l）是包含鏈接l的文檔的數(shù)量。簡單來說，權(quán)值隨著文檔d中鏈接出現(xiàn)的頻率遞增。但是總的來說，因?yàn)槊總€維基百科的頁面都有自己的URL而且都對應(yīng)了一個概念，所以計(jì)算兩個鏈接的相關(guān)度等同于計(jì)算兩個概念的相關(guān)度。

2.2 基于維基百科路徑的語義相關(guān)度算法

維基百科網(wǎng)絡(luò)詞匯集，是一個由條目和超鏈接組成的集合，它的結(jié)構(gòu)是一個有循環(huán)的圖，概念就是圖的節(jié)點(diǎn)，超鏈接就是圖的邊，所以它就可以用一個圖的形式來表示：G={V，E}（V：維基百科中的條目/概念集合，E：維基百科中超鏈接的集合）。在考慮如何計(jì)算任意一個條目對vi和vj之間的相關(guān)度時，NAKAYAMA K等人[7]假設(shè)影響它們之間相關(guān)度主要有以下兩個因素：

（1）從條目 vi到條目 vj的路徑的數(shù)量；

（2）每一條從條目 vi到條目 vj的路徑長度。

如果有很多路徑可以從條目vi到達(dá)條目vj，那么它們之間的相關(guān)度相對較強(qiáng)。另外，兩個條目之間的相關(guān)度還受路徑長短的影響。換句話說，如果在圖G中從條目vi到達(dá)條目vj的路徑相對較短，那么它們之間的相關(guān)度要高于相對較長的。因此，如果從條目vi到達(dá)條目vj的所有路徑為P={p1，p2，...，pn}，NAKAYAMA K將它們之間的 PF（Path Frequency）定義為：

其中，d（lenpk）是一個以路徑pk的長度為變量的單調(diào)遞增函數(shù)，例如對數(shù)函數(shù)的單調(diào)遞增函數(shù)都可用作函數(shù)d（lenpk）。

而且根據(jù)統(tǒng)計(jì)發(fā)現(xiàn)，在計(jì)算相關(guān)度時必須考慮維基百科的鏈接結(jié)構(gòu)的分布特征，例如這樣一種條目，有很多條目都擁有到達(dá)該條目的超鏈接。如果只是用PF的方法，那么這類條目會與很多條目具有較強(qiáng)的相關(guān)度。然而通常情況下該類條目對應(yīng)的概念是普通的比較綜合的大眾的概念。因此，必須考慮這類條目的后向鏈接，NAKAYAMA K定義了 IBF（Inversed Backward Frequency），IBF與 PF組合形成了 PF-IBF方法：

其中，N表示所有的條目數(shù)，bf（vj）表示條目 vj的后向鏈接數(shù)。從上文的PF-IBF公式可以看出，如果條目vi和vj條目通過前向或后向鏈接相連并且vj沒有后向鏈接，則相應(yīng)的pfibf值就會很高，概念之間的相關(guān)度相對較大。

3 結(jié)論

維基百科作為世界上最大的在線百科全書，蘊(yùn)含了豐富的語義知識。本文總結(jié)了利用維基百科完成復(fù)雜的語義相關(guān)度計(jì)算的方法，使用這些算法可以更容易地完成對維基百科的知識挖掘和完成文本分類等工作。但目前，無論是對維基百科使用的研究，還是維基百科相關(guān)算法研究，我國都遠(yuǎn)遠(yuǎn)少于國外。今后，隨著維基百科的優(yōu)勢顯現(xiàn)，相信會有更多的國內(nèi)專家關(guān)注維基百科，維基百科的相關(guān)技術(shù)也會更加成熟。

[1]STRUBE M，PONZETTO S P.WikiRelate! Computing semantic relatednessusing Wikipedia [C].AAAI，2006，6：1419-1424.

[2]ZESCH T，GUREVYCH I.Analysis of the Wikipedia category graph for NLP applications[C].Proceedingsofthe TextGraphs-2 Workshop （NAACL-HLT 2007），2007：1-8.

[3]MEDELYAN O，MILNE D，LEGG C，et al.Mining meaning from Wikipedia[J].International Journal of Human-Computer Studies，2009，67（9）：716-754.

[4]BANERJEE S，PEDERSEN T.Extended gloss overlaps as a measure of semantic relatedness[C].IJCAI，2003，3：805-810.

[5]LESK M.Automaticsensedisambiguation usingmachine readable dictionaries：how to tell a pine cone from an ice cream cone[C].Proceedings of the 5th Annual International Conference on Systems Documentation，ACM，1986：24-26.

[6]GABRILOVICH E，MARKOVITCH S.Computing semantic relatedness using Wikipedia-based explicit semantic analysis[C].JCAI，2007，7：1606-1611.

[7]NAKAYAMA K，HARA T，NISHIO S.Wikipedia mining for an association Web thesaurus construction[M].Web Information Systems Engineering-WISE 2007，Springer Berlin Heidelberg，2007： 322-334.