Concept 3

Choosing K controls how local the model is

Small \(K\) listens to very local evidence. Large \(K\) smooths the prediction across a wider neighborhood.

Small K vs large K

K value	Behavior	Risk
Small \(K\)	Flexible, local boundary	Noise and overfitting
Large \(K\)	Smoother, more stable	Underfitting

\[ K=1 \Rightarrow \text{prediction follows the nearest point} \]

\[ K=n \Rightarrow \text{prediction follows the global majority or average} \]

Small \(K\) can overreact. Large \(K\) can oversmooth.

Bias-variance intuition

K	Bias	Variance	Model behavior
Small	Low	High	Fits local noise
Medium	Balanced	Balanced	Often best validation performance
Large	High	Low	Too smooth

Choosing \(K\) is model tuning. We should not choose it by looking at test performance repeatedly.

Overfitting and underfitting in KNN

Prediction stability

If one mislabeled training point is closest to the query, which value of \(K\) is most likely to make a wrong prediction: 1, 3, or 5?

\(K=1\), because the model blindly trusts the closest single point.

KNN overfits when it reacts too strongly to individual training points. This usually happens when \(K\) is very small.

KNN underfits when it averages over too many neighbors. This usually happens when \(K\) is very large.

Case	What happens	Classroom intuition
\(K=1\)	Every point is controlled by the nearest single example.	One noisy neighbor can flip the answer.
\(K=3\) or \(K=5\)	A small local group votes.	Noise is reduced while locality is preserved.
Very large \(K\)	The model listens to too many faraway points.	Local patterns get washed out.

\[ \text{Small }K \Rightarrow \text{low bias, high variance} \]

\[ \text{Large }K \Rightarrow \text{high bias, low variance} \]

Outlier sensitivity

Noisy neighbor question

If one nearby point is mislabeled, should one neighbor be allowed to decide the prediction alone?

Usually no. This is why \(K=1\) is flexible but risky.

Small \(K\) makes KNN sensitive to outliers and mislabeled examples. Increasing \(K\) or using distance-weighted voting can reduce the influence of one bad point.

Setting	Effect of one outlier
\(K=1\)	Can fully control prediction.
\(K=5\)	Must outvote several neighbors.
Distance-weighted KNN	Outlier matters only if it is very close.

A larger neighborhood can protect the prediction from a single noisy point.

Visualization: K = 1, 3, and 5

The same query point can receive different predictions when \(K\) changes.

Increasing \(K\) increases the neighborhood size. The prediction becomes less sensitive to one nearby point.

Decision boundary changes with K

Boundary shape question

Which boundary should be smoother: \(K=1\) or \(K=15\)?

\(K=15\), because each prediction averages a larger neighborhood.

KNN can make nonlinear boundaries, but \(K\) controls how sharply those boundaries react to the data.

KNN regression smoothing

Smoothing question

For house-price prediction, would \(K=1\) or \(K=25\) produce a smoother price curve?

\(K=25\), because it averages across more neighboring houses.

For regression, increasing \(K\) smooths the prediction curve. Too small can overfit; too large can underfit.

How do we choose K?

Split data into train and validation, or use cross-validation.
Try candidate values: \(K=1,3,5,7,\ldots\).
Evaluate using the right metric.
Pick the \(K\) with best validation performance.
Evaluate final model once on test data.

For classification, odd values of \(K\) are often used to reduce ties in binary classification.

Choose \(K\) using validation or cross-validation performance.

Effective methods to choose K

Method	How it works	When useful
Validation curve	Try many \(K\) values and plot validation score.	Best classroom method because the bias-variance pattern is visible.
Cross-validation	Average performance across folds for each \(K\).	More reliable when data is not very large.
Grid search	Tune \(K\), distance metric, and weights together.	Useful for real projects.
Elbow region	Choose a stable \(K\) where score stops improving significantly.	Useful when many nearby \(K\) values perform similarly.
Domain constraint	Prefer a \(K\) that makes sense operationally.	Useful when explainability matters.

A practical starting range is odd values such as:

\[ K\in\{1,3,5,7,9,11,15,21,31\} \]

Some people use \(\sqrt{n}\) as a rough starting point, but it is only a heuristic. Validation performance should make the final decision.

If several \(K\) values perform almost equally well, prefer the simpler and more stable option, usually the slightly larger \(K\).

Parameter tuning

KNN has more than one hyperparameter.

Hyperparameter	Choices	Effect
`n_neighbors`	1, 3, 5, 7, ...	Controls locality
`metric`	Euclidean, Manhattan, cosine	Defines similarity
`weights`	uniform, distance	Whether closer neighbors count more
`p` in Minkowski	1 or 2 commonly	Manhattan vs Euclidean

For classification, tune \(K\) using the metric that matches the problem: accuracy for balanced classes, F1/recall/precision for imbalanced classes, and RMSE/MAE for regression.

Distance-weighted KNN

Weighted vote

If one neighbor is extremely close and four neighbors are far away, should every neighbor have equal importance?

Not always. Distance weighting lets closer neighbors count more.

Sometimes closer neighbors should influence the prediction more.

\[ w_i=\frac{1}{d(x,x_i)+\epsilon} \]

For regression:

\[ \hat{y}=\frac{\sum_{i\in N_K(x)}w_i y_i}{\sum_{i\in N_K(x)}w_i} \]

For classification, use weighted voting rather than simple majority voting.

KNN with imbalanced classes

Imbalance question

If 95% of customers do not churn, what class is likely to appear more often in most neighborhoods?

The majority class. KNN can miss minority-class regions when the neighborhood is dominated by majority examples.

Class imbalance affects KNN because voting depends on local counts. If minority-class examples are rare, even a minority-like query can be surrounded by many majority-class points.

Method	How it helps
Use recall/F1/PR-AUC	Evaluates minority detection properly.
Distance weighting	Very close minority neighbors can matter more.
Resampling	Changes the neighborhood composition during training.
Tune threshold from probabilities	Uses local vote fraction more carefully.

A local neighborhood can still be majority-heavy even near a minority-like point.

Curse of dimensionality

Dimension question

If we keep adding features, will “nearest” always become more meaningful?

No. In high dimensions, points often become similarly far away, so neighborhoods become less reliable.

KNN works best when distance captures similarity. In high dimensions, data becomes sparse and the nearest point may not be much closer than the farthest point.

\[ \text{distance contrast}=\frac{d_{max}-d_{min}}{d_{min}} \]

As dimensionality grows, this contrast often shrinks. That means nearest and farthest examples can start looking almost equally far.

More features are useful only if they add signal. Too many weak features can make distance less meaningful.

Common remedies include feature selection, dimensionality reduction, better embeddings, and choosing a metric that matches the data.

Fast nearest-neighbor search for large datasets

Brute-force KNN compares the query point with every training point.

\[ \text{brute force cost per query} \approx O(n\cdot p) \]

When \(n\) grows large, prediction can become slow. We can speed it up using smarter search structures or approximate search.

Method	Idea	Best for	Limitation
KD-tree	Split space using feature axes.	Low-dimensional numeric data.	Weak in high dimensions.
Ball tree	Group points into nested balls.	Medium dimensions and non-axis-aligned neighborhoods.	Still weak when dimension is very high.
Approximate nearest neighbors	Search quickly and accept near-best neighbors.	Very large datasets, embeddings, recommendations.	May miss the exact nearest neighbor.
Dimensionality reduction	Reduce features before neighbor search.	High-dimensional noisy data.	Can lose information.
Feature selection	Remove irrelevant features.	Any KNN problem with noisy columns.	Needs careful validation.

In scikit-learn, `KNeighborsClassifier` supports:

`algorithm`	Meaning
`brute`	Compare with all training points.
`kd_tree`	Use KD-tree search.
`ball_tree`	Use Ball-tree search.
`auto`	Let the library choose.

Tree-based methods avoid checking every point when the geometry is favorable.

For text embeddings or very high-dimensional data, approximate nearest-neighbor libraries such as FAISS, HNSW, Annoy, or ScaNN are often more effective than exact KD-tree search.