Vecinos más cercanos

El algoritmo de k-NN (k-nearest neighbours) es el más simple.

El algoritmo es robusto con ejemplos que tienen ruido.

Los vecinos más cercanos a una instancia se obtienen, en caso de atributos continuos, utilizando la distancia Euclideana sobre los $n$ posibles atributos (luego veremos otro tipo de distancias):

$$d(x_i,x_j) = \sqrt{\sum_{r=1}^n (a_{r}(x_i) - a_{r}(x_j))^2}$$

El resultado de la clasificación de k-NN puede ser discreto o continuo.

En el caso discreto, el resultado de la clasificación es la clase más común de los k-vecinos (ver tabla 9.1).

Tabla 9.1: El algoritmo de los k vecinos más cercanos.

La forma que se genera con $k = 1$ es un diagrama de Voronoi alrededor de las instancias almacenadas. A una nueva instancia se le asigna la clasificación del vecino más cercano.

Para clasificaciones continuas, se puede tomar la media de las clasificaciones.

$$f(x_q) = \frac{\sum_{i=1}^k f(x_i)}{k}$$

Un extensión obvia al algoritmo es pesar las clasificaciones de los vecinos de acuerdo a su distancia con el objeto a clasificar (la clasificación de vecinos más cercanos tienen más peso). Promedio ponderado (weigthed average) promedia la salida de los puntos pesados inversamente por su distancia.

Para clases discretas:

$$f(x_q) = argmax_{v \in V} \sum_{i=1}^k w_i \delta(v,f(x_i))$$

donde: $w_i = \frac{1}{d(x_q,x_i)^2}$ (si la distancia es $0$ entonces $w = 0$).

Para clase continuas:

$$f(x_q) = \frac{\sum_{i=1}^k w_i f(x_i)}{\sum_{i=1}^k w_i}$$

Una suposición es que los vecinos más cercanos nos dan la mejor clasificación y esto se hace utilizando todos los atributos.

El problema es que es posible que se tengan muchos atributos irrelevantes que dominen sobre la clasificación (e.g., 2 atributos relevantes dentro de 20 irrelevantes no pintan).

Una posibilidad es pesar las distancias de cada atributo, dandole más peso a los atributos más relevantes.

Otra posibilidad es tratar de determinar estos pesos con ejemplos conocidos de entrenamiento. Alterando los pesos para minimizar el error.

Finalmente, también se pueden eliminar los atributos que se consideran irrelevantes.

Un elemento práctico adicional, tiene que ver con el almacenamiento de los ejemplos. En este caso se han sugerido representaciones basadas en árboles ($kd$-trees) donde las instancias están distribuidas en base a su cercania.