9 votos

Distancia métrica y de la maldición de las dimensiones

En algún lugar leí una nota que si tiene muchos parámetros de $(x_1, x_2, \ldots, x_n)$ y tratar de encontrar una "métrica de similitud" entre estos vectores, usted puede tener una "maldición de dimensioality". Creo que esto significaba que la mayoría de las puntuaciones de similitud será igual y no darle ningún tipo de información útil. En otras palabras, casi todos los socios a los vectores tienen algunas distancia media de puntuación que no es útil para la clasificación o agrupación etc.

¿Sabes dónde puedo aprender más en detalle acerca de eso?

Hay métricas que sufren menos de este efecto?

11voto

Amadiere Puntos 5606

Algunos clásicos de las observaciones de distancias en datos de alta dimensión:

  • K. Beyer, J. Goldstein, R. Ramakrishnan, y U. Eje, ICDT de 1999: "Cuando está más Cercano a los Vecinos Sentido?"
  • C. C. Aggarwal, A. Hinneburg, y D. A. Keim, ICDT de 2001: "En el Sorprendente Comportamiento de la Distancia, las Métricas de Alta el Espacio Tridimensional"

Un par de investigación más reciente sobre esto, lo que implica compartido-vecinos más cercanos y hubness:

  • M. E. Houle, H.-P. Kriegel, P. Kröger, E. Schubert y A. Zimek, SSDBM de 2010: "Puede Compartido Vecino Distancias Vencer la Maldición de la Dimensionalidad?"
  • T. Bernecker, M. E. Houle, H.-P. Kriegel, P. Kröger, M. Renz, E. Schubert y A. Zimek, SSTD de 2011: "la Calidad de la Similitud en el Ranking de Series de Tiempo"
  • N. Tomašev, M. Radovanović, D. Mladenić, y M. Ivanović. Adv. KDDM de 2011: "El papel de hubness en la agrupación de datos de alta dimensión"
  • No recuerdo los otros, la búsqueda para "Hubness", que fue su alta dimensión de la observación

Estos son interesantes, como señalan algunos populares de los malentendidos acerca de la maldición de la dimensionalidad. En esencia, son una muestra de que los resultados teóricos - que supone que los datos a ser yo.yo.d. - no puede ser cierto en general para los datos que tiene más de una distribución. La maldición conduce a problemas numéricos, y una pérdida de la discriminación dentro de una única distribución, mientras que puede hacer que sea aún más fácil diferenciar dos distribuciones que están bien separados.

Algo de esto debe ser bastante obvio. Dicen que usted tiene de los objetos que se $A_i\sim \mathcal{N}(0;1)$ i.yo.d. en cada dimensión y otro conjunto de objetos que se $B_i\sim \mathcal{N}(100;1)$ i.yo.d. en cada dimensión. La diferencia entre los objetos de dos conjuntos diferentes siempre será magnitudes más grande que la distancia dentro de un solo conjunto, y el problema va a conseguir incluso más fácil con el aumento de la dimensionalidad.

Recomiendo la lectura de este trabajo, por Houle et al., en gran parte porque demuestra que diciendo que "estos datos de alta dimensión, y a causa de la maldición de la dimensionalidad no puede ser analizado", se podría estar haciendo las cosas un poco demasiado fácil. Aún que es una línea que está siendo utilizado en todo el lugar. "Nuestro algoritmo solo funciona para los de baja dimensionalidad de los datos, debido a la maldición de la dimensionalidad." "Nuestro índice sólo funciona hasta 10 dimensiones, debido a la maldición de la dimensionalidad." Yadda yadda yadda. Muchas de estas declaraciones aparentemente acaba de mostrar que tales autores no han entendido lo que sucede en la alta dimensionalidad en sus datos y el algoritmo (o necesitaba una excusa). Houle et al. no completamente resolver el rompecabezas (¿todavía? esto es bastante reciente), pero al menos reconsiderar muchos de los populares declaraciones.

Después de todo, si la alta dimensionalidad fueron este gran problema, ¿cómo es que en el texto de la minería de personas utilizan dimensiones en el orden de 10000-100000, mientras que en otros dominios de la gente da para arriba en sólo 10 dimensiones?!?

En cuanto a la segunda parte de tu pregunta: similitud del coseno parece sufrir menos a partir de la dimensionalidad. Aparte de que, como el tiempo que quieras para diferenciar las distintas distribuciones, el control de la precisión numérica y no dependen de la mano elegido umbrales (como usted puede ser que necesite para darles con un montón de dígitos significativos), classic $L_p$-Normas todavía debe de estar bien.

Sin embargo, el Coseno es también afectado por la maldición de la dimensionalidad, como se explica en:

  • M. Radovanović, A. Nanopoulos, y M. Ivanović, SIGIR de 2010. "Sobre la existencia de obstinado resultados en el espacio vectorial de los modelos."

10voto

Patrick Puntos 183
  • Aggarwal C. C., Hinneburg A., Keim, D. A. (2001), "En el Sorprendente el Comportamiento de la Distancia, las Métricas de Alta El Espacio Tridimensional"
  • Beyer K., J. Goldstein, Ramakrishnan, R., Eje U. (1999), "Cuando está más Cercano a los Vecinos Significativo?", ICDE Conferencia El Procedimiento.

2voto

axk Puntos 136

También:

  • Robert J. Durrant, Ata Kabán: Cuando es "vecino más cercano' significativas: A conversar teorema y sus implicaciones. J. Complejidad De 25(4): 385-397 (2009)

  • Ata Kabán: la distancia A la concentración de la conciencia de ciertos datos de las técnicas de reducción. De Reconocimiento De Patrones, 44(2): 265-277 (2011)

  • Ata Kabán: No paramétrico de detección del sentido de las distancias en el alta de datos dimensional. Estadística e Informática 22(2): 375-385 (2012)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X