The Comparison of Algorithms in Change-Points Problem

Kuo-Ching Chang; Chui-Liang Chiang; Chung-Bow  Lee

doi:10.6180/jase.2012.15.1.02

The Comparison of Algorithms in Change-Points Problem

Kuo-Ching Chang¹, Chui-Liang Chiang² and Chung-Bow Lee This email address is being protected from spambots. You need JavaScript enabled to view it.¹

¹Department of Applied Mathematics, National Chung Hsing University, Taichung, Taiwan 402, R.O.C.
²Department of Food Science and Technology, Central Taiwan University of Science and Technology, Taichung, Taiwan 406, R.O.C.

Received: December 30, 2010
Accepted: June 23, 2011
Publication Date: March 1, 2012

Download Citation: ||https://doi.org/10.6180/jase.2012.15.1.02

ABSTRACT

A fast two-stage (TS) algorithm by window method is proposed. First, we apply the window method by using the log-likelihood ratio measure to find a subset of candidate change-points; and use dynamic programming (DP) algorithm on the chosen subset to obtain good initial change-points which will be proximate to the locations of the true change-points. Secondary, the segmental K-means (SKM) algorithm is applied on the initial change-points obtained in the first stage. Some simulated data sets are investigated for four algorithms and the results show that our algorithm works very well. In the comparison of CPU times, our TS algorithm is fast and can be up to 19.07 times than the speed of DP algorithm.

Keywords: Change-Points, Exponential Family, Dynamic Programming, Segmental K-Means

REFERENCES

[1] Hawkins, D. M., “Fitting Multiple Change-Point Models to Data,” Comput Stat Data Anal., Vol. 37, pp. 323 341 (2001).
[2] Venter, J. and Steel, S., “Finding Multiple Abrupt Change-Points,” Comput Stat Data Anal., Vol. 22, pp. 481 504 (1996).
[3] Hawkins, D. M., “On the Choice of Segments in Piecewise Approximation,” J Inst Maths Applics., Vol. 9, pp. 250 256 (1972).
[4] Juang, B. H. and Rabiner, L. R., “The Segmental KMeans Algorithm for Estimating Parameters of Hidden Markov Models,” IEEE Trans Acoust Speech Signal Proc., Vol. 38, pp. 1639 1641 (1990).
[5] Lombard, F. and Carroll, R. J., “Change-Point Estimation via Running Cusums,” Technical report No. 155, Statistics Department, Texas A&M University (1992).
[6] Lee, C.-B., “Nonparametric Multiple Change-Point Estimators,” Stat Probab Lett., Vol. 27, pp. 295 304 (1996).
[7] Bellman, R., Dynamic Programming, Princeton University, Princeton (1957).
[8] Viterbi, A. J., “Error Bounds for Convolutional Codes and an Asymtotically Optimum Decoding Algorithm,” IEEE Trans Inf Theory, Vol. 13, pp. 260 267 (1967).
[9] Forney, G. D., “The Viterbi Algorithm,” Proc IEEE, Vol. 61, pp. 268 278 (1973).
[10] Lee, C.-B., “Estimating the Number of Change-Point in Exponential Families Distributions,” Scand J Stat., Vol. 24, pp. 201-210 (1997).