關(guān)于主動(dòng)學(xué)習(xí)下的知識(shí)圖譜補(bǔ)全研究*

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

1.浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310027

2.浙江省大數(shù)據(jù)智能計(jì)算重點(diǎn)實(shí)驗(yàn)室（浙江大學(xué)），杭州 310027

1 引言

隨著信息科技的突破，新一代人工智能迎來(lái)了史無(wú)前例的發(fā)展熱潮。知識(shí)圖譜作為人工智能的基礎(chǔ)支撐，例如支撐軌道交通運(yùn)維優(yōu)化、系統(tǒng)設(shè)計(jì)等，目前也得到了許多學(xué)者和研究人員的關(guān)注。

知識(shí)圖譜是一種信息網(wǎng)絡(luò)，它包含真實(shí)世界中存在的物品、人物、地點(diǎn)等信息。知識(shí)圖譜一般用三元組集合來(lái)表示，用RDF（resource description framework）或者圖數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)三元組。知識(shí)圖譜目前已經(jīng)被廣泛應(yīng)用在搜索、推薦、問(wèn)答領(lǐng)域，知識(shí)圖譜逐漸成為人工智能領(lǐng)域不可或缺的一部分。學(xué)術(shù)界對(duì)知識(shí)圖譜的研究從未間斷過(guò)，隨著人工智能的熱潮來(lái)臨，研究知識(shí)圖譜變得越來(lái)越重要。

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

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

本文的主要貢獻(xiàn)可以概括如下：

（1）提出了一種采用主動(dòng)學(xué)習(xí)，使用知識(shí)圖譜內(nèi)部和外部關(guān)系驗(yàn)證，從而不斷完善知識(shí)圖譜的框架。這個(gè)框架結(jié)合了主動(dòng)學(xué)習(xí)，能夠不斷完善知識(shí)圖譜。

（2）在鏈接預(yù)測(cè)階段，提出了增強(qiáng)鏈接預(yù)測(cè)算法（enhance link prediction，ELP）來(lái)預(yù)測(cè)知識(shí)圖譜中最有可能形成鏈接的實(shí)體對(duì)。ELP 算法結(jié)合了Rooted PageRank 算法和實(shí)體聚類算法，能夠有效挖掘知識(shí)圖譜中的圖結(jié)構(gòu)信息和語(yǔ)義信息。利用ELP 算法能夠?qū)崿F(xiàn)主動(dòng)學(xué)習(xí)，從而不斷完善知識(shí)圖譜。

（3）在關(guān)系驗(yàn)證階段，提出一種采用基礎(chǔ)驗(yàn)證加增強(qiáng)驗(yàn)證的方法驗(yàn)證關(guān)系。實(shí)驗(yàn)表明，這種方法能夠有效利用知識(shí)圖譜內(nèi)部數(shù)據(jù)和互聯(lián)網(wǎng)數(shù)據(jù)進(jìn)行關(guān)系驗(yàn)證。

2 相關(guān)工作

本文的相關(guān)工作主要涉及鏈接預(yù)測(cè)任務(wù)、知識(shí)圖譜補(bǔ)全任務(wù)、知識(shí)庫(kù)問(wèn)答系統(tǒng)、實(shí)體抽取、關(guān)系抽取等領(lǐng)域。

在知識(shí)圖譜補(bǔ)全領(lǐng)域已經(jīng)有許多學(xué)者做出了豐富的研究，Lao 等人[1]提出路徑排序算法（PRA），PRA通過(guò)計(jì)算知識(shí)圖譜中節(jié)點(diǎn)間的特征矩陣來(lái)實(shí)現(xiàn)知識(shí)圖譜中的鏈接預(yù)測(cè)。PRA 算法主要分成兩步：（1）使用統(tǒng)計(jì)模型來(lái)尋找兩個(gè)節(jié)點(diǎn)間的潛在路徑。（2）計(jì)算任意兩個(gè)節(jié)點(diǎn)間的隨機(jī)游走概率。Gardner 等人[2]在PRA 的基礎(chǔ)上提出了子圖特征提取算法（SFE）。SFE 將知識(shí)圖譜補(bǔ)全任務(wù)看作是二分類問(wèn)題，通過(guò)判斷三元組是否成立來(lái)實(shí)現(xiàn)知識(shí)圖譜缺失補(bǔ)全。SFE 算法主要分成兩步：（1）提取兩個(gè)節(jié)點(diǎn)的一系列特征。（2）采用二分類分類器對(duì)第一步提取的特征做二分類判別。

Bordes 等人[6]提出了詞嵌入模型TransE。TransE模型將實(shí)體和關(guān)系映射到低維空間中的向量，通過(guò)計(jì)算向量間距離h′+r′-t′來(lái)實(shí)現(xiàn)知識(shí)圖譜缺失補(bǔ)全。Wang 等人[7]在TransE 模型的基礎(chǔ)上提出了TransH 模型，TransH 模型將實(shí)體映射到關(guān)系向量的超平面中，增強(qiáng)向量解釋能力。

