多信息加權融合實體對齊算法

馬建紅 劉雙耀 楊 珺

(河北工業大學人工智能與數據科學學院 天津 300401)

0 引 言

近年來，知識圖譜[1]一直是各領域研究的熱點，知識圖譜的構建能夠在一定程度上促進創新的發展，構建完整的知識圖譜需要通過融合多個異構數據源來解決單一數據源知識涵蓋不足、屬性缺失等問題。因此多源異構知識庫的融合問題，便成為知識圖譜發展過程中的研究熱點，其中實體對齊是異構數據源融合的關鍵步驟，即發現兩個或多個數據源中指向現實中同一物質的實體對[2]。由于不同數據源本體的異構性，導致知識的分類結構、表述規范存在一定的差異，如何解決這些差異，并完成多個數據源實體的對齊任務成為了實體對齊算法的難點。

數據源中實體普遍存在“一詞多義”和“一義多詞”等問題，如“氧氣”可以代表化學元素、歌曲名稱、電影名稱、手機應用等多種物質；物理領域“磁通量”這個實體在不同的百科網站有不同的名稱，在百度百科中命名為“磁通量”，在互動百科中命名為“磁通”。因此僅通過實體的名稱屬性難以確定兩個實體是否為現實中同一實體，需要借助有效的實體對齊算法來判斷兩個實體是否為現實中同一實體，從而完成異構數據源的知識融合任務。

1 實體對齊算法

實體對齊算法基本分為兩個方向，基于實體相似度理論[3]的實體對齊算法和基于表示學習[4]的實體對齊算法。文獻[5]提出了一種實體屬性與上下文主題特征相結合的實體對齊算法，該算法以人物類和影視類百科數據為測試集取得了不錯的實驗效果，但針對不具備完整上下文信息的數據表現不佳。文獻[6]提出了一種基于網絡語義標簽的中文知識庫實體對齊算法，在綜合計算多種標簽相似度的情況下取得了較好的對齊效果，其優點是充分利用了百科網站的分類標簽，解決了實體屬性信息缺失、摘要缺失的問題，但存在過度依賴實體標簽的問題。文獻[7]針對異構數據源提出了HistSim和DisNGram兩種選擇算法，HistSim利用實體對齊的歷史數據計算實體對相似度，修剪不匹配的實體，DisNGram算法通過字符級別相似性度量來選擇候選對齊實體。文獻[8]針對大規模數據提出了一種基于貪心算法的實體間對齊關系的推斷方法SiGMa，該方法組合字符串、屬性和結構信息以貪婪的局部搜索方式發現可對齊的實體。文獻[9]提出一種基于知識圖譜嵌入的Bootstrapping實體對齊算法，通過迭代標注出可能對齊的實體，生成新數據加入知識嵌入的模型中進行訓練，綜合利用圖譜全局信息進行實體對齊。

本文提出一種結合動態規劃求解最小編輯距離及引入Doc2vec[10]模型挖掘文本語義特征的實體對齊算法。該算法主要分為兩個部分，第一部分是對實體結構化信息進行數據規范化處理，制定統一描述框架，并通過最小編輯距離求解結構化屬性相似度；第二部分是通過Doc2vec模型對已經去除停用詞和分詞的非結構化文本進行訓練，提取包含其語義信息的特征向量，并通過余弦相似度進行相似度求解。最終通過權值調整，綜合結構化屬性相似度及非結構化文本相似度求解實體綜合相似度進行實體對齊判斷。同時設置對比實驗對本文算法進行驗證，實驗表明，本文算法在準確率和遷移性上均有所提高。

2 多信息加權融合實體對齊框架

本文所解決的實體對齊問題主要針對百科網站及專業化學網站等數據源，通過設計網絡爬蟲爬取各數據源中實體的名稱、簡介、信息表、正文和標簽等信息作為實驗數據。

(1) 通過數據統計算法對原始數據進行數據分析，制定統一的知識表述規范，同時構建專業名詞詞典，用于訓練分詞工具及擴展知識庫。

(2) 針對數據預處理后的結構化屬性引入動態規劃最小編輯距離求解其結構化屬性相似度。

(3) 利用Doc2vec模型深度挖掘非結構化文本語義信息，生成包含文本語義信息的特征向量，并求解余弦相似度獲取非結構化文本相似度。

(4) 通過權值調整，融合結構化屬性相似度及非結構化文本相似度，獲取實體綜合相似度生成候選集合。

(5) 設定閾值進行實體對齊判斷，輸出可對齊實體集合。

多信息加權融合實體對齊框架如圖1所示。

圖1 多信息加權融合實體對齊框架

2.1 研究思路

(1) 通過對多個數據源的本體分析，制定統一的資源描述框架，用于融合后的數據存儲。構建包含五萬余條專業名詞的領域詞典，用于實現數據擴充和訓練分詞工具解決分詞過程中專業名詞強拆分等問題，提高實體對齊算法的實用性。

(2) 針對實體結構化屬性及非結構化文本，分別采用動態規劃最小編輯距離和Doc2vec模型深度挖掘包含文本結構信息及語義信息的特征向量求解其相似度，最終加權平均融合實體多信息，獲取實體綜合相似度，提高實體對齊算法的準確性。

2.2 數據預處理

2.2.1制定統一描述框架

各個數據源中實體屬性信息包含了實體所擁有的所有屬性及屬性值等信息，但是由于數據源的本體異構性導致實體存在相同屬性不同表達方式、相同屬性值不同表述規范等問題，如百科中“分子量”就存在“分子量”“分子質量”“相對分子質量”等多種表達方式，同時相同的物質分子量值存在“16”“16g/mol”“16g·mol-1”等多種表達方式，這種問題會降低模型所求取的實體相似度，從而影響實體對齊的準確率。因此本文通過數據統計將從多數據源所爬取實體的所有屬性及屬性值的表示方式進行整合，結合眾包及人工審核的方式，選取化學領域中常用的屬性及屬性值表示方式為模板，構建了統一的知識庫表述規范。

2.2.2創建領域詞典輔助分詞

通過數據統計及眾包分析，將所有百科網頁中化學資源實體的名稱及別名進行篩選、分類，同時爬取專業化學網站的化學詞條名稱，構建了包含52 124條化學實體名稱的化學領域詞典。

本文采用jieba分詞工具對非結構化文本進行分詞，但現有的jieba分詞工具無法識別專業領域的新型名詞，會產生強拆分問題，例如:“硝基丙烷”會被拆分為“硝基”“丙烷”；“甲苯磺酰氯”會被拆分為“甲苯”“磺酰氯”等，這樣會嚴重影響訓練模型的結果。因此，將整理的化學領域詞典引入jieba分詞工具進行訓練，解決專業名詞強拆分問題，最終完成對非結構化文本信息的分詞工作，保證分詞的準確性。

Doc2vec模型是一種用于句向量訓練的模型，在輸入層增添了一個新的句子向量Paragraph，并在同一個句子的若干次訓練中是共享的，克服了詞袋模型中忽略詞序的缺點。由于Doc2vec模型需綜合考慮語句中各詞的前后信息，因此在去除停用詞階段僅去除正文中的標點符號及各類中英文符號。

2.3 最小編輯距離求解結構化屬性相似度

2.3.1最小編輯距離

字符串的最小編輯距離是形容字符串Str1轉換為字符串Str2的最少操作數，字符的操作包含插入、刪除、替換三種，通過對字符串中字符的操作，使兩個字符串相同，則最少的操作數為兩個字符串的最小編輯距離[11]，兩個字符串的最小編輯距離越小證明兩個字符串越相似，相同字符串的最小編輯距離為0。

將兩個句子Str1與Str2當作兩個字符串，假設Str1與Str2的長度分別為m和n，兩者的編輯距離則可以表示為edit[m][n]，則對句子進行操作時包含以下幾種情況。

1)Str1與Str2末尾字符相同情況下不需要進行任何操作，則滿足條件edit[m][n]=edit[m-1][n-1]。

2)Str1與Str2末尾字符不相同情況下則需要對兩者之一的末尾字符進行相應操作，并計數加1，具體操作如下：

(1) 對Str1或Str2的末尾字符進行替換操作，使之相等，則此時edit[m][n]=edit[m-1][n-1]+1。

(2) 刪除Str1末尾的字符，使Str1與Str2相等，則此時edit[m][n]=edit[m-1][n]+1。

(3) 刪除Str2末尾的字符，使Str2與Str1相等, 則此時edit[m][n]=edit[m][n-1] + 1。

(4) 在Str1的末尾添加Str2的末尾字符，使Str1與Str2相等，則此時Str1的長度變為m+1，但Str1和Str2的末尾字符已經相等，因此只需要比較Str1的前m個字符與Str2的前n-1個字符，滿足edit[m][n]=edit[m][n-1]+1。

(5) 在Str2的末尾添加Str1的末尾字符，使Str2和Str1相等，此時的情況與(4)相同，滿足edit[m][n]=edit[m-1][n]+1。

3) 特殊情況，當Str1為空時，edit[0][n]=n；當Str2為空時，edit[m][0]=m。

根據以上情況可以得到求解最小編輯距離的動態規劃方程為：

edit[m][n]=

(1)

其中flag計算式表示為：

(2)

因此可以通過動態規劃方法求取兩個句子的最小編輯距離edit(Str1,Str2)，同時規定兩個句子之間的最小編輯距離與最長句子長度的比值為兩句子相似度。

2.3.2結構化屬性相似度求解

通過數據預處理，實體E的結構化屬性已經規范化，相同屬性及屬性值的表達形式及表述規范都有了極大的相似度，因此可以通過最小編輯距離來比較高效地判斷兩個屬性對是否為同一屬性以及屬性值是否相同。定義實體屬性S1與S2的最小編輯距離為edit(S1,S2)，長度分別表示為len(S1)和len(S2)，則實體屬性S1與S2的相似度Sim(S1,S2)計算式為：

(3)

定義數據源A中實體Ea的m個結構化屬性為Pa={Pa1,Pa2,…,Pam}，對應的屬性值為Va={Va1,Va2,…,Vam};

定義數據源B中實體Eb的n個結構化屬性為Pb={Pb1,Pb2,…,Pbn},對應的屬性值為Vb={Vb1,Vb2,…,Vbn};

實體Ea與實體Eb的t個公共屬性集合CP=Pa∩Pb；

通過式(4)分別計算公共屬性集合CP中t個屬性的相似度SimCP(Pai,Pbi)，其中edit(Vai,Vbi)表示實體Ea與實體Eb第i個公共屬性的最小編輯距離，len(Vai)和len(Vbi)分別表示實體Ea與實體Eb第i個公共屬性的長度。

(4)

最終定義wi為實體第i個結構化屬性的權值，則通過式(5)求取實體Ea與實體Eb最終的結構化屬性相似度SimZ(Ea,Eb)。

(5)

2.4 Doc2vec模型求解非結構化文本相似度

待對齊的實體除了包含結構化屬性信息外還包含大量的非結構化文本信息，這些非結構化文本信息也包含大量的實體特性，如果實體的結構化屬性稀疏或缺失，則難以依靠僅有結構化屬性進行相似度求解，充分利用非結構化文本信息的特性，可以達到更好的實體對齊效果[12]。在非結構化文本的相似度求解過程中主要分為兩個步驟，第一步是通過Doc2vec模型對已經預處理的非結構化文本進行聯合訓練，生成包含文本語義信息的特征向量;第二步是獲取訓練后實體各個非結構化屬性的特征向量并迭代求解其余弦相似度。

2.4.1Doc2vec模型

Doc2vec模型是一種非監督式算法，可獲得短語、句子和文章等文本的向量表達，Doc2vec模型主要包含“句向量的分布記憶模型(PV-DM)”和“分布詞袋模型(PV-DBOW)”兩種訓練模式[13]。

如圖2所示，在句向量的分布記憶模型(PV-DM)中每一個段文本用唯一的句向量來表示，存儲在Paragraph矩陣的每一列中，同時每一個詞用詞向量來表示并存儲在矩陣Word的某一列中，每次從一句話中滑動采樣固定長度的詞，取其中一個詞作預測詞，其他的作輸入詞。輸入詞對應的詞向量Wordi和本句話對應的句向量Paragraph作為輸入層的輸入，將本句話的向量和本次采樣的詞向量相加求平均或者累加構成一個新的向量X，進而使用這個向量X預測此次窗口內的預測詞Word4。

圖2 句向量的分布記憶模型(PV-DM)原理圖

句向量的分布記憶模型(PV-DM)從固定長度的句子中采用滑動窗口取樣，通過隨機梯度下降的方法訓練句向量和詞向量，在此過程中通過反向傳播獲得梯度，并針對每一個隨機句子去更新模型參數，同時在預測階段通過梯度上升方式獲取一個新句子的句向量[14]。在這個模型里通過前后詞語向量的首尾相連或求均值來預測新增詞語，則最終生成的句向量可表示從當前上下文得來的信息，可以被當作包含句子語義信息的特征向量。

如圖3所示，分布詞袋模型(PV-DBOW)這種方式不把上下文中的詞作為輸入，而是強制這個模型在輸出過程中從句子中隨機抽取詞來進行預測[15]。即在每次迭代的時候，從文本中采樣得到一個窗口，再從這個窗口中隨機采樣一個單詞作為預測任務，讓模型去預測，輸入就是句向量Paragraph。實際上，其意義在于從每一個隨機梯度下降的循環中，抽取一個文本窗口，然后從該文本窗口中抽取一個詞，最終通過一個分類任務得到句向量。

圖3 分布詞袋模型(PV-DBOW)原理圖

2.4.2獲取非結構化文本語義特征向量

Word2vec模型只是基于詞的維度進行“語義分析”，并不具有上下文句子“語義分析”的功能。而Doc2vec模型是對Word2vec模型的改進，在訓練過程中增加了一個段向量，通過在已有上下文和段向量的基礎上預測單詞存在的概率。因此Doc2vec模型的訓練過程是對文本語義的挖掘過程，最終生成的文本表征向量包含了文本的語義信息。

將兩個數據源中所有實體的非結構化文本屬性進行編號，并放入同一個文件進行存儲，以換行符進行分割。使用參數化的Doc2vec模型進行句向量訓練，設置處理的滑動窗口大小為8個單詞，將每個句向量的維度設置為100維，并從訓練結果中提取每個非結構化文本屬性的句向量表示，生成特征向量文檔[16-19]。

2.4.3非結構化文本相似度求解

定義數據源A中實體Ea的m個非結構化文本屬性為Fa={Fa1,Fa2,…,Fam};對應的特征向量為Va={Va1,Va2,…,Vam}。

定義數據源B中實體Eb的n個非結構化文本屬性為Fb={Fb1,Fb2,…,Fbn};對應的特征向量為Vb={Vb1,Vb2,…,Vbn}。

提取每個待對齊實體對的非結構化文本屬性特征向量V，將實體Ea的每個非結構化文本屬性特征向量Va分別與實體Eb的n個非結構化文本屬性特征向量Vb進行余弦相似度求解，|Vai|和|Vbi|表示特征向量Vai和Vbi的模長，則實體對間每個非結構化屬性相似度Sim(Fai,Fbi)的計算式表示為：

(6)

設置相似度閾值為0.4，選取相似度最高屬性對，若相似度大于閾值0.4，則歸為相似屬性，記錄相似度，循環比較后最終得到的t個相似屬性對，則通過式(7)求取實體Ea與實體Eb的非結構化文本相似度SimF(Ea,Eb)。

(7)

2.5 實體對齊判斷

當通過動態規劃最小編輯距離及Doc2vec模型訓練語義特征向量等方法完成了待對齊實體對的結構化屬性相似度SimZ(Ea,Eb)及非結構化文本相似度SimF(Ea,Eb)的求解后，定義w1、w2分別為結構化屬性及非結構化文本所占的權值，最終通過式(8)對實體Ea、Eb的結構化屬性相似度SimZ(Ea,Eb)及非結構化屬性相似度SimF(Ea,Eb)進行權值歸一獲取實體綜合相似度SimE(Ea,Eb)。

SimE(Ea,Eb)=w1·SimZ(Ea,Eb)+w2·SimF(Ea,Eb)

(8)

針對數據源A中的每個實體Ea通過SimE(Ea,Eb)值對數據源B中的實體Eb進行降序排序，生成最優候選序列，選取相似度最高且大于設定閾值的實體Eb當作可對齊實體。

3 實驗與結果分析

3.1 實驗數據集描述

百度百科及互動百科包含豐富的實體資源及較為完整的屬性信息，因此為了驗證本文算法的有效性，本文分別從百度百科及互動百科中隨機抽取了部分化學領域實體，抽取的實體信息包含實體名稱、實體摘要、實體信息表、實體正文等，同時通過數據統計及人工標注的方法形成了一定數量的測試集，具體數據量如表1所示。

表1 實驗數據集

3.2 評價指標

實驗采用評價指標為準確率P、召回率R、綜合指標F1值，其定義如下：

(1) 準確率計算式表示為：

P=NT/(NT+NF)

(9)

式中：NT為實驗對齊結果中正確對齊的實體對數目；NF為實驗對齊結果中錯誤對齊的實體對數目。

(2) 召回率計算式表示為：

R=NT/NA

(10)

式中：NA為測試集中存在的可對齊實體對數目。

(3) 綜合指標F1值計算式表示為：

F1=2PR/(P+R)

(11)

準確率表示通過本文實體對齊算法后所得到正確對齊結果的準確程度；召回率表示通過本文實體對齊算法后得到的準確對齊實體數占測試集中所有可準確對齊實體的比率；F1值為衡量準確率與召回率的綜合指標。

3.3 實驗設置

(1) 權值w1、w2。本文中實體對齊算法是將實體結構化屬性相似度與非結構化文本相似度通過權值融合，求解實體綜合相似度，并生成可對齊實體候選集合，判斷實體對齊結果。因此在權值確定過程中人工抽取500對可對齊數據，分別采取結構化屬性權值與非結構化文本權值w1:w2由大到小進行測試實驗，以平均相似度高低為評價指標，結果如圖4所示。

圖4 w1、w2實驗結果

由于實驗數據是人工整理的可對齊數據，因此500對實驗數據的平均相似度越高則權值比例越符合要求。實驗結果表明結構化屬性與非結構文本權值w1:w2調節為7 ∶3時最合適。將w1、w2代入式(8)可計算實體Ea和Eb的綜合相似度SimE(Ea,Eb)。

(2) 相似度上界u、下界d、中間界限w。經過對多批數據集的實驗結果總結，實體綜合相似度SimE大于0.9的實體對可認定為一定可對齊實體，實體對相似度小于0.3的實體對可認定為一定不可對齊實體。因此設置相似度上界u為0.9，相似度下界d設置為0.3。

在實體對齊實驗中實體綜合相似度SimE需要在0.3與0.9之間取相似度閾值w，實體綜合相似度小于w的認定為不可對齊實體，相似度大于w的認定為可對齊實體，w的取值直接影響實驗結果的準確率、召回率及F1值。具體結果如圖5所示。根據實驗結果分析可得出如下結論，所取的相似度閾值w越大，實驗結果的準確率越高，召回率越低，反之所取的相似度閾值w越小，實驗結果的準確率越低，召回率越高。F1值是評價準確率和召回率的綜合指標，因此相似度閾值的取值應根據F1值進行選取，由圖5可知當相似度閾值取在0.5與0.6之間的時候F1值達到峰值，實驗中取w為0.55。

圖5 w取值實驗結果圖

3.4 實驗結果

確定好模型及參數后，在整理好的實驗數據集上進行測試，實驗結果如表2所示，表中分別列出了百度百科及互動百科部分實體名稱及通過多信息加權融合實體對齊算法求取的相似度，以及實體對齊結果。實驗結果可以驗證在預先設定的相似度閾值w為0.55情況下，多信息加權融合實體對齊算法可以獲得很好的對齊效果。

表2 實體對齊結果

3.5 對比實驗

為了進一步驗證本文算法(MED+Doc2vec)的有效性，設置了如下對比實驗，對比實驗結果如表3所示。

表3 對比實驗及結果

(1) MED+Doc2vec。采用最小編輯距離(MED)求解結構化屬性相似度，Doc2vec模型挖掘非結構化文本語義信息，生成包含語義信息的特征向量，求解相似度，除召回率略低于LCS-LDA方法，準確率及F1值較其他方法均有提高。綜合各項評價指標，可驗證本文算法的有效性。

(2) MED+Word2vec。采用最小編輯距離(MED)求解結構化屬性相似度，Word2vec模型訓練特征詞向量，采用向量拼接方法獲取非結構化文本特征向量，計算非結構化文本相似度，最終綜合求解實體相似度判斷對齊結果。由于Word2vec模型主要是針對詞向量進行訓練，只考慮詞的前后信息，經過拼接形成的句向量無法完全體現句子的語義信息導致準確率較低。

(3) LCS+LDA。采用最長公共子序列(LCS)求解結構化屬性相似度，LDA提取非結構化文本主題詞，構建特征向量，計算非結構化文本相似度，最終綜合求解實體相似度判斷對齊結果。由于LDA是一種詞袋模型，主要通過提取的主題詞進行向量建模，導致特征向量不能完全體現句子的完整信息造成準確率略低于本文算法。

(4) LCS+TF-IDF。采用最長公共子序列(LCS)求解結構化屬性相似度，TF-IDF提取非結構化文本特征，構建特征向量，計算非結構化文本相似度，最終綜合求解實體相似度判斷對齊結果。由于TF-IDF僅考慮句子中出現詞的詞頻特征，導致無法充分體現句子的語義信息，造成實驗準確率較低。

通過對比實驗結果可得多信息加權融合實體對齊算法除召回率略低于LCS+LDA實體對齊算法外，準確率及F1值較其他實體對齊算法均有明顯提高。召回率略低于LCS+LDA實體對齊算法是實驗數據中實體信息的缺失導致的，由于Doc2vec模型更注重通過詞語順序挖掘句子的語義信息，因此相比于LDA模型更加依賴信息的完整程度。但綜合多項評價指標及最終實驗結果，多信息加權融合實體對齊算法在準確率及實用性上均表現更佳。

4 結 語

為了解決多源異構數據庫融合過程中實體對齊的問題，本文針對現有實體對齊算法的不足之處，提出一種多信息加權融合的實體對齊算法。通過動態規劃最小編輯距離求解實體結構化屬性相似度，結合Doc2vec模型深度挖掘非結構化文本語義信息，并求解包含語義信息的特征向量相似度，最終通過權值調節，融合結構化及非結構化屬性相似度，獲得實體綜合相似度完成實體對齊任務。以百度百科及互動百科化學領域實體為數據集進行了實驗驗證，并通過與多種實體對齊算法的比較，有效驗證了多信息加權融合實體對齊算法的有效性。

后續的研究將進一步對算法進行優化調整，并將本文算法應用于多種不同領域進行實驗驗證，同時深入研究大規模數據環境下實體對齊算法的效率問題，這對異構數據源的融合及完整知識圖譜的構建有非常重要的意義。