[發(fā)明專(zhuān)利]一種精準(zhǔn)描述知識(shí)圖譜中元素語(yǔ)義的子圖抽取方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011175554.7
• 申請(qǐng)日: 2020-10-29
• 公開(kāi)（公告）號(hào): CN112256835B
• 公開(kāi)（公告）日: 2021-07-23
• 發(fā)明（設(shè)計(jì)）人: 汪鵬;徐忠鍇
• 申請(qǐng)（專(zhuān)利權(quán)）人: 東南大學(xué)
• 主分類(lèi)號(hào): G06F16/33
• 分類(lèi)號(hào): G06F16/33;G06F16/36;G06F40/216;G06F40/295;G06F40/30
• 代理公司: 南京眾聯(lián)專(zhuān)利代理有限公司 32206
• 代理人: 蔣昱

1.一種精準(zhǔn)描述知識(shí)圖譜中元素語(yǔ)義的子圖抽取方法，其特征在于，該方法包括以下內(nèi)容：

1)知識(shí)圖譜的圖表示和預(yù)處理：根據(jù)知識(shí)圖譜的三元組表示特點(diǎn)，將其轉(zhuǎn)換為一個(gè)帶標(biāo)簽的有向圖G_r，由于G_r中兩節(jié)點(diǎn)間可能存在多條邊，因此G_r是一個(gè)多圖，采用一種結(jié)合知識(shí)圖譜原始圖和二部圖特點(diǎn)的混合表示方式，并這種圖稱(chēng)為知識(shí)圖譜混合圖G_h，對(duì)G_h分別進(jìn)行語(yǔ)義擴(kuò)充、語(yǔ)義明確和精煉操作；

2)語(yǔ)義子圖：語(yǔ)義子圖是用于精確描述知識(shí)圖譜中給定的概念、屬性和實(shí)體元素的有限規(guī)模子圖，其并不強(qiáng)調(diào)語(yǔ)義完整性，即知識(shí)圖譜中有限個(gè)三元組便能精確描述元素在該知識(shí)圖譜中的語(yǔ)義，且元素語(yǔ)義的解釋無(wú)須用到整個(gè)知識(shí)圖譜全部的知識(shí)，語(yǔ)義子圖由描述給定元素的Top-k個(gè)三元組組成；

3)語(yǔ)義子圖抽取的電路模型構(gòu)建：提出一種利用電路模型來(lái)解決語(yǔ)義子圖抽取，即將抽取語(yǔ)義子圖的問(wèn)題轉(zhuǎn)化為一個(gè)電路模型進(jìn)行求解，基于步驟1)處理后得到的圖G_h，圖中的邊傳遞信息的能力對(duì)應(yīng)于電路中的電導(dǎo)率C，圖中的頂點(diǎn)容納信息的能力對(duì)應(yīng)于電路中的電壓V，電流I表征單位時(shí)間內(nèi)在邊上通過(guò)的信息量，并給圖中增加一個(gè)接地的陷入點(diǎn)z，同時(shí)讓其它的所有點(diǎn)都增加一條指向z的邊，知識(shí)圖譜中s點(diǎn)的語(yǔ)義子圖即從s到z的連接子圖中捕獲電流最大的子圖；

4)電路模型中的電導(dǎo)率計(jì)算方法：針對(duì)知識(shí)圖譜圖的特點(diǎn)，提出了一套電導(dǎo)率權(quán)重計(jì)算規(guī)則，知識(shí)圖譜的圖中主要包括概念、屬性、實(shí)體及元語(yǔ)，首先分析不同成分傳遞信息時(shí)的權(quán)重，然后給出由它們構(gòu)成的三元組的電導(dǎo)率計(jì)算規(guī)則，包括頻率規(guī)則、層次規(guī)則、實(shí)體空間規(guī)則、實(shí)體屬性描述規(guī)則和獨(dú)生實(shí)體優(yōu)先規(guī)則；

規(guī)則1.頻率規(guī)則

如果一個(gè)元素頻繁出現(xiàn)在不同三元組中，那么當(dāng)它對(duì)應(yīng)知識(shí)圖譜圖中頂點(diǎn)時(shí)，該頂點(diǎn)的度會(huì)較大；當(dāng)它對(duì)應(yīng)圖中邊時(shí)，這條邊會(huì)涉及較多三元組，這里將元素出現(xiàn)次數(shù)視為頻率，可見(jiàn)，元素頻率越大，它傳遞信息的能力越弱，這種傳遞能力可表示為權(quán)重，為了避免直接用頻率倒數(shù)衡量權(quán)重而導(dǎo)致權(quán)重隨頻率增加而迅速下降，先引入一個(gè)退火函數(shù)g(x，m)：

其中，m是一個(gè)預(yù)先設(shè)定的常數(shù)；ε是一個(gè)很小的正常數(shù)，用于避免出現(xiàn)分子為0的情況，這里將退火函數(shù)中的x設(shè)為元素頻率f(e)，m設(shè)為某成分中元素的最大頻率f_max(e_k)，則元素對(duì)應(yīng)的權(quán)重為：

μ_f(e)＝g(f(e)，f_max(e_k))

此時(shí)退火函數(shù)中的前半部分衡量元素在知識(shí)圖譜中的全局頻率權(quán)重，后半部分衡量在同類(lèi)元素中的相對(duì)頻率權(quán)重；

這種根據(jù)元素頻率計(jì)算權(quán)重的方法稱(chēng)為頻率規(guī)則，頻率規(guī)則對(duì)知識(shí)圖譜中的概念、關(guān)系和元語(yǔ)都適用，由于知識(shí)圖譜一般不會(huì)將領(lǐng)域內(nèi)的實(shí)例相關(guān)的知識(shí)全部加入進(jìn)來(lái)，因此得到的實(shí)例頻率并不可信，所以實(shí)例權(quán)重計(jì)算時(shí)不采用頻率規(guī)則；

規(guī)則2.層次規(guī)則；

層次關(guān)系rdfs：subClassOf和rdfs：subPropertyOf是知識(shí)圖譜中的概念和關(guān)系重要組織形式，直觀上，元素越是位于層次結(jié)構(gòu)中的底層，它傳播信息的能力就越強(qiáng)，因此，由層次造成的傳播能力可用如下權(quán)重衡量：

其中d(e_i)表示元素在層次中的深度，而H_max(e_k)表示e_i所處的層次結(jié)構(gòu)最大深度；

層次規(guī)則適用于概念和關(guān)系；

規(guī)則3.實(shí)例空間規(guī)則；

概念和關(guān)系都是知識(shí)圖譜中的抽象資源，它所對(duì)應(yīng)的實(shí)體或事實(shí)的集合稱(chēng)為其實(shí)例空間，稱(chēng)概念C對(duì)應(yīng)的全部實(shí)例的集合I_sp(C)＝{a_i|a_i∈C}為它的實(shí)例空間，稱(chēng)關(guān)系P所對(duì)應(yīng)的形如a_i，P，b_j的全部二元組a_i，b_i的集合為它的實(shí)例空間，記作I_sp(P)＝{a_i，b_i|a_i∈Dom(P)，b_j∈Rng(P)}，其中Dom(P)和Rng(P)分別表示P的值域和定義域；

在知識(shí)圖譜描述中，組成概念C的實(shí)例空間的a_i滿(mǎn)足a_i，rdf：type，C形式的三元組，組成關(guān)系P的實(shí)例空間的a_i，b_j滿(mǎn)足a_i，P，b_j形式的三元組，概念的實(shí)例空間的規(guī)模越大，說(shuō)明它對(duì)應(yīng)的實(shí)例越多，則它位于概念層次上層的可能性越大，因此包含此概念的三元組傳遞的信息就越少，如果關(guān)系的實(shí)例空間規(guī)模越大，說(shuō)明該關(guān)系被使用得越普遍，因此相應(yīng)的三元組傳遞的信息就越少，考慮實(shí)例空間所得到的權(quán)重仍然可用退火函數(shù)計(jì)算：

其中|I_sp(e)|表示元素e對(duì)應(yīng)的實(shí)例空間大小，表示知識(shí)圖譜中同類(lèi)元素所對(duì)應(yīng)的實(shí)例空間大小的最大值；

規(guī)則4.實(shí)例屬性描述規(guī)則；

通常，當(dāng)一個(gè)實(shí)例比較重要時(shí)，知識(shí)圖譜會(huì)用較多的三元組來(lái)對(duì)其進(jìn)行描述，由于對(duì)任意實(shí)例a_i的描述都具有a_i，p_m，b_j的形式，這里屬性值b_j可能是具體數(shù)值或其它實(shí)例對(duì)象，因此可通過(guò)統(tǒng)計(jì)p_m的數(shù)目來(lái)衡量知識(shí)圖譜對(duì)于實(shí)例a_i的描述程度，采用如下的公式來(lái)計(jì)算實(shí)例的這種權(quán)重：

其中，dp(a_i)和op(a_i)分別表示描述中使用的DatatypeProperty和ObjectProperty，dp_max(a_k)和op_max(a_k)是所有實(shí)例的描述中使用的兩類(lèi)屬性的最大數(shù)目；

規(guī)則5.獨(dú)生實(shí)例優(yōu)先規(guī)則；

設(shè)實(shí)例a_i對(duì)應(yīng)的概念是C，那么C中所包含的實(shí)例個(gè)數(shù)越少，這些實(shí)例傳播信息的能力越強(qiáng)，即概念的實(shí)例越少，這些實(shí)例傳遞的語(yǔ)義信息越多，這種計(jì)算實(shí)例權(quán)重的規(guī)則稱(chēng)為獨(dú)生實(shí)例優(yōu)先規(guī)則，采用退火函數(shù)來(lái)計(jì)算：

μ_lo(a_i)＝g(|C(a_i)|，C_max(a_k))

其中，|C(a_i)|表示實(shí)例a對(duì)應(yīng)的概念所包含的實(shí)例總數(shù)，|C_max(a_k)|表示知識(shí)圖譜中概念所包含的最大實(shí)例數(shù)目；

5)語(yǔ)義子圖的抽取算法：為解決抽取語(yǔ)義子圖的效率問(wèn)題，采用一種貪心策略設(shè)計(jì)語(yǔ)義子圖抽取算法，算法中的貪心思想是優(yōu)先選擇分配電流與所引入的新節(jié)點(diǎn)之比最大的前綴路徑，設(shè)G_max是所求的語(yǔ)義子圖，首先令G_max為空，接下來(lái)迭代地不斷加入從s到z的前綴路徑到G_max中，隨著G_max不斷增長(zhǎng)，新加入的路徑可能包含G_max中已經(jīng)存在的點(diǎn)，貪心規(guī)則優(yōu)先選擇分配電流和給G_max所帶來(lái)的新節(jié)點(diǎn)之比最大的前綴路徑；

對(duì)于所述步驟5)中的語(yǔ)義子圖抽取問(wèn)題，其可分解為兩個(gè)子問(wèn)題：(1)遍歷有向圖中所有從s到z的前綴路徑，計(jì)算每條路徑上的分配電流；(2)遍歷所有由前綴路徑組成的滿(mǎn)足圖規(guī)模約束的子圖，計(jì)算每個(gè)子圖的捕獲電流，并取其中捕獲電流最大者為語(yǔ)義子圖。