Neelakantan 等人[14]提出了Path-RNN 模型來(lái)推理兩個(gè)節(jié)點(diǎn)間的關(guān)系。Path-RNN 將兩個(gè)節(jié)點(diǎn)路徑之間的實(shí)體輸入到循環(huán)神經(jīng)網(wǎng)絡(luò)（recurrent neural network，RNN）中，來(lái)實(shí)現(xiàn)實(shí)體間的關(guān)系推理。Das 等人[15]在Path-RNN 的基礎(chǔ)上提出Single Model，Single Model不僅考慮了節(jié)點(diǎn)間路徑上的實(shí)體，還考慮了路徑上的關(guān)系，增強(qiáng)了神經(jīng)網(wǎng)絡(luò)的表達(dá)能力。

在社交網(wǎng)絡(luò)領(lǐng)域，許多學(xué)者和研究人員對(duì)鏈接預(yù)測(cè)問(wèn)題進(jìn)行了許多研究[19-21]。鏈接預(yù)測(cè)問(wèn)題主要是從圖中篩選出最有可能形成鏈接的k對(duì)節(jié)點(diǎn)對(duì)。解決鏈接預(yù)測(cè)問(wèn)題的方法主要有三類：（1）局部方法；（2）基于路徑的方法；（3）隨機(jī)游走方法。其中局部方法有公共鄰居方法、Jaccard 系數(shù)等，主要的流程是計(jì)算節(jié)點(diǎn)對(duì)之間的相鄰的節(jié)點(diǎn)來(lái)實(shí)現(xiàn)相似度的計(jì)算。基于路徑的方法有最短路徑、Katz 距離等，主要的流程是計(jì)算節(jié)點(diǎn)對(duì)之間的路徑信息來(lái)實(shí)現(xiàn)相似度的計(jì)算。隨機(jī)游走的方法有Rooted PageRank 等，主要的流程是通過(guò)圖中節(jié)點(diǎn)的隨機(jī)游走來(lái)實(shí)現(xiàn)相似度計(jì)算。

主動(dòng)學(xué)習(xí)[22]是一種機(jī)器學(xué)習(xí)技術(shù)，從數(shù)據(jù)中選擇出具有代表性或者能夠有利于學(xué)習(xí)模型快速學(xué)習(xí)的樣本。主動(dòng)學(xué)習(xí)解決的問(wèn)題包含已標(biāo)注的數(shù)據(jù)和未標(biāo)注的數(shù)據(jù)，主動(dòng)學(xué)習(xí)采用算法策略從未標(biāo)注的數(shù)據(jù)中選擇一部分最有利于學(xué)習(xí)模型學(xué)習(xí)的數(shù)據(jù)，交由專家系統(tǒng)進(jìn)行標(biāo)注，標(biāo)注后的數(shù)據(jù)用于學(xué)習(xí)更好的模型。

知識(shí)庫(kù)問(wèn)答系統(tǒng)（knowledge base question answering，KBQA）[23-24]是給定自然語(yǔ)言問(wèn)題，通過(guò)對(duì)自然語(yǔ)言問(wèn)題的語(yǔ)義分析，利用知識(shí)庫(kù)進(jìn)行語(yǔ)義查詢、關(guān)系推理得到答案。KBQA 主要分以下幾個(gè)模塊：?jiǎn)栴}分析、短語(yǔ)映射、消歧、查詢構(gòu)建等。KBQA 主要的應(yīng)用體現(xiàn)在智能問(wèn)答上，同時(shí)也廣泛應(yīng)用于搜索、推薦等領(lǐng)域。

還有許多學(xué)者對(duì)開放世界假設(shè)下的知識(shí)圖譜補(bǔ)全問(wèn)題進(jìn)行了深入的研究[25]。開放世界假設(shè)指知識(shí)圖譜中的關(guān)系代表現(xiàn)實(shí)世界中正確的關(guān)系，知識(shí)圖譜中未知的關(guān)系可能代表現(xiàn)實(shí)世界中錯(cuò)誤的關(guān)系，也可能代表現(xiàn)實(shí)世界中存在的關(guān)系。開放世界假設(shè)對(duì)應(yīng)的是封閉世界假設(shè)，封閉世界假設(shè)是指知識(shí)圖譜中未知的關(guān)系代表現(xiàn)實(shí)世界錯(cuò)誤的關(guān)系。一般知識(shí)圖譜比較完善的時(shí)候，或者是知識(shí)圖譜不完全，但是由于需要通過(guò)知識(shí)圖譜對(duì)現(xiàn)實(shí)世界的問(wèn)題做出回答時(shí)采用封閉世界假設(shè)。

3 知識(shí)圖譜補(bǔ)全方法框架

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

Fig.1 Flowsheet of knowledge graph completion圖1 知識(shí)圖譜補(bǔ)全流程圖

鏈接預(yù)測(cè)模塊主要實(shí)現(xiàn)篩選知識(shí)圖譜中最有可能形成鏈接的k對(duì)節(jié)點(diǎn)對(duì)。鏈接預(yù)測(cè)模塊以知識(shí)圖譜的三元組作為輸入，采用ELP 算法，尋找并篩選整個(gè)知識(shí)圖譜中最有可能形成鏈接的k對(duì)實(shí)體對(duì)。ELP 算法采用實(shí)體聚類算法來(lái)挖掘知識(shí)圖譜中的語(yǔ)義信息，采用Rooted PageRank 算法來(lái)挖掘知識(shí)圖譜中的圖結(jié)構(gòu)信息，經(jīng)過(guò)聯(lián)合篩選來(lái)挖掘知識(shí)圖譜中最有可能形成鏈接的k對(duì)實(shí)體對(duì)。鏈接預(yù)測(cè)模塊輸出實(shí)體對(duì)，由關(guān)系驗(yàn)證模塊進(jìn)行進(jìn)一步的關(guān)系確認(rèn)。關(guān)系驗(yàn)證形成的正確的三元組能夠返回鏈接預(yù)測(cè)模塊進(jìn)行進(jìn)一步的學(xué)習(xí)，使得鏈接預(yù)測(cè)模塊能夠更好地預(yù)測(cè)知識(shí)圖譜中能夠形成鏈接的實(shí)體對(duì)。

關(guān)系驗(yàn)證模塊主要實(shí)現(xiàn)對(duì)實(shí)體對(duì)之間的關(guān)系的驗(yàn)證。關(guān)系驗(yàn)證模塊由基礎(chǔ)驗(yàn)證和增強(qiáng)驗(yàn)證兩部分構(gòu)成。基礎(chǔ)驗(yàn)證采用TransH[7]算法，以知識(shí)圖譜內(nèi)部的數(shù)據(jù)作為訓(xùn)練集，對(duì)鏈接預(yù)測(cè)模塊產(chǎn)生的實(shí)體對(duì)進(jìn)行分類任務(wù)確定實(shí)體對(duì)間的關(guān)系。增強(qiáng)驗(yàn)證模塊通過(guò)爬取、清洗互聯(lián)網(wǎng)結(jié)構(gòu)化數(shù)據(jù)，采用多源數(shù)據(jù)關(guān)系驗(yàn)證和領(lǐng)域?qū)＜业娜藱C(jī)交互方式來(lái)實(shí)現(xiàn)對(duì)基礎(chǔ)驗(yàn)證輸出的三元組集合的進(jìn)一步驗(yàn)證。關(guān)系驗(yàn)證模塊輸出正確的三元組，輸出的三元組返回知識(shí)圖譜補(bǔ)全完善知識(shí)圖譜。正確的三元組還會(huì)返回鏈接預(yù)測(cè)模塊，增強(qiáng)鏈接預(yù)測(cè)模塊的鏈接預(yù)測(cè)效果。

4 鏈接預(yù)測(cè)

鏈接預(yù)測(cè)模塊主要的任務(wù)是從知識(shí)圖譜中篩選出前k對(duì)最有可能形成鏈接的實(shí)體對(duì)。本章提出了增強(qiáng)鏈接預(yù)測(cè)算法（ELP），ELP 算法結(jié)合了Rooted PageRank 算法和實(shí)體聚類算法進(jìn)行聯(lián)合篩選，使得篩選出的候選實(shí)體對(duì)更有可能形成鏈接。Rooted PageRank 算法能夠挖掘知識(shí)圖譜中的圖結(jié)構(gòu)信息，篩選可能形成鏈接的實(shí)體對(duì)。而實(shí)體聚類算法能夠挖掘知識(shí)圖譜中的語(yǔ)義信息，排除不可能形成鏈接的實(shí)體對(duì)。ELP 中算法中的Rooted PageRank算法和實(shí)體聚類算法是相對(duì)獨(dú)立的兩個(gè)子模塊，通過(guò)該兩個(gè)模塊的聯(lián)合篩選，能夠篩選出知識(shí)圖譜中最有可能形成鏈接的實(shí)體對(duì)。由于ELP 算法結(jié)合了知識(shí)圖譜中的語(yǔ)義信息和圖結(jié)構(gòu)信息，因此ELP 算法信息挖掘能力更強(qiáng)，能夠通過(guò)主動(dòng)學(xué)習(xí)增強(qiáng)鏈接預(yù)測(cè)的性能。將在實(shí)驗(yàn)中證明本章提出的ELP 算法效果優(yōu)于Rooted PageRank 算法，并且具有主動(dòng)學(xué)習(xí)能力。本文分知識(shí)圖譜實(shí)體聚類和Rooted PageRank算法兩部分來(lái)介紹ELP 算法。

4.1 實(shí)體聚類算法

本節(jié)提出一種知識(shí)圖譜實(shí)體聚類算法來(lái)挖掘知識(shí)圖譜中的語(yǔ)義信息。在知識(shí)圖譜中，節(jié)點(diǎn)和邊分別代表實(shí)體和關(guān)系，節(jié)點(diǎn)和邊都是有各自的語(yǔ)義的。本節(jié)提出的實(shí)體聚類方法能夠快速篩選出知識(shí)圖譜中的實(shí)體類。篩選出的實(shí)體類可以用于ELP 算法的聯(lián)合篩選。它主要分成兩個(gè)階段：（1）實(shí)體類的初始化；（2）實(shí)體類的合并。

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

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

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

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

算法1初始化實(shí)體類

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

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

任意兩個(gè)相似度超過(guò)閾值τ的實(shí)體類需要進(jìn)行合并，不斷迭代直到?jīng)]有兩個(gè)實(shí)體類相似度超過(guò)閾值τ。

由于實(shí)體類過(guò)程中的每次迭代需要計(jì)算兩兩實(shí)體類間的相似度，當(dāng)實(shí)體類較多時(shí)候，每次迭代需要較大的時(shí)間開銷，因此采用貪心策略來(lái)加速實(shí)體類的合并。實(shí)體類的合并算法如下：

（1）隨機(jī)選取一個(gè)集合，計(jì)算其他集合與當(dāng)前集合的相似度。

（2）選取一個(gè)與當(dāng)前集合相似度最大的集合，如果相似度超過(guò)閾值τ，則將這兩個(gè)集合進(jìn)行合并，并將新的集合作為當(dāng)前集合；如果沒(méi)有超過(guò)閾值τ，則將當(dāng)前集合標(biāo)記為終態(tài)，以后不參與集合合并。

（3）重復(fù)前兩步直到所有集合都為終態(tài)。

算法2實(shí)體類的合并

Fig.3 Diagram of entity class consolidation process圖3 實(shí)體類合并過(guò)程示意圖

4.2 Rooted PageRank 算法

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

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

4.3 ELP 算法

前文所介紹的Rooted PageRank 算法能夠通過(guò)知識(shí)圖譜的圖結(jié)構(gòu)，從知識(shí)圖譜中發(fā)現(xiàn)最有可能形成鏈接的k對(duì)實(shí)體對(duì)。而實(shí)體聚類算法則是挖掘知識(shí)圖譜中的語(yǔ)義信息對(duì)知識(shí)圖譜中的實(shí)體進(jìn)行聚類。本節(jié)將提出ELP 算法，聯(lián)合Rooted PageRank算法和實(shí)體聚類算法對(duì)實(shí)體對(duì)進(jìn)行篩選。

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

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

ELP 算法采用Rooted PageRank 算法和實(shí)體聚類算法聯(lián)合篩選進(jìn)行鏈接預(yù)測(cè)。既考慮了知識(shí)圖譜中的圖結(jié)構(gòu)信息，又考慮了知識(shí)圖譜的語(yǔ)義信息。通過(guò)ELP 算法篩選出的最有可能形成鏈接的k對(duì)實(shí)體對(duì)更具有代表性，可獲得優(yōu)于Rooted PageRank 算法的效果。

另外，ELP 算法具有主動(dòng)學(xué)習(xí)能力。對(duì)于鏈接預(yù)測(cè)問(wèn)題，將整個(gè)知識(shí)圖譜看作是數(shù)據(jù)集Ud，所有在知識(shí)圖譜中有鏈接的數(shù)據(jù)看作是訓(xùn)練集Us，所有不在知識(shí)圖譜中的鏈接看作是測(cè)試集Ut。ELP 算法每次從測(cè)試集Ut選出一定數(shù)量的樣本，通過(guò)關(guān)系驗(yàn)證模塊組合成正確的三元組加入訓(xùn)練集Us，組成新的訓(xùn)練集Us′和新的測(cè)試集Ut′。在實(shí)驗(yàn)環(huán)節(jié)，驗(yàn)證了對(duì)于新的訓(xùn)練集Us′，ELP 算法的鏈接預(yù)測(cè)效果比原訓(xùn)練集Us要好。這說(shuō)明ELP 算法具有主動(dòng)學(xué)習(xí)能力，對(duì)于更完善的數(shù)據(jù)集，ELP 算法有更強(qiáng)的潛在信息挖掘能力。

5 關(guān)系驗(yàn)證

關(guān)系驗(yàn)證模塊驗(yàn)證鏈接預(yù)測(cè)輸出的實(shí)體對(duì)的關(guān)系。對(duì)于鏈接預(yù)測(cè)輸出的任一實(shí)體對(duì)，關(guān)系驗(yàn)證模塊需要找到對(duì)應(yīng)正確的三元組，如果不存在關(guān)系，則有r=NULL。本章采用基礎(chǔ)驗(yàn)證和增強(qiáng)驗(yàn)證兩個(gè)模塊解決關(guān)系驗(yàn)證問(wèn)題。在基礎(chǔ)驗(yàn)證模塊中，將關(guān)系驗(yàn)證問(wèn)題看作是關(guān)系分類問(wèn)題，采用TransH 算法對(duì)鏈接預(yù)測(cè)模塊輸出的實(shí)體對(duì)進(jìn)行分類任務(wù)。在增強(qiáng)驗(yàn)證模塊，通過(guò)爬蟲技術(shù)爬取互聯(lián)網(wǎng)上結(jié)構(gòu)化數(shù)據(jù)信息，采用多源數(shù)據(jù)關(guān)系驗(yàn)證和領(lǐng)域?qū)＜胰藱C(jī)交互方式來(lái)實(shí)現(xiàn)增強(qiáng)驗(yàn)證。

5.1 基礎(chǔ)驗(yàn)證

在基礎(chǔ)驗(yàn)證模塊，本節(jié)只利用知識(shí)圖譜內(nèi)部的數(shù)據(jù)，將關(guān)系驗(yàn)證看作是分類問(wèn)題。對(duì)于任一實(shí)體對(duì)，需要對(duì)所有r∈R 做二分類判別。即是對(duì)于所有的r∈R，判斷三元組是否成立。關(guān)系驗(yàn)證也可以看成是多分類任務(wù)，即對(duì)于實(shí)體對(duì)，分類選擇出正確的關(guān)系r，形成正確的三元組。

