韋慶鋒，何國良

WEI Qingfeng,HE Guoliang

武漢大學(xué) 軟件工程國家重點(diǎn)實(shí)驗(yàn)室，武漢 430072

State Key Lab of Software Engineering,Wuhan University,Wuhan 430072,China

1 引言

時(shí)間序列shapelets是時(shí)間序列中能夠最大限度地表示一個(gè)類別的子序列，是時(shí)間序列局部特征的表示，由Ye等人[1]所提出。shapelets算法采用時(shí)間序列局部片段進(jìn)行分類，很大程度上避免了噪聲的影響，更加精確和健壯，同時(shí)，shapelets分類可以產(chǎn)生具有較高說明性的結(jié)果，能夠很明確地顯示出類別之間的差異之處，指明為什么一個(gè)特定的對(duì)象被分配到一個(gè)特定的類中，幫助研究人員更好地理解數(shù)據(jù)。shapelets已經(jīng)作為時(shí)間序列領(lǐng)域一個(gè)重要的研究主題，受到了越來越多的關(guān)注[2-5]，還被應(yīng)用到了醫(yī)療服務(wù)[6]、運(yùn)動(dòng)檢測[7]、電力需求分析[8]、聚類研究[9]等領(lǐng)域。

最早提出的基于shapelets分類是在查找出shapelets基礎(chǔ)上通過構(gòu)建決策樹的方法來完成的，因此查找出shapelets的好壞決定了分類的效果。原始查找shapelets的方法要產(chǎn)生所有可能的候選集，然后依次計(jì)算它們的信息增益，找出最大的一個(gè)。它的時(shí)間復(fù)雜度為O(N2m4)，N為數(shù)據(jù)集中時(shí)間序列的個(gè)數(shù)，m為時(shí)間序列的長度，由此可見計(jì)算shapelets所需的時(shí)間是非常大的，這成為它被廣泛應(yīng)用的最大障礙。尤其是隨著科技的進(jìn)步，越來越多的領(lǐng)域都需要對(duì)以往產(chǎn)生的大量時(shí)間數(shù)據(jù)進(jìn)行分析挖掘，有些數(shù)據(jù)不僅僅是單變量的，更多是多個(gè)變量相互作用、共同發(fā)展，如股票數(shù)據(jù)、氣象數(shù)據(jù)、多傳感器產(chǎn)生的運(yùn)動(dòng)數(shù)據(jù)等。已有的查找shapelets方法由于時(shí)間復(fù)雜度太高，已經(jīng)不能適應(yīng)當(dāng)今數(shù)據(jù)挖掘的需求，迫切需要一種既能保持shapelets特性，又能縮短計(jì)算時(shí)間的方法。

本文提出了一種新的查找shapelets的方法（NSDS）：基于shapelets非相似的特性，根據(jù)子序列間距離分布設(shè)置一個(gè)距離閾值，從而過濾掉候選集中大部分相似子序列。再改變原始方法中計(jì)算耗時(shí)的信息增益為更加快捷的類可分離性計(jì)算，作為評(píng)價(jià)候選子序列的指標(biāo)，最后得到得分靠前的多個(gè)子序列作為最終選擇出的shapelets。通過實(shí)驗(yàn)表明，該方法在單變量時(shí)間序列數(shù)據(jù)集上查找出的shapelets的分類精度與已有方法相比有所提高，時(shí)間也得到了極大的縮減。NSDS方法擴(kuò)展到多變量時(shí)間序列數(shù)據(jù)集后依然取得了不錯(cuò)的效果。

2 相關(guān)研究

自從shapelets方法提出，針對(duì)shapelets分類的加速提取研究是大多數(shù)研究者所關(guān)注的領(lǐng)域，下面主要介紹國內(nèi)外學(xué)者的相關(guān)研究。

文獻(xiàn)[1]中采用了提前停止距離計(jì)算和熵剪枝的加速方法，這兩種方法雖然簡單但是很高效，尤其是第一種方法，因?yàn)樵疾檎襰hapelets框架中共產(chǎn)生Nm2個(gè)候選子序列，每個(gè)候選子序列都需要計(jì)算與所有時(shí)間序列間的距離。若能減少距離的計(jì)算時(shí)間則可以大大提高整體算法的運(yùn)行速度。

文獻(xiàn)[2]中使用了符號(hào)聚合近似（Symbolic Aggregate Approximation，SAX）對(duì)原始時(shí)間序列進(jìn)行維度約減，將原始數(shù)據(jù)離散化表示為字符串。在此基礎(chǔ)上隨機(jī)遮蓋部分字符串統(tǒng)計(jì)剩下部分的相似性，結(jié)合類別號(hào)對(duì)區(qū)別能力進(jìn)行打分，經(jīng)過多次遮蓋后選取得分靠前的候選者，再進(jìn)行后續(xù)的信息增益計(jì)算得到分類性能最好的子序列。

