Information Technology Reference
In-Depth Information
where brute-force instance-based learning is used for training in most cases. With
brute-force instance-based learning, every training pattern is added to the set of
reference patterns, which can make the size of reference patterns very large. Large
number of reference patterns incur the problem of low performance and aggressive
resource consumption that limits the practical value of the system.
In this paper, we propose a DTW-based clustering algorithm to optimize the
number of reference patterns in a systematic way. In our method, training a
classifier is performed in two phases. In the first phase, a classifier is trained
according to the brute-force instance-based learning. In the second phase, the
DTW-based K-Means clustering algorithm is run on each gesture class over all
the reference patterns. The algorithm partitions the reference patterns into a
small number of clusters according to the similarity measured by DTW and
extracts the centroid of each cluster. The centroids of the clusters become the
new optimized reference patterns for each gesture class. One important issue
in applying K-Means with DTW is that the reference patterns are different in
length. We cannot simply estimate the centroid of non-uniform length patterns
as they are in different hyperspaces. The solution we propose is to warp the
reference patterns along the warping path determined by DTW. By repeating
pairwise warping across all the patterns in a cluster, it is possible to estimate
the centroid of the cluster. We describe the details of the algorithm in section 2.
To show the effectiveness of the algorithm, we applied the algorithm to the
problem of recognizing 26 English uppercase alphabets written using a handheld
device having a 3-d accelerometer. The results from the experiment are presented
in section 3.
2 DTW-Based Temporal Pattern Clustering
In this section, we provide detailed description of how patterns of non-uniform
length can be clustered based on DTW measure. The basic idea is to average
two patterns along
the warping path
generated by DTW. Let us assume that
P
and
Q
are two patterns, each of which is respectively represented as
n × k
and
n × l
matrices. By applying DTW, we can get a warping path
W
,which
is an ordered list of index pairs. Each index pair (
i, j
) corresponds to the best
matching element pairs from
P
and
Q
respectively. With
W
, we can calculate
the centroid
M
of
P
and
Q
as follows.
|F |
j
=1
F
j
), 1
M
i
=
2
(
1
|F |
P
i
+
≤ i ≤ k
F
=
{Q
W
m,
1
|W
m,
0
=
i,
1
≤ m ≤|W|}
m
is the index of the warping path
W
. The length of the warping path is
|W|
.
W
m,
0
is the index of
P
's element that lies in the
m
-th place in the warping
path, while
W
m,
1
is the index for
Q
.Consequently,
F
represents the set of
Q
's elements that are matched to
P
i
. Extending the above formula to
N
pat-
terns , we get the algorithm 2. In the algorithm,
P
is a list of
N
patterns, and
WarpingPathByDTW(
n,M, |M|,P
i
, |P
i
|
) is assumed to calculate the warping
path
W
of two input patterns
M
and
P
i
using DTW.
Search WWH ::
Custom Search