時間序列分割演算法

❶ 時間序列分類演算法

歐式距離不能很好地針對時間序列的波動模式進行分類，研發更適合時間序列分類的距離度量就成為關鍵，這其中最經典的時間序列距離度量就是Dynamic Time Warping （DTW）。 DTW的原理如下：

比如說，給定一個樣本序列X和比對序列Y,Z：
X：3，5，6，7，7，1
Y：3，6，6，7，8，1，1
Z：2，5，7，7，7，7，2
請問是X和Y更相似還是X和Z更相似？
DTW首先會根據序列點之間的距離(歐氏距離)，獲得一個序列距離矩陣 MM，其中行對應X序列，列對應Y序列，矩陣元素為對應行列中X序列和Y序列點到點的歐氏距離：

DTW通過對時間序列波動模式的分析可得到更好的時間序列分類結果。研究表明，在時間序列分類問題上，DTW距離度量配合簡單的最小距離分類法（nearest neighbor）就可以取得較傳統歐式距離演算法（如SVM、經典多層神經網路、決策樹、Adaboost）壓倒性的優勢。

DTW更進一步衍生出多種不同的變種，例如由Keogh和 Pazzani 提出的基於序列一階導數的改進便取得了良好的效果；其中一種簡單的方法叫Complexity Invariant distance (CID)，其利用一階導數信息對DTW距離做計算，在某些問題上具有突出效果。

除了DTW，還有其他考量時間序列的波動模式演算法。例如Ye 和Keogh提出的Shapelet方法：考察序列中具有代表意義的子序列來作為Shapelet特徵而進行分類。Lin等人提出了基於字典的方法，將序列根據特定的字典轉化為詞序列，從而進行分類。Deng提出了基於區間的方法，從區間中提取波動的特徵。

除了上述方法外，聚合演算法（將多種不同演算法聚合在一起）的研究也有了長足的進步。最近提出的COTE演算法幾乎將上述所有不同分類演算法聚合在一起，得到了優異的分類效果。

這一類的方法都是一些通過某種度量關系來提取相關特徵的方法，如詞袋法，通過找到該時間序列中是否有符合已有詞袋中的特徵（序列的樣子），將一個序列用詞來表示，再對詞進行分類。而其他的基於特徵的方法都是利用了類似的方法，如提取統計量，基於規則等，再通過分類模型進行分類。

1、MLP、FCN、ResNet
MLP的輸入是一個向量（數組），通過全連接的形式對整體數組的每一個元素逐層賦予權重，並求得最後的分類，這種方法是一種比較粗暴的學習方法，直接學習所有元素直接的線性或非線性相關關系，但是並沒有去深度挖掘數組中更好的表現特徵，分類效果不佳。

FCN是將MLP中的全鏈接層用卷積層進行替代，Resnet也是，但是其中的卷積層都用一維卷積核進行了替代。

來自於Time Series Classifification from Scratch with Deep Neural Networks: A Strong Baseline.可以看到深度學習的方法效果基本上與傳統方法相接近，甚至有所超過，其中整體表現最好的是FCN。

LSTM_FCN的方法比較簡單，是將輸入分別輸入到兩個分支中，LSTM和FCN，並在最後將兩個輸出分支進行concat進行softmax獲得分類結果。在這篇論文中，作者說這種方法取得了比FCN更好的效果。
在其他的一些比賽方案中，也有resnet+LSTM+FC的組合形式，通過Resnet的一維卷積先提取相關特徵，然後通過LSTM學習一維特徵向量的相關關系，再進行分類，可能針對於不同的問題還是要試試才知道哪個的效果更加好。
BiGRU-CNN與以上方法相比實際上並沒有做什麼大的改進，就是將LSTM分支替換成雙向的GRU分支。

❷ 時間序列分析的具體演算法

