基于聚類的人名消歧研究綜述

展金梅 陳君濤

摘? 要：人名消歧問題屬于文本聚類范圍，但有其自身的特殊性，即參與聚類的文本集采用向量空間模型表示以后具有較高的維度，導(dǎo)致數(shù)據(jù)在聚類過程中效率低下、計算內(nèi)存開銷過高。為了深入分析人名消歧研究中聚類算法的整體應(yīng)用情況，從中國知網(wǎng)期刊數(shù)據(jù)庫收集2006-2018年10月相關(guān)文獻(xiàn)進(jìn)行了統(tǒng)計和分析，介紹了利用聚類算法進(jìn)行人名消歧研究的一般流程，闡述了聚類算法在人名消歧研究的應(yīng)用、聚類評價指標(biāo)和聚類結(jié)果評價，詳細(xì)介紹相關(guān)研究成果及代表文獻(xiàn)，為研究人員提供參考和借鑒。

關(guān)鍵詞：聚類;人名消歧;研究綜述

中圖分類號：TP391.1? ? ? 文獻(xiàn)標(biāo)識碼：A 文章編號：2096-4706（2019）10-0088-04

Abstract：Name disambiguation belongs to the scope of text clustering，but it has its own particularity：the set of text clustering represented by vector space model has a higher dimension，which leads to inefficiency and high computational memory in clustering process. In order to deeply analyze the overall application of clustering algorithm in the research of name disambiguation，the paper collected the related literature from the database of CNKI from October 2006 to October 2018 to statistics and analyze. Also，introduces the general process of using clustering algorithm in the researching name disambiguation，expounds the application of clustering evaluation in researching name disambiguation，clustering evaluation and evaluation of clustering result. Finally，the paper introduces in detail research results and representative literature，which provides reference for researchers of name disambiguation.

Keywords：clustering;name disambiguation;research summary

0? 引? 言

隨著計算機(jī)技術(shù)的發(fā)展，互聯(lián)網(wǎng)技術(shù)的普及，向搜索工具提交人名信息查詢進(jìn)行信息檢索已經(jīng)成為人們獲取人物信息的主要方法。由于人名歧義問題十分普遍，以致于用戶很難在結(jié)果數(shù)據(jù)中準(zhǔn)確有效地定位、獲取和管理所需的人物信息。此外，由于中文文本的復(fù)雜性，中文人名消歧被認(rèn)為比英文人名消歧更加困難，中文人名消歧逐漸成為國內(nèi)研究學(xué)者關(guān)注的問題。在命名實(shí)體中，人名具有很強(qiáng)的歧義性，無論在文本還是在網(wǎng)頁中，都會出現(xiàn)不同的人物擁有同一個姓名的現(xiàn)象，人名消歧是語義社會網(wǎng)絡(luò)系統(tǒng)中較難處理的問題之一。

人名消歧問題屬于文本聚類范圍，但有著其自身的特殊性，即參與聚類的文本集采用向量空間模型表示以后具有較高的維度，導(dǎo)致數(shù)據(jù)在聚類過程中效率低下，計算內(nèi)存開銷過高。自1998年Bagga，Baldwin將人名消歧作為實(shí)體共指中的一部分進(jìn)行了探討之后，研究學(xué)者開始關(guān)注和研究人名消歧的問題。開始分析K-means、DBSCAN等算法的運(yùn)行特點(diǎn)，改進(jìn)和優(yōu)化原算法運(yùn)行速度過慢和系統(tǒng)內(nèi)存開銷過大的缺點(diǎn)，在人名消歧方面取得了較好的研究成果。本文旨在綜述聚類算法在人名消歧研究中的應(yīng)用現(xiàn)狀，對相關(guān)研究文獻(xiàn)進(jìn)行可視化的分析，為研究人員提供參考和借鑒。

1? 文獻(xiàn)發(fā)表情況分析

為了了解聚類算法在人名消歧研究領(lǐng)域中的應(yīng)用現(xiàn)狀，本文在中國知網(wǎng)期刊數(shù)據(jù)庫中進(jìn)行主題檢索，時間限制為2006至2018年10月。為了較好地顯示檢索結(jié)果，文章從中國知網(wǎng)上截取了可視化的文獻(xiàn)發(fā)表年限趨勢圖。同時，對檢索結(jié)果進(jìn)行了簡單統(tǒng)計。

