Gem

Welcome to the supplementary webpage for the GEM paper

This page is intended to give additional information and material including all data sets and source code. You can download all supplementary material in a single zip file (see left) or browse the repository at github.

cDTW vs. GEM dendrograms and the Metal dataset

This sections provides additional dendrograms obtained on the left split (indices 100-499) of the metal dataset. We only state three examples of different types for brevity. All misclassifications of cDTW on this split can be found here in pdf or png format. For a given index the upper dendrogram shows the complete linkage clustering for constrained DTW (with learned parameters) and the lower one the same for the GEM similarity measure (with learned parameters). The images are rendered with DendrogramMetal.py -- feel free to edit this file to obtain dendrograms with single or average linkage.

Index 171 (local trends/deformation)

Obviously, the corresponding child (C) and parent (P) metal strips share a lot of features but differ in a wandering baseline. This artifact is caused by deformation of the fabricated material. The best match (L) under the cDTW distance measure (with learned parameters) accidentally has the same local mean. However, GEM's invariance under local trends makes it possible to select the correct correspondence.

Index 194 (extraction failure/unknown scale)

Although all time series have been scaled to the same length to synchronize the sampling rate of both sensors it may happen, that the extraction of the signal from the data stream is imprecise. A close look at the dendrogram reveals that a slightly downscaled version of P fits a substantial region of C. GEM features scale and translation invariant subsequence matching in the time domain which enables us to find the correct mapping.

Index 255 (occlusion/sensor failure)

This example demonstrates how z-normalization can be harmful when sensor failure occurs. The amplitudes of the distorted time series (P) are significantly altered. GEM avoids this artifact since it does not use z-normalization and allows skips in the query or subject sequence.

Metal and Fish resampled 1NN

Detailed information about all tested distance measures (GEM, (c)DTW, ED) the used splits and learned parameters can be found in the result folder (dn_M* and dn_39*). The histograms can be generated with ResultsMetall.py and ResultsFish.py.

Metal Protocol and Relative Error Rates

The metal dataset consists of 1000 pairs of thickness profile measurements of metal coils. Given a thickness measurement child^i we assign the corresponding time series parent^i for all i in {0,..., 999}. As a result, the dataset consists of 1000 classes with two members each. Since GEM and cDTW both depend on external parameters, we have to carry out parameter learning. Unfortunately, every stratified split of the dataset into a training and test set creates classes with exactly one member which renders parameter learning infeasible. Therefore, we separate a small subset for parameter learning beforehand and determine the error rates on the complementary set to avoid leakage. For our experiments we use the following protocol:

• (i) Shuffle the index set I:={0,...,999} with a random permutation pi to obtain pi(I):={pi(0),...,pi(999)}.
• (ii) Split pi(I) into four disjoint index subsets -- two pairs of parameter learning and holdout sets: (L_left, H_left) as well as (L_right, H_right) with |L_j| = 100 and |H_j| = 400 each.
• (iii) For each of the two pairs (L_j, H_j) do the following: Learn the parameters of the given distance measure on the indices L_j by picking the parameter that yields minimum classification error of a 1NN-classifier built with the parents. After picking the most promising parameter determine the 1NN-classification error on the complementary index set H_j in the same manner. Finally, one yields one error for each H_j. Go to (i) until finished.
  

The partition of the dataset is motivated by the following criteria: Parameters are learned on a small subset since this is the desired real-world setting. The parameter for cDTW is given by the relative window size of the Sakoe-Chiba Band and ranges from 0% to 20%. GEM's scaling parameters s_-, s_+ in S and the averaging coefficient alpha_1 in A are taken from the sets S={1,2} and A={2^{-p} | p in {1,...,8} }. Shuffling the indices during step (i) ensures variability of parameter learning scenarios. Additionally, the dataset is split into two pairs (L_j, H_j) to guarantee the same variability for the final error rate since H_j is substantially altered each run. Otherwise, we would end up with nearly identical holdout sets if we provided only one pair (L, H) for each iteration.

Fish/UCR Protocol and Relative Error Rates

The error rates for the members of the UCR repository are determined by the given protocol: Again, we consider a resampling strategy for our experiments to provide means and standard deviations. The fish dataset has been included into the UCR database and therefore a canonical split into a training and test set is provided. For further resampling we use the following protocol:

• (i) For the first iteration take the UCR split, otherwise accomplish a stratified random split of the dataset into a training and test set conserving the split and class ratios.
• (ii) Learn the parameters of the distance measures with Leave-One-Out-Cross-Validation (LOOCV) on the training set. Pick the parameter that minimizes the error rate.
• (iii) Build a 1NN-classifier with the training set and the optimal parameter. Determine the final error rate on the test set with this classifier. Return to (i) until finished.

UCR database resampled 1NN

The detailed classification rates for all tested distance measures (GEM, (c)DTW, ED) can be found here. This table can be generated with the given Python script. For even more details like the individual splits each iteration please have a look at the results folder.

Visualized classification error

The averaged error rates and standard deviations (error bars) for constrained DTW and GEM on the individual datasets of the UCR repository are shown below.

Prediction power (Texas sharpshooter plot)

The averaged differences of relative error rates and standard deviations (error bars) for constrained DTW and GEM (for both training and test set) on the individual datasets of the UCR repository are shown below.

Speedup Measurements

The makefile for the UCR Suite including the used compiler flags can be found here. The queries and subject of the ECG dataset are provided at the supplementary website of the UCR Suite. The queries and subject for the metal dataset can be generated with the given Python script.

The results for the ECG dataset are illustrated in the following figure: Figure: Performance in terms of execution time for the ECG dataset for the sequential (1 thread), OpenMP (12 threads), CUDA implementation of GEM in comparison to UCR-DTW with three different window settings (0.05, 0.1, 0.2). The x-axis represents the size of Q. S is fixed at size 20.1 million. The y-axis represents the execution time (in seconds), both using logarithmic scale.