Pourquoi la distance euclidienne n'est-elle pas une bonne métrique dans les grandes dimensions?

J'ai lu que "la distance euclidienne n'est pas une bonne distance dans les grandes dimensions". Je suppose que cette déclaration a quelque chose à voir avec la malédiction de la dimensionnalité, mais quoi au juste? En outre, qu'est-ce que les «grandes dimensions»? J'appliquais la classification hiérarchique en utilisant la distance euclidienne avec 100 caractéristiques. Jusqu'à combien de fonctionnalités est-il «sûr» d'utiliser cette métrique?

Un résumé succinct des résultats non intuitifs dans les dimensions supérieures provient de " Quelques informations utiles sur l'apprentissage machine " de Pedro Domingos à l'Université de Washington:

[N] ous intuitions, qui proviennent d'un monde en trois dimensions, ne s'appliquent souvent pas dans les hautes dimensions. Dans les grandes dimensions, la majeure partie de la distribution gaussienne multivariée n’est pas proche de la moyenne, mais dans une «coquille» de plus en plus éloignée qui l’entoure; et la majeure partie du volume d'une orange de haute dimension se trouve dans la peau, pas dans la pulpe. Si un nombre constant d'exemples est distribué uniformément dans un hypercube de grande dimension, au-delà d'une dimension, la plupart des exemples sont plus proches de la face de l'hypercube que de leur plus proche voisin. Et si nous approchons une hypersphère en l’inscrivant dans un hypercube, dans les grandes dimensions, presque tout le volume de l’hypercube est en dehors de l’hypersphère. C'est une mauvaise nouvelle pour l'apprentissage automatique, où les formes d'un type sont souvent approchées par des formes d'un autre.

L'article regorge également de nombreuses perles de sagesse supplémentaires pour l'apprentissage automatique.

Une autre application, au-delà de l’apprentissage automatique, est la recherche du voisin le plus proche: compte tenu d’une observation d’intérêt, trouvez ses voisins les plus proches (en ce sens que ce sont les points les plus éloignés du point de requête). Mais dans les grandes dimensions, un phénomène curieux se pose: le rapport entre les points les plus proches et les plus éloignés se rapproche de 1, c’est-à-dire que les points deviennent essentiellement uniformément distants les uns des autres. Ce phénomène peut être observé pour une grande variété de métriques de distance, mais il est plus prononcé pour la métrique euclidienne que, par exemple, la métrique de distance de Manhattan. Le principe de la recherche du plus proche voisin est que les points "plus proches" sont plus pertinents que les points "plus loin", mais si tous les points sont essentiellement uniformément distants les uns des autres, la distinction est dénuée de sens.

De Charu C. Aggarwal, Alexander Hinneburg, Daniel A. Keim, " Sur le comportement surprenant des métriques de distance dans un espace de grande dimension ":

Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft, " Quand le 'voisin le plus proche' a-t-il une signification? " Pour une cible donnée dans un espace de grande dimension, il est presque égal à 1 pour une grande variété de distributions de données et de fonctions de distance. Dans un tel cas, le problème du voisin le plus proche devient mal défini, car le contraste entre les distances aux différents points de données n'existe pas. Dans de tels cas, même le concept de proximité peut ne pas avoir de sens du point de vue qualitatif: un problème encore plus fondamental que la dégradation des performances des algorithmes de grande dimension.

... De nombreuses structures et algorithmes d'indexation de grande dimension utilisent la métrique de distance [E] uclidienne comme une extension naturelle de son utilisation traditionnelle dans des applications spatiales à deux ou trois dimensions. ... Dans cet article, nous fournissons des résultats théoriques et expérimentaux surprenants en analysant la dépendance de la norme à la valeur de . Plus spécifiquement, nous montrons que les contrastes relatifs des distances à un point de requête dépendent fortement de la métrique utilisée. Ceci fournit des preuves considérables que la signification de la norme détériore plus rapidement dimensionnalité augmente pour des valeurs plus élevées de . Ainsi, pour un problème donné avec une valeur fixe (élevée) pour la dimensionnalité k L k L k k d k L 1 L $L_k$$k$$L_k$$L_k$$k$$d$, il peut être préférable d’utiliser des valeurs inférieures de . Cela signifie que la métrique de distance (métrique de distance de Manhattan) est la plus préférable pour les applications de grandes dimensions, suivie de la métrique euclidienne ( ). ...$k$$L_1$$L_2$

Les auteurs de l'article "Surprising Behavior" proposent ensuite d'utiliser les normes avec . Ils produisent des résultats qui démontrent que ces "normes fractionnaires" présentent la propriété d’augmenter le contraste entre les points les plus éloignés et les plus proches. Cela peut être utile dans certains contextes, mais il y a une mise en garde: ces "normes fractionnaires" ne sont pas des métriques de distance appropriées, car elles violent l'inégalité du triangle. Si l'inégalité triangulaire est une qualité importante à avoir dans votre recherche, les métriques fractionnaires ne seront pas extrêmement utiles. k < $L_k$$k<1$

La notion de distance euclidienne, qui fonctionne bien dans les mondes bidimensionnels et tridimensionnels étudiés par Euclide, a des propriétés dans les dimensions supérieures qui sont contraires à notre (peut-être juste mon ) intuition géométrique qui est aussi une extrapolation de deux et trois dimensions.

Considérons un carré de avec des sommets à . Tracez quatre cercles d'unités de rayon centrés sur . Celles-ci "remplissent" le carré, chaque cercle touchant les côtés du carré en deux points et chaque cercle touchant ses deux voisins. Par exemple, le cercle centré en touche les côtés du carré en et , et les cercles voisins en et . Ensuite, dessinez un petit cercle centré à l'origine( ± 2 , ± 2 ) ( ± 1 , ± 1 ) ( 1 , 1 ) ( 2 , 1 ) ( 1 , 2 ) ( 1 , 0 ) ( 0 , 1 ) r 2 = $4\times 4$$(\pm 2, \pm 2)$$(\pm 1, \pm 1)$$(1,1)$$(2,1)$$(1,2)$$(1,0)$$(0,1)$cela touche les quatre cercles. Puisque le segment de droite dont les extrémités sont les centres de deux cercles osculants passe par le point d’oscillation, il est facile de vérifier que le petit cercle a un rayon et qu’il touche les quatre plus grands cercles . Notez que le petit cercle est "complètement entouré" par les quatre plus grands cercles et est donc complètement à l'intérieur du carré. Notez également que le point se trouve sur le petit cercle. Notez également que depuis l'origine, on ne peut pas "voir" le point sur le bord du carré car la ligne de mire passe par le point d'oscillation des deux cercles centrés à(±r2/$r_2 = \sqrt{2}-1$(r2,0)(2,0,0)(1,0,0)(1,1)(1,-1$(\pm r_2/\sqrt{2}, \pm r_2/\sqrt{2})$$(r_2,0)$$(2,0,0)$$(1,0,0)$$(1,1)$ et . Idem pour les lignes de mire aux autres points où les axes passent par les bords du carré.$(1,-1)$

Ensuite, considérons un cube avec des sommets à . Nous le remplissons avec sphères osculatrices de rayon unité centrées à , puis mettons une sphère osculante plus petite centrée à l'origine. Notez que la petite sphère a un rayon et que le point se trouve à la surface de la petite sphère. Mais remarquez aussi qu'en trois dimensions, on peut "voir" le point $4\times 4 \times 4$$(\pm 2, \pm 2, \pm 2)$$8$$(\pm 1, \pm 1, \pm 1)$$r_3 = \sqrt{3}-1 < 1$$(r_3,0,0)$$(2,0,0)$de l'origine; il n'y a pas de plus grandes sphères plus grandes bloquant la vue comme cela se produit dans deux dimensions. Ces lignes de vision dégagées depuis l'origine jusqu'aux points où les axes passent à travers la surface du cube se retrouvent également dans toutes les plus grandes dimensions.

En généralisant, on peut considérer un -dimensionnelle hypercube du côté et le remplir avec osculatrices hypersphères unité de rayon centré à , puis mettre un « petit » sphère de rayon à l’origine. Le point se situe sur cette sphère "plus petite". Mais notez de que lorsque , et que la "petite" sphère a un rayon unitaire et ne mérite donc pas vraiment le soubriquet de "plus petit" pour$n$$4$$2^n$$(\pm 1, \pm 1, \ldots, \pm 1)$

$$r_n = \sqrt{n}-1\tag{1}$$ ( 1 ) n = $(r_n,0,0, \ldots, 0)$$(1)$$n = 4$$r_n = 1$$n\geq 4$. En fait, il serait préférable que nous l'appelions la "plus grande sphère" ou simplement "la sphère centrale". Comme indiqué dans le dernier paragraphe, il existe un champ de vision dégagé entre l'origine et les points où les axes passent à travers la surface de l'hypercube. Pire encore, quand , on a que , et donc le point de la sphère centrale se situe en dehors de l'hypercube du côté alors qu'il est "complètement entouré" par les hypersphères unité-rayon qui "remplissent" l'hypercube (dans le sens de le tasser).$n > 9$$(1)$$r_n >2$$(r_n, 0, 0, \ldots, 0)$$4$ La sphère centrale "se gonfle" à l'extérieur de l'hypercube dans un espace de grande dimension. Je trouve cela très contre-intuitif car mes traductions mentales de la notion de distance euclidienne en dimensions supérieures, en utilisant l’intuition géométrique que j’ai développée à partir de l’espace 2 et de l’espace 3 que je connais bien, ne décrivent pas la réalité de la réalité. espace de grande dimension.

Ma réponse à la question du PO "D'ailleurs, qu'est-ce que les" grandes dimensions "?" est .$n \geq 9$

C'est une question de signal à bruit . La distance euclidienne, en raison des termes au carré, est particulièrement sensible au bruit; mais même la distance de Manhattan et les distances "fractionnelles" (non métriques) en souffrent.

J'ai trouvé les études dans cet article très éclairantes:

Zimek, A., Schubert, E. et Kriegel, H.-P. (2012),
Une enquête sur la détection de valeurs aberrantes non supervisées dans des données numériques de grande dimension.
Analyse statistique de données, 5: 363–387. doi: 10.1002 / sam.11161

Il revient sur les observations faites dans, par exemple, sur le comportement surprenant des métriques de distance dans les hautes dimensions par Aggarwal, Hinneburg et Keim, mentionnées par @Pat. Mais cela montre également à quel point les expériences de synthèse sont trompeuses et qu'en réalité, les données de grande dimension peuvent devenir plus faciles . Si vous avez beaucoup de signaux (redondants) et que les nouvelles dimensions ajoutent peu de bruit.

La dernière revendication est probablement la plus évidente lorsque l'on considère les dimensions en double. Mapper votre ensemble de données augmente la dimensionnalité représentative, mais ne fait pas du tout échouer la distance euclidienne. (Voir aussi: dimensionnalité intrinsèque )$x,y \rightarrow x,y,x,y,x,y,x,y,...,x,y$

Donc, au final, cela dépend toujours de vos données. Si vous avez beaucoup d'attributs inutiles, la distance euclidienne deviendra inutile. Si vous pouviez facilement intégrer vos données dans un espace de données de faible dimension, la distance euclidienne devrait également fonctionner dans tout l'espace de dimension. En particulier pour les données éparses , telles que les vecteurs TF du texte, il semble que les données présentent une dimensionnalité bien inférieure à celle suggérée par le modèle spatial vectoriel.

Certaines personnes pensent que la distance cosinus est meilleure que la distance euclidienne pour les données de grande dimension. Je ne le pense pas: la distance cosinus et la distance euclidienne sont étroitement liées; il faut donc s'attendre à ce qu'ils souffrent des mêmes problèmes. Toutefois, les données textuelles dans lesquelles le cosinus est populaire sont généralement rares et le cosinus est plus rapide lorsque les données sont rares - il existe donc de bonnes raisons d'utiliser le cosinus; et comme les données sont rares, la dimensionnalité intrinsèque est bien inférieure à la dimension d'espace vectoriel.

Voir également cette réponse que j'ai donnée à une question précédente: https://stats.stackexchange.com/a/29647/7828

Le meilleur endroit pour commencer est probablement de lire À propos du comportement surprenant des métriques de distance dans l'espace de grande dimension par Aggarwal, Hinneburg et Keim. Il existe actuellement un lien fonctionnel (pdf) , mais il devrait être très facile à utiliser si cela casse. En bref, à mesure que le nombre de dimensions augmente, la distance euclidienne relative entre un point d'un ensemble et son plus proche voisin, et entre ce point et son voisin le plus éloigné, change de manière non évidente. Que cela nuise ou non à vos résultats dépend en grande partie de ce que vous essayez d'atteindre et de ce que sont vos données.

La distance euclidienne est très rarement une bonne distance à choisir dans le Machine Learning et cela devient plus évident dans les dimensions supérieures. En effet, la plupart du temps dans Machine Learning, vous ne traitez pas avec un espace métrique euclidien, mais un espace métrique probabiliste et vous devez donc utiliser des fonctions de distance probabilistes et théoriques de l'information, par exemple à base d'entropie.

Les humains aiment l’espace euclidien, car il est facile à conceptualiser. De plus, c’est mathématiquement facile en raison des propriétés de linéarité qui permettent d’appliquer l’algèbre linéaire. Si nous définissons les distances en termes de, disons, la divergence de Kullback-Leibler, il est alors plus difficile de visualiser et de travailler mathématiquement.

Par analogie, imaginez un cercle centré à l'origine. Les points sont répartis uniformément. Supposons qu'un point sélectionné de manière aléatoire se situe à (x1, x2). La distance euclidienne de l'origine est ((x1) ^ 2 + (x2) ^ 2) ^ 0.5

Maintenant, imaginez des points également répartis sur une sphère. Ce même point (x1, x2) sera maintenant probablement (x1, x2, x3). Etant donné que, dans une distribution paire, seuls quelques points ont une des coordonnées zéro, nous supposerons que [x3! = 0] pour notre point également distribué de manière aléatoire. Ainsi, notre point aléatoire est le plus probable (x1, x2, x3) et non (x1, x2, 0).

L'effet de ceci est: tout point aléatoire est maintenant à une distance de ((x1) ^ 2 + (x2) ^ 2 + (x3) ^ 2) ^ 0,5 de l'origine de la sphère 3-D. Cette distance est supérieure à celle d'un point aléatoire proche de l'origine d'un cercle à deux dimensions. Ce problème s'aggrave dans les dimensions supérieures. C'est pourquoi nous avons choisi des métriques autres que les dimensions euclidiennes pour travailler avec des dimensions plus élevées.

EDIT: Il y a un dicton dont je me souviens maintenant: "La plus grande partie de la masse d'un orange de dimension supérieure se trouve dans la peau, pas dans la pulpe", ce qui signifie que dans les dimensions supérieures, les points uniformément répartis sont plus "proches" (distance euclidienne) de la limite que l'origine.

Note latérale: La distance euclidienne n'est pas TROP mauvaise pour les problèmes du monde réel en raison de la 'bénédiction de la non-uniformité', qui stipule fondamentalement que pour des données réelles, vos données ne vont probablement PAS être distribuées uniformément dans l'espace de dimension supérieure, mais occupera un petit sous-ensemble encombré de l’espace. Cela a un sens intuitif: si vous mesurez 100 valeurs concernant l’homme, telles que la taille, le poids, etc., une distribution uniforme sur l’espace dimensionnel n’a aucun sens, par exemple une personne avec (hauteur = 65 pouces, poids = 150 lb, avg_calorie_intake = 4000), ce qui n’est tout simplement pas possible dans le monde réel.

Une autre facette de cette question est la suivante:

Très souvent, les dimensions élevées des problèmes (apprentissage machine / statistiques) résultent de fonctionnalités sur-contraintes.

Cela signifie que les dimensions ne sont PAS indépendantes (ou non corrélées), mais les métriques euclidiennes supposent (au moins) une non-corrélation et risquent donc de ne pas produire les meilleurs résultats.

Donc, pour répondre à votre question, le nombre de "grandes dimensions" est lié au nombre de fonctionnalités interdépendantes, redondantes ou surchargées.

De plus: Csiszar (et al.) Admet que les métriques euclidiennes sont des candidats "naturels" à l'inférence lorsque les caractéristiques ont certaines formes.

Ce document peut également vous aider "Mesure de la similarité améliorée avec sqrt-cosinus", visitez la page https://journalofbigdata.springeropen.com/articles/10.1186/s40537-017-0083-6. Ce document explique pourquoi la distance euclidienne n'est pas une bonne mesure en hauteur données et quel est le meilleur remplacement pour la distance euclidienne dans les données de grandes dimensions. La distance euclidienne est la norme L2 et en diminuant la valeur de k dans la norme Lk, nous pouvons atténuer le problème de la distance dans les données de grande dimension. Vous pouvez également trouver les références dans cet article.