How KNN Works

The K-Nearest Neighbors (KNN) algorithm employs a direct, instance-based approach for classification. This method contrasts with algorithms like Logistic Regression, which aim to learn a specific function (such as the sigmoid) to define decision boundaries. KNN is often called a 'lazy learner' because it does not truly build a distinct model during a training phase. Instead, it memorizes the entire training dataset. The actual work happens when it is asked to classify a new, unseen data point.

Here’s the step-by-step process KNN follows to classify a new data point:

1. Choose K: First, you need to decide on a value for 'K', which represents the number of neighbors to consider. This is a number you, the practitioner, set beforehand (making it a hyperparameter, as we discussed in Chapter 2). Let's say you choose $K=3$.

2. Calculate Distances: When a new data point arrives (let's call it the query point), KNN calculates the distance between this query point and every single data point in the stored training dataset. A common way to measure this distance is using the standard Euclidean distance, which is essentially the straight-line distance between two points in the feature space. If you have two points, $p$ and $q$, in an $n$-dimensional space, the Euclidean distance is calculated as: $d(p, q) = \sqrt{(p_1 - q_1)^2 + (p_2 - q_2)^2 + \dots + (p_n - q_n)^2}$ or more compactly: $d(p, q) = \sqrt{\sum_{i=1}^{n}(p_i - q_i)^2}$ While Euclidean distance is common, other distance metrics can sometimes be used depending on the data. The core idea is to quantify how "similar" or "close" the new point is to each training point based on their features.

3. Find the K Nearest Neighbors: Once all the distances are calculated, the algorithm identifies the 'K' training data points that have the smallest distances to the query point. These are its "nearest neighbors." If we chose $K=3$, KNN finds the 3 training points closest to the new point.

4. Majority Vote: Now, look at the class labels of these 'K' nearest neighbors. KNN performs a simple majority vote among these neighbors. Whichever class is most common among the K neighbors becomes the predicted class for the new query point. For example, if $K=3$ and two neighbors belong to Class A and one belongs to Class B, the new point will be classified as Class A. If $K=5$ and three neighbors are Class B and two are Class A, the prediction is Class B.

5. Assign the Class: The result of the vote is the final classification for the new data point.

Let's visualize this. Imagine we have data points belonging to two classes (Class A in blue, Class B in orange) plotted based on two features. A new, unclassified point (green star) appears. If we set $K=5$, KNN finds the 5 closest training points to the star.

Example of KNN with K=5. The green star is the new point. The algorithm finds the 5 closest points (circled in purple). Four neighbors are Class B (orange) and one is Class A (blue). By majority vote, KNN classifies the new point as Class B.

That's the core mechanism. The choice of 'K' is significant. A small 'K' (like $K=1$) makes the model very sensitive to noise or outliers; the classification can change dramatically based on just one close, potentially anomalous, point. A very large 'K' makes the decision boundary smoother but might obscure local patterns or classify the point based on the overall majority class in the dataset, ignoring nearby points. Choosing the right 'K' often involves trying several values and seeing which performs best on a separate validation dataset (a concept we touched upon in Chapter 2 and will revisit).

Because KNN relies heavily on distance calculations, it's also important that all features are on a comparable scale. This is why feature scaling (which we'll cover in Chapter 6) is often a necessary preprocessing step before using KNN. Features with large values could disproportionately influence the distance calculation if not scaled properly.