在弱標記的傳感器時間序列上基于突變的事件分類

汪雅雯 王 鵬 汪 衛

(復旦大學計算機科學技術學院 上海 200433)

?

在弱標記的傳感器時間序列上基于突變的事件分類

汪雅雯 王 鵬 汪 衛

(復旦大學計算機科學技術學院 上海 200433)

隨著傳感器廣泛應用于各個領域，在傳感器生成的時間序列上識別事件越來越受到廣泛的關注。針對震蕩的傳感器時間序列，提出事件分類算法BEC。對于原始長時間序列和標記時間點作為類標簽，BEC主要解決了兩個問題。首先是將標記時間點擴展為包含充分信息的子序列以分類，再者是提取基于突變的特征以訓練分類模型。實驗結果證明，無需大部分時間序列分類問題中不現實的假設和太多人力干預，BEC提取的基于突變的特征能夠充分描述事件，極大保留事件中關鍵信息，在現實數據集上的表現優于現有的時間序列分類算法。

時間序列 分類 傳感器數據 弱標記

0 引 言

傳感器越來越多的應用于監測各類事件的發生，比如穿戴設備識別跑步、跳繩等運動；橋梁監測系統監測爆破、船撞等。但是，鑒于傳感器數據的特征，傳統的時間序列分類算法并不能適用于傳感器時間序列的分類問題。

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

圖1 爆破事件例舉

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

本文針對傳感器上的時間序列分類問題的特征，提出了基于突變的分類算法BEC。首先，本文提出基于突變的特征的定義。算法并非直接從原始時間序列中提取特征，而是挖掘不同幅值的的突變并組成異常波動序列。為了能夠對齊不同事件的異常，首先將異常標準化為二維數據點的序列，然后借鑒PAA[7]的思想來構造特征向量。另外，為了能夠將標記時間點擴展為標記子序列，BEC算法將窗口作為參數，使用DIRECT[8]來學習得到最優窗口。實驗證明BEC能夠很好地應用于現實情境下的傳感器數據，基于突變恰當提取事件特征，在現實數據集上的表現優于現有的時間序列分類算法。

1 問題定義

1.1 基本定義

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

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

定義3 事件E={E1,E2,…,Em}是一組現實情境中的行為，而Ei表示的是一個事件類別。

實際上，并非如同在文獻[1-2]中所展示的那樣，現實中的時間序列分類問題中不可能預先存在能夠完全對齊的等長序列[4]。原始的標記數據一般是原始長時間序列，以及標志事件發生的標記時間點。BEC算法的輸入是時間序列S和一組事件實例。

定義4 事件實例EIj={t1,t2,…,tmj}包含mj個標記時間點，對應事件類別Ej。

1.2 問題闡述

對于給定的時間序列S和一組事件實例{EI1,EI2,…,EIn}，BEC通過提取特征訓練模型來學習如何區分不同的事件。對給定的查詢時間點tq，根據BEC訓練得到的參數建立分類模型進行分類。

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

2 算法概要

首先對事件作出以下合理的假設：

1) 事件的發生能夠以異常波動的形式表現在傳感器產生的時間序列上。如果沒有事件發生，時間序列一般表現為有細微噪聲的平穩狀態。

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

3) 不同的事件反映在時間序列上會產生不同的異常波動，可以通過提取適當的特征來區分事件。

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

1) 在由事件實例的標記時間點得到的子序列上提取突變點，這些突變點指示可能發生的事件，是BEC算法分析的基礎。

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

3) 為了不僅能夠準確描述事件特征，也能夠對事件進行相似性度量，規整化觀測窗口中的異常序列，得到特征向量。

4) 訓練分類模型，學習相關的參數，對于給定的標記時間點，根據提取的特征和訓練得到的分類模型自動區分不同的事件。

3 特征提取

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

3.1 從時間序列到突變

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

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

BEC將位于指數概率模型末端的數據點視為突變點，隨機變量X的指數分布累積分布函數如下：

P(X>x)=eλx

(1)

(2)

在指數分布概率模型的末端設置閾值，將超過閾值的稱為突變點。注意需同時計算正負向的閾值。

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

圖2 突變挖掘示意圖

定義5 對于事件實例的子序列，突變B的序列是一組有序的超過動態閾值的突變點{b1,b2,…,b|B|}。bj=(tj,vj)包含時間和數值兩個維度。

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

(3)

經過實驗證明，參數P對分類結果并不敏感，而l可以根據領域知識設定，所以不需要通過訓練得到。

3.2 從突變到異常

獨立的突變點對于數據分析而言有些過于瑣碎，因此BEC將距離足夠近的突變點聚集稱為異常。

距離足夠近指的是在時間維度上的距離，采用簡單的基于閾值的方法。如果兩個相鄰突變點之間的時間間隔在閾值τ以內，那么認為它們距離足夠相近。而τ能夠依據相鄰突變點之間的時間間隔的統計值進行設置，如圖3所示，相鄰突變之間的時間間隔大量聚集于一個區段之內，也就是設定τ的依據。此案例中將τ設置為200。

圖3 PAMAP數據集[10]中相鄰突變時間間隔統計圖

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

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

(4)

其中1<…

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

定義6 異常ABi是突變集合gi中最具代表性的數據點，表示為：

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

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

(5)

BEC用單個突變點表示異常，由此忽略原始數據中不重要且多種多樣的細節信息，比如時間序列如何震蕩達到最大峰值。

3.3 從異常到特征

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

3.3.1 觀測窗口

上文中將事件實例的標記時間點擴展為時間序列子序列來避免不必要的數據處理，但是子序列對于分類而言太過于模糊。因此BEC在子序列中選取更為精確的窗口來區分不同的事件。觀測窗口有以下兩個準則:

1) 觀測窗口中一定包含表示類標簽的標記時間點。

2) 如果觀測窗口中包含多個異常，其中具有最大峰值的異常應當位于觀測窗口的中心。因為該異常是事件反映在時間序列上最顯著的表征，如此能夠更精確地匹配對齊不同事件的窗口。

但是在現實情境中，不可能預知合適的觀測窗口，同時已知的類標簽是標記時間點。顯而易見，觀測窗口的大小和位置都需要通過訓練得到。在下一節詳細闡述基于DIRECT訓練觀測窗口，現在假設已知觀測窗口，解釋如何在給定的窗口中提取特征。

對于每一個事件實例，觀測窗口Wob={AB1,AB2,…,ABω}，其中ω表示觀測窗口Wob中異常的個數。對不同的事件實例，其觀測窗口中的異常個數是不同的。

3.3.2 異常標準化

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

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

根據異常點之間的相對位置，BEC將異常序列{AB1,AB2,…,ABω}標準化為時間及數值的二維空間[-1,1]×[0,1]上ω個數據點。令ABmax=(tmax,vmax)表示異常序列中具有最大峰值的異常，其對應數據點為(0,1)。對異常點ABi，通過如下公式計算得到對應的被映射點(0≤i≤ω)：

(6)

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

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

(7)

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

4 分類和參數選取

最近鄰分類算法在時間序列分類領域被證明是極其有效準確的分類模型，BEC采用K-NN(K最近鄰)作為分類模型。在訓練模型的階段，學習得到觀測窗口參數以及分段數目N。對于每種事件實例，BEC創建二類分類器，將該事件實例作為正類，余下的作為負類。

4.1 模型訓練

BEC使用基于DIRECT[8]和交叉驗證的方法訓練觀測窗口大小W和分段數目N。

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

圖4 DIRECT和交叉驗證示意圖

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

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

根據觀測窗口和分段數目，BEC針對每個標記時間點提取特征，并使用留一交叉驗證法來計算參數對的誤差函數。

4.2 分 類

給定查詢時間點tq，BEC在訓練得到的觀測窗口W中依據分段數目N提取特征Ftq。使用歐幾里德距離的K-NN分類器對Ftq進行分類，BEC通過K最近鄰決定時間點tq的類標簽。

5 實驗結果及分析

本節實驗證明BEC在現實問題中具有非常好的應用，在PAMAP數據集[10]和橋梁健康監測數據集上與現有的時間序列分類算法比較。

BEC算法的輸入是標記時間點作為類標簽的原始時間序列，而不是一組經過預處理的時間序列子序列。首先將類標簽隨機分為訓練集和測試集。對于其他作為對比的方法，根據訓練得到的觀測窗口從原始時間序列中提取子序列并組成訓練集和測試集。

為了避免將對比實驗結果歸因于本文子序列提取方法的質疑，在不同的觀測窗口參數上進行實驗比較。同時公平起見，在不同的數據集上均訓練各個算法以得到最優的分類結果。

實驗在Intel Core i5-4690 3.50 GHz CPU以及16 GB內存的機器上進行。BEC用Java實現，SAX-VSM和RPM的源代碼由原作者提供。

5.1 在PAMAP數據集上的應用

PAMAP數據集記錄在身上不同部位佩戴傳感器的實驗對象進行各種活動的數據，在實驗中使用的是PAMAP2數據集中位于腳踝部位的Z軸加速度數據。數據集的原始數據是一條長時間序列，以及標記為多個時間區段的不同活動標簽。在不同事件對應的時間區段內隨機選取一些時間點作為類標簽。

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

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

(a) (b)圖5 步行和北歐健走實驗結果

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

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

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

圖7 跑步和跳繩對比組在時間序列正向提取的特征

5.2 在橋梁健康監測數據集上的應用

橋梁健康監測傳感器收集橋梁不同位置的三個維度的加速度數據等，這里使用的是橋梁固定點Z軸加速度數據。原始數據集是一條長時間序列，以及一組時間點標記多種事件的發生。

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

圖8 爆破和海浪實驗結果

6 結 語

本文提出了一個在現實情境下分類傳感器生成的震蕩時間序列的算法BEC。對于給定的長時間序列以及作為類標簽的標記時間點，BEC基于DIRECT和交叉驗證訓練得到用于分類的合適對象，同時基于突變提取包含數值和位置信息的特征。在現實數據集上通過實驗證明BEC相較于現有的算法具有更高的效率和準確性。

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

[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。中國科技部國家重點研發計劃資助項目(2016YFB1000700)；國家重點基礎研究發展計劃項目(2015CB358800)；國家自然科學基金項目(61672163，61170006)。汪雅雯，碩士生，主研領域：時間序列數據挖掘。王鵬，副教授。汪衛，教授。

TP3

A

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