時間序列演算法分類

A. 時間序列分析方法

時間序列是指一組在連續時間上測得的數據，其在數學上的定義是一組向量x(t), t=0,1,2,3,...，其中t表示數據所在的時間點，x(t)是一組按時間順序（測得）排列的隨機變數。包含單個變數的時間序列稱為單變數時間序列，而包含多個變數的時間序列則稱為多變數。

時間序列在很多方面多有涉及到，如天氣預報，每天每個小時的氣溫，股票走勢等等，在商業方面有諸多應用，如：

下面我們將通過一個航班數據來說明如何使用已有的工具來進行時間序列數據預測。常用來處理時間序列的包有三個：

對於基於AR、MA的方法一般需要數據預處理，因此本文分為三部分：

通過簡單的初步處理以及可視化可以幫助我們有效快速的了解數據的分布（以及時間序列的趨勢）。

觀察數據的頻率直方圖以及密度分布圖以洞察數據結構，從下圖可以看出：

使用 statsmodels 對該時間序列進行分解，以了解該時間序列數據的各個部分，每個部分都代表著一種模式類別。借用 statsmodels 序列分解我們可以看到數據的主要趨勢成分、季節成分和殘差成分，這與我們上面的推測相符合。

如果一個時間序列的均值和方差隨著時間變化保持穩定，則可以說這個時間序列是穩定的。

大多數時間序列模型都是在平穩序列的前提下進行建模的。造成這種情況的主要原因是序列可以有許多種（復雜的）非平穩的方式，而平穩性只有一種，更加的易於分析，易於建模。

在直覺上，如果一段時間序列在某一段時間序列內具有特定的行為，那麼將來很可能具有相同的行為。譬如已連續觀察一個星期都是六點出太陽，那麼可以推測明天也是六點出太陽，誤差非常小。

而且，與非平穩序列相比，平穩序列相關的理論更加成熟且易於實現。

一般可以通過以下幾種方式來檢驗序列的平穩性：

如果時間序列是平穩性的，那麼在ACF/PACF中觀測點數據與之前數據點的相關性會急劇下降。

下圖中的圓錐形陰影是置信區間，區間外的數據點說明其與觀測數據本身具有強烈的相關性，這種相關性並非來自於統計波動。

PACF在計算X(t)和X(t-h)的相關性的時候，挖空在（t-h，t）上所有數據點對X(t)的影響，反應的是X(t)和X(t-h)之間真實的相關性（直接相關性）。

從下圖可以看出，數據點的相關性並沒有急劇下降，因此該序列是非平穩的。

如果序列是平穩的，那麼其滑動均值/方差會隨著時間的變化保持穩定。

但是從下圖我們可以看到，隨著時間的推移，均值呈現明顯的上升趨勢，而方差也呈現出波動式上升的趨勢，因此該序列是非平穩的。

一般來講p值小於0.05我們便認為其是顯著性的，可以拒絕零假設。但是這里的p值為0.99明顯是非顯著性的，因此接受零假設，該序列是非平穩的。

從上面的平穩性檢驗我們可以知道該時間序列為非平穩序列。此外，通過上面1.3部分的序列分解我們也可以看到，該序列可分解為3部分：

我們可以使用數據轉換來對那些較大的數據施加更大的懲罰，如取對數、開平方根、立方根、差分等，以達到序列平穩的目的。

滑動平均後數據失去了其原來的特點（波動式上升），這樣損失的信息過多，肯定是無法作為後續模型的輸入的。

差分是常用的將非平穩序列轉換平穩序列的方法。ARIMA中的 'I' 便是指的差分，因此ARIMA是可以對非平穩序列進行處理的，其相當於先將非平穩序列通過差分轉換為平穩序列再來使用ARMA進行建模。

一般差分是用某時刻數值減去上一時刻數值來得到新序列。但這里有一點區別，我們是使用當前時刻數值來減去其對應時刻的滑動均值。

我們來看看剛剛差分的結果怎麼樣。

讓我們稍微總結下我們剛剛的步驟：

通過上面的3步我們成功的將一個非平穩序列轉換成了一個平穩序列。上面使用的是最簡單的滑動均值，下面我們試試指數滑動平均怎麼樣。

上面是最常用的指數滑動平均的定義，但是pandas實現的指數滑動平均好像與這個有一點區別，詳細區別還得去查pandas文檔。

指數滑動均值的效果看起來也很差。我們使用差分+指數滑動平均再來試試吧。

