Contenido del curso
Algoritmo K-means: Conceptos y Aplicación Práctica
¿Qué es el algoritmo K-means?
El algoritmo K-means es uno de los métodos más populares para el agrupamiento de datos, utilizado especialmente en el análisis exploratorio y minería de datos. Se enfoca en la tarea de dividir un conjunto de puntos en ( K ) grupos o clústeres. Aquí, ( K ) representa el número de clústeres a formar, decisión que dependerá del contexto o problema específico a resolver.
¿Cómo funciona el algoritmo K-means?
El proceso comienza asignando \textit{randomly} un ( K ) número de puntos que actuarán inicialmente como los centros de los grupos. Luego, se miden las distancias entre todos los puntos respecto a estos centros y se asigna cada punto al clúster más cercano.
¿Qué consideraciones debemos tener en cuenta al implementar K-means?
Implementar K-means conlleva algunas consideraciones importantes:
¿Cómo afecta la variabilidad en K-means?
La variabilidad dentro de cada clúster se evalúa generalmente de manera similar a la varianza, con la diferencia de que no se normaliza dividiendo entre el total de puntos. Esta equidad hace que clústeres más grandes tengan un peso mayor, un aspecto a considerar durante el análisis de los resultados.
¿Qué son los outliers en el contexto de K-means?
Durante el proceso de agrupamiento, pueden aparecer puntos que no se ajustan claramente al centro de ningún clúster. Estos puntos, conocidos como outliers, presentan desafíos, ya que pueden ser elementos aislados o indicadores de patrones no evidentes.
Ejecución del método de Feynman en K-means
Una recomendación esencial al aprender a aplicar K-means es implementar el método de Feynman, que implica usar el algoritmo en situaciones simplificadas y verificar rápidamente los resultados. Esto ayuda a desarrollar una comprensión más profunda del comportamiento del algoritmo y facilita la mejora de intuiciones necesarias para su uso efectivo.
Dado que el algoritmo K-means es una potente herramienta para el análisis de datos, es crucial comprender su funcionamiento, limitaciones y consideraciones específicas para aplicarlo con éxito.
Oyarzabal Ivan
Estudiante
Juan Alonso Alcala
Estudiante
Miguel Reyes
Estudiante
Angel Armando Martínez Blanco
EstudianteAngel Armando Martínez Blanco
Estudiante
Luis Fernando Pedroza Taborda
Estudiante
johan Stever Rodriguez Molina
Estudiante
Miguel Andres Rendon Reyes
Estudiante
Carli Code
Profesor
Ovidio Bolivar Jaramillo J.
Estudiante
Christian Daniel Ayala Arias
Estudiante
Angelica Landazabal
Estudiante
Juan Camilo Alvarez Jurado
Estudiante
Iván Ricardo Bohórquez Basto
Estudiante
Miguel Torres
EstudianteIván Ricardo Bohórquez Basto
EstudianteMiguel Torres
Estudiante
Ramón Ruiz
Estudiante
Jhon Freddy Puentes Nuñez
EstudianteMiguel Torres
Estudiante
Jhon Fredy Moofarry Villaquiran
EstudianteMiguel Torres
EstudianteOyarzabal Ivan
Estudiante
mauricio jaime rodriguez teran
Estudiante
Luis Ángel Pérez Meléndez
Estudiante
Santiago Velez
Estudiante
Hector F
Estudiante
Daniel Miranda
EstudianteAngel Armando Martínez Blanco
Estudiante
Paul Bravo
Estudiante
Usuario anónimo
UserDaniel Miranda
Estudiante
JAVIER SANTIAGO SALGADO
Estudiante
María José Medina
Estudiante
JESUS ALBERTO CARREÑO MARTINEZ
Estudiante
Josue Noha Valdivia
Estudiante
Kevin Liao
Estudiante
Carlos Fernando Aguilar González
Estudiante
Javier Reina
Estudiante
Alejandro Cuello Maure
EstudianteJavier Reina
Estudiante
Brais Bea Mascato
Estudiante
David Jaramillo Saldarriaga
EstudianteBrais Bea Mascato
Estudiante
Carlos Esquivel
EstudianteSi 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/
Si me ayudo . Muy didáctico
Excelene
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)
Quise decir, un ambiente virtual con Bokeh instalado jajaja Esta bien chido se los juro :D
Angel, muchas gracias por compartir tu codigo, esta genial.
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.
Osea que un dato nunca va quedar fuera de un grupo y eso puede causar problemas de presición?
Este articulo me ayudó a entender mucho mejor el algoritmo:
Gracias por compartir el articulo
Está muy completo, gracias¡¡¡
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
Excelente recurso. ¡Gracias!
Súper útil!!!
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)
Hola, decidí escribir tu código y correrlo. Hasta el momento me salen varios errores. Dentro de lo que he visto, veo que mezclas redacción en inglés y en español para lo que se imprimiría en pantalla.
Por ahora termino así. Mañana chequeo y hago ajustes a ver que sale y como puedo correrlo funcionalmente.
Gracias por el feedback, @iRick2B. Al terminarlo quedaron unos detalles a mejorar.
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:
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:
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/ :D
Este curso se encuetnra en alguna ruta de aprendizaje? No lo habia visto
Por ahora no está en ninguna ruta. Antes estaba en la Ruta de Data Science. Podrías tomarlo después de terminar el tercer módulo de cursos de la Escuela de Data Science para que pruebes lo que has aprendido en el resto de la ruta, pero ahora en el lenguaje R. :)
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()
BUEN APORTE
trato de hacer el codigo pero ni puedo acercarme a lo que hiciste. ni se como comenzar
Como sabes cual es la K optima?
Si sabes en cuántos grupos estás dividiendo datos, esa es tu K.
Si no conoces el K puedes usar el método del codo: Graficando la distancia que hay en total entre los puntos y sus respectivos centroides, queda una gráfica como la siguiente:
Hazme saber si tienes alguna duda ;)
También existe el método de la silueta, similar al método del codo, se calcula una métrica para cada valor de K que representa lo bien que se han agrupado los puntos, pero en el caso de la silueta se escoge el valor K que aparezca con el valor más alto.
Más info.
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
El agrupamiento k-means es supervisado o es no supervisado? La posición de los k iniciales deben ser aleatorias?
no supervisado
K-Means es no supervisado y la forma más común de inicializar los centroids es forma aleatoria, también hay métodos avanzados para tratar de inicializarlos los más cercano al óptimo posible.
Nos pueden dejar los gif en los enlaces? o darnos la referencia de donde estan, son muy cool
Algoritmo k-Means
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.
Hola Kevin
Te felicito, lo dejaste documentado perfectamente.
Saludos
Puedo concluir que los vectores son las características o parámetros que defino para que se unan estos puntos?
Estoy algo perdido agradezco su ayuda!
Los vectores, son los datos de cada individuo, quiero que pienses en como clasificarias usuarios por sus gustos, compras, edad etc, que caracteristicas usarias para "describirlos", tal vez numero de compras, edad, total de compras, genero de peliculas .
Esas variables hay que encontrar una manera de representarlas numericamente, ejemplo:
Esos datos que tenemos ahora los podemos manejar como "coordenadas", o puntos que podemos usar para poder representarlos en una grafica.
Ejemplo: [10, 25, 1000, 1]
Con esos datos describimos al usuario , y como tenemos muchos usuarios los podemos representar en un plano.
A partir de aqui lo que queda es clasificar, agrupar, etc.
Vector es la forma de "explicar y representar" algo, ya sean usuarios u otra cosa. La distancia es el criterio que usamos para definir como agruparlos.
AlejoCm! Muchas gracias por esa exelente explicación, muy valiosa.
Entiendo que el la big O de este algoritmo sería de tipo exponencial no?. ya que sería algo como o(n^k), siendo n el tamaño de la muestra y k el número de clusters en los que se debe agrupar los datos.
Yo también pensé en un principio que es exponencial. Pero al parecer no hay un consenso sobre el big O de k-means.
En este estudio hicieron que un algoritmo k-means con O(n**2) tuviera un comportamiento lineal.
En varios foros definen la complejidad como O(n * k * i), donde n es el número de elementos, k los grupos e i la cantidad de iteraciones.
La primera asignación de de los centroides es aleatoria, pero una vez se hace está asignación en base a que se reasigna la posición de los centroides?. Por lo que entiendo esta re-asignación no es totalmente azarosa ya que simplemente se desvía ligeramente de la posición anterior del centroide, no?.
En la base a la cercania de los elementos que compone la clase en este sistema. Si tiene un conjunto de datos con 3 clases direfenetes los centroidodes van a tratar de buscar la posicion que refleje la menor distancia respecto a los elementos de esa clase, por lo que este tipo de cluster se basa enteramente en distancias.
