Tanquem el mòdul 4 amb una constatació: en tot el que portem de curs, el coneixement del problema l'hem aportat nosaltres a mà. Vam dissenyar les regles d'optimització del mòdul 2, vam mesurar els pesos del graf del mòdul 3, vam justificar els invariants i les heurístiques del mòdul 4. Però Rutalia acumula milions de registres històrics de lliuraments —hora, zona, pes, distància, retard, incidències— que contenen patrons que ningú no ha escrit mai com a regla. En aquesta lliçó fem el canvi de paradigma: en lloc de programar les regles, deixarem que els algorismes les aprenguin de les dades. Veurem què significa exactament "aprendre", quins tipus d'aprenentatge existeixen, definirem el dataset canònic de Rutalia que farem servir en tot el mòdul, recorrerem el flux de treball complet (entrenar, avaluar, no enganyar-se) i construirem el nostre primer model de cap a cap: un classificador k-NN implementat a mà per predir si un lliurament arribarà tard.

1. Regles escrites vs regles apreses
2. Tipus d'aprenentatge automàtic
3. El dataset canònic de Rutalia
4. El flux de treball: entrenar, avaluar, generalitzar
5. Sobreajustament i infraajustament: memoritzar no és aprendre
6. Validació creuada i mètriques (avançament)
7. Preparació de dades: variables categòriques i escalat
8. Primer model complet: k-NN a mà i amb scikit-learn

Comparem com hem resolt problemes fins ara amb com els resoldrem en aquest mòdul:

La pregunta "quant trigarà aquest lliurament?" il·lustra el canvi. Amb Dijkstra (03-03) obtenim el temps de trajecte segons els pesos que vam mesurar. Però el temps real depèn de factors que no són al graf: l'hora punta, el pes del paquet (buscar aparcament amb 20 kg no és el mateix que amb 200 g), si és divendres, si la zona MER té mercat aquell dia... Ningú a Rutalia no sap escriure aquesta fórmula. Les dades històriques, en canvi, la contenen.

Formalment, en aprenentatge supervisat busquem una funció f tal que f(x) ≈ y, on x és un vector de característiques (features) d'un exemple i y és la resposta coneguda. L'"algorisme d'aprenentatge" és el procediment que, donat un conjunt de parells (x, y), construeix aquesta f. Fixa-t'hi: seguim en un curs d'algorismes. Un algorisme d'aprenentatge és un algorisme com qualsevol altre —amb la seva complexitat, les seves estructures de dades i els seus invariants— la sortida del qual és una altra funció.

L'aprenentatge per reforç —un agent que actua, rep recompenses i ajusta el seu comportament— és la base dels sistemes que juguen a Go o controlen robots, però queda fora d'aquest curs; ens concentrarem en el supervisat (05-01 a 05-04) i el no supervisat (05-05).

Igual que el mòdul 2 va tenir la seva instància canònica del TSP (òptim 35,22 km) i el mòdul 3 el seu graf de 9 zones, aquest mòdul tindrà el seu dataset canònic de lliuraments. Cada fila és un lliurament històric:

Unes files de mostra (clients identificats només per un id fictici):

Com que no podem adjuntar milions de files a una lliçó, farem servir un generador sintètic amb llavor fixa: tot el mòdul treballarà exactament amb les mateixes dades, reproduïbles a la teva màquina. El generador amaga una "veritat" (la fórmula que produeix els minuts) que els nostres models intentaran descobrir sense conèixer-la. Nosaltres sí que la coneixem perquè l'hem escrita, i això ens permetrà jutjar si un model aprèn bé.

Punts importants del generador:

• Llavor 42: default_rng(42) garanteix que tu i aquesta lliçó vegeu els mateixos números. La reproduïbilitat és una pràctica central en ML.
• La veritat oculta és multiplicativa i no lineal (congestió × hora punta × pes): cap model lineal no la capturarà perfectament, cosa que donarà joc a 05-03 i 05-04.
• El soroll gaussià representa allò irreductible: dos lliuraments idèntics mai no triguen exactament el mateix. Cap model no hauria de predir-lo (ni podrà) — intentar-ho és, precisament, sobreajustar.
• Els retards són minoria (al voltant del 15-20%): les classes estan desequilibrades, cosa que explotarem a 05-02 en parlar de mètriques.

L'error clàssic del nouvingut és avaluar el model amb les mateixes dades amb què l'ha entrenat. Un model que memoritza el conjunt d'entrenament treu un 100% en aquell examen... perquè ja en coneixia les respostes. El que importa és com es comporta amb lliuraments que no ha vist mai: d'això se'n diu generalitzar.

El protocol mínim:

Barrejar és essencial: si les dades vinguessin ordenades per data o per zona, el test contindria només un tipus de lliuraments i l'avaluació quedaria esbiaixada. I el conjunt de test és sagrat: no es toca fins al final, ni per triar paràmetres ni per "fer-hi un cop d'ull". Cada vegada que una decisió teva depèn del test, el test deixa de ser una estimació honesta.

Tot model té una "capacitat": quanta complexitat pot representar. L'equilibri és delicat:

• Infraajustament (underfitting): el model és massa simple per al patró. Exemple: predir els minuts de lliurament amb la mitjana global (~35 min per a tothom). Falla en entrenament i en test.
• Sobreajustament (overfitting): el model és tan flexible que memoritza el soroll de l'entrenament. Exemple extrem: una taula de hash (01-04) que guarda cada lliurament històric i en retorna els minuts exactes. Error zero en entrenament, desastre amb lliuraments nous.

Ho podem visualitzar amb k-NN, el model que construirem al final. k-NN amb k=1 respon copiant el lliurament històric més semblant: memoritza, soroll inclòs. Amb k=n (tots els lliuraments) respon sempre la majoria global: infraajusta. El bon k és al mig:

Amb k=1 l'error d'entrenament és 0 (el teu veí més proper ets tu mateix) però el de test és alt. En créixer k tots dos s'acosten fins que, passat el punt òptim, tots dos pugen: el model ja no distingeix res. Aquesta corba en U de l'error de test apareix a tots els models del mòdul; a 05-03 la formalitzarem com el trade-off biaix-variància.

Si el test és sagrat, amb quines dades triem k? Reservar una altra partició (validació) funciona, però malbarata dades. La solució estàndard és la validació creuada de K plecs (K-fold): partir l'entrenament en K trossos, entrenar K vegades deixant cada cop un tros fora com a validació, i fer la mitjana dels K errors.

Cada exemple es fa servir K−1 vegades per entrenar i 1 vegada per validar: aprofitem totes les dades i l'estimació és més estable que la d'una sola partició. El cost: entrenar K vegades — un trade-off temps/fiabilitat molt de l'estil d'aquest curs.

Sobre mètriques, cada problema té les seves i les desenvoluparem allà on toquen: matriu de confusió, precisió/recall/F1 i ROC per a classificació (05-02); MSE, RMSE, MAE i R² per a regressió (05-03); inèrcia i silueta per a clustering (05-05). De moment farem servir la més simple, l'exactitud (accuracy): fracció d'encerts. I n'avancem ja la trampa: si el 85% dels lliuraments de Rutalia són puntuals, un "model" que sempre respon "puntual" encerta el 85% sense haver après res. A 05-02 la destriparem.

Els algorismes de ML operen amb vectors numèrics, i el nostre dataset té una columna categòrica (zona) i columnes numèriques d'escales molt diferents. Dues transformacions imprescindibles:

zona no és un número. Codificar-la com a ALM=0, MER=1, ..., PAR=8 equivaldria a inventar un ordre i una distància falsos (MER és "entre" ALM i EST? PAR és "8 vegades més lluny" que ALM?). La solució és el one-hot: una columna binària per categoria.

Així, la distància entre dues zones diferents qualssevol és sempre la mateixa, sense cap ordre espuri.

El nostre primer model, k-NN, decideix per distància euclidiana entre lliuraments. Observa les escales: distancia_km va de 0,5 a 8, però hora_sortida va de 8 a 20. Una diferència de 6 hores (migdia vs nit, crucial per al retard!) pesa en la distància el mateix que 6 km. I si mesuréssim el pes en grams, aquella columna aixafaria totes les altres. La geometria de l'espai dependria de les unitats — una decisió arbitrària que el model no hauria d'heretar.

L'estandardització ho corregeix: a cada columna se li resta la seva mitjana i es divideix per la seva desviació típica, deixant-les totes amb mitjana 0 i desviació 1.

Detall crucial: la mitjana i la desviació es calculen només amb l'entrenament. Si féssim servir també el test, informació del test es "filtraria" al model (data leakage) i l'avaluació deixaria de ser honesta. És la versió subtil del pecat d'avaluar amb dades d'entrenament.

k veïns més propers (k-NN) és l'algorisme perfecte per començar perquè és pura algorísmia d'aquest curs: distàncies + selecció dels k menors. La idea: per predir si un lliurament nou arribarà tard, busca els k lliuraments històrics més semblants i vota el que ells van fer.

No hi ha "entrenament" real: el model és el dataset. Tota la feina passa en el moment de predir. Per seleccionar els k menors fem servir un heap (01-04): heapq.nsmallest corre en O(n log k), millor que ordenar-ho tot en O(n log n).

Muntem el pipeline complet — codificar, partir, escalar, avaluar:

Compara sempre amb el model trivial: si el teu k-NN no el supera amb claredat, no ha après res d'útil. Amb aquest dataset, k-NN l'hauria de superar amb escreix, perquè el retard depèn fortament de la distància, la zona i l'hora — i els veïns propers en aquest espai comparteixen destí.

I la versió amb scikit-learn, la biblioteca estàndard, que fa el mateix amb validacions i optimitzacions industrials:

Fixa't en el patró fit/transform/predict: fit aprèn de les dades (els paràmetres de l'escalador, o el model), transform/predict apliquen el que s'ha après. Tota l'API de scikit-learn segueix aquest contracte, cosa que ajuda a evitar fugues d'informació.

En aquest mòdul mantindrem sempre la doble via: implementar a mà la mecànica essencial (això és un curs d'algorismes) i després fer servir scikit-learn com a eina de treball, verificant que tots dos coincideixen.

• Avaluar amb les dades d'entrenament. És l'error número u. Un 99% d'exactitud "en train" no diu res; només compta el rendiment sobre dades mai vistes.
• Escalar abans de partir. Si calcules mitjana i desviació amb tot el dataset, filtres informació del test cap al model. Ordre correcte: partir → ajustar transformacions amb train → aplicar a tots dos.
• Codificar categories com a enters ordenats. ALM=0...PAR=8 inventa distàncies inexistents i confon qualsevol algorisme basat en distància. Fes servir one-hot.
• Oblidar el model trivial de referència. Amb classes desequilibrades, una exactitud del 85% pot significar exactament zero aprenentatge. Calcula sempre què treu el "sempre majoria".
• No fixar llavors. Sense random_state/llavor, cada execució dona resultats diferents i és impossible depurar o comparar. Fixa llavors a particions i generadors.
• Consell: desconfia dels resultats massa bons. Una exactitud del 100% gairebé sempre delata una fuga de dades (una feature que "conté" la resposta, o un test contaminat), no un model genial.

1. La corba en U de k. Amb el dataset canònic (llavor 42), avalua el k-NN manual per a k ∈ {1, 3, 7, 15, 31, 61, 121, 501} sobre el conjunt de test. Imprimeix l'exactitud de cada k i localitza la zona bona. Què passa amb k=1? I amb k=501? Explica tots dos extrems en termes de sobreajustament/infraajustament.

2. El desastre de les unitats. Repeteix l'avaluació de k-NN (k=15) amb dues variants: (a) sense estandarditzar res, i (b) sense estandarditzar i amb pes_kg convertit a grams (multiplica aquesta columna per 1000). Compara les tres exactituds (estandarditzat, cru, grams) i explica per què la versió en grams s'enfonsa cap al model trivial.

3. Validació creuada manual. Implementa cv_5fold(X, y, k) que parteixi el conjunt d'entrenament en 5 plecs, entreni/avaluï 5 vegades el k-NN manual i retorni l'exactitud mitjana. Fes-la servir per triar el millor k de {5, 15, 45} sense tocar el test, i només al final avalua el k triat sobre el test.

Exercici 1:

Amb k=1 l'exactitud de test baixa respecte de la zona bona: cada predicció copia un únic veí, soroll inclòs (sobreajustament; sobre el mateix train trauria un 1,0). Amb k=501 es fa la mitjana sobre un terç del dataset i el model tendeix al vot de la majoria global (infraajustament). Els valors intermedis (≈7-61) formen la vall de la U.

Exercici 2:

En cru, hora_sortida (rang ~12) domina sobre les columnes one-hot (rang 1) i el resultat ja es degrada. En grams, la columna de pes presenta diferències de milers mentre les altres varien en unitats: la distància euclidiana es converteix, a la pràctica, en "diferència de pes"; i com que el pes amb prou feines determina el retard, k-NN cau cap al model trivial. Moralitat: les unitats són arbitràries i no han de decidir la geometria — per això s'estandarditza.

Exercici 3:

Fixa't en el detall: l'estandardització s'ajusta dins de cada plec amb la seva part d'entrenament — el mateix principi antifugues de sempre, aplicat recursivament. El test es fa servir una sola vegada, amb el k ja decidit.

Hem creuat la frontera del curs: d'escriure regles a aprendre-les. Ara saps què és un model (una funció apresa d'exemples), quins tipus d'aprenentatge existeixen i, sobretot, coneixes el protocol que ho sosté tot: separar train i test, escalar sense fugues, fer validació creuada i desconfiar de l'exactitud sense context. Hem definit el dataset canònic de Rutalia —2000 lliuraments sintètics amb llavor 42— que ens acompanyarà tot el mòdul, i hem construït un primer classificador complet, k-NN, que en el fons és algorísmia pura: distàncies euclidianes i un heap per als k menors. Però k-NN té límits seriosos (paga O(n·d) per cada predicció i pateix en dimensió alta), i la classificació dona per a molt més. A la lliçó següent, 05-02, explorarem el catàleg de classificadors —arbres de decisió, random forest, Naive Bayes, regressió logística— i aprendrem a mesurar-los seriosament, perquè amb un 85% de lliuraments puntuals, l'exactitud és una mètrica que enganya.