Regla de los K vecinos más cercanos
| ||||||
Regla de los k vecino más cercano (k-NN Nearest Neighbour) es otro clasificador supervisado basado en Reconocimiento de patrones criterios de vecindad, y también se conoce como algoritmo de clasificación ``k-NN``. Parte de la idea de que una nueva muestra será clasificada a la clase a la cual pertenezca la mayor cantidad de vecinos más cercanos del [Reconocimiento de patrones patrón] del conjunto de entrenamiento más cercano a ésta.
Sumario
Regla ``k`-NN`
Al aplicar la regla NN, se explora todo el conocimiento almacenado en el conjunto de entrenamiento para determinar cuál será la clase a la que pertenece una nueva muestra, pero únicamente tiene en cuenta el vecino más próximo a ella, por lo que es lógico pensar que es posible que no se esté aprovechando de forma eficiente toda la información que se podría extraer del conjunto de entrenamiento.
Con el objetivo de resolver esta posible deficiencia surge la regla de los k vecinos más cercanos (k-NN). La regla k-NN es una extensión de la regla NN, en la que se utiliza la información suministrada por los k prototipos del conjunto de entrenamiento más cercanos de una nueva muestra para su clasificación.
Formalmente se define la vecindad de los k vecinos más cercanos de una muestra x como:
Definición de vecindad
Sea un conjunto de entrenamiento de N prototipos pertenecientes a M clases distintas, E el Reconocimiento de patrones espacio de representación de los objetos y x una muestra (). Se define como vecindad al conjunto de prototipos del conjunto de entrenamiento que cumple las tres condiciones siguientes:
La expresión anterior significa que la regla k-NN determina que la clase a la cual pertenece una nueva muestra x es la más votada por sus k vecinos más cercanos.
Ejemplo de funcionamiento
En la imagen superior se ilustra el funcionamiento de esta regla de clasificación. 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 círculos de color rojo. En este ejemplo, se han seleccionado tres vecinos, es decir, (k=3).
De los 3 vecinos más 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 señalar que si se hubiese utilizado como regla de clasificación la NN, la muestra x sería asignada a la Clase 1, pues el vecino más cercano de la muestra x pertenece a la Clase 1.
Ventajas y limitantes
En problemas prácticos donde se aplica esta regla de clasificación se acostumbra tomar un número k de vecinos impar para evitar posibles empates, aunque esta forma es cierta en problemas que poseen dos clases nada más. También, los empates pueden ser resueltos decidiendo aleatoriamente la clasificación de la muestra entre las clases empatadas o la clase donde la distancia media de sus vecinos sea inferior.
Para determinados problemas reales (es decir, con un número finito de muestras e incluso, en muchas ocasiones, un número relativamente pequeño), la aplicación de esta regla podría entenderse como una solución poco apropiada, debido a los pobres resultados que pudieran obtener, es decir, a su baja tasa de aciertos en el correspondiente proceso de clasificación. Este problema también está presente cuando el número de muestras de que se dispone puede considerarse pequeño comparado con la dimensionalidad intrínseca del espacio de representación, lo cual corresponde a una situación bastante habitual.
Fuentes
Facultad de Matemática y Computación de la Universidad de Oriente.
