[發(fā)明專利]事件模式頻繁子圖挖掘與預(yù)測(cè)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011190740.8
• 申請(qǐng)日: 2020-10-30
• 公開（公告）號(hào): CN112287118B
• 公開（公告）日: 2023-06-02
• 發(fā)明（設(shè)計(jì)）人: 崔瑩;代翔;戴禮燦;楊露;潘磊
• 申請(qǐng)（專利權(quán)）人: 西南電子技術(shù)研究所(中國(guó)電子科技集團(tuán)公司第十研究所)
• 主分類號(hào): G06F16/36
• 分類號(hào): G06F16/36;G06F16/34;G06F16/33
• 代理公司: 成都九鼎天元知識(shí)產(chǎn)權(quán)代理有限公司 51214
• 代理人: 陳慶

本發(fā)明公開的一種事件模式頻繁子圖挖掘與預(yù)測(cè)方法，涉及知識(shí)工程技術(shù)領(lǐng)域，旨在降低挖掘開銷，提升挖掘速度。本發(fā)明通過下述技術(shù)方案實(shí)現(xiàn)：在基于密度的圖摘要階段將基于密度圖摘要圖中的節(jié)點(diǎn)劃分成簇或者超級(jí)節(jié)點(diǎn)，依次選取節(jié)點(diǎn)構(gòu)建一個(gè)簡(jiǎn)潔的高層次的圖；在模式挖掘階段，在大規(guī)模的事件圖譜上進(jìn)行頻繁子圖挖掘，基于事件模式挖掘頻繁子圖，在事件圖譜的圖集中找到頻繁出現(xiàn)的子圖；基于圖摘要算法對(duì)輸入圖G進(jìn)行摘要，以摘要結(jié)果為輸入進(jìn)行頻繁子圖挖掘和基于圖摘要的挖掘預(yù)處理；最后，利用多源數(shù)據(jù)，從多方來源多個(gè)角度進(jìn)行事件模式的挖掘與預(yù)測(cè)，根據(jù)用戶定義的最小支持度min_sup或其他輸出標(biāo)準(zhǔn)進(jìn)行候選集過濾和頻繁子圖輸出。

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

本發(fā)明涉及知識(shí)工程技術(shù)領(lǐng)域，尤其涉及事件模式頻繁子圖挖掘與預(yù)測(cè)方法。

背景技術(shù)

知識(shí)圖譜，最早起源于GoogleKnowledgeGraph。知識(shí)圖譜本質(zhì)上是一種語義網(wǎng)絡(luò)。其結(jié)點(diǎn)代表實(shí)體(entity)或者概念(concept)，邊代表實(shí)體/概念之間的各種語義關(guān)系。

事件圖譜作為一類典型的知識(shí)圖譜，目前尚未得到充分有效利用，其潛在價(jià)值亟待開發(fā)利用。事件圖譜主要由事件相關(guān)元素構(gòu)成，包含了所有歷史事件的發(fā)生、發(fā)展的整個(gè)過程，同時(shí)也描述的不同事件間的承接、順序、因果等關(guān)系。如果對(duì)事件圖譜進(jìn)行仔細(xì)的分析，挖掘出其中所包含的事件的規(guī)律和模式，那么就可以通過這種規(guī)律和模式來對(duì)未來的事件進(jìn)行預(yù)測(cè)。這就是基于事件圖譜的事件預(yù)測(cè)的基本出發(fā)點(diǎn)。

事件模式是事件的屬性和關(guān)系的組合，包括事件的前導(dǎo)事件，與前導(dǎo)事件見的關(guān)系，以及事件及其前導(dǎo)事件的類型、地點(diǎn)、參與者以及(周期性)發(fā)生時(shí)間等。通過研究分析，一些高頻的事件模式在三個(gè)月的時(shí)間窗口中可以出現(xiàn)多達(dá)10次以上，是十分優(yōu)秀的預(yù)測(cè)指標(biāo)。但是絕大多數(shù)事件模式只出現(xiàn)一次。所以，我們必須在大量的事件模式中尋找頻繁出現(xiàn)的模式，以之作為候選模式集來預(yù)測(cè)事件。于是，基于事件圖譜的事件預(yù)測(cè)問題就轉(zhuǎn)換成了事件圖譜上的頻繁子圖挖掘問題。目前，基于時(shí)間屬性的事件挖掘技術(shù)主要集中在序列模式和時(shí)間模式挖掘兩個(gè)方面，其中大多數(shù)關(guān)于事件模式挖掘的研究都是根據(jù)序列模式研究的基序列模式挖掘技術(shù)，挖掘序列模式就是挖掘與時(shí)間或其他序列有關(guān)的頻繁發(fā)生的模式。在序列模式的挖掘中，輸入數(shù)據(jù)集是一組序列，叫做數(shù)據(jù)序列。每個(gè)數(shù)據(jù)序列有一系列交易組成，每個(gè)交易是一組項(xiàng)目集。通常，每個(gè)交易都有一個(gè)與之相關(guān)聯(lián)的交易時(shí)間，對(duì)于間隔事件而言，交易時(shí)間是一個(gè)事件間隔。序列模式挖掘的任務(wù)是對(duì)于一個(gè)用戶指定的最小支持度，發(fā)現(xiàn)所有的序列模式。一個(gè)序列模式的支持度是指輸入數(shù)據(jù)集中包含該模式的數(shù)據(jù)序列的百分序列模式挖掘的第一類算法是基于Apriori的算法，Apriori的中心思想是在每個(gè)第k-1自連接生成。這里的頻繁序列中所有滿足用戶指定支持度閾值的序列。基于密度的圖摘要算法(DenseSummarizeGraph,DSG)。受DBSCAN算法的啟發(fā),也采用一定的核心對(duì)象代表若干個(gè)數(shù)據(jù)點(diǎn),但其核心對(duì)象是虛擬的點(diǎn),不是實(shí)際輸入的數(shù)據(jù)。1DBSCAN算法基于密度的聚類的關(guān)鍵思想是:對(duì)于聚類中的每一個(gè)對(duì)象,在給定的半徑(e)的鄰域中至少要包含最小數(shù)目(MinPts)個(gè)對(duì)象,即鄰域的基數(shù)(元組數(shù))必須超過一個(gè)閾值。DBSCAN算法根據(jù)以上的定義在數(shù)據(jù)庫中發(fā)現(xiàn)噪聲與聚類,其基礎(chǔ)是一個(gè)聚類等價(jià)于集合D中核心對(duì)象密度可達(dá)的所有對(duì)象的集合.密度可達(dá)對(duì)象的檢索是通過反復(fù)收集直接密度可達(dá)對(duì)象而實(shí)現(xiàn)的。化學(xué)信息學(xué)、生物信息學(xué)、醫(yī)學(xué)和社會(huì)科學(xué)等領(lǐng)域的科學(xué)研究的迅速發(fā)展積累了大量的圖數(shù)據(jù)，如何從復(fù)雜和龐大的圖數(shù)據(jù)中挖掘出有效信息成為數(shù)據(jù)挖掘領(lǐng)域的熱點(diǎn)。