文獻(xiàn)[3]中利用了三角不等性[10]加速了子序列和時(shí)間序列間距離計(jì)算過程，主要是利用了以下數(shù)學(xué)原理：兩邊之差小于第三邊。具體來說先設(shè)置一個(gè)基準(zhǔn)子序列O，然后計(jì)算兩個(gè)子序列A、B到O的距離之差作為距離下界dlb，A、B之間的實(shí)際距離一定是大于等于dlb的，當(dāng)dlb大于已有的最小實(shí)際距離時(shí)，就可以放心地對(duì)A、B進(jìn)行剪枝，這樣就減少了距離計(jì)算的次數(shù)。又采用了文獻(xiàn)[11]中證明的不同長度序列下界之間的關(guān)系，在只計(jì)算一次實(shí)際下界的情況下推導(dǎo)出更長子序列的下界，從而減少了下界的計(jì)算開銷。最后，再使用一個(gè)近似函數(shù)在遍歷子序列長度時(shí)不是每次往上加1長度，而是跳躍性地遞增。

文獻(xiàn)[4]提出了通過計(jì)算原始時(shí)間序列間的距離來對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換，然后使用現(xiàn)有的分類方法（如SVM）查找shapelets；文獻(xiàn)[5]中使用了特征向量和融合正則化套索相結(jié)合的數(shù)學(xué)方法來尋找shapelets位置；此外，還有使用查找關(guān)鍵點(diǎn)[12]、非頻繁子序列[13]等技術(shù)剪枝shapelets候選集合的方法。

以上的大多數(shù)方法還是基于原始方法中查找shapelets框架的改進(jìn)，在大量的候選子序列中去尋找能最好地表示一個(gè)類別特征的shapelet，雖然創(chuàng)新了許多距離計(jì)算方式、剪枝、距離下界等技術(shù)，但是運(yùn)行效率不穩(wěn)定，受數(shù)據(jù)集自身數(shù)據(jù)分布影響較大，在有些較大數(shù)據(jù)集上時(shí)間消耗還是難以接受。

3 基礎(chǔ)知識(shí)與符號(hào)

下面介紹一些本文中的基礎(chǔ)知識(shí)和符號(hào)：

定義1時(shí)間序列T和子時(shí)間序列s。

一個(gè)按時(shí)間順序排列的觀測值稱為一條時(shí)間序列T={t1,t2,…,tm}，每一個(gè)值ti表示該時(shí)刻下的記錄數(shù)值，m表示時(shí)間序列的長度。

時(shí)間序列T中一個(gè)連續(xù)片段稱為子時(shí)間序列i表示子序列的起始位置，l為子序列的長度。

定義2數(shù)據(jù)集D。

多個(gè)時(shí)間序列及其對(duì)應(yīng)的類標(biāo)號(hào)組成了一個(gè)數(shù)據(jù)集D=＜T1,c1＞,＜T2,c2＞,…,＜TN,cN＞，N表示數(shù)據(jù)集中的時(shí)間序列的數(shù)目。

定義3子序列距離。

兩條相同長度的子序列s、s′，經(jīng)過Z標(biāo)準(zhǔn)化后使用歐氏距離計(jì)算它們之間的相似性，表示為：

定義4子序列和時(shí)間序列距離。

子序列和時(shí)間序列的長度不等，因此通過在長時(shí)間序列上依次滑動(dòng)短序列找出最小距離作為兩者之間的距離，表示為：

定義5相似性距離閾值。

通過對(duì)原始查找shapelets方法的研究發(fā)現(xiàn)：同類別時(shí)間序列中存在大量相似的子序列，不同類別中依然存在許多相似的子序列[14]，這是因?yàn)椴煌悇e序列間的差異主要是來自那些局部具有特殊形態(tài)的序列片段，而非整體都是不同的。這些特殊片段往往范圍不是很大，卻有著能夠區(qū)分其他類別的特別形態(tài)，而余下的其他片段卻沒有關(guān)鍵信息，彼此之間差異很小。根據(jù)shapelets的特性（它對(duì)表征特定類樣本時(shí)距離很小，相反對(duì)其他類別時(shí)的距離較大），那些到任意類別距離都小的子序列是不可能成為shapelets的?；谝陨戏治鍪褂米有蛄虚g距離表征相似性，設(shè)置一個(gè)距離閾值ε，當(dāng)子序列之間的距離小于該閾值時(shí)，則認(rèn)為它們之間是相似的，反之則是非相似的。通過這個(gè)閾值過濾掉候選集合中的相似子序列，省去后續(xù)無用的距離計(jì)算。ε的設(shè)置方法是對(duì)數(shù)據(jù)集中所有子序列間距離從小到大排序，統(tǒng)計(jì)其整體分布情況，確定某一累計(jì)總體距離比例p（事先設(shè)置參數(shù)）下對(duì)應(yīng)的距離。

