基于互信息的知識圖譜實體關聯(lián)關系建模與補全*

夏 維，王珊蕾，尹子都，岳 昆

云南大學 信息學院，昆明 650500

1 引言

隨著Linking Open Data等項目的全面展開，語義Web數(shù)據(jù)源的數(shù)量劇增，大量RDF（resource description framework）數(shù)據(jù)被發(fā)布，互聯(lián)網(wǎng)正從僅包含網(wǎng)頁和網(wǎng)頁之間超鏈接的文檔萬維網(wǎng)（document Web）轉變成包含大量描述各種實體和實體之間豐富關系的數(shù)據(jù)萬維網(wǎng)（data Web）。在這一背景下，互聯(lián)網(wǎng)公司逐步開始以此為基礎構建知識圖譜（knowledge graph，KG）[1-2]。KG為海量數(shù)據(jù)和領域知識提供了一種非常有效的組織方式，是一種結構化的語義知識庫，如YAGO 的 YAGOKB[3]、DBpedia的 DBpediaKB[4]等。借助KG，人們可以從過去單一的網(wǎng)頁鏈接轉向實體鏈接；基于KG的搜索引擎，通過圖結構反饋知識，幫助用戶簡單精確地實現(xiàn)知識的獲取和定位，從而實現(xiàn)真正意義上的語義搜索。近年來，國際上主流的互聯(lián)網(wǎng)公司或研究機構都加入到KG的研究中，研究人員在KG的構建[5]、表示學習[6-7]和補全（completion）[8-9]等方面開展了大量的研究。

KG是一種節(jié)點和邊組成的圖結構，其中節(jié)點表示相應的實體，邊表示實體之間的關系。因為KG中節(jié)點之間的關聯(lián)關系能夠更好地完善搜索結果，服務用戶，所以KG的完備性和準確性尤為重要。雖然當前知識庫數(shù)量不斷增多，規(guī)模不斷擴大，但是仍然有許多知識庫并不完整，例如Google Knowledge Vault[7]項目核心元素Freebase[10]中71%的個人信息缺失“出生地”，75%的個人信息缺失“國籍說明”，這使得KG的補全具有重要的實際意義。

針對圖1中描述用戶瀏覽商品相關信息的KG，補全就是判斷和添加圖1中虛線部分商品節(jié)點之間缺失的關系。

Fig.1 Knowledge graph of users'browsing on commodities圖1 用戶瀏覽商品KG

針對KG補全，目前國內外學者開展了許多系統(tǒng)性的研究。例如，Liu等人[2]綜述了KG中通過實體間關系抽取來補全KG的相關概念和研究領域，介紹了關系抽取的經(jīng)典模型，大多數(shù)KG補全的方法都是以表示學習和知識推理為基礎。其中，從表示學習方面，Zhang等人[11]提出一種實體間相似性度量標準，以及利用實體間常見語義模式來估計三元組間是否存在關系的方法；Minervini等人[12]提出一種統(tǒng)一的方法，利用潛在因素模型（latent factor model）中包括實體類別與子類關系的附加模式知識，實現(xiàn)KG中缺失鏈接的預測。這些方法僅僅以已有的KG中的知識為基礎進行關系抽取，忽略了KG中錯誤的鏈接，從而導致實體間關系預測錯誤。從知識推理方面，Lao等人[13]提出一種基于路徑的知識推理方法，將每種不同的關系路徑作為一維特征，通過統(tǒng)計KG中大量的關系路徑來構建關系分類的特征向量，建立關系分類器進行關系抽?。籊ardner等人[14]在大規(guī)模語料庫上標記潛在特征的邊，旨在提升基于路徑排名算法KG補全準確率。但是，KG中比較稀疏且連通性較差的實體關系不利于關系的抽取，很難有效地補全KG中節(jié)點間的缺失關系。

事實上，隨著社交網(wǎng)絡的普及和廣泛應用，用戶行為記錄依托多種媒介快速產生，即使對于同一實體集，用戶行為中體現(xiàn)出來的實體間的關聯(lián)關系，仍有可能與KG中的描述并不相同。也就是說，KG和用戶行為記錄，分別從領域知識庫和用戶生成數(shù)據(jù)（user-generated data，UGD）這兩方面描述了實體間的關聯(lián)關系。從用戶行為記錄產生和KG構建的角度看，急劇增長的數(shù)據(jù)中所蘊含的知識，也是KG所描述領域知識的有益補充。分析UGD中實體間的關聯(lián)關系，既可以修正KG中單一的實體間錯誤的關聯(lián)關系，又可克服KG中因為節(jié)點間關系稀疏性和連通性差而使得所抽取關系不準確的問題。因此，在UGD中找出實體節(jié)點間的關聯(lián)關系，對KG進行補全，在一定程度上可保證實體間關聯(lián)關系的可靠性和完整性。為了有效實現(xiàn)KG補全，本文需要解決如下問題：

（1）如何從UGD中發(fā)現(xiàn)實體間存在的關聯(lián)關系。

（2）如何有效、準確地利用UGD中實體間的關聯(lián)關系來完成KG補全。

互信息被廣泛應用于文本信息處理等領域[15]，常用于描述兩個變量之間的關聯(lián)程度。UGD中實體之間的關系具有不確定性和依賴性，相比關聯(lián)規(guī)則等度量方法，互信息更能表示不確定信息之間的依賴關系。本文以互信息作為計算UGD中實體間關聯(lián)關系的基礎，從而根據(jù)“實體—關聯(lián)度—實體”三元組的形式構建實體關聯(lián)圖（entity association graph,EAG）。針對海量的UGD，傳統(tǒng)的集中式計算平臺難以處理海量數(shù)據(jù)，Spark分布式計算架構是高效處理海量數(shù)據(jù)的典型代表[16]，其中的GraphX框架為EAG中海量節(jié)點的圖結構操作提供了有效的支持。本文以Spark作為計算框架，在Spark之上實現(xiàn)EAG的構建和KG補全的算法。

在EAG結構中，相鄰實體節(jié)點間一般具有共同的屬性，因此可以從實體節(jié)點的相鄰實體節(jié)點出發(fā)，來判斷實體間是否存在潛在的關聯(lián)關系。例如，通過實體節(jié)點“鼠標”分別與“鍵盤”和“電腦”之間的關聯(lián)，來判斷“鍵盤”和“電腦”之間是否存在潛在關聯(lián)關系。本文將一個實體節(jié)點與相鄰實體節(jié)點之間的關聯(lián)關系看作為一種影響（influence），一個實體節(jié)點與兩個互不相鄰的實體節(jié)點均相鄰，則將一個實體節(jié)點對這兩個互不相鄰的實體節(jié)點的影響綜合起來表示這兩個實體節(jié)點之間的關聯(lián)影響。文獻[17]給出了一種計算多個因素聯(lián)合影響的方法，本文基于此給出一種關聯(lián)影響疊加（superposition）的方法，從而計算實體節(jié)點之間的關聯(lián)影響值。兩個實體節(jié)點之間可能存在多個與這兩個實體節(jié)點均相鄰的實體節(jié)點，因此可能存在多個關聯(lián)影響值。為了有效估計實體節(jié)點間的關聯(lián)度，本文將多個關聯(lián)影響值再次疊加，從而得到這兩個實體節(jié)點之間的綜合關聯(lián)值，進而判斷這兩個實體節(jié)點之間是否存在潛在關聯(lián)關系。在淘寶網(wǎng)真實數(shù)據(jù)[18]上進行了實驗，驗證了本文方法的高效性和有效性。

2 基于互信息的實體節(jié)點關聯(lián)模型構建

在電子商務背景下，UGD是用戶瀏覽網(wǎng)頁或者購買商品等行為產生的記錄，將網(wǎng)頁或者商品作為實體，一條行為記錄表示一個用戶對某種實體的行為。用U={u1,u2,…,um}表示用戶集合，O={o1,o2,…,om}表示實體節(jié)點集合，B={1,2,…,h}表示用戶行為集合，集合B中的元素代表“瀏覽”、“購買”或“收藏”等行為，一條用戶行為記錄表示為{u,o,b}，其中u∈U,o∈O,b∈B。表1給出了一個UGD片段。

Table 1 Fragment of UGD表1 UGD片段

下面給出KG的定義，作為后續(xù)討論的基礎。

定義1（KG）用GK=(VK,EK)表示KG，其中VK={v1,v2,…,vy}為實體節(jié)點的集合，EK={e1,e2,…,el}(l≥1)為實體之間邊的集合。任意一條邊el=(vi,vj)，vi,vj∈EK，i≠j且1≤i,j≤r，節(jié)點vi稱為始點，節(jié)點vj稱為終點，節(jié)點vi和vj之間的關系由標簽（label）表示。

UGD中實體節(jié)點間的關系可以作為KG中實體節(jié)點間缺失關系的有益補充，下面給出實體節(jié)點關聯(lián)模型的定義，用以表示UGD中實體節(jié)點集合中不同實體之間的關聯(lián)關系。

定義2（實體節(jié)點關聯(lián)模型）M=(O,I,ε)稱為UGD中實體節(jié)點關聯(lián)模型，其中O={o1,o2,…,on}表示UGD中實體節(jié)點的集合，且O≠VK，O?VK≠?，I表示實體節(jié)點之間的關聯(lián)值，其中0≤I≤1，ε表示給定的關聯(lián)閾值，0≤ε≤1。

2.1 基于互信息的實體節(jié)點關聯(lián)關系度量

互信息[19]的定義如式（1），是實體間關聯(lián)關系度量的基礎。

定義3（互信息）對于O中任意的兩個實體節(jié)點op和oq(p≠q)，0≤p,q≤n，它們之間的關聯(lián)值定義為：

為了方便計算，對式（2）做如下等價變化：

其中，0≤I(op,oq)≤ 1；P(op,oq)表示O中op和oq的聯(lián)合概率；P(op)和P(oq)分別表示O中op和oq的概率。

其中，N(op,oq)表示在用戶行為記錄中出現(xiàn)實體節(jié)點op或oq的用戶行為記錄條數(shù)；N(op)表示出現(xiàn)op的條數(shù)；N總表示總的用戶行為記錄條數(shù)。以表1中的UGD片段為例，(o1,o2)同時出現(xiàn)的次數(shù)為1，o1和o3同時出現(xiàn)的次數(shù)為0，o2和o3同時出現(xiàn)的次數(shù)為1，因此N(o1,o2)=3，P(o1,o2)=0.75。可見，兩個實體節(jié)點op和oq同時出現(xiàn)的概率越大，I(op,oq)越大，op和oq之間的關聯(lián)關系就越強。給定閾值ε，若節(jié)點之間關聯(lián)度不小于ε，則節(jié)點之間的邊真實存在。

2.2 EAG的構建

基于前述方法，可以得到實體節(jié)點之間的關聯(lián)關系，下面給出EAG的定義。

定義4（EAG）用G=(O,A)表示實體節(jié)點關聯(lián)圖（EAG），其中O={o1,o2,…,on}為實體節(jié)點集合，A={a1,a2,…,as}表示EAG中邊的集合。若O中任意兩個實體節(jié)點ox和oy(1≤x,y≤n,x≠y)有邊相連，則表示ox和oy之間存在關聯(lián)關系。

EAG中相互關聯(lián)的實體節(jié)點之間存在相互影響，一個實體節(jié)點的出現(xiàn)必然會影響另一個實體節(jié)點的出現(xiàn)，另一個節(jié)點的出現(xiàn)也會影響該節(jié)點的出現(xiàn)，但影響的程度往往并不相同，因此實體節(jié)點關聯(lián)關系具有方向性。例如，顧客購買電腦的同時可能也會購買鍵盤。借鑒文獻[20]中的判斷方法，采用式（6）來判定關聯(lián)的方向，其中e(ox→oy)表示關聯(lián)關系方向由實體節(jié)點ox指向實體節(jié)點oy，e(ox←oy)表示關聯(lián)方向由實體節(jié)點oy指向實體節(jié)點ox。假設ox的出現(xiàn)次數(shù)表示為|Mx|，oy的出現(xiàn)次數(shù)表示為|My|，ox和oy出現(xiàn)的次數(shù)用集合表示為|Mx?My|，則有：

針對UGD中大量的實體節(jié)點，以Spark作為編程模型，使用式（3）來衡量兩個實體節(jié)點之間的關聯(lián)程度。首先統(tǒng)計UGD中每個實體節(jié)點出現(xiàn)的次數(shù)，以＜key,value>對形式表示，其中key表示實體節(jié)點，value表示實體節(jié)點出現(xiàn)的次數(shù)；然后對每個實體節(jié)點進行Map操作，統(tǒng)計實體節(jié)點中每對實體節(jié)點的出現(xiàn)次數(shù)。

算法1實體節(jié)點關聯(lián)模型

算法1中，構建EAG模型的時間開銷主要取決于任意兩個實體節(jié)點之間的組合。若EAG中有n個實體節(jié)點，步驟4、步驟5的執(zhí)行時間遠小于O(n2)，步驟7、步驟8和步驟9的執(zhí)行時間為O(n2)，因此算法1的時間復雜度為O(n2)。針對實際中規(guī)模較大的UGD，下文進一步通過實驗來測試算法的有效性。

例1以用戶瀏覽商品為例，若UGD中包含1 000條用戶行為記錄，由算法1的步驟5得到N(“鼠標”)=325，N(“鍵盤”)=400，由步驟6得到 N(“鼠標”,“鍵盤”)=187 ，則根據(jù)上述式（2）、（3）、（4）、（5）、（6）得到0.71>0.58，因此“鼠標”和“鍵盤”之間邊的方向為“鼠標”?“鍵盤”。同理可計算出其他實體節(jié)點間的關聯(lián)度以及它們之間邊的方向，如圖2所示。

Fig.2 EAG of commodities圖2 商品EAG

3 KG的補全

若GK中實體節(jié)點間缺失的邊在G中真實存在，則把這條邊添加到GK中；若GK中實體節(jié)點間缺失的邊在G中不存在，則把這樣的節(jié)點之間的關聯(lián)稱為潛在關聯(lián)，進而通過判斷潛在關聯(lián)的強弱來確定這兩個節(jié)點之間是否需要添加邊。

3.1 實體節(jié)點間潛在的關聯(lián)關系度量

G中一個實體節(jié)點op均與兩個不相鄰的實體節(jié)點oq和oz相鄰，且它們之間的關聯(lián)值分別記為I(op,oq)和I(op,oz)。在實際情形中，一個實體節(jié)點與兩個不相鄰的實體節(jié)點之間關聯(lián)值越高，且關聯(lián)值越接近，則這兩個不相鄰的實體節(jié)點之間的潛在關聯(lián)關系越高，反之，則越低。本文綜合考慮一個實體節(jié)點對兩個不相鄰的實體節(jié)點之間產生的關聯(lián)影響，引入“疊加”的概念[18]。將該實體節(jié)點對兩個不相鄰的實體節(jié)點之間的影響而產生的關聯(lián)影響值記為I(op,oq)⊕I(op,oz)，且疊加算子⊕應滿足：

（1）有界性，0≤ I(op,oq)⊕I(op,oz)≤ 1，這保證了多個關聯(lián)值可以通過兩兩疊加來實現(xiàn)。

（2）交換律，I(op,oq)⊕I(op,oz)=I(op,oz)⊕I(op,oq)，這保證了一個實體節(jié)點對兩個不相鄰的實體節(jié)點之間的潛在關聯(lián)的影響是一個不變的值。

基于上述思路，下面給出不相鄰實體節(jié)點之間潛在關聯(lián)關系的定義。

定義5（關聯(lián)影響）在O中存在任意3個實體節(jié)點 ob、oc和 od，ob分別與 oc和 od相鄰，oc與 od不相鄰，其中ob和oc之間的關聯(lián)度為I(ob,oc)，ob和od之間的關聯(lián)度為 I(ob,od)，且有 ε≤ I(ob,oc),I(ob,od)≤ 1，0≤b,c,d≤ n，b≠ c，b≠ d且 c≠ d，則 oc和 od之間的潛在關聯(lián)關系受實體節(jié)點ob的影響而產生的關聯(lián)影響為：

可見，如果式（7）中I(ob,oc)和I(ob,od)越大且越接近，則I(oc,od)就越大，反之則越小。

3.2 關聯(lián)影響值的疊加

G中的實體節(jié)點數(shù)多，且結構復雜，但是可能存在多個實體節(jié)點與兩個不相鄰的實體節(jié)點均相鄰，因此這兩個不相鄰的實體節(jié)點可能有多個關聯(lián)影響值?；谏鲜鏊枷耄槍蓪嶓w節(jié)點間存在多個關聯(lián)影響值的情況，下面給出對多個關聯(lián)影響值進行疊加的方法，從而得到不相鄰實體節(jié)點間的綜合關聯(lián)值，定義如下。

定義6（綜合關聯(lián)值度量函數(shù)）不相鄰實體節(jié)點oc和od之間有多個關聯(lián)影響值I1(oc,od),I2(oc,od),…,Iz(oc,od)，其中z為oc和od共同的鄰居實體節(jié)點的個數(shù)，則oc和od的綜合關聯(lián)值度量函數(shù) f定義如下：

若 f(I1(oc,od),I2(oc,od),…,Iz(oc,od))≥ ε(0≤ ε≤ 1)，則認為這兩個實體節(jié)點間存在強的潛在關聯(lián)，需要在這兩個實體節(jié)點之間添加一條邊。

GK中實體節(jié)點間缺失的邊，如果在G中存在，則將該邊補全到GK中，本文統(tǒng)一給商品和商品之間添加“influence”的標簽，進而實現(xiàn)KG中實體節(jié)點間缺失關系的補全。上述思想見算法2。

算法2KG補全

算法2中，若UGD中包含n個實體節(jié)點，步驟4、步驟5的執(zhí)行時間為O(n2)，步驟10的執(zhí)行次數(shù)遠小于O(n2)，而算法2的主要時間開銷是尋找相鄰實體節(jié)點的三元組，即為步驟4和步驟5，因此算法2執(zhí)行時間為O(n2)。針對大規(guī)模KG，算法2的實際執(zhí)行性能將通過實驗進一步測試。

例2圖2中不相鄰的實體節(jié)點“電腦”和“鍵盤”間存在“鼠標”和“手機”，且“鼠標”和“手機”都與“電腦”和“鍵盤”相鄰，根據(jù)式（7）可計算出“電腦”和“鍵盤”之間的關聯(lián)受“鼠標”的影響，且產生的關聯(lián)影響值為0.56。同理，基于“手機”對相鄰的“電腦”和“鍵盤”之間關聯(lián)關系的影響，其間的關聯(lián)影響值為0.52。再由式（8）得到“電腦”和“鍵盤”的綜合關聯(lián)值為0.54。若δ=0.52，由于0.54>0.52，因此在實體節(jié)點“電腦”和“鍵盤”之間添加一條邊。

4 實驗結果

為了測試本文提出方法的有效性，采用淘寶網(wǎng)真實用戶行為記錄作為實驗數(shù)據(jù)集[17]，包含2 000個用戶、350 889件商品和1 048 576條用戶行為記錄，格式為user_id::item_id::behavior_ty。實驗環(huán)境如下：1臺主頻為3.3 GHz的4核CPU、內存16 GB的計算機作為Master節(jié)點，9臺主頻為3.3 GHz的8核CPU、內存16 GB的計算機作為Worker節(jié)點，構建了Spark分布式計算平臺。本文測試了構建EAG的效率、加速比和并行效率以及KG補全的有效性。

4.1 EAG的構建效率

為了測試構建EAG的效率，本文隨機選取了淘寶數(shù)據(jù)集中的2.5×105、5.0×105、7.5×105和10.0×105條用戶行為記錄數(shù)據(jù)，并分別測試了Worker數(shù)量為3、6和9情形下算法1的執(zhí)行時間和加速比。由圖3可見，隨著數(shù)據(jù)規(guī)模的增大，不同Worker數(shù)量下的執(zhí)行時間均增大。

Fig.3 Time of EAG construction圖3 構建EAG的時間

并行算法的加速比是單個節(jié)點情況下執(zhí)行時間與多節(jié)點情形下執(zhí)行時間的比值。圖4給出了隨著數(shù)據(jù)規(guī)模增大，不同Worker數(shù)量情形下算法1的加速比。圖5給出了隨著Worker數(shù)量增加，不同數(shù)據(jù)規(guī)模情形下算法1的加速比。可以看出，隨著數(shù)據(jù)規(guī)模的增大，Worker數(shù)量越多，加速比增加越快。但在數(shù)據(jù)為5.0×105和7.5×105情形下，6個Worker和9個Worker時的加速比增加明顯，因為在隨機選取的5.0×105和7.5×105條用戶行為記錄中，商品節(jié)點數(shù)量趨近于商品總數(shù)，多個Worker處理商品節(jié)點的優(yōu)勢較顯著。

Fig.4 Speedup ratio ofAlgorithm 1 with various scales of data sets圖4 不同數(shù)據(jù)集規(guī)模情形下算法1的加速比

Fig.5 Speedup ratio ofAlgorithm 1 with various numbers of Workers圖5 不同Worker數(shù)量情形下算法1加速比

Fig.6 Parallel efficiency ofAlgorithm 1 with various numbers of Workers圖6 不同Worker數(shù)量情形下算法1并行效率

并行算法的并行效率是加速比與節(jié)點數(shù)的比值，圖6給出了隨著Worker數(shù)量增加，不同數(shù)據(jù)規(guī)模算法1的并行效率。可以看出，隨著Worker數(shù)量的增加，不同數(shù)據(jù)規(guī)模的并行效率都降低。圖7給出了隨著數(shù)據(jù)規(guī)模的增加，不同Worker數(shù)量情形下的并行效率?？梢钥闯?，隨著數(shù)據(jù)規(guī)模的增加，不同Worker數(shù)量的并行效率都增加，且同一Worker數(shù)量時，數(shù)據(jù)規(guī)模越大，并行效率越高。這說明算法1對于大規(guī)模數(shù)據(jù)具有良好的可擴展性。

Fig.7 Parallel efficiency ofAlgorithm 1 with various scales of data sets圖7 不同數(shù)據(jù)集規(guī)模情形下算法1并行效率

4.2 KG補全的有效性

為了測試本文從UGD中得到的實體節(jié)點之間的關系補全KG的有效性，首先假設UGD中實體節(jié)點間的關聯(lián)關系是真實、正確的，并以之作為補全KG的基礎。為了保證實體節(jié)點間的關聯(lián)具有一定的可靠性，從數(shù)據(jù)集中隨機選取該數(shù)據(jù)集的5%比例的具有相關聯(lián)的實體節(jié)點，并取它們的關聯(lián)值的平均值作為閾值δ?？紤]到不同數(shù)據(jù)集下的δ值可能不同，分別從20%，30%，…，80%的數(shù)據(jù)集比例下計算δ值，再從不同比例數(shù)據(jù)集構建的EAG中，隨機選取5%比例的邊，根據(jù)與選出的5%比例的邊的相鄰節(jié)點來計算它們的綜合關聯(lián)值，并與真實的關聯(lián)值對比來證明算法2的有效性。若真實的關聯(lián)值與算法2中得到的綜合關聯(lián)值同時小于或者同時大于閾值δ，即算法2得到的實體節(jié)點間關聯(lián)性與真實的關聯(lián)性一致，則表示算法2正確。如表2所示，算法2的正確率為70.02%，這從一定程度上說明了算法2的有效性。

此外，從另一個角度來測試本文基于互信息的補全方法的有效性。將數(shù)據(jù)集分為訓練集和測試集兩部分，并將數(shù)據(jù)集中得到的實體節(jié)點在不同比例的訓練集中測試本文方法（MI）的準確性。由于本文所提出的補全KG的方法是一種基于圖上的實體節(jié)點間關聯(lián)關系的疊加推理，Path Ranking方法（PRA-paths）[21]是通過連接實體的已有路徑來預測實體間的潛在關系，從而補全KG，這兩種方法都是通過已有的路徑進行知識推理來補全KG，具有一定的可比性。因此選取PRA-paths方法與MI方法進行對比來證明MI方法的有效性。在本實驗中，選擇準確率（Precision）、召回率（Recall）和F值作為衡量KG補全算法的指標，分別如式（9）和（10）所示：

Table 2 Accuracy ofAlgorithm 2表2 算法2的正確率

其中，Pre表示準確率；F0表示補全的邊也是測試邊；N(F0)表示補全的邊也是測試邊的條數(shù)；F表示補全的邊；N(F)表示補全的邊的條數(shù)；Rec表示召回率；T表示測試邊；N(T)表示測試邊的條數(shù)。

F值綜合衡量了準確率和召回率，公式如下:

實驗中，分別從淘寶數(shù)據(jù)集中隨機選取出20%、30%、40%、50%、60%、70%、80%作為訓練集，根據(jù)不同比例的訓練集得到的結果如下，從圖8和圖9可以看出，隨著訓練集比例的增加，MI方法和PRA-paths方法的準確率均先增加再降低，召回率逐漸增加。因為隨著訓練集比例的增加，實體節(jié)點增多，圖的連通性好，使得KG補全的準確率和召回率提高。當訓練集比例多于50%時，實體節(jié)點增加速度降低，圖的連通性趨于最大，得到的補全的邊不斷增多，召回率不斷提高，同時得到的無關的邊也在不斷增多，使得KG補全的準確率降低。當訓練集低于50%時，MI方法準確率高于PRA-paths方法，原因在于訓練集比較小的時候，實體節(jié)點較少，圖的連通性較差，MI方法在圖的低連通性下比PRA-paths方法的準確率高。本文還測試了不同比例的訓練集下的F值，從整體上衡量算法的有效性。由圖10可以看出，MI方法的F值在訓練集比例小于65%時均高于PRA-paths方法，因為在連通性低的圖中不利于PRA-paths方法的推理。在訓練集高于65%時，雖然MI方法的F值低于PRA-paths方法，因為MI方法在連通性較好的圖中得到無關的邊比PRA-paths方法多，但是兩種方法F值的差距并不大且MI方法的F值略大于PRA-paths方法的F值，所以與PRA-paths方法相比本文提出的MI方法較為理想。

Fig.8 Precision圖8 準確率

Fig.9 Recall圖9 召回率

Fig.10 F scores圖10 F值

5 總結與展望

本文針對KG中實體節(jié)點間缺失的關系，結合UGD，通過互信息計算實體節(jié)點之間的關聯(lián)關系，進而構建EAG，并根據(jù)EAG的結構，提出一種疊加的方法來計算不相鄰實體節(jié)點間的潛在關聯(lián)關系，從而補全KG。本文用UGD中的實體節(jié)點之間的關聯(lián)關系來補全KG，解決了KG中因為實體節(jié)點間關系稀疏而導致關系抽取不準確的問題。但是當UGD的規(guī)模較大時，得到的EAG圖結構比較復雜，準確率較低且代價較高，因此未來的工作將考慮在實體間添加標記，去掉那些關聯(lián)關系較“弱”的實體節(jié)點，從而提高KG補全的準確率。