L'inégalité triangulaire est-elle satisfaite pour ces distances basées sur la corrélation?

13

Pour le clustering hiérarchique, je vois souvent les deux "métriques" suivantes (elles ne parlent pas exactement) pour mesurer la distance entre deux variables aléatoires et Y : XY L'un ou l'autre remplit-il l'inégalité du triangle? Si oui, comment dois-je le prouver autrement que simplement faire un calcul de force brute? S'ils ne sont pas des métriques, qu'est-ce qu'un simple contre-exemple?

d1(X,Y)=1|Cor(X,Y)|,d2(X,Y)=1(Cor(X,Y))2
Linda
la source
Vous pourriez être intéressé par la révision de ce document: arxiv.org/pdf/1208.3145.pdf .
Chris

Réponses:

5

L' inégalité du triangle sur votre donnerait: d1

d1(X,Z)d1(X,Y)+d1(Y,Z)1|Cor(X,Z)|1|Cor(X,Y)|+1|Cor(Y,Z)||Cor(X,Y)|+|Cor(Y,Z)|1+|Cor(X,Z)|

Cela semble être une inégalité assez facile à vaincre. Nous pouvons rendre le côté droit aussi petit que possible (exactement un) en rendant et Z indépendants. Peut-on alors trouver un Y pour lequel le côté gauche dépasse un?XZY

Si et X et Z ont une variance identique, alors C o r ( X , Y ) = Y=X+ZXZet de même pourCor(Y,Z), donc le côté gauche est bien au-dessus de un et l'inégalité est violée. Exemple de cette violation dans R, oùXetZsont des composants d'une normale multivariée:Cor(X,Y)=220.707Cor(Y,Z)XZ

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

Notez cependant que cette construction ne fonctionne pas avec votre :d2

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

Plutôt que de lancer une attaque théorique sur , à ce stade, j'ai simplement trouvé plus facile de jouer avec la matrice de covariance dans R jusqu'à ce qu'un joli contre-exemple apparaisse. Si V a r ( X ) = 2 , V a r ( Z ) = 1 et C o v ( X , Z ) = 1 donne:d2SigmaVar(X)=2Var(Z)=1Cov(X,Z)=1

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

Nous pouvons également étudier les covariances:

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

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

Les corrélations au carré sont alors: Cor(X,Y)2=Cov(X,Y)2

Cor(X,Z)2=Cov(X,Z)2Var(X)Var(Z)=122×1=0.5
Cor(Y,Z)2=Cov(Y,Z)2
Cor(X,Y)2=Cov(X,Y)2Var(X)Var(Y)=322×5=0.9
Cor(Y,Z)2=Cov(Y,Z)2Var(Y)Var(Z)=225×1=0.8

Alors tandis que d 2 ( X , Y ) = 0,1 et d 2 ( Y , Z ) = 0,2 de sorte que l'inégalité du triangle est violée par une marge substantielle.d2(X,Z)=0.5d2(X,Y)=0.1d2(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
la source
5

XYZ

dXY2=2(n1)(1cosXY)cosXYrXY2(n1)

d1(X,Y)=1|Cor(X,Y)|

|r||r|

d

entrez la description de l'image ici

αβα+βrXYrXZrYZdXYdXZdYZXZα+β). C'est la position dans laquelle la violation de l'inégalité triangulaire par les distances au carré est la plus importante.

dYZ2>dXY2+dXZ2

Par conséquent, concernant

d1(X,Y)=1|Cor(X,Y)|

rd2

Qu'en est-il de la deuxième distance?

d2(X,Y)=1(Cor(X,Y))2

rcos1r2sin21r2SSerror/SStotalsin2

entrez la description de l'image ici

sinYZ2sinXY2+sinXZ2

sin(α+β)=sinαcosβ+cosαsinβsin2

sin2(α+β)=sin2α(1sin2β)+(1sin2α)sin2β+2sinαcosβcosαsinβ=sin2α+sin2β2[sin2αsin2β]+2[sinαcosαsinβcosβ]

sin2(α+β)>sin2α+sin2βαβ.1033.2132

αβ

ttnphns
la source
3

Voir aussi cette préimpression que j'ai écrite: http://arxiv.org/abs/1208.3145 . Je dois encore prendre du temps et le soumettre correctement. L'abstrait:

Nous étudions deux classes de transformations de similitude cosinus et les corrélations de Pearson et Spearman en distances métriques, en utilisant l'outil simple des fonctions de conservation métrique. La première classe place les objets anti-corrélés au maximum les uns des autres. Les transformations précédemment connues entrent dans cette classe. La deuxième classe rassemble les objets corrélés et anti-corrélés. Un exemple d'une telle transformation qui donne une distance métrique est la fonction sinus lorsqu'elle est appliquée à des données centrées.

Le résultat de votre question est que d1 , d2 ne sont en effet pas des métriques et que la racine carrée de d2 est en fait une métrique appropriée.

micans
la source
2

Non.

Contre-exemple le plus simple:

X=(0,0)Y

σ=0Cor

Il s'agit tout au plus d'une métrique sur un sous-ensemble de l'espace de données, sans aucune série constante.

A QUIT - Anony-Mousse
la source
Bon point! Je dois le mentionner dans la pré-impression mentionnée ailleurs.
micans