有監(jiān)督時間序列分割與狀態(tài)識別算法

史明陽,王 鵬,汪 衛(wèi)

(復(fù)旦大學(xué) 軟件學(xué)院,上海 201203)

0 概述

時間序列分割是獲取時間序列內(nèi)在信息的重要方式,在數(shù)據(jù)挖掘領(lǐng)域備受關(guān)注。當(dāng)前的時間序列分割算法多為無監(jiān)督類型,相同的時間序列可以具有多種不同可解釋的分割模式。在實(shí)際情況中,每一個片段的監(jiān)控數(shù)據(jù)通常對應(yīng)于被監(jiān)控對象不同的實(shí)際物理狀態(tài)。顯然,在通過不同分割方法獲得的大量分割結(jié)果中,并不是每一種分割模式都符合用戶的期望。因此,能夠選擇分割的模式在整個識別過程中就顯得尤為重要。

目前關(guān)于時間序列分割方式及其狀態(tài)判斷的研究較少,在此背景下,本文提出一種有監(jiān)督的時間序列分割與狀態(tài)識別算法SSR。通過構(gòu)建特征高斯概率分布模型設(shè)計相關(guān)序列的特征,在此基礎(chǔ)上,利用匹配損失計算和改進(jìn)的貪心策略設(shè)定特征權(quán)重約束,并利用增加分割位置約束條件及增量計算2種優(yōu)化方式進(jìn)一步提高算法效率。

1 相關(guān)工作

關(guān)于時間序列分割及狀態(tài)識別問題的解決方法,目前研究成果較多。文獻(xiàn)[1]提出一種基于重要點(diǎn)的時間序列分割方法,將考察時間窗擴(kuò)展到前一重要點(diǎn)、待考查點(diǎn)和下一指定時間窗之間,再通過考察時間窗口內(nèi)待考察點(diǎn)兩邊模式和變化幅度來確定重要點(diǎn),從而減小分割誤差。文獻(xiàn)[2]提出一種基于重要點(diǎn)與灰色GM(1,1)模型的時間序列分段算法,在保留全局特征的同時保持局部性質(zhì),能夠以較小的擬合誤差實(shí)現(xiàn)序列的壓縮。文獻(xiàn)[3]提出基于信息顆粒和模糊聚類的時間序列分割方法,使得時間序列的分割具有數(shù)據(jù)上的同質(zhì)性,得到既有時間信息又具有同質(zhì)性的時間序列分割結(jié)果。文獻(xiàn)[4]則提出一種基于Floyd算法的海溫時間序列分割方法。

隱馬爾科夫模型(Hidden Markov Model,HMM)是時間序列分割算法中一種常用的典型模型,其中SWAB[5]和pHMM[6]能夠從時間序列中進(jìn)行線性分割。pHMM是基于模式的隱馬爾科夫模型[7]和SWAB的改進(jìn),旨在揭示生成時間序列數(shù)據(jù)的系統(tǒng)全局圖。AutoPlait[8]是另一種典型的時間序列分割算法,它使用最小描述長度(MDL)和多級鏈模型(MLCM)對時間序列的替代HMM評分從而進(jìn)行分割。FLOSS[9]是一種基于Matrix Profile[10]構(gòu)建的在線流媒體語義分割方法。

現(xiàn)有的時間序列狀態(tài)識別方法可分為兩大類[11],一類是基于形狀的方法,其通過相似性度量來測量原始數(shù)字?jǐn)?shù)據(jù)中時間序列之間的距離,此類方法可以實(shí)現(xiàn)高精度,但計算昂貴,基于歐氏距離[12]或DTW距離[13]構(gòu)建的傳統(tǒng)1NN分類器為其典型示例;另一類是基于結(jié)構(gòu)的方法,其使用一些方法來描述類的特征,此類方法更能有效地抵抗噪聲,如SAX-VFSEQL[14]和SAX-VSM[15]在SAX[16]表示時間序列上構(gòu)建分類器。

2 問題描述

為闡述方便,首先給出本文研究的相關(guān)概念和問題的基本定義。

2.1 相關(guān)定義

