# Binary Decision Trees

Every vector is made up of m features, so each of them is a candidate for the creation of a node based on a tuple (feature, threshold):

## Single splitting node

According to the feature and the threshold, the structure of the tree will change. Intuitively, you should pick the feature that best separates your data. In other words, a perfectly separating feature will only be present in a node, and the two subsequent branches won?t be based on it anymore. These conditions guarantee the convergence of the tree toward the final leaves, whose uncertainty is minimized. In real problems, however, this is often impossible, so it?s necessary to find the feature that minimizes the number of decision steps that follow on from this.

For example, consider a class of students where all male students have dark hair and all female students have blonde hair, while both subsets have samples of different sizes. If your task is to determine the composition of the class, you can start with the following subdivision:

However, the Dark color? Block will contain both males and females (which are the targets you want to classify). This concept is expressed using the term purity (or, more often, its opposite concept, impurity). An ideal scenario is based on nodes where the impurity is null so that all subsequent decisions will be taken only on the remaining features. You can simply start from the color block:

The two resulting sets are now pure according to the color feature and this will be enough for your task. If you need further details, such as hair length, other nodes must be added; their impurity won?t be null because you know that there are, for example, both Male and Female students with long hair.

More formally, suppose you define the selection tuple as follows:

Here, the first element is the index of the feature you want to use to split your dataset at a certain node (it will be the entire dataset only at the beginning; after each step, the number of samples decreases), while the second is the threshold that determines left and right branches. The choice of the best threshold is a fundamental element because it determines the structure of the tree and therefore its performance. The goal is to reduce the residual impurity in the least number of splits to have a very short decision path between the sample data and the classification result.

You can also define a total impurity measure by considering the two branches:

Here, D is the whole dataset at the selected node, Dleft and Dright are the resulting subsets (by applying the selection tuple), and I represents the impurity measures.

## Impurity measures

To define the most frequently used impurity measures, you need to consider the total number of target classes:

In a certain node, j, you can define the probability p(y = i|Node = j), where i is an index [0, P-1] associated with each class. In other words, according to a frequentist approach, this value is the ratio between the number of samples belonging to class i and assigned to node j and the total number of samples belonging to the selected node:

## Gini impurity index

The Gini impurity index is defined as follows:

Here, the sum is always extended to all classes. This is a very common measure and it?s used as a default value by scikit-learn. Given a sample, the Gini impurity measures the probability of a misclassification if a label is randomly chosen using the probability distribution of the branch. The index reaches its minimum (0.0) when all the samples of a node are classified into a single category.

## Cross-entropy impurity index

The cross-entropy measure is defined as follows:

This measure is based on information theory, and assumes null values when samples belonging to a single class are present in a split, while it is at its maximum when there?s a uniform distribution among classes (which is one of the worst cases in Decision Trees because it means that there are still many decision steps until the final classification). This index is very similar to the Gini impurity, even though, more formally, cross-entropy allows you to select the split that minimizes uncertainty about the classification, while the Gini impurity minimizes the probability of misclassification.

The concept of mutual information is defined as I(X; Y) = H(X) ? H(X|Y), as the amount of information shared by both variables, or the amount of information about X that you can obtain through knowledge of Y. It?s also helpful to consider the data generating process, p(x), and the conditional probability, p(x|y). It?s easy to prove that the mutual information is the expected value of the Kullback-Leibler divergence between them, with respect to the conditioned variable y:

Therefore, this is when I(X; Y) ? 0, p(x) ? p(x|y) and knowledge of Y doesn?t provide any useful information about X. Conversely, higher I(X; Y) values imply an average strong divergence between the marginal distribution p(x) and the conditional p(x|y). The definition of conditional probability can provide better insight:

Here, the two variables are not statistically independent and knowledge of Y must provide proportional information about X. You can use this concept to define the information gain provided by a split (which is formally equivalent to the mutual information):

In this case, you are interested in the distributions of the parent node and the children. Therefore, when growing a tree, start by selecting the split that provides the highest information gain. This guarantee minimization of the impurities of the subsequent nodes because, in general, the most relevant features are selected at the beginning and the next one is reserved for fine-tuning. The growth of the tree proceeds until one of the following conditions is verified:

All nodes are pure

The information gain is null

The maximum depth has been reached

## Misclassification impurity index

The misclassification impurity index is the simplest index and is defined as follows:

The interpretation is straightforward but, unfortunately, in terms of quality performance, this index is not the best choice because it?s not particularly sensitive to different probability distributions. In all of these cases, Gini or cross-entropy indexes are the most natural choice.

## Feature importance

When growing a Decision Tree with a multidimensional dataset, it can be useful to evaluate the importance of each feature in predicting the output values. Decision Trees offer a different approach based on the impurity reduction determined by every single feature. In particular, considering a feature, x(i), its importance can be determined as follows:

The sum is extended to all nodes where x(i) is used, and Nk is the number of samples reaching the node, k. Therefore, the importance is a weighted sum of all impurity reductions computed, considering only the nodes where the feature is used to split them. If the Gini impurity index is adopted, this measure is also called Gini importance.