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.