張菲菲，李宗海，周曉輝，李曉戈,

1.西安郵電大學，西安 710121

2.濟南中林信息科技有限公司，濟南 250100

基于層次聚類的跨文本中文人名消歧研究

張菲菲1，李宗海2，周曉輝1，李曉戈1,2

1.西安郵電大學，西安 710121

2.濟南中林信息科技有限公司，濟南 250100

人名消歧已經(jīng)成為自然語言處理和信息抽取應用中亟待解決的重要問題。運用中文自然語言處理和信息抽取系統(tǒng)識別命名實體和實體關系，生成實體信息對象（Entity Profile），采用實體信息對象（EP）中的個人信息特征，實體關系和上下文相關信息在Hadoop平臺上基于凝聚的層次聚類方法解決了實體消歧問題。采用哈爾濱工業(yè)大學整理的全網(wǎng)新聞語料作為人名消歧訓練和測試數(shù)據(jù)，著重研究了中文人名消歧特征的選取，參數(shù)的確定和驗證，在訓練集和測試集上分別取得了91.33%和88.73%的F值。說明提出的方法具有較好的可行性。

人名消歧；信息抽?。幌嗨贫?；層次聚類

1 引言

在互聯(lián)網(wǎng)上搜索人名已經(jīng)十分常見，但人名重名的現(xiàn)象也非常普遍，往往搜索的結(jié)果中會出現(xiàn)大量相同名字的網(wǎng)頁。曾統(tǒng)計搜索“李靜”，在結(jié)果去重后選取前43個搜索結(jié)果，統(tǒng)計網(wǎng)頁中的“李靜”分別表示了6個不同的人。

命名實體消歧已經(jīng)成為自然語言處理中亟待解決的重要問題，對問答系統(tǒng)，信息檢索[1]，網(wǎng)絡知識庫和復雜信息網(wǎng)絡構(gòu)建有著重要影響。在基本的三大類命名實體中，人名比地名、組織機構(gòu)名具有更強的歧義性，解決難度也更高。例如，在不同的文本源中，相同的姓名代表不同的人物實體，不同的姓名代表相同的人物實體。這種現(xiàn)象的存在極大地制約著信息抽取應用[2]的可靠性與實用性。本文在自然語言處理和信息抽取技術的基礎上，針對由不同文檔抽取出來的人物實體信息的相似度矩陣進行聚類，從而實現(xiàn)人名消歧。

2 相關工作研究

人名消歧早期主要是針對新聞類型的文本信息及一些學術中自動處理中人名消歧的問題研究。早在1994年，跨文檔指代消解（Cross-Document Co-reference，CDC）作為MUC-6[3]的潛在任務被首次提出。1998年，Bagga和Baldwin[4]提出用向量空間模型（Vector Space Model，VSM）算法，將實體信息的比較轉(zhuǎn)換為空間向量的比較，實現(xiàn)跨文檔人名的指代消解。為了對他們的系統(tǒng)進行評估，他們還提出了B-CUBED算法對跨文檔指代消解進行性能評估。2007年，WePS（Web People Search）[5]評測研討會與語義評測研討會組織了針對英文網(wǎng)頁中的人名消歧的評測任務，WePS還分別在2009年與2010年開展了兩屆關于網(wǎng)絡人名消歧的評測會議。2008年，ACE評測會議將GEDR（Global Entity Detection and Recognition）和GRDR（Global Relation Detection and Recognition）作為兩項重要的評測內(nèi)容，并對英語和阿拉伯語兩類語種進行了評測。

相比于英文，中文人名消歧研究工作開展較晚。2010年，SIGHAN-CIPS聯(lián)合學術會議CLP2010[6]開展了首次設置了中文跨文本人名消歧任務評測，其中東北大學的周曉[7]等在實驗室開發(fā)的領域知識庫中，抽取文檔人物的屬性特征建立不同人物之間的互斥關系，并利用之間的關系進一步聚類。東北大學的丁海波[8]使用了相類似的方法，抽取人物屬性進行初步聚類，之后利用局部上下文特征和全局特征依次進行聚類。這些方法都取得了一定的成果，但由于研究過程都非常依賴領域知識庫，缺少一定的通用性。哈工大的郎君等[9]依據(jù)同名不同人物具有不同網(wǎng)絡思想，對搜索結(jié)果有重名的人名進行消歧。他們都是從特征選擇方面進行人名消歧的研究，而沒有對聚類方法進行改進。

