29
$\begingroup$

I would like to hierarchically cluster my data, but rather than using Euclidean distance, I'd like to use correlation. Also, since the correlation coefficient ranges from -1 to 1, with both -1 and 1 denoting "co-regulation" in my study, I am treating both -1 and 1 as d = 0. So my calculation is $\ d = 1-|r|$

I read in a separate question (regarding k-means clustering), that you should convert r into true euclidean d using the cosine theorem: $d = \sqrt{2(1-r)}$

What is the most accurate way to convert correlation to distance for hierarchical clustering?

$\endgroup$
2
  • 4
    $\begingroup$ Yes, one of possible - and geometrically true way - is the last formula. But you may disregard the sign of $r$ if it makes sense for you, so that $d^2=2(1-|r|)$. In most instances you may drop $2$ safely without affecting clustering results. The distance can be treated as squared euclidean. In this thread it was discussed whether distance-converted correlation measures are metric distances. $\endgroup$
    – ttnphns
    Aug 7, 2015 at 21:26
  • 3
    $\begingroup$ Also, you don't have to always convert $r$ into a linear dissimilarity such as euclidean distance. Not so rarely people do clustering based directly on $r$ or $|r|$ as on similarity;it is angular similarity $\endgroup$
    – ttnphns
    Aug 7, 2015 at 21:39

2 Answers 2

29
$\begingroup$

Requirements for hierarchical clustering

Hierarchical clustering can be used with arbitrary similarity and dissimilarity measures. (Most tools expect a dissimilarity, but will allow negative values - it's up to you to ensure whether small or large valued will be preferred.).

Only methods based on centroids or variance (such as Ward's method) are special, and should be used with squared Euclidean. (To understand why, please study these linkages carefully.)

Single-linkage, average-linkage, complete-linkage are not much affected, it will still be the minimum / average / maximum of the pairwise dissimilarities.

Correlation as distance measure

If you preprocess your data ($n$ observations, $p$ features) such that each feature has $\mu=0$ and $\sigma=1$ (which disallows constant features!), then correlation reduces to cosine:

$$ \text{Corr} (X,Y) = \frac{\text{Cov}(X, Y)} {\sigma_X \sigma_Y} = \frac{\mathbb{E} \left[ (X - \mu_X) (Y - \mu_Y) \right]} {\sigma_X \sigma_Y} = \mathbb{E} [XY] = \frac1n \left<X, Y\right> $$

Under the same conditions, squared Euclidean distance also reduces to cosine:

$$ d_\text{Euclid}^2(X,Y) = \sum (X_i - Y_i)^2 = \sum X_i^2 + \sum Y_i^2 - 2 \sum X_i Y_i \\ = 2n - 2\left<X, Y\right> = 2n \left[1 - \text{Corr}(X, Y)\right] $$

Therefore, unless your data is degenerate, using correlation for hierarchical clustering should be okay. Just preprocess it as explained above, then use squared Euclidean distance.

$\endgroup$
4
  • 2
    $\begingroup$ Only ward's method is special, and should be used with squared Euclidean. Not only Ward's. Any method computing centroids or deviations from centroids will need euclidean or squared euclidean (depending on the implementation) distance, for the sake of geometric precision. With loss of such and the due warning, they could be used with other metric distances. Those methods are centroid, "median", Ward's, variance (not to be confused with Ward's!) and some other. $\endgroup$
    – ttnphns
    Aug 8, 2015 at 8:45
  • $\begingroup$ Thanks, I've made that more clear. I wasn't aware of these variations, I was only thinking of single/average/complete/ward. $\endgroup$ Aug 8, 2015 at 9:58
  • 2
    $\begingroup$ There are a lot of typos and undefined expressions in this post! Could you please review it, fix it up, and explain what "$\langle, \rangle$" are and what "$dim$" might refer to? $\endgroup$
    – whuber
    Feb 17, 2019 at 22:54
  • $\begingroup$ "Therefore the corresponding agglomerative clustering methods can be used for any dissimilarity d and not only for the squared Euclidean distance." vlado.fmf.uni-lj.si/pub/preprint/ward.pdf $\endgroup$
    – O.rka
    Mar 17, 2021 at 18:10
1
$\begingroup$

I'll expand a bit on the accepted answer to show that in case we've standard-scaled the input data (let's assume it's n-dim), then both euclidean and correlation based distance metrics are just scaled variations of each other.

Euclidean distance for standard-scaled data is as follows: $$ E_d^2(X, Y) := \lVert X - Y \lVert^2 = \sum{x_i^2} + \sum{y_i^2} - 2\sum{x_i.y_i} = 2(n - X.Y) $$

The Pearson correlation is also expressed as: $$ \rho(X, Y) := \frac{1}{n} * {\sum(x_i - \bar{x})(y_i - \bar{y})}/{(\sigma_x * \sigma_y)} = \frac{1}{n} X.Y $$

Now, taking the $\rho$ based distance metric, we get $$ \rho_d(X, Y) := \left[{\frac{1 - \rho(X, Y)}{2}}\right]^\frac{1}{2} = \left[{\frac{1 - \frac{1}{n} X.Y}{2}}\right]^\frac{1}{2} $$ I chose this metric because it bounds the distance between 0 and 1. Any other constant would also work.

Now, if we take the ratio of these two metrics, we'll see $$ \frac{\rho_d}{E_d} := \frac{1}{2\sqrt{n}} $$ This ratio is constant when the dimensions are fixed.

$\endgroup$

Your Answer

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

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