Выполняется ли неравенство треугольника для этих корреляционных расстояний?

13

Для иерархической кластеризации я часто вижу следующие две «метрики» (они точно не говорят) для измерения расстояния между двумя случайными переменными $X$ и $Y$ : $\newcommand{\Cor}{\mathrm{Cor}}$

\begin{aligned} d_{1} (X, Y) & = 1 - | C o r (X, Y) |, \\ d_{2} (X, Y) & = 1 - (C o r (X, Y))^{2} \end{aligned}

$\begin{align} d_1(X,Y) &= 1-|\Cor(X,Y)|, \\ d_2(X,Y) &= 1-(\Cor(X,Y))^2 \end{align}$ ли либо выполнить неравенство треугольника? Если так, то как мне доказать это, кроме как просто делать грубые расчеты? Если они не являются показателями, что является простым контрпримером?

correlation clustering distance metric Линда
источник

Вы можете быть заинтересованы в рецензировании этого документа: arxiv.org/pdf/1208.3145.pdf .

Крис

5

Неравенство треугольника на вашем $d_1$ даст: $\newcommand{\Cov}{\mathrm{Cov}}$ $\newcommand{\Cor}{\mathrm{Cor}}$ $\newcommand{\Var}{\mathrm{Var}}$

\begin{aligned} d_{1} (X, Z) & \leq d_{1} (X, Y) + d_{1} (Y, Z) \\ 1 - | C o r (X, Z) | & \leq 1 - | C o r (X, Y) | + 1 - | C o r (Y, Z) | \\ ⟹ | C o r (X, Y) | + | C o r (Y, Z) | & \leq 1 + | C o r (X, Z) | \end{aligned}

$\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*}$

Это, кажется, довольно простое неравенство, чтобы победить. Мы можем сделать правую часть как можно меньше (ровно одну), сделав $X$ и $Z$ независимыми. Тогда можем ли мы найти $Y$ для которого левая часть превышает единицу?

Если и и имеют одинаковую дисперсию, то и аналогично для , поэтому левая часть значительно выше единицы, и неравенство нарушается. Пример этого нарушения в R, где и - компоненты многомерной нормали: $Y=X+Z$ $X$ $Z$ $\Cor(X,Y) = \frac{\sqrt{2}}{2} \approx 0.707$ $\Cor(Y,Z)$ $X$ $Z$

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

Обратите внимание, что эта конструкция не работает с вашим : $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

Вместо того, чтобы начинать теоретическую атаку на , на этом этапе мне просто было проще поиграть с ковариационной матрицей в R, пока не хороший контрпример. Если , и получим: $d_2$ Sigma $\Var(X)=2$ $\Var(Z)=1$ $\Cov(X,Z)=1$

V a r (Y) = V a r (X + Y) = V a r (X) + V a r (Z) + 2 C o v (X, Z) = 2 + 1 + 2 = 5

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

Мы также можем исследовать ковариации:

C o v (X, Y) = C o v (X, X + Z) = C o v (X, X) + C o v (X, Z) = 2 + 1 = 3

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

C o v (Y, Z) = C o v (X + Z, Z) = C o v (X, Z) + C o v (Z, Z) = 1 + 1 = 2

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

Тогда квадратные корреляции:

C o r (X, Z)^{2} = \frac{C o v (X, Z)^{2}}{V a r (X) V a r (Z)} = \frac{1^{2}}{2 \times 1} = 0.5

$\Cor(X,Z)^2 = \frac{\Cov(X,Z)^2}{\Var(X)\Var(Z)}=\frac{1^2}{2\times1}=0.5$

C o r (X, Y)^{2} = \frac{C o v (X, Y)^{2}}{V a r (X) V a r (Y)} = \frac{3^{2}}{2 \times 5} = 0.9

$\Cor(X,Y)^2 = \frac{\Cov(X,Y)^2}{\Var(X)\Var(Y)}=\frac{3^2}{2\times5}=0.9$

C o r (Y, Z)^{2} = \frac{C o v (Y, Z)^{2}}{V a r (Y) V a r (Z)} = \frac{2^{2}}{5 \times 1} = 0.8

$\Cor(Y,Z)^2 = \frac{\Cov(Y,Z)^2}{\Var(Y)\Var(Z)}=\frac{2^2}{5\times1}=0.8$

Тогда тогда как и поэтому неравенство треугольника существенно нарушается. $d_2(X,Z)=0.5$ $d_2(X,Y)=0.1$ $d_2(Y,Z)=0.2$

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

тарпон
источник

5

Давайте три вектора (это может быть переменными или физическими лицами) , и . И мы стандартизировали каждый из них по z-баллам (среднее = 0, дисперсия = 1). $X$ $Y$ $Z$

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

Тогда согласно теореме косинуса ("закон косинусов") квадрат евклидова расстояния между двумя стандартизированными векторами (скажем, X и Y) будет , где , косинусное сходство, является Пирсоном из-за z-стандартизации векторов. Мы можем смело опустить константу множителя из нашего рассмотрения. $d_{XY}^2 = 2(n-1)(1-\cos_{XY})$ $\cos_{XY}$ $r_{XY}$ $2(n-1)$

Итак, получается, что расстояние, выраженное в вопросе какбыло бы квадратом евклидова расстояния, если бы формула не игнорировала знак коэффициента корреляции. $d_1(X,Y)=1-|\Cor(X,Y)|$

