research-article

Hidden markov model-based time series prediction using motifs for detecting inter-time-serial correlations

Authors:

Stefan ConradAuthors Info & Claims

SAC '12: Proceedings of the 27th Annual ACM Symposium on Applied Computing

Pages 158 - 164

https://doi.org/10.1145/2245276.2245308

Published: 26 March 2012 Publication History

Abstract

This paper presents an approach for time series prediction using a Hidden Markov Model, which bases on inter-time-serial correlations. These correlations between time series of a given database are automatically discovered by hierarchically clustering motif-based time series representations, which can be used for the prediction of the future development of one time series on base of known values from the one and correlated time series. The functionality and the influence of the different parameters of the motif-based representation, the inter-time-serial correlation discovery and the prediction capability are evaluated on two large databases of river level measurements and stock data.

References

[1]

R. Agrawal, T. Imielinski, and A. N. Swami. Mining association rules between sets of items in large databases. In Proc. ACM SIGMOD Int. Conf., pages 207--216, Washington, D.C., 1993.

Digital Library

[2]

P. Anderer et al. An e-health solution for automatic sleep classification according to rechtschaffen and kales: validation study of the somnolyzer 24 x 7 utilizing the siesta database. Neuropsychobiology, 51(3): 115--33, 2005.

[3]

F. Bodon. A trie-based apriori implementation for mining frequent item sequences. In Proc. of ACM SIGKDD International Workshop on Open Source Data Mining (OSDM'05), Chicago, IL, USA, 2005.

Digital Library

[4]

K. Buza and L. Schmidt-Thieme. Motif-based Classification of Time Series with Bayesian Networks and SVMs. In Proc. of 32nd Annual Conf. of the Gesellschaft für Klassifikation (GfKl), 2009.

[5]

N. Castro and P. Azevedo. Time Series Motifs Statistical Significance. In Proc. of the SIAM Int. Conf. on Data Mining, pages 687--698. SIAM, 2011.

[6]

S. Chu, E. Keogh, D. Hart, and M. Pazzani. Iterative deepening dynamic time warping for time series. In Proc. of 2nd SIAM Int. Conf. on Data Mining, 2002.

[7]

G. Cimino, G. D. Duce, L. K. Kadonaga, G. Rotundo, A. Sisani, G. Stabile, B. Tirozzi, and M. Whiticar. Time series analysis of geological data. Chemical Geology, 161(1--3): 253--270, 1999.

[8]

C. S. Daw, C. E. A. Finney, and E. R. Tracy. A review of symbolic analysis of experimental data. Review of Scientific Instruments, 74(2): 915--930, 2003.

[9]

H. Ding, G. Trajcevski, P. Scheuermann, X. Wang, and E. Keogh. Querying and mining of time series data: experimental comparison of representations and distance measures. Proc. VLDB Endow., 1, 2008.

Digital Library

[10]

Dirk Eddelbuette. Beancounter portfolio performance toolkit homepage. Last visited 10/2011, http://dirk.eddelbuettel.com/code/beancounter.html.

[11]

Eamonn Keogh. SAX homepage. Last visited 10/2011, http://www.cs.ucr.edu/~eamonn/SAX.htm.

[12]

P. G. Ferreira and P. J. Azevedo. Protein sequence classification through relevant sequence mining and bayes classifiers. In Portuguese Conf. on Artificial Intelligence, pages 236--247, 2005.

Digital Library

[13]

P. G. Ferreira, P. J. Azevedo, C. G. Silva, and R. M. M. Brito. Mining approximate motifs in time series. In Proc. of the 9th Int. Conf. on Discovery Science, pages 7--10, 2006.

Digital Library

[14]

D. H. Fisher. Knowledge acquisition via incremental conceptual clustering. Machine Learning, 1987.

Digital Library

[15]

G. D. Fornay. The Viterbi Algorithm. Proc. of the IEEE, 61(3): 268--278, 1973.

[16]

T.-c. Fu, F.-l. Chung, R. Luk, and C.-m. Ng. Stock time series pattern matching: Template-based vs. rule-based approaches. Eng. Appl. Artif. Intell., 20: 347--364, 2007.

Digital Library

[17]

W. Gaul and L. Schmidt-Thieme. Mining generalized association rules for sequential and path data. In ICDM, pages 593--596. IEEE Computer Society, 2001.

Digital Library

[18]

A. Gellert and L. Vintan. Person movement prediction using hidden markov models. Studies in Informatics and Control, 15(1): 17--30, 2006.

[19]

M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten. The WEKA data mining software: an update. SIGKDD Explor. Newsl., 11: 10--18, 2009.

Digital Library

[20]

M. R. Hassan and B. Nath. Stockmarket forecasting using hidden markov model: A new approach. Int. Conf. on Intelligent Systems Design and Applications, 0: 192--196, 2005.

Digital Library

[21]

S. C. Johnson. Hierarchical clustering schemes. Psychometrika, 2: 241--254, 1967.

[22]

E. Keogh and M. Pazzani. Derivative dynamic time warping. In Proc. of 1st SIAM Int. Conf. on Data Mining (SDM), 2001.

[23]

E. J. Keogh and C. A. Ratanamahatana. Exact indexing of dynamic time warping. Knowl. Inf. Syst., 7(3): 358--386, 2005.

Digital Library

[24]

S. Kotsiantis and D. Kanellopoulos. Discretization techniques: A recent survey. GESTS Int. Transactions on Computer Science and Engineering, 32(1): 47--58, 2006.

[25]

V. Kunik, Z. Solan, S. Edelman, E. Ruppin, and D. Horn. Motif extraction and protein classification. Computational Systems Bioinformatics Conf. Int. IEEE Computer Society, 0: 80--85, 2005.

Digital Library

[26]

Lawrence Berkeley National Lab. The colt project - open source libraries for high performance scientific and technical computing in java. Last visited 10/2011, http://acs.lbl.gov/software/colt.

[27]

V. Levenshtein. Binary Codes Capable of Correcting Deletions, Insertions and Reversals. In Soviet Physics Doklady, volume 10, 1966.

[28]

J. Lin, E. Keogh, L. Wei, and S. Lonardi. Experiencing sax: a novel symbolic representation of time series. Data Mining and Knowledge Discovery, 15: 107--144, 2007. 10.1007/s10618-007-0064-z.

Digital Library

[29]

J. Lin, E. J. Keogh, S. Lonardi, and B. Y. chi Chiu. A symbolic representation of time series, with implications for streaming algorithms. In DMKD, pages 2--11. ACM, 2003.

Digital Library

[30]

F. Mormann, R. G. Andrzejak, C. E. Elger, and K. Lehnertz. Seizure prediction: the long and winding road. Brain, 2006.

[31]

P. Patel, E. J. Keogh, J. Lin, and S. Lonardi. Mining motifs in massive time series databases. In ICDM, pages 370--377. IEEE Computer Society, 2002.

Digital Library

[32]

Pavel Senin. SAX - jmotif - homepage. Last visited 10/11, http://code.google.com/p/jmotif/wiki/SAX.

[33]

D. J. Pedregal, R. Rivas, V. Feliu, L. Sánchez, and A. Linares. A non-linear forecasting system for the Ebro River at Zaragoza, Spain. Environ. Model. Softw., 24(4): 502--509, 2009.

Digital Library

[34]

A. Poritz. Hidden markov models: a guided tour. In Int. Conf. on Acoustics, Speech, and Signal Processing (ICASSP-88), volume 1, pages 7--13, 1988.

[35]

L. Rabiner and B. Juang. An introduction to hidden markov models. ASSP, IEEE, 3(1): 4--16, 1986.

[36]

L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proc. of the IEEE, 77(2): 257--286, 1989.

[37]

S. Robin, S. Schbath, and V. Vandewalle. Statistical tests to compare motif count exceptionalities. BMC Bioinformatics, 8(1): 84, 2007.

[38]

H. Sakoe and S. Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing, 26: 43--49, 1978.

[39]

H. Sakoe and S. Chiba. Dynamic programming algorithm optimization for spoken word recognition. In Readings in speech recognition, 1990.

Digital Library

[40]

S. Salvador and P. Chan. FastDTW: toward accurate dynamic time warping in linear time and space. Intell. Data Anal., 11(5), 2007.

Digital Library

[41]

T. Schlüter and S. Conrad. An approach for automatic sleep stage scoring and apnea-hypopnea detection. In ICDM, pages 1007--1012. IEEE, 2010.

Digital Library

[42]

T. Schlüter and S. Conrad. Tempus: A prototype system for time series analysis and prediction. In Proc. of IADIS Europ. Conf. Data Mining, 2010.

[43]

P. A. Schrodt. Early warning of conflict in southern lebanon using hidden markov models. In The Understanding and Management of Global Violence, pages 131--162. St. Martin's Press, 1997.

[44]

R. H. Shumway and D. S. Stoffer. Time Series Analysis and Its Applications With R Examples. Springer, 2006. ISBN 978-0-387-29317-2.

[45]

G. I. Webb. Discovering significant patterns. Mach. Learn., 68: 1--33, 2007.

Digital Library

[46]

T. Xu, J. Wu, Z. Wu, and Q. Li. Long-term sunspot number prediction based on EMD analysis and AR model. Chin. J. Astron. Astrophys., 8: 337--342, 2008.

[47]

D. Yankov, E. J. Keogh, J. Medina, B. Y. chi Chiu, and V. B. Zordan. Detecting time series motifs under uniform scaling. In KDD, pages 844--853. ACM, 2007.

Digital Library

Cited By

Hsu C(2020)A multi-valued and sequential-labeled decision tree method for recommending sequential patterns in cold-start situationsApplied Intelligence10.1007/s10489-020-01806-0Online publication date: 19-Aug-2020
https://doi.org/10.1007/s10489-020-01806-0
Shayegh FGhasemi FAmirfatahi RSadri SAnsarifard K(2018)Online Single-Channel Seizure Prediction, Based on Seizure Genesis Model of Depth-EEG Signals Using Extended Kalman FilterSignal and Data Processing10.29252/jsdp.15.1.315:1(3-28)Online publication date: 1-Jun-2018
https://doi.org/10.29252/jsdp.15.1.3
Truong CTin HAnh D(2018)Combining motif information and neural network for time series predictionInternational Journal of Business Intelligence and Data Mining10.1504/IJBIDM.2012.0517347:4(318-339)Online publication date: 15-Dec-2018
https://dl.acm.org/doi/10.1504/IJBIDM.2012.051734
Show More Cited By

Recommendations

Inferring ancestry in mouse genomes using a hidden Markov model
BCB '14: Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics

The use of recombinant inbred strains in mice is a powerful tool for understanding the genetics of complex diseases, such as alcohol tolerance. In 1981, McClearn and Kakihana introduced the Inbred Long Sleep (ILS) and Inbred Short Sleep (ISS) mouse ...
PM2.5 concentration prediction using hidden semi-Markov model-based times series data mining

In this paper, a novel framework and methodology based on hidden semi-Markov models (HSMMs) for high PM"2"."5 concentration value prediction is presented. Due to lack of explicit time structure and its short-term memory of past history, a standard ...
A Hidden Semi-Markov Model-Based Speech Synthesis System

A statistical speech synthesis system based on the hidden Markov model (HMM) was recently proposed. In this system, spectrum, excitation, and duration of speech are modeled simultaneously by context-dependent HMMs, and speech parameter vector sequences ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '12: Proceedings of the 27th Annual ACM Symposium on Applied Computing

March 2012

2179 pages

ISBN:9781450308571

DOI:10.1145/2245276

Conference Chairs:
Sascha Ossowski
University Rey Juan Carlos, Spain
,
Paola Lecca
The Microsoft Research - University of Trento COSBI, Italy

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 March 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAC 2012

Sponsor:

SIGAPP

SAC 2012: ACM Symposium on Applied Computing

March 26 - 30, 2012

Trento, Italy

Acceptance Rates

SAC '12 Paper Acceptance Rate 270 of 1,056 submissions, 26%;

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
551
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hsu C(2020)A multi-valued and sequential-labeled decision tree method for recommending sequential patterns in cold-start situationsApplied Intelligence10.1007/s10489-020-01806-0Online publication date: 19-Aug-2020
https://doi.org/10.1007/s10489-020-01806-0
Shayegh FGhasemi FAmirfatahi RSadri SAnsarifard K(2018)Online Single-Channel Seizure Prediction, Based on Seizure Genesis Model of Depth-EEG Signals Using Extended Kalman FilterSignal and Data Processing10.29252/jsdp.15.1.315:1(3-28)Online publication date: 1-Jun-2018
https://doi.org/10.29252/jsdp.15.1.3
Truong CTin HAnh D(2018)Combining motif information and neural network for time series predictionInternational Journal of Business Intelligence and Data Mining10.1504/IJBIDM.2012.0517347:4(318-339)Online publication date: 15-Dec-2018
https://dl.acm.org/doi/10.1504/IJBIDM.2012.051734
Son NAnh D(2018)Discovery of time series $$k$$k-motifs based on multidimensional indexKnowledge and Information Systems10.1007/s10115-014-0814-346:1(59-86)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s10115-014-0814-3
Geilke MKarwath AKramer S(2015)Modeling recurrent distributions in streams using possible worlds2015 IEEE International Conference on Data Science and Advanced Analytics (DSAA)10.1109/DSAA.2015.7344814(1-9)Online publication date: Oct-2015
https://doi.org/10.1109/DSAA.2015.7344814
Cai QChen LSun J(2015)Piecewise statistic approximation based similarity measure for time seriesKnowledge-Based Systems10.1016/j.knosys.2015.05.00585:C(181-195)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.knosys.2015.05.005
Rousseeuw KCaillault ELefebvre AHamad D(2013)Monitoring system of phytoplankton blooms by using unsupervised classifier and time modeling2013 IEEE International Geoscience and Remote Sensing Symposium - IGARSS10.1109/IGARSS.2013.6723700(3962-3965)Online publication date: Jul-2013
https://doi.org/10.1109/IGARSS.2013.6723700
Truong CAnh D(2012)Time Series Prediction Using Motif InformationMulti-disciplinary Trends in Artificial Intelligence10.1007/978-3-642-35455-7_11(110-121)Online publication date: 2012
https://doi.org/10.1007/978-3-642-35455-7_11

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents