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

莊 玉,何振峰

(福州大學 數學與計算機科學學院,福州 350108)

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

莊 玉,何振峰

(福州大學 數學與計算機科學學院,福州 350108)

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

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

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

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

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

1 相關工作

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

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

2 結合狀態最短連續長度約束的HMM

2.1 隱馬爾可夫模型

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

狀態轉移概率矩陣:

A=(aij)N′N其中即由狀態si轉移到狀態sj的概率且

2.2 變點

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

定義1.在t時刻隱狀態鏈的狀態改變,即t時刻出現變點,即:

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

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

2.3 結合狀態最短連續長度約束的HMM確定在時間t出現變點,即:

針對Nam定義的持續的變點,本文提出結合狀態最短連續長度約束的HMM,通過控制了狀態之間的轉移,來控制狀態的最短連續長度,一個約束HMM為一新的五元組

與一般HMM不同的是,約束HMM在學習狀態轉移矩陣時,對狀態之間的轉移加上了限制.如圖1為狀態數為2,h=2時的狀態轉移圖.初始狀態只能從擴展狀態的第一個狀態開始,如圖中的s11,s21,當處于同一個狀態時,s11只能轉移到s12,而處于s12時,說明s1這個狀態已經持續了h=2,s12可達的狀態可以是自身s12另一個狀態的第一個擴展狀態s21.在這樣的限制下,就可以保證一個狀態可以持續至少h=2.

圖 1 2-狀態,h=2狀態轉移圖

當h=1時,約束HMM就是一般HMM模型.

2.4 約束HMM的學習算法

Baum-Welch算法是隱馬爾科夫模型學習問題的一種常用解決方法.約束HMM的學習算法是在Baum-Welch算法基礎上加入狀態最短連續長度的約束.訓練約束HMM的過程如下:

2)計算輔助變量:

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

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

在每次循環的參數重估結束后,都要修改轉移矩陣 A:當i=j時,當如果其他情況下當時,當m=1,n=h或者時,其他情況下控制狀態之間的轉移.

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

2.5 約束HMM的狀態提取算法

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

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

與一般HMM不同的是,約束HMM要限制隱狀態序列最后一個狀態一定是擴展狀態的最后一個狀態,即一定是sih,本文狀態提取算法與Viterbi算法不同之處是把其他擴展狀態的設置為 -1.

3 實驗

3.1 實驗設計與數據準備

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

實驗中用到的數據集:

①已控制變點位置的模擬數據,變點出現在t=10, t=20處.

第一組序列:

第二組序列:

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

圖 2 離散化后的GNP數據

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

① 數據集,整理數據

②初始化約束HMM

③ 用約束Baum-Welch算法訓練約束HMM

④ 用約束Viterbi算法解碼隱狀態序列

⑤ 根據實際應用背景分析隱狀態序列變點

3.2 實驗結果及分析

3.2.1 分別用約束HMM和HMM分析模擬數據

第一組序列:

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

設定h=3,約束HMM得到的隱狀態鏈為:

第二組序列:

用HMM得到隱狀態鏈得到的是:

用約束HMM得到的隱狀態鏈為:

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

3.2.2 分別用約束HMM和HMM分析GNP數據的經濟周期

根據離散化的GNP數據,觀測值有四個為(“F”,“G”,“S”,“X”)分別代表一個完整經濟周期的四個階段:復蘇、高漲、衰退和蕭條.隱狀態為(“K”,“S”)分別代表經濟活動的擴張和收縮狀態.在要求限定下,設置h=2.約束HMM隱狀態擴展為(“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檢測到的變點,無法滿足經濟周期拐點的定義,即無法滿足經濟周期的衰退期至少持續兩個季度,比如變點1962/4,該變點只有一個季度,無法判定為經濟周期,并且變點與變點之間相距時間太短,如 1977/4～1978/1和1978/3～1980/3之間,約束HMM因為限制了h故不會出現這種情況.還可以觀察到一般HMM會把數據開始和結束當做變點,這在約束HMM結果中不會出現.

4 結語

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

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陳希孺.只有一個轉變點的模型的假設檢驗和區間估計.中國科學,1988,31(8):817–827.

13張學新,段志霞.最小二乘法對多變點檢驗的性能研究.河南師范大學學報:自然科學版,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