李廣一，王厚峰

（北京大學(xué) 計算語言學(xué)教育部重點實驗室，北京100871；北京大學(xué) 計算語言學(xué)研究所，北京100871）

1 引言

命名實體識別和歧義消解是自然語言理解的一項重要研究內(nèi)容，對信息抽取、信息檢索、問答系統(tǒng)等都具有重要作用。有關(guān)命名實體識別已有大量研究［1]，近幾年來的國際評測進一步體現(xiàn)出對命名實體消歧的關(guān)注。UNED組織了三屆WePS（Web People Search）評測［2－4]，在沒有命名實體知識庫的情況下，將具有相同指稱的命名實體聚集到一起。自2009年起，TAC（Text Analysis Conference）的KBP（Knowledge Base Population）評測［5－6]都包含了實體鏈接（Entity Linking）的任務(wù)，與 WePS不同的是，KBP提供了關(guān)于實體的知識庫，需要將某個實體鏈接到知識庫的相應(yīng)定義，并將無鏈接關(guān)系的實體進行聚類。

與英文不同，漢語命名實體缺少明確的標(biāo)記形態(tài)，這給命名實體識別和歧義消解帶來了新的挑戰(zhàn)。首先，普通詞可以作為命名實體，例如，“高超”一詞通常用作形容詞，但是也可以作為人名出現(xiàn)；其次，一個詞可以作為多種類型的命名實體出現(xiàn)，例如，“華明”一詞可能是人名、公司名或者地名；另外，重名現(xiàn)象也在漢語中也大量存在并十分嚴(yán)重。

為了探索解決這些問題的方法，第二屆CIPSSIGHAN中文處理國際會議（CLP－2012）舉辦了漢語命名實體識別與歧義消解評測，評測的參加單位提出了不同的方法，取得了較好的結(jié)果。本文基于CLP－2012的評測數(shù)據(jù)，探究了命名實體識別和歧義消解方法，構(gòu)建了一種基于多步聚類的命名實體識別和歧義消解框架。在評測的測試數(shù)據(jù)的F值達(dá)到86.68%，高出參評單位最好結(jié)果6.46%。

2 相關(guān)工作

命名實體識別早期主要使用基于規(guī)則的方法［7]。近幾年大多采用機器學(xué)習(xí)方法，包括：隱馬爾科夫模型［8]、最大熵模型［9]、條件隨機場模型［10]等。

命名實體消歧的方法大致可分為基于文本向量空間模型的聚類方法［11]、基于社會網(wǎng)絡(luò)的方法［12]、基于分類的方法［13]等。在KBP中出現(xiàn)的方法更加豐富多樣［6]，包括無指導(dǎo)相似度計算、有指導(dǎo)分類和排序、基于圖的排序、層次聚合式聚類、譜圖聚類、主題模型等等。

CLP－2012的命名實體識別與消歧任務(wù)共有8支隊伍參加，參評單位提出了很多有效的方法。文獻(xiàn)［14]使用了分類—聚類的兩步模型，并利用文檔集合和互聯(lián)網(wǎng)信息構(gòu)造了Out類和Other類的知識庫定義；文獻(xiàn)［15]應(yīng)用了關(guān)鍵詞提取算法來構(gòu)建特征；文獻(xiàn)［16]抽取了人名實體的19種屬性，并使用了支持向量機（SVM）訓(xùn)練分類器來為難以通過相似度進行判斷的文檔分類；文獻(xiàn)［17]使用了模糊聚類。

3 系統(tǒng)構(gòu)架

CLP－2012的命名實體識別與消歧任務(wù)融合了WeSP和KBP評測的特點。任務(wù)對每個待消歧詞提供了知識庫來表示實體定義，每個定義由一段文字描述。對每個待消歧詞，評測任務(wù)提供了一個文本集合T，每個文本都包含相應(yīng)的待消歧詞。對于每個文本t∈T，判斷t中出現(xiàn)的歧義詞是否對應(yīng)于知識庫中的某個定義，如果是，則輸出該定義的編號，否則需要判斷該待消歧詞是否作為一個普通詞出現(xiàn)，如果是，則將其歸入Other集合，否則表明該詞作為命名實體出現(xiàn)，但是不指向知識庫中的任何一個定義，則將其歸入Out集合。最后需要對Out集合中的文本進行進一步劃分，將指向同一實體的文本歸入同一集合，劃分結(jié)果表示為Out＿01，Out＿02……

CLP－2012的命名實體識別和歧義消解任務(wù)提供了知識庫和待消歧文本兩組語料，其中知識庫的規(guī)模較小，因而文獻(xiàn)［14，18]不同程度地使用了互聯(lián)網(wǎng)資源對知識庫進行擴充。本文提出的方法表明，充分利用知識庫和待消歧文本便可以取得理想的結(jié)果。

本文提出的命名實體識別和歧義消解方法流程如下：首先，依據(jù)文檔和實體定義之間的相似度，進行第一輪聚類；再依據(jù)文檔與類簇之間的相似度，進行第二輪聚類。通過兩輪聚類，將文檔與實體定義之間的鏈接基本完成，剩余的未鏈接文檔主要由Other類和Out類文檔組成。對未鏈接文檔，使用層次聚合式聚類（HAC）算法將Out類文檔進行聚類，再基于相似度和規(guī)則對Other類進行標(biāo)記。最后，使用K－Means算法對結(jié)果進行微調(diào)。本節(jié)余下部分將詳細(xì)介紹本文提出的基于多步聚類的命名實體識別和歧義消解方法。

3.1 預(yù)處理

3.1.1 分詞和詞性標(biāo)注

評測提供的知識庫和待消歧文本兩組語料都是未經(jīng)處理的原始文本，因而需要對其進行分詞和詞性標(biāo)注預(yù)處理。本文使用了由條件隨機場模型（CRF＋＋①http：／／crfpp.googlecode.com／svn／trunk／doc／index.html工具包）設(shè)計并實現(xiàn)的分詞系統(tǒng)，以SIGHAN2005中文分詞評測的北京大學(xué)語料作為訓(xùn)練語料，在測試語料的分詞結(jié)果F值為95.97%。詞性標(biāo)注系統(tǒng)采用了文獻(xiàn)［19]的方法，使用最大熵模型（MaxEnt②http：／／homepages.inf.ed.ac.uk／lzhang10／maxent＿toolkit.html工具包）實現(xiàn)，利用《人民日報》1998年1月語料進行訓(xùn)練，交叉驗證顯示詞性標(biāo)注準(zhǔn)確率為91.14%。詞性標(biāo)注采用了北京大學(xué)標(biāo)注標(biāo)準(zhǔn)，其中nr、ns標(biāo)注分別代表了人名和地名，因此沒有再單獨對語料進行命名實體識別。

3.1.2 特征選取

上下文信息是實體消歧的重要信息，命名實體消歧方法大多選取上下文信息為特征。文獻(xiàn)［16]對命名實體的屬性進行了細(xì)致的抽取，選擇了19種特征。但由于文本的局限性和抽取技術(shù)的限制，過于細(xì)致的特征抽取難以保證準(zhǔn)確和完整。本文選擇的特征如下。

作品名：包括書名、影視劇名等，以書名號作為選取界限。

人名：選擇詞性標(biāo)注為nr的詞。由于北大分詞標(biāo)準(zhǔn)將人名中的姓和名劃分開，所以利用簡單的規(guī)則將其還原成完整的人名。

地名：選擇詞性標(biāo)注為ns的詞。

職業(yè)名稱：文獻(xiàn)［14]將職業(yè)名稱選作特征，取得了良好的實驗效果。本文同樣通過互聯(lián)網(wǎng)構(gòu)建了表示職業(yè)的詞表，共計233個名詞。另外，由于知識庫中一定比例的實體定義為運動員，對于這些定義來說，運動項目名稱對消歧會有顯著的幫助。因此，本方法在詞表中增加了64個表示運動項目的名詞。將文本中出現(xiàn)的包含在該詞表中的詞作為職業(yè)名稱類的特征。

其他名詞特征：選取文檔中所有未被選取的名詞以及名詞性動詞。需要說明的是，由于待消歧詞在每篇文檔中都會出現(xiàn)，對歧義消除沒有幫助，反而可能因大量出現(xiàn)而導(dǎo)致相似度的偏差，因此，特征中沒有包含待消歧詞。

3.1.3 相似度計算

文本間相似度計算采用了基于向量空間模型的余弦相似度，特征權(quán)重使用了加權(quán)的tf－idf值。由于知識庫中的實體定義與待消歧文本之間在文本長度上存在顯著差異，為了緩解這種不平衡性帶來的誤差，本文對待消歧文本的tf值進行了調(diào)整，定義調(diào)整函數(shù)f如式（1）所示。

其中ceil表示向上取整函數(shù)。不同類型的特征在歧義消解時的影響是不同的，為此，本文通過實驗，為不同特征設(shè)定了不同的權(quán)重，權(quán)重值如表1所示。

表1 特征類型權(quán)重表

向量A與向量B的相似度定義為余弦相似度，如式（3）所示。

3.2 基于知識庫的聚類

首先，將文檔與知識庫的定義之間進行鏈接。對待消歧文檔t∈T，計算其與知識庫中所有定義的相似度，按相似度從大到小進行排序，依據(jù)排序結(jié)果，可以找到與文檔t相似度最高的定義x，如果x與文檔t的相似度滿足顯著條件，則將文檔t鏈接到定義x。本文定義顯著條件為，若t與知識庫中所有定義的相似度中，最高值與次高值的差值達(dá)到某一閾值threshold1，則認(rèn)為結(jié)果顯著。之所以設(shè)定顯著條件，而不是將每個文檔分配給最高相似度的那個定義，主要是為了保證聚類結(jié)果的準(zhǔn)確度。

上述聚類作為第一輪聚類。通過第一輪聚類后，一部分文檔被鏈接到知識庫的定義上。假定知識庫中的定義數(shù)為n，將所有與知識庫第i個定義鏈接的文檔都?xì)w入集合Si，于是，第一輪聚類的結(jié)果可以表示為n個集合S1，S2，…，Sn。我們發(fā)現(xiàn)，即便有顯著條件限制，聚類結(jié)果中還是會存在部分錯誤。為了后續(xù)處理達(dá)到更好效果，還需要對第一輪聚類的結(jié)果進行調(diào)整，以盡可能將錯誤的結(jié)果從集合中剔除。調(diào)整主要利用了待消歧文本之間的相似度。本文假定，若同一集合中的文本都含有指向同一定義的同名實體，這些文本之間也存在密切的關(guān)聯(lián)。由于文檔的長度相較實體定義更長，詞匯分布更加均勻，因而相似度的可靠性更高。因此，本文采用的調(diào)整策略為，對于集合Si中的文檔t，如果t與集合中其他文檔的平均相似度大于t與第i個實體定義的相似度，則Si保留t，否則從Si中剔除t，t重新歸入未鏈接文檔集合。

3.3 基于文檔集合的聚類

經(jīng)過第一輪聚類和結(jié)果調(diào)整，得到了聚類結(jié)果S1，S2，…，Sn。在第二輪聚類中，本文使用一輪聚類的結(jié)果來對剩余的文檔進行鏈接。聚類過程如下：對于每個未鏈接文檔t，分別計算t與S1，S2，…，Sn的相似度，定義t與文檔集合S的相似度如式（4）所示。

得到n個相似度后，同樣采用第一輪聚類中的顯著條件，即如果相似度中最高值與次高值的差大于閾值threshold2，則將該文檔t加入與之相似度最高的文檔集合，即將t鏈接到該集合對應(yīng)的實體定義。

3.4 層次聚合式聚類

經(jīng)過前兩輪聚類，大部分與知識庫中的定義相關(guān)聯(lián)的文檔已經(jīng)被鏈接，剩余的未鏈接文檔集合主要由Out類和Other類組成。這些文檔與已鏈接的文檔集合S1，S2，…，Sn的相似度都不符合顯著條件，但其中Out類的文檔可以進一步形成多個集合，這些集合內(nèi)的文檔間相似度較高。本文使用層次聚合式聚類（Hierarchical Agglomerative Clustering，HAC）算法對剩余文檔進行聚類，得到Out類文檔的聚類結(jié)果。聚類方法如下：

（1）將每個文檔作為一個聚類集合；

（2）計算每兩個集合之間的相似度；

（3）將相似度最高的兩個集合合并為一個集合；

（4）重復(fù)（2）和（3）直到任意兩個集合之間的相似度小于某個閾值thresholdHAC。

聚類集合之間的相似度采用組平均相似度，即

因為未鏈接文檔中還包含了Other類文檔，以及少數(shù)未被準(zhǔn)確鏈接的實體文檔，因此層次聚類的停止閾值不應(yīng)過低，目的是盡可能使得聚類過程僅涉及相似度較高的Out類文檔，而不使非Out類文檔參與聚類。

對于聚類的結(jié)果，本文選擇大小超過2的聚類集合作為Out類集合，因為通過實驗我們發(fā)現(xiàn)，大小為2的聚類集合是真實Out類集合的概率不高，選取大小超過2的聚類集合作為Out類集合效果最好。

3.5 判斷Other類文檔

Other類的識別是評測任務(wù)的一個難點，多個參賽單位使用了命名實體識別系統(tǒng)來對Other類進行識別，但由于評測任務(wù)中的待消歧詞大多在漢語中通常作為普通詞出現(xiàn)，所以命名實體識別對這些詞的識別效果不佳。文獻(xiàn)［14]指出他們使用的命名實體識別系統(tǒng)對于多個待消歧詞的識別準(zhǔn)確率僅為0，文獻(xiàn)［20]介紹了CLP－2010人名消歧任務(wù)取得第一的參評單位所采用的人名識別系統(tǒng)，但該系統(tǒng)對“高明”這類通常作為普通詞的人名識別卻無能為力，因而文獻(xiàn)［20]采用了規(guī)則來進行這類人名的識別。

所以，本文提出的方法并沒有像大部分參評單位那樣在第一步進行Other類文檔的識別，而是通過前三步的準(zhǔn)確聚類，來保證大部分Other類文檔在三步聚類之后仍然未被標(biāo)注，然后在剩余的未標(biāo)注文檔中，通過相似度和規(guī)則相結(jié)合的方式來確定Other類文檔。具體方法是：如果未標(biāo)注文檔t與實體定義文檔集合S1，S2，…，Sn以及層次聚合式聚類結(jié)果Out1，Out2，…，Outm的相似度都低于0.02，且待消歧詞前后大小為2的窗口中未出現(xiàn)命名實體或職業(yè)名稱類詞語，則將其標(biāo)記為Other類。

3.6 基于K－Means聚類的結(jié)果調(diào)整

前幾步聚類可以得到鏈接到知識庫定義的n個文檔集合S1，S2，…，Sn以及層次聚合式聚類結(jié)果Out1，Out2，…，Outm，相應(yīng)地，可以得到k＝m＋n個聚類中心，使用類似K－Means聚類的方法，可以對除Other類文檔之外的聚類結(jié)果進行調(diào)整。方法是，將每個非Other類文檔t（t可能仍未歸入到任何一個集合），歸入與之相似度最高的集合，重復(fù)該過程直到所有集合保持穩(wěn)定不變。此時的標(biāo)記結(jié)果就是系統(tǒng)輸出的最終結(jié)果。

4 實驗及結(jié)果分析

4.1 實驗結(jié)果

我們使用CLP－2012評測提供的訓(xùn)練數(shù)據(jù)作為實驗數(shù)據(jù)，訓(xùn)練數(shù)據(jù)共有16個待消歧詞，1634個待消歧文檔?；谟?xùn)練數(shù)據(jù)的實驗表明，表2所示的閾值取值得到了最佳結(jié)果，因此我們依據(jù)表2設(shè)定閾值。

表2 閾值選擇

為了顯示每一步聚類的效果，我們對每一步的結(jié)果進行了評測。由于中間結(jié)果并沒有對所有文檔完成標(biāo)注，所以僅對標(biāo)注結(jié)果的文檔進行評估，準(zhǔn)確率和召回率均為已標(biāo)注文檔的均值。相應(yīng)地我們增加了標(biāo)注率指標(biāo)，來顯示已標(biāo)注文檔占所有文檔的比例。中間結(jié)果的評測數(shù)據(jù)如表3所示。

表3 分步標(biāo)注結(jié)果評測

從表3中可以看出，第一輪聚類標(biāo)注了60%的文本，并且準(zhǔn)確率已經(jīng)達(dá)到了90%，第一輪聚類總體效果良好。第一輪聚類后的調(diào)整有效地提高了準(zhǔn)確率，使得調(diào)整后的聚類集合保持了較高的純度，但是召回率以及標(biāo)注率都有所下降，這說明部分正確標(biāo)注從結(jié)果中被剔除，但調(diào)整的主要目的是提高準(zhǔn)確率，第二輪聚類仍然有可能保證這部分正確的鏈接重新被加入結(jié)果中。第二輪聚類的結(jié)果很好地彌補了第一輪聚類的問題，標(biāo)注文檔比例較第一輪聚類有所上升，準(zhǔn)確率和召回率都顯著提高。層次聚合式聚類后，標(biāo)注率提高了20%，準(zhǔn)確率和召回率僅稍有下降，說明對Out類的聚類結(jié)果比較準(zhǔn)確。判斷Other類后，準(zhǔn)確率和召回率有所下降，說明標(biāo)記Other類的準(zhǔn)確性比知識庫和Out類低。經(jīng)過K－Means聚類調(diào)整后，F(xiàn)值最終為88.35%。

K－Means聚類調(diào)整的迭代過程如表4所示。從表4可以看出，基于K－Means聚類的調(diào)整對結(jié)果有小幅度的提升，由于調(diào)整前聚類結(jié)果較好，所以調(diào)整在4輪迭代后就達(dá)到穩(wěn)定。

使用在訓(xùn)練數(shù)據(jù)上取得最優(yōu)效果的設(shè)定，我們在CLP－2012的測試數(shù)據(jù)上進行了實驗，實驗結(jié)果如表5所示。

表4 K－Means調(diào)整的迭代過程

表5 測試數(shù)據(jù)實驗結(jié)果

我們將實驗結(jié)果與參與評測的前三名系統(tǒng)結(jié)果進行了比較，如表6所示?？梢钥闯?，本文的方法無論在訓(xùn)練集還是測試集上，都優(yōu)于評測前三名的系統(tǒng)。其中測試集F值與評測第一名相比，提高了6.46%。

表6 與其他系統(tǒng)結(jié)果比較

4.2 實驗結(jié)果分析

我們對知識庫實體類、Out類、Other類分別進行了評價，結(jié)果如表7所示。

表7 結(jié)果分類評價

從表7可以看出，對知識庫鏈接以及Out類聚類的結(jié)果較好，這說明本文構(gòu)建的基于向量空間相似度的聚類算法體現(xiàn)出了良好的消歧性能。但基于文本相似度的方法也存在局限性，例如，“高峰”一詞的文檔中，有多篇文章涉及了德云社的演員高峰調(diào)侃北京國安足球隊引發(fā)風(fēng)波的消息，由于國安、足球等詞匯大量出現(xiàn)，錯誤地將相聲演員高峰判斷為曾在北京國安隊效力的球員高峰。對于這種情況，需要更深層次的語義信息來幫助判斷。

表7還顯示，Other類的整體F值僅有55.78%。這說明當(dāng)普通詞作為命名實體時，辨識普通詞的效果不盡如人意。普通詞作為命名實體是漢語的一種常見現(xiàn)象，現(xiàn)有的基于規(guī)則和機器學(xué)習(xí)的方法尚不能很好地解決這類識別問題，還需要從語義理解的角度獲取更多可靠信息來提高該任務(wù)中普通名詞的識別效果。

5 結(jié)語

本文基于向量空間相似度，使用多步聚類的方法，實現(xiàn)了命名實體識別與歧義消解的模型。在CLP－2012評測語料上的實驗結(jié)果表明，本文所采用的多步聚類方法是有效的，將評測的結(jié)果提高了6.46%。同時，本文的方法不需要借助其他語料或者人工構(gòu)造、修改語料，具有良好的適用性。但仍有不足之處，對于普通詞的識別效果較差。

下一步，我們將進一步利用和融合更多信息，包括互聯(lián)網(wǎng)搜索結(jié)果及百科信息等，并從更深層次的語義層面入手，挖掘文本中蘊含的語義信息，來進一步提高命名實體識別和歧義消解的效果。

［1]趙軍.命名實體識別、排歧和跨語言關(guān)聯(lián)［J].中文信息學(xué)報，2009，23（2）：3－17.