定義1(時間序列) 一條時間序列T={t1,t2,…,tn}是長度為n的相等間隔實(shí)際值的連續(xù)有序序列。

定義2(子序列) 一條時間序列T的子序列s是T的子集,其中s的長度小于或等于T。

通常,時間序列數(shù)據(jù)是從真實(shí)的物理環(huán)境中獲得的,這意味著其中包含真實(shí)的物理意義。根據(jù)用戶需求和序列的實(shí)際情況將時間序列分割為子序列,對于分割結(jié)果中分割的子序列和相應(yīng)的語義描述,稱為片段和狀態(tài)。

定義3(片段) 一個時間序列T的第i個分割片段SEGi,是時間序列T分割后的第i個子序列。所以,時間序列T可以用分割片段表示為T={SEG1,SEG2,…,SEGm},其中m為此分割模式中子序列的數(shù)量。

定義4(狀態(tài))子序列SEGi的狀態(tài)ci是指SEGi所屬的分類表示。

本文研究目標(biāo)是將一條完整時間序列分成多個片段并對每一個子序列片段進(jìn)行狀態(tài)識別。根據(jù)上文子序列和狀態(tài)的定義,一個時間序列的分割模式可以定義如下:

定義5(分割模式) 一個關(guān)于時間序列T的分割模式可以表示為S(T)={,,…,},其中,m為這個分割模式中片段的數(shù)量,ri表示第i個片段的分割點(diǎn)位置,ci表示第i個片段的狀態(tài)類別。分割模式S(T)的第i個分割片段可以表示為SEGi={tri-1+1,tri-1+2,…,tri}。

SSR針對狀態(tài)類別已知的時間序列數(shù)據(jù),使用有監(jiān)督的方法建立分類模型。所需要的訓(xùn)練集為帶有狀態(tài)標(biāo)記的子序列集合。

2.2 問題定義

根據(jù)上文描述,本文目標(biāo)為尋找時間序列的一個分割模式,并根據(jù)已知限定信息找到每個段的狀態(tài),使得這個分割模式能夠最大程度符合用戶的期望。此處給出一個形式化的問題定義如下:

定義7給定帶有狀態(tài)類別標(biāo)記的訓(xùn)練數(shù)據(jù)集TS和待分割時間序列T={t1,t2,…,tn},尋找T的最優(yōu)分割模式S*(T)={,,…,}使匹配損失最小。匹配損失的計算將在3.3節(jié)給出。

3 時間序列分割與狀態(tài)識別算法SSR

SSR基于特征高斯概率分布模型及概率最大化思想進(jìn)行時間序列狀態(tài)識別,基于調(diào)整后的貪心策略進(jìn)行時間序列分割,其中時間序列狀態(tài)識別主要分為2個過程,即建立特征高斯概率分布模型和計算匹配損失。

3.1 特征高斯概率分布模型

帶有良好標(biāo)記的訓(xùn)練集可以提供有價值的指導(dǎo)作用,基于有監(jiān)督的方法可以獲得更符合用戶期望的分割模式,而能夠從訓(xùn)練數(shù)據(jù)集中提取相關(guān)信息并合理利用是整個過程中的關(guān)鍵一步。本文通過對訓(xùn)練集中同一類別的樣本數(shù)據(jù)提取相應(yīng)特征,構(gòu)建特征高斯概率分布模型。

3.1.1 特征選擇

首先應(yīng)合理選擇需要從訓(xùn)練集中提取的特征,從而更準(zhǔn)確地描繪不同的序列。在綜合考慮各種特征指標(biāo)之后,選定以下6個特征作為衡量標(biāo)準(zhǔn),分別是樣本序列的長度、均值、標(biāo)準(zhǔn)差、過零率、擬合斜率以及根據(jù)擬合斜率所產(chǎn)生的均方誤差(Mean Squared Error,MSE)損失。

通過不同狀態(tài)類別樣本序列的平均值,結(jié)合序列的長度、標(biāo)準(zhǔn)偏差和過零率,可以得到該類別序列的近似振動程度。同時,通過斜率和MSE損失能夠?qū)r間序列的趨勢進(jìn)行大致判斷。通過上述6個特征,可以粗略描繪出不同狀態(tài)類別時間序列對應(yīng)的特點(diǎn)。

3.1.2 特征高斯概率分布模型

特征模型是根據(jù)不同的狀態(tài)類別建立的。在訓(xùn)練數(shù)據(jù)集中,每一個特征類別下都有多個樣本序列數(shù)據(jù)。在確定提取特征以后,對每一個狀態(tài)類別中樣本序列的每一個特征進(jìn)行計算,同時記錄該特征值數(shù)值的均值和方差,以建立一個特征高斯概率分布模型,表示為M和Σ。Mi,j和Σi,j分別表示狀態(tài)類別i中的樣本序列集關(guān)于第j個特征值的均值和方差,計算公式為:

3.2 特征的權(quán)重約束設(shè)定

上文給出了特征選擇及特征高斯概率分布模型的建立過程。但是在真實(shí)場景的數(shù)據(jù)中時間序列的形態(tài)多樣,其特點(diǎn)屬性各異,在全部6個特征中,對于不同的時間序列,不同的特征對于狀態(tài)類別的區(qū)分度是不同的。所以,對于特征設(shè)定不同的權(quán)重約束是必要的。本文通過引入置信度分?jǐn)?shù)來設(shè)定特征的權(quán)重約束,通過在訓(xùn)練階段評估每個指標(biāo)的分類性能來學(xué)習(xí)置信度分?jǐn)?shù)。

在訓(xùn)練階段,分別使用單一的特征進(jìn)行類別區(qū)分,計算針對當(dāng)前類型時間序列數(shù)據(jù)當(dāng)前特征的分類準(zhǔn)確度,再對6個對應(yīng)的準(zhǔn)確度分?jǐn)?shù)進(jìn)行歸一化處理,得到調(diào)整后的置信度分?jǐn)?shù)w1,w2,…,w6作為每個特征的權(quán)重。

3.3 匹配概率及損失

(1)

通過上述計算,可以得到對于一個T的分割模式S(T)={,,…,}(下文簡寫為S)的匹配概率為:

(2)

其中,fSEGi,j表示SEGi第j個特征值。

在實(shí)際計算過程中,程序處理精度也是需要考慮的問題,由于1以內(nèi)浮點(diǎn)數(shù)的運(yùn)算會引入較大的誤差,因此需要對計算過程做進(jìn)一步處理。在整體尋找最佳匹配狀態(tài)類別的過程中,關(guān)注的并不是概率的絕對數(shù)值,而是概率之間的相對關(guān)系,可以對匹配概率做如下處理:

對式(2)進(jìn)行代數(shù)變換,得到:

(3)

定義匹配損失為:

(4)

將上文給出的權(quán)重約束引入損失計算,改寫式(4),可得到分割模式S的匹配損失為:

3.4 片段分割算法

SSR基于貪心的思想,通過迭代的方式進(jìn)行時間序列的分割。

設(shè)對于時間序列T,當(dāng)前已進(jìn)行i-1輪分割過程,第i-1個分割片段的分割點(diǎn)為ri-1,第i輪的分割過程如下:

對于每一類別由下式進(jìn)行匹配損失計算,得到ci,使得:

在確定當(dāng)前分割片段的狀態(tài)ci以后,根據(jù)前一分割點(diǎn)ri-1、狀態(tài)ci長度特征的均值Mci,1和標(biāo)準(zhǔn)差Σci,1,對分割點(diǎn)ri的范圍進(jìn)行限定,得到:

ri-1+Mci,1-3×Σc1,1≤ri≤ri-1+Mci,1+3×Σc1,1

最后,在限定范圍內(nèi)逐點(diǎn)掃描,得到匹配損失最小的點(diǎn)ri作為具體分割點(diǎn),使得:

至此,得到及第i個分割片段SEGi。

為避免單一類別匹配所產(chǎn)生的局部偏差造成全局的負(fù)面影響,本文對SSR的分割過程進(jìn)行調(diào)整。在狀態(tài)類別匹配損失計算的過程中,不僅考慮當(dāng)前分割片段SEGi的狀態(tài)類別,同時考慮下一序列片段SEGi+1的狀態(tài)類別,從而減小當(dāng)前序列片段的影響程度。

