[發(fā)明專利]一種基于圖結(jié)構(gòu)的數(shù)據(jù)動(dòng)態(tài)分類方法與系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 202010940819.1
• 申請(qǐng)日: 2020-09-09
• 公開（公告）號(hào): CN112084377A
• 公開（公告）日: 2020-12-15
• 發(fā)明（設(shè)計(jì)）人: 高躍;馮玉彤
• 申請(qǐng)（專利權(quán)）人: 清華大學(xué)
• 主分類號(hào): G06F16/901
• 分類號(hào): G06F16/901;G06F16/906;G06F16/23
• 代理公司: 北京律譜知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11457
• 代理人: 黃云鐸;孫紅穎

本發(fā)明公開了一種基于圖結(jié)構(gòu)的數(shù)據(jù)動(dòng)態(tài)分類系統(tǒng)，該系統(tǒng)包括如下單元：圖數(shù)據(jù)輸入單元用于接收動(dòng)態(tài)輸入的圖結(jié)構(gòu)數(shù)據(jù)；數(shù)據(jù)及模型存儲(chǔ)單元用于保存已輸入數(shù)據(jù)及保存當(dāng)前時(shí)刻的分類模型參數(shù)；圖連續(xù)學(xué)習(xí)單元用于根據(jù)輸入圖數(shù)據(jù)動(dòng)態(tài)學(xué)習(xí)分類并更新模型，其中學(xué)習(xí)圖生成單元用于生成指定空間限制下的學(xué)習(xí)圖，圖學(xué)習(xí)單元用于根據(jù)學(xué)習(xí)圖更新分類模型參數(shù)；分類預(yù)測單元用于對(duì)無標(biāo)簽的數(shù)據(jù)給出分類預(yù)測結(jié)果。本發(fā)明還公開了一種基于圖結(jié)構(gòu)的數(shù)據(jù)動(dòng)態(tài)分類方法，本發(fā)明的系統(tǒng)和方法能夠動(dòng)態(tài)學(xué)習(xí)不斷更新的圖結(jié)構(gòu)數(shù)據(jù)，可被用于社交網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、蛋白質(zhì)網(wǎng)絡(luò)等持續(xù)更新的圖數(shù)據(jù)庫。

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

本發(fā)明涉及圖數(shù)據(jù)處理領(lǐng)域，尤其涉及一種基于圖結(jié)構(gòu)的數(shù)據(jù)動(dòng)態(tài)分類方法與系統(tǒng)。

背景技術(shù)

圖數(shù)據(jù)結(jié)構(gòu)通過其自身拓?fù)浣Y(jié)構(gòu)來表征數(shù)據(jù)間的復(fù)雜關(guān)聯(lián)關(guān)系，基于圖結(jié)構(gòu)的數(shù)據(jù)分類是一項(xiàng)廣泛應(yīng)用的分類技術(shù)，借助于數(shù)據(jù)間的關(guān)聯(lián)，實(shí)現(xiàn)學(xué)習(xí)少量數(shù)據(jù)的標(biāo)簽信息并預(yù)測剩余數(shù)據(jù)分類結(jié)果。但此類技術(shù)處理的圖結(jié)構(gòu)往往是靜態(tài)的，在現(xiàn)實(shí)應(yīng)用中，圖數(shù)據(jù)存在動(dòng)態(tài)變化，例如數(shù)據(jù)的變動(dòng)和新數(shù)據(jù)的加入，對(duì)于此類數(shù)據(jù)每次進(jìn)行靜態(tài)圖數(shù)據(jù)學(xué)習(xí)會(huì)耗費(fèi)大量的計(jì)算資源，因此對(duì)已有技術(shù)提出了挑戰(zhàn)，需要一種能夠處理動(dòng)態(tài)圖結(jié)構(gòu)數(shù)據(jù)的高效分類技術(shù)和方法。該技術(shù)既需要對(duì)不斷輸入的圖數(shù)據(jù)保持較低的計(jì)算學(xué)習(xí)效率，還需要時(shí)刻保持對(duì)全部已輸入數(shù)據(jù)的有效分類。

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

為了高效且持續(xù)化地學(xué)習(xí)和處理動(dòng)態(tài)圖結(jié)構(gòu)數(shù)據(jù)，本發(fā)明提供了一種基于圖結(jié)構(gòu)的數(shù)據(jù)動(dòng)態(tài)分類系統(tǒng)，能夠以較低計(jì)算效率保持對(duì)動(dòng)態(tài)變化圖數(shù)據(jù)的分類效果。

本發(fā)明的技術(shù)方案是提供一種基于圖結(jié)構(gòu)的數(shù)據(jù)動(dòng)態(tài)分類系統(tǒng)，包括：圖數(shù)據(jù)輸入單元；數(shù)據(jù)及模型存儲(chǔ)單元，圖連續(xù)學(xué)習(xí)單元，分類預(yù)測單元，其特征在于：

圖數(shù)據(jù)輸入單元用于接收動(dòng)態(tài)輸入的圖結(jié)構(gòu)數(shù)據(jù)，輸入的圖數(shù)據(jù)包含新添加的節(jié)點(diǎn)和邊，以及新節(jié)點(diǎn)與舊節(jié)點(diǎn)的連接關(guān)系，在動(dòng)態(tài)輸入下全體數(shù)據(jù)將形成一個(gè)不斷擴(kuò)張的圖結(jié)構(gòu)。

數(shù)據(jù)及模型存儲(chǔ)單元用于保存已輸入數(shù)據(jù)及保存當(dāng)前時(shí)刻的分類模型參數(shù)；

其中數(shù)據(jù)及模型存儲(chǔ)單元的數(shù)據(jù)存儲(chǔ)部分根據(jù)所述動(dòng)態(tài)輸入圖數(shù)據(jù)進(jìn)行更新，從而維護(hù)整個(gè)不斷擴(kuò)張的圖數(shù)據(jù)；數(shù)據(jù)及模型存儲(chǔ)單元的模型參數(shù)部分通過圖連續(xù)學(xué)習(xí)單元更新，保持對(duì)已輸入全體數(shù)據(jù)的有效分類。

圖連續(xù)學(xué)習(xí)單元，對(duì)新輸入的圖數(shù)據(jù)進(jìn)行學(xué)習(xí)，在限制每次輸入新數(shù)據(jù)后的時(shí)間、空間復(fù)雜度要求下，通過構(gòu)造學(xué)習(xí)圖使得數(shù)據(jù)及模型存儲(chǔ)單元內(nèi)的模型參數(shù)能夠保持對(duì)現(xiàn)有數(shù)據(jù)的良好分類；

分類預(yù)測單元，在任意時(shí)刻調(diào)用分類預(yù)測單元，能夠?qū)σ延袛?shù)據(jù)中無標(biāo)簽數(shù)據(jù)進(jìn)行分類預(yù)測，其中預(yù)測方法為讀取數(shù)據(jù)及模型存儲(chǔ)單元中模型參數(shù)進(jìn)行預(yù)測。

進(jìn)一步地，圖連續(xù)學(xué)習(xí)單元包括學(xué)習(xí)圖生成單元和圖學(xué)習(xí)單元，學(xué)習(xí)圖生成單元生成用于本次學(xué)習(xí)的圖數(shù)據(jù)結(jié)構(gòu)；圖學(xué)習(xí)單元用于接收所述學(xué)習(xí)圖，通過圖學(xué)習(xí)方法進(jìn)行普通的分類學(xué)習(xí)，學(xué)習(xí)方式為半監(jiān)督學(xué)習(xí)，通過給出少部分節(jié)點(diǎn)的標(biāo)簽信息，通過節(jié)點(diǎn)間的信息傳遞學(xué)習(xí)和預(yù)測無標(biāo)簽節(jié)點(diǎn)的標(biāo)簽信息。

進(jìn)一步地，學(xué)習(xí)圖生成策略包括采樣方法和聚類方法，其中，采樣方法通過計(jì)算新數(shù)據(jù)輸入前后節(jié)點(diǎn)度的變化，在允許空間限制下優(yōu)先選取節(jié)點(diǎn)度提升比例高的節(jié)點(diǎn)加入學(xué)習(xí)圖；聚類方法通過對(duì)舊數(shù)據(jù)中的節(jié)點(diǎn)進(jìn)行聚類，將每個(gè)聚類簇作為新節(jié)點(diǎn)加入學(xué)習(xí)圖中，其特征值為簇內(nèi)節(jié)點(diǎn)的均值，其連接關(guān)系為簇內(nèi)節(jié)點(diǎn)連接關(guān)系的并集。

本發(fā)明還提供了一種基于圖結(jié)構(gòu)的數(shù)據(jù)動(dòng)態(tài)分類方法，具體包括以下步驟：

步驟1、通過圖數(shù)據(jù)輸入單元，接收動(dòng)態(tài)輸入的圖結(jié)構(gòu)數(shù)據(jù)，輸入的圖數(shù)據(jù)包含新添加的節(jié)點(diǎn)和邊，以及新節(jié)點(diǎn)與舊節(jié)點(diǎn)的連接關(guān)系，在動(dòng)態(tài)輸入下，全體數(shù)據(jù)將形成一個(gè)不斷擴(kuò)張的圖結(jié)構(gòu)；