時間序列的聚類
在機(jī)器學(xué)習(xí)領(lǐng)域，聚類問題一直是一個非常常見的問題。無論是在傳統(tǒng)的機(jī)器學(xué)習(xí)（Machine Learning）領(lǐng)域，還是自然語言處理（Natural Language Processing）領(lǐng)域，都可以用聚類算法做很多的事情。例如在數(shù)據(jù)分析領(lǐng)域，我們可以把某個物品用特征來描述出來，例如該房子的面積，價格，朝向等內(nèi)容，然后使用聚類算法來把相似的房子聚集到一起；在自然語言處理領(lǐng)域，通常都會尋找一些相似的新聞或者把相似的文本信息聚集到一起，在這種情況下，可以用 Word2Vec 把自然語言處理成向量特征，然后使用 KMeans 等機(jī)器學(xué)習(xí)算法來作聚類。除此之外，另外一種做法是使用 Jaccard 相似度來計算兩個文本內(nèi)容之間的相似性，然后使用層次聚類（Hierarchical Clustering）的方法來作聚類。
本文將會從常見的聚類算法出發(fā)，然后介紹時間序列聚類的常見算法。
機(jī)器學(xué)習(xí)的聚類算法
KMeans — 基于距離的機(jī)器學(xué)習(xí)聚類算法
KMeans 算法的目的是把歐氏空間?
?中的?
?個節(jié)點，基于它們之間的距離公式，把它們劃分成?
?個類別，其中類別?
?的個數(shù)是需要在執(zhí)行算法之前人為設(shè)定的。
從數(shù)學(xué)語言上來說，假設(shè)已知的歐式空間點集為?
?，事先設(shè)定的類別個數(shù)是?
?，當(dāng)然?
?是必須要滿足的，因為類別的數(shù)目不能夠多于點集的元素個數(shù)。算法的目標(biāo)是尋找到合適的集合?
?使得?
?達(dá)到最小，其中?
?表示集合?
中的所有點的均值。
上面的?
?表示歐式空間的歐幾里得距離，在這種情況下，除了使用?
?范數(shù)之外，還可以使用?
?范數(shù)和其余的?
?范數(shù)。只要該范數(shù)滿足距離的三個性質(zhì)即可，也就是非負(fù)數(shù)，對稱，三角不等式。
層次聚類 — 基于相似性的機(jī)器學(xué)習(xí)聚類算法
層次聚類通常來說有兩種方法，一種是凝聚，另外一種是分裂。
所謂凝聚，其大體思想就是在一開始的時候，把點集集合中的每個元素都當(dāng)做一類，然后計算每兩個類之前的相似度，也就是元素與元素之間的距離；然后計算集合與集合之前的距離，把相似的集合放在一起，不相似的集合就不需要合并；不停地重復(fù)以上操作，直到達(dá)到某個限制條件或者不能夠繼續(xù)合并集合為止。
所謂分裂，正好與聚合方法相反。其大體思想就是在剛開始的時候把所有元素都放在一類里面，然后計算兩個元素之間的相似性，把不相似元素或者集合進(jìn)行劃分，直到達(dá)到某個限制條件或者不能夠繼續(xù)分裂集合為止。
在層次聚類里面，相似度的計算函數(shù)就是關(guān)鍵所在。在這種情況下，可以設(shè)置兩個元素之間的距離公式，例如歐氏空間中兩個點的歐式距離。在這種情況下，距離越小表示兩者之間越相似，距離越大則表示兩者之間越不相似。除此之外，還可以設(shè)置兩個元素之間的相似度。例如兩個集合中的公共元素的個數(shù)就可以作為這兩個集合之間的相似性。在文本里面，通常可以計算句子和句子的相似度，簡單來看就是計算兩個句子之間的公共詞語的個數(shù)。
時間序列的聚類算法
通過以上的描述，如果要做時間序列的聚類，通常來說也有多種方法來做，可以使用基于距離的聚類算法 KMeans，也可以使用基于相似度計算的層次聚類算法。
時間序列的特征提取
之前寫過很多時間序列特征提取的方法，無論是常見的時間序列特征，例如最大值，最小值，均值，中位數(shù)，方差，值域等內(nèi)容之外。還可以計算時間序列的熵以及分桶的情況，其分桶的熵指的是把時間序列的值域進(jìn)行切分，就像 Lebesgue 積分一樣，查看落入那些等分桶的時間序列的概率分布情況，就可以進(jìn)行時間序列的分類。除了 Binned Entropy 之外，還有 Sample Entropy 等各種各樣的特征。除了時域特征之外，也可以對時間序列的頻域做特征，例如小波分析，傅里葉分析等等。因此，在這種情況下，其實只要做好了時間序列的特征，使用 KMeans 算法就可以得到時間序列的聚類效果，也就是把相似的曲線放在一起。參考文章：時間序列的表示與信息提取。
在提取時間序列的特征之前，通常可以對時間序列進(jìn)行基線的提取，把時間序列分成基線和誤差項。而基線提取的最簡單方法就是進(jìn)行移動平均算法的擬合過程，在這種情況下，可以把原始的時間序列?
?分成兩個部分?
?和?
?。i.e.?
?。有的時候，提取完時間序列的基線之后，其實對時間序列的基線做特征，有的時候分類效果會優(yōu)于對原始的時間序列做特征。參考文章：兩篇關(guān)于時間序列的論文。
時間序列的相似度計算
如果要計算時間序列的相似度，通常來說除了歐幾里得距離等?
?距離之外，還可以使用 DTW 等方法。在這種情況下，DTW 是基于動態(tài)規(guī)劃算法來做的，基本想法是根據(jù)動態(tài)規(guī)劃原理，來進(jìn)行時間序列的“扭曲”，從而把時間序列進(jìn)行必要的錯位，計算出最合適的距離。一個簡單的例子就是把?
?和?
?進(jìn)行必要的橫坐標(biāo)平移，計算出兩條時間序列的最合適距離。但是，從 DTW 的算法描述來看，它的算法復(fù)雜度是相對高的，是?
?量級的，其中?
表示時間序列的長度。參考文章：時間序列的搜索。
如果不考慮時間序列的“扭曲”的話，也可以直接使用歐氏距離，無論是?
?還是?
?都有它的用武之地。除了距離公式之外，也可以考慮兩條時間序列之間的 Pearson 系數(shù)，如果兩條時間序列相似的話，那么它們之間的 Pearson 系數(shù)接近于 1；如果它們之間是負(fù)相關(guān)的，那么它們之間的 Pearson 系數(shù)接近于 -1；如果它們之間沒有相關(guān)性，Pearson 系數(shù)接近于0。除了 Pearson 系數(shù)之外，也可以考慮它們之間的線性相關(guān)性，畢竟線性相關(guān)性與 Pearson 系數(shù)是等價的。參考文章：時間序列的相似性。
除此之外，我們也可以用 Auto Encoder 等自編碼器技術(shù)對時間序列進(jìn)行特征的編碼，也就是說該自編碼器的輸入層和輸出層是恒等的，中間層的神經(jīng)元個數(shù)少于輸入層和輸出層。在這種情況下，是可以做到對時間序列進(jìn)行特征的壓縮和構(gòu)造的。除了 Auto Encoder 等無監(jiān)督方法之外，如果使用其他有監(jiān)督的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的話，例如前饋神經(jīng)網(wǎng)絡(luò)，循環(huán)神經(jīng)網(wǎng)絡(luò)，卷積神經(jīng)網(wǎng)絡(luò)等網(wǎng)絡(luò)結(jié)構(gòu)，可以把歸一化之后的時間序列當(dāng)做輸入層，輸出層就是時間序列的各種標(biāo)簽，無論是該時間序列的形狀種類還是時間序列的異常/正常標(biāo)簽。當(dāng)該神經(jīng)網(wǎng)絡(luò)訓(xùn)練好了之后，中間層的輸出都可以作為 Time Series To Vector 的一種模式。i.e. 也就是把時間序列壓縮成一個更短一點的向量，然后基于 COSINE 相似度等方法來計算原始時間序列的相似度。參考文章：基于自編碼器的時間序列異常檢測算法，基于前饋神經(jīng)網(wǎng)絡(luò)的時間序列異常檢測算法。
總結(jié)
如果想對時間序列進(jìn)行聚類，其方法是非常多的。無論是時間序列的特征構(gòu)造，還是時間序列的相似度方法，都是需要基于一些人工經(jīng)驗來做的。如果使用深度學(xué)習(xí)的方法的話，要么就提供大量的標(biāo)簽數(shù)據(jù)；要么就只能夠使用一些無監(jiān)督的編碼器的方法了。本文目前初步介紹了一些時間序列的聚類算法，后續(xù)將會基于筆者的學(xué)習(xí)情況來做進(jìn)一步的撰寫工作。
參考文獻(xiàn)
聚類分析：https://en.wikipedia.org/wiki/Cluster_analysis
Dynamic Time Warping：https://en.wikipedia.org/wiki/Dynamic_time_warping
Pearson Coefficient：https://en.wikipedia.org/wiki/Pearson_correlation_coefficient
Auto Encoder：https://en.wikipedia.org/wiki/Autoencoder
Word2Vec：https://en.wikipedia.org/wiki/Word2vec，https://samyzaf.com/ML/nlp/nlp.html
發(fā)布于 2019-01-28
來源：https://zhuanlan.zhihu.com/p/55903495?utm_source=wechat_session&utm_medium=social&utm_oi=55913616506880
