I would add a test that if shuffle is True then results depends on random_state for all cv classes that support this.

PR #7823 was included in 0.19.0, so if it's due to that, I don't think it's a regression since 0.19.x.

There's no test here, and I'm quite confused about what's going on.

It seems that what's going on is we currently pass each class's samples to KFold(self.n_splits, shuffle=self.shuffle, random_state=self.random_state). This PR changes it so that instead of passing self.random_state we pass a RandomState that is progressed in each call to KFold. I don't really see why the current code causes the stated bug.

I will also note that I think there are two design errors here that have been raised previously which make this hard to work with:

1. In the sklearn.cross_validation -> sklearn.model_selection rewrite, we did not carefully design what to do with random states. Ideally check_random_state should be called in some fit method, or perhaps in __init__, such that each call to split is different. Instead we landed up calling check_random_state in split, such that you get the surprising behaviour that passing in a RandomState will give different results for each split but passing in an int will give fixed results for each split.
2. StratifiedKFold uses this "apply K fold to each class" which gives some weird (imbalanced) results. We previously had a sort-and-round-robin approach, which I think was rejected for the wrong reasons (all we needed was a stable sort), and it should be reinstated/available as a much simpler approach.

@jnothman I'm aware that there's some design issues (maybe errors) in StratifiedKFold, but my intention here is to fix bugs.
Apologies I didn't describe the problem very well. I've updated the PR body. Please take some time to have a look.

Do you still believe it's a regression since 0.19?

Do you still believe it's a regression since 0.19?

#7823 is included in 0.19.X (not included in 0.18.X), so I think it's a regression.

Right, so a regression introduced in 0.19... so we should not be scheduling it as a 0.20.x fix.

not each stratification, per se, but each class's samples

this term comes from the doc and I've also updated the doc accordingly.

Thanks @Arjannikov and @qinhanmin2014

I think the solution is simpler than the title of this thread suggest.

My personal solution is to shuffle the data before passing it to StratifiedKFold() with shuffle=False. This fixes all problems, however, it renders shuffle=True useless.

Therefore, I think the appropriate solution is to have StratifiedKFold() shuffle the data with the given random seed (we only have one random seed), and then go about things as normal. In this case, KFold() won't need to shuffle, so that option can be turned off.

My personal solution is to shuffle the data before passing it to StratifiedKFold() with shuffle=False. This fixes all problems, however, it renders shuffle=True useless.

I agree that this can solve the problem. I choose another way because we did so previously and I guess there's not too much difference between these two ways.

I don't understand

I mean we can either shuffle the entire dataset or shuffle each class's samples (with a different random_state). I choose the second way because we did so previously (and it's consistent with our doc).

Oh, I wrote "I don't understand" in response to a comment by @Arjannikov that appears to have since been deleted

Oh, my comment was. We only have one random seed. So it makes more sense to do the shuffle once, at the very beginning. But later I thought about using the same random seed for different subsets of the data would work also. So, I deleted my comment. Sorry.

What confuses me is @qinhanmin2014 note: "(with different random_state)".

@qinhanmin2014, where do you get "different random_state"? StartifiedKFold() takes only one integer as random_state parameter.

@qinhanmin2014, where do you get "different random_state"? StartifiedKFold() takes only one integer as random_state parameter.

We can produce different random states using one integer (the random_state parameter).

We can put this in 0.20.X if people want. It should be merged either way (another pro-forma review anyone, or we can accept @NicolasHug's above?)

The 0.20.3 tag has already been pushed without this fix but I think we should include it in the next LTS bugfix release.

Did I fall to cherry pick this? Sorry :(