Fit binary decision tree for multiclass classification

fitctree computes the predictive measures of association between the decision split xj < u and all possible decision splits xk < v, j ≠ k.

fitctree sorts the possible alternative decision splits in descending order by their predictive measure of association with the optimal split. The surrogate split is the decision split yielding the largest measure.

fitctree decides the child node assignments for observations with a missing value for xi using the surrogate split. If the surrogate predictor also contains a missing value, then fitctree uses the decision split with the second largest measure, and so on, until there are no other surrogates. It is possible for fitctree to split two different observations at node t using two different surrogate splits. For example, suppose the predictors x1 and x2 are the best and second best surrogates, respectively, for the predictor xi, i ∉ {1,2}, at node t. If observation m of predictor xi is missing (i.e., xmi is missing), but xm1 is not missing, then x1 is the surrogate predictor for observation xmi. If observations x(m + 1),i and x(m + 1),1 are missing, but x(m + 1),2 is not missing, then x2 is the surrogate predictor for observation m + 1.

fitctree uses the appropriate impurity gain formula. That is, if fitctree fails to assign all missing observations in node t to children nodes using surrogate splits, then the impurity gain is ΔIU. Otherwise, fitctree uses ΔI for the impurity gain.