KNN( k-nearest Neighbors )

Esta basado en un set de datos en M puntos en N dimensiones, podemos usarlo tanto para clasificar como para regresion. Es un algoritmo de Machine Learning simple pero muy importante!.

Datos que podrian Interesarle para comprender mejor:

Dale click a las imagenes para ver su informacion

Grafico KNN ( k-nearest Neighbors )

Grafico KNN ( k-nearest Neighbors )

En este grafico vemos un problema de clasificacion, donde tenemos dos clases, los triangulos y cuadrados, en medio tenemos un puntos incognica( verde) que queremos saber de que clase es, para eso vamos a ver los vecinos mas cercanos a el, con k=1 vemos que seria un triangulo, con k=2 vemos que es un triangulo tambien(encerramos dos vecinos de tipo triangulo), con k=3 vemos que sigue siendo de tipo triangulo, pero con una probabilidad de 2/3, con k=4 vemos que el algoritmo no se decide, por eso, en general se usa un k no par, con k=5 vecinos mas cercanos, vemos que cambia a clase cuadrado, con probabilidad 3/5.

Cuales son los temas a estudiar cuando estamos analizando los algoritmos de machine learning de KNN?

-Como encontrar el valor de k optimo?

-Como escala el algoritmo?Entrenamiento vs Clasificacion

-Que pasa si tenemos muchos puntos?

-Que pasa si tenemos muchas dimensiones?

Ejemplo de KNN regresion en 1-D

Ejemplo de KNN regresion en 1-D
Ejemplo de KNN regresion en 1-D

En este grafico vemos un ejemplo de regresion para el punto del ejex igual a 4 buscamos los vecinos mas cercanos, vemos que a mayor k puntos mas cercanos nuestro valor y varia en valores distintos, entonces para solucionar esto, hacemos el promedio de los puntos.Ejemplo para k=1, el valor x mas cercano es 3, y su y(3)=6, entonces para k=1 el target para x=4 es un 6, para k=2 vecinos mas cercanos, vemos que son x=3, y x=5, para f(5) tenemos un target(etiqueta) de 3, entonces para calcular el valor definitivo de la etiqueta sacamos el promedio que es igual a 6+3/2=4.5, finalmente si tenemos k=3 vecinos mas cercanos vemos que agregamos el punto x=6 y su valor es 2, entonces el target final es 6+3+2/3 es 3.7

KNN su entrenamiento

El entrenamiento de KNN es nulo, es decir si tiempo de entrenamiento es cero, porque su modelo solo necesita los puntos del set de entrenamiento para predecir, por lo que muchos dices que Knn es el algoritmo de Machine Learning que tiene el mas rapido entrenamiento. Ademas es el caso inverso de todos los algoritmos de Machine Learning, donde no tiene tiempo de entrenamiento, pero para predecir tarda mucho.

KNN clasificacion

KNN para clasificar un punto, necesito calcular la distancia de ese punto contra todos los puntos para calcular los k vecinos mas cercanos, esto trae un problema de performance ya que si tenemos millones de puntos, y por cada punto nuevo tenemos que calcular millones de distancias, ordenarlas o elegir los k mas cercanos, y despues elegir los puntos mas cercanos.Es el algoritmo mas lento para hacer la prediccion.Si los puntos a clasificar son muchos entonces lo que nos conviene es hacer algun metodo para evitar eso.

Efecto K

Efecto K de KNN
Efecto K de KNN

Vemos que tenemos en el primer grafico que hay 3 clases, una roja, otra verde, y otra azul. En el segundo grafico, hacemos entrenamos KNN con k=1, osea, buscamos los vecinos mas cercanos, y el algoritmo nos dice en el segundo grafico que para cada punto se genera un vecindario para el cual el algoritmo nos dice si un punto cae ahi, sera de ese color, para la zona roja, el punto verde( que esta mal clasificado) dentro de ella , nos dice que cualquier punto que caiga cerca de su vencindario sera clasificado como tipo verde, cuando en realidad deberia ser rojo porque alrededor de el, tiene gran cantidad de puntos rojos, por lo tanto el algoritmo alucina, es decir, hace un overfitting, es decir cuando k es mas chico tiene a overfittiar. En el tercer grafico vemos que las fronteras estan mas definidas, ya no ocurre lo que pasaba en el grafico 2 donde el punto verde dentro de la franja roja, ya no se clasifica como verde sino como rojo, la particularidad es que knn define fronteras no lineales,es decir fronteras arbitrarias con gran facilidad, cosa que no ocurre con otros algoritmo de machine learning ya que se necesita gran potencia.

Efecto K KNN , los k vecinos mas cercanos
Efecto K KNN , los k vecinos mas cercanos

Vemos que con k=1 overfittea, es decir para este k, los puntos verdes dentro de la zona roja, generan un vecindario que cualquier punto que caiga cerca de ese vecindario verde, se clasifica como verde, cosa que esta realmente mal!!. Con K=15 las fronteras ya estan mejor definidad, no hay overfitting..

Conclusion:

Con k muy chico overfitting, con k muy grando es underfitting, observar que cualquier punto nuevo a clasificar sera de la clase mayoritaria cuando k es igual al todas de datos del dataset, por lo tanto o vemos con alucinacion, o vemos con ceguera, hay que buscar un k intermedio.

Como encontrar el valor de k optimo?

-Hay que elegir una metrica, ejemplo accuracy, y ver que resultados te da con los distintos valores de k.

-Leave 1 out cross-validation ( clasificar cada punto en base a los demas)

-K-fold Validation

MNIST KNN Precision

MNIST KNN Precision
MNIST KNN Precision

Vemos que a mayor k su accuracy tiende a bajar, el algoritmo a mayor k empieza a underfittiar, vemos que el valor optimo de k estaria alrededor de 10, pero observar que oscila mucho el accuracy, por lo tanto hay que probar con muchos valores de k para entontrar el optimo.

Weighted Distanced (Kernels), extension de KNN

Weighted Distanced (Kernels)
Le asignamos un peso de acuerdo a la distancia al punto a clasificar, esto nos permitira usar K=N

Le asignamos un peso de acuerdo a la distancia al punto a clasificar, esto nos permitira usar K=N, ya que ahora podemos elegir todos los puntos, ya que los mas lejanos tendran a ser casi insignificantes por el peso asignado

Tips

-Es necesario encontrar un aproximacion si los puntos son muchos

– Encontrar el k, tambien hay que buscar una distancia, la mas comun es el euclidea, pero aveces hay casos donde otras distancias son las optimas para el problema.

-KNN los atributos( features) deben estar normalizados, de lo contrario algun feature puede dominar todas las distancias, ya que es es muy sensible a valores incorrectos, es decir podemos escalarlo en rango de 0 a 1 , restarle su promedio y por ultimo dividir por su desviacion standar.

-KNN es muy sensible a dimensiones( feature) ruidosa, si se ve que que el feature edad es muy importante en relacion a la altura, entonces cuando predecimos un valor incorrecto como edad igual a 700 nos puede dar un valor erroneo de altura ejemplo 600 metros.

-Eliminar un atributo aunque puede ser una medida muy drastica

-Reducir el peso del atributo

-Cada atributo aporta un peso diferente en el calculo de distancia

Distancias en KNN

Euclideana (l2)

NCD

Mahalanobis

Hamming

Geodésica

Graph Edit 

Earth Mover

BM25

Manhattan (l1)

l0

lInf

Coseno

Jaccard

Levenshteinhart

Teorema de Cover-Hart:

Teorema de Cover-hart

Si el error optimo de cualquier clasificador de un set de datos es E. Entonces cuando los datos son infinitos Knn tiene un error menor a 2E.

Tener cuidado con la consecuencias:

Conclusiones correctas: Cuando knn utiliza mas puntos, knn mejora, es decir a medida que la cantidad de puntos se acerca a infinito su error se acerca al optimo.

Conclusion Incorrecta: Cuando knn tiene muchos datos entonce es optimo, pero esto solo vale para infinitos datos, y la diferencia entre 1 billon e infinito es igual que la diferencia entre 90 e infinito.

KNN: Eliminacion de Outliers

si “m” vecinos mas cercanos de un punto son de otra clase => outlier( anomalia), ese outlier lo podriamos filtrar o eliminar despues.

KNN:Prototipos(Algoritmos de Hart)

Este algoritmo empezamos con un conjunto vacio de prototipos que nos serviran para decidir con que puntos clasificar y cuales no. Esto se hace por cada punto del set de datos(sin outliers), si su vecino prototipo mas cercano es de otra clase, entonces se agrega el punto al conjunto de prototipos, y esto lo repetimos hasta que no se pueda agregar nuevos ṕrototipos. Clasificar unicamente con los prototipos.

KNN: Optimizacion

KD-trees , VP-tress ,Grafos, LSH

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *