Artificial Intelligence in Medicine
Volume 45, Issue 1 , Pages 11-34 , January 2009

Matching incomplete time series with dynamic time warping: an algorithm and an application to post-stroke rehabilitation

Received 12 December 2007 ,Revised 31 October 2008 ,Accepted 6 November 2008.

References 

  1. Paolucci S, Antonucci G, Grasso MG, Morelli D, Troisi E, Coiro P, et al. Early versus delayed inpatient stroke rehabilitation: a matched comparison conducted in Italy. Archives of Physical Medicine and Rehabilitation. 2000;81(6):695–700
  2. Kwakkel G, van Peppen R, Wagenaar RC, Dauphinee SW, Richards C, Ashburn A, et al. Effects of augmented exercise therapy time after stroke: a meta-analysis. Stroke; A Journal of Cerebral Circulation. 2004;35(11):2529–2539
  3. Forster A, Young J. The clinical and cost effectiveness of physiotherapy in the management of elderly people following a stroke, vol. EB02. London, UK: The Chartered Society Of Physiotherapy; 2002;
  4. Quaglini S, Cavallini A, Gerzeli S, Micieli G. Economic benefit from clinical practice guideline compliance in stroke patient management. Health Policy. 2004;69(3):305–315
  5. Inzitari D. The Italian Guidelines for stroke prevention. The Stroke Prevention and Educational Awareness Diffusion (SPREAD) Collaboration. Neurological Sciences: Official Journal of the Italian Neurological Society and of the Italian Society of Clinical Neurophysiology. 2000;21(1):5–12
  6. Giorgino T, Tormene P, Cattani B, Pistarini C, Quaglini S. Remote support for stroke rehabilitation: MyHeart’s Neurological Rehabilitation concept, Medinfo 2007. In:  Kuhn KA,  Warren JR,  Leong T-Y editor. Proceedings of the 12th world congress on health (medical) informatics, vol. 12 (Part 1). Amsterdam: IOS Press; 2007;p. 92–96
  7. Giorgino T, Tormene P, Quaglini S. A multivariate time-warping based classifier for gesture recognition with wearable strain sensors. In:  Dittmar A,  Clark J,  McAdams E,  Lovell N editor. Engineering in medicine and biology society, 2007. EMBS 2007. 29th annual international conference of the IEEE. Los Alamitos, CA, USA: IEEE Computer Society; 2007;p. 4903–4906
  8. Carpi F, De Rossi D. Electroactive polymer-based devices for e-textiles in biomedicine. IEEE Transactions on Information Technology in Biomedicine. 2005;9(3):295–318
  9. De Rossi D, Lymberis A. New generation of smart wearable health systems and applications. IEEE Transactions on Information Technology in Biomedicine. 2005;9(3):293–294
  10. Giorgino T, Lorussi F, De Rossi D, Quaglini S. Posture classification via wearable strain sensors for neurological rehabilitation. In:  Dhawan A,  Akay M,  Laine AF,  Chon K editor. Engineering in medicine and biology society, 2006. EMBS’06. 28th annual international conference of the IEEE. Los Alamitos, CA, USA: IEEE Computer Society; 2006;p. 6273–6276
  11. Mattmann C, Amft O, Harms H, Troster G, Clemens F. Recognizing upper body postures using textile strain sensors. In:  Starner T,  Schiele B,  Ryhänen T editor. Proceedings of 11th IEEE international symposium on wearable computers. Los Alamitos, CA, USA: IEEE Computer Society; 2007;p. 29–36
  12. Lorussi F, Scilingo EP, Tesconi M, Tognetti A, De Rossi D. Strain sensing fabric for hand posture and gesture monitoring. IEEE Transactions on Information Technology in Biomedicine. 2005;9(3):372–381
  13. P. Tormene, T. Giorgino, Upper-limb rehabilitation exercises acquired through 29 elastomer strain sensors placed on fabric. release 1.0. Accessed: October 30; 2008. http://www.labmedinfo.org/research/myheart/myheart.htm (July 2008).
  14. Duchêne F, Garbay C, Rialle V. Learning recurrent behaviors from heterogeneous multivariate time-series. Artificial intelligence in Medicine. 2007;39(1):25–47
  15. Antunes C, Oliveira A. Temporal data mining: an overview. In:  Unnikrishnan KP,  Uthurusamy R editor. Proceedings of the workshop on temporal data mining at the 7th international conference on knowledge discovery and data mining (KDD’01). San Francisco, CA: Association for Computing Machinery; 2001;p. 1–13
  16. Sakoe H, Chiba S. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing [see also IEEE Transactions on Signal Processing]. 1978;26(1):43–49
  17. Rabiner L, Juang B-H. Fundamentals of speech recognition. Upper Saddle River, NJ, USA: Prentice-Hall, Inc.; 1993;
  18. Kaufman L, Rousseeuw P. Finding Groups in Data: an introduction to cluster analysis. New York: Wiley-Interscience; 1990;
  19. Faundez-Zanuy M. On-line signature recognition based on VQ-DTW. Pattern Recognition. 2007;40(3):981–992
  20. Rath T, Manmatha R. Word image matching using dynamic time warping. In:  Manmatha R editors. Proceedings of the IEEE computer society conference on computer vision and pattern recognition, vol. 2. Los Alamitos, CA, USA: IEEE Computer Society; 2003;p. II-521–II-527
  21. Gollmer K, Posten C. Supervision of bioprocesses using a dynamic time warping algorithm. Control Engineering Practice. 1996;4(9):1287–1295
  22. Huang B, Kinsner W. ECG frame classification using dynamic time warping. In:  Kinsner W,  Sebak A,  Ferens K editor. Proceedings of the Canadian conference on electrical and computer engineering IEEE CCECE 2002, vol. 2. Los Alamitos, CA, USA: IEEE Computer Society; 2002;p. 1105–1110
  23. Syeda-Mahmood T, Beymer D, Wang F. Shape-based matching of ECG recordings. In:  Dittmar A,  Clark J,  McAdams E,  Lovell N editor. Engineering in medicine and biology society, 2007. EMBS 2007. 29th annual international conference of the IEEE. Los Alamitos, CA, USA: IEEE Computer Society; 2007;p. 2012–2018
  24. Tuzcu V, Nas S. Dynamic time warping as a novel tool in pattern recognition of ECG changes in heart rhythm disturbances. In:  Jamshidi M,  Johnson M,  Chen P editor. Proceedings of the IEEE international conference on systems, man and cybernetics, vol. 1. Los Alamitos, CA, USA: IEEE Computer Society; 2005;p. 182–186
  25. Casarotto S, Bianchi A, Cerutti S, Vanello N, Ricciardi E, Gentili C, et al. Combination of event-related potentials and functional magnetic resonance imaging during single-letter reading. In:  Dhawan A,  Akay M,  Laine AF,  Chon K editor. Proceedings of the 28th annual international conference of the IEEE engineering in medicine and biology society EMBS’06. Los Alamitos, CA, USA: IEEE Computer Society; 2006;p. 984–987
  26. Brina CD, Niels R, Overvelde A, Levi G, Hulstijn W. Dynamic time warping: a new method in the study of poor handwriting. Human Movement Science. 2008;27(2):242–255
  27. Aach J, Church GM. Aligning gene expression time series with time warping algorithms. Bioinformatics. 2001;17(6):495–508
  28. Hermans F, Tsiporkova E. Merging microarray cell synchronization experiments through curve alignment. Bioinformatics. 2007;23(2):64–70
  29. Kartikeyan B, Sarkar A. Shape description by time series. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1989;11(9):977–984
  30. Wei L, Keogh E, Xi X. SAXually explicit images: finding unusual shapes. In:  Clifton CW,  Zhong N,  Liu J,  Wah BW,  Wu X editor. Proceedings of the sixth international conference on data mining, 2006, ICDM’06. Los Alamitos, CA, USA: IEEE Computer Society; 2006;p. 711–720
  31. Tak Y-S. A leaf image retrieval scheme based on partial dynamic time warping and two-level filtering. In:  Wei D,  Miyazaki T,  Paik I editor. Proceedings of the 7th IEEE international conference on computer and information technology CIT 2007. Los Alamitos, CA, USA: IEEE Computer Society; 2007;p. 633–638
  32. Mori A, Uchida S, Kurazume R, Taniguchi R, Hasegawa T, Sakoe H. Early recognition and prediction of gestures. In:  Werner B editors. Proceedings of the 18th international conference on pattern recognition ICPR 2006, vol. 3. Los Alamitos, CA, USA: IEEE Computer Society; 2006;p. 560–563
  33. Sakoe H. Two-level DP-matching - A dynamic programming-based pattern matching algorithm for connected word recognition. IEEE Transactions on Acoustics, Speech and Signal Processing [see also IEEE Transactions on Signal Processing]. 1979;27(6):588–595
  34. Myers C, Rabiner L, Rosenberg A. Performance tradeoffs in dynamic time warping algorithms for isolated word recognition. IEEE Transactions on Acoustics Speech and Signal Processing. 1980;28(6):623–635
  35. Wu H, Kido R, Shioyama T. Improvement of continuous dynamic programming for human gesture recognition. In:  Sanfeliu A,  Villanueva J,  Vanrell M,  Alquezar R,  Jain A,  Kittler J editor. Proceedings of the 15th international conference on pattern recognition, vol. 2. Los Alamitos, CA, USA: IEEE Computer Society; 2000;p. 945–948
  36. Keogh E, Xi X, Wei L, Ratanamahatana CA. The UCR time series classification/clustering homepage. Accessed: May 15; 2007. http://www.cs.ucr.edu/eamonn/time_series_data/.
  37. Martin JK, Hirschberg DS. Small sample statistics for classification error rates II: confidence intervals and significance tests. Tech. Re ICS-TR-96–22. University of California, Irvine. Technical Report No. 96–22; 1996.
  38. Scilingo EP, Lorussi F, Mazzoldi A, De Rossi D. Strain-sensing fabrics for wearable kinaesthetic-like systems. IEEE Sensors Journal. 2003;3(4):460–467
  39. Cohen J. A coefficient of agreement for nominal scales. Educational and Psychological Measurement. 1960;20(1):37–46
  40. Kvalseth T. Measurement of interobserver agreement using a “standard”: measure formulation and statistical inferences. In:  Tien JM editors. Proceedings of the IEEE international conference on systems, man, and cybernetics ‘computational cybernetics and simulation’, vol. 2. Los Alamitos, CA, USA: IEEE Computer Society; 1997;p. 1787–1790
  41. Lorussi F, Rocchia W, Scilingo EP, Tognetti A, De Rossi D. Wearable redundant fabric-based sensors arrays for reconstruction of body segment posture. IEEE Sensors Journal. 2004;4(6):807–818
  42. R Development Core Team. R: A language and environment for statistical computing. Vienna, Austria: R Foundation for Statistical Computing; 2007, ISBN 3–900051-07–0.
  43. Demšar J. Statistical comparisons of classifiers over multiple data sets. The Journal of Machine Learning Research. 2006;7:1–30
  44. Salzberg SL. On comparing classifiers: pitfalls to avoid and a recommended approach. Data Mining and Knowledge Discovery. 1997;1(3):317–328
  45. Itakura F. Minimum prediction residual principle applied to speech recognition. IEEE Transactions on Acoustics Speech and Signal Processing [see also IEEE Transactions on Signal Processing]. 1975;23(1):67–72
  46. Myers CS. A comparative study of several dynamic time warping algorithms for speech recognition. Master’s Thesis, MIT Jun 20; 1980.
  47. Keogh E, Pazzani M. Derivative dynamic time warping. In:  Kumar V,  Grossman R editor. First SIAM international conference on data mining. Philadelphia, PA: Society for Industrial and Applied Mathematics; 2001;
  48. Muscillo R, Conforto S, Schmid M, Caselli P, D’Alessio T. Classification of motor activities through derivative dynamic time warping applied on accelerometer data. In:  Dittmar A,  Clark J,  McAdams E,  Lovell N editor. Engineering in medicine and biology society, 2007. EMBS 2007. 29th annual international conference of the IEEE. Los Alamitos, CA, USA: IEEE Computer Society; 2007;p. 4930–4933
  49. Oka R. Spotting method for classification of real world data. The Computer Journal. 1998;41(8):559–565
  50. Rabiner L, Rosenberg A, Levinson S. Considerations in dynamic time warping algorithms for discrete word recognition. IEEE Transactions on Acoustics Speech and Signal Processing. 1978;26(6):575–582
  51. Keogh E, Ratanamahatana CA. Exact indexing of dynamic time warping. Knowledge and Information Systems. 2005;7(3):358–386
  52. Salvador S, Chan P. Fastdtw: Toward accurate dynamic time warping in linear time and space. In:  Unnikrishnan KP,  Uthurusamy R,  Han J editor. KDD workshop on mining temporal and sequential data. New York, NY, USA: ACM; 2004;p. 70–80
  53. Sakurai Y, Faloutsos C, Yamamuro M. Stream monitoring under the time warping distance. In:  Liu L,  Yazici A,  Chirkova R,  Oria V editor. Proceedings of the IEEE 23rd international conference on data engineering ICDE 2007. Los Alamitos, CA, USA: IEEE Computer Society; 2007;p. 1046–1055
  54. Rabiner L. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of IEEE. 1989;77(2):257–286
  55. Oates T, Firoiu L, Cohen PR. Using dynamic time warping to bootstrap hmm-based clustering of time series. Sequence Learning - Paradigms, Algorithms, and Applications. London, UK: Springer-Verlag; 2001;p. 35-52
  56. Yaniv R, Burshtein D. An enhanced dynamic time warping model for improved estimation of dtw parameters. IEEE Transactions on Speech and Audio Processing. 2003;11(3):216–228
  57. Navarro G. A guided tour to approximate string matching. ACM Computing Surveys. 2001;33(1):31–88
  58. P. Reiners, Dynamic programming and sequence alignment. Accessed: October 30; 2008. http://www.ibm.com/developerworks/java/library/j-seqalign/index.html (March 2008).
  59. Henikoff S, Henikoff JG. Amino acid substitution matrices from protein blocks. Proceedings of the National Academy of Sciences of the United States of America. 1992;89(22):10915–10919
  60. Latecki LJ, Megalooikonomou V, Wang Q, Yu D. An elastic partial shape matching technique. Pattern Recognition. 2007;40(11):3069–3080
  61. Warren Liao T. Clustering of time series data-a survey. Pattern Recognition. 2005;38(11):1857–1874
  62. Dixon S. An on-line time warping algorithm for tracking musical performances. In:  Kaelbling LP,  Saffiotti A editor. Proceedings of the nineteenth international joint conference on artificial intelligence, vol. IJCAI-05. Denver, CO: Professional Book Center; 2005;p. 1727–1728
  63. Nishimura T, Oka R. Spotting recognition of human gestures from time-varying images. In:  Kavanaugh ME editors. Proceedings of the second international conference on automatic face and gesture recognition. Los Alamitos, CA, USA: IEEE Computer Society; 1996;p. 318–322
  64. Kameya H, Mori S, Oka R. A segmentation-free biometric writer verification method based on continuous dynamic programming. Pattern Recognition Letters. 2006;27(6):567–577
  65. Stacey M, McGregor C. Temporal abstraction in intelligent clinical data analysis: a survey. Artificial Intelligence in Medicine. 2007;39(1):1–24
  66. Augusto JC. Temporal reasoning for decision support in medicine. Artificial Intelligence in Medicine. 2005;33(1):1–24
  67. Haimowitz IJ. Knowledge-based trend detection and diagnosis. Ph.D. Thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, Cambridge, MA, USA; 1994.
  68. Haimowitz IJ, Kohane IS. Managing temporal worlds for medical trend diagnosis. Artificial Intelligence in Medicine. 1996;8(3):299–321
  69. Giorgino T, Tormene P. dtw: dynamic time warping algorithms. Accessed: October 30; 2008. http://cran.r-project.org/web/packages/dtw/index.html (July 2008).

PII: S0933-3657(08)00177-2

doi: 10.1016/j.artmed.2008.11.007

Artificial Intelligence in Medicine
Volume 45, Issue 1 , Pages 11-34 , January 2009

Article Tools

* Image Usage & Resolution