K-nearest neighbors

The 'K' is the number of nearest training examples (neighbors) that the algorithm looks at when making a prediction for a new data point. For classification, the new point is assigned the majority class among these K neighbors; for regression, it is assigned their average value. Choosing K is a key hyperparameter that affects the model's bias and variance.

KNN is called a lazy learner because it does not build an explicit model during a training phase; instead it simply stores the entire training dataset. All the real computation, such as calculating distances to neighbors, is deferred until a prediction is actually requested. This makes training instant but prediction relatively slow.

The algorithm finds the K closest training points to the new point using a distance metric, then takes a majority vote among their class labels. The class that appears most frequently among the K neighbors becomes the prediction. Ties can be broken by choosing the class of the single closest neighbor or by using an odd value of K.

The Euclidean distance is the square root of the sum of squared differences of coordinates: sqrt((4-1)^2 + (6-2)^2) = sqrt(9 + 16) = sqrt(25) = 5. This straight-line distance is the most common metric used in KNN. It works well when features are on comparable scales.

import math
d = math.sqrt((4-1)**2 + (6-2)**2)
print(d)  # 5.0

KNN relies on distance calculations, so features with larger numeric ranges will dominate the distance and overshadow features with smaller ranges. For example, a salary measured in thousands would overwhelm an age measured in years. Scaling features (e.g., with standardization or min-max normalization) ensures each feature contributes fairly to the distance.

from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X_train)

Yes, KNN can perform regression. Instead of taking a majority vote, it predicts the average (or sometimes a weighted average) of the target values of the K nearest neighbors. This produces a continuous numeric output rather than a class label.

from sklearn.neighbors import KNeighborsRegressor
model = KNeighborsRegressor(n_neighbors=3)
model.fit(X_train, y_train)

With K = 1, the prediction is based entirely on the single nearest neighbor, which makes the model very sensitive to noise and outliers. This usually gives a low-bias but high-variance model that can overfit the training data. The decision boundary becomes very jagged and irregular.

If K is too large, the model considers too many neighbors and the prediction becomes overly smoothed, often just predicting the overall majority class regardless of the input. This leads to high bias and underfitting. The local structure of the data is lost.

Using an odd value of K helps avoid ties in the majority vote when there are two classes. With an even K, the neighbors could split evenly (e.g., 2 vs 2), leaving no clear winner. An odd K guarantees a majority for one of the two classes.

Manhattan distance is the sum of the absolute differences of the coordinates, like the distance traveled along a grid of city blocks. Euclidean distance is the straight-line distance using squared differences. Manhattan distance can be more robust in high dimensions and when movement is restricted to axes.

abs(4-1) + abs(6-2)  # Manhattan distance = 7

The curse of dimensionality refers to the fact that as the number of features grows, data points become increasingly spread out and distances between all points become similar. This makes the notion of 'nearest' neighbor less meaningful, degrading KNN's accuracy. Dimensionality reduction or feature selection can help mitigate it.

For a naive brute-force implementation, predicting one point requires computing the distance to every training sample, giving O(n * d) time where n is the number of training points and d is the number of features. Finding the K smallest distances adds a sorting or selection cost. This is why KNN prediction can be slow on large datasets.

A KD-tree partitions the feature space into nested regions so that the search can ignore large portions of the data that are clearly too far away. This can reduce the average query time from O(n) toward O(log n) in low dimensions. However, KD-trees lose their advantage in very high-dimensional data.

from sklearn.neighbors import KNeighborsClassifier
model = KNeighborsClassifier(n_neighbors=5, algorithm='kd_tree')

In distance-weighted KNN, closer neighbors are given more influence on the prediction than farther ones, often by weighting each neighbor's vote by 1/distance. This means a very close point matters more than a distant one within the K set. It can improve accuracy, especially when K is larger.

KNeighborsClassifier(n_neighbors=5, weights='distance')

KNN is non-parametric, meaning it does not assume a fixed functional form or a fixed number of parameters for the underlying data distribution. Instead, its complexity grows with the data, since it keeps all training examples. This flexibility lets it model complex, irregular decision boundaries.

A small K gives low bias but high variance because predictions follow the training data closely and are sensitive to noise. A large K gives high bias but low variance because predictions are smoothed over many points. The best K balances the two, usually found via cross-validation.

A common approach is k-fold cross-validation, where models with different K values are trained and validated on different splits of the data, and the K that gives the best average validation performance is selected. Plotting the error against K (an 'elbow' plot) also helps identify a good value. This avoids guessing K arbitrarily.

from sklearn.model_selection import cross_val_score
for k in range(1, 20, 2):
    scores = cross_val_score(KNeighborsClassifier(n_neighbors=k), X, y, cv=5)
    print(k, scores.mean())

Because KNN is an instance-based method, it must store the entire training dataset in memory to compare against new points at prediction time. There is no compact model summarizing the data, so memory usage grows directly with the size of the training set. This makes it impractical for very large datasets without modification.

In imbalanced data, the majority class has many more points, so the K nearest neighbors are more likely to belong to that class even near minority-class points. This biases predictions toward the majority class. Remedies include distance weighting, resampling the data, or choosing K carefully.

The KNeighborsClassifier class from sklearn.neighbors is used for classification tasks. You set the number of neighbors with the n_neighbors parameter, then call fit() with the training data and predict() for new data. For regression, KNeighborsRegressor is used instead.

from sklearn.neighbors import KNeighborsClassifier
clf = KNeighborsClassifier(n_neighbors=5)
clf.fit(X_train, y_train)
preds = clf.predict(X_test)

KNN is a supervised learning algorithm that uses labeled data to classify or predict new points based on nearby examples. K-means is an unsupervised algorithm that groups unlabeled data into K clusters by finding cluster centers. They both use distances and the letter K, but solve very different problems.

Because KNN makes decisions based on local neighborhoods rather than a global linear equation, the boundary between classes adapts to the local arrangement of data points. This allows it to form complex, curved, and irregular boundaries. No assumption of linear separability is required.

Categorical features should be encoded numerically, for example with one-hot encoding, so that distance calculations are meaningful. Simply assigning arbitrary integers to categories can imply a false ordering and distort distances. Alternatively, a distance metric designed for categorical data (like Hamming distance) can be used.

import pandas as pd
X_encoded = pd.get_dummies(X, columns=['color'])

It means that calling 'fit' on a KNN model essentially just stores the training data (and may build an index like a KD-tree) rather than optimizing learned parameters. The core work, distance calculation and neighbor search, happens when predictions are made. As a result, training is fast but prediction is comparatively expensive.

Counting the votes, class A appears 3 times and class B appears 2 times. Majority voting selects the most frequent class, so the prediction is A. The point is assigned to A because it has the larger count among the 5 neighbors.

Minkowski distance uses a parameter p in the formula (sum of |x_i - y_i|^p)^(1/p). When p = 2 it becomes Euclidean distance, and when p = 1 it becomes Manhattan distance. Adjusting p lets you tune how distances are measured for a given problem.

KNeighborsClassifier(n_neighbors=5, metric='minkowski', p=2)

With a small K, a single mislabeled or anomalous neighbor can directly change the prediction since few points are consulted. Outliers can therefore have an outsized effect on the decision. Increasing K or using distance weighting reduces this sensitivity.

Min-max normalization rescales each feature using (x - min) / (max - min), mapping values into the range [0, 1]. This ensures all features contribute comparably to distance calculations in KNN. It is an alternative to standardization, which centers data to zero mean and unit variance.

from sklearn.preprocessing import MinMaxScaler
X_scaled = MinMaxScaler().fit_transform(X)

The scaler's parameters (like min, max, mean, or standard deviation) must be learned only from training data to avoid leaking information from the test set into the model. The same fitted scaler is then applied to transform the test data. Fitting on all data would cause data leakage and give optimistic results.

scaler.fit(X_train)
X_train_s = scaler.transform(X_train)
X_test_s = scaler.transform(X_test)

A key advantage of KNN is its simplicity: it is easy to understand and implement, requires no training phase, and makes no assumptions about the data's distribution. It can also naturally handle multi-class problems and adapt to complex decision boundaries. These traits make it a useful baseline model.

KNN regression predicts the average of the neighbors' target values: (10 + 20 + 30) / 3 = 20. The output is a continuous number rather than a class label. If distance weighting were used, closer neighbors would influence the average more.

sum([10, 20, 30]) / 3  # 20.0

Cosine similarity measures the angle between two feature vectors, focusing on their direction rather than their magnitude. Euclidean distance measures the actual straight-line distance, which is affected by magnitude. Cosine is often preferred for text or high-dimensional sparse data where orientation matters more than length.

Because each prediction requires computing distances to potentially every training point, the cost scales with the size of the dataset. For very large datasets this makes each query slow, which is problematic when fast responses are needed. Approximate nearest neighbor methods or tree structures can help speed it up.

Cross-validation systematically evaluates different combinations of K and distance metrics on held-out folds, helping choose the configuration that generalizes best to unseen data. This avoids overfitting hyperparameter choices to a single train-test split. Tools like GridSearchCV automate this search over the hyperparameter grid.

from sklearn.model_selection import GridSearchCV
params = {'n_neighbors': [3,5,7], 'metric': ['euclidean','manhattan']}
gs = GridSearchCV(KNeighborsClassifier(), params, cv=5)
gs.fit(X_train, y_train)