Ir al contenido principal

Clasificación con k-nearest neighbors


En un artículo anterior hablamos de NumPy y me hubiera gustado completarlo con algún ejemplo concreto. Así que voy a aprovechar este artículo para presentaros un algoritmo muy usado en machine learning y de camino a ilustrarlo con código Python (y la librería NumPy).
El algoritmo k-nearest neighbors (abreviado como k-nn) o en español, k vecinos más cercanos, es un algoritmo conceptualmente sencillo y también fácil de implementar, pero que para ciertas tareas puede tener una eficacia más que razonable. En lo que sigue os voy a contar cómo funciona y lo vamos a implementar en Python. En un siguiente artículo, aplicaremos el algoritmo a un problema del mundo real.
K-nn pertenece a la familia de algoritmos de clasificación supervisada, es decir, que necesitan la intervención humana para realizar su aprendizaje. Esta familia de algoritmos son capaces de clasificar elementos dentro de una serie de categorías prefijadas. De forma genérica, esta tarea se llama entrenamiento, y consiste en ofrecer al sistema ejemplos de cada una de las categorías posibles (a este conjunto de datos se le suele llamar dataset o conjunto de entrenamiento). Cuando se ingresan nuevos elementos al sistema éste lo asignará una de las categorías basándose en lo "aprendido" durante el entrenamiento. El proceso de asignar una categoría se llama etiquetado. Hay multitud de algoritmos de clasificación siendo K-nn uno de los más sencillos, por lo que es ideal para empezar a dar los primeros pasos en el aprendizaje automático.
Cuando entrenamos un clasificador hay que elegir en qué características del conjunto de entrenamiento ha de fijarse a la hora de clasificarlos. Por ejemplo, si un banco quiere crear un sistema que ayude a decidir si se aprueba la solicitud de préstamo de un cliente, un par de datos interesantes es el sueldo y las deudas que tenga el cliente (en realidad habría que considerar más, pero vamos a simplificar). En machine learning las características que vamos a usar para entrenar al sistema se llaman atributos (features en inglés). Como tenemos dos atributos vamos a trabajar con datos de dimensión dos. Esto quiere decir que, por cada ejemplo introducido durante el entrenamiento (obtenidos de antiguos clientes), informaremos de los dos atributos (sueldo y deuda) además de a la clase a la que pertenece, que en este caso podríamos etiquetar como "Pagó" o "No pagó" para indicar si ese cliente en concreto pagó el préstamo o por el contrario tuvo problemas para hacerlo.
Dado que sólo tenemos dos atributos (sueldo y deuda) podríamos representar fácilmente en una gráfica. Si el eje de ordenadas representa el sueldo y el de las abscisas representa la deuda, podemos dibujar un punto por cada cliente. Siendo el punto de un color diferente dependiendo de la clase a la que pertenece. En la siguiente figura hemos representado con puntos azules los clientes que pagaron y de rojo los que no (los valores de los ejes están en miles de euros). La pregunta es ¿debemos conceder el préstamo al nuevo cliente representado por el punto verde?


He separado visualmente las dos clases para que quede más claro. Como no siempre será obvio cómo se debe etiquetar el nuevo dato, necesitamos un algoritmo que nos diga si el punto verde debe ser categorizado en una clase o en la otra. El algoritmo es muy sencillo:

  1. k = número de vecinos a tener en cuenta
  2. Calculamos la distancia entre el nuevo punto y todos los del conjunto de entrenamiento
  3. Nos quedamos con los k vecinos más cercanos y etiquetamos el nuevo punto según la clase a la que pertenezcan la mayoría de sus k vecinos

La idea es que el nuevo punto pertenecerá a la misma clase que la de sus vecinos más cercanos, así que la primera decisión a tomar es ¿cuántos vecinos son suficientes vecinos? No hay una respuesta fácil y tampoco quiero entrar en mucho detalle aquí para no confundirte demasiado. La respuesta corta es: prueba con distintos valores para ver cuál funciona mejor con tu conjunto de datos. la respuesta larga la dejamos para otro día. Si observas la siguiente figura, la etiqueta que le corresponde al nuevo punto no es la misma si usamos tres vecinos que si usamos cinco.


Otra concepto que no he definido es el de la distancia entre puntos. Hay varias medidas de distancia, cada una con sus propiedades, sus ventajas y desventajas. Tampoco quiero entrar ahora a explicar cuál es más conveniente para cada aplicación, así que nos quedamos con una que seguramente te suena de tus días de instituto: la distancia euclidiana.


Te refresco la memoria. La distancia entre dos puntos P y Q en un plano (si Pitágoras no andaba muy desencaminado) se obtiene con la siguiente ecuación.
\[d_E(P,Q)=\sqrt{(p_1-q_1)^2 + (p_2-q_2)^2}\]
Si te estás preguntando qué ocurre si nuestros atributos tienen una dimensionalidad mayor de dos, tranquilo. Lo bueno del Álgebra es que funciona bien en dos dimensiones, en tres, en cuatro o en las que haga falta, así que podemos generalizar la ecuación para cualquier cantidad de atributos.
\[d_E(P,Q)=\sqrt{\sum_{i=1}^n (p_i-q_i)^2}\]
Lo bueno de esta ecuación es que usando cálculo matricial un ordenador puede resolverla en un plis plas. Y aquí es donde NumPy nos va a mostrar su verdadero poder (bueno, con dos atributos no lo vamos a notar mucho, pero cuando sean miles será de agradecer).
Hechas las presentaciones, vamos al lío. He implementado el algoritmo en un notebook para Jupyter que os he dejado en el siguiente enlace: https://github.com/albgarse/InteligenciaArtificial/blob/master/Machine%20Learning/KNN.ipynb

Empezamos importando las bibliotecas que vamos a necesitar.
import numpy as np
import random
from IPython.display import display
import matplotlib.pyplot as plt
Vamos a utilizar NumPy para las operaciones con matrices y Matplotlib para generar algunas gráficas. Para mostrar las gráficas en el notebook Jupyter se importa también la función display.
n = 50 # 50 muestras aleatorias
# generamos dos centros para las dos clases de puntos para entrenamiento 
c1 = [random.randint(0,1000), random.randint(0,1000)]
c2 = [random.randint(0,1000), random.randint(0,1000)]
# generamos las muestras aleatorias alrededor de los centros
tuplasC1 = []
tuplasC2 = []
labelsC1 = []
labelsC2 = []
for i in range(int(n/2)):
    tuplasC1.append([c1[0] + random.randint(-100,100), c1[1] + random.randint(-100,100)])
    labelsC1.append(0)
    tuplasC2.append([c2[0] + random.randint(-100,100), c2[1] + random.randint(-100,100)])
    labelsC2.append(1)

labels = labelsC1 + labelsC2
puntos = np.matrix(tuplasC1 + tuplasC2)
# dibujamos los puntos
plt.scatter([puntos[:int(n/2),0]], [puntos[:int(n/2),1]], c="b")
plt.scatter([puntos[int(n/2):,0]], [puntos[int(n/2):,1]], c="g")
display(plt)
En machine learning tan importante como el algoritmo que hayamos decidido usar son los datos con los que lo vamos a alimentar. En este caso vamos a fabricarlos de forma aleatoria. El código anterior genera cincuenta muestras (o puntos o ejemplos, como prefieras) pero he hecho un poco de trampa. Los he creado alrededor de dos puntos distantes para que visualmente queden bien diferenciados. Para mantener la generalidad en todo momento he etiquetado con el valor 0 los puntos pertenecientes a la primera clase y con 1 los de la segunda. Una vez tenemos los datos los ponemos en una matriz de NumPy para poder operar con ellos. Finalmente mostramos la gráfica con los puntos, en azul los de la clase 0 y en verde los de la clase 1. Este es el resultado.


También necesitamos datos nuevos, es decir, aquellos que queremos clasificar.
# generamos puntos aleatorios nuevos para clasificarlos
n_test = 10
tuplas = []
for i in range(n_test):
    tuplas.append([random.randint(0,1000), random.randint(0,1000)])
    
puntos_test = np.matrix(tuplas)
# dibujamos los nuevos puntos junto con los anteriores
plt.scatter([puntos[:int(n/2),0]], [puntos[:int(n/2),1]], c="b")
plt.scatter([puntos[int(n/2):,0]], [puntos[int(n/2):,1]], c="g")
plt.scatter([puntos_test[:,0]], [puntos_test[:,1]], c='r', marker='x')
display(plt)
Generamos diez puntos nuevos de forma totalmente aleatoria y mostramos la gráfica para ver por donde han caído (se muestran como X de color rojo).


Ha llegado el momento de la verdad, veamos cómo se comporta k-nn con nuestros datos.
# usamos KNN para clasificar los nuevos puntos
k = 5 # número de vecinos

pred_label = []
# clasificamos cada uno de los puntos nuevos
for i in range(puntos_test.shape[0]):
    distances = []
    # por cada punto calculamos la distancia con los puntos de entrenamiento 
    for j in range(puntos.shape[0]):
        dist = np.sqrt(np.sum(np.square(puntos[j] - puntos_test[i])))
        distances.append((dist, labels[j])) # guardamos las etiquetas y la distancia

    # ordenamos por distancia y nos quedamos con los k vecinos más cercanos
    distances.sort(key=lambda x: x[0])
    neighbors = distances[:k]
    # contamos los votos para ver qué etiqueta gana
    votes = [0,0]
    for neighbor in neighbors:
        votes[neighbor[1]] = votes[neighbor[1]] + 1
    # obtenemos la etiqueta ganadora
    pred_label.append(votes.index(max(votes)))
