Conversion de la matrice de similarité en matrice de distance (euclidienne)

Dans l'algorithme de forêt aléatoire, Breiman (auteur) construit la matrice de similarité comme suit:

1. Envoyez tous les exemples d'apprentissage dans chaque arbre de la forêt

2. Si deux exemples atterrissent dans le même incrément de feuille élément correspondant dans la matrice de similarité de 1

3. Normaliser la matrice avec le nombre d'arbres

Il dit:

Les proximités entre les cas n et k forment une matrice {prox (n, k)}. D'après leur définition, il est facile de montrer que cette matrice est symétrique, définie positive et bornée au-dessus de 1, avec les éléments diagonaux égaux à 1. Il s'ensuit que les valeurs 1-prox (n, k) sont des distances au carré dans un Euclidien espace de dimension non supérieur au nombre de cas. La source

Dans son implémentation, il utilise sqrt (1-prox) , où prox est une matrice de similarité, pour la convertir en matrice de distance. Je suppose que cela a quelque chose à voir avec les "distances au carré dans un espace euclidien", citées ci-dessus.

Quelqu'un peut-il expliquer pourquoi il s'ensuit que les 1-prox sont des distances au carré dans un espace euclidien et pourquoi il utilise la racine au carré pour obtenir la matrice de distance?

Selon le théorème du cosinus , dans l'espace euclidien, la distance au carré (euclidienne) entre deux points (vecteurs) 1 et 2 est . Les longueurs au carré et sont les sommes des coordonnées au carré des points 1 et 2, respectivement (ce sont les hypoténuses pythagoriciennes). La quantité est appelée produit scalaire (= produit scalaire , = produit interne) des vecteurs 1 et 2.$d_{12}^2 = h_1^2+h_2^2-2h_1h_2\cos\phi$$h_1^2$$h_2^2$$h_1h_2\cos\phi$

Le produit scalaire est également appelé une similitude de type angle entre 1 et 2, et dans l'espace euclidien, il est géométriquement la mesure de similitude la plus valide , car il est facilement converti en distance euclidienne et vice versa (voir également ici ).

Le coefficient de covariance et la corrélation de Pearson sont des produits scalaires. Si vous centrez vos données multivariées (de sorte que l'origine soit au centre du nuage de points), alors est normalisé les variances des vecteurs (pas des variables X et Y sur la photo ci-dessus), tandis que pour les données centrées est Pearson ; ainsi, un produit scalaire est la covariance. [Une note latérale. Si vous pensez en ce moment à la covariance / corrélation entre les variables , pas aux points de données, vous pourriez vous demander s'il est possible de dessiner des variables pour être des vecteurs comme sur l'image ci-dessus. Oui, c'est possible, ça s'appelle "l' espace du sujet "$h^2$$\cos\phi$$r$$\sigma_1\sigma_2r_{12}$"mode de représentation. Le théorème de cosinus reste vrai indépendamment de ce qui est considéré comme des" vecteurs "sur cette instance - des points de données ou des caractéristiques de données.]

Chaque fois que nous avons une matrice de similitude avec 1 sur la diagonale - c'est-à-dire, avec tous les mis à 1, et nous pensons / nous attendons à ce que la similitude soit un produit scalaire euclidien , nous pouvons le convertir en la distance euclidienne au carré si nous en ont besoin (par exemple, pour faire un tel clustering ou MDS qui nécessite des distances et de préférence euclidiennes). Car, par ce qui découle de la formule du théorème de cosinus ci-dessus, est au carré euclidien . Vous pouvez bien sûr supprimer le facteur si votre analyse n'en a pas besoin et convertir par la formule$h$$s$$d^2=2(1-s)$$d$$2$$d^2=1-s$. Comme exemple souvent rencontré, ces formules sont utilisées pour convertir Pearson en distance euclidienne. (Voir aussi ceci et tout le fil là-bas remettant en question certaines formules pour convertir en distance.)$r$$r$

Juste au-dessus, j'ai dit si "nous croyons / nous attendons à ce que ...". Vous pouvez vérifier et être sûr que la similitude la matrice - une particulière à portée de main - est géométriquement « OK » matrice de produit scalaire si la matrice n'a pas de valeurs propres négatives. Mais s'il en a, cela signifie que n'est pas de vrais produits scalaires car il y a un certain degré de non-convergence géométrique soit dans les soit dans les qui "se cachent" derrière la matrice. Il existe des moyens d'essayer de "guérir" une telle matrice avant de la transformer en distances euclidiennes.$s$$s$$h$$d$