He visto en algún sitio que las clásicas de las distancias (como la distancia Euclídea) se convierten débilmente discriminante cuando tenemos multidimensional y de datos dispersos. Por qué? ¿Tiene usted un ejemplo de dos escasa vectores de datos donde la distancia Euclidiana no funciona bien? En este caso, que la similitud deberíamos utilizar?
Respuestas
¿Demasiados anuncios?
Amadiere
Puntos
5606
Creo que no es tanto la dispersión, pero la alta dimensionalidad asocia generalmente con escasos datos. Pero tal vez es aún peor cuando los datos están muy dispersos. Porque entonces la distancia de cualquiera de los dos objetos es probable que sea una media cuadrática de su longitud, o $$\lim_{dim\rightarrow\infty}d(x,y) = ||x-y|| \rightarrow_p \sqrt{||x||^2 + ||y||^2}$$
Esta ecuación tiene trivialmente si $\forall_i x_i=0 \vee y_i=0$. Si aumenta la dimensionalidad y la dispersión suficiente para que vale para casi todos los atributos, la diferencia será mínima.
Peor aún: si usted normalizado sus vectores que tienen la longitud $||x||=1$, entonces la distancia euclidiana de dos objetos será de $\sqrt{2}$ con una probabilidad alta.
Así que, como regla general, para la distancia Euclídea para ser utilizable (que no estoy diciendo útiles o significativos) los objetos deben ser distinto de cero en $3/4$ de atributos. Entonces debe haber un número razonable de atributos donde $|y_i| \neq |x_i-y_i| \neq |x_i|$ de modo que el vector diferencia llega a ser útil. Esto también se aplica a cualquier otra norma inducida por la diferencia. Debido a que en la situación anterior, $|x-y| \rightarrow_p |x + y|$
No creo que este es un comportamiento deseable para las funciones de la distancia a convertido en gran medida independiente de la diferencia, o la diferencia absoluta convergencia de la suma absoluta!
Una solución común es el uso de distancias como el Coseno de distancia. En algunos datos que funcionan muy bien. A grandes rasgos, sólo se centran en los atributos donde ambos vectores son no-cero. Un interesante enfoque se describe en la referencia abajo (que no inventó, pero me gusta su evaluación experimental de las propiedades) es para uso compartido de vecinos más cercanos. Así que incluso cuando los vectores x e y no tienen atributos en común, que podría tener algunas común de los vecinos. Contar el número de objetos que conecta dos objetos está estrechamente relacionada con la gráfica de las distancias.
Hay mucha discusión sobre las funciones de la distancia en:
- Puede Compartido Vecino Distancias Vencer la Maldición de la Dimensionalidad?
M. E. Houle, H.-P. Kriegel, P. Kröger, E. Schubert y A. Zimek
SSDBM 2010
y si usted no prefiere artículos científicos, también en la Wikipedia: Maldición de la Dimensionalidad
MattSayar
Puntos
723
Te sugiero comenzar con
Coseno de distancia,
no Euclidiana, en busca de datos con la mayoría de los vectores de casi ortogonales,
$x \cdot y \aprox$ 0.
Para ver por qué, mira en
$|x - y|^2 = |x|^2 + |y|^2 - 2\ x \cdot$y.
Si $x \cdot y \aprox$ 0, esto se reduce a
$|x|^2 + |y|^2$:
un decadente medida de distancia, como Anony-Mousse de puntos.
Coseno distancia asciende a $x / |x|$,
o proyectar los datos en la superficie de la unidad de la esfera, de manera que todos $|x|$ = 1.
Entonces
$|x - y|^2 = 2 - 2\ x \cdot$y
una muy diferente y generalmente métrica mejor que la llanura Euclidiana.
$ x \cdot$ y puede ser pequeña, pero no es enmascarado por el ruidoso $|x|^2 + |y|^2$.
$x \cdot$ y es sobre todo cerca de 0 para los datos dispersos. Por ejemplo, si $x$ y $y$ de cada 100 términos no-cero y 900 ceros, ellos dos van a ser distinto de cero en sólo 10 de los términos (si el cero términos de dispersión al azar).
La normalización de $x$ /= $|x|$ puede ser lento para los datos dispersos; es rápido en scikit-learn.
Resumen: comenzar con el coseno de distancia, pero no esperes maravillas en cualquier viejo de datos.
El éxito de las métricas requieren de una evaluación, optimización, el conocimiento del dominio.
Aquí es un simple juguete ejemplo que ilustra el efecto de la dimensión de un problema de la discriminación por ejemplo, el problema que se enfrenta cuando se quiere decir si algo es observado o si sólo efecto aleatorio que se observa (este problema es un clásico en la ciencia).
Heurística. La cuestión clave aquí es que la norma Euclidiana da la misma importancia a cualquier dirección. Esto constituye una falta de antes, y como ustedes saben en alta dimensión no hay almuerzo gratis (es decir, si usted no tiene ninguna idea previa de lo que usted está buscando, entonces no hay ninguna razón por la que algunos de ruido no se vería como lo que usted está buscando, esta es la tautología ...).
Yo diría que para cualquier problema que existe un límite de información que es necesario encontrar algo más que ruido. Este límite está relacionado de alguna manera con el "tamaño" de la zona que están tratando de explorar con respecto a la "ruido" (es decir, a nivel de contenido informativo).
En alta dimensión si usted tiene antes de que la señal es escasa, a continuación, puede quitar (es decir, penalizar a) no escasa vector con una métrica con la que se llena el espacio con escasa vector o mediante el uso de una técnica de umbralización.
Marco Suponga que $\xi$ es un vector gaussiano con media $\nu$ diagonal y la covarianza $\sigma Id$ ($\sigma$ es conocido) y que se desea probar la hipótesis simple
$$H_0: \;\nu=0,\; Vs \; H_{\theta}: \; \nu=\theta $$ (para un determinado $\theta\in \mathbb{R}^n$) $\theta$ no es necesariamente conocidos de antemano.
Estadístico de prueba con la energía. La intuición que sin duda tiene es que es una buena idea para evaluar la norma/energía de $\mathcal{E}_n=\frac{1}{n}\sum_{i=1}^n\xi_i^2$ de que la observación $\xi$ para construir un estadístico de prueba. En realidad, usted puede construir un sistema estandarizado de centrado (por debajo de los $H_0$) versión $T_n$ de la energía de $T_n=\frac{\sum_i\xi_i^2-\sigma^2}{\sqrt{2n\sigma^4}}$. Que hace que una región crítica en el nivel de $\alpha$ de la forma $\{T_n\geq v_{1-\alpha}\}$ para un bien escogido $v_{1-\alpha}$
Potencia de la prueba y de la dimensión. En este caso es fácil de probabilidad ejercicio para mostrar la siguiente fórmula para la potencia de la 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 )$$ con $Z$ la suma de $n$ iid variables aleatorias con $\mathbb{E}[Z]=0$ y $Var(Z)=1$.
Esto significa que la potencia de la prueba es el aumento de la energía de la señal de $\|\theta\|^2_2$ y la disminución de $n$. Hablando en términos prácticos esto significa que al aumentar el tamaño $$ n de su problema si no aumentar la fuerza de la señal, al mismo tiempo, entonces usted está agregando valor informativo de la información para su observación (o se están reduciendo la proporción de información útil en la información que usted ha): esto es como la adición de ruido y reduce la potencia de la prueba (es decir, es más probable que te va a decir nada de lo que se observa, mientras que, de hecho, hay algo).
Hacia una prueba con un umbral de estadística. Si no tienes mucha energía en su señal, pero si usted sabe de una transformación lineal que puede ayudar a que usted tiene esta energía concentrada en una pequeña parte de la señal, entonces usted puede construir un estadístico de prueba que evalúe únicamente la energía de la pequeña parte de su señal. Si usted sabe de antemano donde se concentra (por ejemplo, usted sabe que no puede ser altas frecuencias en la señal), entonces usted puede obtener un poder en la anterior prueba con $n$ sustituido por un pequeño número y $\|\theta\|^2_2$ casi el mismo... Si no lo sabes de antemano lo que tienen que estimar que esto conduce a la bien conocida umbral de pruebas.
Tenga en cuenta que este argumento es exactamente en la raíz de muchos artículos, tales como
- Una de Antoniadis, F Abramovich, T Sapatinas, y B Vidal. Wavelet métodos para las pruebas de en el análisis funcional de la varianza de los modelos. Revista internacional de Ondas y su aplicaciones, 93 :1007-1021, 2004.
- M. V. Burnashef y Begmatov. En un problema de detección de la señal que conduce a la distribución estable. Teoría de la probabilidad y sus aplicaciones, 35(3) :556-560, 1990.
- Y. Baraud. No asintótica minimax tasa de pruebas de detección de la señal. Bernoulli, 8 :577-606, 2002.
- J Ventilador. Prueba de significación basado en wavelets umbral y neymar del truncamiento. JASA, 91 :674-688, 1996.
- J. Ventilador y S-K Lin. Prueba de significación cuando los datos son curvas. JASA, 93 :1007-1021, 1998.
- V. Spokoiny. Adaptación de la prueba de hipótesis utilizando wavelets. Anales de Estadísticas, 24(6) :2477-2498, diciembre de 1996.
mat_geek
Puntos
1367
Parte de la maldición de la dimensionalidad es que los datos comienzan a extenderse hacia fuera y lejos del centro. Esto es cierto para multivariante normal, e incluso cuando los componentes son IID (esférica normal). Pero si quieres estrictamente hablar de la distancia Euclídea incluso en el espacio de pocas dimensiones si los datos tienen una correlación estructura de la distancia Euclidiana no es el de métricas adecuadas. Si suponemos que los datos son multivariante normal con algunos distinto de cero covarianzas y para el bien del argumento, supongamos que la matriz de covarianza es conocido. A continuación, la distancia de Mahalanobis es la adecuada medida de distancia y no es la misma que la distancia Euclídea, que lo único que haría sería reducir a si la matriz de covarianza es proporcional a la matriz de identidad.
On Freund
Puntos
3479
Creo que esto está relacionado con la maldición de la dimensionalidad / concentración de medir, pero no puedo encontrar la discusión que motiva este comentario. Creo que había un hilo en metaoptimize, pero no de Google...
Para los datos de texto, la normalización de los vectores utilizando TF-IDF y, a continuación, la aplicación de similitud del coseno probablemente va a obtener mejores resultados que la distancia euclídea como documentos largos (con muchas palabras) pueden compartir los mismos temas, por lo tanto, muy similar a la de corto documentos de compartir un gran número de palabras comunes. El descarte de la norma de los vectores de ayuda en ese caso en particular.
