Difficulty: Advanced
Classification is a supervised learning task where the goal is to predict a categorical label for a given input. Unlike regression, which predicts continuous values, classification assigns inputs to one of several discrete classes. Examples include email spam detection (spam vs not spam), medical diagnosis (disease vs healthy), and image recognition (cat vs dog). Binary classification has two classes, while multi-class classification handles three or more.
K-Nearest Neighbors (KNN) is one of the simplest and most intuitive classification algorithms. It works on a straightforward principle: to classify a new data point, find the K closest data points in the training set (its neighbors) and assign the most common class among those neighbors. The 'K' is a hyperparameter that you choose before training. A small K (like 1) makes the model very sensitive to individual points, while a large K produces smoother decision boundaries but may overlook local patterns.
The distance metric used in KNN determines how 'closeness' is measured. The most common is Euclidean distance: d = sqrt(sum((x_i - y_i)^2)). Other options include Manhattan distance (sum of absolute differences) and Minkowski distance (generalization of both). The choice of distance metric can significantly affect classification results, especially when features have different scales.
Decision boundaries are the regions in feature space where the predicted class changes. In KNN, these boundaries can be complex and non-linear, adapting to the shape of the data distribution. Unlike parametric models like logistic regression that have fixed functional forms, KNN is non-parametric, it makes no assumptions about the underlying data distribution. However, KNN can be computationally expensive at prediction time since it must compute distances to all training points.
Classification accuracy is measured as the proportion of correctly classified instances out of the total. While accuracy is a good starting point, it can be misleading with imbalanced datasets, for example, if 95% of emails are not spam, a model that always predicts "not spam" achieves 95% accuracy but catches zero spam. This is why more nuanced metrics like precision, recall, and F1-score are important.
import math
def euclidean_distance(point1, point2):
return math.sqrt(sum((a - b) ** 2 for a, b in zip(point1, point2)))
# 2D points
A = (1, 2)
B = (4, 6)
C = (1, 5)
print(f"Distance A to B: {euclidean_distance(A, B):.2f}")
print(f"Distance A to C: {euclidean_distance(A, C):.2f}")
print(f"Distance B to C: {euclidean_distance(B, C):.2f}")Euclidean distance from A(1,2) to B(4,6) = sqrt((4-1)^2 + (6-2)^2) = sqrt(9+16) = sqrt(25) = 5.0. From A to C = sqrt(0+9) = 3.0. From B(4,6) to C(1,5) = sqrt(9+1) = sqrt(10) = 3.16.
import math
from collections import Counter
def euclidean_distance(p1, p2):
return math.sqrt(sum((a - b) ** 2 for a, b in zip(p1, p2)))
def knn_classify(train_data, train_labels, new_point, k=3):
distances = []
for i, point in enumerate(train_data):
d = euclidean_distance(point, new_point)
distances.append((d, train_labels[i]))
distances.sort(key=lambda x: x[0])
k_nearest = [label for _, label in distances[:k]]
vote = Counter(k_nearest).most_common(1)[0][0]
return vote
# Training data: (x, y) coordinates with labels
train_data = [(1, 1), (1, 2), (2, 1), (6, 5), (7, 6), (7, 5)]
train_labels = ['A', 'A', 'A', 'B', 'B', 'B']
# Classify new points
test_points = [(2, 2), (5, 5), (1, 0)]
for point in test_points:
label = knn_classify(train_data, train_labels, point, k=3)
print(f"Point {point} -> Class {label}")For point (2,2) with k=3, the three nearest training points are (1,1), (1,2), and (2,1), all class A. For (5,5), the nearest neighbors are the B-class points. The algorithm simply counts votes among the k nearest neighbors.
def accuracy(y_true, y_pred):
correct = sum(1 for t, p in zip(y_true, y_pred) if t == p)
return correct / len(y_true)
y_true = ['cat', 'dog', 'cat', 'cat', 'dog', 'dog', 'cat', 'dog', 'cat', 'dog']
y_pred = ['cat', 'dog', 'cat', 'dog', 'dog', 'cat', 'cat', 'dog', 'cat', 'dog']
acc = accuracy(y_true, y_pred)
print(f"True labels: {y_true}")
print(f"Predicted labels: {y_pred}")
print(f"Accuracy: {acc:.1%}")
print(f"Correct: {int(acc * len(y_true))}/{len(y_true)}")Comparing element by element: positions 0,1,2,4,6,7,8,9 are correct (8 out of 10). Positions 3 and 5 are incorrect (cat predicted as dog, and dog predicted as cat). Accuracy = 8/10 = 80%.
import math
from collections import Counter
def euclidean_distance(p1, p2):
return math.sqrt(sum((a - b) ** 2 for a, b in zip(p1, p2)))
def knn_classify(train_data, train_labels, new_point, k):
distances = []
for i, point in enumerate(train_data):
d = euclidean_distance(point, new_point)
distances.append((d, train_labels[i]))
distances.sort(key=lambda x: x[0])
k_nearest = [label for _, label in distances[:k]]
return Counter(k_nearest).most_common(1)[0][0]
train_data = [(0, 0), (1, 0), (0, 1), (3, 3), (4, 3), (3, 4), (2, 2)]
train_labels = ['A', 'A', 'A', 'B', 'B', 'B', 'A']
test_point = (2.5, 2.5)
print(f"Test point: {test_point}\n")
for k in [1, 3, 5, 7]:
result = knn_classify(train_data, train_labels, test_point, k)
print(f"K={k}: Predicted class = {result}")The same point can be classified differently depending on K. With K=1, the nearest point (3,3) at distance 0.71 is class B. With K=3 and K=5, the nearby B-class points dominate. With K=7, all training points are included and the four A-class points outvote the three B-class points. This demonstrates why K selection is important and should be tuned using validation data.
Classification, K-Nearest Neighbors, Decision boundaries, Accuracy, Distance metrics