Time Series Classification Algorithm Based on Linear Segmentation and HMM
YIN Rui1, LI Xiong-Fei1, LI Jun1, PENG Hong2
1.Key Laboratory of Symbolic Computation and Knowledge Engineering Ministry of Education College of Computer Science and Technology,Jilin University,Changchun 130012 2.Cyber Educational College,Xinjiang Normal University,Wulumuqi 830054
Abstract The multi-segment linear (MSL) feature of the time series are collected, and a time series classification algorithm is proposed, which consists of derivative estimation function, linear segmentation method and DDHMM model (base on HMM). Firstly, the derivative estimation function and the linear segmentation method can be used together to detect the MSL feature. If they are matched, time series can be converted into observed sequence with a special structure. Next, the training observed sequences can be used to train DDHMM models. After training, the time series are classified through comparing the probability value of testing observed sequences generated by each model. The experimental results show that the proposed algorithm has a high accuracy when classifying the time series that match the MSL feature, and it has good performance in the classification on the UCI dataset and the actual projects.
[1] Itakura F.Minimum Prediction Residual Principle Applied to Speech Recognition.IEEE Trans on Acoustics,Speech and Signal Process,1975,23(1): 67-72 [2] Yang Yiming,Pan Rong,Pan Jialin,et al.A Comparative Study on Time Series Classification.Chinese Journal of Computers,2007,30(8): 1259-1265 (in Chinese) (杨一鸣,潘 嵘,潘嘉林,等.时间序列分类问题的算法比较.计算机学报,2007,30(8): 1259-1265) [3] Myers C,Rabiner L,Roseneberg A.Performance Tradeoffs in Dynamic Time Warping Algorithms for Isolated Word Recognition.IEEE Trans on Acoustics Signal Processing,1980,28(6): 623-635 [4] Rabiner L R.A Tutorial on Hidden Markov Models and Selected Application in Speech Recognition // Proc of the IEEE,1989,77(2): 257-286 [5] Deller J R,Hansen H L,Proakis J G.Discrete-Time Processing of Speech Signals.New York,USA: Macmillan,1993 [6] Bahl L,Brown P,de Souza P,et al.Maximum Mutual Information Estimation of Hidden Markov Model Parameters for Speech Recognition // Proc of the IEEE International Conference on Acoustics,Speech,and Signal Processing.Tokyo,Japan,1986: 49-52 [7] Gauvain J L,Lee C H.MAP Estimation of Continuous Density HMM: Theory and Application // Proc of the DARPA Speech and Natural Language Workshop.Harriman,USA: Morgan Kaufman,1992: 185-190 [8] Saul L,Rahim M.Maximum Likelihood and Minimum Classification Error Rate Factor Analysis for Automatic Speech Recognition.IEEE Trans on Speech and Audio Processing,2000,8(2): 115-125 [9] Brants T.Estimating Markov Model Structures // Proc of the 4th Conference on Spoken Language Processing.Philadelphia,USA,1996: 893-896 [10] Bicego M,Murino V,Figueiredo M.A Sequential Pruning Strategy for the Selection of the Number of States in Hidden Markov Models.Pattern Recognition Letters,2003,24(9): 1395-1407 [11] Atlas L,Ostendorf M,Bernard G D.Hidden Markov Models for Monitoring Machining Tool-Wear // Proc of the IEEE International Conference on Acoustics,Speech and Signal Processing.Istanbul,Turkey,2000: 3887-3890 [12] LeGland F,Mevel L.Fault Detection in Hidden Markov Models: A Local Asymptotic Approach // Proc of the 39th IEEE Conference on Decision and Control.Sydney,Australia,2000,5: 4686-4690 [13] Dempster A P,Laird N M,Rubin D B.Maximum Likelihood from Incomplete Data via the EM Algorithm.Journal of the Royal Statistical Society,Series B (Methodological),1977,39(1): 1-38 [14] Mitrovic D.Reliable Method for Driving Events Recognition.IEEE Trans on Intelligent Transportation System,2005,6(2): 198-205 [15] Abou-Moustafa K T,Cheriet M,Suen C Y.On the Structure of Hidden Markov Models.Pattern Recognition Letters,2004,25(8): 923-931 [16] Jger M,Knoll C,Hamprecht F.Weakly Supervised Learning of a Classifier for Unusual Event Detection.IEEE Trans on Image Processing,2008,17(9): 1700-1708 [17] Beyreuther M,Wassermann J.Continuous Earthquake Detection and Classification Using Discrete Hidden Markov Models.Geophysical Journal International,2008,175(3): 1055-1066 [18] Lin T H,Kaminski N,Bar-Joseph Z.Alignment and Classification of Time Series Gene Expression in Clinical Studies // Proc of the 16th ISMB Conference on Intelligent Systems for Molecular Biology.Toronto,Canada,2008: 147-155
2011, Vol. 24 
