汪雅雯 王 鵬 汪 衛(wèi)

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433)

?

在弱標(biāo)記的傳感器時(shí)間序列上基于突變的事件分類

汪雅雯 王 鵬 汪 衛(wèi)

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433)

隨著傳感器廣泛應(yīng)用于各個(gè)領(lǐng)域，在傳感器生成的時(shí)間序列上識(shí)別事件越來越受到廣泛的關(guān)注。針對(duì)震蕩的傳感器時(shí)間序列，提出事件分類算法BEC。對(duì)于原始長(zhǎng)時(shí)間序列和標(biāo)記時(shí)間點(diǎn)作為類標(biāo)簽，BEC主要解決了兩個(gè)問題。首先是將標(biāo)記時(shí)間點(diǎn)擴(kuò)展為包含充分信息的子序列以分類，再者是提取基于突變的特征以訓(xùn)練分類模型。實(shí)驗(yàn)結(jié)果證明，無需大部分時(shí)間序列分類問題中不現(xiàn)實(shí)的假設(shè)和太多人力干預(yù)，BEC提取的基于突變的特征能夠充分描述事件，極大保留事件中關(guān)鍵信息，在現(xiàn)實(shí)數(shù)據(jù)集上的表現(xiàn)優(yōu)于現(xiàn)有的時(shí)間序列分類算法。

時(shí)間序列 分類 傳感器數(shù)據(jù) 弱標(biāo)記

0 引 言

傳感器越來越多的應(yīng)用于監(jiān)測(cè)各類事件的發(fā)生，比如穿戴設(shè)備識(shí)別跑步、跳繩等運(yùn)動(dòng)；橋梁監(jiān)測(cè)系統(tǒng)監(jiān)測(cè)爆破、船撞等。但是，鑒于傳感器數(shù)據(jù)的特征，傳統(tǒng)的時(shí)間序列分類算法并不能適用于傳感器時(shí)間序列的分類問題。

1) 對(duì)于傳感器產(chǎn)生的時(shí)間序列，事件標(biāo)簽一般是原始長(zhǎng)時(shí)間序列上的標(biāo)記時(shí)間點(diǎn)。比如在橋梁健康監(jiān)測(cè)系統(tǒng)中，描述爆破事件為“橋體在13:39發(fā)生爆破”，這里標(biāo)簽并不是事件發(fā)生的完整過程，而是事件進(jìn)行中任何可能的時(shí)間點(diǎn)。如圖1所示，圖中例舉了三次爆破，標(biāo)記時(shí)間點(diǎn)在爆破事件發(fā)生時(shí)間段內(nèi)的任意位置。而在傳統(tǒng)時(shí)間序列分類問題中，長(zhǎng)時(shí)間序列被人為切分為若干等長(zhǎng)的片段來表示事件[1-2]，這種不現(xiàn)實(shí)的假設(shè)也出現(xiàn)在時(shí)間序列領(lǐng)域常用的UCR數(shù)據(jù)集[3]中。在現(xiàn)實(shí)情況中，要么無法得到精確的事件切分，要么需要消耗大量的人力來完成。而且，不精確的分段會(huì)極大地影響分類的準(zhǔn)確度，這種情形稱為弱標(biāo)記的時(shí)間序列[4]。

圖1 爆破事件例舉

2) 現(xiàn)有的特征提取算法對(duì)于傳感器事件分類問題而言，無法提取包含足夠信息的特征。文獻(xiàn)[2]提出的Shapelet提取的是原始序列中最具備區(qū)分性的子序列，使用歐幾里得距離來衡量相似度，但是即使傳感器數(shù)據(jù)看上去很相似，直接在原始序列上比較相似距離仍然有很大的差別。如圖1所示，盡管三個(gè)事件同為爆破，但由于爆破強(qiáng)度、爆破位置等不同，反映在時(shí)間序列上細(xì)節(jié)差異相當(dāng)大。另外選取全局特征的方法，比如文獻(xiàn)[5]中基于DWT的特征提取方法丟失了許多細(xì)節(jié)信息。文獻(xiàn)[6]提出的SAX-VSM將時(shí)間序列轉(zhuǎn)化為SAX單詞，采用類似文本分類的方法訓(xùn)練分類模型，但是忽略了SAX單詞之間的位置信息，而位置信息這一點(diǎn)在傳感器數(shù)據(jù)中相當(dāng)重要。

