Algunas comentarios en el Algoritmo del Vecino K más cercano

El algoritmo del vecino K más cercano es un algoritmo muy eficaz que es usado en muchos problemas prácticos.
Aun cuando existan ejemplos de entrenamiento que tengan ruido,este algoritmo resulta ser bastante robusto . Además puede ser bastante effectivo si se le da un conjutno de entrenamiento lo suficientemente grande. Esto tiene sentido, si recordamos que este algoritmo clasifica a un elemento X dependiendo de como es la clasificación que poseen la mayoría de los vecinos cercanos, por ende se puede suavizar el impacto de un ejemplo de entrenamiento que tenga ruido.

Una cierto "prejuicio" que se tiene en este algoritmo, es que se asume que la clasificación de un elemento x, será muy similar a la clasificación elegida para otros elementos que están cercanos a x.

Ahora bien, otra cosa interesante que hay que considerar de este algoritmo, es que la distancia entre elementos se calcula con base en todos los atributos que poseen. Aunque puede surgir aquí un pequeño inconveniente, ya que, ¿Qué sucedería, si de los 20 atributos solamente 2 son relevantes para la clasificación?
En este caso, es claro que se podrían tener dos elementos cuyos 2 relevantes atributos sean iguales, mas por los demás atributos que poseen,podrían estos elementos estar muy separados entre si. Lo cual haría que este algoritmo fuera bastante "engañoso". Lo que determinaría la distancia entre vecinos, serían los numerosos atributos irrelevantes que los elementos poseen. A esto, se le suele llamar, La maldición de la dimensionalidad!


Un modo para solucionar esto es:
Cuando se está calculando la distancia en la que están dos objetos, se deberá dar un peso differente a cada atributo, esto es, darle prioridad a los atributos de interés, la multiplicación de una constante grande por los atributos de interés, y la multiplicación de una constante pequeña por los atributos menos relevantes, hace esto posible.

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.