Repository: alteryx/evalml (python)

Issue:
Data splitting for time series
Requirements:

1. We're going to start with [Rolling Origin Cross Validation](https://robjhyndman.com/hyndsight/tscv/)
2. Estimators should not be scored on the dates that they are fit on.
3. The max_lag and gap values will mean some rows will be "thrown out" because of nans. Let's try to minimize this amount.

Pull request description:
Data split for time series
### Pull Request Description
Fixes #1381.

-----
*After creating the pull request: in order to pass the **release_notes_updated** check you will need to update the "Future Release" section of* `docs/source/release_notes.rst` *to include this pull request by adding :pr:`123`.*


Patch:
diff --git a/docs/source/release_notes.rst b/docs/source/release_notes.rst
index a03b18ae..8c7a4680 100644
--- a/docs/source/release_notes.rst
+++ b/docs/source/release_notes.rst
@@ -16,6 +16,7 @@ Release Notes
         * Added ``DelayedFeaturesTransformer`` :pr:`1396`
         * Added a ``TimeSeriesRegressionPipeline`` class :pr:`1418`
         * Removed ``core-requirements.txt`` from the package distribution :pr:`1429`
+        * Added a ``TimeSeriesSplit`` data splitter for time series problems :pr:`1441`.
     * Fixes
         * Fixed ``IndexError`` raised in ``AutoMLSearch`` when ``ensembling = True`` but only one pipeline to iterate over :pr:`1397`
         * Fixed stacked ensemble input bug and LightGBM warning and bug in ``AutoMLSearch`` :pr:`1388`
diff --git a/evalml/automl/data_splitters/__init__.py b/evalml/automl/data_splitters/__init__.py
index 5904c53a..bab9b9a8 100644
--- a/evalml/automl/data_splitters/__init__.py
+++ b/evalml/automl/data_splitters/__init__.py
@@ -1,1 +1,2 @@
 from .training_validation_split import TrainingValidationSplit
+from .time_series_split import TimeSeriesSplit
diff --git a/evalml/automl/data_splitters/time_series_split.py b/evalml/automl/data_splitters/time_series_split.py
new file mode 100644
index 00000000..956be71c
--- /dev/null
+++ b/evalml/automl/data_splitters/time_series_split.py
@@ -0,0 +1,83 @@
+import numpy as np
+from sklearn.model_selection import TimeSeriesSplit as SkTimeSeriesSplit
+from sklearn.model_selection._split import BaseCrossValidator
+
+
+class TimeSeriesSplit(BaseCrossValidator):
+    """Rolling Origin Cross Validation for time series problems."""
+
+    def __init__(self, max_delay=0, gap=0, n_splits=3):
+        """Create a TimeSeriesSplit.
+
+        This class uses max_delay and gap values to take into account that evalml time series pipelines perform
+        some feature and target engineering, e.g delaying input features and shifting the target variable by the
+        desired amount. If the data that will be split already has all the features and appropriate target values, and
+        then set max_delay and gap to 0.
+
+        Arguments:
+            max_delay (int): Max delay value for feature engineering. Time series pipelines create delayed features
+                from existing features. This process will introduce NaNs into the first max_delay number of rows. The
+                splitter uses the last max_delay number of rows from the previous split as the first max_delay number
+                of rows of the current split to avoid "throwing out" more data than in necessary.
+            gap (int): Gap used in time series problem. Time series pipelines shift the target variable by gap rows
+                since we are interested in
+            """
+        self.max_delay = max_delay
+        self.gap = gap
+        self.n_splits = n_splits
+        self._splitter = SkTimeSeriesSplit(n_splits=n_splits)
+
+    def get_n_splits(self, X=None, y=None, groups=None):
+        """Get the number of data splits."""
+        return self._splitter.n_splits
+
+    @staticmethod
+    def _check_if_empty(data):
+        return data is None or data.empty
+
+    def split(self, X, y=None, groups=None):
+        """Get the time series splits.
+
+        X and y are assumed to be sorted in ascending time order.
+        This method can handle passing in empty or None X and y data but note that X and y cannot be None or empty
+        at the same time.
+
+        Arguments:
+            X (pd.DataFrame, None): Features to split.
+            y (pd.DataFrame, None): Target variable to split.
+            groups: Ignored but kept for compatibility with sklearn api.
+
+        Returns:
+            Iterator of (train, test) indices tuples.
+        """
+        # Sklearn splitters always assume a valid X is passed but we need to support the
+        # TimeSeriesPipeline convention of being able to pass in empty X dataframes
+        # We'll do this by passing X=y if X is empty
+        if self._check_if_empty(X) and self._check_if_empty(y):
+            raise ValueError("Both X and y cannot be None or empty in TimeSeriesSplit.split")
+        elif self._check_if_empty(X) and not self._check_if_empty(y):
+            split_kwargs = dict(X=y, groups=groups)
+            max_index = y.shape[0]
+        else:
+            split_kwargs = dict(X=X, y=y, groups=groups)
+            max_index = X.shape[0]
+
+        split_size = (max_index // self.n_splits)
+        if split_size < self.gap + self.max_delay:
+            raise ValueError(f"Since the data has {max_index} observations and n_splits={self.n_splits}, "
+                             f"the smallest split would have {split_size} observations. "
+                             f"Since {self.gap + self.max_delay} (gap + max_delay)  > {split_size}, "
+                             "then at least one of the splits would be empty by the time it reaches the pipeline. "
+                             "Please use a smaller number of splits or collect more data.")
+
+        for train, test in self._splitter.split(**split_kwargs):
+            last_train = train[-1]
+            first_test, last_test = test[0], test[-1]
+
+            # Make sure the splits don't extend past our data
+            max_test_index = min(last_test + 1 + self.gap, max_index)
+            max_train_index = min(last_train + 1 + self.gap, max_index)
+
+            new_train = np.arange(0, max_train_index)
+            new_test = np.arange(first_test - self.max_delay, max_test_index)
+            yield new_train, new_test


Test patch:
diff --git a/evalml/tests/automl_tests/test_time_series_split.py b/evalml/tests/automl_tests/test_time_series_split.py
new file mode 100644
index 00000000..58c5a71e
--- /dev/null
+++ b/evalml/tests/automl_tests/test_time_series_split.py
@@ -0,0 +1,56 @@
+import pandas as pd
+import pytest
+
+from evalml.automl.data_splitters import TimeSeriesSplit
+
+
+def test_time_series_split_init():
+    ts_split = TimeSeriesSplit(gap=3, max_delay=4, n_splits=5)
+    assert ts_split.get_n_splits() == 5
+
+    with pytest.raises(ValueError, match="Both X and y cannot be None or empty in TimeSeriesSplit.split"):
+        _ = list(ts_split.split(X=None, y=None))
+
+    with pytest.raises(ValueError, match="Both X and y cannot be None or empty in TimeSeriesSplit.split"):
+        _ = list(ts_split.split(X=pd.DataFrame(), y=pd.Series([])))
+
+
+def test_time_series_split_n_splits_too_big():
+    splitter = TimeSeriesSplit(gap=7, n_splits=4, max_delay=3)
+    X = pd.DataFrame({"features": range(15)})
+    # Each split would have 15 // 5 = 3 data points. However, this is smaller than the number of data_points required
+    # for max_delay and gap
+    with pytest.raises(ValueError, match="Please use a smaller number of splits or collect more data."):
+        list(splitter.split(X))
+
+
+@pytest.mark.parametrize("max_delay,gap", [(0, 0), (1, 0), (2, 0), (0, 3), (1, 1), (4, 2)])
+@pytest.mark.parametrize("X_none,y_none", [(False, False), (True, False), (False, True)])
+def test_time_series_split(max_delay, gap, X_none, y_none):
+    X = pd.DataFrame({"features": range(1, 32)})
+    y = pd.Series(range(1, 32))
+
+    # Splitter does not need a daterange index. We use a daterange index so that the
+    # expected answer is easier to understand
+    y.index = pd.date_range("2020-10-01", "2020-10-31")
+    X.index = pd.date_range("2020-10-01", "2020-10-31")
+
+    answer = [(pd.date_range("2020-10-01", f"2020-10-{10 + gap}"), pd.date_range(f"2020-10-{11 - max_delay}", f"2020-10-{17 + gap}")),
+              (pd.date_range("2020-10-01", f"2020-10-{17 + gap}"), pd.date_range(f"2020-10-{18 - max_delay}", f"2020-10-{24 + gap}")),
+              (pd.date_range("2020-10-01", f"2020-10-{24 + gap}"), pd.date_range(f"2020-10-{25 - max_delay}", "2020-10-31"))]
+
+    if X_none:
+        X = None
+    if y_none:
+        y = None
+
+    ts_split = TimeSeriesSplit(gap=gap, max_delay=max_delay)
+    for i, (train, test) in enumerate(ts_split.split(X, y)):
+        if not X_none:
+            X_train, X_test = X.iloc[train], X.iloc[test]
+            pd.testing.assert_index_equal(X_train.index, answer[i][0])
+            pd.testing.assert_index_equal(X_test.index, answer[i][1])
+        if not y_none:
+            y_train, y_test = y.iloc[train], y.iloc[test]
+            pd.testing.assert_index_equal(y_train.index, answer[i][0])
+            pd.testing.assert_index_equal(y_test.index, answer[i][1])