# Dynamic Time Warping K-Nearest Neighbors¶

$$k$$-nearest neigbors ($$k$$-NN) is an algorithm for identifying the observations most similar to an example.

By combining $$k$$-NN with dynamic time warping as a distance measure, $$k$$-NN can be used as an effective method of sequence classification and regression.

## Recap of general $$k$$-NN¶

Suppose we have a dataset $$\mathcal{D}_\text{train}=\big\{\mathbf{x}^{(n)}\big\}_{n=1}^N$$ with $$N$$ training examples, such that $$\mathbf{x}^{(n)}\in\mathbb{R}^D$$.

When querying against a new example $$\mathbf{x}'\in\mathbb{R}^D$$, the $$k$$-NN algorithm does the following:

1. Computes the distance from $$\mathbf{x}'$$ to every training example in $$\mathcal{D}_\text{train}$$, using a distance measure such as Euclidean distance $$d(\mathbf{x}',\mathbf{x}^{(n)})=\Vert\mathbf{x}'-\mathbf{x}^{(n)}\Vert$$.
2. Obtains a $$k$$-neighborhood $$\mathcal{K}'$$ which is a set of the $$k$$ nearest training examples to $$\mathbf{x}'$$.

Using the intuition that $$\mathbf{x}'$$ being physically close to the examples in $$\mathcal{K}'$$ suggests that they have similar properties, we can use the $$k$$-neighborhood for inference (classification or regression) on $$\mathbf{x}'$$.

## Extending $$k$$-NN to sequences¶

To apply $$k$$-NN to sequences, we use a distance measure that quantifies similarity between sequences.

Sequentia supports multivariate sequences for $$k$$-NN, which can be represented as an ordered sequence of observations $$O=\mathbf{o}^{(1)},\ldots,\mathbf{o}^{(T)}$$, such that $$\mathbf{o}^{(t)}\in\mathbb{R}^D$$. Indeed the lengths of any two observation sequences $$O^{(n)}$$ and $$O^{(m)}$$ may differ.

To compare sequences $$O^{(n)}$$ and $$O^{(m)}$$ we can use the dynamic time warping (DTW) distance measure, which is a dynamic programming algorithm for finding the optimal alignment between two sequences, and can be generalized to higher dimensions.