韓 路，尹子都，王鈺杰，胡 礦，岳 昆+

1.云南大學 信息學院，昆明 650504

2.云南大學 信息技術中心，昆明 650504

基于貝葉斯網的知識圖譜鏈接預測*

韓 路1，尹子都1，王鈺杰1，胡 礦2，岳 昆1+

1.云南大學 信息學院，昆明 650504

2.云南大學 信息技術中心，昆明 650504

結合外部知識，使用特定方法進行知識圖譜的鏈接預測，即知識圖譜中缺失信息的發(fā)現(xiàn)和還原，是目前知識圖譜領域研究的熱點和關鍵。以電子商務應用為背景，基于已經構建好的描述用戶興趣的知識圖譜，結合外部數據集，以貝葉斯網這一重要概率圖模型作為不同商品之間相似性及其不確定性的表示和推理框架，通過對商品屬性進行統(tǒng)計計算，構建反映商品之間相似關系的貝葉斯網，進而基于概率推理機制，定量地判斷商品節(jié)點與用戶節(jié)點之間存在鏈接的真實性，得到真實和完整的知識圖譜，為個性化推薦和關聯(lián)查詢提供依據。建立在真實數據上的實驗結果表明，提出的模型和算法是有效的。

知識圖譜；鏈接預測；貝葉斯網；相似性；概率推理

1 引言

隨著信息技術的不斷發(fā)展和成熟，Web技術正在從網頁之間的鏈接向包含各種實體以及實體之間關系的數據鏈接轉變，傳統(tǒng)的文本萬維網逐步發(fā)展成為數據萬維網，互聯(lián)網公司逐步開始以此為基礎構建知識圖譜（knowledge graph，KG）[1]。借助KG，人們可以從過去單一的網頁鏈接轉向實體鏈接：基于KG的搜索引擎，通過圖結構反饋知識，幫助用戶簡單精確地實現(xiàn)知識的獲取和定位，從而實現(xiàn)真正意義上的語義搜索[2]。KG是一種由節(jié)點和邊組成的圖結構，本質上是由數據構成的語義網[3]。KG中的節(jié)點對應現(xiàn)實世界中存在的實體，節(jié)點之間的邊代表實體之間的關系。KG的研究涉及自然語言處理、機器學習和數據挖掘等多個領域的知識，基于KG的數據挖掘是未來相關研究的趨勢[4]。

網絡關系的鏈接預測是數據挖掘和機器學習領域中一個新興的課題[5]，它是指如何通過網絡中已知的節(jié)點以及網絡結構等信息來預測網絡中無邊相連的兩個節(jié)點之間產生鏈接關系的可能性，能為缺失信息還原和錯誤信息檢測提供支撐技術[6]。

目前，KG研究主要包括如下兩方面：（1）KG的構建，其中包含信息抽取、知識融合等多個過程[7]。（2）KG中知識的推理，KG上的規(guī)則主要是針對關系的，即通過規(guī)則（一般為鏈式規(guī)則）發(fā)現(xiàn)實體之間隱含的關系[1]。

KG鏈接預測是KG推理領域的研究方向之一[8]，由于數據來源廣泛，尤其是Web數據更加雜亂，構建KG的源數據中往往存在大量錯誤及缺失信息。對于存儲KG的知識庫而言，盡管擁有大規(guī)模的數據，但許多數據庫仍然不完整，例如，Google Knowledge Vault項目[9]中的核心元素Freebase[10]中，71%的個人信息缺失“出生地”，75%缺失“國籍說明”等。通過鏈接預測，可以發(fā)現(xiàn)現(xiàn)有KG中缺失和錯誤的信息，得到更為完整和真實的KG，進而更新知識庫。具體而言，KG鏈接預測主要涉及如下兩方面的任務[5]：

（1）預測異常鏈接。由于數據來源的復雜性，現(xiàn)有KG存在部分錯誤邊的情況，通過鏈接預測可以發(fā)現(xiàn)異常鏈接，進而得到更為真實的KG。

（2）預測未知鏈接。針對預測查詢或搜索服務，來預測KG中尚未包含的鏈接。

例如，圖1所示的KG描述了用戶對電影興趣的KG，未知鏈接預測的任務是判斷圖中虛線邊是否真實存在，異常鏈接預測旨在發(fā)現(xiàn)已經存在，但其存在概率很低且可能需要刪除的鏈接關系。

近年來，對于鏈接預測相關問題，國內外學者開展了較為全面和系統(tǒng)的研究。例如，Getoor等人[11]系統(tǒng)地綜述了鏈接挖掘的相關概念和研究領域，介紹了鏈接預測的問題、定義和經典模型。對于KG中的鏈接預測，目前大多數方法都是基于組成KG的RDF（resource description framework）三元組進行，而基于KG圖結構的鏈接預測方法仍有待進一步深入研究。Bordes等人[12]提出了TransE模型，將KG中的關系看作實體間的某種向量；Drumond等人[13]利用張量分解對不完整KG中的RDF三元組進行預測，從而支持KG的更新；Socher等人[14]提出了基于神經網絡的方法，應用于鏈接預測，但方法的復雜性和模型訓練及參數調優(yōu)是其主要缺點；Richardson等人[15]定義了馬爾科夫邏輯網，基于邏輯準則定義KG潛在函數語言的方法，從而進行鏈接預測，但規(guī)則學習以及參數估計成為其應用中的瓶頸。同時，現(xiàn)有方法對于KG中尚未描述但又必須的知識獲取及融合還有許多不足之處，且對于鏈接關系存在的可能性或不確定性不能較好地進行定量計算。

Fig.1 KG of user interest on movies圖1 用戶對電影興趣的KG

貝葉斯網（Bayesian network，BN）[16]是典型的概率圖模型[17]，同時考慮了網絡結構和節(jié)點屬性信息，具有堅實的概率論理論基礎和廣泛應用[18]。適用于表達和分析不確定性知識，能夠對不確定性知識做出有效的推理，是目前不確定知識表達和推理領域最有效的模型之一[19]。KG中實體之間的相互關系存在不確定性，通過BN的概率推理可以發(fā)現(xiàn)這種不確定性。同時，KG中鏈接預測的實質是通過KG中已有的鏈接對未知鏈接進行判斷，這是BN的優(yōu)勢所在。

事實上，除了KG中描述的知識外，現(xiàn)實世界中存在許多與KG相關聯(lián)的外部知識（例如描述商品類型的標簽數據集），這些知識中存在大量人們已經構建好的豐富的先驗知識，可以提供更為全面和真實的信息，KG中提供的數據與外部知識結合，可提高KG鏈接預測的準確性。

本文從已有KG出發(fā)，結合標簽數據集外部知識，構建鏈接貝葉斯網（link Bayesian network，LBN）模型，基于LBN進行概率推理，從而完成KG鏈接預測的任務。

具體而言，本文的研究主要包括如下幾方面：

（1）針對KG中屬性節(jié)點單一，數據量不夠充分的特點，引入與KG相關聯(lián)的描述商品類別的標簽數據集這一外部知識，以便實現(xiàn)將KG中數據和外部數據集結合。標簽數據中對應描述KG中商品實體的標簽，可以充分用于表達商品之間的相似性，提高鏈接預測的準確性。

（2）為了描述商品節(jié)點之間的相似性，利用商品屬性，構建針對KG鏈接預測的LBN。將KG和標簽數據集相結合而構成的商品屬性，構建描述商品之間相關性的LBN，作為BN概率推理及鏈接預測的基礎。

（3）針對KG的鏈接預測，當KG中節(jié)點較多且鏈接比較緊密時，構建的LBN的規(guī)模也會隨之增大。Gibbs采樣是應用最廣泛的馬爾科夫鏈蒙特卡羅（Markov chain Monte Carlo，MCMC）概率算法，可有效地獲取一系列近似等于指定多維概率分布的觀察樣本[20-21]。為了實現(xiàn)基于LBN的高效鏈接預測，本文基于Gibbs采樣給出了LBN的概率推理算法，量化了未知鏈接真實存在的可能性，基于此實現(xiàn)了KG的鏈接預測。

（4）基于MovieLens站點數據（http://grouplens. org/），本文實現(xiàn)并測試了LBN的構建、近似推理和鏈接預測方法的有效性。

本文組織結構如下：第2章描述KG鏈接預測問題，并給出LBN的定義；第3章討論構建LBN模型的方法；第4章研究基于LBN的近似推理算法和KG鏈接預測方法；第5章給出實驗結果和性能分析；第6章總結全文并展望將來的工作。

2 問題描述和相關定義

根據用戶瀏覽信息可以針對特定用戶構建個性化的用戶興趣KG，通過鏈接預測，可以獲得更加完整的KG，進一步應用于查詢和個性化推薦等，從而實現(xiàn)KG對于用戶的核心價值。對于描述用戶興趣的KG，用戶和商品之間的聯(lián)系是研究的重點：為了進行鏈接預測，借助已有的聯(lián)系以及商品屬性，發(fā)現(xiàn)用戶和不存在鏈接商品之間的關系，是本文研究的核心。KG本質上是一種基于圖的數據結構，首先給出KG的形式化定義。

定義1（KG）KG用Gk=(V,E)表示，其中V={v1, v2,…,vn}表示KG中實體對應節(jié)點的集合，E={e1, e2,…,en}表示實體之間邊的集合。任意一條邊對應一個節(jié)點二元組ex={vi,vj}，節(jié)點vi稱為始點，節(jié)點vj稱為終點。

