改進(jìn)曼-惠特尼統(tǒng)計(jì)量的變點(diǎn)檢測(cè)

廣東工業(yè)大學(xué)自動(dòng)化學(xué)院 黃觀納 徐維超 王彥光

關(guān)于時(shí)間序列數(shù)據(jù)的變點(diǎn)研究在諸多領(lǐng)域擁有廣泛的應(yīng)用。對(duì)于給定的時(shí)間序列數(shù)據(jù)，本文采用滑動(dòng)窗口思想計(jì)算型的曼-惠特尼統(tǒng)計(jì)量序列，根據(jù)加權(quán)移動(dòng)平均思想加入權(quán)重參數(shù)，得到改進(jìn)的曼-惠特尼統(tǒng)計(jì)量序列，并根據(jù)改進(jìn)型曼-惠特尼統(tǒng)計(jì)量序列的極值分布指定判定變點(diǎn)的策略。實(shí)驗(yàn)表明：參數(shù)對(duì)于檢測(cè)變點(diǎn)的性能具有雙向性，雖然提高檢測(cè)準(zhǔn)確率，但需要提高平均檢測(cè)誤差作為代價(jià)。

近年來，時(shí)間序列數(shù)據(jù)的研究是一個(gè)廣泛研究的課題，在工業(yè)生產(chǎn)，醫(yī)學(xué)，氣象，圖像，金融等領(lǐng)域起著很重要的作用。時(shí)間序列數(shù)據(jù)是一組隨著時(shí)間變化的序列數(shù)據(jù)，研究時(shí)間序列數(shù)據(jù)的性質(zhì)是否發(fā)生變化隸屬于變點(diǎn)檢測(cè)問題，在工業(yè)故障檢測(cè)，醫(yī)學(xué)中的心電圖和腦電圖，氣候方面的突發(fā)事件分析，人工智能領(lǐng)域的圖像的邊緣檢測(cè)和分割技術(shù)以及語音辨析技術(shù)都能看到兩種課題的結(jié)合。根據(jù)時(shí)間序列數(shù)據(jù)變化性質(zhì)不同，變點(diǎn)檢測(cè)模型可以分為均值突變模型和方差突變模型等；根據(jù)時(shí)間序列數(shù)據(jù)長(zhǎng)度的有限性，變點(diǎn)檢測(cè)模型可以分為離線變點(diǎn)檢測(cè)模型和在線變點(diǎn)檢測(cè)模型。

變點(diǎn)檢測(cè)早期應(yīng)用于統(tǒng)計(jì)控制過程（SPC），基于統(tǒng)計(jì)控制過程中的控制圖算法，許多經(jīng)典的變點(diǎn)檢測(cè)算法如Shewhart控制圖，CUSUM控制圖，EWMA控制圖相繼被提出并廣泛應(yīng)用于變點(diǎn)檢測(cè)領(lǐng)域。而早期的變點(diǎn)檢測(cè)算法主要基于參數(shù)方法，在某些領(lǐng)域存在著局限性。當(dāng)系統(tǒng)采集的數(shù)據(jù)難以知道服從什么分布時(shí)，不局限于系統(tǒng)采集的數(shù)據(jù)的性質(zhì)和參數(shù)的非參數(shù)方法更加適用，如Pettitt(1979)提出的一種曼-惠特尼統(tǒng)計(jì)量的非參數(shù)變點(diǎn)檢測(cè)方法，D.M.Hawkins(2003)提出的一種基于T假設(shè)檢驗(yàn)的非參數(shù)變點(diǎn)檢測(cè)模型以及ROSS提出的基于Cramer-von-Mises統(tǒng)計(jì)量與Kolmogormov-Smirnov統(tǒng)計(jì)量的非參數(shù)變點(diǎn)檢測(cè)模型等。本文的變點(diǎn)檢測(cè)模型基于曼-惠特尼統(tǒng)計(jì)量性質(zhì)并改進(jìn)，對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行離線變點(diǎn)檢測(cè)并分析影響性能的因素。

1 相關(guān)理論

1.1 變點(diǎn)檢測(cè)模型

變點(diǎn)檢測(cè)可以描述為：變點(diǎn)檢測(cè)的過程是檢測(cè)時(shí)間序列數(shù)據(jù)的性質(zhì)是否發(fā)生變化及何時(shí)發(fā)生變化的過程。給定一個(gè)由獨(dú)立同分布的隨機(jī)變量組成的時(shí)間序列，其中服從累積概率密度函數(shù)為均值，為方差，變點(diǎn)檢測(cè)數(shù)學(xué)模型如下：

定義τ為變點(diǎn)的位置，而Δ指的是這里要研究的均值突變的幅度。上述模型是變點(diǎn)離線模型，而當(dāng)n趨向無窮大時(shí)，S轉(zhuǎn)變?yōu)闀r(shí)間序列數(shù)據(jù)流，模型則可以推廣為在線變點(diǎn)模型。

1.2 曼-惠特尼統(tǒng)計(jì)量

曼惠特尼統(tǒng)計(jì)量廣泛應(yīng)用于突變點(diǎn)檢測(cè)研究，它的定義如下：給定兩個(gè)由獨(dú)立同分布的隨機(jī)變量組成的序列，，分別服從累計(jì)概率密度函數(shù)，因此曼惠特尼統(tǒng)計(jì)量可以定義為如下：

其中當(dāng)x>0時(shí)，函數(shù)I(x)取1，否則函數(shù)I(x)取0。在零假設(shè)下，當(dāng)時(shí)，，假設(shè)m和n都趨近于無窮大時(shí)，標(biāo)準(zhǔn)化后的曼惠特尼統(tǒng)計(jì)量近似服從標(biāo)準(zhǔn)正態(tài)分布。

2 利用改進(jìn)型的曼惠特尼統(tǒng)計(jì)量進(jìn)行變點(diǎn)檢測(cè)

結(jié)合上面的變點(diǎn)檢測(cè)數(shù)學(xué)模型和曼-惠特尼統(tǒng)計(jì)量的性質(zhì)，我們采用一種類似滑動(dòng)窗口的方案取獲取待檢測(cè)的時(shí)間序列的曼-惠特尼統(tǒng)計(jì)量序列。假設(shè)，對(duì)應(yīng)的曼惠特尼統(tǒng)計(jì)量Tm就可以得到，然后X,Y向右移動(dòng)一個(gè)單位，就如滑動(dòng)窗口一樣，以此類推我們可以得到曼惠特尼統(tǒng)計(jì)量序列。

當(dāng)時(shí)間序列數(shù)據(jù)S出現(xiàn)變點(diǎn)τ時(shí)，窗口X,Y移動(dòng)到出現(xiàn)變點(diǎn)區(qū)域時(shí)，曼惠特尼統(tǒng)計(jì)量序列T就會(huì)增大（向上突變），直到窗口X,Y完全處于不同的兩個(gè)分布，之后曼惠特尼統(tǒng)計(jì)量序列T就會(huì)下降，知道窗口X,Y完全離開變點(diǎn)區(qū)域。因此我們可以定義檢測(cè)的變點(diǎn)位置是曼惠特尼統(tǒng)計(jì)量序列T達(dá)到最大值的位置，即：

因此我們可以利用滑動(dòng)窗口的方法去獲取某個(gè)時(shí)間序列數(shù)據(jù)的曼-惠特尼統(tǒng)計(jì)量序列，并判斷曼惠特尼統(tǒng)計(jì)量序列最大值的位置是出現(xiàn)突變點(diǎn)的位置。但是，這種情況只是適合出現(xiàn)了突變點(diǎn)的情況，而我們還需要判斷給定的時(shí)間序列是否發(fā)生了突變，這就需要設(shè)定判斷突變點(diǎn)的閾值。參考（Hawkins D M,Qiu P,Kang C W.The Changepoint Model for Statistical Process Control），當(dāng)max(T)>thre，我們可以判定該時(shí)間序列發(fā)生了突變，這里的閾值thre我們可以根據(jù)零假設(shè)時(shí)（時(shí)間序列數(shù)據(jù)未發(fā)生突變時(shí)）的曼-惠特尼統(tǒng)計(jì)量極值分布來決定。令Tmax= max(T)，在給定虛警率α（在零假設(shè)情況下，突變點(diǎn)檢測(cè)模型允許犯錯(cuò)的概率），可得：Pr(Tmax>thre)=α，就可以從這里得出判斷突變點(diǎn)的閾值thre。

根據(jù)加權(quán)移動(dòng)平均思想，我們?cè)谏鲜龅穆?惠特尼統(tǒng)計(jì)量序列T中加入一個(gè)權(quán)重參數(shù)，改進(jìn)的曼-惠特尼統(tǒng)計(jì)量如下：

而隨著權(quán)重參數(shù)λ的加入，eTmax的分布與之前的的曼-惠特尼統(tǒng)計(jì)量Tmax有所不同，利用極值分布取獲取判定變點(diǎn)的閾值時(shí)需要令Pr(eTmax>thre)=α。

3 實(shí)驗(yàn)

3.1 變點(diǎn)檢測(cè)的性能指標(biāo)

為了不失一般性，我們需要根據(jù)蒙特卡羅模擬實(shí)驗(yàn)方法，設(shè)計(jì)一套檢驗(yàn)變點(diǎn)檢測(cè)模型的性能指標(biāo)和實(shí)驗(yàn)方案。對(duì)于變點(diǎn)檢測(cè)性能指標(biāo)的定義，選取檢驗(yàn)準(zhǔn)確率和平均誤差作為文中實(shí)驗(yàn)的變點(diǎn)檢測(cè)模型的性能指標(biāo)，它們的具體定義如下：

檢驗(yàn)準(zhǔn)確率（acc）：

平均誤差（err）：

3.2 參數(shù)λ的影響

根據(jù)文獻(xiàn)（Wang Y,Huang G,Yang J,et al.Change Point Detection with Mean Shift Based on AUC from Symmetric Sliding Windows）中的證明，當(dāng)兩個(gè)窗口長(zhǎng)度一致時(shí)，曼-惠特尼統(tǒng)計(jì)量的方差最小。令m=n=L，隨著窗口長(zhǎng)度的增大，檢驗(yàn)準(zhǔn)確率隨著增大，平均誤差逐漸減小，但到達(dá)一定長(zhǎng)度后，兩個(gè)指標(biāo)趨向穩(wěn)定。因此，取窗口長(zhǎng)度L=50，實(shí)驗(yàn)次數(shù)Ntrial=10000，模擬時(shí)間序列為高斯分布隨機(jī)序列，λ=0,0.8,0.9，均值突變幅度，Δ=[0,0.25,0.50,...,2.00]，對(duì)應(yīng)每個(gè)λ分別算出在不斷增加的Δ下的檢驗(yàn)準(zhǔn)確率與平均誤差序列，實(shí)驗(yàn)結(jié)果如圖1所示。

4 結(jié)果分析

從圖中顯示，隨著均值突變幅度增大，檢測(cè)準(zhǔn)確率逐漸增大；因?yàn)檫@里采取的實(shí)驗(yàn)?zāi)M信號(hào)服從標(biāo)準(zhǔn)高斯分布，所以就如圖顯示一樣，當(dāng)均值突變幅度為1時(shí)，檢測(cè)準(zhǔn)確率可以接近于1。相比于其他的λ=0值，當(dāng)λ=0.8,0.9時(shí)，檢測(cè)準(zhǔn)確率在均值突變幅度小于1的范圍內(nèi)表現(xiàn)優(yōu)于未加入?yún)?shù)λ。同時(shí)，檢測(cè)誤差也隨著均值突變幅度的增大而下降，隨著λ的增大，檢測(cè)平均誤差的衰減速度減緩，其中λ=0.9時(shí)衰減速度減緩的效果很明顯。加入?yún)?shù)λ可以帶來在突變幅度較小時(shí)的檢測(cè)準(zhǔn)確率的提高，到也會(huì)帶來一些誤差上的增加。

圖1 均值突變幅度

5 討論

本文融合指數(shù)加權(quán)移動(dòng)平均思想在原先的曼-惠特尼統(tǒng)計(jì)量序列加入一個(gè)參數(shù)λ，并且通過實(shí)驗(yàn)驗(yàn)證窗口長(zhǎng)度和λ參數(shù)對(duì)于變點(diǎn)檢測(cè)性能的影響。實(shí)驗(yàn)表明：λ參數(shù)在相對(duì)比較低的均值突變時(shí)可以提升變點(diǎn)檢測(cè)的準(zhǔn)確率，而需要犧牲掉檢測(cè)平均誤差，因此如何選擇λ參數(shù)需要我們?cè)谧凕c(diǎn)檢測(cè)的檢測(cè)準(zhǔn)確率和檢測(cè)平均誤差中折衷考慮。本文的實(shí)驗(yàn)僅限至于高斯隨機(jī)分布組成的時(shí)間序列數(shù)據(jù)，其他分布的時(shí)間序列數(shù)據(jù)以及實(shí)際數(shù)據(jù)后續(xù)進(jìn)行深入的探討。