70 K-Nearest Neighbors Interview Questions and Answers (2026)

KNN is a supervised algorithm that predicts a label for a point from its K labeled neighbors. K-Means is an unsupervised algorithm that partitions unlabeled data into K clusters. They share the letter K and a reliance on distance, but they solve different problems.

• Task and data:

  • KNN: classification or regression; it needs labeled training data.

  • K-Means: clustering; it uses no labels and discovers groups on its own.

• Meaning of K:

  • KNN: the number of neighbors consulted for each prediction.

  • K-Means: the number of clusters (centroids) to find.

• Training behavior:

  • KNN is lazy: it stores the data and does all the work at query time.

  • K-Means is eager and iterative: it alternates assigning points to the nearest centroid and recomputing centroids until convergence.

• Output:

  • KNN: a predicted label or value for a new point.

  • K-Means: K centroids plus a cluster assignment for each point.

• Shared traits: both depend on a distance metric, so both are sensitive to feature scaling and to the choice of K.

KNN is non-parametric because it does not assume a fixed functional form with a fixed number of parameters. Its "model" is the training data itself, so its complexity grows with the dataset.

• Parametric models summarize data in a fixed set of parameters:

  • For example, linear regression learns weights; after training, the data can be discarded.

  • They assume a shape (linear, Gaussian, etc.), which can bias predictions when the assumption is wrong.

• KNN keeps all training points:

  • Predictions are computed from the stored neighbors, and no weights are learned.

  • More data means a larger effective model and more flexible decision boundaries.

• No distributional assumption: It can fit arbitrarily complex boundaries given enough data.

• Common confusion: K is a hyperparameter, not a learned parameter, so its existence doesn't make KNN parametric.

• Trade-off: high flexibility, at the cost of memory, slow prediction and sensitivity to the curse of dimensionality.

For a new point, KNN computes its distance to every training point, picks the K closest, and predicts the class that is most common among those neighbors (majority vote).

1. Preprocess: Scale features (e.g. StandardScaler) so that no single feature dominates the distance.

2. Compute distances: Measure the distance from the query to the training points, usually Euclidean; Manhattan, Minkowski and cosine are alternatives.

3. Select the K nearest neighbors: Use brute force, or speed this up with KD-Tree / Ball Tree or approximate nearest-neighbor indexes.

4. Vote:

   • Majority vote: each neighbor counts equally.

   • Distance-weighted vote (weights='distance'): closer neighbors count more.

   • Class probabilities are the vote fractions (e.g. 3 of 5 neighbors gives 0.6).

5. Handle ties: Use an odd K for binary problems, apply distance weighting, or fall back to the single nearest neighbor.

For regression, KNN finds the K nearest training points exactly as it does for classification. It then predicts the average of their target values (optionally weighted by distance) instead of taking a vote.

• Steps:

  1. Scale features and compute distances from the query to the training points.

  2. Take the K closest points.

  3. Predict the mean of their targets, or the median if you want robustness to outliers.

• Distance weighting: Use a weighted mean with weights such as 1/d, so that nearer neighbors influence the prediction more (KNeighborsRegressor(weights='distance')).

• Effect of K:

  • Small K: a jagged, high-variance fit that follows noise.

  • Large K: a smoother, higher-bias fit that flattens toward the global mean.

• Limitations:

  • It produces a piecewise-constant prediction surface.

  • It cannot extrapolate: predictions always stay within the range of the training targets.

KNN's prediction is literally "these specific training examples were most similar, and here is what they were." You can point to the evidence behind every decision. A neural network, by contrast, spreads its reasoning across millions of learned weights.

• Example-based explanations:

  • You can show the K neighbors, their labels and their distances.

  • Explanations like "similar to these 5 approved loans" are intuitive even for non-experts.

• Simple, transparent decision rule: A vote or average over neighbors, with no hidden layers or nonlinear transformations.

• Easy to audit and debug:

  • Mislabeled or anomalous neighbors are visible directly.

  • Fixing the data immediately changes behavior, with no retraining needed.

• Caveats:

  • Interpretability degrades in high dimensions, where "nearness" is hard to understand.

  • It also degrades with learned embeddings, where the distance itself is opaque.

  • There is no global model or feature importance: KNN explains individual predictions locally, not the overall logic.

Eager learners build a generalized model from the training data up front and then discard the data. Lazy learners (like KNN) just store the data and defer all computation until a query arrives.

• Eager learning (e.g. linear regression, decision trees, neural nets):

  • Training is slow and expensive; prediction is fast and cheap.

  • Makes a single global approximation of the target function.

  • Has a compact memory footprint (only the parameters are kept).

• Lazy learning (e.g. KNN, case-based reasoning):

  • Training is trivial: it just stores the data.

  • Prediction is costly: roughly O(n·d) per query with brute force.

  • Builds a local approximation for each query, which can capture complex boundaries.

  • Requires keeping the full training set in memory.

• Practical implications:

  • Lazy learners adapt instantly to new data: add points and no retraining is needed.

  • They struggle with latency at scale unless you use indexes such as KD-Trees or ANN (e.g. FAISS).

KNN is simple, assumption-free and flexible, but it is expensive at prediction time, memory-hungry, and fragile with unscaled, noisy or high-dimensional data.

• Advantages:

  • Simple to understand and implement, and there is no training phase.

  • Non-parametric: it learns arbitrarily complex, nonlinear boundaries.

  • Handles classification, regression and multi-class problems naturally.

  • New data can be added without retraining.

  • Interpretable through the neighbors behind each prediction.

• Disadvantages:

  • Slow prediction (O(n·d) per query) and must store the whole dataset.

  • Curse of dimensionality: in high dimensions, distances become nearly uniform and lose meaning.

  • Requires feature scaling, and is sensitive to irrelevant features.

  • Sensitive to noise and outliers (especially with small K) and to class imbalance (the majority class dominates votes).

  • Results hinge on the choice of K and the distance metric.

  • Cannot extrapolate beyond the training data.

• Mitigations:

  • Speed: KD-Tree / Ball Tree / ANN indexes.

  • Dimensionality: dimensionality reduction (PCA) or feature selection.

  • Noise and imbalance: distance weighting.

  • Hyperparameters: choose K and the metric with cross-validation.

KNN is supervised. It needs labeled training data, and it predicts a new point's label or value from the labels of its nearest neighbors.

• Why it's supervised:

  • Classification votes over the neighbors' class labels; regression averages their targets.

  • Without labels, there is nothing to vote on or average.

• Source of confusion:

  • It is often mixed up with K-Means, which is unsupervised clustering.

  • The plain nearest-neighbor search itself (e.g. sklearn.neighbors.NearestNeighbors) needs no labels. It is used in unsupervised settings such as anomaly detection (distance to the k-th neighbor), building kNN graphs for spectral clustering, and DBSCAN-style density estimation.

• Interview framing: "The KNN classifier/regressor is supervised; the underlying neighbor search is a general tool that also powers unsupervised methods."

Euclidean distance is the straight-line (L2) distance between two feature vectors: the square root of the sum of squared per-feature differences. It is the default metric in most KNN implementations.

• Formula: d(x, y) = sqrt(Σᵢ (xᵢ − yᵢ)²):

  • It is Minkowski distance with p = 2 (scikit-learn's default metric='minkowski', p=2).

  • For ranking neighbors the square root can be skipped, because squared distance preserves the order.

• Properties:

  • Squaring penalizes large differences in a single feature heavily, so it is sensitive to outliers.

  • It is rotation-invariant and treats all dimensions as equally important.

• Practical requirements:

  • Scale features first (standardize or min-max), or large-range features will dominate the distance.

  • It loses contrast in high dimensions, where all distances become similar.

Hamming distance counts the number of positions at which two equal-length vectors differ. It is the natural dissimilarity measure for categorical, binary, or string data, where magnitudes have no meaning.

• Definition: d(x, y) = Σᵢ 1[xᵢ ≠ yᵢ]:

  • Example: "karolin" vs "kathrin" gives 3 differing positions.

  • It is often normalized by length to give a fraction in [0, 1]. scikit-learn's metric='hamming' returns this fraction.

• Use in KNN:

  • Suited to categorical features, binary fingerprints, DNA sequences, and hashed codes.

  • For bit vectors it is computed very fast via XOR plus popcount.

• Limitations:

  • All mismatches count equally, so it ignores how different two categories are.

  • It requires equal-length vectors. Variable-length strings need edit (Levenshtein) distance instead.

  • For sparse binary data, Jaccard is often better, because Hamming counts shared zeros as agreement.

KNN ranks neighbors purely by distance, so a feature with a large numeric range dominates the distance and effectively decides who the neighbors are, regardless of how informative it is. Scaling puts features on comparable ranges so each one contributes fairly.

• Distance is unit-dependent:

  • Example: income (0 to 200,000) and age (18 to 90). A 10-year age gap is negligible next to a $1,000 income gap, so age is ignored.

  • Changing units (meters to millimeters) changes the neighbors, which is a sign the model depends on an arbitrary choice.

• KNN has no learned weights to compensate: Linear models can shrink a coefficient for a large-scale feature; KNN uses raw coordinates directly, so scale is an implicit, unintended weight.

• Common choices: Standardization (StandardScaler), min-max (MinMaxScaler), or RobustScaler when outliers are present.

• Fit the scaler on training data only and apply it to test/query points (a pipeline prevents leakage).

• Caveat: equal scale is a default, not a guarantee of equal importance; deliberate feature weighting may still help.

With two classes and uniform voting, an odd k makes a tied majority vote impossible. Every prediction then has a clear winner, with no arbitrary tie-breaking.

• The tie problem:

  • With k = 4, a 2–2 split is possible, so the prediction depends on a tie-break rule rather than the data.

  • In scikit-learn, vote ties go to the class that appears first in classes_ (the argmax behavior), which is an arbitrary bias.

• Limits of the rule:

  • It only guarantees no ties for binary problems. With 3 or more classes, an odd k can still tie (e.g. k = 3 with labels A, B, C).

  • It does not fix ties in distance, where several points sit exactly at the k-th distance.

• Alternatives:

  • Distance weighting (weights='distance') makes exact ties very unlikely for any k.

  • You can also break ties by the nearest neighbor's label, or by the smaller average distance.

• Odd k is a convenience, not a requirement. k should still be chosen by cross-validation.

Choose k by cross-validation over a range of values. Pick the k with the best validation score on the metric you actually care about, keeping in mind that k controls the bias–variance trade-off.

• What k controls:

  • Small k gives low bias and high variance: jagged boundaries that are sensitive to noise and prone to overfitting.

  • Large k gives high bias and low variance: smooth boundaries that drift toward the majority class or global mean, which underfits.

• Procedure:

  1. Scale the features inside a Pipeline so the scaler is fit per fold.

  2. Grid-search k (e.g. 1 to about 50, odd values for binary problems) using stratified k-fold or LOOCV, which is cheap for KNN.

  3. Plot validation score against k. Prefer the larger k within one standard error of the best score, since it is more stable.

  4. Confirm on a held-out test set.

• Tune jointly:

  • The best k depends on the distance metric and on weights.

  • With 'distance' weighting, a larger k hurts less.

• Heuristics are only starting points:

  • k ≈ √n is a common rule of thumb.

  • Noisy labels favor a larger k.

  • Make k smaller than the size of the smallest class, so that class can still win votes.

The probability of class c is the fraction of the k nearest neighbors that belong to c. With distance weighting, it is the share of total neighbor weight that belongs to c.

• Uniform votes:

  • P(c|x) = (number of neighbors with label c) / k

  • This is a local density estimate: it approximates the posterior in a small region around x.

• Weighted votes: P(c|x) = Σ w_i·[y_i=c] / Σ w_i, for example with w_i = 1/d_i.

• Limitations:

  • The estimates are coarse: only values in {0, 1/k, …, 1} are possible, so small k gives poorly calibrated probabilities of 0 or 1.

  • Fixes: use a larger k, apply Laplace smoothing (count+α)/(k+α·C), or calibrate with CalibratedClassifierCV.

Distance weighting lets closer neighbors count more than farther ones. Predictions then reflect the most similar points, and results become less sensitive to the exact choice of k.

• Problem with uniform voting:

  • A neighbor at the edge of the neighborhood has the same say as one almost on top of the query.

  • With larger k, distant points (often from a denser majority class) can outvote a few very close points.

• Benefits of weighting (e.g., w = 1/d or a Gaussian kernel):

  • It is more faithful to the locality assumption (closer means more similar).

  • It is more robust to k: you can use a larger k for stability without blurring local structure.

  • Ties become very unlikely because weighted sums rarely match exactly.

  • It gives smoother, more informative probability estimates.

• Costs:

  • It is more sensitive to a single very close noisy point.

  • It needs a safeguard for zero distances.

  • It depends even more on proper feature scaling.

• In scikit-learn, use weights="distance" or pass a custom callable.

The curse of dimensionality is a set of effects that appear as the number of features grows. Volume expands exponentially, so data becomes extremely sparse, and distances between points become nearly indistinguishable. Distance-based methods like KNN, k-means, and RBF kernels rely on "close means similar," and that assumption breaks.

• Space grows exponentially, so data becomes sparse:

  • Keeping the same sampling density needs exponentially more data: 10 points per axis means 10^d points.

  • In a unit hypercube, a sub-cube capturing a fraction r of the data has edge length r^(1/d). For d=10 and r=1%, that edge is about 0.63, so a "local" neighborhood spans most of each axis.

• Distances concentrate: The nearest and farthest points end up at almost the same distance from a query, so "nearest" carries little information.

• Most volume sits near the boundary: Most points lie near the edges or shell of the space, far from any center or prototype.

• Irrelevant features dominate: Every noisy dimension adds to the distance, drowning out the few informative ones.

• Practical consequences:

  • KNN accuracy drops and needs far more data.

  • Spatial indexes (KD-trees) degrade to brute force.

  • Hubness appears (some points become neighbors of almost everyone).

• Mitigations:

  • Feature selection, PCA or other reduction, learned embeddings, and metric learning.

  • These work because real data usually lies on a much lower intrinsic-dimensional manifold.

Brute-force KNN is a lazy learner. Training just stores the data. Each prediction computes the distance to every training point, which costs O(ND), plus the cost of picking the k smallest.

• Training:

  • Time is O(1) if you keep a reference to the data, or O(ND) to copy it.

  • Memory is O(ND), and the full dataset must be kept at inference time.

• Prediction per query:

  1. Compute distances: N points × D features = O(ND).

  2. Select the k nearest:

  3. O(N) with quickselect (np.argpartition).

  4. O(N log k) with a max-heap.

  5. O(N log N) with a full sort.

  6. Vote or average over the k neighbors: O(k).

  7. Total: O(ND + N log k), which is dominated by O(ND).

• Batch of M queries:

  • O(MND) time.

  • In practice this is computed as a matrix product using ‖x−q‖² = ‖x‖² + ‖q‖² − 2x·q, which is very fast on BLAS or GPU.

• Implication:

  • The cost is shifted entirely to inference.

  • At scale you use KD-trees or ball trees (low D) or approximate indexes like HNSW and FAISS (high D) to get sublinear query time.

KNN always uses a fixed number of neighbors (k) regardless of how far away they are; radius neighbors uses every training point within a fixed distance r, so the number of voters varies with local density.

• Neighborhood definition:

  • KNN: adaptive radius, fixed count. In sparse regions the k neighbors may be far away and barely relevant.

  • Radius: fixed radius, adaptive count. Dense regions get many voters, sparse regions few or none.

• When radius neighbors helps

• Pitfalls:

  • Empty neighborhoods: must handle with an outlier_label or an error (scikit-learn RadiusNeighborsClassifier).

  • r is hard to tune when density varies a lot; one r can be too small in sparse areas and too large in dense ones.

  • Curse of dimensionality: in high dimensions distances concentrate, so a radius tends to capture almost nothing or almost everything.

• Both are lazy learners, need feature scaling, and support distance weighting (weights='distance').

Radius neighbors suits data with fairly uniform density, or cases where "no close match" should be flagged rather than forced into a prediction (it doubles as a simple novelty check).

Neighbor-based collaborative filtering predicts a user's rating for an item from the ratings of similar users (user-based) or from that user's ratings of similar items (item-based), with similarity computed from the user-item rating matrix.

• User-based:

  1. Represent each user as a vector of their item ratings.

  2. Find the k users most similar to the target user who rated item i.

  3. Predict a similarity-weighted average of their (mean-centered) ratings of i.

• Item-based:

  1. Represent each item as a vector of user ratings; precompute item-item similarities.

  2. For target item i, take the k most similar items the user has already rated.

  3. Predict a similarity-weighted average of the user's ratings on those items.

• Similarity measures:

  • Cosine, adjusted cosine, or Pearson correlation computed over co-rated entries.

  • Mean-centering removes rating-scale bias (harsh vs generous raters).

• Why item-based is often preferred in production:

  • Item similarities are more stable than user tastes, so they can be precomputed offline (Amazon's classic approach).

  • Usually fewer items than users, and recommendations are easy to explain ("because you bought X").

• Limitations:

  • Sparsity: few co-rated items make similarities unreliable.

  • Cold start: new users and items have no ratings to compare.

  • Scale: requires approximate nearest neighbor search or precomputation.

The core inductive bias is smoothness, or locality: points that are close in feature space are assumed to have similar labels. The target function is therefore taken to be locally constant (or close to it) around each query.

• What it implies:

  • There is no global functional form: the model assumes no linearity or parametric shape, only local similarity.

  • The distance metric encodes the bias, because it defines what "similar" means.

• Consequences:

  • Feature scaling matters: unscaled features silently dominate the notion of closeness.

  • All features count equally, so irrelevant features corrupt the neighborhoods.

  • The bias breaks in high dimensions, where every point is roughly equally far away (curse of dimensionality).

• How k tunes it:

  • Small k assumes smoothness only at a very local scale, giving low bias and high variance.

  • Large k assumes smoothness over a wider region, giving smoother boundaries and higher bias.

Normal points sit in dense regions, so their k-th nearest neighbor is close; anomalies are isolated, so their k-th neighbor is far. The distance to the k-th neighbor (k-distance) therefore works directly as an outlier score: the larger it is, the more anomalous the point.

• Procedure:

  1. Scale the features and fit a neighbor index on reference (mostly normal) data.

  2. For each point, compute the distance to its k-th neighbor. When scoring training points, exclude the point itself.

  3. Rank points by this score, or flag those above a threshold (for example, a percentile chosen from the expected contamination rate).

• Why k-th rather than 1st:

  • Using k > 1 avoids missing small clusters of anomalies that are near each other but far from everything else.

  • A common variant averages the distances to all k neighbors, which gives a more stable score.

• Limitations:

  • It is a global score, so points in naturally sparse clusters look anomalous. Local Outlier Factor (LocalOutlierFactor) fixes this by comparing a point's density to its neighbors' density.

  • It is sensitive to scaling, to the choice of k, and to high dimensionality.

Choose cosine distance when the direction of a vector carries the meaning and its magnitude is noise. Typical cases are text embeddings, TF-IDF vectors, and other high-dimensional sparse data.

• What cosine measures:

  • Cosine distance is 1 − (x·y)/(‖x‖‖y‖). It depends only on the angle between vectors and ignores their lengths.

  • A long document and a short one on the same topic come out as similar, whereas Euclidean distance would call them far apart.

• Use cosine for:

  • Text (bag-of-words, TF-IDF) and semantic embeddings, many of which are trained with cosine or dot-product objectives.

  • Sparse, high-dimensional data, where magnitudes vary arbitrarily.

  • User-preference vectors, where overall activity level shouldn't dominate.

• Use Euclidean for: Dense, scaled numeric features where magnitude matters, such as physical measurements or coordinates.

• Useful equivalence: On L2-normalized vectors, ‖x − y‖² = 2(1 − cos). Normalizing and then using Euclidean gives the same ranking, so you can use Euclidean-based indexes (KD-tree, many ANN libraries).

Choose Manhattan (L1) distance when you want robustness to outliers or large single-feature differences, when features are independent and grid-like, or when dimensionality is high. Because L1 sums absolute differences instead of squaring them, no single feature dominates the distance.

• Definition: d(x, y) = Σᵢ |xᵢ − yᵢ| (Minkowski with p = 1)

• When L1 is preferable:

  • Outliers or noisy features: a large difference in one feature grows linearly rather than quadratically.

  • High dimensions: L1 keeps more distance contrast than L2 (Aggarwal et al., 2001), so neighbors remain more meaningful.

  • Grid-like or independent features: movement along axes, city blocks, counts, or ordinal attributes where diagonal shortcuts make no sense.

  • Sparse data, where the differences are sums over a few nonzero entries.

• When Euclidean is preferable: Low-dimensional, continuous, geometrically meaningful spaces where straight-line distance matches intuition.

• In practice, treat p as a hyperparameter (KNeighborsClassifier(p=1) vs p=2) and pick it by cross-validation. Scale features either way.

Use a mismatch-counting metric: Hamming distance (or the simple matching coefficient) when 0s and 1s are equally informative, and Jaccard distance when the vectors are sparse and only shared 1s (presences) matter. Euclidean distance on raw label codes is meaningless, because it invents an order and spacing between categories.

• Hamming / simple matching:

  • Counts the positions where the vectors differ, often normalized by the number of features (metric='hamming' in scikit-learn).

  • Treats 0–0 and 1–1 agreements as equally meaningful (symmetric binary), e.g. yes/no survey answers.

  • For raw categorical features this is the "overlap" metric: distance 0 if the categories are equal, 1 otherwise, summed across features.

• Jaccard: Ignores 0–0 matches. Use it for asymmetric binary data such as purchased items or tags, where two users who both did not buy something are not actually similar.

• One-hot plus Euclidean:

  • With one-hot encoding, each mismatched categorical feature contributes 2 to the squared distance, so the result is √(2 × mismatches).

  • That ranks neighbors the same way Hamming does, but high-cardinality features expand into many columns and inflate dimensionality.

• Mixed numeric and categorical data: use Gower's distance, which combines per-feature dissimilarities.

Minkowski distance is a family of distances, dp(x, y) = (Σ|xi − yi|p)1/p. Setting p = 1 gives Manhattan distance and p = 2 gives Euclidean distance, so a single parameter controls how heavily large coordinate differences are weighted.

• Special cases:

  • p = 1: Manhattan (L1), the sum of absolute differences.

  • p = 2: Euclidean (L2), the straight-line distance.

  • p → ∞: Chebyshev (L∞), the maximum absolute difference across coordinates.

• What p changes:

  • Larger p lets the single biggest coordinate gap dominate the distance.

  • Smaller p spreads influence across coordinates, which makes it more robust to one outlying feature.

  • In high dimensions, L1 tends to preserve more contrast between near and far points than L2.

• Validity: for p ≥ 1 it is a true metric. For p < 1 the triangle inequality fails, so metric-tree pruning is no longer safe.

• In scikit-learn, KNeighborsClassifier defaults to metric='minkowski', p=2, which is Euclidean. Treat p as a hyperparameter you can tune with cross-validation.

KNN only needs the order of the distances, and square root is strictly increasing on non-negative numbers. If a < b then √a < √b, so squared distances produce exactly the same nearest-neighbor ranking while skipping one square root per comparison.

• Why it helps:

  • It avoids n square-root operations per query.

  • It enables a fast vectorized form: ‖x − y‖² = ‖x‖² − 2x·y + ‖y‖², which turns the work into matrix multiplications.

  • Libraries use this internally; scikit-learn's trees work with a "reduced distance" for the same reason.

• Where it is NOT interchangeable:

  • Distance-weighted voting: weights of 1/d and 1/d² give different predictions, so convert back to d if the weights should use true distance.

  • Radius queries: the threshold must be squared too (compare against r²).

  • Squared Euclidean is not a metric, because it violates the triangle inequality. Tree pruning bounds must therefore be derived from true distances and then squared consistently.

Jaccard distance is 1 minus the size of the intersection divided by the size of the union of the "on" features. It measures how much two sets of present attributes fail to overlap, and it ignores features that are absent in both.

• Formula (from the binary match counts):

  • M11 counts features where both vectors are 1. M10 and M01 count the mismatches.

  • Jaccard similarity J = M11 / (M11 + M10 + M01), and Jaccard distance = 1 − J.

  • Example: A = {1,1,0,0,1} and B = {1,0,0,0,1}. Then M11 = 2 and mismatches = 1, so J = 2/3 and the distance is 1/3.

• Why ignore 0–0 matches:

  • In sparse data such as baskets, tags or vocabularies, most features are 0 for everyone. Counting shared absences would make every pair look similar.

  • Hamming distance or the simple matching coefficient counts those 0–0 matches, so it suits symmetric binaries instead.

• Properties:

  • Bounded in [0, 1] and a true metric, so it works with ball trees.

  • It is undefined when both sets are empty; the usual convention is a distance of 0.

  • For large-scale search, MinHash LSH approximates Jaccard similarity efficiently.

• In scikit-learn, use metric='jaccard' on boolean arrays.

KNN weights every feature equally in the distance, so irrelevant or noisy features add random variation that drowns out the signal from useful ones. Neighbors are then chosen partly by chance, and accuracy drops, often sharply as such features accumulate.

• Irrelevant features distort neighborhoods:

  • Each one adds a term to the distance that is unrelated to the label, so truly similar points can look far apart and dissimilar points close.

  • Unlike trees or regularized linear models, KNN has no mechanism to ignore a feature.

• Noisy features add variance: Measurement noise perturbs distances, making the neighbor set unstable and predictions inconsistent.

• Curse of dimensionality amplifies it:

  • As dimensions grow, distances concentrate (nearest and farthest become similar), so "nearest" carries little information.

  • More data is needed to keep neighborhoods dense enough to be meaningful.

• Mitigations:

  • Feature selection (mutual information, wrapper search with cross-validation).

  • Feature weighting or metric learning (e.g. NeighborhoodComponentsAnalysis).

  • Dimensionality reduction (PCA), with the caveat that PCA is unsupervised and may keep high-variance noise.

  • A larger k smooths label noise but does not fix bad features.

Standard metrics like Euclidean distance need every coordinate of both points; a missing value makes the difference term undefined, so the distance is undefined (a NaN propagates). Naive workarounds then make distances incomparable across pairs, which corrupts neighbor rankings.

• Direct failure: Any arithmetic with NaN yields NaN, so sorting by distance breaks; scikit-learn's KNeighborsClassifier raises an error on missing inputs.

• Skipping missing dimensions biases comparisons:

  • A pair compared on 3 features naturally has a smaller sum than a pair compared on 10, so points with more missing values look artificially close.

  • Fix: rescale by the fraction of observed coordinates, as in nan_euclidean_distances: sqrt(total_coords / present_coords × squared distance over present coords).

• Simple imputation distorts geometry: Filling with the mean pulls points toward the center, shrinking distances and creating false neighbors.

• Practical options:

  • Impute (mean/median, KNNImputer, model-based) fit on training data only.

  • Add missing-indicator features if missingness itself is informative.

  • Use a NaN-aware metric (Gower distance for mixed data handles missing values by averaging over available features).

Choose min-max when features have natural, known bounds and few outliers, so mapping them to [0, 1] preserves meaningful relative positions. Prefer z-score when ranges are unbounded or outliers exist, because a single extreme value squashes min-max scaled data into a tiny interval.

• Min-max fits when:

  • Bounds are intrinsic: pixel intensities (0 to 255), percentages, ratings on a fixed scale.

  • You want every feature to have exactly the same range, so maximum per-feature contribution to distance is equal.

  • Mixing with binary/one-hot features that already live in {0, 1}, keeping scales consistent.

• Z-score fits when:

  • Features are unbounded or roughly bell-shaped (e.g. measurements, financial values).

  • Outliers exist: they affect mean and std less than they affect min and max.

• Min-max pitfalls:

  • One outlier compresses all other values, making differences among normal points nearly vanish in the distance.

  • Test points outside the training range fall outside [0, 1].

• With heavy outliers, RobustScaler (median and IQR) is often better than either; when unsure, compare via cross-validation.

One-hot encoding turns a category into binary columns, so two points with different categories differ in exactly two columns: squared Euclidean contribution 2 (distance √2), while matching categories contribute 0. Every pair of categories is therefore equally far apart, which is sensible for nominal data but interacts with scaling and dimensionality.

• Good: no fake ordering: Label encoding (red=0, green=1, blue=2) would make red closer to green than to blue; one-hot avoids this.

• Scale mismatch with numeric features:

  • A category mismatch adds a fixed 2 to the squared distance; against standardized numeric features (typical gaps around 1) it can dominate, and against unscaled ones it can vanish.

  • Every categorical variable contributes the same mismatch penalty regardless of how many levels it has, but many categorical variables collectively can outweigh numeric ones.

• High cardinality:

  • Adds many sparse dimensions, feeding the curse of dimensionality and increasing compute.

  • Similar categories (e.g. neighboring cities) are treated as totally different.

• Remedies:

  • Weight one-hot blocks (e.g. multiply by 1/√2 so a mismatch costs 1) or tune weights by cross-validation.

  • Use mixed-type metrics: Hamming for categoricals, Gower distance for mixed data.

  • Ordinal encoding if categories are truly ordered; embeddings or target encoding for high cardinality.

Feature weighting multiplies each feature's contribution to the distance by a weight, so informative features shape the neighborhood more and irrelevant ones less. This counters KNN's main weakness: treating all features as equally important.

• Weighted distance:

  • d(x, y) = sqrt(Σ w_j (x_j − y_j)²); equivalent to scaling feature j by √w_j before plain Euclidean KNN.

  • Feature selection is the special case of weights in {0, 1}.

• Why it helps:

  • Removes noise from irrelevant features, so neighbors are truly similar in ways that matter for the label.

  • Reduces effective dimensionality, easing the curse of dimensionality.

• How to obtain weights:

  1. Filter scores: mutual information, correlation, or ReliefF (rewards features that separate nearest hits from nearest misses).

  2. Wrapper search: tune weights via cross-validated KNN accuracy.

  3. Metric learning: NeighborhoodComponentsAnalysis or LMNN learn a full linear transform (weights plus feature interactions).

  4. Domain knowledge.

• Caveats:

  • Learned weights can overfit on small data; validate with nested cross-validation.

  • Scale features first, otherwise weights partly just undo unit differences.

KNN imputation fills a missing value by finding the k most similar rows (using the features both rows have observed) and replacing the gap with the average, or distance-weighted average, of those neighbors' values for that feature.

• Steps for a row with a missing feature j:

  1. Compute distances to candidate rows using a NaN-aware metric (scikit-learn uses nan_euclidean, which rescales for missing coordinates).

  2. Keep only candidates that have feature j observed, and take the k nearest.

  3. Fill with their mean (weights="uniform") or inverse-distance weighted mean (weights="distance"); for categoricals use the mode.

• Advantages over mean imputation: Uses relationships between features, so imputed values fit the local structure and preserve variance better.

• Practical concerns:

  • Scale features first, or large-range features dominate neighbor selection.

  • Fit on training data only to avoid leakage; neighbors come from the training set.

  • Costly on large datasets (distance computation per incomplete row) and weak in high dimensions.

  • Assumes data is missing at random; consider adding missing indicators (add_indicator=True).

KNN has no training step: the model is just the stored data. So leaving out one point only means excluding it from its own neighbor search. A single neighbor query over all n points gives the full leave-one-out (LOO) result, with no need to refit n models.

• Why it is cheap:

  • For most models, LOOCV means n separate fits.

  • For KNN, the "model without point i" is the same index minus one point. Querying k + 1 neighbors and dropping the point itself gives exactly the LOO neighborhood.

• All values of k at once:

  • Retrieve the K_max nearest neighbors once, already sorted.

  • The LOO prediction for any k ≤ K_max comes from the first k columns. Tuning k therefore costs about one neighbor search.

• Low-variance error estimate: LOO uses n − 1 training points per prediction, which matters because KNN performance depends on data density.

• Caveats:

  • Exclude the point by index, not by distance 0. Duplicates are legitimate neighbors.

  • Feature scaling fit on the full data leaks slightly into the estimate.

  • The neighbor search itself is still O(n²) brute force, unless you use a tree or ANN index.

With uniform weights, every query's neighborhood is the entire training set. The classifier therefore predicts the overall majority class for every input: a constant model with maximal bias and zero variance.

• Uniform voting (the default):

  • Every query sees the same n votes, so the features are ignored completely.

  • Accuracy equals the majority-class rate, and predicted probabilities equal the class priors.

  • If the classes are perfectly balanced, every prediction is a tie, resolved by the tie-break rule.

• Bias–variance view: this is the extreme underfitting end of the k spectrum, the opposite of k = 1 (which memorizes the training data).

• Distance weighting changes the picture:

  • With weights='distance', all points still vote, but nearby points dominate.

  • The model becomes a global inverse-distance-weighted vote that is not constant and can still be useful.

• Regression analogue: uniform KNN with k = n predicts the global mean of the targets everywhere.

With k = 1, the feature space is partitioned into the Voronoi cells of the training points. Each region takes the label of its single nearest training point. The decision boundary is made of the Voronoi edges that separate points of different classes.

• Geometry:

  • With Euclidean distance, each boundary segment lies on the perpendicular bisector between two opposite-class points.

  • The boundary is therefore piecewise linear: polygonal in 2D, polyhedral in higher dimensions.

  • Other metrics change the cell shapes (e.g. Manhattan distance gives axis-aligned and diagonal pieces).

• Shape in practice:

  • The boundary is highly jagged and irregular.

  • A single noisy or mislabeled point gets its own island of the wrong class.

• Statistical behavior:

  • Training error is zero, since each point is its own nearest neighbor (barring duplicate points with conflicting labels).

  • Variance is high: the boundary shifts significantly when the data changes.

  • Asymptotically (Cover & Hart), the error is at most twice the Bayes error.

• Increasing k smooths the boundary by averaging over several neighbors, so islands caused by noise disappear.

No. A KNN regression prediction is a (weighted) average of the neighbors' targets, which is a convex combination. It can never fall below the minimum or above the maximum target seen in training.

• Why:

  • The prediction is ŷ = Σ wᵢyᵢ, with wᵢ ≥ 0 and Σwᵢ = 1.

  • This holds for both uniform and distance weighting, so ŷ always lies in [min y, max y].

• Behavior outside the training feature range:

  • Far-away queries all share the same edge neighbors, so predictions flatten into a constant plateau.

  • KNN will not continue a trend: on rising house prices or a growing time series, it under-predicts the future.

• Contrast: linear regression extrapolates along its fitted slope. Tree ensembles share KNN's limitation for the same averaging reason.

• Workarounds:

  • Model the trend with a parametric model, then use KNN on the residuals.

  • Predict differences or ratios instead of raw levels (e.g. detrending in time series).

  • Use local linear regression (LOESS-style), which fits a line within each neighborhood.

Logistic regression draws a single linear boundary (a hyperplane in feature space). KNN draws a non-parametric, piecewise-linear boundary that follows the local data, so it can be arbitrarily curved and fragmented. Its flexibility is controlled by k.

• Logistic regression: global and linear:

  • The boundary is where w·x + b = 0 (probability 0.5), which gives one flat hyperplane.

  • Curves only appear if you engineer non-linear features (polynomials, interactions).

  • It is high-bias and low-variance, and the boundary is smooth and stable across resamples.

• KNN: local and non-linear:

  • With k=1, the boundary is built from Voronoi cell edges between differently labeled points. It is jagged and can form islands around single points.

  • It can represent any shape (multiple disjoint regions, curved class borders) without feature engineering.

• Effect of k:

  • Small k gives a very irregular boundary: low bias, high variance, prone to overfitting.

  • Large k gives a smoother boundary. As k → n it collapses toward predicting the majority class everywhere.

• Practical implication: use logistic regression when classes are roughly linearly separable or interpretability matters. Use KNN when the true boundary is complex and data is dense and low-dimensional.

With small k, each prediction depends on one or a few points. A mislabeled training example therefore directly flips predictions in its neighborhood, which increases variance and error.

• Why small k is fragile:

  • With k=1, every noisy label owns a Voronoi cell. Any query landing there inherits the wrong label, creating spurious "islands" in the decision boundary.

  • There is no averaging, so noise is memorized: training error stays at 0 while test error rises.

• Theoretical view: The asymptotic 1-NN error is at most about twice the Bayes error (Cover–Hart). Label noise raises the Bayes error itself, and 1-NN roughly doubles that penalty.

• Mitigations:

  1. Increase k so that isolated wrong labels are outvoted (choose it by cross-validation).

  2. Clean the data with editing methods (e.g., Wilson's Edited Nearest Neighbors), which remove points misclassified by their own neighbors.

  3. Use distance weighting carefully: it helps with far neighbors but still trusts a very close noisy point heavily.

Ties occur when two or more classes receive the same top vote count. They are resolved either by a deterministic rule or by changing the voting so that ties cannot happen.

• Prevent ties:

  • For binary problems, use an odd k. This does not fully work with 3 or more classes.

  • Use distance-weighted voting, since exact equal weight sums are rare.

• Resolve ties when they happen:

  1. Pick the tied class whose neighbor is nearest (or whose tied neighbors have the smallest summed distance).

  2. Shrink k by one and re-vote, repeating until the tie breaks (in the worst case this reaches 1-NN).

  3. Fall back to the class prior: pick the more frequent class overall.

  4. Pick randomly. This is unbiased but non-deterministic, so fix the seed for reproducibility.

• Library behavior:

  • scikit-learn's KNeighborsClassifier takes an argmax, which picks the tied class that appears first in classes_ (an arbitrary, label-order-dependent choice).

  • There is a separate kind of tie: equal neighbor distances at the k-th position. These are resolved by training-data order.

A neighbor at distance zero makes 1/d divide by zero, producing inf or NaN. Either add a small epsilon to the denominator or special-case exact matches.

• Option 1: epsilon smoothing:

  • w = 1 / (d + ε), for example with ε = 1e-9.

  • The exact match gets a huge but finite weight, so it effectively dominates while the math stays well-defined.

• Option 2: exact-match short-circuit:

  • If any neighbor has d == 0, predict using only the zero-distance neighbors (their majority label or mean target) and ignore the rest.

  • scikit-learn's weights="distance" does this: zero-distance points get weight 1 and all others get 0.

• Related concerns:

  • Duplicates with conflicting labels at distance 0 still need tie handling.

  • With 1/d², tiny nonzero distances can overflow, so ε (or capping weights) matters there too.

Under imbalance, the majority class tends to fill every neighborhood and win most votes. Weighting by distance or by class corrects the vote itself. Moving the decision threshold on predict_proba corrects the decision made after voting.

• Distance weighting:

  • A few minority points very close to the query can outweigh many farther majority points.

  • It helps most when minority examples form tight clusters. It does not help if the classes heavily overlap.

• Class weighting:

  • Multiply each neighbor's vote by an inverse class frequency, e.g. n / (C · n_c), so that minority votes count more.

  • You can combine this with distance weights: w_i = class_w[y_i] / d_i.

• Probability thresholds:

  • Instead of argmax (0.5 for binary), predict the minority class when P(minority) ≥ t with t < 0.5, for example 0.2.

  • Tune t on validation data for the target metric (F1, recall at a given precision, cost). This trades precision for recall.

  • Probabilities need a reasonably large k; with small k the probability values are too coarse to threshold usefully.

• Evaluate with imbalance-aware metrics (PR-AUC, F1, balanced accuracy), not accuracy. Alternatives include resampling such as SMOTE.

KNN regression predicts a weighted average of the k nearest neighbors' targets. Each neighbor is weighted by the inverse of its distance, so closer points pull the prediction toward their values.

• Formula:

  • ŷ = Σ w_i·y_i / Σ w_i, with w_i = 1 / d_i^p.

  • Normalizing by Σ w_i keeps ŷ a convex combination, so it always stays within the neighbors' target range.

• The power p:

  • p = 1 is standard. A larger p (e.g. 2) concentrates weight on the very nearest points, producing a more local, higher-variance fit.

  • p = 0 reduces to the plain uniform mean.

• Compared with the uniform average:

  • It is less biased near steep regions and less sensitive to the choice of k.

  • It interpolates training points exactly (zero distance) and needs an ε or exact-match safeguard to do so safely.

• Caveats:

  • Scale features first.

  • Like all KNN, it cannot extrapolate beyond the observed target range.

A KD-tree recursively splits space with axis-aligned hyperplanes, so each node owns a hyper-rectangular region. A query descends to the region that contains it, then backtracks only into regions that could still hold something closer. Most of the data gets pruned this way.

• Construction:

  1. Pick a split dimension: cycle through the axes, or choose the one with the highest spread.

  2. Split at the median along that dimension, which keeps the tree balanced.

  3. Recurse on each half until a node has at most leaf_size points; those points form a leaf bucket.

  4. Build cost is about O(N log N).

• Query (branch and bound):

  1. Descend to the leaf containing the query and compute distances to the points there. This gives the current best (a k-heap).

  2. Backtrack up the tree. At each split, check the distance from the query to the splitting hyperplane (or to the sibling's bounding box).

  3. If that distance is greater than the current k-th best, prune the sibling subtree. Otherwise, search it.

• Performance:

  • Queries take roughly O(log N) in low dimensions (D up to about 10–20).

  • In high D the query ball crosses most splitting planes, pruning fails, and the search approaches O(N), often slower than brute force. A rule of thumb is that you need N ≫ 2^D.

• In practice:

  • scikit-learn exposes it as KNeighborsClassifier(algorithm='kd_tree').

  • Ball trees (hypersphere regions) cope better with non-axis-aligned structure and non-Euclidean metrics.

  • For high-dimensional data, use approximate methods (HNSW, IVF).

Exact search guarantees the true k nearest neighbors but costs roughly linear time per query in high dimensions; approximate nearest neighbor (ANN) search gives up that guarantee (some true neighbors may be missed) in exchange for sub-linear query time, often orders of magnitude faster at large scale.

• Exact search:

  • Brute force is O(n·d) per query; trees (KD/ball) help only in low dimensions and degrade toward a linear scan as d grows.

  • Results are deterministic and correct: good for small data, offline evaluation, or when errors are costly.

• Approximate search:

  • Families: hashing (LSH), graphs (HNSW), quantization/partitioning (IVF, PQ in FAISS), trees/forests (Annoy).

  • Measured by recall@k vs. queries per second; knobs like nprobe or efSearch trade speed for accuracy.

• Hidden costs of ANN:

  • Index build time and extra memory (graph links, codebooks); compression (PQ) lowers memory but also accuracy.

  • Updates/deletes can be awkward, and parameters need tuning per dataset.

• Rule of thumb: exact when n is small or correctness is critical; ANN for millions+ of high-dimensional vectors under latency budgets (e.g. retrieval, recommendations), where slightly lower recall is acceptable.

Prefer a ball tree when data is moderately high-dimensional, clustered or on a low-dimensional manifold, or when you need a non-Euclidean metric; KD-trees win in low dimensions (roughly d < 20) with Minkowski distances, where they are cheaper to build and query.

• How they partition:

  • KD-tree: axis-aligned splits on one coordinate at a time, so the cells are hyper-rectangles.

  • Ball tree: nested hyperspheres (centroid + radius) that fit the data's actual shape rather than the coordinate axes.

• Why ball trees cope better as d grows:

  • Pruning uses the triangle inequality: skip a ball if distance to its center minus its radius exceeds the current k-th best distance.

  • Tight spheres around clustered data prune well even when axis-aligned boxes become loose.

• Metric flexibility: Ball trees work with any true metric (e.g. haversine); KD-trees need axis-decomposable metrics.

• Costs:

  • Ball trees are slower to build, and per-node distance checks are more expensive.

  • In very high dimensions with no structure, both degrade; use brute force or ANN instead.

• In scikit-learn, algorithm='auto' picks among kd_tree, ball_tree and brute using heuristics.

KNN is a lazy learner: the "model" is the entire training set (plus any index). Memory therefore grows with n × d, and every prediction needs fast access to all of it, which conflicts with tight RAM limits on edge devices, small containers or serverless functions.

• Storage scales with data, not model complexity: Example: 10M × 768 float32 vectors is about 30 GB, while a parametric model might be a few MB.

• Index overhead: KD/ball trees and ANN graphs (HNSW links) add memory on top of the raw vectors.

• Query-time cost:

  • Brute-force distance matrices for batches add temporary memory spikes.

  • If data spills to disk, latency explodes because access is random.

• Operational issues:

  • Every replica must hold the full dataset, and adding data enlarges the model.

  • Storing raw training rows can also be a privacy concern.

• Mitigations:

  • Dimensionality reduction, float16 or product quantization (FAISS PQ).

  • Prototype selection or condensing (condensed NN, cluster centroids).

  • Memory-mapped or sharded indexes, or a dedicated vector database service.

  • Or switch to a compact parametric model.

Gower's distance computes a separate dissimilarity for each feature, each scaled to [0, 1] with a rule suited to that feature's type, then takes a weighted average. This puts numeric and categorical features on a common scale, so a single distance exists for KNN to rank.

• Per-feature dissimilarity dk:

  • Numeric: |x − y| / rangek, so dividing by the range removes unit effects.

  • Categorical: 0 if the categories are equal, 1 otherwise.

  • Ordinal: convert to ranks, then treat as numeric divided by the rank range.

  • Asymmetric binary: handled in a Jaccard-like way, where 0–0 pairs are excluded.

• Combination: d = Σ wkδkdk / Σ wkδk:

  • δk = 0 when feature k is missing for either point, so missing values are handled natively.

  • The weights wk let you control each feature's influence; by default all are equal.

• Using it with KNN:

  • Compute the distance matrix yourself (for example with the gower package), then pass metric='precomputed' to scikit-learn.

  • Cost: the matrix needs O(n²) memory and time, and standard KD-trees do not apply, so it is best for small to medium datasets.

• Caveats:

  • Range scaling is sensitive to outliers; one extreme value compresses all other differences on that feature.

  • A categorical mismatch always costs the full 1, which can dominate numeric differences.

Use Mahalanobis distance when features have different variances or are correlated. It measures distance in units of the data's covariance, so redundant or high-variance directions do not dominate the neighbor search the way they do with Euclidean distance.

• Definition: d(x, y) = √((x − y)T S−1 (x − y)), where S is the covariance matrix.:

  • It is equivalent to Euclidean distance after whitening the data (z = S−1/2x).

  • If S is diagonal, it reduces to Euclidean distance on standardized features.

• When it helps:

  • Correlated features, such as height and weight, which would otherwise double-count the same information.

  • Elliptical clusters, where Euclidean distance's spherical neighborhoods misjudge closeness.

• Caveats:

  • S must be invertible. When features outnumber samples, or features are collinear, use shrinkage (for example Ledoit-Wolf) or a pseudo-inverse.

  • A single global S assumes the same shape everywhere, but local structure may differ.

  • Estimate S on the training data only, to avoid leakage.

• Generalization: metric learning methods (NCA, LMNN) learn the matrix M in (x − y)TM(x − y) to optimize KNN accuracy, rather than using S−1.

Metric trees (ball trees, VP-trees, cover trees) skip whole regions using lower bounds on distance, and those bounds are derived from the triangle inequality. If the distance violates it, the bounds can be wrong, so the tree may prune a region that holds a true nearest neighbor and silently return incorrect results.

• The pruning bound:

  • For any point x in a ball with center c and radius r, the triangle inequality guarantees d(q, x) ≥ d(q, c) − d(c, x) ≥ d(q, c) − r.

  • If d(q, c) − r exceeds the current k-th best distance, every point in the ball can be skipped without computing its distance.

  • VP-trees use the related bound |d(q, v) − d(v, x)| relative to a vantage point v.

• What breaks without it:

  • The bound can overestimate the true minimum distance, so pruning discards valid candidates.

  • The result is a correctness bug, not just a slowdown, and it produces no error message.

• Common non-metrics:

  • Squared Euclidean, cosine distance (1 − cos), and Minkowski with p < 1.

  • Fix for cosine: L2-normalize the vectors and use Euclidean distance, which is monotone in cosine. Alternatively use angular distance (arccos), which is a true metric.

• Other required axioms: non-negativity, identity (d(x, y) = 0 exactly when x = y), and symmetry.

• KD-trees differ: they bound distance using coordinate splits, so they support Minkowski-type metrics rather than arbitrary ones.

• In scikit-learn, check BallTree.valid_metrics to see what the tree supports; otherwise fall back to algorithm='brute'.

Cyclical features need a distance that wraps around, so that hour 23 is close to hour 0. Either encode each feature as (sin, cos) on the unit circle and use Euclidean distance, or compute the circular distance min(|a − b|, P − |a − b|) directly, where P is the period.

• Why plain differences fail: |23 − 0| = 23 makes midnight neighbors look maximally far apart.

• Sin/cos encoding:

  • Map each value to θ = 2πv/P, then to the point (sin θ, cos θ).

  • Euclidean distance between these points is the chord length, which increases monotonically with the angular gap. Neighbor rankings therefore match true circular distance.

  • It works with standard KNN, KD-trees and ball trees without a custom metric.

• Direct circular (arc) distance:

  • min(|a − b|, P − |a − b|) is a valid metric on the circle.

  • It needs a custom callable, which is slower in scikit-learn, or a precomputed distance matrix.

• Practical notes:

  • Scale the encoded pair consistently with the other features: chord distance lies in [0, 2], and one cyclic feature becomes two columns.

  • Latitude and longitude are angles on a sphere, so use haversine distance (metric='haversine', which expects radians).

Condensed Nearest Neighbor (Hart, 1968) aims to find a much smaller subset of the training set that still classifies every original training point correctly with 1-NN (a "consistent subset"). This cuts memory and prediction time while approximately preserving the decision boundary.

• Algorithm:

  1. Start the store with one (or one per class) training point.

  2. Classify each remaining point with 1-NN against the store; if misclassified, add it to the store.

  3. Repeat passes until a full pass adds nothing.

• What gets kept: Mostly points near class boundaries; interior points are redundant because nearby same-class prototypes already classify them.

• Limitations:

  • Result depends on processing order and is not guaranteed minimal.

  • Sensitive to noise: mislabeled points are always misclassified, so they get retained; commonly preceded by Wilson's Edited Nearest Neighbor to remove noise.

  • Can slightly lower accuracy versus full KNN, especially with k > 1.

• Also used as an undersampling method for imbalanced data (CondensedNearestNeighbour in imbalanced-learn), removing redundant majority-class samples.