楊秋穎，翁小清

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

0 引 言

時間序列(TS)是從均勻的時間間隔和給定的采樣率下測量收集的有序數(shù)據(jù)集，其研究遍及金融、醫(yī)學、軌跡分析和人體動作分段等多個領域。時間序列聚類[1]是在沒有任何先驗知識的情況下分析大量時間序列數(shù)據(jù)的有效方法，其目的以某種方式將給定的數(shù)據(jù)集劃分為一組不重疊的集群，從而揭示數(shù)據(jù)的底層結構。在進行聚類時合適的維數(shù)約簡和相似性度量對聚類效果有重大影響[2]，但由于時間序列高維，高冗余以及存在非線性結構等特點，將傳統(tǒng)的聚類算法直接用于此類數(shù)據(jù)時往往無法取得滿意的效果。

維數(shù)約簡根據(jù)是否存在變換矩陣，可分為線性和非線性兩種。多維尺度變換[3]、主成分分析[4]等線性方法默認先進行投影變換，然后找到一個使其目標最大化的低維空間；但現(xiàn)實中絕大部分時間序列是非線性的，線性方法在應用時存在局限性。非線性降維方法[5]有核方法、神經(jīng)網(wǎng)絡和流形學習等，局部線性嵌入(Locally Linear Embedding，LLE)[6]是一種重要的流形學習方法。流形學習認為采樣數(shù)據(jù)是由低維流形映射到高維空間得到的，其本質(zhì)是從原始的高維數(shù)據(jù)中尋找產(chǎn)生數(shù)據(jù)的內(nèi)在流形，并求出相應的嵌入映射。LLE假設采樣數(shù)據(jù)分布在一個潛在的流形上，而流形的局部可以近似為歐氏空間，具有線性結構，故任意一點可以表示為其k近鄰的線性組合，并能夠在低維流形進行重構。LLE將高維的非線性結構映射到低維空間的同時很好地保留了其內(nèi)蘊特征。

針對時間序列非線性和維度高的特點，該文提出一種基于LLE和高斯混合模型(Gaussian Mixture Model，GMM)的時間序列聚類算法LLE_GMM。首先從保留數(shù)據(jù)集局部結構的角度，使用LLE將每個高維時間序列樣本表示為其k近鄰的線性組合，并在低維空間進行重構，在保持數(shù)據(jù)集局部幾何結構的同時實現(xiàn)維數(shù)約簡；然后使用GMM從概率分布的角度進行聚類分析。將LLE_GMM算法與已有的非深度學習和深度學習算法進行了比較，在36個數(shù)據(jù)集上的實驗結果表明，該方法對單變量時間序列具有更好的聚類效果。

1 背景和相關工作

1.1 局部線性嵌入

LLE算法的具體步驟為：

(1)尋找每個樣本點xi的k近鄰的集合。

(3)求低維嵌入Y。計算xi在其低維空間的嵌入點yi，使其重構的代價函數(shù)φ(Y)最小，即最小化式(1)：

(1)

這一優(yōu)化問題可以通過對式(2)進行特征值分解得到。

M=(I-W)(I-W)T

(2)

一般的，M的第一個最小特征值為0，不能反映數(shù)據(jù)特征，故選M的第2到d+1個特征值對應的特征向量，即低維嵌入Y={y2,…,yd+1}。

1.2 高斯混合模型

高斯混合模型(GMM)假設數(shù)據(jù)集是有限個高斯分布的線性混合，每個高斯分布對應一個類。具體地，給定類個數(shù)C，對于給定的樣本yi，GMM的概率密度函數(shù)定義為：

(3)

用EM(Expectation Maximization)算法估計GMM參數(shù)。其基本步驟如下：

(1)根據(jù)給定的C值，隨機初始化每個簇的高斯分布參數(shù)(均值和方差)以及權重向量w。

(2)E步：計算數(shù)據(jù)點xi對每個簇的隸屬度E[Zic]。隸屬度越大，樣本由該分模型生成的概率越大。隸屬度公式如式(4)和式(5)所示：

(4)

(5)

(3)M步：用第(2)步計算得到的所有點對每個分模型Zc的隸屬度更新模型參數(shù)，如式(6)～式(8)所示：