本文針對(duì)傳感器上的時(shí)間序列分類問題的特征，提出了基于突變的分類算法BEC。首先，本文提出基于突變的特征的定義。算法并非直接從原始時(shí)間序列中提取特征，而是挖掘不同幅值的的突變并組成異常波動(dòng)序列。為了能夠?qū)R不同事件的異常，首先將異常標(biāo)準(zhǔn)化為二維數(shù)據(jù)點(diǎn)的序列，然后借鑒PAA[7]的思想來構(gòu)造特征向量。另外，為了能夠?qū)?biāo)記時(shí)間點(diǎn)擴(kuò)展為標(biāo)記子序列，BEC算法將窗口作為參數(shù)，使用DIRECT[8]來學(xué)習(xí)得到最優(yōu)窗口。實(shí)驗(yàn)證明BEC能夠很好地應(yīng)用于現(xiàn)實(shí)情境下的傳感器數(shù)據(jù)，基于突變恰當(dāng)提取事件特征，在現(xiàn)實(shí)數(shù)據(jù)集上的表現(xiàn)優(yōu)于現(xiàn)有的時(shí)間序列分類算法。

1 問題定義

1.1 基本定義

定義1 時(shí)間序列S={s1,s2,…,s|S|}是一組有序的實(shí)值序列。

定義2 時(shí)間序列子序列S[i,j]={si,si+1,…,sj}是時(shí)間序列S的一段連續(xù)的分段。

定義3 事件E={E1,E2,…,Em}是一組現(xiàn)實(shí)情境中的行為，而Ei表示的是一個(gè)事件類別。

實(shí)際上，并非如同在文獻(xiàn)[1-2]中所展示的那樣，現(xiàn)實(shí)中的時(shí)間序列分類問題中不可能預(yù)先存在能夠完全對(duì)齊的等長(zhǎng)序列[4]。原始的標(biāo)記數(shù)據(jù)一般是原始長(zhǎng)時(shí)間序列，以及標(biāo)志事件發(fā)生的標(biāo)記時(shí)間點(diǎn)。BEC算法的輸入是時(shí)間序列S和一組事件實(shí)例。

定義4 事件實(shí)例EIj={t1,t2,…,tmj}包含mj個(gè)標(biāo)記時(shí)間點(diǎn)，對(duì)應(yīng)事件類別Ej。

1.2 問題闡述

對(duì)于給定的時(shí)間序列S和一組事件實(shí)例{EI1,EI2,…,EIn}，BEC通過提取特征訓(xùn)練模型來學(xué)習(xí)如何區(qū)分不同的事件。對(duì)給定的查詢時(shí)間點(diǎn)tq，根據(jù)BEC訓(xùn)練得到的參數(shù)建立分類模型進(jìn)行分類。

更直觀地說，BEC解決的是在tq周圍一段時(shí)間內(nèi)發(fā)生了什么事件的問題。算法并不假設(shè)在原始序列上已知的理想片段，而是通過訓(xùn)練學(xué)習(xí)獲取能夠充分描述事件的模式。

2 算法概要

首先對(duì)事件作出以下合理的假設(shè)：

1) 事件的發(fā)生能夠以異常波動(dòng)的形式表現(xiàn)在傳感器產(chǎn)生的時(shí)間序列上。如果沒有事件發(fā)生，時(shí)間序列一般表現(xiàn)為有細(xì)微噪聲的平穩(wěn)狀態(tài)。

2) 事件在時(shí)間序列上產(chǎn)生一些波動(dòng)，其中具有最高峰值的波動(dòng)被視為由事件直接影響產(chǎn)生。同時(shí)，這些波動(dòng)之間的聯(lián)系在事件識(shí)別中有很重要的作用。

3) 不同的事件反映在時(shí)間序列上會(huì)產(chǎn)生不同的異常波動(dòng)，可以通過提取適當(dāng)?shù)奶卣鱽韰^(qū)分事件。

