Q1. What is CART?

A1. CART is an acronym for Classification and Regression Trees, a decision-tree procedure introduced in 1984 by world-renowned UC Berkeley and Stanford statisticians, Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone. Their landmark work created the modern field of sophisticated, mathematically- and theoretically-founded decision trees. The CART methodology solves a number of performance, accuracy, and operational problems that still plague many current decision-tree methods. CART's innovations include:

• solving the "how big to grow the tree" problem;
• using strictly two-way (binary) splitting;
• incorporating automatic testing and tree validation; and
• providing a completely new method for handling missing values.

Q2. What makes Salford Systems' CART the only "true" CART?

A2. Salford Systems' CART is the only decision tree based on the original code of Breiman, Friedman, Olshen, and Stone. Because the code is proprietary, CART is the only true implementation of this classification-and-regression-tree methodology. In addition, the procedure has been substantially enhanced with new features and capabilities in exclusive collaboration with CART's creators. While some other decision-tree products claim to implement selected features of this technology, they are unable to reproduce genuine CART trees and lack key performance and accuracy components. Further, CART's creators continue to collaborate with Salford Systems to refine CART and to develop the next generation of data-mining tools.

Q3. What is a decision tree?

A3. A decision tree is a flow chart or diagram representing a classification system or predictive model. The tree is structured as a sequence of simple questions, and the answers to these questions trace a path down the tree. The end point reached determines the classification or prediction made by the model, which can be a qualitative judgment (e.g., these are responders) or a numerical forecast (e.g., sales will increase 15 percent).

Q4. What makes CART so easy to interpret?

A4. As illustrated above, the results of a decision-tree data-mining project are displayed as a tree-shaped visual diagram. Discovered relationships and patterns in the data - even in massively complex datasets with hundreds of variables - are presented as a flow chart. Compare this to complex parameter coefficients in a logistic regression output or a stream of numbers in a neural-net output, and the appeal of decision trees is readily apparent.

The visual display enables users to see the hierarchical interaction of the variables, in addition,it often confirms previous knowledge about important data relationships, which adds confidence in the reliability and utility of the CART model. Further, because simple if-then rules can be read right off the tree, models are easy to grasp and easy to apply to new data.

Q5. How are decision trees grown?

A5. There are a number of different ways to grow decision trees, but CART uses strictly binary, or two-way, splits that divide each parent node into exactly two child nodes by posing questions with yes/no answers at each decision node. CART searches for questions that split nodes into relatively homogenous child nodes, such as a group consisting largely of responders, or high credit risks, or people who bought sport-utility vehicles. As the tree evolves, the nodes become increasingly more homogenous, identifying important segments. Other methods, such as CHAID, favor multi-way splits that can paint visually appealing trees but that can bog models down with less accurate splits.

Q6. Why is CART unique among decision-tree tools?

A6. CART is based on a decade of research, assuring stable performance and reliable results. CART's proven methodology is characterized by:

• Reliable pruning strategy - CART's developers determined definitively that no stopping rule could be relied on to discover the optimal tree, so they introduced the notion of over-growing trees and then pruning back; this idea, fundamental to CART, ensures that important structure is not overlooked by stopping too soon. Other decision-tree techniques use problematic stopping rules.
• Powerful binary-split search approach - CART's binary decision trees are more sparing with data and detect more structure before too little data are left for learning. Other decision-tree approaches use multi-way splits that fragment the data rapidly, making it difficult to detect rules that require broad ranges of data to discover.
• Automatic self-validation procedures - in the search for patterns in databases it is essential to avoid the trap of "overfitting," or finding patterns that apply only to the training data. CART's embedded test disciplines ensure that the patterns found will hold up when applied to new data. Further, the testing and selection of the optimal tree are an integral part of the CART algorithm. Testing in other decision-tree techniques is conducted after the fact and tree selection is left up to the user.
• In addition, CART accommodates many different types of real-world modeling problems by providing a unique combination of automated solutions:
  • surrogate splitters intelligently handle missing values;
  • adjustable misclassification penalties help avoid the most costly errors;
  • multiple-tree, committee-of-expert methods increase the precision of results; and
  • alternative splitting criteria make progress when other criteria fail.

Q7. What tree-growing, or "splitting," criteria can CART provide?

A7. CART includes seven single-variable splitting criteria - Gini, Symgini, twoing, ordered twoing and class probability for classification trees, and least squares and least absolute deviation for regression trees - and one multi-variable splitting criteria, the linear combinations method. The default Gini method typically performs best, but, given specific circumstances, other methods can generate more accurate models. CART's unique "twoing" procedure, for example, is tuned for classification problems with many classes, such as modeling which of 170 products would be chosen by a given consumer.

Other splitting criteria are available for inherently difficult problems in which even the best models are expected to have a relatively low accuracy. Demographics, for example, are often weak predictors of attitude- and preference-based segments. Special CART tree-growing options can dramatically increase the predictive accuracy of such demographic-based models. Additional unique tree-growing criteria are available for problems involving unequal misclassification costs, ordered target variables, and continuous dependent variables.To deal more effectively with select data patterns, CART also offers splits on linear combination of continuous predictor variables. For this option, CART looks for weighted averages of predictor variables to use as splitters; these weighted averages can reveal important database structure and can uncover new critical measures.

Q8. What are "adjustable misclassification penalties"?

A8. Unlike many data-mining tools, CART can accommodate situations in which some misclassifications, or cases that have been incorrectly classified, are more serious than others. CART users can specify a higher penalty for misclassifying certain data, and the software will steer the tree away from that type of error. Further, when CART cannot guarantee a correct classification, it will try to ensure that the error it does make is less costly. If credit risk is classified as low, moderate, or high, for example, it would be much more costly to classify a high-risk person as low-risk than as moderate-risk. Traditional data mining tools cannot distinguish between these errors.

Q9. What are "intelligent surrogates for missing values"?

A9. CART handles missing values in the database by substituting "surrogate splitters," which are back-up rules that closely mimic the action of primary splitting rules. Suppose that, in a given model, CART splits data according to household income. If a value for income is not available, CART might substitute education level as a good surrogate.

The surrogate splitter contains information that is typically similar to what would be found in the primary splitter. Other products' approaches treat all records with missing values as if the records all had the same unknown value; with that approach all such 'missings" are assigned to the same bin. In CART, each record is processed using data specific to that record. This allows records with different data patterns to be handled differently, which results in a better characterization of the data.

By using surrogates to stand in for missing values, CART generates robust and reliable predictive models, even when applied to very large databases with hundreds of variables and many missing values. CART's identification of surrogate predictor variables also provides an effective way to discover low-cost predictive mechanisms. If the best splitting criterion in a tree involves an expensive or difficult-to-obtain measure, a less-expensive surrogate can be considered instead.

Q10. What are CART's "automatic self-validation procedures"?

A10. CART uses two test procedures to select the "optimal" tree, which is the tree with the lowest overall misclassification cost, thus the highest accuracy. Both test disciplines, one for small datasets and one for large, are entirely automated, ensuring that the optimal tree model will accurately classify existing data and predict results.

For smaller datasets and cases when an analyst does not wish to set aside a portion of the data for test purposes, CART automatically employs cross validation. This frequently occurs in medical research, but a shortage of training data can occur in the study of any rare event, such as specific types of fraud. In cross validation, ten different trees are typically grown, each built from a different ten percent of the total sample. When the results of the ten trees are put together, a highly reliable determination of the optimal tree size is obtained. For large datasets, CART automatically selects test data or uses pre-defined test records or test files to self-validate results.

Q11. What is a "multiple-tree, committee-of-expert method," or "bootstrap aggregation"?

A11. The use of multiple trees in a committee of experts is a relatively new technique, and one of CART's creators has developed a dramatically effective way of combining trees in CART. Prediction errors can be reduced as much as 50 percent by directing CART to draw 50 or more different random samples from the training data, grow a different tree on each sample, and then allow the different trees to "vote" on the best classification. When appropriate, combining trees can yield a substantial performance edge over any other data mining procedure. For more information, see Committee of Experts.

Q12. When can CART be used to advantage as a standalone package?

A12. Most data-mining projects involve classification for gaining insight into existing data and turning that knowledge into a predictive model. Typical classification projects include sifting profitable from unprofitable; detecting fraudulent claims; identifying repeat buyers; profiling high-value customers who are likely to churn; and flagging high credit-risk applications. CART is a state-of-the-art classification tool that, as a standalone package, can investigate any classification task and provide a robust, accurate predictive model. The software tackles the core data-mining challenges by accommodating classification - for categorical variables, such as responder and non-responder - and regression - for continuous variables, such as sales revenue.

In addition to delivering accuracy, CART offers three distinct advantages over other data-mining tools. First, CART is easily accessible to beginning users, and it does not require a high level of technical expertise to operate. CART?s new, user-friendly GUI and reference manual guide users through a quick process, and the default settings perform so well that many highly experienced experts do not change them. Second, CART results are extremely easy to interpret; the tree-shaped flow chart easily identifies the most important predictors. Lastly, CART costs thousands of dollars less than a data-mining suite, and it comparably handles classification projects.

Q13. How can CART complement other data mining packages and/or suites?

A13. CART is an excellent pre-processing complement to data mining packages, such as SAS®. In the first stage of a data mining project, CART can extract the most important variables from a very large list of potential predictors. Focusing on the top variables from the CART model can significantly speed up neural networks and other data mining techniques. For neural nets in particular, CART bypasses "noise" and irrelevant variables, quickly and effectively selecting the best variables for input. The result is significant reductions in neural-net training speeds and more accurate and robust neural networks. In addition, the CART outputs, or "predicted values," can be used as inputs to the neural net.

CART can also be used to:

• establish performance benchmarks;
• detect important interactions that should be included in statistical models; and
• impute values for variables with missing values.

Q14. How quickly can CART generate results?

A14. CART's efficient algorithm generates results much faster than other methods, such as neural nets. On industry-standard servers, CART models based on 300,000 records and 1,000 variables can be generated in less than an hour. More typical problems involving 100,000 records and 450 variables run in approximately 10 minutes, while 100 variables and one million records can be run in less than 30 minutes. Exploratory analyses based on extracts from a large database can be conducted even faster; for example, a sample of 30,000 records with 100 selected input variables can be explored in less than five minutes.

Q15. COMBINE (Bagging, ARCing) Command

A15. The COMBINE command allows one to choose from several ways of combining separate CART trees into a single predictive engine. The trees are combined by either averaging their outputs for regression or by using an unweighted plurality voting scheme for classification. The current version of CART offers two combination methods: Bootstrap aggregation and ARCing. Each generates a set of trees by resampling (with replacement) from the original training data.

When training data is resampled with replacement the effect is to create a new version of the data that is a slightly "perturbed" version of the original. Some original training cases are excluded from the new training sample, and other cases are included multiple times. Typically, 37% of the original cases are not included at all in the resample; the sample is brought up to full size by including other cases more than once. A handful of cases will be replicated 4, 5, 6, or even 7 times, although the most common replication counts are 1 and 2. The effect of this resampling is to randomly alter the weights that cases will have in any analysis, thus shifting slightly the results obtained from tree growing or any other type of statistical analysis.

Bootstrap resampling was originally developed to help analysts determine how much their results might have changed if another random sample had been used instead, or how different results might be when a model is applied to new data. The theory of the bootstrap was developed by Stanford's Brad Efron in 1979 and has been studied extensively since then. For data mining applications, Leo Breiman applied the bootstrap in a novel way: the bootstrap is used to generate many versions of the data set or replications, a separate analysis is conducted for each replication, and then the results are averaged. If the separate analyses differ considerably from each other (suggesting tree instability), the averaging will stabilize the results and yield much more accurate predictions. If the separate analyses are very similar to each other, the trees exhibit stability and the averaging will not harm or improve the predictions. Thus, the more unstable the trees, the greater the benefits of averaging.

Note that COMBINE generates a committee of experts" rather than a single optimal tree. Because a single tree is thus not displayed, there is no simple way to explain the underlying rationale driving the COMBINE predictions. In this sense, combined trees are somewhat akin to the black box of a neural net, although the trees are built much faster.

Two different resampling technologies are currently available within CART:

1. ootstrap Aggregation (or bagging) in which each new resample is drawn in the identical way, and
2. ARCing (Adaptive Resampling and Combining) or ADAPTIVE resampling in which the way a sample is drawn for the next tree depends on the performance of prior trees.

• SETASIDE=PROP=p; where p is a number between 0 and 1,
• SETASIDE=SEPVAR=variable; where variable is equal to 1 for setaside status and 0 otherwise, or
• SETASIDE=FILE=filename; where filename is a separate dataset accessible by CART.

A sample command for bagging might then be:

COMBINE EXPLORE, CYCLES=50, SETASIDE=FILE="HOLDOUT.SYS"

while for ARCing a command might be:

COMBINE EXPLORE CYCLES=50, ARC=YES, POWER=4, SETASIDE=FILE="HOLDOUT.SYS"

There are other options for the COMBINE command which can be used to save individual tree files, save individual samples, produce detailed output on every tree grown, and to control details of the ARC resampling process (see Appendix below).


ARCing Fine Points

Combining methods require the growth of multiple trees all grown under slightly different conditions. Differences can occur in the control settings for the tree, such as when priors are systematically varied, or in the data being used for tree training. In bagging, the data is perturbed by resampling with replacement. The replacement induces a different set of weights on the training data. Bootstrap resampling always leaves some of the data out, reducing its weight to zero, and incorporating other data multiple times, increasing the weight of data included in the resample. Bootstrap resampling can always be conducted without fail. The same cannot be said for an ARC resample, however.

In ARCing, the probability with which a case is selected for the next training set is not constant and is not equal for all cases in the original learn data set; instead, the probability of selection increases with the frequency with which a case has been misclassified in previous trees. Cases that are very difficult to classify receive an increasing probability of selection while other cases that are classified correctly receive declining weights from trial to trial. As the probability of selection becomes more skewed in favor of the difficult-to-classify cases, the probability for selection for the typical case quickly declines to zero and the process of sample building takes an increasingly long time.

One of the ARCing options is a setting controlling how hard the ARCer should try to build a sample. In many runs the ARC process of resampling will simply bog down and the ARCer will automatically reset the probabilities to their equal starting values and continue generating additional trees.

Q16. No Tree

A16. The most frustrating outcome is to learn that CART has apparently not grown a tree. In this circumstance you will obtain a Tree Sequence Summary, but no node detail and no analytical results beyond a variable importance ranking.


SOLUTION 1: PICK a Tree

While you are still in BUILD, issue the PICK command to generate a tree from the tree sequence. Try something like:

PICK NODES = 4

which produces an exploratory tree including all the standard output on node detail, learning sample cost statistics, and so on. Be aware, however, that CART has determined that no tree should be generated, and therefore that the predictive performance of your tree is likely to be poor.

If you have already left BUILD and are back at the CART phase of analysis, grow an exploratory tree with:

ERROR EXPLORE

setting the complexity to a value that limits the tree to a size you wish to examine. Find the complexity value you need from the previous tree sequence output.


SOLUTION 2: Change Priors

CART can experience problems when some levels of a target variable have very few cases and you have specified PRIORS DATA (or PRIORS LEARN or PRIORS TEST). When the costs of misclassification are strictly proportional to the relative frequency of a class in the learning sample, CART may find that it is more accurate not to grow a tree. For example, in a binary problem with 95% class 1 and 5% class 2 cases, classifying all cases as class 1 from the start may yield the lowest costs on test data. To deal with this situation, try PRIORS EQUAL or PRIORS MIX, even if the classes have not been over- or under-sampled. The new priors will alter the penalty for misclassifying the rarer cases and may yield a tree.


SOLUTION 3: Change Costs

This solution is similar to changing priors. By changing costs you penalize CART for failing to split the root node, which might be enough to generate a test-validated tree.


SOLUTION 4: Change the Splitting Rule

For classification trees, Gini is the default node-splitting method; for regression trees, it is LS. You can sometimes induce a reluctant CART to generate test-validated trees by trying another method, for example, twoing or ordered twoing. One method that often proves useful is to adjust CART towards equal sized child nodes with the POWER option. Thus,

METHOD TWOING, POWER = 1

sets the center-cutting exponent to one, decreasing the chance of extremely unbalanced child nodes (end cuts).


Steinberg, Dan and Phillip Colla. CART--Classification and Regression Trees. San Diego, CA: Salford Systems, 1997.

Q17. Insufficient Memory

A17. CART is an extremely memory-intensive program, storing all data used for tree growing in RAM. This means certain large problems may not fit into available memory.


SOLUTION 1: Use A Larger Version of CART

Switch to a larger-memory version of Salford Systems CART. See the platform and operating specific documentation for the limits of the version you are using now, or call Salford Systems for further information.


SOLUTION 2: Adjust Parameters

CART memory requirements depend on several factors, including the number of levels of your dependent variable, the number of independent variables in the search list, the number of categorical predictors, how deep the tree is allowed to grow, and the size of the learning sample. You can experiment with altering these problem dimensions by using the LIMIT, MEMORY and ADJUST commands. MEMORY and ADJUST display your current memory requirements and show you parameter values (if any) that allow your problem to be accommodated.

One extremely useful parameter to adjust is BOPTIONS SUBSAMPLE, which directs CART to search for optimal splits near the top of the tree on a subsample of data, but uses the full data set to populate child nodes. This device saves work space in the nodes with the largest number of cases without reducing the size of the learning sample, while keeping the number of cases in the smaller nodes at their original number.

