陳晨,王厚峰

(1.北京大學計算語言學教育部重點實驗室,北京100871;2.北京大學信息化建設(shè)與管理辦公室,北京100871)

引言

在互聯(lián)網(wǎng)上找人是最常見的搜索。但是,人名重名現(xiàn)象十分普遍,返回的結(jié)果往往含有大量相同名字的網(wǎng)頁。我們曾搜索“李小鵬”,在結(jié)果去重后,選取前55個搜索結(jié)果,發(fā)現(xiàn)這些網(wǎng)頁中的“李小鵬”代表了9個不同的人。

跨文本人名同名消歧是判斷不同文本中的相同人名是否指稱現(xiàn)實中相同實體的過程?？缥谋救嗣缡菧蚀_獲取感興趣人物相關(guān)信息的基礎(chǔ),對多文本摘要(Multi-text summary)、信息融合(Information fusion)等具體應(yīng)用也有重要的作用。但跨文本人名消歧是一項具有挑戰(zhàn)性的任務(wù),主要有以下幾個方面的原因。其一,重名的人數(shù)具有隨機性,有的名字的重名人可能成百上千,有些可能沒有重名;其二,不同名字重名不遵循統(tǒng)一的分布;其三,文本中存在與人物實體無關(guān)、而字串相同的噪音。

隨著多文本處理應(yīng)用的日益廣泛,跨文本同名消歧研究也受到了越來越多的重視。SemEval-2007評測設(shè)立了針對英文的網(wǎng)絡(luò)人物搜索 Web People Search(WePS)[1],2009年的WWW國際會議,再次設(shè)立了這一評測任務(wù),在 CLP SIGHAN 2010上也首次設(shè)置了中文跨文本人名消歧任務(wù)。

本文針對中文跨文本人名同指問題,使用社會網(wǎng)絡(luò)實現(xiàn)同名消歧。首先從文本中抽取與待消歧人名相關(guān)的實體,并利用實體共現(xiàn)信息構(gòu)建社會網(wǎng)絡(luò),再對社會網(wǎng)絡(luò)進行劃分,最后把具有相同社會網(wǎng)絡(luò)子圖的文本聚為一類,代表相同的名字指向相同實體。

本文結(jié)構(gòu)如下：第1節(jié)是相關(guān)工作的介紹;第2節(jié)給出基于社會網(wǎng)絡(luò)分析法的人名消歧框架;第3節(jié)介紹了社會網(wǎng)絡(luò)的獲取方法和實體關(guān)系權(quán)值的計算公式;第4節(jié)描述了基于社會網(wǎng)絡(luò)的聚類算法,包括多種圖劃分準則以及聚類停止條件;第5節(jié)介紹了實驗數(shù)據(jù)和評測標準,同時給出并分析了實驗結(jié)果;第6節(jié)是本文的小結(jié)和今后研究工作的展望。

1 相關(guān)工作

Bagga和Baldwin于1998年首先提出了跨文本的同指(Coreference)消歧任務(wù)[2]。他們對每個文本形成待消歧名字的同指鏈,并為同指鏈生成簡單摘要;然后,將各個摘要用特征向量來表示,在此基礎(chǔ)上,通過聚類方法將具有人名同指關(guān)系的文本聚在一起。Mann和Yarow sky通過學習模板在豐富的特征空間中自動提取人物實體的個人信息作為特征,進行跨文本的同名消歧[3]。Fleischman和Hovy提出使用最大熵模型來計算兩個名字指向同一實體的概率,并使用改進的層次聚類算法對同名的人名進行分類[4]。Malin創(chuàng)建社會網(wǎng)絡(luò)圖來實現(xiàn)人名消歧,第一種方法是基于局部社會網(wǎng)絡(luò)計算相似度并采用層次聚類進行劃分;第二種方法將全局社會網(wǎng)絡(luò)用相似度進行嚴格劃分,再采用隨機游走的方法實現(xiàn)類別劃分[5]。郎君等依據(jù)同名不同人物具有不同社會網(wǎng)絡(luò)的思想,對檢索結(jié)果中有重名的人名進行消歧[6]。Pedersen和Anagha則研究了實體數(shù)目(類的個數(shù))的判定問題[7]。