下面通過一個(gè)具體的實(shí)例來講解ε的設(shè)置方法：任意選擇3個(gè)單變量時(shí)間序列數(shù)據(jù)集（Fish，50words，InlineSkate），計(jì)算每個(gè)數(shù)據(jù)集中子序列間的距離，按從小到大的順序排列后統(tǒng)計(jì)在不同距離區(qū)間下的分布比例，所得到的數(shù)據(jù)使用Excel繪圖，結(jié)果如圖1所示，可見大多數(shù)分布都是傾向于距離較小一側(cè)的。以Inline-Skate為例，選擇數(shù)據(jù)集中累計(jì)占比p=0.25所對(duì)應(yīng)的距離（該例中為1.7）設(shè)置為距離閾值，也就是說針對(duì)InlineSkate數(shù)據(jù)集子序列間距離小于1.7時(shí)認(rèn)為它們是相似的。p值越小，過濾越多，候選子序列也就越少。通過第5章的實(shí)驗(yàn)結(jié)果可以看到通過此方法可以過濾掉大部分的候選子序列，而只選擇少量的（約為0.1%）子序列進(jìn)行距離計(jì)算。p值的設(shè)置需要視不同數(shù)據(jù)集的情況區(qū)別分析，沒有一個(gè)統(tǒng)一的數(shù)值，經(jīng)過反復(fù)試驗(yàn)本文中將其設(shè)置為{0.15，0.25，0.35}三者中的一個(gè)。

圖1 子序列距離分布

定義6基于離散矩陣的類可分離性。

假設(shè)有一組樣本(x,y)∈(Rd×Y)，其中Rd為d維特征空間，Y={1,2,…,c}為類標(biāo)集合。樣本總數(shù)為N，ni表示第i類中的樣本個(gè)數(shù)，xi,j表示第i類中第j個(gè)樣本，u為所有類別的樣本均值，ui為第i類對(duì)應(yīng)所有樣本的均值。則類間離散度矩陣Sb和類內(nèi)離散度矩陣Sw定義為：

基于離散矩陣的類可分離性為兩者的跡或者行列式的比值，即J=Sb/Sw，J值越大，表示類可分離性越好[15]。

對(duì)于一個(gè)候選子序列candidate，計(jì)算它與所有時(shí)間序列的距離，直觀表示如圖2所示，其中紅色矩形代表的是candidate和類別1樣本的距離，綠色三角形代表的是和類別2樣本的距離。按距離大小映射到一維坐標(biāo)后，按照類內(nèi)類間離散度矩陣的定義進(jìn)行計(jì)算，就可以通過類可分離性來評(píng)價(jià)該候選子序列分類性能，得分越高表明該子序列分類性能越好。

圖2 基于離散矩陣的類可分離性

4 非相似shapelets快速查找

4.1 算法綜述

在第3章理論與技術(shù)基礎(chǔ)之上，給出了步驟嚴(yán)密的算法。整體思路是首先通過距離閾值過濾掉相似的子序列，再使用類可分離性對(duì)過濾后的子序列進(jìn)行評(píng)價(jià)，從中選擇得分靠前的部分為shapelets，最后使用選擇出的多個(gè)shapelets對(duì)測試序列進(jìn)行分類。

4.1.1 計(jì)算距離閾值

算法1computerThreshold

輸入：訓(xùn)練集Tr（樣本數(shù)N，長度m，類標(biāo)集合C={1,2,…,c}），累計(jì)比例p，shapelets長度集合Φ∈RL。

輸出：距離閾值ε。

1.Y←?;

2.for 1,2,…,Nm

3.i←rand(N);Φl=rand(ΦL);j=rand(m-Φl+1);

4.i′←rand(N);j′=rand(m-Φl+1);//隨機(jī)選擇子序列起始位置和長度

5. select random candidate:s←Ti,j:j+Φl-1;

6. select random candidate:s′←Ti′,j′:j′+Φl-1;

7.Y.add(dist(s,s′));//計(jì)算子序列間距離加入到Y(jié)集合

8.sort(Y);

9.ε=Y[p];

距離閾值ε的計(jì)算是該算法的基礎(chǔ)，它決定著過濾性能的好壞，按照定義5中介紹的原理與方法，具體計(jì)算過程如算法1所示。先初始化一個(gè)集合Y用來存放子序列間的距離，設(shè)置一共需要計(jì)算的子序列組數(shù)為Nm，任意選取兩條長度相同位置不同的子序列（步驟2～6），按照定義3計(jì)算子序列之間的距離，將得到的距離存放于Y中（步驟7）。此處在選擇子序列對(duì)時(shí)，不是將全部可能位置可能長度的子序列全部計(jì)算一遍，而是使用了固定數(shù)量下隨機(jī)選取的方法，這樣做的好處是保證了與總體分布誤差很小的情況下大大減少了比較的次數(shù)，降低了整體計(jì)算的時(shí)間復(fù)雜度。等到所有的子序列間距離計(jì)算完后對(duì)Y進(jìn)行排序（步驟8），得到事先設(shè)置好的參數(shù)——累計(jì)比例p下對(duì)應(yīng)的距離（步驟9）。

4.1.2 查找shapelets

算法2DiscoveryShapelets

輸入：數(shù)據(jù)集Tr（樣本數(shù)N，長度m，類標(biāo)集合C={1,2,…,c}），累計(jì)比例p，PAA壓縮比例r，shapelets長度集合Φ∈RL，shapelets個(gè)數(shù)k。

輸出：kShapelets,kDistance。