Other parameters that can be adjusted to save memory include the linear combinations option and the number of categorical predictors. Small amounts of memory can be saved by reducing the number of surrogates tracked and the number of competitors printed.


SOLUTION 3: Limit The Search List

CART will search over all variables in the learning sample looking for the best splits. The search list can be limited by listing explicit split candidates on the MODEL or KEEP statements or by eliminating variables on the EXCLUDE command. If you have an idea as to which variables are unlikely to be useful predictors, you can eliminate them from your first runs.

Alternatively, you can run several models, each with a different set of model variables, eliminating the most unimportant variables from each. The elimination process can continue in this way until you can pool all the remaining variables in a single model. Note, however, that this runs the risk of missing some important interactions.


SOLUTION 4: Subdivide Data

Break the problem into smaller pieces. Start by generating an exploratory tree of DEPTH = 1 to find the optimal split at the root node. Such a small tree should allow you to accommodate a rather large data set. Then, using the optimal or near optimal split, divide the data set into two subsets and run separate CART runs on each subsample. If one split still leaves a problem that is too large, repeat the process a second time to yield four subsets.

Once you have determined the truly important variables in this way, go back to the original data, limit the search list to just those variables, and run the model again for all cases.


Steinberg, Dan and Phillip Colla. CART--Classification and Regression Trees. San Diego, CA: Salford Systems, 1997.

Q18. High Costs or All Relative Costs Exceed One

A18. This is a variant of the NO TREE problem. When using a test sample or running a cross validation, all trees in the tree sequence have a relative error that exceeds one. Thus, no split exists that can improve the predictive performance of the tree.


SOLUTION: Vary Priors and Methods

For this problem the solutions provided for the NO TREE situation still hold. Experimentation with PRIORS and alternative splitting rules is your only recourse.

Q19. Cross Validation Breakdown

A19. This is a variant of the NO TREE problem. When using a test sample or running a cross validation, all trees in the tree sequence have a relative error that exceeds one. Thus, no split exists that can improve the predictive performance of the tree.

V-fold cross validation works by partitioning your data into equal-sized segments and holding out one segment at a time for test purposes. If certain classes of the target variable have very small sample sizes it may not be possible to subdivide each class into v subsets. Since CART requires at least one case in each class to run, the cross-validation trees cannot be constructed.


SOLUTION 1: Fewer Cross Validations

By reducing the number of cross validations you may be able to generate the test runs. However, Breiman, Friedman, Olshen and Stone warn that using fewer than 10 cross validations can seriously overestimate the error rate of any tree.


SOLUTION 2: Dedicated Test Samples

Define your own test subsamples with a random number generator in a data step. The best way is to define a new variable, say TEST1, set to 1 for test cases, and 0 otherwise. By adjusting the random number seed you can repeat the process until the desired balance of cases within each class is obtained. The process can be repeated with separate random test samples identified with variables TEST2, TEST3, etc. Running half a dozen CART trees, each with a different test set, will let you know if your results are stable.


Steinberg, Dan and Phillip Colla. CART--Classification and Regression Trees. San Diego, CA: Salford Systems, 1997.

Q20. Costs are Too High

A20. Even the best tree incurs unacceptably high error rates.


SOLUTION 1: Specify Costs

If some misclassifications are worse than others, you might be able to improve CART performance by specifying variable misclassification costs. While this method cannot improve the overall unweighted error rate of the tree, it can improve performance for the most important classes.


SOLUTION 2: Obtain More Data

The tools within CART are designed to give you the most reliable assessment of the predictive accuracy of your tree. If the error rate of the optimal tree is too high, CART is telling you that you probably cannot honestly get what you want. An objective assessment of your data reveals poor predictive power for virtually any model. The solution is to obtain more data on new variables.


SOLUTION 3: Create More Variables

Creating new variables such as sums, differences and ratios of your raw variables could help. You can use Salford Systems BASIC to create these new variables from within CART.


SOLUTION 4: Try Linear Combinations

Search for linear combinations with a high deletion threshold, as in:

LINEAR N=number, DELETE=.4


Steinberg, Dan and Phillip Colla. CART--Classification and Regression Trees. San Diego, CA: Salford Systems, 1997.

Q21. Cannot Apply Tree to New Data

A21.You wish to apply your results to new data, but CASE will not accept the data.

Q32. Cross Validation