(WEIGHTED) ADAPTIVE RADIUS NEAR NEIGHBOR SEARCH: EVALUATION FOR WIFI FINGERPRINT-BASED POSITIONING
arXiv:2604.15940v1 [cs.LG] 17 Apr 2026
KHANG LE1 , JOAQUÍN TORRES-SOSPEDRA2 , PHILIPP MÜLLER3
Abstract. Fixed Radius Near Neighbor (FRNN) search is an alternative to the widely used k Nearest Neighbors (kNN) search. Unlike kNN, FRNN determines a label or an estimate for a test sample based on all training samples within a predefined distance. While this approach is beneficial in certain scenarios, assuming a fixed maximum distance for all training samples can decrease the accuracy of the FRNN. Therefore, in this paper we propose the Adaptive Radius Near Neighbor (ARNN) and the Weighted ARNN (WARNN), which employ adaptive distances and in latter case weights. All three methods are compared to kNN and twelve of its variants for a regression problem, namely WiFi fingerprinting indoor positioning, using 22 different datasets to provide a comprehensive analysis. While the performances of the tested FRNN and ARNN versions were amongst the worse, three of the four best methods in the test were WARNN versions, indicating that using weights together with adaptive distances achieves performance comparable or even better than kNN variants.
1. Introduction In 1951, Fix and Hodges [1] introduced a non-parametric supervised learning method, named k Nearest Neighbors (kNN), that is used until this day in numerous applications and for both classification and regression tasks [2]. The kNN remains one of the most suitable approaches for fingerprint-based positioning systems, particularly in technologies such as WiFi, Bluetooth Low Energy, and Visible Light Communication. In order to remain competitive with alternative machine learning techniques, which avoid exhaustive comparisons with the entire fingerprint map, resulting in faster inference, various optimization strategies have been proposed to accelerate kNN inference, ensuring that kNN continues to be a relevant and competitive approach. The Fixed Radius Near Neighbor (FRNN) search has been around for nearly as long as the kNN, with [3] attributing the origin of the approach to a paper by Levinthal from 1966 [4], but is markedly less used than the kNN. The basic principle behind the FRNN is to label a test sample based on the labels of all training samples within a given distance, which is 1 Faculty of Information Technology and Communication Sciences, Tampere University, Tampere, Finland, ORCID: 0009-0000-8327-4741 2 Department of Computer Science, University of Valencia,% ValgrAI, Valencia, Spain ORCID: 0000-0003-4338-4334 3 Faculty of Medicine and Health Technology, Tampere University, Tampere, Finland, ORCID: 0000-00034314-7339
Version: 17 April 2026 This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. P. Müller acknowledges funding from the Research Council of Finland under decision no. 360768. J. TorresSospedra acknowledges funding from Generalitat Valenciana (CIDEXG/2023/17, Conselleria d’Educació, Universitats i Ocupació). 1
2
LE ET AL.
used as similarity measure, from the test sample. Hence, the number of training samples for different test samples may vary. This is in contrast to the kNN, where the number of closest training samples is fixed to k for any test sample. Both methods have their advantages and disadvantages. Determining the label of a test sample based on a fixed number of k training samples ensures that only samples most similar to the test sample are used. However, the kNN operates with relative similarities. Even if the test sample and its k closest training samples show poor similarity, the kNN will still yield a label for the test sample. This can result in misclassifications, for example, if the test sample is from a class for which no labeled training samples are available. In such scenario the FRNN will return information that the test sample cannot be labelled, which is arguably more desirable than obtaining a misclassification. The drawback of the FRNN is that finding a radius yielding high accuracy while providing labels for (almost) all test samples is cumbersome, because training samples may be unevenly distributed across different areas. To address these shortcomings various modifications of kNN and FRNN have been proposed (see e.g. [2, 5]) to improve their accuracy, with the majority focuses on the kNN. However, Torres-Sospedra et al. [2] demonstrated that none of the proposed improved kNN variants consistently outperformed all other variants when being applied to 69 fingerprint datasets dealing with indoor positioning based on WiFi, BLE, and hybrid signals. Instead, for different datasets different kNN variants emerged as the most accurate variants. Motivated by their work and by the observation that different samples benefit from different radii, we propose two modifications of the FRNN with adaptive radii named the Adaptive Radius Near Neighbor (ARNN) and the Weighted Adaptive Radius Near Neighbor (WARNN). We compare their performance with FRNN and the kNN variants investigated in [2] for indoor positioning using 22 WiFi fingerprint datasets. This paper demonstrates that the performance of the traditional FRNN is inferior to that of the kNN variants, while the newly proposed ARNN performed on par. It, furthermore, shows that the second newly proposed method, the WARNN, can even outperform all tested kNN variants.
2. Related work Since the first introduction of kNN in indoor positioning in 2000 [6], a significant number of its variants has been developed with the aim of improving positioning accuracy by utilizing different techniques. To compare their performance, [2] examined 13 kNN implementations on 69 datasets. The results showed that adaptive weighted methods such as Adaptive Weighted kNN [7] and Self-Adaptive Weighted kNN [8] performed best amongst the evaluated models. However, [2] demonstrated that no single kNN variant outperformed all other variants for all datasets. FRNN was used for indoor positioning based on ion mobility spectrometry measurements in [9]. In the FRNN a predefined radius is used to determine the neighbors of a test sample instead of a fixed value of k. [9] demonstrated that the FRNN can outperform the kNN when a suitable radius is selected. However, this advantage came at the cost of some test samples being not classified due to the absence of training samples within the predefined radius. In [9] FRNN and kNN were evaluated on a single dataset, thus limiting the robustness of the conclusions. Therefore, this article examines the performance of both FRNN and the kNN variants tested in [2] on 22 WiFi datasets.
(WEIGHTED) ADAPTIVE RADIUS NEAR NEIGHBOR SEARCH
3
3. Radius-based Near Neighbors methods 3.1. Fixed Radius Near Neighbor. While kNN variants require the number of closest neighbors k as input, the Fixed Radius Near Neighbor requires a maximum radius rmax as input parameter. This radius is a measure of the similarity between a test sample x = [x1 , . . . , xn ] ∈ Rn and any training sample yi , i = 1, .., N . Instead of searching for the k training samples with the highest similarity (i.e. smallest distance) to x as for kNN-type methods, the FRNN searches for all training samples that are within rmax to the test sample and determines a label for the test sample based on the training samples within rmax . Thus, rmax can be interpreted as minimum similarity required for accepting training samples as being predictive of the label of the test sample x. Therefore, k is variable and an output parameter, if desired, of the FRNN. The FRNN has some theoretic advantages over kNN-type methods. First, it does not require finding a suitable or even an optimal k. Second, if the test sample is from a class for which no training samples are available in the training set Y, then any kNN variant will misclassify the test sample x as belonging to one of the classes present in Y. The FRNN, in contrast, could return in such scenario information that no label could be provided because none of the training samples was within rmax of the test sample. However, this cannot be guaranteed and the FRNN might still yield a misclassification (see e.g. the test results in [9]). Furthermore, choosing a suitable rmax can be challenging and cumbersome. This is explainable by the fact that in most real-world scenario training samples are not uniformly distributed, meaning that training sample density varies in different regions. Therefore, in this paper, two Radius Near Neighbor (RNN) variants inspired by adaptive kNN and weighted kNN are proposed. 3.2. Adaptive Radius Near Neighbors. The Adaptive kNN (AkNN) was proposed to resolve the challenge of selecting an appropriate k [10, 11]. Instead of relying on a fixed value, it dynamically determines an optimal k for each training point by using a separate algorithm. Each test point then finds its nearest neighbor and inherits that k value from that neighbor [5]. Inspired by AkNN we propose the Adaptive Radius Near Neighbors (ARNN) as an alternative to the FRNN. Instead of requiring the user to define rmax , the ARNN determines a suitable ri for any training sample yi in the training phase (see Algorithm 1 for the pseudo-code). The algorithm determines for any yi (i = 1, . . . , N ) its distances to the remaining training samples. It then tests for the k (k = {Kmin , .., Kmax }) closest neighbors if they would yield a correct label in case of a classification task or an accurate estimate in case of a regression task. At the end, it sets ri to the largest distance between the training sample and its k neighbors for the largest k that yields a correct label or accurate estimate. Instead of the largest distance other statistics such as mean or median values could be used, but will not be studied in this manuscript. If none of the tested k values yields a correct label or accurate estimate, then ri is set to zero and yi is likely an outlier. For determining a label or estimate for the test sample x (see Algorithm 2 for the pseudocode), the ARNN determines a set C of training samples for which the test sample is within the radii computed in the training phase. It then computes a label or an estimate based on the training samples in C. If C is empty, meaning that x is not within the neighborhood of any training sample, the ARNN returns information that no label or estimate could be determined, indicating that the test sample is potentially an outlier or from a class that is not present in the training data. 3.3. Weighted Adaptive Radius Near Neighbors. One point of criticism for the kNN is that it assumes that all k neighbors are equally informative when determining a label or estimate for a test sample. However, this assumption is often not fulfilled. For example,
4
LE ET AL.
Algorithm 1: Training phase for ARNN and WARNN. Input: training samples Y = [y1 , . . . , yN ] ∈ Rn×N from M classes, Kmin , Kmax , error threshold τϵ (for regression task) Output: radii r = [r1 , . . . , rN ] for i ← 1 to N do Set ri ← 0 Calculate distances d(yi , yj ) for all j = 1, . . . , N with j ̸= i Sort distances d(yi , yj ) in ascending order and store them in di and the corresponding j in Ii for K ← Kmin to Kmax do Calculate a class label (classification task) or a numeric estimate (regression task) for yi from K training samples associated to the first k indices in Ii If the label is correct (classification task) or the estimate within τϵ (regression task) then set ri ← K-th element in di . end end
Algorithm 2: Test phase for ARNN and WARNN. Input: training samples Y = [y1 , . . . , yN ], radii r = [r1 , . . . , rN ], test sample x = [x1 , . . . , xn ] ∈ Rn Output: Class label (classification task) or numeric estimate (regression task) for x Set C ← ∅ for i ← 1 to N do Calculate distance d(xi , yi ) If d(xi , yi ) ≤ ri then add i to set C end if C ̸= ∅ then Calculate a label or estimate based on the training samples with indices in C else Return that no label (classification task) or estimate (regression task) could be determined due to lack of close neighbors end
when determining a location estimate based on WiFi fingerprints, then training samples with fingerprints almost identical to the fingerprint at the test location most likely provide a better estimate than training samples with fingerprints only roughly the same as the test fingerprint. Therefore, an extension to kNN was introduced that assigns weights to the k neighbors, known as Weighted k Nearest Neighbors (WkNN) [12]. It gives higher weights to closer neighbors and lower weights to distant neighbors, with weights summing up to one. In scenarios where closer neighbors are more representative of the test sample than neighbors further away, this strategy, in general, improves accuracy [5]. Based on this intuition, we propose the use of weights in the ARNN and name it consistently the Weighted Adaptive Radius Near Neighbors (WARNN). In contrast to the WkNN, for the ARNN not only the distance between the test sample x and the training sample yi matters, but also how close this distance is to ri . Consider, a scenario as illustrated in Fig. 1. The test
(WEIGHTED) ADAPTIVE RADIUS NEAR NEIGHBOR SEARCH
5
sample is closer to neighbor 1 than to neighbor 2 in a two dimensional feature space. With the standard weighting function employed commonly in the WkNN, the first neighbor would be assigned a larger weight than the second. However, x is almost at the edge of the neighborhood defined by the radius of neighbor 1 but only half-way between neighbor 2 and the circle defined by its radius. This indicates that the test sample is weakly associated with neighbor 1 but strongly associated with neighbor 2.
Figure 1. Illustration of challenge to choose suitable weights for the WARNN. Therefore, we propose an adaptive decay factor for the inverse distance weighting (IDW) function that reflects the distance between the test sample x and a neighbor yi as well as the relative position of the test sample in the sphere of yi defined by radius ri . The IDW function is defined by (1)
wi =
1 , d(yi , x)α
where α is the decay factor. As the distance d(yi , x) increases the weight decreases, as in the IDW commonly used by WkNN methods. The decay factor α enables controlling the rate at which weights decrease. The higher the decay factor the faster the decay. No optimal decay factor has been reported in the literature and different studies have used values between 1 and 5 [13, 14, 15, 16]. Therefore, we propose an adaptive decay factor defined by (2)
α=1+
d(yi , x) , ri
which ensures that α ∈ [1, 2] and reflects the relative position of the test sample within the sphere around the training sample while ensuring that closer neighbors retain higher influence on the overall label or estimate respectively. 3.4. Coverage ratio. For all three RNN variants it is possible that no label or estimate is returned when the test sample lies outside the radii of all training sample. Although this property is desirable when analyzing samples from unknown classes, it becomes problematic for classification tasks when a large portion of test samples from classes present in the training samples are not classified. For regression tasks it may yield overly optimistic average estimation errors due to yielding only estimates for test samples most similar to any training sample. Thus, to evaluate the performance of RNN methods one should also consider the ratio of test samples for which labels or estimates are provided. This ratio, which is herein referred to
6
LE ET AL.
as coverage ratio, is defined as h , m where h is the number of test samples receiving a label or estimate and m is the total number of test samples (h ≤ m). (3)
γ = 100%
4. Empirical Analysis and Results 4.1. Experimental setup. We applied FRNN, ARNN, and WARNN with two different weighting functions for determining 3-dimensional position estimates and compared them to the kNN and its variants analyzed in [2]. Conversely to [2], the evaluation includes a relevant subset of 22 diverse WiFi datasets widely used in the literature: DSIn [17], LIBn [18], TUTn [19, 20, 21, 22, 23, 24], UJIn [25], SODn [26]. The implemented kNN variants and dataset descriptions are provided in [27] for research reproducibility and replicability [28]. The tested kNN variants included: • M1 : kNN with optimal k and unweighted centroid • M2 : kNN with optimal k and weighted centroid (IDW) • M3 : kNN with optimal k and weighted centroid (IDW2 ) • M4 : Adaptive WkNN [7] (AWKNN) with kmax = 51 • M5 : AWKNN with optimal kmax based on WkNN • M6 : Self-Adaptive WkNN [8] (SAWKNN) with kmax = 51 • M7 : SAWKNN with optimal kmax • M8 : Spatial-Temporal Improved WkNN [30] (STIWkNN) with optimal k • M9 : Distance Weighted and Feature Weighted kNN [29] (DWFWkNN) with physical distance from [29] • M10 : DWFWkNN with physical distance from [2] • M11 : Adaptive Residual WkNN [31] (ARWkNN) with optimal k and Cityblock distance • M12 : ARWkNN with optimal k and Min-Max distance • M13 : ARWkNN with optimal k and Clark distance M1−3 , M6 and M7 used Cityblock, M4 and M5 Cosine, and M8 Euclidean distance metric. Used distance metrics and optimal k values were determined by brute-force search. Tested distance metrics included Euclidean, Cityblock, Min-Max, Cosine, and Clark; tested k values included {1, 2, . . . , 20, 21, 23, . . . , 51}. Details on the used kNN variants are given in [2] and references therein. In addition, the following RNN variants were tested • M14 : FRNN with Euclidean distance • M15 : FRNN with Cityblock distance • M16 : FRNN with Cosine distance • M17 : ARNN with Euclidean distance • M18 : ARNN with Cityblock distance • M19 : ARNN with Cosine distance • M20 : WARNN with Euclidean and IDW (1) with α = 2 • M21 : WARNN with Euclidean and IDW (1) with α defined by (2) • M22 : WARNN with Cityblock and IDW (1) with α = 2 • M23 : WARNN with Cityblock and IDW (1) with α defined by (2) • M24 : WARNN with Cosine and IDW (1) with α = 2 • M25 : WARNN with Cosine and IDW (1) with α defined by (2)
(WEIGHTED) ADAPTIVE RADIUS NEAR NEIGHBOR SEARCH
7
Table 1. Dataset-wise mean 3D positioning errors and average 3D positioning errors for kNN and RNN implementations. Dataset
M1
M2
M3
M4
M5
M6
M7
M8
M9
M10
M11
M12
M13
M14
M15
M16
M17
M18
M19
M20
M21
M22
M23
M24
M25
DSI1 DSI2 LIB1 LIB2 TUT1 TUT2 TUT3 TUT4 TUT5 TUT6 TUT7 UJI1 UJI2 SOD1 SOD2 SOD3 SOD4 SOD5 SOD6 SOD7 SOD8 SOD9
4.09 4.22 2.44 3.70 8.28 11.23 9.06 5.68 6.29 1.87 2.23 8.62 6.35 2.65 1.72 1.80 2.50 2.93 3.72 3.24 3.74 3.61
4.05 4.17 2.43 3.70 8.20 11.02 8.65 5.57 6.23 1.87 2.23 8.61 6.33 2.65 1.71 1.80 2.50 2.92 3.74 3.25 3.76 3.63
4.03 4.11 2.42 3.69 8.06 10.85 8.36 5.52 6.19 1.87 2.15 8.60 6.31 2.64 1.71 1.79 2.50 2.91 3.73 3.26 3.75 3.65
3.86 3.85 2.47 2.64 6.21 8.84 8.33 5.83 5.82 2.12 2.53 7.60 6.66 2.98 1.93 1.97 4.09 3.70 3.96 3.46 3.96 3.98
3.83 3.84 2.44 2.64 6.16 8.83 8.33 5.83 5.93 2.11 2.51 7.58 6.62 2.84 1.99 1.98 4.09 3.14 3.96 3.43 3.98 3.86
4.10 4.05 2.43 3.66 7.67 11.17 8.35 5.76 6.14 1.76 2.10 8.52 6.41 2.67 1.68 1.73 2.48 2.81 3.64 3.29 3.64 3.73
4.03 4.05 2.41 3.68 8.21 11.17 8.32 5.58 6.07 1.75 2.10 8.46 6.31 2.64 1.68 1.79 2.48 2.86 3.61 3.27 3.64 3.62
3.82 3.83 2.44 2.68 6.28 8.79 8.24 5.80 5.93 2.11 2.51 7.59 6.60 2.83 2.00 2.07 4.16 3.17 4.04 3.46 4.15 4.08
27.63 27.88 4.11 5.59 11.87 16.22 20.55 20.27 16.38 14.32 14.34 29.51 21.13 5.45 4.38 7.20 5.33 4.93 8.14 5.61 9.07 7.69
4.14 4.11 2.50 3.35 7.70 9.98 8.57 5.81 6.39 1.95 2.23 7.97 6.03 2.66 2.48 2.46 4.66 3.50 4.70 4.11 4.42 4.29
4.78 4.90 2.47 4.20 9.41 12.40 9.16 6.25 6.92 1.89 2.24 9.42 7.02 3.16 1.85 1.90 2.80 3.18 3.85 3.58 3.99 3.76
3.91 3.95 2.61 2.69 6.93 9.72 8.34 5.68 6.11 1.82 2.11 7.91 6.73 2.98 1.65 1.79 2.92 3.09 3.83 3.62 4.12 3.76
3.90 3.93 2.90 3.25 6.95 9.63 8.39 5.49 5.84 2.01 2.24 7.86 6.53 2.50 1.92 1.82 2.96 2.86 3.96 3.77 4.27 4.09
5.14 5.13 2.69 3.59 7.90 11.17 10.76 7.73 6.77 4.05 3.17 10.35 7.91 3.41 2.75 3.07 3.57 4.11 4.21 4.26 4.46 4.54
5.80 5.75 2.75 3.57 8.39 12.22 13.47 9.27 8.35 4.34 3.39 11.98 8.38 3.13 2.41 2.64 3.36 4.10 4.39 4.34 4.26 4.34
4.06 4.03 2.69 2.77 6.81 8.80 8.49 6.32 6.27 3.04 2.99 7.77 7.41 3.73 2.26 2.54 3.24 4.00 3.68 3.77 4.18 4.27
3.84 3.98 2.87 3.17 7.96 9.59 8.45 5.62 6.89 2.21 2.41 8.64 7.20 2.98 2.04 2.14 3.54 3.74 3.73 3.79 4.05 4.47
4.06 4.05 2.86 3.00 7.15 10.09 9.13 5.92 6.47 2.21 2.43 8.36 7.51 2.77 1.79 1.82 2.67 3.73 3.62 3.54 3.62 3.88
3.79 4.02 2.91 3.21 7.97 9.49 8.49 5.74 6.38 2.27 2.57 8.50 6.83 3.11 1.89 2.15 3.43 3.50 3.60 3.46 3.96 4.55
3.74 3.87 2.75 3.15 7.57 9.53 7.95 5.32 6.57 1.92 2.10 8.14 6.93 2.93 1.91 2.04 3.42 3.45 3.68 3.70 3.99 4.30
3.67 3.75 2.71 3.16 7.51 9.20 7.90 5.28 6.45 1.77 1.98 7.97 6.84 2.88 1.86 1.96 3.38 3.41 3.65 3.68 3.90 4.21
3.74 3.74 2.69 3.01 6.90 10.22 8.38 5.45 6.19 1.84 2.01 7.70 6.98 2.72 1.61 1.69 2.62 3.50 3.51 3.45 3.49 3.81
3.61 3.59 2.66 2.99 6.87 9.69 8.37 5.50 6.12 1.66 1.87 7.46 6.80 2.62 1.52 1.58 2.59 3.48 3.46 3.35 3.45 3.71
3.57 3.83 2.56 3.03 6.81 8.76 8.24 5.32 6.18 1.91 2.18 8.04 6.50 3.05 1.77 1.97 4.08 3.32 3.56 3.44 3.70 4.38
3.67 3.91 2.71 3.06 7.14 9.03 8.33 5.57 6.41 2.24 2.52 8.16 6.58 3.19 1.78 2.08 4.15 3.44 3.58 3.46 3.73 4.38
Average Rank
4.54 13
4.50 12
4.46 11
4.40 7
4.36 3
4.45 10
4.44 9
4.39 6
13.07 22
4.73 18
4.96 19
4.38 5
4.41 8
5.49 20
5.94 21
4.69 16
4.70 17
4.58 14
4.63 15
4.50 12
4.41 8
4.33 2
4.23 1
4.37 4
4.50 12
Background meaning:
lowest error
second highest error
highest error
For all RNN variants a minimum coverage ratio of 90% was required. Optimal rmax values were determined by brute-force search for M14−16 from the following sets: {60, 62, . . . , 260} for M14 , {150, 152, . . . , 300} ∪ {305, 310, . . . , 1000} ∪ {1010, 1020, . . . , 2350} for M15 , and {1.0 · 10−2 , 1.2 · 10−2 , . . . , 9.8 · 10−2 } ∪ {0.100, 0.105, . . . , 0.500} for M16 . In addition, for ARNN and WARNN τϵ = 5 m was used, and Kmin = 1 and Kmax = max (Kmin , {⌈p% · N ⌉) were tested to limit the maximum number of neighbors per training sample to (approximately) p% of the number of training samples. Only values from the set p ∈ [0.1, 0.2, . . . , 25.0] ∪ [25, 26, . . . , 40]} ensuring a coverage ratio of at least 90% were tested. In the positioning task the three-dimensional (3D) position estimate ẑ = [ẑ1 , ẑ2 , ẑ3 ] for test location z = [z1 , z2 , z3 ] given the WiFi Received Signal Strength (RSS) fingerprint y at the test location was determined using the locations of the closest WiFi RSS fingerprints in the training dataset according to the 25 different methods described above. For algorithms incorporating weights, all weights were scaled to sum up to one. The 3D positioning error e3D for ẑ was calculated by q 2 2 2 (4) e3D = (ẑ1 − z1 ) + (ẑ2 − z2 ) + (ẑ3 − z3 ) . 4.2. Comparison of kNN and RNN variants. Table 1 reports the mean 3D positioning errors for each dataset across all methods M1−25 , as well as the average of mean 3D positioning errors computed over all 22 datasets. In addition, for M14−25 coverage ratios for each dataset as well as the average coverage ratio over all 22 datasets are reported. None of the tested kNN variants clearly outperforms the remaining variants and the mean errors for methods M1−13 are similar to those reported in [2]. Small discrepancies in the mean errors reported in Table 1 and [2] could be explained by differences in hardware and software used in both studies. Except for M9 , all kNN variants yield similar average 3D positioning errors with M1−8 and M12−13 differing at most 18 cm (4.1% of the lowest average 3D positioning error) and M10−11 yielding only 8.4% and 13.8% higher average errors than the best performing variant M5 . For the FRNN only the variant using Cosine distance (M16 ) yields competitive performance, with an average 3D positioning error 7.6% above the average error of M5 . Euclidean and Cityblock distances yield 25.9% and 36.2% higher errors than M5 . At the same time, Cosine achieves the highest average coverage ratio of the three tested FRNN variants. The proposed
8
LE ET AL.
Table 2. Coverage ratios of RNN implementations. Dataset
M14
M15
M16
M17
M18
M19
M20
M21
M22
M23
M24
M25
DSI1 DSI2 LIB1 LIB2 TUT1 TUT2 TUT3 TUT4 TUT5 TUT6 TUT7 UJI1 UJI2 SOD01 SOD2 SOD3 SOD4 SOD5 SOD6 SOD7 SOD8 SOD9
93.39 93.39 94.23 93.46 91.63 98.86 90.13 90.82 90.02 90.81 90.78 90.91 90.83 91.43 90.93 90.12 90.70 92.21 95.10 94.12 90.49 93.43
90.52 90.52 90.16 90.80 90.41 90.91 90.13 90.53 90.63 90.26 90.24 90.28 90.33 90.71 90.58 90.12 90.81 90.23 90.69 94.12 90.49 90.49
99.14 99.14 91.73 92.34 90.41 97.73 90.48 90.67 92.26 90.06 90.03 90.37 90.06 90.60 90.35 90.12 90.47 91.40 92.55 90.59 96.08 95.10
98.28 98.28 99.39 90.06 90.20 93.75 90.43 90.10 96.95 92.60 95.68 91.36 90.60 90.36 95.58 99.77 94.42 90.70 99.02 90.69 98.14 96.08
90.80 99.14 98.30 97.18 90.41 98.30 90.81 92.68 90.84 93.90 96.18 90.55 90.31 90.48 97.67 95.93 93.02 90.58 100.00 94.02 100.00 97.06
100.00 98.85 100.00 100.00 90.61 99.43 90.18 91.68 90.22 92.08 95.01 92.26 93.82 90.36 91.40 98.95 99.77 90.23 100.00 90.30 98.04 96.85
98.28 98.28 99.39 90.06 90.20 100.00 90.43 90.10 97.25 92.60 95.68 91.36 90.60 90.36 95.58 99.77 94.42 90.70 99.02 90.69 99.12 100.00
99.14 99.14 99.58 90.06 90.20 100.00 90.43 90.10 96.95 92.60 95.68 91.36 90.60 90.36 96.74 99.77 95.58 90.70 99.02 90.69 99.12 100.00
99.14 99.14 98.56 97.18 90.41 100.00 90.81 92.68 97.96 93.90 96.18 90.55 90.31 90.48 97.67 95.93 93.02 90.58 100.00 94.02 100.00 97.06
99.14 99.14 98.94 97.31 90.41 100.00 90.81 92.68 97.96 93.90 96.18 90.55 90.31 90.48 98.37 95.93 93.02 90.58 100.00 94.02 100.00 100.00
100.00 100.00 100.00 100.00 99.39 99.43 90.18 91.68 90.22 92.08 95.01 92.26 93.82 90.36 91.40 98.95 99.77 90.23 100.00 90.20 98.04 96.86
100.00 100.00 100.00 100.00 98.57 99.43 90.18 91.68 90.22 92.08 95.01 92.26 93.82 90.36 91.40 98.95 99.77 90.23 100.00 90.20 98.04 96.86
Average
92.17
90.63
92.35
94.20
94.46
95.00
94.72
94.90
95.25
95.44
95.45
95.41
ARNN is less sensitive to the distance metric. The average 3D positioning errors with Euclidean, Cityblock, and Cosine distances are within 12 cm and between 5.0% and 7.8% larger than for M5 . Thus, their performance is on a similar level than most kNN variants. Besides better performance, the ARNN variants also yield coverage ratios (see Table 2) that are 2 to 4 percentage points higher than those of the FRNN variants. WARNN variant M23 yields the lowest average 3D positioning error of all 25 tested algorithms, with an average error 3.0% smaller than the lowest error of any kNN variant. In addition, the WARNN seems to be insensitive to the choice of the distance metric and weighting function. The errors of all six tested variants were within 28 cm, with the worst performing variant (M25 ) yielding an average error 3.4% larger than the error of M5 . In addition, all WARNN variants outperformed all FRNN and ARNN variants and yielded coverage ratios of approximately 95% (all within 0.72 percentage points). 4.3. Test with varying error threshold. For the tests in the previous subsection an error threshold of τϵ = 5 m was used. This value was chosen because almost all kNN variants yielded average 3D positioning errors below 5 m in our tests and in [2]. However, modifying the error threshold τϵ in the training phase could theoretically affect both accuracy and coverage ratio. We, therefore, studied the impact of varying τϵ for the best performing RNN variant M23 . Figure 2 shows the 3D average positioning errors and corresponding coverage ratios for threshold values τϵ = {3, 4, . . . , 11} m. Values below 3 m are not reported as they did not ensure a coverage ratio of at least 90% for some datasets. Unsurprisingly, the coverage ratio increased with larger τϵ because fewer training samples had ri = 0, resulting in more training samples being available during the test phase. More surprisingly, increasing the error threshold in the training phase decreased the 3D average positioning error of M23 by up to 11 cm compared to using τϵ = 5 m, which is a reduction of 2.6%. Once τϵ ≥ 8 m the average error seemed to stabilize.
(WEIGHTED) ADAPTIVE RADIUS NEAR NEIGHBOR SEARCH
9
Figure 2. 3D average positioning errors and corresponding coverage ratios of M23 for varying τϵ . If individual threshold values τϵ yielding the mean 3D positioning errors would be chosen for all dataset, the average 3D positioning error could be further reduced to 4.05 m with a coverage ratio of 95.81%. This suggests that using τϵ as a parameter, which should be optimized for each dataset individually, could be beneficial. 5. Conclusions This paper proposed two modifications of the Fixed Radius Near Neighbor search with adaptive radii and compared their performance with the performances of the FRNN as well as 13 k Nearest Neighbors variants for indoor positioning on 22 WiFi fingerprint datasets. This extensive comparison was motivated by [2], which showed that most kNN variants yield similarly positioning errors when evaluated over a large number of datasets, although for single datasets considerable differences in the positioning errors could be observed. Our study confirmed these results for the 13 tested kNN variants and showed that, when assuming a coverage ratio of at least 90%, the traditional FRNN performs worse than most kNN variants. One reason could be the use of fixed radii in the FRNN, which theoretically works well for equally spaced samples but potentially causes performance degradation for unequally distributed samples. Hence, we proposed the Adaptive Radius Near Neighbor search, which takes into account the sample distribution around each training sample when determining adaptive radii. Using adaptive radii reduced the positioning errors to a level achieved my most kNN variants. One shortcoming of the ARNN is, however, that it ignores the varying radii associated with different training samples when computing position estimates for test samples from the locations of these training samples. Therefore, we proposed an extension of the ARNN that weights the contributions of all training samples to the final estimate. We propose two variants of this weighted ARNN; one with a commonly used inverse distance weighting function and one with a custom adaptive decay factor. Based on the results of our extensive evaluation the use of weighting mechanisms enables average positioning errors close or even lower than those of
10
LE ET AL.
the best kNN variants. We finally showed that the accuracy of our WARNN could be further improved by optimizing the error threshold value τϵ used in the training phase. It has to be noted that, unlike the traditional kNN and FRNN, both ARNN and WARNN incur computational cost in the training phase. Future research should, therefore, investigate potential methods for reducing this cost. Furthermore, the performance of ARNN and WARNN variants for other regression tasks as well as classification tasks should be tested and all algorithm hyperparameters should be optimized. Finally, the performance of ARNN and WARNN variants in scenarios where test samples originate from classes absent in the training set should be investigated, as under such conditions radius-based nearest neighbor search is theoretically expected to be the better choice than kNN-type methods due to its possibility to return no estimate when no training samples sufficiently similar to the test sample could be identified. Data Usage and Reproducibility The data and code necessary to reproduce the results presented in this article will be made publicly available after acceptance by the IEEE. References [1] E. Fix and J.L. Hodges, “Discriminatory analysis. nonparametric discrimination: Consistency properties,” Int. Stat. Rev., 57(3), 238–247, 1989. [2] J. Torres-Sospedra, C. Pendão, I. Silva, et al., “Let’s Talk about k-NN for Indoor Positioning: Myths and Facts in RF-based Fingerprinting,” IPIN 2023, Sept. 2023. [3] J.L. Bentley, “A survey of techniques for fixed radius near neighbor searching,” Technical Report SLAC-186 and STAN-CS-75-513, Stanford Linear Accelerator Center, August 1975. [4] C. Levinthal, “Molecular model-building by computer,” Scientific American, 214, 42–52, 1966. [5] S. Uddin, I. Haque, H. Lu, et al., “Comparative performance analysis of K-nearest neighbour (KNN) algorithm and its different variants for disease prediction,” Scientific Reports, 12(6256), 2022. [6] P. Bahl and V. Padmanabhan, “RADAR: An in-building RF-based user location and tracking system,” Proceedings IEEE INFOCOM, 2000. [7] S. Liu, R. Lacerda, and J. Fiorina, “Performance analysis of adaptive K for weighted K-nearest neighbor based indoor positioning”, VTC2022-Spring, June 2022. [8] J. Hu, D. Liu, Z. Yan, H. Liu , “Experimental analysis on weight K -nearest neighbor indoor fingerprint positioning,” IEEE Internet of Things Journal, 6(1), 891–897, 2019. [9] P. Müller, “Flexible K Nearest Neighbors Classifier: Derivation and Application for Ion-mobility Spectrometry-based Indoor Localization,” IPIN 2023, Sept. 2023. [10] D. Wettschereck and T.G. Dietterich, “Locally adaptive nearest neighbor algorithms,” Proceedings of NIPS’93, pp. 184–191, November 1993. [11] S. Sun and R. Huang, “An adaptive k-nearest neighbor algorithm,” 7th Int. Conf. on Fuzzy Systems & Knowledge Discovery, 91–94, 2010. [12] S.A. Dudani, “The Distance-Weighted k-Nearest-Neighbor Rule,” IEEE Trans. SMC, 6(4), 325–327, 1976. [13] A. Bekele, R. Downer, M. Wolcott, et al., “Comparative evaluation of spatial prediction methods in a field experiment for mapping soil potassium,” Soil Science, 168, 15–28, 2003. [14] J. Ping, C. Green, R. Zartman, and K. Bronson, “Exploring spatial dependence of cotton yield using global and local autocorrelation statistics,” Field Crops Research, 89, 219–236, 2004. [15] C. Lloyd, “Assessing the Effect of Integrating Elevation Data Into the Estimation of Monthly Precipitation in Great Britain,” J of Hydrology, 308, 128–150, 2005. [16] G. Lu and D. Wong, “An adaptive inverse-distance weighting spatial interpolation technique,” Computers Geosciences, 34, pp. 1044–1055, 2008. [17] A. Moreira, I. Silva, J. Torres-Sospedra, “The DSI dataset for Wi-FI fingerprinting using mobile devices,” Version 1.0, Zenodo, 2020. [18] G.M. Mendoza-Silva, P. Richter, J. Torres-Sospedra, et al., “Long-term WiFi fingerprinting dataset for research on robust indoor positioning,” Data, 3(1), 3, 2018.
(WEIGHTED) ADAPTIVE RADIUS NEAR NEIGHBOR SEARCH
11
[19] S. Shreshta, J. Talvitie, and E.S. Lohan, “Deconvolution-based indoor localization with WLAN signals and unknown access point locations,” [online] http: //www.cs.tut.fi/tlt/pos/MEASUREMENTS WLAN FOR WEB.zip, 2013 [20] A. Razavi, M. Valkama, and E.S. Lohan, “K-means fingerprint clustering for low-complexity floor estimation in indoor mobile localization,” IEEE Globecom Workshops, 2015. [21] A. Cramariuc, H. Huttunen, and E.S. Lohan, “Clustering benefits in mobile-centric WiFi positioning in multi-floor buildings,” ICL-GNSS, 2016. [22] E.S. Lohan, J. Torres-Sospedra, H. Leppäkoski, et al., “Wi-Fi crowdsourced fingerprinting dataset for indoor positioning,” Data, 2(4), 2017. [23] P. Richter, E.S. Lohan, andJ. Talvitie, “WLAN (WiFi) RSS database for fingerprinting positioning”, Version 1.0.0, Zenodo, 2018. [24] E.S. Lohan, “Additional TAU datasets for Wi-Fi fingerprinting-based positioning,” Zenodo, 2020. [25] J. Torres-Sospedra, R. Montoliu, A. Martı́nez-Usó, et al., “UJIIndoorLoc: A new multi-building and multifloor database for WLAN fingerprint-based indoor localization problems,” IPIN 2014, Sept. 2014. [26] J. Bi, Y. Wang, B. Yu, et al., “Supplementary open dataset for WiFi indoor localization based on received signal strength,” Satell Navig, 3(1), 25, 2022. [27] J. Torres-Sospedra, C. Pendão, I. Silva, et al., “Supplementary Materials for <<Let’s Talk about k-NN for Indoor Positioning: Myths and Facts in RF-based Fingerprinting>>,” Version 1.0, Zenodo, 2023. [28] G.G. Anagnostopoulos and A. Kalousis, “Towards reproducible indoor positioning research,” IPIN 2021, Nov. 2021. [29] X. Liang, X. Gou, and Y. Liu, “Fingerprint-based location positioning using improved KNN,” 3rd IEEE Int. Conf. on Network Infrastr & Digital Content, 57–61, 2012. [30] H. Zou, M. Jin, H. Jiang, et al., “WinIPS: WiFi-based non-intrusive indoor positioning system with online radio map construction and adaptation,” IEEE Trans. Wireless Communications, 16(12), 8118–8130, 2017. [31] S. Xu, C.-C. Chen, Y. Wu, et al., “Adaptive Residual Weighted K-Nearest Neighbor Fingerprint Positioning Algorithm Based on Visible Light Communication,” Sensors, 20(16), 4432, 2020.