[發明專利]一種時間序列中不定長的異常子序列檢測方法

在審

• 申請號: 202110226782.0
• 申請日: 2021-03-01
• 公開（公告）號: CN112966017A
• 公開（公告）日: 2021-06-15
• 發明（設計）人: 陳逸舟;張丹;熊曉菁
• 申請（專利權）人: 北京青萌數海科技有限公司
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/28
• 代理公司: 北京智沃律師事務所 11620
• 代理人: 吳志宏

本發明提供了一種時間序列中不定長的異常子序列檢測方法，在異常子序列的定義采用K近鄰距離的均值/中位數，在子序列距離計算基于STOMP算法進行了并行優化，在算法參數設置用輸入子序列長度范圍和步長，在算法輸出直接輸出各個長度下的異常子序列檢測結果，從中發現不同的異常點，也能夠基于上述檢測結果和一定的評價指標輸出異常程度分值以及判斷得到的異常子序列結果。所述時間序列中不定長的異常子序列檢測方法能夠顯著提升時間序列異常子序列檢測的運行效率和檢測準確率。

技術領域

本發明涉及一種數據挖掘算法領域中的時間序列異常檢測，尤其是涉及一種時間序列中不定長的異常子序列檢測方法。

背景技術

目前異常檢測作為一個廣泛的技術領域，已經在大量的實際場景中得到了應用，并且對于不同的業務領域和數據類型，通常需要應用不同類型的專用技術方法。時間序列異常檢測是針對按時間排布的數據中的離群值進行識別，它可以在非常多的應用領域中發揮作用，例如：在金融市場中，檢測股票市場的突然變化、或特定時間窗口內的異常模式；系統運行診斷方面，可以用于監控設備運行狀況、檢測異常入侵等；在生物領域，由于氨基酸的排列與時間序列數據特征類似，也可以應用時間序列方面的檢測方法。由于不同領域產生的數據特征和提出的業務需求不同，時間序列異常檢測領域也發展出了眾多不同的方法：從數據維度上看，可以分為單序列和多維度數據異常檢測方法；從異常定義上看，可以分為數據點異常和窗口異常檢測；從算法實現角度，又可以分為有監督和無監督的異常檢測算法。

目前研究和應用較多的時間序列異常檢測算法大多是針對單個數據點異常進行檢測，即輸出時間序列中每個數據點的異常概率，進而通過設置閾值來判斷數據點是否屬于異常，這類方法主要針對時間序列中單獨出現的異常(例如心電圖數據中一次異常跳動)進行檢測。然而在實際應用場景中，往往需要對持續一段時間的模式異常(例如心律失常癥狀下心電圖的模式異常)進行識別，此時使用異常子序列檢測算法是更優的選擇。

給定一個長度為n時間序列數據，一段長度為L、起始位置為i的子序列可以表示為。目前普遍使用的異常子序列的定義為：時間序列T中擁有最大的最近鄰距離的子序列，即對于子序列D以及任意的子序列C，以及相應的非重疊子序列集合M_D和M_C，若，則子序列D為時間序列T中的異常子序列。最基礎的定義中使用歐氏距離衡量兩條時間序列的距離，在實際應用中可以使用其他合理的距離度量；另外其對于異常子序列的定義也可以很輕易地拓展到輸出多個異常子序列。

然而，異常子序列的檢測還面臨計算效率低、參數依賴、相似異常識別等方面的困難。首先是計算效率方面，根據上文所述的異常子序列定義，最直接的實現方式即是通過循環計算每兩個子序列之間的距離，從中提取異常子序列，而這種算法的時間復雜度為(其中n為時間序列長度，m為子序列長度)，并且往往時間序列數據的長度較大，因此基于蠻力的算法幾乎是無法完成的。近年來有許多研究針對這一問題，通過將時間序列降維表示和預排序、或者通過設定距離閾值等方式，提出了各種改進效率的算法。其中前者多為啟發式算法，實際計算效率與多個參數的設置、實際數據特征情況均有較強的關聯，當參數設置不當或數據分布不滿足預期時，算法的效率可能會降低到；后者通過設定閾值的方式對距離計算過程進行剪枝，同樣對該閾值的設定有很強的依賴性，閾值設置不合理會導致算法失敗(無法返回任何異常子序列)或效率降低到，并且該閾值很難通過事前經驗進行估計。Yeh等人(2018)提出了一種突破性的算法STOMP，其核心在于通過快速傅里葉變換和移動點積的方法，極大的優化了子序列兩兩之間的距離計算效率，并且計算過程不依賴于其他參數的設定或數據的分布特征，使得在大規模數據集上計算距離成為可行且可預估的。