El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algorismes de Clustering

Següent ►
►

Tot el mòdul fins aquí ha estat aprenentatge supervisat: cada lliurament històric portava la seva etiqueta (retard, minuts_lliurament) i el model aprenia a predir-la. Però hi ha preguntes de Rutalia sense etiqueta possible: quines zones de la ciutat es comporten igual? Quins tipus de lliurament existeixen, en realitat? Ningú no ha marcat la resposta a les dades perquè ningú no la coneix: cal descobrir l'estructura, no imitar-la. Això és l'aprenentatge no supervisat, i la seva tècnica central és el clustering: agrupar exemples de manera que els d'un grup s'assemblin entre si més que als dels altres grups. En aquesta lliçó implementarem k-means des de zero (l'algorisme de Lloyd), veurem el clustering jeràrquic i DBSCAN, tancarem un cercle pendent des del mòdul 3 (tallar el MST de Kruskal és clustering) i ho aplicarem tot a un problema real de Rutalia: agrupar zones per patró de demanda per redissenyar les rutes — cosa que ens retornarà, elegantment, al TSP del mòdul 2.

Contingut

  1. Aprenentatge sense etiquetes: què canvia
  2. k-means: l'algorisme de Lloyd
  3. Inicialització i k-means++
  4. Triar k: mètode del colze i silueta
  5. Limitacions de k-means
  6. Clustering jeràrquic: el dendrograma
  7. Single-linkage = MST: tancant el cercle del mòdul 3
  8. DBSCAN: clustering per densitat
  9. Aplicació Rutalia: zones per patró de demanda (i retorn al TSP)
  10. Taula comparativa

Aprenentatge sense etiquetes: què canvia

Sense y, canvien tres coses fonamentals:

  • No hi ha resposta correcta. En classificació, la matriu de confusió tancava la discussió. Aquí no existeix "el clustering veritable": agrupacions diferents poden ser vàlides per a propòsits diferents.
  • L'avaluació és interna. Mesurem propietats geomètriques (compacitat, separació) i, sobretot, utilitat per al negoci.
  • La distància ho és tot. "Assemblar-se" significa ser a prop en l'espai de features — així que l'escalat de 05-01 passa d'important a crític: una feature mal escalada defineix els clústers tota sola.

k-means: l'algorisme de Lloyd

k-means busca k centroides (punts mitjans) que minimitzin la inèrcia: la suma de distàncies al quadrat de cada punt al seu centroide més proper. Minimitzar-la exactament és NP-dur (vell conegut de 02-02), així que es fa servir una heurística iterativa excel·lent, l'algorisme de Lloyd:

flowchart TD
    A["1. Triar k centroides inicials"] --> B["2. ASSIGNAR: cada punt,\nal centroide més proper"]
    B --> C["3. ACTUALITZAR: cada centroide,\na la mitjana dels seus punts"]
    C --> D{"Ha canviat alguna assignació?"}
    D -->|sí| B
    D -->|no| E["Convergeix: clústers finals"]

Cada pas té una lògica de millora garantida: assignar cada punt al seu centroide més proper no pot augmentar la inèrcia, i moure cada centroide a la mitjana dels seus punts tampoc (la mitjana és el punt que minimitza la suma de quadrats de distàncies — el mateix fet que va aparèixer a mínims quadrats a 05-03). La inèrcia baixa o es manté a cada iteració i les assignacions possibles són finites: l'algorisme sempre acaba. El que no garanteix és acabar a l'òptim global — igual que els voraços de 02-02, convergeix al mínim local que enxampi a prop.

def kmeans_lloyd(X, k, llavor=42, max_iter=100):
    """k-means des de zero. Retorna assignacions, centroides i inèrcia."""
    rng = np.random.default_rng(llavor)
    centroides = X[rng.choice(len(X), k, replace=False)]   # k punts a l'atzar
    for _ in range(max_iter):
        # ASSIGNAR: matriu de distàncies (n × k) per broadcasting
        dists = np.linalg.norm(X[:, None, :] - centroides[None, :, :], axis=2)
        assig = dists.argmin(axis=1)               # centroide més proper
        # ACTUALITZAR: cada centroide a la mitjana dels seus punts
        nous = np.array([X[assig == c].mean(axis=0) if (assig == c).any()
                         else centroides[c] for c in range(k)])
        if np.allclose(nous, centroides):          # sense canvis: convergit
            break
        centroides = nous
    inercia = float(((X - centroides[assig]) ** 2).sum())
    return assig, centroides, inercia

Complexitat per iteració: O(n·k·d) — lineal en tot, per això k-means escala als milions de registres de Rutalia. El nombre d'iteracions fins a convergir sol ser petit a la pràctica.

Inicialització i k-means++

El taló d'Aquil·les de Lloyd: el resultat depèn dels centroides inicials. Dues arrencades desafortunades (p. ex., dos centroides caient al mateix grup natural) convergeixen a mínims locals diferents, alguns dolents. Dos remeis complementaris:

  • Reinicis múltiples: executar l'algorisme diverses vegades amb llavors diferents i quedar-se amb la inèrcia menor (sklearn: n_init=10 per defecte).
  • k-means++: triar els centroides inicials ja separats entre si. El primer a l'atzar; cada següent se sorteja amb probabilitat proporcional a D(x)², la distància al quadrat del punt al seu centroide ja triat més proper — els punts allunyats de tot el que s'ha triat tenen més butlletes.
def kmeans_pp_init(X, k, rng):
    """Inicialització k-means++: centroides separats amb alta probabilitat."""
    centroides = [X[rng.integers(len(X))]]         # el primer, 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()                      # ∝ distància al quadrat
        centroides.append(X[rng.choice(len(X), p=probs)])
    return np.array(centroides)

k-means++ no només funciona bé empíricament: garanteix en esperança una inèrcia a factor O(log k) de l'òptim — una fita d'aproximació probabilística, parenta de les garanties que vam discutir a 02-02. És l'opció per defecte de sklearn (init="k-means++").

Triar k: mètode del colze i silueta

En supervisat, els hiperparàmetres es triaven amb validació creuada contra l'etiqueta. Sense etiqueta, necessitem criteris interns:

  • Mètode del colze: graficar la inèrcia davant de k. La inèrcia sempre baixa en créixer k (amb k=n seria 0: cada punt el seu propi clúster — el sobreajustament del clustering), però baixa a salts grans mentre k és per sota del nombre natural de grups i a salts petits després. El "colze" de la corba suggereix el k natural. És visual i una mica subjectiu.
  • Coeficient de silueta: per a cada punt, compara a (distància mitjana als del seu propi clúster) amb b (distància mitjana als del clúster aliè més proper): s = (b − a) / max(a, b) ∈ [−1, 1]. A prop d'1: ben agrupat; a prop de 0: a la frontera; negatiu: probablement al clúster equivocat. La silueta mitjana del dataset es maximitza sobre diversos k candidats — objectiva i automatitzable (sklearn.metrics.silhouette_score), a canvi 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 colze a la seqüència

Limitacions de k-means

k-means porta escrita la seva geometria: en assignar per distància al centroide, assumeix clústers convexos, aproximadament esfèrics i de mida similar. Falla de manera predictible quan la realitat no coopera:

Situació Què fa k-means Què caldria
Clústers allargats o imbricats (dos anells, dues mitges llunes) Els talla per la meitat amb fronteres rectes DBSCAN o jeràrquic single-linkage
Densitats molt diferents El clúster dens "roba" punts al dispers DBSCAN
Outliers Arrosseguen els centroides (la mitjana no és robusta) DBSCAN (els marca com a soroll)
k desconegut Cal donar-l'hi Jeràrquic (decideixes després) o DBSCAN (l'infereix)

Aquestes limitacions motiven exactament els dos algorismes següents.

Clustering jeràrquic: el dendrograma

El clustering aglomeratiu no fixa k per endavant: construeix totes les granularitats alhora.

  1. Comença amb n clústers (cada punt, el seu).
  2. Uneix els dos clústers més propers.
  3. Repeteix fins que en quedi un de sol.

L'historial de fusions forma un arbre, el dendrograma: l'alçada de cada fusió és la distància a la qual va passar. Tallant el dendrograma a una alçada s'obté una partició; talls més baixos donen més clústers. Es tria la granularitat després de veure l'estructura — el luxe que k-means no dona.

Queda per definir "distància entre clústers" (el linkage), i la tria canvia el caràcter de l'algorisme:

Linkage Distància entre clústers A i B Tendència
Single mínim entre parells (a∈A, b∈B) Encadena: segueix estructures allargades (i crea "ponts" indesitjats)
Complete màxim entre parells Clústers compactes i rodons
Average mitjana entre parells Compromís
Ward menor augment d'inèrcia en fusionar El més semblant a k-means; opció per defecte habitual

A scipy: scipy.cluster.hierarchy.linkage(X, method="ward") i dendrogram(...) per dibuixar-lo; fcluster talla a l'alçada triada. Cost O(n² log n) i memòria O(n²): perfecte per agrupar les 9 zones de Rutalia o uns quants milers de clients, inviable per a milions de files.

Single-linkage = MST: tancant el cercle del mòdul 3

A l'exercici final de 03-04 vam avançar, gairebé com a curiositat, que tallar les k−1 arestes més cares de l'arbre d'expansió mínim de Kruskal parteix el graf en k grups "naturals". Toca tancar aquest cercle: allò era clustering jeràrquic single-linkage, exactament.

La correspondència és precisa. Kruskal (03-04) processa les arestes de menor a major pes unint components amb union-find (01-04). Single-linkage fusiona a cada pas els dos clústers amb el parell de punts més proper entre ells. Són el mateix algorisme: la seqüència d'unions de Kruskal sobre el graf complet de distàncies és la seqüència de fusions de single-linkage, i les alçades del dendrograma són els pesos de les arestes del MST en l'ordre en què Kruskal les accepta. Per això tallar les k−1 arestes més cares del MST equival a tallar el dendrograma per obtenir k clústers.

def clusters_per_mst(X, k):
    """Single-linkage via Kruskal: talla les k-1 arestes més cares del MST."""
    n = len(X)
    arestes = sorted((np.linalg.norm(X[i] - X[j]), i, j)
                     for i in range(n) for j in range(i + 1, n))
    pare = list(range(n))                     # union-find de 01-04
    def find(a):
        while pare[a] != a:
            pare[a] = pare[pare[a]]           # compressió de camí
            a = pare[a]
        return a
    acceptades = []
    for w, i, j in arestes:                   # Kruskal, tal qual 03-04
        ri, rj = find(i), find(j)
        if ri != rj:
            pare[ri] = rj
            acceptades.append((w, i, j))
    # MST complet: n-1 arestes. Treure les k-1 més cares = k components.
    pare = list(range(n))
    for w, i, j in acceptades[:-(k - 1)]:     # ens saltem les k-1 últimes (més cares)
        pare[find(i)] = find(j)
    arrels = {find(i) for i in range(n)}
    return np.array([sorted(arrels).index(find(i)) for i in range(n)])

Un algorisme de grafs del mòdul 3, amb l'estructura de dades del mòdul 1, resulta ser un algorisme d'aprenentatge no supervisat del mòdul 5. Les fronteres entre "algorísmia clàssica" i "machine learning" són més fines del que semblen: el ML és, en gran part, algorísmia aplicada a dades.

DBSCAN: clustering per densitat

DBSCAN abandona centroides i jerarquies: un clúster és una regió densa de punts, tingui la forma que tingui. Dos paràmetres: eps (radi de veïnatge) i min_samples (quants veïns fan "dens" un punt).

  • Punt nucli: té ≥ min_samples veïns a distància ≤ eps.
  • Un clúster és un conjunt màxim de nuclis connectats per cadenes de veïnatge (abastabilitat per densitat), més els punts frontera enganxats a ells.
  • El que no abasta cap nucli és soroll: queda sense clúster, etiquetat −1.

Algorísmicament és una vella amiga: una exploració tipus BFS (03-02) sobre el "graf de densitat" — des de cada nucli no visitat, expandir el veïnatge; si un veí és nucli, continuar expandint per ell. Cost O(n²) ingenu, O(n log n) amb índexs espacials.

Quan guanya a k-means:

  • Formes arbitràries: segueix la densitat, no imposa esferes — resol els anells i mitges llunes on k-means fracassa.
  • No demana k: el nombre de clústers emergeix de les dades.
  • Soroll explícit: els outliers no contaminen cap clúster; a Rutalia, els lliuraments anòmals (adreça errònia, incidència greu) queden assenyalats gratis — clustering i detecció d'anomalies en un.

Les seves febleses: triar eps requereix tacte (regla pràctica: gràfic de la distància al k-èsim veí i buscar-hi el colze), i pateix quan els clústers tenen densitats molt dispars. A sklearn: DBSCAN(eps=0.5, min_samples=5).fit_predict(X_e).

Aplicació Rutalia: zones per patró de demanda (i retorn al TSP)

Ajuntem les peces en un problema real. Rutalia vol redissenyar les seves rutes: quines zones es comporten igual i podrien compartir estratègia de repartiment? Construïm, amb el dataset canònic, el perfil de demanda de cada zona: un vector de features agregades per zona.

dades = generar_dataset()                      # canònic, llavor 42 (05-01)
perfils, noms = [], []
for z in ZONES:
    m = dades["zona"] == z
    perfils.append([
        dades["minuts_lliurament"][m].mean(),  # durada mitjana
        dades["retard"][m].mean(),             # taxa de retard
        (dades["hora_sortida"][m] >= 17).mean(),# fracció de repartiment vespertí
        dades["pes_kg"][m].mean(),             # pes mitjà
    ])
    noms.append(z)
P = np.array(perfils)
P_e = (P - P.mean(axis=0)) / P.std(axis=0)     # estandarditzar: crític

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

Amb la veritat oculta del generador, els grups que emergeixen són interpretables: les zones congestionades (CEN, MER, HOS) s'agrupen per les seves durades i taxes de retard altes; les fluides (IND, PAR, UNI) formen un altre perfil; les intermèdies (ALM, RIO, EST), el tercer. Ningú no va etiquetar les zones: l'estructura era a les dades i l'algorisme l'ha fet visible. (Amb 9 punts, el jeràrquic amb dendrograma seria igual d'apropiat i més il·lustratiu; k-means guanya quan agrupem milers de clients o milions de lliuraments.)

I aquí es tanca el cercle gran del curs: amb els clústers a la mà, operacions assigna repartidors per grup de zones homogènies... i planificar la ruta de cada repartidor dins del seu grup és, de nou, el TSP del mòdul 2 — aquella instància canònica d'òptim 35,22 km — sobre el graf del mòdul 3, amb l'A* del mòdul 4 per als trajectes i els models d'aquest mòdul predient els temps que alimenten els pesos. L'aprenentatge automàtic no substitueix l'algorísmia clàssica: l'alimenta amb millors dades i millors agrupacions, i aquella decisió final de redisseny la prenen les persones d'operacions amb les anàlisis a la mà.

Taula comparativa

Criteri k-means Jeràrquic (aglomeratiu) DBSCAN
Demana k? Sí, per endavant No (es talla el dendrograma després) No (emergeix de la densitat)
Forma dels clústers Esfèrics, convexos Segons el linkage (single: allargats) Arbitrària
Gestió del soroll No (els outliers arrosseguen centroides) No Sí, etiqueta −1
Cost O(n·k·d) per iteració O(n² log n), memòria O(n²) O(n²), O(n log n) amb índex
Escala a milions Sí No Amb índexs espacials, acceptable
Determinista No (inicialització) Sí Sí (donats eps/min_samples)
Paràmetres delicats k, inicialització linkage, alçada de tall eps, min_samples
Fes-lo servir quan… Grups compactes, dades massives Vols la jerarquia / poques dades Formes rares, outliers, k desconegut

Errors Comuns i Consells

  • Agrupar sense estandarditzar. En el perfil de zones, minuts_lliurament (~20-60) aixafaria retard (~0-0,4): els clústers sortirien d'una sola feature. Sense etiqueta que et delati l'error, pot passar desapercebut — estandarditza sempre.
  • Una sola execució de k-means. Lloyd convergeix al mínim local de torn. Fes servir k-means++ i diversos reinicis (n_init), i compara inèrcies.
  • Prendre el k del colze com a veritat revelada. El colze suggereix; la silueta quantifica; el negoci decideix. Si k=3 i k=4 són semblants en silueta però operacions treballa amb 4 equips de repartiment, la resposta és 4.
  • Interpretar els clústers com a categories reals. Un clúster és una regularitat geomètrica, no una veritat del món. Valida sempre amb coneixement del domini abans d'actuar-hi.
  • Fer servir DBSCAN amb densitats molt dispars. Un únic eps no pot servir alhora per a un nucli urbà dens i un polígon dispers; considera el jeràrquic o variants (HDBSCAN).
  • Consell: dibuixa sempre que puguis (projecta a 2D si cal). En clustering, un cop d'ull a l'scatter amb colors val més que qualsevol mètrica interna.

Exercicis

  1. Lloyd sota la lupa. Modifica kmeans_lloyd perquè guardi la inèrcia a cada iteració i executa'l sobre els perfils de zona (k=3) amb 5 llavors diferents. Comprova que (a) la inèrcia no puja mai dins d'una execució, i (b) llavors diferents poden acabar en inèrcies finals diferents. Quina de les dues propietats hem demostrat i quina és només empírica?

  2. El colze i la silueta. Sobre una mostra estandarditzada de 500 lliuraments del dataset canònic (features: distancia_km, hora_sortida, pes_kg), calcula la inèrcia de k-means per a k=2..8 i la silueta mitjana (sklearn.metrics.silhouette_score) per a cada k. Coincideixen el colze i el màxim de silueta? Què faries si no coincideixen?

  3. Kruskal com a clusteritzador. Aplica clusters_per_mst amb k=3 als perfils de zona estandarditzats i compara les particions amb les de k-means i amb AgglomerativeClustering(n_clusters=3, linkage="single") de sklearn. Verifica que MST i single-linkage coincideixen exactament i explica per què k-means pot diferir.

Solucions

Exercici 1:

# Dins del bucle de kmeans_lloyd, després d'assignar:
#   historial.append(float(((X - centroides[assig]) ** 2).sum()))
for s in range(5):
    assig, _, inercia = kmeans_lloyd(P_e, 3, llavor=s)
    print(f"llavor {s}: inercia final = {inercia:.3f}")

(a) és un teorema: cada pas d'assignació i d'actualització no pot augmentar la inèrcia (ho hem argumentat en presentar Lloyd), així que l'historial és monòton no creixent en tota execució. (b) és empírica: la convergència és a un mínim local, i quin toqui depèn de l'arrencada — veuràs llavors que acaben en inèrcies diferents. D'aquí k-means++ i els reinicis.

Exercici 2:

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

Xm = np.column_stack([dades["distancia_km"], dades["hora_sortida"],
                      dades["pes_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}")

Amb dades de lliuraments individuals (força contínues, sense grups gaire marcats), és normal que el colze sigui suau i la silueta modesta i amb màxim en k petit: senyal honest que l'estructura de grups és feble. Si colze i silueta no coincideixen, ni l'un ni l'altra manen: s'examinen els candidats (visualització, perfils mitjans de cada clúster) i decideix la interpretabilitat i l'ús de negoci. "No hi ha clústers nítids" també és un resultat vàlid de l'anàlisi.

Exercici 3:

from sklearn.cluster import AgglomerativeClustering

mst = clusters_per_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 i single-linkage produeixen la mateixa partició (les etiquetes poden estar permutades — compara l'agrupació, no els números): són el mateix algorisme, com hem argumentat, amb la seqüència de fusions dictada per les arestes del MST. k-means pot diferir perquè optimitza una altra cosa (inèrcia respecte de centroides, afavorint grups rodons i equilibrats), mentre que single-linkage segueix cadenes de proximitat encara que formin grups allargats o de mides dispars.

Conclusió

Amb el clustering completem el mapa del mòdul: aprenentatge no supervisat, on no s'imita una etiqueta sinó que es descobreix estructura. Has vist k-means per dins (Lloyd i la seva inèrcia monòtona, k-means++ amb la seva garantia probabilística, el colze i la silueta per triar k, i els seus supòsits esfèrics), el jeràrquic amb el seu dendrograma multiescala, i DBSCAN trobant clústers de forma lliure i assenyalant el soroll — amb la revelació que single-linkage és exactament el Kruskal del mòdul 3 tallat per les seves arestes més cares: l'algorísmia clàssica i l'aprenentatge automàtic són el mateix continent. I amb ella es tanca el mòdul 5 sencer: vam partir d'un canvi de paradigma —deixar que les regles s'aprenguin de les dades— i l'hem recorregut complet: el protocol honest d'avaluació (05-01), classificar (05-02), predir quantitats amb el descens de gradient com a motor (05-03), compondre no-linealitat amb xarxes i retropropagació (05-04) i descobrir estructura sense etiquetes (05-05), sempre sobre els mateixos 2000 lliuraments del dataset canònic de Rutalia. Ara tens l'arsenal complet del curs: anàlisi i estructures (mòdul 1), optimització (mòdul 2), grafs (mòdul 3), cerca i ordenació (mòdul 4) i aprenentatge automàtic (mòdul 5). Al mòdul 6 deixem d'esmolar eines i sortim al món: casos d'estudi reals on aquests algorismes es combinen —optimització a la indústria, grafs a les xarxes socials, cerca i ordenació a gran escala, i el ML d'aquest mòdul posat a treballar en producció—, començant a 06-01 per l'optimització a la indústria.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats