A desigualdade do triângulo é cumprida para essas distâncias baseadas em correlação?

13

Para cluster hierárquico, geralmente vejo as duas "métricas" a seguir (elas não estão falando exatamente) para medir a distância entre duas variáveis aleatórias e : faz tanto alguém cumpre a desigualdade do triângulo? Em caso afirmativo, como devo provar isso, além de apenas fazer um cálculo de força bruta? Se não são métricas, o que é um exemplo simples de contador? $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 Linda
fonte

Você pode estar interessado em revisar este artigo: arxiv.org/pdf/1208.3145.pdf .

31516 Chris

5

A desigualdade de triângulo no seu renderia: $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*}$

Parece uma desigualdade bastante fácil de derrotar. Podemos tornar o lado direito o menor possível (exatamente um), tornando e independentes. Então, podemos encontrar um para o qual o lado esquerdo excede um? $X$ $Z$ $Y$

Se e e tiverem variação idêntica, então e da mesma forma para , então o lado esquerdo está bem acima de um e a desigualdade é violada. Exemplo desta violação em R, onde e são componentes de uma normal multivariada: $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

Observe que essa construção não funciona com o seu : $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

Em vez de lançar um ataque teórico em , nesse estágio, achei mais fácil brincar com a matriz de covariância em R até que um bom contra-exemplo tenha surgido. Permitindo , e fornece: $d_2$ Sigma $\Var(X)=2$ $\Var(Z)=1$ $\Cov(X,Z)=1$

V uma r (Y) = V uma r (X + Y) = V uma r (X) + V uma 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$

Também podemos investigar as covariâncias:

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$

As correlações ao quadrado são:

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$

Então enquanto e assim a desigualdade triangular é violada por uma margem substancial. $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

Silverfish
fonte

5

Vamos ter três vectores (que poderia ser variáveis ou indivíduos) , , e . E padronizamos cada um deles para escores z (média = 0, variação = 1). $X$ $Y$ $Z$

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

Então, de acordo com o teorema do cosseno ("lei dos cossenos"), a distância euclidiana quadrada entre dois vetores padronizados (digamos, X e Y) é , onde , a semelhança de cosseno, é Pearson devido à padronização z de vetores. Podemos omitir com segurança multiplicador constante de nossa consideração. $d_{XY}^2 = 2(n-1)(1-\cos_{XY})$ $\cos_{XY}$ $r_{XY}$ $2(n-1)$

Então, a distância expressa na pergunta comoseria a distância euclidiana ao quadrado se a fórmula não estivesse ignorando o sinal do coeficiente de correlação. $d_1(X,Y)=1-|\Cor(X,Y)|$

Se a matriz des é gramiano (semidefinido positivo), então a raiz quadrada da distância "d1" é a distância euclidiana, que é métrica, é claro. Com matrizes não grandes degeralmente é um caso ou quase um caso em que as distâncias não estão muito longe de convergir no espaço euclidiano. Como a métrica é uma classe mais ampla que a euclidiana, uma determinada matriz de distâncias "sqrt (d1)" pode esperar parecer métrica com bastante frequência. $|r|$ $|r|$

Quanto ao "d1" em si, que é "como" a distância euclidiana quadrada , é definitivamente não-métrico. Até a verdadeira distância euclidiana quadrada não é métrica: ela às vezes viola o princípio da desigualdade do triângulo. [Na análise de agrupamentos, a distância euclidiana ao quadrado é usada com bastante frequência; no entanto, a maioria desses casos implica, na verdade, construir a análise em distâncias não quartadas, sendo os quadrados apenas uma entrada conveniente para cálculos.] Para vê-lo (sobre o quadrado euclidiano ), vamos desenhar nossos três vetores. $d$

insira a descrição da imagem aqui

Os vetores são de tamanho unitário (porque padronizados). Os cossenos dos ângulos ( , , ) são , , , respectivamente. Esses ângulos espalham as distâncias euclidianas correspondentes entre os vetores: , , . Por simplicidade, os três vetores estão todos no mesmo plano (e, portanto, o ângulo entre e é a soma dos outros dois, ). É a posição em que a violação da desigualdade do triângulo pelas distâncias ao quadrado é mais proeminente. $\alpha$ $\beta$ $\alpha+\beta$ $r_{XY}$ $r_{XZ}$ $r_{YZ}$ $d_{XY}$ $d_{XZ}$ $d_{YZ}$ $X$ $Z$ $\alpha+\beta$

Pois, como você pode ver com os olhos, a área quadrada verde supera a soma dos dois quadrados vermelhos: . $d_{YZ}^2 > d_{XY}^2 + d_{XZ}^2$

Portanto, com relação a

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

distância, podemos dizer que não é métrico. Porque mesmo quando todos os s eram originalmente positivos, a distância é o euclidiano, que por si só não é métrico. $r$ $d^2$

Qual é a segunda distância?

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

Como a correlação no caso de vetores padronizados é , é . (De fato, é de regressão linear, uma quantidade que é a correlação ao quadrado da variável dependente com algo ortogonal ao preditor.) Nesse caso, desenhe os senos dos vetores e faça-os ao quadrado (porque nós estão falando sobre a distância que é ): $r$ $\cos$ $1-r^2$ $\sin^2$ $1-r^2$ SSerror/SStotal $\sin^2$

insira a descrição da imagem aqui

Embora não seja visualmente óbvio visualmente, o verde é novamente maior que a soma das áreas vermelhas . $\sin_{YZ}^2$ $\sin_{XY}^2 + \sin_{XZ}^2$

Isso poderia ser provado. Em um plano, . Esquadre os dois lados, pois estamos interessados em . $\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}$

Na última expressão, dois termos importantes são mostrados entre colchetes. Se o segundo dos dois for (ou puder ser) maior que o primeiro, então , e a distância "d2" violará desigualdade triangular. E é assim em nossa imagem que é de cerca de 40 graus e é de cerca de 30 graus (termo 1 é e termo 2 é ). "D2" não é métrico. $\sin^2(\alpha+\beta) > \sin^2\alpha + \sin^2\beta$ $\alpha$ $\beta$ .1033.2132

A raiz quadrada da distância "d2" - a medida da dissimilaridade senoidal - é métrica (acredito). Você pode jogar com vários ângulos e no meu círculo para ter certeza. Se "d2" se mostrará métrico em uma configuração não colinear (ou seja, três vetores que não estão em um avião) também - não posso dizer neste momento, embora suponho provisoriamente que sim. $\alpha$ $\beta$

ttnphns
fonte

3

Veja também esta pré-impressão que escrevi: http://arxiv.org/abs/1208.3145 . Ainda preciso reservar um tempo e enviá-lo adequadamente. O resumo:

Investigamos duas classes de transformações de similaridade de cosseno e correlações de Pearson e Spearman em distâncias métricas, utilizando a ferramenta simples de funções de preservação de métricas. A primeira classe coloca objetos anti-correlacionados maximamente separados. As transformações conhecidas anteriormente se enquadram nessa classe. A segunda classe coleta objetos correlacionados e anti-correlacionados. Um exemplo dessa transformação que gera uma distância métrica é a função seno quando aplicada a dados centralizados.

O resultado positivo para sua pergunta é que d1 , d2 não são realmente métricas e que a raiz quadrada de d2 é de fato uma métrica adequada.

micans
fonte

2

Não.

Contra-exemplo mais simples:

para a distância não é definido em tudo, seja qual for seu é. $X=(0,0)$ $Y$

Qualquer série constante tem desvio padrão e, portanto, causa uma divisão por zero na definição de ... $\sigma=0$ $Cor$

No máximo, é uma métrica em um subconjunto do espaço de dados, sem incluir nenhuma série constante.

Possui QUIT - Anony-Mousse
fonte

Bom ponto! Devo mencionar isso na pré-impressão mencionada em outro lugar.

micans

A desigualdade do triângulo é cumprida para essas distâncias baseadas em correlação?

Respostas: