[發(fā)明專利]一種基于MITree的多維時(shí)間序列在線模體發(fā)現(xiàn)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202111160315.9
• 申請(qǐng)日: 2021-09-30
• 公開（公告）號(hào): CN113902003A
• 公開（公告）日: 2022-01-07
• 發(fā)明（設(shè)計(jì)）人: 王繼民;劉賽佳;朱旭
• 申請(qǐng)（專利權(quán)）人: 河海大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙) 32204
• 代理人: 柏尚春

本發(fā)明公開了一種基于多維實(shí)例樹的多維時(shí)間序列在線模體發(fā)現(xiàn)方法，包括如下步驟：首先使用單維時(shí)間序列模體挖掘方法KMotif挖掘初始滑動(dòng)窗口內(nèi)所有維度包含的K?模體；然后，基于預(yù)先定義的時(shí)間閾值，構(gòu)造模體實(shí)例鄰居；最后，構(gòu)建維護(hù)全局模體實(shí)例信息的MITree結(jié)構(gòu)；隨著新數(shù)據(jù)的到達(dá)，增量更新MITree結(jié)構(gòu)，實(shí)現(xiàn)在線挖掘多維模體。本發(fā)明通過構(gòu)造MITree結(jié)構(gòu)，利用前綴復(fù)用的樹形數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢，每次只需要將基本窗口內(nèi)的數(shù)據(jù)更新到樹結(jié)構(gòu)中，不需要重新對(duì)窗口內(nèi)的所有數(shù)據(jù)重新建立樹結(jié)構(gòu)，節(jié)省了時(shí)間開銷。本發(fā)明在線挖掘流時(shí)間序列中存在的多頻率出現(xiàn)的時(shí)間近似的同步多維模體。

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

本發(fā)明涉及信息處理方法，具體涉及一種基于MITree的多維時(shí)間序列模體在線發(fā)現(xiàn)方法。

背景技術(shù)

模體被定義為近似重復(fù)的序列、形狀、頻繁的趨勢、重復(fù)的模式等。對(duì)于單維模體的定義可以概括分為兩類：K-模體和最近鄰模體。模體挖掘可以通過無監(jiān)督的方式發(fā)現(xiàn)時(shí)間序列數(shù)據(jù)中重復(fù)出現(xiàn)、未知的、有意義的片段，進(jìn)而發(fā)現(xiàn)時(shí)間序列中的潛在規(guī)則和特定事件。隨著大數(shù)據(jù)時(shí)代的到來，在科學(xué)實(shí)驗(yàn)和正常的業(yè)務(wù)操作過程中時(shí)刻都在產(chǎn)生大量的數(shù)據(jù)，同時(shí)這些數(shù)據(jù)呈現(xiàn)多變量、高維度、大容量等特點(diǎn)。多維時(shí)間序列模體是指在多維時(shí)間序列的若干個(gè)維度上同時(shí)出現(xiàn)的重復(fù)模式或者片段。在挖掘多維時(shí)間序列模體時(shí)，需要能夠發(fā)現(xiàn)任意組合的多個(gè)維度上可能的模體。多維模體分析可以從由時(shí)序序列組成的多維序列數(shù)據(jù)中尋找有用的信息，在發(fā)現(xiàn)時(shí)序序列數(shù)據(jù)中內(nèi)在行為和規(guī)律的同時(shí)，反映不同維度時(shí)序序列之間的相互關(guān)系。在環(huán)境管理、醫(yī)療健康、基因工程等領(lǐng)域，進(jìn)行多維模體挖掘具有重要的現(xiàn)實(shí)意義。

目前對(duì)于時(shí)間序列模體挖掘的研究，主要集中在離線時(shí)間序列模體發(fā)現(xiàn)，對(duì)于在線模體挖掘算法的研究較少。

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

發(fā)明目的：為了克服現(xiàn)有技術(shù)中存在的問題，本發(fā)明的目的是提供一種基于多維實(shí)例樹(簡稱：MITree)的多維時(shí)間序列在線模體發(fā)現(xiàn)方法，能夠在線發(fā)現(xiàn)多維時(shí)間序列中存在的多實(shí)例模體信息。

技術(shù)方案：一種基于MITree的多維時(shí)間序列在線模體發(fā)現(xiàn)方法，包括如下步驟：

(1)首先對(duì)基本窗口內(nèi)的時(shí)間序列逐維提取單維時(shí)間序列中的模體，得到單維模體實(shí)例；基于時(shí)間閾值，將所有的單維模體實(shí)例劃分為模體實(shí)例鄰居；

(2)利用發(fā)現(xiàn)的模體實(shí)例鄰居構(gòu)造并更新MITree樹結(jié)構(gòu)；基于MITree樹在線發(fā)現(xiàn)最新的多維模體。

進(jìn)一步的，步驟(1)中，提取單維模體實(shí)例的具體方式為：

采用長度為m的滑動(dòng)窗口對(duì)時(shí)間序列生成子序列，計(jì)算子序列之間的相關(guān)系數(shù)，構(gòu)造相關(guān)系數(shù)矩陣；通過相關(guān)系數(shù)定義兩個(gè)子序列之間的相似度；相關(guān)系數(shù)越高表明兩個(gè)子序列越相似；

去除相關(guān)系數(shù)矩陣中不滿足相關(guān)系數(shù)閾值條件的子序列，，然后將相關(guān)系數(shù)由高到低此時(shí)得到所有子序列滿足條件的匹配序列集合；在每個(gè)維度上提取前k個(gè)K-模體，構(gòu)成K-Motif集合(以下稱為K-Motifs)；按照基于頻率的K-Motifs的定義輸出單維模體 K-Motifs結(jié)果。

進(jìn)一步的，步驟(1)中，構(gòu)造模體實(shí)例鄰居的具體方式為：

使用三元組[dim,k,timestamp]描述所有的單維模體實(shí)例，其中dim表示該模體屬于多維時(shí)間序列哪個(gè)維度序列，k表示屬于該dim維度中第k重要的模體，timestamp描述該模體實(shí)例在原始時(shí)間序列中的開始位置；

基于預(yù)先定義的時(shí)間閾值td，將滿足閾值條件的不同維度的單維模體實(shí)例置入相同的模體實(shí)例鄰居之中；對(duì)于兩個(gè)不同維度的模體實(shí)例[dim1,k1,timestamp1]和 [dim2,k2,timestamp2]，如果滿足條件|timestamp1-timestamp2|＜td，則這兩個(gè)模體實(shí)例屬于鄰居，多個(gè)互為鄰居的模體實(shí)例構(gòu)成一個(gè)模體實(shí)例鄰居；