Hierarchical agglomerative clustering of time-warped series

We have developed a procedure for hierarchical agglomerative clustering of time series data. To measure the dissimilarity between these data, we use classically the Euclidean distance or we apply the costs of the series nonlinear alignment (time warping). In the latter approach, we use the classical...

Full description

Autores:
Tipo de recurso:
Fecha de publicación:
2018
Institución:
Universidad Tecnológica de Bolívar
Repositorio:
Repositorio Institucional UTB
Idioma:
eng
OAI Identifier:
oai:repositorio.utb.edu.co:20.500.12585/8913
Acceso en línea:
https://hdl.handle.net/20.500.12585/8913
Palabra clave:
DTW
Hierarchical clustering
Single/complete linkage
Cluster analysis
Time series
Dissimilarity measures
Effective measures
Euclidean distance
Hier-archical clustering
Hierarchical agglomerative clustering
Single/complete linkage
Time-series data
Visual similarity
Costs
Rights
restrictedAccess
License
http://creativecommons.org/licenses/by-nc-nd/4.0/
id UTB2_df8f3fb596e9056198c8fc86bd1f114d
oai_identifier_str oai:repositorio.utb.edu.co:20.500.12585/8913
network_acronym_str UTB2
network_name_str Repositorio Institucional UTB
repository_id_str
dc.title.none.fl_str_mv Hierarchical agglomerative clustering of time-warped series
title Hierarchical agglomerative clustering of time-warped series
spellingShingle Hierarchical agglomerative clustering of time-warped series
DTW
Hierarchical clustering
Single/complete linkage
Cluster analysis
Time series
Dissimilarity measures
Effective measures
Euclidean distance
Hier-archical clustering
Hierarchical agglomerative clustering
Single/complete linkage
Time-series data
Visual similarity
Costs
title_short Hierarchical agglomerative clustering of time-warped series
title_full Hierarchical agglomerative clustering of time-warped series
title_fullStr Hierarchical agglomerative clustering of time-warped series
title_full_unstemmed Hierarchical agglomerative clustering of time-warped series
title_sort Hierarchical agglomerative clustering of time-warped series
dc.contributor.editor.none.fl_str_mv Gruca A.
Czachorski T.
Harezlak K.
Kozielski S.
Piotrowska A.
Czachorski T.
dc.subject.keywords.none.fl_str_mv DTW
Hierarchical clustering
Single/complete linkage
Cluster analysis
Time series
Dissimilarity measures
Effective measures
Euclidean distance
Hier-archical clustering
Hierarchical agglomerative clustering
Single/complete linkage
Time-series data
Visual similarity
Costs
topic DTW
Hierarchical clustering
Single/complete linkage
Cluster analysis
Time series
Dissimilarity measures
Effective measures
Euclidean distance
Hier-archical clustering
Hierarchical agglomerative clustering
Single/complete linkage
Time-series data
Visual similarity
Costs
description We have developed a procedure for hierarchical agglomerative clustering of time series data. To measure the dissimilarity between these data, we use classically the Euclidean distance or we apply the costs of the series nonlinear alignment (time warping). In the latter approach, we use the classical costs or the modified ones. The modification consists in matching short signal segments instead of single signal samples. The procedure is applied to a few datasets from the internet archive of time series. In this archive, the series of the same classes possess visual similarity but their time evolution is often different (the characteristic waves have different location within the individual signals). Therefore the use of the Euclidean distance as the dissimilarity measure gives poor results. After time warping, the nonlinearly aligned signals match each other better, and therefore the total cost of the alignment appears to be a much more effective measure. It results in higher values of the Purity index used to evaluate the results of clustering. In most cases, the proposed modification of the alignment costs definition leads to still higher values of the index. © 2018, Springer International Publishing AG.
publishDate 2018
dc.date.issued.none.fl_str_mv 2018
dc.date.accessioned.none.fl_str_mv 2020-03-26T16:32:35Z
dc.date.available.none.fl_str_mv 2020-03-26T16:32:35Z
dc.type.coarversion.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_c94f
dc.type.driver.none.fl_str_mv info:eu-repo/semantics/conferenceObject
dc.type.hasversion.none.fl_str_mv info:eu-repo/semantics/publishedVersion
dc.type.spa.none.fl_str_mv Conferencia
status_str publishedVersion
dc.identifier.citation.none.fl_str_mv Advances in Intelligent Systems and Computing; Vol. 659, pp. 207-216
dc.identifier.isbn.none.fl_str_mv 9783319677910
dc.identifier.issn.none.fl_str_mv 21945357
dc.identifier.uri.none.fl_str_mv https://hdl.handle.net/20.500.12585/8913
dc.identifier.doi.none.fl_str_mv 10.1007/978-3-319-67792-7_21
dc.identifier.instname.none.fl_str_mv Universidad Tecnológica de Bolívar
dc.identifier.reponame.none.fl_str_mv Repositorio UTB
dc.identifier.orcid.none.fl_str_mv 55985160800
7004127726
57021964300
57195996744
identifier_str_mv Advances in Intelligent Systems and Computing; Vol. 659, pp. 207-216
9783319677910
21945357
10.1007/978-3-319-67792-7_21
Universidad Tecnológica de Bolívar
Repositorio UTB
55985160800
7004127726
57021964300
57195996744
url https://hdl.handle.net/20.500.12585/8913
dc.language.iso.none.fl_str_mv eng
language eng
dc.relation.conferencedate.none.fl_str_mv 3 October 2017 through 6 October 2017
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_16ec
dc.rights.uri.none.fl_str_mv http://creativecommons.org/licenses/by-nc-nd/4.0/
dc.rights.accessrights.none.fl_str_mv info:eu-repo/semantics/restrictedAccess
dc.rights.cc.none.fl_str_mv Atribución-NoComercial 4.0 Internacional
rights_invalid_str_mv http://creativecommons.org/licenses/by-nc-nd/4.0/
Atribución-NoComercial 4.0 Internacional
http://purl.org/coar/access_right/c_16ec
eu_rights_str_mv restrictedAccess
dc.format.medium.none.fl_str_mv Recurso electrónico
dc.format.mimetype.none.fl_str_mv application/pdf
dc.publisher.none.fl_str_mv Springer Verlag
publisher.none.fl_str_mv Springer Verlag
dc.source.none.fl_str_mv https://www.scopus.com/inward/record.uri?eid=2-s2.0-85030788309&doi=10.1007%2f978-3-319-67792-7_21&partnerID=40&md5=e468edc333362f58b3c61973e1e7dfff
institution Universidad Tecnológica de Bolívar
dc.source.event.none.fl_str_mv 5th International Conference on Man-Machine Interactions, ICMMI 2017
bitstream.url.fl_str_mv https://repositorio.utb.edu.co/bitstream/20.500.12585/8913/1/MiniProdInv.png
bitstream.checksum.fl_str_mv 0cb0f101a8d16897fb46fc914d3d7043
bitstream.checksumAlgorithm.fl_str_mv MD5
repository.name.fl_str_mv Repositorio Institucional UTB
repository.mail.fl_str_mv repositorioutb@utb.edu.co
_version_ 1814021559616012288
spelling Gruca A.Czachorski T.Harezlak K.Kozielski S.Piotrowska A.Czachorski T.Kotas, MarianLeski J.Moroń T.Guzmán J.G.2020-03-26T16:32:35Z2020-03-26T16:32:35Z2018Advances in Intelligent Systems and Computing; Vol. 659, pp. 207-216978331967791021945357https://hdl.handle.net/20.500.12585/891310.1007/978-3-319-67792-7_21Universidad Tecnológica de BolívarRepositorio UTB5598516080070041277265702196430057195996744We have developed a procedure for hierarchical agglomerative clustering of time series data. To measure the dissimilarity between these data, we use classically the Euclidean distance or we apply the costs of the series nonlinear alignment (time warping). In the latter approach, we use the classical costs or the modified ones. The modification consists in matching short signal segments instead of single signal samples. The procedure is applied to a few datasets from the internet archive of time series. In this archive, the series of the same classes possess visual similarity but their time evolution is often different (the characteristic waves have different location within the individual signals). Therefore the use of the Euclidean distance as the dissimilarity measure gives poor results. After time warping, the nonlinearly aligned signals match each other better, and therefore the total cost of the alignment appears to be a much more effective measure. It results in higher values of the Purity index used to evaluate the results of clustering. In most cases, the proposed modification of the alignment costs definition leads to still higher values of the index. © 2018, Springer International Publishing AG.Ministry of Higher Education: BK-220/RAu-3/2016, BKM-508/RAu-3/2016, POIG.02.03.01-24-099/Acknowledgements. This work was partially supported by the Ministry of Science and Higher Education funding for statutory activities (BK-220/RAu-3/2016) and the Ministry of Science and Higher Education funding for statutory activities of young researchers (BKM-508/RAu-3/2016). The work was performed using the infrastructure supported by POIG.02.03.01-24-099/13 grant: GeCONiI—Upper Silesian Center for Computational Science and Engineering.Recurso electrónicoapplication/pdfengSpringer Verlaghttp://creativecommons.org/licenses/by-nc-nd/4.0/info:eu-repo/semantics/restrictedAccessAtribución-NoComercial 4.0 Internacionalhttp://purl.org/coar/access_right/c_16echttps://www.scopus.com/inward/record.uri?eid=2-s2.0-85030788309&doi=10.1007%2f978-3-319-67792-7_21&partnerID=40&md5=e468edc333362f58b3c61973e1e7dfff5th International Conference on Man-Machine Interactions, ICMMI 2017Hierarchical agglomerative clustering of time-warped seriesinfo:eu-repo/semantics/conferenceObjectinfo:eu-repo/semantics/publishedVersionConferenciahttp://purl.org/coar/version/c_970fb48d4fbd8a85http://purl.org/coar/resource_type/c_c94fDTWHierarchical clusteringSingle/complete linkageCluster analysisTime seriesDissimilarity measuresEffective measuresEuclidean distanceHier-archical clusteringHierarchical agglomerative clusteringSingle/complete linkageTime-series dataVisual similarityCosts3 October 2017 through 6 October 2017Bellman, R.E., Dreyfus, S.E., (2015) Applied Dynamic Programming, , Princeton University Press, PrincetonBien, J., Tibshirani, R., Hierarchical clustering with prototypes via minimax linkage (2011) J. Am. Stat. Assoc., 106 (495), pp. 1075-1084Chen, Y., Keogh, E., Hu, B., Begum, N., Bagnall, A., Mueen, A., Batista, G., (2015) The UCR Time Series Classification Archive, , http://www.cs.ucr.edu/Everitt, B.S., Landau, S., Leese, M., Stahl, D., (2011) Hierarchical Clustering, pp. 71-110. , Wiley, HobokenGupta, L., Molfese, D.L., Tammana, R., Simos, P.G., Nonlinear alignment and averaging for estimating the evoked potential (1996) IEEE Trans. Biomed. Eng., 43 (4), pp. 348-356Keogh, E., Exact indexing of dynamic time warping (2002) VLDB 2002, pp. 406-417Keogh, E.J., Pazzani, M.J., Scaling up dynamic time warping for datamining applications (2000) KDD 2000, pp. 285-289Kotas, M., Projective filtering of time warped ECG beats (2008) Comput. Biol. Med., 38 (1), pp. 127-137Kotas, M., Robust projective filtering of time-warped ECG beats (2008) Comput. Methods Programs Biomed., 92 (2), pp. 161-172Kotas, M., Pander, T., Leski, J.M., Averaging of nonlinearly aligned signal cycles for noise suppression (2015) Biomed. Sig. Process. Control, 21, pp. 157-168Leski, J.M., Kotas, M., Hierarchical clustering with planar segments as prototypes (2015) Pattern Recogn. Lett., 54, pp. 1-10Moroń, T., Averaging of time-warped ECG signals for QT interval measurement (2016) Information Technologies in Medicine, 471, pp. 291-302. , Piȩtka, E., Badura, P., Kawa, J., Wieclawek, W. (eds.), Springer International Publishing, SwitzerlandNiennattrakul, V., Ratanamahatana, C.A., On clustering multimedia time series data using k-means and dynamic time warping (2007) MUE 2007, pp. 733-738Petitjean, F., Ketterlin, A., Gançarski, P., A global averaging method for dynamic time warping, with applications to clustering (2011) Pattern Recogn, 44 (3), pp. 678-693Rakthanmanon, T., Campana, B., Mueen, A., Batista, G., Westover, B., Zhu, Q., Zakaria, J., Keogh, E., Searching and mining trillions of time series subsequences under dynamic time warping (2012) KDD 2012, pp. 262-270Sakoe, H., Chiba, S., A similarity evaluation of speech patterns by dynamic programming (1970) Nat. Meeting of Institute of Electronic Communications Engineers of Japan, p. 136Sakoe, H., Chiba, S., Dynamic programming algorithm optimization for spoken word recognition (1978) IEEE Trans. Acoust. Speech Sig. Process., 26 (1), pp. 43-49http://purl.org/coar/resource_type/c_c94fTHUMBNAILMiniProdInv.pngMiniProdInv.pngimage/png23941https://repositorio.utb.edu.co/bitstream/20.500.12585/8913/1/MiniProdInv.png0cb0f101a8d16897fb46fc914d3d7043MD5120.500.12585/8913oai:repositorio.utb.edu.co:20.500.12585/89132023-04-24 09:39:33.928Repositorio Institucional UTBrepositorioutb@utb.edu.co