Decision Tree - Splitting Factor Variables

Question

I'm new to decision trees and I have some confusion about how factor variables and non-ordered character/string variables get handled in a split.

Suppose I have a factor such as "tiny, small, medium, large, huge" where the levels are important. How does a decision tree try to find the best split? Will it only check the 4 obvious splits, or will it check splits for weird combinations like, "tiny or huge but not small medium or large"?

Similarly, how does a decision tree check for a split for an unordered character variable such as "New Orleans, Birmingham, Jackson, Miami, Atlanta"?

I'm using the rpart package in R as I try to learn this stuff, so any references to rpart's implementation would be helpful.

Answer 1

rpart treats differently ordinal and nominal qualitative variables (factors, in R parlance). For your first variable, provided it has been defined as an ordered factor, the only splits considered would be:

• {tiny} {small, medium, large, huge},
• {tiny,small} {medium, large, huge},
• {tiny,small,medium} {large, huge}
• {tiny,small,medium,large}{huge}

while for a purely nominal variable, all $2^{k-1} -1$ posible splits ($k$ = number of levels) would be tested. Of course, this cannot be done with $k$ very large, so you might have to compromise aggregating levels.

Answer 2

Most decision trees do not consider ordinal factors but just categorical and numerical factors. You can code ordinal factors as numerical if you want to build trees more efficiently. However, if you use them as categorical a tree can help you check whether your data or ordinal codification has any inconsistency.

Most decision tree implementations use variations of information gain for classification tasks or squared error for regression tasks. They use the same technique for each split independently of the type of factor.

To learn how trees work with different types of data and different parameters (number of nodes, weights, sampling, etc) I recommend you to use inline sources from BigML in (FREE) development mode. For example, using the data below you can get easily get nice interactive model like this https://bigml.com/shared/model/sddxt90nauxqTTSjRCGyEwmp175

size, city, weather
tiny, New Orleans, good
small, Birmingham, good
medium, Jackson, bad
large, Miami, bad,
huge, Atlanta, good