用隨機過程理論和數理統計學方法，研究隨機數據序列所遵從的統計規律，以用於解決實際問題。由於在多數問題中，隨機數據是依時間先後排成序列的，故稱為時間序列。它包括一般統計分析（如自相關分析、譜分析等），統計模型的建立與推斷，以及關於隨機序列的最優預測、控制和濾波等內容。經典的統計分析都假定數據序列具有獨立性，而時間序列分析則著重研究數據序列的相互依賴關系。後者實際上是對離散指標的隨機過程的統計分析，所以又可看作是隨機過程統計的一個組成部分。例如,用x(t)表示某地區第t個月的降雨量，{x(t)，t=1，2，…}是一時間序列。對t=1，2，…，T，記錄到逐月的降雨量數據x(1)，x(2)，…，x(T)，稱為長度為T的樣本序列。依此即可使用時間序列分析方法，對未來各月的雨量x(T+l)(l=1,2,…)進行預報。時間序列分析在第二次世界大戰前就已應用於經濟預測。二次大戰中和戰後，在軍事科學、空間科學和工業自動化等部門的應用更加廣泛。
就數學方法而言，平穩隨機序列（見平穩過程）的統計分析，在理論上的發展比較成熟，從而構成時間序列分析的基礎。
頻域分析 一個時間序列可看成各種周期擾動的疊加，頻域分析就是確定各周期的振動能量的分配，這種分配稱為「譜」，或「功率譜」。因此頻域分析又稱譜分析。譜分析中的一個重要是統計量,稱為序列的周期圖。當序列含有確定性的周期分量時，通過I(ω)的極大值點尋找這些分量的周期，是譜分析的重要內容之一。在按月記錄的降雨量序列中，序列x(t)就可視為含有以12為周期的確定分量，所以序列x(t)可以表示為 ,它的周期圖I(ω)處有明顯的極大值。
當平穩序列的譜分布函數F（λ）具有譜密度ƒ(λ)（即功率譜）時，可用(2π)-1I(λ)去估計ƒ(λ)，它是ƒ(λ)的漸近無偏估計。如欲求ƒ(λ)的相合估計（見點估計），可用I(ω)的適當的平滑值去估計ƒ(λ),常用的方法為譜窗估計即取ƒ(λ)的估計弮(λ)為 ,式中wt(ω)稱為譜窗函數。譜窗估計是實際應用中的重要方法之一。譜分布F(λ)本身的一種相合估計可由I(ω)的積分直接獲得，即 。研究以上各種估計量的統計性質，改進估計方法，是譜分析的重要內容。時域分析 它的目的在於確定序列在不同時刻取值的相互依賴關系,或者說,確定序列的相關結構。這種結構是用序列的自相關函0,1,…)來描述的,為序列的自協方差函數值,m=Ex(t)是平穩序列的均值。常常採用下列諸式給出m，γ(k),ρ(k)的估計： ,通(k)了解序列的相關結構,稱為自相關分析。研究它們的強、弱相合性及其漸近分布等問題，是相關分析中的基本問題。模型分析 20世紀70年代以來，應用最廣泛的時間序列模型是平穩自回歸-滑動平均模型 (簡稱ARMA模型)。其形狀為： 式中ε(t)是均值為零、方差為σ2的獨立同分布的隨機序列;和σ2為模型的參數,它們滿足： 對一切|z|≤1的復數z成立。p和q是模型的階數，為非負整數。特別當q=0時，上述模型稱為自回歸模型；當p=0時, 稱為滑動平均模型。根據x(t)的樣本值估計這些參數和階數，就是對這種模型的統計分析的內容。對於滿足ARMA模型的平穩序列，其線性最優預測與控制等問題都有較簡捷的解決方法,尤其是自回歸模型,使用更為方便。G.U.尤爾在1925～1930年間就提出了平穩自回歸的概念。1943年,Η.Β.曼和Α.瓦爾德發表了關於這種模型的統計方法及其漸近性質的一些理論結果。一般ARMA模型的統計分析研究，則是20世紀60年代後才發展起來的。特別是關於p，q值的估計及其漸近理論，出現得更晚些。除ARMA模型之外,還有其他的模型分析的研究,其中以線性模型的研究較為成熟，而且都與ARMA模型分析有密切關系。回歸分析 如果時間序列x(t)可表示為確定性分量φ(t)與隨機性分量ω(t)之和，根據樣本值x(1)，x(2)，…,x(T)來估計φ(t)及分析ω(t)的統計規律，屬於時間序列分析中的回歸分析問題。它與經典回歸分析不同的地方是，ω(t)一般不是獨立同分布的，因而在此必須涉及較多的隨機過程知識。當φ(t)為有限個已知函數的未知線性組合時，即 ，式中ω(t)是均值為零的平穩序列,α1,α2,…,αs是未知參數,φ1(t),φ2(t),…,φs(t)是已知的函數,上式稱為線性回歸模型，它的統計分析已被研究得比較深入。前面敘述的降雨量一例，便可用此類模型描述。回歸分析的內容包括:當ω(t)的統計規律已知時，對參數α1,α2,…,αs進行估計,預測x(T+l)之值；當ω(t)的統計規律未知時，既要估計上述參數，又要對ω(t)進行統計分析，如譜分析、模型分析等。在這些內容中,一個重要的課題是:在相當廣泛的情況下，證明 α1,α2,…,αs的最小二乘估計，與其線性最小方差無偏估計一樣，具有相合性和漸近正態分布性質。最小二乘估計姙j(1≤j≤s)不涉及ω(t)的統計相關結構，是由數據x(1)，x(2)，…，x(T)直接算出，由此還可得(t)進行時間序列分析中的各種統計分析，以代替對ω(t)的分析。在理論上也已證明，在適當的條件下，這樣的替代具有滿意的漸近性質。由於ω(t)的真值不能直接量測，這些理論結果顯然有重要的實際意義。這方面的研究仍在不斷發展。
時間序列分析中的最優預測、控制與濾波等方面的內容見平穩過程條。近年來多維時間序列分析的研究有所進展，並應用到工業生產自動化及經濟分析中。此外非線性模型統計分析及非參數統計分析等方面也逐漸引起人們的注意。

❸ 時間序列分析——DTW演算法詳解

DTW（dynamic time warping）是時間序列分析中一個很早（1994年，論文的年紀比我都大）也很經典的演算法了。它其實借用的是經典演算法的「動態規劃」的思想。一般來說，時間序列數據如果要做分類，那麼大體可以將實驗步驟分為：數據預處理（去噪或數據增強），數據表徵，選取分類器（機器學習演算法還需要選取合適的距離計算方法）。雖然DTW演算法也給出了路徑，但我實在想不出如何利用path，因此我更傾向於將DTW演算法歸為距離計算方法。

第一部分Introction不再介紹。直接介紹第二部分：Dynamic Time Warping

作者首先提到，dtw演算法成功應用在了語音識別領域——研究者將現實中一個單詞的發音（其實就是一條時間序列）與模板庫中單詞的發音去一個個匹配。怎麼衡量匹配程度的大小呢？