k-nearest neighbors - just ask the neighbors

Default kNN uses weights="uniform": each of the k neighbors gets exactly one vote, whether it sits right on top of the query or way out at the edge of the neighborhood. The alternative, weights="distance", weights each vote by 1/distance - closer neighbors count more, far ones fade.

Distance weighting softens the biggest annoyance of uniform voting: a neighborhood where 51 lukewarm far-away neighbors outvote 50 near-identical ones. It also makes predictions vary more smoothly as k grows, because adding one more distant neighbor barely moves the answer. You will try it in the homework at k=25 and see whether it buys anything on Lumen.

sklearn's default metric is minkowski with p=2, which is just euclidean distance - the straight-line ruler. Set p=1 and you get manhattan distance: sum of the absolute differences per feature, the "walk the city grid" ruler that is gentler on single-feature outliers. Any p in between (or beyond) is the general minkowski family.

On Lumen the choice barely moves the needle - the features are few and, after scaling, comparable. The metric matters more in high dimensions or on features with heavy tails. The knob to remember: KNeighborsClassifier(metric="minkowski", p=1) flips you to manhattan without changing anything else.

A subtle honesty note straight from the sklearn neighbors guide: if the k-th and (k+1)-th neighbors sit at exactly the same distance but carry different labels, which one makes the cut depends on the ordering of the training data. Rare with continuous features, more common with one-hot grids where many points share coordinates - and worth knowing before you chase a "non-deterministic model" ghost in a debugging session.

Practical hygiene: prefer odd k for binary problems so the vote itself cannot tie.

No training step sounds free until deployment day: kNN ships the training data as the model. Every prediction scans (or tree-searches) the stored rows, so prediction cost grows with training size - the exact opposite of logistic regression, which trains slowly-ish once and then predicts with a handful of multiplications forever.

This is session 1's fraud-team story coming home: the 40 GB kNN scorer next to the kilobyte logistic model. Same accuracy conversation, wildly different memory bill.

Drag k on the moons - watch the boundary wrap around every stray point at k=1 (memorization) and blur into an over-smoothed blob by k=75.

At k=1, every training point's nearest neighbor is itself, so training accuracy is essentially perfect - the model has memorized the data, noise and all. But a new session lands next to whichever old session happens to sit closest, and at Lumen's ~3% conversion rate in a crowded feature space, that single neighbor is nearly uninformative: test AUC 0.504, statistically a coin flip.

This is the sharpest overfitting demonstration in the whole course precisely because nothing was "trained": memorization is not a training pathology, it is a flexibility pathology. Any model flexible enough to store the data will happily do so.

The sklearn guide's advice on choosing k is refreshingly plain: a larger k suppresses the effects of noise, but makes the classification boundaries less distinct. On clean, balanced data you would tune k somewhere modest. On imbalanced data like Lumen - roughly 1 converter per 30 sessions - a converter's local neighborhood is mostly non-converters, so small k drowns the signal in noise and large k keeps helping: 0.504 → 0.533 → 0.592 → 0.640 across our sweep.

But the dial does not rise forever - crank k far enough and every neighborhood contains the same city-wide average, boundaries blur, and performance slides back down. You saw exactly that over-smoothing on the moons at k=75. Where the peak sits is an empirical question, which is homework.

Swap the vote for an average and kNN predicts numbers: KNeighborsRegressor on the 1,306 Lumen buyers, predicting order value. The k sweep tells the entire bias-variance story in four values of R²:

Note the two failure modes bracket the peak: k=1 memorizes (negative R² - you would score better predicting $73 for everyone), k=101 over-smooths (every prediction drifts toward the global mean). Same U-curve as tree depth and polynomial degree, third costume.

Same pipeline, same k=101, one change - pass the numerics through raw instead of standardizing them - and test AUC drops from 0.64 to 0.58. Nothing else moved. In the unscaled run, prior_30d_spend's 0-400 range dominates every distance computation, so the neighbor sets are effectively chosen by spend alone; pages, hour, and most of the one-hot signal get shouted down.

The fix is one line in the ColumnTransformer, and the discipline you already own from intro-ml applies: the scaler lives inside the pipeline and is fit on train only, so no test-set statistics leak in.

Naively, each prediction compares the query to all N stored rows - algorithm="brute", exact and fine for small data. For bigger data sklearn can pre-organize the rows into a kd_tree (splits space along coordinate axes; shines in low dimensions) or a ball_tree (nests points inside hyperspheres; holds up better as dimensions climb). Both prune away whole regions that provably cannot contain a nearest neighbor.

The default algorithm="auto" chooses for you, and its rules are worth knowing: it falls back to brute force when the data is sparse or when dimensionality is high (above 15 or so, tree structures stop paying for themselves - our one-hot-heavy Lumen matrix is exactly that case). The leaf_size knob (default 30) tunes when the trees stop splitting and hand over to brute force at the leaves - it affects speed and memory, never the predictions.

Distance-based reasoning degrades as dimensions pile up. In high-dimensional space, everything is far from everything - the volume grows so fast that your training points become lonely, and the gap between the nearest and farthest neighbor shrinks until "nearest" barely means anything. The vote is only as good as the neighbors' relevance, and in high dimensions relevance thins out.

Lumen after one-hot encoding lives in roughly 20 dimensions - modest, but enough to blunt the tool. That, plus the harsh class imbalance, is the honest reason kNN tops out at 0.64 here while logistic - which learns a global pattern instead of trusting local crowds - reaches 0.69. Not a broken model; a mismatched one. Session 9 turns this instinct into a checklist.