Если матрицаs оказывается градиентным (положительный полуопределенный), тогда корень квадратный из расстояния "d1" - это евклидово расстояние, которое, конечно, является метрикой. С небольшими матрицамиэто часто бывает или почти всегда, когда расстояния не очень хорошо сходятся в евклидовом пространстве. Поскольку метрика является более широким классом, чем евклидова, данная матрица расстояний "sqrt (d1)" может ожидать появления метрики довольно часто. $|r|$ $|r|$

Что касается «d1» как такового, которое является «подобным» квадрату евклидова расстояния, оно определенно неметрическое. Даже истинное квадратное евклидово расстояние не является метрикой: оно иногда нарушает принцип неравенства треугольника. [В кластерном анализе квадрат евклидова расстояния используется довольно часто; тем не менее, в большинстве таких случаев подразумевается построение анализа на неквадратном расстоянии, а квадраты - просто удобный вход для вычислений.] Чтобы увидеть это (о квадрате евклидова ), давайте нарисуем наши три вектора. $d$

введите описание изображения здесь

Векторы имеют единичную длину (потому что стандартизированы). Косинусы углов ( , , ) равны , , соответственно. Эти углы распространяют соответствующие евклидовы расстояния между векторами: , , . Для простоты все три вектора находятся в одной плоскости (и поэтому угол между и является суммой двух других, ). Это положение, в котором нарушение неравенства треугольника квадратами расстояний является наиболее заметным. $\alpha$ $\beta$ $\alpha+\beta$ $r_{XY}$ $r_{XZ}$ $r_{YZ}$ $d_{XY}$ $d_{XZ}$ $d_{YZ}$ $X$ $Z$ $\alpha+\beta$

Ибо, как вы можете видеть глазами, площадь зеленого квадрата превышает сумму двух красных квадратов: . $d_{YZ}^2 > d_{XY}^2 + d_{XZ}^2$

Поэтому относительно

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

Расстояние можно сказать, что это не метрика. Потому что даже когда все были изначально положительными, расстояние является евклидовым которое само не является метрическим. $r$ $d^2$

Что насчет второй дистанции?

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

Поскольку корреляция в случае стандартизированных векторов равна , есть . (Действительно, - это линейная регрессия, величина, которая является квадратом корреляции зависимой переменной с чем-то, ортогональным к предиктору.) В этом случае нарисуйте синусы векторов и сделайте их квадратными (потому что мы речь идет о расстоянии, которое ): $r$ $\cos$ $1-r^2$ $\sin^2$ $1-r^2$ SSerror/SStotal $\sin^2$

введите описание изображения здесь

Хотя визуально это не совсем очевидно, зеленый снова больше, чем сумма красных областей . $\sin_{YZ}^2$ $\sin_{XY}^2 + \sin_{XZ}^2$

Это может быть доказано. На плоскости . Квадрат с обеих сторон, так как мы заинтересованы в . $\sin(\alpha+\beta) = \sin\alpha \cos\beta + \cos\alpha \sin\beta$ $\sin^2$

\begin{aligned} \sin^{2} (α + β) & = \sin^{2} α (1 - \sin^{2} β) + (1 - \sin^{2} α) \sin^{2} β + 2 \sin α \cos β \cos α \sin β \\ = \sin^{2} α + \sin^{2} β - 2 [\sin^{2} α \sin^{2} β] + 2 [\sin α \cos α \sin β \cos β] \end{aligned}

$\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}$

В последнем выражении два важных термина показаны в скобках. Если второе из этих двух (или может быть) больше первого, то и расстояние "d2" нарушается треугольное неравенство. И это так на нашей картинке, где составляет около 40 градусов, а составляет около 30 градусов (термин 1 равен, а термин 2 есть ). «D2» не является метрической $\sin^2(\alpha+\beta) > \sin^2\alpha + \sin^2\beta$ $\alpha$ $\beta$ .1033.2132

Квадратный корень расстояния "d2" - синусоидальной меры - хотя и метрический (я считаю). Вы можете играть с различными углами и на моем круге, чтобы убедиться. Будет ли «d2» показывать метрику в неколлинеарной обстановке (т. Е. Три вектора не на плоскости) - я пока не могу сказать, хотя предположительно предположу, что так и будет. $\alpha$ $\beta$

ttnphns
источник

3

Смотрите также этот препринт, который я написал: http://arxiv.org/abs/1208.3145 . Мне все еще нужно время и правильно представить его. Аннотация:

Мы исследуем два класса преобразований косинусного сходства и корреляций Пирсона и Спирмена в метрические расстояния, используя простой инструмент функций, сохраняющих метрику. Первый класс помещает антикоррелированные объекты максимально далеко друг от друга. Ранее известные преобразования попадают в этот класс. Второй класс сопоставляет коррелированные и антикоррелированные объекты. Примером такого преобразования, которое дает метрическое расстояние, является функция синуса при применении к центрированным данным.

В результате ваш вопрос заключается в том , что d1 , d2 действительно не являются метриками и что квадратный корень из d2 на самом деле является правильной метрикой.

micans
источник

2

Нет.

Простейший контрпример:

для расстояние не определяется вообще, независимо от вашего есть. $X=(0,0)$ $Y$

Любой ряд констант имеет стандартное отклонение , и, следовательно, вызывает деление на ноль в определении ... $\sigma=0$ $Cor$

Самое большее, это метрика в подмножестве пространства данных, не включающая в себя никаких постоянных рядов.

ВЫЙТИ - Anony-Mousse
источник

Хорошая точка зрения! Я должен упомянуть об этом в препринте, упомянутом в другом месте.

micans

Выполняется ли неравенство треугольника для этих корреляционных расстояний?

Ответы: