kNN vs. Weighted kNN for RSSI Positioning

Once you have a radio map, the last decision in the online path is how to collapse the k nearest reference points into one coordinate — and the two standard answers, plain kNN and weighted kNN, behave very differently on a noisy map. This page compares them so you can pick deliberately rather than defaulting; it sits inside WiFi RSSI Fingerprinting & Radio Maps, immediately after a live scan has been aligned and its neighbours found.

What Plain kNN and Weighted kNN Mean

Both methods start identically: align the live scan to the radio map’s BSSID columns, then find the k reference points whose stored RSSI vectors are closest to the live vector in signal space — Euclidean distance measured in dBm, not metres. The methods differ only in how those k neighbours vote on the final position.

Plain kNN takes the unweighted centroid: average the (x, y) coordinates of all k neighbours, every neighbour counting equally. A neighbour that is a near-perfect signal match and one that barely made the cut contribute the same amount.

Plain and weighted kNN compared on how each combines the same neighbours A two-column comparison. Plain kNN gives every neighbour an equal one-over-k share, so a near-exact match is diluted by the other k minus one points, and results are highly sensitive to the choice of k. Weighted kNN gives each neighbour a share proportional to one over its signal-space distance plus a small epsilon, so a near-exact match dominates as it should and distant points self-mute, which makes the result far less sensitive to k. Both degrade gracefully at a survey gap. Weighting costs one division per neighbour and reduces median error from 3.4 to 2.6 metres. One line of arithmetic apart, and much further apart in behaviour Property Plain kNN Weighted kNN Neighbour contribution △ equal, 1/k each ● 1 / (d + eps) Behaviour on a near-exact match △ diluted by k-1 others ● dominates, as it should Behaviour at a survey gap ● degrades gracefully ● degrades gracefully Sensitivity to k △ high ● low — far points self-mute Extra cost ● none ● one division per neighbour Typical median error 3.4 m ● 2.6 m Same neighbours, same distances; the two differ only in how the centroid is combined.

The fourth row is why weighting is worth it. Plain kNN needs k tuned per floor; weighted kNN lets distant neighbours mute themselves, so one k works across a whole campus.

Weighted kNN (WkNN) weights each neighbour by the inverse of its signal-space distance, so a reference point whose fingerprint closely matches the live scan pulls the estimate harder than a marginal one. The estimate is the weighted centroid Σ wᵢ·pᵢ / Σ wᵢ, with wᵢ = 1 / (dᵢ + ε). The ε guard matters: when a live scan lands exactly on a surveyed fingerprint, dᵢ is zero and an unguarded reciprocal divides by zero.

The intuition: plain kNN treats the k neighbours as an equally trustworthy committee; WkNN treats signal-space closeness as confidence and lets the best matches dominate. On a clean map with dense, evenly spaced points the two nearly agree; on a noisy or irregular map they diverge, and which one wins depends on where the error comes from.

Minimal Working Example

The function below computes both estimates from the same neighbour set so you can compare them directly: a plain centroid and an inverse-distance-weighted centroid over the k nearest fingerprints in signal space.

import logging

import numpy as np
from scipy.spatial import cKDTree

logging.basicConfig(level=logging.INFO, format="%(asctime)s [%(levelname)s] %(message)s")
logger = logging.getLogger(__name__)

EPS: float = 1e-6  # guards the inverse-distance weight against a zero-distance match


def knn_estimates(
    tree: cKDTree,
    coords: np.ndarray,
    scan_vector: np.ndarray,
    k: int = 4,
) -> tuple[np.ndarray, np.ndarray]:
    """Return (plain_centroid, weighted_centroid) over the k nearest fingerprints
    in RSSI signal space. Weights are inverse signal-space distance."""
    k = min(k, coords.shape[0])
    try:
        distances, idx = tree.query(scan_vector, k=k)
    except ValueError as exc:
        logger.error("kNN query failed — scan vector width != radio map width: %s", exc)
        raise
    distances = np.atleast_1d(distances).astype(np.float64)
    neighbours = coords[np.atleast_1d(idx)][:, :2]

    plain = neighbours.mean(axis=0)

    weights = 1.0 / (distances + EPS)
    weighted = (weights[:, None] * neighbours).sum(axis=0) / weights.sum()

    logger.info(
        "k=%d plain=(%.2f, %.2f) weighted=(%.2f, %.2f) nearest_d=%.1f dBm",
        k, plain[0], plain[1], weighted[0], weighted[1], distances[0],
    )
    return plain, weighted

kNN vs. Weighted kNN Comparison

Dimension Plain kNN Weighted kNN (inverse distance)
Accuracy on a dense, even map Comparable — neighbours cluster tightly Marginally better; extra cost rarely pays off
Accuracy on a sparse/irregular map Biased toward the geometric centre of the k points Better — the closest match dominates, tracking the true point
Sensitivity to k High — a too-large k drags in distant points that skew the mean Lower — distant neighbours are down-weighted automatically
Behaviour near walls & edges Pulls the estimate inward, off the true edge position Follows the nearest fingerprint, staying closer to the edge
Compute cost One mean over k points One reciprocal, multiply, and divide — negligibly more
Robustness to a single outlier neighbour Low — an outlier shifts the mean fully Higher if the outlier is far in signal space; it gets a small weight
Failure mode Systematic centroid bias Over-trusting one noisy near-match; needs the ε guard
Median positioning error against k for both estimators Two curves of median positioning error against k. Plain kNN reaches its best value of about 3.4 metres at k of three or four and degrades sharply on both sides, passing 8 metres by k of twenty as distant reference points drag the centroid away. Weighted kNN reaches 2.6 metres at k of four and stays within a tenth of a metre of that from k of three all the way to fifteen, because distant neighbours receive negligible weight. The same neighbours, tuned and untuned 4 6 8 1 5 10 15 20 k (neighbours) median positioning error (m) plain kNN weighted kNN plain kNN has one good k weighted kNN is flat from 3 to 15

Flatness is the real result. The half-metre of accuracy is nice; not having to re-tune k per floor as the survey density varies is what makes weighted kNN the default.

The pattern the table encodes: plain kNN’s error is bias (it averages toward the centre of the neighbour cloud), while WkNN trades some of that bias for variance (it follows the best match, including its noise). On a well-surveyed floor the difference is small; near edges, in sparse zones, and whenever k is set generously to smooth noise, WkNN is the safer default.

Common Errors & Fixes

ZeroDivisionError / inf weights when the scan matches a fingerprint exactly. A live scan that lands on a surveyed point has d = 0, and 1/d is infinite, so that neighbour swamps every other and the estimate snaps entirely onto the one point. The fix is the ε guard already in the example — w = 1 / (d + ε) — which keeps an exact match dominant without making it infinite:

Diagnosing a weighted kNN estimate by the shape of its error One diagnostic question with four outcomes. A fix pinned to a single reference point means epsilon is too small, so a near-zero distance swamps the weight sum. A fix drifting towards the centre of the floor means k is too large and distant points still carry weight. A fix that jumps between consecutive scans is not a kNN fault at all but missing smoothing, and should be sent through the fusion filter rather than to the user interface. A fix on the wrong floor is also not a kNN fault: the level must be resolved separately, by a barometer or a floor-specific beacon. The shape of the error names the term to fix The weighted estimate looks wrong. Which term is at fault? three failure signatures, three different fixes fix pinned to one point eps too small a near-zero distance swamps the sum fix drifts to floor centre k too large distant points still carry weight fix jumps between scans no smoothing feed the fusion filter not the UI fix on the wrong floor not a kNN bug resolve level first barometer or beacon

Half of these are not estimator bugs. Jitter and floor errors get misattributed to kNN constantly, and tuning k to chase them makes the estimator worse at the job it was doing correctly.

weights = 1.0 / (distances + EPS)   # never 1.0 / distances

Choosing k blindly. Too small a k (1–2) makes the estimate hop between individual fingerprints and jitter; too large drags in points from across the floor and, under plain kNN especially, biases the centroid. Sweep k against held-out survey points and pick the value that minimises median error — typically 3 to 6 for a metre-scale grid. WkNN tolerates a larger k because it down-weights the far neighbours a plain mean would count fully.

Confusing signal-space distance with physical distance. The dᵢ that weights a neighbour is the dBm distance between RSSI vectors, not the metres between coordinates. Weighting by physical distance instead defeats the whole method — it assumes you already know where the device is. Always compute the weight from the KD-tree’s signal-space distance, and combine only the coordinates.

Integration Point

This choice is the final link in the online positioning path. The neighbours it weights come straight out of the radio map built in Building a WiFi RSSI Radio Map in Python, and the parent WiFi RSSI Fingerprinting & Radio Maps guide covers the alignment step that precedes it. Whichever estimator you pick, its output is still a single noisy fix — it should not be trusted raw. Feed the WkNN estimate, together with a rough confidence derived from the neighbour distances, into the observation model of the particle filter in Sensor Fusion & Particle Filters, which fuses it with motion to produce the smooth, physically plausible track a user actually follows.

Frequently Asked Questions

Is weighted kNN always better than plain kNN?

No. On a dense, evenly surveyed floor where the k neighbours already sit close together in both signal and physical space, the weighted and plain centroids nearly coincide, and the weighting adds cost for no measurable accuracy gain. WkNN pulls ahead specifically where neighbours are unevenly spaced, near walls and edges, or when you deliberately raise k to smooth noise. Benchmark both on held-out points for your building before committing.

How should I choose k?

Empirically. Hold out a set of surveyed points, run positioning with k from 1 upward, and plot median error against k — it usually falls then flattens or rises as distant points dilute the estimate. A metre-scale grid typically lands at k of 3 to 6. Weighted kNN lets you sit at the higher end of that range safely, because its inverse-distance weights suppress the far neighbours that would bias a plain mean.

Why weight by signal-space distance rather than physical distance?

Because physical distance is the unknown you are trying to estimate — you cannot weight by it without already knowing the answer. Signal-space distance, the dBm gap between the live scan and each stored fingerprint, is observable at query time and is a proxy for confidence: a small gap means the environment matches closely. So the weights come from the RSSI distance, and only the neighbours’ coordinates are averaged.

This page sits within the WiFi RSSI Fingerprinting & Radio Maps guide, part of the Indoor Positioning & Fingerprinting reference.