Journal of Applied Science and Engineering

Published by Tamkang University Press

ESCI jase impact factor scopus logo open access rate of Scopus journal

The Comparison of Algorithms in Change-Points Problem

 2012

 Volume 15, Issue 1

Kuo-Ching Chang1, Chui-Liang Chiang2 and Chung-Bow Lee1

1Department of Applied Mathematics, National Chung Hsing University, Taichung, Taiwan 402, R.O.C.

2Department 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

上傳圖片

The plot of Dj measure for window length A=8,12 and 16.

 Copyright The Author(s). This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY 4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are cited.

Download Citation:  BibTeX | http://dx.doi.org/10.6180/jase.2012.15.1.02  

Download PDF

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

  1. [1] Hawkins, D. M., “Fitting Multiple Change-Point Models to Data,” Comput Stat Data Anal., Vol. 37, pp. 323-341 (2001).
  2. [2] Venter, J. and Steel, S., “Finding Multiple Abrupt Change-Points,” Comput Stat Data Anal., Vol. 22, pp. 481-504 (1996).
  3. [3] Hawkins, D. M., “On the Choice of Segments in Piecewise Approximation,” J Inst Maths Applics., Vol. 9, pp. 250-256 (1972).
  4. [4] Juang, B. H. and Rabiner, L. R., “The Segmental K-Means Algorithm for Estimating Parameters of Hidden Markov Models,” IEEE Trans Acoust Speech Signal Proc., Vol. 38, pp. 1639-1641 (1990).
  5. [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. [6] Lee, C.-B., “Nonparametric Multiple Change-Point Estimators,” Stat Probab Lett., Vol. 27, pp. 295-304 (1996).
  7. [7] Bellman, R., Dynamic Programming, Princeton University, Princeton (1957).
  8. [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. [9] Forney, G. D., “The Viterbi Algorithm,” Proc IEEE, Vol. 61, pp. 268-278 (1973).
  10. [10] Lee, C.-B., “Estimating the Number of Change-Point in Exponential Families Distributions,” Scand J Stat., Vol. 24, pp. 201-210 (1997).