k-Nearest Neighbors

This page uses supervised uniform Euclidean k-nearest-neighbor classification. A new observation is classified from labeled training observations that are closest under a defined distance metric.

Cover and Hart state the one-nearest-neighbor rule: assign an unclassified point the category of the nearest previously classified point. The rule uses labeled training pairs. It is not a clustering method, not an unsupervised method, and not a probabilistic generative classifier of the LDA type.

scikit-learn describes neighbors-based classification as instance-based or non-generalizing learning: the method stores training instances rather than fitting a global parametric decision function. Practical implementations still have a fit step that stores the training data and may build a search structure. Do not say that k-NN has no training. The stored labels are required to classify a new object.

Alsberg, Goodacre, Rowland, and Kell used Euclidean k-NN on pyrolysis mass spectra. That supports chemometric use of the method. It does not define the theory on this page.

k-NN classifies from local labeled geometry. The decision for a query depends on the labels of its nearest training observations under the chosen metric. Cover and Hart treat this as a nonparametric rule in the sense that it does not require a specified joint distribution on the measurements and labels. That is not the claim that the method has no parameters. The neighbor count $k$ is a hyperparameter.

The same vote formulation handles two or more class labels without a one-versus-rest construction. That property does not make k-NN universally preferable to LDA, PLS-DA, or later classifiers. It describes the assignment rule.

Nearest is defined by a distance metric. Euclidean distance is not inherent to every k-NN method. This page uses Euclidean distance as the educational default. For vectors $x$ and $z$ with $p$ predictors,

$d(x,z)=\sqrt{{\sum }_{j=1}^p(x_j-z_j{)}^2}$.

scikit-learn documents Minkowski distance with exponent p. To avoid colliding with the number of predictors, this page writes the Minkowski order as $r$:

$d_r(x,z)=({\sum }_{j=1}^p|x_j-z_j{|}^r{)}^{1/r}$. Then $r=2$ is Euclidean distance and $r=1$ is Manhattan distance, matching the scikit-learn Minkowski identities.

Changing the metric changes which training observations are nearest. This page does not catalog every software distance. The scientific point is that the metric defines neighborhood structure.

Let the training set be pairs $(x_i,y_i)$ for $i=1,\dots ,n$. For a query $x$, the 1-nearest-neighbor rule of Cover and Hart selects

and predicts $\hat{y}=y_{i^{\ast }}$.

For general $k$, let $N_k(x)$ be the indices of $k$ training observations of smallest distance to $x$. Cover and Hart, citing Fix and Hodges, describe the $k$-nearest-neighbor rule as assigning the class most heavily represented among those neighbors. scikit-learn states the same assignment: the query receives the class with the most representatives among its nearest neighbors. Alsberg et al. write the chemometric form as the class with the largest number of objects among the $K$ neighbors.

For uniform votes that largest count is

In two-class problems with odd $k$ this can be an absolute majority. In multiclass problems the winning class may have only a plurality. This page uses largest vote count. It does not treat majority as a universal description.

scikit-learn also supports weights="distance": closer neighbors receive greater influence by inverse distance. That is a software option, not the page educational rule. The educational code uses uniform votes only. Inverse distance is not published here as a universal formula $w_i=1/d_i$, because a zero distance would divide by zero. In the current scikit-learn implementation, if a query coincides with one or more training observations, those zero-distance neighbors receive weight 1 and the remaining selected neighbors receive weight 0.

The classifier is the neighbor-and-vote rule. Brute force, KD-tree, and ball-tree searches are computational strategies for finding those neighbors. They do not redefine the classifier.

Equations 1 to 4 are the page educational formulation: Euclidean distance, a $k$-neighborhood, uniform vote counts, and assignment by largest count. Fitted software may use a different metric, weighting, or tie convention. Those choices must be stated when results are compared.

Algorithm 1 is the classification workflow. It is not a description of a KD-tree or ball-tree. For several query observations the same steps are repeated.

The integer $k$ is a model hyperparameter. There is no universal best value. Do not treat $k=3$, $k=5$, odd $k$, or $\sqrt{n}$ as scientific defaults. scikit-learn currently defaults n_neighbors to 5. MATLAB fitcknn currently defaults NumNeighbors to 1. Those are software defaults, not optima.

scikit-learn states that the choice of $k$ is highly data-dependent: a larger $k$ can suppress the effects of noise and can make classification boundaries less distinct. Cover and Hart note the same qualitative tension: a larger neighborhood can reduce the chance of a non-Bayes local decision, while a smaller neighborhood keeps the neighbors closer to the query. Those statements are not the claim that small $k$ always overfits or that large $k$ always underfits.

Select candidate values $k_1,\dots ,k_m$ inside model development. Evaluate each under the same validation design, with identical folds, the same preprocessing, and the same classification metric. Do not generate a new random partition for every $k$ and then attribute all differences to $k$. Do not select $k$ on the final test set. For an unbiased performance claim after that selection, use an outer validation loop or an untouched external test set, as locked on the Cross-Validation page. Evaluate held-out labels with the Classification Metrics page. Training accuracy is not independent predictive evidence.

Distances change if predictor scales change. scikit-learn demonstrates that heterogeneous numerical scales can dominate Euclidean neighborhoods: in the wine example, proline varies on a much larger numerical range than hue, so unscaled distances are driven mainly by proline. After column standardization both variables can influence the neighborhood. That is a modeling fact. It is not the claim that k-NN always requires StandardScaler.

For chemical spectra, scaling and pretreatment depend on the measurement representation. SNV, MSC, derivatives, normalization, and autoscaling change geometry in different ways. scikit-learn StandardScaler uses population standard deviation. The Normalization and Scaling page defines autoscaling with sample standard deviation. Those conventions are not interchangeable. Do not autoscale every spectrum by default. Link pretreatment choices to Normalization and Scaling. If scaling parameters are estimated from several observations, fit them on the training fold only and apply the learned transformation to the validation or test fold. Use a Pipeline in Python. Do not call StandardScaler.fit_transform(X) on the full matrix before cross-validation. A purely sample-wise transform has a different leakage structure, as already distinguished on the Cross-Validation page.

Nearest-neighbor methods need contrast between near and far points. Beyer, Goldstein, Ramakrishnan, and Shaft show that, under a broad set of stated conditions, as dimensionality increases the nearest and farthest distances can become increasingly similar. They explicitly warn that this should not be read as the claim that nearest neighbor is never meaningful in high dimensions, and they identify workloads where the contrast remains informative. This page does not say that all distances become equal, and it does not say that k-NN cannot work above a fixed number of dimensions.

Spectroscopic matrices can have many wavelength or wavenumber variables, strong correlations, and fewer independent observations than measured variables. High dimensionality alone does not prove that k-NN will fail. Distance meaningfulness depends on data geometry, pretreatment, and intrinsic structure.

PCA can be used to build a lower-dimensional representation before k-NN. This page does not recommend PCA-kNN as a default. If PCA is used inside a performance claim, fit PCA inside each training fold. Fitting PCA on all rows and then cross-validating only k-NN leaks validation information into the features. If wavelengths are selected using class labels, that selection also belongs inside model-development validation.

The first Python listing is an educational implementation of Equations 1 to 4. It stores the training matrix during fit_knn_uniform. Neighbor order uses Euclidean distance, then original training index when distances are equal. Vote ties use the smallest class index in np.unique order. That is an implementation convention. It is aligned with MATLAB BreakTies="smallest" for vote-count ties. It is not a universal k-NN law, and it is not claimed to match scikit-learn on distance-tie edge cases.

Production classification uses sklearn KNeighborsClassifier with explicit n_neighbors, weights="uniform", and metric="euclidean". fit stores the training data. predict returns class labels. kneighbors returns neighbor distances and indices. predict_proba returns class probability estimates from neighbor vote shares, with classes in lexicographic order. Those outputs are not independently calibrated probabilities. scikit-learn warns that if neighbors $k$ and $k+1$ have identical distances but different labels, results can depend on the ordering of the training data.

MATLAB training uses fitcknn with NumNeighbors, Euclidean distance, and BreakTies="smallest". Prediction uses predict. MATLAB documents additional options BreakTies="nearest" and BreakTies="random". sklearn and MATLAB do not share one tie policy. MATLAB Standardize=true centers and scales each predictor by its column mean and standard deviation. The default is false. That convention is not assumed to match sklearn StandardScaler. Hyperparameter optimization in MATLAB, if used, still belongs inside the appropriate validation procedure.

import numpy as np  def _validate_xy(X, y):    X = np.asarray(X, dtype=float)    y = np.asarray(y).reshape(-1)    if X.ndim != 2:        raise ValueError("X must be a 2D array of samples by variables.")    if X.shape[0] != y.shape[0]:        raise ValueError("X and y must have the same number of observations.")    if min(X.shape) == 0:        raise ValueError("X must have at least one row and one column.")    if not np.all(np.isfinite(X)):        raise ValueError("X must contain only finite values.")    return X, y  def euclidean_distances(X, z):    X = np.asarray(X, dtype=float)    z = np.asarray(z, dtype=float).reshape(-1)    if X.ndim != 2:        raise ValueError("X must be a 2D array of samples by variables.")    if z.shape[0] != X.shape[1]:        raise ValueError("Query z must have one value per predictor.")    if not np.all(np.isfinite(z)):        raise ValueError("Query z must contain only finite values.")    return np.sqrt(np.sum((X - z) ** 2, axis=1))  def knn_neighborhood(X, z, k):    X = np.asarray(X, dtype=float)    n = X.shape[0]    if int(k) != k or k < 1 or k > n:        raise ValueError("k must be an integer between 1 and n inclusive.")    k = int(k)    distances = euclidean_distances(X, z)    # Equal distances: keep the smaller original training index.    order = np.lexsort((np.arange(n), distances))    idx = order[:k]    return idx, distances[idx]  def knn_vote_counts(y_neighbors, classes):    y_neighbors = np.asarray(y_neighbors).reshape(-1)    classes = np.asarray(classes).reshape(-1)    return np.array(        [int(np.sum(y_neighbors == c)) for c in classes],        dtype=int,    )  def fit_knn_uniform(X, y, k):    X, y = _validate_xy(X, y)    if int(k) != k or k < 1 or k > X.shape[0]:        raise ValueError("k must be an integer between 1 and n inclusive.")    return {        "X": X,        "y": y,        "k": int(k),        "classes": np.unique(y),    }  def predict_knn_uniform(model, X_query):    X_query = np.asarray(X_query, dtype=float)    if X_query.ndim != 2:        raise ValueError("X_query must be a 2D array of samples by variables.")    if X_query.shape[1] != model["X"].shape[1]:        raise ValueError("X_query must have the same number of variables as X.")    if X_query.shape[0] > 0 and not np.all(np.isfinite(X_query)):        raise ValueError("X_query must contain only finite values.")    classes = model["classes"]    y_hat = np.empty(X_query.shape[0], dtype=model["y"].dtype)    for i, z in enumerate(X_query):        idx, _distances = knn_neighborhood(model["X"], z, model["k"])        votes = knn_vote_counts(model["y"][idx], classes)        # Implementation convention, not a universal k-NN law:        # among classes with the largest vote count, choose the        # smallest class index in np.unique order.        y_hat[i] = classes[int(np.argmax(votes))]    return y_hat 

1. 1.

   Cover, T. M., & Hart, P. E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21-27.

   doi:10.1109/TIT.1967.1053964
2. 2.

   Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999). When Is “Nearest Neighbor” Meaningful? Proceedings of the 7th International Conference on Database Theory. Lecture Notes in Computer Science 1540, 217-235.

   doi:10.1007/3-540-49257-7_15
3. 3.

   Alsberg, B. K., Goodacre, R., Rowland, J. J., & Kell, D. B. (1997). Classification of pyrolysis mass spectra by fuzzy multivariate rule induction-comparison with regression, K-nearest neighbour, neural and decision-tree methods. Analytica Chimica Acta, 348(1-3), 389-407.

   doi:10.1016/S0003-2670(97)00064-0
4. 4.

   scikit-learn Developers (n.d.). KNeighborsClassifier and Nearest Neighbors. scikit-learn 1.6 documentation.

5. 5.

   The MathWorks, Inc. (n.d.). fitcknn, ClassificationKNN, and predict (ClassificationKNN). MATLAB documentation.