In 05-01 we built our first classifier (k-NN) to predict whether a Rutalia delivery will arrive late, and we left two loose ends: k-NN has serious limits, and accuracy is a metric that lies. This lesson resolves both. We will walk through the catalog of fundamental classifiers — decision trees, random forest, Naive Bayes and logistic regression — implementing the mechanics of each one by hand (this is still an algorithms course: entropy, recursive partitions, conditional probabilities), and we will learn to evaluate properly with the confusion matrix, precision, recall, F1 and the ROC curve. The setting is still the canonical dataset: 2,000 historical deliveries, seed 42, and a real business question for Rutalia: which deliveries are going to be delayed, so we can warn the customer before it happens?

1. The classification problem at Rutalia
2. k-NN revisited: its limits
3. Decision trees: learning questions
4. Random forest: the wisdom of the forest
5. Naive Bayes: classifying with probabilities
6. Logistic regression: the linear classifier
7. Metrics done right: when accuracy lies
8. Classifier comparison table

Classifying means assigning a discrete class to each example. In our canonical dataset there are two natural problems:

• Binary: delayed ∈ {0, 1}. Do we warn customer C-1042 that their package will arrive late?
• Multiclass: incident type ∈ {none, absent, wrong address, damaged package}. The mechanics are identical (the algorithms in this lesson generalize to k classes); we will work on the binary problem for clarity.

We start from the 05-01 pipeline (same code, same seed):

k-NN performed well in 05-01, but it has two structural problems worth understanding before looking for alternatives:

• O(n·d) cost per query: there is no training phase, so every prediction scans the n historical deliveries computing d coordinates. With Rutalia's real "millions of records" and thousands of predictions per hour, that is unworkable. (Spatial structures exist — k-d trees, ball trees, cousins of the tries from 01-04 — that speed up the low-dimensional case, but they don't fix the underlying issue.)
• The curse of dimensionality: in high dimensions, Euclidean distance loses meaning. With large d, nearly all points end up at roughly the same distance from each other, and "the nearest neighbor" stops being especially similar. Our one-hot encoding already lifted us to 13 dimensions; with hundreds of features, k-NN degrades beyond repair.

The conclusion: we want models that compress the data into a small structure during training and then predict in O(depth) or O(d). The following ones do.

A decision tree classifies by asking chained questions about the features, like a diagnosis:

The remarkable part: nobody wrote those questions. The algorithm picked them from the data. How? By measuring how much "class mixing" each candidate question removes.

A node is pure if all its deliveries belong to the same class. Two standard impurity measures for a node with a proportion p of delays:

Both behave almost identically in practice. The gain of a question is the parent's impurity minus the weighted average of the impurity of the children it produces: at each node, the algorithm chooses the question with maximum gain.

Building the tree is pure divide and conquer, the pattern from 01-03: solve the node (choose the best question), split the data in two and recurse into each half. The base case: a pure node, no useful splits, or maximum depth reached.

