¿Qué es el algoritmo k-Nearest Neighbour? ¿Qué tipo de problemas puede resolver este algoritmo? ¿Qué tipo de matemática se requiere?

KNN es básicamente una técnica no paramétrica, lo que significa que no tiene en cuenta las propiedades generales de los datos.

Se utiliza con fines de clasificación, y rara vez también con fines de regresión.

Clasificación:
Clasificamos el nuevo punto de datos como la clase que posee la mayoría de los K puntos de datos más cercanos al nuevo.

Regresión:
El valor del nuevo punto es el valor del promedio de las distancias entre sus K puntos más cercanos. La métrica de distancia debe tomarse en consecuencia. (elección del usuario).

Debes conocer las matrices, el álgebra lineal y todos los necesarios para la ciencia de datos generales.

El vecino más cercano de K tiene muchos usos en la minería de datos y el aprendizaje automático. Un uso particular es la detección de anomalías.

Digamos que tienes un submarino. Y en este submarino, tienes una computadora que registra datos de los sensores de los submarinos cada minuto. Los tres datos que registra son

1. Profundidad (metros desde el nivel del mar)
2. Potencia consumida (vatios)
3. Consumo de combustible (litros / minuto)

Desea poder monitorear su submarino e inmediatamente reconocer si hay algún tipo de anomalía en los datos que está registrando que indique una anomalía en el submarino.

Entonces, primero revisa sus datos visualmente, decidiendo qué días de sus datos previamente grabados es un buen comportamiento del submarino. Usted decide qué conjuntos de datos se muestran cuando su submarino actúa normalmente. Estos son sus datos de entrenamiento y forman una base de conocimiento. Entonces ahora tiene filas sobre filas donde cada fila tiene 3 columnas (profundidad, consumo de energía, consumo de combustible) durante cada minuto en el que ha decidido que el submarino estaba actuando normalmente.

Puede visualizar que podría trazar cada una de las filas como un solo punto en un gráfico 3D, donde el eje x es la profundidad, el eje y es el poder dibujado y el eje z es el consumo de combustible.

Antes de hacer esto, tendría que normalizar los datos. Tendría que hacer esto porque algunos de los datos tendrán valores inherentemente más altos. Si no lo normalizo, las columnas que tienen valores inherentemente más altos tendrán un mayor impacto en mi algoritmo. Lo que quiero decir es esto. Los valores de profundidad de mi submarino pueden variar desde 0 hasta 7000 metros. Por otro lado, los valores para el consumo de combustible en litros por minuto solo pueden variar de 0 a 10 litros por minuto. Esto no significa que mi consumo de combustible importe menos que mi profundidad. Ambos deberían afectar mi análisis por igual. Puede pensar en esto como algo similar a normalizar un vector como 3i + 2j + 5k a un vector de longitud 1. Cuando se normaliza, el valor del nuevo vector es 3 / sqrt (38) * i + 2 / sqrt (38) * j + 5 / sqrt (38) * k.

Después de normalizar sus datos, puede trazar cada fila de sus datos como un único punto en un gráfico 3D donde cada eje corresponde a uno de profundidad, consumo de energía y consumo de combustible.

Ahora puede usar un algoritmo de agrupación para formar una serie de agrupaciones alrededor de los puntos en ese gráfico tridimensional. Debido a que la profundidad de su submarino, el consumo de combustible y el consumo de energía mostrarán patrones, los puntos en el gráfico que corresponden a filas en sus datos, se agruparán en grupos uno al lado del otro.

Este grupo de grupos (u objetos esféricos) son ubicaciones donde los datos son normales ya que seleccionó estos puntos como datos nominales o normales.

Ahora viene la parte vecina k más cercana. Digamos que una vez que haya creado esta base de conocimiento para el algoritmo, desea usarla para analizar los nuevos datos que su computadora obtiene de los tres sensores del submarino cada minuto. A diferencia de su base de conocimiento donde cada punto era un buen comportamiento, estos nuevos datos podrían ser buenos o malos. Si es malo, quiere que su computadora lo encuentre y le diga para que pueda reparar su submarino.

Entonces … Después de normalizar estos datos, traza cada nuevo punto (cada punto está definido por la profundidad (x), el consumo de energía (y) y el consumo de combustible (z)) en el gráfico 3d ya existente. Si el nuevo punto está dentro de uno de los grupos, entonces es un buen comportamiento y su algoritmo no levanta una bandera. Pero … Si el nuevo punto no está dentro de uno de los grupos, calcula la distancia desde el nuevo punto hasta el borde del grupo más cercano. Cuanto más larga es la distancia, más anómalo es el punto.

Así es como se usa prácticamente el vecino más cercano. Este ejemplo es fácil de imaginar porque utilicé 3 datos y es posible que los humanos visualicemos gráficas en 3 dimensiones. K el vecino más cercano se puede usar en detecciones de anomalías en sistemas del mundo real donde puede tener 4,5,6 incluso docenas o cientos de columnas (cientos de dimensiones) para encontrar patrones y anomalías en los datos. Si está monitoreando un avión, puede tener columnas (dimensiones) que corresponden a la velocidad de descenso, inclinación, aceleración, guiñada, balanceo, velocidad del viento, aletas, desviación del timón, altitud, etc.

El vecino K más cercano se puede usar en los aviones para advertir a los pilotos y al tráfico aéreo si algo sale mal en un avión de una manera que el cerebro humano no puede calcular o comprender. Se puede usar en muchos sistemas o monitoreo biológico de la salud para notificar a los técnicos si algo va mal.

Digamos si quisiéramos predecir qué restaurante cercano le gustaría más a una persona que visita una nueva ciudad. Aquí, el algoritmo NN correspondería a pensar en todas las personas locales que conoce que han comido en restaurantes cercanos, decidir cuál de ellos es más similar al visitante que está buscando un lugar para almorzar, y luego recomendar que el visitante vaya a el restaurante favorito de esta persona. Cuando un visitante solicita una recomendación para almorzar, nuevamente piensa en todas las personas que conoce que han comido en los restaurantes cercanos. Pero en lugar de elegir solo una persona que se parezca más al visitante, usted elige K personas que son más parecidas al visitante.

El problema es muy simple: tiene un conjunto de puntos en n dimensiones. Dado un nuevo punto (llamémoslo consulta), necesita encontrar los k puntos más cercanos a la consulta.

KNN se puede utilizar para resolver muchos problemas, en la clasificación, por ejemplo, puede clasificar un nuevo punto simplemente examinando la clase de sus vecinos más cercanos. También puede usar KNN para encontrar los documentos más similares a un documento dado para plagio, encontrar espejos, etc. En los sistemas de recomendación puede usar KNN para encontrar los artículos que son más similares a un artículo que un usuario no ha revisado y luego calcular si al usuario le gustará o no.
Puede usarlo en algoritmos de agrupamiento y hay muchas más aplicaciones.

Para esto, necesita alguna forma de distancia métrica, hay varias opciones, la más común es la distancia euclidiana tradicional, pero puede usar Manhattan, Hamming, Jaccard, Levenshtein, etc.

Una solución ingenua es buscar linealmente todos los puntos originales calculando la distancia al punto de consulta.

En espacios dimensionales bajos, puede usar alguna forma de índice espacial como árboles kd, árboles cuadrangulares o árboles r para encontrar los puntos en el tiempo sublineal. Desafortunadamente, los índices espaciales funcionan incluso peor que un escaneo lineal ingenuo cuando tiene muchas dimensiones. Esto se conoce como “la maldición de la dimensionalidad”

Para combatir la maldición de la dimensionalidad puedes probar una solución aproximada. Esto se conoce como ANN (vecinos cercanos aproximados). Una forma de hacerlo es utilizando LSH (hashing sensible a la localidad) donde crea una función hash que asignará dos puntos que están cerca uno del otro al mismo depósito. Entonces solo hash la consulta y escanea los puntos del cubo para el vecino más cercano.

Hay otras soluciones interesantes para aproximar KNN como el algoritmo de Greedy Walk.

Lo bueno de los vecinos más cercanos es que no necesitas saber mucho. La única noción que necesito al usar / implementar un KNN es la capacidad de evaluar la distancia entre dos objetos (lo que sea que estén representados como puntos, imágenes …)

La implementación en sí no requiere conocimiento de matemática compleja: dado un punto, encuentre los k puntos más cercanos en su conjunto de entrenamiento y devuelva la etiqueta más representada (clasificación) o el valor promedio de las etiquetas (regresión).

Aquí hay una ilustración simple del proceso:

Entonces, si desea escribir mejores implementaciones de KNN, QuadTrees (Quadtree – Wikipedia) puede ser útil. Del mismo modo, tener un conocimiento de los núcleos (como en SVM …) puede ayudarlo a mejorar el rendimiento de sus KNN (ver por ejemplo: Algoritmo de vecino más cercano del núcleo, por KAI YU, LIANG JI * y XUEGONG ZHANG https://pdfs.semanticscholar.org …)

Comprender los núcleos puede ser un poco más difícil y requiere conocimiento en álgebra, álgebra bilineal (y espacios de Hilbert)

Aquí hay una implementación simple del algoritmo (como puede ver, ¡es bastante corto y genérico!)

El algoritmo vecino K-Nearest es un poderoso modelo de clasificación que se puede usar para clasificar los puntos de datos etiquetados para hacer predicciones sobre nuevos datos.

Se puede usar en muchos campos como el médico (clasificación de cáncer, clasificación de enfermedades del corazón), análisis de sitios web de comercio electrónico, etc.

Hice un video tratando de explicar el algoritmo e implementarlo en los datos del cáncer de mama, eche un vistazo …