Where in Elements of Statistical Learning does it talk of a "trick" to deal with categorical variables for binary classification?

Question

I've struggled to deal with categorical variables in Random Forests, for binary classification. Between 8:15 and 9:30 in this instructional video, it talks of a "clever trick".

It says the trick can be found in Elements of Statistical Learning "trick" to deal with categorical variables for binary classification in Random Forests. But, when I read the section on Random Forests, I can't seem to find this "clever trick"!! Can someone hint at where the right section is, or am I missing something obvious? Thank you.

EDIT:

I read the section 9.2.4: Other Issues - Categorical Predictors, thanks. This sentence is unclear to me, however:

"We order the predictor classes according to the proportion falling in outcome class 1."

Does "proportion" mean:

the ratio of 1's in that class to the total number of examples in the region OR the ratio of 1's in that class to the number of examples in that class?

the latter might be thrown of by skewed data. Say there's a class with only one example that happens to be a 1. By the latter definition of "proportion", this would mean that that class would rank first because it's proportion is 1. Which definition of proportion is correct?

Answer 1

It is mentioned in Section 9.2.4 under Categorical Predictors.

Here is a basic example of the "trick" and why it's important.

Suppose you have a binary response $y$ with values $\{\text{Yes}, \text{No}\}$ and a categorical variable $x$ with levels $\{A, B, C, D, E\}$. When splitting on $x$ at a given node, you have $15$ $(=2^{5-1}-1)$ possible splits. In this scenario, you could consider all possible splits and choose the optimal cutpoint using a specified impurity measure (e.g. entropy, Gini index). However, for a categorical variable with many levels, this strategy will fail.

Instead of considering all $15$ possible splits, let's reduce this to only $4$ splits (or fewer if there are ties). Suppose the proportion of $\text{Yes}$ is $0.8$ in class $A$, $0.7$ class $B$, $0.7$ class $C$, $0.2$ class $D$, and $0.9$ class $E$. One can reorder this as $(0.2, 0.7, 0.7, 0.8, 0.9)$ and split $x$ assuming the values are continuous. Once one determines the optimal cutpoint, say $\leq 0.75$, the values are back transformed, so the split to the left has $x \in \{ B, C, D\}$ and the split to the right has $x \in \{A, E\}$.