Scikit Learn - K-Vecinos más cercanos (KNN)
Este capítulo le ayudará a comprender los métodos de vecinos más cercanos en Sklearn.
Los métodos de aprendizaje basados en vecinos son de ambos tipos, a saber supervised y unsupervised. El aprendizaje basado en vecinos supervisados se puede utilizar tanto para problemas de predicción de clasificación como de regresión, pero se utiliza principalmente para problemas de predicción de clasificación en la industria.
Los métodos de aprendizaje basados en vecinos no tienen una fase de formación especializada y utilizan todos los datos para la formación durante la clasificación. Tampoco asume nada sobre los datos subyacentes. Esa es la razón por la que son vagos y no paramétricos por naturaleza.
El principio principal detrás de los métodos del vecino más cercano es:
Para encontrar un número predefinido de muestras de entrenamiento cerca del nuevo punto de datos
Predecir la etiqueta a partir de este número de muestras de entrenamiento.
Aquí, el número de muestras puede ser una constante definida por el usuario como en el aprendizaje de vecino más cercano K o variar en función de la densidad local del punto como en el aprendizaje de vecino basado en el radio.
Módulo sklearn.neighbors
Scikit-learn tiene sklearn.neighborsmódulo que proporciona funcionalidad para métodos de aprendizaje basados en vecinos supervisados y no supervisados. Como entrada, las clases en este módulo pueden manejar matrices NumPy oscipy.sparse matrices.
Tipos de algoritmos
Los diferentes tipos de algoritmos que se pueden utilizar en la implementación de métodos basados en vecinos son los siguientes:
Fuerza bruta
El cálculo de fuerza bruta de las distancias entre todos los pares de puntos del conjunto de datos proporciona la implementación de búsqueda de vecinos más ingenua. Matemáticamente, para N muestras en dimensiones D, el enfoque de fuerza bruta se escala como0[DN2]
Para muestras de datos pequeñas, este algoritmo puede ser muy útil, pero se vuelve inviable a medida que aumenta el número de muestras. La búsqueda de vecinos por fuerza bruta se puede habilitar escribiendo la palabra clavealgorithm=’brute’.
Árbol KD
Una de las estructuras de datos basadas en árboles que se han inventado para abordar las ineficiencias computacionales del enfoque de fuerza bruta es la estructura de datos de árbol KD. Básicamente, el árbol KD es una estructura de árbol binario que se llama árbol K-dimensional. Divide de forma recursiva el espacio de los parámetros a lo largo de los ejes de datos dividiéndolo en regiones ortográficas anidadas en las que se rellenan los puntos de datos.
Ventajas
A continuación se muestran algunas ventajas del algoritmo de árbol KD:
Construction is fast - Como la partición se realiza solo a lo largo de los ejes de datos, la construcción del árbol KD es muy rápida.
Less distance computations- Este algoritmo requiere cálculos de distancia muy menores para determinar el vecino más cercano de un punto de consulta. Sólo toma[ ()] cálculos de distancia.
Desventajas
Fast for only low-dimensional neighbor searches- Es muy rápido para búsquedas de vecinos de baja dimensión (D <20) pero a medida que D crece se vuelve ineficaz. Como la partición se realiza solo a lo largo de los ejes de datos,
Las búsquedas de vecinos del árbol KD se pueden habilitar escribiendo la palabra clave algorithm=’kd_tree’.
Árbol de bolas
Como sabemos que KD Tree es ineficiente en dimensiones más altas, por lo tanto, para abordar esta ineficiencia de KD Tree, se desarrolló la estructura de datos de Ball Tree. Matemáticamente, divide los datos de forma recursiva, en nodos definidos por un centroide C y un radio r, de tal manera que cada punto del nodo se encuentra dentro de la hiperesfera definida por el centroide.C y radio r. Utiliza la desigualdad triangular, que se indica a continuación, que reduce el número de puntos candidatos para una búsqueda de vecinos.
$$ \ arrowvert X + Y \ arrowvert \ leq \ arrowvert X \ arrowvert + \ arrowvert Y \ arrowvert $$Ventajas
A continuación se muestran algunas ventajas del algoritmo Ball Tree:
Efficient on highly structured data - Como el árbol de bolas divide los datos en una serie de hiper-esferas anidadas, es eficiente en datos altamente estructurados.
Out-performs KD-tree - El árbol de bolas supera al árbol KD en grandes dimensiones porque tiene una geometría esférica de los nodos del árbol de bolas.
Desventajas
Costly - La partición de los datos en una serie de hiper-esferas anidadas hace que su construcción sea muy costosa.
Las búsquedas de vecinos del árbol de bolas se pueden habilitar escribiendo la palabra clave algorithm=’ball_tree’.
Elección del algoritmo de vecinos más cercanos
La elección de un algoritmo óptimo para un conjunto de datos determinado depende de los siguientes factores:
Número de muestras (N) y dimensionalidad (D)
Estos son los factores más importantes que se deben considerar al elegir el algoritmo de vecino más cercano. Es por las razones que se dan a continuación:
El tiempo de consulta del algoritmo Brute Force crece a medida que O [DN].
El tiempo de consulta del algoritmo de árbol de bolas crece a medida que O [D log (N)].
El tiempo de consulta del algoritmo del árbol KD cambia con D de una manera extraña que es muy difícil de caracterizar. Cuando D <20, el costo es O [D log (N)] y este algoritmo es muy eficiente. Por otro lado, es ineficiente en el caso de que D> 20 porque el costo aumenta a casi O [DN].
Estructura de datos
Otro factor que afecta el rendimiento de estos algoritmos es la dimensionalidad intrínseca de los datos o la escasez de datos. Esto se debe a que los tiempos de consulta de los algoritmos de árbol de bolas y árbol de KD pueden verse muy influenciados por él. Considerando que, el tiempo de consulta del algoritmo de fuerza bruta no cambia por la estructura de datos. Generalmente, los algoritmos de árbol Ball y árbol KD producen un tiempo de consulta más rápido cuando se implantan en datos más dispersos con una dimensionalidad intrínseca más pequeña.
Número de vecinos (k)
El número de vecinos (k) solicitados para un punto de consulta afecta el tiempo de consulta de los algoritmos de árbol Ball y árbol KD. Su tiempo de consulta se vuelve más lento a medida que aumenta el número de vecinos (k). Mientras que el tiempo de consulta de Fuerza bruta no se verá afectado por el valor de k.
Número de puntos de consulta
Debido a que necesitan una fase de construcción, los algoritmos del árbol KD y del árbol de bolas serán efectivos si hay una gran cantidad de puntos de consulta. Por otro lado, si hay un número menor de puntos de consulta, el algoritmo de fuerza bruta funciona mejor que los algoritmos de árbol KD y árbol de bolas.