Skip to main content
Erschienen in: International Journal of Machine Learning and Cybernetics 11/2019

27.08.2019 | Original Article

Dynamic time alignment kernel-based fuzzy clustering of non-equal length vector time series

verfasst von: Hongyue Guo, Lidong Wang, Xiaodong Liu

Erschienen in: International Journal of Machine Learning and Cybernetics | Ausgabe 11/2019

Einloggen

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

search-config
loading …

Abstract

Time series clustering is an effective vehicle to explore and visualize the structure of a suite of time series. In this study, we generalize the kernel-based fuzzy c-means clustering algorithm by involving the dynamic time alignment kernel (DTAK) to cluster vector time series. In this method, the nonlinear time alignment embedded in DTAK makes the kernel-based fuzzy c-means available for sequences with variable lengths. However, it is noted that DTAK is not a strictly positive definite kernel, especially when the sample size is large. To overcome this, some strategies are presented to make the proposed algorithm available for large data sets. In addition, it is a challenge task to calculate the average sequence for a series of time series with different lengths. In kernel-based fuzzy c-means algorithm, it is not necessary to calculate the average sequence, which will increase the effectiveness of clustering techniques for time series. In the experiments, the kernel-based fuzzy c-means with DTAK is evaluated by both the data sets from the UCI KDD Archive and real-world data sets. Experimental results delivered by the proposed method demonstrate its effectiveness and robustness.

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!

Weitere Produktempfehlungen anzeigen
Literatur
1.
Zurück zum Zitat Aghabozorgi S, Shirkhorshidi AS, Wah TY (2015) Time-series clustering—a decade review. Inf Syst 53(C):16–38CrossRef Aghabozorgi S, Shirkhorshidi AS, Wah TY (2015) Time-series clustering—a decade review. Inf Syst 53(C):16–38CrossRef
2.
Zurück zum Zitat Chen TY, Kuo FC, Merkel R (2004) On the statistical properties of the f-measure. In: Quality software, 2004. QSIC 2004. In: Proceedings of fourth international conference on, IEEE, pp 146–153 Chen TY, Kuo FC, Merkel R (2004) On the statistical properties of the f-measure. In: Quality software, 2004. QSIC 2004. In: Proceedings of fourth international conference on, IEEE, pp 146–153
3.
Zurück zum Zitat Cuturi M, Vert JP, Birkenes O, Matsui T (2006) A kernel for time series based on global alignments. In: IEEE international conference on acoustics, speech and signal processing, pp II-413–II-416 Cuturi M, Vert JP, Birkenes O, Matsui T (2006) A kernel for time series based on global alignments. In: IEEE international conference on acoustics, speech and signal processing, pp II-413–II-416
4.
Zurück zum Zitat Dhillon IS, Guan Y, Kulis B (2004) Kernel k-means: spectral clustering and normalized cuts. In: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 551–556 Dhillon IS, Guan Y, Kulis B (2004) Kernel k-means: spectral clustering and normalized cuts. In: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 551–556
6.
Zurück zum Zitat Everitt B, Landau S, Leese M (2001) Cluster analysis, 4th edn. Arnold, ParisMATH Everitt B, Landau S, Leese M (2001) Cluster analysis, 4th edn. Arnold, ParisMATH
7.
Zurück zum Zitat Graves D, Pedrycz W (2010) Kernel-based fuzzy clustering and fuzzy clustering: a comparative experimental study 161(4):522–543 Graves D, Pedrycz W (2010) Kernel-based fuzzy clustering and fuzzy clustering: a comparative experimental study 161(4):522–543
8.
Zurück zum Zitat Haasdonk B (2005) Feature space interpretation of svms with indefinite kernels. IEEE Trans Pattern Anal Mach Intell 27(4):482CrossRef Haasdonk B (2005) Feature space interpretation of svms with indefinite kernels. IEEE Trans Pattern Anal Mach Intell 27(4):482CrossRef
9.
Zurück zum Zitat Izakian Z, Mesgari MS, Abraham A (2016) Automated clustering of trajectory data using a particle swarm optimization. Comput Environ Urban Syst 55:55–65CrossRef Izakian Z, Mesgari MS, Abraham A (2016) Automated clustering of trajectory data using a particle swarm optimization. Comput Environ Urban Syst 55:55–65CrossRef
10.
Zurück zum Zitat Ketterlin A (2011) A global averaging method for dynamic time warping, with applications to clustering. Elsevier Science Inc, New YorkMATH Ketterlin A (2011) A global averaging method for dynamic time warping, with applications to clustering. Elsevier Science Inc, New YorkMATH
11.
Zurück zum Zitat Muller KR, Mika S (2001) An introduction to kernel-based learning algorithms. IEEE Trans Neural Netw 12(2):181–201CrossRef Muller KR, Mika S (2001) An introduction to kernel-based learning algorithms. IEEE Trans Neural Netw 12(2):181–201CrossRef
12.
Zurück zum Zitat Li AZ, Tang S, Xue J, Jiang J (2001) Modified FCM clustering based on kernel mapping. In: Proceedings of SPIE, pp 241–245 Li AZ, Tang S, Xue J, Jiang J (2001) Modified FCM clustering based on kernel mapping. In: Proceedings of SPIE, pp 241–245
13.
Zurück zum Zitat Liao TW (2005) Clustering of time series data—a survey. Pattern Recogn 38(11):1857–1874CrossRef Liao TW (2005) Clustering of time series data—a survey. Pattern Recogn 38(11):1857–1874CrossRef
14.
Zurück zum Zitat Niennattrakul V, Srisai D, Ratanamahatana CA (2012) Shape-based template matching for time series data. Knowl-Based Syst 26:1–8CrossRef Niennattrakul V, Srisai D, Ratanamahatana CA (2012) Shape-based template matching for time series data. Knowl-Based Syst 26:1–8CrossRef
15.
Zurück zum Zitat Noma HSK, Shimodaira K (2002) Dynamic time-alignment kernel in support vector machine. Adv Neural Inf Process Syst 14:921 Noma HSK, Shimodaira K (2002) Dynamic time-alignment kernel in support vector machine. Adv Neural Inf Process Syst 14:921
16.
Zurück zum Zitat Sakoe H, Chiba S (1971) A dynamic programming approach to continuous speech recognition. In: Proceedings of the 7th international congress on acoustics, pp 65–69 Sakoe H, Chiba S (1971) A dynamic programming approach to continuous speech recognition. In: Proceedings of the 7th international congress on acoustics, pp 65–69
17.
Zurück zum Zitat Sakoe H, Chiba S (1978) Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans Acoust Speech Signal Process 26(1):43–49CrossRef Sakoe H, Chiba S (1978) Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans Acoust Speech Signal Process 26(1):43–49CrossRef
18.
Zurück zum Zitat Santarcangelo J, Zhang XP (2015) Dynamic time-alignment k-means kernel clustering for time sequence clustering. In: IEEE international conference on image processing, pp 2532–2536 Santarcangelo J, Zhang XP (2015) Dynamic time-alignment k-means kernel clustering for time sequence clustering. In: IEEE international conference on image processing, pp 2532–2536
19.
Zurück zum Zitat Saxena A, Prasad M, Gupta A, Bharill N, Patel OP, Tiwari A, Meng JE, Ding W, Lin CT (2017) A review of clustering techniques and developments. Neurocomputing 2017:267 Saxena A, Prasad M, Gupta A, Bharill N, Patel OP, Tiwari A, Meng JE, Ding W, Lin CT (2017) A review of clustering techniques and developments. Neurocomputing 2017:267
20.
Zurück zum Zitat Shimodaira H, Noma KI, Nakai M, Sagayama S (2001) Dynamic time-alignment kernel in support vector machine. In: International conference on neural information processing systems: natural and synthetic, pp 921–928 Shimodaira H, Noma KI, Nakai M, Sagayama S (2001) Dynamic time-alignment kernel in support vector machine. In: International conference on neural information processing systems: natural and synthetic, pp 921–928
21.
Zurück zum Zitat Wang X, Ma KT, Ng GW, Grimson WEL (2008) Trajectory analysis and semantic region modeling using a nonparametric Bayesian model. In: Computer vision and pattern recognition, 2008. CVPR 2008. IEEE conference on, pp 1–8 Wang X, Ma KT, Ng GW, Grimson WEL (2008) Trajectory analysis and semantic region modeling using a nonparametric Bayesian model. In: Computer vision and pattern recognition, 2008. CVPR 2008. IEEE conference on, pp 1–8
22.
Zurück zum Zitat Xu R, Ii DCW (2005) IEEE, survey of clustering algorithms. IEEE Trans Neural Netw 16(3):645–678CrossRef Xu R, Ii DCW (2005) IEEE, survey of clustering algorithms. IEEE Trans Neural Netw 16(3):645–678CrossRef
23.
Zurück zum Zitat Yi BK, Jagadish H, Faloutsos C (1998) Efficient retrieval of similar time sequences under time warping. In: Data engineering, 1998. Proceedings of 14th international conference on, IEEE, pp 201–208 Yi BK, Jagadish H, Faloutsos C (1998) Efficient retrieval of similar time sequences under time warping. In: Data engineering, 1998. Proceedings of 14th international conference on, IEEE, pp 201–208
24.
Zurück zum Zitat Zha H, He X, Ding C, Gu M, Simon HD (2001) Spectral relaxation for k-means clustering. In: Advances in neural information processing systems, pp 1057–1064 Zha H, He X, Ding C, Gu M, Simon HD (2001) Spectral relaxation for k-means clustering. In: Advances in neural information processing systems, pp 1057–1064
25.
Zurück zum Zitat Zhang DQ, Chen SC (2003) Fuzzy clustering using kernel method. In: International conference on control and automation, 2002. ICCA. Final program and book of, pp 162–163 Zhang DQ, Chen SC (2003) Fuzzy clustering using kernel method. In: International conference on control and automation, 2002. ICCA. Final program and book of, pp 162–163
26.
Zurück zum Zitat Zhou F, De la Torre F, Hodgins JK (2013) Hierarchical aligned cluster analysis for temporal clustering of human motion. Pattern Anal Mach Intell IEEE Trans 35(3):582–596CrossRef Zhou F, De la Torre F, Hodgins JK (2013) Hierarchical aligned cluster analysis for temporal clustering of human motion. Pattern Anal Mach Intell IEEE Trans 35(3):582–596CrossRef
27.
Zurück zum Zitat Zhou S, Gan JQ (2004) Mercer kernel, fuzzy c-means algorithm, and prototypes of clusters, vol 3177, pp 613–618 Zhou S, Gan JQ (2004) Mercer kernel, fuzzy c-means algorithm, and prototypes of clusters, vol 3177, pp 613–618
Metadaten
Titel
Dynamic time alignment kernel-based fuzzy clustering of non-equal length vector time series
verfasst von
Hongyue Guo
Lidong Wang
Xiaodong Liu
Publikationsdatum
27.08.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
International Journal of Machine Learning and Cybernetics / Ausgabe 11/2019
Print ISSN: 1868-8071
Elektronische ISSN: 1868-808X
DOI
https://doi.org/10.1007/s13042-019-01007-3

Weitere Artikel der Ausgabe 11/2019

International Journal of Machine Learning and Cybernetics 11/2019 Zur Ausgabe

Neuer Inhalt