基于圖的中文集成實(shí)體鏈接算法

劉 嶠 鐘 云 李 楊 劉 瑤 秦志光

（電子科技大學(xué)信息與軟件工程學(xué)院 成都 610054）（qliu＠uestc．edu．cn）

基于圖的中文集成實(shí)體鏈接算法

劉 嶠 鐘 云 李 楊 劉 瑤 秦志光

（電子科技大學(xué)信息與軟件工程學(xué)院 成都 610054）（qliu＠uestc．edu．cn）

實(shí)體鏈接（entity linking）是知識(shí)庫(kù)擴(kuò)容的核心關(guān)鍵技術(shù)，傳統(tǒng)的實(shí)體鏈接方法通常受制于本地知識(shí)庫(kù)的知識(shí)水平，而且忽略共現(xiàn)實(shí)體間的語(yǔ)義相關(guān)性．提出了一種基于圖的中文集成實(shí)體鏈接方法，不僅能夠充分利用知識(shí)庫(kù)中實(shí)體間的結(jié)構(gòu)化關(guān)系，而且能夠通過(guò)增量證據(jù)挖掘獲取外部知識(shí)，從而實(shí)現(xiàn)對(duì)同一文本中出現(xiàn)的多個(gè)歧義實(shí)體的批量實(shí)體鏈接．在開(kāi)放域公開(kāi)測(cè)試語(yǔ)料上的實(shí)驗(yàn)結(jié)果表明，所提出的實(shí)體相關(guān)圖構(gòu)造方法、增量證據(jù)挖掘方法和實(shí)體語(yǔ)義一致性判據(jù)是有效的，算法整體性能一致且顯著地優(yōu)于當(dāng)前的主流算法．

集成實(shí)體鏈接；知識(shí)庫(kù)擴(kuò)容；知識(shí)圖譜；實(shí)體相關(guān)圖；中文信息處理

實(shí)體鏈接（entity linking）是文本分析會(huì)議（text analysis conference，TAC）知識(shí)庫(kù)構(gòu)建領(lǐng)域設(shè)定的基本挑戰(zhàn)，任務(wù)目標(biāo)是將從文本中提取到的實(shí)體指稱(chēng)項(xiàng)正確地鏈接到知識(shí)庫(kù)中對(duì)應(yīng)的實(shí)體對(duì)象上［1］．

實(shí)體鏈接是知識(shí)庫(kù)擴(kuò)容的核心關(guān)鍵技術(shù)．隨著面向開(kāi)放域的信息抽取技術(shù)的發(fā)展，人們有可能從海量開(kāi)放數(shù)據(jù)中自動(dòng)抽取出實(shí)體、關(guān)系和屬性信息［2－4］．然而，通過(guò)開(kāi)放域抽取得到的知識(shí)元素間的關(guān)系是扁平化的，缺乏層次性和邏輯性，甚至可能包含大量冗余和錯(cuò)誤信息．為建立結(jié)構(gòu)化的知識(shí)庫(kù)，首先必須解決知識(shí)融合的問(wèn)題，實(shí)體鏈接技術(shù)就是用于解決知識(shí)庫(kù)構(gòu)建過(guò)程中遇到的實(shí)體映射問(wèn)題的信息融合技術(shù)．通過(guò)實(shí)體鏈接，可以消除概念的歧義，剔除冗余和錯(cuò)誤概念，從而確保知識(shí)的質(zhì)量［5］．

具體說(shuō)來(lái)，通過(guò)實(shí)體鏈接可以解決實(shí)體指稱(chēng)項(xiàng)的歧義性和多樣性問(wèn)題［6］．實(shí)體指稱(chēng)項(xiàng)的歧義性是指相同的實(shí)體指稱(chēng)項(xiàng)在不同的上下文環(huán)境中有可能指向不同的實(shí)體對(duì)象，例如實(shí)體指稱(chēng)項(xiàng)“張三”在不同的語(yǔ)境下可能指代不同的實(shí)體對(duì)象．實(shí)體指稱(chēng)項(xiàng)的多樣性則是指某個(gè)特定的實(shí)體對(duì)象，可能與多個(gè)不同的實(shí)體指稱(chēng)項(xiàng)（如別名、縮寫(xiě)等）相對(duì)應(yīng)，例如NBA球星“邁克爾·喬丹”在不同的語(yǔ)境中可以采用“喬丹”、“飛人”甚至姓名縮寫(xiě)“M．J”來(lái)指代．

實(shí)體鏈接技術(shù)不僅具有重要的理論研究?jī)r(jià)值，而且有著重要和迫切的實(shí)際應(yīng)用價(jià)值．知識(shí)庫(kù)擴(kuò)容是自然語(yǔ)言處理、人工智能和專(zhuān)家系統(tǒng)等相關(guān)領(lǐng)域共同關(guān)注的熱點(diǎn)研究領(lǐng)域，而實(shí)體鏈接問(wèn)題是當(dāng)前該領(lǐng)域面臨的主要研究挑戰(zhàn)［5］．近年來(lái)，隨著實(shí)體鏈接技術(shù)的發(fā)展，知識(shí)庫(kù)自動(dòng)構(gòu)建和擴(kuò)容技術(shù)也不斷取得進(jìn)展，一些商用和公益性知識(shí)庫(kù)的規(guī)模得到了迅速擴(kuò)張，例如，WolframAlpha知識(shí)庫(kù)的實(shí)體總數(shù)已超過(guò)10萬(wàn)億條，而谷歌知識(shí)圖譜則擁有5億個(gè)實(shí)體和350億條實(shí)體間的關(guān)系．然而，現(xiàn)有的實(shí)體鏈接技術(shù)仍存在明顯的局限性，如依賴(lài)百科知識(shí)作為實(shí)體鏈接的知識(shí)來(lái)源，導(dǎo)致處理開(kāi)放域?qū)嶓w鏈接任務(wù)時(shí)的性能不穩(wěn)定和計(jì)算效率低下．一旦面向開(kāi)放域的實(shí)體鏈接技術(shù)取得突破，將對(duì)知識(shí)庫(kù)的擴(kuò)容產(chǎn)生極大的推動(dòng)作用，進(jìn)而對(duì)知識(shí)庫(kù)應(yīng)用產(chǎn)生深遠(yuǎn)影響［7］．

現(xiàn)有的實(shí)體鏈接研究成果主要面向英文處理，相對(duì)而言，中文實(shí)體鏈接技術(shù)的發(fā)展稍微有些滯后，主要有如下3方面原因：1）英文的開(kāi)源知識(shí)庫(kù)建設(shè)起步較早，已建成一些較為成熟的知識(shí)庫(kù)，如DBpedia①，F(xiàn)reebase②等，而中文開(kāi)源知識(shí)庫(kù)目前仍處于起步階段，對(duì)實(shí)體鏈接研究工作形成一定的制約；2）中文實(shí)體抽取技術(shù)受制于分詞技術(shù)，分詞和詞性標(biāo)注是中文信息處理技術(shù)的難點(diǎn)，也是制約實(shí)體鏈接技術(shù)發(fā)展和應(yīng)用的關(guān)鍵問(wèn)題之一；3）中文實(shí)體的共指和消歧處理難度比英文更大，原因是中文的語(yǔ)法更為靈活，語(yǔ)義也更加豐富［8］．中文是僅次于英語(yǔ)的世界性語(yǔ)言，對(duì)中文實(shí)體鏈接的研究可以促進(jìn)中文知識(shí)庫(kù)的擴(kuò)容，進(jìn)而提高對(duì)中文信息的智能處理水平，因此是極具前景的研究方向，近年來(lái)吸引了大量的研究努力，TAC 2015會(huì)議也將跨語(yǔ)言實(shí)體鏈接（中文、英文、西班牙語(yǔ)）定為主要挑戰(zhàn)．本文的研究目標(biāo)就是致力于解決中文實(shí)體鏈接研究中當(dāng)前面臨的主要挑戰(zhàn)性問(wèn)題．

當(dāng)前主流的實(shí)體鏈接方法采用基于相似度比較的思路，即通過(guò)計(jì)算實(shí)體指稱(chēng)項(xiàng)與其相應(yīng)的候選實(shí)體間的上下文相似度，選擇相似度最高的候選實(shí)體作為鏈接目標(biāo)［9－10］．該方法的局限性在于每次僅處理文本中出現(xiàn)的一個(gè)待定實(shí)體指稱(chēng)項(xiàng)，計(jì)算效率低，且未考慮該文本中共現(xiàn)實(shí)體間的語(yǔ)義相關(guān)性，造成信息浪費(fèi)和實(shí)體鏈接準(zhǔn)確率降低．研究表明，利用詞語(yǔ)間的共現(xiàn)關(guān)系能夠有效提高消歧的準(zhǔn)確性［11］．本文提出一種基于圖的中文集成實(shí)體鏈接算法（graph－based collective Chinese entity linking algorithm，GCCEL），通過(guò)將文本中出現(xiàn)的實(shí)體指稱(chēng)項(xiàng)以及其候選實(shí)體集合視為圖的頂點(diǎn)集合，利用實(shí)體間的語(yǔ)義相關(guān)性構(gòu)造實(shí)體相關(guān)圖，以圖中頂點(diǎn)的語(yǔ)義一致性為判據(jù)，實(shí)現(xiàn)對(duì)同一文本中出現(xiàn)的多個(gè)實(shí)體的批量實(shí)體鏈接．與相關(guān)工作相比，本文的主要貢獻(xiàn)在于：

1）所設(shè)計(jì)的實(shí)體相關(guān)圖綜合考慮了實(shí)體間的語(yǔ)義相關(guān)度、上下文相似度、實(shí)體的知名度（流行程度）以及實(shí)體在知識(shí)庫(kù)和外部知識(shí)源中表現(xiàn)出的間接語(yǔ)義關(guān)聯(lián)等要素，能夠更準(zhǔn)確地輔助實(shí)現(xiàn)候選實(shí)體的區(qū)分和判別，達(dá)成精準(zhǔn)實(shí)體鏈接的目標(biāo)；

2）在實(shí)體相關(guān)圖構(gòu)造過(guò)程中引入了增量證據(jù)挖掘的思想，在充分利用本地知識(shí)庫(kù)中既有知識(shí)的基礎(chǔ)上，能夠有效利用第三方知識(shí)源提供的實(shí)體背景知識(shí)，從而在降低對(duì)本地知識(shí)庫(kù)的依賴(lài)的同時(shí)，顯著提升實(shí)體鏈接算法的準(zhǔn)確率和召回率；

①http：??datahub．io?dataset?dbpedia

②https：??www．freebase．com

3）提出了一個(gè)完整的基于實(shí)體相關(guān)圖的中文實(shí)體集成鏈接算法原型和一種全新的實(shí)體語(yǔ)義一致性計(jì)算方法，并基于實(shí)體相關(guān)圖實(shí)現(xiàn)了對(duì)開(kāi)放域文本語(yǔ)料的批量實(shí)體鏈接．實(shí)驗(yàn)結(jié)果表明，該算法的準(zhǔn)確率和召回率優(yōu)于當(dāng)前主流的相關(guān)工作，且所需的訓(xùn)練樣本規(guī)模較小，方法適應(yīng)性和推廣性較好．

1 相關(guān)工作

實(shí)體鏈接任務(wù)是知識(shí)庫(kù)構(gòu)建領(lǐng)域當(dāng)前面臨的關(guān)鍵問(wèn)題和基本挑戰(zhàn)之一，由于該技術(shù)對(duì)于知識(shí)庫(kù)擴(kuò)容具有重要的基礎(chǔ)研究?jī)r(jià)值，近年來(lái)受到了學(xué)術(shù)界的廣泛關(guān)注．早期的實(shí)體鏈接研究思路主要針對(duì)單一實(shí)體進(jìn)行考慮，即逐一地將從外部語(yǔ)料中抽取得到的實(shí)體映射到知識(shí)庫(kù)中．近年來(lái)，隨著一系列集成實(shí)體鏈接方法的提出，該類(lèi)方法逐漸成為研究熱點(diǎn)．本節(jié)將首先簡(jiǎn)要介紹實(shí)體鏈接方法的研究進(jìn)展概況，然后重點(diǎn)討論與本文工作密切相關(guān)的集成實(shí)體鏈接方法．

1．1 單實(shí)體鏈接方法

單實(shí)體鏈接方法一次僅對(duì)文本中的一個(gè)實(shí)體進(jìn)行鏈接，而不考慮文本中其他共現(xiàn)實(shí)體的影響．基本研究思路是通過(guò)計(jì)算從文本中抽取得到的實(shí)體指稱(chēng)項(xiàng)與從知識(shí)庫(kù)查詢(xún)得到的候選實(shí)體之間的上下文相似度，選擇相似度最大的候選實(shí)體作為鏈接目標(biāo)．代表性工作是Bunescu等人提出的基于上下文的相似度計(jì)算模型，該模型以維基百科為知識(shí)庫(kù)，對(duì)于給定文本中抽取得到的實(shí)體指稱(chēng)項(xiàng)，在維基百科上查找相應(yīng)的候選實(shí)體構(gòu)成集合，然后利用詞袋模型計(jì)算給定文本和候選實(shí)體所在的維基頁(yè)面之間的余弦相似度，選擇相似度最大的候選實(shí)體作為鏈接對(duì)象［9］．

該項(xiàng)研究工作引發(fā)了學(xué)術(shù)界對(duì)基于相似度計(jì)算的實(shí)體鏈接方法的關(guān)注，產(chǎn)生了一些具備實(shí)用價(jià)值的成果．其中，Silviu在計(jì)算實(shí)體間的余弦相似度時(shí)加入了對(duì)實(shí)體間類(lèi)別相關(guān)性的考慮，在維基百科和新聞網(wǎng)頁(yè)語(yǔ)料上分別取得了88．3%和91．4%的實(shí)體鏈接準(zhǔn)確率［10］．類(lèi)似的方法擴(kuò)展工作還包括Nguyen等人提出的相似度計(jì)算模型，該模型在計(jì)算相似度時(shí)加入了候選實(shí)體在維基百科頁(yè)面的上下文特征（關(guān)鍵詞）和頁(yè)面結(jié)構(gòu)特征（如頁(yè)面重定向、實(shí)體類(lèi)別、錨文本等），從而有效提高了算法的準(zhǔn)確性［12］．

針對(duì)多個(gè)候選實(shí)體可能具有相同的余弦相似度的問(wèn)題，Zeng等人提出采用外部知識(shí)擴(kuò)展實(shí)體指稱(chēng)項(xiàng)特征向量的解決方案（在該論文中是以實(shí)體指稱(chēng)項(xiàng)上下文詞的維基百科頁(yè)面作為外部知識(shí)源，對(duì)輸入文本的特征向量進(jìn)行擴(kuò)展，然后在迭代計(jì)算實(shí)體指稱(chēng)項(xiàng)與其候選實(shí)體的上下文相似度），該方法在新浪微博數(shù)據(jù)集上取得了88．5%的實(shí)體鏈接準(zhǔn)確率［13］．

基于實(shí)體上下文相似度的實(shí)體鏈接算法通常受制于上下文信息的不足，為此Zhang等人提出了一種基于圖模型的維基概念相似度計(jì)算方法，該方法借助維基百科提供的實(shí)體上下文，能夠有效提高實(shí)體指稱(chēng)項(xiàng)與候選實(shí)體間的語(yǔ)義相似度計(jì)算準(zhǔn)確性，在TAC2011會(huì)議的KBP數(shù)據(jù)集取得了80．40%的準(zhǔn)確率［14］．本文提出的GCCEL算法與該方法的主要區(qū)別在于實(shí)體相關(guān)圖的構(gòu)造方法不同．首先，Zhang等人提出的方法僅考慮實(shí)體間的直接上下文關(guān)聯(lián)關(guān)系，而GCCEL算法則在此基礎(chǔ)上進(jìn)一步考慮到了實(shí)體間的間接語(yǔ)義關(guān)聯(lián)關(guān)系，即2個(gè)目標(biāo)實(shí)體均與第三方存在直接關(guān)系的情況．其次，Zhang等人提出的算法是基于全局的維基概念圖的（圖中包含260萬(wàn)個(gè)節(jié)點(diǎn)、5 100萬(wàn)條邊），而本文提出的算法僅針對(duì)輸入文本中出現(xiàn)的實(shí)體構(gòu)造相關(guān)子圖，因此計(jì)算效率更高．

除了基于相似度計(jì)算的方法外，一些學(xué)者還嘗試將統(tǒng)計(jì)機(jī)器學(xué)習(xí)方法引入到實(shí)體鏈接工作中．例如，Zuo等人提出了一個(gè)投票模型，思路是將奇數(shù)個(gè)實(shí)體鏈接方法作為分類(lèi)器，在鏈接時(shí)分別對(duì)每個(gè)候選實(shí)體進(jìn)行0?1判定，獲得半數(shù)以上選票的候選實(shí)體將成為最終的鏈接對(duì)象．該方法在KORE，CoNLLYAGO，CUCERZAN等基準(zhǔn)數(shù)據(jù)集上測(cè)試的結(jié)果顯示，F(xiàn)1值分別達(dá)到了77．83%，87．98%，88．61%［15］．

1．2 集成實(shí)體鏈接方法

單實(shí)體鏈接方法的主要缺點(diǎn)在于沒(méi)有考慮同一篇文檔中出現(xiàn)的實(shí)體間的語(yǔ)義相關(guān)性，而這種由共現(xiàn)關(guān)系導(dǎo)致的語(yǔ)義相關(guān)性對(duì)于區(qū)分有歧義的實(shí)體通常是有幫助的．為了解決這一問(wèn)題，Han等學(xué)者提出了基于實(shí)體共現(xiàn)關(guān)系的集成實(shí)體鏈接方法［16］．

集成實(shí)體鏈接方法的基本思想是對(duì)給定文本中出現(xiàn)的所有實(shí)體指稱(chēng)項(xiàng)，在當(dāng)前的上下文環(huán)境中根據(jù)語(yǔ)義關(guān)聯(lián)關(guān)系同步進(jìn)行消歧，即批量地將其鏈接到本地知識(shí)庫(kù)中對(duì)應(yīng)的實(shí)體對(duì)象上．與單實(shí)體鏈接方法相比，集成實(shí)體鏈接方法的另一個(gè)優(yōu)點(diǎn)是采用語(yǔ)義相關(guān)圖的方式表示文檔中實(shí)體間的語(yǔ)義關(guān)系，從而避免了逐一掃描待定實(shí)體，分別進(jìn)行消歧處理的單線程處理模式，因此有助于提高實(shí)體鏈接效率．

Han等人提出的集成實(shí)體鏈接算法以維基百科作為本地知識(shí)庫(kù)，對(duì)給定文本，首先提取出所有實(shí)體指稱(chēng)項(xiàng)，并通過(guò)查詢(xún)確定每個(gè)實(shí)體指稱(chēng)項(xiàng)在知識(shí)庫(kù)中的候選鏈接對(duì)象；然后，將實(shí)體指稱(chēng)項(xiàng)和候選實(shí)體視為圖的頂點(diǎn)，以實(shí)體間的谷歌距離（Google distance）作為語(yǔ)義相關(guān)性測(cè)度，建立與該文本對(duì)應(yīng)的實(shí)體相關(guān)圖；最后，采用隨機(jī)游走方法對(duì)圖中的候選實(shí)體進(jìn)行排序，得到實(shí)體鏈接的推薦結(jié)果．在維基百科和IITB等基準(zhǔn)語(yǔ)料上的實(shí)驗(yàn)結(jié)果表明，基于圖的集成實(shí)體鏈接算法性能優(yōu)于當(dāng)前主流的單實(shí)體鏈接方法［16］．

該方法的提出在業(yè)界和學(xué)術(shù)界形成了廣泛影響，近年來(lái)涌現(xiàn)出大量相關(guān)工作．其中，Shen等人基于維基百科和Yago知識(shí)庫(kù)提出的LINDEN模型將實(shí)體間的語(yǔ)義關(guān)聯(lián)進(jìn)一步區(qū)分為語(yǔ)義相似性和全局相關(guān)性，在TAC2009會(huì)議數(shù)據(jù)集上實(shí)現(xiàn)了高達(dá)84．32%的實(shí)體鏈接準(zhǔn)確率［17］．Johannes等人則進(jìn)一步考慮了實(shí)體流行度和相似度等因素，并據(jù)此設(shè)計(jì)實(shí)現(xiàn)了一個(gè)面向?qū)嶋H應(yīng)用的AIDA實(shí)體鏈接原型系統(tǒng)［18］．在上述工作的基礎(chǔ)上，Ayman等人通過(guò)修改頂點(diǎn)初始（概率）值的方式，將實(shí)體上下文相似度和實(shí)體流行度等因素結(jié)合到PageRank算法原型中，在AIDA數(shù)據(jù)集上實(shí)現(xiàn)了86．10%的實(shí)體鏈接準(zhǔn)確率［19］．

然而，這些方法存在的共同問(wèn)題是依賴(lài)實(shí)體所在的百科頁(yè)面作為知識(shí)源，對(duì)于非知名實(shí)體的消歧任務(wù)而言，方法的適用性較差［20］．為解決該問(wèn)題，Andrea等人利用BabelNet語(yǔ)義網(wǎng)絡(luò)，采用帶重啟的隨機(jī)游走（random walk with restart，RWR）算法來(lái)計(jì)算實(shí)體間的語(yǔ)義相關(guān)性（稱(chēng)為語(yǔ)義簽名），以此為基礎(chǔ)構(gòu)造實(shí)體相關(guān)圖，并采用抽取密集子圖的方式實(shí)現(xiàn)實(shí)體消歧．所提出的Babelfy算法在KORE和和CoNLL等基準(zhǔn)數(shù)據(jù)集上的準(zhǔn)確率分別達(dá)到71．5%和82．1%，是目前性能表現(xiàn)最好算法之一［21］．Babelfy算法雖然部分降低了對(duì)百科知識(shí)的依賴(lài)，但卻增加了對(duì)本地知識(shí)庫(kù)的依賴(lài)．為充分利用海量公開(kāi)數(shù)據(jù)中包含的實(shí)體區(qū)分性證據(jù)，Li等人提出了增量證據(jù)挖掘的思想，基本思路是采用外部知識(shí)庫(kù)作為對(duì)本地知識(shí)庫(kù)中實(shí)體知識(shí)的補(bǔ)充，在Twitter數(shù)據(jù)集上的模擬實(shí)驗(yàn)表明，采用基于生成模型的增量證據(jù)挖掘方法，能夠有效地提升實(shí)體鏈接的準(zhǔn)確率［22］．

與其他基于圖的集成實(shí)體鏈接方法相比，本文提出的GCCEL算法的主要特點(diǎn)是：在實(shí)體相關(guān)圖的構(gòu)造階段考慮到語(yǔ)義關(guān)系相近的實(shí)體之間的間接關(guān)聯(lián)，并引入了增量證據(jù)挖掘機(jī)制，在實(shí)體鏈接階段綜合考慮了實(shí)體相關(guān)圖的拓?fù)浣Y(jié)構(gòu)特征和實(shí)體間的語(yǔ)義相似性特征．通過(guò)上述改進(jìn)，GCCEL算法能夠有效降低現(xiàn)有基于圖的集成實(shí)體鏈接方法對(duì)本地知識(shí)庫(kù)和單一外部知識(shí)源的依賴(lài)性，顯著提高實(shí)體鏈接算法的準(zhǔn)確率和召回率．此外，與Li等人提出的算法相比，本文提出的增量證據(jù)挖掘方法不是基于生成模型，而是基于實(shí)體間的上下文關(guān)聯(lián)性，因此在計(jì)算上更為簡(jiǎn)捷高效，模型本身也更為直觀，易于理解和擴(kuò)展．

2 基于圖的中文集成實(shí)體鏈接算法

本文提出的基于圖的中文實(shí)體集成鏈接方法由3個(gè)模塊構(gòu)成：候選實(shí)體生成模塊、實(shí)體相關(guān)圖構(gòu)造模塊和集成實(shí)體鏈接模塊，如圖1所示：

Fig．1 The framework of the graph－based collective Chinese entity linking algorithm．圖1 基于圖的中文集成實(shí)體鏈接算法框架

候選實(shí)體生成模塊的主要功能是對(duì)于給定的輸入語(yǔ)料，識(shí)別出其中的所有實(shí)體指稱(chēng)項(xiàng)，據(jù)此分別查找本地知識(shí)庫(kù)，得到與該實(shí)體指稱(chēng)項(xiàng)同名的候選實(shí)體集合，作為后續(xù)構(gòu)造實(shí)體相關(guān)圖的頂點(diǎn)集合．

實(shí)體相關(guān)圖構(gòu)造模塊的主要功能是針對(duì)從同一文本中抽取得到的所有實(shí)體指稱(chēng)項(xiàng)和相應(yīng)的候選實(shí)體集合，構(gòu)造出一張?jiān)撐谋镜膶?shí)體參考關(guān)系圖（referent graph），作為集成實(shí)體鏈接的依據(jù)．為簡(jiǎn)化描述，下文將實(shí)體參考關(guān)系圖簡(jiǎn)稱(chēng)為實(shí)體相關(guān)圖．為彌補(bǔ)本地知識(shí)庫(kù)知識(shí)容量不足的問(wèn)題，在實(shí)體相關(guān)圖的構(gòu)造階段，引入了增量證據(jù)挖掘機(jī)制．

集成實(shí)體鏈接模塊的主要功能是借助實(shí)體相關(guān)圖實(shí)現(xiàn)對(duì)輸入語(yǔ)料中歧義實(shí)體的消歧，將其正確鏈接到本地知識(shí)庫(kù)中的正確的實(shí)體對(duì)象上．基本方法是基于實(shí)體指稱(chēng)項(xiàng)所在文本語(yǔ)料與其候選實(shí)體百科頁(yè)面的余弦相似度和候選實(shí)體的出入度，計(jì)算每個(gè)候選實(shí)體與其對(duì)應(yīng)的實(shí)體指稱(chēng)項(xiàng)的語(yǔ)義一致性，并選擇語(yǔ)義一致性最高的候選實(shí)體作為最終的目標(biāo)鏈接對(duì)象．

2．1 候選實(shí)體生成

本文使用的知識(shí)庫(kù)（以下稱(chēng)本地知識(shí)庫(kù)）以清華大學(xué)發(fā)布的中文知識(shí)庫(kù)為基礎(chǔ)構(gòu)建①，該知識(shí)庫(kù)包含19 542個(gè)概念（類(lèi)別）和802 593個(gè)實(shí)體．為提高實(shí)體語(yǔ)義相似度計(jì)算結(jié)果的準(zhǔn)確性，本文采用百度百科作為外部知識(shí)源對(duì)該知識(shí)庫(kù)中的實(shí)體屬性知識(shí)進(jìn)行了擴(kuò)充．具體方法是針對(duì)知識(shí)庫(kù)中的每個(gè)實(shí)體，抓取實(shí)體對(duì)應(yīng)的百科頁(yè)面，借助頁(yè)面的Infobox抽取該實(shí)體的基本屬性和關(guān)系屬性信息，所抽取的實(shí)體基本屬性包括別名、身高、性別等，所抽取的實(shí)體關(guān)系屬性包括朋友關(guān)系、夫妻關(guān)系、父母關(guān)系等．經(jīng)過(guò)擴(kuò)充后的實(shí)體知識(shí)庫(kù)采用Neo4j圖數(shù)據(jù)庫(kù)進(jìn)行管理．

本地知識(shí)庫(kù)中的同名歧義實(shí)體帶有后綴標(biāo)簽，例如，對(duì)于實(shí)體指稱(chēng)項(xiàng)“李娜”，在本地知識(shí)庫(kù)中有三個(gè)實(shí)體對(duì)象與之對(duì)應(yīng)，后綴標(biāo)簽分別為“北京大學(xué)教授”、“歌手”和“網(wǎng)球運(yùn)動(dòng)員”．采用帶括號(hào)的后綴標(biāo)簽來(lái)表達(dá)和區(qū)分這些歧義實(shí)體，如：李娜（歌手）．

為提高檢索效率，在構(gòu)建本地知識(shí)庫(kù)時(shí)，為每個(gè)實(shí)體節(jié)點(diǎn)建立索引，同名的候選實(shí)體具有相同的索引，指向同一實(shí)體指稱(chēng)項(xiàng)．這樣在查詢(xún)時(shí)，可以一次性查找到給定實(shí)體指稱(chēng)項(xiàng)所對(duì)應(yīng)的所有候選實(shí)體對(duì)象．本文采用Lucene②對(duì)知識(shí)庫(kù)中的實(shí)體建立索引．

候選實(shí)體的生成過(guò)程包括2個(gè)步驟：首先，從給定文本中識(shí)別出所有的實(shí)體指稱(chēng)項(xiàng)．分詞工具采用中科院計(jì)算所發(fā)布的NLPIR漢語(yǔ)分詞系統(tǒng)，根據(jù)輸出的詞性標(biāo)注結(jié)果進(jìn)行實(shí)體識(shí)別．例如，詞性nr表示人名、ns表示地名、nt表示機(jī)構(gòu)名、nz表示其他專(zhuān)用名詞等．為提高實(shí)體識(shí)別結(jié)果的精確率和召回率，采用自定義規(guī)則和添加用戶(hù)字典的方式，對(duì)NLPIR系統(tǒng)進(jìn)行了修正．通過(guò)實(shí)體識(shí)別，可得到文本中所有待定實(shí)體指稱(chēng)項(xiàng)集合M＝｛m1，m2，…，mn｝．

然后，針對(duì)從當(dāng)前語(yǔ)料中識(shí)別出的每個(gè)實(shí)體指稱(chēng)項(xiàng)mi，在本地知識(shí)庫(kù)中進(jìn)行索引查找，若知識(shí)庫(kù)中存在與之同名的索引項(xiàng)，則將該索引項(xiàng)對(duì)應(yīng)的所有實(shí)體對(duì)象作為其初步的候選實(shí)體集合Ni＝｛ni1，ni2，…｝，其中，nik表示實(shí)體指稱(chēng)mi所對(duì)應(yīng)的第k個(gè)候選實(shí)體對(duì)象．最終，得到實(shí)體指稱(chēng)項(xiàng)集合M的初步候選實(shí)體對(duì)象集合N′＝｛N1，N2，…，Nn｝．

2．2 實(shí)體相關(guān)圖構(gòu)造

本文提出的基于圖的集成實(shí)體鏈接算法對(duì)每篇輸入的文本語(yǔ)料構(gòu)造一張實(shí)體相關(guān)圖G＝（V，E），以實(shí)現(xiàn)對(duì)文中實(shí)體的集成鏈接目標(biāo)．其中，V表示頂點(diǎn)集合，E表示邊集合．實(shí)體相關(guān)圖的構(gòu)造是該算法的關(guān)鍵環(huán)節(jié)，由于實(shí)體鏈接的最終決策是依據(jù)圖的拓?fù)浣Y(jié)構(gòu)得出的，因此圖的質(zhì)量對(duì)于實(shí)體鏈接算法的性能具有關(guān)鍵性影響．本節(jié)從圖的頂點(diǎn)集構(gòu)造方法、邊的構(gòu)造方法以及利用外部知識(shí)完善圖的結(jié)構(gòu)等3個(gè)層面，完整介紹實(shí)體相關(guān)圖的構(gòu)造方法．

2．2．1 構(gòu)造頂點(diǎn)集合

本文所使用的實(shí)體相關(guān)圖為有向圖，圖中的頂點(diǎn)為從文本中識(shí)別得到的實(shí)體指稱(chēng)項(xiàng)及相關(guān)的候選實(shí)體集合（以后綴區(qū)分）．在得到初步的候選實(shí)體集合N′之后，首先需要對(duì)其進(jìn)行篩選，以確保在頂點(diǎn)集合中，從文本中識(shí)別得到的待鏈接實(shí)體指稱(chēng)項(xiàng)與其候選實(shí)體對(duì)象之間盡可能具有明確的語(yǔ)義相關(guān)性．當(dāng)實(shí)體指稱(chēng)項(xiàng)在知識(shí)庫(kù)中只有一個(gè)候選實(shí)體且該候選實(shí)體不帶后綴標(biāo)簽時(shí)，則認(rèn)為該候選實(shí)體即是實(shí)體指稱(chēng)項(xiàng)所指的實(shí)體對(duì)象．為簡(jiǎn)化描述，以下將從待處理文本語(yǔ)料中抽取得到的待鏈接實(shí)體指稱(chēng)項(xiàng)簡(jiǎn)稱(chēng)為待定實(shí)體，將從本地知識(shí)庫(kù)中查詢(xún)得到的同名實(shí)體對(duì)象簡(jiǎn)稱(chēng)為候選實(shí)體．

①http：??keg．cs．tsinghua．edu．cn?project?ChineseKB

②https：??lucene．a(chǎn)pache．org

為確定待定實(shí)體和候選實(shí)體的相關(guān)性，首先需要設(shè)法確定一個(gè)待定實(shí)體的候選實(shí)體與該實(shí)體是否具有某種語(yǔ)義上的相關(guān)性，本文所采用的方法是計(jì)算待定實(shí)體所在的文本與其候選實(shí)體所對(duì)應(yīng)的互動(dòng)百科頁(yè)面的余弦相似度，作為判定其語(yǔ)義相關(guān)性的依據(jù)［23］．計(jì)算方法如下：首先采用NLPIR漢語(yǔ)分詞系統(tǒng)對(duì)輸入語(yǔ)料與候選實(shí)體的互動(dòng)百科頁(yè)面進(jìn)分詞和去除停用詞等預(yù)處理，選擇其中的名詞和命名實(shí)體作為特征，分別構(gòu)建特征向量．設(shè)待定實(shí)體mi所在文本的特征向量為Xi＝（x1，x2，…，xn），其候選實(shí)體對(duì)象nij對(duì)應(yīng)的互動(dòng)百科頁(yè)面的特征向量為Yj＝（y1，y2，…，yn），余弦相似度的計(jì)算公式如下：

其中，符號(hào)X·Y表示向量X和Y的內(nèi)積，‖X‖表示向量X的長(zhǎng)度．若候選實(shí)體沒(méi)有對(duì)應(yīng)的百科頁(yè)面，則假設(shè)其與實(shí)體指稱(chēng)項(xiàng)的余弦相似度為零．

