盧 菁,陳婉璐,劉 叢

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

1 引 言

知識(shí)圖譜最初由谷歌為提高搜索引擎的能力而提出,旨在描述現(xiàn)實(shí)世界中存在的實(shí)體以及實(shí)體之間的關(guān)系.隨著人工智能技術(shù)的發(fā)展,知識(shí)圖譜得到了飛速發(fā)展,并已被廣泛應(yīng)用在智能搜索、智能問(wèn)答、個(gè)性化推薦等領(lǐng)域.隨著知識(shí)爆炸式增長(zhǎng),現(xiàn)存的知識(shí)圖譜面臨著知識(shí)更新頻繁的挑戰(zhàn)[1],大量知識(shí)同時(shí)更新,若不進(jìn)行篩選則很容易將錯(cuò)誤信息插入知識(shí)圖譜.

當(dāng)前大多數(shù)知識(shí)圖譜的更新都是由知識(shí)圖譜方發(fā)起主動(dòng)更新,分為全局更新和局部更新:1)全局更新.文獻(xiàn)[2]根據(jù)數(shù)據(jù)流改良了更新方案,每產(chǎn)生一個(gè)更新就生成一條記錄主動(dòng)推送更新,減少更新的量從而一定程度上減少錯(cuò)誤,但提供更新流的數(shù)據(jù)源較少,被動(dòng)更新往往難以實(shí)施;2)局部更新.文獻(xiàn)[3]提出關(guān)注有限的采樣觀測(cè)頻率從而實(shí)現(xiàn)主動(dòng)局部更新,這種方法通過(guò)減少更新的量對(duì)篩選的準(zhǔn)確率略微提升,但知識(shí)更新頻率時(shí)常比估計(jì)的頻率高,導(dǎo)致更新的準(zhǔn)確率較低;文獻(xiàn)[4]進(jìn)一步提出使用時(shí)間約束進(jìn)行查錯(cuò),但其適用范圍僅限于時(shí)間敏感的數(shù)據(jù);文獻(xiàn)[5]提出如果知識(shí)圖中已經(jīng)存在該實(shí)體,將該實(shí)體在知識(shí)圖中的所有信息全部替換,如果不存在,則將信息抽取后直接嵌入知識(shí)圖中,雖然能避免沖突但是直接取代過(guò)期知識(shí)的做法不夠準(zhǔn)確;文獻(xiàn)[6]用三元組分類(lèi)方法計(jì)算三元組知識(shí)的置信度,從而判斷三元組是否為真,若為真則加入,該方案僅利用基于相似度的評(píng)分標(biāo)準(zhǔn)來(lái)判斷語(yǔ)義是否正確,判斷標(biāo)準(zhǔn)單一且不能識(shí)別出更精細(xì)的語(yǔ)義,更不能判斷語(yǔ)義值是否正確,在篩選錯(cuò)的知識(shí)上具有一定局限,不能保證準(zhǔn)確率;文獻(xiàn)[7]進(jìn)一步基于規(guī)則引導(dǎo),利用關(guān)系間的聯(lián)系對(duì)信息的置信度進(jìn)行估算以篩選錯(cuò)誤知識(shí);文獻(xiàn)[8]通過(guò)改進(jìn)目標(biāo)函數(shù)并提出雙模函數(shù)逼近算法來(lái)達(dá)到目標(biāo)函數(shù)最大化,但會(huì)增加原先目標(biāo)函數(shù)求解的復(fù)雜度;文獻(xiàn)[9]根據(jù)挖掘的目標(biāo)函數(shù)的貪婪性使用枚舉方法對(duì)模式集分類(lèi),枚舉的方案會(huì)產(chǎn)生遺漏而不能保證過(guò)濾的準(zhǔn)確性.當(dāng)大量知識(shí)同時(shí)比對(duì)時(shí),實(shí)體類(lèi)型的繁多及實(shí)體間關(guān)系的復(fù)雜性進(jìn)一步加劇了篩選的難度.

綜上所述知識(shí)圖譜自動(dòng)更新面臨著知識(shí)數(shù)量大且更新準(zhǔn)確率低的問(wèn)題,而知識(shí)圖譜中的知識(shí)往往是有規(guī)律的,不同類(lèi)型的知識(shí)都會(huì)遵循各自固有的形式[10],如果將這些特征挖掘出來(lái),利用特征信息構(gòu)造圖模式,對(duì)所抽取知識(shí)進(jìn)行正確性和完備性檢查,則可以避免將錯(cuò)誤的知識(shí)插入圖譜,提高知識(shí)圖譜的質(zhì)量.

圖1是一個(gè)演員出演電影的實(shí)例.從Web中抽取新的知識(shí)<“劉青云”,“出演”,“拆彈專(zhuān)家”>并自動(dòng)插入知識(shí)圖譜時(shí)通常不檢查所抽取的知識(shí)是否包含演員拍攝的時(shí)間,從而造成錯(cuò)誤.若能根據(jù)此類(lèi)知識(shí)的特征構(gòu)造包含時(shí)間特征信息的標(biāo)準(zhǔn)模式,并將新知識(shí)與標(biāo)準(zhǔn)模式進(jìn)行比對(duì),符合標(biāo)準(zhǔn)模式的知識(shí)將被插入知識(shí)圖譜中,若缺乏相應(yīng)信息,則抽取缺乏的特征信息后再進(jìn)行插入,則能提高知識(shí)更新的準(zhǔn)確率.

