We closed module 4 with an observation: throughout the entire course so far, the problem knowledge has been supplied by us, by hand. We designed the optimization rules in module 2, measured the graph weights in module 3, justified the invariants and heuristics in module 4. But Rutalia accumulates millions of historical delivery records — hour, zone, weight, distance, delay, incidents — containing patterns that nobody has ever written down as a rule. In this lesson we make the paradigm shift: instead of programming the rules, we will let algorithms learn them from data. We will see what "learning" means exactly, what types of learning exist, define the canonical Rutalia dataset we will use throughout the module, walk through the complete workflow (train, evaluate, don't fool yourself) and build our first model from start to finish: a k-NN classifier implemented by hand to predict whether a delivery will arrive late.

1. Hand-written rules vs learned rules
2. Types of machine learning
3. The canonical Rutalia dataset
4. The workflow: train, evaluate, generalize
5. Overfitting and underfitting: memorizing is not learning
6. Cross-validation and metrics (a preview)
7. Data preparation: categorical variables and scaling
8. First complete model: k-NN by hand and with scikit-learn

Let's compare how we have solved problems until now with how we will solve them in this module:

The question "how long will this delivery take?" illustrates the shift. With Dijkstra (03-03) we get the travel time according to the weights we measured. But the actual time depends on factors that aren't in the graph: rush hour, the package weight (hunting for parking with 20 kg is not the same as with 200 g), whether it's Friday, whether zone MER has its market that day... Nobody at Rutalia knows how to write that formula. The historical data, on the other hand, contains it.

Formally, in supervised learning we look for a function f such that f(x) ≈ y, where x is a vector of features of an example and y is the known answer. The "learning algorithm" is the procedure that, given a set of pairs (x, y), builds that f. Notice: we are still in an algorithms course. A learning algorithm is an algorithm like any other — with its complexity, its data structures and its invariants — whose output is another function.

Reinforcement learning — an agent that acts, receives rewards and adjusts its behavior — underpins the systems that play Go or control robots, but it falls outside this course; we will focus on supervised (05-01 to 05-04) and unsupervised learning (05-05).

Just as module 2 had its canonical TSP instance (optimum 35.22 km) and module 3 its 9-zone graph, this module will have its canonical delivery dataset. Each row is one historical delivery:

A few sample rows (customers identified only by a fictitious id):

Since we can't attach millions of rows to a lesson, we will use a synthetic generator with a fixed seed: the whole module will work with exactly the same data, reproducible on your machine. The generator hides a "ground truth" (the formula that produces the minutes) which our models will try to discover without knowing it. We do know it, because we wrote it — and that will let us judge whether a model learns well.

Key points about the generator:

• Seed 42: default_rng(42) guarantees that you and this lesson see the same numbers. Reproducibility is a core practice in ML.
• The hidden truth is multiplicative and nonlinear (congestion × rush hour × weight): no linear model will capture it perfectly, which will make things interesting in 05-03 and 05-04.
• The Gaussian noise represents what is irreducible: two identical deliveries never take exactly the same time. No model should (or will be able to) predict it — trying to is, precisely, overfitting.
• Delays are a minority (around 15-20%): the classes are imbalanced, something we will exploit in 05-02 when discussing metrics.

The classic newcomer mistake is evaluating the model on the same data it was trained on. A model that memorizes the training set scores 100% on that exam... because it already knew the answers. What matters is how it behaves on deliveries it has never seen: that is called generalizing.

The minimal protocol:

Shuffling is essential: if the data came sorted by date or by zone, the test set would contain only one kind of delivery and the evaluation would be biased. And the test set is sacred: you don't touch it until the very end, neither to choose parameters nor to "take a peek". Every time one of your decisions depends on the test set, the test set stops being an honest estimate.

Every model has a "capacity": how much complexity it can represent. The balance is delicate:

• Underfitting: the model is too simple for the pattern. Example: predicting delivery minutes with the global mean (~35 min for everyone). It fails on training and on test.
• Overfitting: the model is so flexible that it memorizes the noise in the training data. Extreme example: a hash table (01-04) that stores every historical delivery and returns its exact minutes. Zero error on training, disaster on new deliveries.

We can visualize this with k-NN, the model we will build at the end. k-NN with k=1 answers by copying the most similar historical delivery: it memorizes, noise included. With k=n (all deliveries) it always answers the global majority: it underfits. The good k lies in between:

With k=1 the training error is 0 (your nearest neighbor is yourself) but the test error is high. As k grows, both curves approach each other until, past the optimal point, both rise: the model can no longer tell anything apart. This U-shaped test error curve appears in every model of the module; in 05-03 we will formalize it as the bias-variance trade-off.

If the test set is sacred, what data do we use to choose k? Setting aside another partition (validation) works, but wastes data. The standard solution is K-fold cross-validation: split the training set into K chunks, train K times leaving a different chunk out as validation each time, and average the K errors.

Each example is used K−1 times for training and once for validation: we make use of all the data and the estimate is more stable than that of a single split. The cost: training K times — a time/reliability trade-off very much in the spirit of this course.

Regarding metrics, each problem has its own and we will develop them where they belong: confusion matrix, precision/recall/F1 and ROC for classification (05-02); MSE, RMSE, MAE and R² for regression (05-03); inertia and silhouette for clustering (05-05). For now we will use the simplest one, accuracy: the fraction of correct predictions. And we can already reveal its trap: if 85% of Rutalia's deliveries are on time, a "model" that always answers "on time" scores 85% without having learned anything. In 05-02 we will take it apart.

ML algorithms operate on numeric vectors, and our dataset has one categorical column (zone) and numeric columns on wildly different scales. Two indispensable transformations:

zone is not a number. Encoding it as ALM=0, MER=1, ..., PAR=8 would invent a fake order and a fake distance (is MER "between" ALM and EST? Is PAR "8 times farther" than ALM?). The solution is one-hot encoding: one binary column per category.

This way, the distance between any two distinct zones is always the same, with no spurious ordering.

Our first model, k-NN, decides by Euclidean distance between deliveries. Look at the scales: distance_km ranges from 0.5 to 8, but departure_hour ranges from 8 to 20. A difference of 6 hours (noon vs night — crucial for delays!) weighs as much in the distance as 6 km. And if we measured weight in grams, that column would crush all the others. The geometry of the space would depend on the units — an arbitrary decision the model should not inherit.

Standardization fixes this: from each column we subtract its mean and divide by its standard deviation, leaving them all with mean 0 and deviation 1.

A crucial detail: the mean and deviation are computed only on the training set. If we also used the test set, test information would "leak" into the model (data leakage) and the evaluation would no longer be honest. It is the subtle version of the sin of evaluating on training data.

k-nearest neighbors (k-NN) is the perfect algorithm to start with because it is pure algorithmics from this course: distances + selecting the k smallest. The idea: to predict whether a new delivery will be late, look up the k most similar historical deliveries and vote on what they did.

There is no real "training": the model is the dataset. All the work happens at prediction time. To select the k smallest we use a heap (01-04): heapq.nsmallest runs in O(n log k), better than sorting everything in O(n log n).

Let's assemble the complete pipeline — encode, split, scale, evaluate:

Always compare against the trivial model: if your k-NN doesn't clearly beat it, it hasn't learned anything useful. On this dataset, k-NN should beat it comfortably, because the delay depends strongly on distance, zone and hour — and nearby neighbors in that space share the same fate.

And the scikit-learn version, the standard library, which does the same with industrial-grade validations and optimizations:

Note the fit/transform/predict pattern: fit learns from the data (the scaler's parameters, or the model), transform/predict apply what was learned. The entire scikit-learn API follows this contract, which helps prevent information leaks.

Throughout this module we will always keep the dual track: implement the essential mechanics by hand (this is an algorithms course) and then use scikit-learn as the working tool, verifying that both agree.

• Evaluating on training data. The number one mistake. 99% accuracy "on train" says nothing; only performance on never-seen data counts.
• Scaling before splitting. If you compute mean and deviation on the full dataset, you leak test information into the model. Correct order: split → fit transformations on train → apply to both.
• Encoding categories as ordered integers. ALM=0...PAR=8 invents nonexistent distances and confuses any distance-based algorithm. Use one-hot.
• Forgetting the trivial reference model. With imbalanced classes, 85% accuracy can mean exactly zero learning. Always compute what "always majority" scores.
• Not fixing seeds. Without random_state/seed, every run gives different results and debugging or comparing becomes impossible. Fix seeds in splits and generators.
• Tip: distrust results that look too good. 100% accuracy almost always betrays a data leak (a feature that "contains" the answer, or a contaminated test set), not a brilliant model.

1. The U-shaped curve of k. With the canonical dataset (seed 42), evaluate the manual k-NN for k ∈ {1, 3, 7, 15, 31, 61, 121, 501} on the test set. Print the accuracy for each k and locate the sweet spot. What happens with k=1? And with k=501? Explain both extremes in terms of overfitting/underfitting.

2. The units disaster. Repeat the k-NN evaluation (k=15) with two variants: (a) with no standardization at all, and (b) with no standardization and with weight_kg converted to grams (multiply that column by 1000). Compare the three accuracies (standardized, raw, grams) and explain why the grams version sinks toward the trivial model.

3. Manual cross-validation. Implement cv_5fold(X, y, k) that splits the training set into 5 folds, trains/evaluates the manual k-NN 5 times and returns the mean accuracy. Use it to choose the best k from {5, 15, 45} without touching the test set, and only at the end evaluate the chosen k on the test set.

Exercise 1:

With k=1 the test accuracy drops relative to the sweet spot: each prediction copies a single neighbor, noise included (overfitting; on the training set itself it would score 1.0). With k=501 the vote averages over a third of the dataset and the model tends toward the global majority vote (underfitting). The intermediate values (≈7-61) form the valley of the U.

Exercise 2:

Raw, departure_hour (range ~12) dominates the one-hot columns (range 1) and results already degrade. In grams, the weight column shows differences in the thousands while the others vary in single units: the Euclidean distance becomes, in practice, "weight difference"; and since weight barely determines the delay, k-NN falls toward the trivial model. Moral: units are arbitrary and must not decide the geometry — that is why we standardize.

Exercise 3:

Note the detail: standardization is fitted inside each fold on its training part — the same anti-leakage principle as always, applied recursively. The test set is used a single time, with k already decided.

We have crossed the course's frontier: from writing rules to learning them. You now know what a model is (a function learned from examples), what types of learning exist, and above all you know the protocol that holds everything together: separating train and test, scaling without leaks, cross-validating, and distrusting accuracy without context. We defined the canonical Rutalia dataset — 2,000 synthetic deliveries with seed 42 — that will accompany us through the whole module, and we built a first complete classifier, k-NN, which deep down is pure algorithmics: Euclidean distances and a heap for the k smallest. But k-NN has serious limits (it pays O(n·d) for every prediction and suffers in high dimensions), and classification has much more to offer. In the next lesson, 05-02, we will explore the catalog of classifiers — decision trees, random forest, Naive Bayes, logistic regression — and learn to measure them properly, because with 85% of deliveries on time, accuracy is a metric that lies.