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.

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

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:

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.