K-Nearest Neighbors (K-NN) is a non-parametric, instance-based learning algorithm.

Operation Principle

Rather than learning a model from the training data, K-NN memorizes the data. To make predictions for new, unseen data points, the algorithm looks up the known, labeled data points (the “nearest neighbors”) based on their feature similarity.

Key Steps in K-NN

1. Select K: Define the number of neighbors, denoted by the hyperparameter $K$.
2. Compute distance: Typically, Euclidean or Manhattan distance is used to identify the nearest data points.
3. Majority vote: For classification, the most common class among the K neighbors is predicted. For regression, the average of the neighbors’ values is calculated.

Distance Metric and Nearest Neighbors

• Euclidean Distance: $$\sqrt{\sum_{i=1}^{n}(q_i-p_i)^2}$$
• Manhattan Distance: $$\sum_{i=1}^{n}|q_i-p_i|$$

K-NN Pros and Cons

Advantages

• Simplicity: Easy to understand and implement.
• No Training Period: New data is simply added to the dataset during inference.
• Adaptability: Can dynamically adjust to changes in the data.

Disadvantages

• Computationally Intensive: As the algorithm scales, its computational requirements grow.
• Memory Dependent: Storing the entire dataset for predictions can be impractical for large datasets.
• Sensitivity to Outliers: Outlying points can disproportionately affect the predictions.