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_)


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.

  • 1
    $\begingroup$ Although this looks like a Python code question, I think the real issue is understanding the relevant machine learning concepts. I'm voting to leave open. $\endgroup$ Mar 23 '17 at 15:23

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)


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.

  • $\begingroup$ Okay, I get that as long as I set the value of random_state to a fixed value I would get the same set of results (best_params_) for GridSearchCV. But the value of these parameters depend on the value of random_state itself, that is, how the tree is randomly initialized, thereby creating a certain bias. I think that is the reason why we use an ensemble of many decision trees, so that we select the best features. I don't really get the NP-complete part though. $\endgroup$
    – darthy
    Mar 24 '17 at 18:13
  • $\begingroup$ NP refers to "nondeterministic polynomial time". NP complete problems are problems whose status is unknown. No polynomial time algorithm has yet been discovered for any NP complete problem, nor has anybody yet been able to prove that no polynomial-time algorithm exist for any of them. $\endgroup$
    – phanny
    Mar 24 '17 at 18:38
  • 1
    $\begingroup$ For 100% reproducible result, I think you should also include a random_state in the instantiation of the StratifiedKFold. Otherwise, the folds will change. $\endgroup$ Aug 22 '18 at 7:15
  • $\begingroup$ Yeah, it is like a seed for randomisation of the dataset. $\endgroup$
    – phanny
    Oct 26 '18 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.