基于以上的假設(shè)，本文提出基于突變的事件分類算法BEC。對(duì)于給定的時(shí)間序列S和一組事件實(shí)例{EI1,EI2,…,EIn}，為了避免不必要的處理整條序列，首先將每一個(gè)事件實(shí)例的時(shí)間點(diǎn)依次擴(kuò)展為時(shí)間序列子序列。以時(shí)間點(diǎn)ti為中心，得到長(zhǎng)度為L(zhǎng)的子序列S[ti-L/2,…,ti,…,ti+L/2]。由于擴(kuò)展子序列只是為了降低后續(xù)工作的工作量，所以L并不是一個(gè)非常敏感的參數(shù)，可以根據(jù)實(shí)際需求設(shè)定。后續(xù)的工作在得到的子序列上進(jìn)行。

1) 在由事件實(shí)例的標(biāo)記時(shí)間點(diǎn)得到的子序列上提取突變點(diǎn)，這些突變點(diǎn)指示可能發(fā)生的事件，是BEC算法分析的基礎(chǔ)。

2) 將突變點(diǎn)劃分為不相交的集合組成異常波動(dòng)，它們是事件反映在時(shí)間序列上的表征。為了更好地描述異常波動(dòng)，從集合中選取具有代表性的點(diǎn)表示異常波動(dòng)。

3) 為了不僅能夠準(zhǔn)確描述事件特征，也能夠?qū)κ录M(jìn)行相似性度量，規(guī)整化觀測(cè)窗口中的異常序列，得到特征向量。

4) 訓(xùn)練分類模型，學(xué)習(xí)相關(guān)的參數(shù)，對(duì)于給定的標(biāo)記時(shí)間點(diǎn)，根據(jù)提取的特征和訓(xùn)練得到的分類模型自動(dòng)區(qū)分不同的事件。

3 特征提取

首先在原始序列上提取突變并組成異常，然后在觀測(cè)窗口中處理異常以獲取特征。

3.1 從時(shí)間序列到突變

突變，指的是在平穩(wěn)時(shí)間序列上罕見出現(xiàn)的數(shù)據(jù)點(diǎn)，可以指示可能發(fā)生的事件，因此概率模型通常被用于挖掘時(shí)間序列上的突變。由于僅將突變作為事件的指示而無需太過于精確，BEC沒有選擇復(fù)雜的時(shí)間序列模型，而是拓展了文獻(xiàn)[9]中的方法。

大多數(shù)事件體現(xiàn)在時(shí)間序列上同時(shí)存在正負(fù)向的突變，如加速度數(shù)據(jù)。因此，BEC將數(shù)據(jù)按照X軸切分為正負(fù)向，并分別提取雙向的突變。為了表述方便，在后文中僅按正向進(jìn)行闡述。

BEC將位于指數(shù)概率模型末端的數(shù)據(jù)點(diǎn)視為突變點(diǎn)，隨機(jī)變量X的指數(shù)分布累積分布函數(shù)如下：

P(X>x)=eλx

(1)

(2)

在指數(shù)分布概率模型的末端設(shè)置閾值，將超過閾值的稱為突變點(diǎn)。注意需同時(shí)計(jì)算正負(fù)向的閾值。

由于在整條時(shí)間序列上計(jì)算閾值具有較大的偏差，BEC在時(shí)間序列上滑動(dòng)重疊窗口來計(jì)算動(dòng)態(tài)閾值。首先針對(duì)每個(gè)窗口計(jì)算得到閾值，在窗口重疊的部分計(jì)算相鄰窗口內(nèi)對(duì)應(yīng)的閾值均值。對(duì)于給定的參數(shù)l，以步長(zhǎng)l滑動(dòng)長(zhǎng)度為2l的窗口，即{W1,W2,…,WL/l-1}，其中Wi=S[(i-1)×l+1,(i+1)×l],(0

圖2 突變挖掘示意圖

定義5 對(duì)于事件實(shí)例的子序列，突變B的序列是一組有序的超過動(dòng)態(tài)閾值的突變點(diǎn){b1,b2,…,b|B|}。bj=(tj,vj)包含時(shí)間和數(shù)值兩個(gè)維度。

bj={(tj,vj)|vj>δj∧tj∈Wj∧tj∈Wj+1}

(3)

經(jīng)過實(shí)驗(yàn)證明，參數(shù)P對(duì)分類結(jié)果并不敏感，而l可以根據(jù)領(lǐng)域知識(shí)設(shè)定，所以不需要通過訓(xùn)練得到。

3.2 從突變到異常

獨(dú)立的突變點(diǎn)對(duì)于數(shù)據(jù)分析而言有些過于瑣碎，因此BEC將距離足夠近的突變點(diǎn)聚集稱為異常。

距離足夠近指的是在時(shí)間維度上的距離，采用簡(jiǎn)單的基于閾值的方法。如果兩個(gè)相鄰?fù)蛔凕c(diǎn)之間的時(shí)間間隔在閾值τ以內(nèi)，那么認(rèn)為它們距離足夠相近。而τ能夠依據(jù)相鄰?fù)蛔凕c(diǎn)之間的時(shí)間間隔的統(tǒng)計(jì)值進(jìn)行設(shè)置，如圖3所示，相鄰?fù)蛔冎g的時(shí)間間隔大量聚集于一個(gè)區(qū)段之內(nèi)，也就是設(shè)定τ的依據(jù)。此案例中將τ設(shè)置為200。

圖3 PAMAP數(shù)據(jù)集[10]中相鄰?fù)蛔儠r(shí)間間隔統(tǒng)計(jì)圖

BEC根據(jù)閾值將突變序列{b1,b2,…,b|B|}劃分為不相交的集合G={g1,g2,…,g|G|}，gi表示如下：

gi={bri-1+1,…,bri}

(4)

其中1<…

BEC重點(diǎn)關(guān)注異常兩個(gè)方面的特性。首先是集合中具有最大峰值的突變，再者是異常的分布。從突變集合gi中選取具有最大峰值的突變點(diǎn)來表示它。

定義6 異常ABi是突變集合gi中最具代表性的數(shù)據(jù)點(diǎn)，表示為：

ABi= {bri-1+k|bri-1+k∈gi∧vri-1+k=

max{vri-1+1,…,vri}}

(5)

BEC用單個(gè)突變點(diǎn)表示異常，由此忽略原始數(shù)據(jù)中不重要且多種多樣的細(xì)節(jié)信息，比如時(shí)間序列如何震蕩達(dá)到最大峰值。

3.3 從異常到特征

BEC規(guī)整化觀測(cè)窗口中的異常以提取特征。首先，闡述觀測(cè)窗口的概念。

3.3.1 觀測(cè)窗口

上文中將事件實(shí)例的標(biāo)記時(shí)間點(diǎn)擴(kuò)展為時(shí)間序列子序列來避免不必要的數(shù)據(jù)處理，但是子序列對(duì)于分類而言太過于模糊。因此BEC在子序列中選取更為精確的窗口來區(qū)分不同的事件。觀測(cè)窗口有以下兩個(gè)準(zhǔn)則:

1) 觀測(cè)窗口中一定包含表示類標(biāo)簽的標(biāo)記時(shí)間點(diǎn)。

2) 如果觀測(cè)窗口中包含多個(gè)異常，其中具有最大峰值的異常應(yīng)當(dāng)位于觀測(cè)窗口的中心。因?yàn)樵摦惓Ｊ鞘录从吃跁r(shí)間序列上最顯著的表征，如此能夠更精確地匹配對(duì)齊不同事件的窗口。

但是在現(xiàn)實(shí)情境中，不可能預(yù)知合適的觀測(cè)窗口，同時(shí)已知的類標(biāo)簽是標(biāo)記時(shí)間點(diǎn)。顯而易見，觀測(cè)窗口的大小和位置都需要通過訓(xùn)練得到。在下一節(jié)詳細(xì)闡述基于DIRECT訓(xùn)練觀測(cè)窗口，現(xiàn)在假設(shè)已知觀測(cè)窗口，解釋如何在給定的窗口中提取特征。

對(duì)于每一個(gè)事件實(shí)例，觀測(cè)窗口Wob={AB1,AB2,…,ABω}，其中ω表示觀測(cè)窗口Wob中異常的個(gè)數(shù)。對(duì)不同的事件實(shí)例，其觀測(cè)窗口中的異常個(gè)數(shù)是不同的。

3.3.2 異常標(biāo)準(zhǔn)化

對(duì)不同的事件實(shí)例，BEC描述的是異常的值和位置之間的關(guān)系。比如爆破事件是快速下降的劇烈震蕩，而后續(xù)幾乎沒有其他波峰；而海浪則是包含多個(gè)相近峰值和時(shí)間間隔的波峰。但是，由于異常的數(shù)量和位置各不相同，無法直接度量異常的相似性，因此，BEC在觀測(cè)窗口中基于異常構(gòu)造N維特征向量，以歐幾里得距離衡量異常之間的相似度。

定義7 對(duì)于事件實(shí)例的觀測(cè)窗口，特征F=〈f1,f2,…,fN〉是一組N維對(duì)齊的向量。

根據(jù)異常點(diǎn)之間的相對(duì)位置，BEC將異常序列{AB1,AB2,…,ABω}標(biāo)準(zhǔn)化為時(shí)間及數(shù)值的二維空間[-1,1]×[0,1]上ω個(gè)數(shù)據(jù)點(diǎn)。令A(yù)Bmax=(tmax,vmax)表示異常序列中具有最大峰值的異常，其對(duì)應(yīng)數(shù)據(jù)點(diǎn)為(0,1)。對(duì)異常點(diǎn)ABi，通過如下公式計(jì)算得到對(duì)應(yīng)的被映射點(diǎn)(0≤i≤ω)：

(6)

例如，{(3,1),(4,5),(6,1)}映射為{(-0.5,0.2),(0,1),(1,0.2)}。

盡管將不同事件實(shí)例的異常映射到相同空間，但是由于異常是離散且分布不規(guī)律的，仍然無法直接進(jìn)行相似性度量。BEC將時(shí)間維度劃分為N段，即{seg1,seg2,…,segN}，用實(shí)值表示每個(gè)分段segi。這里N是分段個(gè)數(shù)，表示對(duì)異常位置偏移的容忍度，將在下一節(jié)詳細(xì)闡述如何訓(xùn)練得到N。需要強(qiáng)調(diào)的是，不同的事件實(shí)例分段N值是相同的。

(7)

接下來，BEC使用歐幾里得距離度量特征F和F′之間的相似度。

4 分類和參數(shù)選取

最近鄰分類算法在時(shí)間序列分類領(lǐng)域被證明是極其有效準(zhǔn)確的分類模型，BEC采用K-NN(K最近鄰)作為分類模型。在訓(xùn)練模型的階段，學(xué)習(xí)得到觀測(cè)窗口參數(shù)以及分段數(shù)目N。對(duì)于每種事件實(shí)例，BEC創(chuàng)建二類分類器，將該事件實(shí)例作為正類，余下的作為負(fù)類。

4.1 模型訓(xùn)練

BEC使用基于DIRECT[8]和交叉驗(yàn)證的方法訓(xùn)練觀測(cè)窗口大小W和分段數(shù)目N。

DIRECT是一種采樣策略算法。對(duì)于在搜索空間上的函數(shù)，DIRECT極其有效的迭代尋找全局最優(yōu)點(diǎn)。在BEC算法中，搜索空間是一個(gè)二維空間，表示為R(一個(gè)維度是觀測(cè)窗口大小W，另一個(gè)是分段數(shù)目N)。首先，DIRECT在R的中心點(diǎn)(w0,n0)計(jì)算誤差函數(shù)，然后DIRECT依據(jù)中心點(diǎn)和誤差函數(shù)將搜索空間切分為更小的子空間，這個(gè)過程是迭代進(jìn)行的，直到誤差函數(shù)收斂。通過有效的采樣策略，DIRECT能夠智能定位子空間并快速收斂到全局最優(yōu)值。DIRECT和交叉驗(yàn)證的示意圖如圖4所示，黑色正方形的中心點(diǎn)表示低誤差率，而灰色正方形的中心點(diǎn)表示高誤差率。

圖4 DIRECT和交叉驗(yàn)證示意圖

BEC對(duì)給定參數(shù)(w,n)進(jìn)行如下三個(gè)步驟：首先根據(jù)事件實(shí)例定位大小為w的觀測(cè)窗口，然后在觀測(cè)窗口中獲取異常的特征，最后使用交叉驗(yàn)證來計(jì)算(w,n)的誤差函數(shù)。

用如下的方法來定位觀測(cè)窗口。對(duì)于給定的標(biāo)記時(shí)間點(diǎn)t和觀測(cè)窗口大小w，要獲得觀測(cè)窗口Wob=[r,r+w-1]。Wob被初始化為[t-w/2,t+w/2]，在窗口中找到具有最大峰值的異常，并將其置為新的中心。根據(jù)該中心創(chuàng)建一個(gè)新窗口，在窗口中尋找下一個(gè)具有最大峰值的異常。這個(gè)過程直到窗口不再發(fā)生變化或者標(biāo)記時(shí)間點(diǎn)不再位于窗口中而終止。

根據(jù)觀測(cè)窗口和分段數(shù)目，BEC針對(duì)每個(gè)標(biāo)記時(shí)間點(diǎn)提取特征，并使用留一交叉驗(yàn)證法來計(jì)算參數(shù)對(duì)的誤差函數(shù)。

4.2 分 類

給定查詢時(shí)間點(diǎn)tq，BEC在訓(xùn)練得到的觀測(cè)窗口W中依據(jù)分段數(shù)目N提取特征Ftq。使用歐幾里德距離的K-NN分類器對(duì)Ftq進(jìn)行分類，BEC通過K最近鄰決定時(shí)間點(diǎn)tq的類標(biāo)簽。

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

本節(jié)實(shí)驗(yàn)證明BEC在現(xiàn)實(shí)問題中具有非常好的應(yīng)用，在PAMAP數(shù)據(jù)集[10]和橋梁健康監(jiān)測(cè)數(shù)據(jù)集上與現(xiàn)有的時(shí)間序列分類算法比較。

BEC算法的輸入是標(biāo)記時(shí)間點(diǎn)作為類標(biāo)簽的原始時(shí)間序列，而不是一組經(jīng)過預(yù)處理的時(shí)間序列子序列。首先將類標(biāo)簽隨機(jī)分為訓(xùn)練集和測(cè)試集。對(duì)于其他作為對(duì)比的方法，根據(jù)訓(xùn)練得到的觀測(cè)窗口從原始時(shí)間序列中提取子序列并組成訓(xùn)練集和測(cè)試集。

為了避免將對(duì)比實(shí)驗(yàn)結(jié)果歸因于本文子序列提取方法的質(zhì)疑，在不同的觀測(cè)窗口參數(shù)上進(jìn)行實(shí)驗(yàn)比較。同時(shí)公平起見，在不同的數(shù)據(jù)集上均訓(xùn)練各個(gè)算法以得到最優(yōu)的分類結(jié)果。

實(shí)驗(yàn)在Intel Core i5-4690 3.50 GHz CPU以及16 GB內(nèi)存的機(jī)器上進(jìn)行。BEC用Java實(shí)現(xiàn)，SAX-VSM和RPM的源代碼由原作者提供。

5.1 在PAMAP數(shù)據(jù)集上的應(yīng)用

PAMAP數(shù)據(jù)集記錄在身上不同部位佩戴傳感器的實(shí)驗(yàn)對(duì)象進(jìn)行各種活動(dòng)的數(shù)據(jù)，在實(shí)驗(yàn)中使用的是PAMAP2數(shù)據(jù)集中位于腳踝部位的Z軸加速度數(shù)據(jù)。數(shù)據(jù)集的原始數(shù)據(jù)是一條長(zhǎng)時(shí)間序列，以及標(biāo)記為多個(gè)時(shí)間區(qū)段的不同活動(dòng)標(biāo)簽。在不同事件對(duì)應(yīng)的時(shí)間區(qū)段內(nèi)隨機(jī)選取一些時(shí)間點(diǎn)作為類標(biāo)簽。

文獻(xiàn)[11]中比對(duì)歐幾里德距離的最近鄰、DTW距離的最近鄰、Fast Shapelets以及數(shù)據(jù)集原作者提出的專家算法在數(shù)據(jù)集上的準(zhǔn)確度都低于90%，而BEC算法能達(dá)到超過95%的準(zhǔn)確度。接下來與SAX-VSM[6]以及RPM[12]算法進(jìn)行詳細(xì)的比較和說明。在數(shù)據(jù)集中選取了幾個(gè)容易混淆的活動(dòng)，并把它們分成幾組進(jìn)行實(shí)驗(yàn)，分別是步行和北歐式健走、上樓梯和下樓梯、跑步和跳繩。

在步行和北歐式健走數(shù)據(jù)集上，根據(jù)訓(xùn)練得到的參數(shù)，BEC算法能夠到達(dá)97.85%的準(zhǔn)確度，而且只需要2.86 s的訓(xùn)練時(shí)間。每次實(shí)驗(yàn)都將觀測(cè)窗口作為定值，這里的觀測(cè)窗口包括窗口大小和位置，然后從原始序列中提取子序列作為SAX-VSM和RPM的數(shù)據(jù)集。如圖5所示，其中(a)表示準(zhǔn)確度比對(duì)結(jié)果，(b)表示訓(xùn)練時(shí)間比對(duì)結(jié)果。在對(duì)比中BEC算法只需要訓(xùn)練分段數(shù)據(jù)這一個(gè)參數(shù)，需要大約1 s的訓(xùn)練時(shí)間。但是比較完整訓(xùn)練時(shí)間，BEC算法也勝于對(duì)比算法所需要的3～10 s。SAX-VSM的最高準(zhǔn)確度是95.6%，RPM的最高準(zhǔn)確度為86.96%，而BEC算法最高能達(dá)到接近100%的準(zhǔn)確度。

(a) (b)圖5 步行和北歐健走實(shí)驗(yàn)結(jié)果

在上樓梯和下樓梯數(shù)據(jù)集上，BEC算法需要2.544 s的訓(xùn)練時(shí)間，能夠達(dá)到接近100%的準(zhǔn)確率。如圖6所示，其中(a)表示準(zhǔn)確度比對(duì)結(jié)果，(b)表示訓(xùn)練時(shí)間比對(duì)結(jié)果。給定序列長(zhǎng)度，即觀測(cè)窗口，SAX-VSM和RPM最高達(dá)到97.5%的準(zhǔn)確度，但是所需訓(xùn)練時(shí)間很大程度上受到序列長(zhǎng)度影響。在本例中超過800個(gè)數(shù)據(jù)點(diǎn)，SAX-VSM需要大約10 s的訓(xùn)練時(shí)間，而RPM平均需要100 s。

在跑步和跳繩數(shù)據(jù)集上，BEC算法和SAX-VSM在準(zhǔn)確度上表現(xiàn)接近，都是達(dá)到了幾乎100%的準(zhǔn)確度，但是RPM無法在訓(xùn)練過程中處理本例中的數(shù)據(jù)量。BEC算法需要1.493 s的訓(xùn)練時(shí)間，但是SAX-VSM平均需要15 s的訓(xùn)練時(shí)間。

BEC算法在跑步和跳繩這一對(duì)比組數(shù)據(jù)上提取的特征如圖7所示，圖中W=55 000，N=56。(a)表示跑步原始序列，圓圈標(biāo)示異常，(c)表示跳繩原始序列，圓圈標(biāo)示異常，(b)、(d)分別表示跑步和跳繩的特征。從圖中可見跑步由一組時(shí)間間隔和幅度接近的異常構(gòu)成，而跳繩相較而言異常更加密集且凌亂。這也說明該實(shí)驗(yàn)者跑步步伐穩(wěn)定，而跳繩較為消耗體力。

圖7 跑步和跳繩對(duì)比組在時(shí)間序列正向提取的特征

5.2 在橋梁健康監(jiān)測(cè)數(shù)據(jù)集上的應(yīng)用

橋梁健康監(jiān)測(cè)傳感器收集橋梁不同位置的三個(gè)維度的加速度數(shù)據(jù)等，這里使用的是橋梁固定點(diǎn)Z軸加速度數(shù)據(jù)。原始數(shù)據(jù)集是一條長(zhǎng)時(shí)間序列，以及一組時(shí)間點(diǎn)標(biāo)記多種事件的發(fā)生。

以爆破和海浪為例，SAX-VSM和RPM的準(zhǔn)確度分別最高為59%和86%，但是SAX-VSM需要數(shù)分鐘的訓(xùn)練時(shí)間，而RPM需要訓(xùn)練超過三十分鐘。由于BEC僅僅提取少量數(shù)據(jù)點(diǎn)作為特征，所以即使時(shí)間序列長(zhǎng)度偏長(zhǎng)，BEC所需的訓(xùn)練時(shí)間也在一分鐘之內(nèi)，能夠達(dá)到100%的準(zhǔn)確度。如圖8所示，其中(a)表示準(zhǔn)確度比對(duì)結(jié)果，(b)表示訓(xùn)練時(shí)間比對(duì)結(jié)果。

圖8 爆破和海浪實(shí)驗(yàn)結(jié)果

6 結(jié) 語

