摘 要： 在總結(jié)維基百科特點(diǎn)的基礎(chǔ)上，調(diào)研了國內(nèi)外使用維基百科計(jì)算語義相關(guān)度的算法。根據(jù)這些算法的特點(diǎn)，對(duì)其進(jìn)行了系統(tǒng)的分類，并列舉了每個(gè)分類下的經(jīng)典算法。
關(guān)鍵詞： 維基百科；相關(guān)度；算法
0 引言
相關(guān)度是指事物之間相關(guān)聯(lián)的程度，而語義相關(guān)度是指概念之間相關(guān)聯(lián)的程度。計(jì)算語義相關(guān)度是非常復(fù)雜的，因?yàn)樗枰玫截S富的語義知識(shí)，也要對(duì)不同的關(guān)系給出不同的權(quán)重值。在語義信息處理的相關(guān)研究中，很多研究者利用語料庫的相關(guān)統(tǒng)計(jì)信息獲取語義相關(guān)度信息，也有研究者利用WordNet等語義網(wǎng)絡(luò)來衡量詞或者概念之間的語義相關(guān)度。近年來，很多研究都證明維基百科是計(jì)算語義相關(guān)度的一個(gè)好資源。
最先利用維基百科進(jìn)行語義相關(guān)度研究的是STRUBLE M和PONZETTO S P[1]，他們把應(yīng)用在WordNet上效果比較好的一些經(jīng)典算法應(yīng)用到維基百科中，實(shí)驗(yàn)結(jié)果表明，在大數(shù)據(jù)集上，在維基百科的效果要好于在WordNet的效果。隨后，ZESCH J和GUREVYC I[2]對(duì)維基百科的分類圖和文檔圖進(jìn)行了圖論分析并與GermaNet進(jìn)行了比較，同樣證明了維基百科可以作為一種語義知識(shí)資源代替一些傳統(tǒng)的語義網(wǎng)絡(luò)，將自然語言處理的一些經(jīng)典算法應(yīng)用到維基百科中是可行的。
本文對(duì)維基百科進(jìn)行了研究，對(duì)利用維基百科計(jì)算語義相關(guān)度的算法進(jìn)行了調(diào)研，最后總結(jié)了幾種典型算法的特點(diǎn)并進(jìn)行了分類。
1 維基百科
維基百科于2001年被發(fā)起，現(xiàn)在，它涵蓋了藝術(shù)、地理、歷史、自然科學(xué)等領(lǐng)域，包括了200多種語言的版本，注冊(cè)用戶達(dá)5000多萬。它作為互聯(lián)網(wǎng)上最大的最廣泛使用的免費(fèi)的百科全書，擁有超過百萬的解釋頁面，更新速度快。本文從以下兩方面對(duì)維基百科進(jìn)行系統(tǒng)的介紹。
1.1 維基百科中的條目
條目，即頁面，是維基百科基本的組成單位。為了提高一致性，條目的編輯需遵循一系列的編輯規(guī)則，其主要的規(guī)則有以下6條[3]：
?。?）一個(gè)條目只描述一個(gè)概念，一個(gè)概念只有一個(gè)條目與之對(duì)應(yīng)；
（2）條目的標(biāo)題是簡潔的短語，類似于傳統(tǒng)敘詞表中敘詞；
?。?）同義詞通過重定向鏈接連接；
?。?）消歧義條目為用戶提供可選擇的多種語義；
?。?）條目的開始是對(duì)主題的簡單介紹，第一句定義了概念及其類型；
?。?）條目中有超鏈接，這些超鏈接表示了該條目與其他條目之間的關(guān)系。
根據(jù)這些編輯規(guī)則，將維基百科中的條目分為：分類條目、重定向條目、消歧義條目以及解釋條目。其中分類條目是維基百科中的分類索引，重定向條目和消歧義條目對(duì)應(yīng)規(guī)則（3）和（4），解釋條目對(duì)應(yīng)編輯規(guī)則（1）。
1.2 維基百科中的超鏈接
普通的語料庫和網(wǎng)絡(luò)語料最大的不同點(diǎn)就是網(wǎng)絡(luò)語料庫具有超鏈接，而超鏈接提供了一個(gè)頁面跳轉(zhuǎn)到另一個(gè)頁面的功能。維基百科就是典型的網(wǎng)絡(luò)語料庫。維基百科鏈接結(jié)構(gòu)密集，平均每個(gè)條目擁有20個(gè)超鏈接，而且超鏈接還蘊(yùn)含了豐富的語義信息。一般按照超鏈接的方向把超鏈接分為兩大類：一類是前向鏈接，另一類是后向鏈接。如圖1所示，前向鏈接是指源頁面連接另外一個(gè)頁面的鏈接，后向鏈接是指一個(gè)頁面連接源頁面的鏈接。
除此之外，也可以根據(jù)超鏈接所連接的頁面類型進(jìn)行分類，分別為語言間的鏈接（Interlanguage Links）、分類與子類之間的鏈接（Category to Subcategory）、分類與解釋頁面之間的鏈接（Category to Article）、重定向頁面（Redirect to Article）與解釋頁面之間的鏈接（Article to Article）。根據(jù)這種分類可以初步判斷錨文本之間的關(guān)系（錨文本是超鏈接的文本部分，用戶通過點(diǎn)擊這個(gè)文本就可到達(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)用到維基百科中可能也是可行的。兩個(gè)詞匯的詞匯同現(xiàn)率可以用下面的公式進(jìn)行粗略的定義：
其中，D是包含t1的文檔的集合。為了度量兩個(gè)詞的相關(guān)度，該方法使用了包含這兩個(gè)詞的文檔數(shù)。具體的比較經(jīng)典的方法有共現(xiàn)文檔數(shù)方法（SD）[4]、文字覆蓋法（TO）。
共現(xiàn)文檔數(shù)就是在一個(gè)較大的語料庫中利用詞出現(xiàn)的文檔數(shù)，如Jaccard公式：
其中，dc（i）、dc（j）分別表示包含鏈接i、j的文檔數(shù)，dc（i&j）表示既包含i也包含j的文檔數(shù)。
文字覆蓋法就是通過在2個(gè)詞各自的定義文本中共同出現(xiàn)的文本來計(jì)算相關(guān)度。比較經(jīng)典的算法有Lesk算法[5]。在維基百科中，可以尋找在解釋文檔中的共現(xiàn)詞并利用式（3）來計(jì)算：
其中，n表示文檔ta和tb中都出現(xiàn)的文本片段（可能是一個(gè)詞或連續(xù)的多個(gè)詞），mn表示每個(gè)片段的詞數(shù)，length（ta）和length（tb）表示兩個(gè)文檔的總詞數(shù)。
2.1.2 鏈接共現(xiàn)法
盡管上文中的詞匯共現(xiàn)法已被證明是有效的，但是由于語義分析的復(fù)雜性，自然語言處理仍然存在很多準(zhǔn)確性的問題。所以有人提出了鏈接共現(xiàn)的方法，這種方法只使用語義網(wǎng)絡(luò)中的鏈接來避免自然語言處理中的準(zhǔn)確率的問題。因?yàn)檎Z義網(wǎng)絡(luò)是一個(gè)概念與鏈接的集合，所以使用鏈接同現(xiàn)法是有意義的。具體的公式和詞匯共現(xiàn)的公式的道理是一樣的，不同點(diǎn)只是使用文檔的鏈接代替詞匯。
比較經(jīng)典的鏈接共現(xiàn)的方法是GABRILOVICH E[6]提出的TF-IDF的方法。TF-IDF使用了兩個(gè)度量值：TF（Term Frequency）詞匯頻率和IDF（Inverse Document Frequency）后向文檔頻率。這種方法是通過計(jì)算維基百科頁面中鏈接的權(quán)值得到相應(yīng)概念的向量，然后通過比較概念向量來計(jì)算兩個(gè)概念的相關(guān)度。一個(gè)文檔中鏈接的權(quán)值的計(jì)算公式如下：
其中，tf（l，d）表示在文檔d中鏈接l出現(xiàn)的次數(shù)，N表示維基百科中文檔的數(shù)量，df（l）是包含鏈接l的文檔的數(shù)量。簡單來說，權(quán)值隨著文檔d中鏈接出現(xiàn)的頻率遞增。但是總的來說，因?yàn)槊總€(gè)維基百科的頁面都有自己的URL而且都對(duì)應(yīng)了一個(gè)概念，所以計(jì)算兩個(gè)鏈接的相關(guān)度等同于計(jì)算兩個(gè)概念的相關(guān)度。
2.2 基于維基百科路徑的語義相關(guān)度算法
維基百科網(wǎng)絡(luò)詞匯集，是一個(gè)由條目和超鏈接組成的集合，它的結(jié)構(gòu)是一個(gè)有循環(huán)的圖，概念就是圖的節(jié)點(diǎn)，超鏈接就是圖的邊，所以它就可以用一個(gè)圖的形式來表示：G={V，E}（V：維基百科中的條目/概念集合，E：維基百科中超鏈接的集合）。在考慮如何計(jì)算任意一個(gè)條目對(duì)vi和vj之間的相關(guān)度時(shí)，NAKAYAMA K等人[7]假設(shè)影響它們之間相關(guān)度主要有以下兩個(gè)因素：
?。?）從條目vi到條目vj的路徑的數(shù)量；
?。?）每一條從條目vi到條目vj的路徑長度。
如果有很多路徑可以從條目vi到達(dá)條目vj，那么它們之間的相關(guān)度相對(duì)較強(qiáng)。另外，兩個(gè)條目之間的相關(guān)度還受路徑長短的影響。換句話說，如果在圖G中從條目vi到達(dá)條目vj的路徑相對(duì)較短，那么它們之間的相關(guān)度要高于相對(duì)較長的。因此，如果從條目vi到達(dá)條目vj的所有路徑為P={p1，p2，...，pn}，NAKAYAMA K將它們之間的PF（Path Frequency）定義為：
其中，d（lenpk）是一個(gè)以路徑pk的長度為變量的單調(diào)遞增函數(shù)，例如對(duì)數(shù)函數(shù)的單調(diào)遞增函數(shù)都可用作函數(shù) d（lenpk）。
而且根據(jù)統(tǒng)計(jì)發(fā)現(xiàn)，在計(jì)算相關(guān)度時(shí)必須考慮維基百科的鏈接結(jié)構(gòu)的分布特征，例如這樣一種條目，有很多條目都擁有到達(dá)該條目的超鏈接。如果只是用PF的方法，那么這類條目會(huì)與很多條目具有較強(qiáng)的相關(guān)度。然而通常情況下該類條目對(duì)應(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值就會(huì)很高，概念之間的相關(guān)度相對(duì)較大。
3 結(jié)論
維基百科作為世界上最大的在線百科全書，蘊(yùn)含了豐富的語義知識(shí)。本文總結(jié)了利用維基百科完成復(fù)雜的語義相關(guān)度計(jì)算的方法，使用這些算法可以更容易地完成對(duì)維基百科的知識(shí)挖掘和完成文本分類等工作。但目前，無論是對(duì)維基百科使用的研究，還是維基百科相關(guān)算法研究，我國都遠(yuǎn)遠(yuǎn)少于國外。今后，隨著維基百科的優(yōu)勢(shì)顯現(xiàn)，相信會(huì)有更多的國內(nèi)專家關(guān)注維基百科，維基百科的相關(guān)技術(shù)也會(huì)更加成熟。
參考文獻(xiàn)
[1] STRUBE M， PONZETTO S P. WikiRelate! Computing semantic relatedness using Wikipedia[C]. AAAI， 2006，6： 1419-1424.
[2] ZESCH T， GUREVYCH I. Analysis of the Wikipedia category graph for NLP applications[C]. Proceedings of the 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. Automatic sense disambiguation using machine 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.