Agrupamiento K-means

Si no te quedo del todo claro, esta pagina ayuda mucho, de ahi saque la libreria Kmeans
https://www.jacobsoft.com.mx/es_mx/k-means-clustering-con-python/

Aquí mi K_means. Ejecútenlo usando Bokeh

from bokeh.plotting import figure, show, output_file
import random

class F_Vector:
    def __init__(self, c_1, c_2):
        self.x = c_1
        self.y = c_2
        self.grupo = Semilla(0,0) #aun no pertenece a ningún grupo
        self.color = self.grupo.color #toma el color de su semilla

    def medir_d_semilla(self, semillas): # semillas[ , , ] las semillas y coord
        '''Define a qué grupo pertenece
        según su distancia con cada semilla
        '''
        assert type(semillas) == list, f'El arg debe ser una lista de Semillas'
        distancias = {} # {distancia : semilla}
        for i in semillas:
            assert type(i) == Semilla, f'Debe ser un arreglo de semillas'
            dx = self.x - i.x
            dy = self.y - i.y
            deucl = (dx**2 + dy**2)**(0.5)
            distancias[deucl] = i # {distancia : semilla}
        d_min = min(distancias) #pertenece al grupo de la semilla más cercana
        self.grupo = distancias[d_min]

class Semilla:
    def __init__(self, x, y, nombre = 'Sin asignar', color_sem = '#000000'):
        self.x = x
        self.y = y
        self.nombre = nombre
        self.color = color_sem
        #self.distancia_recorrida = 10###################### eliminar

    def mover_semilla(self, nuevo_x, nuevo_y):
        dx = self.x - nuevo_x
        dy = self.y - nuevo_y
        self.distancia_recorrida = (dx**2 + dy**2)**(0.5)
        self.x = nuevo_x
        self.y = nuevo_y



class Campo:
    def __init__(self, ancho = 200, alto = 200):
        self.ancho = ancho
        self.alto = alto
        self.vectors = []
        self.semillas = []

    def agregar_F_Vector(self):
        randx = random.randint(0, self.ancho)
        randy = random.randint(0, self.alto)
        self.vectors.append(F_Vector(randx, randy))

    def agregar_Semilla(self):
        randx = random.randint(0, self.ancho)
        randy = random.randint(0, self.alto)
        self.semillas.append(Semilla(randx, randy, color_sem = generar_color()))

    def mostrar_campo(self):
        '''Muestra la figura con todos los 
        '''
        figura = figure()
        for i in self.vectors:
            figura.circle(i.x, i.y, color = i.color, size = 7)
        for i in self.semillas:
            figura.asterisk(i.x, i.y, color = i.color, size = 20)
        show(figura)

def K_means(campo):
    '''El campo ya debe tener las semillas y los F_Vectors
    '''
    romper_bucle = False
    while(True):
        #medir las distancias de cada FV con cada semilla
        for F in campo.vectors:
            F.medir_d_semilla(campo.semillas) #asignarle un grupo a cada vector
            F.color = F.grupo.color
        #campo.mostrar_campo()
        #calcular centroides
        for S in campo.semillas:
            dist_x = 0
            dist_y = 0 
            cantidad_Vectores = 0
            for V in campo.vectors:
                if V.grupo == S:
                    dist_x += V.x
                    dist_y += V.y
                    cantidad_Vectores += 1
            if cantidad_Vectores != 0:
                new_x = dist_x/cantidad_Vectores #Medias
                new_y = dist_y/cantidad_Vectores
                S.mover_semilla(new_x, new_y)
        campo.mostrar_campo()
        distancias_recorridas = []
        for sem in campo.semillas:
            print(sem.distancia_recorrida)
            distancias_recorridas.append(sem.distancia_recorrida)
        if max(distancias_recorridas) < 0.5:
            romper_bucle = True
        print(romper_bucle)
        if romper_bucle == True:
            break
    campo.mostrar_campo()



def generar_color():
    letras = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f']
    n = '#'
    for _ in range(6):
        n = n + random.choice(letras)
    return n

if __name__ == '__main__':
    campo = Campo()
    #primero se generan los puntos en la figura
    num = int(input('¿Cuantos Vectores hay? : '))
    for _ in range(num):
        campo.agregar_F_Vector() #random
    #campo.mostrar_campo()
    #se agregan las semillas
    num_semillas = int(input('¿Cuantos grupos quieres formar? : '))
    for _ in range(num_semillas):
        campo.agregar_Semilla()
    campo.mostrar_campo()
    #//////////////////////////////// hasta aqui jala con madres ////////////////////////////////
    K_means(campo)


    # figura = figure()
    # figura.asterisk(20,20, size = 50, color = '#000000')
    # show(figura)

Sobre kmeans mencionar que tiene un punto débil extra, y es que cualquier dato lo va a agregar a un cluster, incluso si este llega a ser un outlier o dato atípico. Por lo cual otras técnicas como DBSCAN pueden resultar mejores.

Este articulo me ayudó a entender mucho mejor el algoritmo:

http://www.it.uc3m.es/~jvillena/irc/practicas/08-09/06.pdf

Les recomiendo este artículo para que conozcan 2 métodos para determinar la cantidad de clusters a utilizar en un set dado. Estos son el método de la silueta y el método del codo.

Referencia: https://medium.com/@jonathanrmzg/k-means-elbow-method-and-silhouette-e565d7ab87aa

De esta manera implemente de manera simulada el algoritmo de K-means. Es un código sencillo con puro Python. 😲

import random
epsilon = 0.01

def generar_centroides(k):
    """Genera k puntos al azar

    Parámetros:
    k int > 0

    Retorna: Lista de k listas de puntos x,y [[int, int], [int, int],...]
    """
    centroids = []
    count = 1
    for _ in range(k):
        if count == 5:
            count = 1

        x = random.randint(0, 5) #Genera puntos con coordenadas de -10 a 10
        y = random.randint(0, 5)        
        if count == 1:
            x = x
            y = y
        elif count == 2:
            x = -x
        elif count == 3:
            x = -x
            y = -y
        elif count == 4:
            y = -y

        centroid = [x, y]
        centroids.append(centroid)
        count += 1

    print(f'Centroides originales: {centroids}')
    return centroids
    

def clusterizar(puntos, centroides):
    """Calcula la distancia de una lista de puntos designados por coordenas x,y con
    una lista de centroides con coordenadas x,y.

    Parámetros:
    puntos list [[int, int], [int, int],...]
    centroides list [[int, int], [int, int],...]

    Retorna: Lista con listas con punto, centroide_asignado, distancia_punto_centroide 
    [[[int, int], [int, int], float], [[int, int], [int, int], float], ...]
    """
    elementos_clusters = []    

    for punto in puntos:
        puntos_centroides_distancias = []
        for centroide in centroides:
            distancia_calculada = distancia(punto, centroide)
            puntos_centroides_distancias.append(distancia_calculada)
        # print(f'len: {len(puntos_centroides_distancias)}')
        # print(puntos_centroides_distancias)
        # print('\n')

        distancias_calculadas = []
        for el in puntos_centroides_distancias:
            distancias_calculadas.append(el[2])
        # print(f'Distancias punto-centroides: {distancias_calculadas}')        

        distancia_min = min(distancias_calculadas)
        # print(f'Distancia min: {distancia_min}')
        
        for el in puntos_centroides_distancias:
            if el[2] == distancia_min:
                elementos_clusters.append(el)
                break  
    
    print(f'Elementos: {elementos_clusters}')
    print(f'Cantidad elementos: {len(elementos_clusters)}')
    print('\n')
    return elementos_clusters


def distancia(punto_1, punto_2):
    """Cálcula la distancia euclidiana entre dos puntos.
    
    Parámetros:
    punto_1, punto_2 list [int, int]
    
    Retorna:
    Una lista con el punto_1, punto_2 y su distancia calculada
    [[int, int], [float, float], float]
    """
    a = punto_1[0]
    b = punto_1[1]
    c = punto_2[0]
    d = punto_2[1]

    result = ((a - c)**2 + (b - d)**2)**0.5 #Cálculo de distancia euclidiana

    return [punto_1, punto_2, result]


def calcular_nuevos_centroides(elementos_cluster, centroids):
    """Calcula el punto promedio de una serie de puntos relacionados para
    convertirlo en el nuevo centroide del cluster.

    Parámetros:
    elementos_cluster list [[punto, centroide, distancia], [punto, centroide, distancia], ...]
    k int > 0

    Retorna:
    Lista con los nuevos centroides calculados en forma [x, y]
    list [centroide, centroide, ...]
    Sumas de distancias de centroide con sus puntos
    list [suma_de_distancias, suma_de_distancias, ...]
    """
    new_centroids = []
    sumas_distancias = []
    for centroid in centroids:
        print(f'Centroid: {centroid}')
        puntos_centroide = []
        for el in elementos_cluster:
            if el[1] == centroid:
                puntos_centroide.append(el)
        print(f'Puntos del cluster: {puntos_centroide}')        

        x_coord = []
        y_coord = []
        suma_de_distancias = 0        
        for el in puntos_centroide:
            x_coord.append(el[0][0])
            y_coord.append(el[0][1])
            suma_de_distancias += el[2]    
        new_x = sum(x_coord) / len(puntos_centroide)
        new_y = sum(y_coord) / len(puntos_centroide)   
        print(f'Suma distancias puntos a centroide: {suma_de_distancias}')  
        print(f'New centroid: x {new_x}, y {new_y}')
        print('\n')

        sumas_distancias.append(suma_de_distancias)
        new_centroid = [new_x, new_y]
        new_centroids.append(new_centroid)
    
    print(f'New centroids: {new_centroids}')
    return (new_centroids, sumas_distancias)
    

def agrupamiento_k_means(vectors, k):
    diferencia_sumas_distancias = 100
    total_distancias = 100

    centroides = generar_centroides(k)

    while diferencia_sumas_distancias > epsilon:
        elementos = clusterizar(vectors, centroides)
        nuevos_centroides, sumas_distancias = calcular_nuevos_centroides(elementos, centroides)
        diferencia_sumas_distancias = total_distancias - sum(sumas_distancias)
        total_distancias = sum(sumas_distancias)
        centroides = nuevos_centroides    

        print(f'Total suma distancias puntos-centroide: {total_distancias}')
        print('---'*15 + '\n')        


if __name__ == "__main__":
    coordenadas = [[2, 1], [3, 5], [4, 5], [-1, 2], [-3, 3], [-3, 1], [-1, -4], [-2, -2], [-2, -1], [3, -4], [4, -5], [4, -3]]
    agrupamiento_k_means(coordenadas, 4)

Notas:
K-means utiliza los centroides(la media de los grupos) para agrupar.
El algoritmo funciona asignando puntos al azar (K define el numero de inicio de los clusters) después:

1. En cada iteración el punto se asigna a un centroide y cada punto se recalcula con la densidad respecto a los centroides.

2.Los puntos se asignan al nuevo centro.

3.El algoritmo se repite de manera iterativa hasta que ya no tenga nada que mejorar.

Importante:

• Elegir el K correcto.
• K-means es my pesado computacionalmente hablando.
• Hacer muestreo.

Esta clase del curso profesional de ciencia de datos está muy buena para entender el algoritmo de K-means: https://platzi.com/clases/1621-data/21041-como-funciona-el-algoritmo-k-means/ 😄

Hacer esto sin la libreria de Kmeans, estaba bastante largo, mucho codigo la verdad, queda algo asi

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
 
df = pd.DataFrame({
    'x1': [12, 20, 28, 18, 29, 33, 24, 45, 45, 52, 51, 52, 55, 53, 55, 61, 64, 69, 72],
    'x2': [39, 36, 30, 52, 54, 46, 55, 59, 63, 70, 66, 63, 58, 23, 14, 8, 19, 7, 24]
})
 
np.random.seed(200)
# Número de centroides k = 3
k = 3
# Inicializamos los centroides a valores aleatorios en el espacio de datos
centroids = {
    i+1: [np.random.randint(0, 80), np.random.randint(0, 80)]
    for i in range(k)
}
     
fig = plt.figure(figsize=(5, 5))
plt.scatter(df['x1'], df['x2'], color='k')
colmap = {1: 'r', 2: 'g', 3: 'b'}
for i in centroids.keys():
    plt.scatter(*centroids[i], color=colmap[i])
plt.title(u'Los k centroides están inicializados')
plt.xlim(0, 80)
plt.ylim(0, 80)
plt.show()

## Asignación de las observaciones a los centroides
 
def asignacion(df, centroids):
    for i in centroids.keys():
        # sqrt((x1 - c1)^2 - (x2 - c2)^2)
        df['distance_from_{}'.format(i)] = (
            np.sqrt(
                (df['x1'] - centroids[i][0]) ** 2
                + (df['x2'] - centroids[i][1]) ** 2
            )
        )
    centroid_distance_cols = ['distance_from_{}'.format(i) for i in centroids.keys()]
    df['closest'] = df.loc[:, centroid_distance_cols].idxmin(axis=1)
    df['closest'] = df['closest'].map(lambda x: int(x.lstrip('distance_from_')))
    df['color'] = df['closest'].map(lambda x: colmap[x])
    return df
 
df = asignacion(df, centroids)
 
fig = plt.figure(figsize=(5, 5))
plt.scatter(df['x1'], df['x2'], color=df['color'], alpha=0.5, edgecolor='k')
for i in centroids.keys():
    plt.scatter(*centroids[i], color=colmap[i])
plt.title(u'Asignación de los datos al clúster del centroide más cercano')
plt.xlim(0, 80)
plt.ylim(0, 80)
plt.show()

## Actualización de los centroides
 
import copy
 
old_centroids = copy.deepcopy(centroids)
 
def update(k):
    for i in centroids.keys():
        centroids[i][0] = np.mean(df[df['closest'] == i]['x1'])
        centroids[i][1] = np.mean(df[df['closest'] == i]['x2'])
    return k
 
centroids = update(centroids)
     
fig = plt.figure(figsize=(5, 5))
ax = plt.axes()
plt.scatter(df['x1'], df['x2'], color=df['color'], alpha=0.5, edgecolor='k')
for i in centroids.keys():
    plt.scatter(*centroids[i], color=colmap[i])
plt.title(u'Actualización de los centroides como la media de los datos del clúster')
plt.xlim(0, 80)
plt.ylim(0, 80)
for i in old_centroids.keys():
    old_x = old_centroids[i][0]
    old_y = old_centroids[i][1]
    dx = (centroids[i][0] - old_centroids[i][0]) * 0.75
    dy = (centroids[i][1] - old_centroids[i][1]) * 0.75
    ax.arrow(old_x, old_y, dx, dy, head_width=2, head_length=3, fc=colmap[i], ec=colmap[i])
plt.show()

## Repetición de la asignación de las observaciones al centroide más cercano
 
df = asignacion(df, centroids)
 
# Representación de resultados
fig = plt.figure(figsize=(5, 5))
plt.scatter(df['x1'], df['x2'], color=df['color'], alpha=0.5, edgecolor='k')
for i in centroids.keys():
    plt.scatter(*centroids[i], color=colmap[i])
plt.title(u'Repetición de la asignación de las observaciones al centroide más cercano')
plt.xlim(0, 80)
plt.ylim(0, 80)
plt.show()

Aquí hay un video de Youtube un poco largo pero explic a detalle el funcionamien to de K-means
https://www.youtube.com/watch?v=N1-eWwsM8NE

Algoritmo k-Means

1. Seleccionar el número de k grupos (clusters)
2. Generar aleatoriamente k puntos que llamaremos centroides
3. Asignar cada elemento del conjunto de datos al centroide más cercano para formar k grupos
4. Reasignar la posición de cada centroide
5. Reasignar los elementos de datos al centroide más cercano nuevamente
   5.1 Si hubo elementos que se asignaron a un centroide distinto al original, regresar al paso 4, de lo contrario, el proceso ha terminado

Fuente: https://www.jacobsoft.com.mx/es_mx/k-means-clustering-con-python/

K means
Asignamos un número k de centroides al azar los cuales iremos ajustando de manera progresiva de manera que se reduzca al máximo la variabilidad de cada grupo (definida como la suma de los cuadrados de las diferencias entre los datos y la media).
Nota:
Para definir k (número de centroides y por lo tanto de clusters) es necesario tener un conocimiento del problema.

Holaaa, les dejo un simulador que hice del algoritmo K-means.

https://github.com/Kevinliaoo/K_means_algorithm

Les comparto mi implementacion:

import random 
import numpy as np
from bokeh.plotting import figure, show

#Function to generate a ramdon array of points
def create_vectors(index):
    data_vec = []
    for i in range(index):
        x = random.randint(0,300)
        y = random.randint(0,300)
        data_vec.append([x,y]) 
    return(data_vec)

#Function to calculate minimum distance between a point (data) and a array of points (k_mean), 
#returns index of point in array with minimum distance to the point "data"
def cal_min_distance(k_mean, data):
    media= []
    for i in range(len(k_mean)):
        x = k_mean[i][0] - data[0]
        y = k_mean[i][1] - data[1]
        media.append((x*x + y*y)**0.5)
    return(media.index(np.min(media)))

#Function to calculate 
def cal_k_vector(cluster):
    len_cluster = len(cluster)
    x_points = [vector[0] for vector in cluster]
    y_points = [vector[1] for vector in cluster]
    x = sum(x_points)/len_cluster
    y = sum(y_points)/len_cluster
    return [x, y]

#Function to pick a color from color vector
def sel_color(i):
    color = ['red','green', 'blue', 'yellow', 'orange', 'magenta', 'cyan', 'lime', 'gold', 'purple', 'gray']
    index = i % len(color)
    return color[index]

#Function to perform k_means clutering between data points (data_vector) and k_means vector
def create_cluster(k_mean, data_vector):
    k_mean_last = []
    p = figure(plot_width=400, plot_height=400)
    #Plot original centroides just to have a reference, reference color is black
    x_points = [vector[0] for vector in k_mean]
    y_points = [vector[1] for vector in k_mean]
    cluster_color="black"
    p.circle(x_points, y_points, size=8, color=cluster_color, alpha=1)
    
    #Process is iterative until k_means vector doesn't have change
    while k_mean != k_mean_last:
        #initializing cluster of data points
        cluster = []
        for j in range(len(k_mean)):
            cluster.append([])
        
        #Copying K_mean vector to check at every iteration if vector is the same
        k_mean_last = k_mean.copy()
        
        #Calculating near point from data points to K_mean vector
        for k in range(len(data_vector)):
            indice=cal_min_distance(k_mean, data_vector[k])
            cluster[indice].append(data_vector[k])
        #Calculating new k_mean vector
        for i in range(len(cluster)):
            if (cluster[i]):
                k_mean[i] = cal_k_vector(cluster[i])
                
        
    #Paint K_means clusters by color, final centroids (k_mean vector) are bigger than data points to diference them.
    for i in range(len(cluster)):
        cluster_color=sel_color(i)
        x_points = [vector[0] for vector in cluster[i]]
        y_points = [vector[1] for vector in cluster[i]]
        p.circle(x_points, y_points, size=2, color=cluster_color, alpha=0.4)
        p.circle(k_mean[i][0], k_mean[i][1], size=10, color=cluster_color, alpha=0.9)    
    show(p) 

def run():    
    data_points = int(input("Ingresa la cantidad de puntos: ")) 
    k_mean_number = int(input("Ingresa el numero de agrupaciones: "))
    data_vector = create_vectors(data_points)
    k_mean_vector = create_vectors(k_mean_number)
    create_cluster(k_mean_vector, data_vector)
    
    
if __name__ == '__main__':
    run()

Este video me ayuda a comprender perfectamente el Agrupamiento en K-medios

https://www.youtube.com/watch?v=LGT9v1QMgTE

Me costó muchísimo entender los códigos, así que usé el artículo que dejó un compañero más abajo https://www.jacobsoft.com.mx/es_mx/k-means-clustering-con-python/ para guiarme y salir con este código:

# K-means Clustering

#Importación de librerías
#Antes de importarlas hay que crear en ambiente virtual
# y descargar las librerias por la consola con pip install
import numpy as numpy
import matplotlib.pyplot as plt
import pandas as pd

# Carga del conjunto de datos

#Importamos las librerías y cargamos el conjunto de datos, 
# indicando que la variable que se analizará es una matriz 
# con las columnas 3 y 4 de conjunto de datos, las cuales 
# corresponden al ingreso anual en miles y la puntuación del cliente.

dataset = pd.read_csv ("Mall_Customers.csv")
X = dataset.iloc[:, [3, 4]].values

#Método del codo para encontrar el múmero óptimo de Clusters
#Generamos los clusters para valores de 1 a 10 (Rango de 1 a 11)
#Obtenemos la suma de las distancias con el tributo inertia_ del objeto kmeans

from sklearn.cluster import KMeans
wcss = []
for i in range (1,11):
    kmeans = KMeans(n_clusters = i, init = "k-means++", random_state = 42)
    kmeans.fit(X)
    wcss.append(kmeans.inertia_)

    print(wcss)
#GRAFICA DE LA SUMA DE DISTACIAS

plt.plot(range(1, 11), wcss)
plt.title("The elbow method")
plt.xlabel("Number of clusters")
plt.ylabel("WCSS")
plt.show()

#Según la gráfica que nos dió por el metodo del codo
# La tendencia disminuye cuando el número de clusters es 5
# Hay que usar K = 5

#Creando el modelo  KMeans para los 5 grupos (Clústers)

kmeans = KMeans(n_clusters = 5, init = "k-means++", random_state = 42 )
y_kmeans = kmeans.fit_predict(X)

# la variable y_kmeans guarda los grupos que corresponden a cada renglón de 
# la muestra de datos, lo que significa que cada registro que corresponde a 
# un cliente, esta asignado a uno de cinco grupos que van de 0 a 4

#VISUALIZACIÓN DE LA GRAFICA DE LOS CLUSTER

plt.scatter(X[y_kmeans == 0, 0], X[y_kmeans == 0, 1], s = 10, c = "red", label = "Cluster 1")
plt.scatter(X[y_kmeans == 1, 0], X[y_kmeans == 1, 1], s = 10, c = "blue", label = "Cluster 2")
plt.scatter(X[y_kmeans == 2, 0], X[y_kmeans == 2, 1], s = 10, c = "green", label = "Cluster 3")  
plt.scatter(X[y_kmeans == 3, 0], X[y_kmeans == 3, 1], s = 10, c = "cyan", label = "Cluster 4") 
plt.scatter(X[y_kmeans == 4, 0], X[y_kmeans == 4, 1], s = 10, c = "magenta", label = "Cluster 5") 

plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s = 30, c = "yellow", label = "Centroids")

plt.title("Clusters of Customers")
plt.xlabel("Annual Income (K$)")
plt.ylabel("Spending Score (1 - 100)")
plt.legend()
plt.show()

# El análisis cluster permite hacer inferencias y tomar decisiones.

El Big O sería O(n^k) ?

n = tamaño del dataset.
k = número de clústers

Les comparto mi código del algoritmo, espero que les guste y cualquier observación es bienvenida 😃.
PD: Como todo es mejorable quizas lo mejor sería crear objetos como el objeto vector para que quede todo más limpio.

import random
import math
from bokeh.plotting import figure, output_file, show
import collections

POINTS_COLOURS = ['turquoise', 'lime', 'dodgerblue', 'fuchsia', 'lightcoral', 'navajowhite']
CLUSTERS_COLOURS = ['teal', 'green', 'blue', 'purple', 'red', 'goldenrod']
SIZE_VECTOR = 10
MIN_LIMIT_POINTS = 1
MAX_LIMIT_POINTS = 30
NUM_VECTORS = 100
NUM_CLUSTERS = 4

def generate_random_vector(numVectors, random_low_number, random_high_number):

    random_vectors = []
    for i in range(numVectors):
        random_vectors.append([random.uniform(random_low_number, random_high_number), random.uniform(random_low_number, random_high_number)])

    return random_vectors


def generate_steps_graph(vectors, clusters_vector, step, random_low_number, random_high_number):

    # get x and y values to generate the graph
    x_values = [ vector[0] for vector in vectors[0] ]
    y_values = [ vector[1] for vector in vectors[0] ]

    # output to static HTML file
    output_file(f"step_{step}_graph.html")

    # create a new plot with a title and axis labels
    p = figure(plot_width=400, plot_height=400, x_range = (random_low_number-1, random_high_number+1), y_range = (random_low_number-1, random_high_number+1))

    if step == 0:
        
        # add a circle renderer with a size, color, and alpha
        p.scatter(x_values, y_values, size=SIZE_VECTOR, color='black', alpha=0.5)
    else:

        values_colors = [ POINTS_COLOURS[num_cluster] for num_cluster in vectors[1] ]

        for index_cluster, cluster_vector in enumerate(clusters_vector):
            x_values.append(cluster_vector[0])
            y_values.append(cluster_vector[1])
            values_colors.append(CLUSTERS_COLOURS[index_cluster])

        # add a circle renderer with a size, color, and alpha
        p.scatter(x_values, y_values, size=SIZE_VECTOR, color=values_colors, alpha=0.5)

    # show the results
    show(p)


def clustering_vectors(vectors, clusters_vector):

    clustered_vectors = []
    
    for vector in vectors[0]:
        
        cluster_distance = {
            'min_cluster_distance': -1,
            'index_min_cluster_distance': -1
        }

        for cluster_vestor_index, cluster_vector in enumerate(clusters_vector):

            if cluster_distance['min_cluster_distance'] == -1:
                cluster_distance['min_cluster_distance'] = get_distance_cluster(vector, cluster_vector)
                cluster_distance['index_min_cluster_distance'] = cluster_vestor_index
            else:
                if get_distance_cluster(vector, cluster_vector) < cluster_distance['min_cluster_distance']:
                    cluster_distance['min_cluster_distance'] = get_distance_cluster(vector, cluster_vector)
                    cluster_distance['index_min_cluster_distance'] = cluster_vestor_index

        clustered_vectors.append(cluster_distance['index_min_cluster_distance'])

    return clustered_vectors


def get_distance_cluster(vector, cluster):
    return math.sqrt( (cluster[0] - vector[0])**2 + (cluster[1] - vector[1])**2 )   # raíz( (x2 - x1)**2 + (y2 - y1)**2 )


def calculate_new_clusters_vector(vectors, clusters_vector):

    new_clusters_vector = [] 

    for index_cluster, cluster in enumerate(clusters_vector):

        cluster_vectors = []

        # extract the vectors of that cluster
        for index_vector, vector in enumerate(vectors[0]):
            
            # print(f'{index_cluster} -> {vectors[1][index_vector]}')
            # making a vectors list with the same cluster
            if index_cluster == vectors[1][index_vector]:
                cluster_vectors.append(vector)

        x_cluster_vector = [float(cluster_vector[0]) for cluster_vector in cluster_vectors]
        y_cluster_vector = [float(cluster_vector[1]) for cluster_vector in cluster_vectors]

        if len(cluster_vectors) == 0:
            # calculate the average of vectors in that cluster to get his new coord
            new_cluster_x_coord = random.uniform(1, 10)
            new_cluster_y_coord = random.uniform(1, 10)
            print('random')
        else:
            # calculate the average of vectors in that cluster to get his new coord
            new_cluster_x_coord = sum(x_cluster_vector) / len(cluster_vectors)
            new_cluster_y_coord = sum(y_cluster_vector) / len(cluster_vectors)

        new_clusters_vector.append([new_cluster_x_coord, new_cluster_y_coord])

    return new_clusters_vector


