多變量時間序列聚類綜述

楊秋穎，翁小清

(河北經(jīng)貿(mào)大學 信息技術(shù)學院，河北 石家莊 050061)

0 引 言

MTS在心理學、經(jīng)濟學、商業(yè)、金融等社會人文科學以及工程、質(zhì)量控制、監(jiān)測和安全等領(lǐng)域是一種非常普遍的數(shù)據(jù)類型。MTS的主要特征為：第一，MTS含有時間和變量兩個維度，且屬性變量間可能存在相關(guān)和冗余[1]；第二，不同的MTS樣本的長度或取樣頻率可能不一定相同[2]。MTS的高維性和高冗余性使得傳統(tǒng)的聚類方法有時無法直接用于此類數(shù)據(jù)類型。

聚類是一個把數(shù)據(jù)對象劃分成子集的過程，每一個子集是一個簇，使得簇中對象彼此相似，但與其他簇中的對象不相似[3]。MTS聚類面臨以下兩個挑戰(zhàn)[4]：

(1)高維度。MTS在時間維度的基礎(chǔ)上增加了變量維度，使得特征的數(shù)量越來越高，確定對MTS聚類有重大貢獻的顯著特征，以及減少表現(xiàn)為虛假特征的滋擾的影響是MTS聚類的一項重大挑戰(zhàn)。

(2)隱含特征。MTS可能存在一些隱藏的特征，這些特征可能不明顯，因此在直接的數(shù)據(jù)分析中被忽略。這些隱含特征是給定數(shù)據(jù)集中的外生因素或內(nèi)生因素。傳統(tǒng)的機器學習技術(shù)在捕捉這些存在但隱藏的特征方面效果較差。因此，在為集群解決方案建模時，需要更先進和嚴格的方法來考慮這些可能的特性。

本文從基于實例、基于特征和基于模型的角度，對近年來MTS聚類方法的研究進行歸類，并簡要介紹其在實際中的應(yīng)用。

1 基于實例的方法(Instance-based)

基于實例的時間序列聚類是指，對未經(jīng)過任何處理的時間序列直接應(yīng)用聚類算法實現(xiàn)聚類[5]。大多是把對傳統(tǒng)數(shù)據(jù)的聚類算法應(yīng)用到了時間序列數(shù)據(jù)上。

Spiegel等[6]提出了一種基于SVD的自底向上算法來識別內(nèi)部均勻的時間序列段。為了識別重復(fù)模式，將獲得的時間序列子段采用層次聚類方法進行分組，提出的自底向上分割算法在自動確定模型秩和合并閾值等特征上擴展了傳感器融合算法。評估表明，所提出的自下而上(BU)方法優(yōu)于直接的臨界點(CP)分割。Spiegel等[7-8]提出了一種基于遞歸圖的距離(RecuRRence plot-based，RRR)，該距離可以度量兩個多變量時間序列之間的相似性，與使用DTW進行聚類識別出的原型序列相比，能夠覆蓋更多的重復(fù)出現(xiàn)的模式。

Li[9]使用DTW構(gòu)建多元時間序列數(shù)據(jù)相似性矩陣和分量屬性序列相似性矩陣，利用近鄰傳播(Affinity Propagation, AP)聚類算法對這些相似性矩陣進行聚類分析進而獲得各種維度視角下的多元時間序列數(shù)據(jù)關(guān)系矩陣，使用Cosim函數(shù)對合并的關(guān)系矩陣進行相似性度量獲得一個相似性矩陣，再次使用PA算法對相似性矩陣進行聚類分析，獲得最終的數(shù)據(jù)類標簽。數(shù)值實驗結(jié)果表明,與傳統(tǒng)聚類方法相比,所提出方法不僅能夠有效地反映總體數(shù)據(jù)特征之間的關(guān)系,而且通過重要分量屬性序列之間的關(guān)聯(lián)關(guān)系分析能夠提高原始時間序列數(shù)據(jù)的聚類效果。但該方法使用了多次AP聚類過程,其時間性能取決于AP聚類的收斂性,通常需要較高的計算時間代價。Attila等[10]以實際應(yīng)用背景為基礎(chǔ)，引入一種新的交叉相關(guān)(Cross-correlation)的相似性度量方法和基于圖的聚類技術(shù)。首先定義兩個樣本間的相似性以及屬性間的相似性，在樣本間相似性的基礎(chǔ)上，提出基于圖的聚類方法和降維方法，實驗表明該方法在噪聲容忍中表現(xiàn)更好。Li[11]受傳統(tǒng)K-means算法的啟發(fā)，在聚類中心的選取上使用CPCA代替?zhèn)鹘y(tǒng)的均值法，在距離度量上使用數(shù)據(jù)在子空間上的重構(gòu)誤差代替歐氏距離，在擁有K-means算法的線性時間復(fù)雜度的基礎(chǔ)上，考慮了原始數(shù)據(jù)值的分布以及變量間關(guān)系。