社會網(wǎng)絡(luò)分析法是在人類學、心理學、社會學、數(shù)學以及統(tǒng)計學等領(lǐng)域中發(fā)展起來的,已經(jīng)經(jīng)歷了約60多年的歷史。至今,社會網(wǎng)絡(luò)分析法早已突破了社會學領(lǐng)域的范圍,為其他領(lǐng)域的學者所采用?！安煌宋?、不同社會關(guān)系;相同人物,相同社會關(guān)系”的思想本身體現(xiàn)了“類聚”特點,本文將社會網(wǎng)絡(luò)分析方法引入到同名消歧中,并使用譜聚類實現(xiàn)了基于社會網(wǎng)絡(luò)關(guān)系的聚類,同時,比較了不同社會網(wǎng)絡(luò)邊權(quán)值和不同圖劃分準則對同名消歧結(jié)果的影響以及不同模塊度停止條件閾值下的人名消歧結(jié)果。

2 基于社會網(wǎng)絡(luò)的人名消歧

處于現(xiàn)實社會中的每一個人都有自己的社會關(guān)系和社交活動圈：如可能接觸到的人、活動的場所以及所屬的機構(gòu)等,這就構(gòu)成了社會網(wǎng)絡(luò)。社會網(wǎng)絡(luò)分析中的概念“自我中心網(wǎng)絡(luò)”和“團塊”正是該現(xiàn)象的概括。自我中心網(wǎng)絡(luò)(Egocentric network)指環(huán)繞在自我周圍的社會網(wǎng)絡(luò),它既包括自我與他人的直接聯(lián)結(jié),也包括這些與自我聯(lián)結(jié)的他人之間的聯(lián)結(jié)。團塊(Clique)是一個群體中的子群體,其成員彼此間的平均緊密程度超過對其子群體外(大群體之內(nèi))的其他成員的平均緊密程度[8]。

應(yīng)用社會網(wǎng)絡(luò)分析法實現(xiàn)人名消歧,首先分析同名的人各自對應(yīng)的自我中心網(wǎng)絡(luò)和團塊,如果對應(yīng)的實體不同,所具有的社會網(wǎng)絡(luò)往往不同,因而很可能屬于不同的團塊,并擁有自我中心網(wǎng)絡(luò)的特點,以此為依據(jù),可以通過集團劃分來區(qū)分不同實體。當然,有相同名字的兩個人也有可能出現(xiàn)在相似的社會網(wǎng)絡(luò)中,但概率是非常小的,本文忽略這種情況。

假設(shè)D={d1,d2,…,dn}表示文本集合,其中的每個文本di(0＜i＜n+1)都含有某個相同的人名Name。在集合D中,Name所指稱的實體表示為集合E={e1,e2,…,em},其中的每一個實體ej都有與之對應(yīng)的社會網(wǎng)絡(luò)關(guān)系Mj,Mj可以理解為與ej相關(guān)的實體(主要是人和機構(gòu))的集合?；谏鐣W(wǎng)絡(luò)的人名消歧,首先是從文本集合D中提取信息,建立Name的總的社會網(wǎng)絡(luò)關(guān)系圖M,然后使用社會網(wǎng)絡(luò)分析方法分析出它的子圖M1,…,Mm,并將待消歧文本d1,d2,…,dn對應(yīng)到各個社會網(wǎng)絡(luò)子圖M1,…,Mm中,將屬于同一社會網(wǎng)絡(luò)的文本聚為一類。在“不同人物、不同社會關(guān)系;相同人物、相同社會關(guān)系”的假設(shè)下,為社會子網(wǎng)M1,…,Mm對應(yīng)的實體e1,e2,…,em找到對應(yīng)的文本子集Dj,其中Dj?D,Dj∩Dk=Ф,1≤j,k≤m,j≠k。

基于社會網(wǎng)絡(luò)的同名消歧框架如下：

1)第一步：文本預(yù)處理;對集合D的每個文本d1,d2,…,dn進行預(yù)處理,包括分詞、詞性標注、命名實體識別等;

2)第二步：社會網(wǎng)絡(luò)的獲取與表達;在d1,d2,…,dn中根據(jù)社會網(wǎng)絡(luò)獲取原則來構(gòu)建同一人名的初始關(guān)系網(wǎng)絡(luò)M;

3)第三步：社會網(wǎng)絡(luò)聚類;在Name的社會網(wǎng)絡(luò)關(guān)系圖M上采用圖分割的算法來實現(xiàn)圖聚類算法,得到M的社會網(wǎng)絡(luò)關(guān)系子圖M1,…,Mm;

4)第四步：社會網(wǎng)絡(luò)映射;將形成各個社會關(guān)系子圖 M1,…,Mm映射回到文本集合D={d1,d2,…,dn}上,使得每個文本di對應(yīng)一個子圖Mj,映射到同一個子圖的文本代表它們包含的人名Name指稱同一實體,從而實現(xiàn)人名消歧。

經(jīng)過社會網(wǎng)絡(luò)獲取步驟,系統(tǒng)可以構(gòu)建一個初始的社會網(wǎng)絡(luò)圖,稱為基本網(wǎng)絡(luò)圖,為無向圖,圖中的節(jié)點表示與Name有關(guān)聯(lián)的實體,圖中的邊代表實體與實體之間的權(quán)值(相似值)。當且僅當兩個實體在同一個文本中共現(xiàn)時,圖中的這兩個實體對應(yīng)的點之間才存在連接邊,如圖1左圖所示。社會網(wǎng)絡(luò)圖聚類是對基本網(wǎng)絡(luò)圖的劃分。圖1的基本社會網(wǎng)絡(luò)圖經(jīng)過聚類得到的社會網(wǎng)絡(luò)圖劃分如圖1右圖所示。

圖1 社會網(wǎng)絡(luò)聚類示意圖

根據(jù)社會網(wǎng)絡(luò)圖中的子圖來劃分各個實體的類別,以實現(xiàn)社會網(wǎng)絡(luò)映射。依次查看包含人名Name的文本,統(tǒng)計文本中包含的實體類別,選擇最多的實體類別作為該文本的類別,從而實現(xiàn)文本類別的劃分,完成聚類。

下面將詳細介紹社會網(wǎng)絡(luò)獲取、表達和基于社會網(wǎng)絡(luò)的聚類算法。

3 社會網(wǎng)絡(luò)表達

在文本預(yù)處理之后,可以得到文本中的人名和機構(gòu)名列表,然后將包含人名、機構(gòu)名數(shù)目不小于2的文本選擇有效文本,從有效文本中獲取社會網(wǎng)絡(luò)關(guān)系。

社會網(wǎng)絡(luò)的構(gòu)造可以看成是構(gòu)造節(jié)點關(guān)系矩陣的過程。每個節(jié)點對應(yīng)于一個名字(人名和機構(gòu)名)。如果兩個節(jié)點同現(xiàn)于一個文本中,其間就有關(guān)系,依據(jù)其出現(xiàn)的上下文來計算之間的權(quán)值,本文考慮了三種不同的權(quán)值方法。

1)共現(xiàn)作為權(quán)值

如果兩個節(jié)點共現(xiàn)于同一個文本,這兩個節(jié)點就相似。假設(shè)用x1…xz表示節(jié)點,M1ij表示 xi與yj的權(quán)值,則權(quán)值計算公式如(1)所示：

2)共現(xiàn)頻次作為權(quán)值

用實體與實體共現(xiàn)的次數(shù)作為權(quán)值,計算實體關(guān)系權(quán)值M2ij,計算公式如(2)所示：

3)共現(xiàn)頻次對數(shù)作為權(quán)值

對共現(xiàn)次數(shù)矩陣進行指數(shù)化調(diào)整,計算對數(shù)型關(guān)系權(quán)值M3ij,計算公式如(3)所示：

