Please use this identifier to cite or link to this item:
A Two-Stage Dynamic Programming Algorithm to Estimate the Location of Change-Points for Simple Linear Regression Model
|關鍵字:||改變點;Change-points;動態規劃演算法;視窗法;二階層動態規劃演算法;Dynamic programming;Window method;Two-stage dynamic programming||出版社:||統計學研究所||引用:||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. Bacon, D. W. and Watts, D. G. (1971). Estimating the transition between two intersecting straight lines. Biometrika, 58,3, 525-534. Barry, D. and 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 University, Princeton.  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. 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. 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. Chin Choy, J. H. and Broemeling, L. D. (1980). Some Bayesian inferences for a changing linear model. Technometrics , 22, 71-78. 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. Fearnhead, P. (2006). Exact and efﬁcient Bayesian inference for multiple changepoint problems. Statistics and Computing , 16, 203-213 Fearnhead, P. and Liu, Z. (2007). Online inference for multiple changepoint problems. Journal of the Royal Statistical Society, 69, 589-605. 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. Hawkins, D. M. (2001). Fitting multiple change-point models to data. Computational Statistics & Data Analysis, 37, 323-341. 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. 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. Hinkley, D. V. (1970). Inference about the change-point in a sequence of random variables. Biometrika, 57, 1, 1-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. Julious, S.A.(2001). Inference and estimation in a changepoint regression problem. The Statistician , 50, 51-61. Lavielle, L. and Lebarbier, E. (2001). An application of MCMC methods for the multiple change-points problem. Signal Processing, 81, 39-53. Lee, C. B. (1996). Nonparametric multiple change-point estimators. Statistics & probability letters, 27, 295-304. Lebarbier, E. (2005). Detecting multiple change-points in the mean of Gaussian process by model selection. Signal Processing, 85, 4, 717-736. Lin, J. G. and Zhu, L. X. and Xie, F. C. (2009). Heteroscedasticity diagnostics for t regression models. Metrika, 70, 59-77. 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. Liu, Z. and Qian, L. (2010). Changepoint Estimation in a Segmented Linear Regression via Empirical Likelihood. Communications in Statistics- Simulation and Computation, 85-100. Lombard, F. and Carroll, R. J. (1992). Change point estimation via running cusums. Technical report No. 155, Statistics Department, Texas A & M University. 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. 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. Page, E. S. (1954). Continuous inspection schemes. Biometrika, 41, 100-115. 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. Seber, G. A. F. and Wild, C. J. (1989) Nonlinear Regression. Wiley, New York. Siegmund, D. (1988). Confidence sets in change point problem. Int. Statist. Rev, 56, 31-48. Sims, C. A. and Zha, T. (2006). Were there regime switches in US monetary policy? American Economic Review , 96, 54-81. Worsley, K. J. (1986). Confidence regions and tests for a change-point in a sequence of exponential family random variables. Biometrika, 73, 91-104. 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. Zhou, H. and Liang, K. (2008). On estimating the change point in generalized linear models. Institute of Mathematical Statistics, 1, 305-320. 謝岳霖 (2009)，改變點迴歸之推論，碩士論文，私立逢甲大學統計與精算研究所，台中。||摘要:||
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.
|Appears in Collections:||統計學研究所|
Show full item record
TAIR Related Article
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.