Salford Systems White Paper Series

• An Overview of CART^® Methodology
• Technical Note for Statisticians
• Do Splitting Rules Really Matter?
• MARS^TM (Multivariate Adaptive Regression Splines)
• Hybrid CART-Logit Model in Classification & Data Mining
• Achieving Results With Next Generation Data Mining Techniques
• Forcasting Recessions: Can We Do Better on MARS? (PDF file)
• Shares, Bonds, or Cash? Asset allocation in the new economy, using CART
• Critical Features of High Performance Decision Trees
• Statistical Process Analysis of Medical Incidents

An Overview of the CART^® Methodology

The CART methodology is technically known as binary recursive partitioning. The process is binary because parent nodes are always split into exactly two child nodes and recursive because the process can be repeated by treating each child node as a parent. The key elements of a CART analysis are a set of rules for:

• splitting each node in a tree;
• deciding when a tree is complete; and
• assigning each terminal node to a class outcome (or predicted value for regression)

Splitting Rules

To split a node into two child nodes, CART always asks questions that have a "yes" or "no" answer. For example, the questions might be: is age <= 55? Or is credit score <= 600?

How do we come up with candidate splitting rules? CART's method is to look at all possible splits for all variables included in the analysis. For example, consider a data set with 215 cases and 19 variables. CART considers up to 215 times 19 splits for a total of 4085 possible splits. Any problem will have a finite number of candidate splits and CART will conduct a brute force search through them all.

Choosing a Split

CART^®s next activity is to rank order each splitting rule on the basis of a quality-of-split criterion. The default criterion used in CART is the GINI rule, essentially a measure of how well the splitting rule separates the classes contained in the parent node. (Alternative criteria are also available).

Class Assignment

Once a best split is found, CART repeats the search process for each child node, continuing recursively until further splitting is impossible or stopped. Splitting is impossible if only one case remains in a particular node or if all the cases in that node are exact copies of each other (on predictor variables). CART also allows splitting to be stopped for several other reasons, including that a node has too few cases. (The default for this lower limit is 10 cases, but may be set higher or lower to suit a particular analysis).

Once a terminal node is found we must decide how to classify all cases falling within it. One simple criterion is the plurality rule: the group with the greatest representation determines the class assignment. CART goes a step further: because each node has the potential for being a terminal node, a class assignment is made for every node whether it is terminal or not. The rules of class assignment can be modified from simple plurality to account for the costs of making a mistake in classification and to adjust for over- or under-sampling from certain classes.

A common technique among the first generation of tree classifiers was to continue splitting nodes (growing the tree) until some goodness-of-split criterion failed to be met. When the quality of a particular split fell below a certain threshold, the tree was not grown further along that branch. When all branches from the root reached terminal nodes, the tree was considered complete. While this technique is still embodied in several commercial programs, including CHAID and KnowledgeSEEKER®, it often yields erroneous results. CART uses a completely different technique.

Pruning Trees

Instead of attempting to decide whether a given node is terminal or not, CART proceeds by growing trees until it is not possible to grow them any further. Once CART has generated what we call a maximal tree, it examines smaller trees obtained by pruning away branches of the maximal tree. Unlike other methods, CART does not stop in the middle of the tree-growing process, because there might still be important information to be discovered by drilling down several more levels.

Testing

Once the maximal tree is grown and a set of sub-trees are derived from it, CART determines the best tree by testing for error rates or costs. With sufficient data, the simplest method is to divide the sample into learning and test sub-samples. The learning sample is used to grow an overly-large tree. The test sample is then used to estimate the rate at which cases are misclassified (possibly adjusted by misclassification costs). The misclassification error rate is calculated for the largest tree and also for every sub-tree. The best sub-tree is the one with the lowest or near-lowest cost, which may be a relatively small tree.

Some studies will not have sufficient data to allow a good-sized separate test sample. The tree-growing methodology is data intensive, requiring many more cases than classical regression. When data are in short supply, CART employs the computer-intensive technique of cross validation.

Cross Validation

Cross validation is used if data are insufficient for a separate test sample. In such cases, CART grows a maximal tree on the entire learning sample. This is the tree that will be pruned back. CART then proceeds by dividing the learning sample into 10 roughly-equal parts, each containing a similar distribution for the dependent variable. CART takes the first 9 parts of the data, constructs the largest possible tree, and uses the remaining 1/10 of the data to obtain initial estimates of the error rate of selected sub-trees. The same process is then repeated (growing the largest possible tree) on another 9/10 of the data while using a different 1/10 part as the test sample. The process continues until each part of the data has been held in reserve one time as a test sample. The results of the 10 mini-test samples are then combined to form error rates for trees of each possible size; these error rates are applied to the tree based on the entire learning sample.

The upshot of this complex process is a set of fairly reliable estimates of the independent predictive accuracy of the tree. This means that we can know how well any tree will perform on completely fresh data-even if we do not have an independent test sample. Because the conventional methods of assessing tree accuracy can be wildly optimistic, cross validation is the method CART normally uses to obtain objective measures for smaller data sets.

Conclusion

CART uses a combination of exhaustive searches and computer-intensive testing techniques to identify useful tree structures of data. It can be applied to virtually any data set and can proceed with little or no guidance from the user. Thus, if you have a data set and have no idea how to proceed with its analysis, you can simply hand it over to CART and let it do the work. If this sounds too good to be true, the natural question is: does CART really deliver useful results that you can trust?

The surprising answer is a resounding yes. When automatic CART analyses are compared with stepwise logistic regressions or discriminant analyses, CART typically performs about 10 to 15 better on the learning sample. CART^®s performance on test samples is even more important. Because CART does not suffer from the statistical deficiencies that plague conventional stepwise techniques, CART will typically be far more accurate on new data. Further, when automatic CART analyses are compared with the best parametric models of sophisticated teams of statisticians, CART is still competitive. CART can often generate models in an hour or two that are only slightly worse in predictive accuracy than models that may take specialists several days to develop.

###

 Technical Note for Statisticians

###

Do Splitting Rules Really Matter?

Introduction

Do decision-tree splitting criteria matter? Contrary to popular opinion in data mining circles, our experience indicates that splitting criteria do matter; in fact, that the difference between using the right rule and the wrong rule could add up to millions of dollars of lost opportunity.

So, why haven?t the differences been noticed?  The answer is simple.  When data sets are small and highly-accurate trees can be generated easily, the particular splitting rule does not matter.  When your golf ball is one inch from the cup, which club or even which end you use is not important-you will be able to sink the ball in one stroke.  Unfortunately, previous examinations of splitting rule performance, the ones that found no differences, did not look at data-mining problems with large data sets where obtaining a good answer is genuinely difficult.

When you are trying to detect fraud, identify borrowers who will declare bankruptcy in the next 12 months, target a direct mail campaign, or tackle other real-world business problems that do not admit of 90+ percent accuracy rates (with currently available data), the splitting rule you choose could materially affect the accuracy and value of your decision tree.  Further, even when different splitting rules yield similarly accurate classifiers, the differences between them may still matter.  With multiple classes, you might care how the errors are distributed across classes.  Between two trees with equal overall error rates, you might prefer a tree that performs better on a particular class or classes.  If the purpose of a decision tree is to yield insight into a causal process or into the structure of a database, splitting rules of similar accuracy can yield trees that vary greatly in their usefulness for interpreting and understanding the data.

This paper explores the key differences between three important splitting criteria-Gini, Twoing and Entropy-for three- and greater-level classification trees and suggests how to choose the right one for a particular problem type.  Although we can make recommendations as to which splitting rule is best suited to which type of problem, it is good practice to always use several splitting rules and compare the results.  You should experiment with several different splitting rules and should expect different results from each.  As you work with different types of data and problems, you will begin to learn which splitting rules typically work best for specific problem types.  Nevertheless, you should never rely on a single rule alone; experimentation is always wise.

Gini, Twoing, and Entropy

The best known rules for binary recursive partitioning are Gini, Twoing, and Entropy.  Because each rule represents a different philosophy as to the purpose of the decision tree, each grows a different style of tree.

Gini Splitting Rule

Gini looks for the largest class in your database (e.g., class A) and strives to isolate it from all other classes.  For example, with four Classes, A, B, C, and D, representing 40, 30, 20, and 10 percent of the data, respectively, the Gini rule would immediately attempt to pull out the Class A records into one node.  Of course, such a separation may not be possible using the available data but if it is the Gini opts for that split.  The diagram below shows the best possible Gini split for these data.

Once the first split is made, Gini continues attempting to split the data that require further segmentation, i.e., the right child node that contains Class B, C and D.  Using the same strategy, Gini attempts to pull out all the Class B records, separating them from the other classes in the node. Gini then tackles the last heterogeneous node, striving to separate Class C from Class D.  If the GINI rule is successful, the final tree would contain four "pure" child nodes:

A pure decision tree such as the above is attainable only in very rare circumstances; in most real world applications, database fields that clearly partition class from class are not available.  If they were, no one would ever receive an unwelcome direct mail piece and bank losses on bad debts would be zero.  Therefore, we cannot expect to grow trees like the one above routinely; however, Gini will try to come as close as possible to this ideal.  A hypothetical example of a more realistic decision tree grown by Gini is displayed below.  While imperfect, it is still an unusually accurate tree.

So what is Gini trying to do?  Gini attempts to separate classes by focusing on one class at a time.  It will always favor working on the largest or, if you use costs or weights, the most "important" class in a node. While this approach might seem short sighted, Gini performance is frequently so good that you should always experiment with it to see how well it does.  Gini is the default rule in CART precisely because it is so often the best splitting rule.

Twoing and Entropy Splitting Rules

The philosophy of Twoing is far different than that of Gini.  Rather than initially pulling out a single class, Twoing first segments the classes into two groups, attempting to find groups that together add up to 50 percent of the data. Twoing then searches for a split to separate the two subgroups.  The diagram below shows the best possible split the Twoing rule could find.

Again, this is an ideal split.  It is unlikely that any real-world database would allow you to cleanly separate four important classes into two subgroups in this way.  However, splits that approach this ideal might be possible, and these are the splits that Twoing seeks to find.  The Entropy rule, which is very similar to Twoing in practice, strives for similar splits.

Variations on Twoing

An important variation of the Twoing rule is Power-Modified Twoing, which places an even heavier weight on splitting the data in a node into two equal-sized partitions.  When the perfect splits illustrated above are available, Twoing and Power-Modified Twoing will select the same split.  When only imperfect partitions are available, Power-Modified Twoing is more likely to generate a near 50-50 partition of the data than is simple Twoing.

General Rules of Thumb

The following rules of thumb are based on our experience in the telecommunications, banking, and market research arenas, and may not apply literally to other subject matters or even other data sets.  Nevertheless, they represent such a consistent set of empirical findings that we expect them to continue to hold in other domains and data sets.

• For a two-level dependent variable that can be predicted with a relative error of less than 0.50, the Gini splitting rule is typically best.
• For a two-level dependent variable that can be predicted with a relative error of 0.80 or higher, Power-Modified Twoing tends to perform best.
• For target variables with 4 to 9 levels, Twoing has a good chance of being the best splitting rule.
• For higher-level categorical dependent variables with 10 or more levels, Twoing or Power- Modified Twoing is often considerably more accurate than Gini.

Take the last rule of thumb, for example.  A data-mining project concerning consumer choice from a set of 28 vehicles is a typical example of the substantial differences that can be observed across alternative splitting rules.  The list of variables in this exercise were quite limited; in particular, the trees needed to be grown without reference to important drivers of choice such as income or price, so the level of accuracy attainable was expected to be low.  In the first run, using CART?s default criterion, the Gini rule grew an 89-node tree with a relative error of 0.919.  The second run using CART®s Twoing rule grew a tree with 50 nodes with a relative error of 0.876.

Reviewing the tree sequences below, one can see that the Twoing rule makes a better first split and continues to pull ahead of Gini on progressively larger trees.  Although the second tree also has quite a high error rate in percentage of error terms, it is a dramatic improvement over the first. In this example of vehicle choice, the Twoing rule was the winner; in other data sets, the winner might be Power-Modified Twoing, Gini, or yet another rule.

CART Tree Sequence for 28 Level Target Variable Using GINI

# of Terminal Tree Nodes	Test Set Relative Cost	Resubstitution Relative Cost	Complexity Parameter
100	0.91973 +/- 0.00636	0.80182	0.00076
95	0.92016 +/- 0.00636	0.80591	0.00079
94	0.92054 +/- 0.00636	0.80678	0.00085
89** (optimal)	0.91921 +/- 0.00636	0.81140	0.00090
88	0.92348 +/- 0.00636	0.81238	0.00095
78	0.92498 +/- 0.00630	0.82236	0.00097
70	0.92259 +/- 0.00639	0.83084	0.00103
19	0.94185 +/- 0.00657	0.90447	0.00236
18	0.94393 +/- 0.00649	0.90696	0.00241
17	0.94393 +/- 0.00649	0.90970	0.00265
13	0.94903 +/- 0.00650	0.92238	0.00306
4	0.97052 +/- 0.00640	0.95574	0.00358
3	0.97227 +/- 0.00566	0.96447	0.00843
2	0.97795 +/- 0.00399	0.97884	0.01386
1	1.00000 +/- 0.00004	1.00000	0.02042

CART Tree Sequence for 28 Level Target Variable Using TWOING

# of Terminal Tree Nodes	Test Set Relative Cost	Resubstitution Relative Cost	Complexity Parameter
55	0.88054 +/- 0.00643	0.77145	0.00112
54	0.88067 +/- 0.00648	0.772064	0.00116
53	0.88067 +/- 0.00648	0.77384	0.00117
51	0.87681 +/- 0.00657	0.77632	0.00121
50** (optimal)	0.87623 +/- 0.00660	0.77764	0.00128
45	0.87697 +/- 0.00653	0.78517	0.00146
43	0.87697 +/- 0.00653	0.78819	0.00147
40	0.88095 +/- 0.00648	0.79281	0.00150
15	0.88822 +/- 0.00703	0.84970	0.00351
14	0.89282 +/- 0.00698	0.85413	0.00428
7	0.90537 +/- 0.00544	0.89082	0.00585
5	0.91961 +/- 0.00513	0.90667	0.00765
4	0.93286 +/- 0.00490	0.92311	0.01586
3	0.94789 +/- 0.00380	0.94347	0.01964
2	0.96803 +/- 0.00217	0.96833	0.02398
1	1.00000 +/- 0.00004	1.00000	0.03055

Conclusion

Which splitting rule you choose when growing a decision tree does matter; sometimes the differences between rules will be modest and at other times profound.  We have found numerous examples where judicious choice of a splitting rule reduces the error rate of a classification tree by 5 to 10 percent.  But the differences go beyond accuracy. Even when the overall accuracy of two trees grown by different splitting rules is identical, the usefulness of the trees for revealing data structure can be quite different.  There will also be times when the value of a decision tree is determined by how rich the best nodes are in certain values of the target variable, and the overall accuracy of the tree is irrelevant.  In such circumstances, the differences between Gini and Twoing could easily be the difference between success and failure (e.g., in the case of fraud detection).

Given that there is no one best splitting rule for all problem types or all purposes, it is important that the decision-tree tool you employ offer several, proven splitting rules with distinct styles and operating characteristics.

Further Reading:

Breiman, L., J. Friedman, R. Olshen and C. Stone, Classification and Regression Trees, Pacific
Grove: Wadsworth, 1984

Breiman, L. Some Properties of Splitting Criteria, Statistics Department, University of California,
Berkeley. 1992.

###

MARS^TM (Multivariate Adaptive Regression Splines)

WHAT IS "MARS"?

MARS, an acronym for Multivariate Adaptive Regression Splines, is a multivariate non-parametric regression procedure introduced in 1991 by world-renowned Stanford statistician and physicist, Jerome Friedman (Friedman, 1991).  Salford Systems? MARS, based on the original code, has been substantially enhanced with new features and capabilities in exclusive collaboration with Friedman.

Overview of Methodology

The MARS procedure builds flexible regression models by fitting separate splines (or basis functions) to distinct intervals of the predictor variables.  Both the variables to use and the end points of the intervals for each variable-referred to as knots-are found via a brute force, exhaustive search procedure, using very fast update algorithms and efficient program coding.  Variables, knots and interactions are optimized simultaneously by evaluating a "loss of fit" (LOF) criterion.  MARS chooses the LOF that most improves the model at each step.  In addition to searching variables one by one, MARS also searches for interactions between variables, allowing any degree of interaction to be considered.

The "optimal" MARS model is selected in a two-phase process.  In the first phase, a model is grown by adding basis functions (new main effects, knots, or interactions) until an overly large model is found.  In the second phase, basis functions are deleted in order of least contribution to the model until an optimal balance of bias and variance is found.  By allowing for any arbitrary shape for the response function as well as for interactions, and by using the two-phase model selection method, MARS is capable of reliably tracking very complex data structures that often hide in high-dimensional data.

Core Capabilities

MARS core capabilities include:

• Automatic variable search Large numbers of variables are examined using efficient algorithms, and all promising variables are identified.
• Automatic variable transformation Every variable selected for entry into the model is repeatedly checked for non-linear response. Highly non-linear functions can be traced with precision via essentially piecewise regression.
• Automatic limited interaction searches  MARS repeatedly searches through the interactions allowed by the analyst.  Unlike recursive partitioning schemes, MARS models may be constrained to forbid interactions of certain types, thus allowing some variables to enter only as main effects, while allowing other variables to enter as interactions, but only with a specified subset of other variables.
• Variable nesting  Certain variables are deemed to be meaningful (possibly non-missing) in the model only if particular conditions are met (e.g., X has a meaningful non-missing value only if categorical variable Y has a value in some range).
• Built-in testing regimens  The analyst can choose to reserve a random subset of data for test, or use v-fold cross-validation to tune the final model selection parameters.

Applications

This new, flexible regression modeling tool is applicable to a wide variety of data analyses, particularly those in which variables possibly may be in need of transformation and interaction effects are likely to be relevant. The software can assist a data analyst to rapidly search through many plausible models and quickly identify important interactions-insights that can lead to significant model improvements.  Further, because the software can be exploited via intelligent default settings, for the first time analysts at all levels can easily access MARS? innovations.

MARS can also be used in conjunction with CART (co-developed by Friedman).  CART first can be used to extract the most important variables from a very large list of potential predictors.  MARS can then focus on the top variables from the CART model, resulting in faster MARS analyses and more accurate and robust models.

Graphical User Interface

Salford Systems' MARS has an easy-to-use, intuitive graphical user interface (GUI).  As shown below, the interface allows the user to control the variables and functional forms to be entered into the model and the interactions to be considered or forbidden, while allowing the MARS algorithm to optimize those parts of the model the analyst chooses to leave free.

Once the model is selected, the user can easily remove or add terms, instantly see the impact of changes on model fit, review diagnostics that assist in model selection, save the model and apply the model to new data for prediction.

Other MARS GUI features include an optional batch/command-line mode, spreadsheet-style browsing of the input data set, and summary text reports.  The enhanced MARS text report includes extensions to the "classic" output (e.g., addition of residual sums of squares, log-likelihood, and other useful diagnostics), making the results easier to comprehend and assisting the analyst in refining the model in subsequent runs.  In addition, the MARS interface provides all essential data management facilities for:

• new variable creation and deletion,
• sorting, merging, and concatenating of data sets,
• deletion of cases,
• random, stratified and exact count sampling, and
• filtering of cases into training and/or test and hold-out samples.

Visualization of Results

In addition to summary text reports, MARS results are also displayed in the Results dialog box.  The GUI output includes ANOVA decomposition, variable importance, and final model tables as well as graphical plots.

MARS automates both the selection of variables and the non-parametric transformation of variables to achieve the best model fit.  Variable transformation is accomplished implicitly through the piecewise regression function used by MARS to trace arbitrary non-linear functions.  MARS communicates this non-parametric transformation graphically, displaying the predicted response as a function of either one or two variables.

MARS automatically produces 2-D plots for main effects (response variable as a function of each predictor) and 3-D surface plots for interactions, with options to spin and rotate.  For higher-order interactions, the user can choose slices of the function for display of 2-D and 3-D subspaces.  Examples of main effects and interaction plots are shown below.

References

Friedman, J. H. (1991a), Multivariate Adaptive Regression Splines (with discussion), Annals of Statistics, 19, 1-141(March).

Steinberg, D. and Colla, P. L., (1995), CART: Tree-Structured Nonparametric DataAnalysis, San Diego, CA: Salford Systems.

Steinberg, D., Colla, P. L., and Kerry Martin (1999), MARS User Guide, San Diego, CA: Salford Systems.

###

The Hybrid CART-Logit Model in Classification and Data Mining

(PowerPoint presentation available for download) - 120k

CART^® and logistic regression are among the most used classification and response modeling tools and both have exhibited excellent performance in a variety of applications. The methods are so fundamental that they appear in almost all data mining suites. Since CART and logit have quite different strengths, it is natural to investigate whether some combination might prove superior. We introduce a new method for combining CART and logit, which exhibits performance advantages, and admits of a natural set of statistical evaluation tests.

Awarded "Best Presentation" at the Eighth Annual Advanced Research Techniques Forum, American Marketing Association, Keystone, CO, 1998.

###

Achieving Results With Next-Generation Data-Mining Techniques

(PowerPoint presentation available for download) - 218k

How do you get all you can from your data mining projects? Recent research reveals that combining the strengths of different data-mining tools can dramatically improve the accuracy of results. In this paper, we illustrate how to hybridize decision trees, neural nets and advanced statistics using case studies drawn from marketing and financial services sectors.

Paper presented at DCI's Database and Client Server World, Boston, MA.

###

Shares, Bonds, or Cash? Asset allocation in the new economy, using CART^®

How an Australian stock brokerage is using CART to optimize allocation of investments. For a copy of this paper, send an email to info@salford-systems.com

###

Critical Features of Decision Trees

PDF file available for download - 158k

Decision trees have justifiably become one of the most popular data mining tools. They are relatively easy to use, the results can usually be displayed in an easy to read flow chart, and their predictive accuracy can be good to excellent across a broad range of database types and structures. This document reviews some of key features of decision trees that any informed analyst should be thinking about when choosing this kind of data mining tool for important data analyses.

###

Statistical Process Analysis of Medical Incidents

by Norio Suzuki, Sojiro Kirihara, and Atsushi Ootaki of Meiji University, Japan

PDF file available for download -127k

Recently, in an effort to construct a system that reduces the risk of medical care, people engaged in the medical field have implemented continual improvement by team activities. Knowledge in total quality management (TQM), especially statistical process analysis and control (SPC) developed in the industrial field, seems to be applicable to medical care. This paper describes the application of statistical process analysis and control to continual improvement in medical care.

###