What is the k-nearest neighbors (kNN) algorithm?

kNN (k-nearest neighbors) is a non-parametric method used for classification and regression. The idea is simple: an object is classified by the majority vote of its neighbors, where the object is assigned to the class most common among its k nearest neighbors. For regression, the average value of the labels of the k nearest neighbors is predicted.

Key aspects:

• Parameter k: The number of nearest neighbors considered when making a decision. The choice of k greatly influences the result. A small k can be sensitive to noise, while a large k may ignore local structures.
• Distance metric: Used to determine "closeness" between data points. Common metrics include Euclidean distance and Manhattan distance.
• Features:
  • "Lazy" algorithm: no or minimal training (just storing training data). Prediction occurs only during query.
  • Simple to implement and understand.
  • Prediction performance may suffer with large datasets, as it requires calculating distances to all training examples.
  • Sensitive to feature scaling.
  • May perform poorly on noisy data.

Workflow steps (for classification):

1. Choose the value of k.
2. Choose the distance metric.
3. For a new object, for which a prediction is needed: a. Calculate the distance between this object and all objects in the training set. b. Select the k nearest objects from the training set. c. Determine the most frequently occurring class among these k objects. d. Assign this class to the new object.

Example (pseudo-code):

# Function to calculate Euclidean distance
def euclidean_distance(p1, p2):
    # ... distance calculation ...

# Function to find k nearest neighbors and predict class
def predict(training_data, new_data_point, k, distance_metric):
    distances = []
    for data_point in training_data:
        dist = distance_metric(new_data_point, data_point['features'])
        distances.append((dist, data_point['label']))

    # Sort by distance and select k nearest
    distances.sort(key=lambda x: x[0])
    k_nearest = distances[:k]

    # Count class votes
    class_votes = {}
    for dist, label in k_nearest:
        class_votes[label] = class_votes.get(label, 0) + 1

    # Determine class with the highest votes
    predicted_class = max(class_votes, key=class_votes.get)
    return predicted_class