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...
- 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 |