Shrink decision tree by shuffling order of attributes I made a decision tree that classifies mushrooms in the UCI Mushroom dataset as either poisonous or edible based on their features. The model has a 100% accuracy on both the training and test set. However, the model is fairly complex and I'm wondering if a simpler decision tree could reach the same performance. My question is how I could go about finding it.
One way that I was thinking is that the data are presented ordinally, but the data aren't actually ordinal. This puts an unnecessary constraint on the decision tree algorithm. For example, the gill color is presented like so:
1 - buff
2 - red
3 - gray
4 - chocolate
5 - black

The first decision is "Is gill color < 3.5", so it splits off buff, red, and gray. But say the optimal split were actually to take buff, gray, and black; there's no way to do that. So can/should I shuffle the order of the values and fit a decision tree to each shuffle and see which one is the smallest? Is this commonly done? Is there an easy way to do it (an sklearn implementation)?
I am perfectly willing to accept a very large increase in processing time in exchange for a simpler tree. (I could run this overnight if needed - I just want the smallest tree possible).
 A: As with any data problem, you should make sure your variables are correctly coded, e.g. as an unordered or ordered factor.
Any good decision tree algorithm then will treat the gill-color variable as an unordered factor. E.g., function ctree (R package partykit) finds the best grouping for unordered factors in a different way than for ordered factors, requiring no additional shuffling. The same goes for function rpart (of package with the same name), but this algorithm suffers from a bias towards variables with a larger number of possible cutpoints, which tends to also increase tree size, so may not be an optimal choice.
It is however very unlikely that treating a variable as an unordered instead of an ordered factor will reduce the number of splits (i.e., yield a simpler tree). The number of possible splits is higher for unordered than ordered factors, so will likely yield a similarly or more complex tree.
A: One way to handle these sorts of features is through one hot encoding (see the Kaggle article.)  In the case of your example, you would create five dummy variables, one for each of the five colors.  The values of the dummy variables would be "1" if the mushroom had that gill color and "0" otherwise.  You would remove the original variable from the dataset, as without any real order the numbers 1-5 aren't meaningful, as you realized.
You can, of course, create combinations of the dummy variables, e.g., one for "buff and red", one for "buff and gray", etc., and add them into the mix.  But as one adds more features, one has to be wary of overfitting the training data due to chance, for example, the only red-black-buff mushroom in the training set was poisonous even though in general red-black-buff isn't particularly likely to be poisonous.  Consequently, care must be taken to limit the possibility of this happening as one adds more features to a problem with a limited number of observations.   In this case, expanding the 22 categorical variables of the UCI mushroom data set using one hot encoding would result in roughly 125 variables to go with the 8124 observations, and adding combinations of variables would very quickly increase that number.
A: To explore different complexities of your model, try doing a grid search over one of the hyperparameters that limits the depth of the model. 
For example min_samples_split or min_samples_leaf over a range (0.001, 0.3). Then you can plot validation set accuracy versus number of decision nodes, and chose a model with a good balance of complexity and performance.
This can be done in combination with feature engineering, for example the recommended one-hot encoding.
