Clustering-Inverse: A Generalized Model for Pattern-Based Time Series Segmentation

Zhaohong Deng, Fu-Lai Chung, Shitong Wang

.

DOI: 10.4236/jilsa.2011.31004                

Abstract

Patterned-based time series segmentation (PTSS) is an important task for many time series data mining applications. In this paper, according to the characteristics of PTSS, a generalized model is proposed for PTSS. First, a new inter-pretation for PTSS is given by comparing this problem with the prototype-based clustering (PC). Then, a novel model, called clustering-inverse model (CI-model), is presented. Finally, two algorithms are presented to implement this model. Our experimental results on artificial and real-world time series demonstrate that the proposed algorithms are quite effective.

Keywords

Pattern-Based Time Series Segmentation, Clustering-Inverse, Dynamic Time Warping, Perceptually Important Points, Evolution Computation, Particle Swarm Optimization, Genetic Algorithm

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	D. Gubbins, “Time Series Analysis and Inverse Theory for Geophysicists,” Cambridge University Press, New York, 2004.
[2]	J. Kennedy and R. C. Eberhart, “A Discrete Version of the Particle Swarm Algorithm,” Proceedings of the Confe-rence on Systems, Man and Cybernetics, Orlando, 12-15 Octo-ber 1997, pp. 4104-4109.
[3]	S. D. Kim, J. W. Lee, J. W. Lee and J. Chae, “A Two-Phase Stock Trading System Using Dis-tributional Differences,” Lecture Notes in Computer Science, Vol. 2453, 2002, pp. 399-423. doi:10.1007/3-540-45801-8_39
[4]	J. Abonyi, B. Feil, S. Nemeth and P. Arva, “Modified Gath-Geva Clustering for Fuzzy Segmentation of Multivariate Time-Series,” Fuzzy Sets and Systems, Vol. 149, No. 1, 2005, pp.39-56. doi:10.1016/j.fss.2004.07.008
[5]	S. W. Kim and B. S. Jeong, “Performance Bottleneck of Subsequence Matching in Time-Series Databases: Observation, Solution, and Performance Evaluation,” Information Sciences, Vol. 177, No. 22, 2007, pp. 4841-4858. doi:10.1016/j.ins.2007.06.032
[6]	E. Keogh and S. Kasetty, “On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration,” Data Mining and Knowledge Discovery, Vol. 7, No. 4, 2002, pp. 349-371. doi:10.1023/A:1024988 512476
[7]	R. Bellman, “On the Approximation of Curves by Line Segments Using Dynamic Programming,” Communications of the ACM, Vol. 4, No. 6, 1961, p. 284. doi:10.11 45/366573.366611
[8]	J. Himberg, K. Korpiaho, H. Mannila, J. Tikanmaki and H. T. T. Toivonen, “Time-Series Segmentation for Context Recognition in Mobile Devices,” Proceedings of IEEE Conference on Data Mining, 2001, pp. 203-210. doi:10.1109/ICDM.2001.989520
[9]	C. L. Fancoua and J. C. Principe, “A Neighborhood Map of Competing One Step Predictors for Piecewise Segmentation and Identification of Time Series,” Proceedings of IEEE International Conference on Neural Networks, 1996, pp. 1906-1911.
[10]	L. Feng, K. Ju and K. H. Chon, “A Method for Segmentation of Switching Dynamic Modes in Time Series,” IEEE Transactions on Systems, Man and Cybernetics, Part B: Cybernetics, Vol. 35, No. 5, 2005, pp. 1058-1064. doi:10.1109/TSMCB.2005.850174
[11]	T. C. Fu, F. L. Chung, V. Ng and R. Luk, “Evolutionary Segmentation of Financial Time Series into Subsequences,” Proceedings of 2001 Congress on Evolutionary Computation, Seoul, 27-30 May 2001, pp. 426-430.
[12]	F. L. Chung, T. C. Fu, V. Ng and R. Luk, “An Evolutionary Approach to Pattern-Based Time Series Segmen-tation,” IEEE Transactions on Evolutionary Computation, Vol. 8, No. 5, 2004, pp. 471-489. doi:10.1109/TEVC.20 04.832863
[13]	D. Berndt and J. Clifford, “Using Dynamic Time Warping to Find Patterns in Time Series,” Proceedings of AAAI-94 Workshop on Knowledge Discovery in Databases, 1994, pp. 229-248.
[14]	M. Sato, Y. Sato and L. C. Jain, “Fuzzy Clustering Models and Applications,” Physica-Verlag, New York, 1997.
[15]	D. Zhang and S. K. Pal, “A Fuzzy Clustering Neural Networks System Design Methodology,” IEEE Transactions on Neural networks, Vol. 11, 2002, pp. 1174-1177. doi:10.1109/72.870048
[16]	C. Wang and S. Wang, “Supporting Content-Based Searches on Time Series via Approximation,” Proceedings of the 12th International Conference on Scientific and Statistical Database Management, Berlin, 26-28 July 2002, pp. 69-81.
[17]	J. Himberg, K. Kor-piaho, H. Mannila, J. Tikanmaki and H. T. T. Toivonen, “Time-Series Segmentation for Context Recognition in Mobile Devices,” Proceedings of IEEE Conference on Data Mining, 2001, pp. 203-210. doi:10.1109/ICDM.2001.989520
[18]	G. Kollios, M. Vlachos and G. Gunopulos, “Discovering Similar Multidimensional Trajectories,” Proceedings of 18th Interna-tional Conference on Data Engineering, 2002.