He preferido hacer una implementación lo más clara posible en detrimento de la eficiencia, ya que con NumPy se puede realizar toda la operación en un sólo paso sin necesidad de usar los dos bucles que he usado en el código, pero creo que así es mucho más intuitivo. Pues bien, el primer bucle i va recorriendo la matriz de los puntos a etiquetar (recuerda que eran 10) y en el bucle interno j los comparamos con cada uno de los ejemplos o puntos del dataset de entrenamiento (recuerda que eran 50). Como ves no hay mucho misterio: calculamos la distancia entre ambos puntos operando matricialmente con NumPy y almacenamos dicha distancia junto a la clase (etiqueta) a la que pertenece el punto con el que estamos comparando. Una vez hemos medido todas las distancias las ordenamos y nos quedamos con las k menores (en este caso k=5). Ahora necesitamos saber a qué clases pertenecen los k vecinos más cercanos. Como hemos almacenado su etiqueta junto con la distancia, sometemos la decisión a un proceso de votación. Cada uno de los k vecinos vota con su etiqueta y la ganadora se asigna al nuevo punto.
# separar los datos clasificados para dibujarlos
g0 = []
g1 = []
for i in range(len(pred_label)):
    if pred_label[i] == 0:
        g0.append([puntos_test[i,0], puntos_test[i,1]])
    else:
        g1.append([puntos_test[i,0], puntos_test[i,1]])
        
grupo0 = np.matrix(g0)
grupo1 = np.matrix(g1)

# mostrar datos ya clasificados
plt.scatter([puntos[:int(n/2),0]], [puntos[:int(n/2),1]], c="b")
plt.scatter([puntos[int(n/2):,0]], [puntos[int(n/2):,1]], c="g")
plt.scatter([grupo0[:,0]], [grupo0[:,1]], c='b', marker='x')
plt.scatter([grupo1[:,0]], [grupo1[:,1]], c='g', marker='x')
display(plt) 
Ahora que hemos clasificados los nuevos puntos los metemos en una matriz simplemente para representarlos en una gráfica, junto con el color definitivo que le corresponde según han sido clasificados por k-nn. De esta forma comprobamos visualmente si la clasificación ha ido según lo esperado.


Para ser un algoritmo que conceptualmente no es nada complejo parece que realiza un buen trabajo. Aunque claro, nuestro ejemplo no es muy impresionante ¿verdad? te preguntarás si todo esto que te he contado sirve realmente para algo útil. Una de las aplicaciones más interesantes de este algoritmo son los sistemas de recomendación. Eso que hace Netflix cuando te recomienda una película según tu historial de visionado o Amazon cuando te recomienda productos en base a tus compras anteriores. Pero también tiene otras utilidades, algunas de ellas bastante más espectaculares que la que acabamos de ver, pero te dejo con la intriga hasta el próximo artículo en el que espero impresionarte un poco más usando a nuestro nuevo amigo k-nn.

Comentarios

Entradas populares de este blog

Criptografía en Python con PyCrypto

A la hora de cifrar información con Python, tenemos algunas opciones, pero una de las más fiables es la librería criptográfica PyCrypto, que soporta funciones para cifrado por bloques, cifrado por flujo y cálculo de hash. Además incorpora sus propios generadores de números aleatorios. Seguidamente os presento algunas de sus características y también como se usa.


Explotando vulnerabilidades: buffer overflow y shellcode

El anterior post lo dediqué a hablaros del funcionamiento de la pila en las llamadas a funciones con la intención de seguir profundizando hoy en los posibles problemas que pueden surgir de una programación poco cuidadosa. La mayoría de los problemas de seguridad que surgen a diario tienen su raíz en una vulnerabilidad del código ejecutable de un programa. Hoy voy a hablar de desbordamiento de buffers o buffer overflow y shellcodes.

Desbordamiento de enteros (Integer Overflow)

Ya os he hablado en este blog de posibles problemas potenciales que se pueden dar en los programas y que son susceptibles de ser explotados para hacer que dichos programas se comporten de forma diferente a la que deberían. Uno de estos problemas es el del desbordamiento de la pila. Sin embargo, hay otros posibles errores de programación que, aunque menos obvios, son igual de peligrosos. Uno de ellos es el desbordamiento de enteros o integer overflow. Para entender cómo funciona os presento un ejemplo muy sencillo pero didáctico.