Your friendly, neighbourhood algorithm!

• KNN: A statistical Machine Learning Algorithm which uses proximity between data points to make classifications or predictions.

• Instance-Based Learning: No fancy model training needed! Just store all the training data and let the neighbors do the talking.

• How it Works:

  • Classification: Majority vote among \(k\) closest data points.
  • Regression: Average the values of the \(k\) nearest data points.

• Distance Metrics:

  • How close are the neighbors? Common ways to measure:
    • Euclidean distance
    • Manhattan distance
    • Minkowski distance

• Euclidean Distance:

  \[ \text{Distance}_{\text{Euclidean}}(x_i, x_q) = \left( \sum_{j=1}^{p} (x_i^{(j)} - x_q^{(j)})^2 \right)^{\frac{1}{2}} \]

• Manhattan Distance (L1-Norm):

  \[ \text{Distance}_{\text{Manhattan}}(x_i, x_q) = \sum_{j=1}^{p} |x_i^{(j)} - x_q^{(j)}| \]

• Minkowski Distance:

  \[ \text{Distance}_{\text{Minkowski}}(x_i, x_q) = \left( \sum_{j=1}^{p} |x_i^{(j)} - x_q^{(j)}|^r \right)^{\frac{1}{r}} \]

  When \(r = 1\), it reduces to Manhattan distance, and when \(r = 2\), it reduces to Euclidean distance.

• Objective: Predict the class label for a new data point based on the majority class among its \(k\) nearest neighbors.
• Mathematical Expression:
  • Let \(\hat{y}\) represent the predicted class label.
  • The predicted class label \(\hat{y}\) is determined by: \[ \hat{y} = \text{argmax}_y \sum_{i=1}^{k} I(y_i = y) \]
  • Where:
    • \(y_i\) represents the class label of the \(i\)th nearest neighbor.
    • \(I(y_i = y)\) is an indicator function that equals 1 if \(y_i = y\) (same class as the new data point) and 0 otherwise.

The above interactive graph visualizes the species of flowers based on their petal length and width. It is clear that Setosa species have small petal width and petal length, while Virginica species have large petal width and petal length. There is a small overlapping region between Setosa and Versicolor species, indicating a higher probability of classification errors in our model within this region.

  # Train Test Split
  set.seed(11)
  train_indices <- sample(1:nrow(iris), 0.7 * nrow(iris)) # 70%-30% train-test split
  
  train_data <- iris[train_indices, -5]
  train_labels <- iris[train_indices, 5]
  
  test_data <- iris[-train_indices, -5] 
  test_labels <- iris[-train_indices, 5] 
  
  # Train KNN model
  k = 3
  knn_model <- knn(train = train_data, test = test_data, cl = train_labels, k = k)
  predicted_labels <- knn_model

Above code demonstrates how to train a simple KNN model to classify Flower Species.

As predicted, there are a few misclassifications in the overlapping region of Versicolor and Virginica species. This occurs because the feature values of these species are similar in that region, making it challenging for the KNN algorithm to distinguish between them based solely on proximity.

• Objective: Predict the continuous value for a new data point based on the average value among its \(k\) nearest neighbors.

• Mathematical Expression:

  • Let \(\hat{y}_q\) represent the predicted value for a new data point \(x_q\).
  • The predicted value \(\hat{y}_q\) is computed as:

  \[ \hat{y}_q = \frac{1}{k} \sum_{i=1}^{k} y_i \]

  Where:

  • \(y_i\) represents the target variable value of the \(i\)-th nearest neighbor.
  • \(k\) is the number of nearest neighbors used in the prediction.

data(mtcars)

set.seed(211)
# Train Test Split
train_indices <- sample(1:nrow(mtcars), 0.7 * nrow(mtcars)) # 70%-30% Train-Test Split
train_data <- mtcars[train_indices, -1]
train_labels <- mtcars[train_indices, 1]
test_data <- mtcars[-train_indices, -1] 
test_labels <- mtcars[-train_indices, 1]

# Train KNN regression model
k <- 3
knn_model <- knn(train = train_data, test = test_data, cl = train_labels, k = k)

# Predictions
predicted_labels <- knn_model

Above code trains a simple regression KNN model to predicted the mpg feature based on other features such as cyl, hp, disp, etc. (Dataset used: mtcars).

The simple regression KNN model does not show promising results, mostly due to the dataset containing many features with different units. This disparity in feature scales can lead to higher errors because KNN relies on distance calculations, which are sensitive to the scale of the features.

• Feature Scaling
  • Normalize or standardize features to ensure equal weighting.
• Optimal k Selection
  • Use cross-validation to find the best k value.
  • Experiment with different k values and evaluate performance.
• Distance Metrics
  • Experiment with different distance metrics (Euclidean, Manhattan, Minkowski) to find the most suitable one.
• Dimensionality Reduction
  • Apply techniques like PCA (Principal Component Analysis) or LDA (Linear Discriminant Analysis) to reduce feature space dimensionality.
• Weighting Neighbors
  • Assign different weights to neighbors based on their distance from the query point.
• Handling Imbalanced Data
  • Use techniques like oversampling, undersampling, or synthetic data generation to balance the dataset.