K-Nearest Neighbors: Learning by Similarity

K-Nearest Neighbors: Learning by Similarity

K-Nearest Neighbors (KNN) is one of the simplest yet effective algorithms for classification and regression. It operates on a fundamental principle: similar things are close to each other in feature space. To classify a new point, KNN finds the k nearest training examples and uses their labels to make a prediction. Despite its simplicity, KNN can be highly effective when the problem has clear local structure.

The Core Concept: Distance and Similarity

KNN relies on distance metrics to define "nearest." The most common metrics are Euclidean distance (L2): d = √((x₁-y₁)² + (x₂-y₂)² + ... + (xₙ-yₙ)²), Manhattan distance (L1): d = |x₁-y₁| + |x₂-y₂| + ... + |xₙ-yₙ|, and Minkowski distance (generalized). The choice of distance metric significantly affects KNN's performance.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier

# Generate synthetic dataset
np.random.seed(42)
X_class1 = np.random.normal([-1, -1], 0.6, (40, 2))
X_class2 = np.random.normal([1, 1], 0.6, (40, 2))
X = np.vstack([X_class1, X_class2])
y = np.hstack([0, 0] * 20 + [1, 1] * 20)

# Train KNN with different k values
fig, axes = plt.subplots(2, 3, figsize=(15, 10))
k_values = [1, 3, 5, 7, 15, 21]

h = 0.02
x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                     np.arange(y_min, y_max, h))

for idx, k in enumerate(k_values):
    ax = axes.flatten()[idx]
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X, y)

    # Predict on mesh
    Z = knn.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)

    # Plot decision regions
    ax.contourf(xx, yy, Z, levels=1, colors=['lightcoral', 'lightblue'], alpha=0.4)
    ax.contour(xx, yy, Z, levels=[0.5], colors='black', linewidths=2)

    # Plot data points
    colors = ['red', 'blue']
    for i in range(2):
        idx_points = y == i
        ax.scatter(X[idx_points, 0], X[idx_points, 1], c=colors[i],
                  s=100, alpha=0.8, edgecolors='black')

    accuracy = knn.score(X, y)
    ax.set_title(f'k={k}, Accuracy={accuracy:.2%}')
    ax.set_xlim(xx.min(), xx.max())
    ax.set_ylim(yy.min(), yy.max())
    ax.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

Computational Complexity and Optimization

KNN is a lazy learner—it stores all training data and performs computation only at prediction time. For each test point, finding k nearest neighbors requires computing distances to all n training points: O(n × d) where d is the number of features. With large datasets, this becomes prohibitively expensive. Techniques like KD-trees and ball trees enable efficient nearest neighbor search.

import numpy as np
import time
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import make_classification

# Generate large dataset
X, y = make_classification(n_samples=10000, n_features=20, n_informative=15,
                           n_redundant=5, random_state=42)

# KNN with different algorithms
algorithms = ['brute', 'kd_tree', 'ball_tree']
times = {}

for algo in algorithms:
    knn = KNeighborsClassifier(n_neighbors=5, algorithm=algo)

    # Training time (KNN just stores data)
    start = time.time()
    knn.fit(X, y)
    train_time = time.time() - start

    # Prediction time
    start = time.time()
    knn.predict(X[:100])  # Predict on 100 test samples
    pred_time = time.time() - start

    times[algo] = {'train': train_time, 'predict': pred_time}
    print(f"{algo}: Train={train_time:.4f}s, Predict={pred_time:.4f}s")

# KD-tree is much faster for prediction on high-dimensional data

Choosing Optimal k: Bias-Variance Tradeoff

The choice of k is critical. Small k (like k=1) means high variance—predictions are sensitive to individual training points, leading to overfitting. Large k means high bias—the algorithm misses local structure, leading to underfitting. The optimal k typically lies somewhere in between and should be chosen via cross-validation.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
from sklearn.datasets import make_moons

# Generate non-linearly separable data
X, y = make_moons(n_samples=300, noise=0.1, random_state=42)

# Evaluate KNN for different k values
k_range = range(1, 31)
train_scores = []
cv_scores = []

for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X, y)
    train_scores.append(knn.score(X, y))
    cv_score = cross_val_score(knn, X, y, cv=5).mean()
    cv_scores.append(cv_score)

# Plot
plt.figure(figsize=(10, 6))
plt.plot(k_range, train_scores, 'o-', label='Training Accuracy', linewidth=2)
plt.plot(k_range, cv_scores, 's-', label='Cross-Validation Accuracy', linewidth=2)
plt.xlabel('k (Number of Neighbors)')
plt.ylabel('Accuracy')
plt.title('KNN: Bias-Variance Tradeoff')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()

optimal_k = k_range[np.argmax(cv_scores)]
print(f"Optimal k: {optimal_k}")

Weighted KNN and Distance-Based Voting

Standard KNN gives equal weight to all k neighbors. Weighted KNN assigns higher weights to closer neighbors. This can improve performance because nearer points are typically more relevant than distant ones. Common weighting schemes include inverse distance (weight = 1/distance) or exponential decay (weight = exp(-distance)).

import numpy as np
from sklearn.neighbors import KNeighborsClassifier

# Compare uniform vs distance-weighted voting
np.random.seed(42)
X = np.random.randn(100, 2)
y = (X[:, 0] + X[:, 1] > 0).astype(int)

# Test point
test_point = np.array([[0.5, 0.5]])

# KNN with uniform weights
knn_uniform = KNeighborsClassifier(n_neighbors=5, weights='uniform')
knn_uniform.fit(X, y)
pred_uniform = knn_uniform.predict(test_point)

# KNN with distance weights
knn_distance = KNeighborsClassifier(n_neighbors=5, weights='distance')
knn_distance.fit(X, y)
pred_distance = knn_distance.predict(test_point)

# Find k nearest neighbors and their distances
distances, indices = knn_distance.kneighbors(test_point)
print("5 Nearest neighbors:")
for i, (idx, dist) in enumerate(zip(indices[0], distances[0])):
    print(f"  Point {idx}: distance={dist:.4f}, label={y[idx]}, weight={1/dist if dist > 0 else float('inf'):.4f}")

print(f"
Prediction (uniform weights): {pred_uniform[0]}")
print(f"Prediction (distance weights): {pred_distance[0]}")

Key Takeaways

• KNN is a lazy learning algorithm that stores training data and computes predictions on-the-fly.
• The choice of distance metric (Euclidean, Manhattan, etc.) significantly affects performance.
• Small k leads to overfitting (high variance), while large k leads to underfitting (high bias).
• Cross-validation should be used to select the optimal k value.
• KD-trees and ball trees enable efficient nearest neighbor search for large datasets.
• Weighted KNN often outperforms uniform KNN by giving higher importance to closer neighbors.

Deep Dive: K-Nearest Neighbors: Learning by Similarity

At this level, we stop simplifying and start engaging with the real complexity of K-Nearest Neighbors: Learning by Similarity. In production systems at companies like Flipkart, Razorpay, or Swiggy — all Indian companies processing millions of transactions daily — the concepts in this chapter are not academic exercises. They are engineering decisions that affect system reliability, user experience, and ultimately, business success.

The Indian tech ecosystem is at an inflection point. With initiatives like Digital India and India Stack (Aadhaar, UPI, DigiLocker), the country has built technology infrastructure that is genuinely world-leading. Understanding the technical foundations behind these systems — which is what this chapter covers — positions you to contribute to the next generation of Indian technology innovation.

Whether you are preparing for JEE, GATE, campus placements, or building your own products, the depth of understanding we develop here will serve you well. Let us go beyond surface-level knowledge.

Advanced Algorithms: Dynamic Programming and Graph Theory

Dynamic Programming (DP) solves complex problems by breaking them into overlapping subproblems. This is a favourite in competitive programming and interviews:

# Longest Common Subsequence — classic DP problem
# Used in: diff tools, DNA sequence alignment, version control

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

# Dijkstra's Shortest Path — used by Google Maps!
import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]  # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))

    return dist

# Real use: Google Maps finding shortest route from
# Connaught Place to India Gate, considering traffic weights

Dijkstra's algorithm is how mapping applications find optimal routes. When you ask Google Maps to navigate from Mumbai to Pune, it models the road network as a weighted graph (intersections are nodes, roads are edges, travel time is weight) and runs a variant of Dijkstra's algorithm. Indian highways, city roads, and even railway networks can all be modelled this way. IRCTC's route optimisation for trains across 13,000+ stations uses graph algorithms at its core.

India's Scale Challenges: Engineering for 1.4 Billion

Building technology for India presents unique engineering challenges that make it one of the most interesting markets in the world. UPI handles 10 billion transactions per month — more than all credit card transactions in the US combined. Aadhaar authenticates 100 million identities daily. Jio's network serves 400 million subscribers across 22 telecom circles. Hotstar streamed IPL to 50 million concurrent viewers — a world record. Each of these systems must handle India's diversity: 22 official languages, 28 states with different regulations, massive urban-rural connectivity gaps, and price-sensitive users expecting everything to work on ₹7,000 smartphones over patchy 4G connections. This is why Indian engineers are globally respected — if you can build systems that work in India, they will work anywhere.

Design Patterns and Production-Grade Code

Writing code that works is step one. Writing code that is maintainable, testable, and scalable is software engineering. Here is an example using the Strategy pattern — commonly asked in interviews:

from abc import ABC, abstractmethod

# Strategy Pattern — different payment methods
class PaymentStrategy(ABC):
    @abstractmethod
    def pay(self, amount: float) -> bool:
        pass

class UPIPayment(PaymentStrategy):
    def __init__(self, upi_id: str):
        self.upi_id = upi_id

    def pay(self, amount: float) -> bool:
        # In reality: call NPCI API, verify, debit
        print(f"Paid ₹{amount} via UPI ({self.upi_id})")
        return True

class CardPayment(PaymentStrategy):
    def __init__(self, card_number: str):
        self.card = card_number[-4:]  # Store only last 4

    def pay(self, amount: float) -> bool:
        print(f"Paid ₹{amount} via Card (****{self.card})")
        return True

class ShoppingCart:
    def __init__(self):
        self.items = []

    def add(self, item: str, price: float):
        self.items.append((item, price))

    def checkout(self, payment: PaymentStrategy):
        total = sum(p for _, p in self.items)
        return payment.pay(total)

# Usage — payment method is injected, not hardcoded
cart = ShoppingCart()
cart.add("Python Book", 599)
cart.add("USB Cable", 199)
cart.checkout(UPIPayment("rahul@okicici"))  # Easy to swap!

The Strategy pattern decouples the payment mechanism from the cart logic. Adding a new payment method (Wallet, Net Banking, EMI) requires ZERO changes to ShoppingCart — you just create a new strategy class. This is the Open/Closed Principle: open for extension, closed for modification. This exact pattern is how Razorpay, Paytm, and PhonePe handle their multiple payment gateways internally.

Research Frontiers and Open Problems in K-Nearest Neighbors: Learning by Similarity

Beyond production engineering, k-nearest neighbors: learning by similarity connects to active research frontiers where fundamental questions remain open. These are problems where your generation of computer scientists will make breakthroughs.

Quantum computing threatens to upend many of our assumptions. Shor's algorithm can factor large numbers efficiently on a quantum computer, which would break RSA encryption — the foundation of internet security. Post-quantum cryptography is an active research area, with NIST standardising new algorithms (CRYSTALS-Kyber, CRYSTALS-Dilithium) that resist quantum attacks. Indian researchers at IISER, IISc, and TIFR are contributing to both quantum computing hardware and post-quantum cryptographic algorithms.

AI safety and alignment is another frontier with direct connections to k-nearest neighbors: learning by similarity. As AI systems become more capable, ensuring they behave as intended becomes critical. This involves formal verification (mathematically proving system properties), interpretability (understanding WHY a model makes certain decisions), and robustness (ensuring models do not fail catastrophically on edge cases). The Alignment Research Center and organisations like Anthropic are working on these problems, and Indian researchers are increasingly contributing.

Edge computing and the Internet of Things present new challenges: billions of devices with limited compute and connectivity. India's smart city initiatives and agricultural IoT deployments (soil sensors, weather stations, drone imaging) require algorithms that work with intermittent connectivity, limited battery, and constrained memory. This is fundamentally different from cloud computing and requires rethinking many assumptions.

Finally, the ethical dimensions: facial recognition in public spaces (deployed in several Indian cities), algorithmic bias in loan approvals and hiring, deepfakes in political campaigns, and data sovereignty questions about where Indian citizens' data should be stored. These are not just technical problems — they require CS expertise combined with ethics, law, and social science. The best engineers of the future will be those who understand both the technical implementation AND the societal implications. Your study of k-nearest neighbors: learning by similarity is one step on that path.

Key Vocabulary

Here are important terms from this chapter that you should know:

🏗️ Architecture Challenge

Design the backend for India's election results system. Requirements: 10 lakh (1 million) polling booths reporting simultaneously, results must be accurate (no double-counting), real-time aggregation at constituency and state levels, public dashboard handling 100 million concurrent users, and complete audit trail. Consider: How do you ensure exactly-once delivery of results? (idempotency keys) How do you aggregate in real-time? (stream processing with Apache Flink) How do you serve 100M users? (CDN + read replicas + edge computing) How do you prevent tampering? (digital signatures + blockchain audit log) This is the kind of system design problem that separates senior engineers from staff engineers.

The Frontier

You now have a deep understanding of k-nearest neighbors: learning by similarity — deep enough to apply it in production systems, discuss tradeoffs in system design interviews, and build upon it for research or entrepreneurship. But technology never stands still. The concepts in this chapter will evolve: quantum computing may change our assumptions about complexity, new architectures may replace current paradigms, and AI may automate parts of what engineers do today.

What will NOT change is the ability to think clearly about complex systems, to reason about tradeoffs, to learn quickly and adapt. These meta-skills are what truly matter. India's position in global technology is only growing stronger — from the India Stack to ISRO to the startup ecosystem to open-source contributions. You are part of this story. What you build next is up to you.

Crafted for Class 10–12 • Core ML Algorithms • Aligned with NEP 2020 & CBSE Curriculum