Categorical Variables in Decision Tree

Question

I was going through the Andrew Ng's notes for Decision Trees. It has one section explaining the usage of categorical variables using Decision Trees in which I am not able to understand this part

" A caveat to the above is that we must take care to not allow a variable to have too many categories. For a set of categories S, our set of possible questions is the power set P(S), of cardinality 2^|S| . Thus, a large number of categories makes question selection computationally intractable. "

Q1 -> How is the possible set of questions is $2^{|S|}$ ? It should be equal to the non-leaf nodes in the decision tree .

Link to Andrew Ng notes on Decision Tree : http://cs229.stanford.edu/notes/cs229-notes-dt.pdf

Can you please give some clarification on it .

Answer 1

The $2^{|S|}$ number of POSSIBLE questions is defined by the number of different combinations of subsets of $S$ that could be part of the first partitions, then the second and so on until the tree is finished. That being the worst case.

Imagine that: $loc \in{} N$ is the first separation, so it's divided into Yes/No. Then $loc \in{} S$ is divided into Yes/No.

Then $loc \in{} E$ is the third partition and the answer is the same (Yes/No), you have 8 (2^3) questions asked. There are many combinations of use/no use/which to combine in which step, etc, but ultimately you will be asking the tree to consider all possibilities, which are $2^{card(S)}$.

Answer 2

The author is referring to the number of possible splits of the given node, by the given feature during the building of the tree. The tree can send any subset of the levels to the left, and the remaining levels to the right. (Well, actually the left/right symmetry means the number of options is cut in half, and there's no point in sending the empty set vs. the full set, so the real number of choices is $2^{|S|-1}-1$, but the point remains that categorical variables with many levels are problematic.)

Compare to a continuous or ordinal variable, where the sort of splits we consider are only $x\leq\alpha$ vs. $x>\alpha$, and $\alpha$ need only range over the number of levels $|S|-1$ (again $-1$ to ignore sending nothing vs. everything).

Answer 3

In simple words, when decision trees is trained it calculates the splits for all the available values of category. Now suppose you have 3 categories in your data you will have do 2**3 calculation = 8 ( Considering all subset of that fetaures)

But now suppose if you have 20 categories in a feature for calculating a single split you have to do 2**20 = 1,048,576 (~1 million calculation of gain). Thats why when number of categories increases it become intractable to run decision trees