關于主動學習下的知識圖譜補全研究*

陳欽況，陳 珂,2+，伍 賽,2，壽黎但,2，陳 剛,2

1.浙江大學 計算機科學與技術學院，杭州 310027

2.浙江省大數據智能計算重點實驗室（浙江大學），杭州 310027

1 引言

隨著信息科技的突破，新一代人工智能迎來了史無前例的發展熱潮。知識圖譜作為人工智能的基礎支撐，例如支撐軌道交通運維優化、系統設計等，目前也得到了許多學者和研究人員的關注。

知識圖譜是一種信息網絡，它包含真實世界中存在的物品、人物、地點等信息。知識圖譜一般用三元組集合來表示，用RDF（resource description framework）或者圖數據庫來存儲三元組。知識圖譜目前已經被廣泛應用在搜索、推薦、問答領域，知識圖譜逐漸成為人工智能領域不可或缺的一部分。學術界對知識圖譜的研究從未間斷過，隨著人工智能的熱潮來臨，研究知識圖譜變得越來越重要。

常見的公開的知識圖譜有Freebase、DBPedia、ConceptNet 等。然而這些知識圖譜都有不同程度的缺失。這些知識圖譜的缺失主要體現在實體與實體之間缺失本應該有關系的邊。知識圖譜補全任務（knowledge graph completion）是致力于通過預測知識圖譜中潛在的關系，從而提高知識圖譜的完整性和可靠性。許多學者對知識圖譜補全任務進行了許多探索和研究，其中包括：（1）路徑排序算法（path ranking algorithm，PRA）[1-5]；（2）詞嵌入技術[6-12]；（3）神經網絡方法[13-18]。這些方法一般將知識圖譜補全任務看作是分類問題，比如路徑排序算法（PRA）的改進——子圖特征提取算法（sub-graph feature extraction，SFE）[2]通過判斷不在知識圖譜中的三元組是否成立，來實現知識圖譜缺失補全。

然而這些方法存在以下兩個問題：（1）這些方法都關注于算法準確率，使用的測試集一般由人工規則進行構建，如果將這些方法應用到真實的知識圖譜上，需要對所有的候選目標進行分類任務，導致龐大的時間開銷。（2）這些方法都只著眼于知識圖譜內部數據的缺失補全，沒有考慮到采用知識圖譜外部數據進行缺失補全，導致利用的信息不充分。這些方法在缺失補全上有這么兩點局限，因此本文提出一種基于主動學習的知識圖譜補全框架，這個框架由三部分構成：不斷更新的知識圖譜、鏈接預測器、關系驗證器。其中鏈接預測器預測知識圖譜中最有可能產生鏈接的k對實體對，關系驗證器推理驗證實體對之間的關系，形成新的三元組完善知識圖譜。

本文的主要貢獻可以概括如下：

（1）提出了一種采用主動學習，使用知識圖譜內部和外部關系驗證，從而不斷完善知識圖譜的框架。這個框架結合了主動學習，能夠不斷完善知識圖譜。

（2）在鏈接預測階段，提出了增強鏈接預測算法（enhance link prediction，ELP）來預測知識圖譜中最有可能形成鏈接的實體對。ELP 算法結合了Rooted PageRank 算法和實體聚類算法，能夠有效挖掘知識圖譜中的圖結構信息和語義信息。利用ELP 算法能夠實現主動學習，從而不斷完善知識圖譜。

（3）在關系驗證階段，提出一種采用基礎驗證加增強驗證的方法驗證關系。實驗表明，這種方法能夠有效利用知識圖譜內部數據和互聯網數據進行關系驗證。

2 相關工作

本文的相關工作主要涉及鏈接預測任務、知識圖譜補全任務、知識庫問答系統、實體抽取、關系抽取等領域。

在知識圖譜補全領域已經有許多學者做出了豐富的研究，Lao 等人[1]提出路徑排序算法（PRA），PRA通過計算知識圖譜中節點間的特征矩陣來實現知識圖譜中的鏈接預測。PRA 算法主要分成兩步：（1）使用統計模型來尋找兩個節點間的潛在路徑。（2）計算任意兩個節點間的隨機游走概率。Gardner 等人[2]在PRA 的基礎上提出了子圖特征提取算法（SFE）。SFE 將知識圖譜補全任務看作是二分類問題，通過判斷三元組是否成立來實現知識圖譜缺失補全。SFE 算法主要分成兩步：（1）提取兩個節點的一系列特征。（2）采用二分類分類器對第一步提取的特征做二分類判別。

Bordes 等人[6]提出了詞嵌入模型TransE。TransE模型將實體和關系映射到低維空間中的向量，通過計算向量間距離h′+r′-t′來實現知識圖譜缺失補全。Wang 等人[7]在TransE 模型的基礎上提出了TransH 模型，TransH 模型將實體映射到關系向量的超平面中，增強向量解釋能力。

Neelakantan 等人[14]提出了Path-RNN 模型來推理兩個節點間的關系。Path-RNN 將兩個節點路徑之間的實體輸入到循環神經網絡（recurrent neural network，RNN）中，來實現實體間的關系推理。Das 等人[15]在Path-RNN 的基礎上提出Single Model，Single Model不僅考慮了節點間路徑上的實體，還考慮了路徑上的關系，增強了神經網絡的表達能力。

在社交網絡領域，許多學者和研究人員對鏈接預測問題進行了許多研究[19-21]。鏈接預測問題主要是從圖中篩選出最有可能形成鏈接的k對節點對。解決鏈接預測問題的方法主要有三類：（1）局部方法；（2）基于路徑的方法；（3）隨機游走方法。其中局部方法有公共鄰居方法、Jaccard 系數等，主要的流程是計算節點對之間的相鄰的節點來實現相似度的計算。基于路徑的方法有最短路徑、Katz 距離等，主要的流程是計算節點對之間的路徑信息來實現相似度的計算。隨機游走的方法有Rooted PageRank 等，主要的流程是通過圖中節點的隨機游走來實現相似度計算。

主動學習[22]是一種機器學習技術，從數據中選擇出具有代表性或者能夠有利于學習模型快速學習的樣本。主動學習解決的問題包含已標注的數據和未標注的數據，主動學習采用算法策略從未標注的數據中選擇一部分最有利于學習模型學習的數據，交由專家系統進行標注，標注后的數據用于學習更好的模型。

知識庫問答系統（knowledge base question answering，KBQA）[23-24]是給定自然語言問題，通過對自然語言問題的語義分析，利用知識庫進行語義查詢、關系推理得到答案。KBQA 主要分以下幾個模塊：問題分析、短語映射、消歧、查詢構建等。KBQA 主要的應用體現在智能問答上，同時也廣泛應用于搜索、推薦等領域。

還有許多學者對開放世界假設下的知識圖譜補全問題進行了深入的研究[25]。開放世界假設指知識圖譜中的關系代表現實世界中正確的關系，知識圖譜中未知的關系可能代表現實世界中錯誤的關系，也可能代表現實世界中存在的關系。開放世界假設對應的是封閉世界假設，封閉世界假設是指知識圖譜中未知的關系代表現實世界錯誤的關系。一般知識圖譜比較完善的時候，或者是知識圖譜不完全，但是由于需要通過知識圖譜對現實世界的問題做出回答時采用封閉世界假設。

3 知識圖譜補全方法框架

本文對知識圖譜作如下定義：知識圖譜由三元組集合O={(h,r,t)}構成。每個三元組都有兩個實體h,t∈E 和關系r∈R，其中E 是實體集合，R 是關系集合。定義,ei∈E,ej∈E 是知識圖譜中的實體對。知識圖譜補全框架的主要流程如圖1 所示，知識圖譜補全框架主要分為鏈接預測和關系驗證兩個模塊。鏈接預測模塊主要是從知識圖譜中篩選出最有可能形成鏈接的k對實體對。關系驗證模塊驗證鏈接預測輸出的實體對之間的關系，形成正確的三元組。形成正確的三元組會返回知識圖譜進行不斷更新迭代。整個知識圖譜補全框架包含了主動學習的思想，鏈接預測模塊從未標注數據中選擇代表性的數據，交由關系驗證模塊進行專家驗證。

Fig.1 Flowsheet of knowledge graph completion圖1 知識圖譜補全流程圖

鏈接預測模塊主要實現篩選知識圖譜中最有可能形成鏈接的k對節點對。鏈接預測模塊以知識圖譜的三元組作為輸入，采用ELP 算法，尋找并篩選整個知識圖譜中最有可能形成鏈接的k對實體對。ELP 算法采用實體聚類算法來挖掘知識圖譜中的語義信息，采用Rooted PageRank 算法來挖掘知識圖譜中的圖結構信息，經過聯合篩選來挖掘知識圖譜中最有可能形成鏈接的k對實體對。鏈接預測模塊輸出實體對，由關系驗證模塊進行進一步的關系確認。關系驗證形成的正確的三元組能夠返回鏈接預測模塊進行進一步的學習，使得鏈接預測模塊能夠更好地預測知識圖譜中能夠形成鏈接的實體對。

關系驗證模塊主要實現對實體對之間的關系的驗證。關系驗證模塊由基礎驗證和增強驗證兩部分構成。基礎驗證采用TransH[7]算法，以知識圖譜內部的數據作為訓練集，對鏈接預測模塊產生的實體對進行分類任務確定實體對間的關系。增強驗證模塊通過爬取、清洗互聯網結構化數據，采用多源數據關系驗證和領域專家的人機交互方式來實現對基礎驗證輸出的三元組集合的進一步驗證。關系驗證模塊輸出正確的三元組，輸出的三元組返回知識圖譜補全完善知識圖譜。正確的三元組還會返回鏈接預測模塊，增強鏈接預測模塊的鏈接預測效果。

4 鏈接預測

鏈接預測模塊主要的任務是從知識圖譜中篩選出前k對最有可能形成鏈接的實體對。本章提出了增強鏈接預測算法（ELP），ELP 算法結合了Rooted PageRank 算法和實體聚類算法進行聯合篩選，使得篩選出的候選實體對更有可能形成鏈接。Rooted PageRank 算法能夠挖掘知識圖譜中的圖結構信息，篩選可能形成鏈接的實體對。而實體聚類算法能夠挖掘知識圖譜中的語義信息，排除不可能形成鏈接的實體對。ELP 中算法中的Rooted PageRank算法和實體聚類算法是相對獨立的兩個子模塊，通過該兩個模塊的聯合篩選，能夠篩選出知識圖譜中最有可能形成鏈接的實體對。由于ELP 算法結合了知識圖譜中的語義信息和圖結構信息，因此ELP 算法信息挖掘能力更強，能夠通過主動學習增強鏈接預測的性能。將在實驗中證明本章提出的ELP 算法效果優于Rooted PageRank 算法，并且具有主動學習能力。本文分知識圖譜實體聚類和Rooted PageRank算法兩部分來介紹ELP 算法。

4.1 實體聚類算法

本節提出一種知識圖譜實體聚類算法來挖掘知識圖譜中的語義信息。在知識圖譜中，節點和邊分別代表實體和關系，節點和邊都是有各自的語義的。本節提出的實體聚類方法能夠快速篩選出知識圖譜中的實體類。篩選出的實體類可以用于ELP 算法的聯合篩選。它主要分成兩個階段：（1）實體類的初始化；（2）實體類的合并。

定義知識圖譜可以看作是有向圖G，其中實體類E 是有向圖G 的節點，三元組o=∈O 可以看成是有向圖G 中從節點h出發到節點t的一條有向邊。定義H={H1,H2,…,H2m}代表頭節點類集合，T={T1,T2,…,T2m}代表尾節點類集合。

對于關系ri∈R，有三元組集合Oi={(hij,ri,tij)}?O，其中hij∈Hi，tij∈Ti。如圖2 所示，頭節點類Hi中的實體hij都有一定的相似性，比如關系-Nationality-對應的頭實體類一般都是人。尾實體類Ti中的實體tij也有一定的相似性，比如關系-Gender-對應的尾實體類一般都是性別。圖2 中的{e1,e2}、{e2,e3}、{e4,e5}、{e6,e7}分別構成4 個實體類{H1,H2,T1,T2}。

Fig.2 Entity class initialization diagram圖2 實體類初始化示意圖

實體類的初始化過程需要遍歷關系集合R，對于每個關系ri∈R，記錄對應的頭實體類Hi和尾實體類Ti。最后得到了2m個初始實體類，該實體類集合記為S={H1,H2,…,H2m,T1,T2,…,T2m} 。值得注意的是，由于知識圖譜包含一些錯誤數據，以及一些關系的頭實體類和尾實體類有一定的重復，因此對于任意的實體e∈E，可能屬于一個或者多個實體類。初始化實體類的流程如下：

算法1初始化實體類

實體聚類算法的第二個階段是合并初始實體類。經過上一步提取的實體類存在很多錯誤，這些錯誤主要體現在以下幾個方面：（1）知識圖譜中可能有些邊是錯誤的，比如大規模的多語言百科知識圖譜DBpedia 有大約10%的錯誤率。知識圖譜中錯誤的三元組可能會導致一些實體類包含少量本不屬于該集合的實體。（2）一些集合之間可能存在大量重復的實體。比如關系-Gender-和關系-Nationality-對應的頭實體類高度相似，這兩個實體類之間存在大量相似的實體。由于實體類初始化提取的實體類存在以上的問題，因此需要對上一步提取的實體類做進一步的處理。實體類的合并過程如圖3 所示，當發現{e1,e2}、{e2,e3}兩個實體類較為相似，這兩個實體類需要被合并，合并完后剩余的實體類有{e1,e2,e3}、{e4,e5}、{e6,e7}三個實體類，記為{H1,T1,T2}。

對于實體類si,sj∈S，count(si)、count(sj)分別代表實體類si和sj中的實體數量。定義兩個集合的相似度：

任意兩個相似度超過閾值τ的實體類需要進行合并，不斷迭代直到沒有兩個實體類相似度超過閾值τ。

由于實體類過程中的每次迭代需要計算兩兩實體類間的相似度，當實體類較多時候，每次迭代需要較大的時間開銷，因此采用貪心策略來加速實體類的合并。實體類的合并算法如下：

（1）隨機選取一個集合，計算其他集合與當前集合的相似度。

（2）選取一個與當前集合相似度最大的集合，如果相似度超過閾值τ，則將這兩個集合進行合并，并將新的集合作為當前集合；如果沒有超過閾值τ，則將當前集合標記為終態，以后不參與集合合并。

（3）重復前兩步直到所有集合都為終態。

算法2實體類的合并

Fig.3 Diagram of entity class consolidation process圖3 實體類合并過程示意圖

4.2 Rooted PageRank 算法

Rooted PageRank 算法[19-20]將知識圖譜看作是無向圖G，其中實體E 是無向圖G的節點，三元組o=∈O 可以看成是無向圖G中從節點h出發到節點t的一條無向邊。介紹Rooted PageRank 算法之前，本節先介紹隨機游走算法（Random Walks）。對于任意節點x∈E，隨機游走算法以等概率游走到和節點x相鄰的節點。定義命中時間Hx,y：從節點x，隨機游走到節點y的期望步長，其中x,y∈E 。那么往返時間Cx,y定義如下：

Rooted PageRank 算法在隨機游走算法的基礎上引入了重啟機制，對于圖G中的任意節點x，每次隨機游走的時候，以α的概率重新回到節點x，以1-α的概率游走到與節點x相鄰的節點。本文定義score(x,y)代表從節點x隨機游走到y的穩定概率。選擇score較高的k個實體對作為知識圖譜中最有可能形成鏈接的實體對。相應的圖計算核方法是(1-α)(I-αD-1A)-1，其中D代表度矩陣，A代表鄰接矩陣。

4.3 ELP 算法

前文所介紹的Rooted PageRank 算法能夠通過知識圖譜的圖結構，從知識圖譜中發現最有可能形成鏈接的k對實體對。而實體聚類算法則是挖掘知識圖譜中的語義信息對知識圖譜中的實體進行聚類。本節將提出ELP 算法，聯合Rooted PageRank算法和實體聚類算法對實體對進行篩選。

在實體聚類算法對知識圖譜中的實體進行聚類后，對于任意兩個實體類Si,Sj∈S，定義三元組集合Oz={(hik,rz,tjk)}?O 并且滿足hik∈Si,tjk∈Sj。定義實體類之間的置信度如下：

如果兩個實體類之間的置信度大于閾值β，則任意兩個實體ei和ej都屬于篩選出的實體候選對。因此，對于實體對,ei∈Si,ej∈Sj，有如下關系：

ELP 算法采用Rooted PageRank 算法和實體聚類算法聯合篩選進行鏈接預測。既考慮了知識圖譜中的圖結構信息，又考慮了知識圖譜的語義信息。通過ELP 算法篩選出的最有可能形成鏈接的k對實體對更具有代表性，可獲得優于Rooted PageRank 算法的效果。

另外，ELP 算法具有主動學習能力。對于鏈接預測問題，將整個知識圖譜看作是數據集Ud，所有在知識圖譜中有鏈接的數據看作是訓練集Us，所有不在知識圖譜中的鏈接看作是測試集Ut。ELP 算法每次從測試集Ut選出一定數量的樣本，通過關系驗證模塊組合成正確的三元組加入訓練集Us，組成新的訓練集Us′和新的測試集Ut′。在實驗環節，驗證了對于新的訓練集Us′，ELP 算法的鏈接預測效果比原訓練集Us要好。這說明ELP 算法具有主動學習能力，對于更完善的數據集，ELP 算法有更強的潛在信息挖掘能力。

5 關系驗證

關系驗證模塊驗證鏈接預測輸出的實體對的關系。對于鏈接預測輸出的任一實體對，關系驗證模塊需要找到對應正確的三元組，如果不存在關系，則有r=NULL。本章采用基礎驗證和增強驗證兩個模塊解決關系驗證問題。在基礎驗證模塊中，將關系驗證問題看作是關系分類問題，采用TransH 算法對鏈接預測模塊輸出的實體對進行分類任務。在增強驗證模塊，通過爬蟲技術爬取互聯網上結構化數據信息，采用多源數據關系驗證和領域專家人機交互方式來實現增強驗證。

5.1 基礎驗證

在基礎驗證模塊，本節只利用知識圖譜內部的數據，將關系驗證看作是分類問題。對于任一實體對，需要對所有r∈R 做二分類判別。即是對于所有的r∈R，判斷三元組是否成立。關系驗證也可以看成是多分類任務，即對于實體對，分類選擇出正確的關系r，形成正確的三元組。

Bordes 等人[6]提出詞嵌入模型TransE，TransE 模型將知識圖譜中的實體和關系都用數學空間的向量來表示。因此，對于三元組，可以通過計算頭實體h和尾實體t的向量距離來實現關系驗證。圖4展現了三元組在數學空間中的關系。

Fig.4 Math space of TransE圖4 TransE 模型數學空間

對于知識圖譜中的三元組O={(h,r,t)}，其中h,t∈E,r∈R，TransE 模型將實體和關系映射到數學空間Rk中，其中k是模型的超參數。定義知識圖譜中的正確的三元組集合為S(h,r,t)，錯誤的三元組集合為S′(h′,r,t′)，其中S′(h′,r,t′)可以隨機替換知識圖譜中正確的三元組的頭實體和尾實體來得到。有如下等式:

其中，γ是超參數。實體向量和關系向量可以通過訓練目標函數L來得到。

Wang等人[7]在TransE模型的基礎上提出了TransH模型，TransH 模型在TransE 模型的基礎上把實體向量和關系向量映射到超平面空間wr。圖5 展現了TransH 模型中的三元組在數學空間中的關系。TransH 模型的距離函數和目標函數如下定義：

Fig.5 Math space of TransH圖5 TransH 模型數學空間

模型訓練開始時，一般用隨機值來初始化實體向量和關系向量。在訓練過程中，為了節省計算資源以及加快訓練速度，研究人員往往采用隨機梯度下降方法SGD（stochastic gradient descent）來實現模型的訓練，采用L2正則化方法來避免模型對訓練數據的過擬合。

5.2 增強驗證

通過基礎驗證后的三元組仍存在許多錯誤，造成這些錯誤的原因主要是基礎驗證只利用了知識圖譜內部的數據信息，然而現實世界中大多數知識圖譜包含的知識信息較為有限。隨著互聯網的進一步發展，諸如百度百科、互動百科、維基百科等包含了大量的知識信息。因此，本文提出利用外部數據進行增強驗證，增強驗證模塊包括三部分：（1）多源數據的采集與清洗；（2）多源數據的關系驗證；（3）領域專家的人機交互驗證。

定義多源數據S={S1,S2,…,Sn}表示不同數據源的數據，數據倉庫KB={KB1,KB2,…,KBn}表示多源數據S經過爬蟲技術采集、數據清洗、數據格式規范化后的數據。對于任意數據倉庫KBi都符合以下形式：

其中，Ei={ei1,ei2,…,eim}代表數據倉庫KBi中的實體集合，Ri={ri1,ri2,…,rim}代表數據倉庫KBi中的關系集合，Oi代表數據倉庫KBi中的三元組集合。增強驗證模塊如圖6。

數據采集部分采用網絡爬蟲技術對互聯網上的網站進行數據爬取。許多網站針對開發者開放了API接口與Dump 文件等。互聯網上的數據如圖7 所示，一般由文本數據和結構化Infobox 數據構成。增強驗證模塊主要采用互聯網的結構化數據進行關系驗證。

Fig.6 Flowsheet of enhanced verification圖6 增強驗證流程圖

Fig.7 Diagram of Wiki Web page圖7 Wiki網頁數據示意圖

爬取后的數據需要進行數據清洗和格式規范化，包含以下幾點：（1）剔除無關字符。（2）關系統一化。在不同數據源中，關系描述可能不一致，因此需要將同一關系的不同描述統一化。（3）實體消歧與統一化。在不同數據源中，實體的描述可能并不一致，可能出現縮寫名等，因此需要對實體進行統一化。經過清洗與規范化后的數據會存入數據倉庫中，進行多源數據關系驗證。

多源數據關系驗證以基礎驗證輸出的三元組集合Op、知識圖譜G和數據倉庫KB為輸入，輸出置信度集合Cp。對于任意三元組o=∈Op，與數據倉庫KBi進行數據對齊需要考慮如下兩點：（1）實體h在知識圖譜G中描述的實體和在數據倉庫KBi中描述的實體是不是同一個實體。（2）數據倉庫KBi是否存在三元組o=。

式（10）描述了三元組關系o與數據倉庫KBi之間的對應關系。

式（11）描述了三元組o與數據倉庫KBi之間置信度。其中VG表示知識圖譜G中包含實體h的三元組集合，VKBi表示在數據倉庫KBi中包含實體h的三元組集合。因此對于三元組o，總的置信度有如下公式：

多源數據關系驗證輸出三元組集合和置信度，經過領域專家人機交互驗證后可以輸出正確的三元組集合。對于置信度較低的三元組，領域專家依靠自身的專業知識來決定三元組是否正確。領域專家人機交互驗證的形式化定義如下：

本節提出的增強驗證包含多源數據采集與清洗、多源關系驗證、領域專家人機交互驗證三部分。增強驗證模塊能夠有效地驗證基礎驗證輸出的三元組集合，形成更加正確的三元組集合。

6 實驗結果

本文的實驗環境是在一臺小型服務器上運行，處理器為Intel?Xeon?Silver 4114 CPU@2.2 GHz，內存為100 GB，操作系統為Ubuntu 18.04.1 LTS Server。使用的語言為Java 和Python，Python 主要用于鏈接預測模塊篩選實體對，Java 主要用于關系驗證模塊驗證實體對的關系。

實驗數據方面，本文采用公開數據集Freebase 和DBpedia。Freebase 數據集和DBpedia 是在知識圖譜領域常用的數據集，被許多科研學者采用。由于Freebase 數據集和DBpea 數據集非常龐大，為了方便起見，本文對Freebase 數據pedia 數據集進行了采樣，選取了一定數量的實體、關系作為實驗的真值數據集。真值數據集如表1 所示。

Table 1 Truth dataset表1 真值數據集

從真值數據集隨機采樣55%、60%、65%、70%、75%、80%、85%、85%、90%、95%的三元組，構成本文的缺失知識圖譜。剩余的三元組作為需要補全完善的缺失值。

6.1 鏈接預測實驗結果

在鏈接預測模塊中，測試了Rooted PageRank（RPR）算法和ELP 算法篩選缺失的知識圖譜中最有可能形成鏈接的前1 000 和前2 000 對實體對，并將篩選出的實體對和真值數據集進行比較，計算出正確預測的實體對百分比。篩選前1 000 對實體對和前2 000 對實體對的結果如表2 所示。圖8 和圖9 表現了在DBpedia 數據集上和Freebase 數據集上的實驗對比。

從圖8 和圖9 中分析發現在DBpedia 和Freebase兩個數據集上，ELP 算法效果均好于RPR 算法。對于前2 000 對實體對，應用了CommonNeighbours、Katz、SimRank 算法[19]進行對比測試。實驗結果如表3 所示。可以看到在DBpedia 和Freebase 數據集上，ELP 算法效果均優于其他算法。這兩個實驗證明了本文提出的ELP 算法的有效性，說明本文算法相較于其他算法而言，能較為準確地篩選知識圖譜中最有可能形成鏈接的前k對實體對。

ELP 算法不僅能夠很好地進行鏈接預測，還具有主動學習能力，隨著知識圖譜的不斷完善，ELP 算法能夠更好地預測知識圖譜中需要進行鏈接的實體對。然而由于知識圖譜越來越完善的同時，需要補全的正確三元組越來越少，用前k對實體對中正確的實體對百分比來評價鏈接預測的主動學習能力并不公平。定義了如下函數來評價在知識圖譜更新過程中算法的鏈接預測能力。

Table 2 Accuracy comparison of RPR and ELP表2 RPR 與ELP 準確率對比

Fig.8 Experiment comparison between RPR and ELP in DBpedia圖8 DBpedia 數據集RPR 與ELP 實驗對比

Fig.9 Experiment comparison between RPR and ELP in Freebase圖9 Freebase數據集RPR 與ELP 實驗對比

Table 3 Accuracy comparison of ELP algorithm and others@2 000表3 ELP 算法與其他算法準確率對比結果@2 000

其中，Dt表示當前知識圖譜剩余還未補全的正確實體對總數，hit代表鏈接預測器篩選出的前k對實體對中正確的實體對個數。相比較于前k對實體對中正確實體對的百分比，Yscore考慮了知識圖譜中剩余還未補全的實體對總數，能較好地評價算法的主動學習的能力。本文在DBpedia 數據集和Freebase 數據集上測試了各個算法的實驗結果，如表4 所示。通過圖10 和圖11 可以看出，隨著知識圖譜的不斷完善，Yscore結果變得越來越高。這說明了隨著知識圖譜的不斷完善，ELP 算法的鏈接預測能力越來越強。因此，ELP 算法具有主動學習能力。

以上的實驗以及分析驗證了如下兩點：（1）本文提出的ELP 算法能夠挖掘知識圖譜中的圖結構信息和語義信息，效果好于Rooted PageRank 算法。（2）本文提出的ELP 算法具有主動學習能力，隨著知識圖譜的完善程度越高，ELP 算法的信息挖掘能力越強。

6.2 關系驗證實驗結果

