La idea principal de k-Nearest-Neighbor tiene en cuenta los puntos más cercanos y decide la clasificación de los datos por mayoría de votos. Si es así, entonces no debería tener problemas en los datos de dimensiones superiores porque los métodos como el hashing sensible a la localidad pueden encontrar vecinos más cercanos de manera eficiente.
Además, la selección de funciones con redes bayesianas puede reducir la dimensión de los datos y facilitar el aprendizaje.
Sin embargo, este artículo de revisión de John Lafferty en aprendizaje estadístico señala que el aprendizaje no paramétrico en espacios de características de alta dimensión sigue siendo un desafío y está sin resolver.
¿Qué va mal?
Respuestas:
Este problema se conoce como la maldición de la dimensionalidad . Básicamente, a medida que aumenta el número de dimensiones, , los puntos en el espacio generalmente tienden a alejarse de todos los demás puntos. Esto hace que la partición del espacio (como es necesario para la clasificación o agrupamiento) sea muy difícil.d
Puedes ver esto por ti mismo muy fácilmente. Generé puntos dimensionales aleatorios en el hipercubo de la unidad en 20 valores de seleccionados uniformemente entre . Para cada valor de calculé la distancia desde el primer punto a todos los demás y tomé el promedio de estas distancias. Al trazar esto, podemos ver que la distancia promedio aumenta con la dimensionalidad, aunque el espacio en el que estamos generando los puntos en cada dimensión sigue siendo el mismo.d d 1..1000 d50 d d 1..1000 d
Distancia promedio vs. dimensionalidad
fuente
No es una respuesta completa, pero la página de Wikipedia que citó dice:
La probabilidad de que esto ocurra aumenta en presencia de espacios de características de alta dimensión.
fuente