Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/18745
標題: 二階層之動態規劃演算法快速估計改變點位置 於簡單線性迴歸模型
A Two-Stage Dynamic Programming Algorithm to Estimate the Location of Change-Points for Simple Linear Regression Model
作者: 張芝瑄
Chang, Chih-Hsuan
關鍵字: 改變點;Change-points;動態規劃演算法;視窗法;二階層動態規劃演算法;Dynamic programming;Window method;Two-stage dynamic programming
出版社: 統計學研究所
引用: [1]Aston, J. A. D. and Peng, J. Y. and Martin, D. E. K. (2012). Implied distributions in multiple change point problems. Statistics and Computing , 22, 981-993. [2]Bacon, D. W. and Watts, D. G. (1971). Estimating the transition between two intersecting straight lines. Biometrika, 58,3, 525-534. [3]Barry, D. and Hartigan, J. A. (1993). A Bayesian analysis for change-point problems. Journal of the American Statistical Association, 88, 309–319. [4]Bellman, R. E. (1957). Dynamic Programming, Princeton University, Princeton. [5] Chang, K. C. and Chiang, C. L. and Lee, C. B. (2012). The Comparison of Algorithms in Change-Points Problem. Journal of Applied Science and Engineering, 15, 1, 11-19. [6]Chernoff, H. and Zacks, S. (1964). Estimating the current mean of a normal distribution which is subject to changes in time. Annals of Mathematical Statistics, 35, 999-1018. [7]Cheon, S. and Kim, J. (2010). Multiple change-point detection of multivariate mean vectors with the Bayesian approach. Computational Statistics & Data Analysis, 54, 406-415. [8]Chin Choy, J. H. and Broemeling, L. D. (1980). Some Bayesian inferences for a changing linear model. Technometrics , 22, 71-78. [9]Fan, T. H. and Chang, K. C. and Lee, C. B. (2006). Bayesian Estimation of the Number of Change Points in Simple Linear Regression Models. Communication in Statistics-Theory and Methods, 35, 689-710. [10]Fearnhead, P. (2006). Exact and efficient Bayesian inference for multiple changepoint problems. Statistics and Computing , 16, 203-213 [11]Fearnhead, P. and Liu, Z. (2007). Online inference for multiple changepoint problems. Journal of the Royal Statistical Society, 69, 589-605. [12]Gyarmati-Szabo, J. and Bogachevb, L. V. and Chena, H. (2011). Modelling threshold exceedances of air pollution concentrations via non-homogeneous Poisson process with multiple change-points. Atmospheric Environment, 45, 5493-5503. [13]Hawkins, D. M. (2001). Fitting multiple change-point models to data. Computational Statistics & Data Analysis, 37, 323-341. [14]He, P. and Fang, L. and Su, Z. (2012). A sequential testing approach to detecting multiple change points in the proportional hazards model. Statistic in Medicine, 32, 1239-1245. [15]Henneken, R. and Dose, F. and Schleip, C. and Menzel, A. (2013). Detecting plant seasonality from webcams using Bayesian multiple change point analysis. Agricultural and Forest Meteorology, 168, 177-185. [16]Hinkley, D. V. (1970). Inference about the change-point in a sequence of random variables. Biometrika, 57, 1, 1-17. [17]Huang, C. Y. and Lyu, M. R. (2011). Estimation and Analysis of Some Generalized Multiple Change-Point Software Reliability Models. IEEE Transactions on Reliability, 60, 2,498. [18]Julious, S.A.(2001). Inference and estimation in a changepoint regression problem. The Statistician , 50, 51-61. [19]Lavielle, L. and Lebarbier, E. (2001). An application of MCMC methods for the multiple change-points problem. Signal Processing, 81, 39-53. [20]Lee, C. B. (1996). Nonparametric multiple change-point estimators. Statistics & probability letters, 27, 295-304. [21]Lebarbier, E. (2005). Detecting multiple change-points in the mean of Gaussian process by model selection. Signal Processing, 85, 4, 717-736. [22]Lin, J. G. and Zhu, L. X. and Xie, F. C. (2009). Heteroscedasticity diagnostics for t regression models. Metrika, 70, 59-77. [23]Lin, J. G. and Chen, J. and Li, Y. (2012). Bayesian Analysis of Student t Linear Regression with Unknown Change-Point and Application to Stock Data Analysis. Comput Econ, 40, 203-217. [24]Liu, Z. and Qian, L. (2010). Changepoint Estimation in a Segmented Linear Regression via Empirical Likelihood. Communications in Statistics- Simulation and Computation, 85-100. [25]Lombard, F. and Carroll, R. J. (1992). Change point estimation via running cusums. Technical report No. 155, Statistics Department, Texas A & M University. [26]Loschi, R.H. and Cruz, F.R.B. (2005). Extension to the product partition model: Computing the probability of a change. Computational Statistics & Data Analysis, 48, 255–268. [27]Ng, V. M. (1990). Bayesian analysis of linear model exhibiting changes in mean and precision at an unknow time points. Commun. Statist. Theor. Meth, 19, 110-120. [28]Page, E. S. (1954). Continuous inspection schemes. Biometrika, 41, 100-115. [29]Quandt, R. E. (1958). The estimation of the parameters of a linear regression system obeying two separate regimes. Journal of American Statistical Association, 53, 873-880. [30]Seber, G. A. F. and Wild, C. J. (1989) Nonlinear Regression. Wiley, New York. [31]Siegmund, D. (1988). Confidence sets in change point problem. Int. Statist. Rev, 56, 31-48. [32]Sims, C. A. and Zha, T. (2006). Were there regime switches in US monetary policy? American Economic Review , 96, 54-81. [33]Worsley, K. J. (1986). Confidence regions and tests for a change-point in a sequence of exponential family random variables. Biometrika, 73, 91-104. [34]Yang, T. Y. and Kuo, L. (2001). Bayesian binary segmentation procedure for a Poisson process with multiple change points. Journal of Computational and Graphical Statistics, 10, 772-785. [35]Zhou, H. and Liang, K. (2008). On estimating the change point in generalized linear models. Institute of Mathematical Statistics, 1, 305-320. [36]謝岳霖 (2009),改變點迴歸之推論,碩士論文,私立逢甲大學統計與精算研究所,台中。
摘要: 
本論文提出二階層動態規劃演算法於簡單線性迴歸之多個改變點模型。該演算法分為兩個步驟,第一步驟為利用視窗法結合概似比函數之觀念尋找可能改變點位置的集合,即稱為候選改變點子集,再用動態規劃演算法於候選改變點子集中找出可能為真實改變點位置,第二步驟再次利用動態規劃演算法檢查此改變點附近之可能改變點,找尋真正改變點位置。對長序列之多個改變點模型,只單用動態規劃演算法在時間運算方面比較費時,而二階層動態規劃演算法可以改善運算時間。本論文將討論兩個實際例子及模擬資料。實際例子為海拔帶狀停滯水資料和代謝途徑資料兩組,而模擬資料則針對不同之樣本數、改變點個數、區間大小、斜率參數、變異數做模擬比較。結果發現在實際資料中,二階層動態規劃演算法及動態規劃演算法在改變點位置有相同的估計值,而在模擬資料上,兩者在改變點之估計誤差量差不多,然而在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.
URI: http://hdl.handle.net/11455/18745
其他識別: U0005-1507201311184700
Appears in Collections:統計學研究所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.