Mtodo de los vecinos ms prximos (k-Nearest Neighbor)El mtodo de lo vecinos ms prximos es un mtodo de clasificacin que estima el valor de lafuncin de densidad de probabilidado directamente laprobabilidada posteriori de que un elemento X pertenezca a la clase C a partir de la informacin proporcionada por el conjunto de prototipos, es decir las muestras conocidas con las que se entrena el sistema.Este paradigma se fundamenta en una idea muy simple e intuitiva, que unido a su fcil implementacin hace que sea un mtodo clasificatorio muy extendido.

Distancia entre dos elementosPara aplicar el mtodo, se debe establecer una regla que permita definir la distancia entre los distintos elementos del espacio de representacin.Por ejemplo los datos Iris pertenecientes al repositorio de RapidMiner contienen los valores de largo y ancho de los ptalos y spalos que se utilizan pata identificar la especie de planta a la que pertenece un espcimen. Con estos valores se puede formar un vectores de 4 dimensiones y la distancia entre dos de ellos vendra dada por

A este tipo de distancia se le llama euclidiana y viene dada en general por:

Esto nos permite conocer cuales muestras estn ms cercanas a otras.

AlgoritmoLuego de que se ha establecido una regla para la distancia entre dos muestras, ahora si se puede aplicar el algoritmo en s, cuya idea bsica consiste en que un nuevo caso se va a clasificar en la clase a la que pertenezcan sus k-vecinos ms prximos.La fase de entrenamiento consiste en almacenar los vectores caractersticos y las etiquetas de las clases de los ejemplos de entrenamiento.En la fase de clasificacin, se calculan las distancias de todos los casos ya clasificados al nuevo caso x, y se seleccionan los k casos cuya distancia a x sea mas corta, es decir se seleccionan los k vecinos ms prximos y la clase que sea mas frecuente en estos k casos ser la asignada a xEn la siguiente figura se presenta un pseudocdigo para el clasificador K- bsico

Ejemplo1:

En la imagen superior se ilustra el funcionamiento de esta regla de clasificacin. En ella se encuentran representadas 12 muestras pertenecientes a dos clases distintas: la Clase 1 est formada por 6 cuadrados de color azul y la Clase 2 formada por 6 crculos de color rojo. En este ejemplo, se han seleccionado tres vecinos, es decir, (k=3).De los 3 vecinos ms cercanos a la muestra x, representada en la figura por una cruz, uno de ellos pertenece a la Clase 1 y los otros dos a la Clase 2. Por tanto, la regla 3-NN asignar la muestra x a la Clase 2. Es importante sealar que si se hubiese utilizado como regla de clasificacin la NN, la muestra x sera asignada a la Clase 1, pues el vecino ms cercano de la muestra x pertenece a la Clase 1.Ejemplo2:

La muestra que se desea clasificar es el circulo verde. Para k = 3este es clasificado con la clase tringulo, ya que hay solo un cuadrado y 2 tringulos, dentro del circulo que los contiene. Sik = 5este es clasificado con la clasecuadrado, ya que hay 2 tringulos y 3 cuadrados, dentro del circulo externo.

Mtodo Atpico

Conviene aclarar que el paradigma K-NN es un tanto atpico si lo comparamos con el resto de paradigmas clasificatorios, ya que mientras que en el resto de paradigmas, la clasificacin de un nuevo caso se lleva a cabo a partir de dos tareas, como son la induccin del modelo clasificatorio y la posterior deduccin (o aplicacin) sobre el nuevo caso, en el paradigma K-NN al no existir modelo explcito, las dos tareas anteriores se encuentran colapsadas en lo que se acostumbra a denominar transinduccin.

Eleccin delLa mejor eleccin dedepende fundamentalmente de los datos; generalmente, valores grandes dereducen el efecto deruidoen la clasificacin, pero crean lmites entre clases parecidas. El caso especial en que la clase es predicha para ser la clase ms cercana a la muestra de entrenamiento (cuando) es llamada Algoritmo del vecino ms cercano.

Resolucin de empates En casos donde solo existen dos clases, se pueden evitar empates escogiendo un valor de k impar. En otros casos se pueden resolver decidiendo aleatoriamente la clasificacin de la muestra entre las clases empatadas, tomando el vecino ms prximo o donde la distancia media de sus vecinos sea inferior.

Variantes sobre el algoritmo bsico K-NN con rechazo: para poder clasificar un nuevo elemento se deben cumplir ciertas garantas prefijadas como por ejemplo que el nmero de votos obtenidos por la clase supere un umbral prefijado o que la diferencia de votos entre las dos clases mas frecuentes ser mayor a un numero prefijado.

K-NN con distancia media: la idea es asignar un nuevo caso a la clase cuya distancia media sea menor.

K-NN con distancia mnima: se selecciona un caso por clase, normalmente el caso ms cercano al baricentro a todos los elementos de dicha clase. A continuacin se asigna al nuevo caso la clase cuyo representante est ms cercano. Esto reduce el nmero de casos a almacenar.

K-NN con pesado de casos seleccionados: los k casos seleccionados no se cuentan de igual forma sino que se tiene en cuenta la distancia dcada caso seleccionado al nuevo caso que se pretende seleccionar. Como ejemplo podemos convenir en pesar cada caso seleccionado de manera inversamente proporcional a la distancia del mismo al nuevo caso.

K-NN con pesado de las variables: se le da un peso a las distancias de cada atributo, dndole as menor importancia a los atributos ms irelevantes que me podran afectar peligrosamente los resultados.

Reduccin del fichero de casos inicialDebido a la fuerte dependencia del costo computacional del clasificador K-NN, se buscan formas de reducir el nmero de casos iniciales almacenados. Dos mtodos para ellos son los siguientes: Edicin de Wilson: Para cada uno de los elementos del fichero de casos inicial, se compara su clase verdadera con la que propone un clasificador K-NN obtenido con todos los casos excepto el mismo. En el caso en que ambas clases no coincidan el caso es eliminado.

Condensacin de Hart: Se efecta una seleccin de casos que pueden considerarse raros. Para ello, para cada caso, y siguiendo el orden en el que se encuentran almacenados los casos en el fichero, se construye un clasificador K-NN con tan solo los casos anteriores al caso en cuestin. Si el caso tiene un valor de la clase distinto al que le asignara el clasificador K-NN, el caso es seleccionado. Si por el contrario la clase verdadera del caso coincide con la propuesta por el clasificador K-NN, el caso no se selecciona. El mtodo de condensacin de Hart es dependiente del orden en que se encuentren almacenados los casos en el fichero.