圖1 圖模式實(shí)例

本文提出一種基于標(biāo)準(zhǔn)模式挖掘的知識(shí)圖譜更新方法:先挖掘知識(shí)圖中的頻繁模式,然后基于Giraph模型求解標(biāo)準(zhǔn)模式,最后用標(biāo)準(zhǔn)模式進(jìn)行圖模擬匹配檢查,符合模式條件的知識(shí)將會(huì)被篩選出并插入;當(dāng)大量知識(shí)同時(shí)更新時(shí),將標(biāo)準(zhǔn)模式向量化并計(jì)算新知識(shí)與標(biāo)準(zhǔn)模式之間的向量距離,符合距離閾值條件的知識(shí)將被篩出并插入,從而減少知識(shí)圖譜更新時(shí)的錯(cuò)誤,提高知識(shí)篩選的準(zhǔn)確率.

本文的主要貢獻(xiàn)包括:

1)針對(duì)知識(shí)圖譜中模式挖掘算法subTopk的缺陷,提出了標(biāo)準(zhǔn)模式的概念和SPM標(biāo)準(zhǔn)模式優(yōu)化挖掘算法,優(yōu)化了貪心增益計(jì)算,提高了標(biāo)準(zhǔn)模式挖掘的準(zhǔn)確度.

2)利用圖模擬的方法,用標(biāo)準(zhǔn)模式匹配待插入知識(shí),符合標(biāo)準(zhǔn)模式的知識(shí)將被篩選出,提高更新知識(shí)的準(zhǔn)確率.

3)當(dāng)大量知識(shí)同時(shí)更新時(shí),借用TransD中將事實(shí)投影到不同領(lǐng)域的思想,將標(biāo)準(zhǔn)模式和待檢查知識(shí)投影到不同空間,計(jì)算知識(shí)向量與標(biāo)準(zhǔn)模式向量間距離,符合閾值條件的知識(shí)將被篩選并插入,從而加快比對(duì)的速度,提高知識(shí)更新的效率.

4)在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),驗(yàn)證了本文提出方法的有效性,與現(xiàn)有的方法比較展現(xiàn)了該方法具有更好的精確率、召回率和F1值.

2 相關(guān)定義及方法流程

2.1 相關(guān)定義及符號(hào)

定義1.知識(shí)圖:知識(shí)圖表示為G=〈V,E,L〉,其中V是節(jié)點(diǎn)集,?v∈V表示節(jié)點(diǎn)集中的任意點(diǎn);E?V×V是邊集,?e∈E表示邊集中的任意邊;L是類(lèi)型集,表示節(jié)點(diǎn)或者邊的類(lèi)型,即L(v)是節(jié)點(diǎn)的實(shí)體類(lèi)型,L(e)是邊的標(biāo)簽,表示兩個(gè)節(jié)點(diǎn)之間的關(guān)系類(lèi)型.

定義2.圖模式:圖模式表示為P=〈VP,EP,LP〉,其中VP是模式節(jié)點(diǎn)集,EP是關(guān)系邊集,LP是類(lèi)型集.

定義3.模式覆蓋度:給定知識(shí)圖G和圖模式P,滿(mǎn)足二元關(guān)系R(P,G)的節(jié)點(diǎn)v和節(jié)點(diǎn)間的邊l構(gòu)成覆蓋子圖GP,模式覆蓋度為該子圖中節(jié)點(diǎn)和邊的總數(shù)與知識(shí)圖G的節(jié)點(diǎn)和邊的總數(shù)的比,記為cov(GP,G),表示如公式(1)所示:

cov(GP,G)=|GP|/|G|

(1)

其中|GP|和|G|均表示圖的大小,分別為覆蓋子圖GP和知識(shí)圖G中節(jié)點(diǎn)和邊的總數(shù).

定義4.頻繁模式:在給定知識(shí)圖上,頻繁模式集為模式覆蓋度超過(guò)給定閾值的所有模式的集合,給定的閾值被稱(chēng)為最小模式覆蓋度.閾值根據(jù)需求設(shè)定,如設(shè)定為0.5,那么cov(GP,G)=|GP|/|G|>0.5的為頻繁模式.

定義6.標(biāo)準(zhǔn)模式挖掘問(wèn)題(SPM):在候選模式集中給定一個(gè)常數(shù)m,Top-m標(biāo)準(zhǔn)模式挖掘問(wèn)題定義如公式(2)所示:

(2)

其中S={P1,P2,…,Pm}有m個(gè)標(biāo)準(zhǔn)模式的集合,GPi為標(biāo)準(zhǔn)模式Pi在知識(shí)圖上的覆蓋子圖,|GPi|為GPi的節(jié)點(diǎn)數(shù)和邊數(shù)的總和.

定義7.圖模擬匹配:給定一個(gè)模式圖P(VP,EP,LP)和一個(gè)數(shù)據(jù)子圖Gsub=(Vsub,Esub,Lsub),兩者之間存在二元關(guān)系S?VP×Vsub,其中VP和Vsub分別表示模式圖節(jié)點(diǎn)和數(shù)據(jù)圖節(jié)點(diǎn)的集合,若LP(v)=Lsub(u),則稱(chēng)該子圖滿(mǎn)足節(jié)點(diǎn)約束;若?(v,v′)∈EP,?(u,u′)∈Et:(u′,v′)∈S,則稱(chēng)該子圖滿(mǎn)足邊約束;若?v∈VP,?u∈Vsub:(u,v)∈S,則稱(chēng)該子圖滿(mǎn)足圖約束,檢查數(shù)據(jù)子圖與模式圖之間是否同時(shí)滿(mǎn)足3個(gè)約束的過(guò)程叫圖模擬匹配.

定義8.知識(shí)向量化:給定一個(gè)知識(shí)圖G=(V,E,L),對(duì)于G中每一條知識(shí)三元組(h,r,t),將三元組中不同類(lèi)型的關(guān)系和實(shí)體投影至不同的空間域中,即對(duì)h和t向不同的關(guān)系空間進(jìn)行投影,并建立h到t的轉(zhuǎn)換關(guān)系.

定義9.向量距離:給定兩個(gè)知識(shí)向量x=(x1,x2,x3,…,xn)和y=(y1,y2,y3,…,yn),兩者間距離公式定義見(jiàn)公式(3):

(3)

問(wèn)題描述:給定知識(shí)圖G=〈V,E,L〉,利用頻繁模式挖掘算法挖掘知識(shí)圖中的頻繁模式P,當(dāng)知識(shí)圖中節(jié)點(diǎn)v和模式節(jié)點(diǎn)vP滿(mǎn)足(v,vP)∈R且模式覆蓋度cov(Pi,G)滿(mǎn)足給定最小模式覆蓋度閾值,同時(shí)使S*=argmax|S|成立時(shí),該模式P是標(biāo)準(zhǔn)模式,利用標(biāo)準(zhǔn)模式設(shè)計(jì)篩選方案,使用圖模擬匹配或計(jì)算向量間距離的方法篩選正確知識(shí),并將正確知識(shí)插入知識(shí)圖譜.

2.2 方法流程

本文提出的基于標(biāo)準(zhǔn)模式挖掘的知識(shí)圖譜更新處理方法流程圖如圖2所示,具體流程步驟如下:

圖2 知識(shí)圖譜更新處理流程圖

1)模式挖掘.利用頻繁模式挖掘算法挖掘初始模式集,給出模式限制參數(shù)并規(guī)范模式;進(jìn)一步用Giraph算法進(jìn)行匹配,剔除描述信息少概括能力差的模式;對(duì)候選模式集進(jìn)行增益計(jì)算,挖掘出具有代表性的標(biāo)準(zhǔn)模式集.

2)構(gòu)造新增知識(shí)圖.利使用詞條更新頻率預(yù)測(cè)器獲取熱詞并作為種子實(shí)體,抽取種子實(shí)體所在三元組以構(gòu)造知識(shí)圖.

3)篩選更新知識(shí).用目標(biāo)模式集中的模式模擬匹配更新知識(shí)圖,根據(jù)近似匹配要求篩選不匹配的知識(shí),當(dāng)大量知識(shí)同時(shí)篩選時(shí),向量化標(biāo)準(zhǔn)模式和待匹配知識(shí),利用向量距離進(jìn)行篩選.

4)更新知識(shí)的嵌入.原本沒(méi)有的實(shí)體其知識(shí)直接嵌入,存在的實(shí)體找出其沖突元素所在三元組,進(jìn)一步判斷是否符合三元組所在模式的約束并更新.

3 標(biāo)準(zhǔn)模式挖掘算法

3.1 候選模式挖掘

先利用GRAMI框架在大圖中挖掘頻繁子圖,通過(guò)調(diào)整頻繁度找到符合的所有子圖,且能避免復(fù)雜的枚舉[11].由于知識(shí)圖譜中實(shí)體信息豐富、實(shí)體間關(guān)系復(fù)雜,圖模式會(huì)根據(jù)實(shí)體和關(guān)系的不同情況而產(chǎn)生不同的大小,為了避免過(guò)于復(fù)雜和龐大,在頻繁模式挖掘后需要對(duì)模式進(jìn)行限制:給定整數(shù)參數(shù)k和n,k為節(jié)點(diǎn)間的路徑長(zhǎng)度,n為模式中的節(jié)點(diǎn)數(shù).有圖模式P,其中kP為模式P中節(jié)點(diǎn)間的最長(zhǎng)路徑長(zhǎng)度,|P|為模式P的節(jié)點(diǎn)數(shù)和路徑長(zhǎng)度,則kP≤k,|P|≤k+n時(shí),模式P滿(mǎn)足限制模式定義.例如圖2中P1的kP1=2,|P1|=5,如果kP1和|P1|滿(mǎn)足給定的參數(shù),那么P1就是符合參數(shù)限制的模式.

實(shí)際應(yīng)用中的知識(shí)圖譜含有大量節(jié)點(diǎn)和邊,判定圖模式P和求解覆蓋子圖GP是耗時(shí)的,本文選用Giraph模型圖模擬[12]的思想進(jìn)一步得到候選模式集:先進(jìn)行模式P與知識(shí)圖G之間任意節(jié)點(diǎn)vP∈V的匹配.如果u的標(biāo)簽l∈VP,且l是P中的葉子節(jié)點(diǎn),則u是匹配的;如果v的標(biāo)簽為l,且P在中l(wèi)有子節(jié)點(diǎn)l′1,l′2,…,l′c,則v在G中具有l(wèi)′1,l′2,…,l′c標(biāo)簽的子節(jié)點(diǎn),且v與其l′i(i=1,2,…,c)標(biāo)簽子節(jié)點(diǎn)之間的邊與邊(l,l′i)的標(biāo)簽一致,則v匹配.將模式v中節(jié)點(diǎn)進(jìn)行拓?fù)渑判?并生成一個(gè)由v決定的標(biāo)簽拓?fù)湫蛄?記為l1,l2,…,lt.對(duì)知識(shí)圖G中的節(jié)點(diǎn),按照P中的標(biāo)簽拓?fù)湫蛄械哪嫘蚺卸ㄏ鄳?yīng)標(biāo)簽的節(jié)點(diǎn)是否匹配,如知識(shí)圖G中存在l1,l2,…,lt標(biāo)簽的匹配節(jié)點(diǎn),那圖模式P就是一個(gè)候選模式,匹配的節(jié)點(diǎn)及與這些節(jié)點(diǎn)相鄰的具有相應(yīng)標(biāo)簽的邊即構(gòu)成覆蓋子圖GP.

從邊緣的葉子節(jié)點(diǎn)開(kāi)始匹配,匹配過(guò)程如圖3所示:從“麥兆輝”、“羅志良”、“劉青云”3個(gè)節(jié)點(diǎn)開(kāi)始匹配,3個(gè)節(jié)點(diǎn)根據(jù)連接的邊的關(guān)系標(biāo)簽同步向上游節(jié)點(diǎn)進(jìn)行消息的傳遞,將會(huì)傳遞本節(jié)點(diǎn)的標(biāo)簽屬性等包含的所有信息,例如“麥兆輝”節(jié)點(diǎn)會(huì)向“竊聽(tīng)風(fēng)云”節(jié)點(diǎn)發(fā)送自身節(jié)點(diǎn)的ID和屬性標(biāo)簽“導(dǎo)演”,“竊聽(tīng)風(fēng)云”節(jié)點(diǎn)接受到信息后繼續(xù)向它的上游節(jié)點(diǎn)發(fā)送信息,信息包含自身信息和從下游節(jié)點(diǎn)收到的信息,以此迭代傳遞.傳遞的過(guò)程中尤其注意標(biāo)簽信息的匹配,所以“金像獎(jiǎng)”節(jié)點(diǎn)與“麥兆輝”節(jié)點(diǎn)此時(shí)不會(huì)進(jìn)行消息的傳遞,因?yàn)槠溥厴?biāo)簽“獲得獎(jiǎng)項(xiàng)”與圖模式P3中的“指導(dǎo)”邊標(biāo)簽不能匹配.迭代傳遞信息的過(guò)程中,消息是合并后迭代傳遞的,邊標(biāo)簽一直保持匹配,邏輯上是“∨”的關(guān)系,節(jié)點(diǎn)均活躍表示匹配,才能保證迭代匹配,最終完成關(guān)于模式P3完整的消息匹配,且P3是一個(gè)匹配的標(biāo)準(zhǔn)模式,圖中虛線為消息傳遞過(guò)程與節(jié)點(diǎn)共同組成模式覆蓋子圖.

圖3 基于Giraph的圖模擬標(biāo)準(zhǔn)模式判定及覆蓋子圖求解

在圖模擬匹配后以模式覆蓋度為度量標(biāo)準(zhǔn),模式的覆蓋度越高,表示該模式對(duì)知識(shí)圖的表示越完備,留下表示更完備的模式.如給定參數(shù)k=2和b=7的限制,圖模式P1、P2、P3均滿(mǎn)足,但在知識(shí)圖中“消失的兇手”節(jié)點(diǎn)標(biāo)簽為“電影”,與圖模式P1的節(jié)點(diǎn)類(lèi)型“電影”相匹配;其上游節(jié)點(diǎn)和下游節(jié)點(diǎn)為“羅志良”和“上?！?節(jié)點(diǎn)類(lèi)型為“導(dǎo)演”和“拍攝地點(diǎn)”,各自的邊標(biāo)簽為“指導(dǎo)”和“拍攝于…”,與P1中的節(jié)點(diǎn)類(lèi)型和邊標(biāo)簽不匹配,那么P1就是一個(gè)不滿(mǎn)足匹配關(guān)系的模式.故P1、P2、P3僅P2、P3滿(mǎn)足標(biāo)準(zhǔn)模式.對(duì)于候選模式P2、P3的二元關(guān)系R(P2,G)和R(P3,G)的覆蓋子圖,分別計(jì)算圖的大小:|GP2|=10,|G|=40,|GP3|=18,可以得到:cov(GP2,G)=|GP2|/|G|=10/40

圖4 P2和P3的覆蓋子圖實(shí)例

3.2 標(biāo)準(zhǔn)模式挖掘

由于模式間可能存在重疊冗余或者相似,如何得到表達(dá)能力強(qiáng)且準(zhǔn)確率高的標(biāo)準(zhǔn)模式進(jìn)一步定義為標(biāo)準(zhǔn)模式挖掘問(wèn)題.根據(jù)定義6可知挖掘問(wèn)題的目標(biāo)函數(shù)argmax|S|是一個(gè)單調(diào)非負(fù)的且有大小約束的次模函數(shù)且滿(mǎn)足次模性,且該函數(shù)能用貪心算法得到近似解結(jié)果為(1-1/e)倍的最優(yōu)解[13].待挖掘的圖模式集具有邊際效益遞減的特點(diǎn)[14],即挖掘出的圖模式集會(huì)隨著新挖掘的標(biāo)準(zhǔn)模式的加入而減小.故標(biāo)準(zhǔn)模式挖掘的目標(biāo)是在候選的圖模式集中得到滿(mǎn)足最大邊際效益的模式.

文獻(xiàn)[15]不斷給初始圖模式集加入覆蓋子集大且邊際效益高的模式,直到子集數(shù)滿(mǎn)足需要的模式數(shù).但這樣的標(biāo)準(zhǔn)模式挖掘目標(biāo)函數(shù)唯一,且利用函數(shù)的次模性來(lái)找到滿(mǎn)足最大邊際效益的圖模式,其挖掘過(guò)程的算法是貪婪的,每次都在標(biāo)準(zhǔn)圖模式集中選擇使當(dāng)前具有最大邊際效益的圖模式加入,即計(jì)算P′←argmaxP∈SPσ(S|P),該算式保證了ΔGP最大化,但不能使ΔGS最大化,即不能保證最終得到的圖模式集覆蓋率最大.

本文不改變目標(biāo)函數(shù)P′←argmaxP∈SPσ(S|P),提出以下改進(jìn)方案:先計(jì)算所有可行的小于m的圖模式集中所有具有最大|GP|的集,然后在計(jì)算的模式集合中選擇只有一個(gè)P使得|GP|最大的模式集,依次選擇包含先前模式的新模式集,新模式集的模式個(gè)數(shù)比先前模式集的模式多一個(gè),迭代得到目標(biāo)標(biāo)準(zhǔn)模式集,在這樣的情況下,求解的結(jié)果會(huì)更加逼近最優(yōu)解.

算法1為SPM標(biāo)準(zhǔn)模式優(yōu)化挖掘算法,先利用GRAMI頻繁模式挖掘工具挖掘頻繁模式(第1行),然后對(duì)模式的大小進(jìn)行限制并進(jìn)行圖模擬匹配(第2～3行),匹配完成后得到候選模式集(第4行).初始化標(biāo)準(zhǔn)模式集為空(第6行),進(jìn)行模式邊際效益和新增模式前后的模式集覆蓋度計(jì)算(第7～9行),計(jì)算后選擇具有最大邊際效益的模式加入模式集(第10～12行),直到模式集中模式個(gè)數(shù)滿(mǎn)足所需結(jié)果集模式個(gè)數(shù).具體算法如下:

算法1. SPM標(biāo)準(zhǔn)模式優(yōu)化挖掘算法

輸入:知識(shí)圖G(V,E,L),限制邊數(shù)k,限制節(jié)點(diǎn)數(shù)n,初始結(jié)果集S← ?,標(biāo)準(zhǔn)模式結(jié)果集模式個(gè)數(shù)m

輸出:標(biāo)準(zhǔn)模式集S

4 知識(shí)篩選

從熱門(mén)語(yǔ)句文本中抽取出相應(yīng)的三元組實(shí)例,構(gòu)造待更新的知識(shí)圖,根據(jù)抽取的知識(shí)量選擇合適的篩選方案:知識(shí)三元組較少時(shí),構(gòu)造更新知識(shí)圖Gnew,用標(biāo)準(zhǔn)模式P匹配更新知識(shí)圖Gnew,剔除不滿(mǎn)足兩者中S?VP×Vnew這樣關(guān)系的節(jié)點(diǎn),剩余節(jié)點(diǎn)構(gòu)成正確知識(shí);當(dāng)待更新知識(shí)量較大時(shí),選擇將標(biāo)準(zhǔn)模式P和更新知識(shí)三元組向量化,用向量間距離衡量向量相似度,大于一定閾值的向量為正確知識(shí),并向量化三元組嵌入更新.

4.1 圖模擬篩選方法

利用挖掘的標(biāo)準(zhǔn)模式集在待更新知識(shí)圖中進(jìn)行圖模擬匹配,具體匹配過(guò)程如下:匹配過(guò)程與找標(biāo)準(zhǔn)模式的匹配類(lèi)似.標(biāo)準(zhǔn)模式集與待更新知識(shí)圖存在二元關(guān)系R(P,G)?VP×V,先根據(jù)待更新知識(shí)圖中節(jié)點(diǎn)的標(biāo)簽在模式集中產(chǎn)生匹配候選集,保證該知識(shí)圖存在后繼節(jié)點(diǎn)與模式圖中對(duì)應(yīng)節(jié)點(diǎn)的后繼關(guān)系,即該知識(shí)圖節(jié)點(diǎn)存在后繼節(jié)點(diǎn)與模式圖節(jié)點(diǎn)的后繼節(jié)點(diǎn)的屬性值相同,按照這樣的近似匹配要求篩選不匹配的節(jié)點(diǎn),剩下的覆蓋子圖為可以嵌入的正確知識(shí).

算法2為基于標(biāo)準(zhǔn)模式圖匹配的更新知識(shí)篩選算法,將算法1中得到的標(biāo)準(zhǔn)模式都與更新知識(shí)圖進(jìn)行匹配(第1行),先從葉子節(jié)點(diǎn)開(kāi)始匹配(第3～5行),依次判斷知識(shí)圖中節(jié)點(diǎn)和邊與標(biāo)準(zhǔn)模式中的節(jié)點(diǎn)和邊(第6～8行),都匹配時(shí)篩選出符合的知識(shí)圖,得到待更新匹配的知識(shí)(第9行).

算法2. 基于標(biāo)準(zhǔn)模式圖匹配的更新知識(shí)篩選算法

輸入:更新知識(shí)圖Gnew,標(biāo)準(zhǔn)模式集S=(P1,P2,…,Pm)

輸出:待更新知識(shí)G*

4.2 向量化篩選方法

上述方法在圖模擬匹配時(shí),會(huì)因過(guò)大的知識(shí)量加大和復(fù)雜的實(shí)體間關(guān)系而急劇增加圖模擬匹配的時(shí)間復(fù)雜度.由于TransD能較好的解決復(fù)雜關(guān)系下的實(shí)體表示區(qū)分性,不同的關(guān)系有不同的投影空間,不同類(lèi)型的實(shí)體有不同的投影方式[16],本文利用翻譯模型TransD捕獲實(shí)體和關(guān)系之間的語(yǔ)義相關(guān)性的思想,通過(guò)映射矩陣Mrh和Mrt來(lái)表示不同關(guān)系下的實(shí)體向量.Mrh和Mrt分別是h和t的映射矩陣,其映射矩陣定義如公式(4)和公式(5)所示:

(4)

(5)

其中rp、hp和tp是投影向量,Im×n為單位矩陣,用來(lái)初始化映射矩陣.對(duì)應(yīng)的每個(gè)三元組(h,r,t)中的兩個(gè)實(shí)體向量h和t投影后分別定義如公式(6)和公式(7)所示:

h⊥=Mrhh

(6)

t⊥=Mrtt

(7)

且兩實(shí)體的投影向量滿(mǎn)足的關(guān)系如公式(8)所示:

h⊥+r≈t⊥

(8)

因此對(duì)于標(biāo)準(zhǔn)模式集S=(P1,P2,P3,…,Pm),任意標(biāo)準(zhǔn)模式三元組(hsp,rsp,tsp)∈Pm,其實(shí)體hsp和tsp的投影如公式(9)和公式(10)所示:

hsp⊥=Mrh_sphsp

(9)

tsp⊥=Mrh_sptsp

(10)

標(biāo)準(zhǔn)模式投影后的向量滿(mǎn)足的關(guān)系如公式(11)所示:

hm⊥+rm≈tm⊥

(11)

對(duì)于更新知識(shí)圖Gnew,其知識(shí)三元組為(hk,rk,tk)∈Gnew,其實(shí)體hk和tk的投影如公式(12)和公式(13)所示:

hk⊥=Mrh_khk

(12)

tk⊥=Mrt_ktk

(13)

知識(shí)三元組向量滿(mǎn)足的關(guān)系為公式(14):

hk⊥+rk≈tk⊥

(14)

對(duì)標(biāo)準(zhǔn)模式和知識(shí)三元組向量化后,計(jì)算標(biāo)準(zhǔn)模式向量與知識(shí)向量的距離,并給定一個(gè)距離差的閾值ε,篩選大于閾值的知識(shí)向量,得到待嵌入的知識(shí).

算法3為基于向量距離計(jì)算的更新知識(shí)篩選算法,在模式向量集中選擇一個(gè)模式的向量,再在知識(shí)向量集中尋找與該模式的向量在同一空間域的知識(shí)三元組向量,并將三元組向量依次與模式向量進(jìn)行距離計(jì)算,直到模式向量集中被選完(第1～6行),判斷兩者的距離差與閾值的關(guān)系,只要與其中一個(gè)模式向量的距離差小于閾值,就作為待更新知識(shí)并放入待更新知識(shí)集中(第7～9行).

算法3. 基于向量距離計(jì)算的更新知識(shí)篩選算法

輸入:更新知識(shí)圖Gnew,標(biāo)準(zhǔn)模式集S=(P1,P2,…,Pm),投影域集D=(D1,D2,…,Dn),向量距離閾值ε

輸出:待更新知識(shí)G*

完成篩選后,得到待更新的知識(shí)圖,利用圖嵌入或三元組嵌入的方法將待更新知識(shí)插入原先的知識(shí)圖譜中.

5 實(shí) 驗(yàn)

5.1 數(shù)據(jù)集與實(shí)驗(yàn)設(shè)計(jì)

中文學(xué)術(shù)信息集成系統(tǒng)Scholar Space包含不同數(shù)據(jù)源的學(xué)術(shù)數(shù)據(jù),并能進(jìn)一步構(gòu)建一個(gè)學(xué)術(shù)關(guān)系知識(shí)圖譜Scholar Graph[17],本文實(shí)驗(yàn)中選擇其計(jì)算機(jī)類(lèi)的數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集,其中節(jié)點(diǎn)數(shù)為774263,邊數(shù)為395833,節(jié)點(diǎn)標(biāo)簽有4類(lèi),邊標(biāo)簽有2類(lèi).本文先通過(guò)簡(jiǎn)單抽樣方法將數(shù)據(jù)集分割,分為比例為80%和20%兩部分,其中80%數(shù)據(jù)集(D1)作為模式挖掘的數(shù)據(jù),20%數(shù)據(jù)集(D2)作為實(shí)行篩選實(shí)驗(yàn)的數(shù)據(jù)并進(jìn)行注錯(cuò)處理.

5.2 評(píng)價(jià)指標(biāo)

本文采用精確率Precision、召回率Recall和F1值作為評(píng)價(jià)指標(biāo).

表1 篩選結(jié)果混淆矩陣

5.3 實(shí)驗(yàn)結(jié)果與分析

根據(jù)5.1中的實(shí)驗(yàn)設(shè)計(jì)進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如下文所示:

5.3.1 頻繁模式挖掘

對(duì)數(shù)據(jù)集D1利用GRAMI挖掘工具挖掘得到頻繁模式集,使得挖掘出的模式對(duì)知識(shí)圖達(dá)到最大覆蓋面積,并使用覆蓋度作為衡量圖模式的覆蓋性的度量標(biāo)準(zhǔn),覆蓋度越大,解集的覆蓋性就越好,且最大為1.挖掘結(jié)果如表2所示.

表2 頻繁模式挖掘參數(shù)

5.3.2 m值取值分析

調(diào)節(jié)m的取值,得到不同的模式覆蓋度cov值,覆蓋度越大表明標(biāo)準(zhǔn)模式集效果越好.

圖5為m值取不同值時(shí)的影響圖,標(biāo)準(zhǔn)模式集在更新知識(shí)圖上的覆蓋度變化如圖5(a)所示:隨著選取的模式個(gè)數(shù)m值的增加,標(biāo)準(zhǔn)模式集的覆蓋度增大,但不會(huì)隨著m值的增加而一直增大,分析這是由于標(biāo)準(zhǔn)模式的大小不同而產(chǎn)生局部重疊的原因.

圖5 調(diào)節(jié)m值的影響圖

不同的m值使得標(biāo)準(zhǔn)模式集的個(gè)數(shù)不同,從而在利用標(biāo)準(zhǔn)模式集篩選更新知識(shí)圖時(shí),會(huì)對(duì)精準(zhǔn)率、召回率和F1產(chǎn)生影響.產(chǎn)生的影響如圖5(b)所示:隨著m值的取值的增大,精確率、召回率會(huì)先增大后略降低并趨于平穩(wěn),F1受精確率和召回率影響,隨著m值的取值的增大先上升后趨于不變,最終當(dāng)m值取7時(shí),使得F1值最大,此時(shí)pre=92.3%,recall=85.6%,覆蓋度為0.876,在保證召回率盡可能大的情況下,提高精確度,使兩者綜合結(jié)果較好,標(biāo)準(zhǔn)模式集最優(yōu),并用該值進(jìn)行接下來(lái)實(shí)驗(yàn).

5.3.3 向量間距離閾值ε調(diào)節(jié)結(jié)果分析

使用得到的標(biāo)準(zhǔn)模式集中的模式依次對(duì)數(shù)據(jù)集D2進(jìn)行圖模擬匹配,匹配后符合的數(shù)據(jù)記為正確數(shù)據(jù);并同時(shí)對(duì)數(shù)據(jù)集D2和標(biāo)準(zhǔn)模式集進(jìn)行向量化,計(jì)算數(shù)據(jù)集D2的向量和標(biāo)準(zhǔn)模式集的向量間距離差,調(diào)節(jié)距離差的閾值,通過(guò)向量間距離判斷兩條知識(shí)間的相似度,驗(yàn)證知識(shí)的正確性,小于閾值時(shí)記為正確的知識(shí).

不同的向量間距離的閾值使得三元組準(zhǔn)確率要求不同,調(diào)節(jié)向量間距離的閾值會(huì)在篩選更新知識(shí)圖時(shí)對(duì)精準(zhǔn)率、召回率和F1產(chǎn)生影響.如圖6所示:向量間距離差的閾值變化時(shí),即向量間相似度范圍發(fā)生變化.距離差閾值越大,則對(duì)兩條向量的相似度要求越低.當(dāng)距離差閾值增大時(shí),召回率呈增加趨勢(shì),精確率呈下降趨勢(shì).數(shù)據(jù)量大時(shí)不一定準(zhǔn)確率高,要在保證召回率的情況下盡量提高精確率和兩者的綜合結(jié)果F1,因此距離差閾值取0.2時(shí),篩選情況能達(dá)到最佳效果.

圖6 距離差閾值對(duì)精確率、召回率和F1的影響圖

5.3.4 知識(shí)量影響分析

本文做了兩種方案在不同知識(shí)量下的影響實(shí)驗(yàn),選取數(shù)據(jù)集的不同數(shù)據(jù)量進(jìn)行實(shí)驗(yàn),運(yùn)行時(shí)間對(duì)比如圖7(a)所示:在較小的數(shù)據(jù)集上兩者的運(yùn)行時(shí)間相近且SP方法要更快一些,但隨著數(shù)據(jù)量的增加SP+VD的運(yùn)行時(shí)間會(huì)更快一些,是由于前者的時(shí)間復(fù)雜度高于后者,在數(shù)據(jù)量較小時(shí)運(yùn)行時(shí)間相近,但隨著數(shù)據(jù)的增加,前者運(yùn)行的復(fù)雜程度比后者高,運(yùn)行時(shí)間也就高于后者.

圖7 SP和SP+VD篩選方案對(duì)比圖

在20%數(shù)據(jù)集上進(jìn)行篩選對(duì)比,結(jié)果如圖7(b)所示:SP精準(zhǔn)率和F1較好,而SP+VD召回率較好,是因?yàn)镾P的篩選過(guò)程中使用的參數(shù)更多更精細(xì),而SP+VD只有向量間距離這一個(gè)參數(shù),前者會(huì)使篩選的結(jié)果更精確,后者則會(huì)篩選出更多預(yù)測(cè)為符合的數(shù)據(jù),且本文提出的兩種方法均能提升對(duì)更新知識(shí)的篩選準(zhǔn)確率.

5.3.5 不同篩選方案結(jié)果分析

本文將提出的方法與[7,8]這兩篇文章中提出的方法進(jìn)行對(duì)比試驗(yàn).

1)TI:文獻(xiàn)[7]提出考慮三元組重要性的特征,分別對(duì)實(shí)體和關(guān)系的重要性進(jìn)行估計(jì)和排名,并根據(jù)排名篩選正確知識(shí).

2)RG:文獻(xiàn)[8]提出計(jì)算基于規(guī)則引導(dǎo)的置信度和關(guān)聯(lián)度來(lái)衡量知識(shí)的正確程度以進(jìn)行篩選.

3)SP:本文提出的基于標(biāo)準(zhǔn)模式挖掘的方法,利用挖掘出的標(biāo)準(zhǔn)模式在更新知識(shí)圖中模擬匹配來(lái)篩選.

4)SP+VD:本文提出的基于向量間距離的方法,向量化三元組知識(shí)和標(biāo)準(zhǔn)模式,通過(guò)計(jì)算向量間距離來(lái)篩選.

圖8為采用4種不同方案(TI方法、RG方法、SP方法、SP+VD方法)篩選數(shù)據(jù)集D2的比較分析圖,由圖8可知在同一數(shù)據(jù)集上,本文提出的SP方法和SP+VD方法在精準(zhǔn)率、召回率和F1這3個(gè)指標(biāo)上均比TI方法對(duì)三元組知識(shí)進(jìn)行正確和錯(cuò)誤的分類(lèi)的效果好,精準(zhǔn)率分別高12.1%和9.3%,召回率分別高15.1%和6.8%,F1分別高13.79%和13.35%.RG方法相對(duì)于TI方法精準(zhǔn)率有提升但仍不夠高,本文的SP方法和SP+VD方法分別比RG方法高1.34%和0.9%.

圖8 不同篩選方案比較分析圖

6 總 結(jié)

提取知識(shí)圖譜的模式信息,利用標(biāo)準(zhǔn)模式篩選更新的知識(shí),對(duì)知識(shí)圖譜的更新準(zhǔn)確率具有重要的研究意義.本文提出一種基于標(biāo)準(zhǔn)模式的知識(shí)圖譜篩選更新方法,該方法先挖掘出數(shù)據(jù)集上的標(biāo)準(zhǔn)模式,然后根據(jù)知識(shí)圖譜更新的數(shù)據(jù)量多少,設(shè)計(jì)了兩種篩選的方案,數(shù)據(jù)量較少時(shí)利用標(biāo)準(zhǔn)模式圖模擬匹配更新知識(shí)圖篩選錯(cuò)誤的知識(shí)或是數(shù)據(jù)量較多時(shí)轉(zhuǎn)化為向量后進(jìn)行向量距離比較篩選,從而提高了知識(shí)更新篩選的準(zhǔn)確率和召回率.本文提出的向量距離比較篩選方法的比較操作在不同的域中,可以分布式進(jìn)行,未來(lái)在其規(guī)模化的基礎(chǔ)上,進(jìn)一步討論如何篩選具有多對(duì)多關(guān)系的知識(shí),且針對(duì)帶有層次信息和動(dòng)態(tài)知識(shí)更新繼續(xù)開(kāi)展研究工作.