Linkage method for hierarchical clustering of binary data

Question

I need to cluster datapoints that are represented as a binary vector, using hierarchical cluster. I chose the manhattan distance and am trying to figure out how to choose the "best" linkage method. I heard that Ward should not be used since it relies on euclidean distance. Is it true? I have not found any "real scientific" references. Are complete/single linkage methods better? Can you give any articles or papers as references?

Thanks!

Answer 1

There is no universal "best". It's your choice.

For example, complete linkage may be nice, because it means any two instances have at not h bits different at height h.

Or you may want average linkage, so that the average number of bits is h.

Or you may want minimax linkage, so that there exists one object, where all others are at most h bits different.

No mathematical reason to prefer one over the other. They are all reasonable to use.

Answer 2

I suppose I would employ cophentic correlation to identify which of the linkage methods mentioned above produces the dendrogram with the highest similarity to the underlying distance matrix.

The distance between two objects in your dendrogram and their first horizontal link, i.e. the point at which they branch off into two different groups, is called their cophenetic distance. There are functions calculating these cophenetic distances for all pairs of n objects, which results in a matrix of dimensions n x n. Now correlate this matrix with the underlying manhattan distance matrix, for all the dendograms you have identified with your different linkage methods, and see which dendogram produces the highest correlation.

Additionally, you can employ Gower's distance, which is the sum of squares difference between the cophenetic distances calculated from your dendrograms, and the underlying distance matrix.

For reference, see section 4.7 in Numerical Ecology with R by Borcard, Gillet and Legendre, 2011 (ISBN 978-1-4419-7975-9).