Return to Answer

EDIT2: While this removes the stochasticity component of the training, the decision trees would still be different because they are trained sequentially, and, while they may share the same random_state, the second tree will sample different random numbers than the first. The thing is that sklearn ensembles generate a new random seed for each child based on the random state they are given. They do not pass along the same random_state.

EDIT2: While this removes the stochasticity component of the training, the decision trees would still be different. The thing is that sklearn ensembles generate a new random seed for each child based on the random state they are given. They do not pass along the same random_state.

The short answer is that you did not pass random_state to RandomForestClassifier.

First things first. The DecisionTreeClassifier has some stochastic behavior. For instance, the splitter code iterates through the features at random:

Summary: Each DecisionTreeClassifier is stochastic, data such as yours, which is small and comes from the same distribution, are bound to produce slightly different trees, even if the random forest itself is deterministic. You can fix this by passing the same seed to each DecisionTreeClassifier which you can do using random_state=something. RandomForestClassifier also has a random_state parameter which it passes along each DecisionTreeClassifier.

EDIT: a previous version of this answer said that RandomForestClassifier was not passing along random_state to each DecisionTreeClassifier. This was wrong, and was removed.

First things first. The DecisionTreeClassifier has some stochastic behavior. For instance, the splitter code iterates through the features at random:

Summary: Each DecisionTreeClassifier is stochastic, data such as yours, which is small and comes from the same distribution, are bound to produce slightly different trees, even if the random forest itself is deterministic. You can fix this by passing the same seed to each DecisionTreeClassifier which you can do using random_state=something. RandomForestClassifier also has a random_state parameter which it passes along each DecisionTreeClassifier. (This is slightly incorrect, see the edit.)

EDIT2: While this removes the stochasticity component of the training, the decision trees would still be different because they are trained sequentially, and, while they may share the same random_state, the second tree will sample different random numbers than the first. The thing is that sklearn ensembles generate a new random seed for each child based on the random state they are given. They do not pass along the same random_state.

You can see this is the case by checking the _set_random_states method from the ensemble base module, in particular this line, which propagates the random_state across the ensembles' children.

The short answer is that random_state from RandomForestClassifier does not work as you think it does. Not sure if this is a bug or not.

This answers part of the question, but does not answer the question fully.

I can hear you thinking:

Even if each DecisionTreeClassifier has some randomness to it, I have used RandomForestClassifier(..., random_state=1), therefore all trees should be identical, right?

(Actually, re-reading your question, I see that you have not done this. But suppose that you did.)

I don't know why, but RandomForestClassifier does not pass along random_state to each DecisionTreeClassifier. You can clearly see that this is the problem by implementing your own random forest, and trying to enable and disable random_state to each DecisionTreeClassifier.

Here, I have done that work for you:

It produces different scores using the sklearn implementation of random forest, but the same scores using my implementation. HOWEVER, if you disable random_state=1 from each tree that I build, you can see that scores become different.

Summary: Clearly, RandomForestClassifier is not passing along the random_state you defined to each DecisionTreeClassifier. While each two random forest with the same hyperparameters are identical, the same is not true to the trees within each random forest. (This could be a bug; I don't know.) But since each DecisionTreeClassifier is stochastic, data such as yours, which is small and comes from the same distribution, are bound to produce slightly different trees, even if the random forest itself is deterministic.

The short answer is that you did not pass random_state to RandomForestClassifier.

To clarify: if the algorithm computes the score for feature A and then computes the score for feature B and it gets score N. Or if it computes first the score for feature B and then for feature A and it gets the same score N, you can see how each decision tree will be different, and have different scores during test, even if the train test is the same (100% if max_depth=None of course). (You can confirm this.)

During my exploration of your question, I have produced the following code with my own implementation of a random forest. Since it took me some time, I figured I might as well paste it here. :) Seriously, it can be useful. You can try to disable random_state from my implementation to see what I mean.

Summary: Each DecisionTreeClassifier is stochastic, data such as yours, which is small and comes from the same distribution, are bound to produce slightly different trees, even if the random forest itself is deterministic. You can fix this by passing the same seed to each DecisionTreeClassifier which you can do using random_state=something. RandomForestClassifier also has a random_state parameter which it passes along each DecisionTreeClassifier.

EDIT: a previous version of this answer said that RandomForestClassifier was not passing along random_state to each DecisionTreeClassifier. This was wrong, and was removed.