An efficient implementation of k-means clustering for time series data with DTW distance
by Duong Tuan Anh; Le Huu Thanh
International Journal of Business Intelligence and Data Mining (IJBIDM), Vol. 10, No. 3, 2015

Abstract: Time series clustering is one of the crucial tasks in time series data mining. The most popular method in time series clustering is k-means algorithm due to its simplicity and flexibility. So far, k-means for time series clustering has been most used with Euclidean distance. Dynamic time warping (DTW) distance measure has increasingly been used as a similarity measurement for various data mining tasks in place of traditional Euclidean distance due to its superiority in sequence-alignment flexibility. However, there exist some difficulties in clustering with DTW distance, for example, the problem of shape averaging in DTW or the problem of speeding up DTW distance calculation. In this paper, we compare the performance of the three shape averaging methods in DTW: nonlinear alignment and averaging filter (NLAAF), prioritised shape averaging (PSA) and DTW barycenter averaging (DBA) and propose an efficient method to implement k-means clustering for time series data with DTW distance. In our method, we choose to use DBA method for shape-based time series averaging, apply early abandoning method for speeding up DTW distance calculation and median-based method for determining initial centroids for k-means clustering. The experimental results on benchmark datasets validate our proposed implementation method for time series k-means clustering with DTW.

Online publication date: Thu, 20-Aug-2015

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Business Intelligence and Data Mining (IJBIDM):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com