Note the algorithmic properties: training costs O(d · n²) per level in this naive version (sklearn brings it down to O(d · n log n) by pre-sorting each column, a direct idea from 04-02), but predicting costs O(depth) — from scanning 1,600 deliveries per query (k-NN) to answering 3 questions. Moreover, the tree needs no scaling (it compares against thresholds, it doesn't compute distances) and it is interpretable: you can show the diagram to Rutalia's head of operations and discuss it.

A tree with no depth limit keeps splitting until every leaf is pure... even if it holds a single delivery. That is memorizing the noise: the U-shaped curve from 05-01, all over again. Antidotes:

• Pre-pruning: cap max_depth, require a minimum number of examples per leaf or a minimum gain to split. That is what we did (max_depth=3).
• Post-pruning: let the tree grow and then remove the branches that don't improve the validation error (more expensive, sometimes better).

In sklearn: DecisionTreeClassifier(max_depth=3, min_samples_leaf=20). Try max_depth=None and compare train vs test: you will watch overfitting happen live.

An individual tree is unstable: change 5% of the data and a different tree may come out (high variance). The solution is surprising: train many different trees and make them vote.

• Bagging (bootstrap aggregating): each tree is trained on a random sample with replacement of the training set (same size n, but with repeats and absentees). Each tree sees slightly different data, so it makes different mistakes.
• Random subspaces: at each node, each tree only considers a random subset of features (typically √d). This decorrelates the trees: without it, they would all start splitting on distance_km and vote almost identically.

Why does averaging work? For the same reason the mean of 100 noisy measurements is more reliable than one: if the trees' errors are (partially) independent, they cancel out in the vote. The variance of the average of T independent estimators is the individual variance divided by T. The trees are not fully independent, but bagging and random subspaces push them toward it — hence the effort to decorrelate them.

An elegant detail: each individual tree is allowed to overfit (unbounded depth), because the average corrects the variance. You lose the interpretability of the single tree, but rf.feature_importances_ still tells you which features matter — at Rutalia you will see distance_km, departure_hour and the congested zones dominate, consistent with the generator's hidden truth.

A complete change of philosophy: instead of learning boundaries, we model probabilities. Bayes' theorem gives us the probability of a delay given the features:

The problem: estimating P(x | delayed) for every full combination of features would require astronomical amounts of data. The "naive" assumption rescues it: assume the features are independent of each other within each class, so the joint probability factors into a product of individual probabilities — each one trivial to estimate by counting.

It is false in general (at Rutalia, zone and distance are correlated), but the classifier only needs the correct class to get the highest product, not exact probabilities. That is why Naive Bayes works better than its assumption deserves.

An example with categorical features (zone and time band):

Two engineering details that are pure algorithmic practice:

• Laplace smoothing (+1 in the counts): without it, a combination never seen in training (a delay in PAR in the early morning?) would have probability 0 and wipe out the entire product.
• Log-probabilities: multiplying many small probabilities causes numerical underflow; adding logarithms is equivalent (log is monotonic) and stable.

Naive Bayes trains in a single counting pass, O(n·d), predicts in O(d) and works surprisingly well with little data and many categorical features (its classic habitat: spam filters). In sklearn: CategoricalNB, GaussianNB (continuous features) or MultinomialNB (counts).

The fourth approach: a linear boundary. We compute a score z = w·x + b (a linear combination of the features, as in the linear programming of 02-01) and convert it into a probability with the sigmoid function:

Geometrically, w·x + b = 0 defines a hyperplane that splits the space in two: on one side we predict a delay, on the other, on time. The (signed) distance to the hyperplane grades the confidence via the sigmoid. It is the quintessential linear classifier: simple, fast (O(d) per prediction), with interpretable coefficients ("each additional km multiplies the odds of a delay by e^w₁").

And where do w and b come from? They are learned by minimizing a cost function via gradient descent — the algorithm we will develop in full detail in 05-03. Here the idea suffices: start with random weights and adjust them iteratively in the direction that reduces the error. In sklearn: LogisticRegression() (it needs scaled features, like any model based on w·x). Its limit is obvious: if the real boundary is not linear (and Rutalia's multiplicative truth isn't), a hyperplane can only approximate it — the way out of that dead end is the neural networks of 05-04, which stack many of these units.

We arrive at the debt outstanding from 05-01. In our dataset, ~85% of deliveries are on time. The "all on time" classifier achieves 85% accuracy while being perfectly useless: it detects not a single delay, which is exactly what Rutalia wants to detect.

Everything starts by breaking down the four possible outcomes:

• Precision = TP / (TP + FP): of the delay warnings we issued, what fraction was real? It measures the cost of false alarms.
• Recall (sensitivity) = TP / (TP + FN): of the actual delays, what fraction did we detect? It measures the delays that slip past us.
• F1 = the harmonic mean of both = 2·P·R / (P + R). The harmonic mean punishes imbalance: if either one is close to 0, F1 collapses even if the other is 1.

The "all on time" classifier stands exposed: recall = 0, F1 = 0, no matter how much 85% accuracy it flaunts. And there is an inherent trade-off: lowering the decision threshold (warning at p > 0.3 instead of p > 0.5) raises recall (you catch more delays) but lowers precision (more false alarms). Which one to prioritize is a business decision: if the warning is a cheap SMS, Rutalia will want high recall; if it triggers a financial compensation, high precision. The metric is chosen by looking at the real cost of each type of error — and the final decision about what to do with each customer remains human; the model only prioritizes.

Probabilistic classifiers let you slide the threshold from 0 to 1. The ROC curve plots, for each threshold, the true positive rate against the false positive rate. The AUC (area under that curve) summarizes overall quality: 1.0 is perfect, 0.5 is a coin flip. Its most useful reading: the AUC is the probability that the model scores a real delay higher than an on-time delivery, both chosen at random. In sklearn: roc_auc_score(y_te, model.predict_proba(X_te)[:, 1]). It is the standard comparison metric when the operating threshold hasn't been fixed yet.

Rule of thumb for tabular data like Rutalia's: start with logistic regression as the baseline, try a random forest (usually the strongest without fine-tuning) and use the single tree when you need to explain the decision.

• Boasting about accuracy with imbalanced classes. The 85% of "all on time" is the floor, not an achievement. Always look at the confusion matrix and the minority class F1.
• Letting the tree grow without limits. 0% training error and mediocre test = textbook overfitting. Cap the depth or the minimum examples per leaf, and always compare train vs test.
• Forgetting smoothing in Naive Bayes. A single zero probability annihilates the whole product. Laplace (+1) is one line of code that prevents absurd predictions.
• Multiplying probabilities instead of adding logs. With dozens of features, the product silently underflows to 0.0. Always work in log space.
• Scaling for trees / not scaling for logistic. Trees compare against thresholds (scaling is irrelevant to them); models built on w·x (logistic, k-NN) demand it. Knowing the internal mechanics prevents the mistake.
• Tip: set the decision threshold according to the business cost of FP vs FN, not the default 0.5. It's free and usually worth more than switching algorithms.

1. The tree versus the forest. With the canonical dataset, train DecisionTreeClassifier with max_depth ∈ {2, 4, 8, None} and a RandomForestClassifier(n_estimators=200). For each model print training and test accuracy. At what depth does the tree clearly overfit? Does the forest overfit even though its trees have unbounded depth?

2. The accuracy trap, with numbers. Implement the trivial "all on time" classifier and compare it with the random forest from exercise 1 using: accuracy, precision, recall and F1 (computed with your confusion_matrix_manual). Write one sentence explaining why Rutalia should never deploy the trivial model despite its accuracy.

3. Moving the threshold. With rf.predict_proba(X_te)[:, 1] get the delay probabilities and evaluate precision and recall for thresholds 0.3, 0.5 and 0.7. Which threshold would you choose if the customer warning is a free SMS? And if each warning triggers a 20% discount?

Exercise 1:

With max_depth=None the tree nails the training set (≈1.0) and loses on the test set: clear overfitting; the train−test gap grows with depth. The forest also brushes 1.0 on train (its trees are deep) but keeps the test score high: the average of decorrelated trees absorbs the variance that dooms the lone tree.

Exercise 2:

The trivial model hovers around acc≈0.85 but with recall=0 and F1=0: it detects no delay at all. The forest will have less of an edge in accuracy than intuition suggests, but far superior recall and F1. The sentence: the trivial model warns about no delay whatsoever, which is exactly the system's one and only job; its accuracy merely reflects that delays are rare.

Exercise 3:

With threshold 0.3 recall goes up (more delays get caught) at the expense of precision; with 0.7, the reverse. Free SMS → cheap false alarms → low threshold (0.3), prioritize recall. 20% discount → each FP costs money → high threshold (0.7), prioritize precision. The right metric depends on the real cost of each error, not on the statistics.

You now have the essential classification catalog and, more importantly, its internal mechanics: trees learn questions by maximizing purity with divide and conquer; the forest averages decorrelated trees to kill variance; Naive Bayes counts and multiplies probabilities (in logarithms, with Laplace); and logistic regression draws a hyperplane and grades confidence with the sigmoid. You also know how to evaluate for real: the confusion matrix, precision/recall/F1 and the threshold as a business decision, because with 85% of deliveries on time, accuracy alone is smoke. One confessed technical debt remains: we said the weights of logistic regression "are learned by minimizing a cost with gradient descent" without explaining how. In 05-03 we settle that debt: we move on to predicting the delivery minutes (regression), and there we will develop gradient descent piece by piece — the algorithm that is also the direct bridge to the neural networks of 05-04.