Repository: scikit-learn/scikit-learn
Pull request: DOC/TST Clarify group order in GroupKFold and LeaveOneGroupOut
<!--
Thanks for contributing a pull request! Please ensure you have taken a look at
the contribution guidelines: https://github.com/scikit-learn/scikit-learn/blob/main/CONTRIBUTING.md
-->

#### Reference Issues/PRs
<!--
Example: Fixes #1234. See also #3456.
Please use keywords (e.g., Fixes) to create link to the issues or pull requests
you resolved, so that they will automatically be closed when your pull request
is merged. See https://github.com/blog/1506-closing-issues-via-pull-requests
-->

Fixes #18338


#### What does this implement/fix? Explain your changes.

- I have added notes to the docstrings of GroupKFold and LeaveOneGroupOut explaining that in the former groups are distributed in an arbitrary order between folds, while in the latter the splits are ordered according to the index of the group left out.
- I added a test to make sure that LeaveOneGroupOut does indeed order the splits in this way.


#### Any other comments?

- Concerning the order in GroupKFold:
    * The order of the groups in the folds calculated by GroupKFold depends on the numpy implementation of `argsort`. (In GroupKFold [line 526](https://github.com/scikit-learn/scikit-learn/blob/691972a7cf04e7a8918b907556b4e9904f82bd0c/sklearn/model_selection/_split.py#L526) we take the indices which sort the array of group sizes. Two groups of the same size may be swapped if we don't use a stable sorting algorithm.)
    * This was implementation was actually changed in numpy version 1.12.0, from a quicksort to introsort.
    * We could make this stable across numpy versions by using a stable sorting algorithm (e.g. we can just pass `kind="stable"` to `argsort`)
- Comparing to other cross validators in _split.py:
    * It might be good to mention the default ordering in the docstrings of other cvs.
    * Other cvs have a `shuffle` option. In #18338 one possible suggestion is with respect to GroupKFold is:
        > add an option to shuffle in whichever ways possible, and then explicitly document the limitations.

<!--
Please be aware that we are a loose team of volunteers so patience is
necessary; assistance handling other issues is very welcome. We value
all user contributions, no matter how minor they are. If we are slow to
review, either the pull request needs some benchmarking, tinkering,
convincing, etc. or more likely the reviewers are simply busy. In either
case, we ask for your understanding during the review process.
For more information, see our FAQ on this topic:
http://scikit-learn.org/dev/faq.html#why-is-my-pull-request-not-getting-any-attention.

Thanks for contributing!
-->


Problem statement:
Clarify group order in GroupKFold and LeaveOneGroupOut
#### Describe the bug
`GroupKFold` builds folds with non-overlapping groups in it. The order of the groups seems random and not sorted by group ID. A naiv user like me expects the groups to be ordered over the folds.

#### Steps/Code to Reproduce
```python
import numpy as np
from sklearn.model_selection import GroupKFold


n_splits, n_samples, n_features = 3, 2, 2
X = np.arange(n_splits * n_samples * n_features).reshape(n_splits * n_samples, n_features)
groups = np.concatenate([np.full(n_samples, i) for i in range(n_splits)])
splits = list(GroupKFold(n_splits=n_splits).split(X, groups=groups))
[(np.unique(groups[train]), np.unique(groups[test])) for train, test in splits]
```
Results show group ID of train and test folds:
```python
[(array([0, 1]), array([2])),
 (array([0, 2]), array([1])),
 (array([1, 2]), array([0]))]
```
Now we add a few samples to the first group (group ID = 0).
```
X = np.r_[X[:n_samples, :], X]
groups = np.r_[groups[:n_samples], groups]
splits = list(GroupKFold(n_splits=n_splits).split(X, groups=groups))
[(np.unique(groups[train]), np.unique(groups[test])) for train, test in splits]
```
Result:
```python
[(array([1, 2]), array([0])),
 (array([0, 1]), array([2])),
 (array([0, 2]), array([1]))]
```

#### Expected Results
I expect the same (first) output for both:
```python
[(array([0, 1]), array([2])),
 (array([0, 2]), array([1])),
 (array([1, 2]), array([0]))]
```

#### Versions
python: 3.7.2
sklearn: 0.24.dev0 (current master as of today morning)

Hints from issue discussion:
what cv objects should guarantee is that order does not change every time you call split. I am more wondering why you have no shuffle and random_state parameters in GroupKFold to match the KFold API.

unless the need you report is quite common I would write my own code / private function/object to do what you suggest
GroupKFold is a deterministic packing algorithm. It's not possible to shuffle except among groups of equal size, and to shuffle samples within groups. This has surprised several users. We should either enhance the documentation, or add an option to shuffle in whichever ways possible, and then explicitly document the limitations.
ok got it makes sense.

@lorentzenchr for your use in linear models I would suggest you try: LeaveOneGroupOut

I think it does what you want here.
@agramfort `LeaveOneGroupOut` does indeed preserve the order of the groups if samples are added as in the code snippet above.

I wonder if that is by chance or behaviour that can be relied upon.
Read the code to check 

Of course, it is not by chance (`LeaveOneGroupOut._iter_test_masks` as compared to `GroupKFold._iter_test_indices`). But it is also not mentioned in the docs. So my question should have better been: Is it something that we want to guarantee and mention in the documentation or not?
+1 to say this in the documentation and ensure that we have test
that would break otherwise

>

> +1 to say this in the documentation and ensure that we have test
that would break otherwise

Help wanted:smiley:
If this is still open, may I work on this? I am a first-time contributor @lorentzenchr. 
take

Commit message: Clarify group order in GroupKFold and LeaveOneGroupOut

Patch to review:
diff --git a/sklearn/model_selection/_split.py b/sklearn/model_selection/_split.py
index e2939f6d96096..b1c438c8b91aa 100644
--- a/sklearn/model_selection/_split.py
+++ b/sklearn/model_selection/_split.py
@@ -496,6 +496,10 @@ class GroupKFold(_BaseKFold):
      [7 8]] [[1 2]
      [3 4]] [3 4] [1 2]
 
+    Notes
+    -----
+    Groups appear in an arbitrary order throughout the folds.
+
     See Also
     --------
     LeaveOneGroupOut : For splitting the data according to explicit
@@ -1138,6 +1142,11 @@ class LeaveOneGroupOut(BaseCrossValidator):
      [3 4]] [[5 6]
      [7 8]] [1 2] [1 2]
 
+    Notes
+    -----
+    Splits are ordered according to the index of the group left out. The first
+    split has training set consting of the group whose index in `groups` is
+    lowest, and so on.
     """
 
     def _iter_test_masks(self, X, y, groups):
diff --git a/sklearn/model_selection/tests/test_split.py b/sklearn/model_selection/tests/test_split.py
index b0e8ee126a7c4..95b6133a6404a 100644
--- a/sklearn/model_selection/tests/test_split.py
+++ b/sklearn/model_selection/tests/test_split.py
@@ -1041,6 +1041,27 @@ def test_leave_group_out_changing_groups():
     assert 3 == LeaveOneGroupOut().get_n_splits(X, y=X, groups=groups)
 
 
+def test_leave_group_out_order_dependence():
+    # Check that LeaveOneGroupOut orders the splits according to the index
+    # of the group left out.
+    groups = np.array([2, 2, 0, 0, 1, 1])
+    X = np.ones(len(groups))
+
+    splits = iter(LeaveOneGroupOut().split(X, groups=groups))
+
+    train, test = next(splits)
+    assert_array_equal(train, [0, 1, 4, 5])
+    assert_array_equal(test, [2, 3])
+
+    train, test = next(splits)
+    assert_array_equal(train, [0, 1, 2, 3])
+    assert_array_equal(test, [4, 5])
+
+    train, test = next(splits)
+    assert_array_equal(train, [2, 3, 4, 5])
+    assert_array_equal(test, [0, 1])
+
+
 def test_leave_one_p_group_out_error_on_fewer_number_of_groups():
     X = y = groups = np.ones(0)
     msg = re.escape("Found array with 0 sample(s)")


Code review comments:
diff_hunk: @@ -1138,6 +1142,11 @@ class LeaveOneGroupOut(BaseCrossValidator):
      [3 4]] [[5 6]
      [7 8]] [1 2] [1 2]
 
+    Notes
path: sklearn/model_selection/_split.py
text: @user1:
Could you move this section above the example section