4

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
set.seed(91)
(df=data.frame(trait1=runif(10,0,10),trait2=runif(10,0,10),
               trait3=sample(letters[1:3],10,replace=T),row.names=paste("sp",1:10,sep="")))

#Generate Gower dissimilarity matrix from trait data
library(cluster)
(dist.gower=daisy(df,metric="gower"))

#Create a vector of clustering methods
tree.methods=c("ward","single","complete","average","mcquitty","median","centroid")  
#Build the trees using each method
trees=lapply(tree.methods,function(i) hclust(dist.gower,method=i))  
#Plot the trees
par(mfrow=c(4,2))
for(i in 1:length(trees)) {plot(trees[[i]])}
#The last two trees have reversals...cannot be converted to ultrametric!
ttnphns
  • 51,648
  • 40
  • 253
  • 462
jslefche
  • 165
  • 1
  • 7

1 Answers1

7

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

ttnphns
  • 51,648
  • 40
  • 253
  • 462
  • @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? – jslefche Apr 19 '12 at 17:19
  • 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](http://en.wikipedia.org/wiki/Metric_(mathematics)). See also [this](http://stats.stackexchange.com/questions/13873/does-a-distance-have-to-be-a-metric-for-an-hierarchical-clustering-to-be-valid/13889#13889). – ttnphns Apr 19 '12 at 17:36
  • What if I convert the Gower distances to Euclidean using Principal Coordinates Analysis? – jslefche Apr 21 '12 at 16:46
  • You could as well make configuration euclidean by simply adding constant to the distances. In any case your distances won't be Gower anymore! – ttnphns Apr 21 '12 at 18:42