A Semi-supervised Approach to Indoor Location Estimation
Hisashi Kashima, Shoko Suzuki, Shohei Hido, Yuta Tsuboi,
Toshihiro Takahashi, Tsuyoshi Idé, Rikiya Takahashi, and Akira TajimaIBM Research
Tokyo Research Laboratory
1623-14, Shimotsuruma, Yamato-shi
Kanagawa 242-8502, JapanAbstract
We describe the approach and the algorithm that we usedfor Task1 “Indoor Location Estimation” in ICDM Data
Mining Contest 2007. We formulated the task as a transduction problem, and employed a semi-supervised learning
approach based on a multi-class version of the label propagation method.

1A formulation as a transduction problem

We formulate the indoor location estimation problem asa transductive multi-class classification problem.
Let the whole dataset consists of N = 5, 333 instances,where the first ` = 505 instances are the labeled data, andthe rest of them are the unlabeled data. The i-th data isgiven as (x(i) , y (i) ), where x(i) ∈ R101 is the vector of thereceived signal strength (RSS) values from the WiFi Access
Points (APs), and y (i) ∈ {1, 2, . . . , 247} is the location label assigned to the RSS vector. As for the unobserved RSSvalues, we filled them by −100, since all RSS values are inthe range of [−100, 0] and unobserved RSS value implies
that it was too weak to detect.
In addition to the RSS values, some portion of the instances are given trace IDs and observation times, whichindicate the trace (i.e. experiment) each instance belongs toand the time when it was observed. We denote by T ID(i)and t(i) the trace ID and the observation time of the i-th instance, respectively. For simplicity, we treat the observation
times as just the orders of observation, i.e. integer values,
although they are given as real values in the original data.
The objective of this task is to predict the location labelsof the unlabeled data, y (`+1) , . . . , y (N ) , since they are notgiven. Note that since the inputs of the test data set are given
in advance of the test phase, we can regard the problem as atransduction problem where test inputs are explicitly used.

2A semi-supervised approach using labelpropagation

We employ a multi-class version of the label propagation method [2], which is one of the supervised learning
approaches [1].
Let f (i) (c) ∈ [0, 1] indicate the probability with which
the location label of the i-th instance is c. For the labeleddata (i ≤ `), the following holds{1 (if c = y (i) )(i).
(1)
f (c) =0 (otherwise)
The task is to predict f (i) (y (i) ) for i > ` and ∀c, with which
we obtain the prediction ĉ(i) for i > ` byĉ(i) = argmax f (i) (c).

(2)

c

In the label propagation framework, we try to minimize
the discrepancies of the label distributions among neighbourhood instances, which is defined as)2∑(∑
w(i,j)
f (i) (c) − f (j) (c) ,(i,j)

cwhere w(i,j) is a constant called the affinity indicating thesimilarity between the i-th instance and the j-th instance,
which we will define later. It is easy to see that the solutionof the above optimization problem satisfies∑ (i,j) (j)
f (c)
jw(i)
∑ (i,j)f (c) =,(3)wjfor ∀i > ` and ∀c. Therefore, instead of solving the large
optimization problem directly, we can iteratively apply (3)to make local updates of predictions until convergence.
The affinity w(i,j) is defined as the maximum of either
(i,j)
(i,j)
wx
defined by RSS vectors and wt
defined by traceIDs and observation times, i.e.
{}
(i,j)
(i,j)
w(i,j) = max wx , wt.

References(4)

Our definition of the affinity tries to imply that two instances
are similar if their RSS vectors are similar or their observation times are consecutive.
For the affinity between two RSS vectors x(i) and x(i) ,we used a heat-kernel like function)(qk x(i) − x(j) kq
(i,j)
,(5)
wx
= exp −σwhere σ is a scale parameter, and we set σ = 0.5 in oursubmission. Also, k · kq is the q-norm which is defined ask x kq =(∑) q1|xd |q,dand we set q = 0.5 based on the observation that this choice
performed well in our preliminary analysis using the nearest
neighbour classifier for the labeled data.
The affinity between two pairs of a trace ID and an observation time is defined as() ()(i,j)
wt= p · δ T ID(i) = T ID(i) · δ |t(i) − t(i) | = 1 ,(6)where p ∈ [0, 1] is a constant indicating the affinity of twoconsecutive observations, and we simply set p = 1 in thesubmission. Also, σ is a function that returns 1 if its argument is true, and 0 if otherwise.

3The algorithm

Based on the discussion in the previous section, each stepof the algorithm is summarized as follows.
1. Initialize f (i) by using (1) for the labeled instances(i ≤ `).
2. Compute the affinities between all pairs of instancesby using (4), (5) and (6).
3. Continue the follwing steps, 3a and 3b, until convergence.
(a) Select i > ` uniformly at random.
(b) Update f (i) (c) for ∀c by using (3).
4. Output prediction for i in the test data by using (2).

[1] X. Zhu. Semi-supervised learning literature survey. Technical
Report Computer Sciences, TR 1530, University of Wisconsin Madison, 2006.
[2] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised
learning using gaussian fields and harmonic functions. In Proceedings of The 20th International Conference on Machine
Learning, 2003.