We've explored the philosophical foundations, computational properties, hyperparameter selection, and aggregation schemes of K-Nearest Neighbors. Now it's time to synthesize everything into complete, implementable algorithms.

This page provides production-quality pseudocode and implementations for:

• KNN Classification (basic and advanced)
• KNN Regression
• Unified KNN with all options
• Computational complexity analysis

These implementations are designed to be correct, clear, and complete—suitable for understanding the algorithm deeply and as a foundation for production systems.

Every KNN implementation follows the same high-level structure, whether for classification or regression:

ALGORITHM KNN:

1. TRAINING (Store):
   - Store training features X_train
   - Store training labels/targets y_train
   - Optionally: build acceleration structure (KD-tree, ball tree)
   - Optionally: precompute and cache distance information

2. PREDICTION (for each query point x_q):
   a. DISTANCE COMPUTATION:
      - Compute distance from x_q to all training points
      - d_i = distance(x_q, x_i) for i = 1, ..., n
   
   b. NEIGHBOR SELECTION:
      - Find indices of k smallest distances
      - neighbors = argsort(distances)[:k]  // or use partial sort
   
   c. AGGREGATION:
      - Gather labels/values of selected neighbors
      - Apply weighting scheme
      - Compute final prediction (vote for classification, mean for regression)
      
   d. RETURN:
      - Return prediction and optionally confidence/probabilities

Let's now detail each component with precise pseudocode.

The distance computation phase calculates distances from the query point to all training points. This is typically the most expensive step.

Pseudocode: Euclidean Distance

FUNCTION euclidean_distance(x1, x2):
    // x1, x2 are d-dimensional vectors
    
    sum_sq = 0
    FOR i = 1 TO d:
        diff = x1[i] - x2[i]
        sum_sq = sum_sq + diff * diff
    
    RETURN sqrt(sum_sq)

Vectorized Distance Matrix

For efficiency, compute distances to all training points at once:

FUNCTION compute_all_distances(x_q, X_train):
    // x_q: query point (d dimensions)
    // X_train: n x d matrix of training points
    // Returns: n-dimensional vector of distances
    
    differences = X_train - x_q  // Broadcasting: n x d matrix
    squared = differences * differences  // Element-wise square
    sum_squared = rowsum(squared)  // n-dimensional vector
    distances = sqrt(sum_squared)  // Element-wise sqrt
    
    RETURN distances

Given n distances, we need to find the k smallest. There are several approaches with different trade-offs:

Approach 1: Full Sort

FUNCTION find_k_nearest_fullsort(distances, k):
    // Sort all distances, return first k indices
    sorted_indices = argsort(distances)  // O(n log n)
    RETURN sorted_indices[0:k]

Complexity: O(n log n). Simple but wasteful when k << n.

Approach 2: Partial Sort (Partition)

FUNCTION find_k_nearest_partition(distances, k):
    // Partition around k-th element, return first k indices
    indices = argpartition(distances, k)  // O(n) average
    k_indices = indices[0:k]
    
    // Optional: sort the k indices by distance
    k_distances = distances[k_indices]
    sorted_within_k = argsort(k_distances)
    RETURN k_indices[sorted_within_k]

Complexity: O(n) average for partition + O(k log k) for optional sorting.

Approach 3: Heap-based Selection

FUNCTION find_k_nearest_heap(distances, k):
    // Maintain a max-heap of size k
    heap = MaxHeap()
    
    FOR i = 0 TO n-1:
        IF heap.size() < k:
            heap.push((distances[i], i))
        ELIF distances[i] < heap.peek().distance:
            heap.pop()
            heap.push((distances[i], i))
    
    RETURN heap.items()

Complexity: O(n log k). Best when k << n.

Here is the complete, production-ready KNN classification algorithm integrating all components:

ALGORITHM KNN_Classification:

INPUT:
    X_train: n × d training feature matrix
    y_train: n-dimensional label vector (integer classes 0, 1, ..., C-1)
    k: number of neighbors
    weights: 'uniform' or 'distance'
    metric: distance function

TRAINING (fit):
    STORE X_train, y_train
    n_classes = max(y_train) + 1

PREDICTION (predict for query x_q):
    // Step 1: Compute distances
    FOR i = 1 TO n:
        distances[i] = metric(x_q, X_train[i])
    
    // Step 2: Find k nearest
    neighbor_indices = argpartition(distances, k)[:k]
    neighbor_distances = distances[neighbor_indices]
    neighbor_labels = y_train[neighbor_indices]
    
    // Step 3: Compute weights
    IF weights == 'uniform':
        w = ones(k)
    ELSE IF weights == 'distance':
        w = 1 / (neighbor_distances + epsilon)
    
    // Step 4: Aggregate votes
    class_weights = zeros(n_classes)
    FOR i = 1 TO k:
        class_weights[neighbor_labels[i]] += w[i]
    
    // Step 5: Return prediction
    RETURN argmax(class_weights)

PROBABILITY (predict_proba for query x_q):
    // Same as prediction steps 1-4, then:
    probabilities = class_weights / sum(class_weights)
    RETURN probabilities

KNN regression follows the same structure, with aggregation by mean instead of voting:

ALGORITHM KNN_Regression:

INPUT:
    X_train: n × d training feature matrix
    y_train: n-dimensional target vector (real values)
    k: number of neighbors
    weights: 'uniform' or 'distance'
    aggregation: 'mean' or 'median'

PREDICTION (predict for query x_q):
    // Steps 1-3: Same as classification
    
    // Step 4: Aggregate values
    IF aggregation == 'mean':
        IF weights == 'uniform':
            prediction = mean(neighbor_values)
        ELSE:
            prediction = sum(w * neighbor_values) / sum(w)
    ELSE IF aggregation == 'median':
        prediction = weighted_median(neighbor_values, w)
    
    RETURN prediction

For production systems, a unified implementation that handles both classification and regression with all options is often desirable:

Understanding the computational complexity of KNN is essential for predicting performance and making deployment decisions.

Practical Performance Guidelines

Memory Requirements

For 32-bit floats:

• Training data: $n \times d \times 4$ bytes
• Example: 1M points × 100 dimensions = 400 MB

For distance caching (rarely practical):

• Distance matrix: $n^2 \times 8$ bytes (doubles)
• Example: 10K points = 800 MB; 100K points = 80 GB (impractical)

We've now covered the complete KNN algorithm from pseudocode to production-ready implementation.

Module Complete!

You've now mastered the KNN Algorithm module, covering:

1. Instance-based Learning: The paradigm of remembering rather than abstracting
2. Lazy Learning: Deferring computation to query time
3. K Selection: Choosing the optimal number of neighbors
4. Voting Schemes: Aggregating neighbor opinions
5. Algorithm Pseudocode: Complete, production-ready implementations

In the next module, we'll explore Distance Metrics—the choice of which fundamentally shapes what 'nearest' means in your feature space.