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

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 : \ newcommand {\ Cor} {\ mathrm {Cor}} \ begin {align} d_1 (X, Y) i = 1- | \ Cor (X, Y) |, \\ d_2 (X, Y) i = 1 - (\ Cor (X, Y)) ^ 2 \ end {align} 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{align} d_1(X,Y) &= 1-|\Cor(X,Y)|, \\ d_2(X,Y) &= 1-(\Cor(X,Y))^2 \end{align}$$

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

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$

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

Możemy również zbadać kowariancje:

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

Kwadratowe korelacje to:

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

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

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$

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$

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{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$

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ą.

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.