一種基于隨機交疊策略的多突變點在線檢測方法

朱俊俊，齊金鵬，鐘金美，任 晴，曹一彤

(東華大學 信息科學與技術(shù)學院，上海 201620)

在當今的大數(shù)據(jù)時代[1-3]，在醫(yī)療服務、健康保健和衛(wèi)生管理過程中產(chǎn)生了海量數(shù)據(jù)集，形成了健康醫(yī)療大數(shù)據(jù)。面對大量的醫(yī)療數(shù)據(jù)，快速分析數(shù)據(jù)流中的有效信息[4-6]已成為當前的研究熱點。突變點檢測技術(shù)是數(shù)據(jù)流研究方向的一個重要分支[7-10]，受到了越來越多的關注。癲癇病人病理信號是一種典型的大規(guī)模時序數(shù)據(jù)，對其進行分析檢測需要較高的準確性和時效性。針對大規(guī)模的病理數(shù)據(jù)進行在線突變點檢測分析也逐漸成為當前研究的熱點方向。

傳統(tǒng)的突變點檢測方法以離線為主，無法對大規(guī)模的時序數(shù)據(jù)進行在線檢測。國內(nèi)外學者在突變點檢測領域取得了一系列研究成果。文獻[7～9]提出了基于距離或相似程度的檢測方法，利用迭代方法優(yōu)化事先設定的目標函數(shù)，最終得到了目標函數(shù)的最優(yōu)解，即可將不滿足條件的點確定為突變點。單總體T檢驗(Student′s Test)可判斷一個樣本平均數(shù)與一個已知的總體平均數(shù)的差異顯著性，適用于樣本數(shù)據(jù)較小的情況，當樣本數(shù)據(jù)屬于大規(guī)模時序數(shù)據(jù)時，T檢驗的檢測效果較差[10]。KS檢驗(Kolmogorov-Smirnov Test)則基于累計分布函數(shù)[11]。兩樣本的KS檢驗對兩樣本經(jīng)驗分布函數(shù)的位置和形態(tài)參數(shù)的差異較為敏感，因此成為了比較兩樣本差異的最常用的非參數(shù)方法之一。但是，上述幾種方法在進行大規(guī)模時序數(shù)據(jù)檢測時，不僅具有時耗較長、精度較低等問題，還沒有加入緩沖區(qū)，因此無法針對大規(guī)模在線時序數(shù)據(jù)流進行在線分析檢測。

針對傳統(tǒng)算法無法在線檢測、檢測精度不高和時耗較長等問題，本文在TSTKS(Ternary Search Tree and KS)[12]算法和滑動窗口模型的基礎上，加入緩沖區(qū)模型和隨機交疊策略，提出了一種基于滑動窗口[13-14]隨機交疊策略的檢測方法：首先，利用緩沖區(qū)接收在線數(shù)據(jù)流，將數(shù)據(jù)復制到數(shù)據(jù)接收器中；然后，在數(shù)據(jù)接收器中使用基于隨機交疊策略的滑動窗口將數(shù)據(jù)流切分成子數(shù)據(jù)段；最后，對每個滑動窗口使用TSTKS算法進行多突變點檢測[15-17]。該方法集合了TSTKS算法、滑動窗口、緩沖區(qū)、隨機交疊策略，可在線快速高效檢測時序數(shù)據(jù)多突變點[18-20]。

1 理論基礎

1.1 方法概述

相比于傳統(tǒng)的離線檢測方法，本文提出了一種利用緩沖區(qū)模型和隨機交疊策略的在線檢測方法。步驟如下：(1)先構(gòu)建緩沖區(qū)模型，利用緩沖區(qū)模型接收時序數(shù)據(jù)流；(2)將緩沖區(qū)內(nèi)的數(shù)據(jù)發(fā)送到數(shù)據(jù)接收器中，在數(shù)據(jù)接收器中利用TSTKS算法和滑動窗口隨機交疊策略，對所接收到的數(shù)據(jù)流進行多突變點檢測；(3)將檢測出的突變點放入突變點集合中，并在原始數(shù)據(jù)集中標注出突變點的位置。時間序列是一個n維的集合，其可被定義為

Zn={x1，x2，x3，…，xi，…}

(1)

式中，xi代表某個數(shù)據(jù)流在i時刻的一個數(shù)據(jù)向量。當n=1時，Zn表示單變量時間序列；當n≥2時，Zn表示多變量的時序序列。系統(tǒng)框架圖如圖1所示。

圖1 基于隨機交疊策略的多突變點在線檢測方法框架圖

如圖1所示，對于在線時序數(shù)據(jù)流Z，本文首先利用緩沖區(qū)buffer將數(shù)據(jù)流復制到數(shù)據(jù)接收器中；然后，在數(shù)據(jù)接收器中使用基于交疊策略的滑動窗口對數(shù)據(jù)進行分割；隨后，在滑動窗口中使用TSTKS算法進行多突變點檢測，并將各個窗口中檢測到的突變點信息放置到的突變點集合中；最后，本文根據(jù)突變點集合中的位置信息，在原始數(shù)據(jù)流中對突變點的位置進行標記。

1.2 緩沖區(qū)設計

在線檢測模型中，數(shù)據(jù)緩沖區(qū)被用于實時接收時序數(shù)據(jù)，這些被接收的數(shù)據(jù)將在隨后被放置到數(shù)據(jù)接收器中進行多突變點檢測。緩沖區(qū)接收時序數(shù)據(jù)流的示意圖如圖2所示。

圖2 緩沖區(qū)模型設計示意圖

圖2(a)中，箭頭為數(shù)據(jù)流的流向，bufferi表示當前時刻第i個緩沖區(qū)。本文所提方法使用bufferi接收在線數(shù)據(jù)流，當緩沖區(qū)滿載后，將數(shù)據(jù)輸入到如圖2(c)所示的數(shù)據(jù)接收器中，以便進行多突變點檢測。操作時，不斷循環(huán)此過程，直至數(shù)據(jù)流結(jié)束。

本文中，緩沖區(qū)的大小僅依賴于當前的時序數(shù)據(jù)的流速。針對不同的數(shù)據(jù)流，緩沖區(qū)的大小需要靈活設置。本文將緩沖區(qū)的長度設為BS(Buffer Size)，則緩沖區(qū)長度的計算式為

BS=t×ω

(2)

式中，t為時間系數(shù)；ω表示在線數(shù)據(jù)流的流速。

1.3 滑動窗口隨機交疊策略

為了避免當突變點處于滑動窗口邊緣時的易漏檢問題，本文提出了一種基于滑動窗口的隨機交疊策略。當緩沖區(qū)接收到數(shù)據(jù)流后，先在數(shù)據(jù)接收器中新開辟一段與緩沖區(qū)大小相同的數(shù)據(jù)空間，再將緩沖區(qū)內(nèi)的數(shù)據(jù)流復制到數(shù)據(jù)接收器中，并使用基于滑動窗口的隨機交疊策略和TSTKS算法進行多突變點檢測?；瑒哟翱陔S機交疊策略示意圖如圖3所示。

圖3 基于滑動窗口隨機交疊策略示意圖

圖3中，以bufferi為例，虛線框為滑動窗口，Wi表示第i個滑動窗口的長度。在bufferi中使用多個滑動窗口，并將待檢測的數(shù)據(jù)流劃分到多個滑動窗口中，然后在每個滑動窗口中使用TSTKS算法進行多突變點檢測。黑色陰影部分為滑動窗口隨機交疊部分，Si為第i個滑動窗口和第i+1個滑動窗口隨機交疊部分的長度。隨機交疊策略中，隨機交疊參數(shù)為

Ti={ti|0

(3)

式中，Ti是隨機選取的一個數(shù)值。設當前滑動窗口的長度為Wi，則隨機交疊部分的長度Si為

Si=Ti×Wi

(4)

對于下一個滑動窗口Wi+1，定義其左邊界為WLj，右邊界為WRj，根據(jù)式(4)中得到的Si可以得到

WLj=Wi-Si

(5)

式中，i，j∈N，j=i+1 。下一個滑動窗口的長度為Wj， 則可以確定其右邊界為

WRj=WLj+Wj

(6)

至此，完成了一次交疊窗口的更替。

1.4 性能指標

為了更加直觀地突出算法的有效性，本文提出了3條性能評價指標，分別是時耗Tim、命中率Hit和平均絕對誤差(Mean Absolute Error，MAE)。時耗表示算法對整段數(shù)據(jù)完成突變點檢測耗用的時間。命中率表示正確檢測的突變點個數(shù)占預先設置的突變點個數(shù)的百分比，可以表示為

(7)

式中，cp為檢測到的正確突變點個數(shù)；N為預先設置的總的突變點個數(shù)。對于多突變點檢測算法而言，平均絕對誤差表示算法檢測出的每個滑動窗口內(nèi)突變點與實際突變點位置距離絕對值的和與N的百分比，可以表示為

(8)

式中，i、j為正整數(shù)；Test表示檢測出的突變點集合；Rel表示實際突變點集合。

2 實驗對比與分析

實驗中，首先選取不同的buffer長度，并驗證buffer長度對實驗結(jié)果有影響；隨后，對比分析滑動窗口算法與滑動窗口隨機交疊算法的多突變點檢測實驗結(jié)果，以驗證隨機交疊策略的有效性；然后，分析TSTKS算法和HWKS(Haar Wavelet and KS)算法、KS檢驗、T檢驗在加入緩沖區(qū)和隨機交疊策略后對多突變點檢測效果的影響；最后，選取癲癇病人發(fā)病狀態(tài)的部分肌電數(shù)據(jù)進行實驗分析，以驗證算法對真實數(shù)據(jù)的影響。

2.1 仿真實驗分析

2.1.1 緩沖區(qū)長度對比實驗

本實驗中，僅根據(jù)時序數(shù)據(jù)的流速來決定buffer的長度，針對不同的數(shù)據(jù)流速，需要靈活調(diào)整buffer的長度。本文對比分析了不同buffer長度對多突變點檢測結(jié)果的影響，結(jié)果如圖4所示。

(a)

圖4中，仿真數(shù)據(jù)長度為215，設置了10個突變點位置，粗方框L表示緩沖區(qū)。圖4(a)～圖4(d)分別對應不同的buffer長度，分別是29、210、211、215。從對比實驗圖中可以看出，隨著緩沖區(qū)長度逐漸增大，突變點檢測效果也逐漸變好。這是由于當緩沖區(qū)長度較小時，對于相同長度的仿真數(shù)據(jù)，需要切分的子段會增多，此時突變點位于緩沖區(qū)邊緣的概率增加，導致突變點漏檢。從該實驗結(jié)果可知，buffer長度影響多突變點檢測效果。

2.1.2 滑動窗口隨機交疊策略對比實驗

在數(shù)據(jù)接收器內(nèi)，用滑動窗口選中一段數(shù)據(jù)，隨后將時序數(shù)據(jù)切分為幾個數(shù)據(jù)子段，并將子段放置到滑動窗口中進行突變點檢測。本文對比了在滑動窗口交疊與不交疊兩種策略下的檢測結(jié)果，如圖5所示。

(a)

圖5中，仿真數(shù)據(jù)長度約為16 500，設置了10個突變點。利用緩沖區(qū)接收時序數(shù)據(jù)，在數(shù)據(jù)接收器中對數(shù)據(jù)進行多突變點檢測。粗方框內(nèi)的矮形細框為滑動窗口，在圖5(a)中滑動窗口交疊，圖5(b)中滑動窗口未交疊。從實驗結(jié)果可以看出，滑動窗口交疊策略檢測出突變點的效果明顯優(yōu)于不交疊策略檢。

2.1.3 與其他算法對比實驗

將TSTKS算法與HWKS算法、KS檢驗、T檢驗進行對比，在4種算法中均加入緩沖區(qū)模型和滑動窗口隨機交疊策略，并對仿真數(shù)據(jù)進行多突變點檢測。通過分析4種算法的時耗、命中率和相對誤差來驗證算法的有效性。各算法檢測突變點效果圖如圖6所示。

(a)

圖6中，仿真數(shù)據(jù)長度為16 500，設置了10個數(shù)據(jù)突變點，buffer的長度設置為211，滑動窗口長度設為29。如圖6所示，各算法加入緩沖區(qū)模型和隨機交疊策略后， TSTKS算法和HWKS算法可基本確定突變點的位置，而KS檢驗和T檢驗法的誤判較多，算法精度較差。在進行1 000次試驗后，得到如表1所示的實驗數(shù)據(jù)。

表1 4種算法性能指標對比表

由表1可得，加入緩沖區(qū)模型和隨機交疊策略后，TSTKS算法和HWKS算法的命中率較高，HWKS算法時耗最小，TSTKS算法次之，KS檢驗和T檢驗時耗較長，準確率較低。

2.2 病變數(shù)據(jù)流實驗分析

2.2.1 緩沖區(qū)長度對比實驗

由于模擬數(shù)據(jù)具有一定的局限性，因此本實驗基于癲癇病人的肌電數(shù)據(jù)對在線算法和離線算法進行對比測試。肌電數(shù)據(jù)來自PhysioBank數(shù)據(jù)庫，實驗中選取了癲癇病人發(fā)病初至發(fā)病結(jié)束的部分肌電 (Electromyogram，EMG)數(shù)據(jù)，數(shù)據(jù)長度為214。本實驗對真實肌電數(shù)據(jù)進行緩沖區(qū)對比實驗，緩沖區(qū)長度分別選取29、210、211、214。由于真實數(shù)據(jù)不同于模擬數(shù)據(jù)，故在本實驗中選用SF和DF來衡量算法的準確性，其中SF表示檢測到的突變點前后兩段的統(tǒng)計波動，DF表示檢測到的突變點前后兩段的細節(jié)波動，Tim表示時耗。突變點的位置往往出現(xiàn)在兩段數(shù)據(jù)統(tǒng)計波動和細節(jié)波動最大處，距離突變點越近，數(shù)值越大。實驗對比圖如圖7所示，實驗結(jié)果如表2所示。

(a)

表2 肌電數(shù)據(jù)緩沖區(qū)長度對比

由圖7和表2可知，算法基本能夠檢測出發(fā)病開始和發(fā)病結(jié)束位置的突變點，基本沒有誤檢的突變點。但對于不同的緩沖區(qū)長度，表2中的數(shù)據(jù)有較明顯的不同。隨著緩沖區(qū)長度不斷增大，時耗相對較低，但統(tǒng)計波動、細節(jié)波動有較明顯的變化，統(tǒng)計波動先增大后減小，細節(jié)波動先減小后增大。由此可知，面對真實數(shù)據(jù)時，緩沖區(qū)長度的選取將影響算法檢測多突變點的準確性。

2.2.2 與其他算法對比

本實驗中，使用真實病理數(shù)據(jù)癲癇病人的部分肌電數(shù)據(jù)作為研究對象，將TSTKS算法和HWKS算法、KS檢驗、T檢驗進行對比。本文在4種算法中均加入緩沖區(qū)模型和滑動窗口隨機交疊策略，對真實肌電數(shù)據(jù)進行多突變點檢測。通過分析各算法的時耗、統(tǒng)計波動和差值波動來驗證算法的有效性。實驗對比圖如圖8所示，實驗結(jié)果如表3所示。

(a)

表3 不種算法性能指標對比表

本實驗中將buffer長度設置為211，滑動窗口長度設為26。分析圖8和表3可知，TSTKS算法和HWKS算法基本可以檢測到肌電數(shù)據(jù)中突變點的起始位置和結(jié)束位置，KS檢驗和T檢驗對肌電數(shù)據(jù)突變點的檢測比較集中，無法較準確地檢測出突變點的起始和結(jié)束位置，說明TSTKS算法和HWKS算法對肌電真實數(shù)據(jù)的多突變點檢測效果比KS檢驗、T檢驗好。從表3可以看出，TSTKS算法檢測出的突變點位置的VF和DF相對較大且時耗較小，說明算法的整體效果較好。

3 結(jié)束語

本文將時序數(shù)據(jù)作為研究對象，在TSTKS算法基礎上引入緩沖區(qū)模型和滑動窗口隨機交疊理論，提出了一種基于隨機策略的在線突變點檢測算法。該方法利用緩沖區(qū)接收在線時序數(shù)據(jù)流，在數(shù)據(jù)接收器中使用基于隨機策略的滑動窗口切分數(shù)據(jù)，并在滑動窗口內(nèi)使用TSTKS算法進行多突變點檢測，以此來提升算法的精度。本文利用模擬數(shù)據(jù)和真實腦電數(shù)據(jù)進行仿真實驗，證明了與滑動窗口算法相比較，本文所提出的算法時耗較短，命中率較高，能夠解決面對大規(guī)模時序數(shù)據(jù)在線檢測所面臨的時耗長、精度差等問題，可作為大規(guī)模病理數(shù)據(jù)快速分析的備用方法。