Skip to main content

2016 | OriginalPaper | Buchkapitel

Piecewise Factorization for Time Series Classification

verfasst von : Qinglin Cai, Ling Chen, Jianling Sun

Erschienen in: Knowledge Discovery, Knowledge Engineering and Knowledge Management

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In the research field of time series analysis and mining, the nearest neighbor classifier (1NN) based on the dynamic time warping distance (DTW) is well known for its high accuracy. However, the high computational complexity of DTW can lead to the expensive time consumption of the classifier. An effective solution is to compute DTW in the piecewise approximation space (PA-DTW). However, most of the existing piecewise approximation methods must predefine the segment length and focus on the simple statistical features, which would influence the precision of PA-DTW. To address this problem, we propose a novel piecewise factorization model (PCHA) for time series, where an adaptive segment method is proposed and the Chebyshev coefficients of subsequences are extracted as features. Based on PCHA, the corresponding PA-DTW measure named ChebyDTW is proposed for the 1NN classifier, which can capture the fluctuation information of time series for the similarity measure. The comprehensive experimental evaluation shows that ChebyDTW can support both accurate and fast 1NN classification.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
2.
Zurück zum Zitat Fu, T.: A review on time series data mining. Eng. Appl. Artif. Intell. 24(1), 164–181 (2011)CrossRef Fu, T.: A review on time series data mining. Eng. Appl. Artif. Intell. 24(1), 164–181 (2011)CrossRef
3.
Zurück zum Zitat Ding, H., Trajcevski, G., Scheuermann, P., Wang, X., Keogh, E.: Querying and mining of time series data: experimental comparison of representations and distance measures. In: Proceedings of the VLDB Endowment, pp. 1542–1552 (2008) Ding, H., Trajcevski, G., Scheuermann, P., Wang, X., Keogh, E.: Querying and mining of time series data: experimental comparison of representations and distance measures. In: Proceedings of the VLDB Endowment, pp. 1542–1552 (2008)
4.
Zurück zum Zitat Hills, J., Lines, J., Baranauskas, E., Mapp, J., Bagnall, A.: Classification of time series by shapelet transformation. Data Min. Knowl. Disc. 28(4), 851–881 (2014)MathSciNetCrossRefMATH Hills, J., Lines, J., Baranauskas, E., Mapp, J., Bagnall, A.: Classification of time series by shapelet transformation. Data Min. Knowl. Disc. 28(4), 851–881 (2014)MathSciNetCrossRefMATH
5.
Zurück zum Zitat Serra, J., Arcos, J.L.: An empirical evaluation of similarity measures for time series classification. Knowl.-Based Syst. 67, 305–314 (2014)CrossRef Serra, J., Arcos, J.L.: An empirical evaluation of similarity measures for time series classification. Knowl.-Based Syst. 67, 305–314 (2014)CrossRef
6.
Zurück zum Zitat Keogh, E., Chakrabarti, K., Pazzani, M., Mehrotra, S.: Dimensionality reduction for fast similarity search in large time series databases. Knowl. Inf. Syst. 3(3), 263–286 (2001)CrossRefMATH Keogh, E., Chakrabarti, K., Pazzani, M., Mehrotra, S.: Dimensionality reduction for fast similarity search in large time series databases. Knowl. Inf. Syst. 3(3), 263–286 (2001)CrossRefMATH
7.
Zurück zum Zitat Keogh, E., Chu, S., Hart, D., Pazzani, M.: Segmenting time series: a survey and novel approach. Data Min. Time Ser. Databases 57, 1–22 (2004)CrossRef Keogh, E., Chu, S., Hart, D., Pazzani, M.: Segmenting time series: a survey and novel approach. Data Min. Time Ser. Databases 57, 1–22 (2004)CrossRef
8.
Zurück zum Zitat Chakrabarti, K., Keogh, E., Mehrotra, S., Pazzani, M.: Locally adaptive dimensionality reduction for indexing large time series databases. ACM Trans. Database Syst. 27(2), 188–228 (2002)CrossRef Chakrabarti, K., Keogh, E., Mehrotra, S., Pazzani, M.: Locally adaptive dimensionality reduction for indexing large time series databases. ACM Trans. Database Syst. 27(2), 188–228 (2002)CrossRef
9.
Zurück zum Zitat Gullo, F., Ponti, G., Tagarelli, A., Greco, S.: A time series representation model for accurate and fast similarity detection. Pattern Recognit. 42(11), 2998–3014 (2009)CrossRefMATH Gullo, F., Ponti, G., Tagarelli, A., Greco, S.: A time series representation model for accurate and fast similarity detection. Pattern Recognit. 42(11), 2998–3014 (2009)CrossRefMATH
10.
Zurück zum Zitat Keogh, E.J., Pazzani, M.J.: Scaling up dynamic time warping to massive datasets. In: Żytkow, J.M., Rauch, J. (eds.) PKDD 1999. LNCS (LNAI), vol. 1704, pp. 1–11. Springer, Heidelberg (1999). doi:10.1007/978-3-540-48247-5_1 CrossRef Keogh, E.J., Pazzani, M.J.: Scaling up dynamic time warping to massive datasets. In: Żytkow, J.M., Rauch, J. (eds.) PKDD 1999. LNCS (LNAI), vol. 1704, pp. 1–11. Springer, Heidelberg (1999). doi:10.​1007/​978-3-540-48247-5_​1 CrossRef
11.
Zurück zum Zitat Li, H., Guo, C.: Piecewise cloud approximation for time series mining. Knowl.-Based Syst. 24(4), 492–500 (2011)CrossRef Li, H., Guo, C.: Piecewise cloud approximation for time series mining. Knowl.-Based Syst. 24(4), 492–500 (2011)CrossRef
12.
Zurück zum Zitat Lin, J., Vlachos, M., Keogh, E., Gunopulos, D., Liu, J., Yu, S., Le, J.: A MPAA-based iterative clustering algorithm augmented by nearest neighbors search for time-series data streams. In: Ho, T.B., Cheung, D., Liu, H. (eds.) PAKDD 2005. LNCS (LNAI), vol. 3518, pp. 333–342. Springer, Heidelberg (2005). doi:10.1007/11430919_40 CrossRef Lin, J., Vlachos, M., Keogh, E., Gunopulos, D., Liu, J., Yu, S., Le, J.: A MPAA-based iterative clustering algorithm augmented by nearest neighbors search for time-series data streams. In: Ho, T.B., Cheung, D., Liu, H. (eds.) PAKDD 2005. LNCS (LNAI), vol. 3518, pp. 333–342. Springer, Heidelberg (2005). doi:10.​1007/​11430919_​40 CrossRef
13.
Zurück zum Zitat Rakthanmanon, T., Campana, B., Mueen, A.: 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, Beijing (2012) Rakthanmanon, T., Campana, B., Mueen, A.: 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, Beijing (2012)
14.
Zurück zum Zitat Keogh, E.J., Pazzani, M.J.: Scaling up dynamic time warping for data mining applications. In: Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 285–289 (2000) Keogh, E.J., Pazzani, M.J.: Scaling up dynamic time warping for data mining applications. In: Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 285–289 (2000)
15.
Zurück zum Zitat Ullman, S., Poggio, T.: Vision: A Computational Investigation into the Human Representation and Processing of Visual Information. MIT Press, Cambridge (1982) Ullman, S., Poggio, T.: Vision: A Computational Investigation into the Human Representation and Processing of Visual Information. MIT Press, Cambridge (1982)
16.
Zurück zum Zitat Gao, J., Sultan, H., Hu, J., Tung, W.: Denoising nonlinear time series by adaptive filtering and wavelet shrinkage: a comparison. IEEE Sig. Process. Lett. 17(3), 237–240 (2010)CrossRef Gao, J., Sultan, H., Hu, J., Tung, W.: Denoising nonlinear time series by adaptive filtering and wavelet shrinkage: a comparison. IEEE Sig. Process. Lett. 17(3), 237–240 (2010)CrossRef
18.
Zurück zum Zitat Cai, Y., Ng, R.: Indexing spatio-temporal trajectories with Chebyshev polynomials. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, pp. 599–610 (2004) Cai, Y., Ng, R.: Indexing spatio-temporal trajectories with Chebyshev polynomials. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, pp. 599–610 (2004)
19.
Zurück zum Zitat Björkman, M., Holmström, K.: Global optimization using the DIRECT algorithm in matlab. Adv. Model. Optim. 1(2), 17–37 (1999)MATH Björkman, M., Holmström, K.: Global optimization using the DIRECT algorithm in matlab. Adv. Model. Optim. 1(2), 17–37 (1999)MATH
20.
Zurück zum Zitat Batista, G.E., Keogh, E.J., Tataw, O.M., Souza, V.M.: CID: an efficient complexity-invariant distance for time series. Data Min. Knowl. Disc. 28(3), 634–669 (2014)MathSciNetCrossRefMATH Batista, G.E., Keogh, E.J., Tataw, O.M., Souza, V.M.: CID: an efficient complexity-invariant distance for time series. Data Min. Knowl. Disc. 28(3), 634–669 (2014)MathSciNetCrossRefMATH
21.
Zurück zum Zitat Keogh, E.J., Pazzani, M.J.: Derivative dynamic time warping. In: Proceedings of SDM, pp. 5–7 (2001) Keogh, E.J., Pazzani, M.J.: Derivative dynamic time warping. In: Proceedings of SDM, pp. 5–7 (2001)
Metadaten
Titel
Piecewise Factorization for Time Series Classification
verfasst von
Qinglin Cai
Ling Chen
Jianling Sun
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-52758-1_5

Neuer Inhalt