作為一種新型、實用的知識組織工具，知識圖譜旨在描述真實世界中的各種實體、概念及其關系，已廣泛應用于互聯網搜素引擎、電子商務等方面。它在實現海量信息資源的深度挖掘、廣泛融合、理解利用方面發(fā)揮了重要作用。知識圖譜本質是一種基于圖數據結構的語義網絡，由節(jié)點和邊組成，節(jié)點表示現實世界的實體，邊表示實體與實體之間的語義關系。

隨著各領域圖譜數量的不斷增加，解決概念體系異構、消除知識實體之間的互操作障礙已成為圖譜應用面臨的關鍵問題。圖譜匹配技術旨在建立概念體系和知識實體之間的語義關系，架起異構圖譜間的橋梁。由于圖譜異構類型的復雜性和多樣性，以及單匹配技術的局限性，知識圖譜融合系統(tǒng)需要組合多種匹配方法才能具有較好的通用性和較為理想的映射結果。如何有效聚合不同匹配器得出的相似度值是圖譜融合亟待解決的問題，是制約多匹配器融合算法自動化的瓶頸。

本文首先通過調研、比較分析幾個典型的知識融合系統(tǒng)，總結知識圖譜融合框架，并將其作為系統(tǒng)設計的參考模型；然后重點研究多匹配器的自動優(yōu)化、聚合器的自適應聚合參數調節(jié)等核心組件的設計，減少在映射參數設置上的人工干預，提高融合系統(tǒng)的自動化程度。在這些工作的基礎上構建一種基于多匹配器自適應聚合的知識圖譜融合系統(tǒng)原型，并進行初步實驗。

1 知識圖譜融合研究現狀

知識圖譜融合的任務是對不同來源、不同結構的知識或知識片段進行融合。通過對多個相關知識圖譜的對齊、關聯和合并，從而對已有知識進行補充、更新和去重，使其成為一個有機整體，以提供更全面知識的共享[1]。知識融合需要解決概念體系的融合和知識實體的融合兩個問題。

概念體系的融合是兩個或多個異構概念體系的融合，是對概念、屬性、關系等知識描述體系進行映射和融合，可以解決知識體系之間的異構性，也稱為本體對齊[2]。知識實體級別的融合即實體對齊，是對兩個不同知識圖譜中的實體(實體本身、屬性等)進行融合。實體對齊的核心是計算兩個知識圖譜中節(jié)點或邊之間的語義關系，主要通過實體名稱及屬性相似度映射的方式。目前知識融合普遍的做法是通過相似度計算(如基于字符串、詞典、詞向量、結構信息以及混合方法等)，對于大于指定相似度閾值的候選對，會提示用戶進行干預或編輯確認，從而實現知識圖譜的融合。如YAGO將Wikipedia中的類別標簽與WordNet的同義詞集進行關聯，同時將Wikipedia中的條目掛接到WordNet的概念體系下，使WordNet能提供較高層的概念體系，使Wikipedia可提供具體的實例信息[3]。

AgreementMakerLight(AML)[4]是一種可擴展的自動化知識融合框架，主要針對大規(guī)模的生物醫(yī)學領域知識的對齊問題，是AgreementMaker[5]的升級版。AML實現了基于字符特征(編輯距離、最長公共字符串等)或利用背景知識庫的多種匹配器，并根據映射效率的不同將其組合為主要匹配器和次要匹配器兩類，用于不同需求的融合場景。最后通過過濾器剔出低于給定相似性閾值以及相互沖突的候選對，從而得到最終期望的對齊結果。

WikiMatch[6]是一個將Wikipedia作為外部背景知識庫的融合系統(tǒng)，通過維基百科搜索引擎提取每個知識節(jié)點在維基中的片段、標簽和注釋，知識節(jié)點之間的相似度就轉化為對應維基片段、標簽和注釋的相似度計算。由于維基百科文章存在多語言版本，并且這些文章彼此是相互鏈接的，因此WikiMatch解決了跨語言知識的融合問題。

S-Match[7]是用于匹配輕量級知識庫的開源融合框架，實現了多個語義匹配器，同時提供多種接口，能夠添加自定義背景知識。S-Match的匹配器分為元素級匹配器和結構級匹配器兩類。映射結果通過預定義的冗余結果過濾器進行過濾和選擇。

SiGMa[8]是一種使用迭代傳播的大規(guī)模知識庫實體對齊系統(tǒng)，利用關系圖中的結構信息及貪婪搜索方式計算實體屬性之間的相似性，以解決大規(guī)模的知識對齊問題。SiGMa充分利用了實體屬性定義的相似度和實體周圍節(jié)點的信息。

2 知識圖譜融合框架設計

筆者以上述4個知識融合系統(tǒng)為代表，詳細剖析了這些系統(tǒng)的組成、融合過程及特點，提出了一種知識圖譜融合系統(tǒng)框架(圖1)。

圖1 知識圖譜融合系統(tǒng)框架

知識圖譜融合系統(tǒng)一般由6部分組成，各部分通過預先定義的接口完成數據傳遞。

預處理器：待匹配知識圖譜導入系統(tǒng)后，進行知識節(jié)點(概念節(jié)點、實體節(jié)點)及特征屬性的提取。

匹配策略選擇器：通過用戶交互或者特征分析，選擇與組合合適的匹配策略，其實質是不同匹配器的選擇與組合。

匹配器：是知識圖譜融合系統(tǒng)的核心部分。本文將執(zhí)行知識節(jié)點相似度計算的簡單匹配器稱為原子匹配器，將綜合使用多種匹配算法的匹配器稱為混合匹配器。

聚合器：通過某種數學方法或規(guī)則將多個匹配器計算的相似度結果值整合為單一相似度的過程。

結果優(yōu)化器：根據預先設定的優(yōu)化規(guī)則篩查不正確的映射關系或低于某一閾值的映射關系，進行最終結果的確認。

用戶交互器：實現知識圖譜的輸入與輸出，以及結果的確認和保存等多項功能。

3 多匹配器自動聚合算法設計

3.1 多匹配器設計

單個匹配技術自身的局限性以及圖譜異構類型的復雜性和多樣性，決定了不會存在某種匹配技術適用于所有異構的圖譜資源，并能夠有效解決各種映射問題。知識圖譜融合系統(tǒng)需要組合多種匹配方法，才能具有較好的通用性和較為理想的映射結果。本文設計了Edit-WordNet、I-sub和Context(語境)3個單獨運行的匹配器。

3.1.1 Edit-WordNet匹配器設計

基于計算編輯距離的相似度能夠發(fā)現知識節(jié)點詞形特征的相似性，而基于WordNet的相似度能夠發(fā)掘其語義上的相似性。由于側重點不同，本文設計的Edit-WordNet混合匹配器可以互補兩者的優(yōu)勢。

定義1：編輯距離相似度算法的計算公式為：

(1)

式中，max(|s1|,|s2|)指較長詞條的字母數目，LD(s1,s2)表示詞條s1、s2之間的編輯距離。

定義2：基于WordNet相似度算法公式為：

Sim(s,t)=2×depth(c)/[depth(s)+depth(t)]=2×depth(c)/[2×depth(c)+n1+n2]

(2)

該公式是Wu Zhibiao和Palmer Martha[9]提出的算法，使用知識節(jié)點間的“IS-A”關系來尋找兩個概念s和t的最近公共上位詞c，最近公共上位詞c是與概念詞s和t間以最少的“IS-A”關系邊相關聯的公共上位詞。公式2中，n1和n2分別表示概念詞s、t與最近公共上位詞c間的最短相對路徑長度。Edit-WordNet算法的主要實現步驟如下。

第一步：分別建立源圖譜和目標圖譜所有單詞符號的上位(is-a)關系矩陣word_1[m][wordPOS.Length](m為源圖譜知識節(jié)點數組KGSource[]長度)和word_2[n][wordPOS.Length]。其中,行是知識節(jié)點預處理后的單詞符號，列為詞性。上位關系矩陣用于保存單詞符號在某一詞性下(名詞、動詞)的所有synset節(jié)點到獨立起始概念(沒有上位概念的節(jié)點)的路徑節(jié)點的信息，包括上位關系節(jié)點的名稱、相對于該synset節(jié)點的相對路徑長度、路徑深度等。

第二步：計算單詞符號之間的相似度：

for(int i=0;i

for(int j=0;j

{

float synDist=LDsim(KGSource[i],KGTarget[j]);//調用編輯距離相似度

①令semDist=Math.Max(Sim(word_1[i][noun],word_2[j][noun]),……,Sim(word_1[i][adverb],word_2[j][adverb]))。其中Sim()的計算方法是根據上位關系矩陣中的節(jié)點名稱和路徑等信息，循環(huán)查找其最近的公共上位詞，通過公式1計算相似度;

②simMatrix[i][j]=Math.Max(semDist,synDist); //對完整度的考慮

}

第三步：歸一化相似度矩陣，通過公式SimWordNet=(sumSim_i+sumSim_j)/(m+n)得到最終相似度值。其中sumSim_i為行最大值之和，sumSim_j為列最大值之和。

3.1.2 I-sub匹配器設計

I-Sub算法是希臘雅典理工大學的Giorgos Stoilos等人從術語學的角度提出的術語映射方法。與同類算法比較，I-Sub具有更好的魯棒性。這種方法計算的相似度由3部分組成：

sim(s1,s2)=comm(s1,s2)-diff(s1,s2)+winkler(s1,s2)

其中，comm(s1,s2)代表兩個字符串的相同點，diff(s1,s2)代表兩個字符串的不同點，winkler(s1,s2)是由winkler提出的一種改善相似度結果的算法[10]。

3.1.3 Context(語境)匹配器設計

Context(語境)匹配器的主要思想是利用知識節(jié)點周圍的多種描述數據為每一個節(jié)點建立一個語境的描述，然后通過向量空間模型方法計算語境之間的相似度，從而得到知識節(jié)點之間的相似度。

知識節(jié)點語境由結構面、屬性面等分面語境構成。結構面語境由知識節(jié)點本身的定義信息(名稱、標簽、注釋)及其所有上位概念、下位概念和同位概念信息構成，用ConS表示；屬性面語境由概念屬性的集合及其屬性的注釋、限制(定義域、值域)等信息構成，用ConA表示；實例面語境由概念的實例集合構成，由ConI表示。結合上述定義，知識節(jié)點cn的語境ConC(cn)可表示為{ConS(cn)，ConA(cn)，ConI(cn)}。圖2所示的書目概念圖譜，Book的語境可以粗略表示為：ConC(Book)={ConS(Book)，ConA(Book)，ConI(Book)}={ Book,book,monograph,collection,written,texts,Entry,Monography,Compilation,Conrerence,Minutes,heading,volume,issue,publishedBy}。

圖2 書目概念圖譜片段

基于知識節(jié)點語境的相似度算法重點在于通過語境建立向量空間模型，通過計算向量之間的相似度(如向量的內積)計算知識節(jié)點之間的相似度。核心算法如下。

第一步：逐一計算每個關鍵詞在每個知識節(jié)點語境中的權重值。

for(int i=0;i<關鍵詞個數numTerms;i++)

for(int j=0;j<概念語境的個數numDocs;j++)

{

關鍵詞i在語境j中出現的頻率freq=termFreq[i][j]；

語境j中所有關鍵詞出現次數最大值maxfreq=maxTermFreq[j]；

計算文檔頻率tf=freq/maxfreq；

語境空間中含有關鍵詞i的語境數目df=docFreq[i]；

計算逆文檔頻率idf=Log(numDocs/df)；

計算關鍵詞i在語境j中的權重值termWeight[i][j]=tf×idf；

}

第二步：計算每對知識節(jié)點基于語境的相似度值。

for(i=0;i

for(j=m;l

{

通過termWeight矩陣，生成權重向量vector(i)，vector(j)；

sim(vector(i),vector(j))=(vector(i)·vector(j))/|vector(i)|×|vector(j)|

}

3.2 匹配器優(yōu)化設計

單獨匹配器在圖譜映射的計算過程中，需考慮每一對知識節(jié)點之間的相似性。假設源KG1中含有m個元素，目標KG2中含有n個元素，則要進行m×n次相似度計算，形成一個m×n維的相似度矩陣。對于1∶1映射，現有的映射方法大多從相似度矩陣中依次挑選出一一對應的、具有高相似性的元素對作為候選映射。因此對于該m×n維的矩陣來說，存在大量毫無意義的相似度值只會增加后續(xù)(如相似度合并)運算的復雜程度，有必要對匹配基數為1∶1的映射采用優(yōu)化策略，對相似度矩陣的規(guī)模進行調節(jié)。

受Similarity Flooding和AgreementMaker系統(tǒng)的啟發(fā)，將這個問題轉化為一個最優(yōu)化分配問題。筆者利用帶權二分圖的思想將匹配器的計算過程做如下建模：定義源圖譜1的所有元素為集合X={x1,x2,…,xm}，目標圖譜2的所有元素為集合Y={y1,y2,…,yn}，然后把兩個集合元素對之間所有可能的m×n個映射關系表示為邊集E，各個元素對的相似度值為邊集E的權重值wij，將其處理后生成一個帶權的完全二分圖，計算出該完全二分圖的最大權匹配，其邊集所對應的頂點元素對集合就是匹配器輸出的最優(yōu)候選映射對(圖3)?？梢圆捎萌缧傺览椒ê妥疃淘鰪娐窂剿惴▉斫鉀Q算法設計問題，此處不再贅述。本文對上述3個匹配器進行了二分圖的優(yōu)化，并作為下文中聚合器的輸入。

圖3 二分圖最大權優(yōu)化示意

3.3 自適應的聚合器設計

聚合器旨在組合多個匹配器的映射結果,如何有效聚合不同匹配器得出的相似度值是制約多匹配器匹配算法的瓶頸。從具體實現上來看，基于函數聚合相似度的方法簡單易實現、易于理解、合并效率較高。然而在這些系統(tǒng)的具體權重值的設定方面，要么通過事前驗算和模擬實驗探索比較合理和滿意的經驗值參數，要么通過用戶交互接口將權重設置權限交給用戶。這些做法無法根據不同的映射任務而靈活調整權重，盲目的聚合往往會削弱有效匹配器的映射效能，嚴重影響映射的發(fā)現。自動聚合的關鍵是能夠根據不同的融合場景自動設置各個匹配器的權重，而權重值的大小與其匹配質量正相關。

理論上講，正確的等同關系映射應該是從KG1到KG2的映射與KG2到KG1的映射所產生的映射關系一致，即在這兩個映射方向上計算的相似度值與其他候選元素對相比都是最高的(所在矩陣的行和列均為最大值)。筆者將這種映射關系稱為穩(wěn)定映射(Stable Match，SM)，因此可以將穩(wěn)定映射的數量作為相似度聚合前粗略測度不同匹配器適用性大小的一個指標。也就是說，哪種匹配算法得到的穩(wěn)定映射關系越多，就說明其適用性越好，在聚合的時候賦予的權重值就應當越高。

圖4是一個基于I-sub算法的相似度矩陣。圖中的加粗斜體數值表示2個映射方向均為最高的相似度值，因此產生了2個穩(wěn)定映射關系(“Inbook”,“Inbook”)和(“Incollection”,“Collection”)；而(“Inbook”,“Book”)不是穩(wěn)定的，因為在KG1到KG2方向上不是最大值。

經過上述步驟，我們將匹配器i的權重值定義為：

式中，counti(CM)表示匹配器i產生的穩(wěn)定映射關系的個數，Sum(count(CM))表示所有匹配器產生的穩(wěn)定映射關系個數之和，由此得到的聚合器計算公式為：

(3)

根據上述單獨匹配器的設計及優(yōu)化后的結果，將各個單獨匹配器產生的最優(yōu)候選映射對作為聚合器的輸入，然后將3組最優(yōu)候選映射的所有源圖譜節(jié)點元素重新組合為集合X′，目標圖譜元素組合為Y′，最后將最優(yōu)候選映射對根據公式(3)進行多相似度值的結果聚合，生成一個新的m′×n′的相似度矩陣。該矩陣可以進一步通過二分圖優(yōu)化或通過閾值策略作為最終結果的輸出。

4 原型系統(tǒng)構建和初步實驗

根據算法設計和分析初步構建了實驗原型系統(tǒng)。該系統(tǒng)運行界面如圖5所示。為了驗證算法的可行性，我們選用單位自建的飛機(KG1，77個知識節(jié)點)與電子對抗裝備(KG2，346個知識節(jié)點)2個領域的知識片段進行了實驗。由于系統(tǒng)采用1∶1的完全二分圖最大權匹配輸出，所以共產生了77對結果集。通過分析發(fā)現，等同和包含關系的映射對集中于閾值>0.85的范圍內(見表1，其中僅第9、第10兩個不相關)，除了字形特征完全相同的所有映射對被發(fā)現外，通過Context或Edit-WordNet匹配器還發(fā)現了(Early_Warning_Aircraft，Early_warning_helicopter)等映射對。實驗初步證明，該系統(tǒng)能夠較為有效地發(fā)現相關知識節(jié)點。

圖4基于雙向映射計算穩(wěn)定映射關系示例

圖5 實驗原型系統(tǒng)運行界面

表1 實驗結果

5 總結與展望

本文的主要研究目的是設計一個自調節(jié)映射參數的知識圖譜融合算法，實現多匹配器的自動優(yōu)化、聚合參數的自動調節(jié)以及映射結果的自動輸出，并在此基礎上構建了一個工具原型和進行了初步實驗。實驗結果初步驗證了融合算法在無人工干預的情況下能夠有效發(fā)現語義相關的知識節(jié)點，為未來系統(tǒng)的構建奠定了基礎。

由于受時間和條件的限制，本文研究仍存在以下一些問題，有待今后進一步探討和解決。需進一步研究結果修正方法，即擬針對單獨匹配器引入最小閾值參數，排除不可能的映射對，進一步提高算法的準確性。最小閾值將通過大量實驗進行選擇。

鑒于WordNet語義相似度算法的缺陷，如何對多義詞進行語義消歧、取出元素synset的正確位序是未來WordNet語義相似度算法改進的重點。此外，圖匹配理論和結構相似性傳播理論是多數先進知識融合系統(tǒng)普遍采用的方法，今后將在后續(xù)版本中加以考慮。

實驗結果有一定的局限性，下一步擬擴大實驗數據范圍，并采用多種性能評測標準進行測試，為系統(tǒng)的進一步優(yōu)化與改進提供依據。