Repository: scikit-learn/scikit-learn
Pull request: [MRG+1] fix StratifiedShuffleSplit with 2d y
#### Fixes #9037


#### What does this implement/fix?

StratifiedShuffleSplit gives unexpected results if given a 2d y, such as a multi-label or multi-task indicator matrix: basically the current behaviour implicitly flattens y, which makes the indices meaningless.

This fix computes the split indices by replacing each row of y with a unique hash. In the multi-label case this corresponds to considering the whole set of active labels as the label for that sample.

This is a WIP since I might have missed some use cases where this is not appropriate.


Problem statement:
StratifiedShuffleSplit generates overlapping train and test indices for multilabel data
#### Description
StratifiedShuffleSplit generates train and test indices which overlap when based on multilabel data.

#### Steps/Code to Reproduce
```python
from sklearn.model_selection import StratifiedShuffleSplit
from sklearn.utils.testing import assert_equal

X = [['A', 'B'], ['C', 'B'], ['A', 'A'], ['A', 'B']]
y = [['0', '1'], ['1', '1'], ['1', '1'], ['0', '1']]

sss = StratifiedShuffleSplit(n_splits=1, test_size=0.5, random_state=3)

for train_index, test_index in sss.split(X, y):
    train = set(train_index)
    test = set(test_index)
    assert_equal(train.intersection(test), set())
```

#### Expected Results
StratifiedShuffleSplit should either handle multilabel data correctly resulting in non-onverlapping train and test indices or present an error message indicating that multilabel is not supported.

#### Actual Results
In case of multilabel data, StratifiedShuffleSplit generates overlapping train and test indices without any warning or error message.

#### Versions
Windows-10-10.0.14393-SP0
Python 3.5.2 |Continuum Analytics, Inc.| (default, Jul  5 2016, 11:41:13) [MSC v.1900 64 bit (AMD64)]
NumPy 1.11.3
SciPy 0.18.1
Scikit-Learn 0.18.1

Hints from issue discussion:
Looks like a bug. For reference, the returned split here is `train_idx=[3, 1]; test_idx=[3, 2]`.

Supporting multi-label sounds tricky to me: what would your desired behaviour be other than simply non-overlapping? Strive for a similar ratio of all unique label sets?

Unless there is some established approach that I'm not familiar with, I would support raising a ValueError here.
Multi-label sampling can indeed be tricky.
I did find some paper on the subject which contained two different approaches:
1. Sample on all different combinations of labels
2. Iterative Stratification, changing the distribution of the labels one at a time 
_(Sechidis, K., Tsoumakas, G., & Vlahavas, I. (2011). On the stratification of multi-label data. Machine Learning and Knowledge Discovery in Databases, 145-158.)_ 

However, I propose to keep it simple and just sample on all different combinations of labels.
That's in fact the workaround I used. I just concatenated the multilabel into a single label.
This is broken even in the simple multi-class case if Y is given as an indicator matrix, e.g. `y = np.array([[0, 1], [1, 0], [1, 0], [0, 1]])`

Commit message: regression test and fix for 2d stratified shuffle split

Patch to review:
diff --git a/sklearn/model_selection/_split.py b/sklearn/model_selection/_split.py
index d51487cd1cb4e..d00855eef4a73 100644
--- a/sklearn/model_selection/_split.py
+++ b/sklearn/model_selection/_split.py
@@ -1472,6 +1472,11 @@ def _iter_indices(self, X, y, groups=None):
         y = check_array(y, ensure_2d=False, dtype=None)
         n_train, n_test = _validate_shuffle_split(n_samples, self.test_size,
                                                   self.train_size)
+
+        if y.ndim == 2:
+            # In multi-label case, map each row to a unique identifier:
+            y = np.array([hash(tuple(row)) for row in y])
+
         classes, y_indices = np.unique(y, return_inverse=True)
         n_classes = classes.shape[0]
 
diff --git a/sklearn/model_selection/tests/test_split.py b/sklearn/model_selection/tests/test_split.py
index 546609f413c15..a99f1818ee3bf 100644
--- a/sklearn/model_selection/tests/test_split.py
+++ b/sklearn/model_selection/tests/test_split.py
@@ -667,6 +667,15 @@ def test_stratified_shuffle_split_overlap_train_test_bug():
     assert_array_equal(np.intersect1d(train, test), [])
 
 
+def test_stratified_shuffle_split_multilabel():
+    # issue 9037
+    for y in [np.array([[0, 1], [1, 0], [1, 0], [0, 1]]),
+              np.array([[0, 1], [1, 1], [1, 1], [0, 1]])]:
+        X = np.ones_like(y)
+        sss = StratifiedShuffleSplit(n_splits=1, test_size=0.5, random_state=0)
+        train, test = next(iter(sss.split(X=X, y=y)))
+        assert_array_equal(np.intersect1d(train, test), [])
+
 def test_predefinedsplit_with_kfold_split():
     # Check that PredefinedSplit can reproduce a split generated by Kfold.
     folds = -1 * np.ones(10)


Code review comments:
diff_hunk: @@ -667,6 +667,15 @@ def test_stratified_shuffle_split_overlap_train_test_bug():
     assert_array_equal(np.intersect1d(train, test), [])
 
 
+def test_stratified_shuffle_split_multilabel():
+    # issue 9037
+    for y in [np.array([[0, 1], [1, 0], [1, 0], [0, 1]]),
path: sklearn/model_selection/tests/test_split.py
text: @user1:
we don't support list of labels right now, right?

@author:
not afaik, why? This is supposed to be a multi-label indicator Y. 

@author:
I could build it explicitly with a (Multi)LabelBinarizer if it makes the test clearer?