基于子段距離計(jì)算的時(shí)間序列分類方法

王子一，商 琳

(南京大學(xué) 計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，南京 210023)(南京大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，南京 210023)

1 引 言

最近以時(shí)間序列形式呈現(xiàn)的數(shù)據(jù)其分析和應(yīng)用在不同領(lǐng)域變得越來(lái)越重要.時(shí)間序列的研究在數(shù)據(jù)挖掘社區(qū)中引起了極大的興趣，時(shí)間序列數(shù)據(jù)廣泛存在于現(xiàn)實(shí)生活領(lǐng)域[2].現(xiàn)實(shí)生活中我們收集的時(shí)間序列數(shù)據(jù)之間不可能全都是完全嚴(yán)格對(duì)齊的，時(shí)間序列之間存在位移，這就導(dǎo)致了我們使用傳統(tǒng)的像KNN這類基于歐式距離計(jì)算相似度的算法在處理時(shí)間序列分類上效果不是很好.因?yàn)樾〉奈灰瓶赡軐?dǎo)致原本屬于同一類的時(shí)間序列在計(jì)算歐式距離時(shí)變得非常大.針對(duì)時(shí)間序列中大量存在這種非對(duì)準(zhǔn)的情況，有人提出了DTW(動(dòng)態(tài)時(shí)間規(guī)整)算法.DTW能夠處理大多數(shù)非對(duì)準(zhǔn)時(shí)間序列間相似性計(jì)算的問(wèn)題.時(shí)間序列數(shù)據(jù)通常在小的子序列而不是完整的串聯(lián)結(jié)構(gòu)上呈現(xiàn)階段間的差異[1].基于距離的相似性度量有時(shí)候仍然不能很好的將這兩類時(shí)間序列區(qū)分開來(lái).2009年Eamonn Keogh針對(duì)時(shí)間序列中存在的這個(gè)問(wèn)題提出了shapelet[1]，一種新的時(shí)間序列分類方法，shapelet代表了時(shí)間序列間最具有區(qū)分性的子段，現(xiàn)在shapelet已經(jīng)被廣泛的應(yīng)用于時(shí)間序列的分類問(wèn)題中，并且shapelet在時(shí)間序列分類上有很高的精度.在使用shapelet對(duì)時(shí)間序列進(jìn)行分類時(shí)shapelet的尋找是該算法中存在的最大的問(wèn)題，暴力搜索shapelet的時(shí)間復(fù)雜度太高，Eamonn Keogh針對(duì)shapelet的搜索提出了一些加速的方法，比如Subsequence Distance Early Abandon，Admissible Entropy Pruning等方法都能加快shapelet的尋找.即使這些加速方法的應(yīng)用使得尋找shapelet的時(shí)間縮短，但是尋找shapelet的時(shí)間復(fù)雜度仍然很高.2014年[2]中提出了一種全新的尋找shapelet方法，即LTS(learning time-series shapelets).LTS能夠通過(guò)訓(xùn)練集自學(xué)習(xí)出前K個(gè)最好的shapelets，在時(shí)間復(fù)雜度上要比搜索式尋找shapelet的時(shí)間復(fù)雜度低，并且精度上要比單個(gè)shapelet的分類精度高.

本文探索一種新的時(shí)間序列分類的方法，基于子段距離的計(jì)算的時(shí)間序列分類方法，通過(guò)對(duì)時(shí)間序列進(jìn)行切分然后對(duì)切分后的子段用k-shape算法進(jìn)行聚類，在聚類結(jié)果中尋找兩類時(shí)間序列各自比較有區(qū)分性的片段，并以此來(lái)作為分類的依據(jù)，該方法思路更為簡(jiǎn)單，且計(jì)算復(fù)雜度不高.在實(shí)驗(yàn)部分，通過(guò)實(shí)驗(yàn)驗(yàn)證了我們算法的分類精度和適用性，并與shaplets算法相比我們提出的算法在時(shí)間復(fù)雜度上的更具有優(yōu)勢(shì).

2 相關(guān)工作

時(shí)間序列的分類問(wèn)題在過(guò)去10多年中已經(jīng)在數(shù)據(jù)挖掘領(lǐng)域引起了極大的興趣，有大量關(guān)于時(shí)間序列分類和挖掘的文獻(xiàn)[4-6].時(shí)間序列數(shù)據(jù)大量的存在于我們的生活中，因此時(shí)間序列數(shù)據(jù)的分析十分有意義.

時(shí)間序列的分類問(wèn)題在最近10年中最具有突破性的研究是Shapelet，Shapelet作為最大程度的預(yù)測(cè)目標(biāo)變量的時(shí)間序列段，最早在[1]中被提出.時(shí)間序列所有的子段被作為shapelet的候選，從所有的子段中我們需要找到能夠最大程度區(qū)分兩類時(shí)間序列的子段，該子段就是shapelet.由于尋找shapelet需要驗(yàn)證所有的子段，因此在時(shí)間復(fù)雜度上是不可接受的.之后有一些工作是如何加速尋找shapelet的，比如2013年Eamonn J. Keogh and Thanawin Rakthanmanon在[3]中介紹如何加速尋找shapelet.但是即使使用加速的方法尋找Shapelet，時(shí)間復(fù)雜度仍是非常高.[2]中提出了一種全新的尋找shapelets的算法LTS，LTS算法可以同時(shí)找到前K個(gè)最好的shapelets，并且LTS算法不需要搜索所有的子段空間去尋找shapelets而是通過(guò)自學(xué)習(xí)方式學(xué)習(xí)出前K個(gè)最好的shapelets.Shapelets已經(jīng)被廣泛的應(yīng)用在時(shí)間序列分析領(lǐng)域，并且在時(shí)間序列分類上有很高的分類精度.

時(shí)間序列的聚類同樣是數(shù)據(jù)挖掘領(lǐng)域值得研究的問(wèn)題，傳統(tǒng)的聚類方法像K-means，已經(jīng)不能有效的實(shí)現(xiàn)時(shí)間序列的聚類，K-means算法進(jìn)行相似性度量時(shí)使用的時(shí)歐氏距離，然而時(shí)間序列之間往往存在這扭曲與位移，這使得歐氏距離不再適用于時(shí)間序列相似性度量的方法.

K-shape是2015[7]提出的一種應(yīng)用在時(shí)間序列中的聚類的方法，K-shape算法的聚類思路與K-means算法很相似，只不過(guò)K-shape算法能夠在時(shí)間序列相似性度量上考慮其形狀上的相似，并且K-shape在更新聚類中心跟K-means也存在差別，K-shape比K-means更加適合時(shí)間序列的聚類.

3 基于子段距離計(jì)算的時(shí)間序列分類方法

3.1 一些常見的定義和符號(hào)

3.1.1 時(shí)間序列數(shù)據(jù)集

時(shí)間序列數(shù)據(jù)集由I個(gè)訓(xùn)練實(shí)例組成，我們假定每個(gè)訓(xùn)練實(shí)例由Q個(gè)有序的值組成.因此我們可以將數(shù)據(jù)集定義為TI×Q，時(shí)間序列的標(biāo)簽Y∈{1，…，C}I，擁有C個(gè)類.

3.1.2 滑動(dòng)窗口子段

長(zhǎng)度為L(zhǎng)的滑動(dòng)窗口子段是一個(gè)時(shí)間序列的一個(gè)子段.具體的第i個(gè)時(shí)間序列中從j時(shí)刻開始的子段被定義為{Ti，j，…，Ti，j+L-1}，如果滑動(dòng)窗口的起始索引每次增加1，那么一個(gè)時(shí)間序列中一共由J=Q-L+1個(gè)子段.

3.1.3 子段與時(shí)間序列之間的距離

第k個(gè)子段Sk與第i個(gè)時(shí)間序列Ti之間的距離，被定義為Ti中所有與k個(gè)子段相同長(zhǎng)度子段與Sk的最小距離，具體的定義如下：

(1)

3.2 算法思路

