API Reference / algorithms / neighbors /

knn.py

K-Nearest Neighbors classifier implementation.

Classes

KNearestNeighborsClassifier

class algorithms.neighbors.knn.KNearestNeighborsClassifier(Classifier)

K-Nearest Neighbors classifier using instance-based lazy learning.

KNearestNeighborsClassifier classifies instances based on similarity to training examples. For each test instance, it finds the k nearest training instances and predicts the majority class among them. The algorithm is "lazy" because it defers computation until prediction time, storing all training instances rather than building an explicit model.
Constructor 
__init__(
    self,
    k: int = 1,
    distance_weighting: str = 'uniform',
    search_algorithm: str = 'brute',
    auto_select_k: bool = False,
    leaf_size: int = 30,
)

Overview

The algorithm operates in the following steps:

  1. Store all training instances during fit() (no model is built).
  2. For a new query point, compute the distance to every training instance
(or use an accelerated search structure such as a KD-tree or Ball Tree).
  1. Select the k closest training instances.
  2. Assign weights to the neighbors according to the chosen weighting scheme.
  3. Predict the class with the highest aggregated weight among the neighbors.

Theory

Given a query point x, the predicted class is:

\hat{y} = \arg\max_{c \in C} \sum_{i \in N_k(x)} w_i \cdot \mathbb{1}(y_i = c)
where:
  • N_k(x): The set of k nearest neighbors of x
  • w_i: Weight assigned to neighbor i
  • C: The set of all classes
Weighting schemes:
  • Uniform: w_i = 1
  • Inverse distance: w_i = 1 / d(x, x_i)
  • Similarity: w_i = 1 / (1 + d(x, x_i))
The default distance metric is Euclidean distance:
d(x, x_i) = \sqrt{\sum_{j=1}^{m} (x_j - x_{i,j})^2}

Parameters

k
int = 1
Number of neighbors to use.
distance_weighting
{'uniform', 'distance', 'distance_squared', 'similarity'} = 'uniform'

How to weight neighbors:

  • •'uniform': All neighbors weighted equally.
  • •'distance': Weight by inverse of distance :math:`1/d`.
  • •'distance_squared': Weight by inverse squared distance :math:`1/d^2`.
  • •'similarity': Weight by similarity :math:`1/(1+d)`.
search_algorithm
{'brute', 'kd_tree', 'ball_tree'} = 'brute'

Algorithm for finding neighbors:

  • •'brute': Brute force search.
  • •'kd_tree': KD-tree for faster search in low dimensions.
  • •'ball_tree': Ball tree for higher-dimensional or non-Euclidean data.
auto_select_k
bool = False
If True, use leave-one-out cross-validation to automatically select the optimal :math:`k`.
leaf_size
int = 30
Leaf size for tree-based search algorithms (KD-tree and Ball Tree).

Attributes

X_train_
np.ndarray
Training features stored for lazy learning.
y_train_
np.ndarray
Training labels stored for lazy learning.
classes_
np.ndarray
Unique class labels discovered during fit.
search_
NearestNeighborSearch
The search structure instance used for neighbor queries.

Notes

Complexity:

  • Training: O(1) (instances are simply stored)
  • Prediction (brute force): O(n \cdot m) per query where n = number of training samples, m = number of features
  • Prediction (KD-tree, average case): O(m \cdot \log n) per query
  • Space: O(n \cdot m) for storing all training instances
When to use KNearestNeighborsClassifier:
  • Small to medium datasets where training time must be near-zero
  • Decision boundaries are highly irregular or non-linear
  • New training instances arrive incrementally (online learning)
  • When an interpretable, non-parametric baseline is needed
  • Low-dimensional feature spaces (especially with tree-based search)

References

Aha1991
Aha, D.W., Kibler, D. and Albert, M.K. (1991). Instance-Based Learning Algorithms. Machine Learning, 6, pp. 37-66. DOI: 10.1007/BF00153759
Cover1967
Cover, T.M. and Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), pp. 21-27. DOI: 10.1109/TIT.1967.1053964
Dudani1976
Dudani, S.A. (1976). The Distance-Weighted k-Nearest-Neighbor Rule. IEEE Transactions on Systems, Man, and Cybernetics, SMC-6(4), pp. 325-327. DOI: 10.1109/TSMC.1976.5408784

See Also

Basic classification with distance-weighted voting:

python 
>>> from tuiml.algorithms.neighbors import KNearestNeighborsClassifier
>>> from tuiml.datasets import load_iris
>>> X, y = load_iris()
>>> clf = KNearestNeighborsClassifier(k=3, distance_weighting='distance')
>>> clf.fit(X, y)
KNearestNeighborsClassifier(k=3, n_train=150, weighting='distance')
>>> clf.predict(X[:1])
array([0])

Methods

get_parameter_schema (cls) -> Dict[str, Dict[str, Any]]

Return parameter schema.

get_capabilities (cls) -> List[str]

Return classifier capabilities.

get_complexity (cls) -> str

Return time/space complexity.

get_references (cls) -> List[str]

Return academic references.

fit (self, X: np.ndarray, y: np.ndarray) -> 'KNearestNeighborsClassifier'

Fit the KNearestNeighborsClassifier classifier by storing the training data.

Parameters
X
np.ndarray of shape (n_samples, n_features)
Training features.
y
np.ndarray of shape (n_samples,)
Target labels.
Returns
self
KNearestNeighborsClassifier
Returns the instance itself.
partial_fit (self, X: np.ndarray, y: np.ndarray, classes: Optional[np.ndarray]=None) -> 'KNearestNeighborsClassifier'

Incrementally add training samples to the classifier.

Parameters
X
np.ndarray of shape (n_samples, n_features)
Incremental training features.
y
np.ndarray of shape (n_samples,)
Incremental target labels.
classes
np.ndarray of shape (n_classes,) = None
List of all classes expected. Can be omitted if model is already fitted.
Returns
self
KNearestNeighborsClassifier
Returns the instance itself.
predict (self, X: np.ndarray) -> np.ndarray

Predict class labels for the provided samples.

Parameters
X
np.ndarray of shape (n_samples, n_features)
The samples to predict.
Returns
y_pred
np.ndarray of shape (n_samples,)
The predicted class labels.
predict_proba (self, X: np.ndarray) -> np.ndarray

Predict class probabilities for the provided samples.

Parameters
X
np.ndarray of shape (n_samples, n_features)
The samples to predict.
Returns
probabilities
np.ndarray of shape (n_samples, n_classes)
The class probabilities.
update (self, X: np.ndarray, y: np.ndarray) -> 'KNearestNeighborsClassifier'

Add new instances to the training set (online learning).

Parameters
X
np.ndarray
New training features.
y
np.ndarray
New training labels.
Returns
self
KNearestNeighborsClassifier
Returns the instance with updated training data.
__repr__ (self) -> str

String representation.

KNearestNeighborsRegressor

class algorithms.neighbors.knn.KNearestNeighborsRegressor(Regressor)

K-Nearest Neighbors regressor using instance-based lazy learning.

KNearestNeighborsRegressor predicts continuous target values based on similarity to training examples. For each test instance, it finds the k nearest training instances and predicts the weighted average of their target values. The algorithm is "lazy" because it defers computation until prediction time, storing all training instances rather than building an explicit model.
Constructor 
__init__(
    self,
    k: int = 1,
    distance_weighting: str = 'uniform',
    search_algorithm: str = 'brute',
    auto_select_k: bool = False,
    leaf_size: int = 30,
)

Overview

The algorithm operates in the following steps:

  1. Store all training instances during fit() (no model is built).
  2. For a new query point, compute the distance to every training instance
(or use an accelerated search structure such as a KD-tree or Ball Tree).
  1. Select the k closest training instances.
  2. Assign weights to the neighbors according to the chosen weighting scheme.
  3. Predict the weighted average of the neighbor target values.

Theory

Given a query point x, the predicted value is:

\hat{y} = \frac{\sum_{i \in N_k(x)} w_i \cdot y_i}{\sum_{i \in N_k(x)} w_i}
where:
  • N_k(x) -- The set of k nearest neighbors of x
  • w_i -- Weight assigned to neighbor i
  • y_i -- Target value of neighbor i
Weighting schemes:
  • Uniform: w_i = 1
  • Inverse distance: w_i = 1 / d(x, x_i)
  • Similarity: w_i = 1 / (1 + d(x, x_i))

Parameters

k
int = 1
Number of neighbors to use.
distance_weighting
{'uniform', 'distance', 'distance_squared', 'similarity'} = 'uniform'

How to weight neighbors:

  • 'uniform' - All neighbors weighted equally.
  • 'distance' - Weight by inverse of distance :math:`1/d`.
  • 'distance_squared' - Weight by inverse squared distance :math:`1/d^2`.
  • 'similarity' - Weight by similarity :math:`1/(1+d)`.
search_algorithm
{'brute', 'kd_tree', 'ball_tree'} = 'brute'

Algorithm for finding neighbors:

  • 'brute' - Brute force search.
  • 'kd_tree' - KD-tree for faster search in low dimensions.
  • 'ball_tree' - Ball tree for higher-dimensional data.
auto_select_k
bool = False
If True, use leave-one-out cross-validation to automatically select the optimal :math:`k` using MSE.
leaf_size
int = 30
Leaf size for tree-based search algorithms (KD-tree and Ball Tree).

Attributes

X_train_
np.ndarray
Training features stored for lazy learning.
y_train_
np.ndarray
Training target values stored for lazy learning.
search_
NearestNeighborSearch
The search structure instance used for neighbor queries.

Notes

Complexity:

  • Training: O(1) (instances are simply stored)
  • Prediction (brute force): O(n \cdot m) per query
  • Prediction (KD-tree, average case): O(m \cdot \log n) per query
  • Space: O(n \cdot m) for storing all training instances
When to use KNearestNeighborsRegressor:
  • Small to medium datasets where training time must be near-zero
  • Non-linear relationships between features and target
  • When an interpretable, non-parametric baseline is needed
  • Low-dimensional feature spaces (especially with tree-based search)

References

Aha1991
Aha, D.W., Kibler, D. and Albert, M.K. (1991). Instance-Based Learning Algorithms. Machine Learning, 6, pp. 37-66. DOI: 10.1007/BF00153759
Cover1967
Cover, T.M. and Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), pp. 21-27. DOI: 10.1109/TIT.1967.1053964

See Also

KNearestNeighborsClassifier

KNN for classification tasks.

Basic regression with distance-weighted averaging:

python 
>>> from tuiml.algorithms.neighbors import KNearestNeighborsRegressor
>>> import numpy as np
>>> X = np.array([[1], [2], [3], [4], [5]])
>>> y = np.array([1.0, 2.1, 2.9, 4.0, 5.1])
>>> reg = KNearestNeighborsRegressor(k=3, distance_weighting='distance')
>>> reg.fit(X, y)
KNearestNeighborsRegressor(k=3, n_train=5, weighting='distance')
>>> reg.predict(np.array([[2.5]]))
array([...])

Methods

get_parameter_schema (cls) -> Dict[str, Dict[str, Any]]

Return parameter schema.

get_capabilities (cls) -> List[str]

Return regressor capabilities.

get_complexity (cls) -> str

Return time/space complexity.

get_references (cls) -> List[str]

Return academic references.

fit (self, X: np.ndarray, y: np.ndarray) -> 'KNearestNeighborsRegressor'

Fit the regressor by storing the training data.

Parameters
X
np.ndarray of shape (n_samples, n_features)
Training features.
y
np.ndarray of shape (n_samples,)
Target values.
Returns
self
KNearestNeighborsRegressor
Returns the instance itself.
partial_fit (self, X: np.ndarray, y: np.ndarray) -> 'KNearestNeighborsRegressor'

Incrementally add training samples to the regressor.

Parameters
X
np.ndarray of shape (n_samples, n_features)
Incremental training features.
y
np.ndarray of shape (n_samples,)
Incremental target values.
Returns
self
KNearestNeighborsRegressor
Returns the instance itself.
predict (self, X: np.ndarray) -> np.ndarray

Predict target values for the provided samples.

Parameters
X
np.ndarray of shape (n_samples, n_features)
The samples to predict.
Returns
y_pred
np.ndarray of shape (n_samples,)
The predicted target values.
score (self, X: np.ndarray, y: np.ndarray) -> float

Compute the R-squared (coefficient of determination) score.

Parameters
X
np.ndarray of shape (n_samples, n_features)
Test features.
y
np.ndarray of shape (n_samples,)
True target values.
Returns
score
float
R-squared score.
update (self, X: np.ndarray, y: np.ndarray) -> 'KNearestNeighborsRegressor'

Add new instances to the training set (online learning).

Parameters
X
np.ndarray
New training features.
y
np.ndarray
New training target values.
Returns
self
KNearestNeighborsRegressor
Returns the instance with updated training data.
__repr__ (self) -> str

String representation.