*! version 2.0 October 12, 2015 J. N. Luchman
help chaidforest

Title

Random forest ensemble classification based on chi-square automated interaction detection (CHAID) as base learner

Syntax

chaidforest depvar [if] [in] [weight] [, ntree(integer) nvuse(integer)
minnode(integer) minsplit(integer) unordered(varlist)
ordered(varlist) noisily missing alpha(pvalue)
dvordered xtile(varlist, xtile_opt) proos(proportion) nosamp

fweights are allowed; see weight.
See chaidforest postestimation for features available after estimation.

Description

chaidforest is an implementation of a random forest (Breiman, 2001) ensemble classification algorithm which is based on the idea that
multiple, relatively less accurate classifiers, when combined, can produce more accurate predictions than a single more accurate classifier
such as a logit-based model - especially when considering out-of-sample predictions.

The chaidforest classifier uses the CHAID algorithm as its "base learner" (see findit chaid for details about the CHAID
algorithm); which means that the chaidforest classifier is built as a "forest" of individual CHAID "trees." After the forest of individual
CHAID trees is "grown," predictions or observed probabilities for each observation can be obtained. The multiple trees grown constitute the
"forest" component of the random forest. Traditionally, a classification and regression tree is used as the base learner for a random forest.
As such, the chaidforest ensemble classifier can be expected to differ somewhat from other random forest classifiers and is similar in
spirit to the cforest() function in the R package
party.

chaidforest proceeds by growing a number of trees set by the user. By default, chaidforest randomly selects a subset of splitting
variables (naturally, without replacement) and a subset of observations (optionally, with [the default] or without replacement) for each
individual tree. The random splitting variable and observation selection constitutes the "random" component of the random forest.

By combining many individual trees, with randomly selected splitting variables and observations, influential variables and observations have less
impact on any individual tree. In particular, less influence by specific splitting variables allows less influential variables to actually
be used to split/partition the data variables in any given tree, increasing their representation in the final predictions and (potentially)
enhancing out-of-sample prediction.

Options

ntree() specifies the number of individual trees chaidforest grows. Using too few trees can result in some splitting variables
or observations being omitted from the results (as they were never sampled). The default number of trees is 100.

nvuse() specifies the number of candidate variables chaidforest will use for any single CHAID tree. Indicating the total
number of splitting variables stops the random sampling of variables as all variables will be used. The default number of splitting variables
is the (rounded) square root of the number of total splitting variables.

minnode() specifies the minimum number of observations allowed in a terminal cluster or "node" of an individual CHAID tree.
See findit chaid for more details about the minnode() option. The default value for minnode() is to use the value corresponding
to .5% (rounded) of the total number of observations.

minsplit() specifies the minimum number of observations across all levels of an optimally merged splitting
variable to allow any split to occur, irrespective of how many observations would be in each of the final clusters/nodes in an individual CHAID
tree. See findit chaid for more details about the minsplit() option. The default value for minsplit() is to use the value
corresponding to 1% (rounded) of the total number of observations.

unordered() treats the variable list included as "unordered." The unordered treatment affects both how categories of the
splitting variables are combined (i.e., any categories can be combined) in any individual CHAID tree.

ordered() treats the variable list included as "ordered." The ordered treatment affects both how categories of the splitting
variables are combined (i.e., only adjacent categories can be combined). Ordered variables with missing invoked, when missing data
are present, treat the missing category as a "floating" option which allows that category to be merged into any (set of) the other ordered
categories in the CHAID trees.

noisily turns on the tracing of the command through split-related data management and estimation runs. noisly
can reassure the user that chaidforest is running or, can show the user the entire process of determining the splits arrived at by each
CHAID tree and the variable/observation selection process.

missing allows missing data in the response and splitting variables to be treated as another, independent category. The
missing option does not meaningfully affect unordered splitting variables, as the missing category is simply treated as another uncordered category.
For ordered splitting and response variables with missing data, the missing option creates a "floating" missing data category.
The missing option primarily affects ordered response variables which is allowed to have "partial" ordering in the Goodman association models
underlying the estimation for each CHAID tree (i.e., all categories beside the missing data are ordered - the missing category has it's own
"effect").

The missing option can also result in missing (i.e., ".p", for predicted missing) as a predicted value and
probability category. Note that all missing values (i.e., ".", ".a", ".b", etc.) will be treated as a single category in the analysis.

alpha() sets the alpha level at which an optimally merged predictor will be split following the merging step in individual
CHAID trees. See findit chaid for more details about the alpha() option - called spltaplha() in chaid. The default
value is .5. Thus, splits that pass the p < .5 threshold are allowed to be split in the individual CHAID trees.

dvordered changes the treatment of the response variable from unordered (each "local" odds ratio allowed to be unique) to ordered
(each "local" odds ratio forced to be the same) in the Goodman association models underlying the current implementation of each CHAID tree's
estimation. As was mentioned previously, missing data on the response variable allows the missing category to have a unique local odds
ratio, and the rest of the categories to have the same odds ratio.

xtile() is a convenience command to take variables that are otherwise continuous, or ordered with many categories (i.e., counts),
and generate a set of ordered categorical quantiles from those variables. The variables created by xtile() are automatically considered
as ordered() and are added to the dataset with the name "xtvarname". Any variables called "xtvarname" already in the dataset will
be overwritten when using xtile(). The xtile() option allows the user specify the number of quantiles created as an option
(i.e., nquantiles(#)) following a comma. Not specifying the number of quantiles will result in 2 quantiles (i.e., a median split; the
default for xtile).

proos() overrides the default random sampling with replacement (i.e., bootstrap sampling) to sampling without replacement.
proos() indicates the proportion of the sample that is "out of sample" (i.e., "OOS") or not sampled. It tends to be the case that bootstrap
sampling obtains about 2/3rds of the observations (i.e., ~.3 is OOS) when the number of observations sampled is equal to the sample size (as is
implemented by chaidforest).

nosamp overrides random sampling of observations (i.e., stops random sampling of or "bagging" observations). All observations in the
estimation sample will be in each CHAID tree.

Remarks

chaidforest itself does not produce results but is rather a command used to "grow" the forest the results of which can subsequently be
"harvested" through postestimation commands (see chaidforest postestimation). Reserving results presentation for the
postestimation stage saves the user from having to wait for computation of statistics and other results in which they are not interested.

As is implied by its name, there is an important element of randomness involved in growing the chaidforest. The random components
are comprised of the sampling splitting variables and observations from the pool of splitting variables and observations for each individual
CHAID tree. Due to the sampling, the user should set seed prior to using chaidforest for reproducibility.

chaidforest makes extensive use of Ben Jann's moremata package (see findit moremata), which is required for
running chaidforest.

chaidforest is an almost fully Mata-based command which saves results to a "chaidtree" vector object called "results." Thus, the
results chaidtree object must remain in memory in Mata for the results to be accessed by postestimation commands. Users will usually not be able
to access these results directly unless they are familiar with Stata's classes.

The CHAID algorithm used by each CHAID tree in chaidforest differs from that implemented by chaid. In particular,
chaidforest only uses the exhaustive CHAID algorithm (Biggs, et al., 1993). Thus, all splits implemented by chaidforest are binary;
there are no multi-way splits. Similar to chaid only 20 levels of any splitting or response variable are allowed currently. Splitting
or response variables with > 20 levels will have to be manually collapsed before analysis. Negative values of splitting and response
variables are also not allowed and must be recoded (due to use of levelsof).

The CHAID algorithm used by each CHAID tree also uses Goodman (1979) association models to produce expected counts
for chi-squares (i.e., as opposed to being based fully on ologit or mlogit models). Goodman association models are loglinear models
(i.e., Poisson regressions) modeling predicted/expected counts by "independent variables" in the row and column of a cross-classification.
The expected counts produced by a traditional chi-square test can be obtained by treating the counts per cell as a
dependent variable and the dummy-coded row/response and column/splitting variables as independent variables. An ordered response or
splitting variable changes the ordered variable to be treated as continuous in the loglinear model (as opposed to dummy coded).
The Goodman models also allow for missing data on splitting or response variables irrespective of variable type (ordered
or unordered) when missing is invoked - incorporated as a dummy code reflecting that missing level in the loglinear model.

Due to numerical issues related to storage of very small p-values, chaidforest uses the Akaike information criterion
(see estat) to decide on splits and the McFadden R-square metric (see maximize) to decide on mergers
when p-values are effectively identical (i.e., when both are effectively 0 at ~10^-300).

chaidforest's Run Time

To manage expectations - the user should be warned that chaidforest is not a particularly fast command to execute compared to other
random forest classifiers. chaidforest was made to be user-friendly, to run entirely from standatd Stata syntax, and to run without the
need for plugins (i.e., to C++) which would speed up the run time (see, for example, findit boost) but would require more of the user to
implement.

The CHAID algorithm is "brute force" in how it merges categories. CHAID's method is intended to be less biased than
alternatives in terms of selecting splitting variables on which to split, but consequently can be time consuming. Moreover, unlike single
CHAID trees, trees in the chaidforest implementation are intended to be lenient in terms of size of tree growth. In other
words, chaidforest is allowed to grow very large individual trees to enhance classification. Specifically, each CHAID tree
differs from chaid's implementation as each split is not Bonferroni corrected, each has high default splitting p-values
(i.e., .5), always uses the exhaustive CHAID merging criterion which creates binary splits, and generally has small values for
minimum splitting and node observation counts. The foregoing characteristics allow for overfitting any individual tree, which
is good (in the aggregate) for classificiation accuracy, but in combination with CHAID's brute force merging rules can make for
long run times for any single forest.

The recommended approach to speeding run time is to collapse the data and use frequency weights. Datasets
with many observations slow down processing. Thus, reducing the number of observations by collapsing across identical observations greatly
speeds all computations with no loss of precision or effect on the results.

Besides the number of observations, chaidforest's run time is most dependent on the number of levels the splitting
variables have - as all valid potential mergers of levels within a splitting variable are attempted for each split, for each tree.
The number of potential mergers then (can) grow(s) geometrically with additional levels of splitting variables. Generally, the
number of levels per splitting variable affects runtime more for unordered (i.e., variables in unordered()) than ordered (i.e.,
variables in ordered()) variables. Unordered variables attempt to merge all possible levels as compared to ordered variables
which only try to merge adjacent levels resulting in differences in run time. Note that missing also adds more levels
to variables with missing data. In light of the discussion above, one way to reduce run time is by manually merging levels of
splitting variables. Binary variables, for instance, require no merging. In general, manually merging splitting variable
categories (by the user or by using xtile()) can save a substantial amount of run time. Users should, of course,
carefully consider the effect of such mergers on the results as accuracy can be affected.

chaidforest's run time is also dependent on: a] the number of trees grown (i.e., ntree()),
b] the number of splitting variables per tree (i.e., nvuse()),
c] the minimum size allowed to split and minimum node/cluster size (i.e., using minsplit() and minnode()), and
d] the probability value allowed to split (i.e., alpha()).