本文提出了一個(gè)在現(xiàn)實(shí)情境下分類傳感器生成的震蕩時(shí)間序列的算法BEC。對(duì)于給定的長(zhǎng)時(shí)間序列以及作為類標(biāo)簽的標(biāo)記時(shí)間點(diǎn)，BEC基于DIRECT和交叉驗(yàn)證訓(xùn)練得到用于分類的合適對(duì)象，同時(shí)基于突變提取包含數(shù)值和位置信息的特征。在現(xiàn)實(shí)數(shù)據(jù)集上通過實(shí)驗(yàn)證明BEC相較于現(xiàn)有的算法具有更高的效率和準(zhǔn)確性。

但是BEC算法僅僅使用固定傳感器數(shù)據(jù)，而沒有考慮不同位置傳感器采集數(shù)據(jù)對(duì)事件識(shí)別的置信度，接下來將充分利用不同傳感器提供的信息，把算法擴(kuò)展為多維度的時(shí)間序列分類問題。

[1] Xing Z Z, Pei J, Keogh E. A brief survey on sequence classification[J]. SIGKDD Explorations, 2010, 12(1):40-48.

[2] Ye L, Keogh E. Time series shapelets:a new primitive for data mining[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28 - July. DBLP, 2009:947-956.

[3] The ucr homepage[EB/OL]. www.cs.ucr.edu/ eamonn/time series data/.

[4] Hu B. Classification of streaming time series under more realistic assumptions[C]// Austin, Texas, USA.:Proceedings of the 13th SIAM International Conference on Data Mining, 2013:578-586.

[5] Aggarwal C C. On effective classification of strings with wavelets[C]// Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2002:163-172.

[6] Senin P, Malinchik S. SAX-VSM:Interpretable Time Series Classification Using SAX and Vector Space Model[C]// IEEE, International Conference on Data Mining. IEEE, 2013:1175-1180.

[7] Keogh E J, Pazzani M J. A Simple Dimensionality Reduction Technique for Fast Similarity Search in Large Time Series Databases[M]// Knowledge Discovery and Data Mining. Current Issues and New Applications. Springer Berlin Heidelberg, 2000:122-133.

[8] Jones D R, Perttunen C D, Stuckman B E. Lipschitzian optimization without the Lipschitz constant[J]. Journal of Optimization Theory and Applications, 1993, 79(1):157-181.

[9] Vlachos M, Wu K L, Chen S K, et al. Fast Burst Correlation of Financial Data[C]// Knowledge Discovery in Databases:Pkdd 2005, European Conference on Principles and Practice of Knowledge Discovery in Databases, Porto, Portugal, October 3-7, 2005, Proceedings. DBLP, 2005:368-379.

[10] Physical activity monitoring for aging people[EB/OL]. http://www.pamap.org.

[11] Rakthanmanon T, Keogh E. Fast Shapelets:A Scalable Algorithm for Discovering Time Series Shapelets[C]// Austin, Texas, USA.:Proceedings of the 13th SIAM International Conference on Data Mining, 2013:668-676.

[12] Wang X, Lin J, Senin P, et al. RPM:representative pattern mining for efficient time series classification[C]// Bordeaux, France:Proceedings of the 19th International Conference on Extending Database Technology, 2016:185-196.

BURST-BASED EVENT CLASSIFICATION ON WEAKLY LABELED TIME SERIES DATA OF SENSORS

Wang Yawen Wang Peng Wang Wei

(SchoolofComputerScience,FudanUniversity,Shanghai200433,China)

Detecting events on time series data generated by sensors has

a great amount of attention with increasingly deployment of variable sensors. This paper proposes a novel framework for classifying events upon oscillating data of sensors called BEC. Given a long raw time series and class labels on marked time points, BEC extracts burst-based features to represent events. There are mainly two important tasks to be solved. First, BEC automatically extends labeled time points to appropriate subsequences containing sufficient information. Second, BEC extracts burst-based features to train the classification model. It is demonstrated on real-life datasets that without unrealistic assumptions and human interventions, BEC extracts burst-based features can fully detect the event, greatly retain the key information in the event, and the performance of the actual data set is better than the existing time series classification algorithm.

Time series Classification Sensor data Weakly labeled

2016-02-08。中國(guó)科技部國(guó)家重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目(2016YFB1000700)；國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目(2015CB358800)；國(guó)家自然科學(xué)基金項(xiàng)目(61672163，61170006)。汪雅雯，碩士生，主研領(lǐng)域：時(shí)間序列數(shù)據(jù)挖掘。王鵬，副教授。汪衛(wèi)，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.07.037