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

If it helps you can see the code and more details here.


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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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