在確定類別的過程中,每次使用2個狀態(tài)類別進(jìn)行匹配損失計算,得到ci、ci+1,使得下式成立:

這種調(diào)整可減少當(dāng)前片段的影響程度,從而減小局部偏差對全局的影響。

4 算法效率優(yōu)化

為提升SSR的算法效率,本文提出了2種算法效率優(yōu)化方式,即通過增加分割點(diǎn)的約束條件及采用增量計算的方式進(jìn)行特征提取。

4.1 分割點(diǎn)約束條件

在上文介紹的算法過程中,對于分割片段SEGi具體分割點(diǎn)位置ri的選定,采用的是掃描并計算匹配損失的方式。顯然,在不靠近真實(shí)分割邊界的部分,相鄰點(diǎn)之間的匹配損失差值極小,逐點(diǎn)計算匹配損失會產(chǎn)生大量冗余的計算過程。

時間序列中狀態(tài)發(fā)生變化的位置,通常伴隨一個或多個特征大幅變化,稱時間序列中發(fā)生這樣巨大變化的點(diǎn)為特殊點(diǎn)。特殊點(diǎn)通常在時間序列上顯示為不一樣的形狀,例如拐點(diǎn)、峰值點(diǎn)等,而實(shí)際的分割點(diǎn)也更可能在這些特殊點(diǎn)中產(chǎn)生。因此,在算法過程開始之前首先預(yù)處理可能的候選分割點(diǎn)集,并在尋找具體分割點(diǎn)的過程中只掃描候選區(qū)間內(nèi)的候選點(diǎn),從中確定具體分割位置。具體求取方法為:以設(shè)定滑動窗口的方法求取窗口內(nèi)各特征值的極值點(diǎn),在對原始序列數(shù)值及每一個特征單獨(dú)判斷后,得到特殊點(diǎn)集合,即分割點(diǎn)候選集A。

那么,對于時間序列T的第i個分割片段SEGi,其狀態(tài)分類為ci,在尋找具體分割點(diǎn)ri時,約束條件為:1)ri∈[lci-3×dci,lci+3×dci];2)ri∈A。

這樣的處理方式,實(shí)際上是對掃描及對應(yīng)的損失計算過程進(jìn)行剪枝操作,從而在不影響精度的情況下降低運(yùn)算量。

4.2 增量計算優(yōu)化

在算法計算過程中,需要根據(jù)當(dāng)前分割點(diǎn)截取序列并從子序列中提取特征,而如果每次均重新計算特征,顯然會帶來大量重復(fù)的計算。筆者通過分析選定的6個特征指標(biāo)發(fā)現(xiàn),平均值、標(biāo)準(zhǔn)偏差、斜率及過零率4個指標(biāo)都可以通過預(yù)處理增量序列的方式減少冗余的計算過程。

在開始分割過程之前,計算待分割時間序列T的前綴和序列、平方前綴和序列及過零次數(shù)和序列。這樣在每次提取特征的過程中,不需要重復(fù)累加的過程,從而節(jié)省了大量的時間。同時采用文獻(xiàn)[17]的方法,將時間序列片段的擬合斜率及截距改寫為:

(5)

(6)

同理,在式(5)及式(6)中也可以使用前綴和序列進(jìn)行增量計算,從而減少計算量。限于篇幅,此處不作展開說明。

4.3 時間復(fù)雜度估算

基于SSR的算法原理及2種優(yōu)化方式,在整個分割及識別過程中,將大量的計算復(fù)雜度轉(zhuǎn)移到訓(xùn)練階段,使預(yù)測階段的復(fù)雜度大幅減小。

由于整個時間序列分割及狀態(tài)識別過程的計算復(fù)雜度受分段模式選擇的影響較大,因此本文基于分段數(shù)量及子序列長度對預(yù)測過程進(jìn)行計算復(fù)雜度的估算。

然而在實(shí)際情況中分割模式多樣,片段數(shù)量及片段長度都存在不同且差異巨大,并不能簡單地根據(jù)平均長度進(jìn)行估算,且各特征特殊點(diǎn)常有重合或近似,也并不會對所有分割點(diǎn)都進(jìn)行匹配。此處給出的復(fù)雜度僅為平均情況下的粗略估算值。

5 實(shí)驗(yàn)及結(jié)果分析

針對本文算法SSR,在真實(shí)場景的數(shù)據(jù)集上進(jìn)行多角度的實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)主要從狀態(tài)識別的準(zhǔn)確度、用戶意圖的匹配程度進(jìn)行分析,并進(jìn)一步對算法加以擴(kuò)展,驗(yàn)證其在多維數(shù)據(jù)上的效果,同時對優(yōu)化方法的效果進(jìn)行對比實(shí)驗(yàn)。

5.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)平臺基于Windows 10,64位操作系統(tǒng),Intel?Core(TM) i7-7700K處理器,4.20 GHz主頻,帶有16 GB內(nèi)存的臺式計算機(jī)。SSR算法使用Python語言實(shí)現(xiàn)。

5.2 數(shù)據(jù)集

本文實(shí)驗(yàn)在以下3個真實(shí)場景的數(shù)據(jù)集上進(jìn)行:

1)PAMAP行人運(yùn)動數(shù)據(jù)集,下文簡稱運(yùn)動數(shù)據(jù)集。PAMAP是一種有氧運(yùn)動數(shù)據(jù)監(jiān)測方案,用于記錄老年人身體的監(jiān)測數(shù)據(jù)。此數(shù)據(jù)監(jiān)測系統(tǒng)監(jiān)測受試者的全球活動,識別基本的有氧活動并估計其強(qiáng)度水平[18-19]。整個數(shù)據(jù)集包含6個被試,每個科目有40多個維度的數(shù)據(jù),主要包括4種類型的監(jiān)測傳感器數(shù)據(jù),即心率、IMU手部監(jiān)測、IMU胸部監(jiān)測和IMU足部監(jiān)測數(shù)據(jù),其中共7種運(yùn)動狀態(tài):步行非常慢,正常步行,越野行走,跑步,騎自行車,跳繩和踢足球,其中每個時間序列長度約180 000。

2)衛(wèi)星桌面聯(lián)試試驗(yàn)數(shù)據(jù)集,下文簡稱衛(wèi)星數(shù)據(jù)集。此數(shù)據(jù)集源自于真實(shí)的衛(wèi)星桌面在線試驗(yàn),記錄了衛(wèi)星運(yùn)行的指標(biāo)。實(shí)驗(yàn)主要關(guān)注電池電壓和姿態(tài)控制的變化。電池電壓序列包括3種不同的充電和放電過程,姿態(tài)控制包括2種不同的運(yùn)動狀態(tài),其中所有序列的長度均為207 908。

3)地鐵運(yùn)行工況監(jiān)測數(shù)據(jù)集,下文簡稱地鐵數(shù)據(jù)集。此數(shù)據(jù)集記錄了真實(shí)的地鐵運(yùn)行的監(jiān)測數(shù)據(jù),通過安裝在內(nèi)部托架上的傳感器監(jiān)測地鐵運(yùn)行過程。本文實(shí)驗(yàn)主要關(guān)注速度和角速度序列。此數(shù)據(jù)集包括加速、減速、勻速和轉(zhuǎn)彎4種運(yùn)行狀態(tài),其中每個時間序列數(shù)據(jù)的長度均為94 221。

真實(shí)場景的數(shù)據(jù)對應(yīng)于現(xiàn)實(shí)世界物理對象的活動。對于所有實(shí)驗(yàn),本文將數(shù)據(jù)集中約70%的數(shù)據(jù)設(shè)置為訓(xùn)練集,其余作為測試集。

5.3 序列分割與狀態(tài)識別實(shí)驗(yàn)

時間序列的分割及狀態(tài)識別是時間序列分析的經(jīng)典主題。本文實(shí)驗(yàn)中選用pHMM[6]和AutoPlait[8]作為對比算法。AutoPlait是一個無參數(shù)算法,pHMM由seg_error和rel_error 2個參數(shù)控制,實(shí)驗(yàn)中將調(diào)整pHMM的參數(shù)以獲得更好的結(jié)果。

圖1和圖2展示了衛(wèi)星數(shù)據(jù)集和地鐵數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果,每組結(jié)果的第一張圖為原始標(biāo)簽的分割及狀態(tài)展示,后三組結(jié)果分別為SSR、AutoPlait和pHMM的實(shí)驗(yàn)結(jié)果。由于pHMM運(yùn)算規(guī)模的限制,在運(yùn)動數(shù)據(jù)集上僅能使用1/4長度的序列進(jìn)行實(shí)驗(yàn)。圖1(d)中seg_error和rel_error分別為0.1和4.0,圖2(d)中則分別為0.1和0.8。

圖1 在衛(wèi)星數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果1

圖2 在地鐵數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果1

在兩組實(shí)驗(yàn)下,SSR都顯示了其優(yōu)越性。pHMM使用長度和斜率來描述序列,AutoPlait通過平均值和方差來區(qū)分序列類別。SSR采用了6種特征對序列進(jìn)行描繪,可以全面地表達(dá)狀態(tài)類別,展現(xiàn)了其在狀態(tài)類別區(qū)分的明顯優(yōu)勢。從特征選擇上,AutoPlait很難對具有穩(wěn)定均值和方差的序列進(jìn)行分割。因此,AutoPlait在這類序列中效果并不理想。pHMM展現(xiàn)了對狀態(tài)的識別優(yōu)勢。在衛(wèi)星數(shù)據(jù)集上,pHMM所得到的狀態(tài)結(jié)果區(qū)分明顯,但是難以與實(shí)際電池充放電過程相關(guān)聯(lián);而在運(yùn)動數(shù)據(jù)集上,pHMM得到分類結(jié)果非常雜亂。這兩種算法的分割和狀態(tài)識別結(jié)果均不理想。SSR在這兩組實(shí)驗(yàn)中都有著比較好的表現(xiàn),可以很明顯地區(qū)分衛(wèi)星數(shù)據(jù)的充放電過程及不同的運(yùn)動狀態(tài)。這是因?yàn)槭褂昧?個特征識別狀態(tài)類別,可以對序列進(jìn)行更精細(xì)的描繪。在SSR的分割結(jié)果中,分割點(diǎn)仍然存在一定的偏差。這樣的誤差產(chǎn)生主要是由于被試者之間的個體差異非常大,例如被試的年齡、性別、身高和體重。相對于整個序列的長度和狀態(tài)類別的多樣性,這樣的誤差是可接受的。

此外,pHMM和AutoPlait均只能獲得單一的分割模式。經(jīng)過參數(shù)調(diào)整后,pHMM的結(jié)果顯示了一定的周期性。然而,pHMM結(jié)果的周期性顯然不符合通常理解下對于周期性的要求。而SSR可以根據(jù)用戶意圖實(shí)現(xiàn)不同的分割模式。通過對比實(shí)驗(yàn)結(jié)果可知,相比pHMM和AutoPlait,SSR在時間序列狀態(tài)識別和分割中性能更好。

表1中給出了本文算法在3種數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果準(zhǔn)確度,其中狀態(tài)分類準(zhǔn)確率表示正確識別狀態(tài)的序列片段比例,最大分割點(diǎn)誤差表示在正確狀態(tài)識別的分割片段中的最大的誤差值占序列總長度的比例。所有的實(shí)驗(yàn)均得到與用戶的意圖一致的分割模式。

表1 實(shí)驗(yàn)結(jié)果準(zhǔn)確度統(tǒng)計

5.4 用戶意圖理解實(shí)驗(yàn)

獲得與用戶意圖一致的分割模式是SSR主要期望實(shí)現(xiàn)的目標(biāo),用戶意圖理解實(shí)驗(yàn)在衛(wèi)星數(shù)據(jù)集上進(jìn)行。

對于衛(wèi)星數(shù)據(jù)集,主要關(guān)注每個指標(biāo)的電壓和位置數(shù)據(jù)的狀態(tài)變化。通過圖3(a)上的標(biāo)注,可以看到3個非常明顯的狀態(tài)變化點(diǎn),圖3(b)中則顯示了一個衛(wèi)星電源電池電壓變化過程中充電和放電3個階段:充電過程,緩慢放電過程及迅速放電過程。

圖3 衛(wèi)星電源電池數(shù)據(jù)形態(tài)示意圖

實(shí)驗(yàn)針對整個過程設(shè)計了2種分割模式的訓(xùn)練集:考慮單個充放電為一個狀態(tài)類別(模式1)以及考慮一個完整充放電周期為一個狀態(tài)類別(模式2)。同樣的模式分割方法也適用于姿態(tài)控制序列。圖4和圖5分別展示了本文算法針對2種分割模式的結(jié)果。其中,圖4為電池電壓序列上的實(shí)驗(yàn)結(jié)果,圖5為姿態(tài)控制序列上的實(shí)驗(yàn)結(jié)果?？梢悦黠@看出,SSR可以根據(jù)用戶設(shè)定進(jìn)行序列的分割及狀態(tài)識別,并得到2種不同分割模式的結(jié)果,而且分割位置的結(jié)果也比較準(zhǔn)確。由此可知,SSR可以很好地理解用戶的意圖并獲得相應(yīng)的分割模式。

圖4 在衛(wèi)星數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果2

圖5 在衛(wèi)星數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果3

5.5 多維擴(kuò)展實(shí)驗(yàn)

在本文研究中,期望算法能夠具有更好的擴(kuò)展性。多維擴(kuò)展實(shí)驗(yàn)在地鐵運(yùn)行監(jiān)測數(shù)據(jù)集上進(jìn)行,實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 在地鐵數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果2

從圖6可以看出,在速度序列中,SSR算法可以區(qū)分4種運(yùn)行狀態(tài),即加速、減速、勻速與轉(zhuǎn)彎;在角速度序列中,只關(guān)心是否處于轉(zhuǎn)彎狀態(tài)?？梢钥闯?在角速度序列上,幾乎所有轉(zhuǎn)彎與非轉(zhuǎn)彎狀態(tài)都可以很好地區(qū)分。對于速度序列,在加速與減速過程中,斜率特征可以起到良好的區(qū)分作用。而針對于勻速與轉(zhuǎn)彎的狀態(tài),在角速度序列上的均值特征有著明顯的不同,從而可對不同的狀態(tài)加以區(qū)分。

5.6 優(yōu)化驗(yàn)證實(shí)驗(yàn)

優(yōu)化驗(yàn)證實(shí)驗(yàn)在運(yùn)動數(shù)據(jù)集上進(jìn)行。在優(yōu)化實(shí)驗(yàn)中,對比了基礎(chǔ)版本的算法(basic-SSR)、增加了增量計算的基礎(chǔ)算法(incre-SSR)以及添加全部優(yōu)化的最終算法(SSR)的效率。3個版本的算法在分割準(zhǔn)確度上沒有明顯的區(qū)別。運(yùn)行時間對比結(jié)果如圖7所示,可以看出,增加了優(yōu)化策略以后,在實(shí)驗(yàn)結(jié)果準(zhǔn)確度幾乎沒有改變的情況下,時間效率獲得了大幅的提高。

圖7 算法優(yōu)化前后的運(yùn)行時間比較

6 結(jié)束語

針對同一時間序列有多種可解釋分割模式的情況,本文提出一種有監(jiān)督的時間序列狀態(tài)識別方法,以期獲得與用戶意圖一致的時間序列分割結(jié)果。通過建立特征高斯概率分布模型,設(shè)定特征的權(quán)重約束,利用概率最大化的思想判斷狀態(tài)類判別,基于調(diào)整后的貪心策略的進(jìn)行序列分割,同時設(shè)計算法的效率優(yōu)化策略與多維擴(kuò)展方式。在真實(shí)場景數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文研究的有效性與可擴(kuò)展性。為進(jìn)一步提高算法的可擴(kuò)展性,后續(xù)將擴(kuò)展有關(guān)優(yōu)化策略,并基于Apache Spark[20]等分布式計算平臺實(shí)現(xiàn)本文算法及相應(yīng)的優(yōu)化剪枝策略,以應(yīng)對分布式情景下更大數(shù)據(jù)規(guī)模和更高效率要求所帶來的技術(shù)挑戰(zhàn)。