在進(jìn)行頂點(diǎn)（實(shí)體）篩選時(shí)，若計(jì)算得到的余弦相似度小于預(yù)先設(shè)定的閾值λ，則認(rèn)為該候選實(shí)體與待鏈接實(shí)體在語(yǔ)義上不相關(guān)，從初始候選實(shí)體集合N′中刪除該候選實(shí)體節(jié)點(diǎn)．λ的取值采用交叉驗(yàn)證方法經(jīng)驗(yàn)地得到，本文的實(shí)驗(yàn)取λ＝0．2．

此外，研究表明，在百科語(yǔ)料中出現(xiàn)頻率在前40%的候選實(shí)體，可以覆蓋約90%的正確實(shí)體鏈接的目標(biāo)對(duì)象［15］．因此為提高算法執(zhí)行效率，本文根據(jù)候選實(shí)體所在互動(dòng)百科頁(yè)面的被瀏覽次數(shù)對(duì)實(shí)體進(jìn)行排序，選擇排在前40%的實(shí)體作為候選實(shí)體對(duì)象，由此可以進(jìn)一步縮小候選實(shí)體的選擇范圍．經(jīng)過(guò)上述2步篩選過(guò)程，得到最終的候選實(shí)體對(duì)象集合N．

實(shí)體相關(guān)圖的頂點(diǎn)集合V定義為：待鏈接實(shí)體指稱(chēng)項(xiàng)集合M和候選實(shí)體對(duì)象集合N的并集．2．2．2 構(gòu)造邊集合

實(shí)體相關(guān)圖的基本假設(shè)是位于同一文本中的實(shí)體之間通常存在語(yǔ)義上的相關(guān)性，利用這種位置上的語(yǔ)義相關(guān)性，能夠提高實(shí)體鏈接的準(zhǔn)確率［24］．

當(dāng)前流行的實(shí)體相關(guān)圖構(gòu)造方法是采用谷歌距離作為實(shí)體間的語(yǔ)義相關(guān)性測(cè)度，據(jù)此建立頂點(diǎn)之間的關(guān)聯(lián)關(guān)系［16，25－26］．然而，采用谷歌距離作為相關(guān)性測(cè)度的主要缺點(diǎn)是計(jì)算量較大，例如以維基百科作為實(shí)體知識(shí)來(lái)源的情況下，為了計(jì)算2個(gè)實(shí)體間的谷歌距離，需要分別統(tǒng)計(jì)這2個(gè)實(shí)體在所有百科頁(yè)面上單獨(dú)出現(xiàn)和共同出現(xiàn)的頻率，對(duì)于大規(guī)模語(yǔ)料而言，這樣的計(jì)算開(kāi)銷(xiāo)是不可接受的．因此，本文采用一種更為直觀和高效的方法來(lái)構(gòu)造邊集合．

基本思路是基于本地知識(shí)庫(kù)的實(shí)體關(guān)系拓?fù)浣Y(jié)構(gòu)來(lái)構(gòu)造邊的集合．具體實(shí)現(xiàn)方法是將實(shí)體間的關(guān)系劃分為直接關(guān)系和間接關(guān)系，分別進(jìn)行處理．

1）直接關(guān)系．是指2個(gè)實(shí)體在本地知識(shí)庫(kù)中存在關(guān)系邊．如果實(shí)體相關(guān)圖的頂點(diǎn)集合V中的2個(gè)實(shí)體頂點(diǎn)vi和vj在知識(shí)庫(kù)中存在直接關(guān)系，則在這2個(gè)頂點(diǎn)間添加一條有向邊，邊的方向與知識(shí)庫(kù)中2個(gè)實(shí)體間的關(guān)系方向保持一致．在當(dāng)前的基于圖的實(shí)體鏈接方法研究領(lǐng)域，主要采用這種方式來(lái)確定實(shí)體間的相關(guān)關(guān)系［14，19］．

然而研究表明，僅考慮知識(shí)庫(kù)中存在的直接關(guān)系是不夠的，因?yàn)橄鄬?duì)于復(fù)雜的實(shí)體關(guān)系而言，知識(shí)庫(kù)中已有的顯式知識(shí)通常是不足的，僅依賴(lài)這些直接關(guān)系進(jìn)行建模，得到的實(shí)體相關(guān)圖很可能無(wú)法正確反映實(shí)體關(guān)系網(wǎng)絡(luò)，從而導(dǎo)致錯(cuò)誤的實(shí)體鏈接結(jié)果［27］．為減輕該問(wèn)題的影響，本文提出一種間接關(guān)系定義，用于幫助完善實(shí)體相關(guān)圖的結(jié)構(gòu)．

2）間接關(guān)系．若2個(gè)實(shí)體在本地知識(shí)庫(kù)中均與一個(gè)以上的第三方實(shí)體存在直接關(guān)系，則稱(chēng)二者間存在間接關(guān)系．如果實(shí)體相關(guān)圖的頂點(diǎn)集合V中的2個(gè)候選實(shí)體頂點(diǎn)vi和vj在本地知識(shí)庫(kù)中存在間接關(guān)系，則在這2個(gè)頂點(diǎn)間添加一對(duì)有向邊．

綜上，對(duì)于給定的頂點(diǎn)集合V，所構(gòu)造的實(shí)體相關(guān)圖的鄰接矩陣的元素（有向邊）的取值如式（2）所示：

其中，eij＝1表示從頂點(diǎn)vi到vj存在一條有向邊?vi，vj?，eij＝0表示從頂點(diǎn)vi到vj不存在直接路徑．注意，當(dāng)i＝j(luò)時(shí)，eij＝0表示在實(shí)體相關(guān)圖中不存在自環(huán)．同時(shí)需要注意的是實(shí)體指稱(chēng)項(xiàng)與其對(duì)應(yīng)的所有候選實(shí)體間均存在一條有向邊，方向由前者指向后者，而同一實(shí)體指稱(chēng)項(xiàng)對(duì)應(yīng)的候選實(shí)體之間不存在路徑．式（2）表明，本文在考查實(shí)體間的語(yǔ)義相關(guān)性時(shí)優(yōu)先考慮實(shí)體間的直接關(guān)系，若實(shí)體間不存在直接關(guān)系，則進(jìn)一步考慮實(shí)體間的間接關(guān)系．

2．2．3 增量證據(jù)挖掘

當(dāng)前主流的實(shí)體鏈接方法大多基于本地知識(shí)庫(kù)中現(xiàn)有的結(jié)構(gòu)化知識(shí)，其中隱含的假設(shè)為知識(shí)庫(kù)中所包含的實(shí)體知識(shí)結(jié)構(gòu)是完整的，能為實(shí)體鏈接提供足夠的背景知識(shí)．然而事實(shí)上現(xiàn)有的知識(shí)庫(kù)技術(shù)并不滿足這一要求，其中的實(shí)體關(guān)系數(shù)據(jù)可能存在錯(cuò)誤、滯后和缺失等問(wèn)題，而且知識(shí)庫(kù)的主要知識(shí)來(lái)源（如百科類(lèi)網(wǎng)站等）也在不斷地動(dòng)態(tài)更新，因此不應(yīng)僅僅依靠本地知識(shí)庫(kù)作為實(shí)體鏈接的唯一知識(shí)來(lái)源［22］．

為充分利用第三方知識(shí)庫(kù)和百科類(lèi)網(wǎng)站知識(shí)更新迅速的優(yōu)點(diǎn)，本文提出一種增量證據(jù)挖掘方法，能夠有效地利用外部知識(shí)對(duì)實(shí)體相關(guān)圖進(jìn)行修正和完善，從而進(jìn)一步提高實(shí)體鏈接的準(zhǔn)確率．作為示例，本文采用互動(dòng)百科（http：??www．baike．com?）網(wǎng)站作為增量證據(jù)挖掘的外部知識(shí)來(lái)源，但在實(shí)際應(yīng)用中，該方法可以很方便地推廣到同時(shí)使用多個(gè)外部數(shù)據(jù)源的場(chǎng)景，且對(duì)外部知識(shí)源沒(méi)有特殊的要求．

增量證據(jù)挖掘方法簡(jiǎn)述如下．若實(shí)體相關(guān)圖的頂點(diǎn)集合V中的2個(gè)候選實(shí)體頂點(diǎn)vi和vj在當(dāng)前知識(shí)庫(kù)中并無(wú)直接或間接關(guān)系，則以這2個(gè)頂點(diǎn)對(duì)應(yīng)的實(shí)體對(duì)象為查詢(xún)條件，利用互動(dòng)百科網(wǎng)站提供的查詢(xún)接口查找其對(duì)應(yīng)的主頁(yè)，進(jìn)而通過(guò)模式匹配和規(guī)則過(guò)濾，確定這2個(gè)給定實(shí)體之間是否存在語(yǔ)義上的相關(guān)性．

若實(shí)體頂點(diǎn)vi的互動(dòng)百科頁(yè)面包含指向?qū)嶓w頂點(diǎn)vj的鏈接，則認(rèn)為頂點(diǎn)vi和vj具有語(yǔ)義上的直接相關(guān)性，相應(yīng)地在實(shí)體相關(guān)圖上增加一條從vi指向vj的有向邊．若實(shí)體頂點(diǎn)vi的互動(dòng)百科頁(yè)面不包含指向?qū)嶓w頂點(diǎn)vj的鏈接，則進(jìn)一步提取出vi和vj所在頁(yè)面的實(shí)體對(duì)象，并求出這2個(gè)實(shí)體對(duì)象集合的交集．對(duì)所得到的交集應(yīng)用預(yù)定義語(yǔ)法規(guī)則進(jìn)行過(guò)濾，去除其中的高頻詞（如地名和建筑物名）和代詞．若經(jīng)過(guò)濾后得到的實(shí)體交集U不為空，則認(rèn)為實(shí)體vi和vj之間存在間接語(yǔ)義關(guān)聯(lián)，相應(yīng)地在實(shí)體相關(guān)圖的頂點(diǎn)vi和vj之間增加一對(duì)有向邊；若U為空集，則采用式（1）計(jì)算實(shí)體vi和vj所在頁(yè)面的余弦相似度，若相似度大于50%，則認(rèn)為實(shí)體vi和vj之間存在間接語(yǔ)義關(guān)聯(lián)，相應(yīng)地在實(shí)體相關(guān)圖的頂點(diǎn)vi和vj之間增加一對(duì)有向邊．經(jīng)過(guò)增量證據(jù)挖掘過(guò)程，得到最終的實(shí)體相關(guān)圖，隨后算法轉(zhuǎn)入集成實(shí)體鏈接階段，基于實(shí)體相關(guān)圖對(duì)文本中提取得到的實(shí)體進(jìn)行批量實(shí)體鏈接．算法1給出了實(shí)體相關(guān)圖構(gòu)造過(guò)程的算法偽代碼框架．

算法1．實(shí)體相關(guān)圖構(gòu)造算法．

輸入：實(shí)體指稱(chēng)項(xiàng)及其候選實(shí)體構(gòu)成的頂點(diǎn)集合V＝M∪N；

輸出：實(shí)體相關(guān)圖G．

2．3 集成實(shí)體鏈接

集成實(shí)體鏈接算法的基本思想是針對(duì)一篇文本中出現(xiàn)的多個(gè)實(shí)體，利用其內(nèi)在的語(yǔ)義關(guān)系輔助消歧，實(shí)現(xiàn)批量實(shí)體鏈接．本文采用實(shí)體相關(guān)圖實(shí)現(xiàn)基于上下文語(yǔ)義關(guān)系的集成實(shí)體鏈接，具體思路是對(duì)于圖中的每個(gè)待定實(shí)體求出該實(shí)體與所有候選實(shí)體之間的語(yǔ)義一致性，從而將實(shí)體鏈接問(wèn)題轉(zhuǎn)化為候選實(shí)體的語(yǔ)義一致性排序問(wèn)題，從中選擇與待定實(shí)體語(yǔ)義一致性最高的候選實(shí)體作為最終的鏈接對(duì)象．方法流程簡(jiǎn)述如下：

1）對(duì)每篇待處理文本語(yǔ)料構(gòu)造實(shí)體相關(guān)圖，并求出圖中所有頂點(diǎn)的出入度．

2）利用2．2．1節(jié)計(jì)算得到的待定實(shí)體和候選實(shí)體之間的余弦相似度以及候選實(shí)體的出入度，按式（3）求得待定實(shí)體和候選實(shí)體之間的語(yǔ)義一致性：

其中，coherence（m，v）表示待定實(shí)體m和與其候選實(shí)體v之間的語(yǔ)義一致性；D（v）表示實(shí)體相關(guān)圖G中頂點(diǎn)v的度，由于G為有向圖，因此D（v）的取值為頂點(diǎn)v的出度與入度之和表示關(guān)于給定的待定實(shí)體mi，求其所有候選實(shí)體頂點(diǎn)的度之和．從式（3）可以看出，本文提出的語(yǔ)義一致性定義包含2部分內(nèi)容表示候選實(shí)體vi與當(dāng)前文本中的實(shí)體間的上下文關(guān)聯(lián)程度；sim（mi，vi）則表示候選實(shí)體vi所在的百科頁(yè)面與當(dāng)前文本的語(yǔ)義相似度．由于相似度的取值范圍均為［0，1］，因此加權(quán)之后函數(shù)coherence的取值范圍也是［0，1］．加權(quán)因子1?2表示對(duì)等加權(quán)，也可以考慮不對(duì)等加權(quán)的情況，但初步實(shí)驗(yàn)結(jié)果表明，少量的權(quán)值修正對(duì)實(shí)體鏈接結(jié)果的影響不大，因此本文采用1?2作為加權(quán)因子，對(duì)加權(quán)因子選擇和加權(quán)項(xiàng)的系統(tǒng)研究留作下一步工作．

3）在計(jì)算出待定實(shí)體和其所有候選實(shí)體間的語(yǔ)義一致性參數(shù)之后，對(duì)候選實(shí)體按語(yǔ)義一致性參數(shù)值從大到小進(jìn)行排序，選擇其中排名最高的候選實(shí)體對(duì)象作為待定實(shí)體的鏈接對(duì)象，形式化表示為：

其中，Link（mi，vk）表示將待定實(shí)體mi鏈接到本地知識(shí)庫(kù)中的候選實(shí)體vk之上，vk為等式右側(cè)的函數(shù)返回值．等式右側(cè)的內(nèi)容表示對(duì)于給定的待定實(shí)體mi，在其候選實(shí)體集合Ni中選出與待定實(shí)體的語(yǔ)義一致性最高的候選實(shí)體，作為實(shí)體指稱(chēng)項(xiàng)mi的鏈接目標(biāo)．

由于待定實(shí)體指稱(chēng)項(xiàng)所對(duì)應(yīng)的實(shí)體對(duì)象可能不在本地知識(shí)庫(kù)中，可能導(dǎo)致候選實(shí)體集合為空集（NIL）的情況出現(xiàn)［17，20］．對(duì)于待定實(shí)體m，采用如下規(guī)則判定其候選實(shí)體集合為空集：

1）若以待定實(shí)體m為查詢(xún)條件，在本地知識(shí)庫(kù)中查詢(xún)結(jié)果為空，則判定候選實(shí)體集合為空集．

2）若針對(duì)待定實(shí)體m的查詢(xún)結(jié)果非空，但所返回的候選實(shí)體與待定實(shí)體的余弦相似度均小于閾值λ，則判定其候選實(shí)體集合為空集．

3）若針對(duì)待定實(shí)體m的查詢(xún)結(jié)果非空，但所返回的候選實(shí)體在實(shí)體相關(guān)圖中均為孤立節(jié)點(diǎn)（僅與m相關(guān)聯(lián)），即該節(jié)點(diǎn)與圖中其他節(jié)點(diǎn)間不存在語(yǔ)義上的關(guān)聯(lián)關(guān)系，則判定其候選實(shí)體集合為空集．

2．4 基于圖的實(shí)體鏈接算法示例

接下來(lái)以一個(gè)例子完整演示GCCEL算法的實(shí)現(xiàn)細(xì)節(jié)．設(shè)給定語(yǔ)料為：“李娜的媽媽李艷萍是全國(guó)勞動(dòng)模范”．通過(guò)人工查詢(xún)，了解到其中的實(shí)體指稱(chēng)項(xiàng)李娜為我國(guó)著名的網(wǎng)球運(yùn)動(dòng)員，即知識(shí)庫(kù)中的“李娜（網(wǎng)球運(yùn)動(dòng)員）”是我們希望正確鏈接的實(shí)體對(duì)象．采用GCCEL算法，實(shí)體鏈接的實(shí)現(xiàn)過(guò)程如下．

首先通過(guò)實(shí)體抽取過(guò)程識(shí)別出待定實(shí)體指稱(chēng)項(xiàng)李娜和李艷萍，然后分別對(duì)其進(jìn)行知識(shí)庫(kù)查詢(xún)，得到李娜的候選實(shí)體集合為｛李娜（歌手）、李娜（網(wǎng)球運(yùn)動(dòng)員）、李娜（北京大學(xué)教授）｝；李艷萍的候選實(shí)體集合為｛李艷萍（山西媽媽?zhuān)⒗钇G萍（全國(guó)優(yōu)秀共青團(tuán)干部）｝．采用式（1）進(jìn)行相似度計(jì)算，得到每個(gè)候選實(shí)體所在的互動(dòng)百科頁(yè)面與給定語(yǔ)料的余弦相似度，計(jì)算結(jié)果如表1所示：

Table 1 Cosine Similarity Between the Undetermined Entitiy and the Candidate Entities表1 候選實(shí)體與待定實(shí)體的余弦相似度

由于候選實(shí)體李娜（北京大學(xué)教授）的互動(dòng)百科頁(yè)面與待消歧語(yǔ)料的余弦相似度小于預(yù)先設(shè)定的閾值λ＝0．2，所以從候選實(shí)體集合中刪除該實(shí)體．以保留下來(lái)的實(shí)體集合（包括待定實(shí)體和候選實(shí)體）為頂點(diǎn)集，采用2．2節(jié)介紹的邊集合構(gòu)造方法和增量證據(jù)挖掘方法構(gòu)造實(shí)體相關(guān)圖，如圖2所示．其中黑色頂點(diǎn)表示待定實(shí)體，白色頂點(diǎn)表示候選實(shí)體．

根據(jù)圖2，可以計(jì)算出圖中所有候選實(shí)體的出入度，然后依據(jù)式（3）求得待定實(shí)體和候選實(shí)體之間的語(yǔ)義一致性，結(jié)果如表2所示：

Table 2 Semantical Coherence between the Undetermined Entitiy and the Candidate Entities表2 待定實(shí)體和候選實(shí)體之間的語(yǔ)義一致性

Fig．2 Referent graph of the example corpus．圖2 示例文本語(yǔ)料的實(shí)體相關(guān)圖

最后，按照2．3節(jié)介紹的實(shí)體鏈接算法，根據(jù)語(yǔ)義一致性對(duì)候選實(shí)體進(jìn)行排序，選擇一致性最高的候選實(shí)體作為待定實(shí)體的鏈接對(duì)象．在本例中，將待定實(shí)體李娜鏈接到知識(shí)庫(kù)中的李娜（網(wǎng)球運(yùn)動(dòng)員），將待定實(shí)體李艷萍鏈接到知識(shí)庫(kù)中的李艷萍（全國(guó)優(yōu)秀共青團(tuán)干部）．至此，對(duì)于給定文本語(yǔ)料，批量地完成了將給定文本中的（歧義）實(shí)體指稱(chēng)項(xiàng)正確鏈接到知識(shí)庫(kù)中的對(duì)應(yīng)實(shí)體對(duì)象上的實(shí)體鏈接任務(wù)．

3 實(shí)驗(yàn)結(jié)果與討論

3．1 實(shí)驗(yàn)數(shù)據(jù)

為驗(yàn)證所提出的集成實(shí)體鏈接算法的有效性，本文采用3組可公開(kāi)獲得的語(yǔ)料進(jìn)行測(cè)試．

第1組語(yǔ)料是哈爾濱工業(yè)大學(xué)智能技術(shù)與自然語(yǔ)言處理研究室公開(kāi)發(fā)布的搜狗人名消歧語(yǔ)料①．該語(yǔ)料根據(jù)國(guó)內(nèi)常用的人名，選取其中相關(guān)新聞報(bào)道最多的12個(gè)人名，對(duì)11 876篇文檔進(jìn)行了人工標(biāo)注．本文從中隨機(jī)抽取120篇文檔進(jìn)行測(cè)試，在預(yù)處理階段去除了文檔中的標(biāo)注信息，僅保留純文本．經(jīng)人工統(tǒng)計(jì)，120篇測(cè)試文檔中共包含1 170個(gè)命名實(shí)體，其中在知識(shí)庫(kù)中存在對(duì)應(yīng)實(shí)體對(duì)象的實(shí)體973個(gè)（InKB類(lèi)型），NIL類(lèi)型實(shí)體的個(gè)數(shù)為197個(gè)．

為驗(yàn)證GCCEL算法對(duì)短文本的實(shí)體鏈接效果，本文進(jìn)一步采用2組公開(kāi)數(shù)據(jù)進(jìn)行了算法性能測(cè)試．其中，第2組語(yǔ)料是從新浪娛樂(lè)新聞網(wǎng)和鳳凰娛樂(lè)新聞網(wǎng)上隨機(jī)地采集得到的180條短新聞文本（平均字符長(zhǎng)度為107字）．隨機(jī)選取其中的30條作為訓(xùn)練樣本，剩余的150條作為測(cè)試樣本．經(jīng)統(tǒng)計(jì)，該訓(xùn)練樣本和測(cè)試樣本所包含的實(shí)體總數(shù)分別為125個(gè)和723個(gè)，其中InKB類(lèi)型實(shí)體個(gè)數(shù)分別為99個(gè)和650個(gè)，NIL類(lèi)型實(shí)體的個(gè)數(shù)分別為26個(gè)和73個(gè)．

第3組語(yǔ)料是NLP＆CC國(guó)際會(huì)議2013年公開(kāi)發(fā)布的微博實(shí)體鏈接評(píng)測(cè)語(yǔ)料②．該數(shù)據(jù)集包含779篇微博文檔，每篇微博文檔的長(zhǎng)度不超過(guò)150字．經(jīng)人工統(tǒng)計(jì)，779篇微博中共包含實(shí)體總數(shù)1 232個(gè)，其中InKB類(lèi)型實(shí)體個(gè)數(shù)為843個(gè)，NIL類(lèi)型實(shí)體個(gè)數(shù)為389個(gè)．

需要說(shuō)明的是，為了模擬開(kāi)放域環(huán)境下的實(shí)體鏈接任務(wù)場(chǎng)景（即訓(xùn)練樣本對(duì)真實(shí)數(shù)據(jù)的覆蓋率很低），本文僅采用30條短新聞文本作為訓(xùn)練樣本用于模型參數(shù)學(xué)習(xí)，因此在3組測(cè)試數(shù)據(jù)集上所使用的模型是完全相同的．實(shí)驗(yàn)數(shù)據(jù)的統(tǒng)計(jì)情況如表3所示．

3．2 實(shí)驗(yàn)方法

為了驗(yàn)證GCCEL算法的有效性，本文從近年的相關(guān)工作中分別選擇了2類(lèi)具有代表性和較高學(xué)術(shù)影響力的方法作為實(shí)驗(yàn)比較的對(duì)象，分別介紹如下．

Table 3 Statistics of the Corpus表3 訓(xùn)練樣本與測(cè)試語(yǔ)料一覽

WTCosSim算法是基于實(shí)體上下文相似度計(jì)算的經(jīng)典實(shí)體鏈接算法［12］．該算法基于維基百科上的實(shí)體知識(shí)進(jìn)行實(shí)體消歧，方法是利用文本中的命名實(shí)體和上下文關(guān)鍵詞構(gòu)造特征向量，并對(duì)查詢(xún)維基百科得到的若干候選實(shí)體所在頁(yè)面進(jìn)行向量化處理，據(jù)此計(jì)算從文本中抽取得到的實(shí)體指稱(chēng)項(xiàng)的上下文與候選實(shí)體的維基百科頁(yè)面上下文之間的余弦相似度，選擇相似度最高的候選實(shí)體作為目標(biāo)鏈接對(duì)象．

Babelfy③是一個(gè)基于圖的實(shí)體鏈接軟件［21］．該軟件基于開(kāi)源的百科字典BabelNet④構(gòu)建，因此支持多語(yǔ)種（包括英語(yǔ)、漢語(yǔ)、俄語(yǔ)等）實(shí)體消歧任務(wù)．其實(shí)體鏈接過(guò)程包含3個(gè)步驟：實(shí)體識(shí)別、候選實(shí)體選擇和實(shí)體消歧．基本思想是利用實(shí)體（節(jié)點(diǎn)）在BabelNet語(yǔ)義網(wǎng)絡(luò)中的三角形關(guān)系計(jì)算每個(gè)實(shí)體節(jié)點(diǎn)的結(jié)構(gòu)權(quán)值，據(jù)此構(gòu)造轉(zhuǎn)移矩陣，然后利用帶重啟的隨機(jī)游走算法得到實(shí)體間的語(yǔ)義相關(guān)性（稱(chēng)為語(yǔ)義簽名）．對(duì)于輸入的待處理文本，Babelfy首先基于語(yǔ)義簽名構(gòu)造其實(shí)體語(yǔ)義關(guān)系圖，然后通過(guò)抽取密集子圖對(duì)歧義實(shí)體進(jìn)行消歧．該方法在基準(zhǔn)數(shù)據(jù)集上的表現(xiàn)非常優(yōu)異，在KORE50和CoNLL數(shù)據(jù)集上的準(zhǔn)確率分別高達(dá)71．5%和82．1%．該方法的主要局限性在于性能完全依賴(lài)于BabelNet知識(shí)庫(kù)的知識(shí)規(guī)模．

除上述2類(lèi)經(jīng)典算法外，本文還選擇在NLP＆CC 2013實(shí)體鏈接競(jìng)賽中獲獎(jiǎng)的CASIA＿EL算法進(jìn)行比較．該算法也屬于基于實(shí)體上下文相似度計(jì)算的傳統(tǒng)實(shí)體鏈接算法［13］，與WTCoSim的區(qū)別在于，針對(duì)因?qū)嶓w上下文信息不足而導(dǎo)致的余弦相似度區(qū)分度不足的問(wèn)題，CASIA＿EL采用文本中實(shí)體指稱(chēng)項(xiàng)上下文詞的維基百科頁(yè)面作為外部知識(shí)源，對(duì)輸入文本的特征向量進(jìn)行了擴(kuò)展，然后再進(jìn)行實(shí)體

①http：??www．datatang．com?data?44022

②http：??www．datatang．com?data?44052

③http：??babelfy．org?index

④http：??babelnet．org相似度計(jì)算，由此提高了實(shí)體相似度的計(jì)算精度，但同時(shí)也導(dǎo)致了算法模型計(jì)算復(fù)雜度的大幅提高．

除與相關(guān)工作進(jìn)行比較外，本文還針對(duì)所提出的GCCEL算法設(shè)計(jì)了一個(gè)對(duì)比實(shí)驗(yàn)，用于演示和討論本文提出的增量證據(jù)挖掘方法對(duì)于系統(tǒng)性能的影響．為簡(jiǎn)化描述，將參與對(duì)比的算法稱(chēng)為Baseline模型，該模型與GCCEL算法模型幾乎完全一致，差別僅在于Baseline中不包含增量證據(jù)挖掘過(guò)程，在構(gòu)造候選實(shí)體關(guān)系圖時(shí)，完全依賴(lài)于知識(shí)庫(kù)現(xiàn)有的知識(shí)結(jié)構(gòu)．

3．3 評(píng)估方法

為客觀評(píng)價(jià)實(shí)驗(yàn)結(jié)果，對(duì)每組實(shí)驗(yàn)數(shù)據(jù)，分別記錄所采用的實(shí)驗(yàn)方法在該數(shù)據(jù)集上的準(zhǔn)確率（Accuracy）、精確率（Precision）、召回率（Recall）、并計(jì)算出相應(yīng)的F1值［16，20］．

實(shí)驗(yàn)結(jié)果的取得方法如下．首先，對(duì)2組測(cè)試數(shù)據(jù)集中的歧義實(shí)體進(jìn)行人工消歧，即人工地將其鏈接到本地知識(shí)庫(kù)中正確的實(shí)體對(duì)象上，對(duì)于不在知識(shí)庫(kù)中的實(shí)體，將其標(biāo)記為NIL．由此得到評(píng)估實(shí)驗(yàn)結(jié)果所需的基本事實(shí)集合T，即該語(yǔ)料中出現(xiàn)的實(shí)體指稱(chēng)項(xiàng)集合．以T1表示測(cè)試語(yǔ)料中由人工將其正確鏈接到本地知識(shí)庫(kù)中對(duì)應(yīng)實(shí)體對(duì)象上的實(shí)體指稱(chēng)項(xiàng)集合，T2表示測(cè)試語(yǔ)料中相應(yīng)實(shí)體對(duì)象不在本地知識(shí)庫(kù)中的實(shí)體指稱(chēng)項(xiàng)集合（即標(biāo)記為NIL的實(shí)體指稱(chēng)項(xiàng)集合），則有：T＝T1∪T2．

然后，對(duì)本文提出的GCCEL算法進(jìn)行測(cè)試，記錄算法GCCEL輸出的實(shí)體鏈接結(jié)果集合，以符號(hào)S表示．以S1表示輸出結(jié)果中鏈接到本地知識(shí)庫(kù)中實(shí)體對(duì)象上的實(shí)體指稱(chēng)項(xiàng)集合，S2表示輸出結(jié)果中的實(shí)體對(duì)象不在本地知識(shí)庫(kù)中的實(shí)體指稱(chēng)項(xiàng)集合，則有：S＝S1∪S2．需要說(shuō)明的是，S中包含的實(shí)體指稱(chēng)項(xiàng)個(gè)數(shù)與T相同，二者的區(qū)別在于：T中的實(shí)體鏈接結(jié)果是經(jīng)人工驗(yàn)證過(guò)的，可以視為基本事實(shí)；S中可能包含錯(cuò)誤的實(shí)體鏈接結(jié)果，即S1中可能包含T2中的實(shí)體指稱(chēng)項(xiàng)，S2中可能包含T1中的實(shí)體指稱(chēng)項(xiàng)，這2種情況均與基本事實(shí)T產(chǎn)生沖突．

通過(guò)將GCCEL算法的輸出結(jié)果S與基本事實(shí)T進(jìn)行對(duì)比，可以根據(jù)式（5）計(jì)算得到算法GCCEL在該數(shù)據(jù)集上的實(shí)體鏈接準(zhǔn)確率：

其中，｜T｜表示集合T中的元素個(gè)數(shù)，｜S1∩T1｜表示算法輸出結(jié)果中正確鏈接到本地知識(shí)庫(kù)中對(duì)應(yīng)的實(shí)體對(duì)象上的實(shí)體指稱(chēng)項(xiàng)個(gè)數(shù)，｜S2∩T2｜則表示被算法正確判定為NIL的實(shí)體指稱(chēng)項(xiàng)個(gè)數(shù)．從式（5）可以看出，準(zhǔn)確率指標(biāo)綜合考慮了算法對(duì)于在本地庫(kù)中和不在本地庫(kù)中的實(shí)體指稱(chēng)項(xiàng)的鏈接效果，是對(duì)實(shí)體鏈接算法綜合性能的評(píng)價(jià)指標(biāo)．

通過(guò)統(tǒng)計(jì)對(duì)應(yīng)的實(shí)體對(duì)象在本地知識(shí)庫(kù)中的實(shí)體指稱(chēng)項(xiàng)集合S1和算法輸出的鏈接到本地知識(shí)庫(kù)中實(shí)體對(duì)象上的實(shí)體指稱(chēng)項(xiàng)集合T1的數(shù)目，可以根據(jù)式（6）與式（7）進(jìn)一步計(jì)算得到算法GCCEL在該數(shù)據(jù)集上的精確率和召回率：

從式（8）可以看出，F(xiàn)1值受算法精確度和召回率的共同影響，當(dāng)二者均趨近于1時(shí)，F(xiàn)1值也趨近于最大值1．顯然，F(xiàn)1值越大，說(shuō)明算法對(duì)于本地知識(shí)庫(kù)中已有實(shí)體的消歧性能越好．由于實(shí)體鏈接任務(wù)的目標(biāo)本身是針對(duì)本地知識(shí)庫(kù)進(jìn)行實(shí)體消歧與匹配，因此F1指標(biāo)是衡量實(shí)體鏈接算法性能的最關(guān)鍵指標(biāo)［20］．準(zhǔn)確率指標(biāo)則可以被視為重要的參考指標(biāo)，按照慣例，對(duì)于實(shí)體鏈接結(jié)果中不在當(dāng)前知識(shí)庫(kù)中的實(shí)體指稱(chēng)項(xiàng)集合，通常在實(shí)體鏈接操作結(jié)束后，會(huì)對(duì)S2∩T2集合中的實(shí)體進(jìn)行聚類(lèi)，然后將其加入到現(xiàn)有知識(shí)庫(kù)中．此后在執(zhí)行新的實(shí)體鏈接操作時(shí)，這部分（當(dāng)前的S2∩T2集合中的）實(shí)體將成為本地知識(shí)庫(kù)中的成員（即可能出現(xiàn)在新的T1集合中），因此在評(píng)估算法性能時(shí)不能忽略準(zhǔn)確率的影響．

3．4 實(shí)驗(yàn)結(jié)果與討論

如3．1節(jié)所述，為模擬開(kāi)放域環(huán)境下的實(shí)體鏈接

精確率的含義是：GCCEL算法正確鏈接到知識(shí)庫(kù)的實(shí)體數(shù)量，占GCCEL算法輸出的實(shí)體鏈接總數(shù)的百分比．該指標(biāo)反映的是GCCEL算法的精確性，精確率越高，表明算法對(duì)于已經(jīng)存在于本地庫(kù)中的實(shí)體執(zhí)行消歧操作時(shí)正確結(jié)果的比率越高．召回率的含義是：GCCEL算法正確鏈接到知識(shí)庫(kù)的實(shí)體數(shù)量，占測(cè)試集中能夠準(zhǔn)確鏈接到知識(shí)庫(kù)中的實(shí)體總數(shù)的百分比．該指標(biāo)反映的是GCCEL算法的查全率，召回率越高，表明算法輸出結(jié)果中對(duì)于本地庫(kù)中已有實(shí)體而言，遺漏正確結(jié)果的可能性越低．

精確率和召回率是一對(duì)具有內(nèi)在矛盾的指標(biāo)，通常情況下，精確率的提高意味著召回率的降低，在實(shí)際應(yīng)用中人們通常會(huì)在這2個(gè)指標(biāo)間進(jìn)行折衷，根據(jù)F1值來(lái)客觀地評(píng)估算法的實(shí)際性能，公式如下：任務(wù)場(chǎng)景，即訓(xùn)練樣本對(duì)真實(shí)數(shù)據(jù)的覆蓋率很低的情況，本文僅采用30條短新聞文本作為訓(xùn)練樣本用于模型參數(shù)學(xué)習(xí)．GCCEL算法的關(guān)鍵參數(shù)是實(shí)體上下文相似性的判定閾值λ，通過(guò)在訓(xùn)練語(yǔ)料上進(jìn)行參數(shù)調(diào)整，得到GCCEL的性能指標(biāo)F1值與λ的關(guān)系如圖3所示．從圖3可以看出，當(dāng)λ＝0．2時(shí)，GCCEL算法的F1值達(dá)到最優(yōu)；而當(dāng)λ取值過(guò)小或過(guò)大時(shí)，算法的性能均會(huì)受到影響．這是因?yàn)棣巳≈颠^(guò)小會(huì)造成較多似是而非的噪音數(shù)據(jù)被判定為候選實(shí)體，導(dǎo)致算法準(zhǔn)確率降低；而當(dāng)λ取值過(guò)大時(shí)，會(huì)造成對(duì)候選實(shí)體的篩選結(jié)果過(guò)于嚴(yán)格，導(dǎo)致算法召回率下降．

Fig．3 F1－values under differentλon training corpus．圖3 F1值與參數(shù)λ在訓(xùn)練集上的關(guān)系

通過(guò)上述實(shí)驗(yàn)，采用λ＝0．2作為實(shí)體相似性判定閾值，得到GCCEL在3組測(cè)試語(yǔ)料上的實(shí)驗(yàn)結(jié)果，分別如表4～6所示．其中，表4和表5給出的是GCCEL算法與2類(lèi)代表性算法和Baseline模型的實(shí)驗(yàn)結(jié)果對(duì)比情況，表6則給出了GCCEL算法與NLP＆CC 2013競(jìng)賽優(yōu)勝算法CASIA＿EL的比較結(jié)果．

由實(shí)驗(yàn)結(jié)果可知，本文提出的GCCEL算法在短新聞?wù)Z料、搜狗人名消歧語(yǔ)料和NLP＆CC微博評(píng)測(cè)語(yǔ)料上的F1值分別為8 8．0 8%，8 7．9 1%和88．53%，準(zhǔn)確率分別為86．92%，87．50%和88．47%，均優(yōu)于近期的相關(guān)工作．

Table 4 Experimental Results on Short News Corpus表4 在短新聞數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果%

Table 5 Experimental Results on Sogou NED Corpus表5 在搜狗人名消歧語(yǔ)料上的實(shí)驗(yàn)結(jié)果%

Table 6 Experimental Results on NLP＆CC 2013Corpus表6 在NLP＆CC 2013評(píng)測(cè)語(yǔ)料上的實(shí)驗(yàn)結(jié)果%

與基于上下文相似度的代表性算法WTCosSim相比，GCCEL算法在3組語(yǔ)料上的F1值分別提高了10．39%，21．94%和10．34%，準(zhǔn)確率分別提高了10．73%，17．78%和9．81%．在NLP＆CC微博評(píng)測(cè)語(yǔ)料上，與相關(guān)工作中表現(xiàn)最好的CASIA＿EL相比，GCCEL算法的精度提高了3．52%，召回率提高了3．38%，F(xiàn)1值提高了3．45%，準(zhǔn)確率與之相當(dāng)．該實(shí)驗(yàn)結(jié)果表明，GCCEL算法的性能表現(xiàn)一致且顯著地優(yōu)于經(jīng)典的上下文相似度算法，但經(jīng)過(guò)改良后的上下文相似度算法（如CASIA＿EL）可以在性能上接近基于圖模型的集成鏈接算法．然而，考慮到算法模型訓(xùn)練所需的數(shù)據(jù)集規(guī)模，GCCEL算法對(duì)訓(xùn)練集樣本規(guī)模和樣本代表性的依賴(lài)性相對(duì)較低，因而與其他2種算法相比，算法推廣性更好，這也從另外一個(gè)側(cè)面顯示出集成實(shí)體鏈接方法的性能優(yōu)越性．

與集成鏈接方法的代表性工作Babelfy相比，GCCEL算法在3組語(yǔ)料上的F1值分別提高了26．28%，36．63%和16．59%，準(zhǔn)確率分別提高了20．02%，32．44%和25．63%．分析其主要原因在于Babelfy算法的性能主要依賴(lài)于BabelNet知識(shí)庫(kù)的知識(shí)含量，對(duì)于當(dāng)前不在知識(shí)庫(kù)中的實(shí)體指稱(chēng)項(xiàng)，該算法僅為其分配一個(gè)抽象實(shí)體（與實(shí)體指稱(chēng)項(xiàng)同名，但沒(méi)有具體信息）作為鏈接對(duì)象，導(dǎo)致實(shí)體鏈接的精度降低．此外，Babelfy算法沒(méi)有考慮到實(shí)體間的間接關(guān)系，也沒(méi)有提供增量證據(jù)挖掘機(jī)制，因此與GCCEL算法相比，其算法性能進(jìn)一步惡化．該實(shí)驗(yàn)結(jié)果表明，本文提出的增量證據(jù)挖掘方法和語(yǔ)義關(guān)聯(lián)分析方法有助于顯著提高集成實(shí)體鏈接算法的整體性能，從而更有效地發(fā)揮集成鏈接的優(yōu)勢(shì)．該結(jié)果同時(shí)也為本文提出的增量證據(jù)挖掘方法的有效性提供了實(shí)驗(yàn)證據(jù)．

為進(jìn)一步評(píng)估本文提出的增量證據(jù)挖掘方法的有效性，我們對(duì)從GCCEL算法中去除了增量挖掘機(jī)制的Baseline算法結(jié)果進(jìn)行觀察．與Baseline相比，GCCEL算法在短新聞?wù)Z料和搜狗人名消歧語(yǔ)料上的F1值分別提高了95．39%和121．83%，準(zhǔn)確率分別提高了75．49%和85．62%．該實(shí)驗(yàn)結(jié)果表明，通過(guò)外部證據(jù)挖掘過(guò)程，能在一定程度上彌補(bǔ)因本地知識(shí)庫(kù)實(shí)體知識(shí)不足對(duì)實(shí)體鏈接算法性能所造成的負(fù)面影響，從而顯著提高實(shí)體消歧的準(zhǔn)確率．由于知識(shí)庫(kù)的知識(shí)容量不足是目前制約知識(shí)庫(kù)應(yīng)用的核心關(guān)鍵問(wèn)題（這也是TAC設(shè)定實(shí)體鏈接任務(wù)的主要原因之一），因此本文提出的增量證據(jù)挖掘方法和相關(guān)實(shí)驗(yàn)證據(jù)對(duì)于幫助解決在知識(shí)庫(kù)知識(shí)容量有限前提下的實(shí)體鏈接問(wèn)題有一定的積極意義和參考價(jià)值．

最后，通過(guò)對(duì)GCCEL算法輸出結(jié)果中的錯(cuò)誤部分進(jìn)行人工比對(duì)和分析，歸納出導(dǎo)致GCCEL算法出錯(cuò)的主要原因如下：

第1類(lèi)錯(cuò)誤是由于實(shí)體識(shí)別錯(cuò)誤所導(dǎo)致的實(shí)體鏈接錯(cuò)誤．例如，對(duì)于“110跨欄運(yùn)動(dòng)員劉翔若選擇退役……”這句話，由于本文所采用的分詞方法將句中的實(shí)體指稱(chēng)項(xiàng)“劉翔”錯(cuò)誤地識(shí)別為“劉翔若”，導(dǎo)致本地知識(shí)庫(kù)查詢(xún)時(shí)返回結(jié)果NIL，未能將其正確鏈接到本地知識(shí)庫(kù)中．

第2類(lèi)錯(cuò)誤是由于本地知識(shí)庫(kù)的實(shí)體知識(shí)不足而導(dǎo)致的實(shí)體鏈接錯(cuò)誤．例如，對(duì)于短新聞?wù)Z料中的“李娜是北京奧運(yùn)會(huì)跳水冠軍得主”，其中的實(shí)體對(duì)象李娜（跳水運(yùn)動(dòng)員）不在本地知識(shí)庫(kù)中，但由于職業(yè)背景的相似性，GCCEL錯(cuò)誤地將其關(guān)聯(lián)到知識(shí)庫(kù)中已有的李娜（網(wǎng)球運(yùn)動(dòng)員）這一實(shí)體指稱(chēng)項(xiàng)上．

第3類(lèi)錯(cuò)誤是由于本文所使用的增量證據(jù)挖掘算法本身不夠完善而導(dǎo)致的實(shí)體鏈接錯(cuò)誤．例如，對(duì)于短新聞?wù)Z料“在東方歌舞團(tuán)，王彤認(rèn)識(shí)了后來(lái)成為知名電視劇導(dǎo)演的劉江”．由于劉江和王彤這2個(gè)實(shí)體在本地庫(kù)中沒(méi)有語(yǔ)義上的關(guān)聯(lián)，所以GCCEL會(huì)調(diào)用增量證據(jù)挖掘過(guò)程，通過(guò)互動(dòng)百科查找二者關(guān)系．結(jié)果在導(dǎo)演劉江的主頁(yè)上發(fā)現(xiàn)了實(shí)體王彤的超鏈接，通過(guò)超鏈接訪問(wèn)該王彤的主頁(yè)，確認(rèn)其身份是攝影師，因而GCCEL將上述語(yǔ)句中提取到的實(shí)體指稱(chēng)項(xiàng)，鏈接到知識(shí)庫(kù)中的實(shí)體對(duì)象王彤（攝影師）名下．然而，這與短新聞?wù)Z料中的實(shí)體王彤身份不同．

通過(guò)對(duì)上述3類(lèi)錯(cuò)誤進(jìn)行總結(jié)，得出如下認(rèn)識(shí)：1）通過(guò)改進(jìn)實(shí)體識(shí)別算法，或采用擴(kuò)充單詞表的方式，可以減輕和消除第1類(lèi)錯(cuò)誤的影響；2）第2類(lèi)錯(cuò)誤是當(dāng)前實(shí)體鏈接研究面臨的主要問(wèn)題，主要受當(dāng)前知識(shí)庫(kù)的完善程度制約，隨著知識(shí)庫(kù)的完善，此類(lèi)問(wèn)題有望逐漸得到解決；3）第3類(lèi)錯(cuò)誤雖然發(fā)生的概率較低，但一旦發(fā)生卻很難及時(shí)察覺(jué)和糾正，是本文下一步工作的重點(diǎn)．

4 結(jié)束語(yǔ)

本文提出一種基于圖和增量證據(jù)挖掘的中文集成實(shí)體鏈接方法，該方法融合了上下文相似度、實(shí)體流行度、實(shí)體相關(guān)度等因素，并在該模型的基礎(chǔ)上搭建了原型系統(tǒng)GCCEL．對(duì)于任意給定的文本，GCCEL綜合考慮了知識(shí)庫(kù)中存在的實(shí)體間的結(jié)構(gòu)化關(guān)系（包括直接關(guān)系和間接關(guān)系）和從外部知識(shí)源獲取的增量證據(jù)，據(jù)此構(gòu)建實(shí)體相關(guān)圖，然后在實(shí)體相關(guān)圖的基礎(chǔ)上利用圖算法實(shí)現(xiàn)對(duì)文本中多個(gè)歧義實(shí)體的集成鏈接．在搜狗人名消歧語(yǔ)料、新聞?wù)Z料和NLP＆CC微博評(píng)測(cè)語(yǔ)料上分別取得了87．91%，88．08%和88．53%的F1值以及87．50%，86．92%和88．47%的準(zhǔn)確率，算法綜合性能顯著優(yōu)于本領(lǐng)域的代表性工作．

論文的主要貢獻(xiàn)包括如下2個(gè)方面：1）通過(guò)實(shí)驗(yàn)證明了基于圖的集成實(shí)體鏈接方法在性能上一致地優(yōu)于當(dāng)前主流的基于上下文相似度的集成實(shí)體鏈接方法；2）實(shí)驗(yàn)表明本文提出的增量證據(jù)挖掘方法能夠有效地彌補(bǔ)本地知識(shí)庫(kù)的知識(shí)結(jié)構(gòu)不完善的問(wèn)題，顯著提高基于圖的集成實(shí)體鏈接方法的整體性能．本文提出的GCCEL算法具有良好的擴(kuò)展性和適應(yīng)性，上述成果為進(jìn)一步開(kāi)展大規(guī)模知識(shí)庫(kù)擴(kuò)容工作提供了有益的思路和方法借鑒．

在后續(xù)工作中，我們將主要從如下2方面著手對(duì)GCCEL算法進(jìn)行改進(jìn)．首先，改進(jìn)現(xiàn)有的增量證據(jù)挖掘算法，通過(guò)增加深度語(yǔ)義分析機(jī)制和實(shí)體識(shí)別過(guò)濾機(jī)制，提高實(shí)體識(shí)別的準(zhǔn)確性．其次，積極探索外部知識(shí)來(lái)源的融合方法，不斷豐富完善本地知識(shí)庫(kù)的規(guī)模和知識(shí)結(jié)構(gòu)，研究并利用不同類(lèi)型的外部知識(shí)，以進(jìn)一步提高實(shí)體鏈接操作的準(zhǔn)確率和召回率．

［1］Huai Baoxing，Bao Teng Fei，Zhu Hengshu，et al．Topic modeling approach to named entity linking［J］．Journal of Software，2014，9（14）：2076 2087（in Chinese）（懷寶興，寶騰飛，祝恒書(shū)．一種基于概率主題模型的命名實(shí)體鏈接方法［J］．軟件學(xué)報(bào)，2014，9（14）：2076 2087）

［2］Ling Xiao，Weld D S．Fine－grained entity recognition［C］?? Proc of the 26th Conf on Association for the Advancement of Artificial Intelligence（AAAI 12）．Menlo Park，CA：AAAI Press，2012：94 100

［3］Wu Fei，Weld D S．Open information extraction using Wikipedia［C］??Proc of the 48th Annual Meeting of the Association for Computational Linguistics（ACL 10）．Stroudsburg，PA：ACL，2010：118 127

［4］Wu Fei，Weld D S．Autonomously semantifying Wikipedia［C］??Proc of the 16th ACM Conf on Information and Knowledge Management（CIKM 07）．New York：ACM，2007：41 50

［5］Heng Ji，Ralph G．Knowledge base population：Successful approaches and challenges［C］??Proc of the 49th Annual Meeting of the Association for Computational Linguistics：Human Language Technologies（ACL 11）．Stroudsburg，PA：ACL，2011：1148 1158

［6］Mark D，Paul M，Rao D，et．a(chǎn)l．Entity disambiguation for knowledge base population［C］??Proc of the 23rd Int Conf on Computational Linguistic（COLING 10）．Stroudsburg，PA：ACL，2010：277 285

［7］Shen Wei，Wang Jianyong，Han Jiawei．Entity Linking with a knowledge base：Issues，techniques，and solutions［J］．IEEE Trans on Knowledge and Data Engineering，2015，27（2）：443 460

［8］Li Xuansong，Stephanie S，Heng Ji，et al．Linguistic resources for entity linking evaluation：From monolingual to cross－lingual［C］??Proc of the 8th Int Conf on Language Resources and Evaluation（LREC 12）．New York：European Language Resources Association，2012：3098 3105

［9］Bunescu R，Pasca M．Using encyclopedic knowledge for named entity disambiguation［C］??Proc of the 11th Conf of the European Chapter of the Association for Computational Linguistics（EACL 06）．Stroudsburg，PA：ACL，2006：9 16

［10］Silviu C．Large－scale named entity disambiguation based on Wikipedia data［C］??Proc of 2007Joint Conf on Empirical Methods in Natural Language Processing and Computational Natural Language Learning（EMNLP 07）．Stroudsburg，PA：ACL，2007：708 716

［11］Yang Zhizhuo，Huang Heyan．WSD method based on heterogeneous relation graph［J］．Journal of Computer Research and Development，2013，50（2）：437 444（in Chinese）（楊陟卓，黃河燕．基于異構(gòu)關(guān)系網(wǎng)絡(luò)圖的詞義消歧研究［J］．計(jì)算機(jī)研究與發(fā)展，2013，50（2）：437 444）

［12］Nguyen H T，Cao T H．Exploring Wikipedia and text features for named entity disambiguation［C］??Proc of the 2nd Int Conf Intelligent Information and Database Systems．Berlin：Springer，2010：24 26

［13］Zeng Yi，Wang Dongsheng，Zhang Tielin，et al．Linking entities in short texts based on a Chinese semantic knowledge base［C］??Proc of the 2nd CCF Conf on Natural Language Processing and Chinese Computing．Berlin：Springer，2013：266 276

［14］Zhang Tao，Liu Kang，Zhao Jun．A graph－based similarity measure between Wikipedia concepts and its application in entity linking system［J］．Journal of Chinese Information Processing，2015，29（2）：58 67（in Chinese）（張濤，劉康，趙軍．一種基于圖模型的維基概念相似度計(jì)算方法及其實(shí)體鏈接系統(tǒng)中的應(yīng)用［J］．中文信息學(xué)報(bào)，2015，29（2）：58 67）

［15］Zuo Zhe，Gjergji K，Toni G，et al．BEL：Bagging for entity linking［C］??Proc of the 25th Int Conf on Computational Linguistics：Technical Papers（COLING 14）．Stroudsburg，PA：ACL，2014：2075 2086

［16］Han Xianpei，Sun Le，Zhao Jun．Collective entity linking in Web text：A graph－based method［C］??Proc of the 34th Int ACM Conf on Research and Development in Information Retrieval（SIGIR 11）．New York：ACM，2011：765 774

［17］Shen Wei，Wang Jianyong，Luo Ping，et al．Linking named entities with knowledge base via semantic knowledge［C］?? Proc of the 21st Annual Conf on World Wide Web（WWW 12）．New York：ACM，2012：449 458

［18］Johannes H，Mohamed A Y，Bordino I，et al．Robust disambiguation of named entities in text［C］??Proc of the Conf on Empirical Methods in Natural Language Processing（EMNLP 11）．Stroudsburg，PA：ACL，2011：782 792

［19］Ayman A，Robert G．Graph ranking for collective named entity disambiguation［C］??Proc of the 52nd Annual Meeting of the Association for Computational Linguistics（ACL 14）．Stroudsburg，PA：ACL，2014：75 80

［20］Guo Zhaochen，Barbosa D．Robust entity linking via random walks［C］??Proc of the 23rd ACM Int Conf on Information and Knowledge Management（CIKM 14）．New York：ACM，2014：499 508

［21］Andrea M，Alessandro R，Roberto N．Entity linking meets word sense disambiguation：A unified approach［C］??Proc of the 2014Transactions of the Association for Computational Linguistics（ACL 14）．Stroudsburg，PA：ACL，2014：231 244

［22］Li Yang，Wang Chi，Han Fangqiu，et al．Mining evidences for named entity disambiguation［C］??Proc of the 19th ACM Int Conf on Knowledge Discovery and Data Mining（SIGKDD 13）．New York：ACM，2013：1070 1078

［23］Zhang Wei，Su Jian，Wang Wenting，et al．Entity linking leveraging automatically generated annotation［C］??Proc of the 23rd Int Conf on Computational Linguistic（COLING 10）．Stroudsburg，PA：ACL，2010：1290 1298

［24］Gentile A L，Zhang Ziqi，Xia Lei，et al．Semantics relatedness approach for named entity disambiguation［C］?? Proc of the 6th Italian Research Conf on Digital Libraries．Berlin：Springer，2010：137 148

［25］Milne D，Witten H I．Learning to link with Wikipedia［C］?? Proc of the 17th ACM Conf on Information and Knowledge Management（CIKM 08）．New York：ACM，2008：509 518

［26］Johannes H，Stephan S，Nguyen D B，et．a(chǎn)l．KORE：Keyphrase overlap relatedness for entity disambiguation［C］??Proc of the 21st ACM Int Conf on Information and Knowledge Management（CIKM 12）．New York：ACM，2012：545 554

［27］Eneko A，Ander B，Aitor S．Studying the Wikipedia hyperlink graph for relatedness and disambiguation［DB?OL］．Ithaca：ArXiv，［2015－05－12］．http：??arxiv．org? pdf?1503．01655v2．pdf

Liu Qiao，born in 1974．PhD and Associate professor．Member of China Computer Federation．His research interests include machine learning and data mining，natural language processing，and social network analysis．

Zhong Yun，born in 1990．Mater．His research interests include entity linking techniques，natural language processing and machine learning（zhongyunuestc＠gmail．com）．

Li Yang，born in 1990．Master．Student member of China Computer Federation．His research interests include knowledge graph，machine learning and natural language processing（kedashqs＠163．com）．

Liu Yao，born in 1978．PhD and lecturer．Member of China Computer Federation．Her research interests include social network analysis，machine learning，data mining，and network measurement（liuyao＠uestc．edu．cn）．

Qin Zhiguang，born in 1956．PhD and professor．Senior member of China Computer Federation．His research interests include information security，social network analysis，and mobile computing（qinzg＠uestc．edu．cn）．

Graph－Based Collective Chinese Entity Linking Algorithm

Liu Qiao，Zhong Yun，Li Yang，Liu Yao，and Qin Zhiguang
（School of Information and Software Engineering，University of Electronic Science and Technology of China，Chengdu 610054）

Entity Linking technology is a central concern of the knowledge base population research area．Traditional entity linking methods are usually limited by the immaturity of the local knowledge base，and deliberately ignore the semantic correlation between the mentions that co－occurr within a text corpus．In this work，we propose a novel graph－based collective entity linking algorithm for Chinese information processing，which not only can take full advantage of the structured relationship of the entities offered by the local knowledge base，but also can make use of the additional background information offered by external knowledge sources．Through an incremental evidence minning process，the algorithm achieves the goal of linking the mentions that are extraced from the text corpus，with their corresponding entities located in the local knowledge base in a batch manner．Experimental results on some open domain corpus demonstrate the validity of the proposed referent graph construction method，the incremental evidence minning process，and the coherence criterion between the mention－entity pairs．Experimental evidences show that the proposed entity linking algorithm consistently outperforms other state－of－the－art algorithms．

collective entity linking；knowledge base population；knowledge graph；referent graph；Chinese information processing

TP391

2015－09－24；

2015－11－16

國(guó)家自然科學(xué)基金項(xiàng)目（61133016，61272527，61202445）；教育部－中國(guó)移動(dòng)科研基金項(xiàng)目（MCM20121041）；中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金（ZYGX2014J066）

This work was supported by the National Natural Science Foundation of China（61133016，61272527，61202445），Chinese Ministry of Education－ChinaMoblie Communications Corporation Research Funds（MCM20121041），and the Fundamental Research Funds for the Central Universities（ZYGX2014J066）．