(6)

newΣc=

(7)

(8)

(4)循環(huán)執(zhí)行(2)和(3)步，計算對數(shù)似然函數(shù)直到收斂。

GMM使用后驗概率不斷更新各個分模型的參數(shù)，最終得到MTS樣本對各個類別的隸屬度，從概率分布角度進行聚類分析。

1.3 相關工作

時間序列聚類大致可以分為基于實例、基于特征和基于模型的方法三種[8]。

基于實例的方法中，Azencott等[9]將基于圖的拉普拉斯譜聚類與模擬退火相結合研究時間序列間的互信息，自動生成最優(yōu)的時間序列聚類，但該方法只是適用于等長的有限數(shù)據(jù)集。考慮時間序列的非線性以及滯后問題，張貝貝等[10]將Copula函數(shù)引入識別動態(tài)相關結構的相似性度量。Guo等[11]推廣了基于核的模糊c均值聚類算法，在動態(tài)時間對準核(DTAK)中嵌入非線性時間對準使得基于核的模糊c均值可以用于可變長度的序列。

基于特征的方法中，Chandereng等[12]考慮時間的滯后性影響時間序列的相似性，提出了一種滯后懲罰加權相關(Lag Penalized Weighted Correlation，LPWC)的聚類相似度度量方法，用于對隨著時間推移表現(xiàn)出密切相關行為的時間序列進行分組。針對長度比較短且存在相位差的時間序列，Yang等[13]提出一種Shape-Distance Ratio (SDR)的相似性度量方法并結合k-Medoids (PAM)分區(qū)聚類算法實現(xiàn)時間序列聚類。Euan等[14]將譜理論與層次聚類相結合，提出層次譜合并(HSM)時間序列聚類算法。Duan等[15]用趨勢濾波對時間序列進行最優(yōu)分割和模糊信息粒化將原始數(shù)據(jù)轉為粒狀時間序列，提出基于線性模糊信息粒的動態(tài)時間扭曲(LFIG_DTW)距離的分層聚類方法，LFIG_DTW算法不僅可以檢測距離的增減趨勢，還可以檢測距離的變化周期和變化速率。Caiado等[16]提出一種新的非參數(shù)的用于描述和比較長時間序列大集合的頻域方法。Wang等[17]針對不等長區(qū)間值時間序列的聚類問題提出BRDTW算法。

Wang等[18]提出時間序列的稀疏子空間聚類算法(Sparse Subspace Clustering，SSC)，利用稀疏表示構造相似度矩陣再進行光譜聚類，將其運用到電影票房研究問題。稀疏編碼字典學習中數(shù)據(jù)樣本與字典原子的長度不一致以及存在時間延遲的問題，Yazdi等[19-20]提出基于非線性時間不變性kSVD (twi-ksvd)的稀疏編碼字典學習時間序列聚類算法。

為了提取時間序列的形狀特征，Zhang等[21]結合shapelet學習、shapelet正則化、光譜分析和偽標記的優(yōu)點，擴展了監(jiān)督式shapelet學習模型來處理未標記的時間序列數(shù)據(jù)，提出了無監(jiān)督顯著子序列學習(Unsupervised Salient Subsequence Learning，USSL)。Xiao等[22]結合時間特征網(wǎng)絡和注意力LSTM網(wǎng)絡提出一種魯棒時序特征網(wǎng)絡(RTFN)，將基于殘差網(wǎng)絡和multi-head卷積神經(jīng)網(wǎng)絡的時間特征網(wǎng)絡用于提取序列的時態(tài)特征，attentional LSTM網(wǎng)絡進一步提取時序中的shapelets特征，并將其用于分類和聚類。

在基于模型的方法中，Corduas等[23]針對傳統(tǒng)的ARIMA模型中one-step-ahead預測函數(shù)可能導致對模型的錯誤描述，提出h-step-ahead預測函數(shù)，用h-step-ahead預測誤差的參數(shù)的歐氏距離平方和度量時間序列的相似性。

基于監(jiān)督學習的深度學習算法可以學習數(shù)據(jù)的隱藏特征。但現(xiàn)實中的時間序列大部分沒有標簽信息，因此基于監(jiān)督學習的深度學習算法無法直接用于時間序列聚類。Xie等[24]提出Deep Embedded Clustering算法，以self-learning的方式定義聚類損失，同時更新網(wǎng)絡和聚類中心的參數(shù)。然而聚類損失并不能保持局部結構，會導致嵌入空間的破壞。為此Guo等[25]使用under-complete的自動編碼器來學習嵌入特征和保持數(shù)據(jù)生成分布的局部結構，提出了Improved Deep Embedded Clustering算法。

Sai等[26]提出深度時間聚類(Deep Temporal Clustering，DTC)，采用CNN自動編碼器與BI-LSTM聚類層學習聚類表示。通過測量預測結果與目標分布之間的KL散度來設計聚類層；但直接轉矩控制的性能很大程度上取決于編碼器的能力，根據(jù)表示學習計算的預測分布在用來計算目標分布時存在不穩(wěn)定性。為提高編碼器能力，Ma等[27]將時間重構和K-Means聚類集成到seq2seq模型中，提出了時間序列輔助分類任務的偽樣本生成策略，提高了編碼器的能力。此外，F(xiàn)ortuin等[28]結合自組織映射(SOM)、變分自編碼器和Markov模型，提出一種可解釋離散表示學習。McConville等[29]采用流形方法提取特征，對重嵌入空間進行淺聚類。Ding等[2]將卷積神經(jīng)網(wǎng)絡在同一方向的輸出變化次數(shù)轉化為時間序列的相似性，通過優(yōu)先收集少量的高相似度數(shù)據(jù)來創(chuàng)建標簽，使用基于卷積神經(jīng)網(wǎng)絡的分類算法輔助聚類。

上述大多數(shù)方法或是未考慮時間序列的非線性結構，或是從保留全局特征的角度進行降維，沒有考慮數(shù)據(jù)集的局部結構，而數(shù)據(jù)集的局部結構對聚類效果有較大影響；此外上述大多數(shù)方法從距離角度度量時間序列的相似性，該文在保留時間序列局部特征的基礎上，使用GMM從概率分布角度進行聚類，提高了聚類性能。

2 基于LLE和GMM的聚類算法

基于LLE和GMM的聚類算法包括兩步驟：首先從保留數(shù)據(jù)集局部結構的角度，使用LLE將每個高維時間序列樣本表示為其k近鄰的線性組合，并在低維空間進行重構，在保持數(shù)據(jù)集局部幾何結構的同時實現(xiàn)維數(shù)約簡；然后使用GMM從概率分布的角度進行聚類分析。算法的主要步驟如下：

算法1：LLE_GMM(X,C,k,d)。

輸入：時間序列數(shù)據(jù)集。X={x1,x2,…,xN,xi∈Rm}，聚類個數(shù)C，近鄰個數(shù)k，嵌入維數(shù)d。

輸出：聚類結果。

Step1：對數(shù)據(jù)集X使用PCA算法去除噪聲和冗余；

Step2：對任意xi的k個最近鄰點xj，構造近鄰集合；

Step4：構造矩陣M=(I-W)(I-W)T，計算M的前d+1個特征值和對應的特征向量，則低維嵌入為Y={y2,…,yd+1}；

Step5：初始化高斯混合模型參數(shù)(w,μ,Σ)開始迭代；

Step6：E-step，求每個樣本對每個類別的概率；

Step7：M-step，優(yōu)化E-step的模型參數(shù)得到新的參數(shù)(w,μ,Σ)；

Step8：重復E-step和M-step，直到參數(shù)收斂或是達到最大迭代次數(shù)；

Step9：用訓練好的GMM模型進行聚類。

上述算法分為降維和模型訓練兩個部分。對于時間序列數(shù)據(jù)集X={x1,x2,…,xN,xi∈Rm}，N為樣本總數(shù)，m為輸入樣本維數(shù)。步驟1中使用PCA預處理的時間復雜度為O(Nm2)；步驟2-5為LLE降維，其中k近鄰搜索的復雜度是O(mN2)，構造權重系數(shù)矩陣的時間復雜度是O(mNk3)，求解低維嵌入的時間復雜度是O(dN2)，d為嵌入維數(shù)；步驟5-9是構建高斯混合模型聚類階段，時間復雜度與迭代次數(shù)有關，每次迭代過程分為E-step和M-step。E-step計算樣本的所屬類別概率的時間復雜度為O(NC)，C為類別個數(shù)；M-step更新參數(shù)w,μ的時間復雜度為O(k)；計算協(xié)方差Σ的時間復雜度為O(NCd2)，故每次迭代的時間復雜度為O(NC(d2+1)+C)；當?shù)螖?shù)為h時，算法整體時間復雜度為O(Nm2+mN2+mNk3+dN2+hNCd2)。

3 實驗結果與分析

在36個來自UCR[30]數(shù)據(jù)庫的時間序列數(shù)據(jù)集上用Rand指數(shù)對聚類性能進行評估。用Matlab 2019b編寫了所有程序，并在方正計算機(內(nèi)存16 GB，CPU 3.30 GHz，Windows 7操作系統(tǒng))上實現(xiàn)。

3.1 數(shù)據(jù)集描述

采用來自UCR數(shù)據(jù)庫的時間序列數(shù)據(jù)集，數(shù)據(jù)集都具有非隨機結構且提供聚類基準，即標簽信息。表1列出了36個數(shù)據(jù)集的主要特征，包括序號、樣本集名稱、樣本總數(shù)、樣本長度和類別個數(shù)。這些數(shù)據(jù)集涉及工業(yè)、圖像識別、人體行為識別、醫(yī)學和化學計量學等領域。

表1 數(shù)據(jù)集概要情況

3.2 評價標準

為使文中算法與已有算法具有對比性，采用常見的外部方法Rand指數(shù)[31](RI)評價LLE_GMM的聚類效果。

(9)

式中，TP表示屬于同類的樣本的預測標簽相同，F(xiàn)N表示屬于同類的樣本的預測標簽不同，F(xiàn)P表示屬于不同類的樣本的預測標簽相同，TN表示不屬于同一類的樣本的預測標簽也不同。Rand指數(shù)取值為[0,1]，是正向指標，當原有的標簽信息與預測結果完全一致時，RI=1。

3.3 性能比較

為檢驗LLE_GMM算法性能，將其與10種已有算法進行Rand指數(shù)(RI)比較，10種算法分為兩個類型：基于非深度學習以及基于深度學習。其中非深度學習的分為基于實例和基于特征兩種，基于特征的聚類算法又分為基于結構和基于形狀兩個方面。

表2給出了用5種基于非深度學習的方法以及LLE_GMM在36個數(shù)據(jù)集上進行聚類的RI值，六種方法的最高RI值在表2中加粗顯示。表2中第1列的序號對應表1中的數(shù)據(jù)集，第2列至第6列分別為KSC[32]、NDFS[33]、RSFS[34]、kshape[35]、USSL[21]的RI值；最后一列給出了LLE_GMM的RI值以及對應的近鄰個數(shù)k和嵌入維數(shù)d。

表2的倒數(shù)第2行Avg給出各種方法的平均RI值，可以看出LLE_GMM在36個數(shù)據(jù)集的平均RI為0.802 0，在六種非深度學習算法中取得最優(yōu)結果。表2的最后一行Win給出各算法在36個數(shù)據(jù)集上取得的最優(yōu)RI的個數(shù)，可以看出LLE_GMM在23個數(shù)據(jù)集上取得最優(yōu)結果。

表2 與非深度學習方法的RI比較

續(xù)表2

表3給出了用5種基于深度學習的方法以及LLE_GMM在36個數(shù)據(jù)集上進行聚類的RI值，這六種方法的最高RI值同樣加粗顯示。表3中第1列的序號對應表1中的數(shù)據(jù)集，第2列至第6列分別為SOM-VAE[28]、N2D[29]、IDEC[25]、DTCR[27]和TSC_CNN[2]的RI值；最后一列給出了LLE_GMM的RI值以及對應的近鄰個數(shù)k和嵌入維數(shù)d。

表3的倒數(shù)第2行Avg給出各種方法的平均RI值，LLE_GMM在36個數(shù)據(jù)集的平均RI在六種算法中同樣取得最優(yōu)結果。表3的最后一行Win給出各算法在36個數(shù)據(jù)集上取得的最優(yōu)RI的個數(shù)，可以看出LLE_GMM在18個數(shù)據(jù)集上取得最優(yōu)結果。

表3 與深度學習方法的RI比較

續(xù)表3

深度學習算法在執(zhí)行時會一定程度上受到算力的限制，LLE_GMM在不依賴硬件設施的同時可以取得不差于深度學習算法的效果。

3.4 消融實驗

LLE_GMM算法有LLE和GMM兩個模塊，為驗證兩個模塊的有效性，分別設置GMM和LLE_Kmeans兩個對照實驗，實驗結果如表4中第2和第3列所示。僅使用GMM模塊，平均RI指數(shù)為0.715 6，相較于LLE_GMM下降了8.64%；LLE_Kmeans的平均RI指數(shù)為0.773 8，相較于LLE_GMM下降了2.82%。實驗證明，GMM相較于Kmeans可以更好地擬合復雜的數(shù)據(jù)分布，發(fā)現(xiàn)橢圓形簇，提升聚類效果。加入LLE模塊的GMM通過維數(shù)約簡有效降低了數(shù)據(jù)冗余，更好地表達非線性數(shù)據(jù)的內(nèi)蘊特征，提升了聚類效果。

表4 消融實驗結果

3.5 參數(shù)對算法性能的影響

LLE_GMM算法有兩個參數(shù)k、d，分別表示近鄰個數(shù)以及嵌入維數(shù)。

圖1給出了d=35在DiatomSizeReduction數(shù)據(jù)集上，以及d=16在DistalPhalanxOutlineAgeGroup數(shù)據(jù)集上，算法的RI值隨近鄰個數(shù)k的變化情況。從圖1中可以看出，當k的取值過小時，RI值較小，考慮可能是過小的近鄰個數(shù)無法保證時間序列樣本在低維空間的拓撲結構；隨著k的增大，RI值逐漸增大達到最大值，然后在一定范圍內(nèi)波動；但是當k值過大時，RI值呈現(xiàn)下降趨勢，考慮近鄰個數(shù)過大時無法體現(xiàn)數(shù)據(jù)集的局部特性。因此，LLE_GMM算法需要根據(jù)應用場景選擇合適的k值。

圖1 LLE_GMM算法RI值隨近鄰個數(shù)k的變化

圖2給出了k=15時在coffee和Meat數(shù)據(jù)集上，算法的RI值隨嵌入維數(shù)d的變化情況。從圖2中可以看出，當d的取值過小時，RI值較小，考慮可能是過小的嵌入維數(shù)導致不同樣本在嵌入空間相互交疊；隨著d逐步增大，RI值快速增大達到最大值；隨后當d值過大時，RI值呈現(xiàn)下降趨勢并最終穩(wěn)定在一定范圍內(nèi)，考慮信息保留過多影響對原始數(shù)據(jù)的特征表達，使得效果下降。所以LLE_GMM算法并不需要很高的嵌入維數(shù)就可以獲得很好的聚類效果。

圖2 LLE_GMM算法RI值隨嵌入維數(shù)d的變化

4 結束語

提出了一種基于LLE和GMM的時間序列聚類算法。首先從保留數(shù)據(jù)集局部結構的角度，使用LLE將每個高維時間序列樣本表示為其k近鄰的線性組合，并在低維空間進行重構，在保持數(shù)據(jù)集局部幾何結構的同時實現(xiàn)維數(shù)約簡；然后使用GMM從概率分布的角度進行聚類分析。在36個數(shù)據(jù)集上分別與基于深度學習和基于非深度學習的算法進行對比，結果表明LLE_GMM的聚類性能好于已有算法。該文所提算法有兩個參數(shù)k和d，人工選取參數(shù)耗時且可能無法獲得全局最優(yōu)，因此如何自適應地選擇最優(yōu)參數(shù)值有待進一步研究；同時GMM限制樣本個數(shù)不得小于維數(shù)，如何在小樣本高維數(shù)據(jù)上改進聚類效果仍需進一步探索。