Contact Us!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

| Download
Views: 31
Image: ubuntu2004
Tweet
Share
Share
Kernel: SageMath 9.1

El Algoritmo de K Means

El problema de agrupamiento es uno de los problemas más importantes del reconocimiento de patrones; se trata de encontrar estructura en una colección de datos. Una definición vaga de agrupamiento podría ser “el proceso de organizar objetos en grupos cuyos miembros son similares de alguna manera”. Por lo tanto, un grupo es una colección de objetos que son "similares" entre ellos y son "diferentes" a los objetos que pertenecen a otros grupos. Uno de los algoritmos más usados para resolver este problema es el algoritmo de K Means.

¿Qué es K Means?

Es un algoritmo para buscar una cantidad, dada por nosotros, de patrones en un conjunto de datos. Este algoritmo aunque es sencillo, es bastante potente por los resultados que genera. Supongamos que tenemos 10,000 datos y tenemos que clasificar cada dato en al menos 5 categorías, encontrando algún criterio de clasificación. Esta tarea tal cual sería super difícil, requeriría muchísimos análisis de distintos tipos para que encontráramos algún patrón, y esto tardaría varios días o semanas. Sin embargo, podemos ejecutar K-Means para que encuentre 5, 6 o tantas clasificaciones como queramos y aunque sean muchos datos, puede encontrar las categorías que deseemos usando criterios estadísticos en su comportamiento. Por esto es un algoritmo muy valorado en la ciencia de datos.

Entendamos el algoritmo

Antes de programarlo, primero comprendamos conceptualmente cómo funciona el algoritmo de K Means. K means imagina cada grupo como un sistema solar. La estrella alrededor de la que gira todo (todas los datos) en el grupo se conoce como centroide del grupo.

Entonces, dado un conjunto de kk centroides y sus coordenadas, podemos averiguar fácilmente a qué grupo pertenece cada dato calculando a qué centroide está más cerca (en términos de distancia euclidiana).

Pero, ¿cómo decidimos dónde están los centroides? Ahí es donde entra el algoritmo de K means. Primero, elegimos un valor para kk, el número de centroides, supongamos que k=3k=3. Luego, podemos elegir 3 puntos al azar y asignarlos para que sean nuestros centroides iniciales. Y usando nuestros centroides iniciales elegidos al azar, podemos crear 3 grupos. Suena un poco tonto, ¿verdad? ¿De qué sirve elegir centroides aleatorios y crear grupos aleatorios?

Aquí está el truco: las medias de nuestros grupos se convierten en nuestros nuevos centroides (para cada grupo, calculamos la xx media y la yy media, y esa es la coordenada de nuestro nuevo centroide). Y siempre que nuestros centroides iniciales seleccionados al azar fueran incluso ligeramente diferentes entre sí, los nuevos centroides (las medias del grupo) serán más óptimos que nuestros centroides iniciales; donde la optimalidad se define como maximizar la similitud dentro del grupo y la diferencia entre los grupos.

Una vez que tenemos nuestros nuevos centroides, podemos reasignar los datos en función de los nuevos centroides. Dado que los centroides se volvieron un poco más óptimos, nuestros grupos también deberían mejorar (en términos de homogeneidad dentro del grupo y varianza entre los grupos). Y ahora podemos volver a calcular nuevos centroides a partir de las medias de las coordenadas de los grupos reasignados. Estos centroides habrán mejorado nuevamente sobre sus predecesores, y podemos seguir repitiendo este proceso hasta que el algoritmo converja.

Los datos

Para mostrar el algoritmo ocuparemos un conjunto de datos que corresponde a puntos de la forma (x,y)=(peso,altura)(x,y)=(peso, altura).

