El algoritmo kNN (k-nearest neighbors) es un algoritmo simple de ML supervisado que puede ser usado tanto para clasificación como para regresión.

El algoritmo predice los valores en función de los elementos más cercanos. El valor predicho será la clase con mayor frecuencia de las instancias cercanas (en caso de clasificación) o un valor calculado a partir de dichas instancias en el caso de regresión (media o media ponderada).

Por ejemplo, supongamos que tenemos un conjunto de datos con una característica y una variable objetivo. Esta variable objetivo tendrá sólo dos posibles valores, con lo que estamos ante un problema de clasificación.

Supongamos que la distribución de los datos es como la siguiente imagen:

Si queremos predecir una instancia nueva (punto verde), nos fijaremos en los datos que están más cerca de ella:

Una cuestión sería elegir el número (K) de muestras cercanas en las que nos deberíamos fijar. Si elegimos k = 1, el modelo asignará a la nueva muestra la clase B. Si asignamos k = 3, el modelo asignará la clase A.

Otra cuestión es elegir una medida de distancia entre las instancias. Existen varias, entre las que destacan:

• Distancia Euclídea: La distancia Euclídea se basa en el teorema de Pitágoras, según el cual, la hipotenusa al cuadrado es igual a la suma de catetos al cuadrado.
  
  
• Distancia de Manhattan: La distancia de Manhattan no mide la distancia en línea recta, sino que considera la distancia como la suma de los catetos.
  
  
• Distancia Minkowski: Es un tipo de distancia que generaliza las distancias Euclídea y de Manhattan. Básicamente, la distancia Minkowski es una distancia que requiere de un parámetro p.

La fórmula de la distancia de Minkowski es la siguiente:

$\displaystyle Minkowski = (\sum_{i=1}^{n}|{x_{i} - y_{i}}|^p)^\frac{1}{p} $

Cuando p=2 obtenemos la distancia Euclídea y si p=1 obtenemos la distancia Manhattan. De todos modos, aunque los valores más típicos de la distancia Minkowski suelen ser 1 y 2, también se le podría asignar otros valores.

Vamos a programar un algoritmo kNN que use la distancia Euclídea.

import pandas as pd
import numpy as np
from scipy import stats

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

from sklearn.metrics import confusion_matrix

# Configuración warnings
# ==============================================================================
import warnings
warnings.filterwarnings('ignore')

Creamos una función que calcule la distancia Euclídea entre dos puntos:

def euclidean_distance(a, b):
    return np.sqrt(np.sum((a - b)**2))

Creamos la función que encontrará los k vecinos más cercanos:

def nearest_neighbors(a, X_train, y_train, k):
    distances = X_train.apply(lambda x: euclidean_distance(a, x), axis = 1).sort_values()
    indexes = distances[0:k].index
    results = y_train[indexes]
    result = stats.mode(results, axis=None)
    #stats.mode devuelve un array con dos elementos. El primero es un array con los valores de la moda (puede ser más de uno) y el segundo el número de elementos
    return result[0][0]

El algoritmo anterior es sencillo. Primero calculamos la distancia del punto pasado (a) con el resto de instancias del conjunto de datos. Ordenamos los valores de menor a mayor y nos quedamos con los k primeros. Por último, devolvemos la moda (el valor más repetido) de esos mismos índices de los valores que contienen nuestras variables objetivos.

Vamos a probar el algoritmo con el conjunto de datos iris.

iris = load_iris()

df = pd.DataFrame(data = iris.data, columns = iris.feature_names)
df['target'] = iris.target

X = df.drop(columns = ['target'], axis = 1)
y = df['target']

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)

Elegimos la última instancia para hacer una prueba:

a = X_test.iloc[-1]
y_real = y_test.iloc[-1]

y_predict = nearest_neighbors(a, X_train, y_train, 51)

print("Predicción:", y_predict)
print("Real:", y_real)

Predicción: 1  Real: 1

En este caso, nuestro modelo acierta la clase.

Vamos a sacar la matriz de confusión para ver como funciona nuestro algoritmo:

def predict(X_test, X_train, y_train, k):
    return X_test.apply(lambda x: nearest_neighbors(x, X_train, y_train, k), axis = 1)
    
y_test_predict = predict(X_test, X_train, y_train, 5)

confusion_matrix(y_test, y_test_predict)

array([[14,  0,  0],
       [ 0, 16,  0],
       [ 0,  1, 14]])

El algoritmo funciona correctamente, además da bastante buen resultado (kNN funciona especialmente bien con el conjunto de datos iris).

Como hemos dicho antes, kNN también se puede usar para problemas de regresión. La diferencia con el modelo anterior es que, en este caso, no devolvemos el valor de clase más repetido (la moda), si no la media (también podría ser la media ponderada) de los valores reales de los k vecinos más cercanos. Para probarlo, vamos a utilizar el dataset heights, donde tenemos la altura de hijos y de padres. El objetivo es predecir la altura de los hijos en función de la altura de sus padres:

df = pd.read_csv('heights.csv')

X = df.drop(columns = ['Son'], axis = 1)
y = df['Son']

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)

Modificamos nuestro algoritmo para devolver la media:

# En este caso hacemos la predicción en base a la media
def nearest_neighbors_regression(a, X_train, y_train, k, distance = 0, p = None):
    distances = X_train.apply(lambda x: euclidean_distance(a, x), axis = 1).sort_values()
    indexes = distances[0:k].index
    results = y_train[indexes]
    result = np.mean(results, axis=None)
    #stats.mode devuelve un array con dos elementos. El primero es un array con los valores de la moda (puede ser más de uno) y el segundo el número de elementos
    return result

Probamos el algoritmo con el último valor del conjunto de test:

a = X_test.iloc[-1]
y_real = y_test.iloc[-1]

y_predict = nearest_neighbors_regression(a, X_train, y_train, 5)
print("Predicción:", y_predict)
print("Real:", y_real)

Predicción: 171.1452
Real: 179.832

Sklearn tiene dos modelos basados en kNN para problemas de clasificación y regresión: KNeighborsClassifier y KNeighborsRegressor. Veamos como utilizar este último sobre el dataset heights:

from sklearn.neighbors import KNeighborsRegressor

model_knn = KNeighborsRegressor(n_neighbors=5, weights='uniform')

model_knn.fit(X_train, y_train)

y_predict = model_knn.predict([a])
print("Predicción:", y_predict)
print("Real:", y_real)

Predicción: [173.2788]
Real: 179.832

Una de las preguntas más importantes sobre el algoritmo kNN es cuántos vecinos deberíamos revisar. Como norma general, existen dos problemas principales a la hora de elegir la k:

• Si la k es demasiado baja, el algoritmo utilizará muy pocos vecinos, lo que tenderá al overfitting.
• Si la k es demasiado alta, la predicción tenderá cada vez más a parecerse a la media, por lo que tendrás un problema de underfitting.

Como norma general, la k se suele elegir mediante la siguiente fórmula:

$\displaystyle k = \sqrt{n}$

Aunque esta regla sea bastante sencilla y rápida, otra forma de elegir el número de k es iterando el modelo con diferentes ks. De esta forma, nos podemos asegurar que la k que elegimos es la que maximiza los resultados (al menos para ese dataset). Sin embargo, lo malo de obtener el número de k de esta forma es que es computacionalmente muy costoso, lo que hace que pierda uno de los valores del algoritmo kNN.

• Modifica el algoritmo kNN para que utilice la distancia Manhattan en lugar de la Euclídea.
  
  
• Modifica de nuevo la función para utilizar la distancia Minkowski a la hora de seleccionar los k vecinos más cercanos. A esta función se le deberá pasar la p para hacer el cálculo de las distancias. Prueba con varios valores de p.
  
  
• Modifica la función de clasificación para que, en caso de empate, incremente el valor de k en 1 hasta que se desempate.
  
  
• Usa KNeighborsClassifier de Sklearn para comprobar su funcionamiento con el conjunto de datos iris.