# Basics of tree-based models

Tree-structure models fall into the machine-learning rather than the inference statistics category as they are commonly used for classification and prediction tasks rather than explanation of relationships between variables. The tree structure represents recursive partitioning of the data to minimize residual deviance that is based on iteratively splitting the data into two subsets.

The most basic type of tree-structure model is a decision tree which is a type of classification and regression tree (CART). A more elaborate version of a CART is called a Conditional Inference Tree (CIT). The difference between a CART and a CIT is that CITs use significance tests, e.g. the p-values, to select and split variables rather than some information measures like the Gini coefficient (Gries 2021).

Like random forests, inference trees are non-parametric and thus do not rely on distributional requirements (or at least on fewer).

## Advantages

Several advantages have been associated with using tree-based models:

Tree-structure models are very useful because they are

**extremely flexible**as they can deal with different types of variables and provide a very good understanding of the structure in the data.Tree-structure models have been deemed particularly interesting for linguists because they can handle

**moderate sample sizes**and many high-order interactions better then regression models.Tree-structure models are (supposedly) better at detecting

**non-linear or non-monotonic relationships**between predictors and dependent variables. This also means that they are better at finding and displaying interaction sinvolving many predictors.Tree-structure models are

**easy**to implement in R and do not require the model selection, validation, and diagnostics associated with regression models.Tree-structure models can be used as

**variable-selection**procedure which informs about which variables have any sort of significant relationship with the dependent variable and can thereby inform model fitting.

## Problems

Despite these potential advantages, a word of warning is in order: Gries (2021) admits that tree-based models can be very useful but there are some issues that but some serious short-comings of tree-structure models remain under-explored. For instance,

Forest-models (Random Forests and Boruta) only inform about the

**importance**of a variable but not if the variable is important as a main effect or as part of interactions (or both)! The importance only shows that there is some important connection between the predictor and the dependent variable. While partial dependence plots (see here for more information) offer a remedy for this shortcoming to a certain degree, regression models are still much better at dealing with this issue.Simple tree-structure models have been shown to fail in detecting the correct predictors if the variance is solely determined by a

**single interaction**(Gries 2021, chap. 7.3). This failure is caused by the fact that the predictor used in the first split of a tree is selected as the one with the strongest main effect (Boulesteix et al. 2015, 344). This issue can, however, be avoided by hard-coding the interactions as predictors plus using ensemble methods such as random forests rather than individual trees (see Gries 2021, chap. 7.3).Another shortcoming is that tree-structure models partition the data (rather than “fitting a line” through the data which can lead to more

**coarse-grained predictions**compared to regression models when dealing with numeric dependent variables (again, see Gries 2021, chap. 7.3).Boulesteix et al. (2015, 341) state that high correlations between predictors can hinder the

**detection of interactions**when using small data sets. However, regression do not fare better here as they are even more strongly affected by (multi-)collinearity (see Gries 2021, chap. 7.3).Tree-structure models are bad a detecting interactions when the variables have

**strong main effects**which is, unfortunately, common when dealing with linguistic data (Wright, Ziegler, and König 2016).Tree-structure models cannot handle

**factorial variables**with many levels (more than 53 levels) which is very common in linguistics where individual speakers or items are variables.Forest-models (Random Forests and Boruta) have been deemed to be better at dealing with small data sets. However, this is only because the analysis is based on

**permutations**of the original small data set. As such, forest-based models only appear to be better at handling small data sets because they “blow up” the data set rather than really being better at analyzing the original data.

Before we implement a conditional inference tree in R, we will have a look at how decision trees work. We will do this in more detail here as random forests and Boruta analyses are extensions of inference trees and are therefore based on the same concepts.

## Classification And Regression Trees

Below is an example of a decision tree which shows what what response to expect - in this case whether a speaker uses discourse *like* or not. Decision trees, like all CARTs and CITs, answer a simple question, namely *How do we best classify elements based on the given predictors?*. The answer that decision trees provide is the classification of the elements based on the levels of the predictors. In simple decision trees, all predictors, even those that are not significant are included in the decision tree. The decision tree shows that the best (or most important) predictor for the use of discourse *like* is age as it is the highest node. Among young speakers, those with high status use *like* more compared with speakers of lower social status. Among old speakers, women use discourse *like* more than men.

```
install.packages("tree")
install.packages("dplyr")
install.packages("grid")
install.packages("flextable")
install.packages("partykit")
install.packages("ggparty")
```

The *yes* and *no* at the bottom show if the speaker should be classified as a user of discourse *like* (*yes* or *no*). Each split can be read as *true* to the left and *false* to the right. So that, at the first split, if the person is between the ages of 15 and 40, we need to follow the branch to the left while we need to follow to the right if the person is not 15 to 40.

Before going through how this conditional decision tree is generated, let us first go over some basic concepts. The top of the decision tree is called *root* or *root node*, the categories at the end of branches are called *leaves* or *leaf nodes*. Nodes that are in-between the root and leaves are called *internal nodes* or just *nodes*. The root node has only arrows or lines pointing away from it, internal nodes have lines going to and from them, while leaf nodes only have lines pointing towards them.

How to prune and evaluate the accuracy of decision trees is not shown here. If you are interested in this, please check out chapter 7 of Gries (2021) which is a highly recommendable resource that provide a lot of additional information about decision trees and CARTs.

We will now focus on how to implement tree-based models in R and continue with getting a more detaled understanding og how tree-based methods work.

## How Tree-Based Methods Work

Let us now go over the process by which the decision tree above is generated. In our example, we want to predict whether a person makes use of discourse *like* given their age, gender, and social status.

Let us now go over the process by which the decision tree above is generated. In our example, we want to predict whether a person makes use of discourse *like* given their age, gender, and social status.

In a first step, we load and inspect the data that we will use in this tutorial. As tree-based models require either numeric or factorized data, we factorize the “character” variables in our data.

```
# load data
<- read.delim("https://slcladal.github.io/data/treedata.txt", header = T, sep = "\t") %>%
citdata ::mutate_if(is.character, factor) dplyr
```

Age | Gender | Status | LikeUser |
---|---|---|---|

15-40 | female | high | no |

15-40 | female | high | no |

15-40 | male | high | no |

41-80 | female | low | yes |

41-80 | male | high | no |

41-80 | male | low | no |

41-80 | female | low | yes |

15-40 | male | high | no |

41-80 | male | low | no |

41-80 | male | low | no |

The data now consists of factors which two levels each.

The first step in generating a decision tree consists in determining, what the root of the decision tree should be. This means that we have to determine which of the variables represents the root node. In order to do so, we tabulate for each variable level, how many speakers of that level have used discourse *like* (LikeUsers) and how many have not used discourse *like* (NonLikeUsers).

```
# tabulate data
table(citdata$LikeUser, citdata$Gender)
```

```
##
## female male
## no 43 75
## yes 91 42
```

`table(citdata$LikeUser, citdata$Age)`

```
##
## 15-40 41-80
## no 34 84
## yes 92 41
```

`table(citdata$LikeUser, citdata$Status)`

```
##
## high low
## no 33 85
## yes 73 60
```

None of the predictors is perfect (the predictors are therefore referred to as *impure*). To determine which variable is the root, we will calculate the degree of “impurity” for each variable - the variable which has the lowest impurity value will be the root.

The most common measure of impurity in the context of conditional inference trees is called *Gini* (an alternative that is common when generating regression trees is the deviance). The Gini value or gini index was introduced by Corrado Gini as a measure for income inequality. In our case we seek to maximize inequality of distributions of leave nodes which is why the gini index is useful for tree based models. For each level we apply the following equation to determine the gini impurity value:

\[\begin{equation} G_{x} = 1 - ( p_{1} )^{2} - ( p_{0} )^{2} \end{equation}\]

For the node for men, this would mean the following:

\[\begin{equation} G_{men} = 1-(\frac{42} {42+75})^{2} - (\frac{75} {42+75})^{2} = 0.4602235 \end{equation}\]

For women, we calculate G or Gini as follows:

\[\begin{equation} G_{women} = 1-(\frac{91} {91+43})^{2} - (\frac{43} {91+43})^{2} = 0.4358432 \end{equation}\]

To calculate the Gini value of Gender, we need to calculate the weighted average leaf node impurity (weighted because the number of speakers is different in each group). We calculate the weighted average leaf node impurity using the equation below.

\[\begin{equation} G_{Gender} = \frac{N_{men}} {N_{Total}} \times G_{men} + \frac{N_{women}} {N_{Total}} \times G_{women} \end{equation}\]

\[\begin{equation} G_{Gender} = \frac{159} {303} \times 0.4602235 + \frac{144} {303} \times 0.4358432 = 0.4611915 \end{equation}\]

We will now perform the gini-calculation for gender (see below).

```
# calculate Gini for men
<- 1-(42/(42+75))^2 - (75/(42+75))^2
gini_men # calculate Gini for women
<- 1-(91/(91+43))^2 - (43/(91+43))^2
gini_women # calculate weighted average of Gini for Gender
<- 42/(42+75)* gini_men + 91/(91+43) * gini_women
gini_gender gini_gender
```

`## [1] 0.4611915`

The gini for gender is 0.4612. In a next step, we revisit the age distribution and we continue to calculate the gini value for age.

```
# calculate Gini for age groups
<- 1-(92/(92+34))^2 - (34/(92+34))^2 # Gini: young
gini_young <- 1-(41/(41+84))^2 - (84/(41+84))^2 # Gini: old
gini_old # calculate weighted average of Gini for Age
<- 92/(92+34)* gini_young + 41/(41+84) * gini_old
gini_age gini_age
```

`## [1] 0.4323148`

The gini for age is .4323 and we continue by revisiting the status distribution and we continue to calculate the gini value for status.

```
<- 1-(73/(33+73))^2 - (33/(33+73))^2 # Gini: high
gini_high <- 1-(60/(60+85))^2 - (85/(60+85))^2 # Gini: low
gini_low # calculate weighted average of Gini for Status
<- 73/(33+73)* gini_high + 60/(60+85) * gini_low
gini_status gini_status
```

`## [1] 0.4960521`

The gini for status is .4961 and we can now compare the gini values for age, gender, and status.

```
# compare age, gender, and status ginis
gini_age; gini_gender; gini_status
```

`## [1] 0.4323148`

`## [1] 0.4611915`

`## [1] 0.4960521`

Since age has the lowest gini (impurity) value, our first split is by age and age, thus, represents our root node. Our manually calculated conditional inference tree right now looks as below.

In a next step, we need to find out which of the remaining variables best separates the speakers who use discourse *like* from those that do not under the first node. In order to do so, we calculate the Gini values for *Gender* and *SocialStatus* for the *15-40* node.

We thus move on and test if and how to split this branch.

```
# 5TH NODE
# split data according to first split (only young data)
<- citdata %>%
young ::filter(Age == "15-40")
dplyr# inspect distribution
<- table(young$LikeUser, young$Gender)
tbyounggender tbyounggender
```

```
##
## female male
## no 17 17
## yes 58 34
```

```
# calculate Gini for Gender
# calculate Gini for men
<- 1-(tbyounggender[2,2]/sum(tbyounggender[,2]))^2 - (tbyounggender[1,2]/sum(tbyounggender[,2]))^2
gini_youngmen # calculate Gini for women
<- 1-(tbyounggender[2,1]/sum(tbyounggender[,1]))^2 - (tbyounggender[1,1]/sum(tbyounggender[,1]))^2
gini_youngwomen # # calculate weighted average of Gini for Gender
<- sum(tbyounggender[,2])/sum(tbyounggender)* gini_youngmen + sum(tbyounggender[,1])/sum(tbyounggender) * gini_youngwomen
gini_younggender gini_younggender
```

`## [1] 0.3885714`

The gini value for gender among young speakers is 0.3886.

We continue by inspecting the status distribution.

```
# calculate Gini for Status
# inspect distribution
<- table(young$LikeUser, young$Status)
tbyoungstatus tbyoungstatus
```

```
##
## high low
## no 11 23
## yes 57 35
```

We now calculate the gini value for status.

```
# calculate Gini for status
# calculate Gini for low
<- 1-(tbyoungstatus[2,2]/sum(tbyoungstatus[,2]))^2 - (tbyoungstatus[1,2]/sum(tbyoungstatus[,2]))^2
gini_younglow # calculate Gini for high
<- 1-(tbyoungstatus[2,1]/sum(tbyoungstatus[,1]))^2 - (tbyoungstatus[1,1]/sum(tbyoungstatus[,1]))^2
gini_younghigh # # calculate weighted average of Gini for status
<- sum(tbyoungstatus[,2])/sum(tbyoungstatus)* gini_younglow + sum(tbyoungstatus[,1])/sum(tbyoungstatus) * gini_younghigh
gini_youngstatus gini_youngstatus
```

`## [1] 0.3666651`

Since the gini value for status (0.3667) is lower than the gini value for gender (0.3886), we split by status.

We would continue to calculate the gini values and always split at the lowest gini levels until we reach a leaf node. Then, we would continue doing the same for the remaining branches until the entire data is binned into different leaf nodes.

In addition to plotting the decision tree, we can also check its accuracy. To do so, we predict the use of *like* based on the decision tree and compare them to the observed uses of *like*. Then we use the `confusionMatrix`

function from the `caret`

package to get an overview of the accuracy statistics.

```
<- as.factor(ifelse(predict(dtree)[,2] > .5, "yes", "no"))
dtreeprediction confusionMatrix(dtreeprediction, citdata$LikeUser)
```

The conditional inference tree has an accuracy of 72.9 percent which is significantly better than the base-line accuracy of 53.0 percent (No Information Rate \(*\) 100). To understand what the other statistics refer to and how they are calculated, run the command `?confusionMatrix`

.

## Splitting numeric, ordinal, and true categorical variables

While it is rather straight forward to calculate the Gini values for categorical variables, it may not seem quite as apparent how to calculate splits for numeric or ordinal variables. To illustrate how the algorithm works on such variables, consider the example data set shown below.

Age | LikeUser |
---|---|

15 | yes |

37 | no |

63 | no |

42 | yes |

22 | yes |

27 | yes |

In a first step, we order the numeric variable so that we arrive at the following table.

Age | LikeUser |
---|---|

15 | yes |

22 | yes |

27 | yes |

37 | no |

42 | yes |

63 | no |

Next, we calculate the means for each level of “Age”.

Age | LikeUser |
---|---|

15.0 | yes |

18.5 | |

22.0 | yes |

24.5 | |

27.0 | yes |

32.0 | |

37.0 | no |

39.5 | |

42.0 | yes |

52.5 |

Now, we calculate the Gini values for each average level of age. How this is done is shown below for the first split.

\[\begin{equation} G_{x} = 1 - ( p_{1} )^{2} - ( p_{0} )^{2} \end{equation}\]

For an age smaller than 18.5 this would mean:

\[\begin{equation} G_{youngerthan18.5} = 1-(\frac{1} {1+0})^{2} - (\frac{0} {1+0})^{2} = 0.0 \end{equation}\]

For an age greater than 18.5, we calculate G or Gini as follows:

\[\begin{equation} G_{olerthan18.5} = 1-(\frac{2} {2+3})^{2} - (\frac{3} {2+3})^{2} = 0.48 \end{equation}\]

Now, we calculate the Gini for that split as we have done above.

\[\begin{equation} G_{split18.5} = \frac{N_{youngerthan18.5}} {N_{Total}} \times G_{youngerthan18.5} + \frac{N_{olderthan18.5}} {N_{Total}} \times G_{olderthan18.5} G_{split18.5} = \frac{1} {6} \times 0.0 + \frac{5} {6} \times 0.48 = 0.4 \end{equation}\]

We then have to calculate the gini values for all possible age splits which yields the following results:

```
# 18.5
1-(1/(1+0))^2 - (0/(1+0))^2
1-(2/(2+3))^2 - (3/(2+3))^2
1/6 * 0.0 + 5/6 * 0.48
# 24.4
1-(2/(2+0))^2 - (0/(2+0))^2
1-(3/(3+1))^2 - (2/(3+1))^2
2/6 * 0.0 + 4/6 * 0.1875
# 32
1-(3/(3+0))^2 - (0/(3+0))^2
1-(1/(1+2))^2 - (2/(1+2))^2
3/6 * 0.0 + 3/6 * 0.4444444
# 39.5
1-(3/(3+1))^2 - (1/(3+1))^2
1-(1/(1+1))^2 - (1/(1+1))^2
4/6 * 0.375 + 2/6 * 0.5
# 52.5
1-(4/(4+1))^2 - (1/(4+1))^2
1-(0/(0+1))^2 - (1/(0+1))^2
5/6 * 0.32 + 1/6 * 0.0
```

AgeSplit | Gini |
---|---|

18.5 | 0.400 |

24.5 | 0.500 |

32.0 | 0.444 |

39.5 | 0.410 |

52.5 | 0.267 |

The split at 52.5 years of age has the lowest Gini value. Accordingly, we would split the data between speakers who are younger than 52.5 and speakers who are older than 52.5 years of age. The lowest Gini value for any age split would also be the Gini value that would be compared to other variables.

The same procedure that we have used to determine potential splits for a numeric variable would apply to an ordinal variable with only two differences:

- The Gini values are calculated for the actual levels and not the means between variable levels.
- The Gini value is nor calculated for the lowest and highest level as the calculation of the Gini values is impossible for extreme values. Extreme levels can, therefore, not serve as a potential split location.

When dealing with categorical variables with more than two levels, the situation is slightly more complex as we would also have to calculate the Gini values for combinations of variable levels. While the calculations are, in principle, analogous to the ones performed for binary of nominal categorical variables, we would also have to check if combinations would lead to improved splits. For instance, imagine we have a variable with categories A, B, and C. In such cases we would not only have to calculate the Gini scores for A, B, and C but also for A plus B, A plus C, and B plus C. Note that we ignore the combination A plus B plus C as this combination would include all other potential combinations.

### References

*Briefings in Bioinformatics*16 (2): 338–45. https://academic.oup.com/bib/article/16/2/338/246566.

*Statistics for Linguistics Using r: A Practical Introduction*. Berlin & New York: Mouton de Gruyter.