(hierarchical) cluster analysis with non-standard distance

Question

My question is triggered by a question that was asked on stackoverflow: https://stackoverflow.com/questions/12198115/using-different-metric-for-hclust-linkage.

The thing is this:

I can formulate an algorithm for hierarchical clustering with some kind of distance between original objects, and I'll also need a distance between objects and clusters of objects (linkage).

Let's say the linkage attaches a "handle" to the cluster which is a (hypothetic) object that can be used with the distance function to calculate the distance from another object (or cluster, if it has such a "handle").

For consistency, I'd use the same distance function for the initial calculation of distance between single objects and later for distance between objects or "cluster handles".

So far, so good.

What I'm wondering about is: what happens if the cluster algorithm is fed with a distance matrix instead of the data matrix (as it is e.g. the case with R's hclust).

• How do I know which distance function on the distance matrix agrees with what distance function on the data matrix? Examples?
• The more basic maths/statistics question underlying this is: please explain to me (chemist, no mathematician/statistician) what the meaning of e.g. Euclidean distance between rows of a distance matrix is?

Answer 1

A somewhat complicated answer to your first question about distances goes like this.

Rencher's Multivariate Analysis cites Lance and Williams (1967) who proposed a general (flexible beta) method underlying most of the existing hierarchical cluster analysis: for three objects A, B and C, be that clusters or individual points considered to be clusters of size 1, if clusters A and B are joined into AB, then the new distance from AB to C can be expressed by $$ d(AB,C) = \alpha_A d(C,A) + \alpha_B d(C,B) + \beta d(A,B) + \gamma| d(C,A) - d(C,B) |, $$ They suggested $\alpha_A + \alpha_B + \beta=1$, $\alpha_A = \alpha_B$, $\gamma=0$ and $\beta < 1$, although you could try other choices. E.g., single linkage is $\alpha_A = \alpha_B = 1/2$, $\beta=0$, $\gamma=-1/2$ (contracting the space), complete linkage is the same except for $\gamma=1/2$ (diluting the space), and Ward's method is $\alpha_A = (n_A + n_C)/(n_A + n_B + n_C)$, $\alpha_B = (n_B + n_C)/(n_A + n_B + n_C)$, $\beta= - n_C/(n_A + n_B + n_C)$, and $\gamma=0$ (somewhat space-contracting). The book discusses the properties of the algorithms, such as monotonicity and space contraction/dilution as functions of these parameters.

So an algorithm can be build just based on the distances, and does not need the data matrix. However, the distance matrix for typical problems (sample size $n$ > dimension of the data $p$) takes more memory than the data matrix, so this may not be a very efficient way of approaching the problem, unless of course the data matrix is all you have.

Answer 2

Many of the linkage distances are computed on a set of pairwise distances. Then this works just fine with a distance matrix. So most of the time, while the intuition is to have a "handle", what is being done is more a statistical approach.

E.g. single-linkage is the minimum distance, and average linkage is the mean distance taken from the submatrix connecting the two clusters.

Note that for efficiency, you will often want to avoid computing the distance matrix (which needs $O(n^2)$ memory) in the first place. I guess the main reason why this is frequently been done is because it allows you to easily plug in other distances, hierarchical clustering is sensible for tiny data sets only in the first place (the naive algorithm has $O(n^3)$ run time!) and because the operation of computing pairwise distances is available as a highly optimized native C operation, which is significantly faster than anything done in the R interpreter.

As for your question on computing a distance on the rows/cols in the distance matrix: I don't think this is a very sensible measure. As each entry is a distance, it corresponds to a RMSE of distance similarity of two objects. I.e. "the object is as far to all other objects as the other". But there are some related methods used for high dimensional data, that choose a number of reference objects (but not the whole database!) and judge object similarity by how similar the distances to these reference points are. So sometimes, this seems to work quite well; but I wouldn't choose the whole data set as reference objects; after all you want to keep dimensionality low (and one reference object ~ one dimension!) and get below $O(n^2)$ runtime. With this approach, you need the full distance matrix, which is a lot of (possibly redundant) computations and memory.