if __name__ == "__main__":
    
    random_vectors = []

    # generate the random vectors
    random_vectors.append(generate_random_vector(NUM_VECTORS, MIN_LIMIT_POINTS, MAX_LIMIT_POINTS))

    # generate the initial plot
    generate_steps_graph(random_vectors, None, 0, MIN_LIMIT_POINTS, MAX_LIMIT_POINTS)

    # generate the clusters for comparing which one is closer to the vectors than the others
    clusters_vector = generate_random_vector(NUM_CLUSTERS, MIN_LIMIT_POINTS, MAX_LIMIT_POINTS)

    # asociate the vector to the closest cluster
    clustered_vectors = clustering_vectors(random_vectors, clusters_vector)

    # set the vector-cluster
    random_vectors.append(clustered_vectors)

    # generate the plot
    generate_steps_graph(random_vectors, clusters_vector, 1, MIN_LIMIT_POINTS, MAX_LIMIT_POINTS)

    for i in range(2, 10):

        # comparing if the centroide is the same for every cluster
        if clusters_vector != calculate_new_clusters_vector(random_vectors, clusters_vector):

            # generate the clusters for comparing which cluster is closer to the vectors
            clusters_vector = calculate_new_clusters_vector(random_vectors, clusters_vector)
        
            # asociate the vector to the closest cluster
            clustered_vectors = clustering_vectors(random_vectors, clusters_vector)

            # set the vector-cluster
            random_vectors[1] = clustered_vectors
        
            # generate the plot
            generate_steps_graph(random_vectors, clusters_vector, i, MIN_LIMIT_POINTS, MAX_LIMIT_POINTS)

        else:
            break

        

K-means
kk es igual a los can de agrupaciones

Estuve toda una tarde intentando programarlo y aquí está!

He exagerado el tamaño de las K para que se visualizará mejor 😄

Hola! 👋🏻
Para entenderlo, en términos generales, piénsalo así:
/

Inicialización: En la primera etapa del algoritmo, se seleccionan de forma aleatoria los puntos de los centroides iniciales. Estos centroides son los puntos que representarán el centro de cada grupo.

Asignación: En esta etapa, cada punto de datos se asigna al centroide más cercano. La distancia entre cada punto y los centroides se calcula utilizando alguna métrica, por lo general, la distancia euclidiana. Cada punto se asigna al grupo cuyo centroide está más cerca en términos de distancia.

Actualización de los centroides: Una vez que todos los puntos han sido asignados a los centroides más cercanos, se recalcula la posición de los centroides. Esto se hace tomando el promedio de las posiciones de todos los puntos asignados a cada centroide. El promedio se calcula en función de las características de los puntos (por ejemplo, coordenadas en un espacio multidimensional).

Repetición: Los pasos 2 y 3 se repiten iterativamente hasta que se cumpla algún criterio de convergencia, como cuando los centroides ya no se mueven o cuando se alcanza un número máximo de iteraciones.

Por lo tanto, en cada iteración, tanto los puntos de los centroides como la asignación de los puntos a los grupos se actualizan. Los puntos de los centroides se mueven hacia el centro de cada grupo en función de los puntos asignados a ellos, y los puntos de datos se asignan al centroide más cercano en cada iteración.

/

Es es la idea general de cómo funciona el algoritmo 😉

Me queda superclaro todos los conceptos y tambien que hay frameworks que pueden ejecutarlos, otra cosa es entender opr dentro las funciones que usan esos frameworks o programar de cero uno algo que haga dendogramas o k means

¡Aquí mi implementación!
https://github.com/Erik-Lopez/kmeans-implementation

https://www.jacobsoft.com.mx/es_mx/k-means-clustering-con-python/

en este link encontré ayuda para entender el tema de k-means, adicional para transcribir el código que use para este reto…gracias!!

![](

GRÁFICA:

![](

Documentación en sklearn
https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html

Este es mi código del k-means con matplotlib y algunas funciones extrasssss

from matplotlib import pyplot as plt
import numpy as np
import pandas as  pd 
import matplotlib.patches as patches
import random 

def generate_random_vectors():
    vectors = []
                                      #coords  #range x # range y  #TAM
    #a = np.random.multivariate_normal([10,0], [[3,1], [1,4]], size=[10,])
    #b = np.random.multivariate_normal([0,20], [[3,1], [1,4]], size=[10,])
    #for i in range(10): 
    #    vector = (a[i][0],a[i][1])
     #   vectors.append(vector)
      #  vector2 = (b[i][0],b[i][1])
       # vectors.append(vector2)
      #random_vectors = []
    for i in range(100):
        vectors.append((random.uniform(0, 15), random.uniform(0, 25)))
     
        
        
    return vectors
    

def distancia_euclidiana(d1,d2):
    x0=d1[0]
    x1=d2[0]
    y0=d1[1]
    y1=d2[1]
    return ((x1-x0)**2+(y1-y0)**2)**0.5

def plot(vector, color="red"):
    x=[]
    y=[]
    for coord in vector: 
        #print(coord)
        x.append(coord[0])
        y.append(coord[1])
    plt.scatter(x,y,color=color)
    #plt.show()

def puntos(punto, vectors): 
    vector_final = []
    for vector in vectors: 
        distancia = distancia_euclidiana(punto,vector)
        vector_final.append(distancia)     
    return vector_final

def matriz_distancias(vectors):
    index = 0
    matriz = []

    for vector in vectors: 
        vectores_obtenidos = puntos(vector, vectors)
        #print(vectores_obtenidos)
        index += 1
        matriz.append(vectores_obtenidos)
    data_df = pd.DataFrame(matriz)
    return data_df
    #print(matriz)
def punto_mas_cercano(coord,vector):
    cercano = 10000
    aux = (0,0)
    for i in vector:
        d = distancia_euclidiana(coord,i)
        if d !=0:
            if cercano>d: 
                cercano = d
                aux = i
                
    return aux


def vector_con_removidos(vector,coord,coord2): 
    vector_final = []
    for j in vector:
        if coord != j and coord2 != j:
            vector_final.append(j)
    
    
    return vector_final

def k_aleatorios(k):
    lista = []
    for i in range(k): 
        x = random.randint(-4, 14)
        y = random.randint(-5, 25)
        coords = (x,y)
        lista.append(coords)
    return lista

def k_definidos(vectores):
    x=[]
    y=[]
    for vector in vectores:
        x.append(vector[0])
        y.append(vector[1])
    mean_x = np.mean(x)
    mean_y= np.mean(y)
    return (mean_x,mean_y)

def obtener_k(matriz):
    lista = []
    for vector in matriz: 
        punto = k_definidos(vector)
        lista.append(punto)
        
    return lista

def vectores_agrupados(vectores, kas):
    matriz = []
    lista = []
    for k in kas: 
        matriz.append([])
    
    for vector in vectores: 
        dis_min = 1000 
        k_aux = (0,0)
        for k in kas:
            d = distancia_euclidiana(k,vector)
            if dis_min>d:
                dis_min = d            
                k_aux = k
        lista.append({k_aux:vector})
    for l in lista: 
        index = 0
        for k in kas: 
            if l.get(k): 
                matriz[index].append(l.get(k))
            index+=1
    for m in matriz: 
        if len(m)==0: 
            m.append((0,0))
            
    return matriz 

def vectores_iguales(matriz_anterior, matriz):
    index = 0
    bandera = False
    for m in matriz: 
        if m != matriz_anterior[index]:
            bandera = True
        else: 
            print("entra")
            bandera = False
        index +=1
    print(bandera)
    return bandera
    
    
if __name__ == '__main__':
    POINTS_COLOURS = ['turquoise', 'lime', 'dodgerblue', 'fuchsia', 'lightcoral', 'navajowhite']
    CLUSTERS_COLOURS = ['teal', 'green', 'blue', 'purple', 'red', 'goldenrod']
    vectors = generate_random_vectors()
    plot(vectors)
    K = 4 # GRUPOS
    kas = k_aleatorios(K)
    index = 0
    for i in kas:
        plt.scatter(i[0],i[1], color=CLUSTERS_COLOURS[index])
        index+=1
    plt.show()


    nuevos_k = kas
    matriz = vectores_agrupados(vectors,nuevos_k)
    matriz_anterior=[]
    for n in range(K):
        matriz_anterior.append([])
        
    while vectores_iguales(matriz_anterior, matriz): 
        matriz_anterior = matriz
        nuevos_k=obtener_k(matriz) 
        matriz = vectores_agrupados(vectors,nuevos_k)
        index = 0
        for i in nuevos_k:
            plt.scatter(i[0],i[1], color=CLUSTERS_COLOURS[index], s=100)
            if(len(matriz[index]) !=0):
                plot(matriz[index], color = POINTS_COLOURS[index])
            index+=1   
        plt.show()
    "ULTIMO PASO POR SI HAY UNA PEQUEÑA DIFERENCIA"
    nuevos_k=obtener_k(matriz) 
    matriz = vectores_agrupados(vectors,nuevos_k)
    index = 0
    plt.scatter([],[])
    plt.show()
    for i in nuevos_k:
        plt.scatter(i[0],i[1], color=CLUSTERS_COLOURS[index], s=100)
        if(len(matriz[index]) !=0):
            plot(matriz[index], color = POINTS_COLOURS[index])
        index+=1   
    plt.show()
    

Computacionalmente, este algoritmo, es muy pesado.

Una vez el algoritmo termina, solo es necesario ingresar datos, para que se determine en qué grupo está.

Los puntos que no se encuentran en el cluster, se les llama los out layers.

Lo importante no es ver el código, sino generar la intuición para usarlo e interpretarlo con tus propias soluciones.

Cuando ya no hay más mejoras, significa que el algoritmo hizo una convergencia.

El algoritmo repite el mismo proceso muchas veces hasta que ya no existan mejoras.

Una vez tenemos el centroide, se ajustan los puntos a este y luego de ello, se genera nuevamente un cálculo, para generar un nuevo centroide.

El algoritmo, una vez hecho el primer grupo, genera algo llamado el centroide, que es la media de las distancias del grupo.

Luego de localizar los puntos que vamos a analizar, el algoritmos calcula la distancia entre ellos.

K es el número de grupos, con los que queremos trabajar. Puede tomar los valores naturales, por lo que es un variable discreta.

Los K-means, también son otra manera de agrupar o clustering. Este algoritmo funciona por asignar puntos al azar y luego decidir cuántos grupos vamos a analizar, siendo esta la K.

Hola a todos, aquí dejo mi k-means.
Aquí una muestra de como gráfica los grupos. Los cuadrados son los centroides, vemos que los puntos que pertenecen a un grupo están coloreados del mismo color que el centroide.

Aquí una captura de la terminal que muestra como se recalculan los centroides:

Aquí el código:

from bokeh.plotting import figure, show
import random
import math

centroides_anteriores = []
centroides_actuales = []


def obtener_puntos(n_puntos):
    puntos = []
    for _ in range(n_puntos):
        x = random.randint(0, 20)
        y = random.randint(0, 20)
        punto = (x, y)
        puntos.append(punto)
    return puntos


def obtener_distancia_euclidiana(punto, punto_centroide):
    return math.sqrt((punto[0] - punto_centroide[0])**2 + (punto[1] - punto_centroide[1])**2)


def graficar_grupos(dict_centroides, grafica):
    for k, v in dict_centroides.items():
        color = ["#" + ''.join([random.choice('0123456789ABCDEF') for j in range(6)])]
        
        grafica.square(k[0], k[1], size=10, color=color)

        for punto in v:
            grafica.circle(punto[0], punto[1], size=6, color=color)


def agrupamiento(centroides, puntos, grafica, iteracion=0, dict_centroides = {}):
    global centroides_actuales, centroides_anteriores

    if iteracion != 0 and centroides_actuales != centroides_anteriores:
        nuevos_centroides = []

        centroides_enviados = []

        for centroide, lista_coordendas in centroides.items():

            centroides_enviados.append(centroide)

            suma_coordenadas_x = 0
            suma_coordenas_y = 0

            for coordenada in lista_coordendas:
                suma_coordenadas_x += coordenada[0]
                suma_coordenas_y += coordenada[1]
            
            promedio_coordenada_x = suma_coordenadas_x / len(lista_coordendas)
            promedio_coordenada_y = suma_coordenas_y / len(lista_coordendas)

            nuevo_centroide = (promedio_coordenada_x, promedio_coordenada_y)

            nuevos_centroides.append(nuevo_centroide)

        centroides_anteriores = centroides_enviados
        centroides_actuales = nuevos_centroides

        print(nuevos_centroides)
        print('*'*100)

        agrupamiento(nuevos_centroides, puntos, grafica, iteracion=0, dict_centroides=dict_centroides)
    elif iteracion == 0 and centroides_actuales != centroides_anteriores:
        distancias = {}
        distancias_agrupadas = {}
        
        for punto in puntos:
            distancias[punto] = []
            for centroide in centroides:
                distancia = obtener_distancia_euclidiana(punto, centroide)
                distancias[punto].append(distancia)

        for centroide in centroides:
            distancias_agrupadas[centroide] = []
        
        # clasificando elementos en sus respectivos centroides
        for k, v in distancias.items():
            distancia_mas_cercano = min(v)
            centroide_mas_cercano = centroides[v.index(distancia_mas_cercano)]
            distancias_agrupadas[centroide_mas_cercano].append(k)

        agrupamiento(distancias_agrupadas, puntos, grafica, iteracion=1, dict_centroides=distancias_agrupadas)
    else:
        graficar_grupos(dict_centroides, grafica)


def main(n_puntos, n_k):
    global centroides_actuales

    grafica = figure(title="Agrupamiento k-means")

    puntos = obtener_puntos(n_puntos)
    centroides = obtener_puntos(n_k)

    centroides_actuales = centroides

    agrupamiento(centroides, puntos, grafica)

    show(grafica)


if __name__ == '__main__':
    n_puntos = int(input('Número de puntos: '))
    n_k = int(input('Número de grupos: '))

    main(n_puntos, n_k)

Mi implementación de k-means con visualizaciones:

#Librerias a utilizar
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
import seaborn as sns
import random
import numpy as np

#Para dar formato a las gráficas
sns.set_theme()

# Variables para condiciones iniciales
n_puntos = 500
n_centros = 6
std = 0.9
semilla = 27
n_iteraciones = 25 #Iteraciones del algoritmo

#Creamos dataset sintetico 
X, y_true = make_blobs(n_samples = n_puntos, centers = n_centros, cluster_std = std, random_state = semilla)

#Visualizamos datos generados
fig = plt.figure(figsize = (7,7))
plt.xlabel("Eje X")
plt.ylabel("Eje Y")
plt.scatter(X[:, 0], X[:, 1], alpha = 0.5, s = 30)

#Seleccionamos aleatoriamente los centros (sin repetir)
ct = []
taken = []
random.seed(semilla)
for i in range(n_centros):
    index = random.randint(0, n_puntos)
    while index in taken:
        index = random.randint(0, n_puntos)
    taken.append(index)
    ct.append(list(X[index]))   
ct = np.array(ct)
    

#CICLO PRINCIPAL DE KMEANS -------------------------------
for i in range(n_iteraciones):
    
    #Matriz de pertenencia a cluster
    gamma = np.zeros([n_puntos, n_centros])
    
    #Clasificamos los puntos
    for j in range(n_puntos):
        dist = []
        for k in range(n_centros):
            dist.append(np.linalg.norm(X[j]-ct[k]))
    
        minima = dist.index(min(dist))
        gamma[j][minima] = 1
    
    #Reajustamos centros
    for j in range(n_centros):

        n_cluster = np.sum(gamma[:, j])
        ct[j] = np.inner(gamma[:, j], X.T)/n_cluster
     
#---------------------------------------------------------

#Creamos arreglo con etiquetas del dataset
etiquetas = []
for i in range(n_puntos):
    etiquetas.append(list(gamma[i]).index(1))

#Visualizamos el resultado del algoritmo
fig = plt.figure(figsize = (7,7))

plt.scatter(X[:, 0], X[:, 1], alpha = 0.5, s = 30, cmap = 'Dark2', c = etiquetas, label = 'Datos')
plt.scatter(ct[:, 0], ct[:, 1], color = 'black', s = 80, label = 'Centros obtenidos', alpha = 0.8)

plt.title('Clustering con K-Means | '+str(n_centros) +' centros | '+str(n_puntos)+' puntos.')
plt.xlabel("Eje X")
plt.ylabel("Eje Y")
plt.legend()

Notas 😄
Agrupamiento K-means.

• Es otro algoritmo de clustering. Agrupa utilizando centroides 🌒.
• Funciona inicializando los centroides al azar y después:
  • En cada iteración el punto se ajusta a su nuevo centroide y cada punto se recalcula con respecto de los centroides.
  • Los puntos se reasignan al nuevo centro.
  • El algoritmo se repite de manera iterativa hasta que ya no existen mejoras.
• Es necesario especificar inicialmente cuantos centros queremos (k). Esto es uno de los principales problemas, ya que si no se conoce a priori cuantos grupos esperamos, algunas veces es muy complicado de determinar 😢.
• Se detiene el algoritmo cuando este converge.
• Es importante notar que este algoritmo es muy costoso computacionalmente. Si se tienen muchos datos, se puede generar una muestra representativa y aleatoria 👀.

en este video y el anterior habla de feynman al final. Alguien me podría explicar?? entiendo lo que es la técnica de feynman pero que relación tiene con estos agrupamientos?? y precisamente cual es la idea en relación a lmplementar un algoritmo de la técnica de feynman?? porque lo que veo que hacen todos es simplemente hacer el algoritmo del agrupamiento que se explica en el video.

Hola, compuse el siguiente código buscando usar POO y la manera mas ágil y global del k-means. les agradecería si me pueden compartir sus observaciones sobre el.

<code>
class datos:
    def __init__(self,n):
        self.n=n

    def generar_datos(self):
        import random
        dato=[]
        for _ in range(self.n):
            x=random.randint(0,100)
            y=random.randint(0,100)
            dato.append([x,y])

        return dato

    def graficar(self,dato):
        from bokeh.plotting import figure, show
        fig=figure()
        for i in dato:
            fig.circle(i[0],i[1])
        show(fig)


def distancia(punto1,punto2):
    '''This function calculates the euclidean distance between two 2D points
        it takes the follwing parameters:
        punto1= takes a 2d tuple or list
        punto2= takes a 2d tuple or list
        '''
    return(abs(punto1[0]-punto2[0])**2+abs(punto1[1]-punto2[1])**2)**0.5

def kmeans(dato,centroides,iter):
    ''' This function calculates n(user input) 2-D k-means centroids after calculating
        k(user input) iterations.
        it takes the following parameters:
        dato= list of (x,y) coordenates describing data points
        centroides= integer of the n numer of centroids
        iter= integer of the k iterations
        Requirements: this function uses matplotlib library
        '''
    from statistics import mean
    import matplotlib.pyplot as plt
    centro=datos(centroides).generar_datos()
    for itera in range(iter):
        belong_c={}
        for r,i in enumerate(dato):
            distan={}
            for j,k in enumerate(centro):
                distan[distancia(i,k)]=j
            belong_c[r]=distan[min(distan.keys())]
        
        colores=['b','g','r','c','m','y','k','w']
        
        dato_final=[]
        for j,k in enumerate(centro):
            update=[dato[i] for i in belong_c.keys() if belong_c[i]==j]
            x=[i[0] for i in update]
            y=[i[1] for i in update]
            centro[j][0]=mean(x)
            centro[j][1]=mean(y)
            if itera==tuple(range(iter))[-1]:
                plt.scatter(x,y,color=colores[j])
                plt.scatter(centro[j][0],centro[j][1],color=colores[j],marker='*')
    plt.show()
    return centro
    
if __name__ == "__main__":
    a=datos(10000).generar_datos()
    k=kmeans(a,3,1000)
    print(k)

El output para los datos presentados fue el siguiente

Por aquí os dejo mi implementación de kmeans junto al código para que podáis probarlo y experimentar con el:
https://github.com/spanishkukli/kmeans
Cualquier observación es bienvenida 😀

Agrupamiento K-means

• Es un algoritmo que agrupa utilizando centroides.
• El algoritmo funciona asignando puntos al azar (K define el número inicial de clusters) y después:
  • En cada iteración el punto se ajusta a su nuevo centroide y cada punto se recalcula con la distancia respecto de los centroides (la media del grupo).
  • Los puntos se reasignan al nuevo centro.
  • El algoritmo se repite de manera iterativa hasta que ya no existen mejoras.
• Consideraciones:
  • Escoger un K que sea correcto, es decir, ¿Cuántos grupos yo quiero generar?
  • Esto es computacionalmente MUY pesado

Aquí dejo mi implementación:

from bokeh.plotting import figure, show, output_file
import random
from bokeh.palettes import Dark2_5 as palette
import itertools

class Punto:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def euclidean_distance(punto_a, punto_b):
    return ((punto_a.x - punto_b.x)**2 + (punto_a.y - punto_b.y)**2)**(1/2)

def k_means(points, centroids, past_clusters, counter):

    n_iteration = counter + 1
    print('ITERACION #', n_iteration)
    current_clusters =  list(list() for i in range(num_kmeans))
    cluster_folded = list()
    distance = list()

    for punto in points:
        for centroide in centroids:
            distance.append(euclidean_distance(punto, centroide))
        shortest_distance = min(distance)
        ncluster = distance.index(shortest_distance)
        current_clusters[ncluster].append(punto)
        distance = []
    for cluster in current_clusters:
        area_total = 0
        producto_area_x = 0
        producto_area_y = 0
     
        for punto in cluster:
            producto_area_x += (punto.y * (punto.x)**2)
            producto_area_y += (punto.x * (punto.y)**2)
            area_total += (punto.x * punto.y)
        centroids[current_clusters.index(cluster)] = Punto((producto_area_x/area_total), (producto_area_y/area_total))
    if(current_clusters == past_clusters):
        return [current_clusters, centroids, n_iteration]
    else:
        for cluster in current_clusters:
            cluster_folded += cluster
        return k_means(cluster_folded, centroids, current_clusters, n_iteration)
            
if __name__ == "__main__":

    num_kmeans = int(input("¿Cuántos clusters?"))
    num_puntos = int(input("¿Cuántos puntos?"))
    max_y = int(input("¿Cuál es el valor máximo para y?"))
    max_x = int(input("¿Cuál es el valor máximo para x?"))

    random_points = list(Punto(random.randint(0, max_x), random.randint(0, max_y)) for i in range(num_puntos))
    random_centroids = list( Punto(random.randint(0, max_x), random.randint(0, max_y)) for i in range(num_kmeans))
    
    k_means_result = k_means(random_points, random_centroids, list(list() for i in range(num_kmeans)), 0)
    final_clusters = k_means_result[0]
    final_centroids = k_means_result[1]

    #GRAFICANDO
    colors = itertools.cycle(palette)
    output_file("line.html")
    p = figure(plot_width=400, plot_height=400,)

    for cluster in final_clusters:
        selected_color = next(colors)
        p.circle_x(x=final_centroids[final_clusters.index(cluster)].x, y=final_centroids[final_clusters.index(cluster)].y, size=20, color=selected_color, fill_alpha=0.3)
        p.circle(list(punto.x for punto in cluster), list(punto.y for punto in cluster), size=5, color=selected_color, alpha=0.4)
    p.title.text = "Iteraciones: " + str(k_means_result[2])
    p.title.align = "center"
    p.title.text_font_size = "25px"

    show(p)

Comportamiento de K-means

¿Cómo se determina cuál es el número inicial de clusters?

https://www.youtube.com/watch?v=wiZjt0HIxKY

Aqui la web de SciLearn donde explican Kmeans https://scikit-learn.org/stable/modules/clustering.html#k-means

Y con la libreria de Kmean es esto xd

# K-Means Clustering

# Importacion de librerias
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

# Carga del conjunto de datos
dataset = pd.read_csv('Clientes_Tienda.csv')
X = dataset.iloc[:, [3, 4]].values

# Metodo del Codo para encontrar el numero optimo de clusters

from sklearn.cluster import KMeans
wcss = []
for i in range(1, 11):
    kmeans = KMeans(n_clusters = i, init = 'k-means++', random_state = 42)
    kmeans.fit(X)
    wcss.append(kmeans.inertia_)

# Grafica de la suma de las distancias
plt.plot(range(1, 11), wcss)
plt.title('The Elbow Method')
plt.xlabel('Number of clusters')
plt.ylabel('WCSS')
plt.show()

# Creando el k-Means para los 5 grupos encontrados
kmeans = KMeans(n_clusters = 5, init = 'k-means++', random_state = 42)
y_kmeans = kmeans.fit_predict(X)

# Visualizacion grafica de los clusters
plt.scatter(X[y_kmeans == 0, 0], X[y_kmeans == 0, 1], s = 100, c = 'red', label = 'Cluster 1')
plt.scatter(X[y_kmeans == 1, 0], X[y_kmeans == 1, 1], s = 100, c = 'blue', label = 'Cluster 2')
plt.scatter(X[y_kmeans == 2, 0], X[y_kmeans == 2, 1], s = 100, c = 'green', label = 'Cluster 3')
plt.scatter(X[y_kmeans == 3, 0], X[y_kmeans == 3, 1], s = 100, c = 'cyan', label = 'Cluster 4')
plt.scatter(X[y_kmeans == 4, 0], X[y_kmeans == 4, 1], s = 100, c = 'magenta', label = 'Cluster 5')

plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s = 300, c = 'yellow', label = 'Centroids')

plt.title('Clusters of customers')
plt.xlabel('Annual Income (k$)')
plt.ylabel('Spending Score (1-100)')
plt.legend()
plt.show()

#Solo funciona si tienes el dataset de la tienda jajaja```

Yo lo resolví de esta forma

from math import sqrt
from random import randint
import collections


class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def get_point(self):
        return (self.x, self.y)

    def point_print(self):
        return (f'p({str(self.x)},{str(self.y)})')

    def __repr__(self):
        return self.point_print()

    def __str__(self):
        return self.point_print()

    def search(self):
        print('This is a Point')


def ecuclidian_distance(point_a, point_b):
    return sqrt((point_a.x - point_b.x)**2 + (point_a.y - point_b.y)**2)


def calculate_centroid(points):
    x_coords = [p.x for p in points]
    y_coords = [p.y for p in points]
    _len = len(points)
    centroid_x = sum(x_coords) / _len
    centroid_y = sum(y_coords) / _len

    return Point(centroid_x, centroid_y)


def k_means(k, points, centroids, pci):

    print('*' * 30)
    print(f'Lista centroides :\n{centroids}')

    points_for_centroid_i = []  # Debe ser una lista de listas

    for _ in range(k):
        points_for_centroid_i.append([])

    # Loop para ver en punto a cuál centroide está más cerca
    for point in points:
        distance_to_centroid_i = []  # Debe ser una lista

        for centroid in centroids:
            distance_to_centroid_i.append(
                ecuclidian_distance(point, centroid))

        # Encontrar el mínimo de la lista y su índice para encontrar el centroide más cercano
        min_distance = min(distance_to_centroid_i)
        chosen_centroid = distance_to_centroid_i.index(min_distance)

        points_for_centroid_i[chosen_centroid].append(point)
    print(f'Las listas de puntos son {points_for_centroid_i}')

    # Comprobar si las nuevas listas son iguales a las anteriores
    equal_collections = 0
    for point_list in points_for_centroid_i:
        # Si la colección es igual a la referencia sumar al colector.
        if collections.Counter(point_list) == collections.Counter(pci[points_for_centroid_i.index(point_list)]):
            equal_collections += 1

    print(f'We have {equal_collections} equal collection points')

    # Si todas las colecciones son iguales salir
    if equal_collections == len(points_for_centroid_i):

        print('the lists are identical. Optimal process')
        return points_for_centroid_i

    print('the lists are NOT identical. ITERATE')

    # Calcular nuevo centroide
    centroids = []
    for point_list in points_for_centroid_i:
        centroids.append(calculate_centroid(point_list))
    print(f'Los nuevos centroides son {centroids}')

    # Iterar
    k_means(k, points, centroids,
            points_for_centroid_i)


if __name__ == '__main__':
    # Número de conjuntos
    k = 4
    num_points = int(input('Ingrese la cantidad de puntos a generar: '))

    # Arreglo de puntos vacíos para inicializar
    points = []

    # Generación de puntos aleatorios
    for _ in range(num_points):
        point = Point(randint(0, 15), randint(0, 15))
        points.append(point)
    print(f'Lista inicial de puntos :\n{points}')

    centroids = []
    points_for_centroid_i = []

    for _ in range(k):
        centroid = Point(randint(0, 15), randint(0, 15))
        centroids.append(centroid)
        points_for_centroid_i.append([])
    print(f'Lista inicial de centroides :\n{centroids}')

    k_means(k, points, centroids, points_for_centroid_i)

Aqui esta mi implementacion de K-means usando Bokeh

import random
import math
from bokeh.plotting import figure, output_file, show

def generate_points(n):
	points = []
	for i in range(1,n+1):
		x = random.randint(0,100)
		y = random.randint(0,100)
		point = {
			'name': f'p{i}',
			'coords': (x, y)
		}
		points.append(point)

	return points

def init_centroids(k, points):
	points_list = points[:]
	centroids = []
	for i in range(k):
		centroid = random.choice(points_list)
		points_list.remove(centroid)
		centroids.append({
			'name': f'c{i}',
			'coords': centroid['coords']
		})

	return centroids

def find_closest_centroid(point, centroids):
	centroid_points = []
	for centroid in centroids:
		distance = math.sqrt((point['coords'][0] - centroid['coords'][0])**2 + (point['coords'][1] - centroid['coords'][1])**2)
		centroid_points.append({
			'distance': distance,
			'coords': point['coords'],
			'centroid': centroid['name']
		})

	centroid_points = sorted(centroid_points, key=lambda k: k['distance'])

	return centroid_points[0]

def group_points_with_closest_centroid(points, centroids):
	group = {}

	for centroid in centroids:
		group[centroid['name']] = []

	for point in points:
		result = find_closest_centroid(point, centroids)
		group[result['centroid']].append({
			'distance': result['distance'],
			'coords': result['coords']
		})

	return group

def calculate_centroid_mean(centroid_points):
	x = 0
	y = 0

	for centroid_point in centroid_points:
		x += centroid_point['coords'][0]
		y += centroid_point['coords'][1]

	coords = (x / len(centroid_points), y / len(centroid_points))

	return coords

def plot(points, centroids):
	p = figure(plot_width=400, plot_height=400)
	p.circle([point['coords'][0] for point in points], [point['coords'][1] for point in points], size=10, color="black", alpha=0.5)
	p.circle([centroid['coords'][0] for centroid in centroids], [centroid['coords'][1] for centroid in centroids], size=10, color="green", alpha=1)
	show(p)

if __name__ == '__main__':
	points_number = int(input('Insert points number to generate: '))	
	points = generate_points(points_number)
	k = int(input('Insert k: '))

	centroids = init_centroids(k, points)

	can_move_center = True

	while can_move_center:
		group = group_points_with_closest_centroid(points, centroids)

		can_move_center = False
		for i in range(len(centroids)):
			centroid_name = centroids[i]['name']
			coords = calculate_centroid_mean(group[centroid_name])

			if centroids[i]['coords'] != coords:
				can_move_center = True

			centroids[i]['coords'] = coords

	plot(points, centroids)

¿Cuáles serían las diferencias entre aplicar, ejecutar o implementar un algoritmo?

https://developers.google.com/machine-learning/clustering/clustering-algorithms#centroid-based-clustering

Acá pueden encontrar los gifs de las clases junto a sus respectivas explicaciones

https://dashee87.github.io/data science/general/Clustering-with-Scikit-with-GIFs/

Aquí mi implementación, devuelve los centroides y un arreglo con los grupos de cada punto; también acepta datos multidimensionales.

import math
import random

def euclidean_distance(u, v):
    assert len(u) == len(v)
    diff = [u[i] - v[i] for i in range(len(u))]
    sq = [d ** 2 for d in diff]
    return math.sqrt(sum(sq))

def kmeans(points, k=3, distance=euclidean_distance):
    dim = len(points[0])
    centroids = [[random.random() for _ in range(dim)] for _ in range(k)]
    clusters = [-1 for _ in range(len(points))]
    prev_clusters = [-1 for _ in range(len(points))]

    changed = True
    while changed:
        dists = [[distance(points[i], centroids[j]) for j in range(k)] for i in range(len(points))]
        print(f'Distances: {dists}')

        clusters = [dists[i].index(min(dists[i])) for i in range(len(points))]
        print(f'Current clusters: {clusters}')

        compare_all = [True if clusters[i] != prev_clusters[i] else False for i in range(len(points))]
        changed = any(compare_all)

        prev_clusters = clusters.copy()

        print(f'Current centroids: {centroids}')
        for i in range(k):
            cluster_points = [points[j] for j in range(len(clusters)) if clusters[j] == i]
            if len(cluster_points) > 0:
                centroids[i] = [sum([p[j] for p in cluster_points]) / len(cluster_points) for j in range(dim)]
        print(f'Modified centroids: {centroids}')

    return centroids, clusters

if __name__ == "__main__":
    dim = 1
    size = 10
    points = [[random.randint(0, 10) for _ in range(dim)] for _ in range(size)]
    
    print(f'Points: {points}')

    print(80*'=')
    centroids, clusters = kmeans(points, k=3)
    print(80*'=')

    print(f'Centroids: {centroids}')
    print(f'Clusters: {clusters}')

Se me ocurre que este algoritmo se puede usar con el giroscopio de un celular para programar una regla para medir niveles de superficie.

Comparto mis NOTAS:
Es un algoritmo que agrupa utilizando centroides.
El algoritmo funciona asignando puntos al azar (k define el numero inicial de clusters) y después:
-En cada iteración el punto se ajusta a su nuevo centroide y cada punto se recalcula con la distancia con respecto de los centroides.
-Los puntos se reasignan al nuevo centro.
-El algoritmo se repite de manera iterativa hasta que ya no existe mejoras.
Consideraciones:
Escoger un “k” que sea correcto para poder llegar a un agrupamiento relevante.
Esto es computacionalmente muy pesado, es por eso la importancia de nuestro conocimiento del muestreo.

No se si esto pueda ayudar pero por logica y segun los calculos matematicos, si generas centros aleatorios lo mejor que puedes hacer es intentar guiar esos centros a la media de todos los puntos del grupo, y sí se que puede haber problemas cuando los datos estan muy dispersos pero si haces que la resta entre la varianza optima y la varianza del centro aleatorio sea proporcional a que tan lejos estará el siguiente centro aleatorio no solo evitaras quedarte en un lugar con poca densidad de puntos de datos sino que en el momento en que llegues a una zona con una alta densidad de puntos te será mas facil llegar al centro optimo.

Una de las dificultades del método es seleccionar los K clusters, existe un método llamado K-means++ y el método del codo que sirve para ayudar en este problema, los pasos son los siguientes:

1. Selecciona el primer centroide aleatoriamente escogiendo un valor del dataset.
2. Calcula la distancia de cada punto X con el centroide.
3. Escoge un nuevo centroide utilizando distribución de probabilidad ponderada para el cuadrado de las distancias
4. Repite los pasos 2 y 3 hasta seleccionar K centroides.

El output final sería una gráfica como la siguiente:

En donde el número óptimo de clusters K se define como el punto donde se presenta la mayor inflexión en la gráfica, que en el caso de la gráfica anterior sería K=5.

Les dejo un recurso para leer más sobre el número óptimo de clusters K

Creo que el BIG O seria O(nki) donde n seria el tamaño de la muestra y k el número de grupos

Dejo mi implementación. En ella le pido al usuario el número de grupos o clusters. Después se generan los centroides y los puntos de manera aleatoria (en un problema real los puntos serían una lista de propiedades obtenidas previamente).
La función clustering asigna cada punto al centroide que tenga más cerca, y una vez asignados todos los puntos a un grupo se recalculan los centroides. Esto se repite hasta que ningún punto cambie de grupo.

import random
import math


def generate_random_points( number_points ):

    points = []

    for _ in range( number_points ):
        x_coord = random.randint(0, 50)
        y_coord = random.randint(0, 50)

        point = (x_coord, y_coord)
        points.append( point )

    return points


def euclidean_distance( point1, point2 ):

    x_diff = point1[0] - point2[0]
    y_diff = point1[1] - point2[1]

    distance = math.sqrt( x_diff**2 + y_diff**2 )

    return distance


def clustering( points, centroids ):

    groups = {}

    for i in range( len(centroids) ):
        groups[i+1] = []

    all_distances = []
    for i in range( len(points) ):

        distances = {}

        for j in range( len(centroids) ):
            distances[j+1] = euclidean_distance( points[i], centroids[j] )

        for key, value in distances.items():
            if value == min( distances.values() ):
                groups[key].append( points[i] )
                print(f'The point {points[i]} go to group {key}')

        all_distances.append(distances)

    return groups


def calculate_centroid( points ):

    sum_x = 0
    sum_y = 0

    for i in range( len(points)):
        sum_x += points[i][0]
        sum_y += points[i][1]

    centroid_x = round( sum_x / len(points), 2 )
    centroid_y = round( sum_y / len(points), 2 )

    centroid = ( centroid_x, centroid_y )

    return centroid
    


def run():
    
    k = int( input('Type the number of clusters: ') )

    points = generate_random_points(20)
    centroids = generate_random_points(k)

    print('First centroids: ')
    print(centroids)
    print('Points to cluster: ')
    print(points)
    print('-----------------------')
    
    all_groups = [{},{'All': points}]

    counter = 1

    while all_groups[counter] != all_groups[counter-1] or counter < 3:

        groups = clustering(points, centroids)
        all_groups.append( groups )
        print('GROUPS')
        print(groups)
        
        for i in range( len(groups) ):
            if len( groups[i+1] ) > 0:
                centroids[i] = calculate_centroid( groups[i+1] ) 

        print('CENTROIDS')
        print(centroids)
        print('-------------------------------')

        counter += 1

    print( all_groups )


if __name__ == '__main__':
    run()

Entiendo que este sea un curso basico o introductorio, pero dejan conceptos muuuuy al azar. Realmente buscando cualquier explicacion en youtube se entiende mejor que como lo explica David aca. Faltan atar muchos cabos.

Un poco mas claro 😃

https://www.youtube.com/watch?v=EZOab1vkFmI

Aquí va un código, copie parte del principio del creado por el compañero Facundo Nicolás García en la clase anterior, y desarrollé K-means sobre él

import random
import math
from bokeh.plotting import figure, show


class Vector:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def get_coordinates(self):
        return (self.x, self.y)

    def __str__(self):
        return f'{self.x}#{self.y}'


def generate_random_vectors(N):
    vectors = []
    for _ in range(N):
        vector = Vector(random.randint(0, 500), random.randint(0, 500))
        vectors.append(vector)
    return vectors


# We can use euclidian distance because we are dealing with a cartesian plane
def get_euclidian_distance(vector_a, vector_b):
    return math.sqrt((vector_a.x - vector_b.x)**2 + (vector_a.y - vector_b.y)**2)

def initialize_centers(K,vecs):
    centers = []
    vecs2 = vecs.copy()
    for _ in range(K):
        chosen = random.choice(vecs2)
        centers.append(chosen)
        vecs2.remove(chosen)
    return(centers)

def run():
    cluster_number = 3
    vectors = generate_random_vectors(5000)
    iterations = 20
    color_i = ["navy","crimson","goldenrod","green","purple","black"]

    # Generating a graph of the vectors with bokeh
    x_points = [vector.x for vector in vectors]
    y_points = [vector.y for vector in vectors]

    p = figure(plot_width=800, plot_height=800)

    # add a circle renderer with a size, color, and alpha
    p.circle(x_points, y_points, size=20, color="navy", alpha=0.5)

    # show the results
    show(p)

    
        
    # First, I define a first cluster formed by a first random vector
    centers = initialize_centers(cluster_number,vectors)
    last_centers = centers.copy()
    cont = 0
    while cont < iterations:
        clusters = []
        cont += 1
        for _ in range(cluster_number): clusters.append([])
        i = 1
        print()
        print(f'iteration number {cont}')
        for center in centers:
            print(f'center{i} = [{center.x},{center.y}]')
            i += 1

        for vector in vectors:
            index = 0
            group = 0
            dist = 99999999999999
            for center in centers:
                dist_aux = get_euclidian_distance(center,vector)
                if(dist > dist_aux):
                    group = index
                    dist = dist_aux
                index += 1
            clusters[group].append(vector)
        index = 0
        p = figure(plot_width=800, plot_height=800)
        for clus in clusters:
            #print(f'group{index}:')
            x_count = 0
            y_count = 0
            for element in clus:
                #print(f'vec = [{element.x},{element.y}]')
                x_count += element.x
                y_count += element.y
            centers[index] = Vector(x_count/len(clus),y_count/len(clus))
            index += 1
            # add a circle renderer with a size, color, and alpha
            x_points = [vector.x for vector in clus]
            y_points = [vector.y for vector in clus]
            p.circle(x_points, y_points, size=20, color=color_i[index], alpha=0.5)
        # show the results
        show(p)
        equals = 0
        for k in range(len(centers)):
            if centers[k].x != last_centers[k].x or centers[k].y != last_centers[k].y:
                break
            else:
                equals += 1
            print()
        if equals == len(centers):
            cont = iterations + 10
            break
        last_centers = centers.copy()
            

    

if __name__ == "__main__":
    run()

Me pasó algo interesante.
el la clase anterior sobre agrupamiento jerárquico nos pidió el profe david que implementemos algún algorímo que simule ese tipo de agrupamiento.
el primero dia lo pude hacer pero luego me di cuenta de que no podía meterle cualquier cantidad de puntos y además los agrupamientos la mayoria de veces no eran correctos.
el segun día comencé a pensar y escribir en mi pizarra otra forma de lograrlo y despues de 2 horas lo terminé y fué entonces cuando pasé a código lo que habia escrito y ví que funcionó perfectamente como yo habia pensado.
al dia siguiente ví la clase de agrupamiento K-means y cuando el profe david lo explico me dije: “uhmm, este tipo de agrupamiento se parece mucho al pensamiento que yo tuve respecto al agrupamiento jerárquico”, y justo despues de que pensé eso me di cuenta de que agregando 1 linea más de código yo ya tendría el código que simula el agrupamiento K-means.
osea, hice el algorítmo para el agrupamiento K-means sin haberlo conocido antes ya que lo hice pensando que hice el algoritmo para el agrupamiento jerárquico.
y lo mejor de todo es que no necesité ninguna librería para el algoritmo.
solamente usé random para crear puntos aleatorios y bokeh para graficar.
pero en sí puedo darle los puntos que yo quiera sin usar random de igual manera…

Este video explica muy bien K-means: https://youtu.be/SwVCfiJNfwg

Muy buen tema, hay que conocer los diferentes algoritmos y definir cuál es mejor para resolver nuestro problema

Aquí dejo mi versión del agrupamiento k-means:
https://github.com/Angrub/Algoritmos-de-agrupamiento.git

Comparto el ejemplo presentado en: https://www.jacobsoft.com.mx/es_mx/k-means-clustering-con-python/ y desarrollado en https://colab.research.google.com/notebooks/intro.ipynb

# K-Means Clustering

# Importacion de librerias
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

# Carga del conjunto de datos
dataset = pd.read_csv('Mall_Customers.csv')
X = dataset.iloc[:, [3, 4]].values

# Metodo del Codo para encontrar el numero optimo de clusters

from sklearn.cluster import KMeans
wcss = []
for i in range(1, 11):
    kmeans = KMeans(n_clusters = i, init = 'k-means++', random_state = 42)
    kmeans.fit(X)
    wcss.append(kmeans.inertia_)

# Grafica de la suma de las distancias
plt.plot(range(1, 11), wcss, c= 'b', marker='o', mfc='red')
plt.title('The Elbow Method')
plt.xlabel('Number of clusters')
plt.ylabel('WCSS')
plt.show()

# Creando el k-Means para los 5 grupos encontrados
kmeans = KMeans(n_clusters = 5, init = 'k-means++', random_state = 42)
y_kmeans = kmeans.fit_predict(X)

# Visualizacion grafica de los clusters
plt.scatter(X[y_kmeans == 0, 0], X[y_kmeans == 0, 1], s = 100, c = 'red', label = 'Cluster 1')
plt.scatter(X[y_kmeans == 1, 0], X[y_kmeans == 1, 1], s = 100, c = 'blue', label = 'Cluster 2')
plt.scatter(X[y_kmeans == 2, 0], X[y_kmeans == 2, 1], s = 100, c = 'green', label = 'Cluster 3')
plt.scatter(X[y_kmeans == 3, 0], X[y_kmeans == 3, 1], s = 100, c = 'cyan', label = 'Cluster 4')
plt.scatter(X[y_kmeans == 4, 0], X[y_kmeans == 4, 1], s = 100, c = 'magenta', label = 'Cluster 5')

plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s = 300, c = 'yellow', label = 'Centroids')

plt.title('Clusters of customers')
plt.xlabel('Annual Income (k$)')
plt.ylabel('Spending Score (1-100)')
#plt.legend()
plt.show()

Excelente