Czy nierówności trójkąta są spełnione dla tych odległości opartych na korelacji?

13

W przypadku hierarchicznego grupowania często widzę następujące dwie „metryki” (nie do końca mówią) do pomiaru odległości między dwiema losowymi zmiennymi i : Czy albo wypełnić trójkąt nierówności? Jeśli tak, to w jaki sposób mam to udowodnić, nie wykonując obliczeń brutalnej siły? Jeśli nie są to wskaźniki, to jaki jest prosty licznik? $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}$

— Linda
źródło

Możesz przejrzeć ten artykuł: arxiv.org/pdf/1208.3145.pdf .

— Chris

5

Nierówność trójkąta na $d_1$ przyniósłby: $\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*}$

Wydaje się to dość łatwą nierównością do pokonania. Możemy uczynić prawą stronę tak małą, jak to możliwe (dokładnie jedną), czyniąc $X$ i $Z$ niezależnymi. Czy możemy zatem znaleźć $Y$ dla którego lewa strona przekracza jedno?

Jeśli oraz i mają identyczną wariancję, to i podobnie dla , więc lewa strona znajduje się znacznie powyżej jednego, a nierówność zostaje naruszona. Przykład tego naruszenia w R, gdzie i są składnikami normalnej zmiennej na wielu odmianach: $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

Pamiętaj jednak, że ta konstrukcja nie działa z twoim : $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

Zamiast przeprowadzić teoretyczny atak na , na tym etapie po prostu łatwiej mi było bawić się macierzą kowariancji w R, dopóki nie pojawiła się ładna kontrprzykład. Dopuszczenie , i daje: $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$

Możemy również zbadać kowariancje:

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$

Kwadratowe korelacje to:

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$

Wtedy podczas gdy i więc nierówność trójkąta jest naruszona przez znaczny margines. $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
źródło

5

Miejmy trzy wektory (może to być zmienne lub osoby) , i . I każdy z nich znormalizowaliśmy do wyników Z (średnia = 0, wariancja = 1). $X$ $Y$ $Z$

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

Zatem zgodnie z twierdzeniem cosinus („prawo cosinusów”) kwadratowa odległość euklidesowa między dwoma znormalizowanymi wektorami (powiedzmy X i Y) wynosi , gdzie , podobieństwo cosinus, to Pearson ze względu na standaryzację z wektorów. Możemy bezpiecznie pominąć stały mnożnik naszych rozważaniach. $d_{XY}^2 = 2(n-1)(1-\cos_{XY})$ $\cos_{XY}$ $r_{XY}$ $2(n-1)$

Okazuje się zatem, że odległość wyrażona w pytaniu jakobyłby kwadratową odległością euklidesową, gdyby formuła nie ignorowała znaku współczynnika korelacji. $d_1(X,Y)=1-|\Cor(X,Y)|$

Jeśli macierzs zdarza się, że jest podzielan (dodatni półfinał), to pierwiastek kwadratowy z odległości „d1” jest odległością euklidesową, co jest oczywiście metryczne. Z niedużymi matrycamiczęsto jest to przypadek lub blisko przypadku, gdy odległości nie są dalekie od zbiegania się dobrze w przestrzeni euklidesowej. Ponieważ metryka jest szerszą klasą niż euklidesowa, dana matryca odległości „sqrt (d1)” mogłaby często pojawiać się jako metryka. $|r|$ $|r|$

Jeśli chodzi o „d1” jako takie, które jest „podobne” do kwadratu odległości euklidesowej, to jest zdecydowanie niemetryczne. Nawet prawdziwa kwadratowa odległość euklidesowa nie jest metryczna: czasami narusza zasadę nierówności trójkąta. [W analizie skupień często stosuje się kwadratową odległość euklidesową; jednak większość takich przypadków zakłada budowanie analizy na odległości nieprzekwadanej, przy czym kwadraty są po prostu wygodnym wkładem do obliczeń.] Aby to zobaczyć (o kwadratowym euklidesie ), narysujmy nasze trzy wektory. $d$

wprowadź opis zdjęcia tutaj

Wektory mają długość jednostkową (ponieważ są znormalizowane). Cosinus kątów ( , , ) to odpowiednio , , . Kąty te rozkładają odpowiednie odległości euklidesowe między wektorami: , , . Dla uproszczenia wszystkie trzy wektory znajdują się na tej samej płaszczyźnie (a zatem kąt między i jest sumą dwóch pozostałych, ). Jest to pozycja, w której najbardziej widoczne jest naruszenie nierówności trójkąta przez kwadraty odległości . $\alpha$ $\beta$ $\alpha+\beta$ $r_{XY}$ $r_{XZ}$ $r_{YZ}$ $d_{XY}$ $d_{XZ}$ $d_{YZ}$ $X$ $Z$ $\alpha+\beta$

Bo, jak widać oczami, zielony kwadrat przewyższa sumę dwóch czerwonych kwadratów: . $d_{YZ}^2 > d_{XY}^2 + d_{XZ}^2$

Dlatego dotyczący

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

odległość możemy powiedzieć, że nie jest metryczna. Ponieważ nawet gdy wszystkie były pierwotnie dodatnie, odległość jest euklidesowa która sama w sobie nie jest metryczna. $r$ $d^2$

Co jest z drugą odległością?

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

Ponieważ korelacja przypadku wektorów znormalizowanych wynosi , oznacza . (Rzeczywiście, jest regresją liniową, wielkością, która jest kwadratową korelacją zmiennej zależnej z czymś prostopadłym do predyktora.) W takim przypadku narysuj sinusy wektorów i ułóż je do kwadratu (ponieważ my mówią o odległości, która jest ): $r$ $\cos$ $1-r^2$ $\sin^2$ $1-r^2$ SSerror/SStotal $\sin^2$

wprowadź opis zdjęcia tutaj

Chociaż wizualnie nie jest to całkiem oczywiste, zielony jest ponownie większy niż suma czerwonych obszarów . $\sin_{YZ}^2$ $\sin_{XY}^2 + \sin_{XZ}^2$

Można to udowodnić. W samolocie . Wyprostuj obie strony, ponieważ jesteśmy zainteresowani . $\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}$

W ostatnim wyrażeniu dwa ważne terminy podano w nawiasach. Jeśli drugi z nich jest (lub może być) większy od pierwszego, wówczas , a odległość „d2” narusza trójkątna nierówność. I tak jest na naszym zdjęciu, gdzie wynosi około 40 stopni, a wynosi około 30 stopni (termin 1 to, a termin 2 to ). „D2” nie jest metryką. $\sin^2(\alpha+\beta) > \sin^2\alpha + \sin^2\beta$ $\alpha$ $\beta$ .1033.2132

Pierwiastek kwadratowy odległości „d2” - miara odmienności sinusoidalnej - jest jednak metryczny (jak sądzę). Aby się upewnić, możesz grać pod różnymi kątami i w moim kręgu. To, czy „d2” okaże się również metryczne w ustawieniach innych niż współliniowe (tj. Trzy wektory nie w płaszczyźnie) - nie mogę w tej chwili powiedzieć, choć wstępnie zakładam, że tak będzie. $\alpha$ $\beta$

— ttnphns
źródło

3

Zobacz także ten przedruk, który napisałem: http://arxiv.org/abs/1208.3145 . Nadal muszę poświęcić czas i odpowiednio go przesłać. Streszczenie:

Badamy dwie klasy transformacji podobieństwa cosinusowego oraz korelacje Pearsona i Spearmana w odległościach metrycznych, wykorzystując proste narzędzie funkcji zachowania metryk. Pierwsza klasa stawia maksymalnie przeciwlegle skorelowane obiekty. Wcześniej znane transformaty należą do tej klasy. Druga klasa zestawia obiekty skorelowane i anty-skorelowane. Przykładem takiej transformacji, która daje metryczną odległość, jest funkcja sinusoidalna po zastosowaniu do wyśrodkowanych danych.

Wynik twojego pytania jest taki , że d1 , d2 faktycznie nie są metrykami i że pierwiastek kwadratowy z d2 jest w rzeczywistości właściwą metryką.

— micans
źródło

2

Nie.

Najprostszy kontrprzykład:

dla odległość nie jest zdefiniowana w ogóle, niezależnie od jest. $X=(0,0)$ $Y$

Każda stała seria ma odchylenie standardowe , a zatem powoduje podział przez zero w definicji ... $\sigma=0$ $Cor$

Jest co najwyżej metryką w podzbiorze przestrzeni danych, nie uwzględniając żadnych stałych serii.

— Ma ZAKOŃCZENIE - Anony-Mus
źródło

Słuszna uwaga! Muszę o tym wspomnieć w przedruku wymienionym w innym miejscu.

— micans