datos=[[158,64],[160,68],[174,72],[165,65],[172,79],[180,98],[163,68],[175,76],[150,48],[171,75],[156,63],[154,54],[174,65],[166,80],[167,83],[155,63],[187,75],[167,58],[182,96],[154,69],[171,82],[168,78],[169,68],[179,80],[152,50],[164,48],[157,67],[160,86],[170,70],[165,60],[183,98],[156,47],[175,79],[173,80],[166,72],[165,71],[174,68],[158,64],[169,75],[169,92],[166,78],[165,75],[145,42],[147,55],[177,105],[176,85],[152,51],[180,85],[170,68],[163,78],[165,82],[170,79],[169,72],[170,76],[162,78],[160,70],[158,63],[162,75],[173,83],[166,81],[158,46],[158,62],[155,80],[155,65]]
print(len(datos))
points(datos, color="blue", size=25)
64
Image in a Jupyter notebook

Y vamos a determinar una variable KK que corresponderá al número de categorías que vamos a ocupar para agrupar los datos

K=3

Centroides aleatorios iniciales

Ahora vamos a generar los centroides iniciales de manera aleatoria. Para esto primero determinaremos los valores mínimos y máximos de xx y yy.

xmin=min([dato[0] for dato in datos])
xmax=max([dato[0] for dato in datos])
ymin=min([dato[1] for dato in datos])
ymax=max([dato[1] for dato in datos])

Ahora generaremos los centroides de manera aleatoria, para ello generaremos un entero entre el valor mínimo y máximo de xx y un entero entre el valor mínimo y máximo de yy, los juntaremos en un punto, y los pondremos en una lista llamada mu 

mu=[]
for i in srange (K):
    x=randint(xmin,xmax)
    y=randint(ymin,ymax)
    mu.append([x,y])
print(mu)
[[151, 78], [145, 98], [167, 42]]

Veamos donde quedaron los centroides

points(datos, color="blue", size=25) +  points(mu[0], color="purple", size=80) +  points(mu[1], color="green", size=80)+  points(mu[2], color="red", size=80)
Image in a Jupyter notebook

Calculando los grupos

Para ayudarnos a calcular los grupos primero hagamos una función que nos diga la distancia (euclidiana) entre dos puntos.

def distancia (P, Q):
    dis=sqrt((P[0]-Q[0])^2+(P[1]-Q[1])^2)
    return dis

Ahora necesitamos una función que, dado un conjunto de centroides, pueda decirnos a qué grupo pertenece cada dato. La siguiente función usa for anidados para calcular la distancia entre cada dato y cada centroide (usando nuestra función distancia). Luego, asigna cada dato a un grupo según el centroide al que esté más cercano. El resultado es la lista de las asignaciones de grupo de cada dato.

def asigna_grupos(centroides, datos):
    Grupos=[]
    for i in srange (len(datos)):
        Distancias=[]
        for centroide in centroides:
            Distancias.append(distancia(centroide,datos[i]))
        grupo=[z for z, val in enumerate(Distancias) if val==min(Distancias)]
        Grupos.append(grupo[0])
    return Grupos

L=["a","b","c","d"]
for i in enumerate(L):
    print(i)
(0, 'a') (1, 'b') (2, 'c') (3, 'd')

Llamemos Asignacion a la primera asignación de los datos a los centroides

Asignacion= asigna_grupos(mu,datos)

Ahora en una lista llamada datos_divididos partamos el conjunto de datos de acuerdo con su centroide

datos_divididos=[[datos[i] for i in srange(len(datos)) if Asignacion[i]==j] for j in srange(K)]

Veamos como agrupó los datos

points(mu[0], color="purple", size=80, marker="D") + points(datos_divididos[0], color="purple", size=25) + points(mu[1], color="green", size=80, marker="D") + points(datos_divididos[1], color="green", size=25) +points(mu[2], color="red", size=80, marker="D") + points(datos_divididos[2], color="red", size=25)
Image in a Jupyter notebook

Calculando los nuevos centroides

Ahora necesitamos una función para el paso de actualización donde asignamos nuevos centroides. La siguiente función parte los datos de acuerdo al grupo que pertenecen. Luego toma los datos que pertenecen a un cierto grupo y calcular la media de dichos. Estas medias calculadas serán nuestros nuevos centroides.

def actualiza_centroides(datos, Asignacion, K):
    datos_divididos=[[datos[i]for i in srange (len(datos)) if Asignacion[i]==j]for j in srange(K)]
    nuevos_centroides=[]
    for grupo in datos_divididos:
        valoresx=[dato[0]for dato in grupo]
        valoresy=[dato[1]for dato in grupo]
        centroide=[mean(valoresx), mean(valoresy)]
        nuevos_centroides.append(centroide)
    return nuevos_centroides

Calculamos los nuevos centroides

Mu=actualiza_centroides(datos, Asignacion, K)

Veamos como son los nuevos centroides

datos_divididos=[ [datos[i] for i in srange(len(datos)) if Asignacion[i]==j  ] for j in srange(K) ]
points(Mu[0], color="purple", size=80, marker="D") + points(datos_divididos[0], color="purple", size=25) + points(Mu[1], color="green", size=80, marker="D") + points(datos_divididos[1], color="green", size=25) +points(Mu[2], color="red", size=80, marker="D") + points(datos_divididos[2], color="red", size=25)
Image in a Jupyter notebook

Corramos K Means

Vayamos con 3 grupos todavía (K=3K = 3). Después de esto, ejecutamos un ciclo for 50 veces (50 es suficiente para la convergencia en este caso) donde calculamos repetidamente nuevos centroides (usando actualiza_centroides) y nuevos grupos (usando asignar_grupo) para que podamos obtener grupos óptimos. Recuerda que al repetir este proceso de calcular las medias de los grupos (también conocidos como nuevos centroides) y asignar nuevos grupos basados en estos nuevos centroides, es como el algoritmo converge a los grupos finales. Este proceso puede tardar algunos minutos.

datos=[[158,64],[160,68],[174,72],[165,65],[172,79],[180,98],[163,68],[175,76],[150,48],[171,75],[156,63],[154,54],[174,65],[166,80],[167,83],[155,63],[187,75],[167,58],[182,96],[154,69],[171,82],[168,78],[169,68],[179,80],[152,50],[164,48],[157,67],[160,86],[170,70],[165,60],[183,98],[156,47],[175,79],[173,80],[166,72],[165,71],[174,68],[158,64],[169,75],[169,92],[166,78],[165,75],[145,42],[147,55],[177,105],[176,85],[152,51],[180,85],[170,68],[163,78],[165,82],[170,79],[169,72],[170,76],[162,78],[160,70],[158,63],[162,75],[173,83],[166,81],[158,46],[158,62],[155,80],[155,65]]
print(len(datos))
points(datos, color="blue", size=25)

K=3

xmin=min([dato[0] for dato in datos])
xmax=max([dato[0] for dato in datos])
ymin=min([dato[1] for dato in datos])
ymax=max([dato[1] for dato in datos])

mu=[]
for i in srange (K):
    x=randint(xmin,xmax)
    y=randint(ymin,ymax)
    mu.append([x,y])
print(mu)

points(datos, color="blue", size=25) +  points(mu[0], color="purple", size=80) +  points(mu[1], color="green", size=80)+  points(mu[2], color="red", size=80)


def distancia (P, Q):
    dis=sqrt((P[0]-Q[0])^2+(P[1]-Q[1])^2)
    return dis

def asigna_grupos(centroides, datos):
    grupos=[]
    for i in srange(len(datos)):
        distancias=[]
        for centroide in centroides:
            distancias.append(distancia(centroide,datos[i]))
        grupo=[z for z, val in enumerate(distancias) if val==min(distancias)]
        grupos.append(grupo[0])
    return grupos

L=[]
for i in enumerate(L):
    print(i)

Asignacion=asigna_grupos(mu,datos)

datos_divididos=[[datos[i]for i in srange (len(datos)) if Asignacion[i]==j] for j in srange(K)]

points(mu[0], color="purple", size=80, marker="D") + points(datos_divididos[0], color="purple", size=25) + points(mu[1], color="green", size=80, marker="D") + points(datos_divididos[1], color="green", size=25) +points(mu[2], color="red", size=80, marker="D") + points(datos_divididos[2], color="red", size=25)

Mu=actualiza_centroides(datos, Asignacion, K)

datos_divididos=[ [datos[i] for i in srange(len(datos)) if Asignacion[i]==j  ] for j in srange(K) ]
points(Mu[0], color="purple", size=80, marker="D") + points(datos_divididos[0], color="purple", size=25) + points(Mu[1], color="green", size=80, marker="D") + points(datos_divididos[1], color="green", size=25) +points(Mu[2], color="red", size=80, marker="D") + points(datos_divididos[2], color="red", size=25)
64 [[171, 87], [147, 55], [176, 77]]
--------------------------------------------------------------------------- NameError Traceback (most recent call last) <ipython-input-6-0577dd3546dc> in <module>() 44 points(mu[Integer(0)], color="purple", size=Integer(80), marker="D") + points(datos_divididos[Integer(0)], color="purple", size=Integer(25)) + points(mu[Integer(1)], color="green", size=Integer(80), marker="D") + points(datos_divididos[Integer(1)], color="green", size=Integer(25)) +points(mu[Integer(2)], color="red", size=Integer(80), marker="D") + points(datos_divididos[Integer(2)], color="red", size=Integer(25)) 45 ---> 46 Mu=actualiza_centroides(datos, Asignacion, K) 47 48 datos_divididos=[ [datos[i] for i in srange(len(datos)) if Asignacion[i]==j ] for j in srange(K) ] NameError: name 'actualiza_centroides' is not defined

Conclusiones

Obviamente, podemos hacer mucho más, incluido agregar más información (en este caso fue solo peso y altura, pero podríamos agregar cintura y/o cuello), ajustar KK (el número de grupos), determinar el número de veces que debemos iterar para que converja el algoritmo y tratar de comprender mejor la identidad y las características clave de cada grupo. Pero eso será en otra ocasión. Espero que al terminar esta práctica, se hayan llevado una idea de cómo es el problema de agrupamiento y cómo K Means usa un algoritmo maravillosamente simple para producir resultados geniales.

Ejercicio

Para esta práctica deberás recopilar dos datos distintos sobre una colección de, al menos, 100 objetos (en la explicación los datos fueron peso y altura y los objetos fueron personas) Estos datos deberán ser expresados con números enteros (si es necesario convierte los datos a una unidad de medida adecuada). Es importante que los datos sean variables que se puedan medir, es decir NO ocupes cosas como categorías o clases.

Después ejecuta el algoritmo de K Medias para algún cierto valor de K que consideres pueda ser adecuado e interpreta cual fue la clasificación que hizo el algoritmo. Postea el tipo de datos que obtuviste, una imagen de la clasificación obtenida y tus conclusiones sobre los grupos que generó el algoritmo.

Para mostrar el algoritmo ocuparemos un conjunto de datos que corresponde a puntos de la forma (x,y)=(base, altura)

datos=[[30,75],[2,7],[14,60],[20,37],[12,97],[80,89],[61,71],[52,6],[10,28],[31,95],[76,36],[43,20],[14,28],[62,20],[40,33],[75,27],[91,21],[6,8],[8,6],[82,39],[11,12],[18,50],[40,28],[76,6],[20,33],[13,84],[50,87],[19,86],[100,200],[182,70],[11,87],[86,37],[15,29],[13,170],[120,120],[5,4],[24,122],[158,20],[100,75],[90,192],[16,178],[125,175],[120,142],[157,155],[171,105],[17,85],[52,151],[80,185],[70,168],[16,178],[125,182],[170,109],[19,13],[10,76],[16,12],[100,100],[200,200],[12,72],[13,183],[66,11],[138,46],[138,62],[135,80],[165,65],[3,7],[1,5],[12,6],[2,30],[11,78],[16,50],[41,61],[12,106],[103,128],[131,195],[176,136],[143,120],[114,128],[162,120],[140,133],[175,127],[191,121],[16,118],[118,6],[42,31],[1,1],[13,5],[4,28],[76,16],[120,133],[113,20],[1,70],[30,7],[20,70],[145,106],[109,200],[121,9],[180,9],[161,101],[122,63],[101,20]]
print(len(datos))
points(datos, color="red", size=25)
100
Image in a Jupyter notebook