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

Anàlisi d'agrupament DBSCAN

Següent ►
►

K-means dibuixa esferes i assigna tots els punts a algun clúster; el jeràrquic fusiona fins on li diguis. Cap dels dos no sap dir "aquest punt no pertany a cap grup" — i per a MercaFresh aquesta frase val diners, perquè una comanda que no s'assembla a cap patró conegut pot ser un error de dades, un abús de promocions o un frau. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) agrupa per densitat: un clúster és una zona on els punts s'apinyen, tingui la forma que tingui, i el que queda en zones despoblades s'etiqueta com a soroll. En aquesta lliçó aprendràs els seus tres tipus de punts (core, border, noise), els seus dos paràmetres (eps i min_samples) i com triar-los amb el gràfic k-distance, veuràs amb make_moons un cas on K-means fracassa i DBSCAN encerta, i l'aplicaràs a la detecció de comandes anòmales a MercaFresh, connectant-lo amb els detectors estadístics dels mòduls anteriors.

Contingut

  1. Clustering per densitat: la idea
  2. Punts core, border i noise
  3. Els paràmetres eps i min_samples
  4. Com triar eps: el gràfic k-distance
  5. On K-means falla: formes no esfèriques (make_moons)
  6. Detecció d'anomalies en comandes MercaFresh
  7. Comparativa: K-means vs. jeràrquic vs. DBSCAN
  8. Limitacions de DBSCAN

Clustering per densitat: la idea

Els dos algorismes anteriors definien un clúster per proximitat a un centre (K-means) o per ordre de fusió (jeràrquic). DBSCAN el defineix per densitat local: un clúster és un conjunt de punts connectats entre si a través de zones denses. La intuïció és cartogràfica: si els clients fossin cases, els clústers serien els pobles — tant és si el poble és rodó, allargat o amb forma de ferradura; el que importa és que les cases estiguin juntes. I les cases aïllades enmig de la muntanya no pertanyen a cap poble: són soroll.

D'aquesta definició en surten gratis les tres propietats que distingeixen DBSCAN:

  • Clústers de qualsevol forma (segueix la densitat, no la distància a un centre).
  • No cal fixar K: troba tants clústers com zones denses existeixin.
  • Concepte natiu de soroll: els punts de zones despoblades reben l'etiqueta especial −1.

Punts core, border i noise

DBSCAN classifica cada punt segons quanta companyia té al seu veïnat de radi eps:

Tipus Definició Paper
Core (nucli) Té almenys min_samples punts (ell inclòs) a distància ≤ eps L'esquelet del clúster: els clústers creixen connectant cores veïns
Border (frontera) No és core, però està a ≤ eps d'algun core Pertany al clúster d'aquest core, sense poder expandir-lo
Noise (soroll) Ni core ni border Etiqueta −1: no pertany a cap clúster 
flowchart LR
    subgraph Cluster["Zona densa = cluster"]
        C1["● core"] --- C2["● core"] --- C3["● core"]
        C3 --- B1["◐ border<br/>(a prop d'un core,<br/>pero amb pocs veins)"]
    end
    N1["○ noise<br/>(aillat: a mes d'eps<br/>de qualsevol core)"]
    Cluster -.-> |"> eps"| N1

L'algorisme funciona així: pren un punt no visitat; si és core, obre un clúster i l'expandeix recursivament amb tots els punts abastables a través de cores encadenats (cada core annexiona el seu veïnat, i els cores del veïnat annexionen el seu); els border se sumen al clúster que els abasta; quan res més no és abastable, el clúster es tanca i es busca el següent core lliure. El que mai no és abastat, queda com a noise. Nota el parentiu amb el single linkage de 05-02 —també encadenava veïns propers—, però amb un filtre de densitat que impedeix que un pont de dos o tres punts solts uneixi dos pobles: per estendre pont calen cores, i ser core exigeix companyia.

Els paràmetres eps i min_samples

Tota la conducta de DBSCAN penja de dos paràmetres:

  • eps: el radi del veïnat. És la definició operativa de "a prop". Massa petit → gairebé ningú no reuneix veïns, gairebé tot és soroll. Massa gran → els veïnats se solapen entre grups diferents i tot col·lapsa en un megaclúster.
  • min_samples: quants veïns calen per ser core. És la definició de "dens". Valors majors exigeixen clústers més massissos i expulsen més punts al soroll. Regla pràctica habitual: min_samples ≈ 2 × nombre de dimensions, i mai menys de 4 llevat de datasets minúsculs.

I una advertència ja familiar: eps és una distància euclidiana, així que les features han d'estar escalades (03-05). Un eps=0.5 significa coses radicalment diferents en euros i en desviacions estàndard.

Com triar eps: el gràfic k-distance

min_samples es fixa amb la regla pràctica; per a eps existeix un mètode gràfic estàndard, el k-distance plot:

  1. Per a cada punt, calcula la distància al seu k-èsim veí més proper, amb k = min_samples (eina coneguda: NearestNeighbors, la maquinària de 04-05).
  2. Ordena aquestes distàncies de menor a major i dibuixa-les.
  3. La corba puja suau mentre recorre punts de zones denses (el seu k-èsim veí és a prop) i es dispara en arribar als punts aïllats. El colze de la corba és el candidat a eps: la frontera entre "distància normal als teus veïns" i "estàs sol".
import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import NearestNeighbors

k = 5                                   # = min_samples previst
nn = NearestNeighbors(n_neighbors=k).fit(X_esc)
dist, _ = nn.kneighbors(X_esc)          # distancies als k veins mes propers
d_k = np.sort(dist[:, -1])              # distancia al k-esim, ordenada

plt.plot(d_k)
plt.xlabel("Punts ordenats")
plt.ylabel(f"Distància al veí {k}")
plt.title("Gràfic k-distance: el colze suggereix eps")
plt.show()

Si la corba es manté per sota de ~0,6 i es dispara a partir d'aquí, eps=0.6 és un bon punt de partida — que afinarem mirant quants clústers i quant soroll produeix. És el tercer "colze" del mòdul (inèrcia a 05-01, dendrograma a 05-02): buscar el salt brusc d'una corba és un patró recurrent per separar senyal de soroll.

On K-means falla: formes no esfèriques (make_moons)

La demostració clàssica usa make_moons, un dataset sintètic amb dues mitges llunes entrellaçades — dos grups evidents per a l'ull humà, però no esfèrics:

from sklearn.datasets import make_moons
from sklearn.cluster import KMeans, DBSCAN
from sklearn.preprocessing import StandardScaler

X, _ = make_moons(n_samples=400, noise=0.07, random_state=42)
X_esc = StandardScaler().fit_transform(X)

km_lab = KMeans(n_clusters=2, random_state=42).fit_predict(X_esc)
db_lab = DBSCAN(eps=0.3, min_samples=5).fit_predict(X_esc)

fig, axes = plt.subplots(1, 2, figsize=(11, 4))
axes[0].scatter(X_esc[:, 0], X_esc[:, 1], c=km_lab, s=12)
axes[0].set_title("K-means: parteix cada lluna per la meitat")
axes[1].scatter(X_esc[:, 0], X_esc[:, 1], c=db_lab, s=12)
axes[1].set_title("DBSCAN: recupera les dues llunes")
plt.show()

El resultat és eloqüent:

  • K-means traça una frontera recta entre els seus dos centroides i parteix cada lluna per la meitat, barrejant trossos de totes dues en cada clúster. No és un error d'ajust: és la seva geometria — tot punt va al centroide més proper, i els centroides de dues llunes entrellaçades cauen on cauen. Cap n_init no ho arregla.
  • DBSCAN recorre cada lluna encadenant cores veïns: la densitat és contínua al llarg de la mitja lluna i es talla entre l'una i l'altra. Recupera les dues formes exactes i marca com a −1 els punts solts del soroll.

Aquest exemple tanca l'advertència de 05-01 ("clústers esfèrics"): quan l'estructura no és convexa, no cal un K-means més ben ajustat sinó un algorisme amb una altra definició de clúster.

Detecció d'anomalies en comandes MercaFresh

Ara l'ús estrella per a MercaFresh. Canviem de taula: en lloc de clients, comandes individuals, amb features com l'import, el nombre d'articles i l'hora del dia. La pregunta ja no és "quins grups hi ha?" sinó "quines comandes no encaixen en cap grup?" — i aquí l'etiqueta −1 de DBSCAN passa de subproducte a protagonista.

import pandas as pd
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import DBSCAN

features = ["import_comanda", "num_articles", "hora_comanda"]
X = comandes[features]
X_esc = StandardScaler().fit_transform(X)

db = DBSCAN(eps=0.6, min_samples=6)          # eps del k-distance; min_samples ~ 2x3 dims
comandes["cluster"] = db.fit_predict(X_esc)

anomales = comandes[comandes["cluster"] == -1]
print(f"Comandes anòmales: {len(anomales)} de {len(comandes)} "
      f"({len(anomales)/len(comandes):.1%})")
print(anomales[features].head())

Què troba cada etiqueta:

  • Els clústers (0, 1, 2...) són els patrons normals de compra: la compra setmanal gran de migdia, la compra ràpida nocturna de pocs articles, etc. Ningú no els va demanar: emergeixen de la densitat.
  • Els −1 són comandes sense patró: un import de 900 € a les 4 de la matinada amb 3 articles; 70 unitats del mateix producte en promoció. Candidats a revisió manual, no culpables automàtics: l'anomalia estadística és una alerta, no un veredicte.

Aquest detector és el tercer d'una sèrie que el curs ha anat construint, i convé veure'ls com a complementaris:

Detector Base Detecta Limitació
Z-score (02-02) Distància a la mitjana en desviacions, per variable Valors extrems en una variable Cec a combinacions: 30 € a les 4 de la matinada és normal en cada variable per separat
Bayes / frau (02-05) Probabilitats condicionades a patrons coneguts El que s'assembla al frau ja vist Necessita exemples previs del patró fraudulent
DBSCAN (aquesta lliçó) Densitat multivariant, sense etiquetes Combinacions rares mai vistes No diu per què és rar; sensible a eps

En un sistema real de MercaFresh conviurien tots tres: el z-score com a primer filtre barat per variable, DBSCAN caçant combinacions inèdites i els senyals bayesians puntuant els patrons de frau documentats. (El projecte 09-04 munta un detector de frau complet; aquí ens quedem amb el paper de DBSCAN.)

Comparativa: K-means vs. jeràrquic vs. DBSCAN

Amb els tres algorismes de clustering del mòdul sobre la taula, la taula de decisió:

Criteri K-means (05-01) Jeràrquic (05-02) DBSCAN (05-04)
Forma de clústers Esfèrica/convexa Segons l'enllaç (Ward ≈ esfèrica; single, cadenes) Arbitrària (segueix la densitat)
K a priori? Sí No (es talla el dendrograma) No (emergeix d'eps/min_samples)
Maneig del soroll No: tot punt a un clúster No (encara que single l'insinua) Sí: etiqueta −1 nativa
Paràmetres clau K enllaç + alçada de tall eps + min_samples
Determinista No (mitigat amb n_init) Sí Sí (llevat d'empats en borders)
Cost Baix: escala a milions $O(n^2)$–$O(n^3)$: milers Mitjà: ~$O(n \log n)$ amb índexs espacials
Requereix escalar Sí Sí Sí
Ideal per a Segments compactes a gran escala Explorar estructura, jerarquies Formes irregulars, anomalies

L'elecció no és cap concurs: a MercaFresh acabem d'usar K-means/jeràrquic per segmentar clients (grups compactes i interpretables) i DBSCAN per vigilar comandes (formes lliures i soroll). Cada pregunta va triar el seu algorisme.

Limitacions de DBSCAN

  • Densitats variables. El taló d'Aquil·les: un únic eps global no pot servir alhora a un clúster molt dens i a un altre de difús — l'eps que preserva el segon fusiona el primer amb els seus veïns, i l'eps del primer desintegra el segon en soroll. (Existeixen variants com HDBSCAN que jerarquitzen la densitat; queden fora d'aquest curs, però convé saber-ne el nom.)
  • Elecció d'eps delicada. El k-distance ajuda, però dècimes amunt o avall canvien el nombre de clústers i el % de soroll. Analitza sempre la sensibilitat provant 2-3 valors al voltant del colze.
  • Alta dimensionalitat. DBSCAN és tan víctima de la maledicció (05-03) com qualsevol mètode de distàncies: amb moltes dimensions les densitats es dilueixen i "a prop" perd sentit. PCA abans de DBSCAN és una combinació habitual.
  • Punts border ambigus. Un border abastable des de dos clústers s'assigna al primer que el visita: petites variacions d'ordre poden moure punts fronterers (el soroll i els cores, en canvi, són estables).
  • Sense centroides. No hi ha una "comanda mitjana" per clúster a perfilar directament; per interpretar un clúster de DBSCAN es calculen estadístics descriptius (02-01) dels seus membres.

Errors Comuns i Consells

  • Executar DBSCAN sense escalar. eps és una distància: amb features en unitats dispars, el radi només "veu" la variable gran. StandardScaler primer, com en tot el mòdul.
  • Tractar el −1 com un clúster més. En perfilar resultats o calcular el silhouette, el soroll no és un grup: filtra'l (etiquetes != -1) abans de descriure clústers, i reporta'l a part com a % de soroll.
  • Ajustar eps fins que el soroll desaparegui. Si el teu objectiu és detectar anomalies, el soroll és el resultat! Un 1-5% de soroll sol ser raonable; 0% significa que has engrandit eps fins a empassar-te les anomalies; 40% significa que l'has empetitit fins a desintegrar els clústers.
  • Copiar l'eps d'un altre dataset. eps depèn de l'escala, la dimensió i la densitat de les teves dades: recalcula el k-distance a cada problema, fins i tot entre versions del mateix dataset.
  • Consell: reporta sempre juntament amb el clustering tres números — nombre de clústers, % de soroll i mida del clúster més gran. Són el diagnòstic instantani d'un eps mal triat (1 clúster gegant = eps gran; soroll massiu = eps petit).

Exercicis

Exercici 1. A mà, amb eps=2 i min_samples=3, classifica com a core, border o noise els punts 1D: [1, 2, 3, 10, 11, 30]. (Distància = valor absolut de la diferència; recorda que el mateix punt compta com a veí.) Quants clústers en resulten i quins punts queden com a soroll?

Exercici 2. Genera make_moons(n_samples=500, noise=0.1, random_state=0), escala, i executa DBSCAN amb min_samples=5 i tres valors d'eps: 0,1, 0,3 i 1,0. Per a cadascun imprimeix el nombre de clústers (excloent el −1) i el % de soroll, i dibuixa els tres resultats. Relaciona el que veus amb el colze del k-distance.

Exercici 3. Simula 300 comandes normals de MercaFresh (import_comanda ~ N(45, 15), num_articles ~ N(18, 6)) i afegeix 5 comandes anòmales (import 400-600 amb 2-4 articles). Escala, tria eps amb el k-distance i comprova si DBSCAN marca les 5 com a soroll. Compara amb un z-score univariant (02-02) sobre import_comanda: també les hauria detectades? I si l'import anòmal fos 60 € amb 2 articles?

Solucions

Exercici 1

Veïnats de radi 2 (comptant-se un mateix): l'1 té {1,2,3} → 3 veïns → core; el 2 té {1,2,3} → core; el 3 té {1,2,3} → core (el 10 queda a distància 7). El 10 té {10,11} → 2 < 3 → no core, border? No està a ≤2 de cap core → noise; l'11, igual → noise; el 30 està sol → noise. Resultat: 1 clúster {1,2,3} i tres punts de soroll {10,11,30}. Observa la subtilesa: 10 i 11 estan junts, però dos punts no basten per fundar un clúster amb min_samples=3 — la densitat exigeix massa crítica, no només proximitat. Amb min_samples=2 haurien format un segon clúster.

Exercici 2

X, _ = make_moons(n_samples=500, noise=0.1, random_state=0)
X_esc = StandardScaler().fit_transform(X)

for eps in [0.1, 0.3, 1.0]:
    lab = DBSCAN(eps=eps, min_samples=5).fit_predict(X_esc)
    n_clu = len(set(lab)) - (1 if -1 in lab else 0)
    soroll = (lab == -1).mean()
    print(f"eps={eps} | clusters={n_clu} | soroll={soroll:.1%}")

Patró esperat: eps=0.1 fragmenta les llunes en molts miniclústers amb molt de soroll (radi menor que la distància típica entre veïns); eps=0.3 dona 2 clústers amb poc soroll — és a prop del colze del k-distance, que per a aquestes dades ronda el 0,2-0,3; eps=1.0 ho fusiona tot en 1 clúster sense soroll (el radi salta el buit entre llunes). La seqüència fragmentació → estructura correcta → col·lapse és el comportament canònic d'eps.

Exercici 3

rng = np.random.default_rng(42)
normals = pd.DataFrame({"import_comanda": rng.normal(45, 15, 300).clip(5),
                        "num_articles": rng.normal(18, 6, 300).clip(1)})
rares = pd.DataFrame({"import_comanda": [420, 480, 510, 555, 600],
                      "num_articles": [3, 2, 4, 2, 3]})
comandes = pd.concat([normals, rares], ignore_index=True)

X_esc = StandardScaler().fit_transform(comandes)
lab = DBSCAN(eps=0.5, min_samples=5).fit_predict(X_esc)   # eps segons el teu k-distance
print(comandes[lab == -1])

Les 5 anòmales apareixen com a −1 (imports a més de 20 desviacions del gruix: aïlladíssimes a l'espai escalat); pot caure també en soroll alguna comanda normal extrema — revisar el % total. El z-score sobre import_comanda també les caçaria (z ≈ +25). La diferència sorgeix amb el cas final: 60 € i 2 articles té z-scores individuals modestos (z ≈ 1 en import, z ≈ −2,7 en articles, cap d'escandalós), però la combinació "import normal amb només 2 articles" (dos articles de 30 €? en un supermercat és atípic) viu en una zona despoblada del pla i DBSCAN pot assenyalar-la. Aquest és exactament l'avantatge multivariant sobre el z-score univariant que anunciava la taula de la lliçó.

Conclusió

DBSCAN completa el teu trio d'algorismes de clustering amb una definició nova: clúster = zona densa, soroll = el que queda fora. Saps classificar punts en core, border i noise, triar min_samples per regla pràctica i eps amb el gràfic k-distance, has vist amb les mitges llunes de make_moons per què la geometria de K-means té límits que cap ajust no arregla, i has posat DBSCAN a fer la feina que millor sap a MercaFresh: assenyalar comandes que no encaixen en cap patró, complementant el z-score univariant de 02-02 i l'enfocament bayesià de 02-05. La taula comparativa dels tres algorismes és, juntament amb la dels set supervisats de 04-07, la teva segona carta de navegació del curs.

Queda una peça per tancar el mòdul. Hem segmentat, jerarquitzat, comprimit i detectat — però per comunicar tot això, una imatge val més que mil taules de centroides, i el mapa 2D de PCA (05-03) era honest però lineal i de vegades borrós. L'última lliçó del mòdul presenta les dues tècniques modernes de visualització que despleguen estructura no lineal en dues dimensions: t-SNE i UMAP, amb els seus poders i les seves trampes d'interpretació.

◄ Anterior
◄
Següent ►
►

Curs de Machine Learning

Mòdul 1: Introducció al Machine Learning

Mòdul 2: Fonaments d'Estadística i Probabilitat

Mòdul 3: Preprocessament de Dades

Mòdul 4: Algorismes de Machine Learning Supervisat

Mòdul 5: Algorismes de Machine Learning No Supervisat

Mòdul 6: Avaluació i Validació de Models

Mòdul 7: Tècniques Avançades i Optimització

Mòdul 8: Implementació i Desplegament de Models

Mòdul 9: Projectes Pràctics

Mòdul 10: Recursos Addicionals

El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats