El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

A 05-01 vam construir el nostre primer classificador (k-NN) per predir si un lliurament de Rutalia arribarà tard, i vam deixar dos serrells pendents: k-NN té límits seriosos, i l'exactitud és una mètrica que enganya. Aquesta lliçó resol totes dues coses. Recorrerem el catàleg de classificadors fonamentals —arbres de decisió, random forest, Naive Bayes i regressió logística—, implementant a mà la mecànica de cadascun (això segueix sent un curs d'algorismes: entropia, particions recursives, probabilitats condicionades), i aprendrem a avaluar seriosament amb matriu de confusió, precisió, recall, F1 i la corba ROC. L'escenari segueix sent el dataset canònic: 2000 lliuraments històrics, llavor 42, i una pregunta de negoci real per a Rutalia: quins lliuraments es retardaran, per poder avisar el client abans que passi?

Contingut

El problema de classificació a Rutalia
k-NN revisitat: els seus límits
Arbres de decisió: aprendre preguntes
Random forest: la saviesa del bosc
Naive Bayes: classificar amb probabilitats
Regressió logística: el classificador lineal
Mètriques de debò: quan l'exactitud enganya
Taula comparativa de classificadors

El problema de classificació a Rutalia

Classificar és assignar una classe discreta a cada exemple. En el nostre dataset canònic hi ha dos problemes naturals:

Binari: retard ∈ {0, 1}. Avisem el client C-1042 que el seu paquet arribarà tard?
Multiclasse: tipus d'incidència ∈ {cap, absent, adreça errònia, paquet danyat}. La mecànica és idèntica (els algorismes d'aquesta lliçó generalitzen a k classes); treballarem sobre el binari per claredat.

Partim del pipeline de 05-01 (mateix codi, mateixa llavor):

dades = generar_dataset()                     # 05-01: 2000 lliuraments, llavor 42
X_num = np.column_stack([dades["distancia_km"], dades["pes_kg"],
                         dades["hora_sortida"], dades["dia_setmana"]])
X = np.column_stack([X_num, one_hot(dades["zona"], ZONES)])
y = dades["retard"]
X_tr, X_te, y_tr, y_te = train_test_split_manual(X, y)

k-NN revisitat: els seus límits

k-NN va funcionar bé a 05-01, però té dos problemes estructurals que convé entendre abans de buscar alternatives:

Cost per consulta O(n·d): no hi ha fase d'entrenament, així que cada predicció recorre els n lliuraments històrics calculant d coordenades. Amb els "milions de registres" reals de Rutalia i milers de prediccions per hora, és inviable. (Hi ha estructures espacials —k-d trees, ball trees, cosines dels tries de 01-04— que acceleren el cas de dimensió baixa, però no resolen el fons de la qüestió.)
La maledicció de la dimensionalitat: en dimensió alta, la distància euclidiana perd significat. Amb d gran, gairebé tots els punts queden aproximadament a la mateixa distància entre si, i "el veí més proper" deixa de ser especialment semblant. El nostre one-hot ja ens ha pujat a 13 dimensions; amb centenars de features, k-NN es degrada sense remei.

La conclusió: volem models que comprimeixin les dades en una estructura petita durant l'entrenament i després prediguin en O(profunditat) o O(d). Els següents ho fan.

Arbres de decisió: aprendre preguntes

Un arbre de decisió classifica fent preguntes encadenades sobre les features, com un diagnòstic:

flowchart TD
    A{"distancia_km > 4.2?"} -->|sí| B{"hora punta?"}
    A -->|no| C{"zona = CEN?"}
    B -->|sí| D[RETARD 0.91]
    B -->|no| E[puntual 0.72]
    C -->|sí| F{"distancia_km > 2.9?"}
    C -->|no| G[puntual 0.95]
    F -->|sí| H[RETARD 0.66]
    F -->|no| I[puntual 0.88]

El que és notable: ningú no ha escrit aquestes preguntes. L'algorisme les ha triat de les dades. Com? Mesurant quanta "barreja de classes" elimina cada pregunta candidata.

Impuresa: entropia i Gini

Un node és pur si tots els seus lliuraments són de la mateixa classe. Dues mesures estàndard d'impuresa per a un node amb proporció p de retards:

Mesura	Fórmula	Rang (binari)	Notes
Entropia	−p·log₂(p) − (1−p)·log₂(1−p)	0 (pur) a 1 (meitat i meitat)	Origen en teoria de la informació
Índex de Gini	2·p·(1−p)	0 (pur) a 0,5	Més barat de calcular; l'opció per defecte de sklearn

Totes dues es comporten gairebé igual a la pràctica. El guany d'una pregunta és la impuresa del pare menys la mitjana ponderada de la impuresa dels fills que produeix: l'algorisme tria, a cada node, la pregunta de màxim guany.

def gini(y):
    """Impuresa de Gini d'un conjunt d'etiquetes binàries."""
    if len(y) == 0:
        return 0.0
    p = y.mean()
    return 2 * p * (1 - p)

def millor_tall(X, y):
    """Busca la parella (feature, llindar) que minimitza la impuresa ponderada."""
    millor = (None, None, gini(y))           # sense tall: impuresa actual
    for j in range(X.shape[1]):              # cada feature...
        for llindar in np.unique(X[:, j]):   # ...i cada valor com a llindar
            esq = X[:, j] <= llindar
            if esq.all() or (~esq).all():
                continue                     # tall inútil: no separa res
            imp = (esq.mean() * gini(y[esq])
                   + (~esq).mean() * gini(y[~esq]))
            if imp < millor[2]:
                millor = (j, llindar, imp)
    return millor                            # (feature, llindar, impuresa)

Construcció recursiva: divideix i venceràs

La construcció de l'arbre és divideix i venceràs pur, el patró de 01-03: resoldre el node (triar la millor pregunta), partir les dades en dues i recórrer recursivament cada meitat. El cas base: node pur, sense talls útils, o profunditat màxima assolida.

def construir_arbre(X, y, profunditat_max=3, nivell=0):
    """Retorna un arbre com a dicts imbricats. Fulla = probabilitat de retard."""
    j, llindar, _ = millor_tall(X, y)
    if nivell == profunditat_max or j is None or gini(y) == 0:
        return {"fulla": True, "p_retard": y.mean(), "n": len(y)}
    esq = X[:, j] <= llindar
    return {"fulla": False, "feature": j, "llindar": llindar,
            "esq": construir_arbre(X[esq], y[esq], profunditat_max, nivell + 1),
            "dre": construir_arbre(X[~esq], y[~esq], profunditat_max, nivell + 1)}

def predir_arbre(node, x):
    """Baixa per l'arbre responent les preguntes: O(profunditat)."""
    while not node["fulla"]:
        node = node["esq"] if x[node["feature"]] <= node["llindar"] else node["dre"]
    return int(node["p_retard"] > 0.5)

arbre = construir_arbre(X_tr, y_tr, profunditat_max=3)
acc = np.mean([predir_arbre(arbre, x) == yv for x, yv in zip(X_te, y_te)])
print(f"Arbre (prof. 3): {acc:.3f}")

Observa les propietats algorísmiques: entrenar costa O(d · n²) per nivell en aquesta versió ingènua (sklearn ho abaixa a O(d · n log n) preordenant cada columna, una idea directa de 04-02), però predir costa O(profunditat) — de recórrer 1600 lliuraments per consulta (k-NN) a respondre 3 preguntes. A més, l'arbre no necessita escalat (compara contra llindars, no calcula distàncies) i és interpretable: pots ensenyar el diagrama al cap d'operacions de Rutalia i discutir-lo.

Sobreajustament i poda

Un arbre sense límit de profunditat continua partint fins que cada fulla és pura... encara que tingui un sol lliurament. Això és memoritzar el soroll: la corba en U de 05-01, un altre cop. Antídots:

Pre-poda: limitar profunditat_max, exigir un mínim d'exemples per fulla o un guany mínim per tallar. És el que hem fet (profunditat_max=3).
Post-poda: deixar créixer l'arbre i després eliminar les branques que no milloren l'error de validació (més costós, de vegades millor).

A sklearn: DecisionTreeClassifier(max_depth=3, min_samples_leaf=20). Prova max_depth=None i compara train vs test: veuràs el sobreajustament en directe.

Random forest: la saviesa del bosc

Un arbre individual és inestable: canvia el 5% de les dades i en pot sortir un arbre diferent (alta variància). La solució és sorprenent: entrenar molts arbres diferents i fer-los votar.

Bagging (bootstrap aggregating): cada arbre s'entrena amb una mostra aleatòria amb reemplaçament de l'entrenament (mateixa mida n, però amb repetits i absents). Cada arbre veu dades lleugerament diferents, així que comet errors diferents.
Subespais aleatoris: a cada node, cada arbre només considera un subconjunt aleatori de features (típicament √d). Això descorrelaciona els arbres: sense això, tots començarien tallant per distancia_km i votarien gairebé el mateix.

Per què funciona fer la mitjana? Pel mateix motiu pel qual la mitjana de 100 mesures sorolloses és més fiable que una de sola: si els errors dels arbres són (parcialment) independents, en votar es cancel·len. La variància de la mitjana de T estimadors independents és la individual dividida per T. Els arbres no són independents del tot, però el bagging i els subespais els hi acosten — d'aquí l'obstinació a descorrelacionar-los.

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(n_estimators=200, max_depth=None,
                            random_state=42).fit(X_tr, y_tr)
print(f"Random forest: {rf.score(X_te, y_te):.3f}")

Detall elegant: cada arbre individual pot sobreajustar (profunditat lliure), perquè la mitjana corregeix la variància. Es perd la interpretabilitat de l'arbre únic, però rf.feature_importances_ encara diu quines features importen — a Rutalia veuràs dominar distancia_km, hora_sortida i les zones congestionades, coherent amb la veritat oculta del generador.

Naive Bayes: classificar amb probabilitats

Canvi total de filosofia: en lloc d'aprendre fronteres, modelem probabilitats. El teorema de Bayes ens dona la probabilitat de retard donades les features:

P(retard | x)  =  P(x | retard) · P(retard) / P(x)

El problema: estimar P(x | retard) per a cada combinació completa de features exigiria dades astronòmiques. La suposició "naive" (ingènua) ho salva: assumir que les features són independents entre si dins de cada classe, de manera que la probabilitat conjunta es factoritza en un producte de probabilitats individuals — cadascuna trivial d'estimar comptant.

És falsa en general (a Rutalia, zona i distància estan correlacionades), però el classificador només necessita que la classe correcta obtingui el producte més gran, no probabilitats exactes. Per això Naive Bayes funciona millor del que la seva suposició mereixeria.

Exemple amb features categòriques (zona i franja horària):

def entrenar_nb(zones, franges, y):
    """Estima les taules de probabilitat per recompte, amb suavitzat de Laplace."""
    model = {}
    for c in (0, 1):
        m = (y == c)
        model[c] = {
            "prior": m.mean(),               # P(classe)
            # P(zona | classe): recompte + 1 (Laplace) per no donar probabilitat 0
            "p_zona": {z: (np.sum(zones[m] == z) + 1) / (m.sum() + len(ZONES))
                       for z in ZONES},
            "p_franja": {f: (np.sum(franges[m] == f) + 1) / (m.sum() + 3)
                         for f in ("mati", "punta", "tarda")},
        }
    return model

def predir_nb(model, zona, franja):
    """Compara log-probabilitats (sumes, no productes: evita l'underflow)."""
    scores = {c: np.log(m["prior"]) + np.log(m["p_zona"][zona])
                 + np.log(m["p_franja"][franja])
              for c, m in model.items()}
    return max(scores, key=scores.get)

Dos detalls d'enginyeria que són pura pràctica algorísmica:

Suavitzat de Laplace (+1 als recomptes): sense això, una combinació mai vista a l'entrenament (retard a PAR de matinada?) tindria probabilitat 0 i anul·laria tot el producte.
Log-probabilitats: multiplicar moltes probabilitats petites provoca underflow numèric; sumar logaritmes és equivalent (el log és monòton) i estable.

Naive Bayes entrena en una sola passada de recompte, O(n·d), prediu en O(d) i funciona sorprenentment bé amb poques dades i moltes features categòriques (el seu hàbitat clàssic: filtres de spam). A sklearn: CategoricalNB, GaussianNB (features contínues) o MultinomialNB (recomptes).

Regressió logística: el classificador lineal

El quart enfocament: una frontera lineal. Es calcula una puntuació z = w·x + b (combinació lineal de les features, com a la programació lineal de 02-01) i es converteix en probabilitat amb la funció sigmoide:

σ(z) = 1 / (1 + e^(−z))        σ(−∞)→0,  σ(0)=0.5,  σ(+∞)→1

def sigmoide(z):
    return 1 / (1 + np.exp(-z))

def predir_logistica(w, b, x):
    p = sigmoide(x @ w + b)     # probabilitat de retard
    return int(p > 0.5)

Geomètricament, w·x + b = 0 defineix un hiperplà que parteix l'espai en dos: a una banda es prediu retard, a l'altra puntualitat. La distància (amb signe) a l'hiperplà gradua la confiança via la sigmoide. És el classificador lineal per excel·lència: simple, ràpid (O(d) per predicció), amb coeficients interpretables ("cada km afegit multiplica les odds de retard per e^w₁").

I d'on surten w i b? S'aprenen minimitzant una funció de cost mitjançant descens de gradient — l'algorisme que desenvoluparem amb tot detall a 05-03. Aquí n'hi ha prou amb la idea: començar amb pesos aleatoris i ajustar-los iterativament en la direcció que redueix l'error. A sklearn: LogisticRegression() (necessita features escalades, com tot model basat en w·x). El seu límit és evident: si la frontera real no és lineal (i la veritat multiplicativa de Rutalia no ho és), un hiperplà només pot aproximar-la — la sortida d'aquest carreró són les xarxes neuronals de 05-04, que apilen moltes d'aquestes unitats.

Mètriques de debò: quan l'exactitud enganya

Arribem al deute pendent de 05-01. En el nostre dataset, ~85% dels lliuraments són puntuals. El classificador "tot puntual" assoleix un 85% d'exactitud sent perfectament inútil: no detecta ni un sol retard, que és justament el que Rutalia vol detectar.

Matriu de confusió

Tot comença per desglossar els quatre resultats possibles:

	Predit: retard	Predit: puntual
Real: retard	VP (veritable positiu)	FN (fals negatiu) — retard no avisat
Real: puntual	FP (fals positiu) — avís en fals	VN (veritable negatiu)

def matriu_confusio(y_real, y_pred):
    vp = np.sum((y_real == 1) & (y_pred == 1))
    fn = np.sum((y_real == 1) & (y_pred == 0))
    fp = np.sum((y_real == 0) & (y_pred == 1))
    vn = np.sum((y_real == 0) & (y_pred == 0))
    return vp, fn, fp, vn

Precisió, recall i F1

Precisió = VP / (VP + FP): dels avisos de retard que emetem, quina fracció era real? Mesura el cost dels avisos en fals.
Recall (sensibilitat) = VP / (VP + FN): dels retards reals, quina fracció detectem? Mesura els retards que se'ns escapen.
F1 = mitjana harmònica de totes dues = 2·P·R / (P + R). L'harmònica castiga el desequilibri: si una de les dues és propera a 0, l'F1 s'enfonsa encara que l'altra sigui 1.

El classificador "tot puntual" queda retratat: recall = 0, F1 = 0, per molt 85% d'exactitud que exhibeixi. I hi ha un trade-off inherent: abaixar el llindar de decisió (avisar amb p > 0.3 en lloc de p > 0.5) apuja el recall (caces més retards) però abaixa la precisió (més falses alarmes). Quin prioritzar és una decisió de negoci: si l'avís és un SMS barat, Rutalia voldrà recall alt; si dispara una compensació econòmica, precisió alta. La mètrica es tria mirant el cost real de cada tipus d'error — i la decisió final sobre què fer amb cada client continua sent humana; el model només prioritza.

Corba ROC i AUC (breu)

Els classificadors probabilístics permeten moure el llindar de 0 a 1. La corba ROC dibuixa, per a cada llindar, la taxa de veritables positius davant de la de falsos positius. L'AUC (àrea sota aquesta corba) resumeix la qualitat global: 1,0 és perfecte, 0,5 és llançar una moneda. La seva lectura més útil: l'AUC és la probabilitat que el model puntuï més alt un retard real que un lliurament puntual, triats a l'atzar. A sklearn: roc_auc_score(y_te, model.predict_proba(X_te)[:, 1]). És la mètrica de comparació estàndard quan encara no s'ha fixat el llindar operatiu.

Taula comparativa de classificadors

Criteri	k-NN	Arbre de decisió	Random forest	Naive Bayes	Reg. logística
Entrenament	Cap	O(d·n log n)	T arbres	O(n·d), una passada	Iteratiu (gradient)
Predicció	O(n·d) ✗	O(prof.) ✓	O(T·prof.)	O(d) ✓	O(d) ✓
Necessita escalat?	Sí	No	No	No	Sí
Frontera no lineal?	Sí	Sí (a trams)	Sí	Limitada	No
Interpretabilitat	Baixa	Alta	Mitjana (importàncies)	Mitjana	Alta (coeficients)
Risc de sobreajustament	k petit	Alt sense poda	Baix	Baix	Baix
Punt fort	Simplicitat	Explicable a negoci	Precisió "de sèrie"	Poques dades, categòriques	Base sòlida i ràpida

Regla pràctica per a dades tabulars com les de Rutalia: comença amb regressió logística com a base (baseline), prova un random forest (sol ser el més fort sense ajust fi) i fes servir l'arbre simple quan necessitis explicar la decisió.

Errors Comuns i Consells

Presumir d'exactitud amb classes desequilibrades. El 85% del "tot puntual" és el terra, no una fita. Mira sempre la matriu de confusió i l'F1 de la classe minoritària.
Deixar créixer l'arbre sense límit. Error de train 0% i test mediocre = sobreajustament de manual. Limita la profunditat o el mínim d'exemples per fulla, i compara sempre train vs test.
Oblidar el suavitzat a Naive Bayes. Una sola probabilitat 0 aniquila el producte sencer. Laplace (+1) és una línia de codi que evita prediccions absurdes.
Multiplicar probabilitats en lloc de sumar logs. Amb desenes de features, el producte fa underflow a 0.0 silenciosament. Treballa sempre en espai logarítmic.
Escalar per a arbres / no escalar per a la logística. Els arbres comparen contra llindars (l'escalat els és igual); els models amb w·x (logística, k-NN) l'exigeixen. Conèixer la mecànica interna evita l'error.
Consell: fixa el llindar de decisió segons el cost de negoci de FP vs FN, no pel 0,5 per defecte. És gratis i sol valer més que canviar d'algorisme.

Exercicis

L'arbre contra el bosc. Amb el dataset canònic, entrena DecisionTreeClassifier amb max_depth ∈ {2, 4, 8, None} i un RandomForestClassifier(n_estimators=200). Per a cada model imprimeix l'exactitud en train i en test. Amb quina profunditat l'arbre sobreajusta clarament? El bosc sobreajusta encara que els seus arbres tinguin profunditat lliure?
La trampa de l'exactitud, amb números. Implementa el classificador trivial "tot puntual" i compara'l amb el random forest de l'exercici 1 fent servir: exactitud, precisió, recall i F1 (calculats amb la teva matriu_confusio). Redacta en una frase per què Rutalia no hauria de desplegar mai el trivial malgrat la seva exactitud.
Moure el llindar. Amb rf.predict_proba(X_te)[:, 1] obtén les probabilitats de retard i avalua precisió i recall per a llindars de 0,3, 0,5 i 0,7. Quin llindar triaries si l'avís al client és un SMS gratuït? I si cada avís dispara un descompte del 20%?

Solucions

Exercici 1:

from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier

for prof in [2, 4, 8, None]:
    a = DecisionTreeClassifier(max_depth=prof, random_state=42).fit(X_tr, y_tr)
    print(f"prof={str(prof):>4}  train={a.score(X_tr, y_tr):.3f}  test={a.score(X_te, y_te):.3f}")

rf = RandomForestClassifier(n_estimators=200, random_state=42).fit(X_tr, y_tr)
print(f"bosc        train={rf.score(X_tr, y_tr):.3f}  test={rf.score(X_te, y_te):.3f}")

Amb max_depth=None l'arbre clava el train (≈1,0) i perd en test: sobreajustament clar; el forat train−test creix amb la profunditat. El bosc també frega l'1,0 en train (els seus arbres són profunds) però manté el test alt: la mitjana d'arbres descorrelacionats absorbeix la variància que condemna l'arbre solitari.

Exercici 2:

pred_trivial = np.zeros_like(y_te)
pred_rf = rf.predict(X_te)

for nom, pred in [("trivial", pred_trivial), ("bosc", pred_rf)]:
    vp, fn, fp, vn = matriu_confusio(y_te, pred)
    prec = vp / (vp + fp) if vp + fp else 0.0
    rec = vp / (vp + fn) if vp + fn else 0.0
    f1 = 2 * prec * rec / (prec + rec) if prec + rec else 0.0
    acc = (vp + vn) / len(y_te)
    print(f"{nom}: acc={acc:.3f} prec={prec:.3f} recall={rec:.3f} F1={f1:.3f}")

El trivial ronda acc≈0,85 però amb recall=0 i F1=0: no detecta cap retard. El bosc tindrà menys marge en exactitud del que suggereix la intuïció, però un recall i un F1 molt superiors. Frase: el trivial no avisa de cap retard, que és exactament l'única funció del sistema; la seva exactitud només reflecteix que els retards són rars.

Exercici 3:

probs = rf.predict_proba(X_te)[:, 1]
for u in (0.3, 0.5, 0.7):
    pred = (probs > u).astype(int)
    vp, fn, fp, vn = matriu_confusio(y_te, pred)
    print(f"llindar {u}: precisió={vp/(vp+fp):.3f}  recall={vp/(vp+fn):.3f}")

Amb llindar 0,3 el recall puja (es cacen més retards) a costa de la precisió; amb 0,7, al revés. SMS gratuït → falses alarmes barates → llindar baix (0,3), prioritza el recall. Descompte del 20% → cada FP costa diners → llindar alt (0,7), prioritza la precisió. La mètrica correcta depèn del cost real de cada error, no de l'estadística.

Conclusió

Ja tens el catàleg essencial de la classificació i, més important, la seva mecànica interna: els arbres aprenen preguntes maximitzant la puresa amb divideix i venceràs; el bosc fa la mitjana d'arbres descorrelacionats per matar la variància; Naive Bayes compta i multiplica probabilitats (en logaritmes, amb Laplace); i la regressió logística traça un hiperplà i gradua la confiança amb la sigmoide. També saps avaluar de debò: la matriu de confusió, precisió/recall/F1 i el llindar com a decisió de negoci, perquè amb un 85% de lliuraments puntuals l'exactitud sola és fum. Ens queda un deute tècnic confessat: hem dit que els pesos de la regressió logística "s'aprenen minimitzant un cost amb descens de gradient", sense explicar com. A 05-03 saldem aquest deute: passem a predir els minuts de lliurament (regressió), i allà desenvoluparem el descens de gradient peça a peça — l'algorisme que, a més, és el pont directe cap a les xarxes neuronals de 05-04.

Algorismes de Classificació