Singhal等[12-13]將主成分分析中的主成分空間間的角度度量、數(shù)據(jù)集間的馬氏距離，以及數(shù)據(jù)中的附加特性的歐式距離進行加權(quán)平均組合，作為傳統(tǒng)K-means算法中的距離度量，提出一種新的多變量時間序列數(shù)據(jù)聚類方法。此外考慮K-means算法中聚類個數(shù)K是個超參數(shù)，提出一種新的確定最佳簇數(shù)的方法。

核K-均值聚類方法需要輸入聚類個數(shù)，不能處理異常值或噪聲，Chandrakala等[14]提出了一種在核特征空間基于密度的聚類方法，可以聚類變長度的MTS樣本，不需要輸入聚類個數(shù)，且性能優(yōu)于光譜聚類以及核K-means聚類。Edmond 等[15]為了將不同的時間序列按照底層數(shù)據(jù)結(jié)構(gòu)進行分組，提出了一種基于獨立分量分析的時間序列數(shù)據(jù)聚類算法。

基于實例的方法使用MTS樣本的全部信息，避免了特征的丟失；但MTS具有高維性和高冗余性，過多的信息可能導(dǎo)致內(nèi)存壓力大、距離度量的計算量大且不穩(wěn)定以及過多的信息使特征表達不準確等問題?；趯嵗腗TS聚類方法特性的比較如表1所示。

表1 基于實例的MTS聚類方法特性的比較

2 基于特征的方法(Feature-based)

基于特征的時間序列聚類是指將時間序列數(shù)據(jù)經(jīng)過變換或映射提取特征，實現(xiàn)維數(shù)約簡，最后再結(jié)合其它聚類算法實現(xiàn)聚類。在基于特征的時間序列聚類中，按照時間序列特征的分類，可以將基于特征的時間序列聚類分成三類，即基于形狀、結(jié)構(gòu)和模型的時間序列聚類?；谛螤畹姆椒ǜ鶕?jù)原始時間序列的波動形狀提取特征，其性能可能會受到噪聲、振幅縮放、偏移平移、縱向縮放、線性漂移和不連續(xù)[1]等問題的影響；基于結(jié)構(gòu)特征的聚類主要是從數(shù)據(jù)的結(jié)構(gòu)特征出發(fā)，揭示時間序列潛在的規(guī)律?；谀Ｐ吞卣鞯木垲愂侵赴凑詹煌囊蠡蚰康?，找到相對應(yīng)的模型，然后根據(jù)模型特征將樣本分到不同的組中。

小波技術(shù)具有保持時間和頻率信息的能力，在非平穩(wěn)信號處理中表現(xiàn)良好，是一種適用于時間序列數(shù)據(jù)處理和監(jiān)測以及統(tǒng)計過程控制的潛在工具[16]。DUrso等[17]首先在若干個尺度上將MTS樣本每個變量分解為小波序列，然后在每個尺度上計算小波的方差、MTS任何兩個變量之間小波系數(shù)的相關(guān)度，最后在每個尺度上將小波的方差以及小波系數(shù)之間的相關(guān)度連接成一個向量，用這個向量代表MTS樣本進行硬和模糊聚類(Crisp and fuzzy clustering)。Barragan等[16]使用基于連續(xù)小波變換(CWT)的多尺度PCA相似性因子計算MTS樣本之間的距離，對MTS樣本進行模糊聚類，并將該方法用于Tennessee Eastman Process(TEP)數(shù)據(jù)集。

此外，考慮MTS具有基于變量和基于時間的維度，Li[18]使用中心序列表示MTS，用分段聚合近似和符號化進一步表示由中心序列導(dǎo)出的擴展序列；Wang等[19]將時間序列的每個變量看成單變量時間序列提取其統(tǒng)計特征組成新的向量；Li[20]計算任意兩個變量之間的協(xié)方差用于表示MTS；Fontes等[21]將改進的PCA相似度因子和基于均值的歐氏距離(AED)結(jié)合在模糊聚類方法中，使用主成分方向和均值的加權(quán)和來比較不同的MTS，并將其用于燃氣渦輪機的故障分析。Li等[1]提出了一種基于動態(tài)時間扭曲(DTW)和形狀距離(SDB)兩種距離測量方法的特征加權(quán)聚類方法。該聚類算法分為四個階段。首先，使用快速搜索和尋找密度峰值(DPC)的聚類方法選擇聚類中心。然后，考慮多元時間序列的整體匹配，對所有變量進行DTW生成模糊隸屬度矩陣。然后利用SBD測量各維間的距離并構(gòu)造多個模糊隸屬度矩陣，重新考慮各獨立維的貢獻。最后，利用傳統(tǒng)的模糊聚類算法模糊C-means對模糊隸屬度矩陣進行聚類并生成聚類結(jié)果。

考慮之前算法均是將多變量數(shù)據(jù)矩陣變成向量進行處理，He等[22]提出一種保持數(shù)據(jù)矩陣結(jié)構(gòu)的基于空間加權(quán)距離的模糊聚類(SWMDFC)算法。算法使用變元的PCA算法，對同一變量的所有樣本構(gòu)造特征向量組成單變量時間序列使用PCA實現(xiàn)變量降維。對降維后的變量還原為多變量時間序列，使用空間加權(quán)距離計算矩陣相似性，最終使用模糊聚類劃分樣本類別。鄭誠[23]將MTS每個時刻的值放入矩形網(wǎng)格中用二維離散余弦變換DCT來對矩形網(wǎng)格提取特征得到特征矩陣，又將每個時刻間的矩陣變換看作向量，從而用高維空間的線段序列來表示多變量時間序列，提出了 LS 相似度來計算線段序列之間的相似程度，最后采用層次聚類來發(fā)現(xiàn)其中的模式并找出其中的離群點。Zhou等[24,25]將MTS數(shù)據(jù)集轉(zhuǎn)化為一個多關(guān)系網(wǎng)絡(luò)，提出了一種基于多重非負矩陣因子分解(MNMF)的多關(guān)系社區(qū)檢測算法，用于MTS聚類；多關(guān)系網(wǎng)絡(luò)描述了MTS樣本之間的局部以及全局關(guān)系，MNMF充分考慮MTS樣本內(nèi)部變量之間的復(fù)雜關(guān)系。Liang等[26]專注于處理高維多元時間序列，將傳感器網(wǎng)絡(luò)在一個時間步長的輸出數(shù)據(jù)表示為一個圖像，并用圖像的BSF特征(Bipolar Sigmoid Feature)來表征圖像內(nèi)容即傳感器網(wǎng)絡(luò)的狀態(tài)，從而將時間序列轉(zhuǎn)化為高維特征空間中的軌跡，引入鏈相似性來度量時間序列的相似性并采用層次聚類方法來探索MTS的模式。

copulas是內(nèi)含隨機變量之間依賴結(jié)構(gòu)的分布，Marti等[27]提出的MTS聚類方法，使用Earth Mover's Distance度量MTS樣本內(nèi)部依賴之間的相似程度，使用Dependence Coefficient度量MTS樣本相互依賴關(guān)系的相似程度對MTS樣本進行聚類，比較這三種距離的優(yōu)缺點。處理MTS中的不可見類的描述和識別方法是具有挑戰(zhàn)性的問題，Hosseini等[28]提出一個無監(jiān)督學習的框架，實現(xiàn)對MTS數(shù)據(jù)集中不可見類的可解釋分析。它基于一種新的多核字典結(jié)構(gòu)(MKD)，使用帶標簽的MTS維的核表示來學習語義屬性。基于這些屬性，無監(jiān)督MKD-SC框架根據(jù)特征空間中未見類的維數(shù)與已見類別維數(shù)的關(guān)系(部分/全部)重新構(gòu)造特征空間中未見類，從而為新數(shù)據(jù)提供可解釋的描述。在得到稀疏編碼的基礎(chǔ)上，提出了一種增量聚類方法來逐步將新的MTS分類為不同的聚類。

基于特征的方法，可以在清楚的表達特征的同時實現(xiàn)維數(shù)約簡；但上述大多數(shù)方法沒有清晰考慮MTS的時間和變量屬性，本質(zhì)上MTS樣本是二維數(shù)據(jù)。圖1是基于特征的MTS聚類方法的梳理。

圖1 基于特征的MTS聚類方法的梳理

3 基于模型的方法(Model-based)

基于模型的時間序列聚類是指，先對時間序列建立模型，然后利用模型的參數(shù)、系數(shù)、誤差等模型信息對時間序列數(shù)據(jù)進行聚類，得到聚類結(jié)果；或者將原始時間序列進行離散化，然后建立模型，提取模型參數(shù)，再進行聚類。時間序列數(shù)據(jù)挖掘可使用的模型有很多，如人工神經(jīng)網(wǎng)絡(luò)、隱馬爾科夫、高斯混合等經(jīng)典模型。

Vaquez等[29]對MTS的變量進行聚類，首先使用遞歸神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Networks)和遷移學習(transfer learning)計算每個MTS樣本變量之間的相似度，得到每個MTS樣本的鄰接矩陣，將這些鄰接矩陣聚合為一個總的鄰接矩陣，然后對變量進行分組。Vazquez等[30]對先前的工作[29]進行了改進，先使用樣條曲線對MTS進行光滑處理，然后再對MTS建立遞歸神經(jīng)網(wǎng)絡(luò)模型。Dino等[31]為了處理來自不同領(lǐng)域的變長多變量時間序列，提出一種新的方法DeTSEC。DeTSEC分為兩個階段，首先學習基于門控循環(huán)單元網(wǎng)絡(luò)(Gated Recurrent Unit, GRU)的加入注意力機制的自動編碼器，旨在初步完成數(shù)據(jù)的嵌入表示；隨后在聚類改進階段向?qū)?yīng)的類延伸嵌入流行。

基于監(jiān)督學習的深度學習算法可以學習數(shù)據(jù)的隱藏特征從而為聚類問題建立更準確的模型。但現(xiàn)實中的時間序列大部分是無標簽的，因此基于監(jiān)督學習的深度學習算法無法直接用于時間序列聚類。為此，Tavakol等[32]首先提取多變量時間序列的特征用于傳統(tǒng)的K-means聚類以獲得數(shù)據(jù)的標簽，從而將問題從無監(jiān)督學習轉(zhuǎn)化為有監(jiān)督學習；其次，建立基于自動編碼器的深度學習模型，學習時間序列數(shù)據(jù)的已知特征和隱藏特征及其創(chuàng)建的標簽，預(yù)測未知的時間序列數(shù)據(jù)的標簽。

Sidart Deb[33]提出了基于向量自回歸(vector auto-regressive, VAR)模型估計的參數(shù)向量來識別多變量時間序列樣本對或樣本組的相似性的檢驗程序。該程序同時適用聚類個數(shù)已知和未知的情況，因此可以廣泛用于現(xiàn)實中的各種問題。Zhou等[34]提出的可以處理不等長、離散值的基于模型的MTS聚類算法包括以下三步：首先將時間序列離散化；然后發(fā)現(xiàn)時態(tài)模式，用置信值表示不同變量之間的關(guān)系，最后，使用模式的置信值對MTS樣本聚類。

用MTS子序列聚類，可以從時態(tài)數(shù)據(jù)中發(fā)現(xiàn)重復(fù)模式。Hallac等[35]提出了一種基于Toeplitz逆協(xié)方差的MTS子序列的聚類方法(TICC)，同時對數(shù)據(jù)進行分段和聚類，根據(jù)子序列的相關(guān)結(jié)構(gòu)對其進行聚類，并通過多層馬爾可夫隨機場(Markov random field，MRF)對每個子序列進行重構(gòu)，為了發(fā)現(xiàn)這些簇，TICC通過動態(tài)規(guī)劃和ADMM來更新簇的MRFs.針對既有名詞性變量又有數(shù)值型變量的MTS，Ghassempour等[36]提出了一種基于HMMs的聚類方法，首先將每個時間序列映射為一個HMM，然后，定義一個合適的度量，計算HMMs之間的距離；最后，基于距離矩陣對HMMs進行聚類。

Li等[37]提出一種基于模型的自適應(yīng)狀態(tài)連續(xù)稀疏逆協(xié)方差(ASCSICC)聚類算法。引入狀態(tài)連續(xù)性，使傳統(tǒng)的高斯混合模型(GMM)適用于時間序列聚類。為了防止過擬合，采用乘子交替方向法優(yōu)化GMM逆協(xié)方差的參數(shù)。此外，該方法同時對時間序列進行分段和聚類。在技術(shù)上，首先根據(jù)相鄰時間序列數(shù)據(jù)的距離相似度估計自適應(yīng)狀態(tài)連續(xù)性。然后，以自適應(yīng)狀態(tài)連續(xù)性的動態(tài)規(guī)劃算法為e步，以求解稀疏逆協(xié)方差的ADMM為m步。將E-step和M-step組合成期望最大化(EM)算法進行聚類處理。Mikalsen等[38]針對缺失數(shù)據(jù)的多元時間序列，提出時間序列聚類核方法(TCK)，利用改進的信息先驗分布對角協(xié)方差GMM模型處理MTS缺失值，利用集成學習方法結(jié)合多個GMM的聚類結(jié)果形成最終的核，以確保對參數(shù)的魯棒性。TCK可以作為許多不同的學習算法的輸入，特別是在核方法中。實驗結(jié)果表明，TCK對超參數(shù)設(shè)置具有較強的魯棒性，對無缺失數(shù)據(jù)的預(yù)測任務(wù)具有較強的魯棒性，對有缺失數(shù)據(jù)的預(yù)測任務(wù)具有較好的魯棒性。

基于模型的方法中，建模過程需要消耗一定時間且使用模型參數(shù)進行聚類，模型的不確定性對聚類效果有一定影響。圖2是基于模型的MTS聚類方法的梳理。

圖2 基于模型的MTS聚類方法的梳理

4 多變量時間序列聚類的應(yīng)用

多變量時間序列聚類廣泛應(yīng)用于金融商業(yè)等社會人文科學以及醫(yī)療、工程、監(jiān)測、人體模式識別和地球物理分析等領(lǐng)域。

Dai C等[39]針對未標記EEG時間序列聚類問題，提出了一種新的EEG聚類算法將腦電聚類映射到改進的Frechet相似性加權(quán)腦電圖的最大權(quán)值團搜索。考慮腦電圖中頂點和邊的權(quán)重，并根據(jù)頂點和邊的相似權(quán)值對腦電圖進行聚類。

Zhang等[40]首先利用離散小波變換獲取每對變量之間的小波方差和相關(guān)系數(shù)，實現(xiàn)多元時間序列的初始聚類，將相關(guān)性相似但形狀相反的時間序列分配到同一聚類中；然后通過符號聚合近似(SAX)方法，基于形狀對多元時間序列進行聚類；最后將這既考慮相關(guān)性又考慮形狀的兩階段多元時間序列聚類算法用于北京IC卡客流量數(shù)據(jù)分析。

為了有效地對金融MTS數(shù)據(jù)進行聚類，Zhou等[41]首先利用局部線性嵌入算法將原始時間序列數(shù)據(jù)進行降維處理，然后對提取的特征向量采用改進的kmeans算法進行聚類。

聚類分析能作為獨立的工具來獲得數(shù)據(jù)分布的情況，還可以作為其他算法的預(yù)處理步驟，簡化計算量，提高分析效率。Kamal等[42]將模糊聚類與遺傳算法相結(jié)合，模糊聚類算法根據(jù)歷史數(shù)據(jù)對每個聚類的隸屬度對其進行模糊化，然后利用這些隸屬度對結(jié)果進行去模糊化。此外，遺傳算法負責選擇適當?shù)哪Ｐ?，將其?yīng)用于交通事故傷亡人數(shù)和著名大學招生數(shù)據(jù)集的預(yù)測。Abonyi等[43]提出了一種用于同時識別局部概率主成分分析(PPCA)模型的聚類算法并將其用于視頻監(jiān)控。其中，PPCA模型用于度量分段的同質(zhì)性，模糊集用于表示分段的時間，聚類相容性準則的模糊決策算法來確定所需分段數(shù)，而所需主成分數(shù)則由模糊協(xié)方差矩陣特征值的橫截面圖來確定。該算法在時間上傾向于連續(xù)聚類，并能檢測出多元時間序列隱藏結(jié)構(gòu)的變化。Chen等[44]提出一種新的自動聚類算法來生成不同長度的語篇區(qū)間，并將其用于加權(quán)指數(shù)(TAIEX)的預(yù)測。

此外，Malik等[45]使用不同的MTS聚類方法對比分析人體平衡控制的四種模式，試圖尋找其關(guān)聯(lián)關(guān)系。Salvo等[46]提出了一種基于動態(tài)時間序列分割和自組織映射技術(shù)的地球物理多元時間序列聚類方法。

5 總 結(jié)

本文從基于實例、基于特征和基于模型三個方面，對MTS聚類方法進行了綜述，并簡要介紹其在現(xiàn)實中的應(yīng)用。MTS聚類研究目前已經(jīng)有了很大的進展，但仍存在很多問題需要解決。例如，MTS的聚類研究主要集中在相似性度量、維數(shù)約簡以及聚類原型的研究，其中度量的穩(wěn)定性，如何從兩個維度進行維數(shù)約減進一步提高聚類效果值得進一步研究；此外，深度學習方法的出現(xiàn)極大的提高了MTS的聚類效果，但許多深度學習方法無法直接處理無標簽數(shù)據(jù)，將深度學習應(yīng)用于MTS聚類也值得今后進一步研究。