Interpretación del algoritmo K de vecinos más próximos

Question

En el libro Los elementos del aprendizaje estadístico http://statweb.stanford.edu/~tibs/ElemStatLearn/printings/ESLII_print10.pdf (página 19-20)

El autor afirma que

1. En el método de los mínimos cuadrados, suponemos la función de regresión $f(x)$ está bien aproximada por una función lineal global.

2. En el método de k vecinos más próximos suponemos la función de regresión $f(x)$ está bien aproximada por una función localmente constante.

Puedo entender esta afirmación cuando $k=1$ (como si supusiéramos que en el segmento de línea que une el punto objetivo $x_i$ y su vecino más cercano $x_j$ la función es constante).

Soy incapaz de entender esta afirmación cuando $k \neq 1$ . Si $k \neq 1$ hacemos una media de los $k$ vecinos más cercanos. Si suponemos que la función es localmente constante, para qué necesitamos promediar, podemos elegir uno de los k vecinos.

¿Puede alguien aclarar qué quiere decir el autor con la afirmación 2?

Answer 1

Tenga en cuenta que para cualquier $k$ la aproximación de la función será constante a trozos en algún conjunto de celdas. Obviamente, las celdas dependerán de la distribución espacial de los datos. Sin embargo, las celdas también dependen de $k$ .

Como señala la pregunta, esto puede resultar poco intuitivo para $k>1$ por lo que una visualización puede ayudar. Aquí considero el caso de puntos en 2D con $k=1$ y $k=2$ . (Esperemos que la generalización quede clara).

A continuación se muestra un conjunto de puntos de datos 2D, junto con su Diagrama de Voronoi (puntos y líneas azules). Las células de Voronoi teselan el plano, y para cada punto $x_i$ su celda correspondiente contiene todos los puntos $x$ que están más cerca de $x_i$ que a cualquier otro punto $x_{j\neq i}$ .

He resaltado un único punto $x_i$ de negro. Para $k=1$ la aproximación de la función será constante dentro de la celda de Voronoi asociada (contorno negro en negrita). Así, en general, las celdas 1-NN corresponden a la Voronoi células.

Ahora considere la $k=2$ caso. Para todos los puntos $x$ en la celda de Voronoi resaltada (negra), su vecino más cercano es $x_i$ . Pero, ¿cuál es su segundo vecino más próximo? El rectángulo negro discontinuo de la imagen anterior muestra los posibles vecinos. La imagen de abajo muestra cómo estos " $k=2$ se determinan los "vecinos", ampliando el área de interés (rectángulo discontinuo arriba).

En esta figura, el punto $x_i$ se ha eliminado y se muestra como un círculo negro hueco. Su celda de Voronoi se indica con el contorno negro discontinuo. El diagrama de Voronoi de los puntos restantes se muestra en azul. Para cualquier punto $x$ en el plano, estas celdas de Voronoi "dejan uno fuera" indican cuál de los puntos azules $x_{j\neq i}$ es su vecino más próximo.

Para los puntos cuyo $k=1$ aproximación utiliza $x_i$ El $k=2$ utilizará un 2º punto basado en el diagrama de Voronoi "leave one out". Por lo tanto, las celdas utilizadas para la aproximación 2-NN se determinarán mediante la intersección de estas celdas de Voronoi "leave one out" con la celda de Voronoi del punto left-out. Esto se muestra en una tercera figura a continuación.

Aquí la célula de Voronoi para $x_i$ se divide en un conjunto de celdas 2-NN. El color de cada subcelda corresponde al 2º vecino más cercano $x_j$ . En cada una de estas subceldas, los 2 vecinos más cercanos son fijos, por lo que la aproximación de la función de 2-NN será constante.

(Nota: Las celdas coloreadas de arriba son en realidad "medias celdas 2-NN", porque para cualquier $x_j$ su diagrama de Voronoi de un lado a otro tendrá una semicelda correspondiente a $x_i$ . En ambas semiceldas la aproximación 2-NN será la misma).

Esperemos que esto ayude a intuir lo que se entiende por "constante a trozos". Para mayores $k$ estas celdas se subdividirían aún más (por ejemplo, utilizando un diagrama de Voronoi de "dejar dos fuera" para $k=3$ ). Lógicamente, los diagramas de Voronoi también pueden extenderse a dimensiones superiores (3D, 4D,...), pero su cálculo práctico resulta inviable. Por supuesto, para kNN nunca se necesita el diagrama completo sobre todo el espacio, sino sólo sobre un conjunto finito de puntos de consulta.

Una nota final. La hipótesis de la constante a trozos no siempre está justificada. Para los casos 2D y 3D, donde la función es suave, un enfoque relacionado que utiliza diagramas de Voronoi incrementales es Interpolación natural de vecinos . (Esto se utiliza a veces para las simulaciones de física, como parte de la Método de los elementos naturales .)

Answer 2

Supongamos que observamos $y_1, \dots, y_n$ donde $y_i = \mu + \varepsilon_i$ para errores iid $\varepsilon_i$ con media 0 y varianza $\sigma^2$ . Sólo estoy denotando el valor constante de $f(x_i)$ para cada $i$ por $\mu$ aquí. Queremos predecir la etiqueta $y_0$ para algún nuevo punto $x_0$ lo que podríamos hacer (1) tomando el punto más cercano a nuestro punto de prueba, digamos $y_1$ o (2) podríamos promediar los $y_i$ sobre todo $n$ .

Ambos son imparciales ya que $E(y_1) = E(\bar y) = \mu$ . Pero sus varianzas difieren: $Var(y_1) = \sigma^2$ mientras que $Var(\bar y) = \sigma^2/n$ Así que $\bar y$ es el mejor estimador.

Por lo tanto, si la función de regresión es realmente constante para todo $n$ de estos puntos, entonces obtendremos un estimador mucho mejor promediando en lugar de usar sólo uno de ellos. Sin embargo, en la práctica no es tan sencillo, porque no creemos que la función de regresión sea verdaderamente constante, por lo que puede ser que el valor esperado de los puntos más alejados sea demasiado diferente y no queramos incluirlos. Todo esto se capta eligiendo $k$ .

Answer 3

Esto es lo que yo entiendo sobre cómo funciona kNN: dada una nueva observación, calcularemos la distancia entre esta nueva observación y todas las demás observaciones del conjunto de datos de entrenamiento. Entonces se obtienen los vecinos (los más cercanos a la nueva observación).

Si $k=5$ entonces miramos las 5 observaciones más cercanas. "una función localmente constante" significa que después de elegir estas 5 observaciones, no nos importan las distancias. Son las mismas, tienen la misma importancia ahora para la predicción.

La media que calculamos es el valor medio de y (que es 0 o 1, para significar "azul" o "naranja"). Dicho de otra forma, será la proporción de la clase positiva (la clase que se intenta predecir, aquí puede ser arbitraria, ya sea "azul" o "naranja").

Ahora bien, si intentamos encontrar una función que no sea "localmente constante", se trataría de una distribución normal. En este caso, obtendremos un algoritmo llamado Análisis Discriminante Lineal o Naive Bayes (dependiendo de algunos otros supuestos).

PD: es la misma lógica para histograma vs distribución paramétrica.