賀依依 黎鐵軍 蔣艷凰

（國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)沙 410073）

1 引言

近幾年來(lái)，鏈接開放數(shù)據(jù)的可用性越來(lái)越高，從而引申出了大規(guī)模知識(shí)圖譜［1］，如FreeBase［2］。在構(gòu)建知識(shí)圖譜的過(guò)程中，需要從不同結(jié)構(gòu)的數(shù)據(jù)中抽取特征節(jié)點(diǎn)（即實(shí)體，例如：人，組織，位置和其他類型等）以及定義節(jié)點(diǎn)間關(guān)系［3］。由于自然語(yǔ)言的表達(dá)存在多樣性、動(dòng)態(tài)性、非規(guī)范性等問(wèn)題，知識(shí)圖譜抽取的多個(gè)實(shí)體節(jié)點(diǎn)（實(shí)體名稱）可能存在多種表達(dá)方式，即表達(dá)歧義。因此需要對(duì)抽取出的實(shí)體進(jìn)行歧義的消解。

在進(jìn)行實(shí)體消歧過(guò)程中，研究的內(nèi)容主要分為兩類：同名消歧與多名聚合［4］。由于翻譯、縮寫、書寫方式等問(wèn)題，造成了對(duì)同一個(gè)實(shí)體單位有不同的表述方式。將這些不同的表述方式識(shí)別成同一個(gè)實(shí)體，即為多名聚合。目前多名聚合問(wèn)題的其中一種解決方法是利用上下文信息構(gòu)建特征向量結(jié)合相似度計(jì)算實(shí)體間距離。將一定閾值距離范圍內(nèi)的實(shí)體進(jìn)行聚合，從而達(dá)到消除歧義的目的［5］。但是對(duì)于大多數(shù)上下文信息匱乏的文本，在進(jìn)行多名聚合過(guò)程中，模型無(wú)法明確給定實(shí)體的特征信息或文本的標(biāo)簽描述。由于不存在明確的文本標(biāo)簽描述，無(wú)法通過(guò)目前常用的分類方式（如語(yǔ)義網(wǎng)絡(luò)［6］等）來(lái)完成對(duì)不同實(shí)體的分類。在這一條件下只能通過(guò)實(shí)體表述本身的文本信息進(jìn)行相似度的計(jì)算，獲取實(shí)體間距離來(lái)進(jìn)行無(wú)監(jiān)督聚類?；诮y(tǒng)計(jì)的計(jì)算和基于規(guī)則的計(jì)算等方式是目前主流的解決方式。通過(guò)將短文本轉(zhuǎn)化為計(jì)算機(jī)可識(shí)別的向量來(lái)進(jìn)行文本間的距離計(jì)算。

當(dāng)大規(guī)模數(shù)據(jù)是無(wú)標(biāo)簽時(shí)，一般是以聚類的方式，對(duì)同一實(shí)體的不同表述進(jìn)行聚合。在聚類的過(guò)程中，主要通過(guò)設(shè)定文本表述的相似度距離的閾值，將文本表述相似的聚成同一個(gè)簇。本文中，主要使用的聚類算法是密度聚類，通過(guò)使用密度聚類，將無(wú)標(biāo)簽短文本的實(shí)體進(jìn)行多名聚合，解決無(wú)實(shí)體標(biāo)簽時(shí)，無(wú)法確定實(shí)體的個(gè)數(shù)問(wèn)題。然而使用密度聚類時(shí)，由于使用的是固定的參數(shù)，會(huì)出現(xiàn)相近的類被合并成一個(gè)聚類。因此在此基礎(chǔ)之上，還可以進(jìn)行二次聚類。

本文中提出了二次聚類的方法。第一次密度聚類將大致相同的實(shí)體表述聚合在同一個(gè)簇。在第一次聚類的基礎(chǔ)上，使用地域約束和第二次聚類對(duì)第一次密度聚類產(chǎn)生的簇，進(jìn)行進(jìn)一步劃分，解決密度聚合過(guò)程中由于密度距離泛化導(dǎo)致的同一簇內(nèi)存在多個(gè)不同實(shí)體的問(wèn)題。

2 相關(guān)工作

實(shí)體消除歧義中多名聚合主要分為兩步，第一步是實(shí)體文本的相似度計(jì)算，第二步是基于文本的相似度對(duì)同一實(shí)體的不同表述進(jìn)行聚類。在本節(jié)中主要介紹文本的相似度計(jì)算和聚類方法。

主流的文本相似度計(jì)算分為三類：基于字符串的方法、基于統(tǒng)計(jì)的經(jīng)驗(yàn)主義方法與基于規(guī)則的理性主義方法。基于字符串的方法通過(guò)計(jì)算兩個(gè)字符串的字面差異來(lái)定義字符串之間的距離。Wang J 等［7］使用編輯距離的方法，通過(guò)計(jì)算一個(gè)字符串變成另一個(gè)字符串的最少編輯次數(shù)（如：增加、刪除和替換單一字符）來(lái)定義字符串間的距離，從而進(jìn)行相似度匹配。但是對(duì)于同一實(shí)體存在詞序上的表達(dá)差異時(shí)，由于距離變化較大，導(dǎo)致文本相似度降低。為了解決這個(gè)問(wèn)題，余婷婷［8］等使用Jaccord計(jì)算兩個(gè)文本間的相似度。Jaccord 通過(guò)計(jì)算文本中詞的交集和并集的比值，來(lái)計(jì)算兩個(gè)文本之間的相似度。但是基于字符串的方法沒(méi)有考慮到文本蘊(yùn)含的特征信息，現(xiàn)有的算法從統(tǒng)計(jì)和規(guī)則兩個(gè)方面進(jìn)行考慮。基于統(tǒng)計(jì)的經(jīng)驗(yàn)主義方法主要是利用統(tǒng)計(jì)方法，通過(guò)構(gòu)建文本向量，來(lái)計(jì)算文本間的相似度。Mikolov T［9］等提出了一系列基于語(yǔ)料庫(kù)的方法，為文本向量賦予各維度的特征信息。其中最常見的就是利用語(yǔ)料庫(kù)中的句子進(jìn)行詞向量的訓(xùn)練（如word2vec［10］，Golve［11］），通過(guò)詞向量來(lái)計(jì)算相似度。由于這種詞向量訓(xùn)練模式是基于句子進(jìn)行訓(xùn)練，而實(shí)體的表述方式一般是名詞性短句，在句法結(jié)構(gòu)上具有很大的相似性。在某種程度上，相同的句法結(jié)構(gòu)中的詞在向量空間中的表述會(huì)非常接近，從而造成即使是不同實(shí)體的表述，相似度也會(huì)非常高。另一種方式是使用TF-IDF（Term Frequency-Inverse Document Frequency，詞頻-逆向文件頻率）［12］，對(duì)詞進(jìn)行加權(quán)。例如，華秀麗［13］等利用TF-IDF 選擇特征項(xiàng)，來(lái)計(jì)算文本的語(yǔ)義相似度。對(duì)于基于規(guī)則的方法，一般是采用人工構(gòu)建的知識(shí)庫(kù)，定義知識(shí)庫(kù)中的規(guī)則來(lái)進(jìn)行文本相似度的計(jì)算。比如彭琦［14］等基于哈爾濱工業(yè)大學(xué)《同義詞詞林》擴(kuò)展版本，利用《同義詞詞林》作為詞語(yǔ)相似度來(lái)計(jì)算文本相似度。

現(xiàn)階段主流的多名聚合是基于分類的方式［6］，根據(jù)訓(xùn)練數(shù)據(jù)，訓(xùn)練指定模型的參數(shù)，然后使用該模型來(lái)完成分類的任務(wù)。例如DSSM、ConvNet、Tree-LSTM、Siamese LSTM［15～19］都是在對(duì)詞語(yǔ)或者句子建模的基礎(chǔ)上得到詞向量或者句向量，來(lái)計(jì)算文本相似度。但是當(dāng)數(shù)據(jù)集是龐大且無(wú)標(biāo)簽時(shí)，多采用聚類的方式。比如K 均值聚類算法（K-means clustering algorithm）［20］，通過(guò)挑選初始的中心點(diǎn)，通過(guò)算法迭代重置中心點(diǎn)，最后達(dá)到類里面的點(diǎn)都足夠近，類與類之間的點(diǎn)都足夠遠(yuǎn)。但是K均值聚類算法最大的缺陷就是需要確定中心點(diǎn)的個(gè)數(shù)。在無(wú)法確定簇的數(shù)目時(shí)，可以使用基于密度聚類算法（Density-Based Spatial Clustering of Application with Noise，DBSCAN）［21］，通過(guò)確定最小的簇的大小和點(diǎn)之間的距離，自動(dòng)生成各個(gè)簇。

3 方法

本文主要是對(duì)論文中作者的所屬單位進(jìn)行多名聚合。整個(gè)處理框架如圖1 所示，主要分為兩個(gè)部分，第一部分是數(shù)據(jù)預(yù)處理，第二部分是聚類。

1）數(shù)據(jù)預(yù)處理：對(duì)數(shù)據(jù)集進(jìn)行數(shù)據(jù)預(yù)處理，去掉特殊字符，同時(shí)對(duì)論文中作者的所屬信息，進(jìn)行實(shí)體詞識(shí)別，提取出單位，城市和國(guó)家的信息。對(duì)提取出的單位的信息還需要進(jìn)行進(jìn)一步的處理。

圖1 處理框架圖

2）聚類：對(duì)于抽取出來(lái)的單位名稱，根據(jù)單位名稱之間的相似度距離，使用DBSCAN［12］進(jìn)行數(shù)據(jù)集的劃分，形成各個(gè)簇。對(duì)于形成的各個(gè)簇，進(jìn)行二次聚類。首先使用地域約束對(duì)形成的各個(gè)簇，進(jìn)行劃分。對(duì)劃分生成的各個(gè)子數(shù)據(jù)集，使用DBSCAN進(jìn)行第二次聚類。

本文中主要的創(chuàng)新點(diǎn)在于聚類部分，下面主要介紹聚類部分。

3.1 DBSCAN

DBSCAN（Density-Based Spatial Clustering of Application with Noise）是基于密度的聚類算法，將密度相連的點(diǎn)的最大的集合定義為簇，能夠把足夠高密度的區(qū)域劃分為簇，并且能夠發(fā)現(xiàn)任意形狀的簇。通過(guò)密度聚類，能夠?qū)?shù)據(jù)集中的實(shí)體表述劃分為不同的簇。

DBSCAN［12］可以被定義為

式（1）中C 表示集群的子數(shù)據(jù)集集合，SD表示應(yīng)聚類的點(diǎn)P 的數(shù)據(jù)集，ε是SD中點(diǎn)P 的鄰域的最大半徑，MinPts 定義簇中的最小點(diǎn)數(shù)。其中ε在本文中為兩個(gè)單位文本表述之間的相似度距離，相似度距離范圍大小可調(diào)。ε和MinPts是影響DBSCAN聚類過(guò)程的兩個(gè)輸入?yún)?shù)。

通過(guò)使用DBSCAN，兩兩計(jì)算單位表述之間的相似度距離，可以初步把相似度距離小于ε的單位表述劃分到同一個(gè)簇中。

3.2 二次聚類

3.2.1 地域約束

在采用聚類算法進(jìn)行多名聚合時(shí)，由于文本附加信息的缺乏，只采用字符串間相似度可能會(huì)將存在部分描述一致的不同實(shí)體合成同一個(gè)簇?；诖耍诿芏染垲惿傻拇仡愔?，可能存在表述類似，但是屬于不同實(shí)體的情況。為了進(jìn)一步區(qū)分同一簇里的不同實(shí)體，本文旨在引入識(shí)別的單位實(shí)體所處的地域信息。地域信息可以作為簇中單位表述的附加約束信息，來(lái)進(jìn)一步區(qū)分簇中不同的實(shí)體。其中地域約束的信息來(lái)源于數(shù)據(jù)預(yù)處理中得到的單位與地域信息詞典。

如圖2 所示，在原始簇中存在多個(gè)表述相近的組織1，2，3 等。這類組織由于其表述相近難以用字符串相似度進(jìn)行區(qū)分，但是不同表述的組織實(shí)體所處的地域可能不同（如北京大學(xué)位于北京，南京大學(xué)位于南京，其中北京大學(xué)與南京大學(xué)的字符串差異僅有一個(gè)詞）。因此可以利用地域信息將存在同一城市的簇中不同單位實(shí)體進(jìn)行進(jìn)一步聚合，不同城市的實(shí)體進(jìn)行進(jìn)一步區(qū)分。如組織1與組織2同時(shí)都存在與城市A 因此它們?yōu)橥粚?shí)體的概率較大，將這兩個(gè)組織實(shí)體進(jìn)行進(jìn)一步合并，其算法實(shí)現(xiàn)如下：

算法1：基于地域約束的簇內(nèi)合并算法

輸入簇內(nèi)組織集合：Sorg

輸入簇內(nèi)組織對(duì)應(yīng)的城市集合：Scity

初始化子簇為C′為空

For i in Size（Sorg）do

isNew=TRUE

for j in Size（C′）do

if Size（city（i）∩city（j））＜size（city（i）∪city（j））do

將org（i）合并進(jìn)入Cj′

city（j）=city（j）∩city（i）

isNew=FALSE

end

if isNew do

為子簇C′創(chuàng)建新元素Cnew′

city（new）=city（j）

end

end

end

輸出子簇C′

在算法1 中，每個(gè)組織實(shí)體org（i）對(duì)應(yīng)一個(gè)所屬的城市集合city（i）（如分校區(qū)的存在可能導(dǎo)致某一大學(xué)在不同城市同時(shí)存在）。如果兩個(gè)組織的城市集合間交集與其并集一致，則代表兩者的城市集合交集為空。兩個(gè)組織不在同一城市出現(xiàn)過(guò)，因此將其分離。如果兩個(gè)組織的城市集合間交集與其并集不一致，則兩者的城市集合存在公有項(xiàng)，即Size（city（i）∩city（j））＜size（city（i）∪city（j））。若兩個(gè)組織在同一城市存在過(guò)，將其合并。通過(guò)對(duì)組織實(shí)體對(duì)應(yīng)的所屬城市集合的集合運(yùn)算能夠?qū)Υ貎?nèi)的不同實(shí)體進(jìn)行進(jìn)一步約束，將同一所屬地域的組織進(jìn)行進(jìn)一步聚合，將不同地域的組織進(jìn)行進(jìn)一步分離。

3.2.2 第二次DBSCAN

由于第一次的DBSCAN 聚類受限于實(shí)體間相似度距離ε。當(dāng)ε的值設(shè)置較小時(shí)，容易將同一實(shí)體的不同表述劃分為多個(gè)簇。這種情況下，消歧結(jié)果較差，難以將同一實(shí)體的不同表述進(jìn)行聚合。當(dāng)ε的值設(shè)置比較大時(shí)，由于實(shí)體間的相似度密度分配不均，容易將距離比較近的不同實(shí)體的簇聚合為同一個(gè)簇，增大消歧誤差。為了保證將同一實(shí)體不同表述進(jìn)行聚合，通常設(shè)計(jì)的相似度ε往往是比較大的，此時(shí)需要解決較大距離時(shí)不同實(shí)體聚合的消歧誤差增大的問(wèn)題。為了解決這個(gè)問(wèn)題，提出了第二次DBSCAN 聚類。通過(guò)設(shè)計(jì)DBSCAN 中的距離函數(shù)，對(duì)一次DBSCAN聚類產(chǎn)生的每一個(gè)簇進(jìn)行二次聚類，其距離函數(shù)設(shè)計(jì)如下：

