Clasificación K-nearest neighbors

Hola

La solución que aplicaría en caso de tener un K par y que mi punto tuviera igual cantidad de vecinos de un grupo y otro, sería buscar la distancia menor entre algún punto de estos dos grupos y mi punto, para desempatar

Ejemplo aplicado (K-nearest neighbor y distancia euclidiana)

Articulo: https://www.linkedin.com/pulse/cómo-predecir-el-valor-de-un-inmueble-con-big-data-y-puentes-núñez?articleId=6434535948884721664#comments-6434535948884721664&trk=public_profile_article_view

Si tuviera una K par, pondria como excepción que de tener vecinos X e Y iguales, buscara otro vecino mas cercano.

Hola, hice un código en cuál clarifiqué 6 productos por su calidad y precio, el usuario puede ingresar un nuevo producto y algoritmo responderá si es “costoso” o “calidoso” de acuerdo a los datos que ya tenía. Finalmente serán graficados los puntos en Bokeh. (Re-alimentación bienvenida!)

import math
from bokeh.io import output_notebook, show
from bokeh.plotting import figure

def welcome():
    print('Welcome to the K-Nearest neighbors code implementation')
    print(f'{"+"*54}')
    
    calidad = int(input("Ingrese la calidad del producto en una escala de 1 a 10: "))
    precio = int(input("Ingrese el precio del producto en una escala de 1 a 10: "))
    k = int(input('Ingrese el número de vecinos que desea comparar (Impar menor de 6): '))

    print(f'El precio ingresado:{precio} con calidad:{calidad}')

    return calidad, precio, k

def graficar(DATOS,calidad,precio):
    x_values = []
    y_values = []

    p = figure(title='Relacion precio calidad', x_axis_label='Calidad', y_axis_label='Precio')

    for key in DATOS:
        x_values.append(key[0])
        y_values.append(key[1])

    p.circle(x_values, y_values, size=15, line_color="navy", fill_color="red", fill_alpha=0.5,legend_label="Datos Clasificados",)
    p.circle(calidad, precio, size=15, line_color="navy", fill_color="blue", fill_alpha=0.5,legend_label="Dato usuario",)

    show(p)

def vecinos(DATOS,distancias,k,keys):

    indices_vecino_mas_cercanos = []
    contador_costoso = 0
    contador_calidad = 0

    #Ordena la lista para conocer las distancias cortas
    distancias_ordenadas = list(sorted(distancias))

    #Unicamente evalua los vecinos que el usuario desea comparar, encontrando a que par de coordenadas corresponen las distancias pequeñas
    for i in range(k):
        value = distancias_ordenadas[i]
        indices_vecino_mas_cercanos.append(distancias.index(value))

    #Recorre los pares coordenados que están más cerca para ver si son costosos y calidosos
    for i in indices_vecino_mas_cercanos:
        tag = keys[i]
        
        print(f'Vecino cercano: {tag} ')

        if DATOS[tag] == 'costoso':
            contador_costoso += 1
        else:
            contador_calidad += 1
    
    if contador_calidad > contador_costoso:
        print('Su producto es calidoso')
    elif contador_calidad < contador_costoso:
        print('Su producto es costoso')
    else:
        print('Su producto no pudo ser calificado')

def calculo_distancia(DATOS,calidad,precio):

    distancias = []
    keys = []

    for key in DATOS:
        tuples = (key[0]),(key[1])
        keys.append(tuples)

        distancia = math.sqrt((calidad - key[0])**2 + (precio - key[1])**2)
        distancias.append(distancia)
        
    return distancias ,keys

if __name__ == "__main__":
    #Pide al usuario su opinión sobre el precio y la calidad del producto a evaluar, también el número de vecinos con que desea comparar.
    calidad, precio, k = welcome()

    DATOS = {
        (2,5) : 'costoso',
        (1,4) : 'costoso',
        (2,6) : 'costoso',
        (5,1) : 'calidad',
        (6,3) : 'calidad',
        (4,1) : 'calidad',
    }

    #Calcula las distancias con respecto a todos los puntos, devuelve arreglo de distantancias y arreglo con las coordenas de los productos ya clasificados
    distancias, keys = calculo_distancia(DATOS,calidad,precio)
    vecinos(DATOS,distancias,k,keys)
    graficar(DATOS,calidad,precio)

El problema de_ k = par_ es que puede salir que la mitad de vecinos cercanos es de un grupo X y la mitad de vecinos cercanos de un grupo Y

Pienso que partiendo de cero se podría usar un algoritmo de clustering con un muestra significativa para definir los grupos y luego usar este algoritmo de clasificación para ir anexando nuevos puntos a los grupos definidos anteriormente.

Clasificación K-nearest neighbors.

• Es uno de los algoritmos mas importante y mas antiguos 👴🏽.
• Parte del supuesto de que ya tenemos algún conjunto de datos clasificados y queremos encontrar la clasificación de un vector nuevo.
• La K se refiere a la cantidad de vecinos que usaremos para clasificar a dicho vector. Se observa a que clase pertenece la mayoría de los k puntos mas cercanos. Es importante determinar el valor de K ❣️.
• Debemos tener cuidado con usar K par ya que puede suceder que toquen K/2 votos para dos clases y no se puede determinar a cual pertenece 😟. Si pasa eso, podemos aumentar el valor de K.

• Es muy costoso computacionalmente y no sirve para altas dimensiones 🔬 pero nuevamente, se puede hacer una muestra 😃.
• Siempre es importante determinar los elementos que contiene el feature vectors, las cuales tienen que representar a los elementos 🔥.

Desde mi punto de vista para k par, seguiría tomando para ese caso el siguiente vecino más cercano hasta realizar un desempate, y claro está se clasificaría con el grupo que mayor vecinos tenga.

Clasificación K-nearest neighbors:

Ventaja:
Sencillo de aprender e implementar.

Desventaja:
Utiliza todo el dataset para entrenar cada punto.
Requiere mucha memoria y CPU.

Para mí un K par debe sumar las distancias de los dos grupos y la distancia menor es el cluster que pertenece

Comparto mis NOTAS:
Es uno de los algortimos más importantes y más antiguos de machine learning.
Parte del supuesto que ya tenemos una clasificación.
Trata de encontrar los “vecinos más cercanos” (tomando como parámetro la distancia entre puntos).
“K” se refiere a la cantidad de vecinos que se utilizaran para clasificar un ejemplo (dato) que aún no ha sido clasificado.
Es computacionalmente muy costoso y no sirve con datos de alta dimensionalidad.

if k %2 != 0 entonces el algoritmo puede dejar muchos datos sin clasificar, por empate entre los otros puntos, por lo cual podemos perder muchos datos para el algoritmo.

Con un valor par existe la posibilidad de empate, tiene la misma probabilidad de ser de un grupo o del otro grupo

Creo que esto pasa cuando los clusters son muy cercanos 😅😂

Los autores de crecimiento personal dicen que uno, es el promedio de las 5 personas con que mas interactúa, asi que
todos los dias nuestro 5-nearest people puede cambiar a mejor.

Me hubiera gustado sin la analogía de GOT, ya que esas palabras que mencionaba en la clasificación no significan nada para mi, además de no ser palabras cuyo significado pueda simplemente suponer.

Pensando así en voz alta: Si k es par, tenemos la mitad de los vecinos de una clase y la mitad de la otra, ¿No serviría calcular la menor distancia del promedio de todos los vecinos de cada clase? Es decir:
clase A(compuesta de 2 vecinos, A1 y A2, con k=4), distancia_A = (dist_A1 + dist_A2)/(k/2).
Lo mismo con la clase B y luego, la menor distancia promedio sería quien se adjudicara el nuevo dato.
¿No serviría?
Claro, podría usarse para N clases, la desventaja sería que haya distancias promedio iguales, lo cual sería posible.

El problema con un K par sería que existe la posibilidad de tener 50% de los datos de un lado y 50% de los datos del otro y por lo tanto no se podría decidir si el punto a analizar pertenece a uno o a otro. En cambio con un K impar pues siempre uno va a tener mayoría si o si.

muy buena clase… pienso que el problema con un k par es cuando hay paridad en los “votos”… ahora eso se puede solucionar aplicando un criterio como ponderar el voto por la distancia (es decir, si un punto está más cerca, entonces su “voto” pesa más).

Saludos a todos desde chile

Si es par, es posible que quede en un empate. Es decir, puede que la cantidad de vecinos en el grupo A sea la misma que en el grupo B

no se deben utilizar valores pares para K, ya que se pueden presentar “empates” al momento de clasificar, y, por tanto, el dato no pertenecería a un grupo en particular, y pasaría outliner, debe ser impar, para que el resultado se incline a una u otra dirección, facilitando así la clasificación

el problema con una K par es que caeríamos en una indeterminación, osea tendríamos 2k = x y 2k = y, y no sabríamos a donde asignar nuestro objeto.

Creo que si hay una “K” par y no tienes alternativa de cambiarla a impar, debería usarse un Modelo de Mezcla Gaussiana (MMG) pero sería cambiar totalmente la metodología de análisis pues este modelo es de clustering y no de clasificación
Aquí explican más cómo funciona este modelo:

https://la.mathworks.com/help/stats/clustering-using-gaussian-mixture-models.html

https://medium.com/datos-y-ciencia/aprendizaje-no-supervisado-en-machine-learning-agrupación-bb8f25813edc#:~:text=Para ello%2C los algoritmos de,con los de clústeres diferentes.&text=Modelo de Agrupamiento Gaussiano

Si tengo un grupo A que esta muy disperso( es decir su desviación estandar es grande comparándolo con el grupo B) y un grupo B que esta mas apretado y ocurriera el caso raro en que un dato debe clasificarse en uno de ellos pero sus cuatros vecinos (2 en el A y 2 en el B) son sorprendentemente equidistantes al dato entonces el dato pertenecerá al grupo A ya que al estar mas disperso tiene mas posiblidades de ser parte de ellos

Resumen de la clase: “Dime con quien andas y te diré quien eres”

para K par en Clasificación K-nearest neighbors puede quedar una paridad y por tanto resultado impreciso o no determinado

un K par, daría la posibilidad de un igual cantidad de vecinos de grupos diferentes (empate) por lo cual no se podría decidir tan simple a que clasificación pertenece. En este caso creo que se podría plantear un promedio de distancia de los puntos de cada clasificación y así determinar a que grupo pertenece el nuevo datapoint. :?

https://github.com/Erik-Lopez/knearest-implementation

¡Aquí mi implementación de K-nearest neighbors!

Hay dos cosas que me parecen curiosas con respecto a k-neares neightbors.

1. Hay problemas no solo con que k sea par sino con que sea divisible entre el número de clásificaciones. Por ejemplo, si hay tres clásificaciones hay problema si es divisible entre 2 o entre 3, por lo que se tendría que tomar por ejemplo 5 como k.
2. Un aumento de k no significa que se afiance la pertenencia a un grupo. Por ejemplo, pudieramos tener que para k = 3 se es de westeros, para k = 5 se es dotraki y para k =7 se vuelve a ser de westeros.

En base a que se define la posicion del elemento el cual queremos saber su clase ?

Notas
Algoritmo K-Nearest Neighbors:
Trata de encontrar los vecinos más cercanos para clasificar. Partiendo de que ya tenemos un grupo de datos clasificados.
K = cantidad de vecinos para clasificar.
Recuerda:
Este algoritmo es muy costoso en el computo, y no nos servirá con datos de alta densidad.

Clasificación K-nearest neighbors

Es un de los algoritmos más importantes dentro del mundo del ML, y también uno de los más antiguos.

• Parte del supuesto de que ya tenemos un conjunto de datos clasificados.
• Trata de encontrar los “vecinos más cercanos”.
• K se refiere a la cantidad de vecinos que se utilizarán para clasificar un ejemplo que aún no ha sido clasificado.
• Es sencillo de implementar y tiene aplicaciones en medicina, finanzas, agricultura, etc.
• Es computacionalmente MUY COSTOSO y no sirve con datos de alta dimensionalidad.

Que aplicacion es la que usa en la tableta? la que parece cuaderno?

El problema de tener un K par es que puede dar igual cantidad de datos cercanos de una clase o de otra, por eso lo más inteligente sería entender cómo funciona el algoritmo y saber que si se va a utilizar para clasificar un dato es recomendable usar un K impar. El algoritmo de KNN no siempre se utiliza para clasificar, puede utilizarse (por ejemplo) como para recomendar basado en la ùltima película vista, si quiero 3 recomendaciones utilizo un K = 3, o si quiero 10 entonces K = 10. En estos casos no influye que sea par o impar.

A que se refiere con Datos de Alta Dimensionalidad?

Si K es igual a un numero par creo que la opción que a mi parecer es poco eficiente y existe la posibilidad de fallar es sumar las distancias y dependiendo de los totales el mas cercano ese es, sé que puede haber un gran error y es el hecho de que exista totales que sean iguales, pero más importante aun no sé si ese enfoque es valido

La respuesta correcta supongo que seria buscar un vecino extra para desempatar.

Son las únicas opciones que se me ocurren aun que estoy casi seguro que la segunda es la correcta

Si hay un K par y empata la cantidad de puntos, funcionaría hacer un promedio de distancias respecto a cada grupo, pero si debería ser un K alto (por ejemplo en 100 datos, mínimo un K de 8), porque por ejemplo un K = 2 tomaría casos muy específicos que no representan todo el grupo.

Se produciría una ambigüedad, en caso de que uno se puede tener un proporción igual con ambos grupos, Por ello seria necesario reforzar el algoritmo para la clasificación, se me ocurre que parte de establecer los vecinos cercanos, abría que ver cuales están mas cerca y cuales mas lejos y que esto influya en la decisión.

Considero que en un K par lo que se hace es evaluar las características esenciales del nuevo dato y luego medir las distancias.

En este caso ya tienes que tener un conjunto de datos clasificados, los cuales son los labels y en base a ello el algoritmo se encargara de clasificar nuevos datos segun la mayor cantidad de vecinos cercanos que pertenecen a un grupo, en caso de que el numero de vecinos cercanos de ambos grupos sea el mismo, lo que haria seria analizar las distancias totales y quedarme con los vecinos mas cercanos.

K nearest neighbours
A partir de una clasificación previa etiquetamos un dato no clasificado.
Tomamos los k vecinos más cercanos y tomamos la decisión según la pertenencia de estos (generalmente por mayoría simple)

k > =3

facinante

ojo q no es el mismo q el otro

En todo conjunto par hacer un conjunto sea divisible en partes iguales y no me da una medida de tendencía a un lado o a otro

Al tomar un número par para K se puede producir un empate, que no permita realizar la clasificación

Mi teoría general sobre las k en números pares es que generas ambigüedad y de ahí desprendo la teoría 1 de que no se clasificaría o no generaría una pertenencia a ningún arquetipo del modelo generando algo similar a un null en una base de datos, teoría 2 se podría generar una recursividad u operaciones innecesarias adicionales tratando de hacer match con un vecino cercano, teoría 3 crearía un infinite loop

Creo que si tenemos que hacer una clasificación forzosamente discreta (o es X o es Y), sería conveniente hacer una sumatoria de todas las distancias, y así aunque haya una cantidad n de vecinos X y una cantidad n de vecinos Y, podríamos tomar rápidamente la sumatoria más pequeña.

Con respecto a el problema de tener un k par y obtener como vecinos más cercanos igual cantidad para los otros clusters( considerando dos clusters) , en caso eso suceda podríamos realizar una media de los vecinos apuntando a cada cluster y , finalmente, clasificando en base a la que obtuvo una menor media.

Otra opción tambien sería buscar un nuevo punto cercano y lograr el desempate, pero pensando en el costo computacional que implica comparar cada distancia con cada punto, resultaría con más demora.

Espero más feedback sobre este pensamiento, pues creo que podría funcionar 😄!

Dependiendo de la cantidad de datos puede ocurrir que con K=6 en dos grupos un objeto tenga 3 características de un grupo y otras tres de otro grupo, entonces quedaría indeterminado…

El problema de un k par seria que en podría haber un empate en los votos de los k puntos mas cercanos que nos permiten seleccionar etiqueta del punto(sin clasificar) la forma en la que se podría solucionar el problema seria colocando pesos a los k puntos y colocar un mayor valor a los puntos que se encuentren mas cerca con respecto de los otros k puntos.
Referencia: https://towardsdatascience.com/everything-you-ever-wanted-to-know-about-k-nearest-neighbors-dab986e21b60

K no podría ser par porque existe la posibilidad de que la mitad de los puntos cercanos sea para una clasificación y la otra mitad sea para otra. No habría punto de desempate para romper esto y el algoritmo no seguiría adelante.

Creo que la dificultad de que k sea un par es la forma como se va utilizar para desempatar y con un par no se va poder.

Se pudiera obtener cuya suma total de las distancias sea menor

El problema con una K par es que pueden haber empates

según yo lo veo al usar un numero impar el algoritmo mide las distancias de todos los puntos en el dataset, luego selecciona los X puntos mas cercanos a el, mira las etiquetas y de estos puntos y como son impares o se va para uno o para el otro, al usar un numero impar el algoritmo ya no podría decidir solo por las etiquetas, tendría que sumar se las distancias de las etiquetas de sus X vecinos mas cercanos con respecto a el y se asignara al grupo que tenga la menor distancia hacia el

Si tuviera una k par, y quedaran 2-2 yo sumaría las diferencias de cada punto con respecto a mi objetivo. Entonces llevaría mi objetivo al grupo donde la la suma de las diferencias fueran menores.

https://github.com/juandasuarez/knearestneighboralg/blob/master/knearestn.py Acá les dejo el algoritmo hecho en Python. Se introduce un valor K y un número de puntos aleatorios, y se genera otro punto aleatorio que se clasifica en un o de los dos grupos.

Abajo se ve el resultado en terminal, el punto nuevo (28,7) termina perteneciendo al grupo 1.

Escoge un valor K mayor a 2: 5
Escoge un número de puntos para cada grupo: 10
Mínimos grupo 1: [2.83, 3.0, 3.61, 4.0, 5.39]
Mínimos grupo 2: []
Grupo 1: [(26, 5), (25, 9), (19, 12), (16, 7), (25, 7), (30, 2), (28, 15), (17,
1), (28, 3), (21, 3), (28, 7)]
Grupo 2: [(1, 19), (12, 18), (12, 23), (3, 22), (15, 18), (8, 20), (4, 20), (13,
 19), (6, 16), (4, 15)]
Punto nuevo: (28, 7)

Me surge la curiosidad sobre como hacen los algoritmos recomendadores para utilizar esta técnica, es decir, como Netflix sabe como usar mi data para recomendarme cosas que mis vecinos vieron?

En caso de tener un K par existiría la posibilidad de tener la misma cantidad de vecinos para dos clasificaciones distintas, por lo tanto, no habría una manera directa de determinar a qué conjunto pertenece mi dato. La mejor solución sería usar siempre un K impar. En caso de que sea obligatoriamente par, yo tomaría el promedio de las distancias respecto a cada conjunto y elegiría la menor.

O sea que podemos decir que en general en machine learning, lo que hacemos es comparar y medir que tan parecidos son los elementos? y en base a esto es que clasificamos.

xd a veces la vida es mas sencilla de lo que creeemos.

Para el problema cuando K es par una solución es la elección por medio de la aleatoriedad

K-nearest neighbors es igual al K-means ??

Supongamos que tengo 50 puntos azules y 3 puntos rojos. Los 50 puntos azules están muy juntos y lejos de los rojos.

Ahora, si mi punto a clasificar se encuentra en el medio de los puntos rojos, y utilizo un k=7, por ejemplo, el algoritmo dirá que mi punto es azul, ya que si bien tiene 3 puntos rojos pegados, a la distancia habran 4 azules.

Como se soluciona esto? Haciendo promedio de las distancias o esto se aplica y no se explicó?

Con una K par se puede tener una probabilidad de 0.50 de pertenecer al un grupo u otro, si los K son grupos distintos

Si existe un K par lo que ocurre es que podria suceder una situacion de indefinicion de clasificacion. Eso sucede porque un datapoint puede que tenga cerca la misma cantidad de objetos de un grupo de y de otro. Por ejemplo, si K =6, un data point podria tener 3 vecinos verdes y 3 vecinos rojos lo que lo haria incapaz al algoritmo de clasificar el datapoint.

Interesante artículo acerca de este algoritmo.
Clasificar con K-Nearest-Neighbor ejemplo en Python

Para el problema del par, seguiría tomando distancias con los “Par”, hasta ver cual es el de menor distancia y unirme a él

ok, lo entendi de manera grafica en plano carteciano, pero y si son datos que no se pueden graficar tan facil… , ahi si no entenderia como se realiza la clasificacion por vecinos 😕

¿Qué tal si eliminamos el vecino más lejano o buscamos otro vecino que se encuentre más cerca?

No he visto game of thrones y me sentí algo perdida al principio hehe pero todo súper claro

y los que no vimos Juego de Tronos como la mama del chavo.

Que bien que en esta clase se use un ejemplo claro.

Cuando K es par existe la posibilidad de que se genere un error en la clasificación del dato. Para evitarlo lo mas recomendable es tomar un numero impar siempre.

Las formas más populares de “medir la cercanía” entre puntos son la distancia Euclidiana (la “de siempre”) o la Cosine Similarity (mide el ángulo de los vectores, cuanto menores, serán similares).

Esta forma de de terminar el vecino mas cercano me hace pensar en sus aplicaciones a proyecciones y mediciones en intención de voto para escoger presidente de un país.

el problema de implementar una k par es que a la hora de insertar un nuevo dato este no sea posible de clasificar. En dicho caso se podrían plantear diversas soluciones como un conteo de la menor distancia entre “votantes”. O como sucede en la politica una segunda vuelta aumentando aleatoriamente la cantidad de k, obviamente se debe tener control de este aumento para evitar un aumento abrupto en los recursos para el calculo.