Using Ward's method on a dissimilarity matrix of Gower distances

Question

I have a question regarding Wards method of hierarchical clustering. I used Gower Distance to create a dissimilarity matrix from an event log. I want to agglomerate it with Ward's method.

Lets suppose i have the following dissimilarity matrix as a starting point:

I now want to use Wards Method to find clusters. At the beginning, every single node is a cluster, so my clusters are 1,2,3,4,5. Now, in the first step, I want to add the two nodes to a cluster where the increase in variance is lowest.

My problem is: I do not have any values for the nodes themselves, only for the distances (the matrix you see in the picture is "all I have"). For calculating variance, I need the mean of each cluster, but I do not have them.

Is it even possible to use wards method in this case? Will I need to use other clustering methods, like Single Linkage?

Any help is greatly appreciated as I do not know how to continue.

Answer 1

1. Ward's linkage method (it is not a "variance" method, - it is the "increase of sum-of-squares" method) requires (squared) euclidean distances. See also.
2. Gower distance sqrt(1-GS) is geometrically "euclidean", so it suits, but 1-GS distance won't suit as geometrically "euclidean". See also.
3. You don't need to compute explicitly cluster centroids from the distance matrix (albeit you could). To do Ward linkage, you need to know SS of deviations from a cluster centroid. This is easily computable from the pairwise squared distances: the sum of squared deviations from centroid is equal to the sum of pairwise squared Euclidean distances divided by the number of points. See also.

But you don't have to do that (pt 3) operation from the individual points base level, on every step. (That would be slow and silly because you'll have to keep the initial size distance matrix throughout the agglomeration.) Hierarchical clustering is based on the generic Lance-Williams formula which updates distances on every step based on the distances observed at the previous step, on the reduced-size distance matrix.

In this answer, you'll see an example how the distance is updated in the centroid linkage method. For the Ward's method, the generic Lance-Williams formula unwraps as follows. Let us be on the step where clusters p and q have just merged into cluster t, and now the distances between t and every other existing cluster (or point) r are to be updated. They are computed by:

$D_{tr} = [(N_r+N_p)D_{rp}+(N_r+N_q)D_{rq}-N_rD_{pq}] / (N_r+N_t)$

where some "Dij" is the distance between clusters i and j, and Ni is the number of points in cluster i.

If the input distances are squared euclidean ones, that formula corresponds to the Ward's objective function $D_{tr} = 2[SS_{t+r}-(SS_t+SS_r)]$: distance computed between two clusters is the magnitude by which the summed square in their joint cluster will be greater than the combined summed square in the two clusters, - the quantity Ward selects to be minimal at each step.

Clearly, the multiplier $2$ can be avoided on the steps (in order to speed up the process). Just divide the squared distances in the input matrix by 2 before starting the agglomeration/computations. Then the above Lance-Williams formula will correspond to objective function without the unnecessary factor $2$.