1.R=?;B=?;disToShapelets=?;

2.ε←computerThreshold(Tr,p,Φ);//計(jì)算距離閾值

3.for 1,2,…,NmL

4.i←rand(N);Φl=rand(Φl);j=rand(m-Φl+1);

5. select random candidate:s←Ti,j:j+Φl-1;

6. if!similarWith(s,B)//候選子序列和已選子序列是否相似

7.Dis←dist(s,Tr);

8.score(s)=ClassSeparability(Dis,C);//計(jì)算類可分離性

9.disToShapelets.add(Dis);B.add(s);

10. elseR.add(s);

11.sort(score);

12.kShapelets←selectK(B);

13.kDistance=selectK(disToShapelets);

查找shapelets過程如算法2所示：給定一個(gè)時(shí)間序列訓(xùn)練集Tr，先對(duì)其中的時(shí)間序列進(jìn)行Z標(biāo)準(zhǔn)化，使得處理后的數(shù)據(jù)滿足標(biāo)準(zhǔn)正態(tài)分布。然后有選擇地根據(jù)數(shù)據(jù)集大小進(jìn)行PAA（Piecewise Aggregate Approximation）處理來降低時(shí)間維度。對(duì)原始數(shù)據(jù)預(yù)處理結(jié)束后，初始化備用集B、拒絕集R和子序列到時(shí)間序列距離集disToShapelets為空（步驟1），集合B中存放的是非相似子序列，R中存放的是與B中相似的子序列。然后計(jì)算距離閾值ε（算法2）。在選取候選子序列s時(shí)，并沒有按照原始方法中的滑動(dòng)窗口遍歷每一種子序列，然后再增加窗口寬度重復(fù)滑動(dòng)的方法，而是采取了隨機(jī)選擇起始位置，隨機(jī)選擇子序列長度的方法。為了不失一般性，將最外層的循環(huán)次數(shù)設(shè)置為NmL（步驟3），產(chǎn)生的隨機(jī)數(shù)滿足均勻分布，這樣做和原始方法中候選集的數(shù)目差不多。隨機(jī)選取一條候選子序列（步驟4、5），計(jì)算它與備用集B中子序列間的距離（步驟6），若大于閾值ε，就將它加入到B中，否則加入到拒絕集R中。對(duì)加入到備用集B中的子序列，計(jì)算它與訓(xùn)練集中所有時(shí)間序列的距離dist(s,Tr)，再通過類可分離性（定義6）對(duì)dist(s,Tr)計(jì)算評(píng)價(jià)得分score，并將dist(s,Tr)加入到距離集合disToShapelets中（步驟7～10）。待全部候選子序列計(jì)算完成后將B內(nèi)子序列按照得分非遞增的順序排序（步驟11），最后選擇得分靠前的k個(gè)子序列作為kShapelets及其對(duì)應(yīng)的kDistance（步驟12、13）。

4.1.3 對(duì)測試序列分類

算法3oneNN(Te,kShapelets,kDistance)

輸入：測試集Te（樣本數(shù)N，長度m，類標(biāo)集合C={1,2,…,c}），選擇出的k個(gè)shapelets及其對(duì)應(yīng)的訓(xùn)練集的距離kDistance。

輸出：分類準(zhǔn)確率Accuracy。

1.correctNum=0;

2.fori=1:N;j=1:k

3.testToShapelets=dist(kShapeletsj,Tei);

4.testToTrain=testToShapelets-kDistance;//經(jīng)處理轉(zhuǎn)換后測試樣本和訓(xùn)練樣本間距離

5.classVal=argmin(testToTrain);//將最近鄰測試樣本的類標(biāo)號(hào)作為分類結(jié)果

6. ifclassVal==testClassi

7.correctNum++;

8.Accuracy=correctNum/N;

查找出shapelets的根本目的是為了對(duì)測試序列進(jìn)行分類，原始方法中使用的是決策樹的分類方法。這樣做的不足之處是：

（1）決策樹中每個(gè)節(jié)點(diǎn)是唯一shapelet，若此shapelet性能不好，將導(dǎo)致分類的徹底失敗；

（2）對(duì)于多分類問題就要選擇多個(gè)shapelets，而原始方法中就只能通過多次查找來解決，這樣做非常耗時(shí)，而且有選擇相似shapelets的風(fēng)險(xiǎn)。

為了解決這些問題，將由算法2得到的kDistance看成是k個(gè)特征屬性組成的向量，每個(gè)特征為一個(gè)shapelet到所有訓(xùn)練序列的距離。對(duì)測試序列和k個(gè)shapelets進(jìn)行距離計(jì)算后，也將得到包含k個(gè)屬性的特征向量。再使用1-NN分類方法尋找每個(gè)測試序列的最近鄰訓(xùn)練樣本，以此來確定測試序列的類別，具體過程如算法3所示。對(duì)于訓(xùn)練集Te中每個(gè)樣本，計(jì)算它與kShapelets的距離，得到一個(gè)長度為k的距離向量testToShapelets（步驟3），然后與訓(xùn)練集kDistance中尋找距離最近的樣本對(duì)應(yīng)的類標(biāo)號(hào)作為該測試樣本的類別（步驟4、5），若與真實(shí)類別相同則correctNum累加1（步驟6、7）。最后返回整體的準(zhǔn)確率。

4.2 參數(shù)分析

4.2.1 PAA的壓縮比例設(shè)置

算法2中提到算法開始前有選擇地對(duì)原始數(shù)據(jù)進(jìn)行PAA降維處理，若使用PAA的壓縮比例r={1/2,1/4,…}，r值越小則降維幅度越大；但是降維后的數(shù)據(jù)會(huì)忽略掉一些原始特征，有可能影響后續(xù)的分類效果，因此r值也不能設(shè)置得過小。在圖3中根據(jù)此問題測試了3個(gè)數(shù)據(jù)集，分析它們在使用不同的PAA壓縮比例r后的分類效果。隨著r的減小，分類準(zhǔn)確率會(huì)有所降低，時(shí)間消耗降低較為明顯。因此只要r值設(shè)置得合理，可以減少計(jì)算時(shí)間，分類精度也沒有太大的影響。

圖3 PAA不同壓縮比例下的分類對(duì)比

4.2.2 子序列長度的設(shè)置

在搜索不同長度的候選子序列時(shí)，原始方法中采用的是窗口逐步加1的方式，這樣做雖然可以把每種可能性都考慮到，但是低效。因?yàn)閟hapelet的核心思想是找出那些代表特征的時(shí)間片段，只要是包含了這些關(guān)鍵特征，無論是長序列還是短序列對(duì)分類是沒有太大差別的，所以原始方法中一個(gè)很突出的問題就是最終選擇出的shapelets之間有很大的重合，而這些重復(fù)計(jì)算占用了大量的時(shí)間，最終導(dǎo)致效率低下。為了解決這一問題，在設(shè)計(jì)shapelet長度集合Φ時(shí)把候選長度設(shè)置為若干個(gè)固定值。為了證明此方法的有效性，假設(shè)選取子序列的長度為0.2～0.6 m，將此長度區(qū)間平分為n(n=3,4,…,15)份，也就是子序列長度有n種可能，統(tǒng)計(jì)查找出的shapelets分類情況，結(jié)果如圖4所示。由結(jié)果可得，子序列長度可選范圍的大小對(duì)分類精度影響不大，但是長度數(shù)量越多，花費(fèi)的時(shí)間也就越多。在本文的實(shí)驗(yàn)中，統(tǒng)一設(shè)置子序列長度為Φ={0.2 m,0.4 m,0.6 m}。

圖4 不同子序列長度下的分類比較

4.2.3 shapelets數(shù)量的設(shè)置

算法2步驟12和13中選擇得分靠前的前k個(gè)子序列，k值大小對(duì)后續(xù)分類準(zhǔn)確率和時(shí)間影響較大，這是一個(gè)對(duì)算法性能有重要影響的參數(shù)。因此做了以下實(shí)驗(yàn)：令k值由小變大，分析它對(duì)分類精度的影響，結(jié)果如圖5所示。因?yàn)閟hapelets數(shù)目只會(huì)影響到測試集分類時(shí)間和結(jié)果，對(duì)訓(xùn)練集尋找shapelets的時(shí)間沒有影響，所以只給出了分類準(zhǔn)確率的結(jié)果。雖然沒有分類時(shí)間的比較，但是顯然知道：分類時(shí)間和shapelets數(shù)目成正比關(guān)系。由結(jié)果可得：選取較少的shapelets時(shí)，會(huì)降低分類準(zhǔn)確率，隨著數(shù)目的增加，準(zhǔn)確率有所上升，到一臨界值時(shí)數(shù)目再增加，準(zhǔn)確率也不會(huì)發(fā)生變化。不同的數(shù)據(jù)集臨界值不同，在后面的實(shí)驗(yàn)中將k統(tǒng)一設(shè)置為備用集B中子序列總量的50%。

圖5 選擇不同shapelets數(shù)目對(duì)分類的影響

4.3 時(shí)間復(fù)雜度分析