［2]J Artiles，J Gonzalo，S Sekine.The SemEval－2007 WePS evaluation：Establishing a Benchmark for the Web People Search Task［C]／／Proceedings of SemEval'07Proceedings of the 4th International Workshop on Semantic Evaluations，2007：64－69.

［3]J Artiles，J Gonzalo，S Sekine.WePS 2Evaluation Campaign：Overview of the Web People Search Clustering Task［C]／／Proceedings of 2nd Web People Search Evaluation Workshop，18th WWW Conference，2009.

［4]J Artiles，A Borthwick，J Gonzalo，et al.WePS－3E－valuation Campaign：Overview of the Web People Search Clustering and Attribute Extraction Tasks［C]／／Proceedings of Conference on Multilingual and Multimodal Information Access Evaluation （CLEF）.2010.

［5]H Ji，R Grishman，H T.Dang，et al.An Overview of the TAC2010Knowledge Base Population Track［C]／／Proceedings of Text Analytics Conference（TAC2010）.

［6]H Ji，R Grishman，H T Dang.An Overview of the TAC2011Knowledge Base Population Track［C]／／Proceedings of Text Analysis Conference（TAC2011）.

［7]R Grishman，B Sundheim.Design of the MUC－6evaluation［C]／／Proceedings of 6th Message Understanding Conference，1995.

［8]J Sun，J Gao，L Zhang，et al.Chinese Named Entity Identification Using Class－based Language Model［C]／／Proceedings of the 19th International Conference on Computational Linguistics（COLING 2002）：1－7.

［9]A Borthwick.A Maximum Entropy Approach to Named Entity Recognition［D].New York：New York University.1999.

［10]X Mao，Y Dong，S He，et al.Chinese Word Segmentation and Named Entity Recognition Based on Conditional Random Fields［C]／／Proceedings of Sixth SIGHAN Workshop on Chinese Language Processing.2008：90－93.

［11]Silviu Cucerzan.Large－Scale Named Entity Disambiguation Based on Wikipedia Data［C]／／Proceedings of the Conference on Empirical Methods in Natural Language Processing（EMNLP2007）：708－716.

［12]Ron Bekkerman，Andrew McCallum.Disambiguating Web Appearances of People in a Social Network［C]／／Proceedings of the 14th International Conference on World Wide Web（WWW2005）：463－470.

［13]X Han，J Zhao.Person Name Disambiguation Based on Web－Based Person Mining and Categorization［C]／／Proceedings of Submitted to Second Web People Search Evaluation Workshop in Conjunction with WWW2009.

［14]Z Peng，L Sun，and X Han.SIR－NERD：A Chinese Named Entity Recognition and Disambiguation System Using a Two－stage Method［C]／／Proceedings of The 2nd CIPS－SIGHAN Joint Conference on Chinese Language Processing（CLP－2012）.

［15]H Zong，D F Wong，and L S Chao.A Template Based Hybrid Model for Chinese Personal Name Disambiguation［C]／／Proceedings of The 2nd CIPS－SIGHAN Joint Conference on Chinese Language Processing（CLP－2012）.

［16]W Han，G Liu，Y Mao，et al.Attribute Based Chinese Named Entity Recognition and Disambiguation［C]／／Proceedings of The 2nd CIPS－SIGHAN Joint Conference on Chinese Language Processing （CLP－2012）.

［17]W Tian，X Pan，Z Yu，et al.Chinese Name Disambiguation Based on Adaptive Clustering with the Attribute Features［C]／／Proceedings of The 2nd CIPSSIGHAN Joint Conference on Chinese Language Processing（CLP－2012）.

［18]J.Liu，R.Xu，Q.Lu，J.Xu.Explore Chinese Encyclopedic Knowledge to Disambiguate Person Names［C]／／Proceedings of The 2nd CIPS－SIGHAN Joint Conference on Chinese Language Processing （CLP－2012）.

［19]H.T.Ng，J.K.Low.Chinese Part－of－speech Tagging：One－at－a－time or All－at－once？ Word－based or Character－based？［C]／／Proceedings of the 2004Conference on Empirical Methods in Natural Language Processing（EMNLP 2004）：277－284.

［20]時迎超，王會珍，肖桐，等.面向人名消歧任務(wù)的人名識別系統(tǒng)［J].中文信息學(xué)報，2009，23（3）：17－22.