3 系統(tǒng)架構(gòu)與研究方法

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

跨文本的命名實體消歧任務可分解為命名實體識別，篇章內(nèi)命名實體融合和跨文本的命名實體消歧。本文提出的人名消歧系統(tǒng)是建立在信息抽取系統(tǒng)之上。圖1給出了信息抽取系統(tǒng)的基本架構(gòu)，其中包含的三大功能模塊：（1）基于自然語言處理技術的信息抽取系統(tǒng)；（2）跨文本的實體信息聚合；（3）信息抽取應用系統(tǒng)。為了提高系統(tǒng)運行效率，整個系統(tǒng)運行在由6臺服務器組成的Hadoop平臺之上，采用了Map Reduce分布式并行計算方式。

信息抽取系統(tǒng)通過對單一文本進行一系列自然語言處理分析，包括實體、實體關系識別，時間、地點歸一化分析，別名識別和指代消解，完成文本內(nèi)的命名實體的信息

對象聚合（Entity Profile merge），并將結(jié)果保存到實體信息庫。跨文本信息聚合系統(tǒng)在完成了跨文本命名實體消岐之后，合并相關的實體信息存回信息庫。實體信息庫為其他上層應用系統(tǒng)，如：問答系統(tǒng)、信息分析系統(tǒng)、信息網(wǎng)絡可視化等提供支持。

圖1 系統(tǒng)框架圖

實體信息聚合系統(tǒng)的關鍵是實體的消岐，在大規(guī)模的文本語料中大量地存在著相同的名稱表示不同的實體，不同的名稱代表相同的實體?？缥谋久麑嶓w消岐工作首先需要進行文本中命名實體的識別，篇章內(nèi)實體消岐。本文所用的基于自然語言處理技術的中文信息抽取系統(tǒng)采用了有限狀態(tài)轉(zhuǎn)換機（FST）規(guī)則和統(tǒng)計機器學習相結(jié)合的方法，運用多層模塊化設計思想實現(xiàn)了非受限域命名實體（NE）識別（時間、地點、人物、組織機構(gòu)、產(chǎn)品），實體關系（Correlated Entity，CE）識別，并利用別名和指代消解實現(xiàn)了命名實體信息對象（Entity Profile）聚合，信息抽取系統(tǒng)的具體技術實現(xiàn)細節(jié)將另文介紹。

3.2 實體信息抽取

系統(tǒng)使用最基本的三類命名實體作為信息抽取的中心：人物實體（NePer），組織實體（NeOrg），地點實體（NeLoc）。其中，與人名消歧密切相關的是人物實體和組織實體。

人物實體（NePer）在文本中表現(xiàn)形式主要為人物姓名，以及部分常見別名，簡稱等，如：

曾國藩/NePer謚號是文正，因而也被人稱為文正公/ NePer.

組織實體（NeOrg）包括組織機構(gòu)的全名及簡稱，如：

中國聯(lián)合網(wǎng)絡通信集團有限公司/NeOrg（簡稱“中國聯(lián)通/NeOrg”）于2009年1月6日/NeTIME在原中國網(wǎng)通/NeOrg和原中國聯(lián)通/NeOrg的基礎上合并組建而成，是中國/NeLoc唯一一家在紐約/NeLoc、香港/NeLoc、上海/NeLoc三地同時上市的電信運營企業(yè)。

實體信息的主要來源是實體間的關系信息，使用規(guī)則進行關系實體（CE）的抽取，本質(zhì)上是模式匹配的過程。抽取關系實體的規(guī)則中主要有兩類要件：實體與限定詞。定義規(guī)則，即是依照行文語法，將目標實體和限定詞按照特定的順序進行排列。當計算機查找到符合這一排列順序的字符串時，規(guī)則生效，關系實體抽取成功。

實體關系定義：R=。ne1是關系R中在起始位置的命名實體，feature1是它的詞性，實體類別等的特征。同理，ne2是關系R中在結(jié)束位置的命名實體，feature2是它的特征。比如：

人物配偶關系：

起始位置的命名實體特征為男性名，結(jié)束位置特征為女性名。

規(guī)則：ne1/NeMa（的）[妻子]（[是]）ne2/NeWom。

規(guī)則定義中，（）表示此位置限定詞允許不出現(xiàn)，[]表示此位置的限定詞是一類詞。規(guī)則中限定詞[妻子]位置上允許的詞有：妻子、夫人、媳婦、老婆等。（）與[]同時出現(xiàn)表示此位置的限定詞是一類詞且允許其不出現(xiàn)。表1是滿足規(guī)則的示例。

表1 人物配偶關系的示例

本文采用隨機下載了互聯(lián)網(wǎng)上新浪新聞80篇，對信息抽取系統(tǒng)進行了命名實體（NE）和實體關系（CE）測試。表2給出了信息抽取系統(tǒng)對于人物，組織機構(gòu)和地點三類命名實體的測試結(jié)果，其準確率達到了89.05%～96.93%，表3為CE關系測試結(jié)果，其準確率達到了83.33%～100%。

表2 命名實體測試結(jié)果（%）

表3 實體關系測試結(jié)果（%）

3.3 實體信息對象模型

在信息抽取系統(tǒng)中，以命名實體和事件為中心，建立了信息對象模型Entity Profile（EP）。EP可定義為一個屬性值矩陣Attribute Value Matrix（AVM），如下：

每一對屬性-值通過信息抽取系統(tǒng)的實體關系（CE）表示，實體關系是由實體為核心的屬性關系，如：所屬機構(gòu)，出生地點以及實體的修飾語等。在非受限領域里，定義了人物，組織機構(gòu)，地點，時間，產(chǎn)品5大類基本實體信息對象。表4為一個文章中人物命名實體的Profile例子。

表4 profile結(jié)構(gòu)

在文檔中，描述實體特征的關鍵信息非常重要，比如：人名，別名，組織名，地名，時間，產(chǎn)品名，聯(lián)系方式（電話號碼，電子郵件等）等。本文采用空間向量對profile選取的所有特征進行向量表示，以便每個profile都可以用一組特征向量所表示。一個文檔的內(nèi)容被看成是它含有特征項所組成的集合，對于含有n個特征項的文檔profile=P(t1，t2，…，tn)，其中tk是特征項，每一個特征項tk都依據(jù)一定的原則被賦予一個權(quán)重wk，表示它們在文檔中的重要程度。這樣一個profile可用它含有的特征項及其特征項所對應的權(quán)重所表示：P=P(t1，w1；t2，w2；…；tn，wn)，簡記為P=P(w1，w2，…，wn)，1≤k≤n。

3.4 特征選取及相似度計算

本文將人名消歧看作是無監(jiān)督的層次聚類問題。選取的特征采用權(quán)值法和空間向量模型（Vector Space Model，VSM）方法計算profile間的相似度，得到所有profile的相似度，最后，利用凝聚層次聚類算法對相似度矩陣進行聚類。

對相同人名進行消歧，最重要的就是需要選出能夠區(qū)別不同人名的一些主要特征，然后通過所選的特征及其之間的相似程度，層次聚類算法可以計算出每個人名所屬的類。比如，任意兩個profileP1=P1(w11，w12，…，w1n)和P2=P2(w21，w22，…，w2n)。本文選取的特征及P1和P2的相似度計算如下：

（1）個人信息特征：個人信息（Personal Information，PI）是識別人物身份特征的重要信息，如姓名，別名，出生日期，出生地點，居住地，Email，職位，家庭成員等。在計算個人信息的相似度時，根據(jù)不同信息對人物特征反映出的程度不同，分別賦予不同的權(quán)重。個人信息特征相似度計算公式：

其中ce1i和ce2j分別表示P1的第i個重要信息和P2的第j個重要信息。

（2）關系信息特征：關系信息（Relationship Information，RI）是與人物有關的命名實體（NE），是指和此人在同一篇文檔內(nèi)共同出現(xiàn)的人，地點，組織機構(gòu)等。關系信息相似度是指由關系信息構(gòu)成的空間向量的相似度，計算公式為：

其中wij=tf×lg，表示由NE構(gòu)成的空間向量。w1j是特征tj在P1中的權(quán)重，w2j是特征tj在P2中的權(quán)重。tf表示特征tj在P中出現(xiàn)的頻率，D表示profile總數(shù)，df表示出現(xiàn)該人名的profile總數(shù)。

（3）文檔上下文信息特征：文檔上下文信息（Document Context Information，DCI）是指在文檔內(nèi)的上下文信息中能夠一定程度反映人物特征的信息。文檔上下文信息相似度是指由文檔上下文信息去除停用詞后構(gòu)成的向量的相似度，計算公式為：

詞語構(gòu)成的空間向量。詞組權(quán)重的計算同樣采用的是TF-IDF方法。

綜上，兩個人物之間的相似度為：

然后根據(jù)兩個profile的相似度值prfsim(p1，p2)來判斷它們是否為共指關系：

其中threshold是共指關系的置信度，即類與類之間合并的閾值。若CO為1，則它們是共指關系，即p1和p2指相同的實體，否則相反。

3.5 層次聚類算法

根據(jù)上述相似度計算方法，計算出兩個profile之間的相似度，形成相似度矩陣，然后進行聚類。本文采用的是層次凝聚聚類算法進行處理人名消歧問題，類間距離計算采用的是平均距離法。公式如下：

聚類初始時，將每個人名對應的profile集P={p1，…，pi，…，pn}中的每一個profilepi看作是一個具有單個成員的類Ci={pi}，所以就構(gòu)成了P的一個聚類C= {c1，c2，…，cn}，對于類(ci，cj)之間采用上面的特征向量進行計算其相似度，然后選取相似度值最大的兩個簇進行合并，形成一個新的類，即ck=ci∪cj，從而對于P形成一個新的聚類C={c1，c2，…，cn-1}；重復上面的步驟，直到所有的簇間的相似度小于某個閾值或全部成為一個簇。偽代碼算法如下：

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

4.1 實驗數(shù)據(jù)

本文使用由哈爾濱工業(yè)大學整理的基于搜狗全網(wǎng)新聞數(shù)據(jù)的人名消歧語料作為實驗數(shù)據(jù)[10]，并選取“李靜”和“李麗”的文本作為訓練集，選取“王磊”和“李明”的文本作為測試集，為了進一步驗證訓練參數(shù)的普遍適用性，對2012年全年人民日報上的“王剛”進行人名消歧，抽取人物profile，對其進行人工標注并以Purity& Inverse Purity Metrics方法對聚類結(jié)果進行了評測。

4.2 實驗評測標準

本文采用Purity&Inverse Purity評測機制。評測指標有三個：Pur、InvP及F值[10]。公式如下：

為了更好地評估實驗結(jié)果，取α=0.5，用Fα=0.5對P和R進行綜合評測。S={S1，S2，…}是將要進行評測的聚類集，R={R1，R2，…}是人工標注的聚類集。

4.3 實驗結(jié)果分析

本文對實驗數(shù)據(jù)主要從三個角度分析，即確定最佳參數(shù)，不同特征組合的最佳結(jié)果對比分析和對最佳參數(shù)驗證。

（1）參數(shù)調(diào)整：實驗采用語料庫中“李靜”和“李麗”的數(shù)據(jù)集作為訓練數(shù)據(jù)，用信息抽取系統(tǒng)對測試集進行處理，共抽取出8 847個人物實體的profile，其中“李靜”和“李麗”的profile共641個。實驗利用自動測試程序?qū)€人信息、關系信息、文檔上下文信息的參數(shù)及閾值四者的不同組合進行循環(huán)測試，對不同組合下得出的F值進行比較，結(jié)果確定最佳一組參數(shù)為α=0.36，β=1，γ= 0.6，且threshold=0.28，其準確率、召回率和F值分別為94.65%、88.24%和91.33%。圖2是在最佳參數(shù)下準確率、召回率和F值改變的曲線圖。

圖2 P、R和F隨閾值的變化曲線圖

圖2顯示，閾值在0.2～0.3之間時，F(xiàn)值相對比較高，在閾值為0.28時，F(xiàn)值達到最高91.33%。同時準確率在逐漸提高時，召回率在逐漸減小。因為當閾值很低的時候，profile中每兩個待消歧的人名就會被聚為一類，所以召回率就比較高。當閾值較高時，使原本應該聚類的profile沒有聚類，導致沒有正確識別出待消歧人名。

（2）特征分析：根據(jù)對個人信息（PI）、關系信息（RI）及文檔上下文信息（DCI）特征選取的不同組合進行了不同實驗，得到的最佳結(jié)果如表5所示。

表5 Purity&Inverse Purity評測機制實驗結(jié)果統(tǒng)計（%）

以上三種特征組合下的F值如圖3所示。

圖3 以上三種特征組合下的F值

從表5可以看出，當僅使用個人信息特征時，準確率尚可，但召回率較低，說明個人信息雖能表示一個人的身份，但由于語料中出現(xiàn)的個人信息特征比較少，所以造成召回率比較低。在加入實體關系特征時，召回率提高了44個百分點，說明語料中使用實體關系特征就能夠較好地表示一個人的身份，且語料中實體關系較多。同時，在構(gòu)建社交網(wǎng)絡時，實體關系信息特征會起著至關重要的作用。比如：

（1）四川省出席黨的十八大代表大會的有丁愛譜、王堅、王志強、李靜、劉作明、宋朝華、吳小可等72名成員。

（2）李靜、宋朝華和吳小可等出席簽約儀式。

此時（1）和（2）中的“李靜”并沒有明顯的個人信息特征，但兩次均與“宋朝華、吳小可”兩人共同出現(xiàn)，說明兩個“李靜”是同一個人。

同時使用三種信息特征時，召回率有所提高，準確率稍微下降，是因為在語料中添加能夠反映人物特征的信息比較多，但這些特征對于每一個人不具有普遍性，所以造成提高了召回率，準確率下降了1.78個百分點，但總體評測標準F值還是有所提高。而且圖2也顯示了在三種情況下，F(xiàn)值也是逐漸提高的。

（3）參數(shù)驗證：對哈爾濱工業(yè)大學整理全網(wǎng)新聞數(shù)據(jù)語料中，選取“王磊”和“李明”進行人名消歧，分別抽取出6 632和14 376個人物實體的profile，對其進行聚類，并采用Purity&Inverse Purity進行評測，同時分別加入維基百科上的“王磊”和“李明”的profile，共6 715和14 407個，用同樣的方法進行驗證，取得結(jié)果分別如表6和表7所示。

表6 兩個人名實驗測試結(jié)果（%）

表7 兩個人名加入百科后實驗測試結(jié)果（%）

圖4 （a）王磊在加入百科前后比較

實驗結(jié)果測試“王磊”和“李明”的F值分別為88.7%和87.28%，取得相對比較理想的結(jié)果，在加入維基百科數(shù)據(jù)后，測試F值分別為89.5%和87.96%，比未加之前分別提高了一個百分點。維基百科中的數(shù)據(jù)比較規(guī)范，更新比較快，且能夠抽取出更為豐富的個人信息和關系信息特征，所以評測的結(jié)果顯示召回率提高了2個百分點，如圖4所示。在加入維基百科數(shù)據(jù)以后，評測結(jié)果說明采用本文系統(tǒng)訓練出的這組參數(shù)具有普遍適用性。

同時，對2012年全年的人民日報上的“王剛”進行人名消歧，共抽取出54 782個人物的profile，采用同樣的方法并對其中533篇“王剛”的profile進行了聚類，聚類結(jié)果是6類實體profile，并且對聚類結(jié)果進行評測，取得非常好的結(jié)果，如表8所示。

表8 人民日報實驗測試結(jié)果（%）

人民日報的數(shù)據(jù)集是web數(shù)據(jù)集上的一個子集，數(shù)據(jù)源相對比較規(guī)范，人物報道相對比較集中，多數(shù)profile只通過個人信息和關系信息特征就很容易合并。實驗結(jié)果表明，本系統(tǒng)在較為規(guī)范的數(shù)據(jù)集下有非常滿意的測試結(jié)果。

5 結(jié)束語

本文主要解決了自然語言處理中的人名消歧問題，采用了基于凝聚層次聚類的方法，通過對個人信息、關系信息及文檔上下文信息特征提取，這三個特征基本能夠確定一個人的身份，實驗通過訓練集對部分數(shù)據(jù)測試，得到一組最佳參數(shù)，再用這組參數(shù)去測試剩下的數(shù)據(jù)，為了進一步證明本文方法的適用性，還采用了2012年的人民日報進行測試，均取得比較好的實驗結(jié)果。

圖4 （b）李明在加入百科前后比較

當然，本文的系統(tǒng)還不夠完善，在下一步的研究工作中，打算結(jié)合互聯(lián)網(wǎng)上的知識數(shù)據(jù)庫進行進一步研究，改進目前的跨文本實體信息聚合系統(tǒng)。

[1]Gao Liqi，Zhang Yu，Liu Ting，et al.Word sense language model for information retrieval[C]//AIRS，2006.

[2]李保利，陳玉忠，俞士汶.信息抽取研究綜述[J].計算機工程與應用，2003，39（10）：1-5.

[3]McCarthy，Lehnert W.Using decision trees for coreference resolution[C]//Proceedings of the Sixth Message Understanding Conference（MUC-6），1995.

[4]Bagga A，Baldwin B.Entity-based cross-document coreferencing using the vector space model[C]//Proceeding of the 17th International Conference on Computational Linguistics，Canada，1998：79-85.

[5]WePS-3 workshop program[EB/OL].（2010-07-10）.http：// nlp.uned.es/weps/.

[6]Task3 Chinese version[EB/OL].（2010-10-16）.http：//www. clpsc.org.cn/clp2010/task3_ch.htm.

[7]周曉，李超，胡明涵，等.基于人物互斥屬性的中文人名消歧[C]//第六屆全國信息檢索學術會議（CCIR），2010：333-340.

[8]丁海波，肖桐，朱靖波.基于多階段的中文人名消歧聚類技術的研究[C]//第六屆全國信息檢索學術會（CCIR），2010：316-324.

[9]郎君，秦兵，宋巍，等.基于社會網(wǎng)絡的人名檢索結(jié)果重名消解[J].計算機學報，2009（7）：1365-1375.

[10]王鑫.人名消歧關鍵技術研究與實現(xiàn)[D].哈爾濱：哈爾濱工業(yè)大學，2012.

[11]Shingo O，Issei S，Minoru Y.Person name disambiguation in Web pages using social network，compound words and latent topics[C]//LNAI 5012：PAKDD2008，2008：260-271.

ZHANG Feifei1,LI Zonghai2,ZHOU Xiaohui1,LI Xiaoge1,2

1.Xi’an University of Posts&Telecommunications,Xi’an 710121,China
2.Jinan Zhonglin Information Technology Co.,Ltd,Jinan 250100,China

Cross-document entity disambiguation is the problem of identifying whether mentions from different documents refer to the same or distinct entities.This paper describes a Chinese information extraction system which involves both document-level IE and corpus-level IE,a pipeline and multi-level modular approach to name entity and Entity Profile extraction.It introduces novel features based on document-level entity profiles and study on the influence of feature selection, parameter selection,parameter validation and analysis on results.Disambiguation is performed based on agglomerative hierarchical clustering using Hadoop.Experiments show that F-measure of training set is 91.33%and testing set is 88.73%, using the whole network news corpus dataset from Harbin Institute of Technology.

entity disambiguation;information extraction;similarity;hierarchical clustering

A

TP391.12

10.3778/j.issn.1002-8331.1309-0423

ZHANG Feifei,LI Zonghai,ZHOU Xiaohui,et al.Cross-document Chinese personal name entity disambiguation based on hierarchical clustering.Computer Engineering and Applications,2014,50（6）：106-111.

張菲菲（1987—），女，碩士，主要研究方向：命名實體消歧和文本數(shù)據(jù)挖掘；李宗海（1988—），男，主要研究方向：信息抽取、人工智能；周曉輝（1978—），男，博士，教授，主要研究方向：電子商務、并行計算和分布式存儲；李曉戈（1962—），男，博士，教授，主要研究方向：自然語言處理、機器學習和文本數(shù)據(jù)挖掘。

2013-09-27

2013-11-15

1002-8331（2014）06-0106-06