k Nearest Neighbors Algorithm
The k-nearest-neighbors rule, abbreviated k-NN, is a classification rule for binary classification.
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?
- 1Select the labels
The decision uses the labels of the selected neighbors, not labels from other points in the training sample.
- 2Count each class
Red appears two times, while Blue appears one time.
- 3Choose 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 |
Changing k changes how many labels participate in the decision
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
Common mistake Counting every point in the training sample
What it looks likeUsing labels from all stored points instead of only the selected k nearest neighbors
Why it failsOnly the labels of the k nearest neighbors participate in the decision.
Do this insteadWrite down the first k selected neighbors and count only their labels.
Common mistake Treating k as a class label
What it looks likeReading k as if it were Red or Blue
Why it failsk controls how many neighbors contribute labels; it is not one of the binary class labels.
Do this insteadUse k to select the group size, then count the labels in that group.
Common mistake Confusing the query point with a neighbor label
What it looks likeAssuming the point being classified already supplies the output label
Why it failsThe query point is the point under consideration; the output is determined by the labels of its selected neighbors.
Do this insteadKeep the query point separate from the neighbor labels and the final predicted label.
Common mistake Ignoring a changed value of k
What it looks likeComparing two results while assuming both decisions counted the same number of neighbors
Why it failsChanging k can change which labels are counted and therefore change the result.
Do this insteadRecord k before comparing the selected groups or their majorities.
Common mistake Assuming the rule specifies how ties are resolved
What it looks likeAdding a tie-breaking procedure as though it were part of the definition
Why it failsThe rule specification does not provide implementation details for resolving a tie.
Do this insteadRecognize 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
Red
Red appears twice and Blue appears once, so Red is the majority label among the selected neighbors.
Rule Summary
- 1The k-NN rule maps a training sample and a chosen k to a label for a point under consideration.
- 2Only the labels of the selected k nearest neighbors participate in the decision.
- 3The predicted label is the majority label among those selected neighbor labels.
- 4Changing k can change the selected group and therefore change the classification result.
- 5When tracing an unexpected result, check k, the neighbor ordering, the selected group, and the label count separately.
At a glance
- 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.