¿Cuándo tiene sentido hoy el "vecino más próximo"?

Question

En 1999, Beyer et al. preguntaron, ¿Cuándo tiene sentido el "vecino más próximo"?

¿Existen mejores formas de analizar y visualizar el efecto de la planitud de la distancia en la búsqueda de NN desde 1999?

¿Proporciona [un determinado] conjunto de datos ¿El problema 10-NN? ¿El problema de 100 NN?

¿Cómo enfocarían hoy esta cuestión los expertos?

---

Editado lunes 24 ene:

¿Qué le parece "distancia blanca" como nombre abreviado de "distancia plana con dimensión creciente" ?

Una forma fácil de ver el "apagón de distancia" es ejecutar 2-NN y trazar las distancias al vecino más próximo y al segundo vecino más próximo. El gráfico siguiente muestra dist ₁ y dist ₂ para un rango de nclusters y dimensiones, mediante Monte Carlo. Este ejemplo muestra un contraste de distancias bastante bueno para la diferencia absoluta escalada |dist ₂ - dist ₁ |. (Las diferencias relativas |dist ₂ / dist ₁ | → 1 a medida que la dimensión → ∞, por lo que se vuelven inútiles).

Si deben utilizarse errores absolutos o relativos en un contexto determinado depende, por supuesto, del ruido "real" presente: difícil.

Sugerencia: siempre 2-NN; 2 vecinos son útiles cuando están cerca, y útiles cuando no.

Answer 1

No tengo una respuesta completa a esta pregunta, pero puedo dar una respuesta parcial sobre algunos aspectos analíticos. Advertencia: He estado trabajando en otros problemas desde que publiqué el primer artículo, así que es muy probable que haya otros buenos artículos de los que no soy consciente.

En primer lugar, creo que merece la pena señalar que, a pesar del título de su artículo "When is `nearest neighbor' meaningful", Beyer et al respondieron en realidad a una pregunta diferente, a saber, cuándo es NN no significativo. Demostramos la inversa de su teorema, bajo algunos supuestos suaves adicionales sobre el tamaño de la muestra, en ¿Cuándo tiene sentido el "vecino más próximo"? A Converse Theorem and Implications. Journal of Complexity, 25(4), agosto de 2009, pp 385-397. y demostró que hay situaciones en las que (en teoría) la concentración de distancias no surgirá (damos ejemplos, pero en esencia el número de características no ruidosas tiene que crecer con la dimensionalidad así que, por supuesto, rara vez surgen en la práctica). Las referencias 1 y 7 citadas en nuestro artículo dan algunos ejemplos de formas en que la concentración de distancias puede mitigarse en la práctica.

Un trabajo de mi supervisor, Ata Kaban, analiza si estos problemas de concentración de distancias persisten a pesar de aplicar técnicas de reducción de la dimensionalidad en Sobre la conciencia de concentración de distancia de ciertas técnicas de reducción de datos. Pattern Recognition. Vol. 44, Issue 2, Feb 2011, pp.265-277. . También hay buenas discusiones.

Un artículo reciente de Radovanovic et al. Hubs en el espacio: Vecinos más próximos populares en datos de alta dimensión. JMLR, 11(Sep), septiembre de 2010, pp:2487-2531. discute la cuestión del "hubness", es decir, cuando un pequeño subconjunto de puntos pertenecen al $k$ vecinos más próximos de muchas de las observaciones etiquetadas. Véase también la tesis doctoral del primer autor, que está en la web.

Answer 2

También podría interesarle análisis de componentes de vecindad por Goldberger et al.

En este caso, se aprende una transformación lineal para maximizar los puntos esperados clasificados correctamente mediante una selección estocástica de la vecindad más próxima.

Como efecto secundario, el número (esperado) de vecinos se determina a partir de los datos.