Bordes 等人[6]提出詞嵌入模型TransE，TransE 模型將知識(shí)圖譜中的實(shí)體和關(guān)系都用數(shù)學(xué)空間的向量來(lái)表示。因此，對(duì)于三元組，可以通過(guò)計(jì)算頭實(shí)體h和尾實(shí)體t的向量距離來(lái)實(shí)現(xiàn)關(guān)系驗(yàn)證。圖4展現(xiàn)了三元組在數(shù)學(xué)空間中的關(guān)系。

Fig.4 Math space of TransE圖4 TransE 模型數(shù)學(xué)空間

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

其中，γ是超參數(shù)。實(shí)體向量和關(guān)系向量可以通過(guò)訓(xùn)練目標(biāo)函數(shù)L來(lái)得到。

Wang等人[7]在TransE模型的基礎(chǔ)上提出了TransH模型，TransH 模型在TransE 模型的基礎(chǔ)上把實(shí)體向量和關(guān)系向量映射到超平面空間wr。圖5 展現(xiàn)了TransH 模型中的三元組在數(shù)學(xué)空間中的關(guān)系。TransH 模型的距離函數(shù)和目標(biāo)函數(shù)如下定義：

Fig.5 Math space of TransH圖5 TransH 模型數(shù)學(xué)空間

模型訓(xùn)練開始時(shí)，一般用隨機(jī)值來(lái)初始化實(shí)體向量和關(guān)系向量。在訓(xùn)練過(guò)程中，為了節(jié)省計(jì)算資源以及加快訓(xùn)練速度，研究人員往往采用隨機(jī)梯度下降方法SGD（stochastic gradient descent）來(lái)實(shí)現(xiàn)模型的訓(xùn)練，采用L2正則化方法來(lái)避免模型對(duì)訓(xùn)練數(shù)據(jù)的過(guò)擬合。

5.2 增強(qiáng)驗(yàn)證

通過(guò)基礎(chǔ)驗(yàn)證后的三元組仍存在許多錯(cuò)誤，造成這些錯(cuò)誤的原因主要是基礎(chǔ)驗(yàn)證只利用了知識(shí)圖譜內(nèi)部的數(shù)據(jù)信息，然而現(xiàn)實(shí)世界中大多數(shù)知識(shí)圖譜包含的知識(shí)信息較為有限。隨著互聯(lián)網(wǎng)的進(jìn)一步發(fā)展，諸如百度百科、互動(dòng)百科、維基百科等包含了大量的知識(shí)信息。因此，本文提出利用外部數(shù)據(jù)進(jìn)行增強(qiáng)驗(yàn)證，增強(qiáng)驗(yàn)證模塊包括三部分：（1）多源數(shù)據(jù)的采集與清洗；（2）多源數(shù)據(jù)的關(guān)系驗(yàn)證；（3）領(lǐng)域?qū)＜业娜藱C(jī)交互驗(yàn)證。

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

其中，Ei={ei1,ei2,…,eim}代表數(shù)據(jù)倉(cāng)庫(kù)KBi中的實(shí)體集合，Ri={ri1,ri2,…,rim}代表數(shù)據(jù)倉(cāng)庫(kù)KBi中的關(guān)系集合，Oi代表數(shù)據(jù)倉(cāng)庫(kù)KBi中的三元組集合。增強(qiáng)驗(yàn)證模塊如圖6。

數(shù)據(jù)采集部分采用網(wǎng)絡(luò)爬蟲技術(shù)對(duì)互聯(lián)網(wǎng)上的網(wǎng)站進(jìn)行數(shù)據(jù)爬取。許多網(wǎng)站針對(duì)開發(fā)者開放了API接口與Dump 文件等。互聯(lián)網(wǎng)上的數(shù)據(jù)如圖7 所示，一般由文本數(shù)據(jù)和結(jié)構(gòu)化Infobox 數(shù)據(jù)構(gòu)成。增強(qiáng)驗(yàn)證模塊主要采用互聯(lián)網(wǎng)的結(jié)構(gòu)化數(shù)據(jù)進(jìn)行關(guān)系驗(yàn)證。

Fig.6 Flowsheet of enhanced verification圖6 增強(qiáng)驗(yàn)證流程圖

Fig.7 Diagram of Wiki Web page圖7 Wiki網(wǎng)頁(yè)數(shù)據(jù)示意圖

爬取后的數(shù)據(jù)需要進(jìn)行數(shù)據(jù)清洗和格式規(guī)范化，包含以下幾點(diǎn)：（1）剔除無(wú)關(guān)字符。（2）關(guān)系統(tǒng)一化。在不同數(shù)據(jù)源中，關(guān)系描述可能不一致，因此需要將同一關(guān)系的不同描述統(tǒng)一化。（3）實(shí)體消歧與統(tǒng)一化。在不同數(shù)據(jù)源中，實(shí)體的描述可能并不一致，可能出現(xiàn)縮寫名等，因此需要對(duì)實(shí)體進(jìn)行統(tǒng)一化。經(jīng)過(guò)清洗與規(guī)范化后的數(shù)據(jù)會(huì)存入數(shù)據(jù)倉(cāng)庫(kù)中，進(jìn)行多源數(shù)據(jù)關(guān)系驗(yàn)證。

多源數(shù)據(jù)關(guān)系驗(yàn)證以基礎(chǔ)驗(yàn)證輸出的三元組集合Op、知識(shí)圖譜G和數(shù)據(jù)倉(cāng)庫(kù)KB為輸入，輸出置信度集合Cp。對(duì)于任意三元組o=∈Op，與數(shù)據(jù)倉(cāng)庫(kù)KBi進(jìn)行數(shù)據(jù)對(duì)齊需要考慮如下兩點(diǎn)：（1）實(shí)體h在知識(shí)圖譜G中描述的實(shí)體和在數(shù)據(jù)倉(cāng)庫(kù)KBi中描述的實(shí)體是不是同一個(gè)實(shí)體。（2）數(shù)據(jù)倉(cāng)庫(kù)KBi是否存在三元組o=。

式（10）描述了三元組關(guān)系o與數(shù)據(jù)倉(cāng)庫(kù)KBi之間的對(duì)應(yīng)關(guān)系。

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

多源數(shù)據(jù)關(guān)系驗(yàn)證輸出三元組集合和置信度，經(jīng)過(guò)領(lǐng)域?qū)＜胰藱C(jī)交互驗(yàn)證后可以輸出正確的三元組集合。對(duì)于置信度較低的三元組，領(lǐng)域?qū)＜乙揽孔陨淼膶I(yè)知識(shí)來(lái)決定三元組是否正確。領(lǐng)域?qū)＜胰藱C(jī)交互驗(yàn)證的形式化定義如下：

本節(jié)提出的增強(qiáng)驗(yàn)證包含多源數(shù)據(jù)采集與清洗、多源關(guān)系驗(yàn)證、領(lǐng)域?qū)＜胰藱C(jī)交互驗(yàn)證三部分。增強(qiáng)驗(yàn)證模塊能夠有效地驗(yàn)證基礎(chǔ)驗(yàn)證輸出的三元組集合，形成更加正確的三元組集合。

6 實(shí)驗(yàn)結(jié)果

本文的實(shí)驗(yàn)環(huán)境是在一臺(tái)小型服務(wù)器上運(yùn)行，處理器為Intel?Xeon?Silver 4114 CPU@2.2 GHz，內(nèi)存為100 GB，操作系統(tǒng)為Ubuntu 18.04.1 LTS Server。使用的語(yǔ)言為Java 和Python，Python 主要用于鏈接預(yù)測(cè)模塊篩選實(shí)體對(duì)，Java 主要用于關(guān)系驗(yàn)證模塊驗(yàn)證實(shí)體對(duì)的關(guān)系。

實(shí)驗(yàn)數(shù)據(jù)方面，本文采用公開數(shù)據(jù)集Freebase 和DBpedia。Freebase 數(shù)據(jù)集和DBpedia 是在知識(shí)圖譜領(lǐng)域常用的數(shù)據(jù)集，被許多科研學(xué)者采用。由于Freebase 數(shù)據(jù)集和DBpea 數(shù)據(jù)集非常龐大，為了方便起見(jiàn)，本文對(duì)Freebase 數(shù)據(jù)pedia 數(shù)據(jù)集進(jìn)行了采樣，選取了一定數(shù)量的實(shí)體、關(guān)系作為實(shí)驗(yàn)的真值數(shù)據(jù)集。真值數(shù)據(jù)集如表1 所示。

Table 1 Truth dataset表1 真值數(shù)據(jù)集

從真值數(shù)據(jù)集隨機(jī)采樣55%、60%、65%、70%、75%、80%、85%、85%、90%、95%的三元組，構(gòu)成本文的缺失知識(shí)圖譜。剩余的三元組作為需要補(bǔ)全完善的缺失值。

6.1 鏈接預(yù)測(cè)實(shí)驗(yàn)結(jié)果

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

從圖8 和圖9 中分析發(fā)現(xiàn)在DBpedia 和Freebase兩個(gè)數(shù)據(jù)集上，ELP 算法效果均好于RPR 算法。對(duì)于前2 000 對(duì)實(shí)體對(duì)，應(yīng)用了CommonNeighbours、Katz、SimRank 算法[19]進(jìn)行對(duì)比測(cè)試。實(shí)驗(yàn)結(jié)果如表3 所示。可以看到在DBpedia 和Freebase 數(shù)據(jù)集上，ELP 算法效果均優(yōu)于其他算法。這兩個(gè)實(shí)驗(yàn)證明了本文提出的ELP 算法的有效性，說(shuō)明本文算法相較于其他算法而言，能較為準(zhǔn)確地篩選知識(shí)圖譜中最有可能形成鏈接的前k對(duì)實(shí)體對(duì)。

ELP 算法不僅能夠很好地進(jìn)行鏈接預(yù)測(cè)，還具有主動(dòng)學(xué)習(xí)能力，隨著知識(shí)圖譜的不斷完善，ELP 算法能夠更好地預(yù)測(cè)知識(shí)圖譜中需要進(jìn)行鏈接的實(shí)體對(duì)。然而由于知識(shí)圖譜越來(lái)越完善的同時(shí)，需要補(bǔ)全的正確三元組越來(lái)越少，用前k對(duì)實(shí)體對(duì)中正確的實(shí)體對(duì)百分比來(lái)評(píng)價(jià)鏈接預(yù)測(cè)的主動(dòng)學(xué)習(xí)能力并不公平。定義了如下函數(shù)來(lái)評(píng)價(jià)在知識(shí)圖譜更新過(guò)程中算法的鏈接預(yù)測(cè)能力。

Table 2 Accuracy comparison of RPR and ELP表2 RPR 與ELP 準(zhǔn)確率對(duì)比

Fig.8 Experiment comparison between RPR and ELP in DBpedia圖8 DBpedia 數(shù)據(jù)集RPR 與ELP 實(shí)驗(yàn)對(duì)比

Fig.9 Experiment comparison between RPR and ELP in Freebase圖9 Freebase數(shù)據(jù)集RPR 與ELP 實(shí)驗(yàn)對(duì)比

Table 3 Accuracy comparison of ELP algorithm and others@2 000表3 ELP 算法與其他算法準(zhǔn)確率對(duì)比結(jié)果@2 000

其中，Dt表示當(dāng)前知識(shí)圖譜剩余還未補(bǔ)全的正確實(shí)體對(duì)總數(shù)，hit代表鏈接預(yù)測(cè)器篩選出的前k對(duì)實(shí)體對(duì)中正確的實(shí)體對(duì)個(gè)數(shù)。相比較于前k對(duì)實(shí)體對(duì)中正確實(shí)體對(duì)的百分比，Yscore考慮了知識(shí)圖譜中剩余還未補(bǔ)全的實(shí)體對(duì)總數(shù)，能較好地評(píng)價(jià)算法的主動(dòng)學(xué)習(xí)的能力。本文在DBpedia 數(shù)據(jù)集和Freebase 數(shù)據(jù)集上測(cè)試了各個(gè)算法的實(shí)驗(yàn)結(jié)果，如表4 所示。通過(guò)圖10 和圖11 可以看出，隨著知識(shí)圖譜的不斷完善，Yscore結(jié)果變得越來(lái)越高。這說(shuō)明了隨著知識(shí)圖譜的不斷完善，ELP 算法的鏈接預(yù)測(cè)能力越來(lái)越強(qiáng)。因此，ELP 算法具有主動(dòng)學(xué)習(xí)能力。

以上的實(shí)驗(yàn)以及分析驗(yàn)證了如下兩點(diǎn)：（1）本文提出的ELP 算法能夠挖掘知識(shí)圖譜中的圖結(jié)構(gòu)信息和語(yǔ)義信息，效果好于Rooted PageRank 算法。（2）本文提出的ELP 算法具有主動(dòng)學(xué)習(xí)能力，隨著知識(shí)圖譜的完善程度越高，ELP 算法的信息挖掘能力越強(qiáng)。

6.2 關(guān)系驗(yàn)證實(shí)驗(yàn)結(jié)果

關(guān)系驗(yàn)證模塊采用TransH 模型對(duì)鏈接預(yù)測(cè)模塊輸出的候選實(shí)體對(duì)進(jìn)行關(guān)系驗(yàn)證。首先對(duì)ELP 算法鏈接預(yù)測(cè)得到的前k對(duì)實(shí)體對(duì)進(jìn)行關(guān)系擴(kuò)展，對(duì)于鏈接預(yù)測(cè)輸出中的正確的實(shí)體對(duì)，需要擴(kuò)展正確的關(guān)系；對(duì)于鏈接預(yù)測(cè)輸出中的錯(cuò)誤的實(shí)體對(duì)，則隨機(jī)擴(kuò)展知識(shí)圖譜中的任一關(guān)系。

對(duì)于鏈接預(yù)測(cè)模塊輸出的前1 000 對(duì)實(shí)體對(duì)和前2 000 對(duì)實(shí)體對(duì)，基礎(chǔ)驗(yàn)證模塊采用TransH 模型進(jìn)行二分類。基礎(chǔ)驗(yàn)證模塊將預(yù)測(cè)的結(jié)果和真值數(shù)據(jù)集進(jìn)行比較，并計(jì)算F1值。F1值的計(jì)算方式如下:

其中，P代表精確率，R代表召回率。F1指標(biāo)能較好地衡量二分類分類器的性能。關(guān)系驗(yàn)證的結(jié)果如表5 所示。

Table 4 Yscore results of active learning in link prediction module表4 鏈接預(yù)測(cè)模塊主動(dòng)學(xué)習(xí)Yscore 結(jié)果

Fig.10 Yscore results of ELP algorithm in DBpedia圖10 DBpedia 數(shù)據(jù)集ELP 算法Yscore 結(jié)果

Fig.11 Yscore results of ELP algorithm in Freebase圖11 Freebase數(shù)據(jù)集ELP 算法Yscore 結(jié)果圖

Table 5 F1 results of relationship verification表5 關(guān)系驗(yàn)證F1 指標(biāo)實(shí)驗(yàn)結(jié)果

