時間序列數據的聚類有什麼好方法？

01-03

如題，時間序列尤其自然的特點，最主要的就是特點就是隨著時間單向前進且每一個時間點有且只可能有一個樣本值。此外時間序列還有自相關(每個樣本點之間不服從獨立同分布)，非線性，滯後等等特點。
如下圖:

下面這條時間序列是上面這條的平移。
肉眼看，這兩條時間序列長得還是"很像的"，但如果用歐氏距離或者相關性這類的"相似性"度量，必然得出二者不相似的結論。
把時間序列平移是個辦法，但這裡其實是蘊含了一個「一條是另一條的滯後」的假設，可能會引入新的Bias(偏差)和"為了顯著而顯著的"的愚蠢做法，用起來也不太理想。
請各路高手集思廣益，給點意見。

對時間序列聚類而言（甚至對任何類型的數據聚類問題來說），聚類演算法本身再怎麼花哨也都不是關鍵。關鍵還在於如何定義相似度（similarity/dissimilarity），以及如何做好數據簡化（data reduction）。大致來說，人們常常把時間序列聚類分成三類：依時間點聚類（時間上的相似度），依形狀聚類（空間上的相似度），還有依變化聚類（數據生成過程的相似度）。

那麼在相似度方面，時間上的相似度就可以用最常見的歐氏距離；空間上的相似度就可以用DTW；數據生成過程的相似度就可以是基於概率的距離了，比如常見的有GMM，以及ARMA的mixture。

數據簡化方面，PAA是個常用於時間序列的數據變換，因為它在保證時間序列的形態的同時儘可能地保證了計算效率。實際應用的時候我們通常會想個辦法自動算出PAA要分割的片段的個數，不然每次拍腦袋定個數也是一件非常折磨人的事情。這裡可以借用Nyquist rate/frequency的概念，也就是頻率不高於B赫茲的時間序列能夠以2*B的抽樣比例保留完整信息。雖然嚴格來講時間序列算不上是頻率有界信號，但因為時間序列數據的高頻部分通常對應的是雜訊，所以我們也可以把時間序列近似地看作是頻率有界信號。這樣的話，通過計算頻率上界來得到PAA的片段的個數，這裡會用到快速傅里葉變換的逆運算，具體不在這裡展開了。為了提高體量很大的時間序列的存儲和查詢效率，在PAA的基礎上有時候還會用到indexing，其中iSAX算是比較著名的方法。它把實數值轉換為離散的符號，但iSAX是個有損壓縮，要是真的最後聚類聚出了偏差，它是要負責任的。

還有一些看起來細枝末節但實際操作的時候極為重要的東西，就是如何優化assignment這一步驟。Assignment就是要迭代每一對標記好的點和未標記的點的距離，像k-means，DBSCAN等等演算法都會涉及這樣的步驟。這樣的運算代價是很大的，可以達到O(n^3)。要解決這個問題，可以找出一個能剔除不必要的pairs的pruning演算法，比如給每個標記好的點預設一個「有效半徑」，如果一個未標記的點A和一個標記好的點B的距離超過了這個有效半徑，那麼在這個有效半徑里的其它標記好的點都不必與這個未標記的點A有什麼聯繫了。給這個演算法加速還可以用locality-sensitive hashing等等方法。

聚類方法仍然是那些聚類方法，只是如何更好得對兩個序列進行相似度度量，可以把序列看做高維向量，但是兩個時間序列可能長度不一樣，發生了位移等等，因此普通的距離計算方法或者相似度計算方法不能夠適應了，因此需要改進，比如DTW，還有一些其他的，忘記了。。。

你需要先理解你所用的time series的特性，不同的time series的生成機制不一樣, 因此對ECG和Forex聚類用的就不是同一種方法。在理解的基礎上你提取features然後再進行聚類, 比如，你可以先用Independent Component Analysis提取features然後用K-means Clustering進行聚類, 或者, 你也可以對time series進行某種編碼, 比如用SAX(Symbolic Aggregate Approximation), 然後再聚類。

不過，個人感覺Time Series Clustering是個大坑。

有些文章可作參考:

Time-series clustering

http://www.cs.ucr.edu/~eamonn/meaningless.pdf

Clustering of time series data

http://robjhyndman.com/papers/wang.pdf

http://www.cs.columbia.edu/~gravano/Papers/2015/sigmod2015.pdf

之前做過一個類似的分析，我還留了一個效果圖

時間序列聚類，可以先設定序列樣本之間的距離度量方式，然後通過基於樣本距離的聚類方法進行聚類。

跟大家講的差不多，這裡最關鍵的還是根據具體的業務需求，設計好不同序列樣本之間的距離計算方法。可能會考慮形狀相似（DTW效果不錯），發生的時間相近，持續的時間相似，信號的頻域相似（看頻譜），序列互相的影響（比如同時發生同樣的變化），演算法的性能等等方面。

至於設計好距離之後用什麼聚類演算法，都差不多，dbscan，或者層次聚類，affinity propagation都可以。

對於時間序列的距離measurement, DTW(Dynamic Time Warping) 是最常用的方法，優點是能夠很好的捕捉形狀，尤其是當你做過normalization之後。在時間序列的分類classification 上，1NN-DTW是效果非常好的。但缺點就是DTW的計算很慢，因為用了動態規劃。對於很長的時間序列，PAA和SAX能更好的捕捉形狀，並且速度不慢。UCR在時間序列上的研究一直是很好的，SAX的作者Keogh就是UCR的教授，他的組也對DTW做過很多研究，多數論文的數據也來自他們的archive, 感興趣的話可以去他的主頁探索一下http://www.cs.ucr.edu/~eamonn/

實際工作中遇到過類似的問題，當時看過的文章是這樣解決的：

1. 採用多時間序列做比對的方法，對各個時間序列做些許平移，找到最合適的「時間起點」，在這個「時間起點」下，所有時間序列之間不存在「延時」現象；

2. 對於不存在「延時」的時間序列，相關係數（pearson或者spearman）是一種比較好的度量，基於此度量做K-means或各種聚類方法，會有比較好的結果。

該方法適用於各條時間序列「延時」程度差異不太大且每條序列都具有一定時長的情況。第一步的計算時間較長，對於大量序列的情況需要用近似演算法求解。

我做過的：

1，FFT快速傅立葉變換，識別音樂和聲。

2，二次指數平滑預測，發現訂單量異常波動。

不知道你要問的聚類，到底是什麼需求？

應該是先需求，再找方法吧。

好比先有釘子，再找鎚子。

這也符合我呼「先問是不是，再問其他」的一貫作風。

如果識別波動外形相似，建議用FFT轉換成頻率域，再做聚類或者什麼的。

波動外形相似，那就是採樣範圍的頻率和強度的相似，如果上下平移，

無外乎就是強度平移，而頻率、初相位幾乎相同。

也是提特徵的做法，主要是DTW太慢了....Similarity Preserving Representation Learning for ...