Database Reference
In-Depth Information
S
t
, the resultant new set
S
t
+1
=
When an additional point
p
t
+1
is added to
S
t
∪{p
t
+1
}
has the generalized median
t
+1
1
t
1
p
t
+1
=
p
t
+
¯
+1
·
p
i
=
+1
·
¯
+1
· p
t
+1
t
t
t
i
=1
p
t
and
whichistheso-calledweightedmeanof¯
p
t
+1
satisfying
1
p
t
+1
,
p
t
)=
p
t
,p
t
+1
)
d
(¯
¯
+1
· d
(¯
,
t
t
¯
p
t
+1
,
p
t
,p
t
+1
)
d
(¯
P
t
+1
)=
+1
· d
(¯
.
t
p
t
+1
is a point on the straight line segment connecting ¯
p
t
Geometrically, ¯
p
t
,p
t
+1
)and1
p
t
,p
t
+1
)
and
p
t
+1
that has distances 1
/
(
t
+1)
· d
(¯
/
(
t
+1)
· d
(¯
p
t
and
to ¯
p
t
+1
, respectively.
On a heuristic basis the special case in real space can be extended to
the domain of strings. Given a set
S
t
=
{p
1
,p
2
,...,p
t
}
of
t
strings and
p
t
, the generalized median of a new set
S
t
+1
its generalized median ¯
=
S
t
∪{p
t
+1
}
p
t
and
p
t
+1
,i.e.byastring
is estimated by a weighted mean of ¯
p
t
+1
such that
¯
p
t
+1
,
p
t
)=
p
t
,p
t
+1
)
d
(¯
¯
α · d
(¯
,
p
t
+1
,p
t
+1
)=(1
p
t
,p
t
+1
)
d
(¯
− α
)
· d
(¯
where
α ∈
[0
,
1].Inrealspace
α
takes the value 1
/
(
t
+ 1). For strings,
however, we have no possibility to specify
in advance. Therefore, we
resort to a search procedure. Remember that our goal is to find ¯
α
p
t
+1
that
S
t
+1
. To determine the optimal
minimizes the consensus error relative to
α
value a series of
α
values 0
,
1
/k,...,
(
k −
1)
/k
is probed and the
α
value
that results in the smallest consensus error is chosen.
The dynamic algorithm uses the method described in [3] for computing
the weighted mean of two strings. It is an extension of the Levenshtein
distance computation [38].
6. Experimental Evaluation
In this section we report some experimental results to demonstrate the
median string concept and to compare some of the computational proce-
dures described above. The used data are online handwritten digits from a
subset
1
of the UNIPEN database [14]. An online handwritten digit is a time
1
Available at ftp: //ftp.ics.uci.edu/pub/machine-learning-databases/pendigits/.
