KNN (K-Nearest Neighbours)

Rodrigo E. Avalos Melgarejo; William Bustamante Duarte

Facultad de Ciencias y Tecnologías (UNC@)
Coronel Oviedo - Paraguay
 Resumen

KNN (vecino más cercano) es un algoritmo de clasificación ampliamente usado debido

a su simplicidad, facilidad de implementación y eficacia. Es uno de los diez mejores
algoritmos de minería de datos, se ha aplicado ampliamente en varios campos. KNN
tiene algunas deficiencias que afectan su precisión de clasificación. Tiene grandes
requisitos de memoria, así como una gran complejidad de tiempo.

En Machine Learning, estamos utilizando la extracción semiautomatizada del

conocimiento de los datos para identificar las especies de flores de IRIS. La clasificación
es un aprendizaje supervisado en el que la respuesta es categórica, es decir, sus valores
están en conjunto desordenado finito. Aquí el problema se refiere a la identificación de
especies de flores IRIS sobre la base de medidas de atributos florales. La clasificación
del conjunto de datos IRIS consistiría en descubrir patrones a partir del examen del
tamaño del pétalo y del sépalo de la flor IRIS y cómo se realizó la predicción al analizar
el patrón a partir de la clase de flor IRIS. En este documento, se entrena el modelo de
aprendizaje automático con datos y cuando se descubren datos no vistos, el modelo
predictivo predice la especie utilizando lo que se aprendió de los datos entrenados.

Palabras clave: Clasificación, Regresión logística, K Vecino más cercano, Aprendizaje

automático.

Abstract

KNN (k-nearest neighbor) is an extensively used classification algorithm owing to its

simplicity, ease of implementation and effectiveness. It is one of the top ten data mining
algorithms, has been widely applied in various fields. KNN has few shortcomings
affecting its accuracy of classification. It has large memory requirements as well as high
time complexity.

In Machine Learning, we are using semi-automated extraction of knowledge of data for

identifying IRIS flower species. Classification is a supervised learning in which the
response is categorical that is its values are in finite unordered set. Here the problem
concerns the identification of IRIS flower species on the basis of flowers attribute
measurements. Classification of IRIS data set would be discovering patterns from
examining petal and sepal size of the IRIS flower and how the prediction was made from
analyzing the pattern to from the class of IRIS flower. In this paper we train the machine
learning model with data and when unseen data is discovered the predictive model
predicts the species using what it has been learnt from the trained data.

Keywords: Classification, Logistic Regression, K Nearest Neighbour, Machine

Learning.
 Introducción estadístico. Hay dos categorías principales
de aprendizaje automático. Son aprendizaje
Supervisado y No Supervisado y aquí en
El K-NN es un algoritmo de aprendizaje este, el documento se enfoca en el
supervisado, es decir, que a partir de un aprendizaje supervisado. El aprendizaje
juego de datos inicial su objetivo será de supervisado es una tarea de inferir una
clasificar correctamente todas las instancias función de datos de entrenamiento
nuevas. El juego de datos típicos de este etiquetados. Los datos de entrenamiento
tipo de algoritmos está formado por varios consisten en un conjunto de ejemplos de
atributos descriptivos y solo un atributo entrenamiento. En el aprendizaje
objetivo también llamado clase. supervisado, cada ejemplo es un par de un
objeto de entrada y un valor de salida
La idea es realmente sencilla: el algoritmo deseado. Un algoritmo de aprendizaje
clasifica cada dato nuevo en el grupo que supervisado analiza los datos de
corresponda, según tenga k vecinos más entrenamiento y produce una función
cerca de un grupo o de otro. Es decir, inferida, que se puede usar para mapear
calcula la distancia del elemento nuevo a nuevos ejemplos. Los problemas de
cada de uno de los existentes, y ordena aprendizaje supervisado se pueden agrupar
dichas distancias de menor a mayor para ir en problemas de regresión y clasificación. El
seleccionando el grupo será, por tanto, el de problema de clasificación es cuando la
mayor frecuencia con menores distancias. variable de salida es una categoría, como
El Machine Learning es el subcampo de la "rojo" o "azul" o "enfermedad" y "sin
ciencia de la computación, según Arthur enfermedad". El problema de regresión es
Samuel en 1959 dijo que "las computadoras cuando la variable de salida es un valor real,
tienen la capacidad de aprender sin estar como "dólares" o "peso".
programadas explícitamente". Desarrollado En este trabajo se presenta un nuevo
a partir del estudio de reconocimiento de método para la identificación de especies de
patrones y teoría de aprendizaje flores de iris. Funciona en dos fases, es
computacional en inteligencia artificial, el decir, entrenamiento y prueba. Durante el
aprendizaje automático explora el estudio y entrenamiento, el conjunto de datos de
la construcción de algoritmos que pueden entrenamiento se carga en el Modelo de
aprender y hacer predicciones sobre datos aprendizaje automático y se asignan las
tales algoritmos superados siguiendo etiquetas. Además, el modelo predictivo
instrucciones de programa estrictamente predice a qué especie pertenece la flor de
estáticas haciendo predicciones o iris. Por lo tanto, la especia Iris esperada
decisiones basadas en datos, a través de está etiquetada.
construyendo un modelo a partir de entradas
de muestra. El aprendizaje automático se Este documento se enfoca en la
emplea en una variedad de tareas clasificación de flores de IRIS usando
informáticas en las que el diseño y la Machine Learning. El enunciado del
programación explícita de algoritmos con un problema se refiere a la identificación de
buen rendimiento son difícil o inviable; las especies de flores IRIS en la base de las
aplicaciones de ejemplo incluyen filtrado de mediciones de atributos florales. La
correo electrónico, detección de intrusos de clasificación del conjunto de datos IRIS
red, aprendizaje de rango y visión por consistiría en descubrir patrones a partir del
computadora. examen del tamaño del pétalo y del sépalo
de la flor IRIS y cómo se hizo la predicción
El aprendizaje automático se centra en el al analizar el patrón para formar la clase de
desarrollo de programas informáticos que flor IRIS. En este documento, entrenamos el
pueden enseñar a crecer y cambiar cuando Modelo de Aprendizaje Automático con
se exponen a nuevos datos. Es un campo datos y cuando se descubren datos no
de investigación en la intersección de vistos, el modelo predictivo predice la
estadísticas, inteligencia artificial y ciencias especie utilizando lo que ha aprendido de
de la computación y también se conoce los datos entrenados
como análisis predictivo o aprendizaje
 Conjunto de datos: variables que se van a predecir
denominadas dados los valores de los
Se distinguen dos tipos, el conjunto de atributos. Se usan, por ejemplo, arboles
entrenamiento y el conjunto de prueba. de regresión, regresión lineal, redes
Para obtener estos, dividimos los datos neuronales, KNN como se verá en este
muéstrales en dos partes; una parte se documento, etc.
utiliza como conjunto de entrenamiento
para determinar los parámetros del KNN
clasificador y la otra parte, llamada
El algoritmo k-NN, asume que todas las
conjunto de prueba (test o conjunto de
instancias corresponden a puntos en un
generalización) se utiliza para estimar el
espacio n-dimensional <n, aunque el
error de generalización ya que el
algoritmo funciona igualmente para
objetivo tales que el clasificador consiga
cualquier otro tipo de espacio, incluso
un error de generalización pequeño
sino es métrico.
evitando el sobreajuste (o sobre
entrenamiento), que consiste en una Los vecinos más cercanos de un
sobrevaloración de la capacidad ejemplo son detenidos en términos de
predictiva de los modelos obtenidos: en una distancia. Usualmente se utiliza la
esencia, no tiene sentido evaluar la distancia euclidea; sin embargo, como
calidad del modelo sobre los datos que se mencionó anteriormente, por ser un
han servido para construirlo ya que esta algoritmo basado en distancias, es
práctica nos lleva a ser demasiado posible utilizar cualquier otra distancia:
optimistas acerca de su calidad. la distancia de Manhattan, la distancia
de Chebychev, etc. En el aprendizaje
El conjunto de entrenamiento suele a su
del vecino más cercano, la función de
vez dividirse en conjuntos de
salida puede ser un valor discreto
entrenamiento (propiamente dicho) y
(clasificación) o continuo (regresión).
conjunto de validación para ajustar el
modelo (Ver Figura 2).
Se suelen utilizar el 80% de los datos Características generales
para entrenar a la máquina, el 10%
como conjunto de validación y el 10%  Las reglas de clasificación por
restante para estimar la generalización vecindad están basadas en la
(pero es solo un criterio orientativo). búsqueda en un conjunto de
prototipos de los k prototipos
más cercanos al patrón a
clasificar.

 No hay un modelo global

asociado a los conceptos a
aprender.

 Las predicciones se realizan

basándose en los ejemplos más
Figure 2: parecidos al que hay que
predecir.

 El coste del aprendizaje es 0,

Modelo todo el coste pasa al cálculo de
Modelo o clasificador, es una conexión la predicción.
entre las variables que son dadas y las
que se van a predecir. Usualmente las
  Se conoce como mecanismo de Clasificación de datos con el
aprendizaje perezoso (lazy método k-vecinos
learning).

 Debemos especificar una

El método de los k-vecinos o k-nn es un
métrica para poder medir la
método retardado y supervisado (pues
proximidad.
su fase de entrenamiento se hace en un
 Suele utilizarse por razones tiempo diferente al de la fase de prueba)
computacionales la distancia cuyo argumento principal es la distancia
Euclídea, para este fin. entre instancias. El método
básicamente consiste en comparar la
nueva instancia a clasificar con los datos
El método k-nn pertenece al grupo de k más cercanos conocidos, y
métodos para tareas de clasificación de dependiendo del parecido entre los
datos que se pueden encontrar dentro atributos el nuevo caso se ubicará en la
de minería de datos. Más clase que más se acerque al valor de
específicamente, k-nn es un método de sus propios atributos (cumpliendo así lo
vecindad basado en casos o instancias. planteado por el concepto de heurística
de consistencia). La principal dificultad
Para poder entender cómo clasificar de este método consiste en determinar
datos usando k-nn es importante el valor de k, ya que si toma un valor
abordar temas como el aprendizaje grande se corre el riesgo de hacer la
basado en casos (haciendo énfasis en clasificación de acuerdo a la mayoría (y
el concepto de heurística de no al parecido), y si el valor es pequeño
consistencia), los métodos basados en puede haber imprecisión en la
vecindad y algunos tipos de medición de clasificación a causa de los pocos datos
distancia. seleccionados como instancias de
comparación. Para enfrentar este
Aprendizaje basado en casos: El
problema se plantearon diferentes
aprendizaje basado en casos o
variaciones del método: en cuanto a la
instancias consiste en extraer
forma de determinar el valor de k, por
información de un conjunto de datos
ejemplo 1-nn, que no es otra cosa más
(también llamados casos o instancias)
que usar como instancia de
conocidos y usarla para clasificar
comparación al primer vecino más
nuevos datos o para agrupar datos
cercano encontrado.
existentes. Un concepto muy importante
dentro del aprendizaje basado en casos
es el de heurística de consistencia (la Métricas para medir
heurística de consistencia es la base del distancia
aprendizaje basado en casos).
Los atributos son las diferentes La distancia es el criterio de
características que determinan un dato,
comparación principal usado en los
es decir, lo particularizan o diferencian
métodos basados en vecindad, por eso
de otros. La clase es un atributo que es conveniente mencionar algunas de
sobresale de los demás y es la base de las diferentes formas usadas para su
la que se parte para poder clasificar y
medición. A continuación, sólo se
agrupar instancias, ésta es la naturaleza
mostrarán los modelos matemáticos
del dato.
generales de cada métrica, sin detalles,
ya que no es un propósito de este
artículo ahondar sobre el tema:
simplemente se desea recordar que Metodología
además de la distancia clásica
euclidiana existen métricas alternativas
Para demostrar el algoritmo KNN
Formula de distancia de Minkowski usamos tal dataset de prueba iris y la
herramienta de Anaconda con Python,
La distancia de Minkowski es una
el dataset consiste en un conjunto de
generalización de las distancias
datos multivariante introducido por
euclidea, Manhattan y Chebychev, Ronald Fisher en su papel de 1936, se
donde un parámetro p debe ser coleccionó la data usada para
definido. Si p = 1, es la distancia de cuantificar la variación morfológica del
Manhattan, si p = 2, es la distancia Iris con las flores de tres especies
euclidea y finalmente si p = 1, es la relacionadas. El conjunto de datos
distancia de Chebychev. contiene 50 muestras de cada una de
Adicionalmente, la distancia euclidea tres especies de Iris (Iris setosa, Iris
es un caso particular de la distancia virginica e Iris versicolor), en total serian
de Mahalanobis: en la distancia 150 muestras. Se midió cuatro rasgos
de cada muestra: lo largo y lo ancho de
euclidea no se tiene en cuenta la
los sépalos y pétalos, en centímetros.
correlación entre los atributos.
Basado en la combinación de estos
 Distancia euclidea cuatro rasgos, Fisher se desarrolló un
modelo discriminante lineal para
distinguir entre una especie y otra. La
herramienta anaconda con el editor de
Spyder y funciona en la pc una vez
 Distancia de Manhattan instalada en el ordenador. Probamos tal
porcentaje del dataset con el algoritmo
KNN utilizando la fórmula de distancia
de Minkowski.

Resultados
 Distancia de Chebychev

 Distancia de Minkowski
 Análisis

Luego de la prueba de entrenamiento

encontramos que este algoritmo
funciona bien para calcular la distancia
de los vecinos más cercanos, no
requiere de mucho entrenamiento y no
requiere de mucha potencia.

Discusión

El dataset IRIS era adecuado pues

consiste en un conjunto de datos que
describe tres tipos de flores Iris (setosa,
virginica y versicolor) por las
dimensiones de su sépalo y pétalo; se
puede usar para entrenar un modelo de
aprendizaje de máquina para que este
infiera el tipo de flor (clasificación) con
base en la combinación de parámetros.

Bibliografía

[1] Cristina García Cambronero,

«Inteligencia en Redes de
Telecomuncicación,» de
ALGORITMOS DE
APRENDIZAJE: KNN &
KMEANS, Madrid, pp. 1-2-4-5.

Podemos ver que la precisión es 0.9 o

90%. La matriz de confusión
proporciona una indicación de los tres
errores cometidos. Finalmente, el [2]
informe de clasificación proporciona un J. A. B. Puerta, «Aplicacion de
desglose de cada clase por precisión, distancias entre terminos para
recuperación, puntaje y soporte que datos planos y jerarquicos,» nº 2,
muestra excelentes resultados (se pp. 10-11, 2011.
concede que el conjunto de datos de
validación fue pequeño).