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

在審

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

本發明公開一種基于子序列全連接和最大團的時間序列模體發現方法。步驟為：1.子序列全連接：使用長度為m的滑動窗口應用嵌套循環計算時間序列T中所有子序列之間的距離；2.構造子序列相似圖：定義相似性閾值，小于相似性閾值的距離用1表示，其他距離值用0表示。將距離矩陣Distance Matrix轉化為對應的鄰接矩陣；3.尋找最大團：使用最大團搜索算法搜索通過圖的鄰接矩陣尋找子序列相似圖中的最大團。最大團頂點對應的時間序列子序列為模體。通過本發明利用子序列全連接和最大團算法發現時間序列模體，提高了時間序列模體發現的效率，解決了已有時間序列模體發現算法無法發現多條模體的問題。

技術領域

本發明涉及一種基于子序列全連接和最大團的時間序列模體發現方法，涉及信息處理技術領域。

背景技術

時間序列是按時間順序排列的、具有相等時間間隔的一系列數據的集合。時間序列無處不在，使其在各個行業獲得普遍的應用。例如金融領域的證券交易數據、氣象領域的氣溫氣壓數據、工業領域的用電數據、醫學領域的腦電波和心電圖數據等等。在時間序列數據挖掘的諸多問題中，時間序列的模式發現是一個基礎性問題。時間序列中的頻繁模式、異常模式、周期模式對時間序列的關聯規則發現，異常檢測，預測等有重要作用。時間序列的模式發現包括查找事先指定模式和預先未知的模式。查找事先指定模式的問題(即按內容查詢)已有諸多解決方法。然而，查找預先未知，重復出現的模式即時間序列模體發現(也稱為時間序列的序列主題發現)問題則面臨更多挑戰。模體發現問題對于時間序列挖掘具有重要意義，可以用于解決數據劃分，海量時間序列數據庫的可視化與歸類，包括聚類、分類、關聯規則發現等問題。現有的模體發現算法存在計算復雜，并且無法發現多條模體的缺點，提高模體發現的效率，發現更多的模體是一個重要的研究方向。

發明內容

發明目的：針對現有技術中存在的問題，本發明提供一種基于子序列全連接和最大團的時間序列模體發現方法，通過子序列連接，構建子序列相似圖，尋找最大團三個步驟以高效地發現時間序列中的多條模體。

技術方案：一種基于子序列全連接和最大團的時間序列模體發現方法，包括以下步驟：

(1)子序列全連接

使用長度為m的滑動窗口應用嵌套循環計算時間序列T中所有子序列之間的距離(即時間序列T的自連接)，此過程使用“超快速”的MASS算法得到距離矩陣(DistanceMatrix)。該算法的“超快速”在于其先對數據進行了快速傅里葉變換，然后執行點積操作，將點積操作的結果再進行逆傅里葉變換。上述操作代替了計算復雜度較高的卷積操作。最后將逆傅里葉變換的結果用于計算基于z-歸一化的歐式距離，得到距離矩陣DistanceMatrix。MASS算法的基本步驟為首先計算時間序列子序列Q和T之間的滑動點積，然后時間序列子序列Q和T的均值和方差，最后計算時間序列子序列之間Q和T的z-歸一化的歐氏距離，返回時間序列子序列Q和T之間的距離值。

MASS算法首先調用了SlidingDotProducts算法，SlidingDotProducts算法主要功能是計算QT[i]的值。SlidingDotProducts算法包括對兩個向量的經典卷積運算，算法將采用快速傅里葉變換和逆快速傅里葉變換替代計算復雜的卷積操作，從而提高MASS算法的速度。因為MASS算法采用z-歸一化的歐氏距離Dist[i]作為時間序列子序列Q與T_i,m之間的距離度量，其需要進行時間序列子序列Q與T_i,m之間的點積計算QT[i]，歐氏距離Dist[i]公式如下：