A multivariate data set with a group column should be supplied, where one part (the training set) is assigned to groups, while the other part (the test set) has question marks in the group column. The rows in the test set are then assigned to groups (i.e., classified) according to their similarity with rows in the training set.
The algorithm is similar to CART algorithm (Breiman et al. 1984) but with some modifications.
Initial tree and pre-pruning
Tree construction starts with a root node Qm containing all samples (rows) in the training set. All possible splitting variables and splitting values are traversed, searching for minimal impurity. The Gini impurity measure is used (see the Past manual for equations).
After the optimal splitting rule has been found in this way, the sample set is assigned to the new subnodes accordingly, and the procedure is repeated recursively for each subnode.
The recursion stops when there is a single sample in the node, or all samples in the node are assigned to the same class. These termination criteria lead to a fully resolved tree, where each sample is assigned to a class unambiguously. This can lead to overfitting, giving poorer quality classification of new samples. The user can therefore set a stricter stopping rule (“pre-pruning”) by choosing a value N>=2 for the minimum number of rows In a node to allow it to split, and/or the maximal depth of the tree (the large default value of 10 will usually give a fully resolved tree).
Post-pruning
The initial tree computed above can be too detailed, leading to overfitting in the classification. The tree can therefore be pruned further, using the “minimal cost-complexity” procedure of Breiman et al. (1984), also formulated by Mingers (1989). Equations are given in the Past manual.
The post-pruning procedure continues iteratively until the criterion α is greater than the “Pruning alpha” value. Setting this value to zero will disable the post-pruning entirely.
Classification
Classification of a sample follows the decision rules of the tree down to a leaf node. The class is then decided by a majority vote among the class memberships of the training samples in the node. The “probability” value (a slight misnomer) is the proportion of samples of the majority class in the node.
The complete decision tree is shown in the “Rules” tab. Each node in the tree has two subnodes; the first subnode is selected if the splitting rule is true, otherwise the second subnode is selected. You can click on a node to hide its subtree.
Cross validation
The decision tree process is automatically cross-validated by the leave-one-out (jackknifing) method.
Missing values are treated as follows. During training, for each internal tree node, the optimal splitting variable and its splitting point are chosen using only non-missing values. Then, the test set samples in the node are assigned to the left or right subnode by this splitting rule only if they have the appropriate non-missing values. The remaining samples in the node (those with missing values for the splitting variable) are assigned to the subnode that acquired the most samples in the first step. During classification, the decision tree is traversed as usual, except that when a decision cannot be made because of a missing value, the subnode with the larger number of samples is chosen.
References
Breiman, L., Friedman, J., Olshen, R., Stone, C. 1984. Classification and Regression Trees. Wadsworth, Belmont, CA.
Mingers, J. 1989. An empirical comparison of pruning methods for decision tree induction. Machine Learning 4:227–243.