# Conformal Prediction for Indoor Localisation with
Fingerprinting Method

Khuong Nguyen, Zhiyuan Luo

► To cite this version:

Khuong Nguyen, Zhiyuan Luo. Conformal Prediction for Indoor Localisation with Fingerprinting Method. 8th International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2012, Halkidiki, Greece. pp.214-223, 10.1007/978-3-642-33412-2_22. hal-01523074

HAL Id: hal-01523074

https://hal.science/hal-01523074

Submitted on 16 May 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Conformal Prediction for Indoor Localisation with Fingerprinting Method

Khuong Nguyen and Zhiyuan Luo

Dept of Computer Science, Royal Holloway, University of London,
Egham, Surrey TW20 0EX, UK

khuong@cantab.net ; zhiyuan@cs.rhul.ac.uk

**Abstract.** Indoor localisation is the state-of-the-art to identify and observe a moving human or object inside a building. Location Fingerprinting is a cost-effective software-based solution utilising the built-in wireless signal of the building to estimate the most probable position of a real-time signal data. In this paper, we apply the Conformal Prediction (CP) algorithm to further enhance the Fingerprinting method. We design a new nonconformity measure with the Weighted K-nearest neighbours (W-KNN) as the underlying algorithm. Empirical results show good performance of the CP algorithm.

**Keywords:** Conformal prediction, indoor localisation, Fingerprinting

## 1 Introduction

The purpose of indoor localisation is to identify and observe a user inside a building. Global Positioning System (GPS) has long been an optimal solution for outdoor localisation, yet the indoor counterpart remains an open research problem, because the complex building infrastructure hinders the GPS signal. In this paper, we applied the Conformal Prediction (CP) algorithm to enhance an effective indoor tracking solution known as “Fingerprinting method” [1]. We designed a new nonconformity measure with the W-KNN as the underlying algorithm. To the best of our knowledge, we are the first to apply CP for the Localisation purpose in general, and for the Indoor Localisation context in particular. The logical progression of the paper is graphically depicted in Figure 1.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Paper progression</figcaption></figure>
## 2 Indoor Localisation Problem

A user can be coarsely identified at room-level or precisely localised at sub-room level. The finest-grained systems offer up to 3cm accuracy, 95% of the time, using intensive hardware implementation [9, 10]. However, they demand massive investment to install and maintain. Balancing between fine-grained tracking and affordable deployment is desirable for recent approaches, which concentrates purely on software solutions. This section outlines the recent approaches with the indoor localisation, as a background to apply Conformal Prediction (CP) in the next section.

### 2.1 Coarse-grained Tracking

The most basic indoor localisation comes from the proximity-based tracking idea. Whenever a user and a base station can communicate, the user's location is determined as the location of the station. This method is further enhanced by dividing the tracking space into grids. The stations are strategically placed in such a way that each grid block is overlapped by the signal from as many different stations as possible (Figure 2). Thus, instead of coarsely predicting the user's location to be somewhere within the station's broadcasting range, the accuracy is improved by interpreting the user's location to be the overlapped portion of the stations the user sees. However, many stations must be deployed to have good signal coverage.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Overlapping signal of 3 stations</figcaption></figure>

Overall, coarse-grained tracking idea is great for localising user at the room-level resolution. The next section discusses how to identify the user at much finer-grained sub-room resolution.

### 2.2 Location Fingerprinting

Coarse-grained tracking is improved further by analysing the wireless signal strength, based on the fact that the radio signal attenuates and gets weaker as it travels in the air. There are two popular measurements to roughly represent the distance between a user and a station: the Received Signal Strength Indication (RSSI) and the Link Quality (LQ). However, two distinct locations might not have a linear relationship in terms of RSSI/LQ and the distance between them. This phenomenon is caused by the signal being blocked by the
indoor objects, known as the multipath issue. An elegant solution - the “Lo-
cation Fingerprinting” method has been widely adopted for its simplicity and
efficiency [1]. This method utilises the built-in wireless signal of the building to
survey a signal-to-position mapping database beforehand, which is known as the
off-line stage. By surveying the whole signal variation at each position, Location
Fingerprinting does not calculate the distance from the user to the station based
on the signal strength. Instead, the system applies pattern-matching algorithms
of the real-time signal and the database record to estimate the most probable
position during the on-line stage.

In comparison to proximity-based tracking, this solution offers much higher
fine-grained tracking even with a few stations. The overall accuracy of the system
relies on two factors. First, if the database is poorly constructed during the off-
line stage, the correct estimation will degrade. Second, the prediction algorithm
chosen in the on-line stage will determine how good the estimated position is.
The Fingerprinting method is depicted in Figure 3.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Location Fingerprinting Method</figcaption></figure>

2.3 Modelling the Indoor Localisation Problem

Without any loss of generality, let us formally model the Location Fingerprinting
method. A general example scheme can be found in Figure 4, where there are
N = 6 base stations (A-F) deployed in a tracking zone. A single location L
is modelled in a 3-dimensional space as L = (d_L^x, d_L^y, d_L^z). The signal strength
RSSI between the user at this location L and all N stations is modelled as an
N-tuple RSSI_L = (s_1, s_2, ..., s_N), where s_i is the signal strength received from
the station i (1 ≤ i ≤ N).

<figure><img src="image_5.png" /><figcaption>Fig. 4. Location fingerprinting deployment example</figcaption></figure>
A database *B* organises the surveyed locations in terms of RSSI and the
corresponding physical co-ordinate as shown in Table 1.

<table><caption>**Table 1.** Off-line database snapshot</caption><thead><tr><th>3-D location (Y)</th><th>RSSI measurement (X)</th></tr></thead><tbody><tr><td>...</td><td>......</td></tr><tr><td>(51, 136, 70)</td><td>(-57, -41, -62, -59, -86, -81)</td></tr><tr><td>(51, 146, 70)</td><td>(-59, -36, -65, -58, -82, -75)</td></tr><tr><td>(51, 156, 70)</td><td>(-56, -38, -69, -58, -84, -73)</td></tr><tr><td>(51, 166, 70)</td><td>(-63, -32, -73, -57, -87, -68)</td></tr><tr><td>(51, 176, 70)</td><td>(-67, -33, -68, -60, -91, -69)</td></tr><tr><td>...</td><td>......</td></tr></tbody></table>

The task is: given an RSSI tuple RSSI<sub>unknown</sub> = (s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>N</sub>) of an unknown location inside the tracking zone, the system compares this tuple with all recorded fingerprints in the database *B* to estimate a closest match, which will tell the correct co-ordinate (d<sup>x</sup>, d<sup>y</sup>, d<sup>z</sup>) of the unknown location. The main challenge is that RSSI measurement at the same location can vary from time to time, and distinct locations might have a similar RSSI combination due to human movements, humidity, furniture re-arrangement, as well as the multipath fading of the indoor environment.

# 3 Conformal Prediction for Indoor Localisation

Having discussed the problem of Indoor Localisation, this section explains and applies the Conformal Prediction (CP) algorithm to address the specific indoor problems outlined previously. Particularly, we show why CP is a suitable algorithm for our purpose. The next section will compare its performance with other traditional algorithms.

## 3.1 Conformal Prediction

Conformal Prediction is a recently developed machine learning algorithm, which uses experiences in the past to confidently and precisely predict the outcome of a new sample [8, 7]. However, what differentiates CP from other similar machine learning algorithms is the ability to produce prediction region for the given confidence level parameter. It has been mathematically proved that the prediction region generated by CP is valid in online setting [8]. In other words, for a confidence level at 95%, the correct estimated position is expected to be included in the prediction region at least 95% of the time. Achieving the prediction result in such a powerful sense, however, CP demands a relatively weak assumption that the training database and the new sample to be classified are generated from
the same distribution independently. CP has been successfully used in many applications such as medical diagnosis and network traffic classification [2, 3].

In general, CP is determined by some nonconformity measure [8]. The non-conformity measure is a real-valued function $A(B, z)$ measuring how different a sample $z$ is to the training database $B$. Whenever a new sample needs to be classified, we exhaustedly test every possible label recorded in the training data, and CP tells us whether to accept that label or not by a test of randomness for a given significance level. CP uses existing machine learning algorithms such as nearest neighbours, SVM and neural network as the underling algorithms to compute a “nonconformity measure” and generate the prediction region [8]. Regardless of the chosen nonconformity measure, the set of locations predicted by CP is always valid in the online setting. However, the efficiency, in other words, the tightness of the prediction region is affected. Ideally, it is more preferred to have as few predictions in the prediction region as possible, without sacrificing the confidence level too much. Each problem requires a customised nonconformity measure to fit the purpose, thus opening more research opportunities. In the next part, we design a new nonconformity measure for the indoor localisation problem.

## 3.2 Applying Conformal Prediction into Fingerprinting method

Giving a training database $B$ mapping physical location co-ordinate to correct Bluetooth signal pattern, and a signal fingerprint at an unknown location, CP precisely predicts a set of locations in the database, which likely matches this new signal fingerprint. This can be formulated as a classification problem, because we divide the physical location into grid points, and the label set is finite. The signal strengths are regarded as the object set $\mathbf{X}$, and the physical locations are regarded as the label set $\mathbf{Y}$. We will apply CP using both the old examples - the training database $B = (z_1, z_2, \dots, z_{n-1})$, and the signal fingerprint of the unknown location (as a new object for $z_n$). Each sample $z_i$ is a combination of the signal strength $RSSI_i = (s_1^i, s_2^i, \dots, s_N^i)$ and the co-ordinate $L_i = (d_i^x, d_i^y, d_i^z)$. A prediction region of $K$ examples is $R^e(L_1, L_2, \dots, L_K) \subset \mathbf{Y}$.

First, CP demands that the training database and the new real-time sample must be generated from the same distribution. This assumption holds because all signals are generated by the same set of base stations independently. Second, to evaluate the difference amongst the samples, the ‘Weighted K-nearest neighbours’ (W-KNN) [4] is chosen as the underlying algorithm to compute the ‘nonconformity score’ $\alpha$. The reason we opted for the ‘Weighted version’ of the traditional K-nearest neighbours algorithm is because of the multipath problem of the indoor signals, which cause many locations further apart to have a similar combination of signal strength. If we treat each of the $K$ neighbours equally, the final estimated position is shifted towards the wrong neighbours further away. By considering the “weight”, corresponding to the inverse “signal distance” between each neighbour and the unknown position, the closer neighbours are prioritised over further away ones. The outline of the Conformal Prediction algorithm with W-KNN is presented in Algorithm 1.
**Algorithm 1 Conformal Predictor with W-KNN**

**Input:** Training database $B=\{z_1, ..., z_l\}$, significance level $\epsilon$, the new example $z_{l+1}$ with known RSSI and $N$ is the number of stations.

**Output:** Prediction region $R$.

**function** DIST_RSSI($P, Q$)

for $i = 1 \rightarrow N$ do

$$distance = distance + (s_P^i - s_Q^i)^2$$

end for

return distance

end function

**function** WEIGHTED_LOCATION($K_{set}, z$)

for $i = 1 \rightarrow K$ do

$$weight1 = 1/\text{dist\_RSSI}(\text{RSSI}_i, \text{RSSI}_z) * K_{set}(d_x^i)$$

$$weight2 = 1/\text{dist\_RSSI}(\text{RSSI}_i, \text{RSSI}_z)$$

end for

return weight1/weight2

end function

**function** NONCONFORM($B, z$)

for $i = 1 \rightarrow N$ do

if ($L_i = L_z$) & dist\_RSSI($B_i, z$) is the smallest then

$$K_{same} = K_{same} + z_i$$

end if

end for

for $i = 1 \rightarrow N$ do

if ($L_i \neq L_z$) & dist\_RSSI($B_i, z$) is the smallest then

$$K_{diff} = K_{diff} + z_i$$

end if

end for

$e_{same} = \text{weighted\_location}(K_{same}, z)$

$e_{diff} = \text{weighted\_location}(K_{diff}, z)$

return sqrt($e_{same} - e_{diff}$)

end function

for $y \in Y$ do

$z_{l+1} = (\text{RSSI}_u, y)$ and include it in $B$

for $z_j$ in $B$ do

$\alpha_j = \text{nonconform}(B, z_j)$

end for

$$p(y) = \frac{\#\{j=1,...,l+1: \alpha_j \geq \alpha_{l+1}\}}{l+1}$$

end for

Predictive set $R = \{y : p(y) \geq \epsilon\}$
Given a training database B, and a new example with a known signal strength pattern but unknown co-ordinate, CP assumes the correct position to be each of the recorded locations in Y. First, we use the Euclidean approach to calculate the “distance” between two signal strength sequences RSSI<sub>P</sub> and RSSI<sub>Q</sub>.

$$
dist(RSSI_P, RSSI_Q) = \sqrt{(s_1^P - s_1^Q)^2 + \dots + (s_N^P - s_N^Q)^2} . \quad (1)
$$

Using Equation (1), we can find *K* entries ($z_1, \dots, z_K$) in the database *B* which have the smallest distances *dist(RSSI*<sub>*i*</sub>, *RSSI*<sub>*u*</sub>) to the unknown location *U*, as well as having the same co-ordinate label *L*<sub>*i*</sub> = (*d*<sub>*i*</sub><sup>*x*</sup>, *d*<sub>*i*</sub><sup>*y*</sup>, *d*<sub>*i*</sub><sup>*z*</sup>) with *U* (1 ≤ *i* ≤ *K*). Then, a weighted average location is calculated from these *K* entries, giving an estimated position *e*<sub>same</sub> = (*d*<sub>*s*</sub><sup>*x*</sup>, *d*<sub>*s*</sub><sup>*y*</sup>, *d*<sub>*s*</sub><sup>*z*</sup>). The below equation is repeated for each co-ordinate of *e*<sub>same</sub>, where δ is a very small constant to prevent division by zero.

$$
d_s^x = \frac{\sum_{i=1}^{K} \frac{1}{\text{dist}(\text{RSSI}_i, \text{RSSI}_u) + \delta} d_i^x}{\sum_{i=1}^{K} \frac{1}{\text{dist}(\text{RSSI}_i, \text{RSSI}_u) + \delta}} . \quad (2)
$$

Similarly, using Equation (1), we find another *K* entries ($z_1, \dots, z_K$) in the database *B* which have smallest distances *dist(RSSI*<sub>*i*</sub>, *RSSI*<sub>*u*</sub>) to the unknown location *U*, but having different co-ordinate label *L*<sub>*i*</sub> = (*d*<sub>*i*</sub><sup>*x*</sup>, *d*<sub>*i*</sub><sup>*y*</sup>, *d*<sub>*i*</sub><sup>*z*</sup>) to *U* (1 ≤ *i* ≤ *K*). Then, another weighted average location is calculated from these *K* entries, giving an estimated position *e*<sub>diff</sub> = (*d*<sub>*d*</sub><sup>*x*</sup>, *d*<sub>*d*</sub><sup>*y*</sup>, *d*<sub>*d*</sub><sup>*z*</sup>).

Our nonconformity measure is the normal Euclidean distance of the two
physical 3-Dimensional locations *e*<sub>same</sub> and *e*<sub>diff</sub>

$$
\alpha = dist(e_{same}, e_{diff}) = \sqrt{(d_s^x - d_d^x)^2 + (d_s^y - d_d^y)^2 + (d_s^z - d_d^z)^2} . \quad (3)
$$

Using Equation (3), we calculate the nonconformity score αᵢ for every entry
in the database B. Then, we count the number of αᵢ which is larger than the
nonconformity score αᵥ of the new sample location U, and divide the total
number of entries in the database B to have the p-value number [8]. Given
a significance level ε beforehand (such as ε = 0.05), the current assumed co-
ordinate label is accepted as the label for the new sample, if and only if the
p-value ≥ ε.

4 Performance Evaluation

Having shown how to apply CP into the Indoor Localisation context, we perform
experiments to evaluate the performance of CP with K-NN, and that of the W-
KNN alone.
## 4.1 Conformal Prediction with W-KNN

For off-line evaluation of CP with W-KNN, we use the Bluetooth signal location database described in [5]. There are 1,052 examples in the training database, and 260 examples in the testing set. Figure 5(a) shows that CP using W-KNN as the underlying algorithm outperforms the W-KNN algorithm alone by 8%-13%. Since CP returns a set of locations, while traditional W-KNN returns just one estimated location for each test sample, we averaged the prediction region returned by CP as a single location for comparison. We compared the performances of CP with the W-KNN algorithm using a Cumulative Distribution Function (CDF) plot (Figure 5(a)). At a significance level $\varepsilon = 0.13$ and $K = 16$, the CP with W-KNN has fewer than 1.5m location error in more than 90% of the time; or it has fewer than 1m location error, 40% of the time. Comparing to the un-Weighted version of K-NN, CP with W-KNN outperforms CP with K-NN by 25% (Figure 5(b)). This enhancement is similar to what reported for W-KNN and K-NN without CP [5]. Varying the $\varepsilon$ and K does affect the accuracy, as explained separately in the next parts.

To verify the validity of the proposed nonconformity measure, we performed leave-out-one on-line cross validation with the above training data only. For $L = 1,052$ samples, we used $L-1$ samples for training and the remaining one for testing. At the same $\varepsilon = 0.13$, the error rate was achieved at 10.8%, which remains valid.

<figure><img src="image_6.png" /><figcaption>Fig. 5. Performance of CP with W-KNN and K-NN</figcaption></figure>

## 4.2 Confidence Level vs. Prediction Region

To study the credibility of the prediction region, we evaluate different confidence levels (see Table 2). The CP Error Rate is the percentage in which CP does not produce a prediction region containing the exact location. For simplicity, we considered a 2-dimensional database, where the prediction region is presented as a set of 2D locations concentrated around a peak position. We observed that the
size of the prediction region decreases as the significance level $\varepsilon$ increases. When the $\varepsilon$ went past 0.38, the prediction region was empty for all testing points. We had precisely 1 prediction label when $\varepsilon$ was around 0.29 for 70% of the test samples. By dividing the training database into 2 equal sets of samples, and used the second set as a test set and the first set as a training set, we worked out that a reasonable confidence level was around 87% with a prediction range of 1.5m - 2m, which is acceptable for tracking users at sub-room resolution. There was only 3.5% of samples with more than 3.5m error. Increasing the confidence level to above 90% allows too many samples getting in the prediction region.

<table><caption>**Table 2.** System accuracy at different confidence levels</caption><thead><tr><th>Confidence level</th><th>Significance level ε</th><th>Prediction range (Average)</th><th>Prediction size (Average)</th><th>CP Error (Average)</th></tr></thead><tbody><tr><td>90%</td><td>0.10</td><td>&gt;2.1m</td><td>62</td><td>7.2%</td></tr><tr><td>87%</td><td>0.13</td><td>1.5m</td><td>29</td><td>11.5%</td></tr><tr><td>71%</td><td>0.29</td><td>3m</td><td>1</td><td>28.7%</td></tr><tr><td>61%</td><td>0.39</td><td>null</td><td>0</td><td>null</td></tr></tbody></table>

## 4.3 Calibrating the K Parameter

Finding an optimal K parameter for the W-KNN is challenging. Each environment and each signal property require the K parameter to be calibrated exclusively. In our system, we experimentally found $K = 16$ to be an optimal value across all testing points. However, some locations had smaller location error with different K value. Generally, starting from $K = 1$, which is equivalent to 1-nearest neighbour only, the accuracy tends to increase as K increases, up to a certain threshold ($K = 16$ in our case). Then, it begins to decrease as K continues to increase. In our experience, from $K = 16$ onwards, the performance is only 7%-10% affected by increasing K.

# 5 Conclusion and Further Work

This section outlines the main contributions of this paper, and the scheme to apply CP for tracking a mobile user.

## 5.1 Contributions

We have demonstrated the application of Conformal Prediction into the Indoor Localisation context. To the best of our knowledge, we are the first to implement Conformal Prediction algorithm into the Localisation problem in general, and the Indoor Localisation in particular. We also designed a new nonconformity measure with the Weighted K-nearest neighbours as the underlying algorithm.
Our initial results showed very promising location accuracy, compared to other
traditional algorithms such as KNN and W-KNN algorithms.

## 5.2 Tracking a Mobile User

Another advantage of CP is that it can work at the on-line learning setting, in
which CP learns from its previous predictions and updates its training database
to improve the accuracy of the next prediction. This scheme perfectly fits the
purpose of tracking an indoor mobile user, since the user cannot jump a long
distance in a short period of time, his next movement is within a certain radius
of his current position.

A challenge to apply CP, however, is the low latency of many tracking sys-
tems. The environment does not always response immediately. Especially with
Bluetooth tracking, the expected delay can be as high as 1.28 seconds, and the
user might have moved away within that time-frame. This is the case of slow
teacher, where immediate feedback cannot be guaranteed. A possible solution is
to evaluate the trustworthy of the received signal at a particular moment. For
example, a signal received in less than 0.5 second would have higher reliability
than that of 2 seconds. We only add the samples with reliable signal measure-
ment into the training database, and discard the others. It is our on-going work
to inspect the improvement of CP for tracking a mobile user, considering the
user movement speeds.

References

1. P. Bahl, V. Padmanabhan: "RADAR: an in-building RF-based user location and tracking system". INFOCOM 2000, 19th Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 2, pp 775-784 (2000).

2. T. Bellotti, Z. Luo, A. Gammerman, F. van Delft, V. Saha: "Qualified Predictions for Microarray and Proteomics Pattern Diagnostics with Confidence Machines". International Journal of Neural Systems, Vol. 15(4), pp 1-12 (2005).

3. M. Dashevskiy, Z. Luo: "Reliable Probabilistic Classification of Internet Traffic", International Journal of Information Acquisition, Vol. 6(2), pp 133-146 (2009).

4. R. O. Duda, P. E. Hart, D. G. Stork: "Pattern Classification", New York: John Wiley & Sons (2001).

5. K. A. Nguyen: "Robot-based Evaluation of Bluetooth Fingerprinting", M.Phil Thesis, Computer Lab, University of Cambridge (2011).

6. K. Proedrou, I. Nouretdinov, V. Vovk, A. Gammerman: "Transductive Confidence Machines for Pattern Recognition", LNCS, Vol. 2430, pp 221-231 (2002).

7. G. Shafer, V. Vovk: "A Tutorial on Conformal Prediction", The Journal of Machine Learning Research, Vol. 9 (2008).

8. V. Vovk, A. Gammerman, G. Shafer: "Algorithmic Learning in a Random World", Springer (2005).

9. R. Want, A. Hopper, V. Falcao, J. Gibbons: "The Active Badge location system. ACM Transaction on Information Systems". ACM Transactions on Information Systems 10, pp 91-102 (1992).

10. A. Ward, A. Jones, A. Hopper: "A New Location Technique for the Active Office". IEEE Personal Communications, Vol. 4, No. 5, pp 42-47 (1997).