Maldición de la dimensionalidad: clasificador kNN

Question

Estoy leyendo Kevin Murphy del libro: Aprendizaje de Máquina-Una Perspectiva probabilística. En el primer capítulo, el autor explica la maldición de la dimensionalidad y hay una parte que no entiendo. Como ejemplo, el autor afirma:

Considere la posibilidad de que las entradas están distribuidos de manera uniforme a lo largo de un D-dimensional de la unidad de cubo. Supongamos que tenemos una estimación de la densidad de las etiquetas de clase por el crecimiento de un hyper cubo alrededor de x hasta que contiene la fracción deseada $f$ de los puntos de datos. La espera longitud de la arista de este cubo es $e_D(f) = f^{\frac{1}{D}}$.

Es la última fórmula que no puedo conseguir mi cabeza alrededor. parece que si usted desea cubrir indican que el 10% de los puntos de la longitud de la arista debe ser de 0,1 a lo largo de cada dimensión? Sé que mi razonamiento es equivocado, pero no puedo entender por qué.

Answer 1

Ese es precisamente el comportamiento inesperado de distancias en altas dimensiones. De 1 dimensión, usted tiene el intervalo [0, 1]. El 10% de los puntos están en un segmento de longitud 0.1. Pero ¿qué pasa cuando la dimensionalidad del espacio de características aumenta?

Que la expresión está diciendo que si usted desea que tenga el 10% de los puntos de 5 dimensiones, usted necesita tener una longitud para el cubo de 0,63, en 10 dimensiones de la 0.79 0.98 por 100 dimensiones.

Como se puede ver, para el aumento de las dimensiones que usted necesita mirar más lejos para obtener la misma cantidad de puntos. Aún más, está diciendo que la mayoría de los puntos están en el límite de el cubo como el número de dimensiones en aumento. Que es inesperado.

Answer 2

Creo que la principal cosa a notar es que la expresión

$$e_D(f) = f^{\frac{1}{D}}$$

es realmente muy empinada al principio. Esto significa que el tamaño del borde que usted tendrá que abarcar una cierta fracción del volumen aumentará drásticamente, especialmente al principio. es decir, el ángulo que usted necesita será ridículamente grande como $D$ aumenta.

Para hacer esto aún más claro, el recuerdo de la parcela, que Murphy muestra:

si se observa, para los valores de $D > 1$, la pendiente es muy grande y, por lo tanto, la función crece muy empinada al principio. Esto se puede apreciar mejor si se toma la derivada de $e_D(f)$:

$$e'_D(f) = \frac{1}{D} f^{\frac{1}{D} - 1} = \frac{1}{D} f^{\frac{1 - D}{D}}$$

Dado que sólo estamos considerando el aumento de dimensión (que son valores enteros), sólo nos preocupa para valores enteros de a $D > 1$. Esto significa que $1-D < 0$. Considere la posibilidad de la expresión para el borde de la siguiente manera:

$$e'_D(f) = \frac{1}{D} (f^{1 - D})^{\frac{1}{D}}$$

Los avisos que estamos planteando $f$ a una potencia menor que 0 (es decir, negativo). Cuando se levanta número de potencias negativas que estamos en algún punto de hacer una recíproca (es decir,$x^{-1} = \frac{1}{x}$). Haciendo un recíproco de un número que es ya muy pequeña ( recall $f < 1$, ya que estamos considerando sólo la fracción de volumen, ya que estamos haciendo KNN, es decir, $k$ más cercano de datos de puntos de un total $N$) significa que el número de "crece mucho". Por lo tanto, podemos obtener el comportamiento deseado, es decir, que como $D$ aumenta el poder se convierte en aún más negativo y, por lo tanto, el borde requerido crece mucho en función de cómo un gran $D$ aumenta el exponente.

(observe que $f^{1 - D}$ crece exponencialmente en comparación con la división de $\frac{1}{D}$ que rápidamente se convierte en insignificante).

Answer 3

sí, así que si tienes un cubo unidad, o en su caso una línea de unidad y los datos se distribuye uniformemente y luego tienes que ir a una longitud de 0,1 a 10% de los datos de captura. Ahora a medida que aumenta las dimensiones, aumentos de D, que deceases el poder y la f es menor que 1, aumentará, tal que si D va hasta el infinito la tienes que capturar todo el cubo, e = 1.