células

K-NN o la influencia de los vecinos

Vamos a iniciar una serie de artículos sobre distintos métodos de aprendizaje supervisado: K-vecinos más cercanos (K-NN), máquinas de soporte vectorial (SVM), árboles de decisión, redes neuronales y métodos probabilísticos.

Recordemos que los métodos de aprendizaje supervisado construyen un modelo a partir de un conjunto de datos de entrenamiento etiquetados. Es decir para cada instancia del conjunto de datos de entrenamiento conocemos el valor de su atributo objetivo o clase. Esto le va a permitir al algoritmo aprender una función que sea capaz de predecir el atributo objetivo para un conjunto de datos nuevos.

En este primer post nos vamos a centrar en el algoritmo K-NN. Este algoritmo es un algoritmo de aprendizaje supervisado de clasificación. Es decir, una vez entrenado, será capaz de predecir la clase de cualquier instancia nueva de datos que se le presente.

Ilustraremos las técnicas con el conjunto de datos Breast Cancer Winscosin Data Set.

Breast Cancer Wisconsin Data Set

Está formado por 569 observaciones con 30 variables de tipo real. El conjunto de datos no presenta valores nulos.

Las variables se calculan a partir de una imagen digitalizada de un aspirado con aguja fina (FNA) de una masa mamaria. Describen las características de los núcleos celulares presentes en la imagen.

Las variables son las siguientes:

  • Radio
  • Textura
  • Perímetro
  • Área
  • Suavidad
  • Compacidad
  • Concavidad
  • Puntos cóncavos
  • Simetría
  • Dimensión fractal

El conjunto de datos está formado por la media, el error estándar y el peor de los valores de las variables para cada una de las imágenes.

El conjunto de datos contiene 212 observaciones clasificadas como malignas y 357 observaciones clasificadas como benignas.

La implementación la realizaremos en Python, utilizando la librería sckit-learn.

K-Nearest Neighbors (K-NN)

El funcionamiento del método es muy simple. Para cada nueva instancia del conjunto de datos a clasificar se seleccionan las k más cercanas del  conjunto de entrenamiento. La clase de la nueva instancia se establece como la clase más frecuente de las k instancias más cercanas. El algoritmo sería el siguiente:

  1. Fijamos el valor de k.
  2. Dada una nueva instancia a clasificar el algoritmo selecciona las k instancias del juego de datos de entrenamiento más cercanas de acuerdo a alguna métrica de distancia definida.
  3. Se asigna a la nueva instancia la clase más frecuente de entre las k instancias más cercanas seleccionadas.

Como veis es un algoritmo tremendamente sencillo y muy efectivo.

Las dos variables que influyen en la bondad del método son el valor de k y la métrica de similitud o distancia escogida. Una de las distancias más utilizada es la distancia euclidea para atributos numérico y la distancia de Hamming para atributos nominales.

El valor de k influye de forma determinante en la ejecución del método. Este valor se escoge tras un número de pruebas. Se suele escoger un número impar o primo para minimizar el número de empates a la hora de decidir la clase de una nueva instancia.

Como cualquier algoritmo que se basa en un cálculo de distancia es muy sensible al rango u orden de los datos. Es muy conveniente realizar un escalado de datos como, por ejemplo, la normalización (z-score) antes de aplicar el algoritmo K-NN.

Aplicando K-NN al Breat Cancer Wisconsin Data Set

En primer lugar, normalizaremos los datos ya que en el conjunto de datos hay atributos con rangos de valores muy distintos.

A continuación construiremos el conjunto de datos de entrenamiento y el conjunto de datos de test. El conjunto de datos de entrenamiento lo utilizaremos para construir el modelo y el conjunto de datos de test para evaluarlo. Para ellos haremos una selección aleatoria del 70% de los datos y los asignaremos al conjunto de datos de entrenamiento. El 30% restante lo asignaremos al conjunto de datos de test.

Finalmente, aplicaremos el algoritmo con k=5 al conjunto de datos de entrenamiento para construir el modelo y, posteriormente, lo aplicaremos al conjunto de test para predecir la clase. La implementación del algoritmo es muy sencilla y se obtiene una exactitud del 95,9% en la clasificación.

Mejorando K-NN

La primera pregunta qué os puede venir a la mente es: ¿por qué k=5? O lo que es lo mismo, ¿existe algún criterio para elegir adecuadamente el valor de k?

Uno de los problemas de hemos de evitar es el sobreentranamiento del modelo (overfitting). Esto implica que el modelo construido se ajusta exclusivamente al juego de datos de entrenamiento y no es capaz de generalizar.

Otro de los problemas con los que nos enfrentamos es el subentrenamento (underfitting), en el que el algoritmo no es capaz de extraer toda la información disponible del conjunto de datos de entrenamiento.

Para elegir el valor más adecuado de k representamos una gráfica que nos muestre la exactitud del modelo para los conjuntos de datos de entrenamiento y test en función del valor de k:

De las gráficas observamos que para valores pequeños de k (k<5) dar lugar a sobreentrenamiento. En general, valores pequeños de k dan lugar a modelos más complejos con un contorno de separación entre clases más ajustado a los datos y, por tanto, más sensible al ruido.

Por otro lado, para valores de k>15 observamos una disminución en la exactitud para el conjunto de entrenamiento y test lo que nos sugiere que se puede estar produciendo subentrenamiento.

Elegiremos el valor de k=11 donde se encuentra el valor más alto para la exactitud. Con este valor se obtiene una exactitud del 97,1%.

Reduciendo dimensiones

¿Podemos hacer algo más para mejorar el algoritmo?

Una técnica de preprocesado que puede favorecer la bondad del modelo es la de reducción de la dimensionalidad. Aplicaremos análisis de componente principales y, seguidamente, el algoritmo K-NN para evaluar sí se produce alguna mejoría.

El análisis de componentes principales trata de transformar los datos en un espacio de dimensión menor con la menor perdida de información (varianza) posible. Los datos originales tienen treinta atributos, lo que significa que los representamos en un espacio de dimensión treinta. Vamos a aplicar componentes principales y seleccionar únicamente las dos primeras componentes con lo que habremos transformado nuestro conjunto original a un espacio de dos dimensiones.

Una de las ventajas de la reducción de la dimensionalidad es que permite realizar representaciones gráficas de los datos:

En ese caso la exactitud del método con reducción de la dimensionalidad es del 94,7%. Obtenemos peores resultados que con el conjunto de datos sin reducir.

Por tanto, nuestra selección para la aplicación de K-NN al problema que estamos considerando sería la del conjunto de datos original sin reducir con k=11.

Como hemos visto K-NN es un algoritmo muy sencillo de aplicar y presenta buena robustez frente al ruido. Este algoritmo se caracteriza en no crear un modelo específico para predicción. El aprendizaje se produce cada vez que se clasifica una nueva instancia del conjunto de datos. A este tipo de métodos se les denomina de aprendizaje perezoso (lazy learning methods). La parte negativa es que el coste computacional del algoritmo es elevado y crece con el conjunto de entrenamiento.

Espero que te haya resultado interesante este post sobre K-NN en análisis y minería de datos en salud.

Si tienes un conjunto de datos de pacientes a  los que crees que se pueda aplicar un modelo supervisado y necesitas ayuda no dudes en contactar conmigo.