title: How to use Dynamic Time warping with kNN in python
body: <p>I have a time-series dataset with two lables (<code>0</code> and <code>1</code>). I am using <em>Dynamic Time Warping (DTW)</em> as a similarity measure for classification using k-nearest neighbour (kNN) as described in these two wonderful blog posts:</p>
  
  <ul>
  <li><a href="https://nbviewer.jupyter.org/github/markdregan/K-Nearest-Neighbors-with-Dynamic-Time-Warping/blob/master/K_Nearest_Neighbor_Dynamic_Time_Warping.ipynb" rel="noreferrer">https://nbviewer.jupyter.org/github/markdregan/K-Nearest-Neighbors-with-Dynamic-Time-Warping/blob/master/K_Nearest_Neighbor_Dynamic_Time_Warping.ipynb</a></li>
  <li><p><a href="http://alexminnaar.com/2014/04/16/Time-Series-Classification-and-Clustering-with-Python.html" rel="noreferrer">http://alexminnaar.com/2014/04/16/Time-Series-Classification-and-Clustering-with-Python.html</a></p>
  
  <pre><code>Arguments
  ---------
  n_neighbors : int, optional (default = 5)
      Number of neighbors to use by default for KNN
  
  max_warping_window : int, optional (default = infinity)
      Maximum warping window allowed by the DTW dynamic
      programming function
  
  subsample_step : int, optional (default = 1)
      Step size for the timeseries array. By setting subsample_step = 2,
      the timeseries length will be reduced by 50% because every second
      item is skipped. Implemented by x[:, ::subsample_step]
  """
  
  def __init__(self, n_neighbors=5, max_warping_window=10000, subsample_step=1):
      self.n_neighbors = n_neighbors
      self.max_warping_window = max_warping_window
      self.subsample_step = subsample_step
  
  def fit(self, x, l):
      """Fit the model using x as training data and l as class labels
  
      Arguments
      ---------
      x : array of shape [n_samples, n_timepoints]
          Training data set for input into KNN classifer
  
      l : array of shape [n_samples]
          Training labels for input into KNN classifier
      """
  
      self.x = x
      self.l = l
  
  def _dtw_distance(self, ts_a, ts_b, d = lambda x,y: abs(x-y)):
      """Returns the DTW similarity distance between two 2-D
      timeseries numpy arrays.
  
      Arguments
      ---------
      ts_a, ts_b : array of shape [n_samples, n_timepoints]
          Two arrays containing n_samples of timeseries data
          whose DTW distance between each sample of A and B
          will be compared
  
      d : DistanceMetric object (default = abs(x-y))
          the distance measure used for A_i - B_j in the
          DTW dynamic programming function
  
      Returns
      -------
      DTW distance between A and B
      """
  
      # Create cost matrix via broadcasting with large int
      ts_a, ts_b = np.array(ts_a), np.array(ts_b)
      M, N = len(ts_a), len(ts_b)
      cost = sys.maxint * np.ones((M, N))
  
      # Initialize the first row and column
      cost[0, 0] = d(ts_a[0], ts_b[0])
      for i in xrange(1, M):
          cost[i, 0] = cost[i-1, 0] + d(ts_a[i], ts_b[0])
  
      for j in xrange(1, N):
          cost[0, j] = cost[0, j-1] + d(ts_a[0], ts_b[j])
  
      # Populate rest of cost matrix within window
      for i in xrange(1, M):
          for j in xrange(max(1, i - self.max_warping_window),
                          min(N, i + self.max_warping_window)):
              choices = cost[i - 1, j - 1], cost[i, j-1], cost[i-1, j]
              cost[i, j] = min(choices) + d(ts_a[i], ts_b[j])
  
      # Return DTW distance given window 
      return cost[-1, -1]
  
  def _dist_matrix(self, x, y):
      """Computes the M x N distance matrix between the training
      dataset and testing dataset (y) using the DTW distance measure
  
      Arguments
      ---------
      x : array of shape [n_samples, n_timepoints]
  
      y : array of shape [n_samples, n_timepoints]
  
      Returns
      -------
      Distance matrix between each item of x and y with
          shape [training_n_samples, testing_n_samples]
      """
  
      # Compute the distance matrix        
      dm_count = 0
  
      # Compute condensed distance matrix (upper triangle) of pairwise dtw distances
      # when x and y are the same array
      if(np.array_equal(x, y)):
          x_s = np.shape(x)
          dm = np.zeros((x_s[0] * (x_s[0] - 1)) // 2, dtype=np.double)
  
          p = ProgressBar(shape(dm)[0])
  
          for i in xrange(0, x_s[0] - 1):
              for j in xrange(i + 1, x_s[0]):
                  dm[dm_count] = self._dtw_distance(x[i, ::self.subsample_step],
                                                    y[j, ::self.subsample_step])
  
                  dm_count += 1
                  p.animate(dm_count)
  
          # Convert to squareform
          dm = squareform(dm)
          return dm
  
      # Compute full distance matrix of dtw distnces between x and y
      else:
          x_s = np.shape(x)
          y_s = np.shape(y)
          dm = np.zeros((x_s[0], y_s[0])) 
          dm_size = x_s[0]*y_s[0]
  
          p = ProgressBar(dm_size)
  
          for i in xrange(0, x_s[0]):
              for j in xrange(0, y_s[0]):
                  dm[i, j] = self._dtw_distance(x[i, ::self.subsample_step],
                                                y[j, ::self.subsample_step])
                  # Update progress bar
                  dm_count += 1
                  p.animate(dm_count)
  
          return dm
  
  def predict(self, x):
      """Predict the class labels or probability estimates for 
      the provided data
  
      Arguments
      ---------
        x : array of shape [n_samples, n_timepoints]
            Array containing the testing data set to be classified
  
      Returns
      -------
        2 arrays representing:
            (1) the predicted class labels 
            (2) the knn label count probability
      """
  
      dm = self._dist_matrix(x, self.x)
  
      # Identify the k nearest neighbors
      knn_idx = dm.argsort()[:, :self.n_neighbors]
  
      # Identify k nearest labels
      knn_labels = self.l[knn_idx]
  
      # Model Label
      mode_data = mode(knn_labels, axis=1)
      mode_label = mode_data[0]
      mode_proba = mode_data[1]/self.n_neighbors
  
      return mode_label.ravel(), mode_proba.ravel()
  </code></pre></li>
  </ul>
  
  <p>However, for classification with kNN the two posts use their own kNN algorithms.</p>
  
  <p>I want to use sklearn's options such as <code>gridsearchcv</code> in my classification. Therefore, I would like to know how I can use Dynamic Time Warping (DTW) with sklearn kNN.</p>
  
  <p><strong>Note: I am not limited to <code>sklearn</code> and happy to receive answers in other libraries as well</strong></p>
  
  <p>I am happy to provide more details if needed.</p>