[發明專利]基于子序列全連接和最大團的時間序列模體發現方法

在審

• 申請號: 201810895890.5
• 申請日: 2018-08-08
• 公開（公告）號: CN109241118A
• 公開（公告）日: 2019-01-18
• 發明（設計）人: 王繼民;朱躍龍;朱曉曉;張鵬程
• 申請（專利權）人: 河海大學
• 主分類號: G06F16/2457
• 分類號: G06F16/2457;G06F16/2458
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 李玉平

1.一種基于子序列全連接和最大團的時間序列模體發現方法，其特征在于，包括以下步驟：

(1)子序列全連接

使用長度為m的滑動窗口應用嵌套循環計算時間序列T中所有子序列之間的距離；

(2)構建子序列相似圖

定義相似性閾值，小于相似性閾值的距離值用1表示，其他距離值用0表示，將距離矩陣轉換為鄰接矩陣；根據鄰接矩陣得到圖，此圖稱為子序列相似圖；

(3)尋找最大團

使用最大團算法解決子序列相似圖的最大團問題；所得最大團的頂點對應時間序列模體的實例。

2.根據權利要求1所述的基于子序列全連接和最大團的時間序列模體發現方法，其特征在于，所述步驟(1)中使用“超快速”的MASS算法得到距離矩陣；該算法的“超快速”在于其先對數據進行了快速傅里葉變換，然后執行點積操作，將點積操作結果再進行逆傅里葉變換，最后將逆傅里葉變換后的結果用于計算基于z-歸一化的歐式距離，得到距離矩陣Distance Matrix。

3.根據權利要求2所述的基于子序列全連接和最大團的時間序列模體發現方法，其特征在于，所述步驟(1)中歐氏距離Dist[i]公式如下：

其中，m為子序列的長度，μ_Q為時間序列子序列Q的平均值，σ_Q為時間序列子序列Q的標準差，M_T為時間序列子序列T_i,m的平均值，∑_T為時間序列子序列T_i,m的標準差。

4.根據權利要求1所述的基于子序列全連接和最大團的時間序列模體發現方法，其特征在于，距離矩陣中存在平凡匹配的子序列的距離值設置為inf，相似性閾值eps＝6，距離值小于eps時，距離元素用1表示，大于相似性閾值或為inf時用0表示，最終得到相似鄰接矩陣。

5.根據權利要求1所述的基于子序列全連接和最大團的時間序列模體發現方法，其特征在于，所述步驟(3)中，使用的最大團算法提出一個新的目標函數:

其中參數d≥0，假設圖G的鄰接矩陣為A，u為函數的局部極小值，定義相關的改進鄰接矩陣為B＝A+I_n，M_d＝(1+d)B-d1_n×n，其中I_n為n階的單位矩陣，1_n×n為元素全1的n×n矩陣；目標函數的局部最小值對應圖G的極大團，全局最小值對應圖G的最大團；使用梯度下降算法作為迭代算法，利用Armijo準則調節步長，求解目標函數的最優解，該最優解對應圖G的最大團。