[發(fā)明專利]一種多圖融合方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201911044229.4
• 申請(qǐng)日: 2019-10-30
• 公開(kāi)（公告）號(hào): CN110750689A
• 公開(kāi)（公告）日: 2020-02-04
• 發(fā)明（設(shè)計(jì)）人: 張偉;趙海燕;金芝
• 申請(qǐng)（專利權(quán)）人: 北京大學(xué)
• 主分類號(hào): G06F16/901
• 分類號(hào): G06F16/901;G06N3/00
• 代理公司: 11732 北京睿智保誠(chéng)專利代理事務(wù)所(普通合伙)
• 代理人: 周新楣

本發(fā)明公開(kāi)了一種多圖融合方法，其通過(guò)接收一組圖作為被融合圖，對(duì)這組被融合圖進(jìn)行預(yù)處理，將其中的每一個(gè)被融合圖轉(zhuǎn)化為一個(gè)節(jié)點(diǎn)具有類型、邊具有類型、邊具有方向的被融合圖，作為后繼處理活動(dòng)的輸入，采用隨機(jī)方式生成一組多圖融合方案，作為初始父代種群，對(duì)于初始父代種群中的多圖融合方案，計(jì)算多圖融合方案的信息熵，多圖融合方案的信息熵形成多圖融合方案的適應(yīng)度，對(duì)于兩個(gè)待交叉的多圖融合方案，選取兩者之間的一條最短編輯路徑上的某個(gè)點(diǎn)作為這兩個(gè)融合方案的一個(gè)交叉結(jié)果，實(shí)現(xiàn)同時(shí)對(duì)多個(gè)圖進(jìn)行融合，并提高多圖的融合質(zhì)量。

技術(shù)領(lǐng)域

本發(fā)明涉及多圖融合技術(shù)領(lǐng)域，尤其是涉及一種多圖融合方法。

背景技術(shù)

圖（Graph）數(shù)據(jù)廣泛出現(xiàn)在各種問(wèn)題領(lǐng)域里，例如，生物領(lǐng)域的蛋白質(zhì)交互圖、知識(shí)表示領(lǐng)域的知識(shí)圖譜、軟件開(kāi)發(fā)領(lǐng)域的各種結(jié)構(gòu)化制品、數(shù)據(jù)存儲(chǔ)領(lǐng)域中基于圖的數(shù)據(jù)庫(kù)。對(duì)于任何有結(jié)構(gòu)的信息，都可以采用圖的方式進(jìn)行表示。一個(gè)圖包含一組節(jié)點(diǎn)和一組節(jié)點(diǎn)之間的邊，節(jié)點(diǎn)用于表示實(shí)體型信息，邊用于表示關(guān)系型信息。圖融合的目標(biāo)是確定不同圖中具有相同或相似語(yǔ)義的節(jié)點(diǎn)，從而實(shí)現(xiàn)多圖數(shù)據(jù)中冗余信息的消除或知識(shí)在不同圖之間的遷移等。多圖融合問(wèn)題的本質(zhì)是一個(gè)優(yōu)化問(wèn)題，要從一個(gè)大規(guī)模的多圖融合方案空間中尋找到一個(gè)高質(zhì)量的多圖融合方案。

然而，現(xiàn)有的多圖融合方法并沒(méi)有真正實(shí)現(xiàn)對(duì)多個(gè)圖的同時(shí)融合，而是把多圖融合問(wèn)題轉(zhuǎn)化為一組兩個(gè)圖之間的融合問(wèn)題，導(dǎo)致多圖融合的結(jié)果與這組兩圖融合問(wèn)題的求解順序相關(guān)，無(wú)法提供一個(gè)高質(zhì)量的多圖融合方案。

發(fā)明內(nèi)容

為了解決上述技術(shù)問(wèn)題，本發(fā)明的目的是提供一種多圖融合方法。

為解決上述技術(shù)問(wèn)題，本發(fā)明采用如下技術(shù)方案：

一種多圖融合方法，包括如下步驟：

S0，接收一組圖作為被融合圖；

S1，對(duì)一組被融合圖進(jìn)行預(yù)處理，將其中的每一個(gè)圖轉(zhuǎn)化為一個(gè)節(jié)點(diǎn)具有類型、邊具有類型、邊具有方向的被融合圖，作為后繼處理活動(dòng)的輸入；

S2，采用隨機(jī)方式生成一組多圖融合方案，作為父代種群的初始值；

S3，對(duì)于父代種群中的多圖融合方案，計(jì)算多圖融合方案的信息熵；

S4，將父代種群中每一個(gè)多圖融合方案的信息熵轉(zhuǎn)化為多圖融合方案的適應(yīng)度；

S5，檢查父代種群中是否存在信息熵為零的多圖融合方案，如果存在這樣的多圖融合方案，則返回該多圖融合方案，并終止當(dāng)前多圖融合過(guò)程；

S6，檢查當(dāng)前的多圖融合過(guò)程是否滿足終止條件，如果滿足終止條件，則返回當(dāng)前父代種群中適應(yīng)度最高的多圖融合方案，并終止當(dāng)前多圖融合過(guò)程；

S7，在父代種群中，把所有多圖融合方案按適應(yīng)度從大到小的順序排列，選擇適應(yīng)度排名靠前的若干多圖融合方案，并將這些多圖融合方案放入子代種群中；

S8，基于融合方案的適應(yīng)度，從父代種群中確定一組待交叉的多圖融合方案對(duì)；

S9，對(duì)于每一對(duì)待交叉的多圖融合方案，選取兩者之間的一條最短編輯路徑上的某個(gè)點(diǎn)作為這兩個(gè)融合方案的一個(gè)交叉結(jié)果，然后把這個(gè)交叉結(jié)果放入子代種群中；

S10，當(dāng)所有待交叉的多圖融合方案對(duì)都完成交叉后，把父代種群清空后再把子代種群中的所有多圖融合方案加入父代種群中，然后把子代種群清空，然后跳轉(zhuǎn)至S3。

其中，一個(gè)被融合圖包含一組節(jié)點(diǎn)和一組存在于節(jié)點(diǎn)之間的邊；被融合圖中的一個(gè)節(jié)點(diǎn)可以具有類型；被融合圖中的一個(gè)節(jié)點(diǎn)可以具有值信息，如一個(gè)數(shù)值、一組數(shù)值、一個(gè)枚舉值、一組枚舉值，一段文本信息等；被融合圖中的一條邊可以具有類型；被融合圖中的一條邊可以是一條有方向的邊，也可以是一條無(wú)方向的邊；