時間序列的聚類

在機器學習領域，聚類問題一直是一個非常常見的問題。無論是在傳統的機器學習（Machine Learning）領域，還是自然語言處理（Natural Language Processing）領域，都可以用聚類演算法做很多的事情。例如在數據分析領域，我們可以把某個物品用特徵來描述出來，例如該房子的面積，價格，朝向等內容，然後使用聚類演算法來把相似的房子聚集到一起；在自然語言處理領域，通常都會尋找一些相似的新聞或者把相似的文本信息聚集到一起，在這種情況下，可以用 Word2Vec 把自然語言處理成向量特徵，然後使用 KMeans 等機器學習演算法來作聚類。除此之外，另外一種做法是使用 Jaccard 相似度來計算兩個文本內容之間的相似性，然後使用層次聚類（Hierarchical Clustering）的方法來作聚類。

本文將會從常見的聚類演算法出發，然後介紹時間序列聚類的常見演算法。

機器學習的聚類演算法

KMeans — 基於距離的機器學習聚類演算法

KMeans 演算法的目的是把歐氏空間 mathbb{R}^{m} 中的 n 個節點，基於它們之間的距離公式，把它們劃分成 K 個類別，其中類別 K 的個數是需要在執行演算法之前人為設定的。

從數學語言上來說，假設已知的歐式空間點集為 {x_{1},cdots,x_{n}} ，事先設定的類別個數是 K ，當然 Kleq n 是必須要滿足的，因為類別的數目不能夠多於點集的元素個數。演算法的目標是尋找到合適的集合 {S_{i}}_{1leq ileq K} 使得 argmin_{S_{i}}sum_{xin S_{i}}||x-mu_{i}||^{2} 達到最小，其中 mu_{i} 表示集合 S_{i} 中的所有點的均值。

上面的 ||cdot|| 表示歐式空間的歐幾裏得距離，在這種情況下，除了使用 L^{2} 範數之外，還可以使用 L^{1} 範數和其餘的 L^{p},pgeq 1 範數。只要該範數滿足距離的三個性質即可，也就是非負數，對稱，三角不等式。

層次聚類 — 基於相似性的機器學習聚類演算法

層次聚類通常來說有兩種方法，一種是凝聚，另外一種是分裂。

所謂凝聚，其大體思想就是在一開始的時候，把點集集合中的每個元素都當做一類，然後計算每兩個類之前的相似度，也就是元素與元素之間的距離；然後計算集合與集合之前的距離，把相似的集合放在一起，不相似的集合就不需要合併；不停地重複以上操作，直到達到某個限制條件或者不能夠繼續合併集合為止。

所謂分裂，正好與聚合方法相反。其大體思想就是在剛開始的時候把所有元素都放在一類裡面，然後計算兩個元素之間的相似性，把不相似元素或者集合進行劃分，直到達到某個限制條件或者不能夠繼續分裂集合為止。

在層次聚類裡面，相似度的計算函數就是關鍵所在。在這種情況下，可以設置兩個元素之間的距離公式，例如歐氏空間中兩個點的歐式距離。在這種情況下，距離越小表示兩者之間越相似，距離越大則表示兩者之間越不相似。除此之外，還可以設置兩個元素之間的相似度。例如兩個集合中的公共元素的個數就可以作為這兩個集合之間的相似性。在文本裡面，通常可以計算句子和句子的相似度，簡單來看就是計算兩個句子之間的公共詞語的個數。

時間序列的聚類演算法

通過以上的描述，如果要做時間序列的聚類，通常來說也有多種方法來做，可以使用基於距離的聚類演算法 KMeans，也可以使用基於相似度計算的層次聚類演算法。

時間序列的特徵提取

之前寫過很多時間序列特徵提取的方法，無論是常見的時間序列特徵，例如最大值，最小值，均值，中位數，方差，值域等內容之外。還可以計算時間序列的熵以及分桶的情況，其分桶的熵指的是把時間序列的值域進行切分，就像 Lebesgue 積分一樣，查看落入那些等分桶的時間序列的概率分佈情況，就可以進行時間序列的分類。除了 Binned Entropy 之外，還有 Sample Entropy 等各種各樣的特徵。除了時域特徵之外，也可以對時間序列的頻域做特徵，例如小波分析，傅裏葉分析等等。因此，在這種情況下，其實只要做好了時間序列的特徵，使用 KMeans 演算法就可以得到時間序列的聚類效果，也就是把相似的曲線放在一起。參考文章：時間序列的表示與信息提取。

在提取時間序列的特徵之前，通常可以對時間序列進行基線的提取，把時間序列分成基線和誤差項。而基線提取的最簡單方法就是進行移動平均演算法的擬合過程，在這種情況下，可以把原始的時間序列 {x_{1},cdots,x_{n}} 分成兩個部分 {baseline_{1},cdots,baseline_{n}} 和 {residual_{1},cdots,residual_{n}} 。i.e. x_{i} = baseline_{i} + residual_{i} 。有的時候，提取完時間序列的基線之後，其實對時間序列的基線做特徵，有的時候分類效果會優於對原始的時間序列做特徵。參考文章：兩篇關於時間序列的論文。

時間序列的相似度計算

如果要計算時間序列的相似度，通常來說除了歐幾裏得距離等 L^{p} 距離之外，還可以使用 DTW 等方法。在這種情況下，DTW 是基於動態規劃演算法來做的，基本想法是根據動態規劃原理，來進行時間序列的「扭曲」，從而把時間序列進行必要的錯位，計算出最合適的距離。一個簡單的例子就是把 y=sin(x) 和 y=cos(x) 進行必要的橫坐標平移，計算出兩條時間序列的最合適距離。但是，從 DTW 的演算法描述來看，它的演算法複雜度是相對高的，是 O(n^{2}) 量級的，其中 n 表示時間序列的長度。參考文章：時間序列的搜索。

如果不考慮時間序列的「扭曲」的話，也可以直接使用歐氏距離，無論是 L^{1}, L^{2} 還是 L^{p} 都有它的用武之地。除了距離公式之外，也可以考慮兩條時間序列之間的 Pearson 係數，如果兩條時間序列相似的話，那麼它們之間的 Pearson 係數接近於 1；如果它們之間是負相關的，那麼它們之間的 Pearson 係數接近於 -1；如果它們之間沒有相關性，Pearson 係數接近於0。除了 Pearson 係數之外，也可以考慮它們之間的線性相關性，畢竟線性相關性與 Pearson 係數是等價的。參考文章：時間序列的相似性。

除此之外，我們也可以用 Auto Encoder 等自編碼器技術對時間序列進行特徵的編碼，也就是說該自編碼器的輸入層和輸出層是恆等的，中間層的神經元個數少於輸入層和輸出層。在這種情況下，是可以做到對時間序列進行特徵的壓縮和構造的。除了 Auto Encoder 等無監督方法之外，如果使用其他有監督的神經網路結構的話，例如前饋神經網路，循環神經網路，卷積神經網路等網路結構，可以把歸一化之後的時間序列當做輸入層，輸出層就是時間序列的各種標籤，無論是該時間序列的形狀種類還是時間序列的異常/正常標籤。當該神經網路訓練好了之後，中間層的輸出都可以作為 Time Series To Vector 的一種模式。i.e. 也就是把時間序列壓縮成一個更短一點的向量，然後基於 COSINE 相似度等方法來計算原始時間序列的相似度。參考文章：基於自編碼器的時間序列異常檢測演算法，基於前饋神經網路的時間序列異常檢測演算法。

總結

如果想對時間序列進行聚類，其方法是非常多的。無論是時間序列的特徵構造，還是時間序列的相似度方法，都是需要基於一些人工經驗來做的。如果使用深度學習的方法的話，要麼就提供大量的標籤數據；要麼就只能夠使用一些無監督的編碼器的方法了。本文目前初步介紹了一些時間序列的聚類演算法，後續將會基於筆者的學習情況來做進一步的撰寫工作。

參考文獻

  1. 聚類分析：en.wikipedia.org/wiki/C
  2. Dynamic Time Warping：en.wikipedia.org/wiki/D
  3. Pearson Coefficient：en.wikipedia.org/wiki/P
  4. Auto Encoder：en.wikipedia.org/wiki/A
  5. Word2Vec：en.wikipedia.org/wiki/W，samyzaf.com/ML/nlp/nlp.

推薦閱讀：

相關文章