[發明專利]一種基于MITree的多維時間序列在線模體發現方法

在審

• 申請號: 202111160315.9
• 申請日: 2021-09-30
• 公開（公告）號: CN113902003A
• 公開（公告）日: 2022-01-07
• 發明（設計）人: 王繼民;劉賽佳;朱旭
• 申請（專利權）人: 河海大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

1.一種基于MITree的多維時間序列在線模體發現方法，其特征在于，包括如下步驟：

(1)首先對基本窗口內的時間序列逐維提取單維時間序列中的K模體，得到單維模體實例；基于時間閾值，在所有的單維模體實例中劃分模體實例鄰居；

(2)利用劃分的模體實例鄰居構造和更新MITree樹結構；

(3)基于MITree樹中的信息在線發現最新的多維模體。

2.根據權利要求1所述的一種基于MITree的多維時間序列在線模體發現方法，其特征在于，步驟(1)中，提取單維模體實例的具體方式為：

采用長度為m的滑動窗口對時間序列生成子序列，計算子序列之間的相關系數，構造相關系數矩陣，通過相關系數定義兩個子序列之間的相似度，相關系數越高表明兩個子序列越相似；

去除相關系數矩陣中不滿足相關系數閾值條件的子序列和平凡匹配的子序列，然后將相關系數由高到低此時得到所有子序列滿足條件的匹配序列集合；在每個維度上提取前k個K-模體，構成K-Motif集合。

3.根據權利要求1所述的一種基于MITree的多維時間序列在線模體發現方法，其特征在于，步驟(1)中，構造模體實例鄰居的具體方式為：

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

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

4.根據權利要求1所述的一種基于MITree的多維時間序列在線模體發現方法，其特征在于，步驟(2)中，所述MITree樹結構包括頭指針表headTable和模體實例樹結構；所述頭指針表headTable存儲從各維度提取的所有K-Motifs信息，包括模體所在的維度dim、所屬模體K、頻率Frequency、時間列表timeList、是否更新Modify、更新次數Count、是否是新的K-Motif信息New。其中，所述頻率Frequency即模體實例個數，時間列表timeList即模體實例出現的位置。

5.根據權利要求4所述的一種基于MITree的多維時間序列在線模體發現方法，其特征在于，步驟(2)中，構造MITree樹結構的具體方式為：

針對每個模體實例鄰居中的模體實例，按照各實例的所屬K-模體的頻率從高到低進行排序；

基于模體實例構造的模體實例鄰居，將所有的模體實例鄰居中的單維模體實例按照維度由低到高順序排列；將排序完畢的模體實例鄰居順序插入MITree結構中，同一個模體實例鄰居中，排序在前的模體實例對應樹路徑中的祖先節點，排序在后的項集對應子孫節點；當所有的模體實例鄰居插入完畢時，MITree結構構造完成。