用戶興趣KG主要包括用戶、商品和商品屬性信息3類實體。KG中的節(jié)點分別代表不同實體，與實體類型對應，集合V中節(jié)點也對應這3種類型。

對于Gk的節(jié)點集合V，用U表示其中的用戶節(jié)點，O={O1,O2,…,Om}表示商品節(jié)點集合，Si={s1,s2,…,sk} (1≤i≤m)表示商品節(jié)點Oi在Gk中對應的屬性節(jié)點集。

例1圖1為用戶電影興趣KG，圖中節(jié)點分為用戶、電影以及電影屬性3類，該KG中的電影屬性主要包括演員和導演等。其中，用戶節(jié)點為U，電影實體集合為O={M1,M2,M3}。M1對應的屬性信息集合S1= {A1,A2,A3}。

此外，KG中實體之間的相互關系存在不確定性，這種不確定性體現(xiàn)在Gk對應邊上，即Gk中的邊以一定的概率真實存在。需要對這種不確定性進行量化，作為鏈接預測的依據，為此引出可信度的概念。

定義2（可信度）KG圖結構Gk中的邊真實存在的概率值稱為可信度。對于有向邊{vi,vj}，用Wij表示其可信度。

可信度越大，表示對應鏈接存在的可能性越大。給定閾值ε，對應特定的鏈接進行可信度計算，可信度大于等于ε的認為其真實存在，若可信度小于閾值ε，則忽略。Gk中已有邊的可信度都大于等于ε，是本文討論的前提。

BN是一個DAG（directed acyclic graph）Gb=(V, E)，其中V代表隨機變量節(jié)點集，每一個節(jié)點對應一個隨機變量，E中的有向邊用來表示節(jié)點之間的條件依賴關系。V中的每一個變量都有一個條件概率表（conditional probability table，CPT），用來表示已知父親節(jié)點狀態(tài)來計算當前狀態(tài)的概率。基于BN的基本概念，提出LBN模型，作為鏈接預測的模型基礎。下面給出LBN的定義。

定義3（LBN）LBN用一個二元組G=(Gl,P)表示，其中：

（1）Gl=(Ol,El)為LBN的DAG結構，Ol={O1,O2,…, Om}為節(jié)點集合，每個節(jié)點對應KG中的一個商品節(jié)點，有向邊集El為節(jié)點之間相似關系的集合。Oi(1≤i≤m)取值為1或0，分別表示Oi在Gk中是否和用戶節(jié)點U之間存在鏈接。若存在有向邊{Oi,Oj}，則稱Oi為Oj的一個父節(jié)點，Oj的父節(jié)點集記為Pa(Oi)。

（2）P={p(Oi|Pa(Oi)|Oi∈O)}為條件概率分布的集合，由各節(jié)點CPT中概率參數值構成，p(Oi|Pa(Oi))表示節(jié)點Oi在其父節(jié)點的影響下的條件概率，用來描述Pa(Oi)的狀態(tài)對Oi的影響。

本文構建商品屬性之間相似關系的LBN。對于圖1中的用戶興趣KG而言，描述商品屬性的信息較少，而且比較單一，無法充分表達商品節(jié)點之間的相似性。本文引入標簽數據集D（所謂標簽即商品所對應的類型）這一“外部知識”。D中主要描述的是KG中集合O的商品實體對應的標簽類型信息：數據集D中一條商品的標簽類型記錄Item可以表示為{Oi,Ti,Li}，其中Oi(1≤i≤m)用以標識KG中商品集合O中的實體，Ti表示Oi對應商品的名稱，Li={l1,l2,…, ln}表示Oi所對應的標簽。

圖1中KG對應的數據集D如表1所示。商品節(jié)點Oi(1≤i≤m)的屬性內容可表示為一個二元組Ci=＜Oi,Bi＞，其中屬性Bi由KG中的節(jié)點集合Si和數據集D中的Li共同組成，即Bi=Si?Li(1≤i≤n)。

Table 1 Data of labels表1 標簽數據集

例2對于商品節(jié)點M2而言，KG中對應的節(jié)點集合S2={D1,A3}，數據集D對應的標簽為L2={l1,l4,l5, l8}，則C2=＜M2,{l1,l4,l5,l8,D1,A3}＞。

3 LBN的構建

構建LBN，首先構建其DAG?；跇嫿ǖ腄AG，可以發(fā)現(xiàn)商品節(jié)點之間的相似關系，從而基于此進行概率推理。以下討論基于Gk和標簽數據集D來構建LBN的DAG的方法。

3.1 節(jié)點選取

LBN的Gl基于KG中商品節(jié)點之間的相似性而構建，因此Ol由KG中的商品節(jié)點組成。構建DAG的第一步是選取商品節(jié)點，對于Gk中的商品節(jié)點，與其相關聯(lián)的邊數多于其余類型的節(jié)點。為此，引入節(jié)點度的概念，作為選取特定節(jié)點的重要依據之一。

定義4（節(jié)點度）節(jié)點度d是指和該節(jié)點相關聯(lián)的邊的條數。對于類似KG的有向圖而言，節(jié)點Oi的入度dp(Oi)是指進入該節(jié)點的邊的條數，節(jié)點的出度do(Oi)是指從該節(jié)點出發(fā)的邊的條數，d(Oi)為入度和出度之和。

本文通過判斷節(jié)點度的大小來獲取集合O中的節(jié)點，對于給定的KG，設置節(jié)點度d，遍歷KG中的所有節(jié)點，依次求節(jié)點的節(jié)點度，對于節(jié)點度不小于d的節(jié)點，加入到集合Ol中，直到遍歷結束，輸出集合Ol。

例3由圖1可知，“電影”節(jié)點對應的最小節(jié)點度d=3，依次遍歷Gk節(jié)點集V中的所有節(jié)點，將節(jié)點度不小于d的節(jié)點添加到集合Ol中，然后輸出Ol，從而可以得到Ol={M1,M2,M3}。

3.2 DAG的構建

LBN中有向邊的集合El描述節(jié)點間的相似關系，DAG的構建包括如下三方面的問題：（1）確定商品對應節(jié)點間是否存在邊，即判斷商品是否相似；（2）若商品之間存在相似關系，則要確定對應節(jié)點之間邊的方向；（3）構建DAG的過程中保證不出現(xiàn)環(huán)。

針對問題（1），對于任意兩個商品，考慮這兩個商品同時具有的屬性占它們所具有全部屬性的比例，該比例越高，則這兩個商品相似度越高；若該值高于相似度閾值ε，則在這兩個商品對應節(jié)點之間存在一條無向邊。下面給出基于對商品屬性信息統(tǒng)計計算得到的用戶間相似度計算方法，商品節(jié)點Oi和Oj的相似度用sim(Oi,Oj)表示：

其中，Bi?Bj描述兩個商品同時具有的屬性，N(Bi?Bj)表示屬性個數；Bi?Bj表示兩個商品共同具有的屬性，N(Bi?Bj)為屬性個數；N(Bi?Bj)和N(Bi?Bj)可基于簡單的統(tǒng)計計算得到。

設ε為給定相似度閾值，當Oi和Oj的相似度sim(Oi,Oj)＞ε時，認為兩個商品是相似的，即商品Oi和Oj對應節(jié)點之間存在一條無向邊。

針對問題（2），考慮任意兩個有邊相連的節(jié)點，這兩個商品的共同屬性占各自屬性的比例反映了它們的共同屬性所占各自屬性的比例，該比例值高的商品吸引的用戶對于該比例值較低者也可能會感興趣；基于此可確定相似關系的指向，從而確定圖中邊的方向。下面給出基于對商品屬性信息統(tǒng)計計算來判斷商品間指向關系的方法，商品Oi對Oj的依賴度用D(Oi|Oj)表示，商品Oj對Oi的依賴度用D(Oj|Oi)表示：

若D(Oi|Oj)＞D(Oj|Oi)，則表示Oi對Oj的依賴程度高于Oj對Oi的依賴程度，即Oj對Oi之間的有向邊應由Oj指向Oi。

針對問題（3），首先建立一個已處理節(jié)點集合，用于存放處理后的節(jié)點。接著選取一個節(jié)點作為初始節(jié)點，分別通過相似性計算方法確定與其他節(jié)點之間的鏈接關系，當此鏈接關系指向的節(jié)點已有指向已處理集合中節(jié)點的邊時，就忽略此鏈接關系，否則就保留此鏈接關系；處理完所有節(jié)點，就得到了目標結構。

算法1描述了上述思想。

算法1構建LBN的DAG

基于以上相似度和興趣依賴度兩個度量標準，可以得到LBN的DAG結構。然后，本文采用似然估計的方法[22]來計算貝葉斯網絡中每個節(jié)點的概率參數表，從而最終得到LBN。

例4對于圖1中KG，構建LBN的節(jié)點集Ol={M1, M2,M3}，其中S1={A1,A2,A3}，S2={D1,A3}，S3={A2,D2, A4}，再結合數據集D便可得到屬性集。按照式（1），計算每兩個電影節(jié)點之間的相似度，得到結果為sim(M1, M2)=0.66，sim(M1,M3)=0.35，sim(M3,M2)=0.54。假設ε的值預先設定為0.50，那么大于該值的兩個節(jié)點之間應該有一條無向邊。通過式（2）、式（3），計算每條邊的方向，例如D(M2|M3)=0.42，D(M3|M2)=0.50，則兩個節(jié)點之間的邊應由節(jié)點M2指向節(jié)點M3。基于似然估計，計算各個節(jié)點的條件概率表CPT。最終得到的LBN如圖2所示。

Fig.2 Asimple LBN圖2 簡單的LBN

4 基于LBN近似推理的KG鏈接預測

BN推理是指利用BN結構及其條件概率表，在給定證據后進行某些節(jié)點取值概率的計算。然而，BN的精確推理具有指數時間[23]。隨著節(jié)點數的增加，推理的時間復雜度也會大幅度增加，尤其對于較大規(guī)模的KG而言，精確推理并不適用。因此，本文選擇BN的近似推理算法。馬爾科夫鏈蒙特卡羅算法[20-21]是目前被廣泛應用的一種貝葉斯近似推理方法，Gibbs采樣是MCMC方法中應用最廣泛的一種。

本文基于Gibbs采樣，利用已經和用戶存在鏈接的商品節(jié)點作為證據節(jié)點，根據證據節(jié)點的取值來計算其他非證據節(jié)點在不同狀態(tài)下的概率值。基于此計算用戶和商品節(jié)點之間的邊的可信度，作為KG鏈接預測的依據。為了便于計算，同時保證方法的普遍性，對于當前采樣節(jié)點，本文僅考慮其馬爾科夫覆蓋（X的馬爾科夫覆蓋是包括X的直接孩子節(jié)點、直接父親節(jié)點以及直接孩子其他父親節(jié)點的節(jié)點集合，記為MB(X)）中的節(jié)點對它的影響[24]。算法2給出了具體的描述。

算法2基于Gibbs采樣的LBN近似推理

利用算法2，可以得到 p(Oj=1|Oi=1)的值，即在給定證據變量Oi=1的情況下，非證據變量Oj=1的概率。由定義4可知，Oj的取值決定節(jié)點Oj與用戶節(jié)點U之間是否存在鏈接。因此，p(Oj=1|Oi=1)的值為{Oi,U}已經存在的情況下{Oj,U}的可信度W。由上述可知，若W≥ε，則該鏈接真實存在。

例5對于圖2中的LBN，{M2,U}已經存在，因此選擇M2為證據節(jié)點，然后計算 p(M1=1|M2=1)，即{M1,U}的可信度。假設當前節(jié)點的狀態(tài)是[M1=1,M2= 1,M3=0]。在當前狀態(tài)下，通過M3馬爾科夫覆蓋中變量在當前狀態(tài)下的值來對非證據節(jié)點M3進行采樣，經過計算便可以得到p(M3=1|M1=1,M2=1)=1和p(M3=0|M1=1,M2=1)=0。假設生成的隨機數r3=0.5，那么采樣結果為M3=0，同時生成新的狀態(tài)[M1= 1,M2=1,M3=0]。若采樣次數為300，其中M1=1的次數為240，則p(M1=1|M2=1)=0.6，即未知鏈接{M1,U}的可信度為0.6。若ε=0.5，則該未知鏈接真實存在。

利用基于Gibbs采樣的LBN推理算法，通過設定Ol中不同節(jié)點為非證據變量，可以依次獲得該節(jié)點取值為1的概率，即該節(jié)點在Gk中與用戶節(jié)點U之間未知鏈接的可信度，然后與給定閾值進行比較，則可判斷該未知鏈接的真實存在性，從而發(fā)現(xiàn)用戶和未存在鏈接商品之間是否存在關系。針對KG的鏈路預測，需要將真實存在的鏈接關系反映在KG的邊上。對于描述用戶興趣的KG，若用戶和商品之間存在關系，統(tǒng)一用“fondof”對其進行標注，實現(xiàn)用戶興趣KG中對于未知鏈接的預測。

5 實驗結果

本文測試了LBN構建和LBN近似推理算法的效率以及KG鏈接預測的有效性。實驗環(huán)境如下：Intel?CoreTMi5 2.40 GHz處理器，4 GB內存，Windows7操作系統(tǒng)，以Eclipse為開發(fā)平臺，MySQL存儲LBN的CPT，使用Java語言編寫程序。實驗中，針對形如圖1的描述用戶對電影興趣的KG，將MovieLens站點數據與KG中原有數據結合，作為本文的測試數據。MovieLens數據集中包含6 040個用戶對3 900部電影的1 000 209條評價數據，數據集格式為UserId：：MovieId：：Title：：Genres：：Rating，依次為用戶Id、電影Id、電影名稱、電影標簽類型和電影評分，每個用戶至少為20部電影評分，其中MovieId：：Title：：Genres構成了本文的外部數據集D。

5.1 LBN的構建效率

為了測試構建LBN算法的時間開銷，選取包含10，20，…，100個節(jié)點的LBN，并分別測試了是否包含數據庫I/O開銷的LBN構建時間，如圖3所示。可以看出，構建LBN的時間隨著節(jié)點數的增加基本呈線性增長趨勢。

Fig.3 Efficiency of LBN construction圖3 構建LBN的效率

5.2 LBN推理效率和收斂性測試

本文測試了基于Gibbs采樣的LBN近似推理算法的效率。圖4和圖5分別給出了在不同節(jié)點數目情況下，隨著采樣次數的不斷增加，算法2返回結果的收斂性和時間開銷。從圖4中可以看出，隨著采樣次數的增加，不同節(jié)點數目情形下LBN推理結果均能較快收斂到一個穩(wěn)定的值（即靜態(tài)分布），這從一定程度上說明了算法2的有效性。從圖5中可以看出，不同節(jié)點數目情形下算法2的執(zhí)行時間都隨著采樣時間呈線性趨勢增加，這說明了LBN近似推理算法的高效性。

5.3 KG鏈接預測有效性測試

KG中的用戶和商品節(jié)點之間的鏈接表示用戶對于商品的偏好，因此通過判斷預測用戶偏好的準確性作為本文KG鏈接預測有效性的衡量標準。從MovieLens數據集中隨機地選擇某一個用戶評分較高的5部電影，將其作為KG中的已知鏈接，再選取5部該用戶未評過分的電影作為KG中的未知鏈接。給定預測閾值，高于閾值，則鏈接預測成功。為了測試基于LBN的概率推理進行KG鏈路預測方法的有效性，將已知邊分為訓練集和測試集兩類。本文實驗中，選擇AUC（area under the receiver operating characteristic curve）、準確率（precision）和召回率（recall）作為衡量鏈接預測算法的指標。

Fig.4 Convergence of LBN approximate inference圖4 LBN近似推理結果的收斂性

Fig.5 Efficiency of LBN approximate inference圖5 LBN近似推理算法的效率

實驗中，測試不同迭代次數、不同訓練集比例下3個指標的結果。從圖6、圖7和圖8中可以看出，迭代次數的不同對于結果影響較小，而訓練集比例的不同結果也會受到影響。對于AUC而言，AUC高于0.5的程度反映了算法在多大程度上比隨機選擇的方法精確[6]。由圖6可以看出，在不同比例的訓練集情況下，AUC的值都大于0.5，且隨著訓練集比例的增加，AUC的值不斷增加。實驗結果在一定程度上說明了本文提出的KG鏈路預測方法的有效性。

Fig.6 AUC of KG link prediction圖6KG鏈路預測方法的AUC

Fig.7 Precision of KG link prediction圖7 KG鏈路預測方法的準確率

Fig.8 Recall of KG link prediction圖8 KG鏈路預測方法的召回率

同時，測試了不同迭代次數、不同訓練集比例下的F值，如圖9所示。F值綜合了準確率和召回率，普遍在0.45以上，整體上說明了本文方法的準確性。

Fig.9 F-measure of KG link prediction圖9KG鏈路預測方法的F值

綜上，實驗結果表明，本文基于LBN的KG鏈路預測方法在模型構建和鏈路預測方面都有較好的性能，也從一定程度上證明了本文方法的可行性。

6 總結與展望

本文以電子商務應用為背景，針對描述用戶興趣的KG，提出將KG與標簽數據集結合，充分描述商品節(jié)點的屬性，并構建了描述各屬性間關聯(lián)關系及其不確定性的LBN。然后基于BN的近似推理算法實現(xiàn)了對于未知鏈接不確定性的高效量化計算，從而發(fā)現(xiàn)KG中缺失的信息。通過建立在真實數據集上的實驗，測試了本文方法的有效性，實驗結果在一定程度上驗證了所提出思路的可行性。

本文從用戶和商品之間的關聯(lián)度出發(fā)，為KG中未知鏈接的預測提供了一種新的思路，但仍是KG鏈路預測的初步探索。從KG鏈路預測問題的特點和應用來看，如何處理大規(guī)模的KG和海量的標簽數據集，合理實現(xiàn)與現(xiàn)有思路的實驗對比，將未知鏈路預測方法擴展到異常鏈路預測，是今后將要開展的工作。

[1]Wang Haofen.semantic search on large scale RDF data[D]. Shanghai:Shanghai Jiao Tong University,2013.

[2]Liu Qiao,Li Yang,Duan Hong,at el.Knowledge graph construction techniques[J].Journal of Computer Research and Development,2016,53(3):582-600.

[3]Doan A H,Madhavan J,Dhamankar R,et al.Learning to match ontologies on the semantic Web[J].The VLDB Journal,2003,12(4):303-319.

[4]Liu Ye,Zhu Weiheng,Pan Yan,et al.Multiple sources fusion for link prediction via low-rank and sparse matrix decomposition[J].Journal of Computer Research and Development,2015,52(2):423-436.

[5]Nickel M,Murphy K,Tresp V,et al.A review of relational machine learning for knowledge graphs[J].Proceedings of the IEEE,2016,104(1):11-33.

[6]Lv Linyuan,Zhou Tao.Link prediction in complex networks: a survey[J].Physica A:Statistical Mechanics and Its Applications,2011,390(6):1150-1170.

[7]Meng Xiaofeng,Du Zhijuan.Research on the big data fusion: issues and challenges[J].Journal of Computer Research and Development,2016,53(2):231-246.

[8]Bordes A,Gabrilovich E.Constructing and mining Web-scale knowledge graphs:KDD 2014 tutorial[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,Aug 24-27, 2014.New York:ACM,2014:1967-1967.

[9]Dong Xin,Gabrilovich E,Heitz G,et al.Knowledge vault: a Web-scale approach to probabilistic knowledge fusion[C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,Aug 24-27,2014.New York:ACM,2014:601-610.

[10]Bollacker K,Evans C,Paritosh P,et al.Freebase:a collaboratively created graph database for structuring human knowledge[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data,Vancouver,Canada, Jun 9-12,2008.New York:ACM,2008:1247-1250.

[11]Getoor L,Diehl C P.Link mining:a survey[J].ACM SIGKDD Explorations Newsletter,2005,7(2):3-12.

[12]BordesA,Usunier N,Garcia-DuranA,et al.Translating embeddings for modeling multi-relational data[C]//Proceedings of the 27th Annual Conference on Neural Information Processing Systems,Lake Tahoe,USA,Dec 5-8,2013.Cambridge,USA:MIT Press,2013:2787-2795.

[13]Drumond L,Rendle S,Schmidt-Thieme L.Predicting RDF triples in incomplete knowledge bases with tensor factorization[C]//Proceedings of the 27th Annual ACM Symposium on Applied Computing,Trento,Italy,Mar 26-30,2012.New York:ACM,2012:326-331.

[14]Socher R,Chen D,Manning C D,et al.Reasoning with neural tensor networks for knowledge base completion[C]//Proceedings of the 27th Annual Conference on Neural Information Processing Systems,Lake Tahoe,USA,Dec 5-8,2013. Cambridge,USA:MIT Press,2013:926-934.

[15]Richardson M,Domingos P.Hybrid Markov logic networks [C]//Proceedings of the 23rd National Conference on Artificial Intelligence,Chicago,USA,Jul 13-17,2008.Menlo Park, USA:AAAI,2008:1106-1111.

[16]Heckerman D,Dan G,Chickering D M.Learning Bayesian networks:the combination of knowledge and statistical data [J].Machine Learning,1995,20(3):197-243.

[17]Koller D,Friedman N.Probabilistic graphical models:principles and techniques adaptive computation and machine learning[M]//Probabilistic Graphical Models:Principles and Techniques.Cambridge,USA:MIT Press,2009:161-168.

[18]Zhang Hongyi,Wang Liwei,Chen Yuxi.Research progressof probabilistic graphical models:a survery[J].Journal of Software,2013,24(11):2476-2497.

[19]Zhang Lianwen,Guo Haipeng.Introduction to Bayesian networks[M].Beijing:Science Press,2006.

[20]Mcculloch E,Variable selection via Gibbs sampling[J].Journal of theAmerican StatisticalAssociation,1993,88(423):881-889.

[21]Bayarri M J,Castellanos M E,Morales J.MCMC methods to approximate conditional predictive distributions[J].Computational Statistics&DataAnalysis,2015,51(2):621-640.

[22]Wang Tianren,Sayre E C.Maximum likelihood estimation (MLE)of students'understanding of vector subtraction[J]. American Institute of Physics Conference Series,2010,1289 (1):329-332.

[23]Pearl J.Probabilistic reasoning in intelligent systems[J].Computer ScienceArtificial Intelligence,1988,70(14):521-538.

[24]Zhu Zexuan,Ong Y S,Dash M.Markov blanket-embedded genetic algorithm for gene selection[J].Pattern Recognition,2007,40(11):3236-3248.

附中文參考文獻：

[1]王昊奮.面向大規(guī)模RDF數據的語義搜索[D].上海:上海交通大學,2013.

[2]劉嶠,李楊,段宏,等.知識圖譜構建技術綜述[J].計算機研究與發(fā)展,2016,53(3):582-600.

[4]劉冶,朱蔚恒,潘炎,等.基于低秩和稀疏矩陣分解的多源融合鏈接預測算法[J].計算機研究與發(fā)展,2015,52(2): 423-436.

[7]孟小峰,杜治娟.大數據融合研究:問題與挑戰(zhàn)[J].計算機研究與發(fā)展,2016,53(2):231-246.

[18]張宏毅,王立威,陳瑜希.概率圖模型研究進展綜述[J].軟件學報,2013,24(11):2476-2497.

[19]張連文,郭海鵬.貝葉斯網引論[M].北京:科學出版社,2006.

HAN Lu was born in 1990.He is an M.S.candidate at Yunnan University.His research interests include data analysis and knowledge discovery.

韓路（1990—），男，河北邯鄲人，云南大學碩士研究生，主要研究領域為數據分析，知識發(fā)現(xiàn)。

YIN Zidu was born in 1990.He is a Ph.D.candidate at Yunnan University.His research interests include knowledge engineering,massive data analysis and services.

尹子都（1990—），男，甘肅天水人，云南大學博士研究生，主要研究領域為知識工程，海量數據分析與服務。

WANG Yujie was born in 1990.He is an M.S.candidate at Yunnan University.His research interests include knowledge engineering,massive data analysis and services.

王鈺杰（1990—），男，河北唐山人，云南大學碩士研究生，主要研究領域為知識工程，海量數據分析與服務。

HU Kuang was born in 1982.He received the M.S.degree in software engineering from Yunnan University in 2009.Now he is a research associate at Information Technology Center,Yunnan University.He is working on Internet data center,and his research interest is container-based virtualization.

胡礦（1982—），男，云南楚雄人，2009年于云南大學軟件工程專業(yè)獲得碩士學位，現(xiàn)為云南大學信息技術中心助理研究員，主要從事數據中心建設工作，主要研究基于容器的虛擬化。

YUE Kun was born in 1979.He received the M.S.degree from Fudan University in 2004,and the Ph.D.degree from Yunnan University in 2009.Now he is a professor and Ph.D.supervisor at Yunnan University,and the member of CCF.His research interests include knowledge engineering,massive data analysis and services.

岳昆（1979—），男，云南曲靖人，2004年于復旦大學獲得碩士學位，2009年于云南大學獲得博士學位，現(xiàn)為云南大學教授、博士生導師，CCF會員，主要研究領域為知識工程，海量數據分析與服務。

Link Prediction of Knowledge Graph Based on Bayesian Network*

HAN Lu1,YIN Zidu1,WANG Yujie1,HU Kuang2,YUE Kun1+
1.School of Information Science and Engineering,Yunnan University,Kunming 650504,China
2.Information Technology Center,Yunnan University,Kunming 650504,China

+Corresponding author:E-mail:kyue@ynu.edu.cn

HAN Lu,YIN Zidu,WANG Yujie,et al.Link prediction of knowledge graph based on Bayesian network. Journal of Frontiers of Computer Science and Technology,2017,11(5)：742-751.

Link prediction is to discover and recover missing information in a knowledge graph(KG).Combining external knowledge and employing some specified methods to fulfill link prediction is the topic with great attention and key problem in KG research.Taking e-commerce application as the background,this paper combines the KG that has been constructed to describe user interest with external data,and adopts Bayesian network(BN),an important probabilistic graphical model,as the framework for representing and inferring the similarities among commodities as well as corresponding uncertainties.This paper constructs the BN to reflect the similarities by statistic computations upon commodity properties,and evaluates the authenticity of the links between commodity and user nodes based on the probabilistic inference mechanism of BN.Consequently,the real and complete KG can be obtained,as the basis of personalized recommendation and correlation query processing.The experimental results established onreal data show the effectiveness of the model and algorithms proposed in this paper.

knowledge graph;link prediction;Bayesian network;similarity;probabilistic inference

10.3778/j.issn.1673-9418.1608042

A

TP391

*The National Natural Science Foundation of China under Grant Nos.61472345,61562090,61402398(國家自然科學基金);the Applied Basic Research Project of Yunnan Province under Grant No.2014FA023(云南省應用基礎研究計劃);the Program for Innovative Research Team in Yunnan University under Grant No.XT412011(云南大學創(chuàng)新團隊培育計劃);the Program for Excellent Young Talents in Yunnan University under Grant No.WX173602(云南大學青年英才培養(yǎng)計劃);the Innovative Research Foundation for Graduate Students of Yunnan University(云南大學研究生科研創(chuàng)新基金項目).

Received 2016-08,Accepted 2016-10.

CNKI網絡優(yōu)先出版:2016-10-31，http://www.cnki.net/kcms/detail/11.5602.TP.20161031.1650.012.html