在中國知網(wǎng)期刊數(shù)據(jù)庫以“人名消歧”為主題詞進(jìn)行檢索，共檢索到論文104篇，以“人名消歧”和“聚類”為主題進(jìn)行檢索，檢索結(jié)果為65篇。2006-2018年10月每年論文發(fā)表量如圖1所示。首先從檢索結(jié)果可知，從2008年開始國內(nèi)研究學(xué)者初步涉及人名消歧的研究領(lǐng)域，至2010年每年的發(fā)文量有所增加。中國中文信息學(xué)會從2010開始每2年召開一次學(xué)術(shù)會議，這對學(xué)者研究熱情和論文發(fā)表量有著一定的影響。

其次，通在中國知網(wǎng)上進(jìn)行主題詞搜索后所列舉的相關(guān)的主題詞可以反映出相關(guān)研究的關(guān)鍵詞和學(xué)者關(guān)注的熱點(diǎn)詞匯。

2? 利用聚類算法進(jìn)行人名消歧研究的一般流程

章順瑞等[1]在對多文檔中文人名消歧工作中利用層次聚類算法進(jìn)行了研究。他們通過特征權(quán)重的計算，并使用TF/IDF的計算方法來構(gòu)建識別人名的規(guī)則，并對中文人名消歧的流程進(jìn)行了描述，具體操作步驟如下：

第一步：對原始語料進(jìn)行預(yù)處理，包括中文分詞、詞性標(biāo)注、人名識別和語料歸類等。

第二步：對處理后的語料進(jìn)行特征抽取或聚類處理。CB6E18A6-CA0D-42C0-9C0F-28C54F624F8F

第三步：采用向量空間模型表示所選取的特征，并利用層次聚類算法對特征向量所表示的文本進(jìn)行聚類。

第四步：對聚類結(jié)果進(jìn)行評測，評估消歧質(zhì)量。

根據(jù)上述描述，人名消歧過程示意圖如圖2所示。

2.1? 數(shù)據(jù)來源

人名消歧的早期研究主要是針對新聞類型的文本信息以及學(xué)術(shù)論文的自動處理（如引文分析）中人名歧義問題進(jìn)行的。隨著互聯(lián)網(wǎng)的快速發(fā)展，人名消歧的研究熱點(diǎn)逐漸轉(zhuǎn)向網(wǎng)絡(luò)搜索中的人名歧義問題。2007年，WePS評測研討會與語義評測研討會（SemEval07）聯(lián)合開展了一項(xiàng)針對網(wǎng)絡(luò)人名消歧的評測任務(wù)，WePS評測研討會還分別在2009年和2010年開展了兩屆關(guān)于網(wǎng)絡(luò)人名消歧的評測。

相比于英文，中文人名消歧研究工作開展較晚。2010年，CIPS-SIGHAN聯(lián)合學(xué)術(shù)會議CLP2010首次開展了中文跨文本人名消歧任務(wù)評測。2012年，CLP2012在CLP2010人名消歧的基礎(chǔ)上，增加了把人名消歧的結(jié)果映射到現(xiàn)實(shí)中具體人物實(shí)體的任務(wù)。CLP2012提供的人名消歧評測語料中包含知識庫（KnowledgeBase，KB）、未標(biāo)記文本集。2014年，CLP2014發(fā)布四個評測任務(wù)，分別是：中文分詞、中文拼寫檢查、簡體中文句法分析、中文人物屬性抽取。每項(xiàng)評測任務(wù)都發(fā)布了相對應(yīng)的語料庫及評價指標(biāo)。2016年，CLP2016則在CLP2014的基礎(chǔ)上發(fā)布了中文篇章分析、傳聞跟蹤、虛詞用法自動識別、多層次中文深度句義分析評測。從此次發(fā)布的任務(wù)可以看出，CLP2016豐富了中文消歧研究的深度，表現(xiàn)在從詞句擴(kuò)大到篇章，從句法分析細(xì)化到虛詞用法，從人物屬性提取延伸到傳聞跟蹤和深度句義分析。

2.2? 數(shù)據(jù)預(yù)處理

待研究數(shù)據(jù)收集后，原始數(shù)據(jù)不能直接用于聚類，需要對數(shù)據(jù)進(jìn)行預(yù)處理。數(shù)據(jù)預(yù)處理是指對數(shù)據(jù)進(jìn)行清洗并轉(zhuǎn)換成適合數(shù)據(jù)挖掘的形式的過程，主要包括數(shù)據(jù)清洗、數(shù)據(jù)轉(zhuǎn)換和豐富、數(shù)據(jù)整合以及數(shù)據(jù)歸約等任務(wù)[2]，在數(shù)據(jù)特征提取操作過程中，需要從研究數(shù)據(jù)中選取具有相同人名的不同命名實(shí)體（NE）或一般詞語的特征。命名實(shí)體特征如人名、地名、組織機(jī)構(gòu)。一般詞語如名詞、動詞等。

2.3? 人名聚類算法

將原始數(shù)據(jù)預(yù)處理結(jié)束后，使用聚類算法對其進(jìn)行分析，達(dá)到人名消歧的目的。當(dāng)前研究者進(jìn)行數(shù)據(jù)聚類的研究算法有：最長公共子序列、層次聚類、多步驟聚類、DBSCAN算法[3]、k-means算法[4]、聚類集成算法[5]等。

Wagner等[6]在1974年提出最長公共子序列（Longest Common Subsequence，LCS），即一個數(shù)列S，如果分別是兩個或多個已知數(shù)列的子序列，且是所有符合此條件序列中最長的，則S稱為已知序列的最長公共子序列。熊李艷等利用向量空間模型對所抽取的特征進(jìn)行向量表示，使得每篇包含人名的文檔都由一組特征向量所代表。向量空間模型利用所選取的特征將文檔形式化為N維空間向量，空間中的每一維都是選取的特征詞語。然后通過計算特征向量之間的相似度決定聚類對象[7]。任景華運(yùn)用中文自然語言處理和信息抽取系統(tǒng)識別命名實(shí)體和實(shí)體關(guān)系，生成實(shí)體信息對象（Entity Profile），采用實(shí)體信息對象（EP）中的個人信息特征，實(shí)體關(guān)系和上下文相關(guān)信息在Hadoop平臺上基于凝聚的層次聚類方法解決了實(shí)體消歧問題[8]。有的學(xué)者針對實(shí)體知識庫的具體情況，將知識庫實(shí)體與漢語命名實(shí)體經(jīng)過多步驟的層次聚類，從而獲得較好的聚類性能[9]。有的學(xué)者則針對知識庫中單條實(shí)體特征稀疏和相似度閾值人工設(shè)置不精確的情況，采用分步聚的手段，利用文本檢索的方法解決單條實(shí)體特征稀疏的問題，獲得初步聚類結(jié)果;再采用自適應(yīng)閾值層次聚類算法實(shí)現(xiàn)人名消歧[10]。通過對句義結(jié)構(gòu)分析，以不同人名實(shí)體具有不同的社會關(guān)系網(wǎng)，而人名實(shí)體間關(guān)系為實(shí)體在句中語義角色間依賴關(guān)系所表現(xiàn)出的基本思想，依據(jù)句子本身的語義結(jié)構(gòu)特點(diǎn)來提取人名實(shí)體之間在句中的以關(guān)系特征為依賴條件的關(guān)聯(lián)關(guān)系，結(jié)合相關(guān)人物的職業(yè)、機(jī)構(gòu)名和人物屬性特征對關(guān)系類型特征進(jìn)行聚類，由此實(shí)現(xiàn)人名消歧。

在基于密度的DBSCAN算法上，通過對DBSCAN算法初始參數(shù)選擇進(jìn)行優(yōu)化，把對算法中的EPs值的確定轉(zhuǎn)換為用戶對數(shù)據(jù)中噪音水平的估計，使參數(shù)的決定更具有客觀性，從而更容易通過數(shù)據(jù)集中實(shí)現(xiàn)人名消歧，解決了電子數(shù)據(jù)庫中文獻(xiàn)著者的人名消歧問題。通過改進(jìn)文本聚類算法k-means來關(guān)注網(wǎng)頁里的人名消歧的問題?；诮?jīng)典的k-means算法如果選擇了一個差的隨機(jī)初始聚類中心，算法會遇到局部收斂的問題，因此提出一種基于最大最小原則改進(jìn)的k-means算法來進(jìn)行人名消歧。根據(jù)不同聚類算法的優(yōu)缺點(diǎn)的不同，依據(jù)人名中的上下文特征、實(shí)體特征和社會關(guān)系特征，利用不同的聚類算法對三個特征構(gòu)成的相似度短陣進(jìn)行劃分，利用均方誤差鄰接矩陣聚類對其進(jìn)行集成，達(dá)到人名消歧，由此，提出聚類集成的人名消歧算法。

2.4? 聚類評價指標(biāo)

因?qū)嶒?yàn)數(shù)據(jù)的來源不同，研究人員選用的評測工具也不一樣。目前，用于人名消歧評價工具主要有P-IP指標(biāo)、B-Cubed指標(biāo)和SemEvalWePS提供的評測工具。下面將分別列舉評測試工具的算法。

式（4）～（6）中，Pre為精確率，Rec為召回率，S為標(biāo)準(zhǔn)聚類結(jié)果集合，d表示文檔，Si∈S表示標(biāo)準(zhǔn)結(jié)果類別集合中的一個類，R為實(shí)際聚類結(jié)果集合，Ri∈R表示實(shí)際結(jié)果類別集合中的其中一類，|Si|和|Ri|分別為集體的Si和Ri大小。

SemEvalWePS提供的評測方法：

其中，，Ci表示要評估的結(jié)果，Lj表示為標(biāo)注的正確結(jié)果，F(xiàn)則表示為準(zhǔn)確率和召回率的調(diào)和系數(shù)。

上述三種評測方法分別均計算了聚類結(jié)果的準(zhǔn)確率、召回率和F值。

2.5? 聚類集成結(jié)果評價方法CB6E18A6-CA0D-42C0-9C0F-28C54F624F8F

目前，常用的評價聚類集成方法有：標(biāo)準(zhǔn)化互信息（NMI）;變化的信息（VI）;Adjusted Rand Index（ARI）。

（1）標(biāo)準(zhǔn)化互信息（NMI）。Strehl和Ghosh[3]提出了標(biāo)準(zhǔn)化互信息（Normalized Mutual Information，NMI），用來衡量多個候選聚類結(jié)果之間的相似性。與λ（a）相對應(yīng)的熵可以表示為：

式（13）返回出來的是一個度量值，但是如果考慮到聚類過程中數(shù)據(jù)集的大小不一致且聚類的簇的數(shù)目不一致時，其原始的定義則不適用了。為此，Wu等人在VI的基礎(chǔ)上提出NVI（標(biāo)準(zhǔn)版的VI），可解決上述問題。其定義如下：

可以看出，NVI和NMI之間很相近，且這兩種方法的值都介于0和1之間，其中，0表示兩個聚類完全不一致，1表示兩個聚類達(dá)到最大的一致性。

（3）Adjusted Rand Index（ARI）。Hubert和Arabie提出ARI的定義如下：

3? 結(jié)? 論

人名消歧問題是本屬于命名實(shí)體消歧的一個分支，屬于文本聚類的范圍。本文通過中國知網(wǎng)發(fā)表的文獻(xiàn)數(shù)據(jù)分析了國內(nèi)學(xué)者對人名消歧研究的情況，列舉了人名消歧工作過程中應(yīng)用到的研究算法、人名消歧流程、研究數(shù)據(jù)來源、聚類評價指標(biāo)和聚類結(jié)果評價方法并對此進(jìn)行了闡述?？赏棺x者對人名消歧工作形成基本的初步認(rèn)識，由此將人名消歧工作應(yīng)用到更多的不同語種之中。

參考文獻(xiàn)：

[1] 章順瑞，游宏梁.基于層次聚類算法的中文人名消歧 [J].現(xiàn)代圖書情報技術(shù)，2010（11）：64-68.

[2] 熊李艷，趙毅，黃衛(wèi)春，等.基于句義結(jié)構(gòu)分析的中文人名消歧 [J].計算機(jī)應(yīng)用研究，2016，33（10）：2898-2901.

[3] 任景華.利用優(yōu)化的DBSCAN算法進(jìn)行文獻(xiàn)著者人名消歧 [J].圖書館理論與實(shí)踐，2014（12）：61-65.

[4] 楊欣欣，李培峰，朱巧明，等.一種基于改進(jìn)的K-means算法的人名消歧系統(tǒng)的設(shè)計與實(shí)現(xiàn) [J].計算機(jī)與數(shù)字工程，2010，38（8）：10-12+17.

[5] 陽怡林，周杰，李弼程.基于聚類集成的人名消歧算法 [J].計算機(jī)應(yīng)用研究，2016，33（9）：2716-2720.

[6] 林翠萍，吳揚(yáng)揚(yáng).采用改進(jìn)最長公共子序列的人名消歧 [J].華僑大學(xué)學(xué)報（自然科學(xué)版），2016，37（2）：201-206.

[7] 朱翔，史曉東，陳毅東.基于層次聚類的中文人名消歧方法研究 [J].心智與計算，2010，4（4）：236-241.

[8] 張菲菲，李宗海，周曉輝，等.基于層次聚類的跨文本中文人名消歧研究 [J].計算機(jī)工程與應(yīng)用，2014，50（6）：106-111.

[9] 李廣一，王厚峰.基于多步聚類的漢語命名實(shí)體識別和歧義消解 [J].中文信息學(xué)報，2013，27（5）：29-34+42.

[10] 陽怡林，周杰，李弼程，等.基于分步聚類的人名消歧算法 [J].數(shù)據(jù)采集與處理，2016，31（1）：213-222.

作者簡介：展金梅（1983-），女，漢族，甘肅靖遠(yuǎn)人，講師，碩士，研究方向：計算機(jī)應(yīng)用、自然算法研究。CB6E18A6-CA0D-42C0-9C0F-28C54F624F8F