Is it ok to use Manhattan distance with Ward's inter-cluster linkage in hierarchical clustering?

Question

I am using hierarchical clustering to analyze time series data. My code is implemented using the Mathematica function DirectAgglomerate[...], which generates hierarchical clusters given the following inputs:

• a distance matrix D

• the name of the method used to determine inter-cluster linkage.

I have calculated the distance matrix D using Manhattan distance:

$$d(x,y) = \sum_i|x_i - y_i|$$

where $i = 1,\cdots, n$ and $n \approx 150$ is the number of data points in my time series.

My question is, is it ok to use Ward's inter-cluster linkage with a Manhattan distance matrix? Some sources suggest that Ward's linkage should only be used with Euclidean distance.

Note that DirectAgglomerate[...] calculates Ward's linkage using the distance matrix only, not the original observations. Unfortunately, I am unsure how Mathematica modifies Ward's original algorithm, which (from my understanding) worked by minimizing the error sum of squares of the observations, calculated with respect to the cluster mean. For example, for a cluster $c$ consisting of a vector of univariate observations, Ward formulated the error sum of squares as:

$$(\sum_j||c_j - mean(c)||_2)^2$$

(Other software tools such as Matlab and R also implement Ward's clustering using just a distance matrix so the question isn't specific to Mathematica.)

Answer 1

The Ward clustering algorithm is a hierarchical clustering method that minimizes an 'inertia' criteria at each step. This inertia quantifies the sum of squared residuals between the reduced signal and the initial signal: it is a measure of the variance of the error in an l2 (Euclidean) sens. Actually, you even mention it in your question. This is why, I believe, it makes no sens to apply it to a distance matrix that is not a l2 Euclidean distance.

On the other hand, an average linkage or a single linkage hierarchical clustering would be perfectly suitable for other distances.

Answer 2

I can't think of any reason why Ward should favor any metric. Ward's method is just another option to decide which clusters to fusion next during agglomeration. This is achieved by finding the two clusters whose fusion will minimize a certain error (examplary source for the formula).

Hence it relies on two concepts:

1. The mean of vectors which (for numerical vectors) is generally calculated by averaging over every dimension separately.
2. The distance metric itself i.e. the concept of similarity expressed by this metric.

So: As long as the properties of the choosen metric (like e.g. rotation,translation or scale invariance) satisfy your needs (and the metric fits to the way the cluster mean is calculated), I don't see any reason to not use it.

I suspect that most people suggest the euclidean metric because they

• want to increase the weight of the differences between a cluster mean and a single observation vector (which is done by quadration)
• or because it came out as best metric in the validation based on their data
• or because it is used in general.

Answer 3

Another way of thinking about this, which might lend itself to an adaptation for $\ell_1$ is that choice of the mean comes from the fact that the mean is the point that minimizes the sum of squared Euclidean distances. If you're using $\ell_1$ to measure the distance between time series, then you should be using a center that minimizes the sum of squared $\ell_1$ distances.

Answer 4

Although Ward is meant to be used with Euclidean distances, this paper suggests that the clustering results using Ward and non-euclidean distances are essentially the same as if they had been used with Euclidean distances as it is meant to be.

It is shown that the result from the Ward method to a non positive-definite and normalized similarity is almost the same as another result from the Ward method to a positive-definite matrix obtained from the original similarity by adding a positive constant to the diagonal elements.

S. Miyamoto, R. Abe, Y. Endo and J. Takeshita, "Ward method of hierarchical clustering for non-Euclidean similarity measures," 2015 7th International Conference of Soft Computing and Pattern Recognition (SoCPaR), Fukuoka, 2015, pp. 60-63, doi: 10.1109/SOCPAR.2015.7492784.