Tracing Trees

.title[
# Tracing Trees
]
.subtitle[
## .light_green[Visualizing Variability in the Architecture of Random Forest Trees Using Extensions of Trace Plots]
]
.author[
### <br>
]
.author[
### Katherine Goode
]
.author[
### Presented at ISU Graphics Group
]
.date[
### April 1, 2021 <br> <br> <br> <br> .small[Code used to create slides available <a href="https://github.com/goodekat/presentations/tree/master/2021-isugg-trace-plots">here</a>]
]

---

# Overview

- Background

- Random forests 
  
  - Trace plots

<br>

- TreeTracer: Trace Plots in R

<br>

- Extending Trace Plots

<br>

- Patterns in the Forest

<br>

- Limitations and Ideas for Future Work

---

# Background

---

## Random Forests

---

## Common Tree Visualization

From [Urbanek (2008)](https://link.springer.com/chapter/10.1007/978-3-540-33037-0_11):

---

## Trace Plots (one tree)

From [Urbanek (2008)](https://link.springer.com/chapter/10.1007/978-3-540-33037-0_11):

---

## Trace Plots (forest of trees)

From [Urbanek (2008)](https://link.springer.com/chapter/10.1007/978-3-540-33037-0_11):

---

## Example: Predicting Penguin Species

```r
# Load the Palmer penguins data and extract features
penguins <- na.omit(palmerpenguins::penguins)
penguins_feat <- 
  penguins %>% 
  select(bill_depth_mm, bill_length_mm, flipper_length_mm, body_mass_g)
```

---

---

```r
# Fit a random forest
set.seed(71)
penguins_rf <-
  randomForest::randomForest(
    species ~ 
      bill_length_mm + 
      bill_depth_mm + 
      flipper_length_mm + 
      body_mass_g,
    data = penguins, 
    ntree = 50
  )
```

```r
# Print the confusion matrix
penguins_rf$confusion
```

```
##           Adelie Chinstrap Gentoo class.error
## Adelie       142         3      1 0.027397260
## Chinstrap      4        64      0 0.058823529
## Gentoo         0         1    118 0.008403361
```

---

<br>

---

---

# TreeTracer: Trace Plots in R

---

## TreeTracer R Package

- Creating trace plots from random forests (with some extensions)

- Extract tree data in a data frame for trace plots

- Compute distances between trees
]

<br>

GitHub repo: [https://github.com/goodekat/TreeTracer](https://github.com/goodekat/TreeTracer)

<br>

```r
# To install the package from GitHub
# Use with caution -- very much still in development
remotes::install_github("goodekat/TreeTracer")
```

---

## Individual Tree Data Frame

### randomForest

```r
rf_tree1 <- randomForest::getTree(rfobj = penguins_rf, k = 1) 
```

<div class="datatables html-widget html-fill-item-overflow-hidden html-fill-item" id="htmlwidget-97e9b616f1ea9173d0e5" style="width:100%;height:auto;"></div>
<script type="application/json" data-for="htmlwidget-97e9b616f1ea9173d0e5">{"x":{"filter":"none","vertical":false,"data":[["1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31"],[2,4,6,8,10,12,14,16,0,0,0,18,20,22,24,0,26,28,0,0,0,0,0,30,0,0,0,0,0,0,0],[3,5,7,9,11,13,15,17,0,0,0,19,21,23,25,0,27,29,0,0,0,0,0,31,0,0,0,0,0,0,0],[1,3,3,2,2,4,4,3,0,0,0,1,1,2,3,0,1,2,0,0,0,0,0,2,0,0,0,0,0,0,0],[43.25,206.5,206.5,16.75,16.8,4575,4100,186,0,0,0,44.65,47,18.75,212.5,0,39.5,18.9,0,0,0,0,0,17.65,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,-1,-1,-1,1,1,1,1,-1,1,1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,-1,-1],[0,0,0,0,0,0,0,0,1,3,1,0,0,0,0,1,0,0,2,1,3,1,2,0,3,1,2,2,1,3,2]],"container":"<table class=\"display\">\n  <thead>\n    <tr>\n      <th> <\/th>\n      <th>left daughter<\/th>\n      <th>right daughter<\/th>\n      <th>split var<\/th>\n      <th>split point<\/th>\n      <th>status<\/th>\n      <th>prediction<\/th>\n    <\/tr>\n  <\/thead>\n<\/table>","options":{"scrollX":600,"scrollY":300,"pageLength":31,"dom":"ti","ordering":false,"columnDefs":[{"className":"dt-right","targets":[1,2,3,4,5,6]},{"orderable":false,"targets":0}],"order":[],"autoWidth":false,"orderClasses":false,"lengthMenu":[10,25,31,50,100]}},"evals":[],"jsHooks":[]}</script>

---

## Individual Tree Data Frame

### TreeTracer

```r
tt_tree1 = TreeTracer::get_tree_data(rf = penguins_rf, k = 1)
```

<div class="datatables html-widget html-fill-item-overflow-hidden html-fill-item" id="htmlwidget-d4a9313d17c94fb0c985" style="width:100%;height:auto;"></div>
<script type="application/json" data-for="htmlwidget-d4a9313d17c94fb0c985">{"x":{"filter":"none","vertical":false,"data":[["1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28"],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,2,2,3,2,3,3,4,3,4,3,4,4,5,4,5,1,2,2,3,2,3,3,4,3,4,4,5],[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14],["bill_length_mm","flipper_length_mm","flipper_length_mm","bill_depth_mm","flipper_length_mm","body_mass_g","bill_depth_mm","flipper_length_mm","body_mass_g","bill_length_mm","body_mass_g","bill_depth_mm","bill_length_mm","bill_depth_mm","flipper_length_mm","bill_depth_mm","bill_length_mm","flipper_length_mm","flipper_length_mm","bill_depth_mm","flipper_length_mm","body_mass_g","body_mass_g","bill_length_mm","body_mass_g","flipper_length_mm","flipper_length_mm","bill_length_mm"],[43.25,206.5,206.5,16.75,206.5,4575,16.75,186,4575,44.65,4100,18.75,44.65,18.9,212.5,17.65,43.25,206.5,206.5,16.8,206.5,4100,4575,47,4100,212.5,186,39.5]],"container":"<table class=\"display\">\n  <thead>\n    <tr>\n      <th> <\/th>\n      <th>tree<\/th>\n      <th>node_depth<\/th>\n      <th>tree_branch<\/th>\n      <th>split_var<\/th>\n      <th>split_point<\/th>\n    <\/tr>\n  <\/thead>\n<\/table>","options":{"scrollX":600,"scrollY":300,"pageLength":28,"dom":"ti","ordering":false,"columnDefs":[{"className":"dt-right","targets":[1,2,3,5]},{"orderable":false,"targets":0}],"order":[],"autoWidth":false,"orderClasses":false,"lengthMenu":[10,25,28,50,100]}},"evals":[],"jsHooks":[]}</script>

---

## Trace Plot Data Frame

```r
tree1_trace <-
* TreeTracer::get_trace_data(
    tree_data = tt_tree1,
    rf = penguins_rf,
    train = penguins_feat
  )
```

<div id="htmlwidget-0c850dfa24ea6f4323d2" style="width:100%;height:350px;" class="datatables html-widget "></div>
<script type="application/json" data-for="htmlwidget-0c850dfa24ea6f4323d2">{"x":{"filter":"none","vertical":false,"data":[["1","2","3","4","5","6"],[1,1,1,1,1,1],[1,2,2,3,2,3],[1,1,2,2,3,3],["bill_length_mm","flipper_length_mm","flipper_length_mm","bill_depth_mm","flipper_length_mm","body_mass_g"],[43.25,206.5,206.5,16.75,206.5,4575],[1,2,2,3,2,4],[0.6,1.6,1.6,2.6,1.6,3.6],[1.4,2.4,2.4,3.4,2.4,4.4],[59.6,231,231,21.5,231,6300],[32.1,172,172,13.1,172,2700],[4,3,3,5,3,2],[0.924363636363636,2.06779661016949,2.06779661016949,2.94761904761905,2.06779661016949,4.01666666666667]],"container":"<table class=\"display\">\n  <thead>\n    <tr>\n      <th> <\/th>\n      <th>tree<\/th>\n      <th>node_depth<\/th>\n      <th>tree_branch<\/th>\n      <th>split_var<\/th>\n      <th>split_point<\/th>\n      <th>seg_xmid<\/th>\n      <th>seg_xmin<\/th>\n      <th>seg_xmax<\/th>\n      <th>split_var_max<\/th>\n      <th>split_var_min<\/th>\n      <th>n_splits<\/th>\n      <th>split_scaled<\/th>\n    <\/tr>\n  <\/thead>\n<\/table>","options":{"scrollX":600,"pageLength":6,"dom":"ti","ordering":false,"columnDefs":[{"className":"dt-right","targets":[1,2,3,5,6,7,8,9,10,11,12]},{"orderable":false,"targets":0}],"order":[],"autoWidth":false,"orderClasses":false,"lengthMenu":[6,10,25,50,100]}},"evals":[],"jsHooks":[]}</script>

---

## Trace Plot Function (one tree)

```r
penguin_trace_tree1 <-
* TreeTracer::trace_plot(
    rf = penguins_rf,
    train = penguins_feat,
    tree_ids = 1,
    alpha = 1
  )
```
]

.right-plot[
<img src="slides_files/figure-html/unnamed-chunk-21-1.png" width="90%" style="display: block; margin: auto;" />
]

---

## Trace Plot Function (multiple trees)

```r
ntrees = penguins_rf$ntree

penguin_trace <-
* TreeTracer::trace_plot(
    rf = penguins_rf,
    train = penguins_feat,
    tree_ids = 1:ntrees,
    alpha = 0.4
  )
```
]

.right-plot[
<img src="slides_files/figure-html/unnamed-chunk-23-1.png" width="90%" style="display: block; margin: auto;" />
]

---

# Extending Trace Plots

---

## Coloring Trees

```r
penguin_trace_col <-
  trace_plot( 
    rf = penguins_rf,
    train = penguins_feat,
    tree_ids = 1:ntrees,
    alpha = 0.4,
*   tree_color = "#9dad7f"
  )
```
]

.right-plot[
<img src="slides_files/figure-html/unnamed-chunk-25-1.png" width="90%" style="display: block; margin: auto;" />
]

---

## Display a Representative Tree

```r
penguin_trace_rep <-
  trace_plot( 
    rf = penguins_rf,
    train = penguins_feat,
    tree_ids = 1:ntrees,
    alpha = 0.4,
    tree_color = "#9dad7f",
*   rep_tree =
*     get_tree_data(
*       rf = penguins_rf,
*       k = 12
*     ),
*   rep_tree_size = 1.5,
*   rep_tree_alpha = 0.9,
*   rep_tree_color = "#557174"
  ) + 
  labs(
    title = "Highlighting Tree 12"
  )
```
]

.right-plot[
<img src="slides_files/figure-html/unnamed-chunk-27-1.png" width="90%" style="display: block; margin: auto;" />
]

---

## Color by ID

```r
penguin_trace_by_id <-
  trace_plot( 
    rf = penguins_rf,
    train = penguins_feat,
    tree_ids = 1:6,
    alpha = 0.9, 
*   color_by_id = TRUE
  ) + 
  scale_color_manual(
    values = c(
      "#c7cfb7",
      "#9dad7f",
      "#557174",
      "#D67236",
      "#F1BB7B",
      "#916a89"
  ))
```
]

.right-plot[
<img src="slides_files/figure-html/unnamed-chunk-29-1.png" width="90%" style="display: block; margin: auto;" />
]

---

## Facet by ID

```r
penguin_trace_facet <-
  trace_plot( 
    rf = penguins_rf,
    train = penguins_feat,
    tree_ids = 1:6,
    alpha = 0.9, 
    color_by_id = TRUE, 
*   facet_by_id = TRUE
  ) + 
  scale_color_manual(
    values = c(
      "#c7cfb7",
      "#9dad7f",
      "#557174",
      "#D67236",
      "#F1BB7B",
      "#916a89"
  ))
```
]

.right-plot[
<img src="slides_files/figure-html/unnamed-chunk-31-1.png" width="100%" style="display: block; margin: auto;" />
]

---

## Maximum Depth

```r
penguin_trace_max <-
  trace_plot( 
    rf = penguins_rf,
    train = penguins_feat,
    tree_ids = 1:ntrees,
    alpha = 0.4,
*   max_depth = 3
  )
```
]

.right-plot[
<img src="slides_files/figure-html/unnamed-chunk-33-1.png" width="100%" style="display: block; margin: auto;" />
]

---

---

---

# Patterns in the Forest

---

## Two Approaches to Finding Patterns

### (1) Clusters of Trees

- Are there clusters of trees within a forest?

- Would tell us if similar or different decision paths are used by the forest

### (2) Representative Tree

- Can we extract a tree that represents the forest?

- Can we extract a tree representative of each cluster?

.medium[
- [Sies and Van Mechelen (2020)](https://link.springer.com/article/10.1007/s00357-019-09350-4)
- [Weinberg and Last (2019)](https://journalofbigdata.springeropen.com/articles/10.1186/s40537-019-0186-3)
- [Weinberg and Last (2017)](https://sciendo.com/article/10.1515/amcs-2017-0051)
- [Banerjee, Ding, and Noone (2011)](https://onlinelibrary.wiley.com/doi/abs/10.1002/sim.4492)
- [Miglio and Soffritti (2004)](https://www.sciencedirect.com/science/article/abs/pii/S016794730300063X?via%3Dihub)
- [Shannon and Banks (1999)](https://onlinelibrary.wiley.com/doi/epdf/10.1002/%28SICI%291097-0258%2819990330%2918%3A6%3C727%3A%3AAID-SIM61%3E3.0.CO%3B2-2)
- [Chipman, George, and McCulloch (1998)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.2598)
]]

.pull-right[<br>.content-box[.center[
**Trace plots would be a great visualization tool for both approaches!**
]]]

---

## Visualizing Clusters

Example of representative trees from clusters within a random forest from [Chipman, George, and McCulloch (1998)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.2598):

]

Same trees in a trace plot:

<img src="slides_files/figure-html/unnamed-chunk-37-1.png" width="100%" style="display: block; margin: auto;" />
]

---

## Visualizing Representative Trees with Variability

Two scenarios:

.pull-left[
<img src="slides_files/figure-html/unnamed-chunk-39-1.png" width="100%" style="display: block; margin: auto;" />
]

.pull-right[
<img src="slides_files/figure-html/unnamed-chunk-40-1.png" width="100%" style="display: block; margin: auto;" />
]

---

## Process for Clustering Trees

1. Start with a distance metric to compare similarities between trees

- Several implemented in TreeTracer

2. Obtain a distance matrix

3. Apply a clustering method:
  
  - Hierarchical clustering

- K-nearest neighbors

- Multi-dimensional scaling

4. Visualize clusters using trace plots

---

## Step 1: Compute Distances

### Strategies to compare trees

Figures from [Sies and Van Mechelen (2020)](https://link.springer.com/article/10.1007/s00357-019-09350-4)

<img src="figures/predictions.png" width="100%" style="display: block; margin: auto;" />
]

<img src="figures/topology.png" width="120%" style="display: block; margin: auto;" />
]

---

### Current metrics implemented in TreeTracer

**[Chipman, George, and McCulloch (1998)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.2598)**

```r
# Fit metric: Compare 
# predictions from two trees
fit_metric <- 
  compute_fit_metric(
    rf = penguins_rf, 
    data = penguins_feat
  )
```

```r
# Partition metric: Determine 
# whether two predictions fall
# in same leaf in two trees
tree_preds <- 
  get_tree_preds(
    data = penguins_feat, 
    rf = penguins_rf
  )
partition_metric <-
  compute_partition_metric(
    rf = penguins_rf,
    tree_preds = tree_preds
  )
```

]

.pull-right[
**[Banerjee, Ding, and Noone (2011)](https://onlinelibrary.wiley.com/doi/abs/10.1002/sim.4492)**

```r
# Covariate metric: Determine 
# the agreement in predictors 
# used by the trees
cov_metric <- 
  compute_covariate_metric(
    rf = penguins_rf
  )

cov_metric3 <-
  compute_covariate_metric(
    rf = penguins_rf, 
    max_depth = 3
  )
```
]

---

### Metric Details

---

## Step 2: Obtain Distance Matrix

---

## Step 3: Apply Clustering Method

---

## Step 4: Visualize clusters

### Covariate Metric

- Coordinate 1 explains variability between trees that use 3 or 4 variables for splits

<br>

---

### Covariate Metric (max depth 3)

- Coordinate 1 explains variability in trees that use body mass for splitting in the first three levels or not

- Coordinate 2 explains variability in trees that use flipper length for splitting in the first three levels or not

---

### Fit Metric

Not clear why these trees are outliers based on the fit metric using a trace plot

- Perhaps a different visualization would be more helpful in this situation or
  
  - Could focus on trying to understand the variability within the large cluster

---

### Partition Metric

---

<br>

---

<br>

---

# Limitations and Ideas for Future Work

---

## Limitations

### Cognitive load

- Too much information to extract understanding?

<br>

### Overplotting issues

- Too many trees hide the trends

<br>

### True trends?

- Are we actually able to identify realistic similarities and differences between trees?

---

##  Ideas for Future Work

- Metric that compares two traces for similarities

- Compare the regions that are used to make a prediction

<br>

### Linking to other plots

- Sectioned scatterplots

- Visualizations of interactions created by splits

- Parallel coordinate plots with split points overlaid
]

- Implement developed methods

- Consider new methods

- Visualize rep tree in context of variability

<br>

### Other

- How to choose a maximum depth? (perhaps based on predictive accuracy)

- How to account for categorical variables?

]

---

# Thank you!