Is triangle inequality fulfilled for these correlation-based distances?

Question

For hierarchical clustering I often see the following two "metrics" (they aren't exactly speaking) for measuring the distance between two random variables $X$ and $Y$: $\newcommand{\Cor}{\mathrm{Cor}}$ \begin{align} d_1(X,Y) &= 1-|\Cor(X,Y)|, \\ d_2(X,Y) &= 1-(\Cor(X,Y))^2 \end{align} Does either one fulfill the triangle inequality? If so how should I prove it other than just doing a bruteforce calculation? If they aren't metrics, what is a simple counter example?

Answer 1

The triangle inequality on your $d_1$ would yield: $\newcommand{\Cov}{\mathrm{Cov}}$ $\newcommand{\Cor}{\mathrm{Cor}}$ $\newcommand{\Var}{\mathrm{Var}}$

\begin{align*} d_1(X,Z) &\leq d_1(X,Y) + d_1(Y,Z) \\ 1 - |\Cor(X,Z)| &\leq 1 - |\Cor(X,Y)| + 1 - |\Cor(Y,Z)| \\ \implies |\Cor(X,Y)| + |\Cor(Y,Z)| &\leq 1 + |\Cor(X,Z)| \end{align*}

This seems quite an easy inequality to defeat. We can make the right-hand side as small as possible (exactly one) by making $X$ and $Z$ independent. Then can we find a $Y$ for which the left-hand side exceeds one?

If $Y=X+Z$ and $X$ and $Z$ have identical variance, then $\Cor(X,Y) = \frac{\sqrt{2}}{2} \approx 0.707$ and similarly for $\Cor(Y,Z)$, so the left-hand side is well above one and the inequality is violated. Example of this violation in R, where $X$ and $Z$ are components of a multivariate normal:

library(MASS)
set.seed(123)
d1 <- function(a,b) {1 - abs(cor(a,b))}

Sigma    <- matrix(c(1,0,0,1), nrow=2) # covariance matrix of X and Z
matrixXZ <- mvrnorm(n=1e3, mu=c(0,0), Sigma=Sigma, empirical=TRUE)
X <- matrixXZ[,1] # mean 0, variance 1
Z <- matrixXZ[,2] # mean 0, variance 1
cor(X,Z) # nearly zero
Y <- X + Z

d1(X,Y) 
# 0.2928932
d1(Y,Z)
# 0.2928932
d1(X,Z)
# 1
d1(X,Z) <= d1(X,Y) + d1(Y,Z)
# FALSE

Though note this construction doesn't work with your $d_2$:

d2 <- function(a,b) {1 - cor(a,b)^2}
d2(X,Y) 
# 0.5
d2(Y,Z)
# 0.5
d2(X,Z)
# 1
d2(X,Z) <= d2(X,Y) + d2(Y,Z)
# TRUE

Rather than launch a theoretical attack on $d_2$, at this stage I just found it easier to play around with the covariance matrix Sigma in R until a nice counterexample popped out. Allowing $\Var(X)=2$, $\Var(Z)=1$ and $\Cov(X,Z)=1$ gives:

$$\Var(Y)=\Var(X+Y)=\Var(X)+\Var(Z)+2\Cov(X,Z)=2+1+2=5$$

We can also investigate the covariances:

$$\Cov(X,Y)=\Cov(X,X+Z)=\Cov(X,X)+\Cov(X,Z)=2+1=3$$ $$\Cov(Y,Z)=\Cov(X+Z,Z)=\Cov(X,Z)+\Cov(Z,Z)=1+1=2$$

The squared correlations are then: $$\Cor(X,Z)^2 = \frac{\Cov(X,Z)^2}{\Var(X)\Var(Z)}=\frac{1^2}{2\times1}=0.5$$ $$\Cor(X,Y)^2 = \frac{\Cov(X,Y)^2}{\Var(X)\Var(Y)}=\frac{3^2}{2\times5}=0.9$$ $$\Cor(Y,Z)^2 = \frac{\Cov(Y,Z)^2}{\Var(Y)\Var(Z)}=\frac{2^2}{5\times1}=0.8$$

Then $d_2(X,Z)=0.5$ while $d_2(X,Y)=0.1$ and $d_2(Y,Z)=0.2$ so the triangle inequality is violated by a substantial margin.

Sigma    <- matrix(c(2,1,1,1), nrow=2) # covariance matrix of X and Z
matrixXZ <- mvrnorm(n=1e3, mu=c(0,0), Sigma=Sigma, empirical=TRUE)
X <- matrixXZ[,1] # mean 0, variance 2
Z <- matrixXZ[,2] # mean 0, variance 1
cor(X,Z) # 0.707
Y  <- X + Z
d2 <- function(a,b) {1 - cor(a,b)^2}
d2(X,Y) 
# 0.1
d2(Y,Z)
# 0.2
d2(X,Z)
# 0.5
d2(X,Z) <= d2(X,Y) + d2(Y,Z)
# FALSE

Answer 2

Let us have three vectors (it could be variables or individuals) $X$, $Y$, and $Z$. And we standardized each of them to z-scores (mean=0, variance=1).

$\newcommand{\Cor}{\mathrm{Cor}}$

Then according to cosine theorem ("law of cosines") squared euclidean distance between two standardized vectors (say, X and Y) is $d_{XY}^2 = 2(n-1)(1-\cos_{XY})$, where $\cos_{XY}$, the cosine similarity, is Pearson $r_{XY}$ due to z-standardization of vectors. We may safely omit $2(n-1)$ constant multiplier from our consideration.

So, it comes that the distance expressed in the question as $d_1(X,Y)=1-|\Cor(X,Y)|$ would be the squared euclidean distance if the formula were not ignoring the sign of the correlation coefficient.

If the matrix of $|r|$s happens to be gramian (positive semidefinite) then square root of "d1" distance is euclidean distance, which is metric of course. With not large matrices of $|r|$ it is often a case or near a case when the distances are not far from well converging in euclidean space. Since metric is a wider class than euclidean, a given matrix of distances "sqrt(d1)" might expect to appear metric quite often.

As for "d1" per se, which is "like" squared euclidean distance, it is definitely non-metric. Even true squared euclidean distance is not metric: it violates sometimes the triangle inequality principle. [In cluster analysis, squared euclidean distance is used quite often; however, the majority of such cases imply actually building the analysis on nonsquared distance, the squared ones being just a convenient input for calculations.] To see it (about squared euclidean $d$), let's draw our three vectors.

The vectors are unit-length (because standardized). Cosines of the angles ($\alpha$, $\beta$, $\alpha+\beta$) are $r_{XY}$, $r_{XZ}$, $r_{YZ}$, respectively. These angles spread corresponding euclidean distances between the vectors: $d_{XY}$, $d_{XZ}$, $d_{YZ}$. For simplicity, the three vectors are all on the same plane (and so the angle between $X$ and $Z$ is the sum of the two other, $\alpha+\beta$). It is the position in which the violation of triangle inequality by the distances squared is most prominent.

For, as you can see with eyes, the green square area excels the sum of the two red squares: $d_{YZ}^2 > d_{XY}^2 + d_{XZ}^2$.

Therefore regarding

$d_1(X,Y)=1-|\Cor(X,Y)|$

distance we can say it is not metric. Because even when all $r$s were originally positive the distance is the euclidean $d^2$ which itself isn't metric.

What is about the second distance?

$d_2(X,Y)=1-(\Cor(X,Y))^2$

Since correlation $r$ in the case of standardized vectors is $\cos$, $1-r^2$ is $\sin^2$. (Indeed, $1-r^2$ is SSerror/SStotal of a linear regression, a quantity which is the squared correlation of the dependent variable with something orthogonal to the predictor.) In that case draw the sines of the vectors, and make them squared (because we are talking about the distance which is $\sin^2$):

Although it is not quite obvious visually, the green $\sin_{YZ}^2$ square is again larger than the sum of red areas $\sin_{XY}^2 + \sin_{XZ}^2$.

It could be proved. On a plane, $\sin(\alpha+\beta) = \sin\alpha \cos\beta + \cos\alpha \sin\beta$. Square both sides since we are interested in $\sin^2$.

\begin{align} \sin^2(\alpha+\beta) &= \sin^2\alpha (1-\sin^2\beta) + (1-\sin^2\alpha) \sin^2\beta + 2 \sin\alpha \cos\beta \cos\alpha \sin\beta \\ &= \sin^2\alpha + \sin^2\beta -2 [\sin^2\alpha \sin^2\beta] +2 [\sin\alpha \cos\alpha \sin\beta \cos\beta] \end{align}

In the last expression, two important terms are shown bracketed. If the second of the two is (or can be) larger than the first one then $\sin^2(\alpha+\beta) > \sin^2\alpha + \sin^2\beta$, and the "d2" distance violates triangular inequality. And it is so on our picture where $\alpha$ is about 40 degrees and $\beta$ is about 30 degrees (term 1 is .1033 and term 2 is .2132). "D2" isn't metric.

The square root of "d2" distance - the sine dissimilarity measure - is metric though (I believe). You can play with various $\alpha$ and $\beta$ angles on my circle to make sure. Whether "d2" will show to be metric in a non-collinear setting (i.e. three vectors not on a plane) too - I can't say at this time, albeit I tentatively suppose it will.

Answer 3

See also this preprint that I wrote: http://arxiv.org/abs/1208.3145 . I still need to take time and properly submit it. The abstract:

We investigate two classes of transformations of cosine similarity and Pearson and Spearman correlations into metric distances, utilising the simple tool of metric-preserving functions. The first class puts anti-correlated objects maximally far apart. Previously known transforms fall within this class. The second class collates correlated and anti-correlated objects. An example of such a transformation that yields a metric distance is the sine function when applied to centered data.

The upshot for your question is that d1, d2 are indeed not metrics and that the square root of d2 is in fact a proper metric.

Answer 4

No.

Simplest counter-example:

for $X=(0,0)$ the distance is not defined at all, whatever your $Y$ is.

Any constant series has standard deviation $\sigma=0$, and thus causes a division by zero in the definition of $Cor$...

At most it is a metric on a subset of the data space, not including any constant series.