二階層之動態規劃演算法快速估計改變點位置於簡單線性迴歸模型

A Two-Stage Dynamic Programming Algorithm to Estimate the Location of Change-Points for Simple Linear Regression Model

張芝瑄(Chih-Hsuan Chang) ； 張國清(Kuo-Ching Chang) ； 李宗寶(Chung-Bow Lee) ； 江翠蓮(Chui-Liang Chiang)

《Journal of Data Analysis》 9卷3期 (2014/06) Pp. 123-164

https://doi.org/10.6338/JDA.201406_9(3).0005

摘要

本論文提出二階層動態規劃演算法於簡單線性迴歸之多個改變點模型。該演算法分為兩個步驟，第一步驟為利用視窗法結合概似比函數之觀念尋找可能改變點位置的集合，即稱為候選改變點子集，再用動態規劃演算法於候選改變點子集中找出可能為真實改變點位置，第二步驟再次利用動態規劃演算法檢查此改變點附近之可能改變點，找尋真正改變點位置。對長序列之多個改變點模型，只單用動態規劃演算法在時間運算方面比較費時，而二階層動態規劃演算法可以改善運算時間。本論文將討論兩個實際例子及模擬資料。實際例子為海拔帶狀停滯水資料和代謝途徑資料兩組，而模擬資料則針對不同之樣本數、改變點個數、區間大小、斜率參數、變異數做模擬比較。結果發現在實際資料中，二階層動態規劃演算法及動態規劃演算法在改變點位置有相同的估計值，而在模擬資料上，兩者在改變點之估計誤差量差不多，然而在CPU時間上，二階層動態規劃演算法估計改變點位置的時間比動態規劃演算法最快約72.61倍，因此以視窗架構之二階層動態規劃演算法可大大的降低計算量。

關鍵字

改變點 ； 動態規劃演算法 ； 視窗法 ； 二階層動態規劃演算法

並列摘要

A fast two-stage dynamic programming (TSDP) algorithm is proposed to estimate the location of multiple change-point for a sequence of data from the simple linear regression model. The TSDP algorithm is divided into two steps. In the first step, we apply the window method for the log-likelihood ratio function to find a subset of candidate change-points, and use the dynamic programming (DP) algorithm on the chosen subset to obtain good initial change-points. In the second step, we apply the DP algorithm again for the change points near the initial chosen change points to find the exact location of change-points. The DP algorithm is time-consuming for a long sequence of data with many change-points, but the TSDP can reduce the computational time. Two real examples including Metabolic pathway data and Stagnant band height data; as well as, simulation data are investigated for DP and TSDP algorithms. We find that the estimated location of change-points for both DP and TSDP algorithms are the same in real examples, while in simulated data, both algorithms produce comparably similar errors. However, in the comparison of CPU time, the TSDP algorithm is fast and can be up to 72.61 times than DP algorithm. Thus, TSDP algorithm can substantially reduce the computation load in change-points problem.

並列關鍵字

Change-points ； Dynamic programming ； Window method ； Two-stage dynamic programming

參考文獻

謝岳霖(2009)。改變點迴歸之推論(碩士論文)。私立逢甲大學統計與精算研究所。

Aston, J. A. D.,Peng, J. Y.,Martin, D. E. K.(2012).Implied distributions in multiple change point problems.Statistics and Computing.22,981-993.

Bacon, D. W.,Watts, D. G.(1971).Estimating the transition between two intersecting straight lines.Biometrika.58(3),525-534.

Barry, D.,Hartigan, J. A.(1993).A Bayesian analysis for change-point problems.Journal of the American Statistical Association.88,309-319.

Bellman, R. E.(1957).Dynamic Programming.Princeton:Princeton University.