¿La distancia euclidiana generalmente no es buena para datos escasos?

He visto en alguna parte que las distancias clásicas (como la distancia euclidiana) se vuelven débilmente discriminantes cuando tenemos datos multidimensionales y escasos. ¿Por qué? ¿Tiene un ejemplo de dos vectores de datos dispersos donde la distancia euclidiana no funciona bien? En este caso, ¿qué similitud debemos usar?

Aquí hay un ejemplo simple de juguete que ilustra el efecto de la dimensión en un problema de discriminación, por ejemplo, el problema que enfrenta cuando quiere decir si se observa algo o si solo se observa un efecto aleatorio (este problema es un clásico en la ciencia).

Heurístico. La cuestión clave aquí es que la norma euclidiana da la misma importancia a cualquier dirección. Esto constituye una falta de previo, y como seguramente sabe en alta dimensión, no hay almuerzo gratis (es decir, si no tiene una idea previa de lo que está buscando, entonces no hay ninguna razón por la cual un poco de ruido no se parezca a lo que es buscando, esto es tautología ...).

Diría que para cualquier problema hay un límite de información que es necesario para encontrar algo más que ruido. Este límite está relacionado de alguna manera con el "tamaño" del área que está tratando de explorar con respecto al nivel de "ruido" (es decir, el nivel de contenido no informativo).

En una dimensión alta, si tiene el previo de que su señal es escasa, entonces puede eliminar (es decir, penalizar) un vector no disperso con una métrica que llena el espacio con un vector disperso o utilizando una técnica de umbral.

Marco Suponga que es un vector gaussiano con media ν y covarianza diagonal σ I d ( se conoce σ ) y que desea probar la hipótesis simple$\xi$$\nu$$\sigma Id$$\sigma$

(para un θ ∈ R n ) θ no necesariamente se conoce de antemano.

Prueba estadística con energía . La intuición que ciertamente tiene es que es una buena idea evaluar la norma / energía $\mathcal{E}_n=\frac{1}{n}\sum_{i=1}^n\xi_i^2$$\xi$$H_0$$T_n$$T_n=\frac{\sum_i\xi_i^2-\sigma^2}{\sqrt{2n\sigma^4}}$$\alpha$$\{T_n\geq v_{1-\alpha}\}$$v_{1-\alpha}$

Poder de la prueba y dimensión. En este caso, es un ejercicio de probabilidad fácil mostrar la siguiente fórmula para el poder de su prueba:

$$P_{\theta}(T\leq v_{1-\alpha})=P\left (Z\leq \frac{v_{1-\alpha}}{\sqrt{1+2\|\theta\|_2^2/(n\sigma^2)}}-\frac{\|\theta\|^2_2}{\sqrt{2n\sigma^4+2\sigma^2\|\theta\|_2^2/(n\sigma^2)}}\right )$$ $Z$$n$$\mathbb{E}[Z]=0$$Var(Z)=1$

Esto significa que la potencia de su prueba aumenta con la energía de su señal y disminuye en . En términos prácticos, esto significa que cuando aumenta el tamaño de su problema si no aumenta la intensidad de la señal al mismo tiempo, entonces está agregando información no informativa a su observación (o está reduciendo la proporción de información útil en la información tienes): esto es como agregar ruido y reduce la potencia de la prueba (es decir, es más probable que digas que no se observa nada mientras realmente hay algo).$\|\theta\|^2_2$$n$$n$

Hacia una prueba con una estadística umbral. Si no tiene mucha energía en su señal, pero si conoce una transformación lineal que puede ayudarlo a concentrar esta energía en una pequeña parte de su señal, entonces puede construir una estadística de prueba que solo evaluará la energía para el pequeño parte de tu señal. Si conoce de antemano donde se concentra (por ejemplo, se conoce que no puede haber altas frecuencias en la señal), entonces usted puede obtener una potencia en la prueba anterior con reemplazado por un número pequeño y casi lo mismo ... Si no lo sabe de antemano, debe estimarlo, esto lleva a pruebas de umbral bien conocidas.$n$$\|\theta\|^2_2$

Tenga en cuenta que este argumento está exactamente en la raíz de muchos documentos como

• A Antoniadis, F Abramovich, T Sapatinas y B Vidakovic. Métodos de wavelet para pruebas en análisis funcional de modelos de varianza. International Journal on Wavelets y sus aplicaciones, 93: 1007–1021, 2004.
• MV Burnashef y Begmatov. En un problema de detección de señal que conduce a una distribución estable. Teoría de la probabilidad y sus aplicaciones, 35 (3): 556–560, 1990.
• Y. Baraud. Tasa mínima no asintótica de prueba en detección de señales. Bernoulli, 8: 577–606, 2002.
• J Fan. Prueba de significación basada en el umbral de wavelet y el truncamiento de Neyman. JASA, 91: 674–688, 1996.
• J. Fan y SK Lin. Prueba de significación cuando los datos son curvas. JASA, 93: 1007-1021, 1998.
• V. Spokoiny. Prueba de hipótesis adaptativa utilizando wavelets. Annals of Statistics, 24 (6): 2477–2498, diciembre de 1996.

Creo que no es tanto la escasez, sino la alta dimensionalidad generalmente asociada con datos escasos. Pero tal vez sea aún peor cuando los datos son muy escasos. Porque entonces la distancia de cualquiera de los dos objetos probablemente será una media cuadrática de sus longitudes, o

Esta ecuación es trivial si . Si aumenta la dimensionalidad y la dispersión lo suficiente como para que se aplique a casi todos los atributos, la diferencia será mínima.$\forall_i x_i=0 \vee y_i=0$

Peor aún: si normalizó sus vectores para que tengan una longitud , entonces la distancia euclidiana de cualquiera de los dos objetos será con alta probabilidad.$||x||=1$$\sqrt{2}$

Entonces, como regla general, para que la distancia euclidiana sea utilizable (no estoy afirmando que sea útil o significativa), los objetos deben ser distintos de cero en de los atributos. Entonces debería haber un número razonable de atributos dondeentonces la diferencia vectorial se vuelve útil. Esto también se aplica a cualquier otra diferencia inducida por la norma. Porque en la situación anterior$3/4$$|y_i| \neq |x_i-y_i| \neq |x_i|$$|x-y| \rightarrow_p |x + y|$

¡No creo que este sea un comportamiento deseable para que las funciones de distancia sean en gran medida independientes de la diferencia real, o de que la diferencia absoluta converja a la suma absoluta!

Una solución común es usar distancias como la distancia cosenoidal. En algunos datos funcionan muy bien. En términos generales, solo miran los atributos donde ambos vectores no son cero. Un enfoque interesante se discute en la referencia a continuación (no lo inventaron, pero me gusta su evaluación experimental de las propiedades) es usar vecinos más cercanos compartidos. Entonces, incluso cuando los vectores x e y no tienen atributos en común, pueden tener algunos vecinos comunes. Contar el número de objetos que conectan dos objetos está estrechamente relacionado con las distancias del gráfico.

Se discute mucho sobre las funciones de distancia en:

• ¿Pueden las distancias vecinas compartidas derrotar la maldición de la dimensionalidad?
  ME Houle, H.-P. Kriegel, P. Kröger, E. Schubert y A. Zimek
  SSDBM 2010

y si no prefieres artículos científicos, también en Wikipedia: Maldición de la dimensionalidad

Sugeriría comenzar con la distancia Coseno , no Euclidiana, para cualquier dato con la mayoría de los vectores casi ortogonales, 0. Para ver por qué, mire . Si 0, esto se reduce a : una mala medida de distancia, como señala Anony-Mousse.$x \cdot y \approx$
$|x - y|^2 = |x|^2 + |y|^2 - 2\ x \cdot y$
$x \cdot y \approx$$|x|^2 + |y|^2$

La distancia coseno equivale a usar, o proyectando los datos en la superficie de la esfera de la unidad, de modo que todos= 1. Entonces una métrica bastante diferente y generalmente mejor que la simple Euclidiana. puede ser pequeño, pero no está enmascarado por ruidoso .$x / |x|$$|x|$$|x - y|^2 = 2 - 2\ x \cdot y$
$x \cdot y$$|x|^2 + |y|^2$

$x \cdot y$ está mayormente cerca de 0 para datos dispersos. Por ejemplo, si e cada uno tiene 100 términos distintos de cero y 900 ceros, ambos serán distintos de cero en solo unos 10 términos (si los términos distintos de cero se dispersan al azar).$x$$y$

Normalizando / =puede ser lento para datos escasos; es rápido en scikit-learn .$x$$|x|$

Resumen: comience con la distancia cosenoidal, pero no espere maravillas con ningún dato antiguo.
Las métricas exitosas requieren evaluación, ajuste, conocimiento del dominio.

Parte de la maldición de la dimensionalidad es que los datos comienzan a extenderse fuera del centro. Esto es cierto para multivariante normal e incluso cuando los componentes son IID (esférico normal). Pero si desea hablar estrictamente sobre la distancia euclidiana, incluso en un espacio dimensional bajo, si los datos tienen una estructura de correlación, la distancia euclidiana no es la métrica adecuada. Si suponemos que los datos son multivariados normales con algunas covarianzas distintas de cero y, en aras del argumento, supongamos que se conoce la matriz de covarianza. Entonces la distancia de Mahalanobis es la medida de distancia apropiada y no es lo mismo que la distancia euclidiana a la que solo se reduciría si la matriz de covarianza es proporcional a la matriz de identidad.

Creo que esto está relacionado con la maldición de la dimensionalidad / concentración de la medida, pero ya no puedo encontrar la discusión que motiva esta observación. Creo que hubo un hilo en la metaoptimización, pero no pude buscarlo en Google ...

Para los datos de texto, la normalización de los vectores usando TF-IDF y luego aplicar la similitud del coseno probablemente arrojará mejores resultados que la distancia euclidiana, ya que los documentos largos (con muchas palabras) pueden compartir los mismos temas, por lo tanto, son muy similares a los documentos cortos que comparten una gran cantidad de datos comunes. palabras. Descartar la norma de los vectores ayuda en ese caso particular.

Una medida axiomática de la dispersión es el llamado conteo , que cuenta el número (finito) de entradas distintas de cero en un vector. Con esta medida, los vectores y poseen la misma escasez. Y absolutamente no es la misma norma . Y (muy escaso) tiene la misma norma que , un vector muy plano y no disperso. Y absolutamente no es el mismo recuento.$\ell_0$$(1,0,0,0)$$(0,21,0,0)$$\ell_2$$(1,0,0,0)$$\ell_2$$\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)$$\ell_0$

Esta función, ni una norma ni una cuasinorma, no es suave ni convexa. Dependiendo del dominio, sus nombres son legión, por ejemplo: función de cardinalidad, medida de numerosidad, o simplemente parsimonia o escasez. A menudo se considera poco práctico para fines prácticos, ya que su uso conduce a problemas NP difíciles .

Si bien las distancias o normas estándar (como la distancia euclidiana ) son más manejables, uno de sus problemas es su homogeneidad:para . Esto podría verse como no intuitivo, ya que el producto escalar no cambia la proporción de entradas nulas en los datos ( es -homogéneo).$\ell_2$$1$

Entonces, en la práctica, algunos combinaciones de ( ), como las regularizaciones de lazo, cresta o red elástica. La norma (distancia de Manhattan o taxi), o sus avatares suavizados, es especialmente útil. Como los trabajos de E. Candès y otros, uno puede explicar por qué es una buena aproximación a : una explicación geométrica . Otros han hecho en , al precio de los problemas de no convexidad.$\ell_p(x)$$p \ge1$$\ell_1$$\ell_1$$\ell_0$$p < 1$$\ell_p(x)$

Otro camino interesante es volver a axiomizar la noción de escasez. Uno de los trabajos notables recientes es Comparing Measures of Sparsity , de N. Hurley et al., Que trata sobre la escasez de distribuciones. A partir de seis axiomas (con nombres divertidos como Robin Hood, Scaling, Rising Tide, Cloning, Bill Gates y Babies), surgieron un par de índices de dispersión: uno basado en el índice de Gini, otro en proporciones de normas, especialmente el uno sobre dos relación norma, que se muestra a continuación:$\frac{\ell_1}{\ell_2}$

Aunque no es convexa, algunas pruebas de convergencia y algunas referencias históricas se detallan en Euclides en un Taxi: Escaso deconvolución ciega con suavizado Regularización$\frac{\ell _1}{\ell_2}$ .

El documento sobre el comportamiento sorprendente de las métricas de distancia en espacios de alta dimensión discute el comportamiento de las métricas de distancia en espacios de altas dimensiones.

Toman en la norma y proponen la manhattan norma como el más eficaz en espacios de alta dimensión para fines de agrupamiento. También introducen una norma fraccional similar a la norma pero con .$L_k$$L_1$ $L_f$$L_k$$f \in (0..1)$

En resumen, muestran que para espacios de altas dimensiones el uso de la norma euclidiana por defecto probablemente no sea una buena idea; Por lo general, tenemos poca intuición en tales espacios, y la explosión exponencial debido al número de dimensiones es difícil de tener en cuenta con la distancia euclidiana.