[發明專利]事件模式頻繁子圖挖掘與預測方法

有效

• 申請號: 202011190740.8
• 申請日: 2020-10-30
• 公開（公告）號: CN112287118B
• 公開（公告）日: 2023-06-02
• 發明（設計）人: 崔瑩;代翔;戴禮燦;楊露;潘磊
• 申請（專利權）人: 西南電子技術研究所(中國電子科技集團公司第十研究所)
• 主分類號: G06F16/36
• 分類號: G06F16/36;G06F16/34;G06F16/33
• 代理公司: 成都九鼎天元知識產權代理有限公司 51214
• 代理人: 陳慶

1.一種事件模式頻繁子圖挖掘與預測方法，其特征在于包括如下步驟：基于密度的圖摘要階段和頻繁子圖的事件模式挖掘階段，在基于密度的圖摘要階段，把密度圖摘要圖中的節點劃分成簇或者超級節點，著眼于最大程度的保存原始圖的節點和邊緣，依次選取節點集合V密度大的節點開始進行摘要，構建一個簡潔的高層次的圖；

事件圖譜由事件相關元素構成，包含所有歷史事件的發生、發展過程，以及不同事件間的關系，事件模式是事件的屬性與關系的組合，包括事件的前導事件、與前導事件的關系，以及事件及與其前導事件的類型、地點、參與者以及發生時間；

在模式挖掘階段，基于事件圖譜開展事件模式挖掘，在大規模的事件圖譜上進行頻繁子圖挖掘，基于密度的圖摘要和頻繁子圖的事件模式挖掘頻繁子圖，即在事件圖譜的圖集中找到頻繁出現的子圖，然后將基于密度的圖摘要算法分為3個階段：預處理階段，頻繁子圖挖掘階段和結果輸出階段，在預處理階段，采用基于密度的圖摘要算法對輸入圖G進行摘要，產生摘要圖G_s＝(V_s，E_s)，然后以摘要結果為輸入，利用校正集C得到摘要結果R＝(G_s,C)，以摘要結果為輸入，在事件圖譜上有效地開展事件模式挖掘及事件發生預測，進行頻繁子圖挖掘階段處理和基于圖摘要的挖掘預處理；

最后，在大規模的事件圖譜上快速的進行頻繁子圖挖掘，利用多源數據，從多方來源多個角度進行事件模式的挖掘與預測，根據用戶定義的最小支持度min_sup或其它輸出標準進行候選集過濾和頻繁子圖輸出，其中，V_s為超級節點集合，E_s表示超級節點邊集合。

2.如權利要求1所述的事件模式頻繁子圖挖掘與預測方法，其特征在于：基于密度的圖摘要階段：采用基于密度的圖摘要算法DSG，根據最小描述長度原則，引入密度的思想進行圖摘要；結合基于密度的子圖發掘算法，對隨機算法Randomized進行改進，在算法初始化時，計算所有節點集合V的密度，按節點密度由大到小進行排序依次進行摘要，并由聚類在一起的相似節點共同作用得到超節點，超節點之間的連邊由聚類分配矩陣和原鄰接矩陣共同作用得到改進了的隨機算法Randomized。

3.如權利要求2所述的事件模式頻繁子圖挖掘與預測方法，其特征在于：隨機算法Randomized對于節點集合V＝(v₁，v₂，…v_n)，依次計算每個節點的密度ρ，密度ρ的計算公式ρ＝ρ₁+αρ₂，0＜α＜1，將節點和節點密度保存在集合U中，然后對集合U按照密度由大到小進行排序，在摘要過程中，依次選取密度大的節點開始進行摘要，其中，ρ₁為一步長密度，ρ₂為二步長密度，α為系數。

4.如權利要求1所述的事件模式頻繁子圖挖掘與預測方法，其特征在于：在預處理階段，對輸入圖G進行如下處理：如果輸入圖G是標號圖，即節點和邊均帶有標簽，則將輸入圖輸入基于密度的圖摘要算法；如果輸入圖G是邊標號圖，即只有邊帶有標簽，而節點沒有標簽，則對于所有節點賦予相同標簽，然后將輸入圖輸入基于密度的圖摘要算法；如果輸入圖G是點標號圖，即只有節點帶有標簽，而邊沒有標簽，則對于所有邊賦予相同標簽，然后將輸入圖輸入基于密度的圖摘要算法；如果輸入圖G是簡單圖，即節點和邊均沒有標簽，則對所有節點賦予相同標簽，對所有邊賦予相同標簽，然后將輸入圖輸入基于密度的圖摘要算法；由進行完摘要之后，產生摘要圖G_s＝(V_s，E_s)，輸出摘要結果R＝(G_s，C)，將校正集C中的邊，加入與其相關的較小的超級節點中產生新的超級節點集合V_s；V_s中的每個節點v_s都是原輸入圖G的一個子圖。