1
$\begingroup$

What are the exact assumptions behind the use of UPGMA? Can I use a non-Euclidean metric? This may result in a non-Euclidean distance matrix. What kind of bias may I encounter if I do so? References are appreciated.

$\endgroup$
1
  • $\begingroup$ Usually UPGMA is associated with ultrametric distances, where the triangle inequality $d(x,z) \le d(x,y) + d(y,z)$ is strengthened to $d(x,z) \le \max\{ d(x,y), d(y,z) \}$ (for every three points $x,y,z$). Equivalently this means that two of the distances $d(x,y), d(x,z), d(y,z)$ are equal and not smaller than the third. I believe this means that all the leaves in the reconstructed tree have the same distance to the root. Note that the usual euclidean distance is not ultrametric. I have no intuition on the consequences when this assumption is left out. $\endgroup$ – Hendrik Jan Feb 2 '17 at 23:40
1
$\begingroup$

While you can modify any algorithm as you see fit, in its pure form UPGMA has the following underlying assumptions at work:

UPGMA (Unweighted Pair-Group Method with Averages), arithmetic average - the average distance between elements of each cluster (weighted by the number of elements).

For example, (AB) and C+(DE) = (55+3x45)/3 = 63.33

Additional Comparative Algorithmic Context

Below is a list of algorithms and their general framework as it relates to each algorithm:

  • SINGLE (Single-link method) – brings together the closest elements.

  • WPGMA (Weighted Pair-Group Method with Averages), arithmetic average (not weighted by the number of elements).

  • WPGMC (Weighted Pair-Group Method with Centroid Average), centroid average (assumes dissimilarity).
  • WPGMS (Weighted Pair-Group Method with Spearman Average), Spearman's average (assumes correlation).

Reference for Modifying UPGMA

The paper below is a wonderful resource for "what-if" scenarios as it relates to UPGMA:

Vavrek, M. J. (2016). A comparison of clustering methods for biogeography with fossil datasets. PeerJ, 4, e1720. http://doi.org/10.7717/peerj.1720

$\endgroup$
2
  • $\begingroup$ This is definitely interesting, but I don't quite see how it answers the question. Does UPGMA assume that the distances are from a Euclidean metric (satisfy the triangle inequality) or not? If you use UPGMA with a distance matrix that doesn't satisfy the triangle inequality, does something go wrong? That's what the question seems to be asking, and I don't see a clear answer to that in your post. Can you edit the answer to more directly answer the question that was asked? $\endgroup$ – D.W. Dec 5 '16 at 1:30
  • $\begingroup$ Sorry but no, this does not answer my question, as noted by D.W. I know how UPGMA and other similar algorithms work. I need to know the assumptions. Isn't it meaningless for example to calculate an average distance between two clusters if the initial distance matrix is not Euclidean? If it is indeed, why precisely? If it is not, why again? $\endgroup$ – Kim Dec 5 '16 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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