[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

An ultra-fast time series distance measure to allow data mining in more complex real-world deployments

  • Published:
Data Mining and Knowledge Discovery Aims and scope Submit manuscript

Abstract

At their core, many time series data mining algorithms reduce to reasoning about the shapes of time series subsequences. This requires an effective distance measure, and for last two decades most algorithms use Euclidean distance or DTW as their core subroutine. We argue that these distance measures are not as robust as the community seems to believe. The undue faith in these measures perhaps derives from an overreliance on the benchmark datasets and self-selection bias. The community is simply reluctant to address more difficult domains, for which current distance measures are ill-suited. In this work, we introduce a novel distance measure MPdist. We show that our proposed distance measure is much more robust than current distance measures. For example, it can handle data with missing values or spurious regions. Furthermore, it allows us to successfully mine datasets that would defeat any Euclidean or DTW distance-based algorithm. Additionally, we show that our distance measure can be computed so efficiently as to allow analytics on very fast arriving streams.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25
Fig. 26
Fig. 27

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. There are several variants of LCSS proposed (under this, and other names). This is the more general explanation of such methods.

  2. This idea is simply the cross correlation, K-Shape is an algorithm that uses cross correlation (Paparrizos and Gravano 2015). However, we abuse terminology a little here to be consistent with the emerging literature.

  3. This is for the case where the query length is not known ahead of time. If the query length is known, it may be possible to have a faster index-based search.

References

  • Abanda A, Mori U, Lozano JA (2019) A review on distance based time series classification. Data Min Knowl Disc 33(2):378–412

    Article  MathSciNet  Google Scholar 

  • Aghabozorgi S, Shirkhorshidi AS, Wah TY (2015) Time-series clustering—a decade review. Inf Syst 53:16–38

    Article  Google Scholar 

  • Ahmed M, Mahmood AN, Islam MR (2016) A survey of anomaly detection techniques in financial domain. Future Gen Comput Syst 55:278–288

    Article  Google Scholar 

  • Bagnall A, Lines J, Bostrom A, Large J, Keogh E (2017) The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances. Data Min Knowl Disc 31(3):606–660

    Article  MathSciNet  Google Scholar 

  • Baker MB, Venugopal PD, Lamp WO (2015) climate change and phenology: Empoasca Fabae (Hemiptera: Cicadellidae) migration and severity of impact. PloS ONE 10(5):e0124915. https://doi.org/10.1371/journal.pone.0124915

    Article  Google Scholar 

  • Batista GE, Wang X, Keogh EJ (2011) A complexity-invariant distance measure for time series. In: Proceedings of the 2011 SIAM international conference on data mining, pp 699–710

  • Berndt DJ, Clifford J (1994). Using dynamic time warping to find patterns in time series. In: KDD workshop, vol 10, pp 359–70

  • Chen Y, Keogh E, Hu B, Begum N, Bagnall A (2015) UCR time series classification archive. Retrieved from www.cs.ucr.edu/~eamonn/time_series_data

  • Darvishzadeh A, Entezari N, Stahovich T (2018) Finding the answer: techniques for locating students’ answers in handwritten problem solutions. In: 2018 16th International conference on frontiers in handwriting recognition (ICFHR), pp 587–592

  • Dau HA, Begum N, Keogh E (2016) Semi-supervision dramatically improves time series clustering under dynamic time warping. In: 25th ACM international on conference on information and knowledge management, pp 999–1008

  • Dau HA, Silva DF, Petitjean F, Forestier G, Bagnall A, Keogh E (2017) Judicious setting of dynamic time warping’s window width allows more accurate classification of time series. In: 2017 IEEE international conference on big data (big data), pp 917–22

  • Dau HA, Bagnall A, Kamgar K, Yeh C-CM, Zhu Y, Gharghabi S, Ratanamahatana CA, Keogh E (2019) The UCR time series archive. IEEE/CAA J Automat Sin 6(6):1293–1305

    Article  Google Scholar 

  • Demšar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30

    MathSciNet  MATH  Google Scholar 

  • Guillame-Bert M, Dubrawski A (2017) Classification of time sequences using graphs of temporal constraints. J Mach Learn Res 18(1):4370–4403

    MathSciNet  Google Scholar 

  • Haigh, Karen Zita, Wendy Foslien, and Valerie Guralnik. 2004. “Visual Query Language: Finding Patterns in and Relationships among Time Series Data.” in Seventh Workshop on Mining Scientific and Engineering Datasets. Vol. 24

  • Honaker J, King G (2010) What to do about missing values in time-series cross-section data. Am J Polit Sci 54(2):561–581

    Article  Google Scholar 

  • Hu B, Chen Y, Zakaria J, Ulanova L, Keogh E (2013) Classification of multi-dimensional streaming time series by weighting each classifier’s track record. In: 2013 IEEE 13th international conference on data mining, pp 281–90

  • Hu B, Chen Y, Keogh E (2016) Classification of streaming time series under more realistic assumptions. Data Min Knowl Disc 30(2):403–437

    Article  MathSciNet  Google Scholar 

  • Imani S, Madrid F, Ding W, Crouter S, Keogh E (2018) Matrix profile XIII: time series snippets: a new primitive for time series data mining. In: 2018 IEEE international conference on big knowledge (ICBK), pp 382–89

  • Jin S, Chen ZM, Backus EA, Sun XL, Xiao B (2012) Characterization of EPG waveforms for the tea green leafhopper, Empoasca Vitis Göthe (Hemiptera: cicadellidae), on tea plants and their correlation with stylet activities. J Insect Physiol 58(9):1235–1244

    Article  Google Scholar 

  • Keogh E (2019) Supporting website for this paper. Retrieved February 29, 2020. https://sites.google.com/site/mpdistinfo/

  • Madden S (2004) Intel Lab Data

  • Mauck K (2018) Personal communication

  • Mei J, Liu M, Wang Y-F, Gao H (2015) Learning a mahalanobis distance-based dynamic time warping measure for multivariate time series classification. IEEE Trans Cybern 46(6):1363–1374

    Article  Google Scholar 

  • Moskovitch R, Shahar Y (2015) Classification-driven temporal discretization of multivariate time series. Data Min Knowl Disc 29(4):871–913

    Article  MathSciNet  Google Scholar 

  • Mueen A (2016) The MASS algorithm. Retrieved May 24, 2016. www.cs.unm.edu/~mueen/FastestSimilaritySearch.html

  • Murray D, Liao J, Stankovic L, Stankovic V, Hauxwell-Baldwin R, Wilson C, Coleman M, Kane T, Firth S (2015) A data management platform for personalised real-time energy feedback. In: The 8th international conference on energy efficiency in domestic appliances and lighting (EEDAL), pp 1293–1307

  • Paparrizos J, Gravano L (2015) K-shape: efficient and accurate clustering of time series. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data, pp 1855–1870

  • Piatetsky-Shapiro G (2014) Data types/sources analyzed. Retrieved April 2, 2018. https://www.kdnuggets.com/polls/2014/data-types-sources-analyzed.html

  • Rakthanmanon T, Campana B, Mueen A, Batista G, Westover B, Zhu Q, Zakaria J, Keogh E (2012) Searching and mining trillions of time series subsequences under dynamic time warping. In: Proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining, pp 262–70

  • Refitsmarthomes.org. (2018) REFIT dataset. Retrieved from www.refitsmarthomes.org/index.php/data

  • Rodriguez JJ, Kuncheva LI, Alonso CJ (2006) Rotation forest: a new classifier ensemble method. IEEE Trans Pattern Anal Mach Intell 28(10):1619–1630

    Article  Google Scholar 

  • Ruutu JPO, Kilkki MK, Nokia Networks Oy (2000) System and method employing last occurrence and sliding window technique for determining minimum and maximum values. U.S. Patent 6,023,453

  • Sarangi SR, Murthy K (2010) DUST: a generalized notion of similarity between uncertain time series. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining, pp 383–392

  • Schäfer P (2015) The BOSS is concerned with time series classification in the presence of noise. Data Min Knowl Disc 29(6):1505–1530

    Article  MathSciNet  Google Scholar 

  • Sengupta S (2015) Multidimensional time series classification and its application to video activity recognition. Ulster University, Derry

    Google Scholar 

  • Serrà J, Arcos JL (2016) Particle swarm optimization for time series motif discovery. Knowl Based Syst 92:127–137

    Article  Google Scholar 

  • Weng X, Shen J (2008a) Classification of multivariate time series using locality preserving projections. Knowl Based Syst 21(7):581–587

    Article  Google Scholar 

  • Weng X, Shen J (2008b) Classification of multivariate time series using two-dimensional singular value decomposition. Knowl Based Syst 21(7):535–539

    Article  Google Scholar 

  • Willett DS, George J, Willett NS, Stelinski LL, Lapointe SL (2016) Machine learning for characterization of insect vector feeding. PLoS Comput Biol 12(11):e1005158. https://doi.org/10.1371/journal.pcbi.1005158

    Article  Google Scholar 

  • Ye L, Keogh E (2009) Time series shapelets: a new primitive for data mining. In Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, pp 947–956

  • Yeh MY, Wu KL, Yu PS, Chen MS (2009) PROUD: a probabilistic approach to processing similarity queries over uncertain data streams. In: Proceedings of the 12th international conference on extending database technology: advances in database technology, pp 684–95

  • Yeh CCM, Zhu Y, Ulanova L, Begum N, Ding Y, Dau YA, Silva DF, Mueen A, Keogh E (2016) Matrix profile I: all pairs similarity joins for time series: a unifying view that includes motifs, discords and shapelets. In: 2016 IEEE 16th international conference on data mining (ICDM). IEEE, pp 1317–22

  • Yi X, Zheng Y, Zhang J, Li T (2016) ST-MVL: filling missing values in geo-sensory time series data

  • Zhang A, Song S, Wang J, Yu PS (2017) Time series data cleaning: from anomaly detection to anomaly repairing. Proc VLDB Endowm 10(10):1046–1057

    Article  Google Scholar 

  • Zhu Y, Zimmerman Z, Senobari NS, Yeh CCM, Funning G, Mueen A, Brisk P, Keogh E (2016) Matrix profile Ii: exploiting a novel algorithm and Gpus to break the one hundred million barrier for time series motifs and joins. In 2016 IEEE 16th international conference on data mining (ICDM), pp 739–48

Download references

Author information

Authors and Affiliations

  1. University of California, Riverside, USA

    Shaghayegh Gharghabi, Shima Imani, Amirali Darvishzadeh & Eamonn Keogh

  2. University of East Anglia, Norwich, UK

    Anthony Bagnall

Authors
  1. Shaghayegh Gharghabi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shima Imani
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Anthony Bagnall
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Amirali Darvishzadeh
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Eamonn Keogh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shaghayegh Gharghabi.

Additional information

Communicated by Albert Bifet.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gharghabi, S., Imani, S., Bagnall, A. et al. An ultra-fast time series distance measure to allow data mining in more complex real-world deployments. Data Min Knowl Disc 34, 1104–1135 (2020). https://doi.org/10.1007/s10618-020-00695-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10618-020-00695-8

Keywords