基于地域約束的單位名稱二次聚類?

賀依依 黎鐵軍 蔣艷凰

（國防科學技術大學計算機學院 長沙 410073）

1 引言

近幾年來，鏈接開放數據的可用性越來越高，從而引申出了大規模知識圖譜［1］，如FreeBase［2］。在構建知識圖譜的過程中，需要從不同結構的數據中抽取特征節點（即實體，例如：人，組織，位置和其他類型等）以及定義節點間關系［3］。由于自然語言的表達存在多樣性、動態性、非規范性等問題，知識圖譜抽取的多個實體節點（實體名稱）可能存在多種表達方式，即表達歧義。因此需要對抽取出的實體進行歧義的消解。

在進行實體消歧過程中，研究的內容主要分為兩類：同名消歧與多名聚合［4］。由于翻譯、縮寫、書寫方式等問題，造成了對同一個實體單位有不同的表述方式。將這些不同的表述方式識別成同一個實體，即為多名聚合。目前多名聚合問題的其中一種解決方法是利用上下文信息構建特征向量結合相似度計算實體間距離。將一定閾值距離范圍內的實體進行聚合，從而達到消除歧義的目的［5］。但是對于大多數上下文信息匱乏的文本，在進行多名聚合過程中，模型無法明確給定實體的特征信息或文本的標簽描述。由于不存在明確的文本標簽描述，無法通過目前常用的分類方式（如語義網絡［6］等）來完成對不同實體的分類。在這一條件下只能通過實體表述本身的文本信息進行相似度的計算，獲取實體間距離來進行無監督聚類。基于統計的計算和基于規則的計算等方式是目前主流的解決方式。通過將短文本轉化為計算機可識別的向量來進行文本間的距離計算。

當大規模數據是無標簽時，一般是以聚類的方式，對同一實體的不同表述進行聚合。在聚類的過程中，主要通過設定文本表述的相似度距離的閾值，將文本表述相似的聚成同一個簇。本文中，主要使用的聚類算法是密度聚類，通過使用密度聚類，將無標簽短文本的實體進行多名聚合，解決無實體標簽時，無法確定實體的個數問題。然而使用密度聚類時，由于使用的是固定的參數，會出現相近的類被合并成一個聚類。因此在此基礎之上，還可以進行二次聚類。

本文中提出了二次聚類的方法。第一次密度聚類將大致相同的實體表述聚合在同一個簇。在第一次聚類的基礎上，使用地域約束和第二次聚類對第一次密度聚類產生的簇，進行進一步劃分，解決密度聚合過程中由于密度距離泛化導致的同一簇內存在多個不同實體的問題。

2 相關工作

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

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

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

3 方法

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

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

圖1 處理框架圖

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

本文中主要的創新點在于聚類部分，下面主要介紹聚類部分。

3.1 DBSCAN

DBSCAN（Density-Based Spatial Clustering of Application with Noise）是基于密度的聚類算法，將密度相連的點的最大的集合定義為簇，能夠把足夠高密度的區域劃分為簇，并且能夠發現任意形狀的簇。通過密度聚類，能夠將數據集中的實體表述劃分為不同的簇。

DBSCAN［12］可以被定義為

式（1）中C 表示集群的子數據集集合，SD表示應聚類的點P 的數據集，ε是SD中點P 的鄰域的最大半徑，MinPts 定義簇中的最小點數。其中ε在本文中為兩個單位文本表述之間的相似度距離，相似度距離范圍大小可調。ε和MinPts是影響DBSCAN聚類過程的兩個輸入參數。

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

3.2 二次聚類

3.2.1 地域約束

在采用聚類算法進行多名聚合時，由于文本附加信息的缺乏，只采用字符串間相似度可能會將存在部分描述一致的不同實體合成同一個簇。基于此，基于密度聚類生成的簇類中，可能存在表述類似，但是屬于不同實體的情況。為了進一步區分同一簇里的不同實體，本文旨在引入識別的單位實體所處的地域信息。地域信息可以作為簇中單位表述的附加約束信息，來進一步區分簇中不同的實體。其中地域約束的信息來源于數據預處理中得到的單位與地域信息詞典。

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

算法1：基于地域約束的簇內合并算法

輸入簇內組織集合：Sorg

輸入簇內組織對應的城市集合：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）合并進入Cj′

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

isNew=FALSE

end

if isNew do

為子簇C′創建新元素Cnew′

city（new）=city（j）

end

end

end

輸出子簇C′

在算法1 中，每個組織實體org（i）對應一個所屬的城市集合city（i）（如分校區的存在可能導致某一大學在不同城市同時存在）。如果兩個組織的城市集合間交集與其并集一致，則代表兩者的城市集合交集為空。兩個組織不在同一城市出現過，因此將其分離。如果兩個組織的城市集合間交集與其并集不一致，則兩者的城市集合存在公有項，即Size（city（i）∩city（j））＜size（city（i）∪city（j））。若兩個組織在同一城市存在過，將其合并。通過對組織實體對應的所屬城市集合的集合運算能夠對簇內的不同實體進行進一步約束，將同一所屬地域的組織進行進一步聚合，將不同地域的組織進行進一步分離。

3.2.2 第二次DBSCAN

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

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

4 實驗

4.1 實驗數據和評估標準

現階段從120 萬篇pubmed 論文的摘要中抽取出來了300 多萬條作者所屬信息。這些信息進行處理，抽取出作者所屬單位，單位所在城市，國家。對抽取出來的單位表述，取最大級別表述。比如一個作者所屬單位是301 醫院某個科室，我們只取出301 醫院作為這個作者所屬的單位。因此，本文中實體消除歧義的工作，就是對這些單位實體進行消歧。將300 多萬條信息經過數據預處理去重后，得到10 萬條不同的單位表述，對其進行聚類。本文中實驗結果的衡量標準使用精確度來衡量。

4.2 實驗結果

本文中驗證了在不同的距離函數下，地域約束和第二次聚類取得的結果。對于實驗結果，我們在不同的距離函數下，選取了一些帶指定字符串的實體單位名稱，第一次聚類參數ε設為0.1 和0.2，距離函數選擇分別為Jaccord 相似度系數，TF-IDF 余弦相似度，以及Word2Vec 歐式距離相似度。第二次聚類為地域信息加上二次密度聚類，對第一次聚類的結果進行劃分。我們使用人工識別的方法，采用上述的精確度的方法來衡量不同方法的評分數值。

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

表1 選取實體類別

篩選出這四類實體，計算對應的精確度。第一次基于不同向量表示函數和二次聚類結果如表2所示。

由于JaccordJaccord 相似度系數函數是將表述存在少量差異的實體名稱進行聚合，當實體間的表述差異為少數幾個字符串且實體名稱較長時，使用Jaccord 將無法進行分離。如“［'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'］”。在使用本論文提出的地域約束后能夠將存在少量實體表述差異的實體進行分離從而提高衡量標準評分結果。

由于TF-IDF 余弦相似度函數是基于詞頻權重，將表述存在較多相近關鍵詞的實體名稱進行聚合，當不同實體的表述差異在非關鍵詞體現時，則難以將不同實體進行分離。以包含帶“university”，“child”，“maternity”，“hospital”字符串的實體單位名稱為例子，第一次聚類產生如［'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”為表述關鍵詞，因此TF-IDF 將這些不同表述的實體形成了聚合。采用地域約束的方式能夠將不同地域的實體進行分離，采用二次聚類能夠放大非公有詞即使這些非公有詞為非高權重關鍵詞，但由于實體間差異同為非高權重關鍵詞，因此能將其進行分類提高衡量標準評分結果。

由于word2vec 歐式距離函數是基于語義的方式將詞序相近的不同實體名稱聚合。當不同實體的表述差異不體現為詞序差異而是少量字符差異時則無法將不同實體進行分離，如：［'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'］。在這一例子中，實體表述皆為名詞性短語描述，差異體現在對于名詞的定義字符上，因此word2vec 無法將其分離。采用二次聚類能夠放大非公有部分來增大實體間差異，從而進行不同實體分離，因此能將其進行分類提高衡量標準評分結果。

基于上述分析，本文提出的方法，采用地域約束的方式能夠將不同地域的實體進行分離。在此基礎之上，再一次對各個簇進行第二次DBSCAN，能夠放大非公有項，增大相近但不一致的實體間差異，從而提高聚類結果的可行性。在本文中，二次聚類主要解決了密度聚類過程中，通過邊界點將表述比較相似，但是屬于不同實體合并為同一個簇的問題。

5 結語

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