API Reference / algorithms / anomaly /

knn_detector.py

kNN-based outlier detection by distance to the k-th nearest neighbour.

Classes

KNNDetector

class algorithms.anomaly.knn_detector.KNNDetector(Classifier)

Score outliers by their distance to the k nearest neighbours.

The oldest idea in outlier detection and still one of the hardest to beat: a point far from its neighbours is anomalous. Unlike the per-feature detectors it works on the joint distribution, so it finds points that are unremarkable in every individual coordinate yet sit in an empty region of the space — the case where ECODDetector and HBOSDetector are blind.
Constructor 
__init__(
    self,
    n_neighbors: int = 5,
    method: str = 'largest',
    metric: str = 'euclidean',
    contamination: float = 0.1,
)

Overview

  1. Index the training data for nearest-neighbour search.
  2. For each point, find its k nearest training neighbours.
  3. Reduce those k distances to a single score with method.
  4. Larger distance means more anomalous.

Theory

With d_{(1)} \leq \dots \leq d_{(k)} the sorted distances from x to its k nearest neighbours, the three reductions are

\mathrm{largest}(x) = d_{(k)}, \quad \mathrm{mean}(x) = \frac{1}{k} \sum_{i=1}^{k} d_{(i)}, \quad \mathrm{median}(x) = \mathrm{median}\{d_{(i)}\}

'largest' is the classic formulation and reacts fastest to a single isolated point; 'mean' and 'median' are steadier when the data has small tight clusters that 'largest' would flag wholesale.

The method measures global distance, so it assumes one roughly uniform density scale. Where density varies across regions — a sparse cluster that is perfectly normal for its neighbourhood — a global radius mislabels the whole sparse region, and LocalOutlierFactorDetector, which normalises by local density, is the correct tool.

Parameters

n_neighbors
int = 5
Number of neighbours k. Set this larger than the biggest group of anomalies you expect. Anomalies arriving in a tight group of more than k points become each other's nearest neighbours, so their distances look small and the group masks itself; once k exceeds the group size the neighbourhood reaches back to the inliers and the score recovers. Smaller values react faster to genuinely isolated points.
method
{'largest', 'mean', 'median'} = 'largest'
How the k distances are reduced to one score.
metric
{'euclidean', 'manhattan', 'cosine'} = 'euclidean'
Distance metric.
contamination
float = 0.1
Expected proportion of outliers. Sets the decision threshold.

Attributes

X_train_
np.ndarray of shape (n_samples, n_features)
Training data retained for neighbour search.
threshold_
float
Decision-function value separating inliers from outliers.
n_features_in_
int
Number of features seen during fit.

Notes

Complexity. Fitting only stores the data. Scoring is O(m n d) by brute force, which is the dominant cost and the method's real limit — the pairwise distance loop runs in the shared C++ kernel tuiml._cpp_ext.distance, but the quadratic term remains. Memory is O(n d).

When to use. Use kNN when anomalies are defined by position in the joint space and the dataset is small enough for a quadratic scan — up to roughly 10^4 points. Features must be scaled first: an unscaled feature with a large range dominates the distance and the detector silently becomes univariate. Above that size, or in high dimension where distances concentrate, prefer IsolationForestDetector or the per-feature detectors.

References

Ramaswamy2000
Ramaswamy, S., Rastogi, R., & Shim, K. (2000). Efficient Algorithms for Mining Outliers from Large Data Sets. ACM SIGMOD, 427-438. :doi:`10.1145/342009.335437`
Angiulli2002
Angiulli, F., & Pizzuti, C. (2002). Fast Outlier Detection in High Dimensional Spaces. PKDD, 15-27. :doi:`10.1007/3-540-45681-3_2`

See Also

LocalOutlierFactorDetector

Normalises by local density.
ABODDetector

Angle-based; survives higher dimension.
ECODDetector

Per-feature, far faster, blind to joint structure.
python 
>>> import numpy as np
>>> from tuiml.algorithms.anomaly import KNNDetector
>>> rng = np.random.default_rng(0)
>>> X = np.vstack([rng.normal(0, 1, (200, 2)), rng.normal(7, 0.5, (10, 2))])
>>> detector = KNNDetector(n_neighbors=15, contamination=0.05).fit(X)
>>> int((detector.predict(X)[-10:] == -1).sum())
10

Note n_neighbors=15 against a group of 10 anomalies. Dropping to

n_neighbors=5 lets the group mask itself and finds only 2 of them:

python 
>>> masked = KNNDetector(n_neighbors=5, contamination=0.05).fit(X)
>>> int((masked.predict(X)[-10:] == -1).sum())
2

Methods

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

Return JSON Schema for algorithm parameters.

get_capabilities (cls) -> List[str]

Return supported capabilities.

get_complexity (cls) -> str

Return complexity analysis.

get_references (cls) -> List[str]

Return academic citations.

fit (self, X: np.ndarray, _y: Optional[np.ndarray]=None) -> 'KNNDetector'

Fit the kNN detector.

Parameters
X
np.ndarray of shape (n_samples, n_features)
Training data. Labels are ignored; the method is unsupervised.
_y
np.ndarray
Ignored, present for API consistency.
Returns
self
KNNDetector
The fitted detector.
decision_function (self, X: np.ndarray) -> np.ndarray

Compute anomaly scores for samples.

Parameters
X
np.ndarray of shape (n_samples, n_features)
Input samples.
Returns
scores
np.ndarray of shape (n_samples,)
Anomaly scores. Lower scores indicate anomalies.
predict (self, X: np.ndarray) -> np.ndarray

Predict if samples are anomalies or not.

Parameters
X
np.ndarray of shape (n_samples, n_features)
Input samples.
Returns
predictions
np.ndarray of shape (n_samples,)
-1 for anomalies, 1 for normal instances.
score_samples (self, X: np.ndarray) -> np.ndarray

Alias for decision_function for compatibility.

Parameters
X
np.ndarray of shape (n_samples, n_features)
Input samples.
Returns
scores
np.ndarray of shape (n_samples,)
Anomaly scores. Lower scores indicate anomalies.
__repr__ (self) -> str

Return a readable representation of the detector.