林翠萍， 吳揚揚

(華僑大學 計算機科學與技術(shù)學院， 福建 廈門 361021)

?

采用改進最長公共子序列的人名消歧

林翠萍， 吳揚揚

(華僑大學 計算機科學與技術(shù)學院， 福建 廈門 361021)

摘要：將名詞、形容詞、動名詞和命名實體作為文本特征，考慮詞序與詞頻，結(jié)合特征項的語義，提出一種基于改進最長公共子序列的文本聚類(LCSC)方法.實驗結(jié)果表明：相對于傳統(tǒng)的余弦值聚類方法，LCSC方法在人名消歧的P-IP指標上，F(xiàn)平均值由74.2%提高到了84.9%；相對于最長公共子序列方法，總體性能也提高了3.7%.

關鍵詞：人名消歧； 文本相似度； 最長公共子序列； 層次聚類

據(jù)統(tǒng)計，在Google或Yahoo上搜索人名的量達到了30%[1]，作為互聯(lián)網(wǎng)檢索的一個子任務，人名搜索返回結(jié)果往往是相關重名人的網(wǎng)頁.目前人名消歧的主流方法是基于向量空間模型的聚類方法，該方法的研究主要集中在特征提取和表示.Bagga等[2]用向量空間模型解決跨文檔人名的共指消解問題.Mann等[3]自動提取了出生地、出生年月、職務等的人物傳記信息，構(gòu)成豐富的特征空間.Pedersen等[4]抓住文檔中的共現(xiàn)詞，以前詞為行、后詞為列的矩陣經(jīng)過奇異值分解后得到表示文檔的特征.Chen等[5]把特征系統(tǒng)地劃分為基于名詞和基于命名實體的特征，用SoftTFIDF計算特征權(quán)重，最后進行層次聚類.Ikeda等[6]在以人名實體、混合關鍵詞和網(wǎng)絡鏈接為特征的基礎上，提出兩階段聚類方法.在中文人名消歧方面，Yang等[7]把特征分為命名實體特征和普通詞特征，通過引入同義詞詞林和詞語相似度來降低數(shù)據(jù)的稀疏性.一方面，傳統(tǒng)的向量空間模型[8]把特征詞或短語組成一個集合;另一方面，特征空間的稀疏性將會限制文本相似度計算的精度.針對上述問題，本文提出了一種改進最長公共子序列的聚類方法(longest common subsequence clustering，LCSC).

1相關工作

1.1知網(wǎng)詞語相似度

知網(wǎng)是一個網(wǎng)狀知識庫，描述了概念與概念之間的關系[9].每一個詞匯可以有多個概念，每一個概念都用一系列的義原來描述.這些義原用樹狀結(jié)構(gòu)組織起來，義原根據(jù)義原之間的屬性關系分為多棵義原樹，這些存在一定關系的義原樹就形成了網(wǎng)狀知識結(jié)構(gòu).劉群等[10]提出了一種計算語義相似度的方法，該方法實際上是獲取兩個詞匯的最大概念相似度.特征項w1有m個概念：s1，1，s1，2，…，s1，m，特征項w2有n個概念：s2，1，s2，2，…，s2，n，則w1和w2的語義相似度為

(1)

文獻[10]對實詞概念語義的表達式分成了4個部分：第一獨立義原描述式，記為sim1(s1,s2)；其他獨立義原描述式，記為sim2(s1,s2)；關系義原描述式，記為sim3(s1,s2)，符號義原描述式，記為sim4(s1,s2).因此，兩個概念的語義表達式的整體相似度記為

(2)

式(2)中:βi(1≤i≤4)是可調(diào)節(jié)的參數(shù)，且滿足b1+b2+b3+b4=1，β1≥β2≥β3≥β4.

1.2最長公共子序列算法描述

最長公共子序列(longestcommonsubsequence,LCS)最初是Wagner等[11]在1974年提出來的，即一個數(shù)列S，如果分別是兩個或多個已知數(shù)列的子序列，且是所有符合此條件序列中最長的，則S稱為已知序列的最長公共子序列.

Hirschberg[12]用動態(tài)規(guī)劃有效地解決了此問題.假設有兩個字符串X，Y，其分別表示為X={a0,a1,…,am-1}和Y={b0,b1,…,bn-1}. 用一個二維矩陣Cm×n存儲迭代過程中當前的最長公共子序列長度. 其中：c[i][j]記錄a0到ai和b0到bj的最長公共子序列的長度，即原始問題的一個子問題的解.當i=0或j=0時，空序列是ai和bj的最長公共子序列，故c[i][j]=0.其他情況下，結(jié)合語義相似度可建立遞歸關系為

(3)

2LCSC方法

從計算機角度看，人名消歧是將多個重名人的文檔集合劃分為若干個子集合，即給定包含同一人名n的文檔集合D，背景知識K，求D的劃分 p={D1,D2,…，Dm},并使劃分中一個子集合對應一個人物ρi(1≤i≤m).人名消歧步驟，如圖1所示.

2.1文本預處理及特征表示

假設一個人物實體對應一篇文檔，先對每篇文檔進行分詞、詞性標注、命名實體識別,并去除不相關文檔.文中所采用的分詞器是孫健開發(fā)的Ansj(http://www.ansj.org/)，以人民日報1998年1月的語料庫為測試的結(jié)果準確率高達98%，召回率為96%，被廣泛運用于自然語言處理中的命名實體識別、多級詞性標注、關鍵詞提取等.

特征提取的目的是降維，并得到有區(qū)分度的特征詞.對于人名消歧而言，其作用可歸納為：找到能區(qū)分不同人物的重要詞，即對相似度計算重要的詞.在文本相似度計算上，以最長公共子序列為依據(jù)；在特征提取上，需要盡可能保留較全面的文本信息.因此，文中依次抽取文中出現(xiàn)的名詞(n)、形容詞(a)、動名詞(vn)和命名實體(nr，ns，nt)，按其在原文的順序組成一個有序的詞語序列表示文本，即d={w1,w2,…,wn}，其中，wi即為所抽取的特征項.

采用經(jīng)典的TFIDF(termfrequency,inversedocumentfrequency)方法來計算特征權(quán)重.其核心思想是：如果某個詞或短語在一篇文章中出現(xiàn)的頻率高，并且在其他文章中很少出現(xiàn)，則認為此詞或短語具有很好的類別區(qū)分能力[13].加權(quán)函數(shù)為詞頻乘以反文檔頻率，即

(4)

式(4)中:TF即為詞頻，指特征i在文檔k中出現(xiàn)的頻率；IDF為反文檔頻率；N為所有類別中的文檔的總數(shù)；nk為包含特征i的文檔數(shù).

利用詞語分類的重要程度為后續(xù)的文本相似度服務，并非要利用TFIDF進行特征的選擇.

2.2改進最長公共子序列的文本相似度

為了充分利用文本自身的詞序和詞頻信息，提出一種基于最長公共子序列的文本相似度計算方法.

2.2.1詞語相似度為了彌補向量空間模型中特征項相互獨立正交的缺陷，文中借助知網(wǎng)(Hownet)的詞匯描述方式，根據(jù)文獻[10]的語義相似度，建立特征項相似度矩陣.二維矩陣SL(A)，L(B)用于存儲特征項之間的相似度.特征項ai和bj若是完全匹配，它們的詞語相似度sim[i][j]將被置為1.0；否則，根據(jù)知網(wǎng)詞語相似度計算方法返回相應的值.

2.2.2結(jié)合語義知識的LCS算法文本去除停用詞以后，抽取其中的名詞、形容詞、動名詞和命名實體組成一個有序的特征詞語序列.當結(jié)合語序考慮文檔相似度時，與經(jīng)典的最長公共子序列的問題極為類似.設文檔A和文檔B的特征項序列分別表示為a1,a2,…,am和b1,b2,…,bn.用一個二維矩陣C(m+1)(n+1)存儲當前的最長公共特征子序列長度.其中：c[i][j]記錄a1到ai和b1到bj的最長公共特征子序列的長度.

考慮表達的多樣性，將原始的LCS算法結(jié)合詞語之間的語義信息，即添加特征項相似度，提出一種結(jié)合語義的LCS算法，即

(5)

式(5)中:sim[i-1][j-1]是A文檔特征序列中第i個特征項和B文檔序列中第j個特征項的相似度，若兩個特征項的相似度超過了一個閾值ε，認為它們是匹配的，最長公共特征子序列長度動態(tài)增加一個單位.

2.2.3基于LCS的文本相似度自Hirschberg[14]提出基于LCS的文本相似度方法之后，不少研究人員在此基礎上提出改進并優(yōu)化.比較常見到的計算方法有文獻[15]提到的LCS與較長的文本長度的比值，即

(6)

2倍的LCS[16]除以兩文本的長度之和，即

(7)

式(7)中:LCSL(A,B)為文檔和文檔的最長公共特征子序列長度；L(A)，L(B)分別為文檔A和文檔B的特征向量的長度.

對于兩篇描述同一人物的長文本和短文本來說，如果采用文獻[15]的方法計算文本相似度，將會得到較小的值.通過加入特征項的權(quán)重,提高文本相似度的精度.改進的文本相似度為

(8)

(9)

式(9)中:wi，k,wj，k分別是兩篇文檔的最長公共特征子序列中對應特征項的權(quán)重，包括了兩個特征序列中的完全匹配特征項和不完全匹配特征項；δ是一個平衡參數(shù).由于文檔特征向量普遍較長，而最長公共特征子序列的長度則較小，所以加入Tk進行適當調(diào)節(jié).只有當兩個對應特征的權(quán)重都超過δ時，Tk才增加1個單位.因此，該方法不僅考慮到了詞序與詞頻，而且在LCS算法中結(jié)合了特征項之間的語義相關度，最終達到提高具有相同含義但使用不同詞匯的文本相似度的目的.

2.3聚類算法

對于人名消歧，由于重名者個數(shù)的不確定性，采用層次聚類算法比較合適.文中采用自底向上的單鏈的層次聚類算法.

3評價指標

實驗選用CIPS-SIGHAN提供的兩種人名消歧評價方法：P-IP和B-Cubed指標.兩種方法分別計算了聚類結(jié)果的正確率，召回率和F值.P-IP指標為

(10)

(11)

(12)

B-cubed指標的公式為

(13)

(14)

(15)

式(13)～(15)中:S={S1,S2,…}是系統(tǒng)輸出的聚類結(jié)果;R={R1,R2,…}是人工標注的聚類結(jié)果.

通常情況下，為了驗證人名消歧系統(tǒng)的整體性能，取各個人名消歧效果的平均表現(xiàn)，即

(16)

(17)

(18)

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

為了檢驗文中提出方法的有效性，進行了對比實驗，將提出的LCSC方法與Baseline、LCS及文獻[17]中的AE方法進行對比.其中：Baseline是傳統(tǒng)的基于向量空間模型的聚類方法，以全文除停用詞外的所有詞為文本特征，采用TFIDF為特征權(quán)重計算公式，以特征向量的夾角余弦值作為文本相似度，再進行單鏈層次聚類.LCS方法中LCS和文本相似度分別采用式(3)，(7)計算.文獻[17]中的AE方法通過抽取人物屬性信息作為特征來進行人名消歧.

4.1數(shù)據(jù)集

采用的數(shù)據(jù)集是搜狗全網(wǎng)新聞人名消歧語料[17]，該語料選取了國內(nèi)最常用的50個人名，抽取含有這50個人名串的新聞報道.對其中新聞報道最多的12個人名的總共11 876篇文檔進行了人工標注.

4.2實驗結(jié)果分析

通過對搜狗全網(wǎng)人名消歧語料中12個人名進行實驗，結(jié)果表明：提出的基于改進的LCS的文本相似度的聚類算法在兩個評測指標上都表現(xiàn)出了良好的效果.P-IP的F值對比，如圖2所示.B-Cubed的F值對比，如圖3所示.

圖2　P-IP的F值對比 圖3　B-Cubed的F值對比　　Fig.2　Comparison of P-IP F-measure　　　　　　　　Fig.3　Comparison of B-Cubed F-measure

圖2，3結(jié)果表明:除“李娜”以外的其他人名，LCS方法和文中提出的LCSC方法的F值都比Baseline有所提高.

在進行LCSC方法的實驗過程中需要調(diào)節(jié)3個參數(shù)，分別是聚類停止閾值l，式(5)的詞語相似度閾值ε及式(9)計算文本相似度時的權(quán)重平衡參數(shù)δ.結(jié)合多個重名人的實驗結(jié)果，l在0.25左右取得總體較高的F值.在l保持一定的情況下，分別對ε和δ進行控制變量法獲取最優(yōu)值.

“張偉”的聚類閾值4在調(diào)整過程中對結(jié)果的影響，如圖4所示.由圖4可知：ε和δ的最優(yōu)值分別為0.9和0.01.12個人的平均F值的對比，如圖5所示.由圖5可知：P-IP的F值從Baseline的74.2%提高到84.9%；B-Cubed的F值從55.0%提高到75.7%.與LCS相比，LCSC方法也分別高出3.7%和3.5%；與AE方法相比，文中方法在P-IP指標上體現(xiàn)出一定的優(yōu)勢.可見，加入了特征項的權(quán)重信息對文本相似度計算起到了一定的作用，使得LCSC方法體現(xiàn)出了較好的性能，與人物屬性抽取方法比較也略勝一籌.

圖4　“張偉”的聚類閾值對結(jié)果的影響　　　　　　　　　　圖5　12個人的平均F值的對比　　Fig.4　 Effect of Zhang wei′s clusterin Fig.5　Comparison of average F-measure threshold to result for 12 persons

5結(jié)束語

通過引入知網(wǎng)的詞語相似度計算，彌補了向量空間中特征項之間相互獨立的缺陷.在最長公共子序列的計算中加入了權(quán)重的平衡參數(shù)，避免了傳統(tǒng)余弦相似度導致的特征稀疏性，從而提高了文本相似度計算的準確率.針對LCSC方法的不足，后續(xù)工作將從預處理和語義分析兩方面入手.此外，提取與LCSC方法結(jié)合的文本特征，也是需要進一步深入的問題.

參考文獻：

[1]ARTILES J,GONZALO J,VERDEJO F.A testbed for people searching strategies in the WWW[C]∥Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Piscataway：ACM，2005:569-570.

[2]BAGGA A,BALDWIN B.Entity-based cross-document coreferencing using the vector space model[C]∥Proceedings of the 17th International Conference on Computational Linguistics.Boston：Association for Computational Linguistics，1998:79-85.

[3]MANN G S,YAROWSKY D.Unsupervised personal name disambiguation[C]∥Proceedings of the 7th Conference on Natural Language Learning at HLT-NAACL.Edmonton：Association for Computational Linguistics，2003:33-40.

[4]PEDERSEN T,PURANDARE A,KULKARNI A.Name discrimination by clustering similar contexts[C]∥Computational Linguistics and Intelligent Text Processing.Berlin：Springer Berlin Heidelberg，2005:226-237.

[5]CHEN Y,MARTUB J.Towards robust unsupervised personal name disambiguation[C]∥EMNLP-CoNLL.Washington D C：IEEE Press,2007:190-198.

[6]IKEDA M,ONO S,SATO I,et al.Person name disambiguation on the web by two-stage clustering[C]∥2nd Web People Search Evaluation Workshop.New York：Association for Computing Machinery，2009：33-38.

[7]YANG Xia, JIN Peng, XIANG Wei.Exploring word similarity to improve Chinese personal name disambiguation[C]∥Web Intelligence and Intelligent Agent Technology.Washington D C：IEEE Press，2011:197-200.

[8]SALTON G,WONG A,YANG C S.A vector space model for automatic indexing[J].Communications of the ACM,1975,18(11):613-620.

[9]董振東,董強.知網(wǎng)簡介[EB/OL][2014-03-16].http://www.keenage.com.

[10]劉群,李素建.基于《知網(wǎng)》的詞匯語義相似度計算[J].中文計算語言學,2002,7(2):59-76.

[11]WAGNER R A,FISCHER M J.The string-to-string correction problem[J].Journal of the ACM (JACM),1974,21(1):168-173.

[12]HIRSCHBERG D S.A linear space algorithm for computing maximal common subsequences[J].Communications of the ACM,1975,18(6):341-343.

[13]施聰鶯,徐朝軍,楊曉江.TFIDF 算法研究綜述[J].計算機應用,2009,29(B6):167-170.

[14]HIRSCHDERG D S.Algorithms for the longest common subsequence problem[J].Journal of the ACMWeb Intelligence and Intelligent Agent Technology.Washington D C:IEEE Press，1977,24(4):664-675.

[15]全方磊.數(shù)據(jù)特征提取在高鐵車地傳輸中的應用研究[D].杭州：浙江大學,2013:39-40.

[16]牛永潔,張成.多種字符串相似度算法的比較研究[J].計算機與數(shù)字工程,2012,40(3):14-17.

[17]張鑫.人名消歧關鍵技術(shù)研究與實現(xiàn)[D].哈爾濱：哈爾濱工業(yè)大學,2012:32-33.

(責任編輯： 陳志賢 英文審校：吳逢鐵 )

Person Name Disambiguation Based on Revised Longest Common Subsequence

LIN Cuiping, WU Yangyang

(College of Computer Science and Technology, Huaqiao University, Xiamen 361021, China)

Abstract：This paper uses nouns, adjectives, gerunds and named entities as text features, and also considers the word order and word frequency when computing the text similarity. A text clustering method based on revised longest common subsequence (LCSC) is proposed. The experimental results show that the LCSC method can significantly improve the overall performance in person name disambiguation compared with traditional clustering method and make the average F-measure increase from 74.2% to 84.9%. The overall performance also improved by 3.7% when compared with the longest common subsequence method.

Keywords：person name disambiguation; text similarity; longest common subsequence； hierarc

中圖分類號：TP 391

文獻標志碼：A

基金項目：福建省科技計劃重大項目(2011H6016)； 福建省科技計劃重點項目(2011H0028)

通信作者：吳揚揚(1957-)，女，教授， 博士，主要從事數(shù)據(jù)庫技術(shù)和數(shù)據(jù)挖掘的研究.E-mail:wuyy@hqu.edu.cn.

收稿日期：2014-08-31

doi:10.11830/ISSN.1000-5013.2016.02.0201

文章編號：1000-5013(2016)02-0201-06