基于約束HMM的變點檢測算法①

莊 玉,何振峰

(福州大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院,福州 350108)

基于約束HMM的變點檢測算法①

莊 玉,何振峰

(福州大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院,福州 350108)

時間序列的變點分析在現(xiàn)今社會各個領(lǐng)域中都有著廣泛的應(yīng)用.針對時間序列進行變點分析中要求變點狀態(tài)需要連續(xù)持續(xù)一定的時間的應(yīng)用背景,提出了一種結(jié)合狀態(tài)最短連續(xù)長度約束的隱馬爾可夫模型.給出了約束Baum-Welch訓(xùn)練算法和約束Viterbi狀態(tài)提取算法.應(yīng)用在仿真數(shù)據(jù)和GNP數(shù)據(jù)集的實驗表明,結(jié)合狀態(tài)最短連續(xù)長度約束的HMM相比于一般HMM在時間序列變點檢測中效率較高.

變點檢測;約束隱馬爾可夫模型;時間序列分割

時間序列是隨時間次序而變化的一系列數(shù)據(jù),是一類多維的復(fù)雜類型數(shù)據(jù)[1].當(dāng)所觀察的時間序列跨越時間越長時,形成的時間序列的隨機變量會由于某種條件的變化,從某時間點開始不再服從原來的分布,即出現(xiàn)了變點.隨著變點問題應(yīng)用的愈加廣泛,在一些文獻中有許多同義詞,包括了結(jié)構(gòu)斷點[2],時間序列分割[3],和檢測“異常點”[4].

時間序列的變點檢測方法可以很好的用HMM來建模,其中時間序列數(shù)據(jù)就是HMM中的輸出符號,可以通過時間序列數(shù)據(jù)來檢測所處的狀態(tài),判斷是否出現(xiàn)變點.一般的HMM對隱狀態(tài)鏈沒有任何限制,即在隱狀態(tài)鏈中可以自由的從一個狀態(tài)轉(zhuǎn)移到其他任何一個狀態(tài).這樣的HMM稱為無約束HMM.在實際工作中,需要解決的問題一般有領(lǐng)域背景.希望訓(xùn)練出的HMM符合用戶的預(yù)期.例如,在經(jīng)濟學(xué)中,至少要有兩個連續(xù)的負(fù)增長(收縮)狀態(tài),才能說這段時間處于經(jīng)濟衰退期[5];在遺傳學(xué)中,一個罕見的遺傳現(xiàn)象比如,至少要有幾百個堿基長,才能被認(rèn)為出現(xiàn)了CpG island(Aston and Martin,2007)[6].

針對于此,本文提出了一種結(jié)合狀態(tài)最短連續(xù)長度約束的隱馬爾可夫模型,一般的HMM假設(shè)時間序列是由一系列隱狀態(tài)構(gòu)成,而系統(tǒng)的運行本質(zhì)就是在不同的隱狀態(tài)間轉(zhuǎn)換,一般的HMM對隱狀態(tài)之間轉(zhuǎn)換沒有限制,本文的方法限制了狀態(tài)之間的轉(zhuǎn)換.首先擴展?fàn)顟B(tài)數(shù)為原來的倍,并在訓(xùn)練模型時加約束,限制了狀態(tài)之間轉(zhuǎn)移,這樣學(xué)習(xí)出約束HMM就自帶限制最小變點連續(xù)長度,滿足在一些特定的應(yīng)用情況下要求狀態(tài)持續(xù)的長度限制.在解碼隱狀態(tài)序列時,控制最后一個狀態(tài)一定是擴展?fàn)顟B(tài)的最后一個,就能保證只要序列中出現(xiàn)狀態(tài)變化即出現(xiàn)變點,并且狀態(tài)已經(jīng)持續(xù)至少h.并將該模型應(yīng)用在兩組已控制變點位置的模擬數(shù)據(jù)和GNP數(shù)據(jù)集,檢測其變點.

1 相關(guān)工作

