k Nearest Neighbors Algorithm
The k-NN rule maps a training sample and a chosen k to a label for each point under consideration.
Try it: k-Nearest Neighbours
How a k-nearest-neighbours classifier labels a new point: measure its distance to every known point, take the K closest, and let them vote.
How it works
- Measure the straight-line (Euclidean) distance from the new point to every labelled point.
- Rank the points from nearest to farthest.
- Keep the K nearest.
- Count how many of them belong to each class; the class with the most votes is the prediction (a tie goes to the class of the nearest tied neighbour).
Default run (15 steps): 10 labelled points and a new query point at (5, 3.5). K = 3. … Prediction: class A — A has the most votes.
Simplified: Small 2-D educational dataset (at most 30 points, three classes). Real KNN uses many features and usually scales them first.
Loading the simulation…
From Data to a Label
The k-nearest-neighbors rule, abbreviated k-NN, is a classification rule for binary classification. It receives a training sample and a chosen value of k. For each point being considered, it returns one label by examining the labels of that point's k nearest neighbors.
The Four Parts of a Decision
A training sample is the collection of labeled points supplied to the rule. The query point is the point currently being considered for classification. The rule identifies that point's nearest neighbors in the training sample and selects the first k neighbors in the ordering. Their labels are the neighbor labels used in the decision. The predicted label is the majority label among those selected labels.
| Part | Role in the rule |
|---|---|
| Training sample | The labeled sample supplied to the rule |
| Query point | The point being considered |
| Neighbor labels | The labels of the selected k nearest neighbors |
| Predicted label | The majority label returned by the rule |
The objects involved in one k-NN classification decision
Counting the Neighbor Labels
A majority of Red
The selected group of neighbors contains two Red labels and one Blue label. What label does the k-NN rule return?
Select the labels: The decision uses the labels of the selected neighbors, not labels from other points in the training sample.
Count each class: Red appears two times, while Blue appears one time.
Choose the majority: Red has the greater count among the selected labels.
The predicted label is Red.
This is the complete decision step once the relevant neighbor labels are known. In binary classification, the labels come from two possible classes. Both labels may appear among the selected neighbors, and the rule chooses the one with the greater count.
What Changing k Changes
The parameter k controls how many neighbors contribute labels to the majority decision. Changing k can change the group being counted. Because a different number of neighbor labels may then be included, the majority label and the classification result can change.
| Chosen k | Labels used | Possible consequence |
|---|---|---|
| Smaller value | A smaller selected group | The majority is based on fewer neighbor labels |
| Larger value | A larger selected group | Additional neighbor labels may affect the majority |
Tracing an Unexpected Result
When a classification result seems unexpected, trace the rule in order. First check the chosen value of k. Next check which neighbors occupy the first k positions in the ordering. Then write down only their labels and recount them. An unexpected result can arise because changing k changes which labels are counted, or because the selected neighbor group or ordering is not the group you expected.
Common Tracing Mistakes
Counting every point in the training sample
Only the labels of the k nearest neighbors participate in the decision.
Fix:
Write down the first k selected neighbors and count only their labels.Treating k as a class label
k controls how many neighbors contribute labels; it is not one of the binary class labels.
Fix:
Use k to select the group size, then count the labels in that group.Confusing the query point with a neighbor label
The query point is the point under consideration; the output is determined by the labels of its selected neighbors.
Fix:
Keep the query point separate from the neighbor labels and the final predicted label.Ignoring a changed value of k
Changing k can change which labels are counted and therefore change the result.
Fix:
Record k before comparing the selected groups or their majorities.Assuming the rule specifies how ties are resolved
The rule specification does not provide implementation details for resolving a tie.
Fix:
Recognize that tie resolution is outside the supplied rule specification.
Practice the Decision Rule
A query point has three selected nearest neighbors with labels Red, Blue, and Red. State the neighbor labels being counted and predict the output of the k-NN rule.
Hints
- Count only the three selected labels.
- Compare the number of Red labels with the number of Blue labels.
What do you think happens?
The selected labels are Red, Blue, and Red. What predicted label should the rule return?
Reveal answer
Answer: Red
Red appears twice and Blue appears once, so Red is the majority label among the selected neighbors.
Rule Summary
- The k-NN rule maps a training sample and a chosen k to a label for a point under consideration.
- Only the labels of the selected k nearest neighbors participate in the decision.
- The predicted label is the majority label among those selected neighbor labels.
- Changing k can change the selected group and therefore change the classification result.
- When tracing an unexpected result, check k, the neighbor ordering, the selected group, and the label count separately.
Key Takeaways
- k-NN accepts a training sample and a chosen value of k, then classifies each point under consideration.
- The rule uses only the labels of the k selected nearest neighbors.
- The label with the greater count becomes the predicted label in binary classification.
- Changing k can change which labels are included and can therefore change the result.
- An unexpected result should be traced through the selected neighbors, their ordering, k, and the final majority count.