Why does sklearn.grid_search.GridSearchCV return random results on every execution?

Question

I was trying to get the optimum features for a decision tree classifier over the Iris dataset using sklearn.grid_search.GridSearchCV. I used StratifiedKFold (sklearn.cross_validation.StratifiedKFold) for cross-validation, since my data was biased. But on every execution of GridSearchCV, it returned a different set of parameters. Shouldn't it return the same set of optimum parameters given that the data and the cross-validation was same every single time?

Source code follows:

from sklearn.tree import DecisionTreeClassifier
from sklearn.grid_search import GridSearchCV

decision_tree_classifier = DecisionTreeClassifier()

parameter_grid = {'max_depth': [1, 2, 3, 4, 5],
                  'max_features': [1, 2, 3, 4]}

cross_validation = StratifiedKFold(all_classes, n_folds=10)

grid_search = GridSearchCV(decision_tree_classifier, param_grid = parameter_grid,
                          cv = cross_validation)

grid_search.fit(all_inputs, all_classes)

print "Best Score: {}".format(grid_search.best_score_)
print "Best params: {}".format(grid_search.best_params_)

Outputs:

Best Score: 0.959731543624
Best params: {'max_features': 2, 'max_depth': 2}

Best Score: 0.973154362416
Best params: {'max_features': 3, 'max_depth': 5}

Best Score: 0.973154362416
Best params: {'max_features': 2, 'max_depth': 5}

Best Score: 0.959731543624
Best params: {'max_features': 3, 'max_depth': 3}

This is an excerpt from an Ipython notebook which I made recently, with reference to Randal S Olson's notebook, which can be found here.

Answer 1

You can avoid this by using any value for random_state parameter as mentioned in documentation:

random_state : int, RandomState instance or None, optional (default=None) If int, random_state is the seed used by the random number generator; If RandomState instance, random_state is the random number generator; If None, the random number generator is the RandomState instance used by np.random.

example: try DecisionTreeClassifier(random_state=0)

Explaination:

This occurs because, you are not using a random_state variable while declaring decision_tree_classifier = DecisionTreeClassifier() .

So, each time a different Decision Tree is generated because:

Decision trees can be unstable because small variations in the data might result in a completely different tree being generated. This problem is mitigated by using decision trees within an ensemble.

This is also mentioned in interface Documentation:

The problem of learning an optimal decision tree is known to be NP-complete under several aspects of optimality and even for simple concepts. Consequently, practical decision-tree learning algorithms are based on heuristic algorithms such as the greedy algorithm where locally optimal decisions are made at each node. Such algorithms cannot guarantee to return the globally optimal decision tree. This can be mitigated by training multiple trees in an ensemble learner, where the features and samples are randomly sampled with replacement.