Repository: aeon-toolkit/aeon
Pull request #1323 (2024-03-18 09:01:06)

[ENH] Capability to use shape-dtw on precomputed transformation
The PR adds a capability to use shape-dtw on pre-computed transformation.

This is for 2 reasons:

1- suppose someone wants to use a transformation we dont have in aeon
2- this is a pre-refactor to fix the ShapeDTWClassifier because it assumes that shapeDTW(x,y)=DTW(f(x),f(y)) which is wrong and this capability will make the refactor much easier


Patch:
diff --git a/aeon/distances/_distance.py b/aeon/distances/_distance.py
index f8f13ac9..7c6517e7 100644
--- a/aeon/distances/_distance.py
+++ b/aeon/distances/_distance.py
@@ -182,6 +182,9 @@ def distance(
             itakura_max_slope=kwargs.get("itakura_max_slope"),
             descriptor=kwargs.get("descriptor", "identity"),
             reach=kwargs.get("reach", 30),
+            transformation_precomputed=kwargs.get("transformation_precomputed", False),
+            transformed_x=kwargs.get("transformed_x", None),
+            transformed_y=kwargs.get("transformed_y", None),
         )
     elif metric == "wddtw":
         return wddtw_distance(
@@ -337,6 +340,9 @@ def pairwise_distance(
             itakura_max_slope=kwargs.get("itakura_max_slope"),
             descriptor=kwargs.get("descriptor", "identity"),
             reach=kwargs.get("reach", 30),
+            transformation_precomputed=kwargs.get("transformation_precomputed", False),
+            transformed_x=kwargs.get("transformed_x", None),
+            transformed_y=kwargs.get("transformed_y", None),
         )
     elif metric == "ddtw":
         return ddtw_pairwise_distance(
@@ -539,6 +545,9 @@ def alignment_path(
             itakura_max_slope=kwargs.get("itakura_max_slope"),
             descriptor=kwargs.get("descriptor", "identity"),
             reach=kwargs.get("reach", 30),
+            transformation_precomputed=kwargs.get("transformation_precomputed", False),
+            transformed_x=kwargs.get("transformed_x", None),
+            transformed_y=kwargs.get("transformed_y", None),
         )
     elif metric == "ddtw":
         return ddtw_alignment_path(
@@ -679,6 +688,9 @@ def cost_matrix(
             itakura_max_slope=kwargs.get("itakura_max_slope"),
             descriptor=kwargs.get("descriptor", "identity"),
             reach=kwargs.get("reach", 30),
+            transformation_precomputed=kwargs.get("transformation_precomputed", False),
+            transformed_x=kwargs.get("transformed_x", None),
+            transformed_y=kwargs.get("transformed_y", None),
         )
     elif metric == "ddtw":
         return ddtw_cost_matrix(
diff --git a/aeon/distances/_shape_dtw.py b/aeon/distances/_shape_dtw.py
index cd51e61d..58ce329f 100644
--- a/aeon/distances/_shape_dtw.py
+++ b/aeon/distances/_shape_dtw.py
@@ -123,6 +123,9 @@ def shape_dtw_distance(
     descriptor: str = "identity",
     reach: int = 30,
     itakura_max_slope: Optional[float] = None,
+    transformation_precomputed: bool = False,
+    transformed_x: Optional[np.ndarray] = None,
+    transformed_y: Optional[np.ndarray] = None,
 ) -> float:
     """Compute the ShapeDTW distance function between two series x and y.
 
@@ -156,6 +159,12 @@ def shape_dtw_distance(
     itakura_max_slope : float, default=None
         Maximum slope as a proportion of the number of time points used to create
         Itakura parallelogram on the bounding matrix. Must be between 0. and 1.
+    transformation_precomputed : bool, default = False
+        To choose if the transformation of the sub-sequences is pre-computed or not.
+    transformed_x : np.ndarray, default = None
+        The transformation of x, ignored if transformation_precomputed is False.
+    transformed_y : np.ndarray, default = None
+        The transformation of y, ignored if transformation_precomputed is False.
 
     Returns
     -------
@@ -194,6 +203,9 @@ def shape_dtw_distance(
             descriptor=descriptor,
             reach=reach,
             bounding_matrix=bounding_matrix,
+            transformation_precomputed=transformation_precomputed,
+            transformed_x=transformed_x,
+            transformed_y=transformed_y,
         )
     if x.ndim == 2 and y.ndim == 2:
         x_pad = _pad_ts_edges(x=x, reach=reach)
@@ -209,6 +221,9 @@ def shape_dtw_distance(
             descriptor=descriptor,
             reach=reach,
             bounding_matrix=bounding_matrix,
+            transformation_precomputed=transformation_precomputed,
+            transformed_x=transformed_x,
+            transformed_y=transformed_y,
         )
 
     raise ValueError("x and y must be 1D or 2D")
@@ -221,13 +236,27 @@ def _shape_dtw_distance(
     bounding_matrix: np.ndarray,
     descriptor: str = "identity",
     reach: int = 30,
+    transformation_precomputed: bool = False,
+    transformed_x: Optional[np.ndarray] = None,
+    transformed_y: Optional[np.ndarray] = None,
 ) -> float:
-    new_x = _transform_subsequences(x=x, descriptor=descriptor, reach=reach)
-    new_y = _transform_subsequences(x=y, descriptor=descriptor, reach=reach)
-
-    shape_dtw_cost_mat = _dtw_cost_matrix(
-        x=new_x, y=new_y, bounding_matrix=bounding_matrix
-    )
+    # for compilation purposes
+    if transformed_x is None:
+        transformed_x = x
+    if transformed_y is None:
+        transformed_y = y
+
+    if not transformation_precomputed:
+        new_x = _transform_subsequences(x=x, descriptor=descriptor, reach=reach)
+        new_y = _transform_subsequences(x=y, descriptor=descriptor, reach=reach)
+
+        shape_dtw_cost_mat = _dtw_cost_matrix(
+            x=new_x, y=new_y, bounding_matrix=bounding_matrix
+        )
+    else:
+        shape_dtw_cost_mat = _dtw_cost_matrix(
+            x=transformed_x, y=transformed_y, bounding_matrix=bounding_matrix
+        )
 
     return _get_shape_dtw_distance_from_cost_mat(
         x=x, y=y, reach=reach, shape_dtw_cost_mat=shape_dtw_cost_mat
@@ -268,6 +297,9 @@ def shape_dtw_cost_matrix(
     descriptor: str = "identity",
     reach: int = 30,
     itakura_max_slope: Optional[float] = None,
+    transformation_precomputed: bool = False,
+    transformed_x: Optional[np.ndarray] = None,
+    transformed_y: Optional[np.ndarray] = None,
 ) -> np.ndarray:
     """Compute the ShapeDTW cost matrix between two series x and y.
 
@@ -298,6 +330,12 @@ def shape_dtw_cost_matrix(
     itakura_max_slope : float, default=None
         Maximum slope as a proportion of the number of time points used to create
         Itakura parallelogram on the bounding matrix. Must be between 0. and 1.
+    transformation_precomputed : bool, default = False
+        To choose if the transformation of the sub-sequences is pre-computed or not.
+    transformed_x : np.ndarray, default = None
+        The transformation of x, ignored if transformation_precomputed is False.
+    transformed_y : np.ndarray, default = None
+        The transformation of y, ignored if transformation_precomputed is False.
 
     Returns
     -------
@@ -326,6 +364,9 @@ def shape_dtw_cost_matrix(
             descriptor=descriptor,
             reach=reach,
             bounding_matrix=bounding_matrix,
+            transformation_precomputed=transformation_precomputed,
+            transformed_x=transformed_x,
+            transformed_y=transformed_y,
         )
     if x.ndim == 2 and y.ndim == 2:
         x_pad = _pad_ts_edges(x=x, reach=reach)
@@ -341,6 +382,9 @@ def shape_dtw_cost_matrix(
             descriptor=descriptor,
             reach=reach,
             bounding_matrix=bounding_matrix,
+            transformation_precomputed=transformation_precomputed,
+            transformed_x=transformed_x,
+            transformed_y=transformed_y,
         )
 
     raise ValueError("x and y must be 1D or 2D")
@@ -353,13 +397,27 @@ def _shape_dtw_cost_matrix(
     bounding_matrix: np.ndarray,
     descriptor: str = "identity",
     reach: int = 30,
+    transformation_precomputed: bool = False,
+    transformed_x: Optional[np.ndarray] = None,
+    transformed_y: Optional[np.ndarray] = None,
 ) -> np.ndarray:
-    new_x = _transform_subsequences(x=x, descriptor=descriptor, reach=reach)
-    new_y = _transform_subsequences(x=y, descriptor=descriptor, reach=reach)
-
-    shapedtw_cost_mat = _dtw_cost_matrix(
-        x=new_x, y=new_y, bounding_matrix=bounding_matrix
-    )
+    # for compilation purposes
+    if transformed_x is None:
+        transformed_x = x
+    if transformed_y is None:
+        transformed_y = y
+
+    if not transformation_precomputed:
+        new_x = _transform_subsequences(x=x, descriptor=descriptor, reach=reach)
+        new_y = _transform_subsequences(x=y, descriptor=descriptor, reach=reach)
+
+        shapedtw_cost_mat = _dtw_cost_matrix(
+            x=new_x, y=new_y, bounding_matrix=bounding_matrix
+        )
+    else:
+        shapedtw_cost_mat = _dtw_cost_matrix(
+            x=transformed_x, y=transformed_y, bounding_matrix=bounding_matrix
+        )
 
     return shapedtw_cost_mat
 
@@ -372,6 +430,9 @@ def shape_dtw_alignment_path(
     descriptor: str = "identity",
     reach: int = 30,
     itakura_max_slope: Optional[float] = None,
+    transformation_precomputed: bool = False,
+    transformed_x: Optional[np.ndarray] = None,
+    transformed_y: Optional[np.ndarray] = None,
 ) -> Tuple[List[Tuple[int, int]], float]:
     """Compute the ShapeDTW alignment path between two series x and y.
 
@@ -402,6 +463,12 @@ def shape_dtw_alignment_path(
     itakura_max_slope : float, default=None
         Maximum slope as a proportion of the number of time points used to create
         Itakura parallelogram on the bounding matrix. Must be between 0. and 1.
+    transformation_precomputed : bool, default = False
+        To choose if the transformation of the sub-sequences is pre-computed or not.
+    transformed_x : np.ndarray, default = None
+        The transformation of x, ignored if transformation_precomputed is False.
+    transformed_y : np.ndarray, default = None
+        The transformation of y, ignored if transformation_precomputed is False.
 
     Returns
     -------
@@ -422,6 +489,9 @@ def shape_dtw_alignment_path(
         descriptor=descriptor,
         reach=reach,
         itakura_max_slope=itakura_max_slope,
+        transformation_precomputed=transformation_precomputed,
+        transformed_x=transformed_x,
+        transformed_y=transformed_y,
     )
 
     if x.ndim == 1 and y.ndim == 1:
@@ -451,6 +521,9 @@ def shape_dtw_pairwise_distance(
     descriptor: str = "identity",
     reach: int = 30,
     itakura_max_slope: Optional[float] = None,
+    transformation_precomputed: bool = False,
+    transformed_x: Optional[np.ndarray] = None,
+    transformed_y: Optional[np.ndarray] = None,
 ) -> np.ndarray:
     """Compute the ShapeDTW pairwise distance among a set of series.
 
@@ -481,6 +554,12 @@ def shape_dtw_pairwise_distance(
     itakura_max_slope : float, default=None
         Maximum slope as a proportion of the number of time points used to create
         Itakura parallelogram on the bounding matrix. Must be between 0. and 1.
+    transformation_precomputed : bool, default = False
+        To choose if the transformation of the sub-sequences is pre-computed or not.
+    transformed_x : np.ndarray, default = None
+        The transformation of x, ignored if transformation_precomputed is False.
+    transformed_y : np.ndarray, default = None
+        The transformation of y, ignored if transformation_precomputed is False.
 
     Returns
     -------
@@ -529,6 +608,9 @@ def shape_dtw_pairwise_distance(
                 descriptor=descriptor,
                 reach=reach,
                 itakura_max_slope=itakura_max_slope,
+                transformation_precomputed=transformation_precomputed,
+                transformed_x=transformed_x,
+                transformed_y=transformed_y,
             )
         if X.ndim == 2:
             _X = X.reshape((X.shape[0], 1, X.shape[1]))
@@ -539,6 +621,9 @@ def shape_dtw_pairwise_distance(
                 descriptor=descriptor,
                 reach=reach,
                 itakura_max_slope=itakura_max_slope,
+                transformation_precomputed=transformation_precomputed,
+                transformed_x=transformed_x,
+                transformed_y=transformed_y,
             )
         raise ValueError("X must be 2D or 3D arrays")
     else:
@@ -553,6 +638,9 @@ def shape_dtw_pairwise_distance(
             descriptor=descriptor,
             reach=reach,
             itakura_max_slope=itakura_max_slope,
+            transformation_precomputed=transformation_precomputed,
+            transformed_x=transformed_x,
+            transformed_y=transformed_y,
         )
 
 
@@ -564,6 +652,9 @@ def _shape_dtw_pairwise_distance(
     descriptor: str = "identity",
     reach: int = 30,
     itakura_max_slope: Optional[float] = None,
+    transformation_precomputed: bool = False,
+    transformed_x: Optional[np.ndarray] = None,
+    transformed_y: Optional[np.ndarray] = None,
 ) -> np.ndarray:
     if y is None:
         y = np.copy(X)
@@ -581,6 +672,9 @@ def _shape_dtw_pairwise_distance(
                 descriptor=descriptor,
                 reach=reach,
                 bounding_matrix=bounding_matrix,
+                transformation_precomputed=transformation_precomputed,
+                transformed_x=transformed_x,
+                transformed_y=transformed_y,
             )
 
     return distances


Test patch:
diff --git a/aeon/distances/tests/test_numba_distance_parameters.py b/aeon/distances/tests/test_numba_distance_parameters.py
index 8ed070d3..22dd729e 100644
--- a/aeon/distances/tests/test_numba_distance_parameters.py
+++ b/aeon/distances/tests/test_numba_distance_parameters.py
@@ -7,6 +7,7 @@ import pytest
 
 from aeon.distances import distance
 from aeon.distances._distance import DISTANCES
+from aeon.distances.tests.test_utils import _generate_shape_dtw_params
 from aeon.testing.expected_results.expected_distance_results import (
     _expected_distance_results_params,
 )
@@ -32,11 +33,19 @@ def _test_distance_params(
     x_multi = make_series(10, 10, return_numpy=True, random_state=1)
     y_multi = make_series(10, 10, return_numpy=True, random_state=2)
 
+    # Shape dtw needs parameters to be generated with the x and y so function used
+    if distance_str == "shape_dtw":
+        param_list.append(_generate_shape_dtw_params)
+
     test_ts = [[x_univ, y_univ], [x_multi, y_multi]]
     results_to_fill = []
 
     i = 0
     for param_dict in param_list:
+        callable_param_dict = None
+        if isinstance(param_dict, Callable):
+            callable_param_dict = param_dict
+
         g_none = False
         if distance_str == "erp" and "g" in param_dict and param_dict["g"] is None:
             g_none = True
@@ -44,6 +53,8 @@ def _test_distance_params(
         j = 0
         curr_results = []
         for x, y in test_ts:
+            if callable_param_dict is not None:
+                param_dict = callable_param_dict(x, y)
             if g_none:
                 _x = x
                 if x.ndim == 1:
@@ -56,8 +67,8 @@ def _test_distance_params(
                 if "g" in param_dict:
                     del param_dict["g"]
             results = [
-                distance_func(x, y, **param_dict),
-                distance(x, y, metric=distance_str, **param_dict),
+                distance_func(x, y, **param_dict.copy()),
+                distance(x, y, metric=distance_str, **param_dict.copy()),
             ]
 
             if distance_str in _expected_distance_results_params:
@@ -91,6 +102,7 @@ DIST_PARAMS = {
     "adtw": BASIC_BOUNDING_PARAMS + [{"warp_penalty": 5.0}],
     "minkowski": [{"p": 1.0}, {"p": 2.0}],
     "sbd": [{"standardize": False}],
+    "shape_dtw": BASIC_BOUNDING_PARAMS + [{"reach": 4}],
 }
 
 
diff --git a/aeon/distances/tests/test_utils.py b/aeon/distances/tests/test_utils.py
index 8fdb9042..fc632ba9 100644
--- a/aeon/distances/tests/test_utils.py
+++ b/aeon/distances/tests/test_utils.py
@@ -3,6 +3,7 @@
 import numpy as np
 import pytest
 
+from aeon.distances._shape_dtw import _pad_ts_edges, _transform_subsequences
 from aeon.distances._utils import reshape_pairwise_to_multiple
 
 SINGLE_POINT_NOT_SUPPORTED_DISTANCES = ["ddtw", "wddtw", "edr"]
@@ -73,3 +74,21 @@ def _make_3d_series(x: np.ndarray) -> np.ndarray:
     else:
         _x = x
     return _x
+
+
+def _generate_shape_dtw_params(x: np.ndarray, y: np.ndarray):
+    if x.ndim == 1:
+        x = x.reshape(1, -1)
+    if y.ndim == 1:
+        y = y.reshape(1, -1)
+    padded_x = _pad_ts_edges(x=x, reach=4)
+    padded_y = _pad_ts_edges(x=y, reach=4)
+
+    transformed_x = _transform_subsequences(x=padded_x, reach=4)
+    transformed_y = _transform_subsequences(x=padded_y, reach=4)
+    return {
+        "transformation_precomputed": True,
+        "transformed_x": transformed_x,
+        "transformed_y": transformed_y,
+        "reach": 10,
+    }
diff --git a/aeon/testing/expected_results/expected_distance_results.py b/aeon/testing/expected_results/expected_distance_results.py
index 735067d9..95dcac1a 100644
--- a/aeon/testing/expected_results/expected_distance_results.py
+++ b/aeon/testing/expected_results/expected_distance_results.py
@@ -159,4 +159,10 @@ _expected_distance_results_params = {
         [15.460501609188993, 108.935882528437],
         [5.45622611835132, 14.285548782488558],
     ],
+    "shape_dtw": [
+        [29.770403454579107, 204.0769040168604],
+        [29.770403454579107, 204.0769040168604],
+        [20.36273099843225, 187.37458448152938],
+        [20.36273099843225, 187.37458448152938],
+    ],
 }