Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
I understand how best split is chosen for random forest for numerical predictors (features).
Numerical predictors are sorted then for every value Gini impurity or entropy is calculated and a threshold is chosen which gives the best split. But how best split is chosen for categorical predictor as there is no specific ordering?
The usual vanilla implementation tries all possible combinations of your categories. It expresses these combinations as an integer which represents which categories are selected and which are left out at the split. It goes from left to right. For example if you have a variable with the classes "Cat", "Dog", "Cow", "Rat" it would sweep through possible splits, meaning something like:
Dog vs the rest = 0100 (remember, read from left to right)
Cat vs the rest = 1000
By themselves, but also
Dog and Cat vs Cow and Rat = 1100
Cow and Cat vs Dog and Rat = 1010
And then, as mentioned, it uses integers to handle this, to represent the split:
library(R.utils)
> intToBin(12)
[1] "1100"
Forest is an ensemble method of trees. So I think your question is more based on the algorithm of trees about splitting variables. There is two kind of categorical predictor, ordered factor, and not ordered factor.
Ordered factor is similar to numeric variable and the random forest will find the cut point, while the latter one is used another algorithm as below.
It will try to catch first level of the factor out as the split and try to fit the model and find the performance with loss function. Then try to find the second level and fit it again and find the performance and so on. In the end, it find the best splitting level combinations according to the best performance.
So you will find that it takes a much longer while and memory for trees model or random forest model to fit factors than numeric.
If your features are categorical, the first idea that comes to my mind is to create a binary feature for every possible value in the category.
Thus, if you have a feature corresponding to "mobile phone brand" which can only be "Samsung, Apple, HTC or Nokia", I would represent it as four categories (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0) and (0, 0, 0, 1) respectively. This way the threshold will select between being a brand or any of the others at each split, without having strange effects.
Hope this helps!
Either choose some random categories and use the category which gives the best split, or choose some random combinations of categories and use the combination which gives the best split.
I think it doesn't really matter which of the two methods you choose since splitting on a combination of categories at a single node can be simulated by splitting on a single category at multiple nodes.