關系驗證模塊采用TransH 模型對鏈接預測模塊輸出的候選實體對進行關系驗證。首先對ELP 算法鏈接預測得到的前k對實體對進行關系擴展，對于鏈接預測輸出中的正確的實體對，需要擴展正確的關系；對于鏈接預測輸出中的錯誤的實體對，則隨機擴展知識圖譜中的任一關系。

對于鏈接預測模塊輸出的前1 000 對實體對和前2 000 對實體對，基礎驗證模塊采用TransH 模型進行二分類。基礎驗證模塊將預測的結果和真值數據集進行比較，并計算F1值。F1值的計算方式如下:

其中，P代表精確率，R代表召回率。F1指標能較好地衡量二分類分類器的性能。關系驗證的結果如表5 所示。

Table 4 Yscore results of active learning in link prediction module表4 鏈接預測模塊主動學習Yscore 結果

Fig.10 Yscore results of ELP algorithm in DBpedia圖10 DBpedia 數據集ELP 算法Yscore 結果

Fig.11 Yscore results of ELP algorithm in Freebase圖11 Freebase數據集ELP 算法Yscore 結果圖

Table 5 F1 results of relationship verification表5 關系驗證F1 指標實驗結果

表5 證明了基礎驗證模塊能夠較好地驗證鏈接預測輸出的實體對之間的關系，基礎驗證模塊的F1指標都集中在0.5～0.8 之間。

爬取Freebase 有關的實體75 043 個，以及它們有關聯的三元組集合。然后以0.25 的概率采樣其中的三元組集合，構建了5 個與Freebase 有關的多源數據倉庫。同樣地，爬取了與DBpedia 有關的實體14 656個，以及與它們有關聯的三元組集合。然后以0.3 的概率采樣其中的三元組集合，構建了5 個與DBpedia有關的多源數據倉庫。基礎驗證標記為正確的三元組將作為多源數據關系驗證的輸入，計算對應的F1指標，結果如表6 所示。從實驗結果可以看出采用較為正確的數據源進行多源關系驗證，能得到較好的效果。

對于多源關系驗證中置信度較低的三元組，增強驗證模塊采用領域專家人機驗證進一步確定三元組關系，可以得到正確的三元組。經過增強驗證后的三元組較為正確，最后采用正確的三元組更新知識圖譜。

6.3 各環節時間實驗結果

本文測試了本文提出的基于主動學習的知識圖譜補全框架的各個環節的時間消耗。框架包含四個環節：（1）實體聚類算法；（2）RPR 算法；（3）ELP 算法；（4）TransH 模型訓練。結果如表7 所示，從表7 中可以看出主要時間開銷在關系驗證模塊中，鏈接預測模塊的時間開銷相對不高。而本文提出的對于知識圖譜實體聚類方法的時間開銷相對于RPR 算法要小很多。總的ELP 算法的時間開銷相對占比不大。

7 結論

本文提出了一種基于主動學習的知識圖譜補全框架來實現對缺失知識圖譜的不斷更新完善。知識圖譜補全框架由不斷更新的知識圖譜、鏈接預測模塊、關系驗證模塊構成。在鏈接預測模塊中，提出的ELP 算法充分考慮了知識圖譜中的語義信息和圖結構信息，能準確實現對知識圖譜的鏈接預測，同時ELP 算法具有主動學習能力，能隨著知識圖譜的不斷完善，可以更好地進行鏈接預測。在實驗中，通過與前人的RPR、SimRank、CommonNeighbours、Katz 等方法進行對比，證明了ELP 算法的有效性。同時，也通過實驗證明了ELP 算法的主動學習能力。關系驗證模塊采用基礎驗證和增強驗證相結合的方法進行關系驗證，這種關系驗證方式能夠結合知識圖譜內部數據和互聯網結構化數據，以及領域專家人機交互標注，能夠驗證三元組的正確性。通過實驗驗證了關系驗證模塊的有效性。關系驗證模塊能驗證鏈接預測模塊輸出的實體對之間的關系，形成正確的三元組，從而更新知識圖譜。

Table 6 F1 results of multi-source data relationship verification表6 多源數據關系驗證F1 實驗結果

Table 7 Time comparison of each step表7 各環節時間對比