表5 證明了基礎(chǔ)驗(yàn)證模塊能夠較好地驗(yàn)證鏈接預(yù)測(cè)輸出的實(shí)體對(duì)之間的關(guān)系，基礎(chǔ)驗(yàn)證模塊的F1指標(biāo)都集中在0.5～0.8 之間。

爬取Freebase 有關(guān)的實(shí)體75 043 個(gè)，以及它們有關(guān)聯(lián)的三元組集合。然后以0.25 的概率采樣其中的三元組集合，構(gòu)建了5 個(gè)與Freebase 有關(guān)的多源數(shù)據(jù)倉(cāng)庫(kù)。同樣地，爬取了與DBpedia 有關(guān)的實(shí)體14 656個(gè)，以及與它們有關(guān)聯(lián)的三元組集合。然后以0.3 的概率采樣其中的三元組集合，構(gòu)建了5 個(gè)與DBpedia有關(guān)的多源數(shù)據(jù)倉(cāng)庫(kù)。基礎(chǔ)驗(yàn)證標(biāo)記為正確的三元組將作為多源數(shù)據(jù)關(guān)系驗(yàn)證的輸入，計(jì)算對(duì)應(yīng)的F1指標(biāo)，結(jié)果如表6 所示。從實(shí)驗(yàn)結(jié)果可以看出采用較為正確的數(shù)據(jù)源進(jìn)行多源關(guān)系驗(yàn)證，能得到較好的效果。

對(duì)于多源關(guān)系驗(yàn)證中置信度較低的三元組，增強(qiáng)驗(yàn)證模塊采用領(lǐng)域?qū)＜胰藱C(jī)驗(yàn)證進(jìn)一步確定三元組關(guān)系，可以得到正確的三元組。經(jīng)過(guò)增強(qiáng)驗(yàn)證后的三元組較為正確，最后采用正確的三元組更新知識(shí)圖譜。

6.3 各環(huán)節(jié)時(shí)間實(shí)驗(yàn)結(jié)果

本文測(cè)試了本文提出的基于主動(dòng)學(xué)習(xí)的知識(shí)圖譜補(bǔ)全框架的各個(gè)環(huán)節(jié)的時(shí)間消耗。框架包含四個(gè)環(huán)節(jié)：（1）實(shí)體聚類算法；（2）RPR 算法；（3）ELP 算法；（4）TransH 模型訓(xùn)練。結(jié)果如表7 所示，從表7 中可以看出主要時(shí)間開銷在關(guān)系驗(yàn)證模塊中，鏈接預(yù)測(cè)模塊的時(shí)間開銷相對(duì)不高。而本文提出的對(duì)于知識(shí)圖譜實(shí)體聚類方法的時(shí)間開銷相對(duì)于RPR 算法要小很多。總的ELP 算法的時(shí)間開銷相對(duì)占比不大。

7 結(jié)論

本文提出了一種基于主動(dòng)學(xué)習(xí)的知識(shí)圖譜補(bǔ)全框架來(lái)實(shí)現(xiàn)對(duì)缺失知識(shí)圖譜的不斷更新完善。知識(shí)圖譜補(bǔ)全框架由不斷更新的知識(shí)圖譜、鏈接預(yù)測(cè)模塊、關(guān)系驗(yàn)證模塊構(gòu)成。在鏈接預(yù)測(cè)模塊中，提出的ELP 算法充分考慮了知識(shí)圖譜中的語(yǔ)義信息和圖結(jié)構(gòu)信息，能準(zhǔn)確實(shí)現(xiàn)對(duì)知識(shí)圖譜的鏈接預(yù)測(cè)，同時(shí)ELP 算法具有主動(dòng)學(xué)習(xí)能力，能隨著知識(shí)圖譜的不斷完善，可以更好地進(jìn)行鏈接預(yù)測(cè)。在實(shí)驗(yàn)中，通過(guò)與前人的RPR、SimRank、CommonNeighbours、Katz 等方法進(jìn)行對(duì)比，證明了ELP 算法的有效性。同時(shí)，也通過(guò)實(shí)驗(yàn)證明了ELP 算法的主動(dòng)學(xué)習(xí)能力。關(guān)系驗(yàn)證模塊采用基礎(chǔ)驗(yàn)證和增強(qiáng)驗(yàn)證相結(jié)合的方法進(jìn)行關(guān)系驗(yàn)證，這種關(guān)系驗(yàn)證方式能夠結(jié)合知識(shí)圖譜內(nèi)部數(shù)據(jù)和互聯(lián)網(wǎng)結(jié)構(gòu)化數(shù)據(jù)，以及領(lǐng)域?qū)＜胰藱C(jī)交互標(biāo)注，能夠驗(yàn)證三元組的正確性。通過(guò)實(shí)驗(yàn)驗(yàn)證了關(guān)系驗(yàn)證模塊的有效性。關(guān)系驗(yàn)證模塊能驗(yàn)證鏈接預(yù)測(cè)模塊輸出的實(shí)體對(duì)之間的關(guān)系，形成正確的三元組，從而更新知識(shí)圖譜。

Table 6 F1 results of multi-source data relationship verification表6 多源數(shù)據(jù)關(guān)系驗(yàn)證F1 實(shí)驗(yàn)結(jié)果

Table 7 Time comparison of each step表7 各環(huán)節(jié)時(shí)間對(duì)比