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.
-
$\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
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:
-
$\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