其中,M2ij為共現(xiàn)頻次,c為常數(shù),作為調(diào)節(jié)因子。與權(quán)值方法2)相比,采用共現(xiàn)頻次的對數(shù)作為權(quán)值可以平滑數(shù)據(jù),對統(tǒng)計結(jié)果和概率估計進行必要的調(diào)整和修補,以降低由于數(shù)據(jù)稀疏現(xiàn)象帶來的統(tǒng)計誤差。

4 社會網(wǎng)絡(luò)聚類

社會網(wǎng)絡(luò)是由若干個“團塊”(Clique)構(gòu)成,每個“團塊”內(nèi)部節(jié)點之間的連接相對緊密,而不同“團塊”之間的連接則相對松散。社會網(wǎng)絡(luò)聚類與一般意義上的聚類不一樣,社會網(wǎng)絡(luò)聚類可以認為是“團塊”的發(fā)現(xiàn)過程,而一般的聚類更多是以共同特征為基礎(chǔ)對節(jié)點聚類。從構(gòu)建的網(wǎng)絡(luò)結(jié)構(gòu)中發(fā)現(xiàn)團塊有很多種方法,比較典型的有譜聚類的圖分割方法。譜聚類算法建立在譜圖理論基礎(chǔ)上,其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的最優(yōu)化劃分問題。與傳統(tǒng)的聚類算法相比,它具有能在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解的優(yōu)點。圖劃分的最優(yōu)解已經(jīng)證明都是NPC問題。一個比較可行的方法就是把問題松弛到連續(xù)區(qū)間,然后利用譜圖理論求得其松弛解。譜圖理論將圖劃分問題轉(zhuǎn)換成求解相似矩陣或Laplacian矩陣的譜分解[9]。

4.1 圖劃分準則

圖劃分的基本原則是：子圖內(nèi)的權(quán)重和最大化和各子圖間的邊權(quán)重最小化。

圖劃分可以分為2-way和任意 k-way,2-way劃分是每次將圖劃分為兩個子圖,k-way則將圖劃分為k個子圖。由于無法事先確定合理的k值,任意給定k會因為選擇不當而得到比較差的聚類結(jié)果。因此,通常情況下按2-way迭代譜聚類更適合。常見的2-way劃分準則有Minimum cut,Average cut,Normalized cut,Minmax cut,Ratio cut等。很多實驗表明,Normalized cut比Average cut得到的結(jié)果更好[9],Minmax cut與Normalized cut具有相似的行為。在本實驗中,分別嘗試了Minimum cut,Normalized cut和Ratio cut三種方法。

1)最小割(Minimum cut)準則

對一個連通圖,將一組邊去掉后,可以將原來的圖分成兩個獨立的連通子圖。如果少去掉一條邊,整個圖仍然保持為連通的,則稱去掉的這組邊為割集。去掉割集后,圖G便劃分為兩個獨立的子圖A和ˉA,這也稱為割。割值按公式(4)計算：

一個連通圖有多組割集,不同的割集對應(yīng)的割值可能是不相等的,割值最小的割稱為最小割。Wu和Leahy提出以最小割來劃分圖G,產(chǎn)生了較好的效果[10]。但是最小割準則容易出現(xiàn)歪斜分割,即容易把小區(qū)域分割出來。

2)規(guī)范割(Normalized cut)準則

為了避免斜歪分割問題,Shi和Malik提出了Normalized cut(Ncut)方法[11]。其規(guī)范化割值的計算方法如公式(5)：

di表示第i個節(jié)點的度。最小化Ncut函數(shù)稱作規(guī)范割準則,該準則不僅能夠衡量類內(nèi)樣本間的相似程度,也能衡量類間樣本間的相異程度。

3)比例割準則(Ratio cut)

Hagen和Kahng提出了比例割目標函數(shù)Rcut[12],如公式(7)：

4.2 譜聚類算法

按照使用的劃分準則,可將譜聚類算法分為2-way譜和k-way譜兩類。2-way劃分準則采取了迭代方式,如果希望得到k個子圖,則只需要經(jīng)過k-1輪的劃分。本文將2-way運用到基于社會網(wǎng)絡(luò)的人名消歧中,主要參考了SM算法[11]。

SM算法(二分遞歸算法)如下：

1)第一步：建立無向圖G,根據(jù)圖G構(gòu)造矩陣相似W和對角D,對角矩陣表示各個節(jié)點的度;

2)第二步：計算(D-W)x=λ Dx第二小特征值及其對應(yīng)的Fiedler向量v2;

3)第三步：升序排列v2中的元素,將重新排序的v2分成兩個部分,使得到劃分的 Ncut(A,ˉA)值最小;

4)第四步：轉(zhuǎn)到第二步再進一步劃分,直到滿足停止條件。

4.3 模塊度停止條件

2-way的譜聚類算法與聚合式聚類一樣,構(gòu)造一棵聚類樹,只不過是按自上而下方式。所以也同樣需要確定停止條件的問題。停止條件對聚類效果好壞有很大影響。Newman等人定義了一個用以評價網(wǎng)絡(luò)劃分質(zhì)量的指標,稱為模塊度(Modularity)[13]。模塊度的定義為：假設(shè)網(wǎng)絡(luò)已經(jīng)被分裂成k個子圖,定義k×k維的矩陣,其中元素b=[bij]n*n表示子圖i和子圖j之間的邊數(shù)占總邊數(shù)的比例,表示與第i個子圖中的節(jié)點相連的邊在所有邊種所占的比例。在此基礎(chǔ)上,用公式(8)來定義模塊度的衡量標準：

如果子圖內(nèi)部邊的比例不大于任意連接時的期望權(quán)值,則有Q=0。Q的上限為1,而Q越接近1,說明團塊結(jié)構(gòu)越明顯,即圖劃分的效果越好。實際網(wǎng)絡(luò)中,該值通常位于0.3～0.7之間,因此,可以通過設(shè)置一個模塊度閾值來決定是否停止聚類。

5 實驗結(jié)果與分析

5.1 測試集與評價指標

本文采用CLP 2010的中文人名消歧任務(wù)提供的訓(xùn)練數(shù)據(jù)作為評測數(shù)據(jù)。該語料對每一個選定的人名,按“字串”匹配的方法從新華社的語料庫中抽出含有該字串的文本,該“人名”的文本集。所提供的數(shù)據(jù)共有32個中文人名的文本集,每個文本集含有100～300個文本。如果文本中對應(yīng)的字串不表示人名(例如,“高明”字串出現(xiàn)在某個文本中,但并不是人名,而是形容詞),則應(yīng)該標記為“丟棄”。在所提供的32個人名數(shù)據(jù)集合中,不同人名指稱的實體數(shù)各有差異,但都在4～166之間,其構(gòu)成分布具有很強的隨機性。

社會網(wǎng)絡(luò)利用的是實體之間的相互關(guān)系。如果某個文本中只出現(xiàn)了所給的人名,而沒有出現(xiàn)其他實體,就不能使用社會網(wǎng)絡(luò),本文所用的方法排出了這樣的文本。

在評測時,CLP 2010使用B_Cubed和P_IP指標,本文也采用這兩種指標評價實驗結(jié)果,計算公式如下：

1)B_Cubed指標

首先對參與聚類的每個文檔分別求出可得到的最大的Precision和Recall,然后再求出平均值作為聚類結(jié)果的Precision和Recall。F-measure采用通常的計算公式計算：

2)P_IP指標

該計算指標對每個類,計算使得值最大的Purity和InversePurity,然后再求出平均值作為聚類結(jié)果的Purity和InversePurity。F-measure采用通常的計算公式計算：

其中,S為標準聚類結(jié)果集合,Si∈S代表標準結(jié)果類別集合中的其中一類;R為實際聚類結(jié)果集合,Rj∈R代表實際結(jié)果聚類集合中的其中一類。|Si|和|Rj|表示集合Si和Rj的大小。

5.2 實驗一：聚類對社會網(wǎng)絡(luò)人名消歧的影響

本文所用的譜聚類工具是 MATLAB中的Spectralib①http：//www.stat.washington.edu/spectral/工具包。為了取得較佳的社會網(wǎng)絡(luò)聚類效果,系統(tǒng)在調(diào)用SM 算法的Ncut分割函數(shù)完成譜聚類同時,設(shè)置標準類別個數(shù)作為社會網(wǎng)絡(luò)聚類個數(shù),將其實驗結(jié)果與基本圖的實驗結(jié)果進行比較?；緢D直接由圖的連通部件劃分實體類別,即在基本社會網(wǎng)絡(luò)圖中如果兩實體之間存在一條路徑互相可達,則這兩個實體屬于一類。實驗結(jié)果如表1所示 。其中,B_Cubed 的“#Pre”為精確率,“#Rec”為召回率,P_IP 的“#Pre”為 Purity,“#Rec”為InversePurity,表中以上數(shù)據(jù)為32個人名實驗下的平均值?！?best”代表實驗結(jié)果評測的F值取得最佳結(jié)果時的人名實驗結(jié)果數(shù)。

由表1可以看出,經(jīng)過聚類后,基于社會網(wǎng)絡(luò)的人名消歧精確度有很大的提高,B_cubed和P_IP的精確率提升了10%以上,F值也有6%以上的提升,但召回率有1%以上的下降?？赡艿脑蛴幸韵聨c：

1)社會網(wǎng)絡(luò)中的名字有歧義。如果社會網(wǎng)絡(luò)中的某個名字本身也是指稱了不同的實體對象,系統(tǒng)卻將其視為同一個實體,這樣該歧義名字會將本不連通的兩個子圖連接形成一個連通子圖,從而降低了基本圖劃分下人名消歧的精確率?；谏鐣W(wǎng)絡(luò)的聚類對含歧義名字的連通子圖進行劃分,可以利用割集理論將上述錯連的子圖劃分開,從而提高人名消歧精確率。

表1 社會網(wǎng)絡(luò)聚類對人名消歧的影響實驗結(jié)果

2)社會網(wǎng)絡(luò)中的名字沒有歧義,但是該名字對應(yīng)的實體確實與待消歧人名對應(yīng)的不同實體都有關(guān)系,如某個單位有兩個“李明”。與1)類似,社會網(wǎng)絡(luò)聚類也可以將關(guān)聯(lián)度低的不同社會網(wǎng)絡(luò)子圖劃分開。

3)召回率的下降,主要是不恰當?shù)膭澐衷斐傻?。由于?shù)據(jù)集中提取的社會網(wǎng)絡(luò)比較稀疏,系統(tǒng)會視其為結(jié)構(gòu)不緊湊并進行不必要的劃分。

社會網(wǎng)絡(luò)中歧義現(xiàn)象包括上面1)和2)中提到的兩種情況：社會網(wǎng)絡(luò)中的名字有歧義,稱之為“名字歧義”;社會網(wǎng)絡(luò)中的實體與待消歧歧義人名對應(yīng)的兩個實體都有關(guān)系,稱之為“關(guān)系歧義”,“名字歧義”和“關(guān)系歧義”統(tǒng)稱為“歧義”。我們對測試集中32個待消歧人名的社會網(wǎng)絡(luò)歧義現(xiàn)象進行了統(tǒng)計,統(tǒng)計結(jié)果如表2所示。統(tǒng)計時,我們默認出現(xiàn)在同一篇文本中的名字僅代表一個實體,表中“多指總數(shù)”是指出現(xiàn)在多于一個文本中的實體名稱總數(shù);“歧義總數(shù)”是指實體名稱出現(xiàn)在多個文本中,但這些文本在待消歧人名的標準聚類中卻不屬于同一類的實體名稱數(shù)量,也就是“歧義”的數(shù)量;“比例”表示“歧義總數(shù)”占“多指總數(shù)”的比率?！皩嶓w關(guān)系對”為存在共現(xiàn)的實體對。

“實體”的歧義比例達到19.53%,所以僅僅根據(jù)社會網(wǎng)絡(luò)基本圖來進行人名消歧是不準確的?！皩嶓w關(guān)系對”的歧義比例為3.16%,社會網(wǎng)絡(luò)聚類對“實體關(guān)系歧義”進行分析,對于人名消歧任務(wù)是很有幫助的。

表2 測試集中社會網(wǎng)絡(luò)歧義比例統(tǒng)計