其中i，j 表示兩個(gè)不同的文本表述，vec(i)表示的文本的向量化。由于二次聚類旨在關(guān)注同一簇內(nèi)兩個(gè)實(shí)體間的差異，因此對(duì)兩個(gè)實(shí)體的文本向量表述的非交集部分采用二范數(shù)（ 二范數(shù)：）求取歐式距離。通過(guò)將放大實(shí)體間的不同表述對(duì)實(shí)體表述的影響來(lái)提高兩個(gè)不同實(shí)體的表述差異，以達(dá)到將不同實(shí)體分離的結(jié)果，減小消歧誤差。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)和評(píng)估標(biāo)準(zhǔn)

現(xiàn)階段從120 萬(wàn)篇pubmed 論文的摘要中抽取出來(lái)了300 多萬(wàn)條作者所屬信息。這些信息進(jìn)行處理，抽取出作者所屬單位，單位所在城市，國(guó)家。對(duì)抽取出來(lái)的單位表述，取最大級(jí)別表述。比如一個(gè)作者所屬單位是301 醫(yī)院某個(gè)科室，我們只取出301 醫(yī)院作為這個(gè)作者所屬的單位。因此，本文中實(shí)體消除歧義的工作，就是對(duì)這些單位實(shí)體進(jìn)行消歧。將300 多萬(wàn)條信息經(jīng)過(guò)數(shù)據(jù)預(yù)處理去重后，得到10 萬(wàn)條不同的單位表述，對(duì)其進(jìn)行聚類。本文中實(shí)驗(yàn)結(jié)果的衡量標(biāo)準(zhǔn)使用精確度來(lái)衡量。

4.2 實(shí)驗(yàn)結(jié)果

本文中驗(yàn)證了在不同的距離函數(shù)下，地域約束和第二次聚類取得的結(jié)果。對(duì)于實(shí)驗(yàn)結(jié)果，我們?cè)诓煌木嚯x函數(shù)下，選取了一些帶指定字符串的實(shí)體單位名稱，第一次聚類參數(shù)ε設(shè)為0.1 和0.2，距離函數(shù)選擇分別為Jaccord 相似度系數(shù)，TF-IDF 余弦相似度，以及Word2Vec 歐式距離相似度。第二次聚類為地域信息加上二次密度聚類，對(duì)第一次聚類的結(jié)果進(jìn)行劃分。我們使用人工識(shí)別的方法，采用上述的精確度的方法來(lái)衡量不同方法的評(píng)分?jǐn)?shù)值。

我們選取了4 類實(shí)體，指定包含的字符串實(shí)體單位名稱，如表1。

表1 選取實(shí)體類別

篩選出這四類實(shí)體，計(jì)算對(duì)應(yīng)的精確度。第一次基于不同向量表示函數(shù)和二次聚類結(jié)果如表2所示。

由于JaccordJaccord 相似度系數(shù)函數(shù)是將表述存在少量差異的實(shí)體名稱進(jìn)行聚合，當(dāng)實(shí)體間的表述差異為少數(shù)幾個(gè)字符串且實(shí)體名稱較長(zhǎng)時(shí)，使用Jaccord 將無(wú)法進(jìn)行分離。如“［'the affiliated changzhou maternity and child health care hospital of nanjing medical university'，'the affiliated maternity and child health hospital of nanjing medical university'，'the affiliated maternity and child health hospital of nanjing medical university wuxi'］”。在使用本論文提出的地域約束后能夠?qū)⒋嬖谏倭繉?shí)體表述差異的實(shí)體進(jìn)行分離從而提高衡量標(biāo)準(zhǔn)評(píng)分結(jié)果。

由于TF-IDF 余弦相似度函數(shù)是基于詞頻權(quán)重，將表述存在較多相近關(guān)鍵詞的實(shí)體名稱進(jìn)行聚合，當(dāng)不同實(shí)體的表述差異在非關(guān)鍵詞體現(xiàn)時(shí)，則難以將不同實(shí)體進(jìn)行分離。以包含帶“university”，“child”，“maternity”，“hospital”字符串的實(shí)體單位名稱為例子，第一次聚類產(chǎn)生如［'no 7 people hospital in zhengzhou'，'shanghai 7th people hospital'，'the 7th people hospital'，'the 7th people hospital of chengdu'，'the 7th people hospital of shanghai'，'the dalian 7th people hospital'］。由于“people”，“hospital”為表述關(guān)鍵詞，因此TF-IDF 將這些不同表述的實(shí)體形成了聚合。采用地域約束的方式能夠?qū)⒉煌赜虻膶?shí)體進(jìn)行分離，采用二次聚類能夠放大非公有詞即使這些非公有詞為非高權(quán)重關(guān)鍵詞，但由于實(shí)體間差異同為非高權(quán)重關(guān)鍵詞，因此能將其進(jìn)行分類提高衡量標(biāo)準(zhǔn)評(píng)分結(jié)果。

由于word2vec 歐式距離函數(shù)是基于語(yǔ)義的方式將詞序相近的不同實(shí)體名稱聚合。當(dāng)不同實(shí)體的表述差異不體現(xiàn)為詞序差異而是少量字符差異時(shí)則無(wú)法將不同實(shí)體進(jìn)行分離，如：［'gongan county people hospital'，'huichang county people hospital'，'huidong county people hospital'，'lianghe county people hospital'，'linxian county people hospital'，'qianxi county people hospital'，'shache county people hospital'］。在這一例子中，實(shí)體表述皆為名詞性短語(yǔ)描述，差異體現(xiàn)在對(duì)于名詞的定義字符上，因此word2vec 無(wú)法將其分離。采用二次聚類能夠放大非公有部分來(lái)增大實(shí)體間差異，從而進(jìn)行不同實(shí)體分離，因此能將其進(jìn)行分類提高衡量標(biāo)準(zhǔn)評(píng)分結(jié)果。

基于上述分析，本文提出的方法，采用地域約束的方式能夠?qū)⒉煌赜虻膶?shí)體進(jìn)行分離。在此基礎(chǔ)之上，再一次對(duì)各個(gè)簇進(jìn)行第二次DBSCAN，能夠放大非公有項(xiàng)，增大相近但不一致的實(shí)體間差異，從而提高聚類結(jié)果的可行性。在本文中，二次聚類主要解決了密度聚類過(guò)程中，通過(guò)邊界點(diǎn)將表述比較相似，但是屬于不同實(shí)體合并為同一個(gè)簇的問(wèn)題。

5 結(jié)語(yǔ)

本文對(duì)密度聚類進(jìn)行了改進(jìn)，在第一次聚類的結(jié)果上，進(jìn)行二次聚類。二次聚類的過(guò)程中，分為兩步，第一步是對(duì)第一次聚類產(chǎn)生的每個(gè)簇進(jìn)行地域劃分。第二步是在經(jīng)過(guò)地域約束處理后產(chǎn)生的新的簇之上，對(duì)其進(jìn)行第二次密度聚類?；诘赜蚣s束，將聚類產(chǎn)生的簇中所屬不同地域的單位進(jìn)行進(jìn)一步的分離，減少由表述相似帶來(lái)的誤差。在基于地域約束產(chǎn)生的結(jié)果上，進(jìn)行第二次密度聚類。設(shè)計(jì)第二次密度聚類的距離函數(shù)，放大實(shí)體間的不同表述對(duì)實(shí)體表述的影響，減少由于密度聚類將不同實(shí)體簇聚合成為同一個(gè)簇這種情況下帶來(lái)的消歧誤差，結(jié)合這兩種情況提高聚類結(jié)果的準(zhǔn)確率。但是在使用地域約束時(shí)，對(duì)于部分沒(méi)有附加地域信息的單位表述，會(huì)獨(dú)立劃分成新的簇，這是之后需要解決的一個(gè)問(wèn)題。對(duì)于文本相似度計(jì)算，word2vec 雖然能夠解決對(duì)單位實(shí)體長(zhǎng)短表述不一致的問(wèn)題，但是并不能將長(zhǎng)短表述不一致的但是為同一實(shí)體的聚合。對(duì)于如何將這種長(zhǎng)短表述不一致的實(shí)體表述進(jìn)行聚合，有待于進(jìn)一步的研究和探討。