
Table 7: A search algorithm for the best S-C band

warping window.

Function [R] = BestWarping[T,**bound**]

1 N**= size of** T;

2 best heuristic = **NegativeInfinite**;

3 for (k = bound **to 0)**

4 bandk= S-C Band at k**% width;**

5 heuristic= evaluate(**bandk**);

6 if (heuristic > best **heuristic**)

7 best heuristic = **heuristic**;

8 R = k;

9 endif

10 endfor

from the original one in that we bound the maximum width of the warping window and we use our evaluation function
(heuristic function) instead of the typical training accuracy.

A simple pseudo code is described in Table 7 below. A set of training data T and a maximum warping window size are required in discovering the best warping window R.

## 3.4 Iterative Band Learning

The iterative R-K band learning is extended from the original learning that it will repeat the learning again and again until a heuristic value no longer increases. In the first step, we initialize all the multi R-K bands with R% Sakoe-Chiba band, where R is the output from the best finding warping window algorithm. We also set a learning threshold to be half of the time series length, and the initial bands are evaluated

| 2   | threshold = L / 2;                              |
|-----|-------------------------------------------------|
| 3   | best heuristic = evaluate(T, band);             |
| 4   | while (threshold) < 1                           |
| 5   | fw band = forward learning(T, L, band, bound);  |
| 6   | bw band = backward learning(T, L, band, bound); |
| 7   | fw heuristic = evaluate(T, fw band);            |
| 8   | bw heuristic = evaluate(T, bw band);            |
| 9   | band = maximum heuristic value band;            |
| 10  | heuristic = maximum heuristic value;            |
| 11  | if heuristic = best heuristic                   |
| 12  | threshold = threshold / 2;                      |
| 13  | endif                                           |
| 14  | endwhile                                        |

In each iteration, our proposed algorithm learns a new R-K
band starting with the previous R-K band learning result both in forward and backward direction. We also run both forward and backward learning and select the best band which gives a higher heuristic value. If the heuristic value is the same as the best heuristic value, the threshold is divided by two; otherwise we update the best heuristic value. We repeat these steps until the threshold falls below 1. Table 8 shows our proposed algorithm, iterative R-K band learning, which requires a set of training data T, a best warping

Table 9: Our proposed R-K band learning algorithm.

Function [R] = ProposedLearning[T, threshold, band, **bound**]

1 L**= length of data in T;**

2 foreachclass i = 1 to c

3 enqueue(1, L, i, Queue);

4 endfor

5 best **heuristic = evaluate(T, band);** 6 while !empty(Queue) 7 [start, end, label] = randomly **dequeue(Queue)** 8 adjustable = adjust(bandlabel, start, end, bound); 9 if adjustable

10 heuristic = evaluate(T, band);

11 if heuristic > best **heuristic**

12 best **heuristic = heuristic;** 13 enqueue(start, end, label, Queue); 14 else 15 undo **adjustment(bandlabel, start, end);**

16 if (start - end) / 2 ≥ **threshold**

17 enqueue(start, mid-1, label, Queue);

18 enqueue(mid, end, label, Queue);

19 endif

20 endif

21 endif 22 endwhile

window R, the length of time series L, and the bound of warping window.

We have modified the original multi R-K bands learning by changing its data structure. We replace multi queues, which are originally assigned for each class by only one single queue with an addition parameter label to each start-end object.

This new queue will draw an object randomly instead of lastin-first-out (LIFO) manner. In addition, we also change an adjustment function by adding a new parameter bound to limit forward learning not to increase the band's size exceeding limited bound. Table 9 shows the proposed R-K band learning on a set of training data T, a learning threshold, an initial band, and the bound of warping window.

## 3.5 Evaluation Function

From Section 2.4, we have briefly described the utility and the algorithm of the Silhouette index. This index is commonly used to measure the quality of a clustered dataset; however, we can utilize this Silhouette index as a heuristic function to measure the quality of a distance measure as well. The DTW distance with multi R-K bands is a distance measure that requires one additional parameter, **Band**, specifying the R-K band to be used (since the multi R-K bands contain one band for each class). Table 10 shows the evaluation function derived from the original Silhouette index.

$$s(i,B a n d)={\frac{b(i,B a n d)-a(i,B a n d)}{\operatorname*{max}\left\{b(i,B a n d),a(i,B a n d)\right\}}}$$
$\downarrow$ . 