Time Series clustering - is K Mean accurate?

Question

My data set is composed by measurement of the same index for 14 years (columns) for 105 countries (rows). I want to cluster countries based on their index trend over time.

I am trying Hierarchical clustering (hclust) and K Medoids (pam) exploiting DTW distance matrix (dtw package).

I also tried K Mean, using the DTW distance matrix as first argument of function kmeans. The algorithm works, but I'm not sure about the accuracy of that, since K Mean exploit Eucledian Distance and computes centroids as means.

I am also thinking about using data directly, but I can't understand how the result would be accurate since the algorithm would consider different measurement of the same variable over time as different variables in order to compute the centroids at each iteration and Eucledian distance to assign observations to clusters. It doesn't seem to me that this process could cluster time series as well as Hierarchical and K Medoids clustering.

Is K Mean algorithm a good choice when clustering Time Series or it is better to use algorithms that exploit distance concept as DTW (but are slower)? Does it exist an R function that allows to use K Mean algorithm with distance matrix or a specific package to cluster Time Series data?

Answer 1

1) The original k-means is defined indeed for exclusively Euclidean distances, and it's called k-means because the clusters are represented by cluster means, which for squared Euclidean distances as used in the original k-means objective function can be shown to be the optimal centers. This does not in general hold for other distances.

2) I don't know how exactly you ran k-means on your DTW distances, but if you for example used the R-function kmeans (which expects Euclidean data as input - but this is called kmeans not kmean as you wrote), chances are it has interpreted the rows of your distance matrix as vectors and has used them as the basis for computing Euclidean distances. This is for sure not the most efficient use of your distances!

3) Euclidean distances will not normally take the dependence structure of time series into account, so I wouldn't recommend k-means for them. k-means "can" handle time series, but this doesn't mean the results are any good.

4) To my chagrin, there is some literature and software that uses the name "k-means" for a more general method that can also handle other distances. Very often this is not well explained (there is more than one way of generalising the k-means principle to more general distances, and often the authors won't tell you what exactly was done; also often there is no theoretical justification), and also the optimal centroid objects for other distances are usually not means, so the name "k-means" is inappropriate for this stuff. Actually I would not use such a procedure and rather use k-medoids (pam) if this was the kind of thing I am after, because k-medoids is well defined, uses a proper different name, and in fact does a thing very similar to k-means but for general distances. (Although this is quite different from running k-means on the distance vectors, which you may have accidentally done.)