基于LLE和高斯混合模型的時間序列聚類

楊秋穎，翁小清

(河北經貿大學 信息技術學院，河北 石家莊 050061)

0 引 言

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

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

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

1 背景和相關工作

1.1 局部線性嵌入

LLE算法的具體步驟為：

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

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

(1)

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

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

(2)

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

1.2 高斯混合模型

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

(3)

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

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

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

(4)

(5)

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

(6)

newΣc=

(7)

(8)

(4)循環執行(2)和(3)步，計算對數似然函數直到收斂。

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

1.3 相關工作

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

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

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

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

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

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

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

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

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

2 基于LLE和GMM的聚類算法

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

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

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

輸出：聚類結果。

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

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

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

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

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

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

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

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

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

3 實驗結果與分析

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

3.1 數據集描述

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

表1 數據集概要情況

3.2 評價標準

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

(9)

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

3.3 性能比較

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

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

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

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

續表2

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

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

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

續表3

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

3.4 消融實驗

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

表4 消融實驗結果

3.5 參數對算法性能的影響

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

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

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

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

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

4 結束語

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