4. Decision Trees

Decision Trees

• Can be used to predict a categorical or a continuous target (called regression trees in the latter case)
• Unlike logistic regression and neural networks, no equations are estimated in decision trees
• A tree structure of rules over the input variables are used to classify or predict the cases according to the target variable
• The rules are of an IF-THEN form. For example:
  • If Risk = Low, then predict on-time payment of a loan
• Advantages:
  1. Easy to interpret (Tree structured presentation)
  2. Allow mixed input data types: Categorical, ordinal, & interval
  3. Allow discrete (binary and categorical) or continuous target
  4. Robust to outliers in inputs
  5. No problem with missing values
  6. Automatically:
     • Accommodates nonlinearity
     • Selects input variables
• Disadvantages:
  1. Error prone if training data too small
  2. Can be time consuming to train
  3. Builds rectangular regions which may not correspond well with actual data distribution

3. Optimize complexity (Pruning)

1. Predictive Model Sequence
   • Create a sequence of models with increasing complexity
2. Maximal Tree
   • A maximal tree is the most complex model in the sequence
3. Pruning One Split
   • The next model in the sequence is formed by pruning one split from the maximal tree
   • Each subtree’s predictive performance is rated on validation data
   • The subtree with the highest validation assessment is selected
4. Pruning Two Splits
   • Similarly, this is done for subsequent models
   • Prune two splits from the maximal tree
   • Rate each subtree using validation assessment and select the subtree with the best assessment rating
5. Subsequent Pruning
   • Continue pruning until all subtrees are considered
6. Selecting the Best Tree
   • Compare validation assessment between tree complexities
7. Validation Assessment
   • Choose the simplest model with the highest validation assessment

• Binary Target Predictions
  1. Decision Optimization
     1. Accuracy
        • True positive
        • True negative
        • Maximize accuracy: Agreement between outcome and prediction
     2. Misclassification
        • False negative
        • False positive
        • Minimize misclassification: disagreement between outcome and prediction
  2. Ranking Optimization
     1. Concordance
        • Target = 0 -> Low score
        • Target = 1 -> High score
        • Maximize concordance: proper ordering of primary and secondary outcomes
     2. Discordance
        • Target = 0 -> High score
        • Target = 1 -> Low score
        • Minimize discordance: improper ordering of primary and secondary outcomes
  3. Estimate Optimization
     1. Squared error
        • Target -> Estimate^2
        • Minimize squared error: squared difference between target and prediction

Pruning Criteria (Limiting the size of a decision tree)

1. Entropy Pruning Criterion:
   • Entropy is used to calculate the homogeneity of a sample
   • If the sample is completely homogeneous, the entropy is zero and if the sample is an equally divided, it has entropy of one
   • The pruning is based on the entropy set target
2. Gini Pruning Criterion:
   • As with entropy, the change in Gini statistic is calculated based on the change in the global Gini statistic
3. Misclassification Rate Pruning Criterion:
   • The misclassification rate is simply the number of mispredictions divided by the number of predictions
   • Thus, a predicted target level can be set, and the tree is pruned back if it cannot meet the misclassification rate target
4. Average Square Error Pruning Criterion:
   • The average square error (ASE) is based on the sum of squares error (SSE)
   • Similarly, a predicted a target level can be set and the tree is pruned back if it cannot meet the ASE target

SAS Applications

3. SAS - Decision Tree

• 3.1. Creating Training and Validation Data
  • Click the Sample tool tab to use the "Data Partition" tool
  • Select the "Data Partition" node and examine its Properties panel
    • Use the Properties panel to select the fraction of data devoted to the Training, Validation, and Test partitions
    • By default, less than half the available data is used for generating the predictive models
    • There is a trade-off in various partitioning strategies:
      • More data devoted to training results in more stable predictive models, but less stable model assessments, and vice versa
      • The Test partition is used only for calculating fit statistics after the modeling and model selection is complete
        • Enter 50 as the Training value in the Data Partition node
        • Enter 50 as the Validation value in the Data Partition node
        • Enter 0 as the Test value in the Data Partition node

• 3.2.2. Creating a Splitting Rule

• 3.2.3. Adding More Splits

• 3.2.4. Changing a Splitting Rule

• 3.2.5. Creating the Maximal Tree

• 4.1. Assessing a Decision Tree

• 4.2. Pruning a Decision Tree

• The maximal tree is then sequentially pruned so that the sequence consists of the best 15-leaf tree, the best 14-leaf tree, and continue
• The tree in the sequence with the lowest overall validation misclassification rate is selected.

• 4.4. Additional Diagnostic Tools
  1. Treemap
     • The Tree Map window is intended to be used in conjunction with the Tree window to gauge the relative size of each leaf
     • The size of the small rectangle in the treemap indicates the fraction of the training data present in the corresponding leaf. It appears that only a small fraction of the training data finds its way to this leaf
  2. Leaf Statistic Bar Chart
     • This window compares the blue predicted outcome percentages in the left bars (from the training data) to the red observed outcome percentages in the right bars (from the validation data)
     • This plot reveals how well training data response rates are reflected in the validation data
     • Ideally, the bars should be of the same height
     • Differences in bar heights are usually the result of small case counts in the corresponding leaf
  3. Variable Importance
     • Select View -> Model -> Variable Importance
     • The Variable Importance window provides insight into the importance of inputs in the decision tree
     • The magnitude of the importance statistic relates to the amount of variability in the target explained by the corresponding input relative to the input at the top of the table
  4. The Score Rankings Overlay Plot
     • Is commonly called a cumulative lift chart
     • Cases in the training and validation data are ranked, based on decreasing predicted target values
     • A fraction of the ranked data is selected (given by the decile value)
     • The proportion of cases with the primary target value in this fraction is compared to the proportion of cases with the primary target value overall (given by the cumulative lift value)
     • A useful model shows high lift in low deciles in both the training and validation data
     • For example, the Score Ranking plot shows that in the top 20% of cases (ranked by predicted probability), the training and validation lifts are approximately 1.26
     • This means that the proportion of primary outcome cases in this top 20% is about 26% more likely to have the primary outcome than a randomly selected 20% of cases.
  5. Fit Statistics
     • The Fit Statistics window is used to compare various models built within SAS Enterprise Miner. The misclassification and average square error statistics are of most interest for this analysis
  6. The Output Window
     • The Output window provides information generated by the SAS procedures that are used to generate the analysis results. For the decision tree, this information includes variable importance, tree leaf report, model fit statistics, classification information, and score rankings