The HPFOREST Procedure

Split-search algorithms generally inflate the worth of variables that offer many split possibilities beyond the predictive ability of the variable. Nominal variables are especially troublesome because they offer possible binary splits of the data, where k is the number of categories. A nominal variable that has many categories and no predictive power can produce a split of greater apparent worth simply by chance than a predictive variable that offers fewer split choices.

The problem motivated Gordon Kass to invent CHAID (Kass 1980), an algorithm that penalizes variables that produce more split candidates. The problem is mentioned in Breiman et al.; 1984, p. 42, as one of the weaknesses of their algorithm. The problem is worse in Ross Quinlan’s C5.0 algorithm (1993) because that algorithm creates many branches for a categorical input and only two for an interval input. Each branch provides an estimate of the target. Allowing some variables more estimates of a target than others gives those variables an unfair competitive advantage.

A popular solution is to select the splitting variable with a statistical test that does not involve searching for a splitting rule. The test adjusts for the different number of categories. Only the winning variable is used in a search for a splitting rule. Loh and Shih (1997) first proposed this in their QUEST algorithm, and Loh continues to evolve the method in GUIDE. The PRESELECT=LOH and PRESELECT=HOTHORN options in the PROC HPFOREST statement specify a variation of Loh’s method and a different method that is attributed to Hothorn, Hornik, and Zeileis (2006), respectively.

Although these methods are fast and mitigate selection bias, they do not focus on selecting a variable that produces the strongest split. When there is no nominal input variable that has many categories, searching for a split with each variable is apt to produce a more accurate model. The PRESELECT=BINNEDSEARCH option specifies this approach. For more information, see the section Selecting a Splitting Variable.

This section illustrates selection bias in traditional methods and the impressive handling by the more recent methods. The data contain a purely random input , which has j nominal categories, and a second input , which has k categories and is predictive of the target. The plots show the proportions of samples in which a method selects instead of the predictive input, . The larger the proportion, the greater the bias of the method toward variables that offer more splitting possibilities than predictive power.

The data contain 500 observations. The target Y has values 0 and 1 with equal probabilities. Nominal input has equally probable integer values from 0 through . The probability that given that is greater than or equal to is 0.6 (and therefore ). With enough data, a splitting algorithm that uses assigns values that are less than to one branch, and the rest to the other branch. is equally distributed without reference to Y. With enough data, the best split on has negligible worth. A variable selection method chooses between two variables. After repeating this for 1,000 samples, the proportion of times is selected is recorded and plotted for several combinations of j and k.

Figure 7.5 shows the proportion of samples for which is selected instead of when the split-search algorithm uses the reduction in Gini impurity as the splitting criterion. As shown in the figure, Gini reduction selects more often as the number of categories j increases. When j is similar to k, Gini reduction selects between 15% and 30% of the time. For , is selected about 75% of the time. Gini reduction selects the wrong variable more often than not for these values of j and k.

Figure 7.5: Proportion of Samples for Which Gini Reduction Selects

Figure 7.6 shows the proportion of samples for which is selected using the CHAID split-search algorithm. The figure shows that CHAID selects less often as the number of categories j increases. CHAID penalizes variables that have many categories, and the penalty is larger than necessary. For , the proportion of times CHAID selects decreases from about 70% () to less than 10% (). CHAID selects the wrong variable more often than not when j is much less than k.

Figure 7.6: Proportion of Samples for Which CHAID Selects

Figure 7.7 shows the proportion of samples for which the PRESELECT=HOTHORN option in the PROC HPFOREST statement selects by using a test of association. As shown in the figure, given , PROC HPFOREST selects the same proportion of times regardless of the number of categories j. When the number of categories k of increases, PROC HPFOREST selects more often. However, the proportion never reaches 40%. The PRESELECT=HOTHORN option does not select the wrong variable more than 40% of the time for any values of j and k examined. The PRESELECT=LOH option produces similar results and is not shown.

Figure 7.7: Proportion of Samples for Which an Association Test Selects

The material in this section is part of a fuller discussion in De Ville and Neville (2013) of variable selection bias.