在上面我們通過 取log+(指數)滑動平均+差分 已經成功將非平穩序列轉換為了平穩序列。

下面我們看看，轉換後的平穩序列的各個成分是什麼樣的。不過這里我們使用的是最簡單的差分，當前時刻的值等於原始序列當前時刻的值減去原始序列中上一時刻的值，即： x'(t) = x(t) - x(t-1)。

看起來挺不錯，是個平穩序列的樣子。不過，還是檢驗一下吧。

可以看到，趨勢(Trend)部分已基本被去除，但是季節性(seasonal)部分還是很明顯，而ARIMA是無法對含有seasonal的序列進行建模分析的。

在一開始我們提到了3個包均可以對時間序列進行建模。

為了簡便，這里 pmdarima 和 statsmodels.tsa 直接使用最好的建模方法即SARIMA，該方法在ARIMA的基礎上添加了額外功能，可以擬合seasonal部分以及額外添加的數據。

在使用ARIMA（Autoregressive Integrated Moving Average）模型前，我們先簡單了解下這個模型。這個模型其實可以包括三部分，分別對應著三個參數（p, d, q）：

因此ARIMA模型就是將AR和MA模型結合起來然後加上差分，克服了不能處理非平穩序列的問題。但是，需要注意的是，其仍然無法對seasonal進行擬合。

下面開始使用ARIMA來擬合數據。

（1） 先分訓練集和驗證集。需要注意的是這里使用的原始數據來進行建模而非轉換後的數據。

（2）ARIMA一階差分建模並預測

（3）對差分結果進行還原

先手動選擇幾組參數，然後參數搜索找到最佳值。需要注意的是，為了避免過擬合，這里的階數一般不太建議取太大。

可視化看看結果怎麼樣吧。

（6）最後，我們還能對擬合好的模型進行診斷看看結果怎麼樣。

我們主要關心的是確保模型的殘差（resial）部分互不相關，並且呈零均值正態分布。若季節性ARIMA（SARIMA）不滿足這些屬性，則表明它可以進一步改善。模型診斷根據下面的幾個方面來判斷殘差是否符合正態分布：

同樣的，為了方便，我們這里使用 pmdarima 中一個可以自動搜索最佳參數的方法 auto_arima 來進行建模。

一般來說，在實際生活和生產環節中，除了季節項，趨勢項，剩餘項之外，通常還有節假日的效應。所以，在prophet演算法裡面，作者同時考慮了以上四項，即：

上式中，

更多詳細Prophet演算法內容可以參考 Facebook 時間序列預測演算法 Prophet 的研究 。

Prophet演算法就是通過擬合這幾項，然後把它們累加起來得到時間序列的預測值。

Prophet提供了直觀且易於調整的參數：

Prophet對輸入數據有要求：

關於 Prophet 的使用例子可以參考 Prophet example notebooks

下面使用 Prophet 來進行處理數據。

參考：
Facebook 時間序列預測演算法 Prophet 的研究
Prophet example notebooks
auto_arima documentation for selecting best model
數據分析技術：時間序列分析的AR/MA/ARMA/ARIMA模型體系
https://github.com/advaitsave/Introction-to-Time-Series-forecasting-Python
時間序列分析
My First Time Series Comp (Added Prophet)
Prophet官方文檔： https://facebookincubator.github.io

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

用隨機過程理論和數理統計學方法，研究隨機數據序列所遵從的統計規律，以用於解決實際問題。由於在多數問題中，隨機數據是依時間先後排成序列的，故稱為時間序列。它包括一般統計分析（如自相關分析、譜分析等），統計模型的建立與推斷，以及關於隨機序列的最優預測、控制和濾波等內容。經典的統計分析都假定數據序列具有獨立性，而時間序列分析則著重研究數據序列的相互依賴關系。後者實際上是對離散指標的隨機過程的統計分析，所以又可看作是隨機過程統計的一個組成部分。例如,用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)的真值不能直接量測，這些理論結果顯然有重要的實際意義。這方面的研究仍在不斷發展。
時間序列分析中的最優預測、控制與濾波等方面的內容見平穩過程條。近年來多維時間序列分析的研究有所進展，並應用到工業生產自動化及經濟分析中。此外非線性模型統計分析及非參數統計分析等方面也逐漸引起人們的注意。

C. 時間序列分類演算法

歐式距離不能很好地針對時間序列的波動模式進行分類，研發更適合時間序列分類的距離度量就成為關鍵，這其中最經典的時間序列距離度量就是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分支。