I'm attempting to perform hierarchical agglomerative cluster analysis in R.

However, when I use particular clustering methods, I get reversals (upward branching) in the resulting tree, which violates the ultrametric property.

enter image description here

The two methods are: UPGMC and WPGMC (methods="median" and "centroid" in hclust). Legendre & Legendre in their Numerical Ecology book suggest some reasons why this may occur (Section 8.6). However, they provide no solutions to rectify the issue and convert the trees to ultrametric.

I'm curious: is this an unavoidable consequence of the data and the clustering method, or is there a way that I can produce a tree that satisfies the ultrametric property using these two methods?

Here is an example data set and R code to play with:

#Generate data frame with mixed continuous and categorical trait data for 10 species

#Generate Gower dissimilarity matrix from trait data

#Create a vector of clustering methods
#Build the trees using each method
trees=lapply(tree.methods,function(i) hclust(dist.gower,method=i))  
#Plot the trees
for(i in 1:length(trees)) {plot(trees[[i]])}
#The last two trees have reversals...cannot be converted to ultrametric!

1 Answer 1


This is unavoidable consequence of the data and the clustering method. Centroid and median agglomerations can produce such "reversals" with some data. Because, in principle, distance between cluster centres can diminish on a later step of agglomeration.

Most practical way out is to ignore the fact that the reversal occured and to align the "sunk" senior (later) cross-bars with the highest cross-bar which is junior (earlier) to it. Like I show below.

One more notion. In your place, I'd refrain from using geometric methods (centroid, median, Ward) - suitable for euclidean distance - with nonmetric Gower coefficient.

enter image description here

  • $\begingroup$ @ttnphns--Thanks for your response! I like your corrected diagram. I have simply excluded these two methods from my analysis...but out of curiosity, do you have a reference for your last point re: geometric methods and the nonmetric distances? $\endgroup$
    – jslefche
    Apr 19, 2012 at 17:19
  • $\begingroup$ The 3 methods I cite are called "geometric" in some texts because they are engaged in calculating cluster centroids in euclidean space. Thus, they call for euclidean distance as input. Gower (dis)similarity is far not euclidean, it is generally non-metric. See also this. $\endgroup$
    – ttnphns
    Apr 19, 2012 at 17:36
  • $\begingroup$ What if I convert the Gower distances to Euclidean using Principal Coordinates Analysis? $\endgroup$
    – jslefche
    Apr 21, 2012 at 16:46
  • $\begingroup$ You could as well make configuration euclidean by simply adding constant to the distances. In any case your distances won't be Gower anymore! $\endgroup$
    – ttnphns
    Apr 21, 2012 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.