¿Por qué la distancia euclidiana no es una buena métrica en dimensiones altas?

Question

He leído que "la distancia euclidiana no es una buena distancia en dimensiones altas". Supongo que esta afirmación tiene algo que ver con la maldición de la dimensionalidad, pero ¿qué es exactamente? Además, ¿qué son las "altas dimensiones"? He estado aplicando la agrupación jerárquica utilizando la distancia euclidiana con 100 características. ¿Hasta cuántas características es "seguro" utilizar esta métrica?

Answer 1

La noción de distancia euclidiana, que funciona bien en los mundos bidimensional y tridimensional estudiados por Euclides, tiene algunas propiedades en dimensiones superiores que son contrarias a nuestro (quizá sólo mi ) intuición geométrica que también es una extrapolación de las dos y tres dimensiones.

Considere una $4\times 4$ cuadrado con vértices en $(\pm 2, \pm 2)$ . Dibuja cuatro círculos de radio unitario centrados en $(\pm 1, \pm 1)$ . Estos "llenan" el cuadrado con cada círculo tocando los lados del cuadrado en dos puntos, y cada círculo toca a sus dos vecinos. Por ejemplo, el círculo centrado en $(1,1)$ toca los lados del cuadrado en $(2,1)$ y $(1,2)$ y sus círculos vecinos en $(1,0)$ y $(0,1)$ . A continuación, dibuje un pequeño círculo centrado en el origen que toca los cuatro círculos. Como el segmento de línea cuyos puntos extremos son los centros de dos círculos osculantes pasa por el punto de osculación, es fácilmente que el círculo pequeño tiene radio $r_{2} = \sqrt{2}-1$ y que toca toca los cuatro círculos mayores en $(\pm r_2/\sqrt{2}, \pm r_2/\sqrt{2})$ . Observe que el círculo pequeño está "completamente rodeado" por los cuatro círculos más grandes y, por tanto, también está completamente dentro del cuadrado. Obsérvese también que el punto $(r_2,0)$ se encuentra en el círculo pequeño. Observa también que desde el origen no se puede "ver" el punto $(2,0)$ en el borde del cuadrado porque la línea de visión pasa por el punto de osculación $(1,0)$ de los dos círculos centrados en $(1,1)$ y $(1,-1)$ . Lo mismo ocurre con las líneas de visión hacia los otros puntos por los que pasan los ejes los bordes del cuadrado.

A continuación, considere un $4\times 4 \times 4$ cubo con vértices en $(\pm 2, \pm 2, \pm 2)$ . Lo llenamos con $8$ osculando esferas de radio unitario centradas en $(\pm 1, \pm 1, \pm 1)$ y a continuación, poner una esfera oscilante más pequeña centrada en el origen. Obsérvese que la esfera pequeña tiene radio $r_3 = \sqrt{3}-1 < 1$ y el punto $(r_3,0,0)$ se encuentra en la superficie de la pequeña esfera. Pero fíjate también en que en tres dimensiones, uno puede "ver" el punto $(2,0,0)$ desde el origen; no hay esferas más grandes bloqueando la vista como ocurre en dos dimensiones. Estas líneas de visión claras desde el origen hasta los puntos donde los ejes pasan por la superficie del cubo se dan también en todas las dimensiones mayores.

Generalizando, podemos considerar un $n$ -hipercubo de lado $4$ y llenarlo con $2^n$ hiperesferas de radio unitario osculantes centradas en $(\pm 1, \pm 1, \ldots, \pm 1)$ y luego poner una esfera oscilante "más pequeña" de radio $$r_n = \sqrt{n}-1\tag{1}$$ en el origen. El punto $(r_n,0,0, \ldots, 0)$ se encuentra en esta esfera "más pequeña". Pero, fíjate en $(1)$ que cuando $n = 4$ , $r_n = 1$ y por tanto la esfera "más pequeña" tiene un radio unitario y, por tanto, no merece realmente el sobrenombre de "más pequeña" para $n\geq 4$ . De hecho, sería mejor si la llamáramos "esfera mayor" o simplemente "esfera central". Como se ha señalado en el último párrafo, existe una línea de visión clara desde el origen hasta los puntos donde los ejes pasan por la superficie del hipercubo. Peor aún, cuando $n > 9$ tenemos de $(1)$ que $r_n >2$ y, por tanto, el punto $(r_n, 0, 0, \ldots, 0)$ en la esfera central se encuentra fuera del hipercubo de lado $4$ aunque esté "completamente rodeado" por las hiperesferas de radio unitario que "llenan" el hipercubo (en el sentido de empaquetarlo). La esfera central esfera se "abulta" fuera del hipercubo en el espacio de alta dimensión. Encuentro esto muy contraintuitivo porque mis traducciones mentales de la noción de distancia euclidiana a dimensiones superiores, utilizando la intuición geométrica que he desarrollado de los espacios 2 y 3 con los que estoy familiarizado, no describen describen la realidad del espacio de alta dimensión.

Mi respuesta a la pregunta del OP "Además, ¿qué son las 'altas dimensiones'?" es $n \geq 9$ .

Answer 2

Se trata de relación señal/ruido . La distancia euclidiana, debido a los términos al cuadrado, es especialmente sensible al ruido; pero incluso la distancia Manhattan y las distancias "fraccionales" (no métricas) sufren.

Los estudios de este artículo me han parecido muy esclarecedores:

Zimek, A., Schubert, E. y Kriegel, H.-P. (2012),
Un estudio sobre la detección no supervisada de valores atípicos en datos numéricos de alta dimensión.
Análisis estadístico de la minería de datos, 5: 363-387. doi: 10.1002/sam.11161

Vuelve a las observaciones realizadas, por ejemplo, en On the Surprising Behavior of Distance Metrics in High Dimensional Space, de Aggarwal, Hinneburg y Keim, mencionado por @Pat. Pero también muestra cómo nuestros experimentos sintéticos son engañosos y que de hecho datos de alta dimensión puede se vuelven más fáciles . Si tienes mucha señal (redundante), y las nuevas dimensiones añaden poco ruido.

La última afirmación es probablemente la más obvia cuando se consideran las dimensiones duplicadas. Trazado de su conjunto de datos $x,y \rightarrow x,y,x,y,x,y,x,y,...,x,y$ aumenta la dimensionalidad representativa, pero no hace fallar en absoluto la distancia euclidiana. (Véase también: dimensionalidad intrínseca )

Así que, al final, sigue dependiendo de sus datos. Si tiene muchos atributos inútiles, la distancia euclidiana será inútil. Si puede incluir fácilmente sus datos en un espacio de datos de baja dimensión, entonces la distancia euclidiana también debería funcionar en el espacio de dimensión completa. En particular, para escaso datos, como los vectores TF de un texto, parece ser que los datos tienen una dimensionalidad mucho menor de lo que sugiere el modelo de espacio vectorial.

Algunos creen que la distancia coseno es mejor que la euclidiana en datos de alta dimensión. Yo no lo creo: la distancia coseno y la distancia euclidiana son estrechamente relacionados, por lo que es de esperar que sufran los mismos problemas. Sin embargo, los datos textuales en los que el coseno es popular suelen ser escaso y el coseno es más rápido en los datos dispersos, así que para los datos dispersos hay buenas razones para utilizar el coseno; y como los datos son dispersos, la dimensionalidad intrínseca es mucho menor que la dimensión del espacio vectorial.

Véase también esta respuesta que di a una pregunta anterior: https://stats.stackexchange.com/a/29647/7828

Answer 3

El mejor lugar para empezar es probablemente leer Sobre el sorprendente comportamiento de las métricas de distancia en espacios de alta dimensión por Aggarwal, Hinneburg y Keim . Hay un enlace que funciona actualmente aquí (pdf) pero debería ser muy fácil de buscar en Google si se rompe. En resumen, a medida que aumenta el número de dimensiones, la distancia euclidiana relativa entre un punto de un conjunto y su vecino más cercano, y entre ese punto y su vecino más lejano, cambia de algunas formas no obvias. Que esto afecte o no a tus resultados depende en gran medida de lo que intentes conseguir y de cómo sean tus datos.

Answer 4

La distancia euclidiana rara vez es una buena distancia para elegir en el aprendizaje automático y esto se hace más evidente en dimensiones más altas. Esto se debe a que la mayoría de las veces en el aprendizaje automático no se trata de un espacio métrico euclidiano, sino de un espacio métrico probabilístico y, por tanto, se deberían utilizar funciones de distancia probabilísticas y teóricas de la información, por ejemplo, las basadas en la entropía.

A los humanos les gusta el espacio euclidiano porque es fácil de conceptualizar, y además es matemáticamente fácil debido a las propiedades de linealidad que significan que podemos aplicar el álgebra lineal. Si definimos las distancias en términos de, por ejemplo, la divergencia de Kullback-Leibler, es más difícil de visualizar y de trabajar matemáticamente.

Answer 5

Como analogía, imagine un círculo centrado en el origen. Los puntos se distribuyen uniformemente. Supongamos que un punto elegido al azar está en (x1, x2). La distancia euclidiana al origen es ((x1)^2 + (x2)^2)^0,5

Ahora, imagina puntos distribuidos uniformemente en una esfera. Ese mismo punto (x1, x2) será ahora probablemente (x1, x2, x3). Como, en una distribución uniforme, sólo unos pocos puntos tienen una de las coordenadas como cero, supondremos que [x3 != 0] para nuestro punto distribuido uniformemente al azar. Así, nuestro punto aleatorio es muy probablemente (x1, x2, x3) y no (x1, x2, 0).

El efecto de esto es: cualquier punto aleatorio está ahora a una distancia de ((x1)^2 + (x2)^2 + (x3)^2)^0,5 del origen de la esfera tridimensional. Esta distancia es mayor que la de un punto aleatorio cerca del origen de un círculo bidimensional. Este problema empeora en dimensiones más altas, por lo que elegimos métricas distintas a la euclidiana para trabajar con dimensiones más altas.

EDIT: Hay un dicho que ahora recuerdo: "La mayor parte de la masa de una naranja de dimensiones superiores está en la piel, no en la pulpa", lo que significa que en dimensiones superiores uniformemente Los puntos distribuidos están más "cerca" (distancia euclidiana) de la frontera que del origen.

Nota al margen: la distancia euclidiana no es DEMASIADO mala para los problemas del mundo real debido a la "bendición de la no uniformidad", que básicamente afirma que para los datos reales, tus datos probablemente NO van a estar distribuidos uniformemente en el espacio de mayor dimensión, sino que ocuparán un pequeño subconjunto agrupado del espacio. Esto tiene sentido de forma intuitiva: si se miden 100 magnitudes sobre los seres humanos, como la altura, el peso, etc., una distribución uniforme en el espacio dimensional no tiene sentido, por ejemplo, una persona con (height=65 pulgadas, peso=150 libras, avg_calorie_intake=4000), lo cual no es posible en el mundo real.