2.3. K-Nearest Neighbors

K-Nearest Neighbors (KNN) does almost no work at training time. Instead, it does most of its work at prediction time. RustyML implements it as KNN<T>, a generic classifier over any label type T that supports hashing and equality comparison.

The API resembles scikit-learn’s KNeighborsClassifier, with a few RustyML-specific differences. The label type is generic, not limited to integers. The distance metric is one DistanceCalculationMetric enum, shared with DBSCAN and the clustering metrics. Tie-breaking is deterministic, based on the order labels first appear. A separate entry point runs prediction in parallel.

2.3.1. Lazy Learning: Where the Cost Lives

KNN is the purest lazy learner in the crate. Its fit method does almost no learning. It validates the input, copies the training feature matrix, and encodes the labels into compact usize indices, which makes voting a cheap integer operation. Unlike logistic regression or a decision tree, KNN does not compress the training data into weights or a tree of splits. predict does all the real work.

This deferral has a real cost. There is no trained model to consult, so classifying one query means measuring its distance to every training row and keeping the k smallest. On the brute-force path, the distance stage costs O(n_train * n_test * d) for n_test queries against n_train training rows in d dimensions. Each query also needs an O(n_train) partial selection step to pull out the k nearest values. This step uses Quickselect through select_nth_unstable, not a full O(n_train log n_train) sort. Memory use is O(n_train * d), because the entire training set stays in memory for the life of the model. The training set is the model. You accept this tradeoff to get a non-parametric classifier with no training phase and no assumptions about the shape of the decision boundary.

Two consequences follow. First, prediction latency scales with the size of the training set. KNN that runs fast on a few thousand rows can become the bottleneck on a few hundred thousand. Second, geometry decides accuracy at query time. This is why the distance metric and feature scaling, covered later in this page, matter more here than in almost any other model.

2.3.2. Constructing a Classifier

The constructor takes only k. Every other setting has a default value. You set these values through chained builder methods:

// Core surface (from src/machine_learning/neighbors/knn.rs)
pub fn new(k: usize) -> Result<Self, Error>;                       // Err if k == 0
pub fn with_weighting_strategy(self, s: WeightingStrategy) -> Self;
pub fn with_metric(self, m: DistanceCalculationMetric) -> Result<Self, Error>; // validates Minkowski p

pub fn fit<S1, S2>(&mut self, x: &ArrayBase<S1, Ix2>, y: &ArrayBase<S2, Ix1>)
    -> Result<&mut Self, Error>;
pub fn predict<S>(&self, x: &ArrayBase<S, Ix2>) -> Result<Array1<T>, Error>;
pub fn predict_parallel<S>(&self, x: &ArrayBase<S, Ix2>) -> Result<Array1<T>, Error>; // T: Sync + Send
pub fn fit_predict<S1, S2>(&mut self, x: &..., y: &...) -> Result<Array1<T>, Error>;

new returns Error::InvalidParameter when k == 0. This is the one failure every caller can hit during construction. with_metric can also fail, because it validates the Minkowski order, covered in the next section. with_weighting_strategy cannot fail and returns Self directly. A fully specified builder chain therefore ends with ? or .unwrap() on the metric call. This matches the order used throughout the test suite.

The two enums that parameterize the model:

KNN::<T>::default() gives you k = 5, Uniform weighting, and Euclidean distance. These are the same defaults you get from calling new(5) and changing nothing else. Read the stored configuration back with get_k, get_weighting_strategy, get_metric, and get_x_train. get_x_train returns Option<&Array2<f64>>, which is None before you call fit.

The label type T is fully generic. Any type that is Clone + Hash + Eq works, so integer class codes, String labels, or your own enum all work. fit encodes the labels it sees into indices, in first-appearance order, and stores the reverse map. predict decodes the indices back to the original T. Feed in Array1<String>, and you get Array1<String> back. KNN is a classifier only. The crate has no KNN regressor. For neighbor-averaged regression, build it yourself on the distance primitives in Chapter 6.1.

Here is a full example. It uses both the sequential and parallel entry points:

use ndarray::array;
use rustyml::machine_learning::{DistanceCalculationMetric, KNN, WeightingStrategy};

fn main() {
    let x_train = array![
        [1.0, 2.0],
        [2.0, 3.0],
        [3.0, 4.0],
        [6.0, 6.0],
        [7.0, 7.0],
        [8.0, 8.0],
    ];
    let y_train = array![0, 0, 0, 1, 1, 1];

    let mut knn = KNN::new(3)
        .unwrap()
        .with_weighting_strategy(WeightingStrategy::Uniform)
        .with_metric(DistanceCalculationMetric::Euclidean)
        .unwrap();

    knn.fit(&x_train, &y_train).unwrap();

    let x_test = array![[1.5, 2.5], [7.5, 7.0]];
    let seq = knn.predict(&x_test).unwrap();
    let par = knn.predict_parallel(&x_test).unwrap();

    assert_eq!(seq, par); // deterministic: both paths agree exactly
    println!("k = {}", knn.get_k());
    println!("predictions: {:?}", seq);
}

fit checks for the mistakes that would otherwise cause a panic at predict time. It returns Error::EmptyInput for a zero-row x. It returns Error::NonFinite if x holds a NaN or an infinity. It returns Error::DimensionMismatch when y.len() differs from x.nrows(). It returns Error::InvalidInput when the training set has fewer samples than k. For example, you cannot ask for 5 neighbors from 3 points. predict and predict_parallel add Error::NotFitted when you call them before fit. They also return EmptyInput, DimensionMismatch for a query with the wrong feature count, and NonFinite for a query matrix with NaN or infinite values. See Error Handling for the full Error enum.

fit_predict fits the model, then predicts on the same training matrix. With k = 1, it returns the training labels unchanged. Each point’s nearest neighbor is itself, at distance zero. This makes fit_predict useful as a sanity check, but useless as an accuracy estimate. For a real estimate of generalization, hold out data with Train-Test Split and score it with the classification metrics.

2.3.3. Distance Metrics and the Minkowski Order

The metric decides what counts as nearest. RustyML exposes 3 metrics through one enum, shared across the library. Euclidean (L2) is the straight-line default. Manhattan (L1) sums the absolute differences between coordinates. Use Manhattan when features are independent axes measured in different units, or when you want robustness against a single outlying coordinate. Minkowski(p) generalizes both metrics. p = 1 reduces to Manhattan, and p = 2 reduces to Euclidean, exactly. The test suite asserts these equalities on shared data. Intermediate or larger values of p interpolate and extrapolate the shape of the unit ball.

with_metric validates the Minkowski order. It returns Error::InvalidParameter if p < 1 or p is not finite. This is a real constraint, not a style choice. Orders below 1 violate the triangle inequality, so the result is no longer a valid metric. Such an order would also break the pruning logic of the kd-tree index, described later in this page. The bare distance function minkowski_distance_row panics on p < 1. Routing through with_metric turns that panic into a recoverable Err you can handle. Minkowski(2.0) is legal, and numerically identical to Euclidean. Prefer the Euclidean variant when you want L2. Euclidean enables a matrix-multiply fast path, covered in section 2.3.7, that the general Minkowski code does not have.

use ndarray::array;
use rustyml::machine_learning::{DistanceCalculationMetric, KNN, WeightingStrategy};

fn main() {
    let x_train = array![[3.0, 0.0], [0.0, 4.0]];
    let y_train = array![0, 1];

    let mut knn = KNN::new(1)
        .unwrap()
        .with_weighting_strategy(WeightingStrategy::Uniform)
        .with_metric(DistanceCalculationMetric::Minkowski(3.0))
        .unwrap();
    knn.fit(&x_train, &y_train).unwrap();

    // Under L3: dist((0,3),(3,0)) = 54^(1/3) ~= 3.78 > dist((0,3),(0,4)) = 1
    let x_test = array![[0.0, 3.0]];
    println!("{:?}", knn.predict(&x_test).unwrap()); // nearest is (0,4) -> class 1
}

Chapter 6.1, Distance Metrics covers the metric abstraction in more depth, including the comparable-distance trick that lets the spatial index skip the final root.

2.3.4. Weighting Strategies and Tie-Breaking

After KNN finds the k neighbors, WeightingStrategy decides how their labels combine into one prediction.

Uniform is a plain majority vote. Each of the k neighbors contributes one vote to its class, and the class with the most votes wins. Distance weights each neighbor by 1.0 / distance, so a neighbor twice as close counts twice as much. Use distance weighting when k is large enough that the neighbor set reaches genuinely dissimilar points. The far points still vote, but their influence decays. Distance weighting also lowers the sensitivity of the result to the exact value of k.

Distance weighting has one edge case that the implementation handles explicitly. A query that coincides with a training point sits at distance zero, and 1.0 / 0.0 is infinity. To avoid that, the code checks for exact matches first. If any of the k neighbors sits at distance exactly 0.0, only those exact-match neighbors vote, by count, and KNN ignores the rest. This makes an exact hit behave like a lookup, which is almost always what you want.

use ndarray::array;
use rustyml::machine_learning::{DistanceCalculationMetric, KNN, WeightingStrategy};

fn main() {
    let x_train = array![[0.0, 0.0], [10.0, 0.0]];
    let y_train = array![0, 1];

    let mut knn = KNN::new(2)
        .unwrap()
        .with_weighting_strategy(WeightingStrategy::Distance)
        .with_metric(DistanceCalculationMetric::Euclidean)
        .unwrap();
    knn.fit(&x_train, &y_train).unwrap();

    // Both points are always in the k=2 set. The nearer one wins the weighted vote.
    let x_test = array![[1.0, 0.0], [9.0, 0.0]];
    println!("weighted: {:?}", knn.predict(&x_test).unwrap()); // [0, 1]

    // Exact match short-circuits the 1/0 problem: it votes by count, not weight.
    let x_exact = array![[0.0, 0.0]];
    println!("exact:    {:?}", knn.predict(&x_exact).unwrap()); // [0]
}

RustyML breaks ties with a deliberate, documented rule, not an arbitrary one. A tie happens when 2 classes have equal vote counts under Uniform, or equal summed weight under Distance. The winner is the class with the smallest encoded index. That index is not the smallest label value. It is the order in which fit first saw each label. For example, if your training targets show label 7 before label 3, 7 encodes to index 0 and wins ties against 3. Ties are broken deterministically and reproducibly, but the resolution depends on the order of the training rows. Reordering your data can flip a tied prediction. This same determinism is what lets predict and predict_parallel guarantee identical results.

2.3.5. Choosing k

k is the setting that changes behavior the most. It acts as a direct bias-variance dial. A small k, down to the extreme of k = 1, gives a low-bias, high-variance classifier. Its decision boundary hugs the data and follows every wrinkle, including mislabeled points and noise. A large k averages over a wider neighborhood. This lowers variance but raises bias. Push k far enough, and the model drifts toward always predicting the most common class overall. It then starts to erase small but real minority regions. A common starting point is a k near the square root of the training-set size. Tune it against a validation split. There is no substitute for measuring the result.

The classic advice to use an odd k for binary classification is about ties. RustyML’s tie-break is deterministic, so an even k never causes an error. A 50/50 split resolves by first-encounter order, but that resolution can feel arbitrary, and it depends on the order of your data. An odd k keeps binary votes from ever landing on a tie. Distance weighting also reduces this problem, because exact ties in summed real-valued weights are unlikely. Remember also the hard floor from section 2.3.2. fit rejects any k greater than the number of training samples.

This example makes the variance concrete. It places a single mislabeled point inside the class-0 region, then places a query right next to it. At k = 1, the noise wins. At k = 3 and k = 5, the surrounding genuine class-0 points outvote it:

use ndarray::array;
use rustyml::machine_learning::{DistanceCalculationMetric, KNN, WeightingStrategy};

fn main() {
    // Two clean clusters plus one mislabeled point at (2.5, 0): it sits inside
    // the class-0 region but carries the class-1 label.
    let x_train = array![
        [0.0, 0.0], [1.0, 0.0], [2.0, 0.0], [3.0, 0.0],     // class 0
        [10.0, 0.0], [11.0, 0.0], [12.0, 0.0], [13.0, 0.0], // class 1
        [2.5, 0.0],                                         // noise, class 1
    ];
    let y_train = array![0, 0, 0, 0, 1, 1, 1, 1, 1];

    let x_test = array![[2.4, 0.0]]; // right next to the noisy point

    for k in [1usize, 3, 5] {
        let mut knn = KNN::new(k)
            .unwrap()
            .with_weighting_strategy(WeightingStrategy::Uniform)
            .with_metric(DistanceCalculationMetric::Euclidean)
            .unwrap();
        knn.fit(&x_train, &y_train).unwrap();
        let pred = knn.predict(&x_test).unwrap();
        println!("k = {k}: prediction = {}", pred[0]);
    }
}

The prediction flips from the noisy label to the correct one as k grows:

k = 1: prediction = 1
k = 3: prediction = 0
k = 5: prediction = 0

This single-point sensitivity at k = 1 is the high-variance failure mode. Increasing k trades it for a smoother, more biased boundary.

2.3.6. Feature Scaling Is Not Optional

This mistake causes more failures than any other, so it gets its own section. KNN ranks neighbors by raw distance, and every metric here sums per-coordinate differences. Suppose one feature ranges over the thousands and another ranges over [0, 1]. The large-range feature then dominates the distance, and the small-range feature becomes invisible, regardless of which one actually carries the label. Unlike a linear model, which can learn a small coefficient for a large-scale feature, KNN has no coefficients to compensate. You must scale the features yourself before you call fit.

The example below encodes the label entirely in a small-range column. A large-range column carries no information about the label. On raw features, the large column decides the nearest neighbor, and the prediction is wrong. Standardizing with the training set’s per-column mean and standard deviation, applied to both train and query data, puts the informative column on equal footing. The prediction is then right:

use ndarray::{array, Axis};
use rustyml::machine_learning::KNN;

fn main() {
    // Column 0 spans the ~1000s and is uninformative. Column 1 in {0, 10} carries the label.
    let x_train = array![
        [1000.0, 0.0],  // class 0
        [3000.0, 0.0],  // class 0
        [1050.0, 10.0], // class 1
        [3050.0, 10.0], // class 1
    ];
    let y_train = array![0, 0, 1, 1];

    // Column 1 = 9.0 says class 1. Column 0 = 1010.0 is closest to a class-0 row.
    let x_test = array![[1010.0, 9.0]];

    let mut raw = KNN::new(1).unwrap();
    raw.fit(&x_train, &y_train).unwrap();
    let raw_pred = raw.predict(&x_test).unwrap();

    // Standardize with statistics computed on the TRAINING set, applied to both.
    let mean = x_train.mean_axis(Axis(0)).unwrap();
    let std = x_train.std_axis(Axis(0), 0.0);
    let x_train_s = (&x_train - &mean) / &std;
    let x_test_s = (&x_test - &mean) / &std;

    let mut scaled = KNN::new(1).unwrap();
    scaled.fit(&x_train_s, &y_train).unwrap();
    let scaled_pred = scaled.predict(&x_test_s).unwrap();

    println!("raw features:  {:?}", raw_pred);    // dominated by column 0 -> [0]
    println!("standardized:  {:?}", scaled_pred); // respects column 1  -> [1]
}

The example scales the data by hand, to stay self-contained. It still follows correct statistical practice. The mean and standard deviation come from the training data only, then apply to the query. The code never re-estimates them on the test set. In a real pipeline, use the crate’s standardize helper, or normalize, instead of writing this by hand. Fit the transform on the training set, then apply that same transform to new data. Fitting the transform again on the test set leaks information. Standardization to zero mean and unit variance is the usual choice. Min-max normalization is the alternative when you need features bounded to a fixed range.

2.3.7. Sequential vs Parallel Prediction, the kd-tree, and the Euclidean Fast Path

RustyML gives you 2 prediction entry points. predict runs sequentially and works for any label type. predict_parallel spreads the per-query work across a Rayon pool. Use predict_parallel for large query batches. It requires T: Sync + Send. Both methods build any shared index once, up front, on a single thread, before the queries run. predict_parallel then parallelizes over the test rows. The tie-break is deterministic, so the two paths return bit-identical label arrays. The test suite checks this across Uniform, Distance, and large-k configurations. You can develop with predict, then switch to predict_parallel for throughput, without changing a single result.

Under the hood, the search takes one of 2 routes. In low dimensions, at most 8 features, predict builds a kd-tree over the training data on first use, and caches it. The kd-tree gives average-case neighbor lookups that beat scanning every row. Above 8 features, the tree stops pruning effectively. This is the curse of dimensionality, where nearly every point becomes roughly equidistant from every other. Above that limit, the code falls back to a brute-force scan, and the full O(n_train * n_test * d) cost from section 2.3.1 applies. This 8-feature ceiling comes from calibration on one data shape, not from a universal law. Clustered data and different dataset sizes shift the actual crossover point. It remains the fixed threshold that the current implementation uses.

The brute-force Euclidean case gets a dedicated optimization. Squared Euclidean distance expands to ||x||^2 + ||t||^2 - 2 * x . t. The only per-pair term left is the dot product x . t, which is a matrix multiply. RustyML precomputes the training rows’ squared norms once and shares them across every query. It then computes the cross terms through the gemmkit matrix-multiply backend. This backend blocks the work to keep it cache-resident on large training sets. It also switches between a per-row GEMV swarm and a tiled GEMM, depending on whether the training matrix still fits in the shared L3 cache. Manhattan and Minkowski have no such algebraic shortcut. They fall back to a plain per-pair metric scan. This is another reason to prefer the Euclidean variant when you want L2. The kd-tree rebuilds lazily, and KNN drops it whenever you call fit again. A refitted model therefore never serves stale neighbors. See Performance Tuning and Parallelism for more on the parallelism gates and tuning.

2.3.8. Persistence

KNN<T> serializes with save_to_path and load_from_path when T is Serialize + Deserialize, as i32 and String are. Persistence writes the compact postcard binary format, regardless of the file extension you choose. It stores exactly what defines the model: k, the weighting strategy, the metric, the training matrix, and the label encoding. The kd-tree is not serialized. It is marked #[serde(skip)] and rebuilds lazily on the loaded model’s first predict call. A reloaded classifier therefore produces predictions identical to the original, with no extra work from you.

use ndarray::array;
use rustyml::machine_learning::{DistanceCalculationMetric, KNN};

fn main() {
    let x_train = array![
        [0.0, 0.0], [1.0, 0.0], [2.0, 0.0],
        [10.0, 0.0], [11.0, 0.0], [12.0, 0.0],
    ];
    let y_train = array![0, 0, 0, 1, 1, 1];

    let mut knn = KNN::new(3)
        .unwrap()
        .with_metric(DistanceCalculationMetric::Manhattan)
        .unwrap();
    knn.fit(&x_train, &y_train).unwrap();

    let path = "knn_model.bin";
    knn.save_to_path(path).unwrap();

    // Rebuilds its kd-tree lazily on first predict. k, metric, and labels are restored.
    let loaded = KNN::<i32>::load_from_path(path).unwrap();

    let x_test = array![[0.5, 0.0], [11.5, 0.0]];
    assert_eq!(
        knn.predict(&x_test).unwrap(),
        loaded.predict(&x_test).unwrap()
    );
    println!("round-trip predictions match");

    std::fs::remove_file(path).unwrap();
}

A KNN model carries its entire training set, so the serialized file grows with n_train * d. Persistence here saves your data plus a little metadata, not a handful of learned parameters. If model size matters to you, that alone is a reason to consider a parametric classifier instead. Model Persistence in Depth covers the format and its guarantees.

KNN<T> also implements the crate’s shared Fit and Predict traits. These traits are re-exported from machine_learning, and defined in crate::traits. Fit takes the training data as an (x, y) tuple. You will normally call the inherent fit, predict, and predict_parallel methods shown throughout this page. The traits exist so that generic code can treat every estimator the same way.