Nearest Neighbors

Clasificación y principales características

El algoritmo KNN es:

• De clasificación, principalmente, aunque también se adapta a problemas de regresión: si las etiquetas de los datos de entrenamiento son variables continuas en lugar de variables discretas, la etiqueta asignada a un nuevo punto se calcula en función de la media de las etiquetas de sus k vecinos más cercanos.
• Supervisado: requiere datos de entrenamiento etiquetados.
• De aprendizaje basado en instancias.
• De tipo “perezoso” (lazy): durante el entrenamiento simplemente guarda las instancias, no construye ningún modelo (a diferencia de, por ejemplo, los árboles de decisión).
• No paramétrico: no hace suposiciones sobre la distribución que siguen los datos (a diferencia de, por ejemplo, un modelo lineal).
• Local: asume que la clase de un dato depende solo de los k vecinos más cercanos (no se construye un modelo global).

Objetivo

El objetivo de KNN es encontrar el número (predefinido) de muestras de entrenamiento más cercanas en distancia a un nuevo punto y predecir su etiqueta a partir de ellas.

El algoritmo KNN asume que los puntos que se encuentran próximos unos de otros serán, a su vez, similares entre sí. Por tanto, depende de que esta suposición sea lo suficientemente cierta como para que el algoritmo sea útil. KNN captura la idea de similitud (a veces llamada distancia, proximidad o cercanía) con una base sencilla de matemáticas: calcular la distancia entre puntos en un gráfico. Hay muchas formas de calcular la distancia y alguna en concreto puede ser preferible frente a otras, según el problema que estemos tratando de resolver:

• Distancia euclídea
• Distancia de Manhattan
• Distancia de Minkowski

En general, la distancia euclidiana estándar es la opción más común.

Métricas de distancias

Distancia euclídea

from sklearn.neighbors import DistanceMetric

Ejemplo en 2D

dist = DistanceMetric.get_metric('euclidean')

X = [[1, 2],
    [6, 7]]

dist.pairwise(X)

array([[0.        , 7.07106781],
       [7.07106781, 0.        ]])

Ejemplo en 3D

X = [[4, 2, 3],
    [1, 4, 5]]

dist.pairwise(X)

array([[0.        , 4.12310563],
       [4.12310563, 0.        ]])

Distancia Manhattan

from sklearn.neighbors import DistanceMetric

dist = DistanceMetric.get_metric('manhattan')

X = [[3, 3],
    [10 ,8]]

dist.pairwise(X)

array([[ 0., 12.],
       [12.,  0.]])

Distancia Minkowski

Equivalencia con distancia Manhattan

from sklearn.neighbors import DistanceMetric

dist_manhattan = DistanceMetric.get_metric('minkowski', p=1)

X = [[3, 3],
    [10 ,8]]

# El resultado es idéntico al obtenido utilizando la métrica de la distancia Manhattan
dist_manhattan.pairwise(X)

array([[ 0., 12.],
       [12.,  0.]])

Equivalencia con distancia euclídea

dist_euclidea = DistanceMetric.get_metric('minkowski', p=2)

X = [[1, 2],
    [6, 7]]

# El resultado es idéntico al obtenido utilizando la métrica de la distancia euclídea
dist_euclidea.pairwise(X)

array([[0.        , 7.07106781],
       [7.07106781, 0.        ]])

KNN en Scikit-Learn

El módulo sklearn.neighbors contiene métodos de aprendizaje tanto supervisado como no supervisado:

• El algoritmo KNN no supervisado permite encontrar los vecinos más cercanos a un punto dado. Es la base de muchos otros métodos de aprendizaje, especialmente el aprendizaje múltiple (manifold learning) y la agrupación espectral (spectral clustering) .
• El KNN supervisado permite, no solo encontrar a los vecinos más cercanos a un punto, sino también predecir la etiqueta de dicho punto en base a las etiquetas de sus vecinos. Viene en dos versiones: para problemas de clasificación (datos con etiquetas discretas) y para problemas de regresión (datos con etiquetas continuas).

Vecinos más cercanos sin supervisión

Dentro del módulo sklearn.neighbors, la clase NearestNeighbors es la que implementa el modelo de vecinos más cercanos sin supervisión. Actúa como una interfaz uniforme a tres diferentes algoritmos de vecinos más próximos:

• Un algoritmo de fuerza bruta
• KDTree
• BallTree

Para especificar el uso de uno de estos algoritmos, la clase NearestNeighbors tiene el parámetro algorithm. Además, algunos algoritmos se puede utilizar también de forma independiente, ya que scikit-learn cuenta con clases separadas para ellos.

Algoritmo de fuerza bruta

La implementación de búsqueda de vecinos más simple implica el cálculo por fuerza bruta de las distancias entre todos los pares de puntos en el conjunto de datos. Evidentemente, cuantas más dimensiones haya en el conjunto de datos, menos eficiente es esta técnica, llegando a ser incluso inviable.

Este algoritmo se especifica utilizando el parámetro algorithm = ‘brute’.

Algoritmo KDTree

Para abordar los problemas de coste computacional del enfoque de fuerza bruta, se han inventado una variedad de estructuras de datos basadas en árboles. En general, estas estructuras intentan reducir el número requerido de cálculos de distancia. La idea básica detrás es que si el punto A está muy lejos del punto B, y el punto B está muy cerca del punto C, entonces sabemos que A y C son muy distantes el uno del otro, sin tener que calcular explícitamente su distancia. De esta manera, el coste computacional de una búsqueda de vecinos más cercanos se puede reducir.

Un enfoque en esta línea es el de la estructura de datos del árbol KD (abreviatura de árbol K-dimensional), que generaliza árboles a un número arbitrario de dimensiones. El árbol KD es una estructura de árbol binario que divide de forma recursiva el espacio de parámetros a lo largo de los ejes de datos. Aunque es muy eficaz en bajas dimensiones, también se vuelve ineficaz a medida que crece el número de dimensiones, debido a la “maldición de la dimensionalidad”.

En scikit-learn, este algoritmo se especifica mediante el parámetro algorithm = ‘kd_tree’.

Algoritmo BallTree

Para abordar las ineficiencias de los árboles KD en dimensiones más altas, se desarrolló el algoritmo BallTree. Donde los árboles KD dividen los datos a lo largo de ejes cartesianos, los árboles de bolas dividen los datos en una serie de hiper-esferas anidadas. Esto hace que la construcción del árbol sea más costosa que la del árbol KD, pero da como resultado una estructura de datos que puede ser muy eficiente en datos altamente estructurados, incluso en dimensiones muy altas.

En scikit-learn, las búsquedas de vecinos basadas en árboles de bolas se especifican mediante el parámetro algorithm = ‘ball_tree’.

Vecinos más cercanos con supervisión

Estas técnicas permiten encontrar los vecinos más cercanos a un punto dado y, en base a las etiquetas de dichos vecinos, predecir la etiqueta del punto. Por tanto:

• Si las etiquetas son discretas, el problema es de clasificación.
• Si las etiquetas son continuas, el problema es de regresión.

Problemas de clasificación

En los modelos de vecinos más cercanos, el número de muestras utilizadas para hacer las predicciones puede ser una constante definida por el usuario (k, que hace referencia al número de vecinos más cercanos) o variar según la densidad local de puntos (búsqueda de vecinos basada en el radio r). Así, dentro del módulo sklearn.neighbors, Scikit-learn implementa dos clasificadores de vecinos más cercanos diferentes:

• La clase KNeighborsClassifier implementa el aprendizaje basado en los k vecinos más cercanos. Es la técnica más utilizada. Nota importante: si dos vecinos k+1 y k tienen distancias idénticas pero etiquetas diferentes, el resultado dependerá del orden de los datos de entrenamiento.
• La clase RadiusNeighborsClassifier implementa el aprendizaje basado en el número de vecinos dentro de un radio fijo. Este método es más apropiado en los casos en los que los datos no se muestrean de manera uniforme. El usuario especifica un radio fijo, de modo que los puntos en vecindarios más dispersos usan menos vecinos más cercanos para la clasificación. Para espacios de parámetros de alta dimensión, este método se vuelve menos efectivo debido a la llamada “maldición de la dimensionalidad”.

En ambos casos, la etiqueta de clasificación se calcula a partir de un voto de mayoría simple de los vecinos más cercanos de cada punto: a un punto nuevo se le asigna la clase de datos que tiene más representantes dentro de los vecinos más cercanos del punto. Sin embargo, en algunas circunstancias puede ser mejor ponderar a los vecinos de modo que los vecinos más cercanos contribuyan más al ajuste. Esto se puede ajustar mediante el parámetro “weights”:

• El valor predeterminado weights = ‘uniform’ asigna pesos uniformes a cada vecino.
• El valor weights = ‘distance’ asigna pesos proporcionales a la inversa de la distancia desde el punto de consulta.

Alternativamente, se puede proporcionar una función definida por el usuario de la distancia para calcular los pesos.

Problemas de regresión

La regresión basada en vecinos se puede utilizar en los casos en que las etiquetas de datos son variables continuas en lugar de discretas. La etiqueta asignada a un punto de consulta se calcula en función de la media de las etiquetas de sus vecinos más cercanos.

Igual que en el caso de clasificación, el número de muestras utilizadas para hacer las predicciones puede venir dado por k o por r. Así, dentro del módulo sklearn.neighbors, Scikit-learn implementa dos regresores de vecinos más cercanos diferentes:

• La clase KNeighborsRegressor implementa el aprendizaje basado en los k vecinos más cercanos.
• La clase RadiusNeighborsRegressor implementa el aprendizaje basado en el número de vecinos dentro de un radio fijo.

La regresión básica de vecinos más cercanos utiliza ponderaciones uniformes: es decir, cada punto de la vecindad local contribuye de manera uniforme a la predicción de un punto de consulta. En algunas circunstancias, puede ser útil ponderar las muestras de manera que los puntos cercanos contribuyan más a la regresión que los puntos lejanos. Esto se puede ajustar mediante el parámetro “weights”:

• El valor predeterminado weights = ‘uniform’ asigna pesos iguales a cada vecino.
• El valor weights = ‘distance’ asigna pesos proporcionales a la inversa de la distancia desde el punto de consulta.

Alternativamente, se puede proporcionar una función definida por el usuario de la distancia para calcular los pesos.

Hiperparámetros

Modelo basados en k vecinos más cercanos

Para analizar los parámetros más importantes, veamos la sintaxis de las clases que nos interesan:

class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, *, weights=‘uniform’, algorithm=‘auto’, leaf_size=30, p=2, metric=‘minkowski’, metric_params=None, n_jobs=None, **kwargs)

class sklearn.neighbors.KNeighborsRegressor(n_neighbors=5, *, weights=‘uniform’, algorithm=‘auto’, leaf_size=30, p=2, metric=‘minkowski’, metric_params=None, n_jobs=None, **kwargs)

Hiperparámetro n_neighbors

Es el parámetro que se utiliza en los algoritmos que buscan los k vecinos más cercanos. La elección óptima del valor de n_neighbors depende en gran medida de los datos: en general, un mayor valor suprime los efectos del ruido, pero hace que los límites de clasificación sean menos distintos.

• Si k=1, las instancias que son ruido (es decir, aquellas que provocan solape entre clases) ejercen una gran influencia.
• Si k>1, se tienen en cuenta más vecinos y las instancias ruidosas pierden influencia.
• Si k es muy grande, se pierde la idea principal de localidad del algoritmo.

En general:

• Cuanto menor es k, mayor es la varianza (se consigue una menor estabilidad).
• Cuanto mayor es k, mayor es el bias (se consigue una menor precisión).

Hiperparámetro weights

Es la función de peso utilizada en la predicción. Puede ser una de las siguientes opciones:

{‘uniform’, ‘distance’} o callable

Por defecto es ‘uniform’.

• ‘uniforme’: pesos uniformes. Todos los puntos de cada vecindario se ponderan por igual.
• ‘distance’: pesos en base a la inversa de la distancia. En este caso, se pondera de tal forma que los vecinos más cercanos de un punto dado tendrán una mayor influencia que los vecinos más alejados.
• callable (invocable): una función definida por el usuario que acepta una matriz de distancias y devuelve una matriz de la misma forma que contiene los pesos.

Hiperparámetro algorithm

Es el algoritmo utilizado para calcular los vecinos más cercanos. Puede ser una de las siguientes opciones:

{‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}

Por defecto es ’auto’.

• ‘ball_tree’ usará BallTree.
• ‘kd_tree’ usará KDTree.
• ‘brute’ utilizará una búsqueda de fuerza bruta.
• ‘auto’ intentará decidir el algoritmo más apropiado según los valores pasados método fit del modelo.

Nota: si se detecta que los datos son disperos (sparse), se anulará la configuración de este parámetro, utilizando por defecto la fuerza bruta.

Hiperparámetro leaf_size

El tamaño de la hoja que se le pasa a los algoritmos BallTree o KDTree. Según el valor que se le dé, se puede ver afectada la velocidad de construcción y consulta, así como la memoria requerida para almacenar el árbol. El valor óptimo depende de la naturaleza del problema.

Debe ser un número entero y por defecto se fija en 30.

Hiperparámetro p

Es el parámetro de potencia para la métrica de Minkowski.

Debe ser un número entero, que por defecto se fija en 2.

• Cuando p = 1, equivale a usar manhattan_distance (l1).
• Cuando p = 2, equivale a usar euclidean_distance (l2).
• Para p arbitrario, se usa minkowski_distance (l_p).

Hiperparámetro metric

Es la métrica de distancia que se utilizará.

Debe ser un string o un callable (invocable), y por defecto se fija en ‘minkowski’.

Con p = 2 es equivalente a la métrica euclidiana estándar. En la documentación de DistanceMetric de Scikit-Learn hay una lista de métricas disponibles.

https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.DistanceMetric.html#sklearn.neighbors.DistanceMetric

Hiperparámetro metric_params

A través de este parámetro se pueden pasar parámetros adicionales que necesite la función métrica.

Debe ser un objeto de tipo diccionario, por defecto está fijo en “Ninguno”.

Modelo basados en un radio de vecinos más cercanos

Para analizar los parámetros más importantes, veamos la sintaxis de las clases que nos interesan:

class sklearn.neighbors.RadiusNeighborsClassifier(radius=1.0, *, weights=‘uniform’, algorithm=‘auto’, leaf_size=30, p=2, metric=‘minkowski’, outlier_label=None, metric_params=None, n_jobs=None, **kwargs)

class sklearn.neighbors.RadiusNeighborsRegressor(radius=1.0, *, weights=‘uniform’, algorithm=‘auto’, leaf_size=30, p=2, metric=‘minkowski’, metric_params=None, n_jobs=None, **kwargs)

Hiperparámetro radius

Es el parámetro que se utiliza en los algoritmos que buscan los vecinos más cercanos dentro de un radio especificado por el usuario.

Debe ser un número en coma flotante, y el valor predeterminado es 1.0.

En este caso, los puntos en vecindarios más dispersos usan menos vecinos para la clasificación. Para espacios de parámetros de alta dimensión, este método se vuelve menos efectivo debido a la llamada “maldición de la dimensionalidad”.

Hiperparámetro outlier_label

Es la etiqueta que se desea dar a las muestras atípicas (muestras sin vecinos en un radio determinado). Se puede especificar mediante una de las siguientes opciones:

Debe ser una de las siguientes opciones:

{manual label, ‘most_frequent’}, default=None

El valor predeterminado es None.

• Manual label (etiqueta manual): debe ser un string o un número entero (del mismo tipo que sea y), o bien una lista de etiquetas manuales si se utiliza salida múltiple.
• ‘most_frequent’: asigna la etiqueta más frecuente de y a los valores atípicos.
• None (ninguno): cuando se detecta algún valor atípico, se generará ValueError.

Resto de hiperparámetros

Son iguales que los de los modelos basados en k vecinos más cercanos.