ML0054 KNN Classification

Written by

Please explain how KNN classification works.

Answer

K-Nearest Neighbors (KNN) is a simple, non-parametric algorithm that predicts a label by majority vote among the $K$ nearest neighbors of a test point, using a chosen distance metric. It is intuitive and effective for small datasets, though less efficient on large-scale data.

(1) Instance-Based Method: KNN learns no explicit model; it stores the training data and predicts from similarity.
(2) Distance-Based Classification: For a test point, it computes the distance to every training point (e.g., Euclidean).
(3) Majority Vote: It selects the $K$ closest neighbors and assigns the most frequent label among them.
(4) Sensitive To K And Metric: Performance depends on the choice of $K$ and the distance measure (Euclidean, Manhattan, …).
(5) No Training Phase: All computation happens at prediction time: hence “lazy learning”.

KNN with K equals five decision regions over two classes where only the horizontal feature is informative

Figure 1: KNN (K=5) decision regions: the boundary wiggles because each query point polls its 5 nearest neighbors: local votes trace the class structure instead of fitting a global line. Note only Feature 1 is informative here; the vertical wiggle is the noise feature leaking into the vote.

Mathematical Formulation:
$\mathrm{distance}(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$
$\hat{y} = \arg\max_{c \in \mathcal{C}} \; \sum_{i=1}^{K} \mathbb{1}(y_i = c)$

Where:

$x_i$ and $y_i$ are the $i$ -th features of the query and training points; $n$ is the number of features (first formula: Euclidean distance).
$\hat{y}$ is the predicted class for the query point; $\mathcal{C}$ is the set of all classes; $K$ is the number of neighbors polled.
$y_i$ is the label of the $i$ -th neighbor and $\mathbb{1}(y_i = c)$ the indicator counting that neighbor’s vote for class $c$ .