K-Nearest Neighbors and Similarity

By the end of this lesson, you will be able to...

• trace a K-nearest-neighbors prediction from feature values to a vote;

• explain how scaling and k change which examples get a say;

• identify when local similarity is a poor basis for a prediction because of data geometry or prediction cost.

Idea in one sentence: KNN predicts from the outcomes of nearby past cases, so the definition of “nearby” is the model's most important decision.

Core Insight

A course team wants to flag students who may need support this week. For each student, it has two features available at prediction time: attendance rate over the last month and days since the last learning activity. It also has the eventual outcome for previous students: whether they withdrew before the end of the term.

A tempting first model is: “Fit one global rule that divides high-risk and low-risk students.” That can be useful; lesson 009 showed one way to choose such a boundary. But suppose risk is local. Students with 70% attendance may be safe when they were active yesterday, yet risky when they have been inactive for three weeks. A single simple boundary may hide that neighborhood pattern.

K-nearest neighbors (KNN) asks a different question for each new student: which recorded students are most similar under a chosen representation, and what happened to them? It stores the training cases and delays its main decision until prediction time. The visible consequence is important: distance, scaling, and the number of neighbors are not housekeeping settings around the model. Together, they are the model.

A Local Model Needs a Meaningful Neighborhood

Consider a new student, Mira:

We might first use the raw numeric values and ordinary Euclidean distance:

distance(x, z) = √((attendance_x − attendance_z)² + (inactive_x − inactive_z)²)

This first attempt looks neutral: it applies the same formula to every feature. It works while feature units are comparable and a one-point difference means roughly the same kind of change in each feature. Here they are not comparable. Attendance is recorded as a proportion from 0 to 1, while inactivity is a count from 0 to 30 or more. A difference of 0.05 attendance points is tiny beside a difference of 5 days only because of the chosen units, not because the team has decided that five days is always more important.

The initial model is therefore missing a modeling decision: what changes in the two measurements should count as equally large? KNN cannot answer that from labels alone. The representation must answer it first.

Make Distance Comparable Before Asking for Neighbors

For a small teaching example, suppose the training set has these training-only reference values:

attendance mean = 0.70, standard deviation = 0.10
inactive-days mean = 15, standard deviation = 10

Standardization turns each value into “how many training-set standard deviations from the training mean”:

scaled value = (raw value − training mean) / training standard deviation

These numbers are illustrative, not measurements from a real course. Mira becomes (0, -1.0): average attendance and ten days less inactive than the training average. The critical rule is not the exact arithmetic. Fit the means and standard deviations on the training partition only, then reuse them unchanged for validation, test, and future cases. Estimating them from all rows lets evaluation data influence the representation.

After scaling, the distance trace is visible:

The stronger model is now inspectable:

1. Transform Mira and every stored case with the same training-fitted scaler.
2. Compute their distances in the transformed feature space.
3. Sort by distance.
4. Keep the closest k cases.
5. Aggregate their labels into a prediction.

With k = 3, the nearest cases are B, A, and C. Two withdrew and one did not, so an unweighted majority vote predicts withdrawal risk for Mira.

nearest 3 outcomes: [yes, no, yes]
yes votes: 2
no votes:  1
prediction: yes

Notice what the trace does and does not establish. It establishes the result for this deliberately small representation and vote rule. It does not establish a causal claim such as “inactivity causes withdrawal,” and it does not make the label a decision by itself. A support team still needs the threshold and error-cost reasoning from lesson 008 before deciding how to act on a risk score.

So far, we have seen that KNN has no hidden global boundary in this example. Its decision is assembled from stored cases at query time. This matters because a change in scaling can change the neighbor list before a single vote is counted.

k Decides How Local the Decision Is

Why not always use the one closest case? With k = 1, Mira copies B's label. That is responsive to a very local pattern, but it also makes the result vulnerable to one noisy label, an unusual student, or a small measurement error. If B's outcome was incorrectly recorded, one case controls the answer.

Increasing k makes the vote less sensitive to any one point. In the same table, k = 5 gives four yes votes and one no vote. That looks stable, but it has a different problem: distant case E has extremely low attendance, a pattern unlike Mira's. A larger neighborhood can blur a useful local distinction by importing cases that are only “near” because the dataset has few better examples.

For binary classification, an odd k often avoids an exact unweighted tie. Distance-weighted voting is another option: a very close neighbor contributes more than a farther one. It can preserve locality without letting an arbitrary rank cutoff make all selected cases equal. But weighting introduces another choice: how fast should influence decay with distance, and what should happen at distance zero? There is no default setting that answers those questions for every problem.

The trade-off is explicit:

small k  -> more local detail, more sensitivity to noise and label errors
large k  -> smoother vote, more risk of erasing a real local pattern

Choose k, the scaling method, and any weighting rule with a validation procedure that resembles the future decision. Do not choose the setting with the prettiest training score; KNN can reproduce its training examples extremely well when k is small, which says little about new students.

Where the Local Story Breaks

KNN has two practical boundaries that are easy to miss because its “training” step is so small.

First, it shifts work to prediction time. A direct implementation compares a new case with every stored training row, then sorts or selects the closest distances. With n stored cases and d features, a simple exact query takes work proportional to n × d, and the system must retain the examples. Indexes and approximate-neighbor methods can reduce lookup time under particular geometric conditions, but they trade exactness, memory, build cost, or tuning complexity. The useful operational signal is prediction latency as the stored dataset and feature count grow, not the apparent speed of fitting.

Second, distance becomes less discriminating in many dimensions. In a sparse feature space with hundreds of weak or irrelevant columns, the closest and farthest points can become similarly far away. The ranked neighbor list still exists, but “closest” may no longer mean meaningfully similar. Adding every available column is not a remedy; irrelevant dimensions can dilute the few features that express the problem. This is a boundary of the local-similarity assumption, not merely an implementation inconvenience.

This gives a useful comparison with the previous lesson. An SVM learns a global boundary shaped by a small set of constraining points. KNN retains cases and makes a local decision for each query. Neither is automatically more trustworthy. A global model can miss a genuine local pattern; a local model can be misled by a bad distance definition, sparse neighborhoods, or expensive lookup. The evidence to inspect is the validation error pattern, the stability of predictions under sensible feature changes, and the cost of errors at the decision threshold.

Trace It Yourself

Check: Suppose the team accidentally records attendance as 70 rather than 0.70 but leaves inactivity in days. Before scaling, which feature is likely to dominate Euclidean distance, and why?

Think first, then reveal.

Answer: Attendance is likely to dominate because its numeric range is now roughly 0–100, much larger than the inactivity range. That does not prove attendance is more relevant; it only shows that the encoding has given it more geometric weight. Scaling or a domain-justified distance rule is needed before treating the result as similarity.

Check: A single near neighbor is labeled yes, but the next four very similar neighbors are labeled no. What is the likely difference between choosing k = 1 and k = 5?

Think first, then reveal.

Answer: k = 1 predicts yes because it follows the single closest case. An unweighted k = 5 vote predicts no four to one. The disagreement is useful evidence that the prediction is sensitive to the neighborhood definition; inspect labels, distances, and validation performance rather than declaring one setting inherently correct.

Practice: Choose a Representation Before You Vote

A clinic wants to retrieve similar appointment records to predict a missed visit. Its candidate features are travel distance in kilometers, days since the last visit, appointment type, and a free-text note. A teammate proposes raw Euclidean distance over all four columns, assigning arbitrary integers to appointment type and counting shared words in the note.

What should the team decide before trusting a KNN vote?

Model answer: Start by defining a feature contract: which fields are available when the appointment is scheduled, what each feature means, and how each should contribute to similarity. Standardize continuous values using training-only statistics. Do not treat arbitrary category codes as numeric distances; use an encoding or a domain-specific similarity rule that makes “close” meaningful. Text needs a deliberate representation and may add many sparse dimensions. Then compare a small set of justified k and weighting choices on validation data that respects any patient or time dependence. The goal is not to make KNN win; it is to find out whether a stable, useful neighborhood exists for this decision.

Resources

• [DOCUMENTATION] scikit-learn: Nearest Neighbors — Focus: compare brute-force, tree-based, and nearest-neighbor terminology without confusing search method with the prediction rule.
• [PAPER] Nearest Neighbor Pattern Classification — Focus: read the original statistical framing of nearest-neighbor classification and its asymptotic result.
• [DOCUMENTATION] scikit-learn: Preprocessing data — Focus: connect scaling choices to the geometry used by distance-based models.

Key Takeaways

• KNN predicts by transforming a new case, finding nearby stored cases, and aggregating their labels; it does not first learn one global rule.
• Scaling, feature representation, distance, and k define whose experience counts as relevant evidence.
• A small k preserves local detail but is noise-sensitive; a large k stabilizes the vote but can blur the local pattern.
• Cheap fitting does not make KNN cheap overall: exact lookup, storage, and weak distance contrast in high dimensions are important limits.