1-nearest neighbor (1NN) with Dynamic Time Warping (DTW) distance is a popular time series classification technique. In the last decades, research on DTW aimed to improve its classification accuracy, memory usage, and efficiency. According to a recent study, the appropriate selection of the Warping Window Size (WWS) is crucial for the accuracy of 1NN-DTW. In this work, we consider person identification based on keystroke dynamics as a time series classification task, and we examine whether WWS is crucial in this case. We performed experiments on a real-world dataset containing more than 400 typing sessions obtained from 12 users. In the case of this dataset, each user typed the same fixed text. We found that the aforementioned hypothesis was correct, i.e., the classification accuracy indeed depends on the WWS. Furthermore, according to our observations, in our case, the optimal WWS is less than 3% which is substantially different from 10% that has been used as a default value in various works.
Biometric authentication systems are based on user
traits and characteristics. There are two major forms
of biometrics: those based on physiological attributes
and those based on behavioral characteristics. The
physiological type includes biometrics based on stable
body traits, such as the face, iris, fingerprint, and the
hand, and are considered to be more robust and secure.
However, they are also considered to be more
vulnerable to intrusions, expensive and require special
equipment [
Recently, keystroke dynamics has gained
popularity [
Various methods have been used for user
authentication based on keystroke dynamics, such as Bayesian
classifiers, neural networks, SVM, Markov chains and
dimensionality reduction [
Measuring the similarity between a pair of time
series is an important task which is usually applied in
many data mining applications such as anomaly
detection [
Given two time series T1 of length n, and T2 of length m
T1 = ( T1[
T2 = ( T2[
The simplest way to define the similarity S is to
treat these sequences as vectors and to compute the
Euclidean distance between them directly. However,
this requires both time series to be of the same length,
i.e., m = n, but this is not always the case in real-world
applications [
DTW [
In order to understand DTW in more detail, we define an n by m matrix D, in which each entry di; j corresponds to the squared distance between two values of the time series: di; j = (T1[i] T2[ j])2. To find the best match between the two time series, we retrieve a path through the matrix, called warping path, that minimizes the total cumulative distance. The warping path is a sequence of neighboring entries1 of D so that it begins in the top left (first row, first column) corner of D, and it ends in the bottom right corner (last row, last column). In particular, the optimal warping path W is the path that minimizes the cost. The DTW distance is 1With neighbors of di; j we mean: di 1; j 1, di 1; j, di 1; j+1, di; j 1, di; j+1, di+1; j 1, di+1; j, di+1; j+1. where P is the set of all warping paths.
This warping path can be found using dynamic programming to evaluate the following recurrence: s [i; j] = di; j + min 8 s [i < s [i : s [i; j (1) (2) Note that s (i; j) is the cumulative distance along the optimal warping path.
In most applications, it may not be reasonable to allow for arbitrarily large shifts and elongations, therefore, the calculations are usually restricted to the entries around the diagonal of the matrix, i.e., si; j is calculated , ji jj w;
Input: T1: array [1..n], T2: array [1..m] Output: distance s = array[0..n][0..m] for i = 1, ..., n do for j = 1, ..., m do
s [i,j] = ¥ s [0,0] = 0 for i = 1, ..., n do for j = 1, ..., m do cost = (T1[i] T2[ j])2 s [i,j] = cost +
min(s [i-1, j], s [i , j-1], s [i-1, j-1]) return s [n,m] where w is the Warping Window Size (WWS) which controls the maximum amount of warping. In the cases, where some of the terms si; j 1, si 1; j, si 1; j 1 are undefined (i.e., they have not been calculated), they are excluded from Eq. (2). WWS is often set to 10% of the length of the time series.
The effect of WWS on the classification
performance has been studied, for example, in [
The goal of our experiments is to examine the effect of warping window size on the accuracy of person identification. 3.1
We used the dataset associated with Task 1 of the
Person Identification Challenge. Typing dynamics of 12
users were recorded in 458 sessions with a JavaScript
(JS) application. In each typing session, the users were
asked to type some sentences and the keyboard events
keyup, keydown and keypress were captured by the JS
application. For each of the aforementioned events,
the time (in milliseconds) was also recorded, see [
We are given the true identity of the users (coded by integer numbers from 1 to 12) for 5 typing patterns per user. We use this data as training data.
Additionally, hypothetical user identities for the rest of the typing patterns are given. This data is used as test data.
Our task is to decide if the hypothetical identities match the true identities of the users who typed those patterns.
The submission system at the webpage of the challenge is used to evaluate our predictions for the test data. 3.2
In order to experimentally examine the role of the warping window size, we use 1-nearest neighbor with DTW with various warping window sizes w 2 f0; 1; 2 : : : ; lmaxg where lmax is the length of the longest 2biointelligence.hu/typing-challenge/ typing pattern sequence. Before running the DTW distance between each pair of keystroke time series, the data must be pre-proceeded, then we classify users’ test data.
extract down-down and down-up durations, the raw data must be preprocessed. In particular, we performed the following preprocessing steps: select time and relevant event types, i.e., keydown and keyup.
Sometimes the first event of the typing pattern is a keyup event (see Fig. 3) which is caused by clicking the shift key to change the cursor between registration form fields, so we removed it.
For simplicity, we removed sequential successive keydown or successive keyup events, and we kept the latest keydown and the first keyup (see Fig. 4).
the approach for extracting down-down (between keystroke) and down-up (keystroke duration) metrics. To test the effect of the warping window size on the classification accuracy, we performed empirical experiments on the datasets containing (i) keystroke durations and (ii) between-keystroke-times. Additionally, we experimented with a combination of the two aforementioned options.
We vary the warping window size from 0 (Euclidean) to lmax (no constraint/full calculation) and record the accuracy for each warping window size. The results are shown in Fig. 5, Fig. 6 and Fig. 7. 3.4
A study made by Ratanamahatana et al. [
Input: typingP : List [] Output: ksDuration: List [] counter = 0 ksDuration = [] while not end of list do ksDuration[counter] =
typingP[counter + 1] - typingP[counter]
counter = counter + 2
return ksDuration
Based on the result of Ratanamahatana et al.[
Our results confirm the hypothesis of Dau et al. [
This work was supported by the project no. 204603/2018/ FEKUTSTRAT within the Institutional Excellence Program in Higher Education of the Hungarian Ministry of Human Capacities.