# Scikit's permuted features in decision tree implementation

In the Scikit's docummentation of decision trees I found a note:

"The features are always randomly permuted at each split. Therefore, the best found split may vary, even with the same training data and max_features=n_features"

However, according to my knowledge decision trees make exhaustive search and look for the best split, according to given criterion, among all the features. Where do the permutations come from then and why are they there?

• The next clause in that sentence is "if the improvement of the criterion is identical for several splits enumerated during the search of the best split" so it sounds like they might be saying the randomness comes into play in the event of a tie for best split.
– Dan
Aug 1 '19 at 16:03
• Honestly I don't think so, I believe that it means that when using all the features selected with max_num of features we get only ties, it goes beyond this limit and keeps searching. Aug 1 '19 at 16:10

From the documentation:

The features are always randomly permuted at each split. Therefore, the best found split may vary, even with the same training data and max_features=n_features, if the improvement of the criterion is identical for several splits enumerated during the search of the best split. To obtain a deterministic behaviour during fitting, random_state has to be fixed.

This is saying that in the case that 2 or more features are tied for the best split, then which feature is chosen will depend on this random permutation.

The permutations are used to randomly sample which features to use. If your data has 10 features and you specify max_features=2, then the permutation is used to find the split from among the features. I surmise this works by permuting and then testing the quality of each feature until the termination criterion is met. The termination criterion will depend on the other model hyperparameters. Usually this will terminate because max_features has been exhausted (so if you find a valid split, it won’t test more than 2 in this example), but minimum information gain, minimum samples per leaf, etc. are also relevant here. Importantly, more than max_features will be considered if no valid partition is found among the sampled features.

OP writes:

However, according to my knowledge decision trees make exhaustive search and look for the best split, according to given criterion, among all the features. Where do the permutations come from then and why are they there?

This is not an accurate description of how the sklearn.tree.DecisionTreeClassifier class works. How many features to consider is governed by max_features.

max_features : int, float, string or None, optional (default=None) The number of features to consider when looking for the best split:

The number of features to consider when looking for the best split:

• If int, then consider max_features features at each split.

• If float, then max_features is a fraction and int(max_features * n_features) features are considered at each split.

• If “auto”, then max_features=sqrt(n_features).

• If “sqrt”, then max_features=sqrt(n_features).

• If “log2”, then max_features=log2(n_features). If None, then max_features=n_features.

Note: the search for a split does not stop until at least one valid partition of the node samples is found, even if it requires to effectively inspect more than max_features features.

• Thank you very much Sycorax, very exhaustive answer. But to be honest this part of Scikit's documentation is not very clear. They should include the information that permutations are important only if a tie is found. Aug 5 '19 at 10:51
• If you feel that the documentation could be made more clear, you could suggest an improvement to the sklearn developers.
– Sycorax
Aug 5 '19 at 13:29