Options b]-d] correspond to parameters which affect the size of the trees grown and prediction accuracy
for any one CHAID tree. Small minimum split and node sizes allow for overfitting, as does large p-values, which although more time
consuming, large individual CHAID trees will result in better classification accuracy which is favorable for accuracy in the aggregate.
Additionally, more splitting variables allow for bigger possible trees (as well as longer run times), but fewer chances for
moderately predictive splitting variables to improve accuracy. The user is urged to use all 3 these options carefully as they can
affect predictions.

Option a] corresponds to smoothing over the randomness of the any individual tree in the forest. More trees take longer to run,
but tend to produce better, more replicable, and more consistent results. Thus, reducing the number of trees below the default is not generally
recommended - but adding more trees, when feasible, is encouraged.

Introductory examples

#1: Basic random forest analysis with altered minsplit() and minnode() and very liberal alpha()

clear all

set seed 1234567

webuse auto

chaidforest foreign, unordered(rep78) minnode(2) minsplit(5) xtile(length weight, nquantiles(3)) alpha(.8)

#2: Basic random forest analysis as in #1 with specified out-of-bag proportion and sampling without replacement

chaidforest foreign, unordered(rep78) minnode(2) minsplit(5) xtile(length weight, nquantiles(3)) proos(.25)

#3: Large-scale random forest with ordered response variable and specified number of trees (warning: can be time consuming)

webuse nhanes2f, clear

chaidforest health, dvordered unordered(region race) ordered(diabetes sex smsa heartatk) xtile(houssiz sizplace, nquantiles(3))
ntree(500)

#3: Large-scale random forest as in #3, collapsed with frequency weight

preserve

generate byte fwgt = 1

xtile xthoussiz = houssiz, nquantiles(3)

xtile xtsizplace = sizplace, nquantiles(3)

collapse (sum) fwgt, by(health region race xthoussiz xtsizplace diabetes sex smsa heartatk)

chaidforest health [fweight = fwgt], dvordered unordered(region race) ordered(xthoussiz xtsizplace diabetes sex smsa heartatk) ntree(500)

restore

#4: Random forest without "bagging" observations (only randomly selects splitting variables)

webuse sysdsn1, clear

chaidforest insure, ordered(male nonwhite) unordered(site) xtile(age, nquantiles(2)) nosamp

#5: Random forest without random splitting variable selection (only "bags" observations)

chaidforest insure, ordered(male nonwhite) unordered(site) xtile(age, nquantiles(2)) nvuse(4)

#6: Random forest incorporating missing data

chaidforest insure, ordered(male nonwhite) unordered(site) xtile(age, nquantiles(2)) missing

Saved results

chaidforest saves the following results to e():

scalars

e(ntree) number of CHAID trees in the random forest

e(nvuse) number of splitting variables used per CHAID tree

e(N_tree) number of observations used per CHAID tree

e(minsplit) minimum number of observations required for any CHAID tree to try to continue to make splits in the data

e(minnode) minimum number of observations required for any CHAID tree to allow a node/cluster to actually be split

macros

e(cmdline) command as typed

e(cmd) chaidforest

e(title) title in estimation output

e(predict) program used to implement predict

e(splitvars) list of splitting variable names

e(depvar) name of dependent/response variable

functions

e(sample) marks estimation sample

References

Breiman, L. (2001). Random forests. Machine learning, 45(1), 5-32.

Biggs, D., de Ville, B., and Suen, E. (1991). A method of choosing multiway partitions for classification and decision trees. Journal of Applied Statistics, 18, 49-62.

Goodman, L. A. (1979). Simple models for the analysis of association in cross-classifications having ordered categories. Journal of the American Statistical Association, 74(367), 537-552.

Kass, G. V. (1980). An exploratory technique for investigating large quantities of categorical data. Applied Statistics, 29, 2, 119-127.

Strobl, C., Malley, J., and Tutz, G. (2009). An Introduction to recursive partitioning: Rationale, application, and characteristics of classification and regression trees, bagging, and random forests. Psychological Methods, 14(4), 323–348.

Author

Joseph N. Luchman

Senior Scientist

Fors Marsh Group LLC

Arlington, VA

jluchman@forsmarshgroup.com

Also see

[R] levelsof, [R] tabulate twoway, [R] xtile, [R] poisson, [R] maximize,
[R] estat, [R] collapse.