EventDTW: An Improved Dynamic Time Warping Algorithm for Aligning Biomedical Signals of Nonuniform Sampling Frequencies
The dynamic time warping (DTW) algorithm is widely used in pattern matching and sequence alignment tasks, including speech recognition and time series clustering. However, DTW algorithms perform poorly when aligning sequences of uneven sampling frequencies. This makes it difficult to apply DTW to pr...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-05-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/20/9/2700 |
| _version_ | 1827717257808052224 |
|---|---|
| author | Yihang Jiang Yuankai Qi Will Ke Wang Brinnae Bent Robert Avram Jeffrey Olgin Jessilyn Dunn |
| author_facet | Yihang Jiang Yuankai Qi Will Ke Wang Brinnae Bent Robert Avram Jeffrey Olgin Jessilyn Dunn |
| author_sort | Yihang Jiang |
| collection | DOAJ |
| description | The dynamic time warping (DTW) algorithm is widely used in pattern matching and sequence alignment tasks, including speech recognition and time series clustering. However, DTW algorithms perform poorly when aligning sequences of uneven sampling frequencies. This makes it difficult to apply DTW to practical problems, such as aligning signals that are recorded simultaneously by sensors with different, uneven, and dynamic sampling frequencies. As multi-modal sensing technologies become increasingly popular, it is necessary to develop methods for high quality alignment of such signals. Here we propose a DTW algorithm called EventDTW which uses information propagated from defined events as basis for path matching and hence sequence alignment. We have developed two metrics, the error rate (ER) and the singularity score (SS), to define and evaluate alignment quality and to enable comparison of performance across DTW algorithms. We demonstrate the utility of these metrics on 84 publicly-available signals in addition to our own multi-modal biomedical signals. EventDTW outperformed existing DTW algorithms for optimal alignment of signals with different sampling frequencies in 37% of artificial signal alignment tasks and 76% of real-world signal alignment tasks. |
| first_indexed | 2024-03-10T19:56:58Z |
| format | Article |
| id | doaj.art-ef63b9d738e24fe99758c39e475551e7 |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-10T19:56:58Z |
| publishDate | 2020-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-ef63b9d738e24fe99758c39e475551e72023-11-19T23:54:16ZengMDPI AGSensors1424-82202020-05-01209270010.3390/s20092700EventDTW: An Improved Dynamic Time Warping Algorithm for Aligning Biomedical Signals of Nonuniform Sampling FrequenciesYihang Jiang0Yuankai Qi1Will Ke Wang2Brinnae Bent3Robert Avram4Jeffrey Olgin5Jessilyn Dunn6The Departments of Biomedical Engineering and Biostatistics & Bioinformatics, Duke University, Durham, NC 27708, USAThe Departments of Biomedical Engineering and Biostatistics & Bioinformatics, Duke University, Durham, NC 27708, USAThe Departments of Biomedical Engineering and Biostatistics & Bioinformatics, Duke University, Durham, NC 27708, USAThe Departments of Biomedical Engineering and Biostatistics & Bioinformatics, Duke University, Durham, NC 27708, USAThe Division of Cardiology and the Cardiovascular Research Institute, University of California San Francisco, San Francisco, CA 94143, USAThe Division of Cardiology and the Cardiovascular Research Institute, University of California San Francisco, San Francisco, CA 94143, USAThe Departments of Biomedical Engineering and Biostatistics & Bioinformatics, Duke University, Durham, NC 27708, USAThe dynamic time warping (DTW) algorithm is widely used in pattern matching and sequence alignment tasks, including speech recognition and time series clustering. However, DTW algorithms perform poorly when aligning sequences of uneven sampling frequencies. This makes it difficult to apply DTW to practical problems, such as aligning signals that are recorded simultaneously by sensors with different, uneven, and dynamic sampling frequencies. As multi-modal sensing technologies become increasingly popular, it is necessary to develop methods for high quality alignment of such signals. Here we propose a DTW algorithm called EventDTW which uses information propagated from defined events as basis for path matching and hence sequence alignment. We have developed two metrics, the error rate (ER) and the singularity score (SS), to define and evaluate alignment quality and to enable comparison of performance across DTW algorithms. We demonstrate the utility of these metrics on 84 publicly-available signals in addition to our own multi-modal biomedical signals. EventDTW outperformed existing DTW algorithms for optimal alignment of signals with different sampling frequencies in 37% of artificial signal alignment tasks and 76% of real-world signal alignment tasks.https://www.mdpi.com/1424-8220/20/9/2700dynamic time warpingsignal alignmentnonuniform sampling |
| spellingShingle | Yihang Jiang Yuankai Qi Will Ke Wang Brinnae Bent Robert Avram Jeffrey Olgin Jessilyn Dunn EventDTW: An Improved Dynamic Time Warping Algorithm for Aligning Biomedical Signals of Nonuniform Sampling Frequencies Sensors dynamic time warping signal alignment nonuniform sampling |
| title | EventDTW: An Improved Dynamic Time Warping Algorithm for Aligning Biomedical Signals of Nonuniform Sampling Frequencies |
| title_full | EventDTW: An Improved Dynamic Time Warping Algorithm for Aligning Biomedical Signals of Nonuniform Sampling Frequencies |
| title_fullStr | EventDTW: An Improved Dynamic Time Warping Algorithm for Aligning Biomedical Signals of Nonuniform Sampling Frequencies |
| title_full_unstemmed | EventDTW: An Improved Dynamic Time Warping Algorithm for Aligning Biomedical Signals of Nonuniform Sampling Frequencies |
| title_short | EventDTW: An Improved Dynamic Time Warping Algorithm for Aligning Biomedical Signals of Nonuniform Sampling Frequencies |
| title_sort | eventdtw an improved dynamic time warping algorithm for aligning biomedical signals of nonuniform sampling frequencies |
| topic | dynamic time warping signal alignment nonuniform sampling |
| url | https://www.mdpi.com/1424-8220/20/9/2700 |
| work_keys_str_mv | AT yihangjiang eventdtwanimproveddynamictimewarpingalgorithmforaligningbiomedicalsignalsofnonuniformsamplingfrequencies AT yuankaiqi eventdtwanimproveddynamictimewarpingalgorithmforaligningbiomedicalsignalsofnonuniformsamplingfrequencies AT willkewang eventdtwanimproveddynamictimewarpingalgorithmforaligningbiomedicalsignalsofnonuniformsamplingfrequencies AT brinnaebent eventdtwanimproveddynamictimewarpingalgorithmforaligningbiomedicalsignalsofnonuniformsamplingfrequencies AT robertavram eventdtwanimproveddynamictimewarpingalgorithmforaligningbiomedicalsignalsofnonuniformsamplingfrequencies AT jeffreyolgin eventdtwanimproveddynamictimewarpingalgorithmforaligningbiomedicalsignalsofnonuniformsamplingfrequencies AT jessilyndunn eventdtwanimproveddynamictimewarpingalgorithmforaligningbiomedicalsignalsofnonuniformsamplingfrequencies |