¿Maldición de la dimensionalidad explicó en máquina aprendizaje?

Question

Estoy teniendo problemas para entender la maldición de la dimensionalidad. Específicamente, me encontré con él mientras se hace la scikit-learn tutorial de python. Por favor alguien puede explicar lo de abajo en una manera más sencilla? Lo siento, he estado tratando de entender por el tiempo más largo y no puede entender cómo se les ocurrió el cálculo para el número de ejemplos de formación para lograr un eficiente KNN estimador?

Aquí está la explicación:

Para un estimador para ser eficaz, necesita la distancia entre vecinos de los puntos a ser menor que algún valor d, que depende del problema. En una dimensión, esto requiere, en promedio, n ~ 1/d puntos. En el contexto de la anterior KNN ejemplo, si los datos se describe por una función con valores que van de 0 a 1 y con el n de capacitación observaciones, a continuación, los nuevos datos serán no más lejos de 1/n. Por lo tanto, el vecino más cercano regla de decisión será eficaz tan pronto como 1/n es pequeña en comparación con la escala de entre-función de clase de variaciones.

Si el número de características es p, ahora requiere n ~ 1/d^p puntos. Supongamos que nos requieren de 10 puntos en una sola dimensión: Ahora 10^p puntos son necesarios en p dimensiones para allanar el [0, 1] el espacio. Como p se hace más grande, el número de puntos de entrenamiento necesarios para un buen estimador crece de manera exponencial.

enlace aquí

EDIT: también es la tilde (~) supone que representan de manera aproximada en que ejemplo? o el python tilde operador?

Answer 1

"La maldición de la dimensionalidad" básicamente significa que como los datos crecen más grandes, cómputo de la construcción de un modelo se vuelve más complicado, por lo tanto, toma mucho tiempo.

En segundo lugar, el número de características es mucho más importante que el número de casos (filas) sobre este problema.

Y "~" allí representa la aproximación

Answer 2

matty-d ya ha dado una muy buena respuesta, pero he encontrado otra respuesta que explique este problema igual de bien, de un usuario de Quora Kevin Lacker:

Digamos que usted tiene una línea recta de 100 metros de largo y se le cayó un penny en algún lugar en ella. No sería demasiado difícil de encontrar. Camine a lo largo de la línea y se tarda dos minutos.

Ahora digamos que usted tiene un cuadrado de 100 metros a cada lado y se le cayó un centavo en algún lugar en ella. Sería muy duro, como en la búsqueda a través de dos campos de fútbol pegadas. Podría tomar días.

Ahora un cubo de 100 metros de ancho. Eso es como la búsqueda de un edificio de 30 pisos el tamaño de un estadio de fútbol. Ugh.

La dificultad de la búsqueda a través del espacio consigue una mucho más difícil de lo tiene más dimensiones. Usted podría no darse cuenta de esto intuitivamente cuando es sólo declaró en fórmulas matemáticas, ya que todos ellos tienen el mismo "ancho". Esa es la maldición de la dimensionalidad. Se llega a tener un nombre debido a que es poco intuitivo, útil y simple.

Answer 3

Que ejemplo puede dar un poco de intuición del problema, pero no es en realidad una rigurosa prueba en todo: eso es sólo un ejemplo de que muchas de las muestras son necesarias para obtener una "buena" la cobertura de los espacios. Podría ser (y de hecho hay, por ejemplo, hexágonos en 2D ya) mucho más eficiente coberturas de una cuadrícula regular... (la sofisticada zona de baja discrepancia secuencias se dedica a esto) ...y demostrando que incluso con mejor cubiertas todavía hay algunos maldición de la dimensionalidad es otra cuestión. En realidad, en ciertos espacios de funciones incluso hay formas de evitar este problema aparente.