Motif Discovery in Long Time Series: Classifying Phonocardiograms | SpringerLink
Skip to main content
Springer Nature Link
Log in

Motif Discovery in Long Time Series: Classifying Phonocardiograms

  • Conference paper
  • First Online:
Artificial Intelligence XXXVI (SGAI 2019)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 11927))

  • 1094 Accesses

Abstract

A mechanism is presented for classifying phonocardiograms (PCGs) by interpreting PCGs as time series and using the concept of motifs, times series subsequences that are good discriminators of class, to support nearest neighbour classification. A particular challenge addressed by the work is that PCG time series are large which renders exact motif discovery to be computationally expensive; it is not realistic to compare every candidate time series subsequence with every other time series subsequence in order to discover exact motifs. Instead, a mechanism is proposed the firstly makes use of the cyclic nature of PCGs and secondly adopts a novel time series pruning mechanism. The evaluation, conducted using a canine PCG dataset, illustrated that the proposed approach produced the same classification accuracy but in a significantly more efficient manner.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Alhijailan, H., Coenen, F., Dukes-McEwan, J., Thiyagalingam, J.: Segmenting sound waves to support phonocardiogram analysis: the PCGseg approach. In: Geng, X., Kang, B.-H. (eds.) PRICAI 2018. LNCS (LNAI), vol. 11013, pp. 100–112. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-97310-4_12

    Chapter  Google Scholar 

  2. Atkins, C., et al.: Guidelines for the diagnosis and treatment of canine chronic valvular heart disease. J. Vet. Intern. Med. 23(6), 1142–1150 (2009). https://doi.org/10.1111/j.1939-1676.2009.0392.x

    Article  Google Scholar 

  3. Bagnall, A., Hills, J., Lines, J.: Finding motif sets in time series. CoRR, July 2014

    Google Scholar 

  4. Cherif, L.H., Debba, S.: Variability of pulmonary blood pressure, splitting of the second heart sound and heart rate. J. Clin. Exp. Cardiol. 8(10), 1–3 (2017). https://doi.org/10.4172/2155-9880.1000550

    Article  Google Scholar 

  5. Chiu, B., Keogh, E., Lonardi, S.: Probabilistic discovery of time series motifs. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2003, pp. 493–498. ACM, New York (2003). https://doi.org/10.1145/956750.956808

  6. Dasarathy, B.V.: Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. IEEE Computer Society Press Tutorial, IEEE Computer Society Press, the University of Michigan (1991)

    Google Scholar 

  7. Dau, H.A., Keogh, E.: Matrix profile V: a generic technique to incorporate domain knowledge into motif discovery. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2017, pp. 125–134. ACM, New York (2017). https://doi.org/10.1145/3097983.3097993

  8. Delgado-Trejos, E., Quiceno-Manrique, A., Godino-Llorente, J., Blanco-Velasco, M., Castellanos-Dominguez, G.: Digital auscultation analysis for heart murmur detection. Ann. Biomed. Eng. 37(2), 337–353 (2009). https://doi.org/10.1007/s10439-008-9611-z

    Article  Google Scholar 

  9. Ding, H., Trajcevski, G., Scheuermann, P., Wang, X., Keogh, E.: Querying and mining of time series data: experimental comparison of representations and distance measures. Proc. VLDB Endow. 1(2), 1542–1552 (2008). https://doi.org/10.14778/1454159.1454226

    Article  Google Scholar 

  10. Gao, Y., Lin, J., Rangwala, H.: Iterative grammar-based framework for discovering variable-length time series motifs. In: IEEE International Conference on Data Mining, pp. 111–116. IEEE, November 2017. https://doi.org/10.1109/ICDM.2017.20

  11. Guéhéneuc, Y.G., Antoniol, G.: DeMIMA: a multilayered approach for design pattern identification. IEEE Trans. Softw. Eng. 34(5), 667–684 (2008). https://doi.org/10.1109/TSE.2008.48

    Article  Google Scholar 

  12. Hamza Cherif, L., Debbal, S.M., Bereksi-Reguig, F.: Segmentation of heart sounds and heart murmurs. J. Mech. Med. Biol. 8(4), 549–559 (2008). https://doi.org/10.1142/S0219519408002759

    Article  Google Scholar 

  13. Hannan, E.J.: Time Series Analysis. Chapman and Hall, London (1960)

    MATH  Google Scholar 

  14. Hutchins, L.N., Murphy, S.M., Singh, P., Graber, J.H.: Position-dependent motif characterization using non-negative matrix factorization. Bioinformatics 24(23), 2684–2690 (2008). https://doi.org/10.1093/bioinformatics/btn526

    Article  Google Scholar 

  15. Krejci, A., Hupp, T.R., Lexa, M., Vojtesek, B., Muller, P.: Hammock: a hidden markov model-based peptide clustering algorithm to identify protein-interaction consensus motifs in large datasets. Bioinformatics 32(1), 9–16 (2016). https://doi.org/10.1093/bioinformatics/btv522

    Article  Google Scholar 

  16. Lehner, R.J., Rangayyan, R.M.: A three-channel microcomputer system for segmentation and characterization of the phonocardiogram. IEEE Trans. Biomed. Eng. 34(6), 485–489 (1987). https://doi.org/10.1109/TBME.1987.326060

    Article  Google Scholar 

  17. Li, N., Crane, M., Gurrin, C., Ruskin, H.J.: Finding motifs in large personal lifelogs. In: Proceedings of the 7th Augmented Human International Conference 2016, pp. 1–8. ACM, New York (2016). https://doi.org/10.1145/2875194.2875214

  18. Lin, J., Keogh, E., Lonardi, S., Patel, P.: Finding motifs in time series. In: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 53–68 (2002)

    Google Scholar 

  19. Lin, J., Keogh, E., Wei, L., Lonardi, S.: Experiencing SAX: a novel symbolic representation of time series. Data Min. Knowl. Discov. 15(2), 107–144 (2007). https://doi.org/10.1007/s10618-007-0064-z

    Article  MathSciNet  Google Scholar 

  20. Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: simple building blocks of complex networks. Science 298(5594), 824–827 (2002). https://doi.org/10.1126/science.298.5594.824

    Article  Google Scholar 

  21. Mubarak, Q., Akram, M.U., Shaukat, A., Ramazan, A.: Quality assessment and classification of heart sounds using PCG signals. In: Khan, F., Jan, M.A., Alam, M. (eds.) Applications of Intelligent Technologies in Healthcare. EICC, pp. 1–11. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-96139-2_1

    Chapter  Google Scholar 

  22. Mueen, A., Keogh, E., Zhu, Q., Cash, S., Westover, B.: Exact discovery of time series motifs. In: Proceedings of the 2009 SIAM International Conference on Data Mining, pp. 473–484 (2009). https://doi.org/10.1137/1.9781611972795.41

  23. Nakamura, K., et al.: Left atrial strain at different stages of myxomatous mitral valve disease in dogs. J. Vet. Intern. Med. 31(2), 316–325 (2017). https://doi.org/10.1111/jvim.14660

    Article  Google Scholar 

  24. Oliveira, J., Sousa, C., Coimbra, M.: Coupled hidden Markov model for automatic ECG and PCG segmentation. In: 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1023–1027, March 2017. https://doi.org/10.1109/ICASSP.2017.7952311

  25. Ramli, D., Hooi, M., Chee, K.: Development of heartbeat detection kit for biometric authentication system. Procedia Comput. Sci. 96, 305–314 (2016). https://doi.org/10.1016/j.procs.2016.08.143

    Article  Google Scholar 

  26. Stojanović, M.B., Božić, M.M., Stanković, M.M., Stajić, Z.P.: A methodology for training set instance selection using mutual information in time series prediction. Neurocomputing 141(Supplement C), 236–245 (2014). https://doi.org/10.1016/j.neucom.2014.03.006

  27. Thijs, G., et al.: A Gibbs sampling method to detect overrepresented motifs in the upstream regions of coexpressed genes. J. Comput. Biol. 9(2), 447–464 (2004). https://doi.org/10.1089/10665270252935566

  28. Torkamani, S., Lohweg, V.: Survey on time series motif discovery. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 7(2), 1–8 (2017). https://doi.org/10.1002/widm.1199

    Article  Google Scholar 

  29. Vahdatpour, A., Amini, N., Sarrafzadeh, M.: Toward unsupervised activity discovery using multi-dimensional motif detection in time series. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI 2009, pp. 1261–1266. Morgan Kaufmann Publishers Inc., San Francisco (2009)

    Google Scholar 

  30. Vaswani, A., Khaw, H.J., Dougherty, S., Zamvar, V., Lang, C.: Cardiology in a Heartbeat. Scion Publishing Limited, Banbury (2015)

    Google Scholar 

  31. Wang, X., Fang, Z., Wang, P., Zhu, R., Wang, W.: A distributed multi-level composite index for KNN processing on long time series. In: Candan, S., Chen, L., Pedersen, T.B., Chang, L., Hua, W. (eds.) DASFAA 2017. LNCS, vol. 10177, pp. 215–230. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55753-3_14

    Chapter  Google Scholar 

  32. Zhao, Y., et al.: Measurement of two new indicators of cardiac reserve in humans, rats, rabbits, and dogs. J. Biomed. Sci. Eng. 6(10), 960–963 (2013). https://doi.org/10.4236/jbise.2013.610118

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Liverpool, Liverpool, UK

    Hajar Alhijailan & Frans Coenen

  2. College of Computer and Information Sciences, King Saud University, Riyadh, Saudi Arabia

    Hajar Alhijailan

Authors
  1. Hajar Alhijailan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Frans Coenen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hajar Alhijailan .

Editor information

Editors and Affiliations

  1. University of Portsmouth, Portsmouth, UK

    Max Bramer

  2. Middlesex University, London, UK

    Miltos Petridis

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Alhijailan, H., Coenen, F. (2019). Motif Discovery in Long Time Series: Classifying Phonocardiograms. In: Bramer, M., Petridis, M. (eds) Artificial Intelligence XXXVI. SGAI 2019. Lecture Notes in Computer Science(), vol 11927. Springer, Cham. https://doi.org/10.1007/978-3-030-34885-4_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-34885-4_16

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-34884-7

  • Online ISBN: 978-3-030-34885-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation