Los vecinos K más cercanos

Resumen Del Algoritmo de los k vecinos: (Por si no quieres leer toooda la explicación)
El algoritmo es simple, supongamos que se tiene un objeto X que se quiere clasificar,y se tiene además un conjunto de entrenamiento, el cual consiste de una serie de objetos cada uno con su etiqueta correspondiente. El algoritmo lo que hará para clasificar al objeto X, es tomar del conjunto de entrenamiento K elementos, estos K elementos son los K elementos del conjunto de entrenamiento que más se parecen a X. Se analizará cual etiqueta de los K elementos es la que se presenta con más frequencia, y esta etiqueta será la que se le pondrá a X. Tengo un objeto nuevo que quiero clasificar, pues le pondré el nombre del objeto que más se paresca a él que ya conosco con anterioridad. Así de simple =)

El algoritmo de los K vecinos más cercanos es uno de los algoritmos más simples que existen que muestran la escencia del aprendizaje basado en instancias.
Este algorimo asume que todas las instancias corresponden a puntos que se encuentran en un espacio de dimensión n. El vecino más cercano de una instancia es definido en términos de la distancia Euclidiana estándar.
Para aclarar esto, imagínese una instancia arbitraria x descrita por el vector:
( a1(x), a2(x) , . . .,an(x)



Donde a r(x) corresponde al valor del r"eavo" atributo de la instancia x. Entonces la distancia entre las instancias xi y xj se define por d(xi,xj), donde:

d(xi,xj)= Σ (ar(xi)- ar(xj))^2

En este algoritmo, la función objetivo puede contener valores discretos o valores continuos.
Por ahora consideraremos que queremos aprender una función objetivo que es discreta.
El algoritmo para aproximar una funcion objetivo que es discreta es:

Algoritmo de entrenamiento:

• Para cada uno de los ejemplos de entrenamiento (x,f(x)) agrega el ejemplo a la lista de ejemplos de entrenamiento.

Algoritmo de clasificacion:

• Dada una instancia Xq que quiere ser clasificada,
  
  
• Sean x1 . . .xk las k instancias de los ejemplos de entrenamiento que están más cercanas a Xq
• Regresa
  

un vector f(xq)=argmax Σ D(v,f(xi))

donde D (a,b)=1 si a=b y D(a,b)=0 en cualquier otro caso.
v pertenece al conjunto finito V:(v1,...v2). Este es el conjunto finito al cual es mapeada la función objetivo.

En resumen: Este algoritmo funciona siguiendo un modelo basado en la memoria. La memoria guarda un conjunto de objetos ó instancias que forman parte del entrenamiento. Para cada uno de estos objetos, se sabe cual es su salida, esto es, los objetos están etiquetados. Cada ejemplo contiene un conjunto de valores independientes que producen un conjunto de salida dependiente de ellos.

Cuando las variables dependientes son continuas,se dice que la tarea a tratar es regresión. De lo contrario se trata de clasificación. Por ende este algoritmo puede manejar tanto tareas de regresión y de clasificación.

Dado un conjunto nuevo de valores independientes se busca estimar medinate los k vecinos más cercanos, la salida de este. Esto se logra encontrando k ejemplos de entrenamiento, que en distancia estén más cercanos al objeto a clasificar, de allí el nombre k vecinos más cercanos.


Para la regresión, las prediciones de los K vecinos más cercanos se basan en los promedios de las salidas de los k vecinos más cercanos; Para la clasificación, se utiliza una votación mayoritaria.

En el método de los vécinos K más cercanos, aprender significa Memorizar!

Ahora dare un pequeño ejemplo, para aclarar las cosas
Observese el siguiente dibujo, se tienen dos tipos de instancias, las estrellas y los pentagonos. La tarea del clasificador, será decir si una instancia X es un trapecio ó una estrella. Los ejemplos de entrenamiento son lo que que se muestran, en conjunto con un elemento "?" que se quiere clasificar. Si se tomará el primer vecino más cercano, esto es K=1, entonces se clasificaría al elemento ?, como estrella. Pero, si se tomarán los 5 vecinos más cercanos, se clasificaría al elemento ? como trapecio.