5.3 實驗二：實體關(guān)系權(quán)值計算方法對比

前面第3節(jié)介紹了三種實體關(guān)系緊密度的計算方式：共現(xiàn)作為權(quán)值、共現(xiàn)頻次作為權(quán)值和共現(xiàn)頻次對數(shù)作為權(quán)值。共現(xiàn)權(quán)值矩陣為01矩陣,值為0代表兩個實體沒有共現(xiàn),1為有共現(xiàn)。共現(xiàn)頻次權(quán)值矩陣的元素為兩實體共現(xiàn)頻次。共現(xiàn)頻次對數(shù)權(quán)值矩陣,對共現(xiàn)次數(shù)計算對數(shù)值,并加入常數(shù)指標c進行平滑。

本實驗對將實體關(guān)系權(quán)值不同計算方法進行對比,使用SM算法,設(shè)置歧義人名的標準類別個數(shù)作為社會網(wǎng)絡(luò)聚類個數(shù),在對數(shù)化矩陣中設(shè)置c=1。實驗結(jié)果如表3所示。

表3 實體關(guān)系權(quán)值計算方法實驗對比

在32個人名消歧的實驗中,有14個人名的聚類實驗使用三種實體關(guān)系矩陣得到完全相同的結(jié)果,平均F值的數(shù)值僅有約0.4%的差別,最佳結(jié)果人名數(shù)也沒有特別大的差別。這說明實體關(guān)系權(quán)值的計算方法對基于社會網(wǎng)絡(luò)的人名消歧實驗影響不大。

5.4 實驗三：譜聚類圖劃分準則函數(shù)對比

實驗研究不同圖劃分準則對人名消歧的影響,設(shè)置歧義人名的標準類別個數(shù)作為社會網(wǎng)絡(luò)聚類個數(shù) ,將 MiNcut、Rcut、Ncut 圖劃分準則使用在社會網(wǎng)絡(luò)聚類的人名消歧實驗中,并將實驗結(jié)果進行比較。如表4所示。

對每個人名測試數(shù)據(jù)取 Ncut、Rcut、MiNcut三種圖劃分準則下的最佳結(jié)果比較,若Ncut對應(yīng)的結(jié)果在三個結(jié)果中的表現(xiàn)最好,則 Ncut對應(yīng)的#best統(tǒng)計量加1。因此,#best統(tǒng)計量高表明對應(yīng)的劃分準則表現(xiàn)好。根據(jù)以上表格可知,從#best值統(tǒng)計量來看,Ncut和Rcut的結(jié)果要好于Mincut。加之 Ncut的 F值最高,所以 Ncut又好于Rcut方法。從更多細節(jié)來看,在32個人名消歧的實驗中,Ncut和 Rcut的#best都是22,其中聚類效果完全一樣的有14個,也說明了這兩種方法的結(jié)果一致性是比較高的。

表4 圖劃分準則函數(shù)實驗對比

5.5 實驗四：譜聚類停止條件對比

SM算法與自頂向下的層次聚類的過程類似,構(gòu)造了一顆聚類樹,需要定義停止條件來決定聚類樹的停止層次,即最終類別的個數(shù)。本文4.3節(jié)介紹了基于模塊度的譜聚類停止條件計算方法。本實驗按模塊度停止條件進行實驗,結(jié)果如表5所示。

表5 模塊度停止條件實驗對比

從實驗結(jié)果來看,停止條件的效果并不好。由于在實際網(wǎng)絡(luò)中該值通常位于0.3～0.7之間,我們一共對三個閾值0.41、0.4、0.3進行了實驗。在最好結(jié)果中,平均精確率和平均召回率大致相等,F值也只有67.94%。在我們的實驗中,模塊度停止條件的結(jié)果并不好,一個可能的原因是使用了統(tǒng)一的模塊度閾值。不同的人名需要的模塊度閾值可能是不一樣的。本文對模塊度閾值等于0.41時,共有13個人名的F值低于70%。閾值取值不恰當,精確率和召回率會嚴重分化,從而導(dǎo)致F值很低。隨著精確率和召回率之間的值差越來越小,F值逐漸升高。F值超過80%的人名實驗也是13個,所取的閾值可能符合預(yù)期。

由實驗的結(jié)果來看,如果要將社會網(wǎng)絡(luò)聚類運用到人名消歧中,需要解決停止條件的問題,這也是聚類算法普遍面臨的問題。

6 結(jié)論

本文研究了基于社會網(wǎng)絡(luò)的人名消歧。社會網(wǎng)絡(luò)表示了特定實體之間比較持久的、穩(wěn)定的社會關(guān)系。社會網(wǎng)絡(luò)可以看成由多個節(jié)點構(gòu)成的一種社會結(jié)構(gòu),節(jié)點通常是指人或組織機構(gòu)。節(jié)點之間的邊代表各種社會關(guān)系。

在基于社會網(wǎng)絡(luò)的人名消歧中,將人名消歧看成是社會網(wǎng)絡(luò)的圖劃分問題。本文詳細討論了社會網(wǎng)絡(luò)獲取、關(guān)系矩陣構(gòu)造、社會網(wǎng)絡(luò)聚類、社會網(wǎng)絡(luò)映射的實現(xiàn)。社會網(wǎng)絡(luò)聚類主要是采取了譜聚類的方法,介紹了譜聚類中的譜圖理論、圖劃分準則、譜聚類算法及模塊度停止條件。最后,針對基于社會網(wǎng)絡(luò)的人名消歧進行了實驗。

今后的工作重點是對社會網(wǎng)絡(luò)分析功能的完善和社會網(wǎng)絡(luò)聚類停止條件的研究。同時,采用更好的實體識別模塊來提高識別正確率,增加其他類型的命名實體作為特征以及將文本聚類的思想與之相結(jié)合,以更好地實現(xiàn)人名消歧。

[1]J.Artiles,J.Gonzalo,S.Sekine.The SemEval-2007WePS Evaluation：Establishing a benchmark for the Web People Search Task[C]//SemEval,2007.

[2]A.Bagga,B.Baldwin.Entity-based cross-document coreferencing using the Vector Space Model[C]//Proceedings of the 17th international conference on Computational linguistics-Volume 1,1998：79-85.

[3]G.S.Mann,D.Yarowsky.Unsupervised personal name disambiguation[C]//Proceedings of the seventh conference on Natural languagelearningat HLTNAACL,2003：33-40.

[4]M.B.Fleischman,E.Hovy.Multi-document person name resolution[C]//Proceedings of ACL-42,Reference Resolution Workshop,2004.

[5]B.M alin.Unsupervised Name Disambiguation via Social Network Similarity[C]//Workshop Notes on Link Analysis,Counterterrorism,and Security,2005.

[6]郎君,秦兵,宋巍,等.基于社會網(wǎng)絡(luò)的人名檢索結(jié)果重名消歧[J].計算機學報,2009,32(7)：1365-1374.

[7]T.Pedersen,K.Anagha.Automatic Cluster Stopping with Criterion Functions and the Gap Statistic[C]//Proceedings of the Demonstration Session of the Human Language Technology Conference and the Sixth Annual Meeting of the North American Chapter of the Association for Computational Linguistic,New York City.2006.

[8]Scott J.Social network analysis：A handbook(2nd ed.)[M].Thousands Oaks,CA：Sage.2000.

[9]Ng A,Jordan M,Weiss Y.On spectral clustering：A-nalysis and an algorithm.Advances in Neural Information Precessing Systems 14[C]//MIT Press,2002.

[10]Z.Wu,R.Leahy.An Optimal Graph Theoretic Approach to Data Clustering：Theory and Its Application to Image Segmentation[J].IEEE Trans.Pattern Analysis and Machine Intelligence,1993,15(11)：1101-1113.

[11]Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Trans.Pattern Analysis and Machine Intelligence,2000,22(8)：888-905.

[12]L.Hagen,A.B.Kahng.New spectral methods for ratio cut partitioning and clustering[J].IEEE.T rans.On Computed Aided Desgin,1992,11：1074-1085.

[13]Newman M.E.J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2)：026113.