“Dime con quién vas y te diré quién eres”
Este refrán rancio y conocido por tod@s, me da pie a comentar un algoritmo muy popular y utilizado en modelos de clasificación: el de los K vecinos más cercanos o K-NN (K Nearest Neighbours).
Concepto
La idea es realmente sencilla: el algoritmo clasifica cada dato nuevo en el grupo que corresponda, según tenga k vecinos más cerca de un grupo o de otro. Es decir, calcula la distancia del elemento nuevo a cada uno de los existentes, y ordena dichas distancias de menor a mayor para ir seleccionando el grupo al que pertenecer. Este grupo será, por tanto, el de mayor frecuencia con menores distancias.
El K-NN es un algoritmo de aprendizaje supervisado, es decir, que a partir de un juego de datos inicial su objetivo será el de clasificar correctamente todas las instancias nuevas. El juego de datos típico de este tipo de algoritmos está formado por varios atributos descriptivos y un solo atributo objetivo (también llamado clase).
¿Cómo funciona? Ejemplo
En contraste con otros algoritmos de aprendizaje supervisado, K-NN no genera un modelo fruto del aprendizaje con datos de entrenamiento, sino que el aprendizaje sucede en el mismo momento en el que se prueban los datos de test. A este tipo de algoritmos se les llama lazy learning methods y funciona como en este ejemplo:
Pensemos en un juego de datos donde cada instancia se corresponde con un cliente de una entidad financiera. Para cada cliente conocemos una serie de atributos, como sus ingresos, gastos, patrimonio, edad,etc., también para cada cliente tenemos un atributo objetivo o clase que trataremos predecir: es o no apto para un préstamo personal.
Sea D nuestro juego de datos en el que distinguimos la siguiente estructura:
Donde dm indica cada una de las instancias del juego de datos (los clientes), am,n indica cada uno de los atributos descriptivos (ingresos, gastos, patrimonio, edad, etc.) y c indica el atributo objetivo o clase a predecir (es o no apto para un préstamo personal).
Para crear el modelo, partimos nuestro juego de datos D en dos partes aleatorias: una compuesta por el 70% que usaremos para entrenar, y otra por el 30% restante que usaremos para validar el modelo.
En este punto, merece la pena comentar que puede llegar a producirse el efecto del sobreentrenamiento del modelo (overfitting), lo que provoca que el modelo que se construye, en lugar de describir las estructuras subyacentes del juego de datos, lo que acaba describiendo sea, exclusivamente, el juego de datos de entrenamiento no siendo extrapolable a otros juegos de datos.
Fijamos un valor para k, habitualmente pequeño, y hacemos que el algoritmo compute una instancia d del juego de datos de prueba. Fruto de este proceso, el algoritmo selecciona las k instancias del juego de datos de entrenamiento más cercanas (de acuerdo con la métrica de similitud utilizada) y se asigna la instancia d a la clase más frecuente de entre las k instancias seleccionadas como más cercanas.
Como vemos, sin duda, se trata de un algoritmo tremendamente simple pero con una buena efectividad.
Destacar que K-NN es muy sensible a:
- La variable k, de modo que con valores distintos de k podemos obtener resultados también muy distintos. Este valor suele fijarse tras un proceso de pruebas con varias instancias.
- La métrica de similitud utilizada, puesto que esta influirá, fuertemente, en las relaciones de cercanía que se irán estableciendo en el proceso de construcción del algoritmo. La métrica de distancia puede llegar a contener pesos que nos ayudarán a calibrar el algoritmo de clasificación, convirtiéndola, de hecho, en una métrica personalizada.
Vemos cómo influye el valor de k:
- Para k = 1 el algoritmo clasificará la bola con signo + como blanca
- Para k = 2 el algoritmo no tiene criterio para clasificar la bola con signo +
- Para k >= 3 el algoritmo clasificará la bola con signo + como negra
Su mayor debilidad es la lentitud en el proceso de clasificación puesto que su objetivo no es obtener un modelo optimizado, sino que cada instancia de prueba es comparada contra todo el juego de datos de entrenamiento y, será la bondad de los resultados lo que determinará el ajuste de aspectos del algoritmo como el propio valor k, el criterio de selección de instancias para formar parte del juego de datos “D” de entrenamiento o la propia métrica de medida de similitud.
Finalmente, conoceremos la precisión del algoritmo a través de una evaluación de la matriz de confusión. En ella, se valorarán los verdaderos positivos, los falsos positivos, los positivos incorrectos, etc.
Aplicaciones
Este modelo se utiliza en data mining (minería de datos), por lo que su uso en aprendizaje automático (Machine Learning) es una de sus aplicaciones clave para, por ejemplo, sistemas de recomendación (plataformas de contenido digital, procesos de venta cruzada en eCommerce, etc.).
Por último y, a modo de comentario, el concepto de los vecinos más cercanos es un importante factor en la física de estado sólido, ya que las propiedades de la materia se modifican en función de la estructura de las redes y las distancias entre los átomos. De hecho, es habitual hacer aproximaciones en los modelos físicos para despreciar aquellas partículas que no forman parte de los K vecinos más próximos.
¿Qué más casos de uso podrían plantearse con este tipo de modelo?
