[SPARK-23409] RandomForest/DecisionTree (syntactic) pruning of redundant subtrees

• Type: Improvement
• Status: Resolved
• Priority: Minor
• Resolution: Duplicate
• Affects Version/s: 2.2.1
• Component/s: MLlib
• Assignee: Unassigned
• Reporter: Alessandro Solimando
• Created: 13/Feb/18 13:36
• Updated: 16/Feb/18 21:30
• Resolved: 16/Feb/18 21:30

Description

Improvement: redundancy elimination from decision trees where all the leaves of a given subtree share the same prediction.

Benefits:

• Model interpretability
• Faster unitary model invocation (relevant for massive number of invocations)
• Smaller model memory footprint

For instance, consider the following decision tree.

Original Decision Tree

DecisionTreeClassificationModel (uid=dtc_e794a5a3aa9e) of depth 3 with 15 nodes
  If (feature 1 <= 0.5)
   If (feature 2 <= 0.5)
    If (feature 0 <= 0.5)
     Predict: 0.0
    Else (feature 0 > 0.5)
     Predict: 0.0
   Else (feature 2 > 0.5)
    If (feature 0 <= 0.5)
     Predict: 0.0
    Else (feature 0 > 0.5)
     Predict: 0.0
  Else (feature 1 > 0.5)
   If (feature 2 <= 0.5)
    If (feature 0 <= 0.5)
     Predict: 1.0
    Else (feature 0 > 0.5)
     Predict: 1.0
   Else (feature 2 > 0.5)
    If (feature 0 <= 0.5)
     Predict: 0.0
    Else (feature 0 > 0.5)
     Predict: 0.0

The proposed method, taken as input the first tree, aims at producing as output the following (semantically equivalent) tree:

Pruned Decision Tree

DecisionTreeClassificationModel (uid=dtc_e794a5a3aa9e) of depth 3 with 15 nodes
  If (feature 1 <= 0.5)
   Predict: 0.0
  Else (feature 1 > 0.5)
   If (feature 2 <= 0.5)
    Predict: 1.0
   Else (feature 2 > 0.5)
    Predict: 0.0

Issue Links

• duplicates: SPARK-3159 Check for reducible DecisionTree