El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Algoritmos de Clustering

Siguiente ►
►

Todo el módulo hasta aquí ha sido aprendizaje supervisado: cada entrega histórica traía su etiqueta (retraso, minutos_entrega) y el modelo aprendía a predecirla. Pero hay preguntas de Rutalia sin etiqueta posible: ¿qué zonas de la ciudad se comportan igual? ¿Qué tipos de entrega existen, en realidad? Nadie ha marcado la respuesta en los datos porque nadie la conoce: hay que descubrir la estructura, no imitarla. Eso es el aprendizaje no supervisado, y su técnica central es el clustering: agrupar ejemplos de modo que los de un grupo se parezcan entre sí más que a los de otros grupos. En esta lección implementaremos k-means desde cero (el algoritmo de Lloyd), veremos el clustering jerárquico y DBSCAN, cerraremos un círculo pendiente desde el módulo 3 (cortar el MST de Kruskal es clustering) y aplicaremos todo a un problema real de Rutalia: agrupar zonas por patrón de demanda para rediseñar las rutas — lo que nos devolverá, elegantemente, al TSP del módulo 2.

Contenido

  1. Aprendizaje sin etiquetas: qué cambia
  2. k-means: el algoritmo de Lloyd
  3. Inicialización y k-means++
  4. Elegir k: método del codo y silueta
  5. Limitaciones de k-means
  6. Clustering jerárquico: el dendrograma
  7. Single-linkage = MST: cerrando el círculo del módulo 3
  8. DBSCAN: clustering por densidad
  9. Aplicación Rutalia: zonas por patrón de demanda (y vuelta al TSP)
  10. Tabla comparativa

Aprendizaje sin etiquetas: qué cambia

Sin y, cambian tres cosas fundamentales:

  • No hay respuesta correcta. En clasificación, la matriz de confusión zanjaba la discusión. Aquí no existe "el clustering verdadero": distintas agrupaciones pueden ser válidas para distintos propósitos.
  • La evaluación es interna. Medimos propiedades geométricas (compacidad, separación) y, sobre todo, utilidad para el negocio.
  • La distancia lo es todo. "Parecerse" significa estar cerca en el espacio de features — así que el escalado de 05-01 pasa de importante a crítico: una feature mal escalada define los clusters ella sola.

k-means: el algoritmo de Lloyd

k-means busca k centroides (puntos medios) que minimicen la inercia: la suma de distancias al cuadrado de cada punto a su centroide más cercano. Minimizarla exactamente es NP-duro (viejo conocido de 02-02), así que se usa una heurística iterativa excelente, el algoritmo de Lloyd:

flowchart TD
    A["1. Elegir k centroides iniciales"] --> B["2. ASIGNAR: cada punto,\nal centroide más cercano"]
    B --> C["3. ACTUALIZAR: cada centroide,\na la media de sus puntos"]
    C --> D{"¿Cambió alguna asignación?"}
    D -->|sí| B
    D -->|no| E["Converge: clusters finales"]

Cada paso tiene una lógica de mejora garantizada: asignar cada punto a su centroide más cercano no puede aumentar la inercia, y mover cada centroide a la media de sus puntos tampoco (la media es el punto que minimiza la suma de cuadrados de distancias — el mismo hecho que apareció en mínimos cuadrados en 05-03). La inercia baja o se mantiene en cada iteración y las asignaciones posibles son finitas: el algoritmo siempre termina. Lo que no garantiza es terminar en el óptimo global — igual que los voraces de 02-02, converge al mínimo local que le pille cerca.

def kmeans_lloyd(X, k, semilla=42, max_iter=100):
    """k-means desde cero. Devuelve asignaciones, centroides e inercia."""
    rng = np.random.default_rng(semilla)
    centroides = X[rng.choice(len(X), k, replace=False)]   # k puntos al azar
    for _ in range(max_iter):
        # ASIGNAR: matriz de distancias (n × k) por broadcasting
        dists = np.linalg.norm(X[:, None, :] - centroides[None, :, :], axis=2)
        asig = dists.argmin(axis=1)                # centroide más cercano
        # ACTUALIZAR: cada centroide a la media de sus puntos
        nuevos = np.array([X[asig == c].mean(axis=0) if (asig == c).any()
                           else centroides[c] for c in range(k)])
        if np.allclose(nuevos, centroides):        # sin cambios: convergido
            break
        centroides = nuevos
    inercia = float(((X - centroides[asig]) ** 2).sum())
    return asig, centroides, inercia

Complejidad por iteración: O(n·k·d) — lineal en todo, por eso k-means escala a los millones de registros de Rutalia. El número de iteraciones hasta converger suele ser pequeño en la práctica.

Inicialización y k-means++

El talón de Aquiles de Lloyd: el resultado depende de los centroides iniciales. Dos arranques desafortunados (p. ej., dos centroides cayendo en el mismo grupo natural) convergen a mínimos locales distintos, algunos malos. Dos remedios complementarios:

  • Reinicios múltiples: ejecutar el algoritmo varias veces con semillas distintas y quedarse con la menor inercia (sklearn: n_init=10 por defecto).
  • k-means++: elegir los centroides iniciales ya separados entre sí. El primero al azar; cada siguiente se sortea con probabilidad proporcional a D(x)², la distancia al cuadrado del punto a su centroide ya elegido más cercano — los puntos lejanos de todo lo elegido tienen más papeletas.
def kmeans_pp_init(X, k, rng):
    """Inicialización k-means++: centroides separados con alta probabilidad."""
    centroides = [X[rng.integers(len(X))]]         # el primero, uniforme
    for _ in range(k - 1):
        d2 = np.min([((X - c) ** 2).sum(axis=1) for c in centroides], axis=0)
        probs = d2 / d2.sum()                      # ∝ distancia al cuadrado
        centroides.append(X[rng.choice(len(X), p=probs)])
    return np.array(centroides)

k-means++ no solo funciona bien empíricamente: garantiza en esperanza una inercia a factor O(log k) del óptimo — una cota de aproximación probabilística, pariente de las garantías que discutimos en 02-02. Es el defecto de sklearn (init="k-means++").

Elegir k: método del codo y silueta

En supervisado, los hiperparámetros se elegían con validación cruzada contra la etiqueta. Sin etiqueta, necesitamos criterios internos:

  • Método del codo: graficar la inercia frente a k. La inercia siempre baja al crecer k (con k=n sería 0: cada punto su propio cluster — el sobreajuste del clustering), pero baja a saltos grandes mientras k está por debajo del número natural de grupos y a saltos pequeños después. El "codo" de la curva sugiere el k natural. Es visual y algo subjetivo.
  • Coeficiente de silueta: para cada punto, compara a (distancia media a los de su propio cluster) con b (distancia media a los del cluster ajeno más cercano): s = (b − a) / max(a, b) ∈ [−1, 1]. Cerca de 1: bien agrupado; cerca de 0: en la frontera; negativo: probablemente en el cluster equivocado. La silueta media del dataset se maximiza sobre varios k candidatos — objetivo y automatizable (sklearn.metrics.silhouette_score), a cambio de costar O(n²).
for k in range(2, 9):
    _, _, inercia = kmeans_lloyd(X_e, k)
    print(f"k={k}: inercia={inercia:10.1f}")   # busca el codo en la secuencia

Limitaciones de k-means

k-means lleva escrita su geometría: al asignar por distancia al centroide, asume clusters convexos, aproximadamente esféricos y de tamaño similar. Falla de forma predecible cuando la realidad no coopera:

Situación Qué hace k-means Qué haría falta
Clusters alargados o anidados (dos anillos, dos medias lunas) Los corta por la mitad con fronteras rectas DBSCAN o jerárquico single-linkage
Densidades muy distintas El cluster denso "roba" puntos al disperso DBSCAN
Outliers Arrastran los centroides (la media no es robusta) DBSCAN (los marca como ruido)
k desconocido Hay que dárselo Jerárquico (decides después) o DBSCAN (lo infiere)

Estas limitaciones motivan exactamente los dos algoritmos siguientes.

Clustering jerárquico: el dendrograma

El clustering aglomerativo no fija k por adelantado: construye todas las granularidades a la vez.

  1. Empieza con n clusters (cada punto, el suyo).
  2. Une los dos clusters más cercanos.
  3. Repite hasta que quede uno solo.

El historial de fusiones forma un árbol, el dendrograma: la altura de cada fusión es la distancia a la que ocurrió. Cortando el dendrograma a una altura se obtiene una partición; cortes más bajos dan más clusters. Se elige la granularidad después de ver la estructura — el lujo que k-means no da.

Queda por definir "distancia entre clusters" (el linkage), y la elección cambia el carácter del algoritmo:

Linkage Distancia entre clusters A y B Tendencia
Single mínimo entre pares (a∈A, b∈B) Encadena: sigue estructuras alargadas (y crea "puentes" indeseados)
Complete máximo entre pares Clusters compactos y redondos
Average media entre pares Compromiso
Ward menor aumento de inercia al fusionar El más parecido a k-means; defecto habitual

En scipy: scipy.cluster.hierarchy.linkage(X, method="ward") y dendrogram(...) para dibujarlo; fcluster corta a la altura elegida. Coste O(n² log n) y memoria O(n²): perfecto para agrupar las 9 zonas de Rutalia o unos miles de clientes, inviable para millones de filas.

Single-linkage = MST: cerrando el círculo del módulo 3

En el ejercicio final de 03-04 adelantamos, casi como curiosidad, que cortar las k−1 aristas más caras del árbol de expansión mínima de Kruskal parte el grafo en k grupos "naturales". Toca cerrar ese círculo: eso era clustering jerárquico single-linkage, exactamente.

La correspondencia es precisa. Kruskal (03-04) procesa las aristas de menor a mayor peso uniendo componentes con union-find (01-04). Single-linkage fusiona en cada paso los dos clusters con el par de puntos más cercano entre ellos. Son el mismo algoritmo: la secuencia de uniones de Kruskal sobre el grafo completo de distancias es la secuencia de fusiones de single-linkage, y las alturas del dendrograma son los pesos de las aristas del MST en el orden en que Kruskal las acepta. Por eso cortar las k−1 aristas más caras del MST equivale a cortar el dendrograma para obtener k clusters.

def clusters_por_mst(X, k):
    """Single-linkage vía Kruskal: corta las k-1 aristas más caras del MST."""
    n = len(X)
    aristas = sorted((np.linalg.norm(X[i] - X[j]), i, j)
                     for i in range(n) for j in range(i + 1, n))
    padre = list(range(n))                    # union-find de 01-04
    def find(a):
        while padre[a] != a:
            padre[a] = padre[padre[a]]        # compresión de camino
            a = padre[a]
        return a
    aceptadas = []
    for w, i, j in aristas:                   # Kruskal, tal cual 03-04
        ri, rj = find(i), find(j)
        if ri != rj:
            padre[ri] = rj
            aceptadas.append((w, i, j))
    # MST completo: n-1 aristas. Quitar las k-1 más caras = k componentes.
    padre = list(range(n))
    for w, i, j in aceptadas[:-(k - 1)]:      # nos saltamos las k-1 últimas (más caras)
        padre[find(i)] = find(j)
    raices = {find(i) for i in range(n)}
    return np.array([sorted(raices).index(find(i)) for i in range(n)])

Un algoritmo de grafos del módulo 3, con la estructura de datos del módulo 1, resulta ser un algoritmo de aprendizaje no supervisado del módulo 5. Las fronteras entre "algoritmia clásica" y "machine learning" son más finas de lo que parecen: ML es, en gran parte, algoritmia aplicada a datos.

DBSCAN: clustering por densidad

DBSCAN abandona centroides y jerarquías: un cluster es una región densa de puntos, tenga la forma que tenga. Dos parámetros: eps (radio de vecindad) y min_samples (cuántos vecinos hacen "denso" a un punto).

  • Punto núcleo: tiene ≥ min_samples vecinos a distancia ≤ eps.
  • Un cluster es un conjunto máximo de núcleos conectados por cadenas de vecindad (alcanzabilidad por densidad), más los puntos frontera pegados a ellos.
  • Lo que no alcanza ningún núcleo es ruido: queda sin cluster, etiquetado −1.

Algorítmicamente es una vieja amiga: una exploración tipo BFS (03-02) sobre el "grafo de densidad" — desde cada núcleo no visitado, expandir la vecindad; si un vecino es núcleo, seguir expandiendo por él. Coste O(n²) ingenuo, O(n log n) con índices espaciales.

Cuándo gana a k-means:

  • Formas arbitrarias: sigue la densidad, no impone esferas — resuelve los anillos y medias lunas donde k-means fracasa.
  • No pide k: el número de clusters emerge de los datos.
  • Ruido explícito: los outliers no contaminan ningún cluster; en Rutalia, las entregas anómalas (dirección errónea, incidencia grave) quedan señaladas gratis — clustering y detección de anomalías en uno.

Sus debilidades: elegir eps requiere tacto (regla práctica: gráfico de la distancia al k-ésimo vecino y buscar el codo), y sufre cuando los clusters tienen densidades muy dispares. En sklearn: DBSCAN(eps=0.5, min_samples=5).fit_predict(X_e).

Aplicación Rutalia: zonas por patrón de demanda (y vuelta al TSP)

Juntemos las piezas en un problema real. Rutalia quiere rediseñar sus rutas: ¿qué zonas se comportan igual y podrían compartir estrategia de reparto? Construimos, con el dataset canónico, el perfil de demanda de cada zona: un vector de features agregadas por zona.

datos = generar_dataset()                      # canónico, semilla 42 (05-01)
perfiles, nombres = [], []
for z in ZONAS:
    m = datos["zona"] == z
    perfiles.append([
        datos["minutos_entrega"][m].mean(),    # duración media
        datos["retraso"][m].mean(),            # tasa de retraso
        (datos["hora_salida"][m] >= 17).mean(),# fracción de reparto vespertino
        datos["peso_kg"][m].mean(),            # peso medio
    ])
    nombres.append(z)
P = np.array(perfiles)
P_e = (P - P.mean(axis=0)) / P.std(axis=0)     # estandarizar: crítico

asig, cents, _ = kmeans_lloyd(P_e, k=3)
for c in range(3):
    print(f"cluster {c}: {[nombres[i] for i in range(9) if asig[i] == c]}")

Con la verdad oculta del generador, los grupos que emergen son interpretables: las zonas congestionadas (CEN, MER, HOS) se agrupan por sus duraciones y tasas de retraso altas; las fluidas (IND, PAR, UNI) forman otro perfil; las intermedias (ALM, RIO, EST), el tercero. Nadie etiquetó las zonas: la estructura estaba en los datos y el algoritmo la hizo visible. (Con 9 puntos, el jerárquico con dendrograma sería igual de apropiado y más ilustrativo; k-means gana cuando agrupamos miles de clientes o millones de entregas.)

Y aquí se cierra el círculo grande del curso: con los clusters en la mano, operaciones asigna repartidores por grupo de zonas homogéneas... y planificar la ruta de cada repartidor dentro de su grupo es, de nuevo, el TSP del módulo 2 — aquella instancia canónica de óptimo 35,22 km — sobre el grafo del módulo 3, con el A* del módulo 4 para los trayectos y los modelos de este módulo prediciendo los tiempos que alimentan los pesos. El aprendizaje automático no sustituye a la algoritmia clásica: la alimenta con mejores datos y mejores agrupaciones, y esa decisión final de rediseño la toman las personas de operaciones con los análisis en la mano.

Tabla comparativa

Criterio k-means Jerárquico (aglomerativo) DBSCAN
¿Pide k? Sí, por adelantado No (se corta el dendrograma después) No (emerge de la densidad)
Forma de clusters Esféricos, convexos Según linkage (single: alargados) Arbitraria
Manejo de ruido No (los outliers arrastran centroides) No Sí, etiqueta −1
Coste O(n·k·d) por iteración O(n² log n), memoria O(n²) O(n²), O(n log n) con índice
Escala a millones Sí No Con índices espaciales, aceptable
Determinista No (inicialización) Sí Sí (dado eps/min_samples)
Parámetros delicados k, inicialización linkage, altura de corte eps, min_samples
Úsalo cuando… Grupos compactos, datos masivos Quieres la jerarquía / pocos datos Formas raras, outliers, k desconocido

Errores Comunes y Consejos

  • Agrupar sin estandarizar. En el perfil de zonas, minutos_entrega (~20-60) aplastaría a retraso (~0-0.4): los clusters saldrían de una sola feature. Sin etiqueta que te delate el error, puede pasar inadvertido — estandariza siempre.
  • Una sola ejecución de k-means. Lloyd converge al mínimo local de turno. Usa k-means++ y varios reinicios (n_init), y compara inercias.
  • Tomar el k del codo como verdad revelada. El codo sugiere; la silueta cuantifica; el negocio decide. Si k=3 y k=4 son parecidos en silueta pero operaciones trabaja con 4 equipos de reparto, la respuesta es 4.
  • Interpretar los clusters como categorías reales. Un cluster es una regularidad geométrica, no una verdad del mundo. Valida siempre con conocimiento del dominio antes de actuar sobre él.
  • Usar DBSCAN con densidades muy dispares. Un único eps no puede servir a la vez para un casco urbano denso y un polígono disperso; considera jerárquico o variantes (HDBSCAN).
  • Consejo: dibuja siempre que puedas (proyecta a 2D si hace falta). En clustering, un vistazo al scatter con colores vale más que cualquier métrica interna.

Ejercicios

  1. Lloyd bajo la lupa. Modifica kmeans_lloyd para que guarde la inercia en cada iteración y ejecútalo sobre los perfiles de zona (k=3) con 5 semillas distintas. Comprueba que (a) la inercia nunca sube dentro de una ejecución, y (b) distintas semillas pueden terminar en inercias finales distintas. ¿Cuál de las dos propiedades demostramos y cuál es solo empírica?

  2. El codo y la silueta. Sobre una muestra estandarizada de 500 entregas del dataset canónico (features: distancia_km, hora_salida, peso_kg), calcula la inercia de k-means para k=2..8 y la silueta media (sklearn.metrics.silhouette_score) para cada k. ¿Coinciden el codo y el máximo de silueta? ¿Qué harías si no coinciden?

  3. Kruskal como clusterizador. Aplica clusters_por_mst con k=3 a los perfiles de zona estandarizados y compara las particiones con las de k-means y con AgglomerativeClustering(n_clusters=3, linkage="single") de sklearn. Verifica que MST y single-linkage coinciden exactamente y explica por qué k-means puede diferir.

Soluciones

Ejercicio 1:

# Dentro del bucle de kmeans_lloyd, tras asignar:
#   historial.append(float(((X - centroides[asig]) ** 2).sum()))
for s in range(5):
    asig, _, inercia = kmeans_lloyd(P_e, 3, semilla=s)
    print(f"semilla {s}: inercia final = {inercia:.3f}")

(a) es un teorema: cada paso de asignación y de actualización no puede aumentar la inercia (lo argumentamos al presentar Lloyd), así que el historial es monótono no creciente en toda ejecución. (b) es empírica: la convergencia es a un mínimo local, y cuál toque depende del arranque — verás semillas que terminan en inercias distintas. De ahí k-means++ y los reinicios.

Ejercicio 2:

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

Xm = np.column_stack([datos["distancia_km"], datos["hora_salida"],
                      datos["peso_kg"]])[:500]
Xm = (Xm - Xm.mean(axis=0)) / Xm.std(axis=0)
for k in range(2, 9):
    km = KMeans(n_clusters=k, n_init=10, random_state=42).fit(Xm)
    print(f"k={k}: inercia={km.inertia_:8.1f}  "
          f"silueta={silhouette_score(Xm, km.labels_):.3f}")

Con datos de entregas individuales (bastante continuos, sin grupos muy marcados), es normal que el codo sea suave y la silueta modesta y con máximo en k pequeño: señal honesta de que la estructura de grupos es débil. Si codo y silueta no coinciden, ni uno ni otra mandan: se examinan los candidatos (visualización, perfiles medios de cada cluster) y decide la interpretabilidad y el uso de negocio. "No hay clusters nítidos" también es un resultado válido del análisis.

Ejercicio 3:

from sklearn.cluster import AgglomerativeClustering

mst = clusters_por_mst(P_e, 3)
single = AgglomerativeClustering(n_clusters=3, linkage="single").fit_predict(P_e)
km = kmeans_lloyd(P_e, 3)[0]
print(mst, single, km, sep="\n")

MST y single-linkage producen la misma partición (las etiquetas pueden estar permutadas — compara la agrupación, no los números): son el mismo algoritmo, como argumentamos, con la secuencia de fusiones dictada por las aristas del MST. k-means puede diferir porque optimiza otra cosa (inercia respecto a centroides, favoreciendo grupos redondos y equilibrados), mientras single-linkage sigue cadenas de cercanía aunque formen grupos alargados o de tamaños dispares.

Conclusión

Con el clustering completamos el mapa del módulo: aprendizaje no supervisado, donde no se imita una etiqueta sino que se descubre estructura. Viste k-means por dentro (Lloyd y su inercia monótona, k-means++ con su garantía probabilística, el codo y la silueta para elegir k, y sus supuestos esféricos), el jerárquico con su dendrograma multiescala, y DBSCAN encontrando clusters de forma libre y señalando el ruido — con la revelación de que single-linkage es exactamente el Kruskal del módulo 3 cortado en sus aristas más caras: la algoritmia clásica y el aprendizaje automático son el mismo continente. Y con ella se cierra el módulo 5 entero: partimos de un cambio de paradigma —dejar que las reglas se aprendan de los datos— y lo recorremos completo: el protocolo honesto de evaluación (05-01), clasificar (05-02), predecir cantidades con el descenso de gradiente como motor (05-03), componer no linealidad con redes y backpropagation (05-04) y descubrir estructura sin etiquetas (05-05), siempre sobre las mismas 2000 entregas del dataset canónico de Rutalia. Ahora tienes el arsenal completo del curso: análisis y estructuras (módulo 1), optimización (módulo 2), grafos (módulo 3), búsqueda y ordenación (módulo 4) y aprendizaje automático (módulo 5). En el módulo 6 dejamos de afilar herramientas y salimos al mundo: casos de estudio reales donde estos algoritmos se combinan —optimización en la industria, grafos en redes sociales, búsqueda y ordenación a gran escala, y el ML de este módulo puesto a trabajar en producción—, empezando en 06-01 por la optimización en la industria.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados