Why the performance of random forest is related to the order of training samples?

Question

everyone! I find that the performance of random forest classifier in python seems to be related to the order of training samples. Can anyone help me to figure out the reason? Thanks very much!

from sklearn.ensemble import RandomForestClassifier
import numpy as np
from sklearn.datasets import load_digits
def shuffle_train():
    digits = load_digits()
    # print digits.data.shape
    cls = RandomForestClassifier(random_state=0,class_weight='balanced')
    ind = np.arange(1000) # take the first 1000 samples as training dataset
    np.random.shuffle(ind)
    training_data = digits.data[ind, :]
    training_label = digits.target[ind] # shuffle the training dataset
    cls.fit(training_data, training_label)

    testing_data = digits.data[1000:, :]
    testing_label = digits.target[1000:]
    testing_pred = cls.predict(testing_data)
    print np.sum(testing_label==testing_pred)


if __name__ == '__main__':
    for i in range(20):
        shuffle_train() # try 20 times and get different results

And this is the output:

714
715
708
701
702
719
708
712
710
714
723
725
726
722
734
714
701
717
717
689

Answer 1

Given how you've written your code, this is expected behavior.

You've set the seed of the random forest explicitly. This means that the same randomization is used. Part of the randomization procedure of a random forest is to construct boot-strapped samples of the data. The way that sklearn accomplishes bootstrapping is to assign weights to indices of samples in $X$. If you change the order of the data in $X$, but fix the seed of the random forest, the same indices will be given bootstrap weights. However, in your code snippet, those indices correspond to different samples (because the data are shuffled), hence the data provided to each tree will be different between runs.

Providing different data to a decision tree results in a very different tree, because trees are high-variance estimators.

If you need to consistent results between different runs, you'll need to impose a fixed ordering on the data in addition to fixing the seed of the random forest.

If you don't need exact correspondence between different runs, but just want results to be approximately the same between runs, you can just increase the number of trees. Increasing the number of trees in a random forest will tend to reduce the variance of the random forest procedure.

Answer 2

To obtain deterministic behavior during fitting you have to set bootstrap=False and max_features=None in addition to the parameters that you have specified when calling RandomForestClassifier().

While I am not familiar with the source code, I guess that the order of the training data leads to different random samples with replacement when bootstrap samples are used to build trees.

What is less clear, why you need to set max_features=None because the subset of features considered in each split should not be a source of randomness when the random state is fixed as in your example. In fact, when you set class_weight=None you can check that the behavior is as expected, i.e. you don't need to set max_features=None to induce deterministic behavior.