楊秋穎，翁小清

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

0 引 言

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

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

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

1 背景和相關(guān)工作

1.1 局部線性嵌入

LLE算法的具體步驟為：

(1)尋找每個(gè)樣本點(diǎn)xi的k近鄰的集合。

(3)求低維嵌入Y。計(jì)算xi在其低維空間的嵌入點(diǎn)yi，使其重構(gòu)的代價(jià)函數(shù)φ(Y)最小，即最小化式(1)：

(1)

這一優(yōu)化問(wèn)題可以通過(guò)對(duì)式(2)進(jìn)行特征值分解得到。

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

(2)

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

1.2 高斯混合模型

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

(3)

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

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

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

(4)

(5)

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

(6)

newΣc=

(7)

(8)

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

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

1.3 相關(guān)工作

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

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

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

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

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

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

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

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

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

2 基于LLE和GMM的聚類算法

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

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

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

輸出：聚類結(jié)果。

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

Step2：對(duì)任意xi的k個(gè)最近鄰點(diǎn)xj，構(gòu)造近鄰集合；

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

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

Step6：E-step，求每個(gè)樣本對(duì)每個(gè)類別的概率；

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

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

Step9：用訓(xùn)練好的GMM模型進(jìn)行聚類。

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

采用來(lái)自UCR數(shù)據(jù)庫(kù)的時(shí)間序列數(shù)據(jù)集，數(shù)據(jù)集都具有非隨機(jī)結(jié)構(gòu)且提供聚類基準(zhǔn)，即標(biāo)簽信息。表1列出了36個(gè)數(shù)據(jù)集的主要特征，包括序號(hào)、樣本集名稱、樣本總數(shù)、樣本長(zhǎng)度和類別個(gè)數(shù)。這些數(shù)據(jù)集涉及工業(yè)、圖像識(shí)別、人體行為識(shí)別、醫(yī)學(xué)和化學(xué)計(jì)量學(xué)等領(lǐng)域。

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

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

(9)

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

3.3 性能比較

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

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

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

表2 與非深度學(xué)習(xí)方法的RI比較

續(xù)表2

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

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

表3 與深度學(xué)習(xí)方法的RI比較

續(xù)表3

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

3.4 消融實(shí)驗(yàn)

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

表4 消融實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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