Barycentre Averaging for the Move-Split-Merge Time Series Distance Measure

Research areas:

• Uncategorized

Year:

2023

Type of Publication:

In Proceedings

Keywords:

Time Series Distances, Time Series Clustering, Move Split Merge, Barycentre Averaging, Dynamic Barycentre Averaging, MSM Barycentre Averaging, DBA, MBA

Authors:

• Holder, Christopher
• Guijo-Rubio, David
• Bagnall, Anthony

Volume:

1

Book title:

15th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management

Pages:

51-62

Organization:

Rome, Italy

ISSN:

2184-3228

BibTex:

@conference{BarycentreAveragingTimeSeries_2023, author = "Christopher Holder and David Guijo-Rubio and Anthony Bagnall", abstract = "Distance functions play a core role in many time series machine learning algorithms for tasks such as clustering, classification and regression. Time series often require bespoke distance functions because small offsets in time can lead to large distances between series that are conceptually similar. Elastic distances compensate for misalignment by creating a path through a cost matrix by warping and/or editing time series. Time series are most commonly clustered with partitional algorithms such as k-means and k-medoids using elastic distance measures such as Dynamic Time Warping (DTW). The distance is used to assign cases to the closest cluster representative. k-means requires the averaging of time series to find these representative centroids. If DTW is used to assign membership, but the arithmetic mean is used to find centroids, k-means performance degrades significantly. An averaging technique specific to DTW, called DTW Barycentre Averaging (DBA), overcomes the averaging problem however, can only be used with DTW. As such alternative distance functions such as Move-Split-Merge (MSM) are forced to use the arithmetic mean to compute new centroids and suffer similar degraded performance as k-means-DTW without DBA. To address this we propose a averaging method for MSM distance, MSM Barycentre Averaging (MBA) and show that when used to find centroids it significantly improves MSM based k-means and is better than commonly used alternatives.", booktitle = "15th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management", doi = "https://www.scitepress.org/PublicationsDetail.aspx?ID=h27zf/TeD4k={\&}amp;t=1", issn = "2184-3228", keywords = "Time Series Distances, Time Series Clustering, Move Split Merge, Barycentre Averaging, Dynamic Barycentre Averaging, MSM Barycentre Averaging, DBA, MBA", organization = "Rome, Italy", pages = "51--62", title = " {B}arycentre {A}veraging for the {M}ove-{S}plit-{M}erge {T}ime {S}eries {D}istance {M}easure ", url = "www.scitepress.org/PublicationsDetail.aspx?ID=h27zf/TeD4k={\&}amp;t=1", volume = "1", year = "2023", }

Abstract:

Distance functions play a core role in many time series machine learning algorithms for tasks such as clustering, classification and regression. Time series often require bespoke distance functions because small offsets in time can lead to large distances between series that are conceptually similar. Elastic distances compensate for misalignment by creating a path through a cost matrix by warping and/or editing time series. Time series are most commonly clustered with partitional algorithms such as k-means and k-medoids using elastic distance measures such as Dynamic Time Warping (DTW). The distance is used to assign cases to the closest cluster representative. k-means requires the averaging of time series to find these representative centroids. If DTW is used to assign membership, but the arithmetic mean is used to find centroids, k-means performance degrades significantly. An averaging technique specific to DTW, called DTW Barycentre Averaging (DBA), overcomes the averaging problem however, can only be used with DTW. As such alternative distance functions such as Move-Split-Merge (MSM) are forced to use the arithmetic mean to compute new centroids and suffer similar degraded performance as k-means-DTW without DBA. To address this we propose a averaging method for MSM distance, MSM Barycentre Averaging (MBA) and show that when used to find centroids it significantly improves MSM based k-means and is better than commonly used alternatives.