¿Qué es el algoritmo de K-means y cómo funciona?

Clase 5 de 27 • Curso de Clustering con Python y scikit-learn

Clase anteriorSiguiente clase

johan Stever Rodriguez Molina

student•

Un par de observaciones que pueden servir.

Kmeans es un método basado en “distancias”, luego el calculo en cada iteracion se puede ver afectado ante la existencia de outliers.
Es costoso a nivel computacional cuando la cantidad de datos aumenta, ya que implica comparar cada dato con todos los demás.
Tiene un problema grave y es que a cada punto NECESARIAMENTE lo ubica dentro de un cluster. Si tenemos un outlier nunca lo vamos a percibir por que lo va a asignar a un cluster

Juan R. Vergara M.

student•

Gracias por el aporte 📝🥇

Luis Irigoyen

student•

Para el punto 1 y 3 se puede reducir bastante el margen de error con un buen manejo de outliers.

Nixon Rolando García Ramírez

student•

Jajaja cuando hasta una animacion te da resultados dudosos jajaja 😔.

Astin severino

student•

K-means es un algoritmo de clustering o agrupamiento no supervisado que tiene como objetivo dividir un conjunto de puntos en K grupos (o clusters), en el que cada punto pertenece al grupo cuyo valor medio es más cercano. El "valor medio" aquí se refiere al promedio de los puntos y se llama "centroide".

Cómo funciona:

Inicialización: Se seleccionan K puntos al azar como centroides iniciales. Estos pueden ser puntos aleatorios o una selección aleatoria de puntos del conjunto de datos.
Asignación: Cada punto se asigna al centroide más cercano.
Actualización de centroides: El centroide de cada cluster se recalcula como el promedio de todos los puntos asignados a ese cluster.
Repetición: Los pasos 2 y 3 se repiten hasta que los centroides no cambien significativamente en iteraciones consecutivas o hasta que se cumpla alguna otra condición de parada (como un número máximo de iteraciones).
Resultado: Una vez que el algoritmo se detiene, tendremos K clusters con puntos asignados a cada uno de ellos.

Visualización:

Paso 1: Inicialización

Paso 2 y 3: Asignación y Actualización

Consideraciones:

La elección inicial de centroides puede afectar el resultado. Por lo tanto, a menudo se ejecuta el algoritmo varias veces con diferentes inicializaciones y se elige el resultado con el valor más bajo de la función objetivo.
Es importante preprocesar los datos (por ejemplo, normalizarlos) antes de aplicar K-means, ya que el algoritmo es sensible a la escala de las características.
El número de clusters, K, debe ser determinado previamente. A veces, el valor óptimo de K se determina usando técnicas como el "método del codo".
K-means puede no funcionar bien cuando los clusters tienen formas no esféricas o tamaños muy diferentes.

Carlos Mazzaroli

student•

No sera mucho aporte este comentario por que tiendo a realizar mi resumen completo con los proyectos. Pero como siempre dije y digo en estos cursos, Carlos sos de las mejores personas que vi en esta plataforma explicando temas, siempre estuve el pendiente por que hace cuando empecé a estudiar Web Dev hacia los cursos del profe Sergio Orduz de matemáticas por gusto propio, y sentí que faltaba esa calidad de profesor y manera extensa de explicar las cosas, por que armaban cursos muy al punto y se sentían como si buscara un tutorial paso a paso en medium de cómo hacer un X en especifico y ya. Muy lindo tener un profe como vos en la plataforma :) 10/10

Santiago Ahumada Lozano

student•

Hola, ¿Qué pasa si tras generar aleatoriamente los centroides iniciales, ningún punto es clusterizado con el grupo de alguno de los centroides? ¿No se daña la convergencia del algoritmos? Me gustaría saber si hay una manera estándar de generar los centroides iniciales (si hay código mejor) ¡Gracias!

Santiago Ahumada Lozano

student•

Creo que esta función de numpy puede ayudar

np.random.uniform(-min, max, size=(10, 2))

Donde min y max son los topes a los que pueden llegar los datos

Santiago Ahumada Lozano

student•

¿Se reemplazarían sólo las medias asociadas a los clusters no vacíos?

Juan Acevedo

student•

Algo interesante que veo de la formula planteada y es que esa es una formula para ver en general que tan bien es el clsutering ya que es la suma de las distancias totales de cada uno de los culsters, ya para que sea la distancia a un punto en especial sería

la raíz de x - c al cuadrado , donde x el punto del cluster y c el centroide del cluster

Mario Alexander Vargas Celis

student•

El algoritmo de K-Means es uno de los algoritmos de clustering más populares en machine learning no supervisado. Su objetivo es dividir un conjunto de datos en K grupos (clústers), donde cada grupo contiene puntos que son similares entre sí y diferentes de los de otros grupos.

🧠 ¿Qué hace K-Means?

Dado un número K (el número de clústers deseado), el algoritmo agrupa los datos de forma que se minimice la distancia de cada punto a su centroide (el "centro" del clúster).

⚙️ ¿Cómo funciona K-Means? (Pasos)

Inicialización:
- Escoge K puntos aleatorios como centroides iniciales (uno por clúster).
Asignación de clústers:
- Cada punto se asigna al clúster más cercano (usando, por ejemplo, distancia euclidiana).
Actualización de centroides:
- Se recalcula el centroide de cada clúster como el promedio de los puntos asignados a él.
Repetir:
- Repite los pasos 2 y 3 hasta que:
  - Los centroides ya no cambian significativamente, o
  - Se alcanza un número máximo de iteraciones.

📈 Ejemplo visual

Imagina un conjunto de puntos dispersos. K-Means:

Coloca 3 puntos aleatorios como centroides (si K = 3).
Agrupa los puntos según cercanía a esos centroides.
Recalcula los centroides.
Repite hasta que las posiciones de los centroides se estabilicen.

✅ Ventajas

Fácil de entender e implementar.
Funciona bien con clústers esféricos y separados.
Rápido incluso con grandes conjuntos de datos.

⚠️ Limitaciones

Tienes que definir K previamente.
Es sensible a:
- Outliers
- Inicialización aleatoria (puede converger a soluciones subóptimas).
Asume que los clústers son de forma redonda y de tamaño similar.

🔍 ¿Cuándo usarlo?

Segmentación de clientes.
Agrupamiento de imágenes.
Análisis exploratorio de datos.

Santiago Ahumada Lozano

student•

Programé este algoritmo desde 0 pero hay centroides ignorados (Deberian ser 10) ...alguna idea?

Santiago Ahumada Lozano

student•

Giovany samaca

student•

Hola Santiago.

Veo que hay demasiados clusters, por la grafica veo que es mas viable implementar el algoritmo con cuatro o tres clusters para que los centroides no sean ignorados y la clusterizacion sea mas acertiva.

Alfredo Olmedo

student•

Complejidad algoritmica temporal

El algoritmo K-means no realiza una iteración completa por cada centroide de manera individual, sino que actualiza los centroides y asigna los puntos a los clústeres en un ciclo iterativo.

La complejidad temporal de K-means se determina principalmente por dos procesos:

Asignación de puntos a los centroides más cercanos, lo cual tiene una complejidad de O(n \* k \* d) donde n es el número de puntos de datos, k es el número de centroides (clústeres) y d es la dimensión de los datos.
Recalcular los centroides en función de los puntos asignados, lo cual también tiene una complejidad de O(n \* k \* d).

Estos dos pasos se repiten durante un número determinado de iteraciones, i, lo que lleva a la complejidad total del algoritmo K-means a ser O(n \* k \* i \* d). Es decir, no es factorial (O(n!)) sino lineal respecto a las iteraciones y puntos de datos.

Entonces, aunque K-means puede ser costoso en términos de tiempo de cómputo para grandes conjuntos de datos y muchas dimensiones, no es tan ineficiente como una complejidad factorial. Aún así, hay optimizaciones y variaciones del algoritmo, como K-means++, que ayudan a mejorar su desempeño.

Jorge Miguel Diaz

student•

En estos casos ¿Tiene solución el algoritmo o se tendrían que recalcular los centroides desde el principio?

Octavio De Paula

student•

Esa pagina es adictiva para un cientifico de datos ;)

Julián Cárdenas

student•

Para ilustrar cómo funciona el algoritmo K-means, consideremos un ejemplo simple con un conjunto de datos bidimensional en el que queremos agrupar puntos en dos clústeres. Imagina que tienes los siguientes puntos en un plano cartesiano:

Punto A: (2, 3)
Punto B: (3, 3)
Punto C: (2, 2)
Punto D: (6, 5)
Punto E: (6, 6)
Punto F: (7, 7)

Pasos del algoritmo K-means:

Inicialización: Inicialmente, seleccionamos dos puntos aleatorios como los centros iniciales de los clústeres. Supongamos que elegimos los puntos A y D como centros iniciales.

Asignación: Calculamos la distancia entre cada punto de datos y los centros de los clústeres (A y D) y asignamos cada punto al clúster cuyo centro está más cerca. Por ejemplo, los puntos A, B, y C se asignarían al clúster A, y los puntos D, E, y F se asignarían al clúster D.
Actualización de los centros: Calculamos los nuevos centros de los clústeres como el promedio de los puntos asignados a cada clúster. Los nuevos centros serían (2.33, 2.67) para el clúster A y (6.33, 6.0) para el clúster D.
Repetición: Repetimos los pasos 2 y 3. Después de la segunda iteración, los puntos se asignarán de manera diferente. Ahora, los puntos A, B, C, y D se asignarán al clúster A, y los puntos E y F se asignarán al clúster D.
Resultados: Después de varias iteraciones, el algoritmo convergerá a una solución. En este caso, los dos clústeres resultantes serán:

Clúster 1:

Punto A: (2, 3) Punto B: (3, 3) Punto C: (2, 2) Punto D: (6, 5)

Clúster 2: Punto E: (6, 6) Punto F: (7, 7)

En este ejemplo, K-means ha agrupado los puntos en dos clústeres basados en su proximidad en el espacio bidimensional. Ten en cuenta que la elección de los centros iniciales puede afectar los resultados, y en la práctica, el algoritmo se ejecuta varias veces con diferentes inicializaciones para mejorar la estabilidad de los clústeres.

Julián Cárdenas

student•

K-means es un algoritmo de agrupamiento (clustering) ampliamente utilizado en el campo de la minería de datos y el aprendizaje automático. Su objetivo principal es dividir un conjunto de datos en grupos o clústeres, de tal manera que los elementos dentro de un mismo grupo sean similares entre sí, mientras que los elementos de grupos diferentes sean distintos. A continuación, te explicaré cómo funciona el algoritmo K-means: *

Inicialización: El primer paso es seleccionar un número predefinido de clústeres (K) que deseas obtener a partir de tus datos. Luego, se eligen K puntos iniciales como centros de los clústeres. Estos puntos iniciales pueden ser seleccionados aleatoriamente o mediante algún otro método, como k-means++ para mejorar la inicialización.
Asignación: Para cada punto de datos en tu conjunto, se calcula la distancia entre el punto y los K centros de los clústeres. El punto se asigna al clúster cuyo centro está más cerca de él. Esto crea K grupos iniciales.
Actualización de los centros: Una vez que todos los puntos de datos se han asignado a un clúster, se recalculan los centros de cada clúster como el promedio de todos los puntos asignados a ese clúster. Estos nuevos centros representan el "centroide" de cada grupo.
Repetición: Los pasos 2 y 3 se repiten iterativamente hasta que se cumpla algún criterio de detención, como la convergencia (cuando los centros de los clústeres dejan de cambiar significativamente) o después de un número fijo de iteraciones.
Resultados: Una vez que el algoritmo ha convergido, los puntos de datos se encuentran asignados a sus respectivos clústeres. El resultado es un conjunto de K grupos, donde cada grupo contiene puntos de datos similares entre sí y diferentes de los puntos en otros grupos.

Es importante tener en cuenta que K-means es un algoritmo heurístico y puede converger a un mínimo local en lugar de encontrar la solución óptima global. Por lo tanto, en la práctica, es común ejecutar el algoritmo varias veces con diferentes inicializaciones y seleccionar la mejor solución. También, la elección de un valor adecuado para K puede ser crucial, y se pueden utilizar métodos como el codo (elbow method) o el índice de Davies-Bouldin para determinar el número óptimo de clústeres.

K-means es eficiente y fácil de implementar, pero tiene limitaciones, como la sensibilidad a la inicialización y la forma de los clústeres. Para problemas más complejos, es posible que se necesiten algoritmos de agrupamiento más avanzados.

Juan Pablo Lagos Idrobo

student•

Es verdad lo facil que es entender este algoritmo con visulizacion, me encanta.

¿Qué es el algoritmo de K-means y cómo funciona?

Fundamentos de clustering

¿Qué es el clustering en machine learning?

Tu primer clustering con scikit-learn

¿Cuándo usar clustering?

¿Cómo evaluar modelos de clustering?

K-means

¿Qué es el algoritmo de K-means y cómo funciona?

¿Cuándo usar K-means?

Implementando K-means

Encontrando K

Evaluando resultados de K-means

Hierarchical clustering

¿Qué es hierarchical clustering y cómo funciona?

¿Cuándo usar hierarchical clustering?

Implementando hierarchical clustering

Evaluando resultados de hierarchical clustering

DBSCAN

¿Qué es DBSCAN y cómo funciona?

¿Cuándo usar DBSCAN?

Implementando DBSCAN

Encontrar híper-parámetros

Evaluando resultados de DBSCAN

Proyecto: resolviendo un problema con clustering

Preparar datos para clusterizar

Aplicando PCA para clustering

Resolviendo con K-means

Resolviendo con hierarchical clustering

Resolviendo con DBSCAN

Resolviendo con DBSCAN (sin PCA)

Evaluación resultados de distintos modelos de clustering

Conclusiones

Proyecto final y cierre

Comparte tu proyecto de segmentación con clustering y certifícate