對(duì)于樣本數(shù)為N、時(shí)間長度為m的數(shù)據(jù)集，原始算法中shapelet候選集的大小為Nm2，查找最好的shapelet時(shí)間復(fù)雜度為O(N2m4)。若使用PAA進(jìn)行時(shí)間維度的降維，其壓縮比例r={1/2,1/4,…}，那么降維后的時(shí)間復(fù)雜度為O(r4N2m4)。通過設(shè)置一個(gè)距離閾值可以對(duì)候選子序列進(jìn)行過濾，假設(shè)過濾的比例為其中為備用集合中子序列的數(shù)量，為拒絕集中子序列的數(shù)量。因此，若PAA和過濾子序列的方法同時(shí)被使用，候選集的大小為fNr2m2，最終查找多個(gè)shapelets的時(shí)間復(fù)雜度為O(fNr2m2×Nr2m2)=O(fN2r4m4)。本算法還需要額外計(jì)算兩部分：計(jì)算距離閾值和比較候選子序列與已選子序列間的相似性，前者的計(jì)算復(fù)雜度為O(Nrm×rm)=O(Nr2m2)；后者的復(fù)雜度為O((1-，其中為子序列長度可能取值的數(shù)目，根據(jù)4.2節(jié)中的分析，由于的數(shù)量級(jí)為1～2，因此額外需要計(jì)算部分的復(fù)雜度為O(2Nr2m2)，相比于過濾后的子序列中查找shapelets的時(shí)間復(fù)雜度O(fN2r4m4)相差1～2個(gè)數(shù)量級(jí)，所以最終的時(shí)間消耗為O(fN2r4m4)。本方法和原始方法計(jì)算時(shí)間比值是fr4，第5章的實(shí)驗(yàn)結(jié)果同樣驗(yàn)證了此分析的結(jié)論，由此可見NSDS方法可以大大縮短計(jì)算時(shí)間。

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

5.1UCR數(shù)據(jù)集

為了評(píng)價(jià)本文新提出的非相似shapelets快速查找方法（NSDS）的有效性，選用了UCR作為單變量時(shí)間序列數(shù)據(jù)集[16]，它們中大多數(shù)已被用到時(shí)間序列的仿真實(shí)驗(yàn)中，每個(gè)數(shù)據(jù)集的具體信息描述如表1所示，采用原數(shù)據(jù)集中默認(rèn)的訓(xùn)練集和測試集。分類器采用1-NN，使用歐氏距離計(jì)算樣本之間的相似性。實(shí)驗(yàn)環(huán)境為Core i7四核CPU，主頻3.60 GHz，內(nèi)存8 GB，Windows 8系統(tǒng)，使用Java編程語言。對(duì)比算法選用文獻(xiàn)[2]中提出的FS算法。

5.2 單變量時(shí)間序列分類性能

將NSDS方法和FS方法在每個(gè)數(shù)據(jù)集上分別計(jì)算10次，取其平均值作為最終的實(shí)驗(yàn)結(jié)果，如表2。其中第3～5列的r、p、k分別對(duì)應(yīng)算法2中的3個(gè)輸入?yún)?shù)：PAA壓縮比例、距離累積比例、最終選擇shapelets集中的數(shù)目。通過設(shè)置不同的參數(shù)，經(jīng)過多次實(shí)驗(yàn)，取最好分類結(jié)果時(shí)對(duì)應(yīng)的參數(shù)值。第6列的數(shù)值表示的是最終選擇出的shapelets子序列數(shù)目占所有候選子序列的比值，當(dāng)該比值小于0.001時(shí)只進(jìn)行標(biāo)記，未給出精確數(shù)值。最后4列代表著兩種方法各自的分類準(zhǔn)確率和查找shapelets時(shí)間，為了明顯起見，將分類準(zhǔn)確率高和運(yùn)行速度快的數(shù)值加粗表示。

由表2結(jié)果可得：NSDS方法在分類準(zhǔn)確性上要優(yōu)于FS方法，在所有的45個(gè)數(shù)據(jù)集中有33個(gè)數(shù)據(jù)集使用NSDS方法分類準(zhǔn)確性更高，最大地提升為Cricket_Z數(shù)據(jù)集的0.285，最小的為ECGFive數(shù)據(jù)集上的0.003，平均為0.101。相對(duì)地在另外12個(gè)數(shù)據(jù)集中，F(xiàn)S方法分類準(zhǔn)確性優(yōu)于NSDS方法的幅度都較小，最大的也只有0.046，最小的為0.003，平均為0.022。

表1 UCR時(shí)間序列數(shù)據(jù)集

表2 UCR數(shù)據(jù)集分類準(zhǔn)確率和時(shí)間對(duì)比

圖6為兩種方法分類準(zhǔn)確率比較的直觀顯示，圖中左上部分的區(qū)域代表FS算法查找出的shapelets分類準(zhǔn)確率較好，相反的右下部分代表NSDS方法較好，且距離對(duì)角線越遠(yuǎn)的區(qū)域代表兩者之間差別越大。從圖6中可以明顯看到大約3/4數(shù)據(jù)集的結(jié)果都落在了NSDS區(qū)域，且整體偏離對(duì)角線的幅度大于落在FS區(qū)域里的數(shù)據(jù)集，這和之前的定量分析相一致。

圖6 NSDS方法與FS方法分類準(zhǔn)確率比較

在查找shapelets時(shí)間方面，NSDS方法一致優(yōu)于FS方法，并且優(yōu)勢非常明顯，平均都要快3～4個(gè)數(shù)量級(jí)，與4.3節(jié)中時(shí)間復(fù)雜度分析的fr4相一致。最大的速度提高是InlineSkate數(shù)據(jù)集，提高了119354倍。在每個(gè)數(shù)據(jù)集上的查找時(shí)間都控制在幾秒以內(nèi)，這無疑對(duì)后續(xù)的數(shù)據(jù)挖掘或者是計(jì)算能力不是很強(qiáng)的設(shè)備提供了可能性。NSDS的計(jì)算時(shí)間之所以能夠如此之短，除了PAA降維的作用之外，更主要是因?yàn)槭褂昧司嚯x閾值過濾候選子序列的方法，從表2中可以看出最終選擇出的shapelets子序列數(shù)目占所有候選子序列的比值都非常小，大多數(shù)都在10-3級(jí)別，最大的也僅有0.07。剩下的少數(shù)子序列計(jì)算它們與時(shí)間序列的距離也就變得非常容易，這種先過濾后計(jì)算方式可以最大程度地減少時(shí)間復(fù)雜度，優(yōu)于先計(jì)算后過濾的方式[17]。

5.3 shapelets可解釋性

知道使用shapelet進(jìn)行分類的一個(gè)很大優(yōu)勢是它具有良好的可解釋性，能夠很明確地顯示出類別之間的差異之處，指明為什么一個(gè)特定的對(duì)象被分配到一個(gè)特定的類中，幫助研究人員更好地理解數(shù)據(jù)。在本文方法中是選擇出最好的k個(gè)shapelets，通過類可分離性評(píng)價(jià)好壞，那么這k個(gè)shapelets是否依然保持了良好的可解釋性呢，為此將所選擇出的shapelets結(jié)果繪制出來，結(jié)果如圖7所示。

由圖7可得，圖（a）中為Trace數(shù)據(jù)集中不同類別的樣本直觀表示，可見每種類別都有自己獨(dú)一無二的特性，如類別1中在時(shí)間點(diǎn)50附近有一個(gè)短暫的高峰，類別2和類別1的區(qū)別就是沒有這種高峰，顯然這個(gè)短暫的高峰就是一個(gè)shapelet。圖（b）中為通過NSDS算法得到的shapelets中部分子序列，很明顯shapelet1包含了之前人為分析應(yīng)該為shapelet的片段，同樣另外2個(gè)也包含了其他類別顯著的特征。該結(jié)果同時(shí)也說明了shapelet只需要包含這些關(guān)鍵特征，長序列和短序列是沒有太大差別的。

5.4 多變量時(shí)間序列數(shù)據(jù)分類性能

圖7 Trace數(shù)據(jù)集中NSDS方法選擇出的shapelets

目前使用較多的多變量時(shí)間序列分類方法是基于實(shí)例的，也就是說選擇合適的相似性度量方法計(jì)算實(shí)例之間的距離，再按距離大小進(jìn)行分類。例如，基于動(dòng)態(tài)時(shí)間彎曲（DTW）和K-NN的多變量時(shí)間序列分類方法使用非常廣泛，但是在某些數(shù)據(jù)集上表現(xiàn)得并不是很理想[18]；或者是使用特征表示方法，對(duì)原始數(shù)據(jù)進(jìn)行特征提取，再進(jìn)行分類[19]；還有的學(xué)者將多種處理手段融合，比如Banko和Abonyi[20]將基于PCA的特征提取方法與DTW相似性度量方法相結(jié)合，轉(zhuǎn)換后的數(shù)據(jù)保留了變量間的相互關(guān)系；Prieto等人[21]提出了分層分類的策略，先使用多分類器對(duì)每個(gè)變量進(jìn)行學(xué)習(xí)，融合底層分類結(jié)果后再使用高層學(xué)習(xí)器確定最終類別。

以上這些方法有的計(jì)算復(fù)雜度很高，有的在處理過程中丟失了原始數(shù)據(jù)的物理特性，有的經(jīng)過復(fù)雜計(jì)算后對(duì)分類性能提升并不高。結(jié)合本章對(duì)子序列shapelet的學(xué)習(xí)，使用基于多個(gè)shapelets的組合分類器方法來對(duì)多變量時(shí)間序列分類。具體來說就是對(duì)每個(gè)變量使用NSDS方法尋找多個(gè)shapelets，然后使用1-NN方法分類，這樣就構(gòu)建出d個(gè)分類器（d為變量數(shù)），采用投票的方式融合多分類器的結(jié)果作為最終分類類別。

人體活動(dòng)識(shí)別是指在測試者身上放置多個(gè)運(yùn)動(dòng)感應(yīng)器來記錄活動(dòng)數(shù)據(jù)，并對(duì)這些數(shù)據(jù)進(jìn)行挖掘來獲得運(yùn)動(dòng)模式的過程，該研究鄰域近幾年隨著運(yùn)動(dòng)記錄設(shè)備的普及化而得到了越來越多的關(guān)注[22-24]。這些活動(dòng)數(shù)據(jù)從本質(zhì)上來說就是多變量時(shí)間序列，每個(gè)變量代表著一個(gè)感應(yīng)器獲得的時(shí)序數(shù)據(jù)。因此實(shí)驗(yàn)中選用文獻(xiàn)[22]中介紹的Daily and Sports Activities Data Set作為實(shí)驗(yàn)數(shù)據(jù)。

表3 NSDS方法在運(yùn)動(dòng)數(shù)據(jù)集上分類結(jié)果

表4 不同感應(yīng)設(shè)備下的混淆矩陣

Daily and Sports Activities Data Set是由Bilkent University從8個(gè)實(shí)驗(yàn)者采集而得：在每個(gè)實(shí)驗(yàn)者身上的5個(gè)不同部位放置5個(gè)感應(yīng)設(shè)備采集19種動(dòng)作的運(yùn)動(dòng)時(shí)間序列。每個(gè)設(shè)備包含多個(gè)加速度計(jì)、陀螺儀、磁強(qiáng)計(jì)感應(yīng)器，最終得到數(shù)據(jù)集包含9120個(gè)樣本，每個(gè)樣本變量維數(shù)45，時(shí)間維數(shù)125。本實(shí)驗(yàn)選擇其中5類常用的動(dòng)作（站立、行走、上樓、跳躍、打籃球），也就是共2400個(gè)樣本。隨機(jī)選擇其中2/3作為訓(xùn)練集，1/3作為測試集，PAA壓縮比例r設(shè)置為0.5，距離累積比例p設(shè)置為15，重復(fù)10次，取平均值作為最終結(jié)果，如表3所示。

由表3結(jié)果分析可得：根據(jù)測試者身上感應(yīng)設(shè)備的多少而采集到的數(shù)據(jù)集變量數(shù)是不相同的，分別使用單一感應(yīng)設(shè)備和組合感應(yīng)設(shè)備來對(duì)運(yùn)動(dòng)進(jìn)行識(shí)別。表中第2列代表不同的放置部位：T（軀干）、RA（右胳膊）、LA（左胳膊）、RL（右腿）、LL（左腿）。顯然NSFS方法對(duì)運(yùn)動(dòng)識(shí)別的準(zhǔn)確率較高，當(dāng)僅使用一個(gè)感應(yīng)設(shè)備時(shí)，可以達(dá)到最低91.275%、最高95.125%的準(zhǔn)確率。其中放置在右腿的感應(yīng)設(shè)備采集的數(shù)據(jù)分類準(zhǔn)確率最高，這和人們的常識(shí)也相一致：腿部動(dòng)作幅度最大。隨著變量數(shù)的增加，分類準(zhǔn)確率逐漸增加，查找shapelets和分類所需的時(shí)間也在逐步增加，當(dāng)使用全部5個(gè)感應(yīng)設(shè)備時(shí)，分類準(zhǔn)確率達(dá)到97.625%，這說明了有些動(dòng)作是需要身體各部位協(xié)作來完成的，如果只是觀察其中某個(gè)部位錯(cuò)誤分類的可能性也就越大。

為了更加深入地分析該數(shù)據(jù)集，給出了表3中序號(hào)1和序號(hào)9實(shí)驗(yàn)中一次結(jié)果的混淆矩陣，如表4所示。表中各行代表真實(shí)類別，各列代表使用NSDS方法得到的預(yù)測類別。對(duì)于upstairs和walk兩個(gè)動(dòng)作，使用基于軀干的傳感器和所有傳感器都可以做到完美分類，錯(cuò)誤率為0；stand和jump動(dòng)作中有個(gè)別樣本被錯(cuò)誤分類；分類效果最差的是play basketball動(dòng)作，在兩種情況下的分類錯(cuò)誤數(shù)分別為53和17，相應(yīng)的錯(cuò)誤率為33.125%和10.625%。其中主要是被錯(cuò)誤分類成stand動(dòng)作，在使用基于軀干的傳感器時(shí)有47次被錯(cuò)誤分類成stand動(dòng)作，使用全部傳感器時(shí)這一錯(cuò)誤次數(shù)為17。分析其中的原因是和數(shù)據(jù)自身采集時(shí)有關(guān)，因?yàn)閿?shù)據(jù)在采集時(shí)要求測試者連續(xù)完成每個(gè)動(dòng)作5 min，然后將所收集的數(shù)據(jù)按照5 s的窗口劃分成60等份，在做play basketball這個(gè)動(dòng)作時(shí)，中間會(huì)有短暫的靜止?fàn)顟B(tài)，這些靜止?fàn)顟B(tài)被劃分成小塊時(shí)就會(huì)和stand動(dòng)作很相似；其次因?yàn)閜lay basketball這個(gè)動(dòng)作更多的是手臂的參與，而軀干有時(shí)會(huì)處于靜止?fàn)顟B(tài)，所以在只使用T時(shí)play basketball被錯(cuò)誤分成stand的次數(shù)遠(yuǎn)遠(yuǎn)高于使用全部感應(yīng)設(shè)備。

6 結(jié)束語

本文提出了一種快速查找非相似時(shí)間序列shapelets的方法，充分利用shapelets思想的特性，而不拘泥于原始方法中的框架，使用了多種加速方法和近似計(jì)算，在不影響分類精度甚至是提升精度的情況下極大地減少計(jì)算時(shí)間。為解決多變量時(shí)間序列的shapelets問題或者計(jì)算能力不強(qiáng)的設(shè)備上使用shapelets問題提供了一種可行的選擇。在后續(xù)的工作中將會(huì)繼續(xù)致力于時(shí)間序列shapelets的研究問題，進(jìn)一步改進(jìn)本方法，減少參數(shù)的輸入，盡量減少人為因素的影響，增強(qiáng)算法的魯棒性。