¿Cuándo es significativo el "vecino más cercano" hoy?

En 1999, Beyer et al. preguntó: ¿ Cuándo es significativo el "vecino más cercano"?

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

¿El conjunto de datos [un determinado] proporciona respuestas significativas al problema 1-NN? El problema de 10 NN? El problema de 100 NN?

¿Cómo abordarían ustedes hoy esta pregunta?

Ediciones lunes 24 de enero:

¿Qué tal "distancia blanca" como un nombre más corto para "distancia plana con dimensión creciente"?

Una manera fácil de ver el "distanciamiento de distancia" es correr 2-NN y trazar distancias al vecino más cercano y al segundo vecino más cercano. La siguiente gráfica muestra dist ₁ y dist ₂ para un rango de nclusters y dimensiones, de Monte Carlo. Este ejemplo muestra un contraste de distancia bastante bueno para la diferencia absoluta escalada | dist ₂ - dist ₁ |. (Las diferencias relativas | dist ₂ / dist ₁ | → 1 como dimensión → ∞, se vuelven inútiles.)

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

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

ingrese la descripción de la imagen aquí

machine-learning k-nearest-neighbour denis
fuente

Beyer y col. parece estar abordando un aspecto un poco diferente del problema NN. Pero, para fines de clasificación (binaria), en condiciones moderadas, es un resultado clásico que la clasificación 1-NN tiene, en el peor de los casos , el doble de probabilidad de error del clasificador Bayes (es decir, óptimo) asintóticamente. En otras palabras, el primer vecino más cercano contiene "al menos la mitad de la información" sobre la etiqueta del objetivo como lo hace el mejor clasificador. En este sentido, el 1-NN parece bastante relevante. (Ver Cover & Hart (1967) para más información. Me sorprende que Beyer et al. No lo cite).

Cardenal

@cardinal, el límite de Cover-Hart parece no depender en absoluto de la dimensión, como usted dice un aspecto diferente?

denis

sí, creo que esto es cierto y este fue, en gran parte, mi punto de plantearlo. 1-NN parece bastante relevante en ese sentido, es decir, el hecho de que funciona (tan) bien (teóricamente) uniformemente en la dimensión del espacio de características parece ayudarlo a mantenerse por sí mismo, independientemente del comportamiento del más cercano y los vecinos más lejanos se encuentran en un gran espacio dimensional. Me hace preguntarme si Beyer fue consciente de todo este resultado (clásico).

Cardenal

@cardinal La parte superior de la página 24 en Cover and Hart parece un lugar donde podría surgir un problema en su prueba, en el paso donde Cover y Hart argumentan que cada RV x \ in X tiene la propiedad de que cada esfera abierta sobre x tiene medida distinta de cero Si consideramos la geometría de la hiperesfera, vemos que el volumen del interior de la hiperesfera se reduce con el aumento de la dimensión, por lo que, en el límite, la bola abierta sobre x contiene solo x en su interior. Alternativamente, a través del SLLN, los iid RVs x en el espacio métrico X yacen en la superficie de la hiperesfera con probabilidad uno.

Bob Durrant

Consulte también las métricas L1 o L.5 para la agrupación .

denis

Respuestas:

No tengo una respuesta completa a esta pregunta, pero puedo dar una respuesta parcial sobre algunos de los aspectos analíticos. Advertencia: He estado trabajando en otros problemas desde el primer artículo a continuación, por lo que es muy probable que haya otras cosas buenas que no conozco.

Primero, creo que vale la pena señalar que, a pesar del título de su artículo "Cuando el 'vecino más cercano' es significativo", Beyer et al respondieron una pregunta diferente, es decir, cuándo NN no es significativo. Probamos lo contrario a su teorema, bajo algunos supuestos leves adicionales sobre el tamaño de la muestra, en When Is 'Nearest Neighbour' Significativo: un teorema inverso y sus implicaciones. Journal of Complexity, 25 (4), agosto de 2009, págs. 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 sin ruido debe crecer con la dimensionalidad, por lo 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 distancia puede mitigarse en la práctica.

Un artículo de mi supervisor, Ata Kaban, analiza si estos problemas de concentración a distancia persisten a pesar de aplicar técnicas de reducción de dimensionalidad en Conocimiento de concentración a distancia de ciertas técnicas de reducción de datos. Reconocimiento de patrones. Vol. 44, número 2, febrero de 2011, págs. 265-277. . Hay una buena discusión allí también.

$k$

Bob Durrant
fuente

Gracias Bob, +1. Una pregunta relacionada, ¿tendrías una regla general para elegir un valor de q fraccional-métrico (o debería hacer eso como una pregunta separada)?

denis

q = 1 / p

$q=1/p$

p > 1

$p>1$

p

$p$

l_{0}

$l_0$

p = 1

$p=1$

l_{1}

$l_{1}$

l_{q = 1 / p}

$l_{q=1/p}$

p > 1

$p>1$

p

$p$

\sum | a_{j} - b_{j} |^{q}

$\sum |a_j - b_j|^q$

1 / q

$1/q$

< q <

$< q <$

ℓ_{p}

$\ell_{p}$

También podría estar interesado en el análisis de componentes de vecindario por Goldberger et al.

Aquí, se aprende una transformación lineal para maximizar los puntos clasificados correctamente esperados a través de una selección estocástica del vecindario más cercano.

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

bayerj
fuente

Gracias bayer. Parece que el "aprendizaje métrico a distancia" está en auge: scholar.goo tiene 50 títulos desde 2008. ¿Pero el papel de auge o el uso real? Nota al pie, el código para nca dice "iteraciones ... al menos 100000 para obtener buenos resultados". Nota 2, la mayor parte del trabajo sobre el aprendizaje métrico a distancia parece modelar una distancia de Mahalanobis; ¿Conoces otros modelos de distancia?

denis

Tengo diferentes experiencias con NCA, por lo general, converge bastante rápido para mí. Verifique "reducción de dimensionalidad mediante el aprendizaje de un mapeo invariante" de LeCun y "Hashing de pérdida mínima para códigos binarios compactos" de Norouzi.

bayerj