# Hierarchical clustering, linkage methods and dynamic time warping

My goal is to cluster time series based on their DTW distance. Therefore I've calculated full distance matrices as input for several clustering algorithms. I first had a look at hierarchical methods, since the number of clusters don't have to be specified at the beginning (moreover k-means is problematic because of the problem of averaging time series under DTW and k-medoids is expensive).

Single linkage (not really useful), complete linkage and average linkage (UPGMA/WPGMA) are unproblematic methods, another criterion which seems to be often used is the Ward method (in R: ward.D2 for the hclust-function). I've seen at least one paper which uses the Ward method with DTW distances, however I am bit skeptical about the usage of Ward in this context. The ward distance of two clusters $A,B$ is defined, according to that paper, as:

$$D_{AB}=\frac{||c_A-c_B||^2}{1/|A|+1/|B|}$$

Where $c_A,c_B$ is the centroid of A, B.

My questions are:

1. How the centroids are calculated if only a distance matrix is given? (I'm guessing this calculation can't be applied when DTW distances are used.)

2. Since the application of the Ward method with DTW distances seems to be questionable, are there any other alternative (hierarchical) clustering methods, which can be used with a DTW distance matrix?

• "(moreover k-means is problematic because of the problem of averaging time series under DTW and k-medoids is expensive)." This is not really the case, see cs.ucr.edu/~eamonn/ICDM_2014_DTW_average.pdf – eamonn Feb 12 '15 at 3:21