本文提出了一種思路更為簡(jiǎn)單的時(shí)間序列分類方法.為了簡(jiǎn)單起見，我們假定分類任務(wù)為二分類.首先我們將訓(xùn)練集中的時(shí)間序列按照規(guī)定好的子段長(zhǎng)度以及步長(zhǎng)進(jìn)行等長(zhǎng)的切分，并將該子段對(duì)應(yīng)的原始標(biāo)簽加上.比如，Si是Ti的一個(gè)子段，那么Si的標(biāo)簽應(yīng)該與Ti的標(biāo)簽相同.將切分好的所有子段放在一起進(jìn)行聚類.我們知道聚類的目的在于將相似的樣本聚集在一起，這里我們將所有子段進(jìn)行聚類的目的在于，我們?cè)噲D通過(guò)聚類將相似的子段聚在一起.我們分析聚類后的結(jié)果，根據(jù)聚類結(jié)果我們發(fā)現(xiàn)某一類中標(biāo)簽label=1與label=2的子段的數(shù)量差不多，那么我們有理由認(rèn)為這些子段基本上普遍存在于兩類時(shí)間序列中.如果根據(jù)聚類結(jié)果我們發(fā)現(xiàn)某一類中l(wèi)abel=1子段數(shù)量顯著多于label=2子段數(shù)量，那么我們有理由認(rèn)為該類中的子段顯著存在label=1的時(shí)間序列中，反之亦然.根據(jù)聚類的結(jié)果，我們計(jì)算各個(gè)類中l(wèi)abel=1子段相對(duì)于該類中所有子段所占的比例，根據(jù)我們計(jì)算好的比例，我們挑選出最大與最小的值，并找到對(duì)應(yīng)的聚類.比如，我們通過(guò)聚類算法聚成了(C1，…，Ck)K個(gè)類，然后通過(guò)計(jì)算這K個(gè)類中l(wèi)abel=1子段所占的比例，發(fā)現(xiàn)Ci中l(wèi)abel=1子段所占比例最高，那么我們認(rèn)為Ci中的子段應(yīng)該是顯著的出現(xiàn)在label=1的時(shí)間序列中.如果我們發(fā)現(xiàn)Cj中l(wèi)abel=1子段所占比例最低，那么我們認(rèn)為Cj中的子段應(yīng)該是顯著的出現(xiàn)在label=2的時(shí)間序列中.當(dāng)我們找到Ci和Cj后，我們將Ci中l(wèi)abel=1所有的子段取均值得到mean1，我們認(rèn)為mean1能夠大致上表達(dá)label=1時(shí)間序列的特點(diǎn).同理，我們將Cj中l(wèi)abel=2所有的子段取均值得到mean2，我們認(rèn)為mean2能夠大致上表達(dá)label=2時(shí)間序列的特點(diǎn).得到mean1跟mean2后，對(duì)于新來(lái)的時(shí)間序列樣本，我們分別計(jì)算該樣本與mean1與mean2之間的最小距離min_dis1與min_dis2.如果min_dis1

在聚類算法的選擇中，我們考慮過(guò)k-means與k-shape兩種聚類算法，但是由于k-means在距離過(guò)程中僅考慮的是歐式距離，而忽略形狀，所以在聚類結(jié)果中有可能將形狀差異很大而在歐式距離上很接近，這是我們不希望得到的聚類結(jié)果.由于以上的原因我們使用k-shape作為時(shí)間序列子段的聚類算法.K-shape算法在[7]被提出，用來(lái)處理時(shí)間序列的聚類.因?yàn)镵-shape在聚類過(guò)程中會(huì)考慮到時(shí)間序列形狀上的相似性，所以使用k-shape聚類將會(huì)得到更理想的結(jié)果.

算法偽代碼如下：

Require：時(shí)間序列T∈RI×Q，標(biāo)簽Y(對(duì)于二分類來(lái)說(shuō)Y=a或Y=b)，子段長(zhǎng)度Seq_len，步長(zhǎng)Sep，聚類中心數(shù)K，迭代次數(shù)maxIter，驗(yàn)證集T′∈RI′×Q.

Input：T，Y，Seq_len，Sep，K，maxIter

1 對(duì)T按照Seq_len，Sep進(jìn)行切，將切分后的子段放入X中，將該子段的標(biāo)簽放入Y′中.

2 初始化矩陣M，臨時(shí)變量Tmp=10000

3 for interation = {1，…，maxIter} do

4 在X上執(zhí)行K-shape算法，聚類中心為K，得到聚類結(jié)果Cluster

5 計(jì)算K個(gè)類中，各類label=a子段的數(shù)量并計(jì)算label=a占該類總子段數(shù)的比例，放入V中

6 在V中選出最大跟最小的兩個(gè)數(shù)，并得到對(duì)應(yīng)類的索引index1，index2

7 在Cluster[index1]中計(jì)算label=a子段的均值mean1，在Cluster[index2]中計(jì)算label=2子段均值 mean2

8 根據(jù)mean1，mean2在T′中驗(yàn)證分類精度，根據(jù)輸出confusion matrix，計(jì)算FP+FN

9 if FP+FN

10 tmp = FP+FN

11 M = (mean1，mean2)

12 在M中取出mean1，mean2，在測(cè)試集中分類，得到confusion matrix

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

為了說(shuō)明本文提出算法的有效性，我們?cè)O(shè)計(jì)了相關(guān)實(shí)驗(yàn).一方面我們從分類精度上證明了我們算法的有效性，另一方面我們使用算法對(duì)存在扭曲和位移的時(shí)間序列數(shù)據(jù)進(jìn)行分類，證明了我們算法的適用性.

4.1 實(shí)驗(yàn)設(shè)置

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

UCR數(shù)據(jù)集是目前時(shí)間序列分類與聚類方面最常用的數(shù)據(jù)集.比如Gun_Point數(shù)據(jù)集中收集了兩類時(shí)間序列數(shù)據(jù)，分別表示同一場(chǎng)景中是否有槍.

我們使用UCR數(shù)據(jù)集中Gun_Point，Coffee，BeetleFly，ToSegmentation1，ShapeletSim 5個(gè)數(shù)據(jù)集來(lái)進(jìn)行實(shí)驗(yàn)，因?yàn)檫@些數(shù)據(jù)集訓(xùn)練集中的兩個(gè)類別的樣本數(shù)量是基本相同的，并且訓(xùn)練集中的樣本不是太多.這對(duì)我們的算法是非常重要的，只有訓(xùn)練集中兩類樣本的數(shù)量基本相同，聚類后的結(jié)果才有意義.訓(xùn)練集樣本不能太多是因?yàn)椋S著訓(xùn)練集樣本的增多我們切分得到子段的數(shù)量也會(huì)增多，在聚類過(guò)程中增加了聚類的不穩(wěn)定性.按照shapelet的思想，如果shapelet是出現(xiàn)在label=1的時(shí)間序列上的一個(gè)子段，那么我們認(rèn)為label=1的絕大部分時(shí)間序列中均有與shapelet相似的子段，而label=2的絕大部分時(shí)間序列上均不存在與shapelet相似的子段.基于以上這種思考我們認(rèn)為訓(xùn)練樣本并不一定要足夠多，只要能夠找出顯著出現(xiàn)在某一類時(shí)間序列中的子段即可.

4.1.2 超參數(shù)設(shè)置

我們的這種新的時(shí)間序列分類方法中所涉及到的超參數(shù)有三個(gè)，子段長(zhǎng)度seq_len，步長(zhǎng)(即滑動(dòng)窗口每次滑動(dòng)增加的索引值)sep，k-shape聚類算法中的k.

對(duì)于子段長(zhǎng)度我們參考了[2]對(duì)shapelets初始化長(zhǎng)度給定的初始值，seq_len∈{0.025，0.075，0.125，0.175，0.2}×100% Of Q.按照該經(jīng)驗(yàn)值我們?cè)O(shè)定seq_len的長(zhǎng)度.對(duì)于sep并沒(méi)有比較好的經(jīng)驗(yàn)值來(lái)參考，但是我們建議sep應(yīng)滿足

seq=seq_len-2*i，

(2)

對(duì)于k也沒(méi)有比較好的經(jīng)驗(yàn)值來(lái)參考，一般k值不宜太大，k值太大會(huì)使得聚類結(jié)果不穩(wěn)定，k值也不宜太小，k值太小會(huì)使得最后的分類結(jié)果不準(zhǔn)確.

4.1.3 Baselines

在實(shí)驗(yàn)對(duì)照階段，我們選擇三種baselines，SVM，Logistic-Regression，以及[2]提出的LTS算法.

4.2 實(shí)驗(yàn)方法

該方法中最大的不確定因素來(lái)自聚類過(guò)程的不確定性，由于聚類的樣本數(shù)量很大，而k值又不能太小，這導(dǎo)致了聚類過(guò)程存在很大的不確定性，也就是說(shuō)對(duì)于同一數(shù)據(jù)集我們?cè)谠摂?shù)據(jù)集上執(zhí)行多次的k-shape算法，最后的結(jié)果可能每次都會(huì)不太一樣，并且不可能每次聚類的結(jié)果都是好的.對(duì)于不好的聚類結(jié)果最后分類的錯(cuò)誤率自然會(huì)更高一點(diǎn)，也就是說(shuō)分類的質(zhì)量可以用聚類的質(zhì)量來(lái)衡量.對(duì)于上述這種情況，我們處理的方法是，我們將樣本切分為訓(xùn)練集，驗(yàn)證集和測(cè)試集，在訓(xùn)練集上執(zhí)行k-shape算法，在驗(yàn)證集上評(píng)價(jià)聚類的好壞.評(píng)價(jià)標(biāo)準(zhǔn)根據(jù)在驗(yàn)證集輸出的confusion matrix，confusion matrix中FN+FP越大說(shuō)明聚類結(jié)果越差，我們經(jīng)過(guò)若干次迭代，保留FN+FP最小的聚類結(jié)果，記錄mean1以及mean2依此作為分類的標(biāo)準(zhǔn).最后，我們?cè)跍y(cè)試集上驗(yàn)證我們的分類精度.

4.3 實(shí)驗(yàn)結(jié)果

表1給出了四種不同算法分別在5個(gè)不同數(shù)據(jù)集上的錯(cuò)誤率，一般的我們定義二分類的錯(cuò)誤率

(3)

表1 包含3個(gè)Baselines的在5個(gè)時(shí)間序列數(shù)據(jù)集上的錯(cuò)誤率Table 1 Error ration involving 5 time series datasets and 3 baselines

更直觀的，我們用3D-柱狀圖來(lái)展示4種算法在不同數(shù)據(jù)集上的錯(cuò)誤率，如圖1所示.

圖1 錯(cuò)誤率的3D-柱狀圖Fig.1 3D-histogram of the Error Ration

4.4 實(shí)驗(yàn)分析

從4.3中錯(cuò)誤率圖中，我們的算法在5個(gè)數(shù)據(jù)集上的表現(xiàn)不錯(cuò).其中在Gun_Point，Coffee，BeetleFly上的我們算法與SVM，Logistic-Regression算法的性能相當(dāng).在TS1，ShapeletSim兩個(gè)數(shù)據(jù)集上我們算法比SVM和Logistic-Regression效果好很多.我們畫出了5個(gè)數(shù)據(jù)集中部分時(shí)序數(shù)據(jù)的圖，如圖2-圖6所示.

如圖所示，在Gun_Point，Coffee，BeetleFly三個(gè)數(shù)據(jù)集中同一類時(shí)間序列數(shù)據(jù)上“幾乎”不存在位移或者扭曲，所以SVM和Logistic-Regression在這三個(gè)數(shù)據(jù)集上的分類效果比較理想.

圖3 Coffee訓(xùn)練集中l(wèi)abel=1的時(shí)間序列數(shù)據(jù)Fig.3 Time series data of label=1 in Coffee training set

圖4 BeetleFly訓(xùn)練集中l(wèi)abel=1的時(shí)間序列數(shù)據(jù)Fig.4 Time series data of label=1 in BeetleFly training set

如圖5-圖6所示，在TS1跟ShapeletSim兩個(gè)數(shù)據(jù)集中同一類時(shí)間序列之間存在明顯的扭曲跟位移，事實(shí)上這種位移跟扭曲在現(xiàn)實(shí)的時(shí)間序列數(shù)據(jù)中是普遍存在的.所以SVM跟Logistic-Regression這類傳統(tǒng)的分類算法在處理時(shí)間序列分類上是存在很大的不足.而我們提出的算法在這兩個(gè)數(shù)據(jù)集上的分類精度雖然沒(méi)有LTS算法的分類精度高，但是在時(shí)間復(fù)雜度上我們算法的時(shí)間復(fù)雜度要更低.在4.5中我們將分析我們算法的優(yōu)勢(shì)與不足.

圖5 TS1訓(xùn)練集中l(wèi)abel=1的時(shí)間序列數(shù)據(jù)Fig．5 Timeseriesdataoflabel=1inTS1trainingset圖6 ShapeletSim訓(xùn)練集中l(wèi)abel=1的時(shí)間序列數(shù)據(jù)Fig．6 Timeseriesdataoflabel=1inShapeletSimtrainingset

4.5 算法分析

我們算法的優(yōu)勢(shì)是相比與傳統(tǒng)的分類的算法，更加適合時(shí)間序列的分類，尤其對(duì)于存在扭曲和位移的時(shí)間序列.雖然我們沒(méi)有與DTW分類器比較，但是直接參考[2]中DTW分類器在BeetleFly跟Coffee兩個(gè)數(shù)據(jù)集上的精度是遠(yuǎn)沒(méi)我們算法的分類精度高.相比于LTS我們的分類精度沒(méi)有LTS算法的分類精度高.我們算法的優(yōu)勢(shì)在于時(shí)間復(fù)雜度上，根據(jù)[7]中k-shape算法的時(shí)間復(fù)雜度為O(max{n·k·m·log(m)，n·m2，k·m3}).所以我們算法的時(shí)間復(fù)雜度為O(max{n·k·m·log(m)，n·m2，k·m3}×maxIter)，其中k指的是聚類中心數(shù)，m指的是聚類時(shí)間序列的長(zhǎng)度，n指的是時(shí)間序列數(shù).maxIter指的是我們算法迭代執(zhí)行k-shape算法的最大次數(shù).LTS算法的時(shí)間復(fù)雜度為O(K×IQ2×maxIter)其中K指的LTS算法學(xué)得shapelets的數(shù)量，I指的是時(shí)間序列的數(shù)量，Q指的是shapelets的長(zhǎng)度，K個(gè)shapelets的長(zhǎng)度都是不同的.由于我們算法是將原時(shí)間序列切分后進(jìn)行聚類，所以m是非常小的，并且我們算法所需的迭代次數(shù)要遠(yuǎn)小于LTS算法的迭代次數(shù).在最好的情況下我們算法的時(shí)間復(fù)雜度大概會(huì)比LTS算法大概會(huì)低一個(gè)數(shù)量級(jí).同時(shí)在算法本身的復(fù)雜度上，我們的算法要簡(jiǎn)單的多.我們算法的不足在于對(duì)超參數(shù)的設(shè)置，不同的超參數(shù)對(duì)于最后分類精度有很大的影響.

5 結(jié)論以及未來(lái)的工作

在這篇文章中，我們提出一種新的時(shí)間序列分類的方法，并在5個(gè)數(shù)據(jù)集上驗(yàn)證了我們算法的可行性.雖然分類的精度沒(méi)有LTS算法的分類精度高，但在時(shí)間復(fù)雜度上要低的多，并且與其他的分類器相比我們的算法也存在優(yōu)勢(shì).同時(shí)，我們算法也有很大的改善空間，比如對(duì)超參數(shù)的設(shè)置，比如對(duì)最后分類策略的選擇，將來(lái)我們將圍繞我們算法的不足展開一些相應(yīng)的工作，并試圖探索這種算法在時(shí)間序列多分類中的可能性.