變點問題的研究始于Page在Biometrika上發(fā)表的一篇關(guān)于連續(xù)抽樣檢驗的文章[7].近二十年來,變點問題的研究在理論和世紀(jì)應(yīng)用等方面有了快速的發(fā)展.理論上已有了一系列較為成熟的結(jié)果,國外的變點的應(yīng)用研究主要涉及金融股票市場檢測[8]、環(huán)境檢測[9]、醫(yī)藥與生物工程[10]、系統(tǒng)維護[11]等.我國學(xué)者對變點問題的研究始于上世紀(jì)80年代,由陳希孺教授和繆柏其教授利用“局部法”開始了變點的研究[12]．在我國對于變點問題的應(yīng)用還是很少的,只在少數(shù)領(lǐng)域中獲得了應(yīng)用,如張學(xué)新等[13]研究了最小二乘法檢測多個變點的性能,并成功檢測出1952-2003年中國主要經(jīng)濟部門GNP的變點.

對實際應(yīng)用背景下,Chib[14]和 Luong[15]提出了一種帶約束的HMM即隱狀態(tài)鏈中的狀態(tài)轉(zhuǎn)移是有一定限制的.Nam[16]提出了基于HMM的限制最小連續(xù)長度變點的定義,描述了一個基于該定義的約束HMM,但是他沒有給出明確的約束模型的定義,沒有說明狀態(tài)遷移矩陣以及訓(xùn)練該模型的算法.他是用一般的訓(xùn)練算法來學(xué)習(xí)HMM,對于限制的最小變點連續(xù)長度是在分析隱序列時來約束,而且Nam提出的模型是用來做變點的風(fēng)險分析.而本文提出的結(jié)合狀態(tài)最短連續(xù)長度的約束HMM,描述其狀態(tài)之間的遷移限制,給出了約束HMM的訓(xùn)練算法以及狀態(tài)提取算法,用來解決實際問題中對于最小狀態(tài)連續(xù)長度的限制的問題.

2 結(jié)合狀態(tài)最短連續(xù)長度約束的HMM

2.1 隱馬爾可夫模型

HMM是一種雙重隨機過程,一個是隱含的有限狀態(tài)馬爾可夫鏈即xt,它描述狀態(tài)的轉(zhuǎn)移,另一個描述狀態(tài)與觀察值之間的統(tǒng)計對應(yīng)關(guān)系.在實際問題中我們只能看到觀察值,而不能直接看到隱狀態(tài).只能通過研究觀察值序列yt去推斷隱狀態(tài)序列xt[17].隱馬爾可夫模型為一五元組其中:

狀態(tài)轉(zhuǎn)移概率矩陣:

A=(aij)N′N其中即由狀態(tài)si轉(zhuǎn)移到狀態(tài)sj的概率且

2.2 變點

使用HMM為時間序列建模,在已知隱狀態(tài)序列的情況下,時間序列變點的一般定義如定義1.

定義1.在t時刻隱狀態(tài)鏈的狀態(tài)改變,即t時刻出現(xiàn)變點,即:

然而,對于一些實際的應(yīng)用中,確定一個變點,要求這個狀態(tài)變化要持續(xù)一定的時間,比如第四部分的分析GNP數(shù)據(jù)的經(jīng)濟周期等,而用一般的HMM分析時,無法限制.在這些應(yīng)用情況下,Nam定義一個持續(xù)的變點如定義2.

定義2的兩個重要的特性:第一,與其他基于HMM 的變點方法相似,變點的分析是從隱狀態(tài)序列推斷的;第二,相比于分析隱馬爾科夫鏈的狀態(tài)變化,更重要的是分析在隱馬爾科夫鏈中最短持續(xù)長度h的狀態(tài)變化.第二個點就是本文提出結(jié)合最短連續(xù)長度約束HMM的主要思想.

2.3 結(jié)合狀態(tài)最短連續(xù)長度約束的HMM確定在時間t出現(xiàn)變點,即:

針對Nam定義的持續(xù)的變點,本文提出結(jié)合狀態(tài)最短連續(xù)長度約束的HMM,通過控制了狀態(tài)之間的轉(zhuǎn)移,來控制狀態(tài)的最短連續(xù)長度,一個約束HMM為一新的五元組

與一般HMM不同的是,約束HMM在學(xué)習(xí)狀態(tài)轉(zhuǎn)移矩陣時,對狀態(tài)之間的轉(zhuǎn)移加上了限制.如圖1為狀態(tài)數(shù)為2,h=2時的狀態(tài)轉(zhuǎn)移圖.初始狀態(tài)只能從擴展?fàn)顟B(tài)的第一個狀態(tài)開始,如圖中的s11,s21,當(dāng)處于同一個狀態(tài)時,s11只能轉(zhuǎn)移到s12,而處于s12時,說明s1這個狀態(tài)已經(jīng)持續(xù)了h=2,s12可達(dá)的狀態(tài)可以是自身s12另一個狀態(tài)的第一個擴展?fàn)顟B(tài)s21.在這樣的限制下,就可以保證一個狀態(tài)可以持續(xù)至少h=2.

圖 1 2-狀態(tài),h=2狀態(tài)轉(zhuǎn)移圖

當(dāng)h=1時,約束HMM就是一般HMM模型.

2.4 約束HMM的學(xué)習(xí)算法

Baum-Welch算法是隱馬爾科夫模型學(xué)習(xí)問題的一種常用解決方法.約束HMM的學(xué)習(xí)算法是在Baum-Welch算法基礎(chǔ)上加入狀態(tài)最短連續(xù)長度的約束.訓(xùn)練約束HMM的過程如下:

2)計算輔助變量:

3)參數(shù)更新,重估公式:

與一般HMM不同,由于隱狀態(tài)擴展為原來的h倍,初始狀態(tài)只能從開始,即m11時,.

在每次循環(huán)的參數(shù)重估結(jié)束后,都要修改轉(zhuǎn)移矩陣 A:當(dāng)i=j時,當(dāng)如果其他情況下當(dāng)時,當(dāng)m=1,n=h或者時,其他情況下控制狀態(tài)之間的轉(zhuǎn)移.

本文的方法與一般的Baum-Welch算法不同的地方就在于在參數(shù)重估步驟中,對初始概率,輸出矩陣和狀態(tài)轉(zhuǎn)移矩陣的修改.

2.5 約束HMM的狀態(tài)提取算法

解決給定模型及觀測序列O,求生成此觀測序列的最大可能的隱狀態(tài)序列,一般采用的是Viterbi算法,解碼最大可能的隱狀態(tài)序列.

在分析隱狀態(tài)序列變點時,有兩種情況一種是隱狀態(tài)序列最后一個狀態(tài)允許是一半狀態(tài),另一種是狀態(tài)必須滿足h個,本文的方法是用到后一種情況來分析Viterbi序列.限制了隱狀態(tài)序列最后一個狀態(tài)一定是擴展?fàn)顟B(tài)的最后一個狀態(tài),保證了最后一個狀態(tài)的持續(xù)時間也不小于h.算法1為約束HMM的狀態(tài)提取算法.

與一般HMM不同的是,約束HMM要限制隱狀態(tài)序列最后一個狀態(tài)一定是擴展?fàn)顟B(tài)的最后一個狀態(tài),即一定是sih,本文狀態(tài)提取算法與Viterbi算法不同之處是把其他擴展?fàn)顟B(tài)的設(shè)置為 -1.

3 實驗

3.1 實驗設(shè)計與數(shù)據(jù)準(zhǔn)備

為了驗證本文提出的約束HMM比一般的HMM在檢測實際應(yīng)用上的便捷性,我們將約束HMM應(yīng)用到實際數(shù)據(jù)的處理與分析工作之中.

實驗中用到的數(shù)據(jù)集:

①已控制變點位置的模擬數(shù)據(jù),變點出現(xiàn)在t=10, t=20處.

第一組序列:

第二組序列:

根據(jù)經(jīng)濟周期理論,一個完整的經(jīng)濟周期應(yīng)包括復(fù)蘇、高漲、衰退、蕭條等四個階段,故將GNP數(shù)據(jù)即觀測序列離散化為四個觀測值,離散化的結(jié)果如圖2.

圖 2 離散化后的GNP數(shù)據(jù)

基于約束HMM的變點檢測方法步驟:

① 數(shù)據(jù)集,整理數(shù)據(jù)

②初始化約束HMM

③ 用約束Baum-Welch算法訓(xùn)練約束HMM

④ 用約束Viterbi算法解碼隱狀態(tài)序列

⑤ 根據(jù)實際應(yīng)用背景分析隱狀態(tài)序列變點

3.2 實驗結(jié)果及分析

3.2.1 分別用約束HMM和HMM分析模擬數(shù)據(jù)

第一組序列:

用HMM為觀察序列建模,得出隱狀態(tài)鏈得到的是:

設(shè)定h=3,約束HMM得到的隱狀態(tài)鏈為:

第二組序列:

用HMM得到隱狀態(tài)鏈得到的是:

用約束HMM得到的隱狀態(tài)鏈為:

對比序列1和2的結(jié)果,一般HMM容易檢測出小波動的變點,即狀態(tài)改變只有一兩個時間點,容易檢測出額外的變點如t=1,t=29,而使用約束HMM就能夠準(zhǔn)確地檢測到變點的位置,并保證了狀態(tài)至少持續(xù)了h=3時間.

3.2.2 分別用約束HMM和HMM分析GNP數(shù)據(jù)的經(jīng)濟周期

根據(jù)離散化的GNP數(shù)據(jù),觀測值有四個為(“F”,“G”,“S”,“X”)分別代表一個完整經(jīng)濟周期的四個階段:復(fù)蘇、高漲、衰退和蕭條.隱狀態(tài)為(“K”,“S”)分別代表經(jīng)濟活動的擴張和收縮狀態(tài).在要求限定下,設(shè)置h=2.約束HMM隱狀態(tài)擴展為(“K1”,“K2”,“S1”,“S2”).

用一般的HMM檢測到的變點分布如圖3所示.

圖 3 一般HMM檢測到的變點分布

從圖3可觀察到檢測出了12個變點,分別分布在1951/2～1952/2,1953/3～1954/2,1955/4～1958/2,1959/3～1 959/4,1960/2～1960/4,1962/4,1968/3～1970/4,1971/2～197 1/4,1973/2～1975/1,1977/4～1978/1,1978/3～1980/3,1981/ 2～1982/4,1984/3～1984/4

基于約束HMM檢測到的變點如圖4.

圖 4 約束HMM檢測到的變點分布

檢測出 8個變點分別分布在 1953/2～1954/2, 1957/2～1958/1,1960/2～1960/1,1969/4～1970/2,1971/2～ 1971/4,1973/3～1975/1,1979/1～1980/2,1981/2～1982/3.

由一般HMM檢測到的變點和約束HMM檢測到的變點對比分析可得到,一般HMM檢測到的變點,無法滿足經(jīng)濟周期拐點的定義,即無法滿足經(jīng)濟周期的衰退期至少持續(xù)兩個季度,比如變點1962/4,該變點只有一個季度,無法判定為經(jīng)濟周期,并且變點與變點之間相距時間太短,如 1977/4～1978/1和1978/3～1980/3之間,約束HMM因為限制了h故不會出現(xiàn)這種情況.還可以觀察到一般HMM會把數(shù)據(jù)開始和結(jié)束當(dāng)做變點,這在約束HMM結(jié)果中不會出現(xiàn).

4 結(jié)語

基于一般HMM的變點檢測方法沒有考慮到實際應(yīng)用背景中要求變點狀態(tài)持續(xù)一定時間,比如本文實驗中檢測經(jīng)濟周期時,需要衰退期至少持續(xù)兩個季度.本文提出結(jié)合狀態(tài)最短連續(xù)長度約束HMM通過控制狀態(tài)之間的轉(zhuǎn)移,能夠有效的檢測出時間序列的變點,并且滿足相關(guān)應(yīng)用背景對狀態(tài)持續(xù)一定時間的要求.實驗結(jié)果表明,較之一般HMM,約束HMM在保證檢測變點準(zhǔn)確度前提下,滿足了狀態(tài)最短持續(xù)時間,提高了變點檢測效率.

1 Janacek G.Time series analysis forecasting and control. Journal of Time SeriesAnalysis,2010,31(4):303.

2 Davis RA,Lee TCM,Rodriguez-Yam G A.Structural break estimation for nonstationary time series models.Journal of theAmerican StatisticalAssociation,2006,101(473):223–239.

3 Cheong SA,Fornia RP,Lee GHT,et al.The Japanese economy in crises:A time series segmentation study. Economics:The Open-Access,Open-Assessment E-Journal, 2012,6(2012-5):1–81.

4 Zaccarelli N,Li BL,Petrosillo I,et al.Order and disorder in ecologicaltime-series:Introducing normalized spectral entropy.Ecological Indicators,2013,28(5):22–30.

5 Stock JH,Watson M W.Has the business cycle changed and why?Nber MacroeconomicsAnnual,2002,17(1):159–218.

6 Aston JAD,Martin DEK.Distributions associated with general runs and patterns in hidden Markov models.Annals ofApplied Statistics,2007,1(2):585–611.

7 Page ES.Continuous inspection schemes.Biometrika,1954, 41(1/2):100–115.

8 Tseng YH,Durbin P,Tzeng GH.Using a fuzzy piecewise regression analysis to predict the nonlinear time-series of turbulent flows with automatic change-point detection.Flow Turbulence&Combustion,2001,67(2):81–106.

9 Leonte D,Nott DJ,Dunsmuir WTM.Smoothing and change point detection for gamma ray count data.Mathematical Geology,2003,35(2):175–194.

10 Patra K,Dey DK.A general class of change point and change curve modeling for life time data.Annals of the Institute of Statistical Mathematics,2002,54(3):517–530.

11 Moltchanov D.State description of wireless channels using change-point statistical tests. Wired/wireless Internet Communications,2006,(3970):275–286.

12陳希孺.只有一個轉(zhuǎn)變點的模型的假設(shè)檢驗和區(qū)間估計.中國科學(xué),1988,31(8):817–827.

13張學(xué)新,段志霞.最小二乘法對多變點檢驗的性能研究.河南師范大學(xué)學(xué)報:自然科學(xué)版,2009,37(6):7–10.

14 Chib S.Estimation and comparison of multiple change-point models.Journal of Econometrics,1998,86(2):221–241.

15 Luong TM,Rozenholc Y,Nuel G.Fast estimation of posterior probabilities in change-point analysis through a constrained hidden Markov model.Computational Statistics &DataAnalysis,2013,(68):129–140.

16 Nam CFH,Aston JAD,Johansen AM.Quantifying the uncertainty in change points.Journal of Time Series Analysis,2012,33(5):807–823.

17 Concha OP,Xu RYD,Moghaddam Z,et al.HMM-MIO:An enhanced hidden Markov model for action recognition. CVPR Workshops,2011:62–69.

Change Point Detection Based on Constrained Hidden Markov Model

ZHUANG Yu,HE Zhen-Feng

(School of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China)

The change point detection of time series is widely applied in various fields.In some applications,a minimum period is required before a state change.Motivated by such applications,a constrained Hidden Markov Model,which combines with the shortest state continuous length constraint,is proposed in this study.Moreover,a constrained Baum-Welch training algorithm and a constrained Viterbi state extraction algorithm are also given.And experimental results based on the simulation data and GNP data sets indicate that the constrained HMM has higher performance than the general HMM.

change point detection;constrained Hidden Markov Model;time series segmentation

2016-08-06;收到修改稿時間:2016-09-20

10.15888/j.cnki.csa.005712